1 //===- CodeGenSchedule.h - Scheduling Machine Models ------------*- 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 the machine model as decribed in
11 // the target description.
13 //===----------------------------------------------------------------------===//
15 #ifndef CODEGEN_SCHEDULE_H
16 #define CODEGEN_SCHEDULE_H
18 #include "llvm/TableGen/Record.h"
19 #include "llvm/Support/ErrorHandling.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/StringMap.h"
26 class CodeGenSchedModels;
27 class CodeGenInstruction;
29 typedef std::vector<Record*> RecVec;
30 typedef std::vector<Record*>::const_iterator RecIter;
32 typedef std::vector<unsigned> IdxVec;
33 typedef std::vector<unsigned>::const_iterator IdxIter;
35 void splitSchedReadWrites(const RecVec &RWDefs,
36 RecVec &WriteDefs, RecVec &ReadDefs);
38 /// We have two kinds of SchedReadWrites. Explicitly defined and inferred
39 /// sequences. TheDef is nonnull for explicit SchedWrites, but Sequence may or
40 /// may not be empty. TheDef is null for inferred sequences, and Sequence must
43 /// IsVariadic controls whether the variants are expanded into multiple operands
44 /// or a sequence of writes on one operand.
45 struct CodeGenSchedRW {
53 CodeGenSchedRW(): TheDef(0), HasVariants(false), IsVariadic(false),
55 CodeGenSchedRW(Record *Def): TheDef(Def), IsVariadic(false) {
56 Name = Def->getName();
57 HasVariants = Def->isSubClassOf("SchedVariant");
59 IsVariadic = Def->getValueAsBit("Variadic");
61 // Read records don't currently have sequences, but it can be easily
62 // added. Note that implicit Reads (from ReadVariant) may have a Sequence
64 IsSequence = Def->isSubClassOf("WriteSequence");
67 CodeGenSchedRW(const IdxVec &Seq, const std::string &Name):
68 Name(Name), TheDef(0), HasVariants(false), IsVariadic(false),
69 IsSequence(true), Sequence(Seq) {
70 assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
73 bool isValid() const {
74 assert((!HasVariants || TheDef) && "Variant write needs record def");
75 assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
76 assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
77 assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
78 return TheDef || !Sequence.empty();
88 /// Each instruction description will be mapped to a scheduling class. There are
89 /// four types of classes:
91 /// 1) An explicitly defined itinerary class with ItinClassDef set.
92 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
94 /// 2) An implied class with a list of SchedWrites and SchedReads that are
95 /// defined in an instruction definition and which are common across all
96 /// subtargets. ProcIndices contains 0 for any processor.
98 /// 3) An implied class with a list of InstRW records that map instructions to
99 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
100 /// instructions to this class. ProcIndices contains all the processors that
101 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
102 /// still be defined for processors with no InstRW entry.
104 /// 4) An inferred class represents a variant of another class that may be
105 /// resolved at runtime. ProcIndices contains the set of processors that may
106 /// require the class. ProcIndices are propagated through SchedClasses as
107 /// variants are expanded. Multiple SchedClasses may be inferred from an
108 /// itinerary class. Each inherits the processor index from the ItinRW record
109 /// that mapped the itinerary class to the variant Writes or Reads.
110 struct CodeGenSchedClass {
112 Record *ItinClassDef;
116 // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
119 // InstReadWrite records associated with this class. Any Instrs that the
120 // definitions refer to that are not mapped to this class should be ignored.
123 CodeGenSchedClass(): ItinClassDef(0) {}
124 CodeGenSchedClass(Record *rec): ItinClassDef(rec) {
125 Name = rec->getName();
126 ProcIndices.push_back(0);
130 void dump(const CodeGenSchedModels *SchedModels) const;
136 // ModelName is a unique name used to name an instantiation of MCSchedModel.
138 // ModelDef is NULL for inferred Models. This happens when a processor defines
139 // an itinerary but no machine model. If the processer defines neither a machine
140 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
141 // the special "NoModel" field set to true.
143 // ItinsDef always points to a valid record definition, but may point to the
144 // default NoItineraries. NoItineraries has an empty list of InstrItinData
147 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
148 struct CodeGenProcModel {
150 std::string ModelName;
154 // Derived members...
156 // Array of InstrItinData records indexed by a CodeGenSchedClass index.
157 // This list is empty if the Processor has no value for Itineraries.
158 // Initialized by collectProcItins().
161 // Map itinerary classes to per-operand resources.
162 // This list is empty if no ItinRW refers to this Processor.
165 CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
167 Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
174 /// Top level container for machine model data.
175 class CodeGenSchedModels {
176 RecordKeeper &Records;
177 const CodeGenTarget &Target;
179 // List of unique processor models.
180 std::vector<CodeGenProcModel> ProcModels;
182 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
183 typedef DenseMap<Record*, unsigned> ProcModelMapTy;
184 ProcModelMapTy ProcModelMap;
186 // Per-operand SchedReadWrite types.
187 std::vector<CodeGenSchedRW> SchedWrites;
188 std::vector<CodeGenSchedRW> SchedReads;
190 // List of unique SchedClasses.
191 std::vector<CodeGenSchedClass> SchedClasses;
193 // Map SchedClass name to itinerary index.
194 // These are either explicit itinerary classes or classes implied by
195 // instruction definitions with SchedReadWrite lists.
196 StringMap<unsigned> SchedClassIdxMap;
198 // SchedClass indices 1 up to and including NumItineraryClasses identify
199 // itinerary classes that are explicitly used for this target's instruction
200 // definitions. NoItinerary always has index 0 regardless of whether it is
201 // explicitly referenced.
203 // Any implied SchedClass has an index greater than NumItineraryClasses.
204 unsigned NumItineraryClasses;
206 // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
207 unsigned NumInstrSchedClasses;
209 // Map Instruction to SchedClass index. Only for Instructions mentioned in
211 typedef DenseMap<Record*, unsigned> InstClassMapTy;
212 InstClassMapTy InstrClassMap;
215 CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
217 Record *getModelOrItinDef(Record *ProcDef) const {
218 Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
219 Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
220 if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
221 assert(ModelDef->getValueAsBit("NoModel")
222 && "Itineraries must be defined within SchedMachineModel");
228 const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
229 Record *ModelDef = getModelOrItinDef(ProcDef);
230 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
231 assert(I != ProcModelMap.end() && "missing machine model");
232 return ProcModels[I->second];
235 const CodeGenProcModel &getProcModel(Record *ModelDef) const {
236 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
237 assert(I != ProcModelMap.end() && "missing machine model");
238 return ProcModels[I->second];
241 // Iterate over the unique processor models.
242 typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
243 ProcIter procModelBegin() const { return ProcModels.begin(); }
244 ProcIter procModelEnd() const { return ProcModels.end(); }
246 // Get a SchedWrite from its index.
247 const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
248 assert(Idx < SchedWrites.size() && "bad SchedWrite index");
249 assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
250 return SchedWrites[Idx];
252 // Get a SchedWrite from its index.
253 const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
254 assert(Idx < SchedReads.size() && "bad SchedRead index");
255 assert(SchedReads[Idx].isValid() && "invalid SchedRead");
256 return SchedReads[Idx];
259 const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
260 return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
263 unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
265 // Check if any instructions are assigned to an explicit itinerary class other
267 bool hasItineraryClasses() const { return NumItineraryClasses > 0; }
269 // Return the number of itinerary classes in use by this target's instruction
270 // descriptions, not including "NoItinerary".
271 unsigned numItineraryClasses() const {
272 return NumItineraryClasses;
275 // Get a SchedClass from its index.
276 CodeGenSchedClass &getSchedClass(unsigned Idx) {
277 assert(Idx < SchedClasses.size() && "bad SchedClass index");
278 return SchedClasses[Idx];
280 const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
281 assert(Idx < SchedClasses.size() && "bad SchedClass index");
282 return SchedClasses[Idx];
285 // Get an itinerary class's index. Value indices are '0' for NoItinerary up to
286 // and including numItineraryClasses().
287 unsigned getItinClassIdx(Record *ItinDef) const {
288 assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass");
289 unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName());
290 assert(Idx <= NumItineraryClasses && "bad ItinClass index");
294 // Get the SchedClass index for an instruction. Instructions with no
295 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
297 unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
299 unsigned getSchedClassIdx(const RecVec &RWDefs) const;
301 unsigned getSchedClassIdxForItin(const Record *ItinDef) {
302 return SchedClassIdxMap[ItinDef->getName()];
305 typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
306 SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
307 SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
309 void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
310 void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
312 unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads,
313 const IdxVec &ProcIndices);
315 unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
317 unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const;
320 void collectProcModels();
322 // Initialize a new processor model if it is unique.
323 void addProcModel(Record *ProcDef);
325 void collectSchedRW();
327 std::string genRWName(const IdxVec& Seq, bool IsRead);
328 unsigned findRWForSequence(const IdxVec &Seq, bool IsRead);
330 void collectSchedClasses();
332 std::string createSchedClassName(const IdxVec &OperWrites,
333 const IdxVec &OperReads);
334 std::string createSchedClassName(const RecVec &InstDefs);
335 void createInstRWClass(Record *InstRWDef);
337 void collectProcItins();
339 void collectProcItinRW();