CodeGenRegisters.h revision 280031
1193323Sed//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines structures to encapsulate information gleaned from the 11193323Sed// target register and register class definitions. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15280031Sdim#ifndef LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 16280031Sdim#define LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 17193323Sed 18224145Sdim#include "llvm/ADT/ArrayRef.h" 19226633Sdim#include "llvm/ADT/BitVector.h" 20208599Srdivacky#include "llvm/ADT/DenseMap.h" 21224145Sdim#include "llvm/ADT/SetVector.h" 22276479Sdim#include "llvm/CodeGen/MachineValueType.h" 23234353Sdim#include "llvm/Support/ErrorHandling.h" 24249423Sdim#include "llvm/TableGen/Record.h" 25276479Sdim#include "llvm/TableGen/SetTheory.h" 26223017Sdim#include <cstdlib> 27280031Sdim#include <list> 28223017Sdim#include <map> 29249423Sdim#include <set> 30193323Sed#include <string> 31193323Sed#include <vector> 32280031Sdim#include <deque> 33193323Sed 34193323Sednamespace llvm { 35223017Sdim class CodeGenRegBank; 36193323Sed 37280031Sdim /// Used to encode a step in a register lane mask transformation. 38280031Sdim /// Mask the bits specified in Mask, then rotate them Rol bits to the left 39280031Sdim /// assuming a wraparound at 32bits. 40280031Sdim struct MaskRolPair { 41280031Sdim unsigned Mask; 42280031Sdim uint8_t RotateLeft; 43280031Sdim bool operator==(const MaskRolPair Other) { 44280031Sdim return Mask == Other.Mask && RotateLeft == Other.RotateLeft; 45280031Sdim } 46280031Sdim bool operator!=(const MaskRolPair Other) { 47280031Sdim return Mask != Other.Mask || RotateLeft != Other.RotateLeft; 48280031Sdim } 49280031Sdim }; 50280031Sdim 51234353Sdim /// CodeGenSubRegIndex - Represents a sub-register index. 52234353Sdim class CodeGenSubRegIndex { 53234353Sdim Record *const TheDef; 54239462Sdim std::string Name; 55239462Sdim std::string Namespace; 56239462Sdim 57239462Sdim public: 58261991Sdim uint16_t Size; 59261991Sdim uint16_t Offset; 60234353Sdim const unsigned EnumValue; 61280031Sdim mutable unsigned LaneMask; 62280031Sdim mutable SmallVector<MaskRolPair,1> CompositionLaneMaskTransform; 63234353Sdim 64261991Sdim // Are all super-registers containing this SubRegIndex covered by their 65261991Sdim // sub-registers? 66261991Sdim bool AllSuperRegsCovered; 67261991Sdim 68234353Sdim CodeGenSubRegIndex(Record *R, unsigned Enum); 69239462Sdim CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum); 70234353Sdim 71239462Sdim const std::string &getName() const { return Name; } 72239462Sdim const std::string &getNamespace() const { return Namespace; } 73234353Sdim std::string getQualifiedName() const; 74234353Sdim 75234353Sdim // Order CodeGenSubRegIndex pointers by EnumValue. 76234353Sdim struct Less { 77234353Sdim bool operator()(const CodeGenSubRegIndex *A, 78234353Sdim const CodeGenSubRegIndex *B) const { 79234353Sdim assert(A && B); 80234353Sdim return A->EnumValue < B->EnumValue; 81234353Sdim } 82234353Sdim }; 83234353Sdim 84234353Sdim // Map of composite subreg indices. 85234353Sdim typedef std::map<CodeGenSubRegIndex*, CodeGenSubRegIndex*, Less> CompMap; 86234353Sdim 87234353Sdim // Returns the subreg index that results from composing this with Idx. 88234353Sdim // Returns NULL if this and Idx don't compose. 89234353Sdim CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const { 90234353Sdim CompMap::const_iterator I = Composed.find(Idx); 91276479Sdim return I == Composed.end() ? nullptr : I->second; 92234353Sdim } 93234353Sdim 94234353Sdim // Add a composite subreg index: this+A = B. 95234353Sdim // Return a conflicting composite, or NULL 96234353Sdim CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, 97234353Sdim CodeGenSubRegIndex *B) { 98239462Sdim assert(A && B); 99234353Sdim std::pair<CompMap::iterator, bool> Ins = 100234353Sdim Composed.insert(std::make_pair(A, B)); 101261991Sdim // Synthetic subreg indices that aren't contiguous (for instance ARM 102261991Sdim // register tuples) don't have a bit range, so it's OK to let 103261991Sdim // B->Offset == -1. For the other cases, accumulate the offset and set 104261991Sdim // the size here. Only do so if there is no offset yet though. 105261991Sdim if ((Offset != (uint16_t)-1 && A->Offset != (uint16_t)-1) && 106261991Sdim (B->Offset == (uint16_t)-1)) { 107261991Sdim B->Offset = Offset + A->Offset; 108261991Sdim B->Size = A->Size; 109261991Sdim } 110276479Sdim return (Ins.second || Ins.first->second == B) ? nullptr 111276479Sdim : Ins.first->second; 112234353Sdim } 113234353Sdim 114234353Sdim // Update the composite maps of components specified in 'ComposedOf'. 115234353Sdim void updateComponents(CodeGenRegBank&); 116234353Sdim 117234353Sdim // Return the map of composites. 118234353Sdim const CompMap &getComposites() const { return Composed; } 119234353Sdim 120243830Sdim // Compute LaneMask from Composed. Return LaneMask. 121280031Sdim unsigned computeLaneMask() const; 122243830Sdim 123234353Sdim private: 124234353Sdim CompMap Composed; 125234353Sdim }; 126234353Sdim 127193323Sed /// CodeGenRegister - Represents a register definition. 128193323Sed struct CodeGenRegister { 129193323Sed Record *TheDef; 130221345Sdim unsigned EnumValue; 131221345Sdim unsigned CostPerUse; 132234353Sdim bool CoveredBySubRegs; 133223017Sdim 134223017Sdim // Map SubRegIndex -> Register. 135234353Sdim typedef std::map<CodeGenSubRegIndex*, CodeGenRegister*, 136234353Sdim CodeGenSubRegIndex::Less> SubRegMap; 137223017Sdim 138223017Sdim CodeGenRegister(Record *R, unsigned Enum); 139223017Sdim 140223017Sdim const std::string &getName() const; 141223017Sdim 142239462Sdim // Extract more information from TheDef. This is used to build an object 143239462Sdim // graph after all CodeGenRegister objects have been created. 144239462Sdim void buildObjectGraph(CodeGenRegBank&); 145239462Sdim 146239462Sdim // Lazily compute a map of all sub-registers. 147223017Sdim // This includes unique entries for all sub-sub-registers. 148239462Sdim const SubRegMap &computeSubRegs(CodeGenRegBank&); 149223017Sdim 150239462Sdim // Compute extra sub-registers by combining the existing sub-registers. 151239462Sdim void computeSecondarySubRegs(CodeGenRegBank&); 152239462Sdim 153239462Sdim // Add this as a super-register to all sub-registers after the sub-register 154239462Sdim // graph has been built. 155239462Sdim void computeSuperRegs(CodeGenRegBank&); 156239462Sdim 157223017Sdim const SubRegMap &getSubRegs() const { 158223017Sdim assert(SubRegsComplete && "Must precompute sub-registers"); 159223017Sdim return SubRegs; 160223017Sdim } 161223017Sdim 162224145Sdim // Add sub-registers to OSet following a pre-order defined by the .td file. 163234353Sdim void addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet, 164234353Sdim CodeGenRegBank&) const; 165224145Sdim 166239462Sdim // Return the sub-register index naming Reg as a sub-register of this 167239462Sdim // register. Returns NULL if Reg is not a sub-register. 168239462Sdim CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const { 169239462Sdim return SubReg2Idx.lookup(Reg); 170239462Sdim } 171239462Sdim 172234353Sdim typedef std::vector<const CodeGenRegister*> SuperRegList; 173224145Sdim 174239462Sdim // Get the list of super-registers in topological order, small to large. 175239462Sdim // This is valid after computeSubRegs visits all registers during RegBank 176239462Sdim // construction. 177224145Sdim const SuperRegList &getSuperRegs() const { 178224145Sdim assert(SubRegsComplete && "Must precompute sub-registers"); 179224145Sdim return SuperRegs; 180224145Sdim } 181224145Sdim 182239462Sdim // Get the list of ad hoc aliases. The graph is symmetric, so the list 183239462Sdim // contains all registers in 'Aliases', and all registers that mention this 184239462Sdim // register in 'Aliases'. 185239462Sdim ArrayRef<CodeGenRegister*> getExplicitAliases() const { 186239462Sdim return ExplicitAliases; 187239462Sdim } 188239462Sdim 189239462Sdim // Get the topological signature of this register. This is a small integer 190239462Sdim // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have 191239462Sdim // identical sub-register structure. That is, they support the same set of 192239462Sdim // sub-register indices mapping to the same kind of sub-registers 193239462Sdim // (TopoSig-wise). 194239462Sdim unsigned getTopoSig() const { 195239462Sdim assert(SuperRegsComplete && "TopoSigs haven't been computed yet."); 196239462Sdim return TopoSig; 197239462Sdim } 198239462Sdim 199234353Sdim // List of register units in ascending order. 200234353Sdim typedef SmallVector<unsigned, 16> RegUnitList; 201280031Sdim typedef SmallVector<unsigned, 16> RegUnitLaneMaskList; 202234353Sdim 203239462Sdim // How many entries in RegUnitList are native? 204239462Sdim unsigned NumNativeRegUnits; 205239462Sdim 206234353Sdim // Get the list of register units. 207239462Sdim // This is only valid after computeSubRegs() completes. 208234353Sdim const RegUnitList &getRegUnits() const { return RegUnits; } 209234353Sdim 210280031Sdim ArrayRef<unsigned> getRegUnitLaneMasks() const { 211280031Sdim return makeArrayRef(RegUnitLaneMasks).slice(0, NumNativeRegUnits); 212280031Sdim } 213280031Sdim 214239462Sdim // Get the native register units. This is a prefix of getRegUnits(). 215239462Sdim ArrayRef<unsigned> getNativeRegUnits() const { 216239462Sdim return makeArrayRef(RegUnits).slice(0, NumNativeRegUnits); 217239462Sdim } 218239462Sdim 219280031Sdim void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) { 220280031Sdim RegUnitLaneMasks = LaneMasks; 221280031Sdim } 222280031Sdim 223234353Sdim // Inherit register units from subregisters. 224234353Sdim // Return true if the RegUnits changed. 225234353Sdim bool inheritRegUnits(CodeGenRegBank &RegBank); 226234353Sdim 227234353Sdim // Adopt a register unit for pressure tracking. 228234353Sdim // A unit is adopted iff its unit number is >= NumNativeRegUnits. 229234353Sdim void adoptRegUnit(unsigned RUID) { RegUnits.push_back(RUID); } 230234353Sdim 231234353Sdim // Get the sum of this register's register unit weights. 232234353Sdim unsigned getWeight(const CodeGenRegBank &RegBank) const; 233234353Sdim 234224145Sdim // Order CodeGenRegister pointers by EnumValue. 235224145Sdim struct Less { 236224145Sdim bool operator()(const CodeGenRegister *A, 237224145Sdim const CodeGenRegister *B) const { 238226633Sdim assert(A && B); 239224145Sdim return A->EnumValue < B->EnumValue; 240224145Sdim } 241224145Sdim }; 242224145Sdim 243224145Sdim // Canonically ordered set. 244224145Sdim typedef std::set<const CodeGenRegister*, Less> Set; 245224145Sdim 246223017Sdim private: 247223017Sdim bool SubRegsComplete; 248239462Sdim bool SuperRegsComplete; 249239462Sdim unsigned TopoSig; 250239462Sdim 251239462Sdim // The sub-registers explicit in the .td file form a tree. 252239462Sdim SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices; 253239462Sdim SmallVector<CodeGenRegister*, 8> ExplicitSubRegs; 254239462Sdim 255239462Sdim // Explicit ad hoc aliases, symmetrized to form an undirected graph. 256239462Sdim SmallVector<CodeGenRegister*, 8> ExplicitAliases; 257239462Sdim 258239462Sdim // Super-registers where this is the first explicit sub-register. 259239462Sdim SuperRegList LeadingSuperRegs; 260239462Sdim 261223017Sdim SubRegMap SubRegs; 262224145Sdim SuperRegList SuperRegs; 263239462Sdim DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx; 264234353Sdim RegUnitList RegUnits; 265280031Sdim RegUnitLaneMaskList RegUnitLaneMasks; 266193323Sed }; 267193323Sed 268193323Sed 269224145Sdim class CodeGenRegisterClass { 270224145Sdim CodeGenRegister::Set Members; 271226633Sdim // Allocation orders. Order[0] always contains all registers in Members. 272226633Sdim std::vector<SmallVector<Record*, 16> > Orders; 273226633Sdim // Bit mask of sub-classes including this, indexed by their EnumValue. 274226633Sdim BitVector SubClasses; 275226633Sdim // List of super-classes, topologocally ordered to have the larger classes 276226633Sdim // first. This is the same as sorting by EnumValue. 277226633Sdim SmallVector<CodeGenRegisterClass*, 4> SuperClasses; 278226633Sdim Record *TheDef; 279226633Sdim std::string Name; 280226633Sdim 281226633Sdim // For a synthesized class, inherit missing properties from the nearest 282226633Sdim // super-class. 283226633Sdim void inheritProperties(CodeGenRegBank&); 284226633Sdim 285234353Sdim // Map SubRegIndex -> sub-class. This is the largest sub-class where all 286234353Sdim // registers have a SubRegIndex sub-register. 287280031Sdim DenseMap<const CodeGenSubRegIndex *, CodeGenRegisterClass *> 288280031Sdim SubClassWithSubReg; 289226633Sdim 290234353Sdim // Map SubRegIndex -> set of super-reg classes. This is all register 291234353Sdim // classes SuperRC such that: 292234353Sdim // 293234353Sdim // R:SubRegIndex in this RC for all R in SuperRC. 294234353Sdim // 295280031Sdim DenseMap<const CodeGenSubRegIndex *, SmallPtrSet<CodeGenRegisterClass *, 8>> 296280031Sdim SuperRegClasses; 297234353Sdim 298239462Sdim // Bit vector of TopoSigs for the registers in this class. This will be 299239462Sdim // very sparse on regular architectures. 300239462Sdim BitVector TopoSigs; 301239462Sdim 302224145Sdim public: 303226633Sdim unsigned EnumValue; 304193323Sed std::string Namespace; 305249423Sdim SmallVector<MVT::SimpleValueType, 4> VTs; 306193323Sed unsigned SpillSize; 307193323Sed unsigned SpillAlignment; 308193323Sed int CopyCost; 309223017Sdim bool Allocatable; 310224145Sdim std::string AltOrderSelect; 311280031Sdim /// Contains the combination of the lane masks of all subregisters. 312280031Sdim unsigned LaneMask; 313193323Sed 314226633Sdim // Return the Record that defined this class, or NULL if the class was 315226633Sdim // created by TableGen. 316226633Sdim Record *getDef() const { return TheDef; } 317226633Sdim 318226633Sdim const std::string &getName() const { return Name; } 319226633Sdim std::string getQualifiedName() const; 320249423Sdim ArrayRef<MVT::SimpleValueType> getValueTypes() const {return VTs;} 321193323Sed unsigned getNumValueTypes() const { return VTs.size(); } 322221345Sdim 323193323Sed MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const { 324193323Sed if (VTNum < VTs.size()) 325193323Sed return VTs[VTNum]; 326234353Sdim llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!"); 327193323Sed } 328221345Sdim 329224145Sdim // Return true if this this class contains the register. 330224145Sdim bool contains(const CodeGenRegister*) const; 331221345Sdim 332224145Sdim // Returns true if RC is a subclass. 333212904Sdim // RC is a sub-class of this class if it is a valid replacement for any 334221345Sdim // instruction operand where a register of this classis required. It must 335212904Sdim // satisfy these conditions: 336212904Sdim // 337212904Sdim // 1. All RC registers are also in this. 338212904Sdim // 2. The RC spill size must not be smaller than our spill size. 339212904Sdim // 3. RC spill alignment must be compatible with ours. 340212904Sdim // 341226633Sdim bool hasSubClass(const CodeGenRegisterClass *RC) const { 342226633Sdim return SubClasses.test(RC->EnumValue); 343226633Sdim } 344193323Sed 345226633Sdim // getSubClassWithSubReg - Returns the largest sub-class where all 346226633Sdim // registers have a SubIdx sub-register. 347280031Sdim CodeGenRegisterClass * 348280031Sdim getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const { 349226633Sdim return SubClassWithSubReg.lookup(SubIdx); 350226633Sdim } 351226633Sdim 352280031Sdim void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx, 353234353Sdim CodeGenRegisterClass *SubRC) { 354226633Sdim SubClassWithSubReg[SubIdx] = SubRC; 355226633Sdim } 356226633Sdim 357234353Sdim // getSuperRegClasses - Returns a bit vector of all register classes 358234353Sdim // containing only SubIdx super-registers of this class. 359280031Sdim void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx, 360280031Sdim BitVector &Out) const; 361234353Sdim 362234353Sdim // addSuperRegClass - Add a class containing only SudIdx super-registers. 363234353Sdim void addSuperRegClass(CodeGenSubRegIndex *SubIdx, 364234353Sdim CodeGenRegisterClass *SuperRC) { 365234353Sdim SuperRegClasses[SubIdx].insert(SuperRC); 366234353Sdim } 367234353Sdim 368226633Sdim // getSubClasses - Returns a constant BitVector of subclasses indexed by 369226633Sdim // EnumValue. 370276479Sdim // The SubClasses vector includes an entry for this class. 371226633Sdim const BitVector &getSubClasses() const { return SubClasses; } 372226633Sdim 373226633Sdim // getSuperClasses - Returns a list of super classes ordered by EnumValue. 374226633Sdim // The array does not include an entry for this class. 375226633Sdim ArrayRef<CodeGenRegisterClass*> getSuperClasses() const { 376226633Sdim return SuperClasses; 377226633Sdim } 378226633Sdim 379224145Sdim // Returns an ordered list of class members. 380224145Sdim // The order of registers is the same as in the .td file. 381224145Sdim // No = 0 is the default allocation order, No = 1 is the first alternative. 382224145Sdim ArrayRef<Record*> getOrder(unsigned No = 0) const { 383226633Sdim return Orders[No]; 384224145Sdim } 385212904Sdim 386224145Sdim // Return the total number of allocation orders available. 387226633Sdim unsigned getNumOrders() const { return Orders.size(); } 388212904Sdim 389226633Sdim // Get the set of registers. This set contains the same registers as 390226633Sdim // getOrder(0). 391226633Sdim const CodeGenRegister::Set &getMembers() const { return Members; } 392226633Sdim 393239462Sdim // Get a bit vector of TopoSigs present in this register class. 394239462Sdim const BitVector &getTopoSigs() const { return TopoSigs; } 395239462Sdim 396234353Sdim // Populate a unique sorted list of units from a register set. 397234353Sdim void buildRegUnitSet(std::vector<unsigned> &RegUnits) const; 398234353Sdim 399224145Sdim CodeGenRegisterClass(CodeGenRegBank&, Record *R); 400226633Sdim 401226633Sdim // A key representing the parts of a register class used for forming 402226633Sdim // sub-classes. Note the ordering provided by this key is not the same as 403226633Sdim // the topological order used for the EnumValues. 404226633Sdim struct Key { 405226633Sdim const CodeGenRegister::Set *Members; 406226633Sdim unsigned SpillSize; 407226633Sdim unsigned SpillAlignment; 408226633Sdim 409226633Sdim Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0) 410226633Sdim : Members(M), SpillSize(S), SpillAlignment(A) {} 411226633Sdim 412226633Sdim Key(const CodeGenRegisterClass &RC) 413226633Sdim : Members(&RC.getMembers()), 414226633Sdim SpillSize(RC.SpillSize), 415226633Sdim SpillAlignment(RC.SpillAlignment) {} 416226633Sdim 417226633Sdim // Lexicographical order of (Members, SpillSize, SpillAlignment). 418226633Sdim bool operator<(const Key&) const; 419226633Sdim }; 420226633Sdim 421226633Sdim // Create a non-user defined register class. 422239462Sdim CodeGenRegisterClass(CodeGenRegBank&, StringRef Name, Key Props); 423226633Sdim 424226633Sdim // Called by CodeGenRegBank::CodeGenRegBank(). 425226633Sdim static void computeSubClasses(CodeGenRegBank&); 426193323Sed }; 427223017Sdim 428239462Sdim // Register units are used to model interference and register pressure. 429239462Sdim // Every register is assigned one or more register units such that two 430239462Sdim // registers overlap if and only if they have a register unit in common. 431239462Sdim // 432239462Sdim // Normally, one register unit is created per leaf register. Non-leaf 433239462Sdim // registers inherit the units of their sub-registers. 434239462Sdim struct RegUnit { 435239462Sdim // Weight assigned to this RegUnit for estimating register pressure. 436239462Sdim // This is useful when equalizing weights in register classes with mixed 437239462Sdim // register topologies. 438239462Sdim unsigned Weight; 439239462Sdim 440239462Sdim // Each native RegUnit corresponds to one or two root registers. The full 441239462Sdim // set of registers containing this unit can be computed as the union of 442239462Sdim // these two registers and their super-registers. 443239462Sdim const CodeGenRegister *Roots[2]; 444239462Sdim 445249423Sdim // Index into RegClassUnitSets where we can find the list of UnitSets that 446249423Sdim // contain this unit. 447249423Sdim unsigned RegClassUnitSetsIdx; 448239462Sdim 449276479Sdim RegUnit() : Weight(0), RegClassUnitSetsIdx(0) { 450276479Sdim Roots[0] = Roots[1] = nullptr; 451276479Sdim } 452249423Sdim 453239462Sdim ArrayRef<const CodeGenRegister*> getRoots() const { 454239462Sdim assert(!(Roots[1] && !Roots[0]) && "Invalid roots array"); 455239462Sdim return makeArrayRef(Roots, !!Roots[0] + !!Roots[1]); 456239462Sdim } 457239462Sdim }; 458239462Sdim 459234353Sdim // Each RegUnitSet is a sorted vector with a name. 460234353Sdim struct RegUnitSet { 461234353Sdim typedef std::vector<unsigned>::const_iterator iterator; 462234353Sdim 463234353Sdim std::string Name; 464234353Sdim std::vector<unsigned> Units; 465261991Sdim unsigned Weight; // Cache the sum of all unit weights. 466261991Sdim unsigned Order; // Cache the sort key. 467261991Sdim 468261991Sdim RegUnitSet() : Weight(0), Order(0) {} 469234353Sdim }; 470234353Sdim 471239462Sdim // Base vector for identifying TopoSigs. The contents uniquely identify a 472239462Sdim // TopoSig, only computeSuperRegs needs to know how. 473239462Sdim typedef SmallVector<unsigned, 16> TopoSigId; 474239462Sdim 475223017Sdim // CodeGenRegBank - Represent a target's registers and the relations between 476223017Sdim // them. 477223017Sdim class CodeGenRegBank { 478224145Sdim SetTheory Sets; 479224145Sdim 480280031Sdim std::deque<CodeGenSubRegIndex> SubRegIndices; 481234353Sdim DenseMap<Record*, CodeGenSubRegIndex*> Def2SubRegIdx; 482234353Sdim 483239462Sdim CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace); 484239462Sdim 485239462Sdim typedef std::map<SmallVector<CodeGenSubRegIndex*, 8>, 486239462Sdim CodeGenSubRegIndex*> ConcatIdxMap; 487239462Sdim ConcatIdxMap ConcatIdx; 488239462Sdim 489234353Sdim // Registers. 490280031Sdim std::deque<CodeGenRegister> Registers; 491243830Sdim StringMap<CodeGenRegister*> RegistersByName; 492223017Sdim DenseMap<Record*, CodeGenRegister*> Def2Reg; 493234353Sdim unsigned NumNativeRegUnits; 494223017Sdim 495239462Sdim std::map<TopoSigId, unsigned> TopoSigs; 496234353Sdim 497239462Sdim // Includes native (0..NumNativeRegUnits-1) and adopted register units. 498239462Sdim SmallVector<RegUnit, 8> RegUnits; 499239462Sdim 500226633Sdim // Register classes. 501280031Sdim std::list<CodeGenRegisterClass> RegClasses; 502224145Sdim DenseMap<Record*, CodeGenRegisterClass*> Def2RC; 503226633Sdim typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap; 504226633Sdim RCKeyMap Key2RC; 505224145Sdim 506234353Sdim // Remember each unique set of register units. Initially, this contains a 507234353Sdim // unique set for each register class. Simliar sets are coalesced with 508234353Sdim // pruneUnitSets and new supersets are inferred during computeRegUnitSets. 509234353Sdim std::vector<RegUnitSet> RegUnitSets; 510234353Sdim 511234353Sdim // Map RegisterClass index to the index of the RegUnitSet that contains the 512234353Sdim // class's units and any inferred RegUnit supersets. 513249423Sdim // 514249423Sdim // NOTE: This could grow beyond the number of register classes when we map 515249423Sdim // register units to lists of unit sets. If the list of unit sets does not 516249423Sdim // already exist for a register class, we create a new entry in this vector. 517234353Sdim std::vector<std::vector<unsigned> > RegClassUnitSets; 518234353Sdim 519261991Sdim // Give each register unit set an order based on sorting criteria. 520261991Sdim std::vector<unsigned> RegUnitSetOrder; 521261991Sdim 522226633Sdim // Add RC to *2RC maps. 523226633Sdim void addToMaps(CodeGenRegisterClass*); 524226633Sdim 525234353Sdim // Create a synthetic sub-class if it is missing. 526234353Sdim CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, 527234353Sdim const CodeGenRegister::Set *Membs, 528234353Sdim StringRef Name); 529234353Sdim 530226633Sdim // Infer missing register classes. 531226633Sdim void computeInferredRegisterClasses(); 532234353Sdim void inferCommonSubClass(CodeGenRegisterClass *RC); 533234353Sdim void inferSubClassWithSubReg(CodeGenRegisterClass *RC); 534280031Sdim void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) { 535280031Sdim inferMatchingSuperRegClass(RC, RegClasses.begin()); 536280031Sdim } 537226633Sdim 538280031Sdim void inferMatchingSuperRegClass( 539280031Sdim CodeGenRegisterClass *RC, 540280031Sdim std::list<CodeGenRegisterClass>::iterator FirstSubRegRC); 541280031Sdim 542234353Sdim // Iteratively prune unit sets. 543234353Sdim void pruneUnitSets(); 544223017Sdim 545234353Sdim // Compute a weight for each register unit created during getSubRegs. 546234353Sdim void computeRegUnitWeights(); 547234353Sdim 548234353Sdim // Create a RegUnitSet for each RegClass and infer superclasses. 549234353Sdim void computeRegUnitSets(); 550234353Sdim 551223017Sdim // Populate the Composite map from sub-register relationships. 552223017Sdim void computeComposites(); 553223017Sdim 554243830Sdim // Compute a lane mask for each sub-register index. 555280031Sdim void computeSubRegLaneMasks(); 556243830Sdim 557280031Sdim /// Computes a lane mask for each register unit enumerated by a physical 558280031Sdim /// register. 559280031Sdim void computeRegUnitLaneMasks(); 560280031Sdim 561223017Sdim public: 562223017Sdim CodeGenRegBank(RecordKeeper&); 563223017Sdim 564224145Sdim SetTheory &getSets() { return Sets; } 565224145Sdim 566223017Sdim // Sub-register indices. The first NumNamedIndices are defined by the user 567223017Sdim // in the .td files. The rest are synthesized such that all sub-registers 568223017Sdim // have a unique name. 569280031Sdim const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const { 570280031Sdim return SubRegIndices; 571280031Sdim } 572223017Sdim 573234353Sdim // Find a SubRegIndex form its Record def. 574234353Sdim CodeGenSubRegIndex *getSubRegIdx(Record*); 575223017Sdim 576223017Sdim // Find or create a sub-register index representing the A+B composition. 577234353Sdim CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A, 578234353Sdim CodeGenSubRegIndex *B); 579223017Sdim 580239462Sdim // Find or create a sub-register index representing the concatenation of 581239462Sdim // non-overlapping sibling indices. 582239462Sdim CodeGenSubRegIndex * 583261991Sdim getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8>&); 584239462Sdim 585239462Sdim void 586261991Sdim addConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts, 587239462Sdim CodeGenSubRegIndex *Idx) { 588239462Sdim ConcatIdx.insert(std::make_pair(Parts, Idx)); 589239462Sdim } 590239462Sdim 591280031Sdim const std::deque<CodeGenRegister> &getRegisters() { return Registers; } 592243830Sdim const StringMap<CodeGenRegister*> &getRegistersByName() { 593243830Sdim return RegistersByName; 594243830Sdim } 595223017Sdim 596223017Sdim // Find a register from its Record def. 597223017Sdim CodeGenRegister *getReg(Record*); 598223017Sdim 599234353Sdim // Get a Register's index into the Registers array. 600234353Sdim unsigned getRegIndex(const CodeGenRegister *Reg) const { 601234353Sdim return Reg->EnumValue - 1; 602234353Sdim } 603234353Sdim 604239462Sdim // Return the number of allocated TopoSigs. The first TopoSig representing 605239462Sdim // leaf registers is allocated number 0. 606239462Sdim unsigned getNumTopoSigs() const { 607239462Sdim return TopoSigs.size(); 608239462Sdim } 609239462Sdim 610239462Sdim // Find or create a TopoSig for the given TopoSigId. 611239462Sdim // This function is only for use by CodeGenRegister::computeSuperRegs(). 612239462Sdim // Others should simply use Reg->getTopoSig(). 613239462Sdim unsigned getTopoSig(const TopoSigId &Id) { 614239462Sdim return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second; 615239462Sdim } 616239462Sdim 617239462Sdim // Create a native register unit that is associated with one or two root 618239462Sdim // registers. 619276479Sdim unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) { 620239462Sdim RegUnits.resize(RegUnits.size() + 1); 621239462Sdim RegUnits.back().Roots[0] = R0; 622239462Sdim RegUnits.back().Roots[1] = R1; 623239462Sdim return RegUnits.size() - 1; 624239462Sdim } 625239462Sdim 626234353Sdim // Create a new non-native register unit that can be adopted by a register 627234353Sdim // to increase its pressure. Note that NumNativeRegUnits is not increased. 628234353Sdim unsigned newRegUnit(unsigned Weight) { 629239462Sdim RegUnits.resize(RegUnits.size() + 1); 630239462Sdim RegUnits.back().Weight = Weight; 631239462Sdim return RegUnits.size() - 1; 632234353Sdim } 633234353Sdim 634234353Sdim // Native units are the singular unit of a leaf register. Register aliasing 635234353Sdim // is completely characterized by native units. Adopted units exist to give 636234353Sdim // register additional weight but don't affect aliasing. 637234353Sdim bool isNativeUnit(unsigned RUID) { 638234353Sdim return RUID < NumNativeRegUnits; 639234353Sdim } 640234353Sdim 641239462Sdim unsigned getNumNativeRegUnits() const { 642239462Sdim return NumNativeRegUnits; 643239462Sdim } 644239462Sdim 645239462Sdim RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; } 646239462Sdim const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; } 647239462Sdim 648280031Sdim std::list<CodeGenRegisterClass> &getRegClasses() { return RegClasses; } 649280031Sdim 650280031Sdim const std::list<CodeGenRegisterClass> &getRegClasses() const { 651224145Sdim return RegClasses; 652224145Sdim } 653224145Sdim 654224145Sdim // Find a register class from its def. 655224145Sdim CodeGenRegisterClass *getRegClass(Record*); 656224145Sdim 657224145Sdim /// getRegisterClassForRegister - Find the register class that contains the 658224145Sdim /// specified physical register. If the register is not in a register 659224145Sdim /// class, return null. If the register is in multiple classes, and the 660224145Sdim /// classes have a superset-subset relationship and the same set of types, 661224145Sdim /// return the superclass. Otherwise return null. 662224145Sdim const CodeGenRegisterClass* getRegClassForRegister(Record *R); 663224145Sdim 664234353Sdim // Get the sum of unit weights. 665234353Sdim unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const { 666234353Sdim unsigned Weight = 0; 667234353Sdim for (std::vector<unsigned>::const_iterator 668234353Sdim I = Units.begin(), E = Units.end(); I != E; ++I) 669239462Sdim Weight += getRegUnit(*I).Weight; 670234353Sdim return Weight; 671234353Sdim } 672234353Sdim 673261991Sdim unsigned getRegSetIDAt(unsigned Order) const { 674261991Sdim return RegUnitSetOrder[Order]; 675261991Sdim } 676261991Sdim const RegUnitSet &getRegSetAt(unsigned Order) const { 677261991Sdim return RegUnitSets[RegUnitSetOrder[Order]]; 678261991Sdim } 679261991Sdim 680234353Sdim // Increase a RegUnitWeight. 681234353Sdim void increaseRegUnitWeight(unsigned RUID, unsigned Inc) { 682239462Sdim getRegUnit(RUID).Weight += Inc; 683234353Sdim } 684234353Sdim 685234353Sdim // Get the number of register pressure dimensions. 686234353Sdim unsigned getNumRegPressureSets() const { return RegUnitSets.size(); } 687234353Sdim 688234353Sdim // Get a set of register unit IDs for a given dimension of pressure. 689261991Sdim const RegUnitSet &getRegPressureSet(unsigned Idx) const { 690234353Sdim return RegUnitSets[Idx]; 691234353Sdim } 692234353Sdim 693249423Sdim // The number of pressure set lists may be larget than the number of 694249423Sdim // register classes if some register units appeared in a list of sets that 695249423Sdim // did not correspond to an existing register class. 696249423Sdim unsigned getNumRegClassPressureSetLists() const { 697249423Sdim return RegClassUnitSets.size(); 698249423Sdim } 699249423Sdim 700234353Sdim // Get a list of pressure set IDs for a register class. Liveness of a 701234353Sdim // register in this class impacts each pressure set in this list by the 702234353Sdim // weight of the register. An exact solution requires all registers in a 703234353Sdim // class to have the same class, but it is not strictly guaranteed. 704234353Sdim ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const { 705234353Sdim return RegClassUnitSets[RCIdx]; 706234353Sdim } 707234353Sdim 708223017Sdim // Computed derived records such as missing sub-register indices. 709223017Sdim void computeDerivedInfo(); 710224145Sdim 711234353Sdim // Compute the set of registers completely covered by the registers in Regs. 712234353Sdim // The returned BitVector will have a bit set for each register in Regs, 713234353Sdim // all sub-registers, and all super-registers that are covered by the 714234353Sdim // registers in Regs. 715234353Sdim // 716234353Sdim // This is used to compute the mask of call-preserved registers from a list 717234353Sdim // of callee-saves. 718234353Sdim BitVector computeCoveredRegisters(ArrayRef<Record*> Regs); 719261991Sdim 720261991Sdim // Bit mask of lanes that cover their registers. A sub-register index whose 721261991Sdim // LaneMask is contained in CoveringLanes will be completely covered by 722261991Sdim // another sub-register with the same or larger lane mask. 723261991Sdim unsigned CoveringLanes; 724223017Sdim }; 725193323Sed} 726193323Sed 727193323Sed#endif 728