1193323Sed//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file defines structures to encapsulate information gleaned from the 10193323Sed// target register and register class definitions. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14280031Sdim#ifndef LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 15280031Sdim#define LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 16193323Sed 17327952Sdim#include "InfoByHwMode.h" 18224145Sdim#include "llvm/ADT/ArrayRef.h" 19226633Sdim#include "llvm/ADT/BitVector.h" 20208599Srdivacky#include "llvm/ADT/DenseMap.h" 21341825Sdim#include "llvm/ADT/STLExtras.h" 22314564Sdim#include "llvm/ADT/SetVector.h" 23314564Sdim#include "llvm/ADT/SmallPtrSet.h" 24314564Sdim#include "llvm/ADT/SmallVector.h" 25314564Sdim#include "llvm/ADT/SparseBitVector.h" 26314564Sdim#include "llvm/ADT/StringMap.h" 27314564Sdim#include "llvm/ADT/StringRef.h" 28314564Sdim#include "llvm/MC/LaneBitmask.h" 29234353Sdim#include "llvm/Support/ErrorHandling.h" 30341825Sdim#include "llvm/Support/MachineValueType.h" 31249423Sdim#include "llvm/TableGen/Record.h" 32276479Sdim#include "llvm/TableGen/SetTheory.h" 33314564Sdim#include <cassert> 34314564Sdim#include <cstdint> 35309124Sdim#include <deque> 36280031Sdim#include <list> 37223017Sdim#include <map> 38193323Sed#include <string> 39314564Sdim#include <utility> 40193323Sed#include <vector> 41193323Sed 42193323Sednamespace llvm { 43314564Sdim 44223017Sdim class CodeGenRegBank; 45309124Sdim template <typename T, typename Vector, typename Set> class SetVector; 46193323Sed 47280031Sdim /// Used to encode a step in a register lane mask transformation. 48280031Sdim /// Mask the bits specified in Mask, then rotate them Rol bits to the left 49280031Sdim /// assuming a wraparound at 32bits. 50280031Sdim struct MaskRolPair { 51314564Sdim LaneBitmask Mask; 52280031Sdim uint8_t RotateLeft; 53314564Sdim 54288943Sdim bool operator==(const MaskRolPair Other) const { 55280031Sdim return Mask == Other.Mask && RotateLeft == Other.RotateLeft; 56280031Sdim } 57288943Sdim bool operator!=(const MaskRolPair Other) const { 58280031Sdim return Mask != Other.Mask || RotateLeft != Other.RotateLeft; 59280031Sdim } 60280031Sdim }; 61280031Sdim 62234353Sdim /// CodeGenSubRegIndex - Represents a sub-register index. 63234353Sdim class CodeGenSubRegIndex { 64234353Sdim Record *const TheDef; 65239462Sdim std::string Name; 66239462Sdim std::string Namespace; 67239462Sdim 68239462Sdim public: 69261991Sdim uint16_t Size; 70261991Sdim uint16_t Offset; 71234353Sdim const unsigned EnumValue; 72314564Sdim mutable LaneBitmask LaneMask; 73280031Sdim mutable SmallVector<MaskRolPair,1> CompositionLaneMaskTransform; 74234353Sdim 75327952Sdim /// A list of subregister indexes concatenated resulting in this 76327952Sdim /// subregister index. This is the reverse of CodeGenRegBank::ConcatIdx. 77327952Sdim SmallVector<CodeGenSubRegIndex*,4> ConcatenationOf; 78327952Sdim 79261991Sdim // Are all super-registers containing this SubRegIndex covered by their 80261991Sdim // sub-registers? 81261991Sdim bool AllSuperRegsCovered; 82341825Sdim // A subregister index is "artificial" if every subregister obtained 83341825Sdim // from applying this index is artificial. Artificial subregister 84341825Sdim // indexes are not used to create new register classes. 85341825Sdim bool Artificial; 86261991Sdim 87234353Sdim CodeGenSubRegIndex(Record *R, unsigned Enum); 88239462Sdim CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum); 89234353Sdim 90239462Sdim const std::string &getName() const { return Name; } 91239462Sdim const std::string &getNamespace() const { return Namespace; } 92234353Sdim std::string getQualifiedName() const; 93234353Sdim 94234353Sdim // Map of composite subreg indices. 95288943Sdim typedef std::map<CodeGenSubRegIndex *, CodeGenSubRegIndex *, 96360784Sdim deref<std::less<>>> 97360784Sdim CompMap; 98234353Sdim 99234353Sdim // Returns the subreg index that results from composing this with Idx. 100234353Sdim // Returns NULL if this and Idx don't compose. 101234353Sdim CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const { 102234353Sdim CompMap::const_iterator I = Composed.find(Idx); 103276479Sdim return I == Composed.end() ? nullptr : I->second; 104234353Sdim } 105234353Sdim 106234353Sdim // Add a composite subreg index: this+A = B. 107234353Sdim // Return a conflicting composite, or NULL 108234353Sdim CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, 109234353Sdim CodeGenSubRegIndex *B) { 110239462Sdim assert(A && B); 111234353Sdim std::pair<CompMap::iterator, bool> Ins = 112234353Sdim Composed.insert(std::make_pair(A, B)); 113261991Sdim // Synthetic subreg indices that aren't contiguous (for instance ARM 114261991Sdim // register tuples) don't have a bit range, so it's OK to let 115261991Sdim // B->Offset == -1. For the other cases, accumulate the offset and set 116261991Sdim // the size here. Only do so if there is no offset yet though. 117261991Sdim if ((Offset != (uint16_t)-1 && A->Offset != (uint16_t)-1) && 118261991Sdim (B->Offset == (uint16_t)-1)) { 119261991Sdim B->Offset = Offset + A->Offset; 120261991Sdim B->Size = A->Size; 121261991Sdim } 122276479Sdim return (Ins.second || Ins.first->second == B) ? nullptr 123276479Sdim : Ins.first->second; 124234353Sdim } 125234353Sdim 126234353Sdim // Update the composite maps of components specified in 'ComposedOf'. 127234353Sdim void updateComponents(CodeGenRegBank&); 128234353Sdim 129234353Sdim // Return the map of composites. 130234353Sdim const CompMap &getComposites() const { return Composed; } 131234353Sdim 132243830Sdim // Compute LaneMask from Composed. Return LaneMask. 133314564Sdim LaneBitmask computeLaneMask() const; 134243830Sdim 135327952Sdim void setConcatenationOf(ArrayRef<CodeGenSubRegIndex*> Parts); 136327952Sdim 137327952Sdim /// Replaces subregister indexes in the `ConcatenationOf` list with 138327952Sdim /// list of subregisters they are composed of (if any). Do this recursively. 139327952Sdim void computeConcatTransitiveClosure(); 140327952Sdim 141360784Sdim bool operator<(const CodeGenSubRegIndex &RHS) const { 142360784Sdim return this->EnumValue < RHS.EnumValue; 143360784Sdim } 144360784Sdim 145234353Sdim private: 146234353Sdim CompMap Composed; 147234353Sdim }; 148234353Sdim 149193323Sed /// CodeGenRegister - Represents a register definition. 150193323Sed struct CodeGenRegister { 151193323Sed Record *TheDef; 152221345Sdim unsigned EnumValue; 153221345Sdim unsigned CostPerUse; 154234353Sdim bool CoveredBySubRegs; 155288943Sdim bool HasDisjunctSubRegs; 156341825Sdim bool Artificial; 157223017Sdim 158223017Sdim // Map SubRegIndex -> Register. 159360784Sdim typedef std::map<CodeGenSubRegIndex *, CodeGenRegister *, 160360784Sdim deref<std::less<>>> 161288943Sdim SubRegMap; 162223017Sdim 163223017Sdim CodeGenRegister(Record *R, unsigned Enum); 164223017Sdim 165314564Sdim const StringRef getName() const; 166223017Sdim 167239462Sdim // Extract more information from TheDef. This is used to build an object 168239462Sdim // graph after all CodeGenRegister objects have been created. 169239462Sdim void buildObjectGraph(CodeGenRegBank&); 170239462Sdim 171239462Sdim // Lazily compute a map of all sub-registers. 172223017Sdim // This includes unique entries for all sub-sub-registers. 173239462Sdim const SubRegMap &computeSubRegs(CodeGenRegBank&); 174223017Sdim 175239462Sdim // Compute extra sub-registers by combining the existing sub-registers. 176239462Sdim void computeSecondarySubRegs(CodeGenRegBank&); 177239462Sdim 178239462Sdim // Add this as a super-register to all sub-registers after the sub-register 179239462Sdim // graph has been built. 180239462Sdim void computeSuperRegs(CodeGenRegBank&); 181239462Sdim 182223017Sdim const SubRegMap &getSubRegs() const { 183223017Sdim assert(SubRegsComplete && "Must precompute sub-registers"); 184223017Sdim return SubRegs; 185223017Sdim } 186223017Sdim 187224145Sdim // Add sub-registers to OSet following a pre-order defined by the .td file. 188234353Sdim void addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet, 189234353Sdim CodeGenRegBank&) const; 190224145Sdim 191239462Sdim // Return the sub-register index naming Reg as a sub-register of this 192239462Sdim // register. Returns NULL if Reg is not a sub-register. 193239462Sdim CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const { 194239462Sdim return SubReg2Idx.lookup(Reg); 195239462Sdim } 196239462Sdim 197234353Sdim typedef std::vector<const CodeGenRegister*> SuperRegList; 198224145Sdim 199239462Sdim // Get the list of super-registers in topological order, small to large. 200239462Sdim // This is valid after computeSubRegs visits all registers during RegBank 201239462Sdim // construction. 202224145Sdim const SuperRegList &getSuperRegs() const { 203224145Sdim assert(SubRegsComplete && "Must precompute sub-registers"); 204224145Sdim return SuperRegs; 205224145Sdim } 206224145Sdim 207239462Sdim // Get the list of ad hoc aliases. The graph is symmetric, so the list 208239462Sdim // contains all registers in 'Aliases', and all registers that mention this 209239462Sdim // register in 'Aliases'. 210239462Sdim ArrayRef<CodeGenRegister*> getExplicitAliases() const { 211239462Sdim return ExplicitAliases; 212239462Sdim } 213239462Sdim 214239462Sdim // Get the topological signature of this register. This is a small integer 215239462Sdim // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have 216239462Sdim // identical sub-register structure. That is, they support the same set of 217239462Sdim // sub-register indices mapping to the same kind of sub-registers 218239462Sdim // (TopoSig-wise). 219239462Sdim unsigned getTopoSig() const { 220239462Sdim assert(SuperRegsComplete && "TopoSigs haven't been computed yet."); 221239462Sdim return TopoSig; 222239462Sdim } 223239462Sdim 224234353Sdim // List of register units in ascending order. 225288943Sdim typedef SparseBitVector<> RegUnitList; 226314564Sdim typedef SmallVector<LaneBitmask, 16> RegUnitLaneMaskList; 227234353Sdim 228239462Sdim // How many entries in RegUnitList are native? 229288943Sdim RegUnitList NativeRegUnits; 230239462Sdim 231234353Sdim // Get the list of register units. 232239462Sdim // This is only valid after computeSubRegs() completes. 233234353Sdim const RegUnitList &getRegUnits() const { return RegUnits; } 234234353Sdim 235314564Sdim ArrayRef<LaneBitmask> getRegUnitLaneMasks() const { 236288943Sdim return makeArrayRef(RegUnitLaneMasks).slice(0, NativeRegUnits.count()); 237280031Sdim } 238280031Sdim 239239462Sdim // Get the native register units. This is a prefix of getRegUnits(). 240288943Sdim RegUnitList getNativeRegUnits() const { 241288943Sdim return NativeRegUnits; 242239462Sdim } 243239462Sdim 244280031Sdim void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) { 245280031Sdim RegUnitLaneMasks = LaneMasks; 246280031Sdim } 247280031Sdim 248234353Sdim // Inherit register units from subregisters. 249234353Sdim // Return true if the RegUnits changed. 250234353Sdim bool inheritRegUnits(CodeGenRegBank &RegBank); 251234353Sdim 252234353Sdim // Adopt a register unit for pressure tracking. 253288943Sdim // A unit is adopted iff its unit number is >= NativeRegUnits.count(). 254288943Sdim void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); } 255234353Sdim 256234353Sdim // Get the sum of this register's register unit weights. 257234353Sdim unsigned getWeight(const CodeGenRegBank &RegBank) const; 258234353Sdim 259224145Sdim // Canonically ordered set. 260288943Sdim typedef std::vector<const CodeGenRegister*> Vec; 261224145Sdim 262223017Sdim private: 263223017Sdim bool SubRegsComplete; 264239462Sdim bool SuperRegsComplete; 265239462Sdim unsigned TopoSig; 266239462Sdim 267239462Sdim // The sub-registers explicit in the .td file form a tree. 268239462Sdim SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices; 269239462Sdim SmallVector<CodeGenRegister*, 8> ExplicitSubRegs; 270239462Sdim 271239462Sdim // Explicit ad hoc aliases, symmetrized to form an undirected graph. 272239462Sdim SmallVector<CodeGenRegister*, 8> ExplicitAliases; 273239462Sdim 274239462Sdim // Super-registers where this is the first explicit sub-register. 275239462Sdim SuperRegList LeadingSuperRegs; 276239462Sdim 277223017Sdim SubRegMap SubRegs; 278224145Sdim SuperRegList SuperRegs; 279239462Sdim DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx; 280234353Sdim RegUnitList RegUnits; 281280031Sdim RegUnitLaneMaskList RegUnitLaneMasks; 282193323Sed }; 283193323Sed 284288943Sdim inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) { 285288943Sdim return A.EnumValue < B.EnumValue; 286288943Sdim } 287193323Sed 288288943Sdim inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) { 289288943Sdim return A.EnumValue == B.EnumValue; 290288943Sdim } 291288943Sdim 292224145Sdim class CodeGenRegisterClass { 293288943Sdim CodeGenRegister::Vec Members; 294226633Sdim // Allocation orders. Order[0] always contains all registers in Members. 295314564Sdim std::vector<SmallVector<Record*, 16>> Orders; 296226633Sdim // Bit mask of sub-classes including this, indexed by their EnumValue. 297226633Sdim BitVector SubClasses; 298226633Sdim // List of super-classes, topologocally ordered to have the larger classes 299226633Sdim // first. This is the same as sorting by EnumValue. 300226633Sdim SmallVector<CodeGenRegisterClass*, 4> SuperClasses; 301226633Sdim Record *TheDef; 302226633Sdim std::string Name; 303226633Sdim 304226633Sdim // For a synthesized class, inherit missing properties from the nearest 305226633Sdim // super-class. 306226633Sdim void inheritProperties(CodeGenRegBank&); 307226633Sdim 308234353Sdim // Map SubRegIndex -> sub-class. This is the largest sub-class where all 309234353Sdim // registers have a SubRegIndex sub-register. 310280031Sdim DenseMap<const CodeGenSubRegIndex *, CodeGenRegisterClass *> 311280031Sdim SubClassWithSubReg; 312226633Sdim 313234353Sdim // Map SubRegIndex -> set of super-reg classes. This is all register 314234353Sdim // classes SuperRC such that: 315234353Sdim // 316234353Sdim // R:SubRegIndex in this RC for all R in SuperRC. 317234353Sdim // 318280031Sdim DenseMap<const CodeGenSubRegIndex *, SmallPtrSet<CodeGenRegisterClass *, 8>> 319280031Sdim SuperRegClasses; 320234353Sdim 321239462Sdim // Bit vector of TopoSigs for the registers in this class. This will be 322239462Sdim // very sparse on regular architectures. 323239462Sdim BitVector TopoSigs; 324239462Sdim 325224145Sdim public: 326226633Sdim unsigned EnumValue; 327321369Sdim StringRef Namespace; 328327952Sdim SmallVector<ValueTypeByHwMode, 4> VTs; 329327952Sdim RegSizeInfoByHwMode RSI; 330193323Sed int CopyCost; 331223017Sdim bool Allocatable; 332321369Sdim StringRef AltOrderSelect; 333288943Sdim uint8_t AllocationPriority; 334280031Sdim /// Contains the combination of the lane masks of all subregisters. 335314564Sdim LaneBitmask LaneMask; 336288943Sdim /// True if there are at least 2 subregisters which do not interfere. 337288943Sdim bool HasDisjunctSubRegs; 338309124Sdim bool CoveredBySubRegs; 339341825Sdim /// A register class is artificial if all its members are artificial. 340341825Sdim bool Artificial; 341193323Sed 342226633Sdim // Return the Record that defined this class, or NULL if the class was 343226633Sdim // created by TableGen. 344226633Sdim Record *getDef() const { return TheDef; } 345226633Sdim 346226633Sdim const std::string &getName() const { return Name; } 347226633Sdim std::string getQualifiedName() const; 348327952Sdim ArrayRef<ValueTypeByHwMode> getValueTypes() const { return VTs; } 349193323Sed unsigned getNumValueTypes() const { return VTs.size(); } 350221345Sdim 351360784Sdim bool hasType(const ValueTypeByHwMode &VT) const { 352360784Sdim return std::find(VTs.begin(), VTs.end(), VT) != VTs.end(); 353360784Sdim } 354360784Sdim 355344779Sdim const ValueTypeByHwMode &getValueTypeNum(unsigned VTNum) const { 356193323Sed if (VTNum < VTs.size()) 357193323Sed return VTs[VTNum]; 358234353Sdim llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!"); 359193323Sed } 360221345Sdim 361224145Sdim // Return true if this this class contains the register. 362224145Sdim bool contains(const CodeGenRegister*) const; 363221345Sdim 364224145Sdim // Returns true if RC is a subclass. 365212904Sdim // RC is a sub-class of this class if it is a valid replacement for any 366221345Sdim // instruction operand where a register of this classis required. It must 367212904Sdim // satisfy these conditions: 368212904Sdim // 369212904Sdim // 1. All RC registers are also in this. 370212904Sdim // 2. The RC spill size must not be smaller than our spill size. 371212904Sdim // 3. RC spill alignment must be compatible with ours. 372212904Sdim // 373226633Sdim bool hasSubClass(const CodeGenRegisterClass *RC) const { 374226633Sdim return SubClasses.test(RC->EnumValue); 375226633Sdim } 376193323Sed 377226633Sdim // getSubClassWithSubReg - Returns the largest sub-class where all 378226633Sdim // registers have a SubIdx sub-register. 379280031Sdim CodeGenRegisterClass * 380280031Sdim getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const { 381226633Sdim return SubClassWithSubReg.lookup(SubIdx); 382226633Sdim } 383226633Sdim 384321369Sdim /// Find largest subclass where all registers have SubIdx subregisters in 385321369Sdim /// SubRegClass and the largest subregister class that contains those 386321369Sdim /// subregisters without (as far as possible) also containing additional registers. 387321369Sdim /// 388321369Sdim /// This can be used to find a suitable pair of classes for subregister copies. 389321369Sdim /// \return std::pair<SubClass, SubRegClass> where SubClass is a SubClass is 390321369Sdim /// a class where every register has SubIdx and SubRegClass is a class where 391321369Sdim /// every register is covered by the SubIdx subregister of SubClass. 392321369Sdim Optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>> 393321369Sdim getMatchingSubClassWithSubRegs(CodeGenRegBank &RegBank, 394321369Sdim const CodeGenSubRegIndex *SubIdx) const; 395321369Sdim 396280031Sdim void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx, 397234353Sdim CodeGenRegisterClass *SubRC) { 398226633Sdim SubClassWithSubReg[SubIdx] = SubRC; 399226633Sdim } 400226633Sdim 401234353Sdim // getSuperRegClasses - Returns a bit vector of all register classes 402234353Sdim // containing only SubIdx super-registers of this class. 403280031Sdim void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx, 404280031Sdim BitVector &Out) const; 405234353Sdim 406321369Sdim // addSuperRegClass - Add a class containing only SubIdx super-registers. 407234353Sdim void addSuperRegClass(CodeGenSubRegIndex *SubIdx, 408234353Sdim CodeGenRegisterClass *SuperRC) { 409234353Sdim SuperRegClasses[SubIdx].insert(SuperRC); 410234353Sdim } 411234353Sdim 412226633Sdim // getSubClasses - Returns a constant BitVector of subclasses indexed by 413226633Sdim // EnumValue. 414276479Sdim // The SubClasses vector includes an entry for this class. 415226633Sdim const BitVector &getSubClasses() const { return SubClasses; } 416226633Sdim 417226633Sdim // getSuperClasses - Returns a list of super classes ordered by EnumValue. 418226633Sdim // The array does not include an entry for this class. 419226633Sdim ArrayRef<CodeGenRegisterClass*> getSuperClasses() const { 420226633Sdim return SuperClasses; 421226633Sdim } 422226633Sdim 423224145Sdim // Returns an ordered list of class members. 424224145Sdim // The order of registers is the same as in the .td file. 425224145Sdim // No = 0 is the default allocation order, No = 1 is the first alternative. 426224145Sdim ArrayRef<Record*> getOrder(unsigned No = 0) const { 427226633Sdim return Orders[No]; 428224145Sdim } 429212904Sdim 430224145Sdim // Return the total number of allocation orders available. 431226633Sdim unsigned getNumOrders() const { return Orders.size(); } 432212904Sdim 433226633Sdim // Get the set of registers. This set contains the same registers as 434226633Sdim // getOrder(0). 435288943Sdim const CodeGenRegister::Vec &getMembers() const { return Members; } 436226633Sdim 437239462Sdim // Get a bit vector of TopoSigs present in this register class. 438239462Sdim const BitVector &getTopoSigs() const { return TopoSigs; } 439239462Sdim 440234353Sdim // Populate a unique sorted list of units from a register set. 441341825Sdim void buildRegUnitSet(const CodeGenRegBank &RegBank, 442341825Sdim std::vector<unsigned> &RegUnits) const; 443234353Sdim 444224145Sdim CodeGenRegisterClass(CodeGenRegBank&, Record *R); 445226633Sdim 446226633Sdim // A key representing the parts of a register class used for forming 447226633Sdim // sub-classes. Note the ordering provided by this key is not the same as 448226633Sdim // the topological order used for the EnumValues. 449226633Sdim struct Key { 450288943Sdim const CodeGenRegister::Vec *Members; 451327952Sdim RegSizeInfoByHwMode RSI; 452226633Sdim 453327952Sdim Key(const CodeGenRegister::Vec *M, const RegSizeInfoByHwMode &I) 454327952Sdim : Members(M), RSI(I) {} 455226633Sdim 456226633Sdim Key(const CodeGenRegisterClass &RC) 457327952Sdim : Members(&RC.getMembers()), RSI(RC.RSI) {} 458226633Sdim 459327952Sdim // Lexicographical order of (Members, RegSizeInfoByHwMode). 460226633Sdim bool operator<(const Key&) const; 461226633Sdim }; 462226633Sdim 463226633Sdim // Create a non-user defined register class. 464239462Sdim CodeGenRegisterClass(CodeGenRegBank&, StringRef Name, Key Props); 465226633Sdim 466226633Sdim // Called by CodeGenRegBank::CodeGenRegBank(). 467226633Sdim static void computeSubClasses(CodeGenRegBank&); 468193323Sed }; 469223017Sdim 470239462Sdim // Register units are used to model interference and register pressure. 471239462Sdim // Every register is assigned one or more register units such that two 472239462Sdim // registers overlap if and only if they have a register unit in common. 473239462Sdim // 474239462Sdim // Normally, one register unit is created per leaf register. Non-leaf 475239462Sdim // registers inherit the units of their sub-registers. 476239462Sdim struct RegUnit { 477239462Sdim // Weight assigned to this RegUnit for estimating register pressure. 478239462Sdim // This is useful when equalizing weights in register classes with mixed 479239462Sdim // register topologies. 480239462Sdim unsigned Weight; 481239462Sdim 482239462Sdim // Each native RegUnit corresponds to one or two root registers. The full 483239462Sdim // set of registers containing this unit can be computed as the union of 484239462Sdim // these two registers and their super-registers. 485239462Sdim const CodeGenRegister *Roots[2]; 486239462Sdim 487249423Sdim // Index into RegClassUnitSets where we can find the list of UnitSets that 488249423Sdim // contain this unit. 489249423Sdim unsigned RegClassUnitSetsIdx; 490341825Sdim // A register unit is artificial if at least one of its roots is 491341825Sdim // artificial. 492341825Sdim bool Artificial; 493239462Sdim 494341825Sdim RegUnit() : Weight(0), RegClassUnitSetsIdx(0), Artificial(false) { 495276479Sdim Roots[0] = Roots[1] = nullptr; 496276479Sdim } 497249423Sdim 498239462Sdim ArrayRef<const CodeGenRegister*> getRoots() const { 499239462Sdim assert(!(Roots[1] && !Roots[0]) && "Invalid roots array"); 500239462Sdim return makeArrayRef(Roots, !!Roots[0] + !!Roots[1]); 501239462Sdim } 502239462Sdim }; 503239462Sdim 504234353Sdim // Each RegUnitSet is a sorted vector with a name. 505234353Sdim struct RegUnitSet { 506234353Sdim typedef std::vector<unsigned>::const_iterator iterator; 507234353Sdim 508234353Sdim std::string Name; 509234353Sdim std::vector<unsigned> Units; 510314564Sdim unsigned Weight = 0; // Cache the sum of all unit weights. 511314564Sdim unsigned Order = 0; // Cache the sort key. 512261991Sdim 513314564Sdim RegUnitSet() = default; 514234353Sdim }; 515234353Sdim 516239462Sdim // Base vector for identifying TopoSigs. The contents uniquely identify a 517239462Sdim // TopoSig, only computeSuperRegs needs to know how. 518239462Sdim typedef SmallVector<unsigned, 16> TopoSigId; 519239462Sdim 520223017Sdim // CodeGenRegBank - Represent a target's registers and the relations between 521223017Sdim // them. 522223017Sdim class CodeGenRegBank { 523224145Sdim SetTheory Sets; 524224145Sdim 525327952Sdim const CodeGenHwModes &CGH; 526327952Sdim 527280031Sdim std::deque<CodeGenSubRegIndex> SubRegIndices; 528234353Sdim DenseMap<Record*, CodeGenSubRegIndex*> Def2SubRegIdx; 529234353Sdim 530239462Sdim CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace); 531239462Sdim 532239462Sdim typedef std::map<SmallVector<CodeGenSubRegIndex*, 8>, 533239462Sdim CodeGenSubRegIndex*> ConcatIdxMap; 534239462Sdim ConcatIdxMap ConcatIdx; 535239462Sdim 536234353Sdim // Registers. 537280031Sdim std::deque<CodeGenRegister> Registers; 538243830Sdim StringMap<CodeGenRegister*> RegistersByName; 539223017Sdim DenseMap<Record*, CodeGenRegister*> Def2Reg; 540234353Sdim unsigned NumNativeRegUnits; 541223017Sdim 542239462Sdim std::map<TopoSigId, unsigned> TopoSigs; 543234353Sdim 544239462Sdim // Includes native (0..NumNativeRegUnits-1) and adopted register units. 545239462Sdim SmallVector<RegUnit, 8> RegUnits; 546239462Sdim 547226633Sdim // Register classes. 548280031Sdim std::list<CodeGenRegisterClass> RegClasses; 549224145Sdim DenseMap<Record*, CodeGenRegisterClass*> Def2RC; 550226633Sdim typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap; 551226633Sdim RCKeyMap Key2RC; 552224145Sdim 553234353Sdim // Remember each unique set of register units. Initially, this contains a 554234353Sdim // unique set for each register class. Simliar sets are coalesced with 555234353Sdim // pruneUnitSets and new supersets are inferred during computeRegUnitSets. 556234353Sdim std::vector<RegUnitSet> RegUnitSets; 557234353Sdim 558234353Sdim // Map RegisterClass index to the index of the RegUnitSet that contains the 559234353Sdim // class's units and any inferred RegUnit supersets. 560249423Sdim // 561249423Sdim // NOTE: This could grow beyond the number of register classes when we map 562249423Sdim // register units to lists of unit sets. If the list of unit sets does not 563249423Sdim // already exist for a register class, we create a new entry in this vector. 564314564Sdim std::vector<std::vector<unsigned>> RegClassUnitSets; 565234353Sdim 566261991Sdim // Give each register unit set an order based on sorting criteria. 567261991Sdim std::vector<unsigned> RegUnitSetOrder; 568261991Sdim 569341825Sdim // Keep track of synthesized definitions generated in TupleExpander. 570341825Sdim std::vector<std::unique_ptr<Record>> SynthDefs; 571341825Sdim 572226633Sdim // Add RC to *2RC maps. 573226633Sdim void addToMaps(CodeGenRegisterClass*); 574226633Sdim 575234353Sdim // Create a synthetic sub-class if it is missing. 576234353Sdim CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, 577288943Sdim const CodeGenRegister::Vec *Membs, 578234353Sdim StringRef Name); 579234353Sdim 580226633Sdim // Infer missing register classes. 581226633Sdim void computeInferredRegisterClasses(); 582234353Sdim void inferCommonSubClass(CodeGenRegisterClass *RC); 583234353Sdim void inferSubClassWithSubReg(CodeGenRegisterClass *RC); 584314564Sdim 585280031Sdim void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) { 586280031Sdim inferMatchingSuperRegClass(RC, RegClasses.begin()); 587280031Sdim } 588226633Sdim 589280031Sdim void inferMatchingSuperRegClass( 590280031Sdim CodeGenRegisterClass *RC, 591280031Sdim std::list<CodeGenRegisterClass>::iterator FirstSubRegRC); 592280031Sdim 593234353Sdim // Iteratively prune unit sets. 594234353Sdim void pruneUnitSets(); 595223017Sdim 596234353Sdim // Compute a weight for each register unit created during getSubRegs. 597234353Sdim void computeRegUnitWeights(); 598234353Sdim 599234353Sdim // Create a RegUnitSet for each RegClass and infer superclasses. 600234353Sdim void computeRegUnitSets(); 601234353Sdim 602223017Sdim // Populate the Composite map from sub-register relationships. 603223017Sdim void computeComposites(); 604223017Sdim 605243830Sdim // Compute a lane mask for each sub-register index. 606280031Sdim void computeSubRegLaneMasks(); 607243830Sdim 608280031Sdim /// Computes a lane mask for each register unit enumerated by a physical 609280031Sdim /// register. 610280031Sdim void computeRegUnitLaneMasks(); 611280031Sdim 612223017Sdim public: 613327952Sdim CodeGenRegBank(RecordKeeper&, const CodeGenHwModes&); 614223017Sdim 615224145Sdim SetTheory &getSets() { return Sets; } 616224145Sdim 617327952Sdim const CodeGenHwModes &getHwModes() const { return CGH; } 618327952Sdim 619223017Sdim // Sub-register indices. The first NumNamedIndices are defined by the user 620223017Sdim // in the .td files. The rest are synthesized such that all sub-registers 621223017Sdim // have a unique name. 622280031Sdim const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const { 623280031Sdim return SubRegIndices; 624280031Sdim } 625223017Sdim 626234353Sdim // Find a SubRegIndex form its Record def. 627234353Sdim CodeGenSubRegIndex *getSubRegIdx(Record*); 628223017Sdim 629223017Sdim // Find or create a sub-register index representing the A+B composition. 630234353Sdim CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A, 631234353Sdim CodeGenSubRegIndex *B); 632223017Sdim 633239462Sdim // Find or create a sub-register index representing the concatenation of 634239462Sdim // non-overlapping sibling indices. 635239462Sdim CodeGenSubRegIndex * 636261991Sdim getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8>&); 637239462Sdim 638360784Sdim const std::deque<CodeGenRegister> &getRegisters() const { 639360784Sdim return Registers; 640360784Sdim } 641314564Sdim 642360784Sdim const StringMap<CodeGenRegister *> &getRegistersByName() const { 643243830Sdim return RegistersByName; 644243830Sdim } 645223017Sdim 646223017Sdim // Find a register from its Record def. 647223017Sdim CodeGenRegister *getReg(Record*); 648223017Sdim 649234353Sdim // Get a Register's index into the Registers array. 650234353Sdim unsigned getRegIndex(const CodeGenRegister *Reg) const { 651234353Sdim return Reg->EnumValue - 1; 652234353Sdim } 653234353Sdim 654239462Sdim // Return the number of allocated TopoSigs. The first TopoSig representing 655239462Sdim // leaf registers is allocated number 0. 656239462Sdim unsigned getNumTopoSigs() const { 657239462Sdim return TopoSigs.size(); 658239462Sdim } 659239462Sdim 660239462Sdim // Find or create a TopoSig for the given TopoSigId. 661239462Sdim // This function is only for use by CodeGenRegister::computeSuperRegs(). 662239462Sdim // Others should simply use Reg->getTopoSig(). 663239462Sdim unsigned getTopoSig(const TopoSigId &Id) { 664239462Sdim return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second; 665239462Sdim } 666239462Sdim 667239462Sdim // Create a native register unit that is associated with one or two root 668239462Sdim // registers. 669276479Sdim unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) { 670239462Sdim RegUnits.resize(RegUnits.size() + 1); 671341825Sdim RegUnit &RU = RegUnits.back(); 672341825Sdim RU.Roots[0] = R0; 673341825Sdim RU.Roots[1] = R1; 674341825Sdim RU.Artificial = R0->Artificial; 675341825Sdim if (R1) 676341825Sdim RU.Artificial |= R1->Artificial; 677239462Sdim return RegUnits.size() - 1; 678239462Sdim } 679239462Sdim 680234353Sdim // Create a new non-native register unit that can be adopted by a register 681234353Sdim // to increase its pressure. Note that NumNativeRegUnits is not increased. 682234353Sdim unsigned newRegUnit(unsigned Weight) { 683239462Sdim RegUnits.resize(RegUnits.size() + 1); 684239462Sdim RegUnits.back().Weight = Weight; 685239462Sdim return RegUnits.size() - 1; 686234353Sdim } 687234353Sdim 688234353Sdim // Native units are the singular unit of a leaf register. Register aliasing 689234353Sdim // is completely characterized by native units. Adopted units exist to give 690234353Sdim // register additional weight but don't affect aliasing. 691360784Sdim bool isNativeUnit(unsigned RUID) const { 692234353Sdim return RUID < NumNativeRegUnits; 693234353Sdim } 694234353Sdim 695239462Sdim unsigned getNumNativeRegUnits() const { 696239462Sdim return NumNativeRegUnits; 697239462Sdim } 698239462Sdim 699239462Sdim RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; } 700239462Sdim const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; } 701239462Sdim 702280031Sdim std::list<CodeGenRegisterClass> &getRegClasses() { return RegClasses; } 703280031Sdim 704280031Sdim const std::list<CodeGenRegisterClass> &getRegClasses() const { 705224145Sdim return RegClasses; 706224145Sdim } 707224145Sdim 708224145Sdim // Find a register class from its def. 709224145Sdim CodeGenRegisterClass *getRegClass(Record*); 710224145Sdim 711224145Sdim /// getRegisterClassForRegister - Find the register class that contains the 712224145Sdim /// specified physical register. If the register is not in a register 713224145Sdim /// class, return null. If the register is in multiple classes, and the 714224145Sdim /// classes have a superset-subset relationship and the same set of types, 715224145Sdim /// return the superclass. Otherwise return null. 716224145Sdim const CodeGenRegisterClass* getRegClassForRegister(Record *R); 717224145Sdim 718360784Sdim // Analog of TargetRegisterInfo::getMinimalPhysRegClass. Unlike 719360784Sdim // getRegClassForRegister, this tries to find the smallest class containing 720360784Sdim // the physical register. If \p VT is specified, it will only find classes 721360784Sdim // with a matching type 722360784Sdim const CodeGenRegisterClass * 723360784Sdim getMinimalPhysRegClass(Record *RegRecord, ValueTypeByHwMode *VT = nullptr); 724360784Sdim 725234353Sdim // Get the sum of unit weights. 726234353Sdim unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const { 727234353Sdim unsigned Weight = 0; 728234353Sdim for (std::vector<unsigned>::const_iterator 729234353Sdim I = Units.begin(), E = Units.end(); I != E; ++I) 730239462Sdim Weight += getRegUnit(*I).Weight; 731234353Sdim return Weight; 732234353Sdim } 733234353Sdim 734261991Sdim unsigned getRegSetIDAt(unsigned Order) const { 735261991Sdim return RegUnitSetOrder[Order]; 736261991Sdim } 737314564Sdim 738261991Sdim const RegUnitSet &getRegSetAt(unsigned Order) const { 739261991Sdim return RegUnitSets[RegUnitSetOrder[Order]]; 740261991Sdim } 741261991Sdim 742234353Sdim // Increase a RegUnitWeight. 743234353Sdim void increaseRegUnitWeight(unsigned RUID, unsigned Inc) { 744239462Sdim getRegUnit(RUID).Weight += Inc; 745234353Sdim } 746234353Sdim 747234353Sdim // Get the number of register pressure dimensions. 748234353Sdim unsigned getNumRegPressureSets() const { return RegUnitSets.size(); } 749234353Sdim 750234353Sdim // Get a set of register unit IDs for a given dimension of pressure. 751261991Sdim const RegUnitSet &getRegPressureSet(unsigned Idx) const { 752234353Sdim return RegUnitSets[Idx]; 753234353Sdim } 754234353Sdim 755249423Sdim // The number of pressure set lists may be larget than the number of 756249423Sdim // register classes if some register units appeared in a list of sets that 757249423Sdim // did not correspond to an existing register class. 758249423Sdim unsigned getNumRegClassPressureSetLists() const { 759249423Sdim return RegClassUnitSets.size(); 760249423Sdim } 761249423Sdim 762234353Sdim // Get a list of pressure set IDs for a register class. Liveness of a 763234353Sdim // register in this class impacts each pressure set in this list by the 764234353Sdim // weight of the register. An exact solution requires all registers in a 765234353Sdim // class to have the same class, but it is not strictly guaranteed. 766234353Sdim ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const { 767234353Sdim return RegClassUnitSets[RCIdx]; 768234353Sdim } 769234353Sdim 770223017Sdim // Computed derived records such as missing sub-register indices. 771223017Sdim void computeDerivedInfo(); 772224145Sdim 773234353Sdim // Compute the set of registers completely covered by the registers in Regs. 774234353Sdim // The returned BitVector will have a bit set for each register in Regs, 775234353Sdim // all sub-registers, and all super-registers that are covered by the 776234353Sdim // registers in Regs. 777234353Sdim // 778234353Sdim // This is used to compute the mask of call-preserved registers from a list 779234353Sdim // of callee-saves. 780234353Sdim BitVector computeCoveredRegisters(ArrayRef<Record*> Regs); 781261991Sdim 782261991Sdim // Bit mask of lanes that cover their registers. A sub-register index whose 783261991Sdim // LaneMask is contained in CoveringLanes will be completely covered by 784261991Sdim // another sub-register with the same or larger lane mask. 785314564Sdim LaneBitmask CoveringLanes; 786321369Sdim 787321369Sdim // Helper function for printing debug information. Handles artificial 788321369Sdim // (non-native) reg units. 789321369Sdim void printRegUnitName(unsigned Unit) const; 790223017Sdim }; 791193323Sed 792314564Sdim} // end namespace llvm 793314564Sdim 794314564Sdim#endif // LLVM_UTILS_TABLEGEN_CODEGENREGISTERS_H 795