Add TRI::getSubClassWithSubReg(RC, Idx) function.
[oota-llvm.git] / 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
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