1 //===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines structures to encapsulate information gleaned from the 10 // target register and register class definitions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 15 #define LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 16 17 #include "CodeGenHwModes.h" 18 #include "InfoByHwMode.h" 19 #include "llvm/ADT/ArrayRef.h" 20 #include "llvm/ADT/BitVector.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/STLExtras.h" 23 #include "llvm/ADT/SetVector.h" 24 #include "llvm/ADT/SmallPtrSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/SparseBitVector.h" 27 #include "llvm/ADT/StringMap.h" 28 #include "llvm/ADT/StringRef.h" 29 #include "llvm/MC/LaneBitmask.h" 30 #include "llvm/Support/ErrorHandling.h" 31 #include "llvm/TableGen/Record.h" 32 #include "llvm/TableGen/SetTheory.h" 33 #include <cassert> 34 #include <cstdint> 35 #include <deque> 36 #include <functional> 37 #include <list> 38 #include <map> 39 #include <memory> 40 #include <optional> 41 #include <string> 42 #include <utility> 43 #include <vector> 44 45 namespace llvm { 46 47 class CodeGenRegBank; 48 49 /// Used to encode a step in a register lane mask transformation. 50 /// Mask the bits specified in Mask, then rotate them Rol bits to the left 51 /// assuming a wraparound at 32bits. 52 struct MaskRolPair { 53 LaneBitmask Mask; 54 uint8_t RotateLeft; 55 56 bool operator==(const MaskRolPair Other) const { 57 return Mask == Other.Mask && RotateLeft == Other.RotateLeft; 58 } 59 bool operator!=(const MaskRolPair Other) const { 60 return Mask != Other.Mask || RotateLeft != Other.RotateLeft; 61 } 62 }; 63 64 /// CodeGenSubRegIndex - Represents a sub-register index. 65 class CodeGenSubRegIndex { 66 Record *const TheDef; 67 std::string Name; 68 std::string Namespace; 69 70 public: 71 uint16_t Size; 72 uint16_t Offset; 73 const unsigned EnumValue; 74 mutable LaneBitmask LaneMask; 75 mutable SmallVector<MaskRolPair,1> CompositionLaneMaskTransform; 76 77 /// A list of subregister indexes concatenated resulting in this 78 /// subregister index. This is the reverse of CodeGenRegBank::ConcatIdx. 79 SmallVector<CodeGenSubRegIndex*,4> ConcatenationOf; 80 81 // Are all super-registers containing this SubRegIndex covered by their 82 // sub-registers? 83 bool AllSuperRegsCovered; 84 // A subregister index is "artificial" if every subregister obtained 85 // from applying this index is artificial. Artificial subregister 86 // indexes are not used to create new register classes. 87 bool Artificial; 88 89 CodeGenSubRegIndex(Record *R, unsigned Enum); 90 CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum); 91 CodeGenSubRegIndex(CodeGenSubRegIndex&) = delete; 92 getName()93 const std::string &getName() const { return Name; } getNamespace()94 const std::string &getNamespace() const { return Namespace; } 95 std::string getQualifiedName() const; 96 97 // Map of composite subreg indices. 98 typedef std::map<CodeGenSubRegIndex *, CodeGenSubRegIndex *, 99 deref<std::less<>>> 100 CompMap; 101 102 // Returns the subreg index that results from composing this with Idx. 103 // Returns NULL if this and Idx don't compose. compose(CodeGenSubRegIndex * Idx)104 CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const { 105 CompMap::const_iterator I = Composed.find(Idx); 106 return I == Composed.end() ? nullptr : I->second; 107 } 108 109 // Add a composite subreg index: this+A = B. 110 // Return a conflicting composite, or NULL addComposite(CodeGenSubRegIndex * A,CodeGenSubRegIndex * B)111 CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, 112 CodeGenSubRegIndex *B) { 113 assert(A && B); 114 std::pair<CompMap::iterator, bool> Ins = 115 Composed.insert(std::make_pair(A, B)); 116 // Synthetic subreg indices that aren't contiguous (for instance ARM 117 // register tuples) don't have a bit range, so it's OK to let 118 // B->Offset == -1. For the other cases, accumulate the offset and set 119 // the size here. Only do so if there is no offset yet though. 120 if ((Offset != (uint16_t)-1 && A->Offset != (uint16_t)-1) && 121 (B->Offset == (uint16_t)-1)) { 122 B->Offset = Offset + A->Offset; 123 B->Size = A->Size; 124 } 125 return (Ins.second || Ins.first->second == B) ? nullptr 126 : Ins.first->second; 127 } 128 129 // Update the composite maps of components specified in 'ComposedOf'. 130 void updateComponents(CodeGenRegBank&); 131 132 // Return the map of composites. getComposites()133 const CompMap &getComposites() const { return Composed; } 134 135 // Compute LaneMask from Composed. Return LaneMask. 136 LaneBitmask computeLaneMask() const; 137 138 void setConcatenationOf(ArrayRef<CodeGenSubRegIndex*> Parts); 139 140 /// Replaces subregister indexes in the `ConcatenationOf` list with 141 /// list of subregisters they are composed of (if any). Do this recursively. 142 void computeConcatTransitiveClosure(); 143 144 bool operator<(const CodeGenSubRegIndex &RHS) const { 145 return this->EnumValue < RHS.EnumValue; 146 } 147 148 private: 149 CompMap Composed; 150 }; 151 152 /// CodeGenRegister - Represents a register definition. 153 class CodeGenRegister { 154 public: 155 Record *TheDef; 156 unsigned EnumValue; 157 std::vector<int64_t> CostPerUse; 158 bool CoveredBySubRegs = true; 159 bool HasDisjunctSubRegs = false; 160 bool Artificial = true; 161 bool Constant = false; 162 163 // Map SubRegIndex -> Register. 164 typedef std::map<CodeGenSubRegIndex *, CodeGenRegister *, 165 deref<std::less<>>> 166 SubRegMap; 167 168 CodeGenRegister(Record *R, unsigned Enum); 169 170 StringRef getName() const; 171 172 // Extract more information from TheDef. This is used to build an object 173 // graph after all CodeGenRegister objects have been created. 174 void buildObjectGraph(CodeGenRegBank&); 175 176 // Lazily compute a map of all sub-registers. 177 // This includes unique entries for all sub-sub-registers. 178 const SubRegMap &computeSubRegs(CodeGenRegBank&); 179 180 // Compute extra sub-registers by combining the existing sub-registers. 181 void computeSecondarySubRegs(CodeGenRegBank&); 182 183 // Add this as a super-register to all sub-registers after the sub-register 184 // graph has been built. 185 void computeSuperRegs(CodeGenRegBank&); 186 getSubRegs()187 const SubRegMap &getSubRegs() const { 188 assert(SubRegsComplete && "Must precompute sub-registers"); 189 return SubRegs; 190 } 191 192 // Add sub-registers to OSet following a pre-order defined by the .td file. 193 void addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet, 194 CodeGenRegBank&) const; 195 196 // Return the sub-register index naming Reg as a sub-register of this 197 // register. Returns NULL if Reg is not a sub-register. getSubRegIndex(const CodeGenRegister * Reg)198 CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const { 199 return SubReg2Idx.lookup(Reg); 200 } 201 202 typedef std::vector<const CodeGenRegister*> SuperRegList; 203 204 // Get the list of super-registers in topological order, small to large. 205 // This is valid after computeSubRegs visits all registers during RegBank 206 // construction. getSuperRegs()207 const SuperRegList &getSuperRegs() const { 208 assert(SubRegsComplete && "Must precompute sub-registers"); 209 return SuperRegs; 210 } 211 212 // Get the list of ad hoc aliases. The graph is symmetric, so the list 213 // contains all registers in 'Aliases', and all registers that mention this 214 // register in 'Aliases'. getExplicitAliases()215 ArrayRef<CodeGenRegister*> getExplicitAliases() const { 216 return ExplicitAliases; 217 } 218 219 // Get the topological signature of this register. This is a small integer 220 // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have 221 // identical sub-register structure. That is, they support the same set of 222 // sub-register indices mapping to the same kind of sub-registers 223 // (TopoSig-wise). getTopoSig()224 unsigned getTopoSig() const { 225 assert(SuperRegsComplete && "TopoSigs haven't been computed yet."); 226 return TopoSig; 227 } 228 229 // List of register units in ascending order. 230 typedef SparseBitVector<> RegUnitList; 231 typedef SmallVector<LaneBitmask, 16> RegUnitLaneMaskList; 232 233 // How many entries in RegUnitList are native? 234 RegUnitList NativeRegUnits; 235 236 // Get the list of register units. 237 // This is only valid after computeSubRegs() completes. getRegUnits()238 const RegUnitList &getRegUnits() const { return RegUnits; } 239 getRegUnitLaneMasks()240 ArrayRef<LaneBitmask> getRegUnitLaneMasks() const { 241 return ArrayRef(RegUnitLaneMasks).slice(0, NativeRegUnits.count()); 242 } 243 244 // Get the native register units. This is a prefix of getRegUnits(). getNativeRegUnits()245 RegUnitList getNativeRegUnits() const { 246 return NativeRegUnits; 247 } 248 setRegUnitLaneMasks(const RegUnitLaneMaskList & LaneMasks)249 void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) { 250 RegUnitLaneMasks = LaneMasks; 251 } 252 253 // Inherit register units from subregisters. 254 // Return true if the RegUnits changed. 255 bool inheritRegUnits(CodeGenRegBank &RegBank); 256 257 // Adopt a register unit for pressure tracking. 258 // A unit is adopted iff its unit number is >= NativeRegUnits.count(). adoptRegUnit(unsigned RUID)259 void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); } 260 261 // Get the sum of this register's register unit weights. 262 unsigned getWeight(const CodeGenRegBank &RegBank) const; 263 264 // Canonically ordered set. 265 typedef std::vector<const CodeGenRegister*> Vec; 266 267 private: 268 bool SubRegsComplete; 269 bool SuperRegsComplete; 270 unsigned TopoSig; 271 272 // The sub-registers explicit in the .td file form a tree. 273 SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices; 274 SmallVector<CodeGenRegister*, 8> ExplicitSubRegs; 275 276 // Explicit ad hoc aliases, symmetrized to form an undirected graph. 277 SmallVector<CodeGenRegister*, 8> ExplicitAliases; 278 279 // Super-registers where this is the first explicit sub-register. 280 SuperRegList LeadingSuperRegs; 281 282 SubRegMap SubRegs; 283 SuperRegList SuperRegs; 284 DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx; 285 RegUnitList RegUnits; 286 RegUnitLaneMaskList RegUnitLaneMasks; 287 }; 288 289 inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) { 290 return A.EnumValue < B.EnumValue; 291 } 292 293 inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) { 294 return A.EnumValue == B.EnumValue; 295 } 296 297 class CodeGenRegisterClass { 298 CodeGenRegister::Vec Members; 299 // Allocation orders. Order[0] always contains all registers in Members. 300 std::vector<SmallVector<Record*, 16>> Orders; 301 // Bit mask of sub-classes including this, indexed by their EnumValue. 302 BitVector SubClasses; 303 // List of super-classes, topologocally ordered to have the larger classes 304 // first. This is the same as sorting by EnumValue. 305 SmallVector<CodeGenRegisterClass*, 4> SuperClasses; 306 Record *TheDef; 307 std::string Name; 308 309 // For a synthesized class, inherit missing properties from the nearest 310 // super-class. 311 void inheritProperties(CodeGenRegBank&); 312 313 // Map SubRegIndex -> sub-class. This is the largest sub-class where all 314 // registers have a SubRegIndex sub-register. 315 DenseMap<const CodeGenSubRegIndex *, CodeGenRegisterClass *> 316 SubClassWithSubReg; 317 318 // Map SubRegIndex -> set of super-reg classes. This is all register 319 // classes SuperRC such that: 320 // 321 // R:SubRegIndex in this RC for all R in SuperRC. 322 // 323 DenseMap<const CodeGenSubRegIndex *, SmallPtrSet<CodeGenRegisterClass *, 8>> 324 SuperRegClasses; 325 326 // Bit vector of TopoSigs for the registers in this class. This will be 327 // very sparse on regular architectures. 328 BitVector TopoSigs; 329 330 public: 331 unsigned EnumValue; 332 StringRef Namespace; 333 SmallVector<ValueTypeByHwMode, 4> VTs; 334 RegSizeInfoByHwMode RSI; 335 int CopyCost; 336 bool Allocatable; 337 StringRef AltOrderSelect; 338 uint8_t AllocationPriority; 339 bool GlobalPriority; 340 uint8_t TSFlags; 341 /// Contains the combination of the lane masks of all subregisters. 342 LaneBitmask LaneMask; 343 /// True if there are at least 2 subregisters which do not interfere. 344 bool HasDisjunctSubRegs; 345 bool CoveredBySubRegs; 346 /// A register class is artificial if all its members are artificial. 347 bool Artificial; 348 /// Generate register pressure set for this register class and any class 349 /// synthesized from it. 350 bool GeneratePressureSet; 351 352 // Return the Record that defined this class, or NULL if the class was 353 // created by TableGen. getDef()354 Record *getDef() const { return TheDef; } 355 356 std::string getNamespaceQualification() const; getName()357 const std::string &getName() const { return Name; } 358 std::string getQualifiedName() const; 359 std::string getIdName() const; 360 std::string getQualifiedIdName() const; getValueTypes()361 ArrayRef<ValueTypeByHwMode> getValueTypes() const { return VTs; } getNumValueTypes()362 unsigned getNumValueTypes() const { return VTs.size(); } 363 bool hasType(const ValueTypeByHwMode &VT) const; 364 getValueTypeNum(unsigned VTNum)365 const ValueTypeByHwMode &getValueTypeNum(unsigned VTNum) const { 366 if (VTNum < VTs.size()) 367 return VTs[VTNum]; 368 llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!"); 369 } 370 371 // Return true if this class contains the register. 372 bool contains(const CodeGenRegister*) const; 373 374 // Returns true if RC is a subclass. 375 // RC is a sub-class of this class if it is a valid replacement for any 376 // instruction operand where a register of this classis required. It must 377 // satisfy these conditions: 378 // 379 // 1. All RC registers are also in this. 380 // 2. The RC spill size must not be smaller than our spill size. 381 // 3. RC spill alignment must be compatible with ours. 382 // hasSubClass(const CodeGenRegisterClass * RC)383 bool hasSubClass(const CodeGenRegisterClass *RC) const { 384 return SubClasses.test(RC->EnumValue); 385 } 386 387 // getSubClassWithSubReg - Returns the largest sub-class where all 388 // registers have a SubIdx sub-register. 389 CodeGenRegisterClass * getSubClassWithSubReg(const CodeGenSubRegIndex * SubIdx)390 getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const { 391 return SubClassWithSubReg.lookup(SubIdx); 392 } 393 394 /// Find largest subclass where all registers have SubIdx subregisters in 395 /// SubRegClass and the largest subregister class that contains those 396 /// subregisters without (as far as possible) also containing additional registers. 397 /// 398 /// This can be used to find a suitable pair of classes for subregister copies. 399 /// \return std::pair<SubClass, SubRegClass> where SubClass is a SubClass is 400 /// a class where every register has SubIdx and SubRegClass is a class where 401 /// every register is covered by the SubIdx subregister of SubClass. 402 std::optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>> 403 getMatchingSubClassWithSubRegs(CodeGenRegBank &RegBank, 404 const CodeGenSubRegIndex *SubIdx) const; 405 setSubClassWithSubReg(const CodeGenSubRegIndex * SubIdx,CodeGenRegisterClass * SubRC)406 void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx, 407 CodeGenRegisterClass *SubRC) { 408 SubClassWithSubReg[SubIdx] = SubRC; 409 } 410 411 // getSuperRegClasses - Returns a bit vector of all register classes 412 // containing only SubIdx super-registers of this class. 413 void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx, 414 BitVector &Out) const; 415 416 // addSuperRegClass - Add a class containing only SubIdx super-registers. addSuperRegClass(CodeGenSubRegIndex * SubIdx,CodeGenRegisterClass * SuperRC)417 void addSuperRegClass(CodeGenSubRegIndex *SubIdx, 418 CodeGenRegisterClass *SuperRC) { 419 SuperRegClasses[SubIdx].insert(SuperRC); 420 } 421 422 // getSubClasses - Returns a constant BitVector of subclasses indexed by 423 // EnumValue. 424 // The SubClasses vector includes an entry for this class. getSubClasses()425 const BitVector &getSubClasses() const { return SubClasses; } 426 427 // getSuperClasses - Returns a list of super classes ordered by EnumValue. 428 // The array does not include an entry for this class. getSuperClasses()429 ArrayRef<CodeGenRegisterClass*> getSuperClasses() const { 430 return SuperClasses; 431 } 432 433 // Returns an ordered list of class members. 434 // The order of registers is the same as in the .td file. 435 // No = 0 is the default allocation order, No = 1 is the first alternative. 436 ArrayRef<Record*> getOrder(unsigned No = 0) const { 437 return Orders[No]; 438 } 439 440 // Return the total number of allocation orders available. getNumOrders()441 unsigned getNumOrders() const { return Orders.size(); } 442 443 // Get the set of registers. This set contains the same registers as 444 // getOrder(0). getMembers()445 const CodeGenRegister::Vec &getMembers() const { return Members; } 446 447 // Get a bit vector of TopoSigs present in this register class. getTopoSigs()448 const BitVector &getTopoSigs() const { return TopoSigs; } 449 450 // Get a weight of this register class. 451 unsigned getWeight(const CodeGenRegBank&) const; 452 453 // Populate a unique sorted list of units from a register set. 454 void buildRegUnitSet(const CodeGenRegBank &RegBank, 455 std::vector<unsigned> &RegUnits) const; 456 457 CodeGenRegisterClass(CodeGenRegBank&, Record *R); 458 CodeGenRegisterClass(CodeGenRegisterClass&) = delete; 459 460 // A key representing the parts of a register class used for forming 461 // sub-classes. Note the ordering provided by this key is not the same as 462 // the topological order used for the EnumValues. 463 struct Key { 464 const CodeGenRegister::Vec *Members; 465 RegSizeInfoByHwMode RSI; 466 KeyKey467 Key(const CodeGenRegister::Vec *M, const RegSizeInfoByHwMode &I) 468 : Members(M), RSI(I) {} 469 KeyKey470 Key(const CodeGenRegisterClass &RC) 471 : Members(&RC.getMembers()), RSI(RC.RSI) {} 472 473 // Lexicographical order of (Members, RegSizeInfoByHwMode). 474 bool operator<(const Key&) const; 475 }; 476 477 // Create a non-user defined register class. 478 CodeGenRegisterClass(CodeGenRegBank&, StringRef Name, Key Props); 479 480 // Called by CodeGenRegBank::CodeGenRegBank(). 481 static void computeSubClasses(CodeGenRegBank&); 482 483 // Get ordering value among register base classes. getBaseClassOrder()484 std::optional<int> getBaseClassOrder() const { 485 if (TheDef && !TheDef->isValueUnset("BaseClassOrder")) 486 return TheDef->getValueAsInt("BaseClassOrder"); 487 return {}; 488 } 489 }; 490 491 // Register categories are used when we need to deterine the category a 492 // register falls into (GPR, vector, fixed, etc.) without having to know 493 // specific information about the target architecture. 494 class CodeGenRegisterCategory { 495 Record *TheDef; 496 std::string Name; 497 std::list<CodeGenRegisterClass *> Classes; 498 499 public: 500 CodeGenRegisterCategory(CodeGenRegBank &, Record *R); 501 CodeGenRegisterCategory(CodeGenRegisterCategory &) = delete; 502 503 // Return the Record that defined this class, or NULL if the class was 504 // created by TableGen. getDef()505 Record *getDef() const { return TheDef; } 506 getName()507 std::string getName() const { return Name; } getClasses()508 std::list<CodeGenRegisterClass *> getClasses() const { return Classes; } 509 }; 510 511 // Register units are used to model interference and register pressure. 512 // Every register is assigned one or more register units such that two 513 // registers overlap if and only if they have a register unit in common. 514 // 515 // Normally, one register unit is created per leaf register. Non-leaf 516 // registers inherit the units of their sub-registers. 517 struct RegUnit { 518 // Weight assigned to this RegUnit for estimating register pressure. 519 // This is useful when equalizing weights in register classes with mixed 520 // register topologies. 521 unsigned Weight; 522 523 // Each native RegUnit corresponds to one or two root registers. The full 524 // set of registers containing this unit can be computed as the union of 525 // these two registers and their super-registers. 526 const CodeGenRegister *Roots[2]; 527 528 // Index into RegClassUnitSets where we can find the list of UnitSets that 529 // contain this unit. 530 unsigned RegClassUnitSetsIdx; 531 // A register unit is artificial if at least one of its roots is 532 // artificial. 533 bool Artificial; 534 RegUnitRegUnit535 RegUnit() : Weight(0), RegClassUnitSetsIdx(0), Artificial(false) { 536 Roots[0] = Roots[1] = nullptr; 537 } 538 getRootsRegUnit539 ArrayRef<const CodeGenRegister*> getRoots() const { 540 assert(!(Roots[1] && !Roots[0]) && "Invalid roots array"); 541 return ArrayRef(Roots, !!Roots[0] + !!Roots[1]); 542 } 543 }; 544 545 // Each RegUnitSet is a sorted vector with a name. 546 struct RegUnitSet { 547 typedef std::vector<unsigned>::const_iterator iterator; 548 549 std::string Name; 550 std::vector<unsigned> Units; 551 unsigned Weight = 0; // Cache the sum of all unit weights. 552 unsigned Order = 0; // Cache the sort key. 553 554 RegUnitSet() = default; 555 }; 556 557 // Base vector for identifying TopoSigs. The contents uniquely identify a 558 // TopoSig, only computeSuperRegs needs to know how. 559 typedef SmallVector<unsigned, 16> TopoSigId; 560 561 // CodeGenRegBank - Represent a target's registers and the relations between 562 // them. 563 class CodeGenRegBank { 564 SetTheory Sets; 565 566 const CodeGenHwModes &CGH; 567 568 std::deque<CodeGenSubRegIndex> SubRegIndices; 569 DenseMap<Record*, CodeGenSubRegIndex*> Def2SubRegIdx; 570 571 CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace); 572 573 typedef std::map<SmallVector<CodeGenSubRegIndex*, 8>, 574 CodeGenSubRegIndex*> ConcatIdxMap; 575 ConcatIdxMap ConcatIdx; 576 577 // Registers. 578 std::deque<CodeGenRegister> Registers; 579 StringMap<CodeGenRegister*> RegistersByName; 580 DenseMap<Record*, CodeGenRegister*> Def2Reg; 581 unsigned NumNativeRegUnits; 582 583 std::map<TopoSigId, unsigned> TopoSigs; 584 585 // Includes native (0..NumNativeRegUnits-1) and adopted register units. 586 SmallVector<RegUnit, 8> RegUnits; 587 588 // Register classes. 589 std::list<CodeGenRegisterClass> RegClasses; 590 DenseMap<Record*, CodeGenRegisterClass*> Def2RC; 591 typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap; 592 RCKeyMap Key2RC; 593 594 // Register categories. 595 std::list<CodeGenRegisterCategory> RegCategories; 596 DenseMap<Record *, CodeGenRegisterCategory *> Def2RCat; 597 using RCatKeyMap = 598 std::map<CodeGenRegisterClass::Key, CodeGenRegisterCategory *>; 599 RCatKeyMap Key2RCat; 600 601 // Remember each unique set of register units. Initially, this contains a 602 // unique set for each register class. Simliar sets are coalesced with 603 // pruneUnitSets and new supersets are inferred during computeRegUnitSets. 604 std::vector<RegUnitSet> RegUnitSets; 605 606 // Map RegisterClass index to the index of the RegUnitSet that contains the 607 // class's units and any inferred RegUnit supersets. 608 // 609 // NOTE: This could grow beyond the number of register classes when we map 610 // register units to lists of unit sets. If the list of unit sets does not 611 // already exist for a register class, we create a new entry in this vector. 612 std::vector<std::vector<unsigned>> RegClassUnitSets; 613 614 // Give each register unit set an order based on sorting criteria. 615 std::vector<unsigned> RegUnitSetOrder; 616 617 // Keep track of synthesized definitions generated in TupleExpander. 618 std::vector<std::unique_ptr<Record>> SynthDefs; 619 620 // Add RC to *2RC maps. 621 void addToMaps(CodeGenRegisterClass*); 622 623 // Create a synthetic sub-class if it is missing. 624 CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, 625 const CodeGenRegister::Vec *Membs, 626 StringRef Name); 627 628 // Infer missing register classes. 629 void computeInferredRegisterClasses(); 630 void inferCommonSubClass(CodeGenRegisterClass *RC); 631 void inferSubClassWithSubReg(CodeGenRegisterClass *RC); 632 inferMatchingSuperRegClass(CodeGenRegisterClass * RC)633 void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) { 634 inferMatchingSuperRegClass(RC, RegClasses.begin()); 635 } 636 637 void inferMatchingSuperRegClass( 638 CodeGenRegisterClass *RC, 639 std::list<CodeGenRegisterClass>::iterator FirstSubRegRC); 640 641 // Iteratively prune unit sets. 642 void pruneUnitSets(); 643 644 // Compute a weight for each register unit created during getSubRegs. 645 void computeRegUnitWeights(); 646 647 // Create a RegUnitSet for each RegClass and infer superclasses. 648 void computeRegUnitSets(); 649 650 // Populate the Composite map from sub-register relationships. 651 void computeComposites(); 652 653 // Compute a lane mask for each sub-register index. 654 void computeSubRegLaneMasks(); 655 656 /// Computes a lane mask for each register unit enumerated by a physical 657 /// register. 658 void computeRegUnitLaneMasks(); 659 660 public: 661 CodeGenRegBank(RecordKeeper&, const CodeGenHwModes&); 662 CodeGenRegBank(CodeGenRegBank&) = delete; 663 getSets()664 SetTheory &getSets() { return Sets; } 665 getHwModes()666 const CodeGenHwModes &getHwModes() const { return CGH; } 667 668 // Sub-register indices. The first NumNamedIndices are defined by the user 669 // in the .td files. The rest are synthesized such that all sub-registers 670 // have a unique name. getSubRegIndices()671 const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const { 672 return SubRegIndices; 673 } 674 675 // Find a SubRegIndex from its Record def or add to the list if it does 676 // not exist there yet. 677 CodeGenSubRegIndex *getSubRegIdx(Record*); 678 679 // Find a SubRegIndex from its Record def. 680 const CodeGenSubRegIndex *findSubRegIdx(const Record* Def) const; 681 682 // Find or create a sub-register index representing the A+B composition. 683 CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A, 684 CodeGenSubRegIndex *B); 685 686 // Find or create a sub-register index representing the concatenation of 687 // non-overlapping sibling indices. 688 CodeGenSubRegIndex * 689 getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8>&); 690 getRegisters()691 const std::deque<CodeGenRegister> &getRegisters() const { 692 return Registers; 693 } 694 getRegistersByName()695 const StringMap<CodeGenRegister *> &getRegistersByName() const { 696 return RegistersByName; 697 } 698 699 // Find a register from its Record def. 700 CodeGenRegister *getReg(Record*); 701 702 // Get a Register's index into the Registers array. getRegIndex(const CodeGenRegister * Reg)703 unsigned getRegIndex(const CodeGenRegister *Reg) const { 704 return Reg->EnumValue - 1; 705 } 706 707 // Return the number of allocated TopoSigs. The first TopoSig representing 708 // leaf registers is allocated number 0. getNumTopoSigs()709 unsigned getNumTopoSigs() const { 710 return TopoSigs.size(); 711 } 712 713 // Find or create a TopoSig for the given TopoSigId. 714 // This function is only for use by CodeGenRegister::computeSuperRegs(). 715 // Others should simply use Reg->getTopoSig(). getTopoSig(const TopoSigId & Id)716 unsigned getTopoSig(const TopoSigId &Id) { 717 return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second; 718 } 719 720 // Create a native register unit that is associated with one or two root 721 // registers. 722 unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) { 723 RegUnits.resize(RegUnits.size() + 1); 724 RegUnit &RU = RegUnits.back(); 725 RU.Roots[0] = R0; 726 RU.Roots[1] = R1; 727 RU.Artificial = R0->Artificial; 728 if (R1) 729 RU.Artificial |= R1->Artificial; 730 return RegUnits.size() - 1; 731 } 732 733 // Create a new non-native register unit that can be adopted by a register 734 // to increase its pressure. Note that NumNativeRegUnits is not increased. newRegUnit(unsigned Weight)735 unsigned newRegUnit(unsigned Weight) { 736 RegUnits.resize(RegUnits.size() + 1); 737 RegUnits.back().Weight = Weight; 738 return RegUnits.size() - 1; 739 } 740 741 // Native units are the singular unit of a leaf register. Register aliasing 742 // is completely characterized by native units. Adopted units exist to give 743 // register additional weight but don't affect aliasing. isNativeUnit(unsigned RUID)744 bool isNativeUnit(unsigned RUID) const { 745 return RUID < NumNativeRegUnits; 746 } 747 getNumNativeRegUnits()748 unsigned getNumNativeRegUnits() const { 749 return NumNativeRegUnits; 750 } 751 getRegUnit(unsigned RUID)752 RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; } getRegUnit(unsigned RUID)753 const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; } 754 getRegClasses()755 std::list<CodeGenRegisterClass> &getRegClasses() { return RegClasses; } 756 getRegClasses()757 const std::list<CodeGenRegisterClass> &getRegClasses() const { 758 return RegClasses; 759 } 760 getRegCategories()761 std::list<CodeGenRegisterCategory> &getRegCategories() { 762 return RegCategories; 763 } 764 getRegCategories()765 const std::list<CodeGenRegisterCategory> &getRegCategories() const { 766 return RegCategories; 767 } 768 769 // Find a register class from its def. 770 CodeGenRegisterClass *getRegClass(const Record *) const; 771 772 /// getRegisterClassForRegister - Find the register class that contains the 773 /// specified physical register. If the register is not in a register 774 /// class, return null. If the register is in multiple classes, and the 775 /// classes have a superset-subset relationship and the same set of types, 776 /// return the superclass. Otherwise return null. 777 const CodeGenRegisterClass* getRegClassForRegister(Record *R); 778 779 // Analog of TargetRegisterInfo::getMinimalPhysRegClass. Unlike 780 // getRegClassForRegister, this tries to find the smallest class containing 781 // the physical register. If \p VT is specified, it will only find classes 782 // with a matching type 783 const CodeGenRegisterClass * 784 getMinimalPhysRegClass(Record *RegRecord, ValueTypeByHwMode *VT = nullptr); 785 786 // Get the sum of unit weights. getRegUnitSetWeight(const std::vector<unsigned> & Units)787 unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const { 788 unsigned Weight = 0; 789 for (unsigned Unit : Units) 790 Weight += getRegUnit(Unit).Weight; 791 return Weight; 792 } 793 getRegSetIDAt(unsigned Order)794 unsigned getRegSetIDAt(unsigned Order) const { 795 return RegUnitSetOrder[Order]; 796 } 797 getRegSetAt(unsigned Order)798 const RegUnitSet &getRegSetAt(unsigned Order) const { 799 return RegUnitSets[RegUnitSetOrder[Order]]; 800 } 801 802 // Increase a RegUnitWeight. increaseRegUnitWeight(unsigned RUID,unsigned Inc)803 void increaseRegUnitWeight(unsigned RUID, unsigned Inc) { 804 getRegUnit(RUID).Weight += Inc; 805 } 806 807 // Get the number of register pressure dimensions. getNumRegPressureSets()808 unsigned getNumRegPressureSets() const { return RegUnitSets.size(); } 809 810 // Get a set of register unit IDs for a given dimension of pressure. getRegPressureSet(unsigned Idx)811 const RegUnitSet &getRegPressureSet(unsigned Idx) const { 812 return RegUnitSets[Idx]; 813 } 814 815 // The number of pressure set lists may be larget than the number of 816 // register classes if some register units appeared in a list of sets that 817 // did not correspond to an existing register class. getNumRegClassPressureSetLists()818 unsigned getNumRegClassPressureSetLists() const { 819 return RegClassUnitSets.size(); 820 } 821 822 // Get a list of pressure set IDs for a register class. Liveness of a 823 // register in this class impacts each pressure set in this list by the 824 // weight of the register. An exact solution requires all registers in a 825 // class to have the same class, but it is not strictly guaranteed. getRCPressureSetIDs(unsigned RCIdx)826 ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const { 827 return RegClassUnitSets[RCIdx]; 828 } 829 830 // Computed derived records such as missing sub-register indices. 831 void computeDerivedInfo(); 832 833 // Compute the set of registers completely covered by the registers in Regs. 834 // The returned BitVector will have a bit set for each register in Regs, 835 // all sub-registers, and all super-registers that are covered by the 836 // registers in Regs. 837 // 838 // This is used to compute the mask of call-preserved registers from a list 839 // of callee-saves. 840 BitVector computeCoveredRegisters(ArrayRef<Record*> Regs); 841 842 // Bit mask of lanes that cover their registers. A sub-register index whose 843 // LaneMask is contained in CoveringLanes will be completely covered by 844 // another sub-register with the same or larger lane mask. 845 LaneBitmask CoveringLanes; 846 847 // Helper function for printing debug information. Handles artificial 848 // (non-native) reg units. 849 void printRegUnitName(unsigned Unit) const; 850 }; 851 852 } // end namespace llvm 853 854 #endif // LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 855