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
{
55 CodeGenSchedRW(): TheDef(0), IsAlias(false), HasVariants(false),
56 IsVariadic(false), IsSequence(false) {}
57 CodeGenSchedRW(Record
*Def
): TheDef(Def
), IsAlias(false), IsVariadic(false) {
58 Name
= Def
->getName();
59 HasVariants
= Def
->isSubClassOf("SchedVariant");
61 IsVariadic
= Def
->getValueAsBit("Variadic");
63 // Read records don't currently have sequences, but it can be easily
64 // added. Note that implicit Reads (from ReadVariant) may have a Sequence
66 IsSequence
= Def
->isSubClassOf("WriteSequence");
69 CodeGenSchedRW(const IdxVec
&Seq
, const std::string
&Name
):
70 Name(Name
), TheDef(0), IsAlias(false), HasVariants(false),
71 IsVariadic(false), IsSequence(true), Sequence(Seq
) {
72 assert(Sequence
.size() > 1 && "implied sequence needs >1 RWs");
75 bool isValid() const {
76 assert((!HasVariants
|| TheDef
) && "Variant write needs record def");
77 assert((!IsVariadic
|| HasVariants
) && "Variadic write needs variants");
78 assert((!IsSequence
|| !HasVariants
) && "Sequence can't have variant");
79 assert((!IsSequence
|| !Sequence
.empty()) && "Sequence should be nonempty");
80 assert((!IsAlias
|| Aliases
.empty()) && "Alias cannot have aliases");
81 return TheDef
|| !Sequence
.empty();
89 /// Represent a transition between SchedClasses induced by SchedVariant.
90 struct CodeGenSchedTransition
{
98 /// Each instruction description will be mapped to a scheduling class. There are
99 /// four types of classes:
101 /// 1) An explicitly defined itinerary class with ItinClassDef set.
102 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
104 /// 2) An implied class with a list of SchedWrites and SchedReads that are
105 /// defined in an instruction definition and which are common across all
106 /// subtargets. ProcIndices contains 0 for any processor.
108 /// 3) An implied class with a list of InstRW records that map instructions to
109 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
110 /// instructions to this class. ProcIndices contains all the processors that
111 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
112 /// still be defined for processors with no InstRW entry.
114 /// 4) An inferred class represents a variant of another class that may be
115 /// resolved at runtime. ProcIndices contains the set of processors that may
116 /// require the class. ProcIndices are propagated through SchedClasses as
117 /// variants are expanded. Multiple SchedClasses may be inferred from an
118 /// itinerary class. Each inherits the processor index from the ItinRW record
119 /// that mapped the itinerary class to the variant Writes or Reads.
120 struct CodeGenSchedClass
{
122 Record
*ItinClassDef
;
126 // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
129 std::vector
<CodeGenSchedTransition
> Transitions
;
131 // InstRW records associated with this class. These records may refer to an
132 // Instruction no longer mapped to this class by InstrClassMap. These
133 // Instructions should be ignored by this class because they have been split
134 // off to join another inferred class.
137 CodeGenSchedClass(): ItinClassDef(0) {}
138 CodeGenSchedClass(Record
*rec
): ItinClassDef(rec
) {
139 Name
= rec
->getName();
140 ProcIndices
.push_back(0);
144 void dump(const CodeGenSchedModels
*SchedModels
) const;
150 // ModelName is a unique name used to name an instantiation of MCSchedModel.
152 // ModelDef is NULL for inferred Models. This happens when a processor defines
153 // an itinerary but no machine model. If the processer defines neither a machine
154 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
155 // the special "NoModel" field set to true.
157 // ItinsDef always points to a valid record definition, but may point to the
158 // default NoItineraries. NoItineraries has an empty list of InstrItinData
161 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
162 struct CodeGenProcModel
{
164 std::string ModelName
;
168 // Derived members...
170 // Array of InstrItinData records indexed by a CodeGenSchedClass index.
171 // This list is empty if the Processor has no value for Itineraries.
172 // Initialized by collectProcItins().
175 // Map itinerary classes to per-operand resources.
176 // This list is empty if no ItinRW refers to this Processor.
179 // All read/write resources associated with this processor.
181 RecVec ReadAdvanceDefs
;
183 // Per-operand machine model resources associated with this processor.
184 RecVec ProcResourceDefs
;
186 CodeGenProcModel(unsigned Idx
, const std::string
&Name
, Record
*MDef
,
188 Index(Idx
), ModelName(Name
), ModelDef(MDef
), ItinsDef(IDef
) {}
190 bool hasInstrSchedModel() const {
191 return !WriteResDefs
.empty() || !ItinRWDefs
.empty();
194 unsigned getProcResourceIdx(Record
*PRDef
) const;
201 /// Top level container for machine model data.
202 class CodeGenSchedModels
{
203 RecordKeeper
&Records
;
204 const CodeGenTarget
&Target
;
206 // List of unique processor models.
207 std::vector
<CodeGenProcModel
> ProcModels
;
209 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
210 typedef DenseMap
<Record
*, unsigned> ProcModelMapTy
;
211 ProcModelMapTy ProcModelMap
;
213 // Per-operand SchedReadWrite types.
214 std::vector
<CodeGenSchedRW
> SchedWrites
;
215 std::vector
<CodeGenSchedRW
> SchedReads
;
217 // List of unique SchedClasses.
218 std::vector
<CodeGenSchedClass
> SchedClasses
;
220 // Map SchedClass name to itinerary index.
221 // These are either explicit itinerary classes or classes implied by
222 // instruction definitions with SchedReadWrite lists.
223 StringMap
<unsigned> SchedClassIdxMap
;
225 // SchedClass indices 1 up to and including NumItineraryClasses identify
226 // itinerary classes that are explicitly used for this target's instruction
227 // definitions. NoItinerary always has index 0 regardless of whether it is
228 // explicitly referenced.
230 // Any implied SchedClass has an index greater than NumItineraryClasses.
231 unsigned NumItineraryClasses
;
233 // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
234 unsigned NumInstrSchedClasses
;
236 // Map Instruction to SchedClass index. Only for Instructions mentioned in
238 typedef DenseMap
<Record
*, unsigned> InstClassMapTy
;
239 InstClassMapTy InstrClassMap
;
242 CodeGenSchedModels(RecordKeeper
& RK
, const CodeGenTarget
&TGT
);
244 Record
*getModelOrItinDef(Record
*ProcDef
) const {
245 Record
*ModelDef
= ProcDef
->getValueAsDef("SchedModel");
246 Record
*ItinsDef
= ProcDef
->getValueAsDef("ProcItin");
247 if (!ItinsDef
->getValueAsListOfDefs("IID").empty()) {
248 assert(ModelDef
->getValueAsBit("NoModel")
249 && "Itineraries must be defined within SchedMachineModel");
255 const CodeGenProcModel
&getModelForProc(Record
*ProcDef
) const {
256 Record
*ModelDef
= getModelOrItinDef(ProcDef
);
257 ProcModelMapTy::const_iterator I
= ProcModelMap
.find(ModelDef
);
258 assert(I
!= ProcModelMap
.end() && "missing machine model");
259 return ProcModels
[I
->second
];
262 const CodeGenProcModel
&getProcModel(Record
*ModelDef
) const {
263 ProcModelMapTy::const_iterator I
= ProcModelMap
.find(ModelDef
);
264 assert(I
!= ProcModelMap
.end() && "missing machine model");
265 return ProcModels
[I
->second
];
268 // Iterate over the unique processor models.
269 typedef std::vector
<CodeGenProcModel
>::const_iterator ProcIter
;
270 ProcIter
procModelBegin() const { return ProcModels
.begin(); }
271 ProcIter
procModelEnd() const { return ProcModels
.end(); }
273 // Get a SchedWrite from its index.
274 const CodeGenSchedRW
&getSchedWrite(unsigned Idx
) const {
275 assert(Idx
< SchedWrites
.size() && "bad SchedWrite index");
276 assert(SchedWrites
[Idx
].isValid() && "invalid SchedWrite");
277 return SchedWrites
[Idx
];
279 // Get a SchedWrite from its index.
280 const CodeGenSchedRW
&getSchedRead(unsigned Idx
) const {
281 assert(Idx
< SchedReads
.size() && "bad SchedRead index");
282 assert(SchedReads
[Idx
].isValid() && "invalid SchedRead");
283 return SchedReads
[Idx
];
286 const CodeGenSchedRW
&getSchedRW(unsigned Idx
, bool IsRead
) const {
287 return IsRead
? getSchedRead(Idx
) : getSchedWrite(Idx
);
289 CodeGenSchedRW
&getSchedRW(Record
*Def
, unsigned &Idx
) {
290 bool IsRead
= Def
->isSubClassOf("SchedRead");
291 Idx
= getSchedRWIdx(Def
, IsRead
);
292 return const_cast<CodeGenSchedRW
&>(
293 IsRead
? getSchedRead(Idx
) : getSchedWrite(Idx
));
295 CodeGenSchedRW
&getSchedRW(Record
*Def
) {
297 return getSchedRW(Def
, Idx
);
300 unsigned getSchedRWIdx(Record
*Def
, bool IsRead
, unsigned After
= 0) const;
302 // Return true if the given write record is referenced by a ReadAdvance.
303 bool hasReadOfWrite(Record
*WriteDef
) const;
305 // Check if any instructions are assigned to an explicit itinerary class other
307 bool hasItineraryClasses() const { return NumItineraryClasses
> 0; }
309 // Return the number of itinerary classes in use by this target's instruction
310 // descriptions, not including "NoItinerary".
311 unsigned numItineraryClasses() const {
312 return NumItineraryClasses
;
315 // Get a SchedClass from its index.
316 CodeGenSchedClass
&getSchedClass(unsigned Idx
) {
317 assert(Idx
< SchedClasses
.size() && "bad SchedClass index");
318 return SchedClasses
[Idx
];
320 const CodeGenSchedClass
&getSchedClass(unsigned Idx
) const {
321 assert(Idx
< SchedClasses
.size() && "bad SchedClass index");
322 return SchedClasses
[Idx
];
325 // Get the SchedClass index for an instruction. Instructions with no
326 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
328 unsigned getSchedClassIdx(const CodeGenInstruction
&Inst
) const;
330 unsigned getSchedClassIdx(const RecVec
&RWDefs
) const;
332 unsigned getSchedClassIdxForItin(const Record
*ItinDef
) {
333 return SchedClassIdxMap
[ItinDef
->getName()];
336 typedef std::vector
<CodeGenSchedClass
>::const_iterator SchedClassIter
;
337 SchedClassIter
schedClassBegin() const { return SchedClasses
.begin(); }
338 SchedClassIter
schedClassEnd() const { return SchedClasses
.end(); }
340 void findRWs(const RecVec
&RWDefs
, IdxVec
&Writes
, IdxVec
&Reads
) const;
341 void findRWs(const RecVec
&RWDefs
, IdxVec
&RWs
, bool IsRead
) const;
342 void expandRWSequence(unsigned RWIdx
, IdxVec
&RWSeq
, bool IsRead
) const;
344 unsigned addSchedClass(const IdxVec
&OperWrites
, const IdxVec
&OperReads
,
345 const IdxVec
&ProcIndices
);
347 unsigned findOrInsertRW(ArrayRef
<unsigned> Seq
, bool IsRead
);
349 unsigned findSchedClassIdx(const IdxVec
&Writes
, const IdxVec
&Reads
) const;
351 Record
*findProcResUnits(Record
*ProcResKind
,
352 const CodeGenProcModel
&PM
) const;
355 void collectProcModels();
357 // Initialize a new processor model if it is unique.
358 void addProcModel(Record
*ProcDef
);
360 void collectSchedRW();
362 std::string
genRWName(const IdxVec
& Seq
, bool IsRead
);
363 unsigned findRWForSequence(const IdxVec
&Seq
, bool IsRead
);
365 void collectSchedClasses();
367 std::string
createSchedClassName(const IdxVec
&OperWrites
,
368 const IdxVec
&OperReads
);
369 std::string
createSchedClassName(const RecVec
&InstDefs
);
370 void createInstRWClass(Record
*InstRWDef
);
372 void collectProcItins();
374 void collectProcItinRW();
376 void inferSchedClasses();
378 void inferFromRW(const IdxVec
&OperWrites
, const IdxVec
&OperReads
,
379 unsigned FromClassIdx
, const IdxVec
&ProcIndices
);
380 void inferFromItinClass(Record
*ItinClassDef
, unsigned FromClassIdx
);
381 void inferFromInstRWs(unsigned SCIdx
);
383 void collectProcResources();
385 void collectItinProcResources(Record
*ItinClassDef
);
387 void collectRWResources(const IdxVec
&Writes
, const IdxVec
&Reads
,
388 const IdxVec
&ProcIndices
);
390 void addProcResource(Record
*ProcResourceKind
, CodeGenProcModel
&PM
);
392 void addWriteRes(Record
*ProcWriteResDef
, unsigned PIdx
);
394 void addReadAdvance(Record
*ProcReadAdvanceDef
, unsigned PIdx
);