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 "SetTheory.h"
19 #include "llvm/TableGen/Record.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/StringMap.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 {
58 CodeGenSchedRW(): Index(0), TheDef(0), IsAlias(false), HasVariants(false),
59 IsVariadic(false), IsSequence(false) {}
60 CodeGenSchedRW(unsigned Idx, Record *Def): Index(Idx), TheDef(Def),
61 IsAlias(false), IsVariadic(false) {
62 Name = Def->getName();
63 IsRead = Def->isSubClassOf("SchedRead");
64 HasVariants = Def->isSubClassOf("SchedVariant");
66 IsVariadic = Def->getValueAsBit("Variadic");
68 // Read records don't currently have sequences, but it can be easily
69 // added. Note that implicit Reads (from ReadVariant) may have a Sequence
71 IsSequence = Def->isSubClassOf("WriteSequence");
74 CodeGenSchedRW(unsigned Idx, bool Read, const IdxVec &Seq,
75 const std::string &Name):
76 Index(Idx), Name(Name), TheDef(0), IsRead(Read), IsAlias(false),
77 HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) {
78 assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
81 bool isValid() const {
82 assert((!HasVariants || TheDef) && "Variant write needs record def");
83 assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
84 assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
85 assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
86 assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases");
87 return TheDef || !Sequence.empty();
95 /// Represent a transition between SchedClasses induced by SchedVariant.
96 struct CodeGenSchedTransition {
102 /// Scheduling class.
104 /// Each instruction description will be mapped to a scheduling class. There are
105 /// four types of classes:
107 /// 1) An explicitly defined itinerary class with ItinClassDef set.
108 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
110 /// 2) An implied class with a list of SchedWrites and SchedReads that are
111 /// defined in an instruction definition and which are common across all
112 /// subtargets. ProcIndices contains 0 for any processor.
114 /// 3) An implied class with a list of InstRW records that map instructions to
115 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
116 /// instructions to this class. ProcIndices contains all the processors that
117 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
118 /// still be defined for processors with no InstRW entry.
120 /// 4) An inferred class represents a variant of another class that may be
121 /// resolved at runtime. ProcIndices contains the set of processors that may
122 /// require the class. ProcIndices are propagated through SchedClasses as
123 /// variants are expanded. Multiple SchedClasses may be inferred from an
124 /// itinerary class. Each inherits the processor index from the ItinRW record
125 /// that mapped the itinerary class to the variant Writes or Reads.
126 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(): ItinClassDef(0) {}
144 CodeGenSchedClass(Record *rec): ItinClassDef(rec) {
145 Name = rec->getName();
146 ProcIndices.push_back(0);
150 void dump(const CodeGenSchedModels *SchedModels) const;
156 // ModelName is a unique name used to name an instantiation of MCSchedModel.
158 // ModelDef is NULL for inferred Models. This happens when a processor defines
159 // an itinerary but no machine model. If the processer defines neither a machine
160 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
161 // the special "NoModel" field set to true.
163 // ItinsDef always points to a valid record definition, but may point to the
164 // default NoItineraries. NoItineraries has an empty list of InstrItinData
167 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
168 struct CodeGenProcModel {
170 std::string ModelName;
174 // Derived members...
176 // Array of InstrItinData records indexed by a CodeGenSchedClass index.
177 // This list is empty if the Processor has no value for Itineraries.
178 // Initialized by collectProcItins().
181 // Map itinerary classes to per-operand resources.
182 // This list is empty if no ItinRW refers to this Processor.
185 // All read/write resources associated with this processor.
187 RecVec ReadAdvanceDefs;
189 // Per-operand machine model resources associated with this processor.
190 RecVec ProcResourceDefs;
192 CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
194 Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
196 bool hasInstrSchedModel() const {
197 return !WriteResDefs.empty() || !ItinRWDefs.empty();
200 unsigned getProcResourceIdx(Record *PRDef) const;
207 /// Top level container for machine model data.
208 class CodeGenSchedModels {
209 RecordKeeper &Records;
210 const CodeGenTarget &Target;
212 // Map dag expressions to Instruction lists.
215 // List of unique processor models.
216 std::vector<CodeGenProcModel> ProcModels;
218 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
219 typedef DenseMap<Record*, unsigned> ProcModelMapTy;
220 ProcModelMapTy ProcModelMap;
222 // Per-operand SchedReadWrite types.
223 std::vector<CodeGenSchedRW> SchedWrites;
224 std::vector<CodeGenSchedRW> SchedReads;
226 // List of unique SchedClasses.
227 std::vector<CodeGenSchedClass> SchedClasses;
229 // Map SchedClass name to itinerary index.
230 // These are either explicit itinerary classes or classes implied by
231 // instruction definitions with SchedReadWrite lists.
232 StringMap<unsigned> SchedClassIdxMap;
234 // SchedClass indices 1 up to and including NumItineraryClasses identify
235 // itinerary classes that are explicitly used for this target's instruction
236 // definitions. NoItinerary always has index 0 regardless of whether it is
237 // explicitly referenced.
239 // Any implied SchedClass has an index greater than NumItineraryClasses.
240 unsigned NumItineraryClasses;
242 // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
243 unsigned NumInstrSchedClasses;
245 // Map Instruction to SchedClass index. Only for Instructions mentioned in
247 typedef DenseMap<Record*, unsigned> InstClassMapTy;
248 InstClassMapTy InstrClassMap;
251 CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
253 Record *getModelOrItinDef(Record *ProcDef) const {
254 Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
255 Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
256 if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
257 assert(ModelDef->getValueAsBit("NoModel")
258 && "Itineraries must be defined within SchedMachineModel");
264 const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
265 Record *ModelDef = getModelOrItinDef(ProcDef);
266 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
267 assert(I != ProcModelMap.end() && "missing machine model");
268 return ProcModels[I->second];
271 const CodeGenProcModel &getProcModel(Record *ModelDef) const {
272 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
273 assert(I != ProcModelMap.end() && "missing machine model");
274 return ProcModels[I->second];
277 // Iterate over the unique processor models.
278 typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
279 ProcIter procModelBegin() const { return ProcModels.begin(); }
280 ProcIter procModelEnd() const { return ProcModels.end(); }
282 // Get a SchedWrite from its index.
283 const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
284 assert(Idx < SchedWrites.size() && "bad SchedWrite index");
285 assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
286 return SchedWrites[Idx];
288 // Get a SchedWrite from its index.
289 const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
290 assert(Idx < SchedReads.size() && "bad SchedRead index");
291 assert(SchedReads[Idx].isValid() && "invalid SchedRead");
292 return SchedReads[Idx];
295 const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
296 return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
298 CodeGenSchedRW &getSchedRW(Record *Def) {
299 bool IsRead = Def->isSubClassOf("SchedRead");
300 unsigned Idx = getSchedRWIdx(Def, IsRead);
301 return const_cast<CodeGenSchedRW&>(
302 IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
304 const CodeGenSchedRW &getSchedRW(Record*Def) const {
305 return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
308 unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
310 // Return true if the given write record is referenced by a ReadAdvance.
311 bool hasReadOfWrite(Record *WriteDef) const;
313 // Check if any instructions are assigned to an explicit itinerary class other
315 bool hasItineraryClasses() const { return NumItineraryClasses > 0; }
317 // Return the number of itinerary classes in use by this target's instruction
318 // descriptions, not including "NoItinerary".
319 unsigned numItineraryClasses() const {
320 return NumItineraryClasses;
323 // Get a SchedClass from its index.
324 CodeGenSchedClass &getSchedClass(unsigned Idx) {
325 assert(Idx < SchedClasses.size() && "bad SchedClass index");
326 return SchedClasses[Idx];
328 const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
329 assert(Idx < SchedClasses.size() && "bad SchedClass index");
330 return SchedClasses[Idx];
333 // Get the SchedClass index for an instruction. Instructions with no
334 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
336 unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
338 unsigned getSchedClassIdx(const RecVec &RWDefs) const;
340 unsigned getSchedClassIdxForItin(const Record *ItinDef) {
341 return SchedClassIdxMap[ItinDef->getName()];
344 typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
345 SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
346 SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
348 void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
349 void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
350 void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
351 void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
352 const CodeGenProcModel &ProcModel) const;
354 unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads,
355 const IdxVec &ProcIndices);
357 unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
359 unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const;
361 Record *findProcResUnits(Record *ProcResKind,
362 const CodeGenProcModel &PM) const;
365 void collectProcModels();
367 // Initialize a new processor model if it is unique.
368 void addProcModel(Record *ProcDef);
370 void collectSchedRW();
372 std::string genRWName(const IdxVec& Seq, bool IsRead);
373 unsigned findRWForSequence(const IdxVec &Seq, bool IsRead);
375 void collectSchedClasses();
377 std::string createSchedClassName(const IdxVec &OperWrites,
378 const IdxVec &OperReads);
379 std::string createSchedClassName(const RecVec &InstDefs);
380 void createInstRWClass(Record *InstRWDef);
382 void collectProcItins();
384 void collectProcItinRW();
386 void inferSchedClasses();
388 void inferFromRW(const IdxVec &OperWrites, const IdxVec &OperReads,
389 unsigned FromClassIdx, const IdxVec &ProcIndices);
390 void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
391 void inferFromInstRWs(unsigned SCIdx);
393 void collectProcResources();
395 void collectItinProcResources(Record *ItinClassDef);
397 void collectRWResources(unsigned RWIdx, bool IsRead,
398 const IdxVec &ProcIndices);
400 void collectRWResources(const IdxVec &Writes, const IdxVec &Reads,
401 const IdxVec &ProcIndices);
403 void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM);
405 void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
407 void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);