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;
29 class CodeGenRegisterClass;
31 using RecVec = std::vector<Record*>;
32 using RecIter = std::vector<Record*>::const_iterator;
34 using IdxVec = std::vector<unsigned>;
35 using IdxIter = std::vector<unsigned>::const_iterator;
37 /// We have two kinds of SchedReadWrites. Explicitly defined and inferred
38 /// sequences. TheDef is nonnull for explicit SchedWrites, but Sequence may or
39 /// may not be empty. TheDef is null for inferred sequences, and Sequence must
42 /// IsVariadic controls whether the variants are expanded into multiple operands
43 /// or a sequence of writes on one operand.
44 struct CodeGenSchedRW {
57 : Index(0), TheDef(nullptr), IsRead(false), IsAlias(false),
58 HasVariants(false), IsVariadic(false), IsSequence(false) {}
59 CodeGenSchedRW(unsigned Idx, Record *Def)
60 : Index(Idx), TheDef(Def), IsAlias(false), IsVariadic(false) {
61 Name = Def->getName();
62 IsRead = Def->isSubClassOf("SchedRead");
63 HasVariants = Def->isSubClassOf("SchedVariant");
65 IsVariadic = Def->getValueAsBit("Variadic");
67 // Read records don't currently have sequences, but it can be easily
68 // added. Note that implicit Reads (from ReadVariant) may have a Sequence
70 IsSequence = Def->isSubClassOf("WriteSequence");
73 CodeGenSchedRW(unsigned Idx, bool Read, ArrayRef<unsigned> Seq,
74 const std::string &Name)
75 : Index(Idx), Name(Name), TheDef(nullptr), IsRead(Read), IsAlias(false),
76 HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) {
77 assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
80 bool isValid() const {
81 assert((!HasVariants || TheDef) && "Variant write needs record def");
82 assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
83 assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
84 assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
85 assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases");
86 return TheDef || !Sequence.empty();
94 /// Represent a transition between SchedClasses induced by SchedVariant.
95 struct CodeGenSchedTransition {
101 /// Scheduling class.
103 /// Each instruction description will be mapped to a scheduling class. There are
104 /// four types of classes:
106 /// 1) An explicitly defined itinerary class with ItinClassDef set.
107 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
109 /// 2) An implied class with a list of SchedWrites and SchedReads that are
110 /// defined in an instruction definition and which are common across all
111 /// subtargets. ProcIndices contains 0 for any processor.
113 /// 3) An implied class with a list of InstRW records that map instructions to
114 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
115 /// instructions to this class. ProcIndices contains all the processors that
116 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
117 /// still be defined for processors with no InstRW entry.
119 /// 4) An inferred class represents a variant of another class that may be
120 /// resolved at runtime. ProcIndices contains the set of processors that may
121 /// require the class. ProcIndices are propagated through SchedClasses as
122 /// variants are expanded. Multiple SchedClasses may be inferred from an
123 /// itinerary class. Each inherits the processor index from the ItinRW record
124 /// that mapped the itinerary class to the variant Writes or Reads.
125 struct CodeGenSchedClass {
128 Record *ItinClassDef;
132 // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
135 std::vector<CodeGenSchedTransition> Transitions;
137 // InstRW records associated with this class. These records may refer to an
138 // Instruction no longer mapped to this class by InstrClassMap. These
139 // Instructions should be ignored by this class because they have been split
140 // off to join another inferred class.
143 CodeGenSchedClass(unsigned Index, std::string Name, Record *ItinClassDef)
144 : Index(Index), Name(std::move(Name)), ItinClassDef(ItinClassDef) {}
146 bool isKeyEqual(Record *IC, ArrayRef<unsigned> W,
147 ArrayRef<unsigned> R) const {
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;
161 /// Represent the cost of allocating a register of register class RCDef.
163 /// The cost of allocating a register is equivalent to the number of physical
164 /// registers used by the register renamer. Register costs are defined at
165 /// register class granularity.
166 struct CodeGenRegisterCost {
169 CodeGenRegisterCost(Record *RC, unsigned RegisterCost)
170 : RCDef(RC), Cost(RegisterCost) {}
171 CodeGenRegisterCost(const CodeGenRegisterCost &) = default;
172 CodeGenRegisterCost &operator=(const CodeGenRegisterCost &) = delete;
175 /// A processor register file.
177 /// This class describes a processor register file. Register file information is
178 /// currently consumed by external tools like llvm-mca to predict dispatch
179 /// stalls due to register pressure.
180 struct CodeGenRegisterFile {
182 Record *RegisterFileDef;
184 unsigned NumPhysRegs;
185 std::vector<CodeGenRegisterCost> Costs;
187 CodeGenRegisterFile(StringRef name, Record *def)
188 : Name(name), RegisterFileDef(def), NumPhysRegs(0) {}
190 bool hasDefaultCosts() const { return Costs.empty(); }
195 // ModelName is a unique name used to name an instantiation of MCSchedModel.
197 // ModelDef is NULL for inferred Models. This happens when a processor defines
198 // an itinerary but no machine model. If the processor defines neither a machine
199 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
200 // the special "NoModel" field set to true.
202 // ItinsDef always points to a valid record definition, but may point to the
203 // default NoItineraries. NoItineraries has an empty list of InstrItinData
206 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
207 struct CodeGenProcModel {
209 std::string ModelName;
213 // Derived members...
215 // Array of InstrItinData records indexed by a CodeGenSchedClass index.
216 // This list is empty if the Processor has no value for Itineraries.
217 // Initialized by collectProcItins().
220 // Map itinerary classes to per-operand resources.
221 // This list is empty if no ItinRW refers to this Processor.
224 // List of unsupported feature.
225 // This list is empty if the Processor has no UnsupportedFeatures.
226 RecVec UnsupportedFeaturesDefs;
228 // All read/write resources associated with this processor.
230 RecVec ReadAdvanceDefs;
232 // Per-operand machine model resources associated with this processor.
233 RecVec ProcResourceDefs;
235 // List of Register Files.
236 std::vector<CodeGenRegisterFile> RegisterFiles;
238 // Optional Retire Control Unit definition.
239 Record *RetireControlUnit;
241 // List of PfmCounters.
242 RecVec PfmIssueCounterDefs;
243 Record *PfmCycleCounterDef = nullptr;
245 CodeGenProcModel(unsigned Idx, std::string Name, Record *MDef,
247 Index(Idx), ModelName(std::move(Name)), ModelDef(MDef), ItinsDef(IDef),
248 RetireControlUnit(nullptr) {}
250 bool hasItineraries() const {
251 return !ItinsDef->getValueAsListOfDefs("IID").empty();
254 bool hasInstrSchedModel() const {
255 return !WriteResDefs.empty() || !ItinRWDefs.empty();
258 bool hasExtraProcessorInfo() const {
259 return RetireControlUnit || !RegisterFiles.empty() ||
260 !PfmIssueCounterDefs.empty() ||
261 PfmCycleCounterDef != nullptr;
264 unsigned getProcResourceIdx(Record *PRDef) const;
266 bool isUnsupported(const CodeGenInstruction &Inst) const;
273 /// Top level container for machine model data.
274 class CodeGenSchedModels {
275 RecordKeeper &Records;
276 const CodeGenTarget &Target;
278 // Map dag expressions to Instruction lists.
281 // List of unique processor models.
282 std::vector<CodeGenProcModel> ProcModels;
284 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
285 using ProcModelMapTy = DenseMap<Record*, unsigned>;
286 ProcModelMapTy ProcModelMap;
288 // Per-operand SchedReadWrite types.
289 std::vector<CodeGenSchedRW> SchedWrites;
290 std::vector<CodeGenSchedRW> SchedReads;
292 // List of unique SchedClasses.
293 std::vector<CodeGenSchedClass> SchedClasses;
295 // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
296 unsigned NumInstrSchedClasses;
298 RecVec ProcResourceDefs;
299 RecVec ProcResGroups;
301 // Map each instruction to its unique SchedClass index considering the
302 // combination of it's itinerary class, SchedRW list, and InstRW records.
303 using InstClassMapTy = DenseMap<Record*, unsigned>;
304 InstClassMapTy InstrClassMap;
307 CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
309 // iterator access to the scheduling classes.
310 using class_iterator = std::vector<CodeGenSchedClass>::iterator;
311 using const_class_iterator = std::vector<CodeGenSchedClass>::const_iterator;
312 class_iterator classes_begin() { return SchedClasses.begin(); }
313 const_class_iterator classes_begin() const { return SchedClasses.begin(); }
314 class_iterator classes_end() { return SchedClasses.end(); }
315 const_class_iterator classes_end() const { return SchedClasses.end(); }
316 iterator_range<class_iterator> classes() {
317 return make_range(classes_begin(), classes_end());
319 iterator_range<const_class_iterator> classes() const {
320 return make_range(classes_begin(), classes_end());
322 iterator_range<class_iterator> explicit_classes() {
323 return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
325 iterator_range<const_class_iterator> explicit_classes() const {
326 return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
329 Record *getModelOrItinDef(Record *ProcDef) const {
330 Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
331 Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
332 if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
333 assert(ModelDef->getValueAsBit("NoModel")
334 && "Itineraries must be defined within SchedMachineModel");
340 const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
341 Record *ModelDef = getModelOrItinDef(ProcDef);
342 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
343 assert(I != ProcModelMap.end() && "missing machine model");
344 return ProcModels[I->second];
347 CodeGenProcModel &getProcModel(Record *ModelDef) {
348 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
349 assert(I != ProcModelMap.end() && "missing machine model");
350 return ProcModels[I->second];
352 const CodeGenProcModel &getProcModel(Record *ModelDef) const {
353 return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef);
356 // Iterate over the unique processor models.
357 using ProcIter = std::vector<CodeGenProcModel>::const_iterator;
358 ProcIter procModelBegin() const { return ProcModels.begin(); }
359 ProcIter procModelEnd() const { return ProcModels.end(); }
360 ArrayRef<CodeGenProcModel> procModels() const { return ProcModels; }
362 // Return true if any processors have itineraries.
363 bool hasItineraries() const;
365 // Get a SchedWrite from its index.
366 const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
367 assert(Idx < SchedWrites.size() && "bad SchedWrite index");
368 assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
369 return SchedWrites[Idx];
371 // Get a SchedWrite from its index.
372 const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
373 assert(Idx < SchedReads.size() && "bad SchedRead index");
374 assert(SchedReads[Idx].isValid() && "invalid SchedRead");
375 return SchedReads[Idx];
378 const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
379 return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
381 CodeGenSchedRW &getSchedRW(Record *Def) {
382 bool IsRead = Def->isSubClassOf("SchedRead");
383 unsigned Idx = getSchedRWIdx(Def, IsRead);
384 return const_cast<CodeGenSchedRW&>(
385 IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
387 const CodeGenSchedRW &getSchedRW(Record *Def) const {
388 return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
391 unsigned getSchedRWIdx(const Record *Def, bool IsRead) const;
393 // Return true if the given write record is referenced by a ReadAdvance.
394 bool hasReadOfWrite(Record *WriteDef) const;
396 // Get a SchedClass from its index.
397 CodeGenSchedClass &getSchedClass(unsigned Idx) {
398 assert(Idx < SchedClasses.size() && "bad SchedClass index");
399 return SchedClasses[Idx];
401 const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
402 assert(Idx < SchedClasses.size() && "bad SchedClass index");
403 return SchedClasses[Idx];
406 // Get the SchedClass index for an instruction. Instructions with no
407 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
409 unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
411 using SchedClassIter = std::vector<CodeGenSchedClass>::const_iterator;
412 SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
413 SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
414 ArrayRef<CodeGenSchedClass> schedClasses() const { return SchedClasses; }
416 unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
418 void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
419 void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
420 void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
421 void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
422 const CodeGenProcModel &ProcModel) const;
424 unsigned addSchedClass(Record *ItinDef, ArrayRef<unsigned> OperWrites,
425 ArrayRef<unsigned> OperReads,
426 ArrayRef<unsigned> ProcIndices);
428 unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
430 Record *findProcResUnits(Record *ProcResKind, const CodeGenProcModel &PM,
431 ArrayRef<SMLoc> Loc) const;
434 void collectProcModels();
436 // Initialize a new processor model if it is unique.
437 void addProcModel(Record *ProcDef);
439 void collectSchedRW();
441 std::string genRWName(ArrayRef<unsigned> Seq, bool IsRead);
442 unsigned findRWForSequence(ArrayRef<unsigned> Seq, bool IsRead);
444 void collectSchedClasses();
446 void collectRetireControlUnits();
448 void collectRegisterFiles();
450 void collectPfmCounters();
452 void collectOptionalProcessorInfo();
454 std::string createSchedClassName(Record *ItinClassDef,
455 ArrayRef<unsigned> OperWrites,
456 ArrayRef<unsigned> OperReads);
457 std::string createSchedClassName(const RecVec &InstDefs);
458 void createInstRWClass(Record *InstRWDef);
460 void collectProcItins();
462 void collectProcItinRW();
464 void collectProcUnsupportedFeatures();
466 void inferSchedClasses();
468 void checkCompleteness();
470 void inferFromRW(ArrayRef<unsigned> OperWrites, ArrayRef<unsigned> OperReads,
471 unsigned FromClassIdx, ArrayRef<unsigned> ProcIndices);
472 void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
473 void inferFromInstRWs(unsigned SCIdx);
475 bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
476 void verifyProcResourceGroups(CodeGenProcModel &PM);
478 void collectProcResources();
480 void collectItinProcResources(Record *ItinClassDef);
482 void collectRWResources(unsigned RWIdx, bool IsRead,
483 ArrayRef<unsigned> ProcIndices);
485 void collectRWResources(ArrayRef<unsigned> Writes, ArrayRef<unsigned> Reads,
486 ArrayRef<unsigned> ProcIndices);
488 void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM,
489 ArrayRef<SMLoc> Loc);
491 void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
493 void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);