Home | History | Annotate | Download | only in Target
      1 //=== Target/TargetRegisterInfo.h - Target Register Information -*- 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 describes an abstract interface used to get information about a
     11 // target machines register file.  This information is used for a variety of
     12 // purposed, especially register allocation.
     13 //
     14 //===----------------------------------------------------------------------===//
     15 
     16 #ifndef LLVM_TARGET_TARGETREGISTERINFO_H
     17 #define LLVM_TARGET_TARGETREGISTERINFO_H
     18 
     19 #include "llvm/ADT/ArrayRef.h"
     20 #include "llvm/CodeGen/MachineBasicBlock.h"
     21 #include "llvm/CodeGen/MachineValueType.h"
     22 #include "llvm/IR/CallingConv.h"
     23 #include "llvm/MC/MCRegisterInfo.h"
     24 #include <cassert>
     25 #include <functional>
     26 
     27 namespace llvm {
     28 
     29 class BitVector;
     30 class MachineFunction;
     31 class RegScavenger;
     32 template<class T> class SmallVectorImpl;
     33 class VirtRegMap;
     34 class raw_ostream;
     35 
     36 class TargetRegisterClass {
     37 public:
     38   typedef const MCPhysReg* iterator;
     39   typedef const MCPhysReg* const_iterator;
     40   typedef const MVT::SimpleValueType* vt_iterator;
     41   typedef const TargetRegisterClass* const * sc_iterator;
     42 
     43   // Instance variables filled by tablegen, do not use!
     44   const MCRegisterClass *MC;
     45   const vt_iterator VTs;
     46   const uint32_t *SubClassMask;
     47   const uint16_t *SuperRegIndices;
     48   const unsigned LaneMask;
     49   /// Classes with a higher priority value are assigned first by register
     50   /// allocators using a greedy heuristic. The value is in the range [0,63].
     51   const uint8_t AllocationPriority;
     52   /// Whether the class supports two (or more) disjunct subregister indices.
     53   const bool HasDisjunctSubRegs;
     54   const sc_iterator SuperClasses;
     55   ArrayRef<MCPhysReg> (*OrderFunc)(const MachineFunction&);
     56 
     57   /// getID() - Return the register class ID number.
     58   ///
     59   unsigned getID() const { return MC->getID(); }
     60 
     61   /// begin/end - Return all of the registers in this class.
     62   ///
     63   iterator       begin() const { return MC->begin(); }
     64   iterator         end() const { return MC->end(); }
     65 
     66   /// getNumRegs - Return the number of registers in this class.
     67   ///
     68   unsigned getNumRegs() const { return MC->getNumRegs(); }
     69 
     70   /// getRegister - Return the specified register in the class.
     71   ///
     72   unsigned getRegister(unsigned i) const {
     73     return MC->getRegister(i);
     74   }
     75 
     76   /// contains - Return true if the specified register is included in this
     77   /// register class.  This does not include virtual registers.
     78   bool contains(unsigned Reg) const {
     79     return MC->contains(Reg);
     80   }
     81 
     82   /// contains - Return true if both registers are in this class.
     83   bool contains(unsigned Reg1, unsigned Reg2) const {
     84     return MC->contains(Reg1, Reg2);
     85   }
     86 
     87   /// getSize - Return the size of the register in bytes, which is also the size
     88   /// of a stack slot allocated to hold a spilled copy of this register.
     89   unsigned getSize() const { return MC->getSize(); }
     90 
     91   /// getAlignment - Return the minimum required alignment for a register of
     92   /// this class.
     93   unsigned getAlignment() const { return MC->getAlignment(); }
     94 
     95   /// getCopyCost - Return the cost of copying a value between two registers in
     96   /// this class. A negative number means the register class is very expensive
     97   /// to copy e.g. status flag register classes.
     98   int getCopyCost() const { return MC->getCopyCost(); }
     99 
    100   /// isAllocatable - Return true if this register class may be used to create
    101   /// virtual registers.
    102   bool isAllocatable() const { return MC->isAllocatable(); }
    103 
    104   /// hasType - return true if this TargetRegisterClass has the ValueType vt.
    105   ///
    106   bool hasType(MVT vt) const {
    107     for(int i = 0; VTs[i] != MVT::Other; ++i)
    108       if (MVT(VTs[i]) == vt)
    109         return true;
    110     return false;
    111   }
    112 
    113   /// vt_begin / vt_end - Loop over all of the value types that can be
    114   /// represented by values in this register class.
    115   vt_iterator vt_begin() const {
    116     return VTs;
    117   }
    118 
    119   vt_iterator vt_end() const {
    120     vt_iterator I = VTs;
    121     while (*I != MVT::Other) ++I;
    122     return I;
    123   }
    124 
    125   /// hasSubClass - return true if the specified TargetRegisterClass
    126   /// is a proper sub-class of this TargetRegisterClass.
    127   bool hasSubClass(const TargetRegisterClass *RC) const {
    128     return RC != this && hasSubClassEq(RC);
    129   }
    130 
    131   /// hasSubClassEq - Returns true if RC is a sub-class of or equal to this
    132   /// class.
    133   bool hasSubClassEq(const TargetRegisterClass *RC) const {
    134     unsigned ID = RC->getID();
    135     return (SubClassMask[ID / 32] >> (ID % 32)) & 1;
    136   }
    137 
    138   /// hasSuperClass - return true if the specified TargetRegisterClass is a
    139   /// proper super-class of this TargetRegisterClass.
    140   bool hasSuperClass(const TargetRegisterClass *RC) const {
    141     return RC->hasSubClass(this);
    142   }
    143 
    144   /// hasSuperClassEq - Returns true if RC is a super-class of or equal to this
    145   /// class.
    146   bool hasSuperClassEq(const TargetRegisterClass *RC) const {
    147     return RC->hasSubClassEq(this);
    148   }
    149 
    150   /// getSubClassMask - Returns a bit vector of subclasses, including this one.
    151   /// The vector is indexed by class IDs, see hasSubClassEq() above for how to
    152   /// use it.
    153   const uint32_t *getSubClassMask() const {
    154     return SubClassMask;
    155   }
    156 
    157   /// getSuperRegIndices - Returns a 0-terminated list of sub-register indices
    158   /// that project some super-register class into this register class. The list
    159   /// has an entry for each Idx such that:
    160   ///
    161   ///   There exists SuperRC where:
    162   ///     For all Reg in SuperRC:
    163   ///       this->contains(Reg:Idx)
    164   ///
    165   const uint16_t *getSuperRegIndices() const {
    166     return SuperRegIndices;
    167   }
    168 
    169   /// getSuperClasses - Returns a NULL terminated list of super-classes.  The
    170   /// classes are ordered by ID which is also a topological ordering from large
    171   /// to small classes.  The list does NOT include the current class.
    172   sc_iterator getSuperClasses() const {
    173     return SuperClasses;
    174   }
    175 
    176   /// isASubClass - return true if this TargetRegisterClass is a subset
    177   /// class of at least one other TargetRegisterClass.
    178   bool isASubClass() const {
    179     return SuperClasses[0] != nullptr;
    180   }
    181 
    182   /// getRawAllocationOrder - Returns the preferred order for allocating
    183   /// registers from this register class in MF. The raw order comes directly
    184   /// from the .td file and may include reserved registers that are not
    185   /// allocatable. Register allocators should also make sure to allocate
    186   /// callee-saved registers only after all the volatiles are used. The
    187   /// RegisterClassInfo class provides filtered allocation orders with
    188   /// callee-saved registers moved to the end.
    189   ///
    190   /// The MachineFunction argument can be used to tune the allocatable
    191   /// registers based on the characteristics of the function, subtarget, or
    192   /// other criteria.
    193   ///
    194   /// By default, this method returns all registers in the class.
    195   ///
    196   ArrayRef<MCPhysReg> getRawAllocationOrder(const MachineFunction &MF) const {
    197     return OrderFunc ? OrderFunc(MF) : makeArrayRef(begin(), getNumRegs());
    198   }
    199 
    200   /// Returns the combination of all lane masks of register in this class.
    201   /// The lane masks of the registers are the combination of all lane masks
    202   /// of their subregisters.
    203   unsigned getLaneMask() const {
    204     return LaneMask;
    205   }
    206 };
    207 
    208 /// TargetRegisterInfoDesc - Extra information, not in MCRegisterDesc, about
    209 /// registers. These are used by codegen, not by MC.
    210 struct TargetRegisterInfoDesc {
    211   unsigned CostPerUse;          // Extra cost of instructions using register.
    212   bool inAllocatableClass;      // Register belongs to an allocatable regclass.
    213 };
    214 
    215 /// Each TargetRegisterClass has a per register weight, and weight
    216 /// limit which must be less than the limits of its pressure sets.
    217 struct RegClassWeight {
    218   unsigned RegWeight;
    219   unsigned WeightLimit;
    220 };
    221 
    222 /// TargetRegisterInfo base class - We assume that the target defines a static
    223 /// array of TargetRegisterDesc objects that represent all of the machine
    224 /// registers that the target has.  As such, we simply have to track a pointer
    225 /// to this array so that we can turn register number into a register
    226 /// descriptor.
    227 ///
    228 class TargetRegisterInfo : public MCRegisterInfo {
    229 public:
    230   typedef const TargetRegisterClass * const * regclass_iterator;
    231 private:
    232   const TargetRegisterInfoDesc *InfoDesc;     // Extra desc array for codegen
    233   const char *const *SubRegIndexNames;        // Names of subreg indexes.
    234   // Pointer to array of lane masks, one per sub-reg index.
    235   const unsigned *SubRegIndexLaneMasks;
    236 
    237   regclass_iterator RegClassBegin, RegClassEnd;   // List of regclasses
    238   unsigned CoveringLanes;
    239 
    240 protected:
    241   TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
    242                      regclass_iterator RegClassBegin,
    243                      regclass_iterator RegClassEnd,
    244                      const char *const *SRINames,
    245                      const unsigned *SRILaneMasks,
    246                      unsigned CoveringLanes);
    247   virtual ~TargetRegisterInfo();
    248 public:
    249 
    250   // Register numbers can represent physical registers, virtual registers, and
    251   // sometimes stack slots. The unsigned values are divided into these ranges:
    252   //
    253   //   0           Not a register, can be used as a sentinel.
    254   //   [1;2^30)    Physical registers assigned by TableGen.
    255   //   [2^30;2^31) Stack slots. (Rarely used.)
    256   //   [2^31;2^32) Virtual registers assigned by MachineRegisterInfo.
    257   //
    258   // Further sentinels can be allocated from the small negative integers.
    259   // DenseMapInfo<unsigned> uses -1u and -2u.
    260 
    261   /// isStackSlot - Sometimes it is useful the be able to store a non-negative
    262   /// frame index in a variable that normally holds a register. isStackSlot()
    263   /// returns true if Reg is in the range used for stack slots.
    264   ///
    265   /// Note that isVirtualRegister() and isPhysicalRegister() cannot handle stack
    266   /// slots, so if a variable may contains a stack slot, always check
    267   /// isStackSlot() first.
    268   ///
    269   static bool isStackSlot(unsigned Reg) {
    270     return int(Reg) >= (1 << 30);
    271   }
    272 
    273   /// stackSlot2Index - Compute the frame index from a register value
    274   /// representing a stack slot.
    275   static int stackSlot2Index(unsigned Reg) {
    276     assert(isStackSlot(Reg) && "Not a stack slot");
    277     return int(Reg - (1u << 30));
    278   }
    279 
    280   /// index2StackSlot - Convert a non-negative frame index to a stack slot
    281   /// register value.
    282   static unsigned index2StackSlot(int FI) {
    283     assert(FI >= 0 && "Cannot hold a negative frame index.");
    284     return FI + (1u << 30);
    285   }
    286 
    287   /// isPhysicalRegister - Return true if the specified register number is in
    288   /// the physical register namespace.
    289   static bool isPhysicalRegister(unsigned Reg) {
    290     assert(!isStackSlot(Reg) && "Not a register! Check isStackSlot() first.");
    291     return int(Reg) > 0;
    292   }
    293 
    294   /// isVirtualRegister - Return true if the specified register number is in
    295   /// the virtual register namespace.
    296   static bool isVirtualRegister(unsigned Reg) {
    297     assert(!isStackSlot(Reg) && "Not a register! Check isStackSlot() first.");
    298     return int(Reg) < 0;
    299   }
    300 
    301   /// virtReg2Index - Convert a virtual register number to a 0-based index.
    302   /// The first virtual register in a function will get the index 0.
    303   static unsigned virtReg2Index(unsigned Reg) {
    304     assert(isVirtualRegister(Reg) && "Not a virtual register");
    305     return Reg & ~(1u << 31);
    306   }
    307 
    308   /// index2VirtReg - Convert a 0-based index to a virtual register number.
    309   /// This is the inverse operation of VirtReg2IndexFunctor below.
    310   static unsigned index2VirtReg(unsigned Index) {
    311     return Index | (1u << 31);
    312   }
    313 
    314   /// getMinimalPhysRegClass - Returns the Register Class of a physical
    315   /// register of the given type, picking the most sub register class of
    316   /// the right type that contains this physreg.
    317   const TargetRegisterClass *
    318     getMinimalPhysRegClass(unsigned Reg, MVT VT = MVT::Other) const;
    319 
    320   /// getAllocatableClass - Return the maximal subclass of the given register
    321   /// class that is alloctable, or NULL.
    322   const TargetRegisterClass *
    323     getAllocatableClass(const TargetRegisterClass *RC) const;
    324 
    325   /// getAllocatableSet - Returns a bitset indexed by register number
    326   /// indicating if a register is allocatable or not. If a register class is
    327   /// specified, returns the subset for the class.
    328   BitVector getAllocatableSet(const MachineFunction &MF,
    329                               const TargetRegisterClass *RC = nullptr) const;
    330 
    331   /// getCostPerUse - Return the additional cost of using this register instead
    332   /// of other registers in its class.
    333   unsigned getCostPerUse(unsigned RegNo) const {
    334     return InfoDesc[RegNo].CostPerUse;
    335   }
    336 
    337   /// isInAllocatableClass - Return true if the register is in the allocation
    338   /// of any register class.
    339   bool isInAllocatableClass(unsigned RegNo) const {
    340     return InfoDesc[RegNo].inAllocatableClass;
    341   }
    342 
    343   /// getSubRegIndexName - Return the human-readable symbolic target-specific
    344   /// name for the specified SubRegIndex.
    345   const char *getSubRegIndexName(unsigned SubIdx) const {
    346     assert(SubIdx && SubIdx < getNumSubRegIndices() &&
    347            "This is not a subregister index");
    348     return SubRegIndexNames[SubIdx-1];
    349   }
    350 
    351   /// getSubRegIndexLaneMask - Return a bitmask representing the parts of a
    352   /// register that are covered by SubIdx.
    353   ///
    354   /// Lane masks for sub-register indices are similar to register units for
    355   /// physical registers. The individual bits in a lane mask can't be assigned
    356   /// any specific meaning. They can be used to check if two sub-register
    357   /// indices overlap.
    358   ///
    359   /// If the target has a register such that:
    360   ///
    361   ///   getSubReg(Reg, A) overlaps getSubReg(Reg, B)
    362   ///
    363   /// then:
    364   ///
    365   ///   (getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B)) != 0
    366   ///
    367   /// The converse is not necessarily true. If two lane masks have a common
    368   /// bit, the corresponding sub-registers may not overlap, but it can be
    369   /// assumed that they usually will.
    370   /// SubIdx == 0 is allowed, it has the lane mask ~0u.
    371   unsigned getSubRegIndexLaneMask(unsigned SubIdx) const {
    372     assert(SubIdx < getNumSubRegIndices() && "This is not a subregister index");
    373     return SubRegIndexLaneMasks[SubIdx];
    374   }
    375 
    376   /// The lane masks returned by getSubRegIndexLaneMask() above can only be
    377   /// used to determine if sub-registers overlap - they can't be used to
    378   /// determine if a set of sub-registers completely cover another
    379   /// sub-register.
    380   ///
    381   /// The X86 general purpose registers have two lanes corresponding to the
    382   /// sub_8bit and sub_8bit_hi sub-registers. Both sub_32bit and sub_16bit have
    383   /// lane masks '3', but the sub_16bit sub-register doesn't fully cover the
    384   /// sub_32bit sub-register.
    385   ///
    386   /// On the other hand, the ARM NEON lanes fully cover their registers: The
    387   /// dsub_0 sub-register is completely covered by the ssub_0 and ssub_1 lanes.
    388   /// This is related to the CoveredBySubRegs property on register definitions.
    389   ///
    390   /// This function returns a bit mask of lanes that completely cover their
    391   /// sub-registers. More precisely, given:
    392   ///
    393   ///   Covering = getCoveringLanes();
    394   ///   MaskA = getSubRegIndexLaneMask(SubA);
    395   ///   MaskB = getSubRegIndexLaneMask(SubB);
    396   ///
    397   /// If (MaskA & ~(MaskB & Covering)) == 0, then SubA is completely covered by
    398   /// SubB.
    399   unsigned getCoveringLanes() const { return CoveringLanes; }
    400 
    401   /// regsOverlap - Returns true if the two registers are equal or alias each
    402   /// other. The registers may be virtual register.
    403   bool regsOverlap(unsigned regA, unsigned regB) const {
    404     if (regA == regB) return true;
    405     if (isVirtualRegister(regA) || isVirtualRegister(regB))
    406       return false;
    407 
    408     // Regunits are numerically ordered. Find a common unit.
    409     MCRegUnitIterator RUA(regA, this);
    410     MCRegUnitIterator RUB(regB, this);
    411     do {
    412       if (*RUA == *RUB) return true;
    413       if (*RUA < *RUB) ++RUA;
    414       else             ++RUB;
    415     } while (RUA.isValid() && RUB.isValid());
    416     return false;
    417   }
    418 
    419   /// hasRegUnit - Returns true if Reg contains RegUnit.
    420   bool hasRegUnit(unsigned Reg, unsigned RegUnit) const {
    421     for (MCRegUnitIterator Units(Reg, this); Units.isValid(); ++Units)
    422       if (*Units == RegUnit)
    423         return true;
    424     return false;
    425   }
    426 
    427   /// getCalleeSavedRegs - Return a null-terminated list of all of the
    428   /// callee saved registers on this target. The register should be in the
    429   /// order of desired callee-save stack frame offset. The first register is
    430   /// closest to the incoming stack pointer if stack grows down, and vice versa.
    431   ///
    432   virtual const MCPhysReg*
    433   getCalleeSavedRegs(const MachineFunction *MF) const = 0;
    434 
    435   /// getCallPreservedMask - Return a mask of call-preserved registers for the
    436   /// given calling convention on the current function.  The mask should
    437   /// include all call-preserved aliases.  This is used by the register
    438   /// allocator to determine which registers can be live across a call.
    439   ///
    440   /// The mask is an array containing (TRI::getNumRegs()+31)/32 entries.
    441   /// A set bit indicates that all bits of the corresponding register are
    442   /// preserved across the function call.  The bit mask is expected to be
    443   /// sub-register complete, i.e. if A is preserved, so are all its
    444   /// sub-registers.
    445   ///
    446   /// Bits are numbered from the LSB, so the bit for physical register Reg can
    447   /// be found as (Mask[Reg / 32] >> Reg % 32) & 1.
    448   ///
    449   /// A NULL pointer means that no register mask will be used, and call
    450   /// instructions should use implicit-def operands to indicate call clobbered
    451   /// registers.
    452   ///
    453   virtual const uint32_t *getCallPreservedMask(const MachineFunction &MF,
    454                                                CallingConv::ID) const {
    455     // The default mask clobbers everything.  All targets should override.
    456     return nullptr;
    457   }
    458 
    459   /// getReservedRegs - Returns a bitset indexed by physical register number
    460   /// indicating if a register is a special register that has particular uses
    461   /// and should be considered unavailable at all times, e.g. SP, RA. This is
    462   /// used by register scavenger to determine what registers are free.
    463   virtual BitVector getReservedRegs(const MachineFunction &MF) const = 0;
    464 
    465   /// Prior to adding the live-out mask to a stackmap or patchpoint
    466   /// instruction, provide the target the opportunity to adjust it (mainly to
    467   /// remove pseudo-registers that should be ignored).
    468   virtual void adjustStackMapLiveOutMask(uint32_t *Mask) const { }
    469 
    470   /// getMatchingSuperReg - Return a super-register of the specified register
    471   /// Reg so its sub-register of index SubIdx is Reg.
    472   unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx,
    473                                const TargetRegisterClass *RC) const {
    474     return MCRegisterInfo::getMatchingSuperReg(Reg, SubIdx, RC->MC);
    475   }
    476 
    477   /// getMatchingSuperRegClass - Return a subclass of the specified register
    478   /// class A so that each register in it has a sub-register of the
    479   /// specified sub-register index which is in the specified register class B.
    480   ///
    481   /// TableGen will synthesize missing A sub-classes.
    482   virtual const TargetRegisterClass *
    483   getMatchingSuperRegClass(const TargetRegisterClass *A,
    484                            const TargetRegisterClass *B, unsigned Idx) const;
    485 
    486   /// getSubClassWithSubReg - Returns the largest legal sub-class of RC that
    487   /// supports the sub-register index Idx.
    488   /// If no such sub-class exists, return NULL.
    489   /// If all registers in RC already have an Idx sub-register, return RC.
    490   ///
    491   /// TableGen generates a version of this function that is good enough in most
    492   /// cases.  Targets can override if they have constraints that TableGen
    493   /// doesn't understand.  For example, the x86 sub_8bit sub-register index is
    494   /// supported by the full GR32 register class in 64-bit mode, but only by the
    495   /// GR32_ABCD regiister class in 32-bit mode.
    496   ///
    497   /// TableGen will synthesize missing RC sub-classes.
    498   virtual const TargetRegisterClass *
    499   getSubClassWithSubReg(const TargetRegisterClass *RC, unsigned Idx) const {
    500     assert(Idx == 0 && "Target has no sub-registers");
    501     return RC;
    502   }
    503 
    504   /// composeSubRegIndices - Return the subregister index you get from composing
    505   /// two subregister indices.
    506   ///
    507   /// The special null sub-register index composes as the identity.
    508   ///
    509   /// If R:a:b is the same register as R:c, then composeSubRegIndices(a, b)
    510   /// returns c. Note that composeSubRegIndices does not tell you about illegal
    511   /// compositions. If R does not have a subreg a, or R:a does not have a subreg
    512   /// b, composeSubRegIndices doesn't tell you.
    513   ///
    514   /// The ARM register Q0 has two D subregs dsub_0:D0 and dsub_1:D1. It also has
    515   /// ssub_0:S0 - ssub_3:S3 subregs.
    516   /// If you compose subreg indices dsub_1, ssub_0 you get ssub_2.
    517   ///
    518   unsigned composeSubRegIndices(unsigned a, unsigned b) const {
    519     if (!a) return b;
    520     if (!b) return a;
    521     return composeSubRegIndicesImpl(a, b);
    522   }
    523 
    524   /// Transforms a LaneMask computed for one subregister to the lanemask that
    525   /// would have been computed when composing the subsubregisters with IdxA
    526   /// first. @sa composeSubRegIndices()
    527   unsigned composeSubRegIndexLaneMask(unsigned IdxA, unsigned LaneMask) const {
    528     if (!IdxA)
    529       return LaneMask;
    530     return composeSubRegIndexLaneMaskImpl(IdxA, LaneMask);
    531   }
    532 
    533   /// Debugging helper: dump register in human readable form to dbgs() stream.
    534   static void dumpReg(unsigned Reg, unsigned SubRegIndex = 0,
    535                       const TargetRegisterInfo* TRI = nullptr);
    536 
    537 protected:
    538   /// Overridden by TableGen in targets that have sub-registers.
    539   virtual unsigned composeSubRegIndicesImpl(unsigned, unsigned) const {
    540     llvm_unreachable("Target has no sub-registers");
    541   }
    542 
    543   /// Overridden by TableGen in targets that have sub-registers.
    544   virtual unsigned
    545   composeSubRegIndexLaneMaskImpl(unsigned, unsigned) const {
    546     llvm_unreachable("Target has no sub-registers");
    547   }
    548 
    549 public:
    550   /// getCommonSuperRegClass - Find a common super-register class if it exists.
    551   ///
    552   /// Find a register class, SuperRC and two sub-register indices, PreA and
    553   /// PreB, such that:
    554   ///
    555   ///   1. PreA + SubA == PreB + SubB  (using composeSubRegIndices()), and
    556   ///
    557   ///   2. For all Reg in SuperRC: Reg:PreA in RCA and Reg:PreB in RCB, and
    558   ///
    559   ///   3. SuperRC->getSize() >= max(RCA->getSize(), RCB->getSize()).
    560   ///
    561   /// SuperRC will be chosen such that no super-class of SuperRC satisfies the
    562   /// requirements, and there is no register class with a smaller spill size
    563   /// that satisfies the requirements.
    564   ///
    565   /// SubA and SubB must not be 0. Use getMatchingSuperRegClass() instead.
    566   ///
    567   /// Either of the PreA and PreB sub-register indices may be returned as 0. In
    568   /// that case, the returned register class will be a sub-class of the
    569   /// corresponding argument register class.
    570   ///
    571   /// The function returns NULL if no register class can be found.
    572   ///
    573   const TargetRegisterClass*
    574   getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
    575                          const TargetRegisterClass *RCB, unsigned SubB,
    576                          unsigned &PreA, unsigned &PreB) const;
    577 
    578   //===--------------------------------------------------------------------===//
    579   // Register Class Information
    580   //
    581 
    582   /// Register class iterators
    583   ///
    584   regclass_iterator regclass_begin() const { return RegClassBegin; }
    585   regclass_iterator regclass_end() const { return RegClassEnd; }
    586 
    587   unsigned getNumRegClasses() const {
    588     return (unsigned)(regclass_end()-regclass_begin());
    589   }
    590 
    591   /// getRegClass - Returns the register class associated with the enumeration
    592   /// value.  See class MCOperandInfo.
    593   const TargetRegisterClass *getRegClass(unsigned i) const {
    594     assert(i < getNumRegClasses() && "Register Class ID out of range");
    595     return RegClassBegin[i];
    596   }
    597 
    598   /// getRegClassName - Returns the name of the register class.
    599   const char *getRegClassName(const TargetRegisterClass *Class) const {
    600     return MCRegisterInfo::getRegClassName(Class->MC);
    601   }
    602 
    603   /// getCommonSubClass - find the largest common subclass of A and B. Return
    604   /// NULL if there is no common subclass.
    605   const TargetRegisterClass *
    606   getCommonSubClass(const TargetRegisterClass *A,
    607                     const TargetRegisterClass *B) const;
    608 
    609   /// getPointerRegClass - Returns a TargetRegisterClass used for pointer
    610   /// values.  If a target supports multiple different pointer register classes,
    611   /// kind specifies which one is indicated.
    612   virtual const TargetRegisterClass *
    613   getPointerRegClass(const MachineFunction &MF, unsigned Kind=0) const {
    614     llvm_unreachable("Target didn't implement getPointerRegClass!");
    615   }
    616 
    617   /// getCrossCopyRegClass - Returns a legal register class to copy a register
    618   /// in the specified class to or from. If it is possible to copy the register
    619   /// directly without using a cross register class copy, return the specified
    620   /// RC. Returns NULL if it is not possible to copy between a two registers of
    621   /// the specified class.
    622   virtual const TargetRegisterClass *
    623   getCrossCopyRegClass(const TargetRegisterClass *RC) const {
    624     return RC;
    625   }
    626 
    627   /// getLargestLegalSuperClass - Returns the largest super class of RC that is
    628   /// legal to use in the current sub-target and has the same spill size.
    629   /// The returned register class can be used to create virtual registers which
    630   /// means that all its registers can be copied and spilled.
    631   virtual const TargetRegisterClass *
    632   getLargestLegalSuperClass(const TargetRegisterClass *RC,
    633                             const MachineFunction &) const {
    634     /// The default implementation is very conservative and doesn't allow the
    635     /// register allocator to inflate register classes.
    636     return RC;
    637   }
    638 
    639   /// getRegPressureLimit - Return the register pressure "high water mark" for
    640   /// the specific register class. The scheduler is in high register pressure
    641   /// mode (for the specific register class) if it goes over the limit.
    642   ///
    643   /// Note: this is the old register pressure model that relies on a manually
    644   /// specified representative register class per value type.
    645   virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC,
    646                                        MachineFunction &MF) const {
    647     return 0;
    648   }
    649 
    650   /// Get the weight in units of pressure for this register class.
    651   virtual const RegClassWeight &getRegClassWeight(
    652     const TargetRegisterClass *RC) const = 0;
    653 
    654   /// Get the weight in units of pressure for this register unit.
    655   virtual unsigned getRegUnitWeight(unsigned RegUnit) const = 0;
    656 
    657   /// Get the number of dimensions of register pressure.
    658   virtual unsigned getNumRegPressureSets() const = 0;
    659 
    660   /// Get the name of this register unit pressure set.
    661   virtual const char *getRegPressureSetName(unsigned Idx) const = 0;
    662 
    663   /// Get the register unit pressure limit for this dimension.
    664   /// This limit must be adjusted dynamically for reserved registers.
    665   virtual unsigned getRegPressureSetLimit(const MachineFunction &MF,
    666                                           unsigned Idx) const = 0;
    667 
    668   /// Get the dimensions of register pressure impacted by this register class.
    669   /// Returns a -1 terminated array of pressure set IDs.
    670   virtual const int *getRegClassPressureSets(
    671     const TargetRegisterClass *RC) const = 0;
    672 
    673   /// Get the dimensions of register pressure impacted by this register unit.
    674   /// Returns a -1 terminated array of pressure set IDs.
    675   virtual const int *getRegUnitPressureSets(unsigned RegUnit) const = 0;
    676 
    677   /// Get a list of 'hint' registers that the register allocator should try
    678   /// first when allocating a physical register for the virtual register
    679   /// VirtReg. These registers are effectively moved to the front of the
    680   /// allocation order.
    681   ///
    682   /// The Order argument is the allocation order for VirtReg's register class
    683   /// as returned from RegisterClassInfo::getOrder(). The hint registers must
    684   /// come from Order, and they must not be reserved.
    685   ///
    686   /// The default implementation of this function can resolve
    687   /// target-independent hints provided to MRI::setRegAllocationHint with
    688   /// HintType == 0. Targets that override this function should defer to the
    689   /// default implementation if they have no reason to change the allocation
    690   /// order for VirtReg. There may be target-independent hints.
    691   virtual void getRegAllocationHints(unsigned VirtReg,
    692                                      ArrayRef<MCPhysReg> Order,
    693                                      SmallVectorImpl<MCPhysReg> &Hints,
    694                                      const MachineFunction &MF,
    695                                      const VirtRegMap *VRM = nullptr) const;
    696 
    697   /// updateRegAllocHint - A callback to allow target a chance to update
    698   /// register allocation hints when a register is "changed" (e.g. coalesced)
    699   /// to another register. e.g. On ARM, some virtual registers should target
    700   /// register pairs, if one of pair is coalesced to another register, the
    701   /// allocation hint of the other half of the pair should be changed to point
    702   /// to the new register.
    703   virtual void updateRegAllocHint(unsigned Reg, unsigned NewReg,
    704                                   MachineFunction &MF) const {
    705     // Do nothing.
    706   }
    707 
    708   /// Allow the target to reverse allocation order of local live ranges. This
    709   /// will generally allocate shorter local live ranges first. For targets with
    710   /// many registers, this could reduce regalloc compile time by a large
    711   /// factor. It is disabled by default for three reasons:
    712   /// (1) Top-down allocation is simpler and easier to debug for targets that
    713   /// don't benefit from reversing the order.
    714   /// (2) Bottom-up allocation could result in poor evicition decisions on some
    715   /// targets affecting the performance of compiled code.
    716   /// (3) Bottom-up allocation is no longer guaranteed to optimally color.
    717   virtual bool reverseLocalAssignment() const { return false; }
    718 
    719   /// Allow the target to override the cost of using a callee-saved register for
    720   /// the first time. Default value of 0 means we will use a callee-saved
    721   /// register if it is available.
    722   virtual unsigned getCSRFirstUseCost() const { return 0; }
    723 
    724   /// requiresRegisterScavenging - returns true if the target requires (and can
    725   /// make use of) the register scavenger.
    726   virtual bool requiresRegisterScavenging(const MachineFunction &MF) const {
    727     return false;
    728   }
    729 
    730   /// useFPForScavengingIndex - returns true if the target wants to use
    731   /// frame pointer based accesses to spill to the scavenger emergency spill
    732   /// slot.
    733   virtual bool useFPForScavengingIndex(const MachineFunction &MF) const {
    734     return true;
    735   }
    736 
    737   /// requiresFrameIndexScavenging - returns true if the target requires post
    738   /// PEI scavenging of registers for materializing frame index constants.
    739   virtual bool requiresFrameIndexScavenging(const MachineFunction &MF) const {
    740     return false;
    741   }
    742 
    743   /// requiresVirtualBaseRegisters - Returns true if the target wants the
    744   /// LocalStackAllocation pass to be run and virtual base registers
    745   /// used for more efficient stack access.
    746   virtual bool requiresVirtualBaseRegisters(const MachineFunction &MF) const {
    747     return false;
    748   }
    749 
    750   /// hasReservedSpillSlot - Return true if target has reserved a spill slot in
    751   /// the stack frame of the given function for the specified register. e.g. On
    752   /// x86, if the frame register is required, the first fixed stack object is
    753   /// reserved as its spill slot. This tells PEI not to create a new stack frame
    754   /// object for the given register. It should be called only after
    755   /// processFunctionBeforeCalleeSavedScan().
    756   virtual bool hasReservedSpillSlot(const MachineFunction &MF, unsigned Reg,
    757                                     int &FrameIdx) const {
    758     return false;
    759   }
    760 
    761   /// trackLivenessAfterRegAlloc - returns true if the live-ins should be tracked
    762   /// after register allocation.
    763   virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const {
    764     return false;
    765   }
    766 
    767   /// needsStackRealignment - true if storage within the function requires the
    768   /// stack pointer to be aligned more than the normal calling convention calls
    769   /// for.
    770   virtual bool needsStackRealignment(const MachineFunction &MF) const {
    771     return false;
    772   }
    773 
    774   /// getFrameIndexInstrOffset - Get the offset from the referenced frame
    775   /// index in the instruction, if there is one.
    776   virtual int64_t getFrameIndexInstrOffset(const MachineInstr *MI,
    777                                            int Idx) const {
    778     return 0;
    779   }
    780 
    781   /// needsFrameBaseReg - Returns true if the instruction's frame index
    782   /// reference would be better served by a base register other than FP
    783   /// or SP. Used by LocalStackFrameAllocation to determine which frame index
    784   /// references it should create new base registers for.
    785   virtual bool needsFrameBaseReg(MachineInstr *MI, int64_t Offset) const {
    786     return false;
    787   }
    788 
    789   /// materializeFrameBaseRegister - Insert defining instruction(s) for
    790   /// BaseReg to be a pointer to FrameIdx before insertion point I.
    791   virtual void materializeFrameBaseRegister(MachineBasicBlock *MBB,
    792                                             unsigned BaseReg, int FrameIdx,
    793                                             int64_t Offset) const {
    794     llvm_unreachable("materializeFrameBaseRegister does not exist on this "
    795                      "target");
    796   }
    797 
    798   /// resolveFrameIndex - Resolve a frame index operand of an instruction
    799   /// to reference the indicated base register plus offset instead.
    800   virtual void resolveFrameIndex(MachineInstr &MI, unsigned BaseReg,
    801                                  int64_t Offset) const {
    802     llvm_unreachable("resolveFrameIndex does not exist on this target");
    803   }
    804 
    805   /// isFrameOffsetLegal - Determine whether a given base register plus offset
    806   /// immediate is encodable to resolve a frame index.
    807   virtual bool isFrameOffsetLegal(const MachineInstr *MI, unsigned BaseReg,
    808                                   int64_t Offset) const {
    809     llvm_unreachable("isFrameOffsetLegal does not exist on this target");
    810   }
    811 
    812 
    813   /// saveScavengerRegister - Spill the register so it can be used by the
    814   /// register scavenger. Return true if the register was spilled, false
    815   /// otherwise. If this function does not spill the register, the scavenger
    816   /// will instead spill it to the emergency spill slot.
    817   ///
    818   virtual bool saveScavengerRegister(MachineBasicBlock &MBB,
    819                                      MachineBasicBlock::iterator I,
    820                                      MachineBasicBlock::iterator &UseMI,
    821                                      const TargetRegisterClass *RC,
    822                                      unsigned Reg) const {
    823     return false;
    824   }
    825 
    826   /// eliminateFrameIndex - This method must be overriden to eliminate abstract
    827   /// frame indices from instructions which may use them.  The instruction
    828   /// referenced by the iterator contains an MO_FrameIndex operand which must be
    829   /// eliminated by this method.  This method may modify or replace the
    830   /// specified instruction, as long as it keeps the iterator pointing at the
    831   /// finished product.  SPAdj is the SP adjustment due to call frame setup
    832   /// instruction.  FIOperandNum is the FI operand number.
    833   virtual void eliminateFrameIndex(MachineBasicBlock::iterator MI,
    834                                    int SPAdj, unsigned FIOperandNum,
    835                                    RegScavenger *RS = nullptr) const = 0;
    836 
    837   //===--------------------------------------------------------------------===//
    838   /// Subtarget Hooks
    839 
    840   /// \brief SrcRC and DstRC will be morphed into NewRC if this returns true.
    841   virtual bool shouldCoalesce(MachineInstr *MI,
    842                               const TargetRegisterClass *SrcRC,
    843                               unsigned SubReg,
    844                               const TargetRegisterClass *DstRC,
    845                               unsigned DstSubReg,
    846                               const TargetRegisterClass *NewRC) const
    847   { return true; }
    848 
    849   //===--------------------------------------------------------------------===//
    850   /// Debug information queries.
    851 
    852   /// getFrameRegister - This method should return the register used as a base
    853   /// for values allocated in the current stack frame.
    854   virtual unsigned getFrameRegister(const MachineFunction &MF) const = 0;
    855 };
    856 
    857 
    858 //===----------------------------------------------------------------------===//
    859 //                           SuperRegClassIterator
    860 //===----------------------------------------------------------------------===//
    861 //
    862 // Iterate over the possible super-registers for a given register class. The
    863 // iterator will visit a list of pairs (Idx, Mask) corresponding to the
    864 // possible classes of super-registers.
    865 //
    866 // Each bit mask will have at least one set bit, and each set bit in Mask
    867 // corresponds to a SuperRC such that:
    868 //
    869 //   For all Reg in SuperRC: Reg:Idx is in RC.
    870 //
    871 // The iterator can include (O, RC->getSubClassMask()) as the first entry which
    872 // also satisfies the above requirement, assuming Reg:0 == Reg.
    873 //
    874 class SuperRegClassIterator {
    875   const unsigned RCMaskWords;
    876   unsigned SubReg;
    877   const uint16_t *Idx;
    878   const uint32_t *Mask;
    879 
    880 public:
    881   /// Create a SuperRegClassIterator that visits all the super-register classes
    882   /// of RC. When IncludeSelf is set, also include the (0, sub-classes) entry.
    883   SuperRegClassIterator(const TargetRegisterClass *RC,
    884                         const TargetRegisterInfo *TRI,
    885                         bool IncludeSelf = false)
    886     : RCMaskWords((TRI->getNumRegClasses() + 31) / 32),
    887       SubReg(0),
    888       Idx(RC->getSuperRegIndices()),
    889       Mask(RC->getSubClassMask()) {
    890     if (!IncludeSelf)
    891       ++*this;
    892   }
    893 
    894   /// Returns true if this iterator is still pointing at a valid entry.
    895   bool isValid() const { return Idx; }
    896 
    897   /// Returns the current sub-register index.
    898   unsigned getSubReg() const { return SubReg; }
    899 
    900   /// Returns the bit mask if register classes that getSubReg() projects into
    901   /// RC.
    902   const uint32_t *getMask() const { return Mask; }
    903 
    904   /// Advance iterator to the next entry.
    905   void operator++() {
    906     assert(isValid() && "Cannot move iterator past end.");
    907     Mask += RCMaskWords;
    908     SubReg = *Idx++;
    909     if (!SubReg)
    910       Idx = nullptr;
    911   }
    912 };
    913 
    914 // This is useful when building IndexedMaps keyed on virtual registers
    915 struct VirtReg2IndexFunctor : public std::unary_function<unsigned, unsigned> {
    916   unsigned operator()(unsigned Reg) const {
    917     return TargetRegisterInfo::virtReg2Index(Reg);
    918   }
    919 };
    920 
    921 /// PrintReg - Helper class for printing registers on a raw_ostream.
    922 /// Prints virtual and physical registers with or without a TRI instance.
    923 ///
    924 /// The format is:
    925 ///   %noreg          - NoRegister
    926 ///   %vreg5          - a virtual register.
    927 ///   %vreg5:sub_8bit - a virtual register with sub-register index (with TRI).
    928 ///   %EAX            - a physical register
    929 ///   %physreg17      - a physical register when no TRI instance given.
    930 ///
    931 /// Usage: OS << PrintReg(Reg, TRI) << '\n';
    932 ///
    933 class PrintReg {
    934   const TargetRegisterInfo *TRI;
    935   unsigned Reg;
    936   unsigned SubIdx;
    937 public:
    938   explicit PrintReg(unsigned reg, const TargetRegisterInfo *tri = nullptr,
    939                     unsigned subidx = 0)
    940     : TRI(tri), Reg(reg), SubIdx(subidx) {}
    941   void print(raw_ostream&) const;
    942 };
    943 
    944 static inline raw_ostream &operator<<(raw_ostream &OS, const PrintReg &PR) {
    945   PR.print(OS);
    946   return OS;
    947 }
    948 
    949 /// PrintRegUnit - Helper class for printing register units on a raw_ostream.
    950 ///
    951 /// Register units are named after their root registers:
    952 ///
    953 ///   AL      - Single root.
    954 ///   FP0~ST7 - Dual roots.
    955 ///
    956 /// Usage: OS << PrintRegUnit(Unit, TRI) << '\n';
    957 ///
    958 class PrintRegUnit {
    959 protected:
    960   const TargetRegisterInfo *TRI;
    961   unsigned Unit;
    962 public:
    963   PrintRegUnit(unsigned unit, const TargetRegisterInfo *tri)
    964     : TRI(tri), Unit(unit) {}
    965   void print(raw_ostream&) const;
    966 };
    967 
    968 static inline raw_ostream &operator<<(raw_ostream &OS, const PrintRegUnit &PR) {
    969   PR.print(OS);
    970   return OS;
    971 }
    972 
    973 /// PrintVRegOrUnit - It is often convenient to track virtual registers and
    974 /// physical register units in the same list.
    975 class PrintVRegOrUnit : protected PrintRegUnit {
    976 public:
    977   PrintVRegOrUnit(unsigned VRegOrUnit, const TargetRegisterInfo *tri)
    978     : PrintRegUnit(VRegOrUnit, tri) {}
    979   void print(raw_ostream&) const;
    980 };
    981 
    982 static inline raw_ostream &operator<<(raw_ostream &OS,
    983                                       const PrintVRegOrUnit &PR) {
    984   PR.print(OS);
    985   return OS;
    986 }
    987 
    988 } // End llvm namespace
    989 
    990 #endif
    991