utils/TableGen/CodeGenRegisters.h

   1 //===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines structures to encapsulate information gleaned from the
  11 // target register and register class definitions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef CODEGEN_REGISTERS_H
  16 #define CODEGEN_REGISTERS_H
  17
  18 #include "SetTheory.h"
  19 #include "llvm/TableGen/Record.h"
  20 #include "llvm/CodeGen/ValueTypes.h"
  21 #include "llvm/ADT/ArrayRef.h"
  22 #include "llvm/ADT/BitVector.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/SetVector.h"
  25 #include <cstdlib>
  26 #include <map>
  27 #include <string>
  28 #include <set>
  29 #include <vector>
  30
  31 namespace llvm {
  32   class CodeGenRegBank;
  33
  34   /// CodeGenRegister - Represents a register definition.
  35   struct CodeGenRegister {
  36     Record *TheDef;
  37     unsigned EnumValue;
  38     unsigned CostPerUse;
  39
  40     // Map SubRegIndex -> Register.
  41     typedef std::map<Record*, CodeGenRegister*, LessRecord> SubRegMap;
  42
  43     CodeGenRegister(Record *R, unsigned Enum);
  44
  45     const std::string &getName() const;
  46
  47     // Get a map of sub-registers computed lazily.
  48     // This includes unique entries for all sub-sub-registers.
  49     const SubRegMap &getSubRegs(CodeGenRegBank&);
  50
  51     const SubRegMap &getSubRegs() const {
  52       assert(SubRegsComplete && "Must precompute sub-registers");
  53       return SubRegs;
  54     }
  55
  56     // Add sub-registers to OSet following a pre-order defined by the .td file.
  57     void addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const;
  58
  59     // List of super-registers in topological order, small to large.
  60     typedef std::vector<CodeGenRegister*> SuperRegList;
  61
  62     // Get the list of super-registers.
  63     // This is only valid after computeDerivedInfo has visited all registers.
  64     const SuperRegList &getSuperRegs() const {
  65       assert(SubRegsComplete && "Must precompute sub-registers");
  66       return SuperRegs;
  67     }
  68
  69     // Order CodeGenRegister pointers by EnumValue.
  70     struct Less {
  71       bool operator()(const CodeGenRegister *A,
  72                       const CodeGenRegister *B) const {
  73         assert(A && B);
  74         return A->EnumValue < B->EnumValue;
  75       }
  76     };
  77
  78     // Canonically ordered set.
  79     typedef std::set<const CodeGenRegister*, Less> Set;
  80
  81   private:
  82     bool SubRegsComplete;
  83     SubRegMap SubRegs;
  84     SuperRegList SuperRegs;
  85   };
  86
  87
  88   class CodeGenRegisterClass {
  89     CodeGenRegister::Set Members;
  90     // Allocation orders. Order[0] always contains all registers in Members.
  91     std::vector<SmallVector<Record*, 16> > Orders;
  92     // Bit mask of sub-classes including this, indexed by their EnumValue.
  93     BitVector SubClasses;
  94     // List of super-classes, topologocally ordered to have the larger classes
  95     // first.  This is the same as sorting by EnumValue.
  96     SmallVector<CodeGenRegisterClass*, 4> SuperClasses;
  97     Record *TheDef;
  98     std::string Name;
  99
 100     // For a synthesized class, inherit missing properties from the nearest
 101     // super-class.
 102     void inheritProperties(CodeGenRegBank&);
 103
 104     // Map SubRegIndex -> sub-class.  This is the largest sub-class where all
 105     // registers have a SubRegIndex sub-register.
 106     DenseMap<Record*, CodeGenRegisterClass*> SubClassWithSubReg;
 107
 108     // Map SubRegIndex -> set of super-reg classes.  This is all register
 109     // classes SuperRC such that:
 110     //
 111     //   R:SubRegIndex in this RC for all R in SuperRC.
 112     //
 113     DenseMap<Record*, SmallPtrSet<CodeGenRegisterClass*, 8> > SuperRegClasses;
 114   public:
 115     unsigned EnumValue;
 116     std::string Namespace;
 117     std::vector<MVT::SimpleValueType> VTs;
 118     unsigned SpillSize;
 119     unsigned SpillAlignment;
 120     int CopyCost;
 121     bool Allocatable;
 122     // Map SubRegIndex -> RegisterClass
 123     DenseMap<Record*,Record*> SubRegClasses;
 124     std::string AltOrderSelect;
 125
 126     // Return the Record that defined this class, or NULL if the class was
 127     // created by TableGen.
 128     Record *getDef() const { return TheDef; }
 129
 130     const std::string &getName() const { return Name; }
 131     std::string getQualifiedName() const;
 132     const std::vector<MVT::SimpleValueType> &getValueTypes() const {return VTs;}
 133     unsigned getNumValueTypes() const { return VTs.size(); }
 134
 135     MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const {
 136       if (VTNum < VTs.size())
 137         return VTs[VTNum];
 138       assert(0 && "VTNum greater than number of ValueTypes in RegClass!");
 139       abort();
 140     }
 141
 142     // Return true if this this class contains the register.
 143     bool contains(const CodeGenRegister*) const;
 144
 145     // Returns true if RC is a subclass.
 146     // RC is a sub-class of this class if it is a valid replacement for any
 147     // instruction operand where a register of this classis required. It must
 148     // satisfy these conditions:
 149     //
 150     // 1. All RC registers are also in this.
 151     // 2. The RC spill size must not be smaller than our spill size.
 152     // 3. RC spill alignment must be compatible with ours.
 153     //
 154     bool hasSubClass(const CodeGenRegisterClass *RC) const {
 155       return SubClasses.test(RC->EnumValue);
 156     }
 157
 158     // getSubClassWithSubReg - Returns the largest sub-class where all
 159     // registers have a SubIdx sub-register.
 160     CodeGenRegisterClass *getSubClassWithSubReg(Record *SubIdx) const {
 161       return SubClassWithSubReg.lookup(SubIdx);
 162     }
 163
 164     void setSubClassWithSubReg(Record *SubIdx, CodeGenRegisterClass *SubRC) {
 165       SubClassWithSubReg[SubIdx] = SubRC;
 166     }
 167
 168     // getSuperRegClasses - Returns a bit vector of all register classes
 169     // containing only SubIdx super-registers of this class.
 170     void getSuperRegClasses(Record *SubIdx, BitVector &Out) const;
 171
 172     // addSuperRegClass - Add a class containing only SudIdx super-registers.
 173     void addSuperRegClass(Record *SubIdx, CodeGenRegisterClass *SuperRC) {
 174       SuperRegClasses[SubIdx].insert(SuperRC);
 175     }
 176
 177     // getSubClasses - Returns a constant BitVector of subclasses indexed by
 178     // EnumValue.
 179     // The SubClasses vector includs an entry for this class.
 180     const BitVector &getSubClasses() const { return SubClasses; }
 181
 182     // getSuperClasses - Returns a list of super classes ordered by EnumValue.
 183     // The array does not include an entry for this class.
 184     ArrayRef<CodeGenRegisterClass*> getSuperClasses() const {
 185       return SuperClasses;
 186     }
 187
 188     // Returns an ordered list of class members.
 189     // The order of registers is the same as in the .td file.
 190     // No = 0 is the default allocation order, No = 1 is the first alternative.
 191     ArrayRef<Record*> getOrder(unsigned No = 0) const {
 192         return Orders[No];
 193     }
 194
 195     // Return the total number of allocation orders available.
 196     unsigned getNumOrders() const { return Orders.size(); }
 197
 198     // Get the set of registers.  This set contains the same registers as
 199     // getOrder(0).
 200     const CodeGenRegister::Set &getMembers() const { return Members; }
 201
 202     CodeGenRegisterClass(CodeGenRegBank&, Record *R);
 203
 204     // A key representing the parts of a register class used for forming
 205     // sub-classes.  Note the ordering provided by this key is not the same as
 206     // the topological order used for the EnumValues.
 207     struct Key {
 208       const CodeGenRegister::Set *Members;
 209       unsigned SpillSize;
 210       unsigned SpillAlignment;
 211
 212       Key(const Key &O)
 213         : Members(O.Members),
 214           SpillSize(O.SpillSize),
 215           SpillAlignment(O.SpillAlignment) {}
 216
 217       Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0)
 218         : Members(M), SpillSize(S), SpillAlignment(A) {}
 219
 220       Key(const CodeGenRegisterClass &RC)
 221         : Members(&RC.getMembers()),
 222           SpillSize(RC.SpillSize),
 223           SpillAlignment(RC.SpillAlignment) {}
 224
 225       // Lexicographical order of (Members, SpillSize, SpillAlignment).
 226       bool operator<(const Key&) const;
 227     };
 228
 229     // Create a non-user defined register class.
 230     CodeGenRegisterClass(StringRef Name, Key Props);
 231
 232     // Called by CodeGenRegBank::CodeGenRegBank().
 233     static void computeSubClasses(CodeGenRegBank&);
 234   };
 235
 236   // CodeGenRegBank - Represent a target's registers and the relations between
 237   // them.
 238   class CodeGenRegBank {
 239     RecordKeeper &Records;
 240     SetTheory Sets;
 241
 242     std::vector<Record*> SubRegIndices;
 243     unsigned NumNamedIndices;
 244     std::vector<CodeGenRegister*> Registers;
 245     DenseMap<Record*, CodeGenRegister*> Def2Reg;
 246
 247     // Register classes.
 248     std::vector<CodeGenRegisterClass*> RegClasses;
 249     DenseMap<Record*, CodeGenRegisterClass*> Def2RC;
 250     typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap;
 251     RCKeyMap Key2RC;
 252
 253     // Add RC to *2RC maps.
 254     void addToMaps(CodeGenRegisterClass*);
 255
 256     // Create a synthetic sub-class if it is missing.
 257     CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC,
 258                                               const CodeGenRegister::Set *Membs,
 259                                               StringRef Name);
 260
 261     // Infer missing register classes.
 262     void computeInferredRegisterClasses();
 263     void inferCommonSubClass(CodeGenRegisterClass *RC);
 264     void inferSubClassWithSubReg(CodeGenRegisterClass *RC);
 265     void inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
 266                                     unsigned FirstSubRegRC = 0);
 267
 268     // Composite SubRegIndex instances.
 269     // Map (SubRegIndex, SubRegIndex) -> SubRegIndex.
 270     typedef DenseMap<std::pair<Record*, Record*>, Record*> CompositeMap;
 271     CompositeMap Composite;
 272
 273     // Populate the Composite map from sub-register relationships.
 274     void computeComposites();
 275
 276   public:
 277     CodeGenRegBank(RecordKeeper&);
 278
 279     SetTheory &getSets() { return Sets; }
 280
 281     // Sub-register indices. The first NumNamedIndices are defined by the user
 282     // in the .td files. The rest are synthesized such that all sub-registers
 283     // have a unique name.
 284     const std::vector<Record*> &getSubRegIndices() { return SubRegIndices; }
 285     unsigned getNumNamedIndices() { return NumNamedIndices; }
 286
 287     // Map a SubRegIndex Record to its enum value.
 288     unsigned getSubRegIndexNo(Record *idx);
 289
 290     // Find or create a sub-register index representing the A+B composition.
 291     Record *getCompositeSubRegIndex(Record *A, Record *B, bool create = false);
 292
 293     const std::vector<CodeGenRegister*> &getRegisters() { return Registers; }
 294
 295     // Find a register from its Record def.
 296     CodeGenRegister *getReg(Record*);
 297
 298     ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
 299       return RegClasses;
 300     }
 301
 302     // Find a register class from its def.
 303     CodeGenRegisterClass *getRegClass(Record*);
 304
 305     /// getRegisterClassForRegister - Find the register class that contains the
 306     /// specified physical register.  If the register is not in a register
 307     /// class, return null. If the register is in multiple classes, and the
 308     /// classes have a superset-subset relationship and the same set of types,
 309     /// return the superclass.  Otherwise return null.
 310     const CodeGenRegisterClass* getRegClassForRegister(Record *R);
 311
 312     // Computed derived records such as missing sub-register indices.
 313     void computeDerivedInfo();
 314
 315     // Compute full overlap sets for every register. These sets include the
 316     // rarely used aliases that are neither sub nor super-registers.
 317     //
 318     // Map[R1].count(R2) is reflexive and symmetric, but not transitive.
 319     //
 320     // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2].
 321     void computeOverlaps(std::map<const CodeGenRegister*,
 322                                   CodeGenRegister::Set> &Map);
 323   };
 324 }
 325
 326 #endif