X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenRegisters.h;h=dc441436537db399cfb1d4f1d3a5501106f86277;hb=HEAD;hp=8f85b0874bf7925e4022d1417425379b48077c4a;hpb=4ffd89fa4d2788611187d1a534d2ed46adf1702c;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h index 8f85b0874bf..dc441436537 100644 --- a/utils/TableGen/CodeGenRegisters.h +++ b/utils/TableGen/CodeGenRegisters.h @@ -12,26 +12,44 @@ // //===----------------------------------------------------------------------===// -#ifndef CODEGEN_REGISTERS_H -#define CODEGEN_REGISTERS_H +#ifndef LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H +#define LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H -#include "SetTheory.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" -#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/ADT/SparseBitVector.h" +#include "llvm/CodeGen/MachineValueType.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/TableGen/Record.h" +#include "llvm/TableGen/SetTheory.h" #include +#include #include #include #include #include +#include namespace llvm { class CodeGenRegBank; + /// Used to encode a step in a register lane mask transformation. + /// Mask the bits specified in Mask, then rotate them Rol bits to the left + /// assuming a wraparound at 32bits. + struct MaskRolPair { + unsigned Mask; + uint8_t RotateLeft; + bool operator==(const MaskRolPair Other) const { + return Mask == Other.Mask && RotateLeft == Other.RotateLeft; + } + bool operator!=(const MaskRolPair Other) const { + return Mask != Other.Mask || RotateLeft != Other.RotateLeft; + } + }; + /// CodeGenSubRegIndex - Represents a sub-register index. class CodeGenSubRegIndex { Record *const TheDef; @@ -39,8 +57,15 @@ namespace llvm { std::string Namespace; public: + uint16_t Size; + uint16_t Offset; const unsigned EnumValue; - unsigned LaneMask; + mutable unsigned LaneMask; + mutable SmallVector CompositionLaneMaskTransform; + + // Are all super-registers containing this SubRegIndex covered by their + // sub-registers? + bool AllSuperRegsCovered; CodeGenSubRegIndex(Record *R, unsigned Enum); CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum); @@ -49,23 +74,15 @@ namespace llvm { const std::string &getNamespace() const { return Namespace; } std::string getQualifiedName() const; - // Order CodeGenSubRegIndex pointers by EnumValue. - struct Less { - bool operator()(const CodeGenSubRegIndex *A, - const CodeGenSubRegIndex *B) const { - assert(A && B); - return A->EnumValue < B->EnumValue; - } - }; - // Map of composite subreg indices. - typedef std::map CompMap; + typedef std::map> CompMap; // Returns the subreg index that results from composing this with Idx. // Returns NULL if this and Idx don't compose. CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const { CompMap::const_iterator I = Composed.find(Idx); - return I == Composed.end() ? 0 : I->second; + return I == Composed.end() ? nullptr : I->second; } // Add a composite subreg index: this+A = B. @@ -75,7 +92,17 @@ namespace llvm { assert(A && B); std::pair Ins = Composed.insert(std::make_pair(A, B)); - return (Ins.second || Ins.first->second == B) ? 0 : Ins.first->second; + // Synthetic subreg indices that aren't contiguous (for instance ARM + // register tuples) don't have a bit range, so it's OK to let + // B->Offset == -1. For the other cases, accumulate the offset and set + // the size here. Only do so if there is no offset yet though. + if ((Offset != (uint16_t)-1 && A->Offset != (uint16_t)-1) && + (B->Offset == (uint16_t)-1)) { + B->Offset = Offset + A->Offset; + B->Size = A->Size; + } + return (Ins.second || Ins.first->second == B) ? nullptr + : Ins.first->second; } // Update the composite maps of components specified in 'ComposedOf'. @@ -85,22 +112,28 @@ namespace llvm { const CompMap &getComposites() const { return Composed; } // Compute LaneMask from Composed. Return LaneMask. - unsigned computeLaneMask(); + unsigned computeLaneMask() const; private: CompMap Composed; }; + inline bool operator<(const CodeGenSubRegIndex &A, + const CodeGenSubRegIndex &B) { + return A.EnumValue < B.EnumValue; + } + /// CodeGenRegister - Represents a register definition. struct CodeGenRegister { Record *TheDef; unsigned EnumValue; unsigned CostPerUse; bool CoveredBySubRegs; + bool HasDisjunctSubRegs; // Map SubRegIndex -> Register. - typedef std::map SubRegMap; + typedef std::map> + SubRegMap; CodeGenRegister(Record *R, unsigned Enum); @@ -164,18 +197,27 @@ namespace llvm { } // List of register units in ascending order. - typedef SmallVector RegUnitList; + typedef SparseBitVector<> RegUnitList; + typedef SmallVector RegUnitLaneMaskList; // How many entries in RegUnitList are native? - unsigned NumNativeRegUnits; + RegUnitList NativeRegUnits; // Get the list of register units. // This is only valid after computeSubRegs() completes. const RegUnitList &getRegUnits() const { return RegUnits; } + ArrayRef getRegUnitLaneMasks() const { + return makeArrayRef(RegUnitLaneMasks).slice(0, NativeRegUnits.count()); + } + // Get the native register units. This is a prefix of getRegUnits(). - ArrayRef getNativeRegUnits() const { - return makeArrayRef(RegUnits).slice(0, NumNativeRegUnits); + RegUnitList getNativeRegUnits() const { + return NativeRegUnits; + } + + void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) { + RegUnitLaneMasks = LaneMasks; } // Inherit register units from subregisters. @@ -183,26 +225,14 @@ namespace llvm { bool inheritRegUnits(CodeGenRegBank &RegBank); // Adopt a register unit for pressure tracking. - // A unit is adopted iff its unit number is >= NumNativeRegUnits. - void adoptRegUnit(unsigned RUID) { RegUnits.push_back(RUID); } + // A unit is adopted iff its unit number is >= NativeRegUnits.count(). + void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); } // Get the sum of this register's register unit weights. unsigned getWeight(const CodeGenRegBank &RegBank) const; - // Order CodeGenRegister pointers by EnumValue. - struct Less { - bool operator()(const CodeGenRegister *A, - const CodeGenRegister *B) const { - assert(A && B); - return A->EnumValue < B->EnumValue; - } - }; - // Canonically ordered set. - typedef std::set Set; - - // Compute the set of registers overlapping this. - void computeOverlaps(Set &Overlaps, const CodeGenRegBank&) const; + typedef std::vector Vec; private: bool SubRegsComplete; @@ -223,11 +253,19 @@ namespace llvm { SuperRegList SuperRegs; DenseMap SubReg2Idx; RegUnitList RegUnits; + RegUnitLaneMaskList RegUnitLaneMasks; }; + inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) { + return A.EnumValue < B.EnumValue; + } + + inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) { + return A.EnumValue == B.EnumValue; + } class CodeGenRegisterClass { - CodeGenRegister::Set Members; + CodeGenRegister::Vec Members; // Allocation orders. Order[0] always contains all registers in Members. std::vector > Orders; // Bit mask of sub-classes including this, indexed by their EnumValue. @@ -244,15 +282,16 @@ namespace llvm { // Map SubRegIndex -> sub-class. This is the largest sub-class where all // registers have a SubRegIndex sub-register. - DenseMap SubClassWithSubReg; + DenseMap + SubClassWithSubReg; // Map SubRegIndex -> set of super-reg classes. This is all register // classes SuperRC such that: // // R:SubRegIndex in this RC for all R in SuperRC. // - DenseMap > SuperRegClasses; + DenseMap> + SuperRegClasses; // Bit vector of TopoSigs for the registers in this class. This will be // very sparse on regular architectures. @@ -261,12 +300,17 @@ namespace llvm { public: unsigned EnumValue; std::string Namespace; - std::vector VTs; + SmallVector VTs; unsigned SpillSize; unsigned SpillAlignment; int CopyCost; bool Allocatable; std::string AltOrderSelect; + uint8_t AllocationPriority; + /// Contains the combination of the lane masks of all subregisters. + unsigned LaneMask; + /// True if there are at least 2 subregisters which do not interfere. + bool HasDisjunctSubRegs; // Return the Record that defined this class, or NULL if the class was // created by TableGen. @@ -274,7 +318,7 @@ namespace llvm { const std::string &getName() const { return Name; } std::string getQualifiedName() const; - const std::vector &getValueTypes() const {return VTs;} + ArrayRef getValueTypes() const {return VTs;} unsigned getNumValueTypes() const { return VTs.size(); } MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const { @@ -301,19 +345,20 @@ namespace llvm { // getSubClassWithSubReg - Returns the largest sub-class where all // registers have a SubIdx sub-register. - CodeGenRegisterClass* - getSubClassWithSubReg(CodeGenSubRegIndex *SubIdx) const { + CodeGenRegisterClass * + getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const { return SubClassWithSubReg.lookup(SubIdx); } - void setSubClassWithSubReg(CodeGenSubRegIndex *SubIdx, + void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx, CodeGenRegisterClass *SubRC) { SubClassWithSubReg[SubIdx] = SubRC; } // getSuperRegClasses - Returns a bit vector of all register classes // containing only SubIdx super-registers of this class. - void getSuperRegClasses(CodeGenSubRegIndex *SubIdx, BitVector &Out) const; + void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx, + BitVector &Out) const; // addSuperRegClass - Add a class containing only SudIdx super-registers. void addSuperRegClass(CodeGenSubRegIndex *SubIdx, @@ -323,7 +368,7 @@ namespace llvm { // getSubClasses - Returns a constant BitVector of subclasses indexed by // EnumValue. - // The SubClasses vector includs an entry for this class. + // The SubClasses vector includes an entry for this class. const BitVector &getSubClasses() const { return SubClasses; } // getSuperClasses - Returns a list of super classes ordered by EnumValue. @@ -344,7 +389,7 @@ namespace llvm { // Get the set of registers. This set contains the same registers as // getOrder(0). - const CodeGenRegister::Set &getMembers() const { return Members; } + const CodeGenRegister::Vec &getMembers() const { return Members; } // Get a bit vector of TopoSigs present in this register class. const BitVector &getTopoSigs() const { return TopoSigs; } @@ -358,16 +403,11 @@ namespace llvm { // sub-classes. Note the ordering provided by this key is not the same as // the topological order used for the EnumValues. struct Key { - const CodeGenRegister::Set *Members; + const CodeGenRegister::Vec *Members; unsigned SpillSize; unsigned SpillAlignment; - Key(const Key &O) - : Members(O.Members), - SpillSize(O.SpillSize), - SpillAlignment(O.SpillAlignment) {} - - Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0) + Key(const CodeGenRegister::Vec *M, unsigned S = 0, unsigned A = 0) : Members(M), SpillSize(S), SpillAlignment(A) {} Key(const CodeGenRegisterClass &RC) @@ -403,7 +443,13 @@ namespace llvm { // these two registers and their super-registers. const CodeGenRegister *Roots[2]; - RegUnit() : Weight(0) { Roots[0] = Roots[1] = 0; } + // Index into RegClassUnitSets where we can find the list of UnitSets that + // contain this unit. + unsigned RegClassUnitSetsIdx; + + RegUnit() : Weight(0), RegClassUnitSetsIdx(0) { + Roots[0] = Roots[1] = nullptr; + } ArrayRef getRoots() const { assert(!(Roots[1] && !Roots[0]) && "Invalid roots array"); @@ -417,6 +463,10 @@ namespace llvm { std::string Name; std::vector Units; + unsigned Weight; // Cache the sum of all unit weights. + unsigned Order; // Cache the sort key. + + RegUnitSet() : Weight(0), Order(0) {} }; // Base vector for identifying TopoSigs. The contents uniquely identify a @@ -428,8 +478,7 @@ namespace llvm { class CodeGenRegBank { SetTheory Sets; - // SubRegIndices. - std::vector SubRegIndices; + std::deque SubRegIndices; DenseMap Def2SubRegIdx; CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace); @@ -439,7 +488,7 @@ namespace llvm { ConcatIdxMap ConcatIdx; // Registers. - std::vector Registers; + std::deque Registers; StringMap RegistersByName; DenseMap Def2Reg; unsigned NumNativeRegUnits; @@ -450,7 +499,7 @@ namespace llvm { SmallVector RegUnits; // Register classes. - std::vector RegClasses; + std::list RegClasses; DenseMap Def2RC; typedef std::map RCKeyMap; RCKeyMap Key2RC; @@ -462,22 +511,34 @@ namespace llvm { // Map RegisterClass index to the index of the RegUnitSet that contains the // class's units and any inferred RegUnit supersets. + // + // NOTE: This could grow beyond the number of register classes when we map + // register units to lists of unit sets. If the list of unit sets does not + // already exist for a register class, we create a new entry in this vector. std::vector > RegClassUnitSets; + // Give each register unit set an order based on sorting criteria. + std::vector RegUnitSetOrder; + // Add RC to *2RC maps. void addToMaps(CodeGenRegisterClass*); // Create a synthetic sub-class if it is missing. CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, - const CodeGenRegister::Set *Membs, + const CodeGenRegister::Vec *Membs, StringRef Name); // Infer missing register classes. void computeInferredRegisterClasses(); void inferCommonSubClass(CodeGenRegisterClass *RC); void inferSubClassWithSubReg(CodeGenRegisterClass *RC); - void inferMatchingSuperRegClass(CodeGenRegisterClass *RC, - unsigned FirstSubRegRC = 0); + void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) { + inferMatchingSuperRegClass(RC, RegClasses.begin()); + } + + void inferMatchingSuperRegClass( + CodeGenRegisterClass *RC, + std::list::iterator FirstSubRegRC); // Iteratively prune unit sets. void pruneUnitSets(); @@ -492,7 +553,11 @@ namespace llvm { void computeComposites(); // Compute a lane mask for each sub-register index. - void computeSubRegIndexLaneMasks(); + void computeSubRegLaneMasks(); + + /// Computes a lane mask for each register unit enumerated by a physical + /// register. + void computeRegUnitLaneMasks(); public: CodeGenRegBank(RecordKeeper&); @@ -502,7 +567,9 @@ namespace llvm { // Sub-register indices. The first NumNamedIndices are defined by the user // in the .td files. The rest are synthesized such that all sub-registers // have a unique name. - ArrayRef getSubRegIndices() { return SubRegIndices; } + const std::deque &getSubRegIndices() const { + return SubRegIndices; + } // Find a SubRegIndex form its Record def. CodeGenSubRegIndex *getSubRegIdx(Record*); @@ -514,15 +581,15 @@ namespace llvm { // Find or create a sub-register index representing the concatenation of // non-overlapping sibling indices. CodeGenSubRegIndex * - getConcatSubRegIndex(const SmallVector&); + getConcatSubRegIndex(const SmallVector&); void - addConcatSubRegIndex(const SmallVector &Parts, + addConcatSubRegIndex(const SmallVector &Parts, CodeGenSubRegIndex *Idx) { ConcatIdx.insert(std::make_pair(Parts, Idx)); } - const std::vector &getRegisters() { return Registers; } + const std::deque &getRegisters() { return Registers; } const StringMap &getRegistersByName() { return RegistersByName; } @@ -550,7 +617,7 @@ namespace llvm { // Create a native register unit that is associated with one or two root // registers. - unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = 0) { + unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) { RegUnits.resize(RegUnits.size() + 1); RegUnits.back().Roots[0] = R0; RegUnits.back().Roots[1] = R1; @@ -579,7 +646,9 @@ namespace llvm { RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; } const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; } - ArrayRef getRegClasses() const { + std::list &getRegClasses() { return RegClasses; } + + const std::list &getRegClasses() const { return RegClasses; } @@ -602,6 +671,13 @@ namespace llvm { return Weight; } + unsigned getRegSetIDAt(unsigned Order) const { + return RegUnitSetOrder[Order]; + } + const RegUnitSet &getRegSetAt(unsigned Order) const { + return RegUnitSets[RegUnitSetOrder[Order]]; + } + // Increase a RegUnitWeight. void increaseRegUnitWeight(unsigned RUID, unsigned Inc) { getRegUnit(RUID).Weight += Inc; @@ -611,10 +687,17 @@ namespace llvm { unsigned getNumRegPressureSets() const { return RegUnitSets.size(); } // Get a set of register unit IDs for a given dimension of pressure. - RegUnitSet getRegPressureSet(unsigned Idx) const { + const RegUnitSet &getRegPressureSet(unsigned Idx) const { return RegUnitSets[Idx]; } + // The number of pressure set lists may be larget than the number of + // register classes if some register units appeared in a list of sets that + // did not correspond to an existing register class. + unsigned getNumRegClassPressureSetLists() const { + return RegClassUnitSets.size(); + } + // Get a list of pressure set IDs for a register class. Liveness of a // register in this class impacts each pressure set in this list by the // weight of the register. An exact solution requires all registers in a @@ -634,6 +717,11 @@ namespace llvm { // This is used to compute the mask of call-preserved registers from a list // of callee-saves. BitVector computeCoveredRegisters(ArrayRef Regs); + + // Bit mask of lanes that cover their registers. A sub-register index whose + // LaneMask is contained in CoveringLanes will be completely covered by + // another sub-register with the same or larger lane mask. + unsigned CoveringLanes; }; }