X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FTarget%2FTargetRegisterInfo.h;h=2a8ef98cc770d6e98da6653001ed08cdd05f4fcc;hb=0b8c9a80f20772c3793201ab5b251d3520b9cea3;hp=2a3b8b6184e2f5cdf574928bc5e89c74ad36dc35;hpb=c7d67f90d36375f1ff512a3857c887b7e4246adb;p=oota-llvm.git diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h index 2a3b8b6184e..2a8ef98cc77 100644 --- a/include/llvm/Target/TargetRegisterInfo.h +++ b/include/llvm/Target/TargetRegisterInfo.h @@ -16,9 +16,11 @@ #ifndef LLVM_TARGET_TARGETREGISTERINFO_H #define LLVM_TARGET_TARGETREGISTERINFO_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/ValueTypes.h" -#include "llvm/ADT/DenseSet.h" +#include "llvm/IR/CallingConv.h" +#include "llvm/MC/MCRegisterInfo.h" #include #include @@ -26,105 +28,82 @@ namespace llvm { class BitVector; class MachineFunction; -class MachineMove; class RegScavenger; template class SmallVectorImpl; +class VirtRegMap; class raw_ostream; -/// TargetRegisterDesc - This record contains all of the information known about -/// a particular register. The Overlaps field contains a pointer to a zero -/// terminated array of registers that this register aliases, starting with -/// itself. This is needed for architectures like X86 which have AL alias AX -/// alias EAX. The SubRegs field is a zero terminated array of registers that -/// are sub-registers of the specific register, e.g. AL, AH are sub-registers of -/// AX. The SuperRegs field is a zero terminated array of registers that are -/// super-registers of the specific register, e.g. RAX, EAX, are super-registers -/// of AX. -/// -struct TargetRegisterDesc { - const char *Name; // Printable name for the reg (for debugging) - const unsigned *Overlaps; // Overlapping registers, described above - const unsigned *SubRegs; // Sub-register set, described above - const unsigned *SuperRegs; // Super-register set, described above -}; - class TargetRegisterClass { public: - typedef const unsigned* iterator; - typedef const unsigned* const_iterator; - - typedef const EVT* vt_iterator; + typedef const MCPhysReg* iterator; + typedef const MCPhysReg* const_iterator; + typedef const MVT::SimpleValueType* vt_iterator; typedef const TargetRegisterClass* const * sc_iterator; -private: - unsigned ID; - const char *Name; + + // Instance variables filled by tablegen, do not use! + const MCRegisterClass *MC; const vt_iterator VTs; - const sc_iterator SubClasses; + const uint32_t *SubClassMask; + const uint16_t *SuperRegIndices; const sc_iterator SuperClasses; - const sc_iterator SubRegClasses; - const sc_iterator SuperRegClasses; - const unsigned RegSize, Alignment; // Size & Alignment of register in bytes - const int CopyCost; - const iterator RegsBegin, RegsEnd; - DenseSet RegSet; -public: - TargetRegisterClass(unsigned id, - const char *name, - const EVT *vts, - const TargetRegisterClass * const *subcs, - const TargetRegisterClass * const *supcs, - const TargetRegisterClass * const *subregcs, - const TargetRegisterClass * const *superregcs, - unsigned RS, unsigned Al, int CC, - iterator RB, iterator RE) - : ID(id), Name(name), VTs(vts), SubClasses(subcs), SuperClasses(supcs), - SubRegClasses(subregcs), SuperRegClasses(superregcs), - RegSize(RS), Alignment(Al), CopyCost(CC), RegsBegin(RB), RegsEnd(RE) { - for (iterator I = RegsBegin, E = RegsEnd; I != E; ++I) - RegSet.insert(*I); - } - virtual ~TargetRegisterClass() {} // Allow subclasses + ArrayRef (*OrderFunc)(const MachineFunction&); /// getID() - Return the register class ID number. /// - unsigned getID() const { return ID; } + unsigned getID() const { return MC->getID(); } /// getName() - Return the register class name for debugging. /// - const char *getName() const { return Name; } + const char *getName() const { return MC->getName(); } /// begin/end - Return all of the registers in this class. /// - iterator begin() const { return RegsBegin; } - iterator end() const { return RegsEnd; } + iterator begin() const { return MC->begin(); } + iterator end() const { return MC->end(); } /// getNumRegs - Return the number of registers in this class. /// - unsigned getNumRegs() const { return (unsigned)(RegsEnd-RegsBegin); } + unsigned getNumRegs() const { return MC->getNumRegs(); } /// getRegister - Return the specified register in the class. /// unsigned getRegister(unsigned i) const { - assert(i < getNumRegs() && "Register number out of range!"); - return RegsBegin[i]; + return MC->getRegister(i); } /// contains - Return true if the specified register is included in this /// register class. This does not include virtual registers. bool contains(unsigned Reg) const { - return RegSet.count(Reg); + return MC->contains(Reg); } /// contains - Return true if both registers are in this class. bool contains(unsigned Reg1, unsigned Reg2) const { - return contains(Reg1) && contains(Reg2); + return MC->contains(Reg1, Reg2); } + /// getSize - Return the size of the register in bytes, which is also the size + /// of a stack slot allocated to hold a spilled copy of this register. + unsigned getSize() const { return MC->getSize(); } + + /// getAlignment - Return the minimum required alignment for a register of + /// this class. + unsigned getAlignment() const { return MC->getAlignment(); } + + /// getCopyCost - Return the cost of copying a value between two registers in + /// this class. A negative number means the register class is very expensive + /// to copy e.g. status flag register classes. + int getCopyCost() const { return MC->getCopyCost(); } + + /// isAllocatable - Return true if this register class may be used to create + /// virtual registers. + bool isAllocatable() const { return MC->isAllocatable(); } + /// hasType - return true if this TargetRegisterClass has the ValueType vt. /// bool hasType(EVT vt) const { for(int i = 0; VTs[i] != MVT::Other; ++i) - if (VTs[i] == vt) + if (EVT(VTs[i]) == vt) return true; return false; } @@ -141,122 +120,95 @@ public: return I; } - /// subregclasses_begin / subregclasses_end - Loop over all of - /// the subreg register classes of this register class. - sc_iterator subregclasses_begin() const { - return SubRegClasses; - } - - sc_iterator subregclasses_end() const { - sc_iterator I = SubRegClasses; - while (*I != NULL) ++I; - return I; - } - - /// getSubRegisterRegClass - Return the register class of subregisters with - /// index SubIdx, or NULL if no such class exists. - const TargetRegisterClass* getSubRegisterRegClass(unsigned SubIdx) const { - assert(SubIdx>0 && "Invalid subregister index"); - return SubRegClasses[SubIdx-1]; - } - - /// superregclasses_begin / superregclasses_end - Loop over all of - /// the superreg register classes of this register class. - sc_iterator superregclasses_begin() const { - return SuperRegClasses; + /// hasSubClass - return true if the specified TargetRegisterClass + /// is a proper sub-class of this TargetRegisterClass. + bool hasSubClass(const TargetRegisterClass *RC) const { + return RC != this && hasSubClassEq(RC); } - sc_iterator superregclasses_end() const { - sc_iterator I = SuperRegClasses; - while (*I != NULL) ++I; - return I; + /// hasSubClassEq - Returns true if RC is a sub-class of or equal to this + /// class. + bool hasSubClassEq(const TargetRegisterClass *RC) const { + unsigned ID = RC->getID(); + return (SubClassMask[ID / 32] >> (ID % 32)) & 1; } - /// hasSubClass - return true if the specified TargetRegisterClass - /// is a proper subset of this TargetRegisterClass. - bool hasSubClass(const TargetRegisterClass *cs) const { - for (int i = 0; SubClasses[i] != NULL; ++i) - if (SubClasses[i] == cs) - return true; - return false; + /// hasSuperClass - return true if the specified TargetRegisterClass is a + /// proper super-class of this TargetRegisterClass. + bool hasSuperClass(const TargetRegisterClass *RC) const { + return RC->hasSubClass(this); } - /// subclasses_begin / subclasses_end - Loop over all of the classes - /// that are proper subsets of this register class. - sc_iterator subclasses_begin() const { - return SubClasses; + /// hasSuperClassEq - Returns true if RC is a super-class of or equal to this + /// class. + bool hasSuperClassEq(const TargetRegisterClass *RC) const { + return RC->hasSubClassEq(this); } - sc_iterator subclasses_end() const { - sc_iterator I = SubClasses; - while (*I != NULL) ++I; - return I; + /// getSubClassMask - Returns a bit vector of subclasses, including this one. + /// The vector is indexed by class IDs, see hasSubClassEq() above for how to + /// use it. + const uint32_t *getSubClassMask() const { + return SubClassMask; } - /// hasSuperClass - return true if the specified TargetRegisterClass is a - /// proper superset of this TargetRegisterClass. - bool hasSuperClass(const TargetRegisterClass *cs) const { - for (int i = 0; SuperClasses[i] != NULL; ++i) - if (SuperClasses[i] == cs) - return true; - return false; + /// getSuperRegIndices - Returns a 0-terminated list of sub-register indices + /// that project some super-register class into this register class. The list + /// has an entry for each Idx such that: + /// + /// There exists SuperRC where: + /// For all Reg in SuperRC: + /// this->contains(Reg:Idx) + /// + const uint16_t *getSuperRegIndices() const { + return SuperRegIndices; } - /// superclasses_begin / superclasses_end - Loop over all of the classes - /// that are proper supersets of this register class. - sc_iterator superclasses_begin() const { + /// getSuperClasses - Returns a NULL terminated list of super-classes. The + /// classes are ordered by ID which is also a topological ordering from large + /// to small classes. The list does NOT include the current class. + sc_iterator getSuperClasses() const { return SuperClasses; } - sc_iterator superclasses_end() const { - sc_iterator I = SuperClasses; - while (*I != NULL) ++I; - return I; - } - /// isASubClass - return true if this TargetRegisterClass is a subset /// class of at least one other TargetRegisterClass. bool isASubClass() const { return SuperClasses[0] != 0; } - /// allocation_order_begin/end - These methods define a range of registers - /// which specify the registers in this class that are valid to register - /// allocate, and the preferred order to allocate them in. For example, - /// callee saved registers should be at the end of the list, because it is - /// cheaper to allocate caller saved registers. - /// - /// These methods take a MachineFunction argument, which can be used to tune - /// the allocatable registers based on the characteristics of the function, - /// subtarget, or other criteria. + /// getRawAllocationOrder - Returns the preferred order for allocating + /// registers from this register class in MF. The raw order comes directly + /// from the .td file and may include reserved registers that are not + /// allocatable. Register allocators should also make sure to allocate + /// callee-saved registers only after all the volatiles are used. The + /// RegisterClassInfo class provides filtered allocation orders with + /// callee-saved registers moved to the end. /// - /// Register allocators should account for the fact that an allocation - /// order iterator may return a reserved register and always check - /// if the register is allocatable (getAllocatableSet()) before using it. + /// The MachineFunction argument can be used to tune the allocatable + /// registers based on the characteristics of the function, subtarget, or + /// other criteria. /// - /// By default, these methods return all registers in the class. + /// By default, this method returns all registers in the class. /// - virtual iterator allocation_order_begin(const MachineFunction &MF) const { - return begin(); - } - virtual iterator allocation_order_end(const MachineFunction &MF) const { - return end(); + ArrayRef getRawAllocationOrder(const MachineFunction &MF) const { + return OrderFunc ? OrderFunc(MF) : makeArrayRef(begin(), getNumRegs()); } +}; - /// getSize - Return the size of the register in bytes, which is also the size - /// of a stack slot allocated to hold a spilled copy of this register. - unsigned getSize() const { return RegSize; } - - /// getAlignment - Return the minimum required alignment for a register of - /// this class. - unsigned getAlignment() const { return Alignment; } - - /// getCopyCost - Return the cost of copying a value between two registers in - /// this class. A negative number means the register class is very expensive - /// to copy e.g. status flag register classes. - int getCopyCost() const { return CopyCost; } +/// TargetRegisterInfoDesc - Extra information, not in MCRegisterDesc, about +/// registers. These are used by codegen, not by MC. +struct TargetRegisterInfoDesc { + unsigned CostPerUse; // Extra cost of instructions using register. + bool inAllocatableClass; // Register belongs to an allocatable regclass. }; +/// Each TargetRegisterClass has a per register weight, and weight +/// limit which must be less than the limits of its pressure sets. +struct RegClassWeight { + unsigned RegWeight; + unsigned WeightLimit; +}; /// TargetRegisterInfo base class - We assume that the target defines a static /// array of TargetRegisterDesc objects that represent all of the machine @@ -264,213 +216,208 @@ public: /// to this array so that we can turn register number into a register /// descriptor. /// -class TargetRegisterInfo { -protected: - const unsigned* SubregHash; - const unsigned SubregHashSize; - const unsigned* AliasesHash; - const unsigned AliasesHashSize; +class TargetRegisterInfo : public MCRegisterInfo { public: typedef const TargetRegisterClass * const * regclass_iterator; private: - const TargetRegisterDesc *Desc; // Pointer to the descriptor array + const TargetRegisterInfoDesc *InfoDesc; // Extra desc array for codegen const char *const *SubRegIndexNames; // Names of subreg indexes. - unsigned NumRegs; // Number of entries in the array + // Pointer to array of lane masks, one per sub-reg index. + const unsigned *SubRegIndexLaneMasks; regclass_iterator RegClassBegin, RegClassEnd; // List of regclasses - int CallFrameSetupOpcode, CallFrameDestroyOpcode; - protected: - TargetRegisterInfo(const TargetRegisterDesc *D, unsigned NR, + TargetRegisterInfo(const TargetRegisterInfoDesc *ID, regclass_iterator RegClassBegin, regclass_iterator RegClassEnd, - const char *const *subregindexnames, - int CallFrameSetupOpcode = -1, - int CallFrameDestroyOpcode = -1, - const unsigned* subregs = 0, - const unsigned subregsize = 0, - const unsigned* aliases = 0, - const unsigned aliasessize = 0); + const char *const *SRINames, + const unsigned *SRILaneMasks); virtual ~TargetRegisterInfo(); public: - enum { // Define some target independent constants - /// NoRegister - This physical register is not a real target register. It - /// is useful as a sentinal. - NoRegister = 0, + // Register numbers can represent physical registers, virtual registers, and + // sometimes stack slots. The unsigned values are divided into these ranges: + // + // 0 Not a register, can be used as a sentinel. + // [1;2^30) Physical registers assigned by TableGen. + // [2^30;2^31) Stack slots. (Rarely used.) + // [2^31;2^32) Virtual registers assigned by MachineRegisterInfo. + // + // Further sentinels can be allocated from the small negative integers. + // DenseMapInfo uses -1u and -2u. - /// FirstVirtualRegister - This is the first register number that is - /// considered to be a 'virtual' register, which is part of the SSA - /// namespace. This must be the same for all targets, which means that each - /// target is limited to this fixed number of registers. - FirstVirtualRegister = 16384 - }; + /// isStackSlot - Sometimes it is useful the be able to store a non-negative + /// frame index in a variable that normally holds a register. isStackSlot() + /// returns true if Reg is in the range used for stack slots. + /// + /// Note that isVirtualRegister() and isPhysicalRegister() cannot handle stack + /// slots, so if a variable may contains a stack slot, always check + /// isStackSlot() first. + /// + static bool isStackSlot(unsigned Reg) { + return int(Reg) >= (1 << 30); + } + + /// stackSlot2Index - Compute the frame index from a register value + /// representing a stack slot. + static int stackSlot2Index(unsigned Reg) { + assert(isStackSlot(Reg) && "Not a stack slot"); + return int(Reg - (1u << 30)); + } + + /// index2StackSlot - Convert a non-negative frame index to a stack slot + /// register value. + static unsigned index2StackSlot(int FI) { + assert(FI >= 0 && "Cannot hold a negative frame index."); + return FI + (1u << 30); + } /// isPhysicalRegister - Return true if the specified register number is in /// the physical register namespace. static bool isPhysicalRegister(unsigned Reg) { - assert(Reg && "this is not a register!"); - return Reg < FirstVirtualRegister; + assert(!isStackSlot(Reg) && "Not a register! Check isStackSlot() first."); + return int(Reg) > 0; } /// isVirtualRegister - Return true if the specified register number is in /// the virtual register namespace. static bool isVirtualRegister(unsigned Reg) { - assert(Reg && "this is not a register!"); - return Reg >= FirstVirtualRegister; + assert(!isStackSlot(Reg) && "Not a register! Check isStackSlot() first."); + return int(Reg) < 0; } /// virtReg2Index - Convert a virtual register number to a 0-based index. /// The first virtual register in a function will get the index 0. static unsigned virtReg2Index(unsigned Reg) { - return Reg - FirstVirtualRegister; + assert(isVirtualRegister(Reg) && "Not a virtual register"); + return Reg & ~(1u << 31); } /// index2VirtReg - Convert a 0-based index to a virtual register number. /// This is the inverse operation of VirtReg2IndexFunctor below. static unsigned index2VirtReg(unsigned Index) { - return Index + FirstVirtualRegister; + return Index | (1u << 31); } - /// printReg - Print a virtual or physical register on OS. - void printReg(unsigned Reg, raw_ostream &OS) const; - /// getMinimalPhysRegClass - Returns the Register Class of a physical /// register of the given type, picking the most sub register class of /// the right type that contains this physreg. const TargetRegisterClass * getMinimalPhysRegClass(unsigned Reg, EVT VT = MVT::Other) const; + /// getAllocatableClass - Return the maximal subclass of the given register + /// class that is alloctable, or NULL. + const TargetRegisterClass * + getAllocatableClass(const TargetRegisterClass *RC) const; + /// getAllocatableSet - Returns a bitset indexed by register number /// indicating if a register is allocatable or not. If a register class is /// specified, returns the subset for the class. BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC = NULL) const; - const TargetRegisterDesc &operator[](unsigned RegNo) const { - assert(RegNo < NumRegs && - "Attempting to access record for invalid register number!"); - return Desc[RegNo]; + /// getCostPerUse - Return the additional cost of using this register instead + /// of other registers in its class. + unsigned getCostPerUse(unsigned RegNo) const { + return InfoDesc[RegNo].CostPerUse; } - /// Provide a get method, equivalent to [], but more useful if we have a - /// pointer to this object. - /// - const TargetRegisterDesc &get(unsigned RegNo) const { - return operator[](RegNo); + /// isInAllocatableClass - Return true if the register is in the allocation + /// of any register class. + bool isInAllocatableClass(unsigned RegNo) const { + return InfoDesc[RegNo].inAllocatableClass; } - /// getAliasSet - Return the set of registers aliased by the specified - /// register, or a null list of there are none. The list returned is zero - /// terminated. - /// - const unsigned *getAliasSet(unsigned RegNo) const { - // The Overlaps set always begins with Reg itself. - return get(RegNo).Overlaps + 1; + /// getSubRegIndexName - Return the human-readable symbolic target-specific + /// name for the specified SubRegIndex. + const char *getSubRegIndexName(unsigned SubIdx) const { + assert(SubIdx && SubIdx < getNumSubRegIndices() && + "This is not a subregister index"); + return SubRegIndexNames[SubIdx-1]; } - /// getOverlaps - Return a list of registers that overlap Reg, including - /// itself. This is the same as the alias set except Reg is included in the - /// list. - /// These are exactly the registers in { x | regsOverlap(x, Reg) }. + /// getSubRegIndexLaneMask - Return a bitmask representing the parts of a + /// register that are covered by SubIdx. /// - const unsigned *getOverlaps(unsigned RegNo) const { - return get(RegNo).Overlaps; - } - - /// getSubRegisters - Return the list of registers that are sub-registers of - /// the specified register, or a null list of there are none. The list - /// returned is zero terminated and sorted according to super-sub register - /// relations. e.g. X86::RAX's sub-register list is EAX, AX, AL, AH. + /// Lane masks for sub-register indices are similar to register units for + /// physical registers. The individual bits in a lane mask can't be assigned + /// any specific meaning. They can be used to check if two sub-register + /// indices overlap. /// - const unsigned *getSubRegisters(unsigned RegNo) const { - return get(RegNo).SubRegs; - } - - /// getSuperRegisters - Return the list of registers that are super-registers - /// of the specified register, or a null list of there are none. The list - /// returned is zero terminated and sorted according to super-sub register - /// relations. e.g. X86::AL's super-register list is RAX, EAX, AX. + /// If the target has a register such that: /// - const unsigned *getSuperRegisters(unsigned RegNo) const { - return get(RegNo).SuperRegs; - } - - /// getName - Return the human-readable symbolic target-specific name for the - /// specified physical register. - const char *getName(unsigned RegNo) const { - return get(RegNo).Name; - } - - /// getNumRegs - Return the number of registers this target has (useful for - /// sizing arrays holding per register information) - unsigned getNumRegs() const { - return NumRegs; - } - - /// getSubRegIndexName - Return the human-readable symbolic target-specific - /// name for the specified SubRegIndex. - const char *getSubRegIndexName(unsigned SubIdx) const { - assert(SubIdx && "This is not a subregister index"); - return SubRegIndexNames[SubIdx-1]; + /// getSubReg(Reg, A) overlaps getSubReg(Reg, B) + /// + /// then: + /// + /// getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B) != 0 + /// + /// The converse is not necessarily true. If two lane masks have a common + /// bit, the corresponding sub-registers may not overlap, but it can be + /// assumed that they usually will. + unsigned getSubRegIndexLaneMask(unsigned SubIdx) const { + // SubIdx == 0 is allowed, it has the lane mask ~0u. + assert(SubIdx < getNumSubRegIndices() && "This is not a subregister index"); + return SubRegIndexLaneMasks[SubIdx]; } /// regsOverlap - Returns true if the two registers are equal or alias each /// other. The registers may be virtual register. bool regsOverlap(unsigned regA, unsigned regB) const { - if (regA == regB) - return true; - + if (regA == regB) return true; if (isVirtualRegister(regA) || isVirtualRegister(regB)) return false; - // regA and regB are distinct physical registers. Do they alias? - size_t index = (regA + regB * 37) & (AliasesHashSize-1); - unsigned ProbeAmt = 0; - while (AliasesHash[index*2] != 0 && - AliasesHash[index*2+1] != 0) { - if (AliasesHash[index*2] == regA && AliasesHash[index*2+1] == regB) - return true; - - index = (index + ProbeAmt) & (AliasesHashSize-1); - ProbeAmt += 2; - } - + // Regunits are numerically ordered. Find a common unit. + MCRegUnitIterator RUA(regA, this); + MCRegUnitIterator RUB(regB, this); + do { + if (*RUA == *RUB) return true; + if (*RUA < *RUB) ++RUA; + else ++RUB; + } while (RUA.isValid() && RUB.isValid()); return false; } - /// isSubRegister - Returns true if regB is a sub-register of regA. - /// - bool isSubRegister(unsigned regA, unsigned regB) const { - // SubregHash is a simple quadratically probed hash table. - size_t index = (regA + regB * 37) & (SubregHashSize-1); - unsigned ProbeAmt = 2; - while (SubregHash[index*2] != 0 && - SubregHash[index*2+1] != 0) { - if (SubregHash[index*2] == regA && SubregHash[index*2+1] == regB) + /// hasRegUnit - Returns true if Reg contains RegUnit. + bool hasRegUnit(unsigned Reg, unsigned RegUnit) const { + for (MCRegUnitIterator Units(Reg, this); Units.isValid(); ++Units) + if (*Units == RegUnit) return true; - - index = (index + ProbeAmt) & (SubregHashSize-1); - ProbeAmt += 2; - } - return false; } - /// isSuperRegister - Returns true if regB is a super-register of regA. - /// - bool isSuperRegister(unsigned regA, unsigned regB) const { - return isSubRegister(regB, regA); - } - /// getCalleeSavedRegs - Return a null-terminated list of all of the /// callee saved registers on this target. The register should be in the /// order of desired callee-save stack frame offset. The first register is - /// closed to the incoming stack pointer if stack grows down, and vice versa. - virtual const unsigned* getCalleeSavedRegs(const MachineFunction *MF = 0) + /// closest to the incoming stack pointer if stack grows down, and vice versa. + /// + virtual const MCPhysReg* getCalleeSavedRegs(const MachineFunction *MF = 0) const = 0; + /// getCallPreservedMask - Return a mask of call-preserved registers for the + /// given calling convention on the current sub-target. The mask should + /// include all call-preserved aliases. This is used by the register + /// allocator to determine which registers can be live across a call. + /// + /// The mask is an array containing (TRI::getNumRegs()+31)/32 entries. + /// A set bit indicates that all bits of the corresponding register are + /// preserved across the function call. The bit mask is expected to be + /// sub-register complete, i.e. if A is preserved, so are all its + /// sub-registers. + /// + /// Bits are numbered from the LSB, so the bit for physical register Reg can + /// be found as (Mask[Reg / 32] >> Reg % 32) & 1. + /// + /// A NULL pointer means that no register mask will be used, and call + /// instructions should use implicit-def operands to indicate call clobbered + /// registers. + /// + virtual const uint32_t *getCallPreservedMask(CallingConv::ID) const { + // The default mask clobbers everything. All targets should override. + return 0; + } /// getReservedRegs - Returns a bitset indexed by physical register number /// indicating if a register is a special register that has particular uses @@ -478,50 +425,45 @@ public: /// used by register scavenger to determine what registers are free. virtual BitVector getReservedRegs(const MachineFunction &MF) const = 0; - /// getSubReg - Returns the physical register number of sub-register "Index" - /// for physical register RegNo. Return zero if the sub-register does not - /// exist. - virtual unsigned getSubReg(unsigned RegNo, unsigned Index) const = 0; - - /// getSubRegIndex - For a given register pair, return the sub-register index - /// if the second register is a sub-register of the first. Return zero - /// otherwise. - virtual unsigned getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const = 0; - /// getMatchingSuperReg - Return a super-register of the specified register /// Reg so its sub-register of index SubIdx is Reg. unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, const TargetRegisterClass *RC) const { - for (const unsigned *SRs = getSuperRegisters(Reg); unsigned SR = *SRs;++SRs) - if (Reg == getSubReg(SR, SubIdx) && RC->contains(SR)) - return SR; - return 0; - } - - /// canCombineSubRegIndices - Given a register class and a list of - /// subregister indices, return true if it's possible to combine the - /// subregister indices into one that corresponds to a larger - /// subregister. Return the new subregister index by reference. Note the - /// new index may be zero if the given subregisters can be combined to - /// form the whole register. - virtual bool canCombineSubRegIndices(const TargetRegisterClass *RC, - SmallVectorImpl &SubIndices, - unsigned &NewSubIdx) const { - return 0; + return MCRegisterInfo::getMatchingSuperReg(Reg, SubIdx, RC->MC); } /// getMatchingSuperRegClass - Return a subclass of the specified register /// class A so that each register in it has a sub-register of the /// specified sub-register index which is in the specified register class B. + /// + /// TableGen will synthesize missing A sub-classes. virtual const TargetRegisterClass * getMatchingSuperRegClass(const TargetRegisterClass *A, - const TargetRegisterClass *B, unsigned Idx) const { - return 0; + const TargetRegisterClass *B, unsigned Idx) const; + + /// getSubClassWithSubReg - Returns the largest legal sub-class of RC that + /// supports the sub-register index Idx. + /// If no such sub-class exists, return NULL. + /// If all registers in RC already have an Idx sub-register, return RC. + /// + /// TableGen generates a version of this function that is good enough in most + /// cases. Targets can override if they have constraints that TableGen + /// doesn't understand. For example, the x86 sub_8bit sub-register index is + /// supported by the full GR32 register class in 64-bit mode, but only by the + /// GR32_ABCD regiister class in 32-bit mode. + /// + /// TableGen will synthesize missing RC sub-classes. + virtual const TargetRegisterClass * + getSubClassWithSubReg(const TargetRegisterClass *RC, unsigned Idx) const { + assert(Idx == 0 && "Target has no sub-registers"); + return RC; } /// composeSubRegIndices - Return the subregister index you get from composing /// two subregister indices. /// + /// The special null sub-register index composes as the identity. + /// /// If R:a:b is the same register as R:c, then composeSubRegIndices(a, b) /// returns c. Note that composeSubRegIndices does not tell you about illegal /// compositions. If R does not have a subreg a, or R:a does not have a subreg @@ -531,11 +473,47 @@ public: /// ssub_0:S0 - ssub_3:S3 subregs. /// If you compose subreg indices dsub_1, ssub_0 you get ssub_2. /// - virtual unsigned composeSubRegIndices(unsigned a, unsigned b) const { - // This default implementation is correct for most targets. - return b; + unsigned composeSubRegIndices(unsigned a, unsigned b) const { + if (!a) return b; + if (!b) return a; + return composeSubRegIndicesImpl(a, b); + } + +protected: + /// Overridden by TableGen in targets that have sub-registers. + virtual unsigned composeSubRegIndicesImpl(unsigned, unsigned) const { + llvm_unreachable("Target has no sub-registers"); } +public: + /// getCommonSuperRegClass - Find a common super-register class if it exists. + /// + /// Find a register class, SuperRC and two sub-register indices, PreA and + /// PreB, such that: + /// + /// 1. PreA + SubA == PreB + SubB (using composeSubRegIndices()), and + /// + /// 2. For all Reg in SuperRC: Reg:PreA in RCA and Reg:PreB in RCB, and + /// + /// 3. SuperRC->getSize() >= max(RCA->getSize(), RCB->getSize()). + /// + /// SuperRC will be chosen such that no super-class of SuperRC satisfies the + /// requirements, and there is no register class with a smaller spill size + /// that satisfies the requirements. + /// + /// SubA and SubB must not be 0. Use getMatchingSuperRegClass() instead. + /// + /// Either of the PreA and PreB sub-register indices may be returned as 0. In + /// that case, the returned register class will be a sub-class of the + /// corresponding argument register class. + /// + /// The function returns NULL if no register class can be found. + /// + const TargetRegisterClass* + getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA, + const TargetRegisterClass *RCB, unsigned SubB, + unsigned &PreA, unsigned &PreB) const; + //===--------------------------------------------------------------------===// // Register Class Information // @@ -550,47 +528,112 @@ public: } /// getRegClass - Returns the register class associated with the enumeration - /// value. See class TargetOperandInfo. + /// value. See class MCOperandInfo. const TargetRegisterClass *getRegClass(unsigned i) const { assert(i < getNumRegClasses() && "Register Class ID out of range"); return RegClassBegin[i]; } + /// getCommonSubClass - find the largest common subclass of A and B. Return + /// NULL if there is no common subclass. + const TargetRegisterClass * + getCommonSubClass(const TargetRegisterClass *A, + const TargetRegisterClass *B) const; + /// getPointerRegClass - Returns a TargetRegisterClass used for pointer /// values. If a target supports multiple different pointer register classes, /// kind specifies which one is indicated. - virtual const TargetRegisterClass *getPointerRegClass(unsigned Kind=0) const { - assert(0 && "Target didn't implement getPointerRegClass!"); - return 0; // Must return a value in order to compile with VS 2005 + virtual const TargetRegisterClass * + getPointerRegClass(const MachineFunction &MF, unsigned Kind=0) const { + llvm_unreachable("Target didn't implement getPointerRegClass!"); } /// getCrossCopyRegClass - Returns a legal register class to copy a register - /// in the specified class to or from. Returns NULL if it is possible to copy - /// between a two registers of the specified class. + /// in the specified class to or from. If it is possible to copy the register + /// directly without using a cross register class copy, return the specified + /// RC. Returns NULL if it is not possible to copy between a two registers of + /// the specified class. virtual const TargetRegisterClass * getCrossCopyRegClass(const TargetRegisterClass *RC) const { - return NULL; + return RC; } - /// getAllocationOrder - Returns the register allocation order for a specified - /// register class in the form of a pair of TargetRegisterClass iterators. - virtual std::pair - getAllocationOrder(const TargetRegisterClass *RC, - unsigned HintType, unsigned HintReg, - const MachineFunction &MF) const { - return std::make_pair(RC->allocation_order_begin(MF), - RC->allocation_order_end(MF)); + /// getLargestLegalSuperClass - Returns the largest super class of RC that is + /// legal to use in the current sub-target and has the same spill size. + /// The returned register class can be used to create virtual registers which + /// means that all its registers can be copied and spilled. + virtual const TargetRegisterClass* + getLargestLegalSuperClass(const TargetRegisterClass *RC) const { + /// The default implementation is very conservative and doesn't allow the + /// register allocator to inflate register classes. + return RC; } - /// ResolveRegAllocHint - Resolves the specified register allocation hint - /// to a physical register. Returns the physical register if it is successful. - virtual unsigned ResolveRegAllocHint(unsigned Type, unsigned Reg, - const MachineFunction &MF) const { - if (Type == 0 && Reg && isPhysicalRegister(Reg)) - return Reg; + /// getRegPressureLimit - Return the register pressure "high water mark" for + /// the specific register class. The scheduler is in high register pressure + /// mode (for the specific register class) if it goes over the limit. + /// + /// Note: this is the old register pressure model that relies on a manually + /// specified representative register class per value type. + virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC, + MachineFunction &MF) const { return 0; } + /// Get the weight in units of pressure for this register class. + virtual const RegClassWeight &getRegClassWeight( + const TargetRegisterClass *RC) const = 0; + + /// Get the weight in units of pressure for this register unit. + virtual unsigned getRegUnitWeight(unsigned RegUnit) const = 0; + + /// Get the number of dimensions of register pressure. + virtual unsigned getNumRegPressureSets() const = 0; + + /// Get the name of this register unit pressure set. + virtual const char *getRegPressureSetName(unsigned Idx) const = 0; + + /// Get the register unit pressure limit for this dimension. + /// This limit must be adjusted dynamically for reserved registers. + virtual unsigned getRegPressureSetLimit(unsigned Idx) const = 0; + + /// Get the dimensions of register pressure impacted by this register class. + /// Returns a -1 terminated array of pressure set IDs. + virtual const int *getRegClassPressureSets( + const TargetRegisterClass *RC) const = 0; + + /// Get the dimensions of register pressure impacted by this register unit. + /// Returns a -1 terminated array of pressure set IDs. + virtual const int *getRegUnitPressureSets(unsigned RegUnit) const = 0; + + /// Get a list of 'hint' registers that the register allocator should try + /// first when allocating a physical register for the virtual register + /// VirtReg. These registers are effectively moved to the front of the + /// allocation order. + /// + /// The Order argument is the allocation order for VirtReg's register class + /// as returned from RegisterClassInfo::getOrder(). The hint registers must + /// come from Order, and they must not be reserved. + /// + /// The default implementation of this function can resolve + /// target-independent hints provided to MRI::setRegAllocationHint with + /// HintType == 0. Targets that override this function should defer to the + /// default implementation if they have no reason to change the allocation + /// order for VirtReg. There may be target-independent hints. + virtual void getRegAllocationHints(unsigned VirtReg, + ArrayRef Order, + SmallVectorImpl &Hints, + const MachineFunction &MF, + const VirtRegMap *VRM = 0) const; + + /// avoidWriteAfterWrite - Return true if the register allocator should avoid + /// writing a register from RC in two consecutive instructions. + /// This can avoid pipeline stalls on certain architectures. + /// It does cause increased register pressure, though. + virtual bool avoidWriteAfterWrite(const TargetRegisterClass *RC) const { + return false; + } + /// UpdateRegAllocHint - A callback to allow target a chance to update /// register allocation hints when a register is "changed" (e.g. coalesced) /// to another register. e.g. On ARM, some virtual registers should target @@ -608,6 +651,13 @@ public: return false; } + /// useFPForScavengingIndex - returns true if the target wants to use + /// frame pointer based accesses to spill to the scavenger emergency spill + /// slot. + virtual bool useFPForScavengingIndex(const MachineFunction &MF) const { + return true; + } + /// requiresFrameIndexScavenging - returns true if the target requires post /// PEI scavenging of registers for materializing frame index constants. virtual bool requiresFrameIndexScavenging(const MachineFunction &MF) const { @@ -632,6 +682,12 @@ public: return false; } + /// trackLivenessAfterRegAlloc - returns true if the live-ins should be tracked + /// after register allocation. + virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const { + return false; + } + /// needsStackRealignment - true if storage within the function requires the /// stack pointer to be aligned more than the normal calling convention calls /// for. @@ -640,7 +696,7 @@ public: } /// getFrameIndexInstrOffset - Get the offset from the referenced frame - /// index in the instruction, if the is one. + /// index in the instruction, if there is one. virtual int64_t getFrameIndexInstrOffset(const MachineInstr *MI, int Idx) const { return 0; @@ -659,33 +715,24 @@ public: virtual void materializeFrameBaseRegister(MachineBasicBlock *MBB, unsigned BaseReg, int FrameIdx, int64_t Offset) const { - assert(0 && "materializeFrameBaseRegister does not exist on this target"); + llvm_unreachable("materializeFrameBaseRegister does not exist on this " + "target"); } /// resolveFrameIndex - Resolve a frame index operand of an instruction /// to reference the indicated base register plus offset instead. virtual void resolveFrameIndex(MachineBasicBlock::iterator I, unsigned BaseReg, int64_t Offset) const { - assert(0 && "resolveFrameIndex does not exist on this target"); + llvm_unreachable("resolveFrameIndex does not exist on this target"); } /// isFrameOffsetLegal - Determine whether a given offset immediate is /// encodable to resolve a frame index. virtual bool isFrameOffsetLegal(const MachineInstr *MI, int64_t Offset) const { - assert(0 && "isFrameOffsetLegal does not exist on this target"); - return false; // Must return a value in order to compile with VS 2005 + llvm_unreachable("isFrameOffsetLegal does not exist on this target"); } - /// getCallFrameSetup/DestroyOpcode - These methods return the opcode of the - /// frame setup/destroy instructions if they exist (-1 otherwise). Some - /// targets use pseudo instructions in order to abstract away the difference - /// between operating with a frame pointer and operating without, through the - /// use of these two instructions. - /// - int getCallFrameSetupOpcode() const { return CallFrameSetupOpcode; } - int getCallFrameDestroyOpcode() const { return CallFrameDestroyOpcode; } - /// eliminateCallFramePseudoInstr - This method is called during prolog/epilog /// code insertion to eliminate call frame setup and destroy pseudo /// instructions (but only if the Target is using them). It is responsible @@ -697,10 +744,8 @@ public: eliminateCallFramePseudoInstr(MachineFunction &MF, MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const { - assert(getCallFrameSetupOpcode()== -1 && getCallFrameDestroyOpcode()== -1 && - "eliminateCallFramePseudoInstr must be implemented if using" - " call frame setup/destroy pseudo instructions!"); - assert(0 && "Call Frame Pseudo Instructions do not exist on this target!"); + llvm_unreachable("Call Frame Pseudo Instructions do not exist on this " + "target!"); } @@ -730,22 +775,74 @@ public: //===--------------------------------------------------------------------===// /// Debug information queries. - /// getDwarfRegNum - Map a target register to an equivalent dwarf register - /// number. Returns -1 if there is no equivalent value. The second - /// parameter allows targets to use different numberings for EH info and - /// debugging info. - virtual int getDwarfRegNum(unsigned RegNum, bool isEH) const = 0; - /// getFrameRegister - This method should return the register used as a base /// for values allocated in the current stack frame. virtual unsigned getFrameRegister(const MachineFunction &MF) const = 0; - /// getRARegister - This method should return the register where the return - /// address can be found. - virtual unsigned getRARegister() const = 0; + /// getCompactUnwindRegNum - This function maps the register to the number for + /// compact unwind encoding. Return -1 if the register isn't valid. + virtual int getCompactUnwindRegNum(unsigned, bool) const { + return -1; + } }; +//===----------------------------------------------------------------------===// +// SuperRegClassIterator +//===----------------------------------------------------------------------===// +// +// Iterate over the possible super-registers for a given register class. The +// iterator will visit a list of pairs (Idx, Mask) corresponding to the +// possible classes of super-registers. +// +// Each bit mask will have at least one set bit, and each set bit in Mask +// corresponds to a SuperRC such that: +// +// For all Reg in SuperRC: Reg:Idx is in RC. +// +// The iterator can include (O, RC->getSubClassMask()) as the first entry which +// also satisfies the above requirement, assuming Reg:0 == Reg. +// +class SuperRegClassIterator { + const unsigned RCMaskWords; + unsigned SubReg; + const uint16_t *Idx; + const uint32_t *Mask; + +public: + /// Create a SuperRegClassIterator that visits all the super-register classes + /// of RC. When IncludeSelf is set, also include the (0, sub-classes) entry. + SuperRegClassIterator(const TargetRegisterClass *RC, + const TargetRegisterInfo *TRI, + bool IncludeSelf = false) + : RCMaskWords((TRI->getNumRegClasses() + 31) / 32), + SubReg(0), + Idx(RC->getSuperRegIndices()), + Mask(RC->getSubClassMask()) { + if (!IncludeSelf) + ++*this; + } + + /// Returns true if this iterator is still pointing at a valid entry. + bool isValid() const { return Idx; } + + /// Returns the current sub-register index. + unsigned getSubReg() const { return SubReg; } + + /// Returns the bit mask if register classes that getSubReg() projects into + /// RC. + const uint32_t *getMask() const { return Mask; } + + /// Advance iterator to the next entry. + void operator++() { + assert(isValid() && "Cannot move iterator past end."); + Mask += RCMaskWords; + SubReg = *Idx++; + if (!SubReg) + Idx = 0; + } +}; + // This is useful when building IndexedMaps keyed on virtual registers struct VirtReg2IndexFunctor : public std::unary_function { unsigned operator()(unsigned Reg) const { @@ -753,10 +850,56 @@ struct VirtReg2IndexFunctor : public std::unary_function { } }; -/// getCommonSubClass - find the largest common subclass of A and B. Return NULL -/// if there is no common subclass. -const TargetRegisterClass *getCommonSubClass(const TargetRegisterClass *A, - const TargetRegisterClass *B); +/// PrintReg - Helper class for printing registers on a raw_ostream. +/// Prints virtual and physical registers with or without a TRI instance. +/// +/// The format is: +/// %noreg - NoRegister +/// %vreg5 - a virtual register. +/// %vreg5:sub_8bit - a virtual register with sub-register index (with TRI). +/// %EAX - a physical register +/// %physreg17 - a physical register when no TRI instance given. +/// +/// Usage: OS << PrintReg(Reg, TRI) << '\n'; +/// +class PrintReg { + const TargetRegisterInfo *TRI; + unsigned Reg; + unsigned SubIdx; +public: + explicit PrintReg(unsigned reg, const TargetRegisterInfo *tri = 0, + unsigned subidx = 0) + : TRI(tri), Reg(reg), SubIdx(subidx) {} + void print(raw_ostream&) const; +}; + +static inline raw_ostream &operator<<(raw_ostream &OS, const PrintReg &PR) { + PR.print(OS); + return OS; +} + +/// PrintRegUnit - Helper class for printing register units on a raw_ostream. +/// +/// Register units are named after their root registers: +/// +/// AL - Single root. +/// FP0~ST7 - Dual roots. +/// +/// Usage: OS << PrintRegUnit(Unit, TRI) << '\n'; +/// +class PrintRegUnit { + const TargetRegisterInfo *TRI; + unsigned Unit; +public: + PrintRegUnit(unsigned unit, const TargetRegisterInfo *tri) + : TRI(tri), Unit(unit) {} + void print(raw_ostream&) const; +}; + +static inline raw_ostream &operator<<(raw_ostream &OS, const PrintRegUnit &PR) { + PR.print(OS); + return OS; +} } // End llvm namespace