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();
86 /// Represent a transition between SchedClasses induced by SchedVariant.
87 struct CodeGenSchedTransition {
95 /// Each instruction description will be mapped to a scheduling class. There are
96 /// four types of classes:
98 /// 1) An explicitly defined itinerary class with ItinClassDef set.
99 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
101 /// 2) An implied class with a list of SchedWrites and SchedReads that are
102 /// defined in an instruction definition and which are common across all
103 /// subtargets. ProcIndices contains 0 for any processor.
105 /// 3) An implied class with a list of InstRW records that map instructions to
106 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
107 /// instructions to this class. ProcIndices contains all the processors that
108 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
109 /// still be defined for processors with no InstRW entry.
111 /// 4) An inferred class represents a variant of another class that may be
112 /// resolved at runtime. ProcIndices contains the set of processors that may
113 /// require the class. ProcIndices are propagated through SchedClasses as
114 /// variants are expanded. Multiple SchedClasses may be inferred from an
115 /// itinerary class. Each inherits the processor index from the ItinRW record
116 /// that mapped the itinerary class to the variant Writes or Reads.
117 struct CodeGenSchedClass {
119 Record *ItinClassDef;
123 // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
126 std::vector<CodeGenSchedTransition> Transitions;
128 // InstReadWrite records associated with this class. Any Instrs that the
129 // definitions refer to that are not mapped to this class should be ignored.
132 CodeGenSchedClass(): ItinClassDef(0) {}
133 CodeGenSchedClass(Record *rec): ItinClassDef(rec) {
134 Name = rec->getName();
135 ProcIndices.push_back(0);
139 void dump(const CodeGenSchedModels *SchedModels) const;
145 // ModelName is a unique name used to name an instantiation of MCSchedModel.
147 // ModelDef is NULL for inferred Models. This happens when a processor defines
148 // an itinerary but no machine model. If the processer defines neither a machine
149 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
150 // the special "NoModel" field set to true.
152 // ItinsDef always points to a valid record definition, but may point to the
153 // default NoItineraries. NoItineraries has an empty list of InstrItinData
156 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
157 struct CodeGenProcModel {
159 std::string ModelName;
163 // Derived members...
165 // Array of InstrItinData records indexed by a CodeGenSchedClass index.
166 // This list is empty if the Processor has no value for Itineraries.
167 // Initialized by collectProcItins().
170 // Map itinerary classes to per-operand resources.
171 // This list is empty if no ItinRW refers to this Processor.
174 // All read/write resources associated with this processor.
176 RecVec ReadAdvanceDefs;
178 // Per-operand machine model resources associated with this processor.
179 RecVec ProcResourceDefs;
181 CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
183 Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
185 bool hasInstrSchedModel() const {
186 return !WriteResDefs.empty() || !ItinRWDefs.empty();
189 unsigned getProcResourceIdx(Record *PRDef) const;
196 /// Top level container for machine model data.
197 class CodeGenSchedModels {
198 RecordKeeper &Records;
199 const CodeGenTarget &Target;
201 // List of unique processor models.
202 std::vector<CodeGenProcModel> ProcModels;
204 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
205 typedef DenseMap<Record*, unsigned> ProcModelMapTy;
206 ProcModelMapTy ProcModelMap;
208 // Per-operand SchedReadWrite types.
209 std::vector<CodeGenSchedRW> SchedWrites;
210 std::vector<CodeGenSchedRW> SchedReads;
212 // List of unique SchedClasses.
213 std::vector<CodeGenSchedClass> SchedClasses;
215 // Map SchedClass name to itinerary index.
216 // These are either explicit itinerary classes or classes implied by
217 // instruction definitions with SchedReadWrite lists.
218 StringMap<unsigned> SchedClassIdxMap;
220 // SchedClass indices 1 up to and including NumItineraryClasses identify
221 // itinerary classes that are explicitly used for this target's instruction
222 // definitions. NoItinerary always has index 0 regardless of whether it is
223 // explicitly referenced.
225 // Any implied SchedClass has an index greater than NumItineraryClasses.
226 unsigned NumItineraryClasses;
228 // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
229 unsigned NumInstrSchedClasses;
231 // Map Instruction to SchedClass index. Only for Instructions mentioned in
233 typedef DenseMap<Record*, unsigned> InstClassMapTy;
234 InstClassMapTy InstrClassMap;
237 CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
239 Record *getModelOrItinDef(Record *ProcDef) const {
240 Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
241 Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
242 if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
243 assert(ModelDef->getValueAsBit("NoModel")
244 && "Itineraries must be defined within SchedMachineModel");
250 const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
251 Record *ModelDef = getModelOrItinDef(ProcDef);
252 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
253 assert(I != ProcModelMap.end() && "missing machine model");
254 return ProcModels[I->second];
257 const CodeGenProcModel &getProcModel(Record *ModelDef) const {
258 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
259 assert(I != ProcModelMap.end() && "missing machine model");
260 return ProcModels[I->second];
263 // Iterate over the unique processor models.
264 typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
265 ProcIter procModelBegin() const { return ProcModels.begin(); }
266 ProcIter procModelEnd() const { return ProcModels.end(); }
268 // Get a SchedWrite from its index.
269 const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
270 assert(Idx < SchedWrites.size() && "bad SchedWrite index");
271 assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
272 return SchedWrites[Idx];
274 // Get a SchedWrite from its index.
275 const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
276 assert(Idx < SchedReads.size() && "bad SchedRead index");
277 assert(SchedReads[Idx].isValid() && "invalid SchedRead");
278 return SchedReads[Idx];
281 const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
282 return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
285 unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
287 // Check if any instructions are assigned to an explicit itinerary class other
289 bool hasItineraryClasses() const { return NumItineraryClasses > 0; }
291 // Return the number of itinerary classes in use by this target's instruction
292 // descriptions, not including "NoItinerary".
293 unsigned numItineraryClasses() const {
294 return NumItineraryClasses;
297 // Get a SchedClass from its index.
298 CodeGenSchedClass &getSchedClass(unsigned Idx) {
299 assert(Idx < SchedClasses.size() && "bad SchedClass index");
300 return SchedClasses[Idx];
302 const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
303 assert(Idx < SchedClasses.size() && "bad SchedClass index");
304 return SchedClasses[Idx];
307 // Get the SchedClass index for an instruction. Instructions with no
308 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
310 unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
312 unsigned getSchedClassIdx(const RecVec &RWDefs) const;
314 unsigned getSchedClassIdxForItin(const Record *ItinDef) {
315 return SchedClassIdxMap[ItinDef->getName()];
318 typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
319 SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
320 SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
322 void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
323 void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
324 void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
326 unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads,
327 const IdxVec &ProcIndices);
329 unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
331 unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const;
333 Record *findProcResUnits(Record *ProcResKind,
334 const CodeGenProcModel &PM) const;
337 void collectProcModels();
339 // Initialize a new processor model if it is unique.
340 void addProcModel(Record *ProcDef);
342 void collectSchedRW();
344 std::string genRWName(const IdxVec& Seq, bool IsRead);
345 unsigned findRWForSequence(const IdxVec &Seq, bool IsRead);
347 void collectSchedClasses();
349 std::string createSchedClassName(const IdxVec &OperWrites,
350 const IdxVec &OperReads);
351 std::string createSchedClassName(const RecVec &InstDefs);
352 void createInstRWClass(Record *InstRWDef);
354 void collectProcItins();
356 void collectProcItinRW();
358 void inferSchedClasses();
360 void inferFromRW(const IdxVec &OperWrites, const IdxVec &OperReads,
361 unsigned FromClassIdx, const IdxVec &ProcIndices);
362 void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
363 void inferFromInstRWs(unsigned SCIdx);
365 void collectProcResources();
367 void collectItinProcResources(Record *ItinClassDef);
369 void collectRWResources(const IdxVec &Writes, const IdxVec &Reads,
370 const IdxVec &ProcIndices);
372 void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM);
374 void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
376 void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);