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 described in
11 // the target description.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_UTILS_TABLEGEN_CODEGENSCHEDULE_H
16 #define LLVM_UTILS_TABLEGEN_CODEGENSCHEDULE_H
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"
27 class CodeGenSchedModels;
28 class CodeGenInstruction;
30 typedef std::vector<Record*> RecVec;
31 typedef std::vector<Record*>::const_iterator RecIter;
33 typedef std::vector<unsigned> IdxVec;
34 typedef std::vector<unsigned>::const_iterator IdxIter;
36 void splitSchedReadWrites(const RecVec &RWDefs,
37 RecVec &WriteDefs, RecVec &ReadDefs);
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
44 /// IsVariadic controls whether the variants are expanded into multiple operands
45 /// or a sequence of writes on one operand.
46 struct CodeGenSchedRW {
59 : Index(0), TheDef(nullptr), IsRead(false), IsAlias(false),
60 HasVariants(false), IsVariadic(false), IsSequence(false) {}
61 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");
67 IsVariadic = Def->getValueAsBit("Variadic");
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
72 IsSequence = Def->isSubClassOf("WriteSequence");
75 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");
82 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();
96 /// Represent a transition between SchedClasses induced by SchedVariant.
97 struct CodeGenSchedTransition {
103 /// Scheduling class.
105 /// Each instruction description will be mapped to a scheduling class. There are
106 /// four types of classes:
108 /// 1) An explicitly defined itinerary class with ItinClassDef set.
109 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
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.
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.
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 {
130 Record *ItinClassDef;
134 // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
137 std::vector<CodeGenSchedTransition> Transitions;
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.
145 CodeGenSchedClass(): Index(0), ItinClassDef(nullptr) {}
147 bool isKeyEqual(Record *IC, ArrayRef<unsigned> W, ArrayRef<unsigned> R) {
148 return ItinClassDef == IC && makeArrayRef(Writes) == W &&
149 makeArrayRef(Reads) == R;
152 // Is this class generated from a variants if existing classes? Instructions
153 // are never mapped directly to inferred scheduling classes.
154 bool isInferred() const { return !ItinClassDef; }
157 void dump(const CodeGenSchedModels *SchedModels) const;
163 // ModelName is a unique name used to name an instantiation of MCSchedModel.
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.
170 // ItinsDef always points to a valid record definition, but may point to the
171 // default NoItineraries. NoItineraries has an empty list of InstrItinData
174 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
175 struct CodeGenProcModel {
177 std::string ModelName;
181 // Derived members...
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().
188 // Map itinerary classes to per-operand resources.
189 // This list is empty if no ItinRW refers to this Processor.
192 // List of unsupported feature.
193 // This list is empty if the Processor has no UnsupportedFeatures.
194 RecVec UnsupportedFeaturesDefs;
196 // All read/write resources associated with this processor.
198 RecVec ReadAdvanceDefs;
200 // Per-operand machine model resources associated with this processor.
201 RecVec ProcResourceDefs;
202 RecVec ProcResGroupDefs;
204 CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
206 Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
208 bool hasItineraries() const {
209 return !ItinsDef->getValueAsListOfDefs("IID").empty();
212 bool hasInstrSchedModel() const {
213 return !WriteResDefs.empty() || !ItinRWDefs.empty();
216 unsigned getProcResourceIdx(Record *PRDef) const;
218 bool isUnsupported(const CodeGenInstruction &Inst) const;
225 /// Top level container for machine model data.
226 class CodeGenSchedModels {
227 RecordKeeper &Records;
228 const CodeGenTarget &Target;
230 // Map dag expressions to Instruction lists.
233 // List of unique processor models.
234 std::vector<CodeGenProcModel> ProcModels;
236 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
237 typedef DenseMap<Record*, unsigned> ProcModelMapTy;
238 ProcModelMapTy ProcModelMap;
240 // Per-operand SchedReadWrite types.
241 std::vector<CodeGenSchedRW> SchedWrites;
242 std::vector<CodeGenSchedRW> SchedReads;
244 // List of unique SchedClasses.
245 std::vector<CodeGenSchedClass> SchedClasses;
247 // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
248 unsigned NumInstrSchedClasses;
250 RecVec ProcResourceDefs;
251 RecVec ProcResGroups;
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;
259 CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
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;
264 class_iterator classes_begin() { return SchedClasses.begin(); }
265 const_class_iterator classes_begin() const { return SchedClasses.begin(); }
266 class_iterator classes_end() { return SchedClasses.end(); }
267 const_class_iterator classes_end() const { return SchedClasses.end(); }
268 iterator_range<class_iterator> classes() {
269 return make_range(classes_begin(), classes_end());
271 iterator_range<const_class_iterator> classes() const {
272 return make_range(classes_begin(), classes_end());
274 iterator_range<class_iterator> explicit_classes() {
275 return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
277 iterator_range<const_class_iterator> explicit_classes() const {
278 return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
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");
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];
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];
304 const CodeGenProcModel &getProcModel(Record *ModelDef) const {
305 return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef);
308 // Iterate over the unique processor models.
309 typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
310 ProcIter procModelBegin() const { return ProcModels.begin(); }
311 ProcIter procModelEnd() const { return ProcModels.end(); }
312 ArrayRef<CodeGenProcModel> procModels() const { return ProcModels; }
314 // Return true if any processors have itineraries.
315 bool hasItineraries() const;
317 // Get a SchedWrite from its index.
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];
323 // Get a SchedWrite from its index.
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];
330 const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
331 return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
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));
339 const CodeGenSchedRW &getSchedRW(Record*Def) const {
340 return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
343 unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
345 // Return true if the given write record is referenced by a ReadAdvance.
346 bool hasReadOfWrite(Record *WriteDef) const;
348 // Get a SchedClass from its index.
349 CodeGenSchedClass &getSchedClass(unsigned Idx) {
350 assert(Idx < SchedClasses.size() && "bad SchedClass index");
351 return SchedClasses[Idx];
353 const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
354 assert(Idx < SchedClasses.size() && "bad SchedClass index");
355 return SchedClasses[Idx];
358 // Get the SchedClass index for an instruction. Instructions with no
359 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
361 unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
363 typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
364 SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
365 SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
366 ArrayRef<CodeGenSchedClass> schedClasses() const { return SchedClasses; }
368 unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
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;
376 unsigned addSchedClass(Record *ItinDef, ArrayRef<unsigned> OperWrites,
377 ArrayRef<unsigned> OperReads,
378 ArrayRef<unsigned> ProcIndices);
380 unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
382 unsigned findSchedClassIdx(Record *ItinClassDef, ArrayRef<unsigned> Writes,
383 ArrayRef<unsigned> Reads) const;
385 Record *findProcResUnits(Record *ProcResKind,
386 const CodeGenProcModel &PM) const;
389 void collectProcModels();
391 // Initialize a new processor model if it is unique.
392 void addProcModel(Record *ProcDef);
394 void collectSchedRW();
396 std::string genRWName(ArrayRef<unsigned> Seq, bool IsRead);
397 unsigned findRWForSequence(ArrayRef<unsigned> Seq, bool IsRead);
399 void collectSchedClasses();
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);
407 void collectProcItins();
409 void collectProcItinRW();
411 void collectProcUnsupportedFeatures();
413 void inferSchedClasses();
415 void checkCompleteness();
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);
422 bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
423 void verifyProcResourceGroups(CodeGenProcModel &PM);
425 void collectProcResources();
427 void collectItinProcResources(Record *ItinClassDef);
429 void collectRWResources(unsigned RWIdx, bool IsRead,
430 ArrayRef<unsigned> ProcIndices);
432 void collectRWResources(ArrayRef<unsigned> Writes, ArrayRef<unsigned> Reads,
433 ArrayRef<unsigned> ProcIndices);
435 void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM);
437 void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
439 void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);