• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- CodeGenSchedule.h - Scheduling Machine Models ------------*- 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 the machine model as described in
11 // the target description.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_UTILS_TABLEGEN_CODEGENSCHEDULE_H
16 #define LLVM_UTILS_TABLEGEN_CODEGENSCHEDULE_H
17 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/TableGen/Record.h"
22 #include "llvm/TableGen/SetTheory.h"
23 
24 namespace llvm {
25 
26 class CodeGenTarget;
27 class CodeGenSchedModels;
28 class CodeGenInstruction;
29 
30 typedef std::vector<Record*> RecVec;
31 typedef std::vector<Record*>::const_iterator RecIter;
32 
33 typedef std::vector<unsigned> IdxVec;
34 typedef std::vector<unsigned>::const_iterator IdxIter;
35 
36 void splitSchedReadWrites(const RecVec &RWDefs,
37                           RecVec &WriteDefs, RecVec &ReadDefs);
38 
39 /// We have two kinds of SchedReadWrites. Explicitly defined and inferred
40 /// sequences.  TheDef is nonnull for explicit SchedWrites, but Sequence may or
41 /// may not be empty. TheDef is null for inferred sequences, and Sequence must
42 /// be nonempty.
43 ///
44 /// IsVariadic controls whether the variants are expanded into multiple operands
45 /// or a sequence of writes on one operand.
46 struct CodeGenSchedRW {
47   unsigned Index;
48   std::string Name;
49   Record *TheDef;
50   bool IsRead;
51   bool IsAlias;
52   bool HasVariants;
53   bool IsVariadic;
54   bool IsSequence;
55   IdxVec Sequence;
56   RecVec Aliases;
57 
CodeGenSchedRWCodeGenSchedRW58   CodeGenSchedRW()
59     : Index(0), TheDef(nullptr), IsRead(false), IsAlias(false),
60       HasVariants(false), IsVariadic(false), IsSequence(false) {}
CodeGenSchedRWCodeGenSchedRW61   CodeGenSchedRW(unsigned Idx, Record *Def)
62     : Index(Idx), TheDef(Def), IsAlias(false), IsVariadic(false) {
63     Name = Def->getName();
64     IsRead = Def->isSubClassOf("SchedRead");
65     HasVariants = Def->isSubClassOf("SchedVariant");
66     if (HasVariants)
67       IsVariadic = Def->getValueAsBit("Variadic");
68 
69     // Read records don't currently have sequences, but it can be easily
70     // added. Note that implicit Reads (from ReadVariant) may have a Sequence
71     // (but no record).
72     IsSequence = Def->isSubClassOf("WriteSequence");
73   }
74 
CodeGenSchedRWCodeGenSchedRW75   CodeGenSchedRW(unsigned Idx, bool Read, ArrayRef<unsigned> Seq,
76                  const std::string &Name)
77       : Index(Idx), Name(Name), TheDef(nullptr), IsRead(Read), IsAlias(false),
78         HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) {
79     assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
80   }
81 
isValidCodeGenSchedRW82   bool isValid() const {
83     assert((!HasVariants || TheDef) && "Variant write needs record def");
84     assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
85     assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
86     assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
87     assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases");
88     return TheDef || !Sequence.empty();
89   }
90 
91 #ifndef NDEBUG
92   void dump() const;
93 #endif
94 };
95 
96 /// Represent a transition between SchedClasses induced by SchedVariant.
97 struct CodeGenSchedTransition {
98   unsigned ToClassIdx;
99   IdxVec ProcIndices;
100   RecVec PredTerm;
101 };
102 
103 /// Scheduling class.
104 ///
105 /// Each instruction description will be mapped to a scheduling class. There are
106 /// four types of classes:
107 ///
108 /// 1) An explicitly defined itinerary class with ItinClassDef set.
109 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
110 ///
111 /// 2) An implied class with a list of SchedWrites and SchedReads that are
112 /// defined in an instruction definition and which are common across all
113 /// subtargets. ProcIndices contains 0 for any processor.
114 ///
115 /// 3) An implied class with a list of InstRW records that map instructions to
116 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
117 /// instructions to this class. ProcIndices contains all the processors that
118 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
119 /// still be defined for processors with no InstRW entry.
120 ///
121 /// 4) An inferred class represents a variant of another class that may be
122 /// resolved at runtime. ProcIndices contains the set of processors that may
123 /// require the class. ProcIndices are propagated through SchedClasses as
124 /// variants are expanded. Multiple SchedClasses may be inferred from an
125 /// itinerary class. Each inherits the processor index from the ItinRW record
126 /// that mapped the itinerary class to the variant Writes or Reads.
127 struct CodeGenSchedClass {
128   unsigned Index;
129   std::string Name;
130   Record *ItinClassDef;
131 
132   IdxVec Writes;
133   IdxVec Reads;
134   // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
135   IdxVec ProcIndices;
136 
137   std::vector<CodeGenSchedTransition> Transitions;
138 
139   // InstRW records associated with this class. These records may refer to an
140   // Instruction no longer mapped to this class by InstrClassMap. These
141   // Instructions should be ignored by this class because they have been split
142   // off to join another inferred class.
143   RecVec InstRWs;
144 
CodeGenSchedClassCodeGenSchedClass145   CodeGenSchedClass(): Index(0), ItinClassDef(nullptr) {}
146 
isKeyEqualCodeGenSchedClass147   bool isKeyEqual(Record *IC, ArrayRef<unsigned> W, ArrayRef<unsigned> R) {
148     return ItinClassDef == IC && makeArrayRef(Writes) == W &&
149            makeArrayRef(Reads) == R;
150   }
151 
152   // Is this class generated from a variants if existing classes? Instructions
153   // are never mapped directly to inferred scheduling classes.
isInferredCodeGenSchedClass154   bool isInferred() const { return !ItinClassDef; }
155 
156 #ifndef NDEBUG
157   void dump(const CodeGenSchedModels *SchedModels) const;
158 #endif
159 };
160 
161 // Processor model.
162 //
163 // ModelName is a unique name used to name an instantiation of MCSchedModel.
164 //
165 // ModelDef is NULL for inferred Models. This happens when a processor defines
166 // an itinerary but no machine model. If the processor defines neither a machine
167 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
168 // the special "NoModel" field set to true.
169 //
170 // ItinsDef always points to a valid record definition, but may point to the
171 // default NoItineraries. NoItineraries has an empty list of InstrItinData
172 // records.
173 //
174 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
175 struct CodeGenProcModel {
176   unsigned Index;
177   std::string ModelName;
178   Record *ModelDef;
179   Record *ItinsDef;
180 
181   // Derived members...
182 
183   // Array of InstrItinData records indexed by a CodeGenSchedClass index.
184   // This list is empty if the Processor has no value for Itineraries.
185   // Initialized by collectProcItins().
186   RecVec ItinDefList;
187 
188   // Map itinerary classes to per-operand resources.
189   // This list is empty if no ItinRW refers to this Processor.
190   RecVec ItinRWDefs;
191 
192   // List of unsupported feature.
193   // This list is empty if the Processor has no UnsupportedFeatures.
194   RecVec UnsupportedFeaturesDefs;
195 
196   // All read/write resources associated with this processor.
197   RecVec WriteResDefs;
198   RecVec ReadAdvanceDefs;
199 
200   // Per-operand machine model resources associated with this processor.
201   RecVec ProcResourceDefs;
202   RecVec ProcResGroupDefs;
203 
CodeGenProcModelCodeGenProcModel204   CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
205                    Record *IDef) :
206     Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
207 
hasItinerariesCodeGenProcModel208   bool hasItineraries() const {
209     return !ItinsDef->getValueAsListOfDefs("IID").empty();
210   }
211 
hasInstrSchedModelCodeGenProcModel212   bool hasInstrSchedModel() const {
213     return !WriteResDefs.empty() || !ItinRWDefs.empty();
214   }
215 
216   unsigned getProcResourceIdx(Record *PRDef) const;
217 
218   bool isUnsupported(const CodeGenInstruction &Inst) const;
219 
220 #ifndef NDEBUG
221   void dump() const;
222 #endif
223 };
224 
225 /// Top level container for machine model data.
226 class CodeGenSchedModels {
227   RecordKeeper &Records;
228   const CodeGenTarget &Target;
229 
230   // Map dag expressions to Instruction lists.
231   SetTheory Sets;
232 
233   // List of unique processor models.
234   std::vector<CodeGenProcModel> ProcModels;
235 
236   // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
237   typedef DenseMap<Record*, unsigned> ProcModelMapTy;
238   ProcModelMapTy ProcModelMap;
239 
240   // Per-operand SchedReadWrite types.
241   std::vector<CodeGenSchedRW> SchedWrites;
242   std::vector<CodeGenSchedRW> SchedReads;
243 
244   // List of unique SchedClasses.
245   std::vector<CodeGenSchedClass> SchedClasses;
246 
247   // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
248   unsigned NumInstrSchedClasses;
249 
250   RecVec ProcResourceDefs;
251   RecVec ProcResGroups;
252 
253   // Map each instruction to its unique SchedClass index considering the
254   // combination of it's itinerary class, SchedRW list, and InstRW records.
255   typedef DenseMap<Record*, unsigned> InstClassMapTy;
256   InstClassMapTy InstrClassMap;
257 
258 public:
259   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
260 
261   // iterator access to the scheduling classes.
262   typedef std::vector<CodeGenSchedClass>::iterator class_iterator;
263   typedef std::vector<CodeGenSchedClass>::const_iterator const_class_iterator;
classes_begin()264   class_iterator classes_begin() { return SchedClasses.begin(); }
classes_begin()265   const_class_iterator classes_begin() const { return SchedClasses.begin(); }
classes_end()266   class_iterator classes_end() { return SchedClasses.end(); }
classes_end()267   const_class_iterator classes_end() const { return SchedClasses.end(); }
classes()268   iterator_range<class_iterator> classes() {
269    return make_range(classes_begin(), classes_end());
270   }
classes()271   iterator_range<const_class_iterator> classes() const {
272    return make_range(classes_begin(), classes_end());
273   }
explicit_classes()274   iterator_range<class_iterator> explicit_classes() {
275     return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
276   }
explicit_classes()277   iterator_range<const_class_iterator> explicit_classes() const {
278     return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
279   }
280 
getModelOrItinDef(Record * ProcDef)281   Record *getModelOrItinDef(Record *ProcDef) const {
282     Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
283     Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
284     if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
285       assert(ModelDef->getValueAsBit("NoModel")
286              && "Itineraries must be defined within SchedMachineModel");
287       return ItinsDef;
288     }
289     return ModelDef;
290   }
291 
getModelForProc(Record * ProcDef)292   const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
293     Record *ModelDef = getModelOrItinDef(ProcDef);
294     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
295     assert(I != ProcModelMap.end() && "missing machine model");
296     return ProcModels[I->second];
297   }
298 
getProcModel(Record * ModelDef)299   CodeGenProcModel &getProcModel(Record *ModelDef) {
300     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
301     assert(I != ProcModelMap.end() && "missing machine model");
302     return ProcModels[I->second];
303   }
getProcModel(Record * ModelDef)304   const CodeGenProcModel &getProcModel(Record *ModelDef) const {
305     return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef);
306   }
307 
308   // Iterate over the unique processor models.
309   typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
procModelBegin()310   ProcIter procModelBegin() const { return ProcModels.begin(); }
procModelEnd()311   ProcIter procModelEnd() const { return ProcModels.end(); }
procModels()312   ArrayRef<CodeGenProcModel> procModels() const { return ProcModels; }
313 
314   // Return true if any processors have itineraries.
315   bool hasItineraries() const;
316 
317   // Get a SchedWrite from its index.
getSchedWrite(unsigned Idx)318   const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
319     assert(Idx < SchedWrites.size() && "bad SchedWrite index");
320     assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
321     return SchedWrites[Idx];
322   }
323   // Get a SchedWrite from its index.
getSchedRead(unsigned Idx)324   const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
325     assert(Idx < SchedReads.size() && "bad SchedRead index");
326     assert(SchedReads[Idx].isValid() && "invalid SchedRead");
327     return SchedReads[Idx];
328   }
329 
getSchedRW(unsigned Idx,bool IsRead)330   const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
331     return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
332   }
getSchedRW(Record * Def)333   CodeGenSchedRW &getSchedRW(Record *Def) {
334     bool IsRead = Def->isSubClassOf("SchedRead");
335     unsigned Idx = getSchedRWIdx(Def, IsRead);
336     return const_cast<CodeGenSchedRW&>(
337       IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
338   }
getSchedRW(Record * Def)339   const CodeGenSchedRW &getSchedRW(Record*Def) const {
340     return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
341   }
342 
343   unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
344 
345   // Return true if the given write record is referenced by a ReadAdvance.
346   bool hasReadOfWrite(Record *WriteDef) const;
347 
348   // Get a SchedClass from its index.
getSchedClass(unsigned Idx)349   CodeGenSchedClass &getSchedClass(unsigned Idx) {
350     assert(Idx < SchedClasses.size() && "bad SchedClass index");
351     return SchedClasses[Idx];
352   }
getSchedClass(unsigned Idx)353   const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
354     assert(Idx < SchedClasses.size() && "bad SchedClass index");
355     return SchedClasses[Idx];
356   }
357 
358   // Get the SchedClass index for an instruction. Instructions with no
359   // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
360   // for NoItinerary.
361   unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
362 
363   typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
schedClassBegin()364   SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
schedClassEnd()365   SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
schedClasses()366   ArrayRef<CodeGenSchedClass> schedClasses() const { return SchedClasses; }
367 
numInstrSchedClasses()368   unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
369 
370   void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
371   void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
372   void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
373   void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
374                           const CodeGenProcModel &ProcModel) const;
375 
376   unsigned addSchedClass(Record *ItinDef, ArrayRef<unsigned> OperWrites,
377                          ArrayRef<unsigned> OperReads,
378                          ArrayRef<unsigned> ProcIndices);
379 
380   unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
381 
382   unsigned findSchedClassIdx(Record *ItinClassDef, ArrayRef<unsigned> Writes,
383                              ArrayRef<unsigned> Reads) const;
384 
385   Record *findProcResUnits(Record *ProcResKind,
386                            const CodeGenProcModel &PM) const;
387 
388 private:
389   void collectProcModels();
390 
391   // Initialize a new processor model if it is unique.
392   void addProcModel(Record *ProcDef);
393 
394   void collectSchedRW();
395 
396   std::string genRWName(ArrayRef<unsigned> Seq, bool IsRead);
397   unsigned findRWForSequence(ArrayRef<unsigned> Seq, bool IsRead);
398 
399   void collectSchedClasses();
400 
401   std::string createSchedClassName(Record *ItinClassDef,
402                                    ArrayRef<unsigned> OperWrites,
403                                    ArrayRef<unsigned> OperReads);
404   std::string createSchedClassName(const RecVec &InstDefs);
405   void createInstRWClass(Record *InstRWDef);
406 
407   void collectProcItins();
408 
409   void collectProcItinRW();
410 
411   void collectProcUnsupportedFeatures();
412 
413   void inferSchedClasses();
414 
415   void checkCompleteness();
416 
417   void inferFromRW(ArrayRef<unsigned> OperWrites, ArrayRef<unsigned> OperReads,
418                    unsigned FromClassIdx, ArrayRef<unsigned> ProcIndices);
419   void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
420   void inferFromInstRWs(unsigned SCIdx);
421 
422   bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
423   void verifyProcResourceGroups(CodeGenProcModel &PM);
424 
425   void collectProcResources();
426 
427   void collectItinProcResources(Record *ItinClassDef);
428 
429   void collectRWResources(unsigned RWIdx, bool IsRead,
430                           ArrayRef<unsigned> ProcIndices);
431 
432   void collectRWResources(ArrayRef<unsigned> Writes, ArrayRef<unsigned> Reads,
433                           ArrayRef<unsigned> ProcIndices);
434 
435   void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM);
436 
437   void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
438 
439   void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);
440 };
441 
442 } // namespace llvm
443 
444 #endif
445