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         return A->EnumValue < B->EnumValue;
74       }
75     };
76 
77     // Canonically ordered set.
78     typedef std::set<const CodeGenRegister*, Less> Set;
79 
80   private:
81     bool SubRegsComplete;
82     SubRegMap SubRegs;
83     SuperRegList SuperRegs;
84   };
85 
86 
87   class CodeGenRegisterClass {
88     CodeGenRegister::Set Members;
89     const std::vector<Record*> *Elements;
90     std::vector<SmallVector<Record*, 16> > AltOrders;
91     // Bit mask of sub-classes including this, indexed by their EnumValue.
92     BitVector SubClasses;
93     // List of super-classes, topologocally ordered to have the larger classes
94     // first.  This is the same as sorting by EnumValue.
95     SmallVector<CodeGenRegisterClass*, 4> SuperClasses;
96   public:
97     Record *TheDef;
98     unsigned EnumValue;
99     std::string Namespace;
100     std::vector<MVT::SimpleValueType> VTs;
101     unsigned SpillSize;
102     unsigned SpillAlignment;
103     int CopyCost;
104     bool Allocatable;
105     // Map SubRegIndex -> RegisterClass
106     DenseMap<Record*,Record*> SubRegClasses;
107     std::string AltOrderSelect;
108 
109     const std::string &getName() const;
110     const std::vector<MVT::SimpleValueType> &getValueTypes() const {return VTs;}
111     unsigned getNumValueTypes() const { return VTs.size(); }
112 
113     MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const {
114       if (VTNum < VTs.size())
115         return VTs[VTNum];
116       assert(0 && "VTNum greater than number of ValueTypes in RegClass!");
117       abort();
118     }
119 
120     // Return true if this this class contains the register.
121     bool contains(const CodeGenRegister*) const;
122 
123     // Returns true if RC is a subclass.
124     // RC is a sub-class of this class if it is a valid replacement for any
125     // instruction operand where a register of this classis required. It must
126     // satisfy these conditions:
127     //
128     // 1. All RC registers are also in this.
129     // 2. The RC spill size must not be smaller than our spill size.
130     // 3. RC spill alignment must be compatible with ours.
131     //
132     bool hasSubClass(const CodeGenRegisterClass *RC) const {
133       return SubClasses.test(RC->EnumValue);
134     }
135 
136     // getSubClasses - Returns a constant BitVector of subclasses indexed by
137     // EnumValue.
138     // The SubClasses vector includs an entry for this class.
139     const BitVector &getSubClasses() const { return SubClasses; };
140 
141     // getSuperClasses - Returns a list of super classes ordered by EnumValue.
142     // The array does not include an entry for this class.
143     ArrayRef<CodeGenRegisterClass*> getSuperClasses() const {
144       return SuperClasses;
145     }
146 
147     // Returns an ordered list of class members.
148     // The order of registers is the same as in the .td file.
149     // No = 0 is the default allocation order, No = 1 is the first alternative.
150     ArrayRef<Record*> getOrder(unsigned No = 0) const {
151       if (No == 0)
152         return *Elements;
153       else
154         return AltOrders[No - 1];
155     }
156 
157     // Return the total number of allocation orders available.
158     unsigned getNumOrders() const { return 1 + AltOrders.size(); }
159 
160     // Get the set of registers.  This set contains the same registers as
161     // getOrder(0).
162     const CodeGenRegister::Set &getMembers() const { return Members; }
163 
164     CodeGenRegisterClass(CodeGenRegBank&, Record *R);
165 
166     // Called by CodeGenRegBank::CodeGenRegBank().
167     static void computeSubClasses(ArrayRef<CodeGenRegisterClass*>);
168   };
169 
170   // CodeGenRegBank - Represent a target's registers and the relations between
171   // them.
172   class CodeGenRegBank {
173     RecordKeeper &Records;
174     SetTheory Sets;
175 
176     std::vector<Record*> SubRegIndices;
177     unsigned NumNamedIndices;
178     std::vector<CodeGenRegister*> Registers;
179     DenseMap<Record*, CodeGenRegister*> Def2Reg;
180 
181     std::vector<CodeGenRegisterClass*> RegClasses;
182     DenseMap<Record*, CodeGenRegisterClass*> Def2RC;
183 
184     // Composite SubRegIndex instances.
185     // Map (SubRegIndex, SubRegIndex) -> SubRegIndex.
186     typedef DenseMap<std::pair<Record*, Record*>, Record*> CompositeMap;
187     CompositeMap Composite;
188 
189     // Populate the Composite map from sub-register relationships.
190     void computeComposites();
191 
192   public:
193     CodeGenRegBank(RecordKeeper&);
194 
195     SetTheory &getSets() { return Sets; }
196 
197     // Sub-register indices. The first NumNamedIndices are defined by the user
198     // in the .td files. The rest are synthesized such that all sub-registers
199     // have a unique name.
200     const std::vector<Record*> &getSubRegIndices() { return SubRegIndices; }
201     unsigned getNumNamedIndices() { return NumNamedIndices; }
202 
203     // Map a SubRegIndex Record to its enum value.
204     unsigned getSubRegIndexNo(Record *idx);
205 
206     // Find or create a sub-register index representing the A+B composition.
207     Record *getCompositeSubRegIndex(Record *A, Record *B, bool create = false);
208 
209     const std::vector<CodeGenRegister*> &getRegisters() { return Registers; }
210 
211     // Find a register from its Record def.
212     CodeGenRegister *getReg(Record*);
213 
214     ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
215       return RegClasses;
216     }
217 
218     // Find a register class from its def.
219     CodeGenRegisterClass *getRegClass(Record*);
220 
221     /// getRegisterClassForRegister - Find the register class that contains the
222     /// specified physical register.  If the register is not in a register
223     /// class, return null. If the register is in multiple classes, and the
224     /// classes have a superset-subset relationship and the same set of types,
225     /// return the superclass.  Otherwise return null.
226     const CodeGenRegisterClass* getRegClassForRegister(Record *R);
227 
228     // Computed derived records such as missing sub-register indices.
229     void computeDerivedInfo();
230 
231     // Compute full overlap sets for every register. These sets include the
232     // rarely used aliases that are neither sub nor super-registers.
233     //
234     // Map[R1].count(R2) is reflexive and symmetric, but not transitive.
235     //
236     // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2].
237     void computeOverlaps(std::map<const CodeGenRegister*,
238                                   CodeGenRegister::Set> &Map);
239   };
240 }
241 
242 #endif
243