1//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines structures to encapsulate information gleaned from the
10// target register and register class definitions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H
15#define LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H
16
17#include "CodeGenHwModes.h"
18#include "InfoByHwMode.h"
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/SparseBitVector.h"
27#include "llvm/ADT/StringMap.h"
28#include "llvm/ADT/StringRef.h"
29#include "llvm/MC/LaneBitmask.h"
30#include "llvm/Support/ErrorHandling.h"
31#include "llvm/TableGen/Record.h"
32#include "llvm/TableGen/SetTheory.h"
33#include <cassert>
34#include <cstdint>
35#include <deque>
36#include <functional>
37#include <list>
38#include <map>
39#include <memory>
40#include <optional>
41#include <string>
42#include <utility>
43#include <vector>
44
45namespace llvm {
46
47class CodeGenRegBank;
48
49/// Used to encode a step in a register lane mask transformation.
50/// Mask the bits specified in Mask, then rotate them Rol bits to the left
51/// assuming a wraparound at 32bits.
52struct MaskRolPair {
53 LaneBitmask Mask;
54 uint8_t RotateLeft;
55
56 bool operator==(const MaskRolPair Other) const {
57 return Mask == Other.Mask && RotateLeft == Other.RotateLeft;
58 }
59 bool operator!=(const MaskRolPair Other) const {
60 return Mask != Other.Mask || RotateLeft != Other.RotateLeft;
61 }
62};
63
64/// CodeGenSubRegIndex - Represents a sub-register index.
65class CodeGenSubRegIndex {
66 Record *const TheDef;
67 std::string Name;
68 std::string Namespace;
69
70public:
71 SubRegRangeByHwMode Range;
72 const unsigned EnumValue;
73 mutable LaneBitmask LaneMask;
74 mutable SmallVector<MaskRolPair, 1> CompositionLaneMaskTransform;
75
76 /// A list of subregister indexes concatenated resulting in this
77 /// subregister index. This is the reverse of CodeGenRegBank::ConcatIdx.
78 SmallVector<CodeGenSubRegIndex *, 4> ConcatenationOf;
79
80 // Are all super-registers containing this SubRegIndex covered by their
81 // sub-registers?
82 bool AllSuperRegsCovered;
83 // A subregister index is "artificial" if every subregister obtained
84 // from applying this index is artificial. Artificial subregister
85 // indexes are not used to create new register classes.
86 bool Artificial;
87
88 CodeGenSubRegIndex(Record *R, unsigned Enum, const CodeGenHwModes &CGH);
89 CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum);
90 CodeGenSubRegIndex(CodeGenSubRegIndex &) = delete;
91
92 const std::string &getName() const { return Name; }
93 const std::string &getNamespace() const { return Namespace; }
94 std::string getQualifiedName() const;
95
96 // Map of composite subreg indices.
97 typedef std::map<CodeGenSubRegIndex *, CodeGenSubRegIndex *,
98 deref<std::less<>>>
99 CompMap;
100
101 // Returns the subreg index that results from composing this with Idx.
102 // Returns NULL if this and Idx don't compose.
103 CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const {
104 CompMap::const_iterator I = Composed.find(x: Idx);
105 return I == Composed.end() ? nullptr : I->second;
106 }
107
108 // Add a composite subreg index: this+A = B.
109 // Return a conflicting composite, or NULL
110 CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, CodeGenSubRegIndex *B,
111 const CodeGenHwModes &CGH) {
112 assert(A && B);
113 std::pair<CompMap::iterator, bool> Ins = Composed.insert(x: std::pair(A, B));
114
115 // Synthetic subreg indices that aren't contiguous (for instance ARM
116 // register tuples) don't have a bit range, so it's OK to let
117 // B->Offset == -1. For the other cases, accumulate the offset and set
118 // the size here. Only do so if there is no offset yet though.
119 unsigned NumModes = CGH.getNumModeIds();
120 // Skip default mode.
121 for (unsigned M = 0; M < NumModes; ++M) {
122 // Handle DefaultMode last.
123 if (M == DefaultMode)
124 continue;
125 SubRegRange &Range = this->Range.get(Mode: M);
126 SubRegRange &ARange = A->Range.get(Mode: M);
127 SubRegRange &BRange = B->Range.get(Mode: M);
128
129 if (Range.Offset != (uint16_t)-1 && ARange.Offset != (uint16_t)-1 &&
130 BRange.Offset == (uint16_t)-1) {
131 BRange.Offset = Range.Offset + ARange.Offset;
132 BRange.Size = ARange.Size;
133 }
134 }
135
136 // Now handle default.
137 SubRegRange &Range = this->Range.get(Mode: DefaultMode);
138 SubRegRange &ARange = A->Range.get(Mode: DefaultMode);
139 SubRegRange &BRange = B->Range.get(Mode: DefaultMode);
140 if (Range.Offset != (uint16_t)-1 && ARange.Offset != (uint16_t)-1 &&
141 BRange.Offset == (uint16_t)-1) {
142 BRange.Offset = Range.Offset + ARange.Offset;
143 BRange.Size = ARange.Size;
144 }
145
146 return (Ins.second || Ins.first->second == B) ? nullptr : Ins.first->second;
147 }
148
149 // Update the composite maps of components specified in 'ComposedOf'.
150 void updateComponents(CodeGenRegBank &);
151
152 // Return the map of composites.
153 const CompMap &getComposites() const { return Composed; }
154
155 // Compute LaneMask from Composed. Return LaneMask.
156 LaneBitmask computeLaneMask() const;
157
158 void setConcatenationOf(ArrayRef<CodeGenSubRegIndex *> Parts);
159
160 /// Replaces subregister indexes in the `ConcatenationOf` list with
161 /// list of subregisters they are composed of (if any). Do this recursively.
162 void computeConcatTransitiveClosure();
163
164 bool operator<(const CodeGenSubRegIndex &RHS) const {
165 return this->EnumValue < RHS.EnumValue;
166 }
167
168private:
169 CompMap Composed;
170};
171
172/// CodeGenRegister - Represents a register definition.
173class CodeGenRegister {
174public:
175 Record *TheDef;
176 unsigned EnumValue;
177 std::vector<int64_t> CostPerUse;
178 bool CoveredBySubRegs = true;
179 bool HasDisjunctSubRegs = false;
180 bool Artificial = true;
181 bool Constant = false;
182
183 // Map SubRegIndex -> Register.
184 typedef std::map<CodeGenSubRegIndex *, CodeGenRegister *, deref<std::less<>>>
185 SubRegMap;
186
187 CodeGenRegister(Record *R, unsigned Enum);
188
189 StringRef getName() const;
190
191 // Extract more information from TheDef. This is used to build an object
192 // graph after all CodeGenRegister objects have been created.
193 void buildObjectGraph(CodeGenRegBank &);
194
195 // Lazily compute a map of all sub-registers.
196 // This includes unique entries for all sub-sub-registers.
197 const SubRegMap &computeSubRegs(CodeGenRegBank &);
198
199 // Compute extra sub-registers by combining the existing sub-registers.
200 void computeSecondarySubRegs(CodeGenRegBank &);
201
202 // Add this as a super-register to all sub-registers after the sub-register
203 // graph has been built.
204 void computeSuperRegs(CodeGenRegBank &);
205
206 const SubRegMap &getSubRegs() const {
207 assert(SubRegsComplete && "Must precompute sub-registers");
208 return SubRegs;
209 }
210
211 // Add sub-registers to OSet following a pre-order defined by the .td file.
212 void addSubRegsPreOrder(SetVector<const CodeGenRegister *> &OSet,
213 CodeGenRegBank &) const;
214
215 // Return the sub-register index naming Reg as a sub-register of this
216 // register. Returns NULL if Reg is not a sub-register.
217 CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const {
218 return SubReg2Idx.lookup(Val: Reg);
219 }
220
221 typedef std::vector<const CodeGenRegister *> SuperRegList;
222
223 // Get the list of super-registers in topological order, small to large.
224 // This is valid after computeSubRegs visits all registers during RegBank
225 // construction.
226 const SuperRegList &getSuperRegs() const {
227 assert(SubRegsComplete && "Must precompute sub-registers");
228 return SuperRegs;
229 }
230
231 // Get the list of ad hoc aliases. The graph is symmetric, so the list
232 // contains all registers in 'Aliases', and all registers that mention this
233 // register in 'Aliases'.
234 ArrayRef<CodeGenRegister *> getExplicitAliases() const {
235 return ExplicitAliases;
236 }
237
238 // Get the topological signature of this register. This is a small integer
239 // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have
240 // identical sub-register structure. That is, they support the same set of
241 // sub-register indices mapping to the same kind of sub-registers
242 // (TopoSig-wise).
243 unsigned getTopoSig() const {
244 assert(SuperRegsComplete && "TopoSigs haven't been computed yet.");
245 return TopoSig;
246 }
247
248 // List of register units in ascending order.
249 typedef SparseBitVector<> RegUnitList;
250 typedef SmallVector<LaneBitmask, 16> RegUnitLaneMaskList;
251
252 // How many entries in RegUnitList are native?
253 RegUnitList NativeRegUnits;
254
255 // Get the list of register units.
256 // This is only valid after computeSubRegs() completes.
257 const RegUnitList &getRegUnits() const { return RegUnits; }
258
259 ArrayRef<LaneBitmask> getRegUnitLaneMasks() const {
260 return ArrayRef(RegUnitLaneMasks).slice(N: 0, M: NativeRegUnits.count());
261 }
262
263 // Get the native register units. This is a prefix of getRegUnits().
264 RegUnitList getNativeRegUnits() const { return NativeRegUnits; }
265
266 void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) {
267 RegUnitLaneMasks = LaneMasks;
268 }
269
270 // Inherit register units from subregisters.
271 // Return true if the RegUnits changed.
272 bool inheritRegUnits(CodeGenRegBank &RegBank);
273
274 // Adopt a register unit for pressure tracking.
275 // A unit is adopted iff its unit number is >= NativeRegUnits.count().
276 void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); }
277
278 // Get the sum of this register's register unit weights.
279 unsigned getWeight(const CodeGenRegBank &RegBank) const;
280
281 // Canonically ordered set.
282 typedef std::vector<const CodeGenRegister *> Vec;
283
284private:
285 bool SubRegsComplete;
286 bool SuperRegsComplete;
287 unsigned TopoSig;
288
289 // The sub-registers explicit in the .td file form a tree.
290 SmallVector<CodeGenSubRegIndex *, 8> ExplicitSubRegIndices;
291 SmallVector<CodeGenRegister *, 8> ExplicitSubRegs;
292
293 // Explicit ad hoc aliases, symmetrized to form an undirected graph.
294 SmallVector<CodeGenRegister *, 8> ExplicitAliases;
295
296 // Super-registers where this is the first explicit sub-register.
297 SuperRegList LeadingSuperRegs;
298
299 SubRegMap SubRegs;
300 SuperRegList SuperRegs;
301 DenseMap<const CodeGenRegister *, CodeGenSubRegIndex *> SubReg2Idx;
302 RegUnitList RegUnits;
303 RegUnitLaneMaskList RegUnitLaneMasks;
304};
305
306inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) {
307 return A.EnumValue < B.EnumValue;
308}
309
310inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) {
311 return A.EnumValue == B.EnumValue;
312}
313
314class CodeGenRegisterClass {
315 CodeGenRegister::Vec Members;
316 // Allocation orders. Order[0] always contains all registers in Members.
317 std::vector<SmallVector<Record *, 16>> Orders;
318 // Bit mask of sub-classes including this, indexed by their EnumValue.
319 BitVector SubClasses;
320 // List of super-classes, topologocally ordered to have the larger classes
321 // first. This is the same as sorting by EnumValue.
322 SmallVector<CodeGenRegisterClass *, 4> SuperClasses;
323 Record *TheDef;
324 std::string Name;
325
326 // For a synthesized class, inherit missing properties from the nearest
327 // super-class.
328 void inheritProperties(CodeGenRegBank &);
329
330 // Map SubRegIndex -> sub-class. This is the largest sub-class where all
331 // registers have a SubRegIndex sub-register.
332 DenseMap<const CodeGenSubRegIndex *, CodeGenRegisterClass *>
333 SubClassWithSubReg;
334
335 // Map SubRegIndex -> set of super-reg classes. This is all register
336 // classes SuperRC such that:
337 //
338 // R:SubRegIndex in this RC for all R in SuperRC.
339 //
340 DenseMap<const CodeGenSubRegIndex *, SmallPtrSet<CodeGenRegisterClass *, 8>>
341 SuperRegClasses;
342
343 // Bit vector of TopoSigs for the registers in this class. This will be
344 // very sparse on regular architectures.
345 BitVector TopoSigs;
346
347public:
348 unsigned EnumValue;
349 StringRef Namespace;
350 SmallVector<ValueTypeByHwMode, 4> VTs;
351 RegSizeInfoByHwMode RSI;
352 int CopyCost;
353 bool Allocatable;
354 StringRef AltOrderSelect;
355 uint8_t AllocationPriority;
356 bool GlobalPriority;
357 uint8_t TSFlags;
358 /// Contains the combination of the lane masks of all subregisters.
359 LaneBitmask LaneMask;
360 /// True if there are at least 2 subregisters which do not interfere.
361 bool HasDisjunctSubRegs;
362 bool CoveredBySubRegs;
363 /// A register class is artificial if all its members are artificial.
364 bool Artificial;
365 /// Generate register pressure set for this register class and any class
366 /// synthesized from it.
367 bool GeneratePressureSet;
368
369 // Return the Record that defined this class, or NULL if the class was
370 // created by TableGen.
371 Record *getDef() const { return TheDef; }
372
373 std::string getNamespaceQualification() const;
374 const std::string &getName() const { return Name; }
375 std::string getQualifiedName() const;
376 std::string getIdName() const;
377 std::string getQualifiedIdName() const;
378 ArrayRef<ValueTypeByHwMode> getValueTypes() const { return VTs; }
379 unsigned getNumValueTypes() const { return VTs.size(); }
380 bool hasType(const ValueTypeByHwMode &VT) const;
381
382 const ValueTypeByHwMode &getValueTypeNum(unsigned VTNum) const {
383 if (VTNum < VTs.size())
384 return VTs[VTNum];
385 llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!");
386 }
387
388 // Return true if this class contains the register.
389 bool contains(const CodeGenRegister *) const;
390
391 // Returns true if RC is a subclass.
392 // RC is a sub-class of this class if it is a valid replacement for any
393 // instruction operand where a register of this classis required. It must
394 // satisfy these conditions:
395 //
396 // 1. All RC registers are also in this.
397 // 2. The RC spill size must not be smaller than our spill size.
398 // 3. RC spill alignment must be compatible with ours.
399 //
400 bool hasSubClass(const CodeGenRegisterClass *RC) const {
401 return SubClasses.test(Idx: RC->EnumValue);
402 }
403
404 // getSubClassWithSubReg - Returns the largest sub-class where all
405 // registers have a SubIdx sub-register.
406 CodeGenRegisterClass *
407 getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const {
408 return SubClassWithSubReg.lookup(Val: SubIdx);
409 }
410
411 /// Find largest subclass where all registers have SubIdx subregisters in
412 /// SubRegClass and the largest subregister class that contains those
413 /// subregisters without (as far as possible) also containing additional
414 /// registers.
415 ///
416 /// This can be used to find a suitable pair of classes for subregister
417 /// copies. \return std::pair<SubClass, SubRegClass> where SubClass is a
418 /// SubClass is a class where every register has SubIdx and SubRegClass is a
419 /// class where every register is covered by the SubIdx subregister of
420 /// SubClass.
421 std::optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>
422 getMatchingSubClassWithSubRegs(CodeGenRegBank &RegBank,
423 const CodeGenSubRegIndex *SubIdx) const;
424
425 void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx,
426 CodeGenRegisterClass *SubRC) {
427 SubClassWithSubReg[SubIdx] = SubRC;
428 }
429
430 // getSuperRegClasses - Returns a bit vector of all register classes
431 // containing only SubIdx super-registers of this class.
432 void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx,
433 BitVector &Out) const;
434
435 // addSuperRegClass - Add a class containing only SubIdx super-registers.
436 void addSuperRegClass(CodeGenSubRegIndex *SubIdx,
437 CodeGenRegisterClass *SuperRC) {
438 SuperRegClasses[SubIdx].insert(Ptr: SuperRC);
439 }
440
441 // getSubClasses - Returns a constant BitVector of subclasses indexed by
442 // EnumValue.
443 // The SubClasses vector includes an entry for this class.
444 const BitVector &getSubClasses() const { return SubClasses; }
445
446 // getSuperClasses - Returns a list of super classes ordered by EnumValue.
447 // The array does not include an entry for this class.
448 ArrayRef<CodeGenRegisterClass *> getSuperClasses() const {
449 return SuperClasses;
450 }
451
452 // Returns an ordered list of class members.
453 // The order of registers is the same as in the .td file.
454 // No = 0 is the default allocation order, No = 1 is the first alternative.
455 ArrayRef<Record *> getOrder(unsigned No = 0) const { return Orders[No]; }
456
457 // Return the total number of allocation orders available.
458 unsigned getNumOrders() const { return Orders.size(); }
459
460 // Get the set of registers. This set contains the same registers as
461 // getOrder(0).
462 const CodeGenRegister::Vec &getMembers() const { return Members; }
463
464 // Get a bit vector of TopoSigs present in this register class.
465 const BitVector &getTopoSigs() const { return TopoSigs; }
466
467 // Get a weight of this register class.
468 unsigned getWeight(const CodeGenRegBank &) const;
469
470 // Populate a unique sorted list of units from a register set.
471 void buildRegUnitSet(const CodeGenRegBank &RegBank,
472 std::vector<unsigned> &RegUnits) const;
473
474 CodeGenRegisterClass(CodeGenRegBank &, Record *R);
475 CodeGenRegisterClass(CodeGenRegisterClass &) = delete;
476
477 // A key representing the parts of a register class used for forming
478 // sub-classes. Note the ordering provided by this key is not the same as
479 // the topological order used for the EnumValues.
480 struct Key {
481 const CodeGenRegister::Vec *Members;
482 RegSizeInfoByHwMode RSI;
483
484 Key(const CodeGenRegister::Vec *M, const RegSizeInfoByHwMode &I)
485 : Members(M), RSI(I) {}
486
487 Key(const CodeGenRegisterClass &RC)
488 : Members(&RC.getMembers()), RSI(RC.RSI) {}
489
490 // Lexicographical order of (Members, RegSizeInfoByHwMode).
491 bool operator<(const Key &) const;
492 };
493
494 // Create a non-user defined register class.
495 CodeGenRegisterClass(CodeGenRegBank &, StringRef Name, Key Props);
496
497 // Called by CodeGenRegBank::CodeGenRegBank().
498 static void computeSubClasses(CodeGenRegBank &);
499
500 // Get ordering value among register base classes.
501 std::optional<int> getBaseClassOrder() const {
502 if (TheDef && !TheDef->isValueUnset(FieldName: "BaseClassOrder"))
503 return TheDef->getValueAsInt(FieldName: "BaseClassOrder");
504 return {};
505 }
506};
507
508// Register categories are used when we need to deterine the category a
509// register falls into (GPR, vector, fixed, etc.) without having to know
510// specific information about the target architecture.
511class CodeGenRegisterCategory {
512 Record *TheDef;
513 std::string Name;
514 std::list<CodeGenRegisterClass *> Classes;
515
516public:
517 CodeGenRegisterCategory(CodeGenRegBank &, Record *R);
518 CodeGenRegisterCategory(CodeGenRegisterCategory &) = delete;
519
520 // Return the Record that defined this class, or NULL if the class was
521 // created by TableGen.
522 Record *getDef() const { return TheDef; }
523
524 std::string getName() const { return Name; }
525 std::list<CodeGenRegisterClass *> getClasses() const { return Classes; }
526};
527
528// Register units are used to model interference and register pressure.
529// Every register is assigned one or more register units such that two
530// registers overlap if and only if they have a register unit in common.
531//
532// Normally, one register unit is created per leaf register. Non-leaf
533// registers inherit the units of their sub-registers.
534struct RegUnit {
535 // Weight assigned to this RegUnit for estimating register pressure.
536 // This is useful when equalizing weights in register classes with mixed
537 // register topologies.
538 unsigned Weight;
539
540 // Each native RegUnit corresponds to one or two root registers. The full
541 // set of registers containing this unit can be computed as the union of
542 // these two registers and their super-registers.
543 const CodeGenRegister *Roots[2];
544
545 // Index into RegClassUnitSets where we can find the list of UnitSets that
546 // contain this unit.
547 unsigned RegClassUnitSetsIdx;
548 // A register unit is artificial if at least one of its roots is
549 // artificial.
550 bool Artificial;
551
552 RegUnit() : Weight(0), RegClassUnitSetsIdx(0), Artificial(false) {
553 Roots[0] = Roots[1] = nullptr;
554 }
555
556 ArrayRef<const CodeGenRegister *> getRoots() const {
557 assert(!(Roots[1] && !Roots[0]) && "Invalid roots array");
558 return ArrayRef(Roots, !!Roots[0] + !!Roots[1]);
559 }
560};
561
562// Each RegUnitSet is a sorted vector with a name.
563struct RegUnitSet {
564 typedef std::vector<unsigned>::const_iterator iterator;
565
566 std::string Name;
567 std::vector<unsigned> Units;
568 unsigned Weight = 0; // Cache the sum of all unit weights.
569 unsigned Order = 0; // Cache the sort key.
570
571 RegUnitSet(std::string Name) : Name(Name) {}
572};
573
574// Base vector for identifying TopoSigs. The contents uniquely identify a
575// TopoSig, only computeSuperRegs needs to know how.
576typedef SmallVector<unsigned, 16> TopoSigId;
577
578// CodeGenRegBank - Represent a target's registers and the relations between
579// them.
580class CodeGenRegBank {
581 SetTheory Sets;
582
583 const CodeGenHwModes &CGH;
584
585 std::deque<CodeGenSubRegIndex> SubRegIndices;
586 DenseMap<Record *, CodeGenSubRegIndex *> Def2SubRegIdx;
587
588 CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace);
589
590 typedef std::map<SmallVector<CodeGenSubRegIndex *, 8>, CodeGenSubRegIndex *>
591 ConcatIdxMap;
592 ConcatIdxMap ConcatIdx;
593
594 // Registers.
595 std::deque<CodeGenRegister> Registers;
596 StringMap<CodeGenRegister *> RegistersByName;
597 DenseMap<Record *, CodeGenRegister *> Def2Reg;
598 unsigned NumNativeRegUnits;
599
600 std::map<TopoSigId, unsigned> TopoSigs;
601
602 // Includes native (0..NumNativeRegUnits-1) and adopted register units.
603 SmallVector<RegUnit, 8> RegUnits;
604
605 // Register classes.
606 std::list<CodeGenRegisterClass> RegClasses;
607 DenseMap<Record *, CodeGenRegisterClass *> Def2RC;
608 typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass *> RCKeyMap;
609 RCKeyMap Key2RC;
610
611 // Register categories.
612 std::list<CodeGenRegisterCategory> RegCategories;
613 DenseMap<Record *, CodeGenRegisterCategory *> Def2RCat;
614 using RCatKeyMap =
615 std::map<CodeGenRegisterClass::Key, CodeGenRegisterCategory *>;
616 RCatKeyMap Key2RCat;
617
618 // Remember each unique set of register units. Initially, this contains a
619 // unique set for each register class. Simliar sets are coalesced with
620 // pruneUnitSets and new supersets are inferred during computeRegUnitSets.
621 std::vector<RegUnitSet> RegUnitSets;
622
623 // Map RegisterClass index to the index of the RegUnitSet that contains the
624 // class's units and any inferred RegUnit supersets.
625 //
626 // NOTE: This could grow beyond the number of register classes when we map
627 // register units to lists of unit sets. If the list of unit sets does not
628 // already exist for a register class, we create a new entry in this vector.
629 std::vector<std::vector<unsigned>> RegClassUnitSets;
630
631 // Give each register unit set an order based on sorting criteria.
632 std::vector<unsigned> RegUnitSetOrder;
633
634 // Keep track of synthesized definitions generated in TupleExpander.
635 std::vector<std::unique_ptr<Record>> SynthDefs;
636
637 // Add RC to *2RC maps.
638 void addToMaps(CodeGenRegisterClass *);
639
640 // Create a synthetic sub-class if it is missing.
641 CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC,
642 const CodeGenRegister::Vec *Membs,
643 StringRef Name);
644
645 // Infer missing register classes.
646 void computeInferredRegisterClasses();
647 void inferCommonSubClass(CodeGenRegisterClass *RC);
648 void inferSubClassWithSubReg(CodeGenRegisterClass *RC);
649
650 void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) {
651 inferMatchingSuperRegClass(RC, FirstSubRegRC: RegClasses.begin());
652 }
653
654 void inferMatchingSuperRegClass(
655 CodeGenRegisterClass *RC,
656 std::list<CodeGenRegisterClass>::iterator FirstSubRegRC);
657
658 // Iteratively prune unit sets.
659 void pruneUnitSets();
660
661 // Compute a weight for each register unit created during getSubRegs.
662 void computeRegUnitWeights();
663
664 // Create a RegUnitSet for each RegClass and infer superclasses.
665 void computeRegUnitSets();
666
667 // Populate the Composite map from sub-register relationships.
668 void computeComposites();
669
670 // Compute a lane mask for each sub-register index.
671 void computeSubRegLaneMasks();
672
673 /// Computes a lane mask for each register unit enumerated by a physical
674 /// register.
675 void computeRegUnitLaneMasks();
676
677public:
678 CodeGenRegBank(RecordKeeper &, const CodeGenHwModes &);
679 CodeGenRegBank(CodeGenRegBank &) = delete;
680
681 SetTheory &getSets() { return Sets; }
682
683 const CodeGenHwModes &getHwModes() const { return CGH; }
684
685 // Sub-register indices. The first NumNamedIndices are defined by the user
686 // in the .td files. The rest are synthesized such that all sub-registers
687 // have a unique name.
688 const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const {
689 return SubRegIndices;
690 }
691
692 // Find a SubRegIndex from its Record def or add to the list if it does
693 // not exist there yet.
694 CodeGenSubRegIndex *getSubRegIdx(Record *);
695
696 // Find a SubRegIndex from its Record def.
697 const CodeGenSubRegIndex *findSubRegIdx(const Record *Def) const;
698
699 // Find or create a sub-register index representing the A+B composition.
700 CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A,
701 CodeGenSubRegIndex *B);
702
703 // Find or create a sub-register index representing the concatenation of
704 // non-overlapping sibling indices.
705 CodeGenSubRegIndex *
706 getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &,
707 const CodeGenHwModes &CGH);
708
709 const std::deque<CodeGenRegister> &getRegisters() const { return Registers; }
710
711 const StringMap<CodeGenRegister *> &getRegistersByName() const {
712 return RegistersByName;
713 }
714
715 // Find a register from its Record def.
716 CodeGenRegister *getReg(Record *);
717
718 // Get a Register's index into the Registers array.
719 unsigned getRegIndex(const CodeGenRegister *Reg) const {
720 return Reg->EnumValue - 1;
721 }
722
723 // Return the number of allocated TopoSigs. The first TopoSig representing
724 // leaf registers is allocated number 0.
725 unsigned getNumTopoSigs() const { return TopoSigs.size(); }
726
727 // Find or create a TopoSig for the given TopoSigId.
728 // This function is only for use by CodeGenRegister::computeSuperRegs().
729 // Others should simply use Reg->getTopoSig().
730 unsigned getTopoSig(const TopoSigId &Id) {
731 return TopoSigs.insert(x: std::pair(Id, TopoSigs.size())).first->second;
732 }
733
734 // Create a native register unit that is associated with one or two root
735 // registers.
736 unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) {
737 RegUnit &RU = RegUnits.emplace_back();
738 RU.Roots[0] = R0;
739 RU.Roots[1] = R1;
740 RU.Artificial = R0->Artificial;
741 if (R1)
742 RU.Artificial |= R1->Artificial;
743 return RegUnits.size() - 1;
744 }
745
746 // Create a new non-native register unit that can be adopted by a register
747 // to increase its pressure. Note that NumNativeRegUnits is not increased.
748 unsigned newRegUnit(unsigned Weight) {
749 RegUnit &RU = RegUnits.emplace_back();
750 RU.Weight = Weight;
751 return RegUnits.size() - 1;
752 }
753
754 // Native units are the singular unit of a leaf register. Register aliasing
755 // is completely characterized by native units. Adopted units exist to give
756 // register additional weight but don't affect aliasing.
757 bool isNativeUnit(unsigned RUID) const { return RUID < NumNativeRegUnits; }
758
759 unsigned getNumNativeRegUnits() const { return NumNativeRegUnits; }
760
761 RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; }
762 const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; }
763
764 std::list<CodeGenRegisterClass> &getRegClasses() { return RegClasses; }
765
766 const std::list<CodeGenRegisterClass> &getRegClasses() const {
767 return RegClasses;
768 }
769
770 std::list<CodeGenRegisterCategory> &getRegCategories() {
771 return RegCategories;
772 }
773
774 const std::list<CodeGenRegisterCategory> &getRegCategories() const {
775 return RegCategories;
776 }
777
778 // Find a register class from its def.
779 CodeGenRegisterClass *getRegClass(const Record *) const;
780
781 /// getRegisterClassForRegister - Find the register class that contains the
782 /// specified physical register. If the register is not in a register
783 /// class, return null. If the register is in multiple classes, and the
784 /// classes have a superset-subset relationship and the same set of types,
785 /// return the superclass. Otherwise return null.
786 const CodeGenRegisterClass *getRegClassForRegister(Record *R);
787
788 // Analog of TargetRegisterInfo::getMinimalPhysRegClass. Unlike
789 // getRegClassForRegister, this tries to find the smallest class containing
790 // the physical register. If \p VT is specified, it will only find classes
791 // with a matching type
792 const CodeGenRegisterClass *
793 getMinimalPhysRegClass(Record *RegRecord, ValueTypeByHwMode *VT = nullptr);
794
795 // Get the sum of unit weights.
796 unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const {
797 unsigned Weight = 0;
798 for (unsigned Unit : Units)
799 Weight += getRegUnit(RUID: Unit).Weight;
800 return Weight;
801 }
802
803 unsigned getRegSetIDAt(unsigned Order) const {
804 return RegUnitSetOrder[Order];
805 }
806
807 const RegUnitSet &getRegSetAt(unsigned Order) const {
808 return RegUnitSets[RegUnitSetOrder[Order]];
809 }
810
811 // Increase a RegUnitWeight.
812 void increaseRegUnitWeight(unsigned RUID, unsigned Inc) {
813 getRegUnit(RUID).Weight += Inc;
814 }
815
816 // Get the number of register pressure dimensions.
817 unsigned getNumRegPressureSets() const { return RegUnitSets.size(); }
818
819 // Get a set of register unit IDs for a given dimension of pressure.
820 const RegUnitSet &getRegPressureSet(unsigned Idx) const {
821 return RegUnitSets[Idx];
822 }
823
824 // The number of pressure set lists may be larget than the number of
825 // register classes if some register units appeared in a list of sets that
826 // did not correspond to an existing register class.
827 unsigned getNumRegClassPressureSetLists() const {
828 return RegClassUnitSets.size();
829 }
830
831 // Get a list of pressure set IDs for a register class. Liveness of a
832 // register in this class impacts each pressure set in this list by the
833 // weight of the register. An exact solution requires all registers in a
834 // class to have the same class, but it is not strictly guaranteed.
835 ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const {
836 return RegClassUnitSets[RCIdx];
837 }
838
839 // Computed derived records such as missing sub-register indices.
840 void computeDerivedInfo();
841
842 // Compute the set of registers completely covered by the registers in Regs.
843 // The returned BitVector will have a bit set for each register in Regs,
844 // all sub-registers, and all super-registers that are covered by the
845 // registers in Regs.
846 //
847 // This is used to compute the mask of call-preserved registers from a list
848 // of callee-saves.
849 BitVector computeCoveredRegisters(ArrayRef<Record *> Regs);
850
851 // Bit mask of lanes that cover their registers. A sub-register index whose
852 // LaneMask is contained in CoveringLanes will be completely covered by
853 // another sub-register with the same or larger lane mask.
854 LaneBitmask CoveringLanes;
855
856 // Helper function for printing debug information. Handles artificial
857 // (non-native) reg units.
858 void printRegUnitName(unsigned Unit) const;
859};
860
861} // end namespace llvm
862
863#endif // LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H
864

source code of llvm/utils/TableGen/Common/CodeGenRegisters.h