1 //===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines structures to encapsulate information gleaned from the
11 // target register and register class definitions.
13 //===----------------------------------------------------------------------===//
15 #ifndef CODEGEN_REGISTERS_H
16 #define CODEGEN_REGISTERS_H
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"
34 /// CodeGenRegister - Represents a register definition.
35 struct CodeGenRegister {
39 bool CoveredBySubRegs;
41 // Map SubRegIndex -> Register.
42 typedef std::map<Record*, CodeGenRegister*, LessRecord> SubRegMap;
44 CodeGenRegister(Record *R, unsigned Enum);
46 const std::string &getName() const;
48 // Get a map of sub-registers computed lazily.
49 // This includes unique entries for all sub-sub-registers.
50 const SubRegMap &getSubRegs(CodeGenRegBank&);
52 const SubRegMap &getSubRegs() const {
53 assert(SubRegsComplete && "Must precompute sub-registers");
57 // Add sub-registers to OSet following a pre-order defined by the .td file.
58 void addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const;
60 // List of super-registers in topological order, small to large.
61 typedef std::vector<CodeGenRegister*> SuperRegList;
63 // Get the list of super-registers.
64 // This is only valid after computeDerivedInfo has visited all registers.
65 const SuperRegList &getSuperRegs() const {
66 assert(SubRegsComplete && "Must precompute sub-registers");
70 // Order CodeGenRegister pointers by EnumValue.
72 bool operator()(const CodeGenRegister *A,
73 const CodeGenRegister *B) const {
75 return A->EnumValue < B->EnumValue;
79 // Canonically ordered set.
80 typedef std::set<const CodeGenRegister*, Less> Set;
85 SuperRegList SuperRegs;
89 class CodeGenRegisterClass {
90 CodeGenRegister::Set Members;
91 // Allocation orders. Order[0] always contains all registers in Members.
92 std::vector<SmallVector<Record*, 16> > Orders;
93 // Bit mask of sub-classes including this, indexed by their EnumValue.
95 // List of super-classes, topologocally ordered to have the larger classes
96 // first. This is the same as sorting by EnumValue.
97 SmallVector<CodeGenRegisterClass*, 4> SuperClasses;
101 // For a synthesized class, inherit missing properties from the nearest
103 void inheritProperties(CodeGenRegBank&);
105 // Map SubRegIndex -> sub-class. This is the largest sub-class where all
106 // registers have a SubRegIndex sub-register.
107 DenseMap<Record*, CodeGenRegisterClass*> SubClassWithSubReg;
109 // Map SubRegIndex -> set of super-reg classes. This is all register
110 // classes SuperRC such that:
112 // R:SubRegIndex in this RC for all R in SuperRC.
114 DenseMap<Record*, SmallPtrSet<CodeGenRegisterClass*, 8> > SuperRegClasses;
117 std::string Namespace;
118 std::vector<MVT::SimpleValueType> VTs;
120 unsigned SpillAlignment;
123 // Map SubRegIndex -> RegisterClass
124 DenseMap<Record*,Record*> SubRegClasses;
125 std::string AltOrderSelect;
127 // Return the Record that defined this class, or NULL if the class was
128 // created by TableGen.
129 Record *getDef() const { return TheDef; }
131 const std::string &getName() const { return Name; }
132 std::string getQualifiedName() const;
133 const std::vector<MVT::SimpleValueType> &getValueTypes() const {return VTs;}
134 unsigned getNumValueTypes() const { return VTs.size(); }
136 MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const {
137 if (VTNum < VTs.size())
139 assert(0 && "VTNum greater than number of ValueTypes in RegClass!");
143 // Return true if this this class contains the register.
144 bool contains(const CodeGenRegister*) const;
146 // Returns true if RC is a subclass.
147 // RC is a sub-class of this class if it is a valid replacement for any
148 // instruction operand where a register of this classis required. It must
149 // satisfy these conditions:
151 // 1. All RC registers are also in this.
152 // 2. The RC spill size must not be smaller than our spill size.
153 // 3. RC spill alignment must be compatible with ours.
155 bool hasSubClass(const CodeGenRegisterClass *RC) const {
156 return SubClasses.test(RC->EnumValue);
159 // getSubClassWithSubReg - Returns the largest sub-class where all
160 // registers have a SubIdx sub-register.
161 CodeGenRegisterClass *getSubClassWithSubReg(Record *SubIdx) const {
162 return SubClassWithSubReg.lookup(SubIdx);
165 void setSubClassWithSubReg(Record *SubIdx, CodeGenRegisterClass *SubRC) {
166 SubClassWithSubReg[SubIdx] = SubRC;
169 // getSuperRegClasses - Returns a bit vector of all register classes
170 // containing only SubIdx super-registers of this class.
171 void getSuperRegClasses(Record *SubIdx, BitVector &Out) const;
173 // addSuperRegClass - Add a class containing only SudIdx super-registers.
174 void addSuperRegClass(Record *SubIdx, CodeGenRegisterClass *SuperRC) {
175 SuperRegClasses[SubIdx].insert(SuperRC);
178 // getSubClasses - Returns a constant BitVector of subclasses indexed by
180 // The SubClasses vector includs an entry for this class.
181 const BitVector &getSubClasses() const { return SubClasses; }
183 // getSuperClasses - Returns a list of super classes ordered by EnumValue.
184 // The array does not include an entry for this class.
185 ArrayRef<CodeGenRegisterClass*> getSuperClasses() const {
189 // Returns an ordered list of class members.
190 // The order of registers is the same as in the .td file.
191 // No = 0 is the default allocation order, No = 1 is the first alternative.
192 ArrayRef<Record*> getOrder(unsigned No = 0) const {
196 // Return the total number of allocation orders available.
197 unsigned getNumOrders() const { return Orders.size(); }
199 // Get the set of registers. This set contains the same registers as
201 const CodeGenRegister::Set &getMembers() const { return Members; }
203 CodeGenRegisterClass(CodeGenRegBank&, Record *R);
205 // A key representing the parts of a register class used for forming
206 // sub-classes. Note the ordering provided by this key is not the same as
207 // the topological order used for the EnumValues.
209 const CodeGenRegister::Set *Members;
211 unsigned SpillAlignment;
214 : Members(O.Members),
215 SpillSize(O.SpillSize),
216 SpillAlignment(O.SpillAlignment) {}
218 Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0)
219 : Members(M), SpillSize(S), SpillAlignment(A) {}
221 Key(const CodeGenRegisterClass &RC)
222 : Members(&RC.getMembers()),
223 SpillSize(RC.SpillSize),
224 SpillAlignment(RC.SpillAlignment) {}
226 // Lexicographical order of (Members, SpillSize, SpillAlignment).
227 bool operator<(const Key&) const;
230 // Create a non-user defined register class.
231 CodeGenRegisterClass(StringRef Name, Key Props);
233 // Called by CodeGenRegBank::CodeGenRegBank().
234 static void computeSubClasses(CodeGenRegBank&);
237 // CodeGenRegBank - Represent a target's registers and the relations between
239 class CodeGenRegBank {
240 RecordKeeper &Records;
243 std::vector<Record*> SubRegIndices;
244 unsigned NumNamedIndices;
245 std::vector<CodeGenRegister*> Registers;
246 DenseMap<Record*, CodeGenRegister*> Def2Reg;
249 std::vector<CodeGenRegisterClass*> RegClasses;
250 DenseMap<Record*, CodeGenRegisterClass*> Def2RC;
251 typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap;
254 // Add RC to *2RC maps.
255 void addToMaps(CodeGenRegisterClass*);
257 // Create a synthetic sub-class if it is missing.
258 CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC,
259 const CodeGenRegister::Set *Membs,
262 // Infer missing register classes.
263 void computeInferredRegisterClasses();
264 void inferCommonSubClass(CodeGenRegisterClass *RC);
265 void inferSubClassWithSubReg(CodeGenRegisterClass *RC);
266 void inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
267 unsigned FirstSubRegRC = 0);
269 // Composite SubRegIndex instances.
270 // Map (SubRegIndex, SubRegIndex) -> SubRegIndex.
271 typedef DenseMap<std::pair<Record*, Record*>, Record*> CompositeMap;
272 CompositeMap Composite;
274 // Populate the Composite map from sub-register relationships.
275 void computeComposites();
278 CodeGenRegBank(RecordKeeper&);
280 SetTheory &getSets() { return Sets; }
282 // Sub-register indices. The first NumNamedIndices are defined by the user
283 // in the .td files. The rest are synthesized such that all sub-registers
284 // have a unique name.
285 const std::vector<Record*> &getSubRegIndices() { return SubRegIndices; }
286 unsigned getNumNamedIndices() { return NumNamedIndices; }
288 // Map a SubRegIndex Record to its enum value.
289 unsigned getSubRegIndexNo(Record *idx);
291 // Find or create a sub-register index representing the A+B composition.
292 Record *getCompositeSubRegIndex(Record *A, Record *B, bool create = false);
294 const std::vector<CodeGenRegister*> &getRegisters() { return Registers; }
296 // Find a register from its Record def.
297 CodeGenRegister *getReg(Record*);
299 ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
303 // Find a register class from its def.
304 CodeGenRegisterClass *getRegClass(Record*);
306 /// getRegisterClassForRegister - Find the register class that contains the
307 /// specified physical register. If the register is not in a register
308 /// class, return null. If the register is in multiple classes, and the
309 /// classes have a superset-subset relationship and the same set of types,
310 /// return the superclass. Otherwise return null.
311 const CodeGenRegisterClass* getRegClassForRegister(Record *R);
313 // Computed derived records such as missing sub-register indices.
314 void computeDerivedInfo();
316 // Compute full overlap sets for every register. These sets include the
317 // rarely used aliases that are neither sub nor super-registers.
319 // Map[R1].count(R2) is reflexive and symmetric, but not transitive.
321 // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2].
322 void computeOverlaps(std::map<const CodeGenRegister*,
323 CodeGenRegister::Set> &Map);
325 // Compute the set of registers completely covered by the registers in Regs.
326 // The returned BitVector will have a bit set for each register in Regs,
327 // all sub-registers, and all super-registers that are covered by the
328 // registers in Regs.
330 // This is used to compute the mask of call-preserved registers from a list
332 BitVector computeCoveredRegisters(ArrayRef<Record*> Regs);