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