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
31namespace 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
105    DenseMap<Record*, CodeGenRegisterClass*> SubClassWithSubReg;
106
107  public:
108    unsigned EnumValue;
109    std::string Namespace;
110    std::vector<MVT::SimpleValueType> VTs;
111    unsigned SpillSize;
112    unsigned SpillAlignment;
113    int CopyCost;
114    bool Allocatable;
115    // Map SubRegIndex -> RegisterClass
116    DenseMap<Record*,Record*> SubRegClasses;
117    std::string AltOrderSelect;
118
119    // Return the Record that defined this class, or NULL if the class was
120    // created by TableGen.
121    Record *getDef() const { return TheDef; }
122
123    const std::string &getName() const { return Name; }
124    std::string getQualifiedName() const;
125    const std::vector<MVT::SimpleValueType> &getValueTypes() const {return VTs;}
126    unsigned getNumValueTypes() const { return VTs.size(); }
127
128    MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const {
129      if (VTNum < VTs.size())
130        return VTs[VTNum];
131      assert(0 && "VTNum greater than number of ValueTypes in RegClass!");
132      abort();
133    }
134
135    // Return true if this this class contains the register.
136    bool contains(const CodeGenRegister*) const;
137
138    // Returns true if RC is a subclass.
139    // RC is a sub-class of this class if it is a valid replacement for any
140    // instruction operand where a register of this classis required. It must
141    // satisfy these conditions:
142    //
143    // 1. All RC registers are also in this.
144    // 2. The RC spill size must not be smaller than our spill size.
145    // 3. RC spill alignment must be compatible with ours.
146    //
147    bool hasSubClass(const CodeGenRegisterClass *RC) const {
148      return SubClasses.test(RC->EnumValue);
149    }
150
151    // getSubClassWithSubReg - Returns the largest sub-class where all
152    // registers have a SubIdx sub-register.
153    CodeGenRegisterClass *getSubClassWithSubReg(Record *SubIdx) const {
154      return SubClassWithSubReg.lookup(SubIdx);
155    }
156
157    void setSubClassWithSubReg(Record *SubIdx, CodeGenRegisterClass *SubRC) {
158      SubClassWithSubReg[SubIdx] = SubRC;
159    }
160
161    // getSubClasses - Returns a constant BitVector of subclasses indexed by
162    // EnumValue.
163    // The SubClasses vector includs an entry for this class.
164    const BitVector &getSubClasses() const { return SubClasses; }
165
166    // getSuperClasses - Returns a list of super classes ordered by EnumValue.
167    // The array does not include an entry for this class.
168    ArrayRef<CodeGenRegisterClass*> getSuperClasses() const {
169      return SuperClasses;
170    }
171
172    // Returns an ordered list of class members.
173    // The order of registers is the same as in the .td file.
174    // No = 0 is the default allocation order, No = 1 is the first alternative.
175    ArrayRef<Record*> getOrder(unsigned No = 0) const {
176        return Orders[No];
177    }
178
179    // Return the total number of allocation orders available.
180    unsigned getNumOrders() const { return Orders.size(); }
181
182    // Get the set of registers.  This set contains the same registers as
183    // getOrder(0).
184    const CodeGenRegister::Set &getMembers() const { return Members; }
185
186    CodeGenRegisterClass(CodeGenRegBank&, Record *R);
187
188    // A key representing the parts of a register class used for forming
189    // sub-classes.  Note the ordering provided by this key is not the same as
190    // the topological order used for the EnumValues.
191    struct Key {
192      const CodeGenRegister::Set *Members;
193      unsigned SpillSize;
194      unsigned SpillAlignment;
195
196      Key(const Key &O)
197        : Members(O.Members),
198          SpillSize(O.SpillSize),
199          SpillAlignment(O.SpillAlignment) {}
200
201      Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0)
202        : Members(M), SpillSize(S), SpillAlignment(A) {}
203
204      Key(const CodeGenRegisterClass &RC)
205        : Members(&RC.getMembers()),
206          SpillSize(RC.SpillSize),
207          SpillAlignment(RC.SpillAlignment) {}
208
209      // Lexicographical order of (Members, SpillSize, SpillAlignment).
210      bool operator<(const Key&) const;
211    };
212
213    // Create a non-user defined register class.
214    CodeGenRegisterClass(StringRef Name, Key Props);
215
216    // Called by CodeGenRegBank::CodeGenRegBank().
217    static void computeSubClasses(CodeGenRegBank&);
218  };
219
220  // CodeGenRegBank - Represent a target's registers and the relations between
221  // them.
222  class CodeGenRegBank {
223    RecordKeeper &Records;
224    SetTheory Sets;
225
226    std::vector<Record*> SubRegIndices;
227    unsigned NumNamedIndices;
228    std::vector<CodeGenRegister*> Registers;
229    DenseMap<Record*, CodeGenRegister*> Def2Reg;
230
231    // Register classes.
232    std::vector<CodeGenRegisterClass*> RegClasses;
233    DenseMap<Record*, CodeGenRegisterClass*> Def2RC;
234    typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap;
235    RCKeyMap Key2RC;
236
237    // Add RC to *2RC maps.
238    void addToMaps(CodeGenRegisterClass*);
239
240    // Infer missing register classes.
241    void computeInferredRegisterClasses();
242
243    // Composite SubRegIndex instances.
244    // Map (SubRegIndex, SubRegIndex) -> SubRegIndex.
245    typedef DenseMap<std::pair<Record*, Record*>, Record*> CompositeMap;
246    CompositeMap Composite;
247
248    // Populate the Composite map from sub-register relationships.
249    void computeComposites();
250
251  public:
252    CodeGenRegBank(RecordKeeper&);
253
254    SetTheory &getSets() { return Sets; }
255
256    // Sub-register indices. The first NumNamedIndices are defined by the user
257    // in the .td files. The rest are synthesized such that all sub-registers
258    // have a unique name.
259    const std::vector<Record*> &getSubRegIndices() { return SubRegIndices; }
260    unsigned getNumNamedIndices() { return NumNamedIndices; }
261
262    // Map a SubRegIndex Record to its enum value.
263    unsigned getSubRegIndexNo(Record *idx);
264
265    // Find or create a sub-register index representing the A+B composition.
266    Record *getCompositeSubRegIndex(Record *A, Record *B, bool create = false);
267
268    const std::vector<CodeGenRegister*> &getRegisters() { return Registers; }
269
270    // Find a register from its Record def.
271    CodeGenRegister *getReg(Record*);
272
273    ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
274      return RegClasses;
275    }
276
277    // Find a register class from its def.
278    CodeGenRegisterClass *getRegClass(Record*);
279
280    /// getRegisterClassForRegister - Find the register class that contains the
281    /// specified physical register.  If the register is not in a register
282    /// class, return null. If the register is in multiple classes, and the
283    /// classes have a superset-subset relationship and the same set of types,
284    /// return the superclass.  Otherwise return null.
285    const CodeGenRegisterClass* getRegClassForRegister(Record *R);
286
287    // Computed derived records such as missing sub-register indices.
288    void computeDerivedInfo();
289
290    // Compute full overlap sets for every register. These sets include the
291    // rarely used aliases that are neither sub nor super-registers.
292    //
293    // Map[R1].count(R2) is reflexive and symmetric, but not transitive.
294    //
295    // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2].
296    void computeOverlaps(std::map<const CodeGenRegister*,
297                                  CodeGenRegister::Set> &Map);
298  };
299}
300
301#endif
302