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