1 //===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===//
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 #define DEBUG_TYPE "subtarget-emitter"
17 #include "CodeGenSchedule.h"
18 #include "CodeGenTarget.h"
19 #include "llvm/TableGen/Error.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/Regex.h"
22 #include "llvm/ADT/STLExtras.h"
27 static void dumpIdxVec(const IdxVec &V) {
28 for (unsigned i = 0, e = V.size(); i < e; ++i) {
29 dbgs() << V[i] << ", ";
32 static void dumpIdxVec(const SmallVectorImpl<unsigned> &V) {
33 for (unsigned i = 0, e = V.size(); i < e; ++i) {
34 dbgs() << V[i] << ", ";
39 // (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp.
40 struct InstrsOp : public SetTheory::Operator {
41 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
42 ArrayRef<SMLoc> Loc) {
43 ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc);
47 // (instregex "OpcPat",...) Find all instructions matching an opcode pattern.
49 // TODO: Since this is a prefix match, perform a binary search over the
50 // instruction names using lower_bound. Note that the predefined instrs must be
51 // scanned linearly first. However, this is only safe if the regex pattern has
52 // no top-level bars. The DAG already has a list of patterns, so there's no
53 // reason to use top-level bars, but we need a way to verify they don't exist
54 // before implementing the optimization.
55 struct InstRegexOp : public SetTheory::Operator {
56 const CodeGenTarget &Target;
57 InstRegexOp(const CodeGenTarget &t): Target(t) {}
59 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
60 ArrayRef<SMLoc> Loc) {
61 SmallVector<Regex*, 4> RegexList;
62 for (DagInit::const_arg_iterator
63 AI = Expr->arg_begin(), AE = Expr->arg_end(); AI != AE; ++AI) {
64 StringInit *SI = dyn_cast<StringInit>(*AI);
66 throw TGError(Loc, "instregex requires pattern string: "
67 + Expr->getAsString());
68 std::string pat = SI->getValue();
69 // Implement a python-style prefix match.
72 pat.insert(pat.end(), ')');
74 RegexList.push_back(new Regex(pat));
76 for (CodeGenTarget::inst_iterator I = Target.inst_begin(),
77 E = Target.inst_end(); I != E; ++I) {
78 for (SmallVectorImpl<Regex*>::iterator
79 RI = RegexList.begin(), RE = RegexList.end(); RI != RE; ++RI) {
80 if ((*RI)->match((*I)->TheDef->getName()))
81 Elts.insert((*I)->TheDef);
84 DeleteContainerPointers(RegexList);
88 /// CodeGenModels ctor interprets machine model records and populates maps.
89 CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
90 const CodeGenTarget &TGT):
91 Records(RK), Target(TGT), NumItineraryClasses(0) {
93 Sets.addFieldExpander("InstRW", "Instrs");
95 // Allow Set evaluation to recognize the dags used in InstRW records:
96 // (instrs Op1, Op1...)
97 Sets.addOperator("instrs", new InstrsOp);
98 Sets.addOperator("instregex", new InstRegexOp(Target));
100 // Instantiate a CodeGenProcModel for each SchedMachineModel with the values
101 // that are explicitly referenced in tablegen records. Resources associated
102 // with each processor will be derived later. Populate ProcModelMap with the
103 // CodeGenProcModel instances.
106 // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly
107 // defined, and populate SchedReads and SchedWrites vectors. Implicit
108 // SchedReadWrites that represent sequences derived from expanded variant will
109 // be inferred later.
112 // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly
113 // required by an instruction definition, and populate SchedClassIdxMap. Set
114 // NumItineraryClasses to the number of explicit itinerary classes referenced
115 // by instructions. Set NumInstrSchedClasses to the number of itinerary
116 // classes plus any classes implied by instructions that derive from class
117 // Sched and provide SchedRW list. This does not infer any new classes from
119 collectSchedClasses();
121 // Find instruction itineraries for each processor. Sort and populate
122 // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires
123 // all itinerary classes to be discovered.
126 // Find ItinRW records for each processor and itinerary class.
127 // (For per-operand resources mapped to itinerary classes).
130 // Infer new SchedClasses from SchedVariant.
133 // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and
135 collectProcResources();
138 /// Gather all processor models.
139 void CodeGenSchedModels::collectProcModels() {
140 RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor");
141 std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName());
143 // Reserve space because we can. Reallocation would be ok.
144 ProcModels.reserve(ProcRecords.size()+1);
146 // Use idx=0 for NoModel/NoItineraries.
147 Record *NoModelDef = Records.getDef("NoSchedModel");
148 Record *NoItinsDef = Records.getDef("NoItineraries");
149 ProcModels.push_back(CodeGenProcModel(0, "NoSchedModel",
150 NoModelDef, NoItinsDef));
151 ProcModelMap[NoModelDef] = 0;
153 // For each processor, find a unique machine model.
154 for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i)
155 addProcModel(ProcRecords[i]);
158 /// Get a unique processor model based on the defined MachineModel and
159 /// ProcessorItineraries.
160 void CodeGenSchedModels::addProcModel(Record *ProcDef) {
161 Record *ModelKey = getModelOrItinDef(ProcDef);
162 if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second)
165 std::string Name = ModelKey->getName();
166 if (ModelKey->isSubClassOf("SchedMachineModel")) {
167 Record *ItinsDef = ModelKey->getValueAsDef("Itineraries");
168 ProcModels.push_back(
169 CodeGenProcModel(ProcModels.size(), Name, ModelKey, ItinsDef));
172 // An itinerary is defined without a machine model. Infer a new model.
173 if (!ModelKey->getValueAsListOfDefs("IID").empty())
174 Name = Name + "Model";
175 ProcModels.push_back(
176 CodeGenProcModel(ProcModels.size(), Name,
177 ProcDef->getValueAsDef("SchedModel"), ModelKey));
179 DEBUG(ProcModels.back().dump());
182 // Recursively find all reachable SchedReadWrite records.
183 static void scanSchedRW(Record *RWDef, RecVec &RWDefs,
184 SmallPtrSet<Record*, 16> &RWSet) {
185 if (!RWSet.insert(RWDef))
187 RWDefs.push_back(RWDef);
188 // Reads don't current have sequence records, but it can be added later.
189 if (RWDef->isSubClassOf("WriteSequence")) {
190 RecVec Seq = RWDef->getValueAsListOfDefs("Writes");
191 for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I)
192 scanSchedRW(*I, RWDefs, RWSet);
194 else if (RWDef->isSubClassOf("SchedVariant")) {
195 // Visit each variant (guarded by a different predicate).
196 RecVec Vars = RWDef->getValueAsListOfDefs("Variants");
197 for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) {
198 // Visit each RW in the sequence selected by the current variant.
199 RecVec Selected = (*VI)->getValueAsListOfDefs("Selected");
200 for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I)
201 scanSchedRW(*I, RWDefs, RWSet);
206 // Collect and sort all SchedReadWrites reachable via tablegen records.
207 // More may be inferred later when inferring new SchedClasses from variants.
208 void CodeGenSchedModels::collectSchedRW() {
209 // Reserve idx=0 for invalid writes/reads.
210 SchedWrites.resize(1);
211 SchedReads.resize(1);
213 SmallPtrSet<Record*, 16> RWSet;
215 // Find all SchedReadWrites referenced by instruction defs.
216 RecVec SWDefs, SRDefs;
217 for (CodeGenTarget::inst_iterator I = Target.inst_begin(),
218 E = Target.inst_end(); I != E; ++I) {
219 Record *SchedDef = (*I)->TheDef;
220 if (!SchedDef->isSubClassOf("Sched"))
222 RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW");
223 for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) {
224 if ((*RWI)->isSubClassOf("SchedWrite"))
225 scanSchedRW(*RWI, SWDefs, RWSet);
227 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
228 scanSchedRW(*RWI, SRDefs, RWSet);
232 // Find all ReadWrites referenced by InstRW.
233 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
234 for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) {
235 // For all OperandReadWrites.
236 RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites");
237 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
239 if ((*RWI)->isSubClassOf("SchedWrite"))
240 scanSchedRW(*RWI, SWDefs, RWSet);
242 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
243 scanSchedRW(*RWI, SRDefs, RWSet);
247 // Find all ReadWrites referenced by ItinRW.
248 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
249 for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
250 // For all OperandReadWrites.
251 RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites");
252 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
254 if ((*RWI)->isSubClassOf("SchedWrite"))
255 scanSchedRW(*RWI, SWDefs, RWSet);
257 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
258 scanSchedRW(*RWI, SRDefs, RWSet);
262 // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted
263 // for the loop below that initializes Alias vectors.
264 RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias");
265 std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord());
266 for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) {
267 Record *MatchDef = (*AI)->getValueAsDef("MatchRW");
268 Record *AliasDef = (*AI)->getValueAsDef("AliasRW");
269 if (MatchDef->isSubClassOf("SchedWrite")) {
270 if (!AliasDef->isSubClassOf("SchedWrite"))
271 throw TGError((*AI)->getLoc(), "SchedWrite Alias must be SchedWrite");
272 scanSchedRW(AliasDef, SWDefs, RWSet);
275 assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
276 if (!AliasDef->isSubClassOf("SchedRead"))
277 throw TGError((*AI)->getLoc(), "SchedRead Alias must be SchedRead");
278 scanSchedRW(AliasDef, SRDefs, RWSet);
281 // Sort and add the SchedReadWrites directly referenced by instructions or
282 // itinerary resources. Index reads and writes in separate domains.
283 std::sort(SWDefs.begin(), SWDefs.end(), LessRecord());
284 for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) {
285 assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite");
286 SchedWrites.push_back(CodeGenSchedRW(SchedWrites.size(), *SWI));
288 std::sort(SRDefs.begin(), SRDefs.end(), LessRecord());
289 for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) {
290 assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite");
291 SchedReads.push_back(CodeGenSchedRW(SchedReads.size(), *SRI));
293 // Initialize WriteSequence vectors.
294 for (std::vector<CodeGenSchedRW>::iterator WI = SchedWrites.begin(),
295 WE = SchedWrites.end(); WI != WE; ++WI) {
298 findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence,
301 // Initialize Aliases vectors.
302 for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) {
303 Record *AliasDef = (*AI)->getValueAsDef("AliasRW");
304 getSchedRW(AliasDef).IsAlias = true;
305 Record *MatchDef = (*AI)->getValueAsDef("MatchRW");
306 CodeGenSchedRW &RW = getSchedRW(MatchDef);
308 throw TGError((*AI)->getLoc(), "Cannot Alias an Alias");
309 RW.Aliases.push_back(*AI);
312 for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) {
313 dbgs() << WIdx << ": ";
314 SchedWrites[WIdx].dump();
317 for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) {
318 dbgs() << RIdx << ": ";
319 SchedReads[RIdx].dump();
322 RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite");
323 for (RecIter RI = RWDefs.begin(), RE = RWDefs.end();
325 if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) {
326 const std::string &Name = (*RI)->getName();
327 if (Name != "NoWrite" && Name != "ReadDefault")
328 dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n';
333 /// Compute a SchedWrite name from a sequence of writes.
334 std::string CodeGenSchedModels::genRWName(const IdxVec& Seq, bool IsRead) {
335 std::string Name("(");
336 for (IdxIter I = Seq.begin(), E = Seq.end(); I != E; ++I) {
337 if (I != Seq.begin())
339 Name += getSchedRW(*I, IsRead).Name;
345 unsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead,
346 unsigned After) const {
347 const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
348 assert(After < RWVec.size() && "start position out of bounds");
349 for (std::vector<CodeGenSchedRW>::const_iterator I = RWVec.begin() + After,
350 E = RWVec.end(); I != E; ++I) {
351 if (I->TheDef == Def)
352 return I - RWVec.begin();
357 bool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const {
358 for (unsigned i = 0, e = SchedReads.size(); i < e; ++i) {
359 Record *ReadDef = SchedReads[i].TheDef;
360 if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance"))
363 RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites");
364 if (std::find(ValidWrites.begin(), ValidWrites.end(), WriteDef)
365 != ValidWrites.end()) {
373 void splitSchedReadWrites(const RecVec &RWDefs,
374 RecVec &WriteDefs, RecVec &ReadDefs) {
375 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) {
376 if ((*RWI)->isSubClassOf("SchedWrite"))
377 WriteDefs.push_back(*RWI);
379 assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite");
380 ReadDefs.push_back(*RWI);
386 // Split the SchedReadWrites defs and call findRWs for each list.
387 void CodeGenSchedModels::findRWs(const RecVec &RWDefs,
388 IdxVec &Writes, IdxVec &Reads) const {
391 splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs);
392 findRWs(WriteDefs, Writes, false);
393 findRWs(ReadDefs, Reads, true);
396 // Call getSchedRWIdx for all elements in a sequence of SchedRW defs.
397 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs,
399 for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) {
400 unsigned Idx = getSchedRWIdx(*RI, IsRead);
401 assert(Idx && "failed to collect SchedReadWrite");
406 void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq,
408 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
409 if (!SchedRW.IsSequence) {
410 RWSeq.push_back(RWIdx);
414 SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1;
415 for (int i = 0; i < Repeat; ++i) {
416 for (IdxIter I = SchedRW.Sequence.begin(), E = SchedRW.Sequence.end();
418 expandRWSequence(*I, RWSeq, IsRead);
423 // Expand a SchedWrite as a sequence following any aliases that coincide with
424 // the given processor model.
425 void CodeGenSchedModels::expandRWSeqForProc(
426 unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
427 const CodeGenProcModel &ProcModel) const {
429 const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead);
430 Record *AliasDef = 0;
431 for (RecIter AI = SchedWrite.Aliases.begin(), AE = SchedWrite.Aliases.end();
433 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
434 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
435 Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
436 if (&getProcModel(ModelDef) != &ProcModel)
440 throw TGError(AliasRW.TheDef->getLoc(), "Multiple aliases "
441 "defined for processor " + ProcModel.ModelName +
442 " Ensure only one SchedAlias exists per RW.");
443 AliasDef = AliasRW.TheDef;
446 expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead),
447 RWSeq, IsRead,ProcModel);
450 if (!SchedWrite.IsSequence) {
451 RWSeq.push_back(RWIdx);
455 SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1;
456 for (int i = 0; i < Repeat; ++i) {
457 for (IdxIter I = SchedWrite.Sequence.begin(), E = SchedWrite.Sequence.end();
459 expandRWSeqForProc(*I, RWSeq, IsRead, ProcModel);
464 // Find the existing SchedWrite that models this sequence of writes.
465 unsigned CodeGenSchedModels::findRWForSequence(const IdxVec &Seq,
467 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
469 for (std::vector<CodeGenSchedRW>::iterator I = RWVec.begin(), E = RWVec.end();
471 if (I->Sequence == Seq)
472 return I - RWVec.begin();
474 // Index zero reserved for invalid RW.
478 /// Add this ReadWrite if it doesn't already exist.
479 unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq,
481 assert(!Seq.empty() && "cannot insert empty sequence");
485 unsigned Idx = findRWForSequence(Seq, IsRead);
489 unsigned RWIdx = IsRead ? SchedReads.size() : SchedWrites.size();
490 CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead));
492 SchedReads.push_back(SchedRW);
494 SchedWrites.push_back(SchedRW);
498 /// Visit all the instruction definitions for this target to gather and
499 /// enumerate the itinerary classes. These are the explicitly specified
500 /// SchedClasses. More SchedClasses may be inferred.
501 void CodeGenSchedModels::collectSchedClasses() {
503 // NoItinerary is always the first class at Idx=0
504 SchedClasses.resize(1);
505 SchedClasses.back().Name = "NoItinerary";
506 SchedClasses.back().ProcIndices.push_back(0);
507 SchedClassIdxMap[SchedClasses.back().Name] = 0;
509 // Gather and sort all itinerary classes used by instruction descriptions.
510 RecVec ItinClassList;
511 for (CodeGenTarget::inst_iterator I = Target.inst_begin(),
512 E = Target.inst_end(); I != E; ++I) {
513 Record *ItinDef = (*I)->TheDef->getValueAsDef("Itinerary");
514 // Map a new SchedClass with no index.
515 if (!SchedClassIdxMap.count(ItinDef->getName())) {
516 SchedClassIdxMap[ItinDef->getName()] = 0;
517 ItinClassList.push_back(ItinDef);
520 // Assign each itinerary class unique number, skipping NoItinerary==0
521 NumItineraryClasses = ItinClassList.size();
522 std::sort(ItinClassList.begin(), ItinClassList.end(), LessRecord());
523 for (unsigned i = 0, N = NumItineraryClasses; i < N; i++) {
524 Record *ItinDef = ItinClassList[i];
525 SchedClassIdxMap[ItinDef->getName()] = SchedClasses.size();
526 SchedClasses.push_back(CodeGenSchedClass(ItinDef));
528 // Infer classes from SchedReadWrite resources listed for each
529 // instruction definition that inherits from class Sched.
530 for (CodeGenTarget::inst_iterator I = Target.inst_begin(),
531 E = Target.inst_end(); I != E; ++I) {
532 if (!(*I)->TheDef->isSubClassOf("Sched"))
534 IdxVec Writes, Reads;
535 findRWs((*I)->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
536 // ProcIdx == 0 indicates the class applies to all processors.
537 IdxVec ProcIndices(1, 0);
538 addSchedClass(Writes, Reads, ProcIndices);
540 // Create classes for InstRW defs.
541 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
542 std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord());
543 for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI)
544 createInstRWClass(*OI);
546 NumInstrSchedClasses = SchedClasses.size();
548 bool EnableDump = false;
549 DEBUG(EnableDump = true);
552 for (CodeGenTarget::inst_iterator I = Target.inst_begin(),
553 E = Target.inst_end(); I != E; ++I) {
554 Record *SchedDef = (*I)->TheDef;
555 std::string InstName = (*I)->TheDef->getName();
556 if (SchedDef->isSubClassOf("Sched")) {
559 findRWs((*I)->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
560 dbgs() << "SchedRW machine model for " << InstName;
561 for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI)
562 dbgs() << " " << SchedWrites[*WI].Name;
563 for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI)
564 dbgs() << " " << SchedReads[*RI].Name;
567 unsigned SCIdx = InstrClassMap.lookup((*I)->TheDef);
569 const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs;
570 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
572 const CodeGenProcModel &ProcModel =
573 getProcModel((*RWI)->getValueAsDef("SchedModel"));
574 dbgs() << "InstRW on " << ProcModel.ModelName << " for " << InstName;
577 findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"),
579 for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI)
580 dbgs() << " " << SchedWrites[*WI].Name;
581 for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI)
582 dbgs() << " " << SchedReads[*RI].Name;
587 if (!SchedDef->isSubClassOf("Sched")
588 && (SchedDef->getValueAsDef("Itinerary")->getName() == "NoItinerary")) {
589 dbgs() << "No machine model for " << (*I)->TheDef->getName() << '\n';
594 unsigned CodeGenSchedModels::getSchedClassIdx(
595 const RecVec &RWDefs) const {
597 IdxVec Writes, Reads;
598 findRWs(RWDefs, Writes, Reads);
599 return findSchedClassIdx(Writes, Reads);
602 /// Find an SchedClass that has been inferred from a per-operand list of
603 /// SchedWrites and SchedReads.
604 unsigned CodeGenSchedModels::findSchedClassIdx(const IdxVec &Writes,
605 const IdxVec &Reads) const {
606 for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) {
607 // Classes with InstRWs may have the same Writes/Reads as a class originally
608 // produced by a SchedRW definition. We need to be able to recover the
609 // original class index for processors that don't match any InstRWs.
610 if (I->ItinClassDef || !I->InstRWs.empty())
613 if (I->Writes == Writes && I->Reads == Reads) {
614 return I - schedClassBegin();
620 // Get the SchedClass index for an instruction.
621 unsigned CodeGenSchedModels::getSchedClassIdx(
622 const CodeGenInstruction &Inst) const {
624 unsigned SCIdx = InstrClassMap.lookup(Inst.TheDef);
628 // If this opcode isn't mapped by the subtarget fallback to the instruction
629 // definition's SchedRW or ItinDef values.
630 if (Inst.TheDef->isSubClassOf("Sched")) {
631 RecVec RWs = Inst.TheDef->getValueAsListOfDefs("SchedRW");
632 return getSchedClassIdx(RWs);
634 Record *ItinDef = Inst.TheDef->getValueAsDef("Itinerary");
635 assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass");
636 unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName());
637 assert(Idx <= NumItineraryClasses && "bad ItinClass index");
641 std::string CodeGenSchedModels::createSchedClassName(
642 const IdxVec &OperWrites, const IdxVec &OperReads) {
645 for (IdxIter WI = OperWrites.begin(), WE = OperWrites.end(); WI != WE; ++WI) {
646 if (WI != OperWrites.begin())
648 Name += SchedWrites[*WI].Name;
650 for (IdxIter RI = OperReads.begin(), RE = OperReads.end(); RI != RE; ++RI) {
652 Name += SchedReads[*RI].Name;
657 std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) {
660 for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) {
661 if (I != InstDefs.begin())
663 Name += (*I)->getName();
668 /// Add an inferred sched class from a per-operand list of SchedWrites and
669 /// SchedReads. ProcIndices contains the set of IDs of processors that may
670 /// utilize this class.
671 unsigned CodeGenSchedModels::addSchedClass(const IdxVec &OperWrites,
672 const IdxVec &OperReads,
673 const IdxVec &ProcIndices)
675 assert(!ProcIndices.empty() && "expect at least one ProcIdx");
677 unsigned Idx = findSchedClassIdx(OperWrites, OperReads);
680 std::set_union(SchedClasses[Idx].ProcIndices.begin(),
681 SchedClasses[Idx].ProcIndices.end(),
682 ProcIndices.begin(), ProcIndices.end(),
683 std::back_inserter(PI));
684 SchedClasses[Idx].ProcIndices.swap(PI);
687 Idx = SchedClasses.size();
688 SchedClasses.resize(Idx+1);
689 CodeGenSchedClass &SC = SchedClasses.back();
690 SC.Name = createSchedClassName(OperWrites, OperReads);
691 SC.Writes = OperWrites;
692 SC.Reads = OperReads;
693 SC.ProcIndices = ProcIndices;
698 // Create classes for each set of opcodes that are in the same InstReadWrite
699 // definition across all processors.
700 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) {
701 // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that
702 // intersects with an existing class via a previous InstRWDef. Instrs that do
703 // not intersect with an existing class refer back to their former class as
704 // determined from ItinDef or SchedRW.
705 SmallVector<std::pair<unsigned, SmallVector<Record *, 8> >, 4> ClassInstrs;
706 // Sort Instrs into sets.
707 const RecVec *InstDefs = Sets.expand(InstRWDef);
708 if (InstDefs->empty())
709 throw TGError(InstRWDef->getLoc(), "No matching instruction opcodes");
711 for (RecIter I = InstDefs->begin(), E = InstDefs->end(); I != E; ++I) {
713 InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I);
714 if (Pos != InstrClassMap.end())
717 // This instruction has not been mapped yet. Get the original class. All
718 // instructions in the same InstrRW class must be from the same original
719 // class because that is the fall-back class for other processors.
720 Record *ItinDef = (*I)->getValueAsDef("Itinerary");
721 SCIdx = SchedClassIdxMap.lookup(ItinDef->getName());
722 if (!SCIdx && (*I)->isSubClassOf("Sched"))
723 SCIdx = getSchedClassIdx((*I)->getValueAsListOfDefs("SchedRW"));
725 unsigned CIdx = 0, CEnd = ClassInstrs.size();
726 for (; CIdx != CEnd; ++CIdx) {
727 if (ClassInstrs[CIdx].first == SCIdx)
731 ClassInstrs.resize(CEnd + 1);
732 ClassInstrs[CIdx].first = SCIdx;
734 ClassInstrs[CIdx].second.push_back(*I);
736 // For each set of Instrs, create a new class if necessary, and map or remap
738 unsigned CIdx = 0, CEnd = ClassInstrs.size();
739 for (; CIdx != CEnd; ++CIdx) {
740 unsigned OldSCIdx = ClassInstrs[CIdx].first;
741 ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second;
742 // If the all instrs in the current class are accounted for, then leave
743 // them mapped to their old class.
744 if (SchedClasses[OldSCIdx].InstRWs.size() == InstDefs.size()) {
745 assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 &&
746 "expected a generic SchedClass");
749 unsigned SCIdx = SchedClasses.size();
750 SchedClasses.resize(SCIdx+1);
751 CodeGenSchedClass &SC = SchedClasses.back();
752 SC.Name = createSchedClassName(InstDefs);
753 // Preserve ItinDef and Writes/Reads for processors without an InstRW entry.
754 SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef;
755 SC.Writes = SchedClasses[OldSCIdx].Writes;
756 SC.Reads = SchedClasses[OldSCIdx].Reads;
757 SC.ProcIndices.push_back(0);
758 // Map each Instr to this new class.
759 // Note that InstDefs may be a smaller list than InstRWDef's "Instrs".
760 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel");
761 SmallSet<unsigned, 4> RemappedClassIDs;
762 for (ArrayRef<Record*>::const_iterator
763 II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) {
764 unsigned OldSCIdx = InstrClassMap[*II];
765 if (OldSCIdx && RemappedClassIDs.insert(OldSCIdx)) {
766 for (RecIter RI = SchedClasses[OldSCIdx].InstRWs.begin(),
767 RE = SchedClasses[OldSCIdx].InstRWs.end(); RI != RE; ++RI) {
768 if ((*RI)->getValueAsDef("SchedModel") == RWModelDef) {
769 throw TGError(InstRWDef->getLoc(), "Overlapping InstRW def " +
770 (*II)->getName() + " also matches " +
771 (*RI)->getValue("Instrs")->getValue()->getAsString());
773 assert(*RI != InstRWDef && "SchedClass has duplicate InstRW def");
774 SC.InstRWs.push_back(*RI);
777 InstrClassMap[*II] = SCIdx;
779 SC.InstRWs.push_back(InstRWDef);
783 // Gather the processor itineraries.
784 void CodeGenSchedModels::collectProcItins() {
785 for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(),
786 PE = ProcModels.end(); PI != PE; ++PI) {
787 CodeGenProcModel &ProcModel = *PI;
788 RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID");
789 // Skip empty itinerary.
790 if (ItinRecords.empty())
793 ProcModel.ItinDefList.resize(NumItineraryClasses+1);
795 // Insert each itinerary data record in the correct position within
796 // the processor model's ItinDefList.
797 for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) {
798 Record *ItinData = ItinRecords[i];
799 Record *ItinDef = ItinData->getValueAsDef("TheClass");
800 if (!SchedClassIdxMap.count(ItinDef->getName())) {
801 DEBUG(dbgs() << ProcModel.ItinsDef->getName()
802 << " has unused itinerary class " << ItinDef->getName() << '\n');
805 assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass");
806 unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName());
807 assert(Idx <= NumItineraryClasses && "bad ItinClass index");
808 ProcModel.ItinDefList[Idx] = ItinData;
810 // Check for missing itinerary entries.
811 assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec");
813 for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) {
814 if (!ProcModel.ItinDefList[i])
815 dbgs() << ProcModel.ItinsDef->getName()
816 << " missing itinerary for class "
817 << SchedClasses[i].Name << '\n';
822 // Gather the read/write types for each itinerary class.
823 void CodeGenSchedModels::collectProcItinRW() {
824 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
825 std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord());
826 for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
827 if (!(*II)->getValueInit("SchedModel")->isComplete())
828 throw TGError((*II)->getLoc(), "SchedModel is undefined");
829 Record *ModelDef = (*II)->getValueAsDef("SchedModel");
830 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
831 if (I == ProcModelMap.end()) {
832 throw TGError((*II)->getLoc(), "Undefined SchedMachineModel "
833 + ModelDef->getName());
835 ProcModels[I->second].ItinRWDefs.push_back(*II);
839 /// Infer new classes from existing classes. In the process, this may create new
840 /// SchedWrites from sequences of existing SchedWrites.
841 void CodeGenSchedModels::inferSchedClasses() {
842 // Visit all existing classes and newly created classes.
843 for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) {
844 if (SchedClasses[Idx].ItinClassDef)
845 inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx);
846 else if (!SchedClasses[Idx].InstRWs.empty())
847 inferFromInstRWs(Idx);
849 inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads,
850 Idx, SchedClasses[Idx].ProcIndices);
852 assert(SchedClasses.size() < (NumInstrSchedClasses*6) &&
853 "too many SchedVariants");
857 /// Infer classes from per-processor itinerary resources.
858 void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef,
859 unsigned FromClassIdx) {
860 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
861 const CodeGenProcModel &PM = ProcModels[PIdx];
862 // For all ItinRW entries.
863 bool HasMatch = false;
864 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
866 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
867 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
870 throw TGError((*II)->getLoc(), "Duplicate itinerary class "
871 + ItinClassDef->getName()
872 + " in ItinResources for " + PM.ModelName);
874 IdxVec Writes, Reads;
875 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
876 IdxVec ProcIndices(1, PIdx);
877 inferFromRW(Writes, Reads, FromClassIdx, ProcIndices);
882 /// Infer classes from per-processor InstReadWrite definitions.
883 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) {
884 const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs;
885 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) {
886 const RecVec *InstDefs = Sets.expand(*RWI);
887 RecIter II = InstDefs->begin(), IE = InstDefs->end();
888 for (; II != IE; ++II) {
889 if (InstrClassMap[*II] == SCIdx)
892 // If this class no longer has any instructions mapped to it, it has become
896 IdxVec Writes, Reads;
897 findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
898 unsigned PIdx = getProcModel((*RWI)->getValueAsDef("SchedModel")).Index;
899 IdxVec ProcIndices(1, PIdx);
900 inferFromRW(Writes, Reads, SCIdx, ProcIndices);
905 // Helper for substituteVariantOperand.
906 struct TransVariant {
907 Record *VarOrSeqDef; // Variant or sequence.
908 unsigned RWIdx; // Index of this variant or sequence's matched type.
909 unsigned ProcIdx; // Processor model index or zero for any.
910 unsigned TransVecIdx; // Index into PredTransitions::TransVec.
912 TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti):
913 VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {}
916 // Associate a predicate with the SchedReadWrite that it guards.
917 // RWIdx is the index of the read/write variant.
923 PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {}
926 // A Predicate transition is a list of RW sequences guarded by a PredTerm.
927 struct PredTransition {
928 // A predicate term is a conjunction of PredChecks.
929 SmallVector<PredCheck, 4> PredTerm;
930 SmallVector<SmallVector<unsigned,4>, 16> WriteSequences;
931 SmallVector<SmallVector<unsigned,4>, 16> ReadSequences;
932 SmallVector<unsigned, 4> ProcIndices;
935 // Encapsulate a set of partially constructed transitions.
936 // The results are built by repeated calls to substituteVariants.
937 class PredTransitions {
938 CodeGenSchedModels &SchedModels;
941 std::vector<PredTransition> TransVec;
943 PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {}
945 void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq,
946 bool IsRead, unsigned StartIdx);
948 void substituteVariants(const PredTransition &Trans);
955 bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term);
956 void getIntersectingVariants(
957 const CodeGenSchedRW &SchedRW, unsigned TransIdx,
958 std::vector<TransVariant> &IntersectingVariants);
959 void pushVariant(const TransVariant &VInfo, bool IsRead);
963 // Return true if this predicate is mutually exclusive with a PredTerm. This
964 // degenerates into checking if the predicate is mutually exclusive with any
965 // predicate in the Term's conjunction.
967 // All predicates associated with a given SchedRW are considered mutually
968 // exclusive. This should work even if the conditions expressed by the
969 // predicates are not exclusive because the predicates for a given SchedWrite
970 // are always checked in the order they are defined in the .td file. Later
971 // conditions implicitly negate any prior condition.
972 bool PredTransitions::mutuallyExclusive(Record *PredDef,
973 ArrayRef<PredCheck> Term) {
975 for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end();
977 if (I->Predicate == PredDef)
980 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead);
981 assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant");
982 RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants");
983 for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) {
984 if ((*VI)->getValueAsDef("Predicate") == PredDef)
991 static bool hasAliasedVariants(const CodeGenSchedRW &RW,
992 CodeGenSchedModels &SchedModels) {
996 for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) {
997 const CodeGenSchedRW &AliasRW =
998 SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW"));
999 if (AliasRW.HasVariants)
1001 if (AliasRW.IsSequence) {
1003 SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead);
1004 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
1006 if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead),
1016 static bool hasVariant(ArrayRef<PredTransition> Transitions,
1017 CodeGenSchedModels &SchedModels) {
1018 for (ArrayRef<PredTransition>::iterator
1019 PTI = Transitions.begin(), PTE = Transitions.end();
1020 PTI != PTE; ++PTI) {
1021 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1022 WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end();
1023 WSI != WSE; ++WSI) {
1024 for (SmallVectorImpl<unsigned>::const_iterator
1025 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
1026 if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels))
1030 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1031 RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end();
1032 RSI != RSE; ++RSI) {
1033 for (SmallVectorImpl<unsigned>::const_iterator
1034 RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) {
1035 if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels))
1043 // Populate IntersectingVariants with any variants or aliased sequences of the
1044 // given SchedRW whose processor indices and predicates are not mutually
1045 // exclusive with the given transition,
1046 void PredTransitions::getIntersectingVariants(
1047 const CodeGenSchedRW &SchedRW, unsigned TransIdx,
1048 std::vector<TransVariant> &IntersectingVariants) {
1050 std::vector<TransVariant> Variants;
1051 if (SchedRW.HasVariants) {
1052 unsigned VarProcIdx = 0;
1053 if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) {
1054 Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel");
1055 VarProcIdx = SchedModels.getProcModel(ModelDef).Index;
1057 // Push each variant. Assign TransVecIdx later.
1058 const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants");
1059 for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
1060 Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0));
1062 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1064 // If either the SchedAlias itself or the SchedReadWrite that it aliases
1065 // to is defined within a processor model, constrain all variants to
1067 unsigned AliasProcIdx = 0;
1068 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1069 Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
1070 AliasProcIdx = SchedModels.getProcModel(ModelDef).Index;
1072 const CodeGenSchedRW &AliasRW =
1073 SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW"));
1075 if (AliasRW.HasVariants) {
1076 const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants");
1077 for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
1078 Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0));
1080 if (AliasRW.IsSequence) {
1082 TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0));
1085 for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) {
1086 TransVariant &Variant = Variants[VIdx];
1087 // Don't expand variants if the processor models don't intersect.
1088 // A zero processor index means any processor.
1089 SmallVector<unsigned, 4> &ProcIndices = TransVec[TransIdx].ProcIndices;
1090 if (ProcIndices[0] && Variants[VIdx].ProcIdx) {
1091 unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(),
1096 const CodeGenProcModel &PM =
1097 *(SchedModels.procModelBegin() + Variant.ProcIdx);
1098 throw TGError(Variant.VarOrSeqDef->getLoc(),
1099 "Multiple variants defined for processor " + PM.ModelName +
1100 " Ensure only one SchedAlias exists per RW.");
1103 if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) {
1104 Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate");
1105 if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm))
1108 if (IntersectingVariants.empty()) {
1109 // The first variant builds on the existing transition.
1110 Variant.TransVecIdx = TransIdx;
1111 IntersectingVariants.push_back(Variant);
1114 // Push another copy of the current transition for more variants.
1115 Variant.TransVecIdx = TransVec.size();
1116 IntersectingVariants.push_back(Variant);
1117 TransVec.push_back(TransVec[TransIdx]);
1122 // Push the Reads/Writes selected by this variant onto the PredTransition
1123 // specified by VInfo.
1124 void PredTransitions::
1125 pushVariant(const TransVariant &VInfo, bool IsRead) {
1127 PredTransition &Trans = TransVec[VInfo.TransVecIdx];
1129 // If this operand transition is reached through a processor-specific alias,
1130 // then the whole transition is specific to this processor.
1131 if (VInfo.ProcIdx != 0)
1132 Trans.ProcIndices.assign(1, VInfo.ProcIdx);
1135 if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) {
1136 Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate");
1137 Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef));
1138 RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected");
1139 SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead);
1142 assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") &&
1143 "variant must be a SchedVariant or aliased WriteSequence");
1144 SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead));
1147 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead);
1149 SmallVectorImpl<SmallVector<unsigned,4> > &RWSequences = IsRead
1150 ? Trans.ReadSequences : Trans.WriteSequences;
1151 if (SchedRW.IsVariadic) {
1152 unsigned OperIdx = RWSequences.size()-1;
1153 // Make N-1 copies of this transition's last sequence.
1154 for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) {
1155 RWSequences.push_back(RWSequences[OperIdx]);
1157 // Push each of the N elements of the SelectedRWs onto a copy of the last
1158 // sequence (split the current operand into N operands).
1159 // Note that write sequences should be expanded within this loop--the entire
1160 // sequence belongs to a single operand.
1161 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1162 RWI != RWE; ++RWI, ++OperIdx) {
1165 ExpandedRWs.push_back(*RWI);
1167 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1168 RWSequences[OperIdx].insert(RWSequences[OperIdx].end(),
1169 ExpandedRWs.begin(), ExpandedRWs.end());
1171 assert(OperIdx == RWSequences.size() && "missed a sequence");
1174 // Push this transition's expanded sequence onto this transition's last
1175 // sequence (add to the current operand's sequence).
1176 SmallVectorImpl<unsigned> &Seq = RWSequences.back();
1178 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1179 RWI != RWE; ++RWI) {
1181 ExpandedRWs.push_back(*RWI);
1183 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1185 Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end());
1189 // RWSeq is a sequence of all Reads or all Writes for the next read or write
1190 // operand. StartIdx is an index into TransVec where partial results
1191 // starts. RWSeq must be applied to all transitions between StartIdx and the end
1193 void PredTransitions::substituteVariantOperand(
1194 const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) {
1196 // Visit each original RW within the current sequence.
1197 for (SmallVectorImpl<unsigned>::const_iterator
1198 RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) {
1199 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead);
1200 // Push this RW on all partial PredTransitions or distribute variants.
1201 // New PredTransitions may be pushed within this loop which should not be
1202 // revisited (TransEnd must be loop invariant).
1203 for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size();
1204 TransIdx != TransEnd; ++TransIdx) {
1205 // In the common case, push RW onto the current operand's sequence.
1206 if (!hasAliasedVariants(SchedRW, SchedModels)) {
1208 TransVec[TransIdx].ReadSequences.back().push_back(*RWI);
1210 TransVec[TransIdx].WriteSequences.back().push_back(*RWI);
1213 // Distribute this partial PredTransition across intersecting variants.
1214 // This will push a copies of TransVec[TransIdx] on the back of TransVec.
1215 std::vector<TransVariant> IntersectingVariants;
1216 getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants);
1217 if (IntersectingVariants.empty())
1218 throw TGError(SchedRW.TheDef->getLoc(), "No variant of this type has a "
1219 "matching predicate on any processor ");
1220 // Now expand each variant on top of its copy of the transition.
1221 for (std::vector<TransVariant>::const_iterator
1222 IVI = IntersectingVariants.begin(),
1223 IVE = IntersectingVariants.end();
1224 IVI != IVE; ++IVI) {
1225 pushVariant(*IVI, IsRead);
1231 // For each variant of a Read/Write in Trans, substitute the sequence of
1232 // Read/Writes guarded by the variant. This is exponential in the number of
1233 // variant Read/Writes, but in practice detection of mutually exclusive
1234 // predicates should result in linear growth in the total number variants.
1236 // This is one step in a breadth-first search of nested variants.
1237 void PredTransitions::substituteVariants(const PredTransition &Trans) {
1238 // Build up a set of partial results starting at the back of
1239 // PredTransitions. Remember the first new transition.
1240 unsigned StartIdx = TransVec.size();
1241 TransVec.resize(TransVec.size() + 1);
1242 TransVec.back().PredTerm = Trans.PredTerm;
1243 TransVec.back().ProcIndices = Trans.ProcIndices;
1245 // Visit each original write sequence.
1246 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1247 WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end();
1248 WSI != WSE; ++WSI) {
1249 // Push a new (empty) write sequence onto all partial Transitions.
1250 for (std::vector<PredTransition>::iterator I =
1251 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1252 I->WriteSequences.resize(I->WriteSequences.size() + 1);
1254 substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx);
1256 // Visit each original read sequence.
1257 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1258 RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end();
1259 RSI != RSE; ++RSI) {
1260 // Push a new (empty) read sequence onto all partial Transitions.
1261 for (std::vector<PredTransition>::iterator I =
1262 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1263 I->ReadSequences.resize(I->ReadSequences.size() + 1);
1265 substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx);
1269 // Create a new SchedClass for each variant found by inferFromRW. Pass
1270 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions,
1271 unsigned FromClassIdx,
1272 CodeGenSchedModels &SchedModels) {
1273 // For each PredTransition, create a new CodeGenSchedTransition, which usually
1274 // requires creating a new SchedClass.
1275 for (ArrayRef<PredTransition>::iterator
1276 I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) {
1277 IdxVec OperWritesVariant;
1278 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1279 WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end();
1280 WSI != WSE; ++WSI) {
1281 // Create a new write representing the expanded sequence.
1282 OperWritesVariant.push_back(
1283 SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false));
1285 IdxVec OperReadsVariant;
1286 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1287 RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end();
1288 RSI != RSE; ++RSI) {
1289 // Create a new read representing the expanded sequence.
1290 OperReadsVariant.push_back(
1291 SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true));
1293 IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end());
1294 CodeGenSchedTransition SCTrans;
1295 SCTrans.ToClassIdx =
1296 SchedModels.addSchedClass(OperWritesVariant, OperReadsVariant,
1298 SCTrans.ProcIndices = ProcIndices;
1299 // The final PredTerm is unique set of predicates guarding the transition.
1301 for (SmallVectorImpl<PredCheck>::const_iterator
1302 PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) {
1303 Preds.push_back(PI->Predicate);
1305 RecIter PredsEnd = std::unique(Preds.begin(), Preds.end());
1306 Preds.resize(PredsEnd - Preds.begin());
1307 SCTrans.PredTerm = Preds;
1308 SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans);
1312 // Create new SchedClasses for the given ReadWrite list. If any of the
1313 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant
1314 // of the ReadWrite list, following Aliases if necessary.
1315 void CodeGenSchedModels::inferFromRW(const IdxVec &OperWrites,
1316 const IdxVec &OperReads,
1317 unsigned FromClassIdx,
1318 const IdxVec &ProcIndices) {
1319 DEBUG(dbgs() << "INFER RW: ");
1321 // Create a seed transition with an empty PredTerm and the expanded sequences
1322 // of SchedWrites for the current SchedClass.
1323 std::vector<PredTransition> LastTransitions;
1324 LastTransitions.resize(1);
1325 LastTransitions.back().ProcIndices.append(ProcIndices.begin(),
1328 for (IdxIter I = OperWrites.begin(), E = OperWrites.end(); I != E; ++I) {
1330 expandRWSequence(*I, WriteSeq, /*IsRead=*/false);
1331 unsigned Idx = LastTransitions[0].WriteSequences.size();
1332 LastTransitions[0].WriteSequences.resize(Idx + 1);
1333 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx];
1334 for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI)
1336 DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1338 DEBUG(dbgs() << " Reads: ");
1339 for (IdxIter I = OperReads.begin(), E = OperReads.end(); I != E; ++I) {
1341 expandRWSequence(*I, ReadSeq, /*IsRead=*/true);
1342 unsigned Idx = LastTransitions[0].ReadSequences.size();
1343 LastTransitions[0].ReadSequences.resize(Idx + 1);
1344 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx];
1345 for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI)
1347 DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1349 DEBUG(dbgs() << '\n');
1351 // Collect all PredTransitions for individual operands.
1352 // Iterate until no variant writes remain.
1353 while (hasVariant(LastTransitions, *this)) {
1354 PredTransitions Transitions(*this);
1355 for (std::vector<PredTransition>::const_iterator
1356 I = LastTransitions.begin(), E = LastTransitions.end();
1358 Transitions.substituteVariants(*I);
1360 DEBUG(Transitions.dump());
1361 LastTransitions.swap(Transitions.TransVec);
1363 // If the first transition has no variants, nothing to do.
1364 if (LastTransitions[0].PredTerm.empty())
1367 // WARNING: We are about to mutate the SchedClasses vector. Do not refer to
1368 // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions.
1369 inferFromTransitions(LastTransitions, FromClassIdx, *this);
1372 // Collect and sort WriteRes, ReadAdvance, and ProcResources.
1373 void CodeGenSchedModels::collectProcResources() {
1374 // Add any subtarget-specific SchedReadWrites that are directly associated
1375 // with processor resources. Refer to the parent SchedClass's ProcIndices to
1376 // determine which processors they apply to.
1377 for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd();
1378 SCI != SCE; ++SCI) {
1379 if (SCI->ItinClassDef)
1380 collectItinProcResources(SCI->ItinClassDef);
1382 collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices);
1384 // Add resources separately defined by each subtarget.
1385 RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes");
1386 for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) {
1387 Record *ModelDef = (*WRI)->getValueAsDef("SchedModel");
1388 addWriteRes(*WRI, getProcModel(ModelDef).Index);
1390 RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance");
1391 for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) {
1392 Record *ModelDef = (*RAI)->getValueAsDef("SchedModel");
1393 addReadAdvance(*RAI, getProcModel(ModelDef).Index);
1395 // Finalize each ProcModel by sorting the record arrays.
1396 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
1397 CodeGenProcModel &PM = ProcModels[PIdx];
1398 std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(),
1400 std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(),
1402 std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(),
1406 dbgs() << "WriteResDefs: ";
1407 for (RecIter RI = PM.WriteResDefs.begin(),
1408 RE = PM.WriteResDefs.end(); RI != RE; ++RI) {
1409 if ((*RI)->isSubClassOf("WriteRes"))
1410 dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " ";
1412 dbgs() << (*RI)->getName() << " ";
1414 dbgs() << "\nReadAdvanceDefs: ";
1415 for (RecIter RI = PM.ReadAdvanceDefs.begin(),
1416 RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) {
1417 if ((*RI)->isSubClassOf("ReadAdvance"))
1418 dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " ";
1420 dbgs() << (*RI)->getName() << " ";
1422 dbgs() << "\nProcResourceDefs: ";
1423 for (RecIter RI = PM.ProcResourceDefs.begin(),
1424 RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) {
1425 dbgs() << (*RI)->getName() << " ";
1431 // Collect itinerary class resources for each processor.
1432 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) {
1433 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
1434 const CodeGenProcModel &PM = ProcModels[PIdx];
1435 // For all ItinRW entries.
1436 bool HasMatch = false;
1437 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
1439 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
1440 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
1443 throw TGError((*II)->getLoc(), "Duplicate itinerary class "
1444 + ItinClassDef->getName()
1445 + " in ItinResources for " + PM.ModelName);
1447 IdxVec Writes, Reads;
1448 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
1449 IdxVec ProcIndices(1, PIdx);
1450 collectRWResources(Writes, Reads, ProcIndices);
1455 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead,
1456 const IdxVec &ProcIndices) {
1457 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
1458 if (SchedRW.TheDef) {
1459 if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) {
1460 for (IdxIter PI = ProcIndices.begin(), PE = ProcIndices.end();
1462 addWriteRes(SchedRW.TheDef, *PI);
1465 else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) {
1466 for (IdxIter PI = ProcIndices.begin(), PE = ProcIndices.end();
1468 addReadAdvance(SchedRW.TheDef, *PI);
1472 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1474 IdxVec AliasProcIndices;
1475 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1476 AliasProcIndices.push_back(
1477 getProcModel((*AI)->getValueAsDef("SchedModel")).Index);
1480 AliasProcIndices = ProcIndices;
1481 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
1482 assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes");
1485 expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead);
1486 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
1488 collectRWResources(*SI, IsRead, AliasProcIndices);
1493 // Collect resources for a set of read/write types and processor indices.
1494 void CodeGenSchedModels::collectRWResources(const IdxVec &Writes,
1495 const IdxVec &Reads,
1496 const IdxVec &ProcIndices) {
1498 for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI)
1499 collectRWResources(*WI, /*IsRead=*/false, ProcIndices);
1501 for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI)
1502 collectRWResources(*RI, /*IsRead=*/true, ProcIndices);
1506 // Find the processor's resource units for this kind of resource.
1507 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind,
1508 const CodeGenProcModel &PM) const {
1509 if (ProcResKind->isSubClassOf("ProcResourceUnits"))
1512 Record *ProcUnitDef = 0;
1513 RecVec ProcResourceDefs =
1514 Records.getAllDerivedDefinitions("ProcResourceUnits");
1516 for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end();
1519 if ((*RI)->getValueAsDef("Kind") == ProcResKind
1520 && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) {
1522 throw TGError((*RI)->getLoc(),
1523 "Multiple ProcessorResourceUnits associated with "
1524 + ProcResKind->getName());
1530 throw TGError(ProcResKind->getLoc(),
1531 "No ProcessorResources associated with "
1532 + ProcResKind->getName());
1537 // Iteratively add a resource and its super resources.
1538 void CodeGenSchedModels::addProcResource(Record *ProcResKind,
1539 CodeGenProcModel &PM) {
1541 Record *ProcResUnits = findProcResUnits(ProcResKind, PM);
1543 // See if this ProcResource is already associated with this processor.
1544 RecIter I = std::find(PM.ProcResourceDefs.begin(),
1545 PM.ProcResourceDefs.end(), ProcResUnits);
1546 if (I != PM.ProcResourceDefs.end())
1549 PM.ProcResourceDefs.push_back(ProcResUnits);
1550 if (!ProcResUnits->getValueInit("Super")->isComplete())
1553 ProcResKind = ProcResUnits->getValueAsDef("Super");
1557 // Add resources for a SchedWrite to this processor if they don't exist.
1558 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) {
1559 assert(PIdx && "don't add resources to an invalid Processor model");
1561 RecVec &WRDefs = ProcModels[PIdx].WriteResDefs;
1562 RecIter WRI = std::find(WRDefs.begin(), WRDefs.end(), ProcWriteResDef);
1563 if (WRI != WRDefs.end())
1565 WRDefs.push_back(ProcWriteResDef);
1567 // Visit ProcResourceKinds referenced by the newly discovered WriteRes.
1568 RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources");
1569 for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end();
1570 WritePRI != WritePRE; ++WritePRI) {
1571 addProcResource(*WritePRI, ProcModels[PIdx]);
1575 // Add resources for a ReadAdvance to this processor if they don't exist.
1576 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef,
1578 RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs;
1579 RecIter I = std::find(RADefs.begin(), RADefs.end(), ProcReadAdvanceDef);
1580 if (I != RADefs.end())
1582 RADefs.push_back(ProcReadAdvanceDef);
1585 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const {
1586 RecIter PRPos = std::find(ProcResourceDefs.begin(), ProcResourceDefs.end(),
1588 if (PRPos == ProcResourceDefs.end())
1589 throw TGError(PRDef->getLoc(), "ProcResource def is not included in "
1590 "the ProcResources list for " + ModelName);
1591 // Idx=0 is reserved for invalid.
1592 return 1 + PRPos - ProcResourceDefs.begin();
1596 void CodeGenProcModel::dump() const {
1597 dbgs() << Index << ": " << ModelName << " "
1598 << (ModelDef ? ModelDef->getName() : "inferred") << " "
1599 << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
1602 void CodeGenSchedRW::dump() const {
1603 dbgs() << Name << (IsVariadic ? " (V) " : " ");
1606 dumpIdxVec(Sequence);
1611 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const {
1612 dbgs() << "SCHEDCLASS " << Name << '\n'
1614 for (unsigned i = 0, N = Writes.size(); i < N; ++i) {
1615 SchedModels->getSchedWrite(Writes[i]).dump();
1621 dbgs() << "\n Reads: ";
1622 for (unsigned i = 0, N = Reads.size(); i < N; ++i) {
1623 SchedModels->getSchedRead(Reads[i]).dump();
1629 dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n';
1632 void PredTransitions::dump() const {
1633 dbgs() << "Expanded Variants:\n";
1634 for (std::vector<PredTransition>::const_iterator
1635 TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) {
1637 for (SmallVectorImpl<PredCheck>::const_iterator
1638 PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end();
1639 PCI != PCE; ++PCI) {
1640 if (PCI != TI->PredTerm.begin())
1642 dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name
1643 << ":" << PCI->Predicate->getName();
1645 dbgs() << "},\n => {";
1646 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1647 WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end();
1648 WSI != WSE; ++WSI) {
1650 for (SmallVectorImpl<unsigned>::const_iterator
1651 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
1652 if (WI != WSI->begin())
1654 dbgs() << SchedModels.getSchedWrite(*WI).Name;