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 15193323Sed#ifndef CODEGEN_REGISTERS_H 16193323Sed#define CODEGEN_REGISTERS_H 17193323Sed 18224145Sdim#include "SetTheory.h" 19224145Sdim#include "llvm/ADT/ArrayRef.h" 20226633Sdim#include "llvm/ADT/BitVector.h" 21208599Srdivacky#include "llvm/ADT/DenseMap.h" 22224145Sdim#include "llvm/ADT/SetVector.h" 23249423Sdim#include "llvm/CodeGen/ValueTypes.h" 24234353Sdim#include "llvm/Support/ErrorHandling.h" 25249423Sdim#include "llvm/TableGen/Record.h" 26223017Sdim#include <cstdlib> 27223017Sdim#include <map> 28249423Sdim#include <set> 29193323Sed#include <string> 30193323Sed#include <vector> 31193323Sed 32193323Sednamespace llvm { 33223017Sdim class CodeGenRegBank; 34193323Sed 35234353Sdim /// CodeGenSubRegIndex - Represents a sub-register index. 36234353Sdim class CodeGenSubRegIndex { 37234353Sdim Record *const TheDef; 38239462Sdim std::string Name; 39239462Sdim std::string Namespace; 40239462Sdim 41239462Sdim public: 42263508Sdim uint16_t Size; 43263508Sdim uint16_t Offset; 44234353Sdim const unsigned EnumValue; 45243830Sdim unsigned LaneMask; 46234353Sdim 47263508Sdim // Are all super-registers containing this SubRegIndex covered by their 48263508Sdim // sub-registers? 49263508Sdim bool AllSuperRegsCovered; 50263508Sdim 51234353Sdim CodeGenSubRegIndex(Record *R, unsigned Enum); 52239462Sdim CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum); 53234353Sdim 54239462Sdim const std::string &getName() const { return Name; } 55239462Sdim const std::string &getNamespace() const { return Namespace; } 56234353Sdim std::string getQualifiedName() const; 57234353Sdim 58234353Sdim // Order CodeGenSubRegIndex pointers by EnumValue. 59234353Sdim struct Less { 60234353Sdim bool operator()(const CodeGenSubRegIndex *A, 61234353Sdim const CodeGenSubRegIndex *B) const { 62234353Sdim assert(A && B); 63234353Sdim return A->EnumValue < B->EnumValue; 64234353Sdim } 65234353Sdim }; 66234353Sdim 67234353Sdim // Map of composite subreg indices. 68234353Sdim typedef std::map<CodeGenSubRegIndex*, CodeGenSubRegIndex*, Less> CompMap; 69234353Sdim 70234353Sdim // Returns the subreg index that results from composing this with Idx. 71234353Sdim // Returns NULL if this and Idx don't compose. 72234353Sdim CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const { 73234353Sdim CompMap::const_iterator I = Composed.find(Idx); 74234353Sdim return I == Composed.end() ? 0 : I->second; 75234353Sdim } 76234353Sdim 77234353Sdim // Add a composite subreg index: this+A = B. 78234353Sdim // Return a conflicting composite, or NULL 79234353Sdim CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, 80234353Sdim CodeGenSubRegIndex *B) { 81239462Sdim assert(A && B); 82234353Sdim std::pair<CompMap::iterator, bool> Ins = 83234353Sdim Composed.insert(std::make_pair(A, B)); 84263508Sdim // Synthetic subreg indices that aren't contiguous (for instance ARM 85263508Sdim // register tuples) don't have a bit range, so it's OK to let 86263508Sdim // B->Offset == -1. For the other cases, accumulate the offset and set 87263508Sdim // the size here. Only do so if there is no offset yet though. 88263508Sdim if ((Offset != (uint16_t)-1 && A->Offset != (uint16_t)-1) && 89263508Sdim (B->Offset == (uint16_t)-1)) { 90263508Sdim B->Offset = Offset + A->Offset; 91263508Sdim B->Size = A->Size; 92263508Sdim } 93234353Sdim return (Ins.second || Ins.first->second == B) ? 0 : Ins.first->second; 94234353Sdim } 95234353Sdim 96234353Sdim // Update the composite maps of components specified in 'ComposedOf'. 97234353Sdim void updateComponents(CodeGenRegBank&); 98234353Sdim 99234353Sdim // Return the map of composites. 100234353Sdim const CompMap &getComposites() const { return Composed; } 101234353Sdim 102243830Sdim // Compute LaneMask from Composed. Return LaneMask. 103243830Sdim unsigned computeLaneMask(); 104243830Sdim 105234353Sdim private: 106234353Sdim CompMap Composed; 107234353Sdim }; 108234353Sdim 109193323Sed /// CodeGenRegister - Represents a register definition. 110193323Sed struct CodeGenRegister { 111193323Sed Record *TheDef; 112221345Sdim unsigned EnumValue; 113221345Sdim unsigned CostPerUse; 114234353Sdim bool CoveredBySubRegs; 115223017Sdim 116223017Sdim // Map SubRegIndex -> Register. 117234353Sdim typedef std::map<CodeGenSubRegIndex*, CodeGenRegister*, 118234353Sdim CodeGenSubRegIndex::Less> SubRegMap; 119223017Sdim 120223017Sdim CodeGenRegister(Record *R, unsigned Enum); 121223017Sdim 122223017Sdim const std::string &getName() const; 123223017Sdim 124239462Sdim // Extract more information from TheDef. This is used to build an object 125239462Sdim // graph after all CodeGenRegister objects have been created. 126239462Sdim void buildObjectGraph(CodeGenRegBank&); 127239462Sdim 128239462Sdim // Lazily compute a map of all sub-registers. 129223017Sdim // This includes unique entries for all sub-sub-registers. 130239462Sdim const SubRegMap &computeSubRegs(CodeGenRegBank&); 131223017Sdim 132239462Sdim // Compute extra sub-registers by combining the existing sub-registers. 133239462Sdim void computeSecondarySubRegs(CodeGenRegBank&); 134239462Sdim 135239462Sdim // Add this as a super-register to all sub-registers after the sub-register 136239462Sdim // graph has been built. 137239462Sdim void computeSuperRegs(CodeGenRegBank&); 138239462Sdim 139223017Sdim const SubRegMap &getSubRegs() const { 140223017Sdim assert(SubRegsComplete && "Must precompute sub-registers"); 141223017Sdim return SubRegs; 142223017Sdim } 143223017Sdim 144224145Sdim // Add sub-registers to OSet following a pre-order defined by the .td file. 145234353Sdim void addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet, 146234353Sdim CodeGenRegBank&) const; 147224145Sdim 148239462Sdim // Return the sub-register index naming Reg as a sub-register of this 149239462Sdim // register. Returns NULL if Reg is not a sub-register. 150239462Sdim CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const { 151239462Sdim return SubReg2Idx.lookup(Reg); 152239462Sdim } 153239462Sdim 154234353Sdim typedef std::vector<const CodeGenRegister*> SuperRegList; 155224145Sdim 156239462Sdim // Get the list of super-registers in topological order, small to large. 157239462Sdim // This is valid after computeSubRegs visits all registers during RegBank 158239462Sdim // construction. 159224145Sdim const SuperRegList &getSuperRegs() const { 160224145Sdim assert(SubRegsComplete && "Must precompute sub-registers"); 161224145Sdim return SuperRegs; 162224145Sdim } 163224145Sdim 164239462Sdim // Get the list of ad hoc aliases. The graph is symmetric, so the list 165239462Sdim // contains all registers in 'Aliases', and all registers that mention this 166239462Sdim // register in 'Aliases'. 167239462Sdim ArrayRef<CodeGenRegister*> getExplicitAliases() const { 168239462Sdim return ExplicitAliases; 169239462Sdim } 170239462Sdim 171239462Sdim // Get the topological signature of this register. This is a small integer 172239462Sdim // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have 173239462Sdim // identical sub-register structure. That is, they support the same set of 174239462Sdim // sub-register indices mapping to the same kind of sub-registers 175239462Sdim // (TopoSig-wise). 176239462Sdim unsigned getTopoSig() const { 177239462Sdim assert(SuperRegsComplete && "TopoSigs haven't been computed yet."); 178239462Sdim return TopoSig; 179239462Sdim } 180239462Sdim 181234353Sdim // List of register units in ascending order. 182234353Sdim typedef SmallVector<unsigned, 16> RegUnitList; 183234353Sdim 184239462Sdim // How many entries in RegUnitList are native? 185239462Sdim unsigned NumNativeRegUnits; 186239462Sdim 187234353Sdim // Get the list of register units. 188239462Sdim // This is only valid after computeSubRegs() completes. 189234353Sdim const RegUnitList &getRegUnits() const { return RegUnits; } 190234353Sdim 191239462Sdim // Get the native register units. This is a prefix of getRegUnits(). 192239462Sdim ArrayRef<unsigned> getNativeRegUnits() const { 193239462Sdim return makeArrayRef(RegUnits).slice(0, NumNativeRegUnits); 194239462Sdim } 195239462Sdim 196234353Sdim // Inherit register units from subregisters. 197234353Sdim // Return true if the RegUnits changed. 198234353Sdim bool inheritRegUnits(CodeGenRegBank &RegBank); 199234353Sdim 200234353Sdim // Adopt a register unit for pressure tracking. 201234353Sdim // A unit is adopted iff its unit number is >= NumNativeRegUnits. 202234353Sdim void adoptRegUnit(unsigned RUID) { RegUnits.push_back(RUID); } 203234353Sdim 204234353Sdim // Get the sum of this register's register unit weights. 205234353Sdim unsigned getWeight(const CodeGenRegBank &RegBank) const; 206234353Sdim 207224145Sdim // Order CodeGenRegister pointers by EnumValue. 208224145Sdim struct Less { 209224145Sdim bool operator()(const CodeGenRegister *A, 210224145Sdim const CodeGenRegister *B) const { 211226633Sdim assert(A && B); 212224145Sdim return A->EnumValue < B->EnumValue; 213224145Sdim } 214224145Sdim }; 215224145Sdim 216224145Sdim // Canonically ordered set. 217224145Sdim typedef std::set<const CodeGenRegister*, Less> Set; 218224145Sdim 219223017Sdim private: 220223017Sdim bool SubRegsComplete; 221239462Sdim bool SuperRegsComplete; 222239462Sdim unsigned TopoSig; 223239462Sdim 224239462Sdim // The sub-registers explicit in the .td file form a tree. 225239462Sdim SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices; 226239462Sdim SmallVector<CodeGenRegister*, 8> ExplicitSubRegs; 227239462Sdim 228239462Sdim // Explicit ad hoc aliases, symmetrized to form an undirected graph. 229239462Sdim SmallVector<CodeGenRegister*, 8> ExplicitAliases; 230239462Sdim 231239462Sdim // Super-registers where this is the first explicit sub-register. 232239462Sdim SuperRegList LeadingSuperRegs; 233239462Sdim 234223017Sdim SubRegMap SubRegs; 235224145Sdim SuperRegList SuperRegs; 236239462Sdim DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx; 237234353Sdim RegUnitList RegUnits; 238193323Sed }; 239193323Sed 240193323Sed 241224145Sdim class CodeGenRegisterClass { 242224145Sdim CodeGenRegister::Set Members; 243226633Sdim // Allocation orders. Order[0] always contains all registers in Members. 244226633Sdim std::vector<SmallVector<Record*, 16> > Orders; 245226633Sdim // Bit mask of sub-classes including this, indexed by their EnumValue. 246226633Sdim BitVector SubClasses; 247226633Sdim // List of super-classes, topologocally ordered to have the larger classes 248226633Sdim // first. This is the same as sorting by EnumValue. 249226633Sdim SmallVector<CodeGenRegisterClass*, 4> SuperClasses; 250226633Sdim Record *TheDef; 251226633Sdim std::string Name; 252226633Sdim 253226633Sdim // For a synthesized class, inherit missing properties from the nearest 254226633Sdim // super-class. 255226633Sdim void inheritProperties(CodeGenRegBank&); 256226633Sdim 257234353Sdim // Map SubRegIndex -> sub-class. This is the largest sub-class where all 258234353Sdim // registers have a SubRegIndex sub-register. 259234353Sdim DenseMap<CodeGenSubRegIndex*, CodeGenRegisterClass*> SubClassWithSubReg; 260226633Sdim 261234353Sdim // Map SubRegIndex -> set of super-reg classes. This is all register 262234353Sdim // classes SuperRC such that: 263234353Sdim // 264234353Sdim // R:SubRegIndex in this RC for all R in SuperRC. 265234353Sdim // 266234353Sdim DenseMap<CodeGenSubRegIndex*, 267234353Sdim SmallPtrSet<CodeGenRegisterClass*, 8> > SuperRegClasses; 268234353Sdim 269239462Sdim // Bit vector of TopoSigs for the registers in this class. This will be 270239462Sdim // very sparse on regular architectures. 271239462Sdim BitVector TopoSigs; 272239462Sdim 273224145Sdim public: 274226633Sdim unsigned EnumValue; 275193323Sed std::string Namespace; 276249423Sdim SmallVector<MVT::SimpleValueType, 4> VTs; 277193323Sed unsigned SpillSize; 278193323Sed unsigned SpillAlignment; 279193323Sed int CopyCost; 280223017Sdim bool Allocatable; 281224145Sdim std::string AltOrderSelect; 282193323Sed 283226633Sdim // Return the Record that defined this class, or NULL if the class was 284226633Sdim // created by TableGen. 285226633Sdim Record *getDef() const { return TheDef; } 286226633Sdim 287226633Sdim const std::string &getName() const { return Name; } 288226633Sdim std::string getQualifiedName() const; 289249423Sdim ArrayRef<MVT::SimpleValueType> getValueTypes() const {return VTs;} 290193323Sed unsigned getNumValueTypes() const { return VTs.size(); } 291221345Sdim 292193323Sed MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const { 293193323Sed if (VTNum < VTs.size()) 294193323Sed return VTs[VTNum]; 295234353Sdim llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!"); 296193323Sed } 297221345Sdim 298224145Sdim // Return true if this this class contains the register. 299224145Sdim bool contains(const CodeGenRegister*) const; 300221345Sdim 301224145Sdim // Returns true if RC is a subclass. 302212904Sdim // RC is a sub-class of this class if it is a valid replacement for any 303221345Sdim // instruction operand where a register of this classis required. It must 304212904Sdim // satisfy these conditions: 305212904Sdim // 306212904Sdim // 1. All RC registers are also in this. 307212904Sdim // 2. The RC spill size must not be smaller than our spill size. 308212904Sdim // 3. RC spill alignment must be compatible with ours. 309212904Sdim // 310226633Sdim bool hasSubClass(const CodeGenRegisterClass *RC) const { 311226633Sdim return SubClasses.test(RC->EnumValue); 312226633Sdim } 313193323Sed 314226633Sdim // getSubClassWithSubReg - Returns the largest sub-class where all 315226633Sdim // registers have a SubIdx sub-register. 316234353Sdim CodeGenRegisterClass* 317234353Sdim getSubClassWithSubReg(CodeGenSubRegIndex *SubIdx) const { 318226633Sdim return SubClassWithSubReg.lookup(SubIdx); 319226633Sdim } 320226633Sdim 321234353Sdim void setSubClassWithSubReg(CodeGenSubRegIndex *SubIdx, 322234353Sdim CodeGenRegisterClass *SubRC) { 323226633Sdim SubClassWithSubReg[SubIdx] = SubRC; 324226633Sdim } 325226633Sdim 326234353Sdim // getSuperRegClasses - Returns a bit vector of all register classes 327234353Sdim // containing only SubIdx super-registers of this class. 328234353Sdim void getSuperRegClasses(CodeGenSubRegIndex *SubIdx, BitVector &Out) const; 329234353Sdim 330234353Sdim // addSuperRegClass - Add a class containing only SudIdx super-registers. 331234353Sdim void addSuperRegClass(CodeGenSubRegIndex *SubIdx, 332234353Sdim CodeGenRegisterClass *SuperRC) { 333234353Sdim SuperRegClasses[SubIdx].insert(SuperRC); 334234353Sdim } 335234353Sdim 336226633Sdim // getSubClasses - Returns a constant BitVector of subclasses indexed by 337226633Sdim // EnumValue. 338226633Sdim // The SubClasses vector includs an entry for this class. 339226633Sdim const BitVector &getSubClasses() const { return SubClasses; } 340226633Sdim 341226633Sdim // getSuperClasses - Returns a list of super classes ordered by EnumValue. 342226633Sdim // The array does not include an entry for this class. 343226633Sdim ArrayRef<CodeGenRegisterClass*> getSuperClasses() const { 344226633Sdim return SuperClasses; 345226633Sdim } 346226633Sdim 347224145Sdim // Returns an ordered list of class members. 348224145Sdim // The order of registers is the same as in the .td file. 349224145Sdim // No = 0 is the default allocation order, No = 1 is the first alternative. 350224145Sdim ArrayRef<Record*> getOrder(unsigned No = 0) const { 351226633Sdim return Orders[No]; 352224145Sdim } 353212904Sdim 354224145Sdim // Return the total number of allocation orders available. 355226633Sdim unsigned getNumOrders() const { return Orders.size(); } 356212904Sdim 357226633Sdim // Get the set of registers. This set contains the same registers as 358226633Sdim // getOrder(0). 359226633Sdim const CodeGenRegister::Set &getMembers() const { return Members; } 360226633Sdim 361239462Sdim // Get a bit vector of TopoSigs present in this register class. 362239462Sdim const BitVector &getTopoSigs() const { return TopoSigs; } 363239462Sdim 364234353Sdim // Populate a unique sorted list of units from a register set. 365234353Sdim void buildRegUnitSet(std::vector<unsigned> &RegUnits) const; 366234353Sdim 367224145Sdim CodeGenRegisterClass(CodeGenRegBank&, Record *R); 368226633Sdim 369226633Sdim // A key representing the parts of a register class used for forming 370226633Sdim // sub-classes. Note the ordering provided by this key is not the same as 371226633Sdim // the topological order used for the EnumValues. 372226633Sdim struct Key { 373226633Sdim const CodeGenRegister::Set *Members; 374226633Sdim unsigned SpillSize; 375226633Sdim unsigned SpillAlignment; 376226633Sdim 377226633Sdim Key(const Key &O) 378226633Sdim : Members(O.Members), 379226633Sdim SpillSize(O.SpillSize), 380226633Sdim SpillAlignment(O.SpillAlignment) {} 381226633Sdim 382226633Sdim Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0) 383226633Sdim : Members(M), SpillSize(S), SpillAlignment(A) {} 384226633Sdim 385226633Sdim Key(const CodeGenRegisterClass &RC) 386226633Sdim : Members(&RC.getMembers()), 387226633Sdim SpillSize(RC.SpillSize), 388226633Sdim SpillAlignment(RC.SpillAlignment) {} 389226633Sdim 390226633Sdim // Lexicographical order of (Members, SpillSize, SpillAlignment). 391226633Sdim bool operator<(const Key&) const; 392226633Sdim }; 393226633Sdim 394226633Sdim // Create a non-user defined register class. 395239462Sdim CodeGenRegisterClass(CodeGenRegBank&, StringRef Name, Key Props); 396226633Sdim 397226633Sdim // Called by CodeGenRegBank::CodeGenRegBank(). 398226633Sdim static void computeSubClasses(CodeGenRegBank&); 399193323Sed }; 400223017Sdim 401239462Sdim // Register units are used to model interference and register pressure. 402239462Sdim // Every register is assigned one or more register units such that two 403239462Sdim // registers overlap if and only if they have a register unit in common. 404239462Sdim // 405239462Sdim // Normally, one register unit is created per leaf register. Non-leaf 406239462Sdim // registers inherit the units of their sub-registers. 407239462Sdim struct RegUnit { 408239462Sdim // Weight assigned to this RegUnit for estimating register pressure. 409239462Sdim // This is useful when equalizing weights in register classes with mixed 410239462Sdim // register topologies. 411239462Sdim unsigned Weight; 412239462Sdim 413239462Sdim // Each native RegUnit corresponds to one or two root registers. The full 414239462Sdim // set of registers containing this unit can be computed as the union of 415239462Sdim // these two registers and their super-registers. 416239462Sdim const CodeGenRegister *Roots[2]; 417239462Sdim 418249423Sdim // Index into RegClassUnitSets where we can find the list of UnitSets that 419249423Sdim // contain this unit. 420249423Sdim unsigned RegClassUnitSetsIdx; 421239462Sdim 422249423Sdim RegUnit() : Weight(0), RegClassUnitSetsIdx(0) { Roots[0] = Roots[1] = 0; } 423249423Sdim 424239462Sdim ArrayRef<const CodeGenRegister*> getRoots() const { 425239462Sdim assert(!(Roots[1] && !Roots[0]) && "Invalid roots array"); 426239462Sdim return makeArrayRef(Roots, !!Roots[0] + !!Roots[1]); 427239462Sdim } 428239462Sdim }; 429239462Sdim 430234353Sdim // Each RegUnitSet is a sorted vector with a name. 431234353Sdim struct RegUnitSet { 432234353Sdim typedef std::vector<unsigned>::const_iterator iterator; 433234353Sdim 434234353Sdim std::string Name; 435234353Sdim std::vector<unsigned> Units; 436263508Sdim unsigned Weight; // Cache the sum of all unit weights. 437263508Sdim unsigned Order; // Cache the sort key. 438263508Sdim 439263508Sdim RegUnitSet() : Weight(0), Order(0) {} 440234353Sdim }; 441234353Sdim 442239462Sdim // Base vector for identifying TopoSigs. The contents uniquely identify a 443239462Sdim // TopoSig, only computeSuperRegs needs to know how. 444239462Sdim typedef SmallVector<unsigned, 16> TopoSigId; 445239462Sdim 446223017Sdim // CodeGenRegBank - Represent a target's registers and the relations between 447223017Sdim // them. 448223017Sdim class CodeGenRegBank { 449224145Sdim SetTheory Sets; 450224145Sdim 451234353Sdim // SubRegIndices. 452234353Sdim std::vector<CodeGenSubRegIndex*> SubRegIndices; 453234353Sdim DenseMap<Record*, CodeGenSubRegIndex*> Def2SubRegIdx; 454234353Sdim 455239462Sdim CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace); 456239462Sdim 457239462Sdim typedef std::map<SmallVector<CodeGenSubRegIndex*, 8>, 458239462Sdim CodeGenSubRegIndex*> ConcatIdxMap; 459239462Sdim ConcatIdxMap ConcatIdx; 460239462Sdim 461234353Sdim // Registers. 462224145Sdim std::vector<CodeGenRegister*> Registers; 463243830Sdim StringMap<CodeGenRegister*> RegistersByName; 464223017Sdim DenseMap<Record*, CodeGenRegister*> Def2Reg; 465234353Sdim unsigned NumNativeRegUnits; 466223017Sdim 467239462Sdim std::map<TopoSigId, unsigned> TopoSigs; 468234353Sdim 469239462Sdim // Includes native (0..NumNativeRegUnits-1) and adopted register units. 470239462Sdim SmallVector<RegUnit, 8> RegUnits; 471239462Sdim 472226633Sdim // Register classes. 473226633Sdim std::vector<CodeGenRegisterClass*> RegClasses; 474224145Sdim DenseMap<Record*, CodeGenRegisterClass*> Def2RC; 475226633Sdim typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap; 476226633Sdim RCKeyMap Key2RC; 477224145Sdim 478234353Sdim // Remember each unique set of register units. Initially, this contains a 479234353Sdim // unique set for each register class. Simliar sets are coalesced with 480234353Sdim // pruneUnitSets and new supersets are inferred during computeRegUnitSets. 481234353Sdim std::vector<RegUnitSet> RegUnitSets; 482234353Sdim 483234353Sdim // Map RegisterClass index to the index of the RegUnitSet that contains the 484234353Sdim // class's units and any inferred RegUnit supersets. 485249423Sdim // 486249423Sdim // NOTE: This could grow beyond the number of register classes when we map 487249423Sdim // register units to lists of unit sets. If the list of unit sets does not 488249423Sdim // already exist for a register class, we create a new entry in this vector. 489234353Sdim std::vector<std::vector<unsigned> > RegClassUnitSets; 490234353Sdim 491263508Sdim // Give each register unit set an order based on sorting criteria. 492263508Sdim std::vector<unsigned> RegUnitSetOrder; 493263508Sdim 494226633Sdim // Add RC to *2RC maps. 495226633Sdim void addToMaps(CodeGenRegisterClass*); 496226633Sdim 497234353Sdim // Create a synthetic sub-class if it is missing. 498234353Sdim CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, 499234353Sdim const CodeGenRegister::Set *Membs, 500234353Sdim StringRef Name); 501234353Sdim 502226633Sdim // Infer missing register classes. 503226633Sdim void computeInferredRegisterClasses(); 504234353Sdim void inferCommonSubClass(CodeGenRegisterClass *RC); 505234353Sdim void inferSubClassWithSubReg(CodeGenRegisterClass *RC); 506234353Sdim void inferMatchingSuperRegClass(CodeGenRegisterClass *RC, 507234353Sdim unsigned FirstSubRegRC = 0); 508226633Sdim 509234353Sdim // Iteratively prune unit sets. 510234353Sdim void pruneUnitSets(); 511223017Sdim 512234353Sdim // Compute a weight for each register unit created during getSubRegs. 513234353Sdim void computeRegUnitWeights(); 514234353Sdim 515234353Sdim // Create a RegUnitSet for each RegClass and infer superclasses. 516234353Sdim void computeRegUnitSets(); 517234353Sdim 518223017Sdim // Populate the Composite map from sub-register relationships. 519223017Sdim void computeComposites(); 520223017Sdim 521243830Sdim // Compute a lane mask for each sub-register index. 522243830Sdim void computeSubRegIndexLaneMasks(); 523243830Sdim 524223017Sdim public: 525223017Sdim CodeGenRegBank(RecordKeeper&); 526223017Sdim 527224145Sdim SetTheory &getSets() { return Sets; } 528224145Sdim 529223017Sdim // Sub-register indices. The first NumNamedIndices are defined by the user 530223017Sdim // in the .td files. The rest are synthesized such that all sub-registers 531223017Sdim // have a unique name. 532234353Sdim ArrayRef<CodeGenSubRegIndex*> getSubRegIndices() { return SubRegIndices; } 533223017Sdim 534234353Sdim // Find a SubRegIndex form its Record def. 535234353Sdim CodeGenSubRegIndex *getSubRegIdx(Record*); 536223017Sdim 537223017Sdim // Find or create a sub-register index representing the A+B composition. 538234353Sdim CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A, 539234353Sdim CodeGenSubRegIndex *B); 540223017Sdim 541239462Sdim // Find or create a sub-register index representing the concatenation of 542239462Sdim // non-overlapping sibling indices. 543239462Sdim CodeGenSubRegIndex * 544263508Sdim getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8>&); 545239462Sdim 546239462Sdim void 547263508Sdim addConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts, 548239462Sdim CodeGenSubRegIndex *Idx) { 549239462Sdim ConcatIdx.insert(std::make_pair(Parts, Idx)); 550239462Sdim } 551239462Sdim 552224145Sdim const std::vector<CodeGenRegister*> &getRegisters() { return Registers; } 553243830Sdim const StringMap<CodeGenRegister*> &getRegistersByName() { 554243830Sdim return RegistersByName; 555243830Sdim } 556223017Sdim 557223017Sdim // Find a register from its Record def. 558223017Sdim CodeGenRegister *getReg(Record*); 559223017Sdim 560234353Sdim // Get a Register's index into the Registers array. 561234353Sdim unsigned getRegIndex(const CodeGenRegister *Reg) const { 562234353Sdim return Reg->EnumValue - 1; 563234353Sdim } 564234353Sdim 565239462Sdim // Return the number of allocated TopoSigs. The first TopoSig representing 566239462Sdim // leaf registers is allocated number 0. 567239462Sdim unsigned getNumTopoSigs() const { 568239462Sdim return TopoSigs.size(); 569239462Sdim } 570239462Sdim 571239462Sdim // Find or create a TopoSig for the given TopoSigId. 572239462Sdim // This function is only for use by CodeGenRegister::computeSuperRegs(). 573239462Sdim // Others should simply use Reg->getTopoSig(). 574239462Sdim unsigned getTopoSig(const TopoSigId &Id) { 575239462Sdim return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second; 576239462Sdim } 577239462Sdim 578239462Sdim // Create a native register unit that is associated with one or two root 579239462Sdim // registers. 580239462Sdim unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = 0) { 581239462Sdim RegUnits.resize(RegUnits.size() + 1); 582239462Sdim RegUnits.back().Roots[0] = R0; 583239462Sdim RegUnits.back().Roots[1] = R1; 584239462Sdim return RegUnits.size() - 1; 585239462Sdim } 586239462Sdim 587234353Sdim // Create a new non-native register unit that can be adopted by a register 588234353Sdim // to increase its pressure. Note that NumNativeRegUnits is not increased. 589234353Sdim unsigned newRegUnit(unsigned Weight) { 590239462Sdim RegUnits.resize(RegUnits.size() + 1); 591239462Sdim RegUnits.back().Weight = Weight; 592239462Sdim return RegUnits.size() - 1; 593234353Sdim } 594234353Sdim 595234353Sdim // Native units are the singular unit of a leaf register. Register aliasing 596234353Sdim // is completely characterized by native units. Adopted units exist to give 597234353Sdim // register additional weight but don't affect aliasing. 598234353Sdim bool isNativeUnit(unsigned RUID) { 599234353Sdim return RUID < NumNativeRegUnits; 600234353Sdim } 601234353Sdim 602239462Sdim unsigned getNumNativeRegUnits() const { 603239462Sdim return NumNativeRegUnits; 604239462Sdim } 605239462Sdim 606239462Sdim RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; } 607239462Sdim const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; } 608239462Sdim 609226633Sdim ArrayRef<CodeGenRegisterClass*> getRegClasses() const { 610224145Sdim return RegClasses; 611224145Sdim } 612224145Sdim 613224145Sdim // Find a register class from its def. 614224145Sdim CodeGenRegisterClass *getRegClass(Record*); 615224145Sdim 616224145Sdim /// getRegisterClassForRegister - Find the register class that contains the 617224145Sdim /// specified physical register. If the register is not in a register 618224145Sdim /// class, return null. If the register is in multiple classes, and the 619224145Sdim /// classes have a superset-subset relationship and the same set of types, 620224145Sdim /// return the superclass. Otherwise return null. 621224145Sdim const CodeGenRegisterClass* getRegClassForRegister(Record *R); 622224145Sdim 623234353Sdim // Get the sum of unit weights. 624234353Sdim unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const { 625234353Sdim unsigned Weight = 0; 626234353Sdim for (std::vector<unsigned>::const_iterator 627234353Sdim I = Units.begin(), E = Units.end(); I != E; ++I) 628239462Sdim Weight += getRegUnit(*I).Weight; 629234353Sdim return Weight; 630234353Sdim } 631234353Sdim 632263508Sdim unsigned getRegSetIDAt(unsigned Order) const { 633263508Sdim return RegUnitSetOrder[Order]; 634263508Sdim } 635263508Sdim const RegUnitSet &getRegSetAt(unsigned Order) const { 636263508Sdim return RegUnitSets[RegUnitSetOrder[Order]]; 637263508Sdim } 638263508Sdim 639234353Sdim // Increase a RegUnitWeight. 640234353Sdim void increaseRegUnitWeight(unsigned RUID, unsigned Inc) { 641239462Sdim getRegUnit(RUID).Weight += Inc; 642234353Sdim } 643234353Sdim 644234353Sdim // Get the number of register pressure dimensions. 645234353Sdim unsigned getNumRegPressureSets() const { return RegUnitSets.size(); } 646234353Sdim 647234353Sdim // Get a set of register unit IDs for a given dimension of pressure. 648263508Sdim const RegUnitSet &getRegPressureSet(unsigned Idx) const { 649234353Sdim return RegUnitSets[Idx]; 650234353Sdim } 651234353Sdim 652249423Sdim // The number of pressure set lists may be larget than the number of 653249423Sdim // register classes if some register units appeared in a list of sets that 654249423Sdim // did not correspond to an existing register class. 655249423Sdim unsigned getNumRegClassPressureSetLists() const { 656249423Sdim return RegClassUnitSets.size(); 657249423Sdim } 658249423Sdim 659234353Sdim // Get a list of pressure set IDs for a register class. Liveness of a 660234353Sdim // register in this class impacts each pressure set in this list by the 661234353Sdim // weight of the register. An exact solution requires all registers in a 662234353Sdim // class to have the same class, but it is not strictly guaranteed. 663234353Sdim ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const { 664234353Sdim return RegClassUnitSets[RCIdx]; 665234353Sdim } 666234353Sdim 667223017Sdim // Computed derived records such as missing sub-register indices. 668223017Sdim void computeDerivedInfo(); 669224145Sdim 670234353Sdim // Compute the set of registers completely covered by the registers in Regs. 671234353Sdim // The returned BitVector will have a bit set for each register in Regs, 672234353Sdim // all sub-registers, and all super-registers that are covered by the 673234353Sdim // registers in Regs. 674234353Sdim // 675234353Sdim // This is used to compute the mask of call-preserved registers from a list 676234353Sdim // of callee-saves. 677234353Sdim BitVector computeCoveredRegisters(ArrayRef<Record*> Regs); 678263508Sdim 679263508Sdim // Bit mask of lanes that cover their registers. A sub-register index whose 680263508Sdim // LaneMask is contained in CoveringLanes will be completely covered by 681263508Sdim // another sub-register with the same or larger lane mask. 682263508Sdim unsigned CoveringLanes; 683223017Sdim }; 684193323Sed} 685193323Sed 686193323Sed#endif 687