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 described in
11 // the target description.
13 //===----------------------------------------------------------------------===//
15 #include "CodeGenInstruction.h"
16 #include "CodeGenSchedule.h"
17 #include "CodeGenTarget.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include "llvm/Support/Regex.h"
26 #include "llvm/TableGen/Error.h"
33 #define DEBUG_TYPE "subtarget-emitter"
36 static void dumpIdxVec(ArrayRef<unsigned> V) {
37 for (unsigned Idx : V)
38 dbgs() << Idx << ", ";
44 // (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp.
45 struct InstrsOp : public SetTheory::Operator {
46 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
47 ArrayRef<SMLoc> Loc) override {
48 ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc);
52 // (instregex "OpcPat",...) Find all instructions matching an opcode pattern.
54 // TODO: Since this is a prefix match, perform a binary search over the
55 // instruction names using lower_bound. Note that the predefined instrs must be
56 // scanned linearly first. However, this is only safe if the regex pattern has
57 // no top-level bars. The DAG already has a list of patterns, so there's no
58 // reason to use top-level bars, but we need a way to verify they don't exist
59 // before implementing the optimization.
60 struct InstRegexOp : public SetTheory::Operator {
61 const CodeGenTarget &Target;
62 InstRegexOp(const CodeGenTarget &t): Target(t) {}
64 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
65 ArrayRef<SMLoc> Loc) override {
66 SmallVector<Regex, 4> RegexList;
67 for (DagInit::const_arg_iterator
68 AI = Expr->arg_begin(), AE = Expr->arg_end(); AI != AE; ++AI) {
69 StringInit *SI = dyn_cast<StringInit>(*AI);
71 PrintFatalError(Loc, "instregex requires pattern string: "
72 + Expr->getAsString());
73 std::string pat = SI->getValue();
74 // Implement a python-style prefix match.
77 pat.insert(pat.end(), ')');
79 RegexList.push_back(Regex(pat));
81 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
82 for (auto &R : RegexList) {
83 if (R.match(Inst->TheDef->getName()))
84 Elts.insert(Inst->TheDef);
90 } // end anonymous namespace
92 /// CodeGenModels ctor interprets machine model records and populates maps.
93 CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
94 const CodeGenTarget &TGT):
95 Records(RK), Target(TGT) {
97 Sets.addFieldExpander("InstRW", "Instrs");
99 // Allow Set evaluation to recognize the dags used in InstRW records:
100 // (instrs Op1, Op1...)
101 Sets.addOperator("instrs", llvm::make_unique<InstrsOp>());
102 Sets.addOperator("instregex", llvm::make_unique<InstRegexOp>(Target));
104 // Instantiate a CodeGenProcModel for each SchedMachineModel with the values
105 // that are explicitly referenced in tablegen records. Resources associated
106 // with each processor will be derived later. Populate ProcModelMap with the
107 // CodeGenProcModel instances.
110 // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly
111 // defined, and populate SchedReads and SchedWrites vectors. Implicit
112 // SchedReadWrites that represent sequences derived from expanded variant will
113 // be inferred later.
116 // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly
117 // required by an instruction definition, and populate SchedClassIdxMap. Set
118 // NumItineraryClasses to the number of explicit itinerary classes referenced
119 // by instructions. Set NumInstrSchedClasses to the number of itinerary
120 // classes plus any classes implied by instructions that derive from class
121 // Sched and provide SchedRW list. This does not infer any new classes from
123 collectSchedClasses();
125 // Find instruction itineraries for each processor. Sort and populate
126 // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires
127 // all itinerary classes to be discovered.
130 // Find ItinRW records for each processor and itinerary class.
131 // (For per-operand resources mapped to itinerary classes).
134 // Find UnsupportedFeatures records for each processor.
135 // (For per-operand resources mapped to itinerary classes).
136 collectProcUnsupportedFeatures();
138 // Infer new SchedClasses from SchedVariant.
141 // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and
143 DEBUG(dbgs() << "\n+++ RESOURCE DEFINITIONS (collectProcResources) +++\n");
144 collectProcResources();
149 /// Gather all processor models.
150 void CodeGenSchedModels::collectProcModels() {
151 RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor");
152 std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName());
154 // Reserve space because we can. Reallocation would be ok.
155 ProcModels.reserve(ProcRecords.size()+1);
157 // Use idx=0 for NoModel/NoItineraries.
158 Record *NoModelDef = Records.getDef("NoSchedModel");
159 Record *NoItinsDef = Records.getDef("NoItineraries");
160 ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef);
161 ProcModelMap[NoModelDef] = 0;
163 // For each processor, find a unique machine model.
164 DEBUG(dbgs() << "+++ PROCESSOR MODELs (addProcModel) +++\n");
165 for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i)
166 addProcModel(ProcRecords[i]);
169 /// Get a unique processor model based on the defined MachineModel and
170 /// ProcessorItineraries.
171 void CodeGenSchedModels::addProcModel(Record *ProcDef) {
172 Record *ModelKey = getModelOrItinDef(ProcDef);
173 if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second)
176 std::string Name = ModelKey->getName();
177 if (ModelKey->isSubClassOf("SchedMachineModel")) {
178 Record *ItinsDef = ModelKey->getValueAsDef("Itineraries");
179 ProcModels.emplace_back(ProcModels.size(), Name, ModelKey, ItinsDef);
182 // An itinerary is defined without a machine model. Infer a new model.
183 if (!ModelKey->getValueAsListOfDefs("IID").empty())
184 Name = Name + "Model";
185 ProcModels.emplace_back(ProcModels.size(), Name,
186 ProcDef->getValueAsDef("SchedModel"), ModelKey);
188 DEBUG(ProcModels.back().dump());
191 // Recursively find all reachable SchedReadWrite records.
192 static void scanSchedRW(Record *RWDef, RecVec &RWDefs,
193 SmallPtrSet<Record*, 16> &RWSet) {
194 if (!RWSet.insert(RWDef).second)
196 RWDefs.push_back(RWDef);
197 // Reads don't current have sequence records, but it can be added later.
198 if (RWDef->isSubClassOf("WriteSequence")) {
199 RecVec Seq = RWDef->getValueAsListOfDefs("Writes");
200 for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I)
201 scanSchedRW(*I, RWDefs, RWSet);
203 else if (RWDef->isSubClassOf("SchedVariant")) {
204 // Visit each variant (guarded by a different predicate).
205 RecVec Vars = RWDef->getValueAsListOfDefs("Variants");
206 for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) {
207 // Visit each RW in the sequence selected by the current variant.
208 RecVec Selected = (*VI)->getValueAsListOfDefs("Selected");
209 for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I)
210 scanSchedRW(*I, RWDefs, RWSet);
215 // Collect and sort all SchedReadWrites reachable via tablegen records.
216 // More may be inferred later when inferring new SchedClasses from variants.
217 void CodeGenSchedModels::collectSchedRW() {
218 // Reserve idx=0 for invalid writes/reads.
219 SchedWrites.resize(1);
220 SchedReads.resize(1);
222 SmallPtrSet<Record*, 16> RWSet;
224 // Find all SchedReadWrites referenced by instruction defs.
225 RecVec SWDefs, SRDefs;
226 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
227 Record *SchedDef = Inst->TheDef;
228 if (SchedDef->isValueUnset("SchedRW"))
230 RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW");
231 for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) {
232 if ((*RWI)->isSubClassOf("SchedWrite"))
233 scanSchedRW(*RWI, SWDefs, RWSet);
235 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
236 scanSchedRW(*RWI, SRDefs, RWSet);
240 // Find all ReadWrites referenced by InstRW.
241 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
242 for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) {
243 // For all OperandReadWrites.
244 RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites");
245 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
247 if ((*RWI)->isSubClassOf("SchedWrite"))
248 scanSchedRW(*RWI, SWDefs, RWSet);
250 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
251 scanSchedRW(*RWI, SRDefs, RWSet);
255 // Find all ReadWrites referenced by ItinRW.
256 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
257 for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
258 // For all OperandReadWrites.
259 RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites");
260 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
262 if ((*RWI)->isSubClassOf("SchedWrite"))
263 scanSchedRW(*RWI, SWDefs, RWSet);
265 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
266 scanSchedRW(*RWI, SRDefs, RWSet);
270 // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted
271 // for the loop below that initializes Alias vectors.
272 RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias");
273 std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord());
274 for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) {
275 Record *MatchDef = (*AI)->getValueAsDef("MatchRW");
276 Record *AliasDef = (*AI)->getValueAsDef("AliasRW");
277 if (MatchDef->isSubClassOf("SchedWrite")) {
278 if (!AliasDef->isSubClassOf("SchedWrite"))
279 PrintFatalError((*AI)->getLoc(), "SchedWrite Alias must be SchedWrite");
280 scanSchedRW(AliasDef, SWDefs, RWSet);
283 assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
284 if (!AliasDef->isSubClassOf("SchedRead"))
285 PrintFatalError((*AI)->getLoc(), "SchedRead Alias must be SchedRead");
286 scanSchedRW(AliasDef, SRDefs, RWSet);
289 // Sort and add the SchedReadWrites directly referenced by instructions or
290 // itinerary resources. Index reads and writes in separate domains.
291 std::sort(SWDefs.begin(), SWDefs.end(), LessRecord());
292 for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) {
293 assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite");
294 SchedWrites.emplace_back(SchedWrites.size(), *SWI);
296 std::sort(SRDefs.begin(), SRDefs.end(), LessRecord());
297 for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) {
298 assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite");
299 SchedReads.emplace_back(SchedReads.size(), *SRI);
301 // Initialize WriteSequence vectors.
302 for (std::vector<CodeGenSchedRW>::iterator WI = SchedWrites.begin(),
303 WE = SchedWrites.end(); WI != WE; ++WI) {
306 findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence,
309 // Initialize Aliases vectors.
310 for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) {
311 Record *AliasDef = (*AI)->getValueAsDef("AliasRW");
312 getSchedRW(AliasDef).IsAlias = true;
313 Record *MatchDef = (*AI)->getValueAsDef("MatchRW");
314 CodeGenSchedRW &RW = getSchedRW(MatchDef);
316 PrintFatalError((*AI)->getLoc(), "Cannot Alias an Alias");
317 RW.Aliases.push_back(*AI);
320 dbgs() << "\n+++ SCHED READS and WRITES (collectSchedRW) +++\n";
321 for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) {
322 dbgs() << WIdx << ": ";
323 SchedWrites[WIdx].dump();
326 for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) {
327 dbgs() << RIdx << ": ";
328 SchedReads[RIdx].dump();
331 RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite");
332 for (RecIter RI = RWDefs.begin(), RE = RWDefs.end();
334 if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) {
335 const std::string &Name = (*RI)->getName();
336 if (Name != "NoWrite" && Name != "ReadDefault")
337 dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n';
342 /// Compute a SchedWrite name from a sequence of writes.
343 std::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) {
344 std::string Name("(");
345 for (auto I = Seq.begin(), E = Seq.end(); I != E; ++I) {
346 if (I != Seq.begin())
348 Name += getSchedRW(*I, IsRead).Name;
354 unsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead,
355 unsigned After) const {
356 const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
357 assert(After < RWVec.size() && "start position out of bounds");
358 for (std::vector<CodeGenSchedRW>::const_iterator I = RWVec.begin() + After,
359 E = RWVec.end(); I != E; ++I) {
360 if (I->TheDef == Def)
361 return I - RWVec.begin();
366 bool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const {
367 for (unsigned i = 0, e = SchedReads.size(); i < e; ++i) {
368 Record *ReadDef = SchedReads[i].TheDef;
369 if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance"))
372 RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites");
373 if (is_contained(ValidWrites, WriteDef)) {
382 void splitSchedReadWrites(const RecVec &RWDefs,
383 RecVec &WriteDefs, RecVec &ReadDefs) {
384 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) {
385 if ((*RWI)->isSubClassOf("SchedWrite"))
386 WriteDefs.push_back(*RWI);
388 assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite");
389 ReadDefs.push_back(*RWI);
394 } // end namespace llvm
396 // Split the SchedReadWrites defs and call findRWs for each list.
397 void CodeGenSchedModels::findRWs(const RecVec &RWDefs,
398 IdxVec &Writes, IdxVec &Reads) const {
401 splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs);
402 findRWs(WriteDefs, Writes, false);
403 findRWs(ReadDefs, Reads, true);
406 // Call getSchedRWIdx for all elements in a sequence of SchedRW defs.
407 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs,
409 for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) {
410 unsigned Idx = getSchedRWIdx(*RI, IsRead);
411 assert(Idx && "failed to collect SchedReadWrite");
416 void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq,
418 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
419 if (!SchedRW.IsSequence) {
420 RWSeq.push_back(RWIdx);
424 SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1;
425 for (int i = 0; i < Repeat; ++i) {
426 for (IdxIter I = SchedRW.Sequence.begin(), E = SchedRW.Sequence.end();
428 expandRWSequence(*I, RWSeq, IsRead);
433 // Expand a SchedWrite as a sequence following any aliases that coincide with
434 // the given processor model.
435 void CodeGenSchedModels::expandRWSeqForProc(
436 unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
437 const CodeGenProcModel &ProcModel) const {
439 const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead);
440 Record *AliasDef = nullptr;
441 for (RecIter AI = SchedWrite.Aliases.begin(), AE = SchedWrite.Aliases.end();
443 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
444 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
445 Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
446 if (&getProcModel(ModelDef) != &ProcModel)
450 PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases "
451 "defined for processor " + ProcModel.ModelName +
452 " Ensure only one SchedAlias exists per RW.");
453 AliasDef = AliasRW.TheDef;
456 expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead),
457 RWSeq, IsRead,ProcModel);
460 if (!SchedWrite.IsSequence) {
461 RWSeq.push_back(RWIdx);
465 SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1;
466 for (int i = 0; i < Repeat; ++i) {
467 for (IdxIter I = SchedWrite.Sequence.begin(), E = SchedWrite.Sequence.end();
469 expandRWSeqForProc(*I, RWSeq, IsRead, ProcModel);
474 // Find the existing SchedWrite that models this sequence of writes.
475 unsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq,
477 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
479 for (std::vector<CodeGenSchedRW>::iterator I = RWVec.begin(), E = RWVec.end();
481 if (makeArrayRef(I->Sequence) == Seq)
482 return I - RWVec.begin();
484 // Index zero reserved for invalid RW.
488 /// Add this ReadWrite if it doesn't already exist.
489 unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq,
491 assert(!Seq.empty() && "cannot insert empty sequence");
495 unsigned Idx = findRWForSequence(Seq, IsRead);
499 unsigned RWIdx = IsRead ? SchedReads.size() : SchedWrites.size();
500 CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead));
502 SchedReads.push_back(SchedRW);
504 SchedWrites.push_back(SchedRW);
508 /// Visit all the instruction definitions for this target to gather and
509 /// enumerate the itinerary classes. These are the explicitly specified
510 /// SchedClasses. More SchedClasses may be inferred.
511 void CodeGenSchedModels::collectSchedClasses() {
513 // NoItinerary is always the first class at Idx=0
514 SchedClasses.resize(1);
515 SchedClasses.back().Index = 0;
516 SchedClasses.back().Name = "NoInstrModel";
517 SchedClasses.back().ItinClassDef = Records.getDef("NoItinerary");
518 SchedClasses.back().ProcIndices.push_back(0);
520 // Create a SchedClass for each unique combination of itinerary class and
522 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
523 Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary");
524 IdxVec Writes, Reads;
525 if (!Inst->TheDef->isValueUnset("SchedRW"))
526 findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
528 // ProcIdx == 0 indicates the class applies to all processors.
529 IdxVec ProcIndices(1, 0);
531 unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, ProcIndices);
532 InstrClassMap[Inst->TheDef] = SCIdx;
534 // Create classes for InstRW defs.
535 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
536 std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord());
537 DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n");
538 for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI)
539 createInstRWClass(*OI);
541 NumInstrSchedClasses = SchedClasses.size();
543 bool EnableDump = false;
544 DEBUG(EnableDump = true);
548 dbgs() << "\n+++ ITINERARIES and/or MACHINE MODELS (collectSchedClasses) +++\n";
549 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
550 StringRef InstName = Inst->TheDef->getName();
551 unsigned SCIdx = InstrClassMap.lookup(Inst->TheDef);
553 if (!Inst->hasNoSchedulingInfo)
554 dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n';
557 CodeGenSchedClass &SC = getSchedClass(SCIdx);
558 if (SC.ProcIndices[0] != 0)
559 PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class "
560 "must not be subtarget specific.");
563 if (SC.ItinClassDef->getName() != "NoItinerary") {
564 ProcIndices.push_back(0);
565 dbgs() << "Itinerary for " << InstName << ": "
566 << SC.ItinClassDef->getName() << '\n';
568 if (!SC.Writes.empty()) {
569 ProcIndices.push_back(0);
570 dbgs() << "SchedRW machine model for " << InstName;
571 for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE; ++WI)
572 dbgs() << " " << SchedWrites[*WI].Name;
573 for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI)
574 dbgs() << " " << SchedReads[*RI].Name;
577 const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs;
578 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
580 const CodeGenProcModel &ProcModel =
581 getProcModel((*RWI)->getValueAsDef("SchedModel"));
582 ProcIndices.push_back(ProcModel.Index);
583 dbgs() << "InstRW on " << ProcModel.ModelName << " for " << InstName;
586 findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"),
588 for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI)
589 dbgs() << " " << SchedWrites[*WI].Name;
590 for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI)
591 dbgs() << " " << SchedReads[*RI].Name;
594 // If ProcIndices contains zero, the class applies to all processors.
595 if (!std::count(ProcIndices.begin(), ProcIndices.end(), 0)) {
596 for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(),
597 PE = ProcModels.end(); PI != PE; ++PI) {
598 if (!std::count(ProcIndices.begin(), ProcIndices.end(), PI->Index))
599 dbgs() << "No machine model for " << Inst->TheDef->getName()
600 << " on processor " << PI->ModelName << '\n';
606 /// Find an SchedClass that has been inferred from a per-operand list of
607 /// SchedWrites and SchedReads.
608 unsigned CodeGenSchedModels::findSchedClassIdx(Record *ItinClassDef,
609 ArrayRef<unsigned> Writes,
610 ArrayRef<unsigned> Reads) const {
611 for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) {
612 if (I->ItinClassDef == ItinClassDef && makeArrayRef(I->Writes) == Writes &&
613 makeArrayRef(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 return InstrClassMap.lookup(Inst.TheDef);
628 CodeGenSchedModels::createSchedClassName(Record *ItinClassDef,
629 ArrayRef<unsigned> OperWrites,
630 ArrayRef<unsigned> OperReads) {
633 if (ItinClassDef && ItinClassDef->getName() != "NoItinerary")
634 Name = ItinClassDef->getName();
635 for (unsigned Idx : OperWrites) {
638 Name += SchedWrites[Idx].Name;
640 for (unsigned Idx : OperReads) {
642 Name += SchedReads[Idx].Name;
647 std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) {
650 for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) {
651 if (I != InstDefs.begin())
653 Name += (*I)->getName();
658 /// Add an inferred sched class from an itinerary class and per-operand list of
659 /// SchedWrites and SchedReads. ProcIndices contains the set of IDs of
660 /// processors that may utilize this class.
661 unsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef,
662 ArrayRef<unsigned> OperWrites,
663 ArrayRef<unsigned> OperReads,
664 ArrayRef<unsigned> ProcIndices) {
665 assert(!ProcIndices.empty() && "expect at least one ProcIdx");
667 unsigned Idx = findSchedClassIdx(ItinClassDef, OperWrites, OperReads);
668 if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) {
670 std::set_union(SchedClasses[Idx].ProcIndices.begin(),
671 SchedClasses[Idx].ProcIndices.end(),
672 ProcIndices.begin(), ProcIndices.end(),
673 std::back_inserter(PI));
674 SchedClasses[Idx].ProcIndices.swap(PI);
677 Idx = SchedClasses.size();
678 SchedClasses.resize(Idx+1);
679 CodeGenSchedClass &SC = SchedClasses.back();
681 SC.Name = createSchedClassName(ItinClassDef, OperWrites, OperReads);
682 SC.ItinClassDef = ItinClassDef;
683 SC.Writes = OperWrites;
684 SC.Reads = OperReads;
685 SC.ProcIndices = ProcIndices;
690 // Create classes for each set of opcodes that are in the same InstReadWrite
691 // definition across all processors.
692 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) {
693 // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that
694 // intersects with an existing class via a previous InstRWDef. Instrs that do
695 // not intersect with an existing class refer back to their former class as
696 // determined from ItinDef or SchedRW.
697 SmallVector<std::pair<unsigned, SmallVector<Record *, 8>>, 4> ClassInstrs;
698 // Sort Instrs into sets.
699 const RecVec *InstDefs = Sets.expand(InstRWDef);
700 if (InstDefs->empty())
701 PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes");
703 for (RecIter I = InstDefs->begin(), E = InstDefs->end(); I != E; ++I) {
704 InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I);
705 if (Pos == InstrClassMap.end())
706 PrintFatalError((*I)->getLoc(), "No sched class for instruction.");
707 unsigned SCIdx = Pos->second;
708 unsigned CIdx = 0, CEnd = ClassInstrs.size();
709 for (; CIdx != CEnd; ++CIdx) {
710 if (ClassInstrs[CIdx].first == SCIdx)
714 ClassInstrs.resize(CEnd + 1);
715 ClassInstrs[CIdx].first = SCIdx;
717 ClassInstrs[CIdx].second.push_back(*I);
719 // For each set of Instrs, create a new class if necessary, and map or remap
721 unsigned CIdx = 0, CEnd = ClassInstrs.size();
722 for (; CIdx != CEnd; ++CIdx) {
723 unsigned OldSCIdx = ClassInstrs[CIdx].first;
724 ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second;
725 // If the all instrs in the current class are accounted for, then leave
726 // them mapped to their old class.
728 const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs;
729 if (!RWDefs.empty()) {
730 const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]);
731 unsigned OrigNumInstrs = 0;
732 for (RecIter I = OrigInstDefs->begin(), E = OrigInstDefs->end();
734 if (InstrClassMap[*I] == OldSCIdx)
737 if (OrigNumInstrs == InstDefs.size()) {
738 assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 &&
739 "expected a generic SchedClass");
740 DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":"
741 << SchedClasses[OldSCIdx].Name << " on "
742 << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n");
743 SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef);
748 unsigned SCIdx = SchedClasses.size();
749 SchedClasses.resize(SCIdx+1);
750 CodeGenSchedClass &SC = SchedClasses.back();
752 SC.Name = createSchedClassName(InstDefs);
753 DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on "
754 << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n");
756 // Preserve ItinDef and Writes/Reads for processors without an InstRW entry.
757 SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef;
758 SC.Writes = SchedClasses[OldSCIdx].Writes;
759 SC.Reads = SchedClasses[OldSCIdx].Reads;
760 SC.ProcIndices.push_back(0);
761 // Map each Instr to this new class.
762 // Note that InstDefs may be a smaller list than InstRWDef's "Instrs".
763 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel");
764 SmallSet<unsigned, 4> RemappedClassIDs;
765 for (ArrayRef<Record*>::const_iterator
766 II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) {
767 unsigned OldSCIdx = InstrClassMap[*II];
768 if (OldSCIdx && RemappedClassIDs.insert(OldSCIdx).second) {
769 for (RecIter RI = SchedClasses[OldSCIdx].InstRWs.begin(),
770 RE = SchedClasses[OldSCIdx].InstRWs.end(); RI != RE; ++RI) {
771 if ((*RI)->getValueAsDef("SchedModel") == RWModelDef) {
772 PrintFatalError(InstRWDef->getLoc(), "Overlapping InstRW def " +
773 (*II)->getName() + " also matches " +
774 (*RI)->getValue("Instrs")->getValue()->getAsString());
776 assert(*RI != InstRWDef && "SchedClass has duplicate InstRW def");
777 SC.InstRWs.push_back(*RI);
780 InstrClassMap[*II] = SCIdx;
782 SC.InstRWs.push_back(InstRWDef);
786 // True if collectProcItins found anything.
787 bool CodeGenSchedModels::hasItineraries() const {
788 for (CodeGenSchedModels::ProcIter PI = procModelBegin(), PE = procModelEnd();
790 if (PI->hasItineraries())
796 // Gather the processor itineraries.
797 void CodeGenSchedModels::collectProcItins() {
798 DEBUG(dbgs() << "\n+++ PROBLEM ITINERARIES (collectProcItins) +++\n");
799 for (CodeGenProcModel &ProcModel : ProcModels) {
800 if (!ProcModel.hasItineraries())
803 RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID");
804 assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect");
806 // Populate ItinDefList with Itinerary records.
807 ProcModel.ItinDefList.resize(NumInstrSchedClasses);
809 // Insert each itinerary data record in the correct position within
810 // the processor model's ItinDefList.
811 for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) {
812 Record *ItinData = ItinRecords[i];
813 Record *ItinDef = ItinData->getValueAsDef("TheClass");
814 bool FoundClass = false;
815 for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd();
817 // Multiple SchedClasses may share an itinerary. Update all of them.
818 if (SCI->ItinClassDef == ItinDef) {
819 ProcModel.ItinDefList[SCI->Index] = ItinData;
824 DEBUG(dbgs() << ProcModel.ItinsDef->getName()
825 << " missing class for itinerary " << ItinDef->getName() << '\n');
828 // Check for missing itinerary entries.
829 assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec");
831 for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) {
832 if (!ProcModel.ItinDefList[i])
833 dbgs() << ProcModel.ItinsDef->getName()
834 << " missing itinerary for class "
835 << SchedClasses[i].Name << '\n';
840 // Gather the read/write types for each itinerary class.
841 void CodeGenSchedModels::collectProcItinRW() {
842 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
843 std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord());
844 for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
845 if (!(*II)->getValueInit("SchedModel")->isComplete())
846 PrintFatalError((*II)->getLoc(), "SchedModel is undefined");
847 Record *ModelDef = (*II)->getValueAsDef("SchedModel");
848 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
849 if (I == ProcModelMap.end()) {
850 PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel "
851 + ModelDef->getName());
853 ProcModels[I->second].ItinRWDefs.push_back(*II);
857 // Gather the unsupported features for processor models.
858 void CodeGenSchedModels::collectProcUnsupportedFeatures() {
859 for (CodeGenProcModel &ProcModel : ProcModels) {
860 for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) {
861 ProcModel.UnsupportedFeaturesDefs.push_back(Pred);
866 /// Infer new classes from existing classes. In the process, this may create new
867 /// SchedWrites from sequences of existing SchedWrites.
868 void CodeGenSchedModels::inferSchedClasses() {
869 DEBUG(dbgs() << "\n+++ INFERRING SCHED CLASSES (inferSchedClasses) +++\n");
870 DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n");
872 // Visit all existing classes and newly created classes.
873 for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) {
874 assert(SchedClasses[Idx].Index == Idx && "bad SCIdx");
876 if (SchedClasses[Idx].ItinClassDef)
877 inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx);
878 if (!SchedClasses[Idx].InstRWs.empty())
879 inferFromInstRWs(Idx);
880 if (!SchedClasses[Idx].Writes.empty()) {
881 inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads,
882 Idx, SchedClasses[Idx].ProcIndices);
884 assert(SchedClasses.size() < (NumInstrSchedClasses*6) &&
885 "too many SchedVariants");
889 /// Infer classes from per-processor itinerary resources.
890 void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef,
891 unsigned FromClassIdx) {
892 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
893 const CodeGenProcModel &PM = ProcModels[PIdx];
894 // For all ItinRW entries.
895 bool HasMatch = false;
896 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
898 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
899 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
902 PrintFatalError((*II)->getLoc(), "Duplicate itinerary class "
903 + ItinClassDef->getName()
904 + " in ItinResources for " + PM.ModelName);
906 IdxVec Writes, Reads;
907 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
908 IdxVec ProcIndices(1, PIdx);
909 inferFromRW(Writes, Reads, FromClassIdx, ProcIndices);
914 /// Infer classes from per-processor InstReadWrite definitions.
915 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) {
916 for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) {
917 assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!");
918 Record *Rec = SchedClasses[SCIdx].InstRWs[I];
919 const RecVec *InstDefs = Sets.expand(Rec);
920 RecIter II = InstDefs->begin(), IE = InstDefs->end();
921 for (; II != IE; ++II) {
922 if (InstrClassMap[*II] == SCIdx)
925 // If this class no longer has any instructions mapped to it, it has become
929 IdxVec Writes, Reads;
930 findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
931 unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index;
932 IdxVec ProcIndices(1, PIdx);
933 inferFromRW(Writes, Reads, SCIdx, ProcIndices); // May mutate SchedClasses.
939 // Helper for substituteVariantOperand.
940 struct TransVariant {
941 Record *VarOrSeqDef; // Variant or sequence.
942 unsigned RWIdx; // Index of this variant or sequence's matched type.
943 unsigned ProcIdx; // Processor model index or zero for any.
944 unsigned TransVecIdx; // Index into PredTransitions::TransVec.
946 TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti):
947 VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {}
950 // Associate a predicate with the SchedReadWrite that it guards.
951 // RWIdx is the index of the read/write variant.
957 PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {}
960 // A Predicate transition is a list of RW sequences guarded by a PredTerm.
961 struct PredTransition {
962 // A predicate term is a conjunction of PredChecks.
963 SmallVector<PredCheck, 4> PredTerm;
964 SmallVector<SmallVector<unsigned,4>, 16> WriteSequences;
965 SmallVector<SmallVector<unsigned,4>, 16> ReadSequences;
966 SmallVector<unsigned, 4> ProcIndices;
969 // Encapsulate a set of partially constructed transitions.
970 // The results are built by repeated calls to substituteVariants.
971 class PredTransitions {
972 CodeGenSchedModels &SchedModels;
975 std::vector<PredTransition> TransVec;
977 PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {}
979 void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq,
980 bool IsRead, unsigned StartIdx);
982 void substituteVariants(const PredTransition &Trans);
989 bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term);
990 void getIntersectingVariants(
991 const CodeGenSchedRW &SchedRW, unsigned TransIdx,
992 std::vector<TransVariant> &IntersectingVariants);
993 void pushVariant(const TransVariant &VInfo, bool IsRead);
996 } // end anonymous namespace
998 // Return true if this predicate is mutually exclusive with a PredTerm. This
999 // degenerates into checking if the predicate is mutually exclusive with any
1000 // predicate in the Term's conjunction.
1002 // All predicates associated with a given SchedRW are considered mutually
1003 // exclusive. This should work even if the conditions expressed by the
1004 // predicates are not exclusive because the predicates for a given SchedWrite
1005 // are always checked in the order they are defined in the .td file. Later
1006 // conditions implicitly negate any prior condition.
1007 bool PredTransitions::mutuallyExclusive(Record *PredDef,
1008 ArrayRef<PredCheck> Term) {
1009 for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end();
1011 if (I->Predicate == PredDef)
1014 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead);
1015 assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant");
1016 RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants");
1017 for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) {
1018 if ((*VI)->getValueAsDef("Predicate") == PredDef)
1025 static bool hasAliasedVariants(const CodeGenSchedRW &RW,
1026 CodeGenSchedModels &SchedModels) {
1030 for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) {
1031 const CodeGenSchedRW &AliasRW =
1032 SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW"));
1033 if (AliasRW.HasVariants)
1035 if (AliasRW.IsSequence) {
1037 SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead);
1038 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
1040 if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead),
1050 static bool hasVariant(ArrayRef<PredTransition> Transitions,
1051 CodeGenSchedModels &SchedModels) {
1052 for (ArrayRef<PredTransition>::iterator
1053 PTI = Transitions.begin(), PTE = Transitions.end();
1054 PTI != PTE; ++PTI) {
1055 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1056 WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end();
1057 WSI != WSE; ++WSI) {
1058 for (SmallVectorImpl<unsigned>::const_iterator
1059 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
1060 if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels))
1064 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1065 RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end();
1066 RSI != RSE; ++RSI) {
1067 for (SmallVectorImpl<unsigned>::const_iterator
1068 RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) {
1069 if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels))
1077 // Populate IntersectingVariants with any variants or aliased sequences of the
1078 // given SchedRW whose processor indices and predicates are not mutually
1079 // exclusive with the given transition.
1080 void PredTransitions::getIntersectingVariants(
1081 const CodeGenSchedRW &SchedRW, unsigned TransIdx,
1082 std::vector<TransVariant> &IntersectingVariants) {
1084 bool GenericRW = false;
1086 std::vector<TransVariant> Variants;
1087 if (SchedRW.HasVariants) {
1088 unsigned VarProcIdx = 0;
1089 if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) {
1090 Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel");
1091 VarProcIdx = SchedModels.getProcModel(ModelDef).Index;
1093 // Push each variant. Assign TransVecIdx later.
1094 const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants");
1095 for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
1096 Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0));
1097 if (VarProcIdx == 0)
1100 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1102 // If either the SchedAlias itself or the SchedReadWrite that it aliases
1103 // to is defined within a processor model, constrain all variants to
1105 unsigned AliasProcIdx = 0;
1106 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1107 Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
1108 AliasProcIdx = SchedModels.getProcModel(ModelDef).Index;
1110 const CodeGenSchedRW &AliasRW =
1111 SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW"));
1113 if (AliasRW.HasVariants) {
1114 const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants");
1115 for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
1116 Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0));
1118 if (AliasRW.IsSequence) {
1120 TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0));
1122 if (AliasProcIdx == 0)
1125 for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) {
1126 TransVariant &Variant = Variants[VIdx];
1127 // Don't expand variants if the processor models don't intersect.
1128 // A zero processor index means any processor.
1129 SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices;
1130 if (ProcIndices[0] && Variants[VIdx].ProcIdx) {
1131 unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(),
1136 const CodeGenProcModel &PM =
1137 *(SchedModels.procModelBegin() + Variant.ProcIdx);
1138 PrintFatalError(Variant.VarOrSeqDef->getLoc(),
1139 "Multiple variants defined for processor " +
1141 " Ensure only one SchedAlias exists per RW.");
1144 if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) {
1145 Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate");
1146 if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm))
1149 if (IntersectingVariants.empty()) {
1150 // The first variant builds on the existing transition.
1151 Variant.TransVecIdx = TransIdx;
1152 IntersectingVariants.push_back(Variant);
1155 // Push another copy of the current transition for more variants.
1156 Variant.TransVecIdx = TransVec.size();
1157 IntersectingVariants.push_back(Variant);
1158 TransVec.push_back(TransVec[TransIdx]);
1161 if (GenericRW && IntersectingVariants.empty()) {
1162 PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has "
1163 "a matching predicate on any processor");
1167 // Push the Reads/Writes selected by this variant onto the PredTransition
1168 // specified by VInfo.
1169 void PredTransitions::
1170 pushVariant(const TransVariant &VInfo, bool IsRead) {
1171 PredTransition &Trans = TransVec[VInfo.TransVecIdx];
1173 // If this operand transition is reached through a processor-specific alias,
1174 // then the whole transition is specific to this processor.
1175 if (VInfo.ProcIdx != 0)
1176 Trans.ProcIndices.assign(1, VInfo.ProcIdx);
1179 if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) {
1180 Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate");
1181 Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef));
1182 RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected");
1183 SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead);
1186 assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") &&
1187 "variant must be a SchedVariant or aliased WriteSequence");
1188 SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead));
1191 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead);
1193 SmallVectorImpl<SmallVector<unsigned,4>> &RWSequences = IsRead
1194 ? Trans.ReadSequences : Trans.WriteSequences;
1195 if (SchedRW.IsVariadic) {
1196 unsigned OperIdx = RWSequences.size()-1;
1197 // Make N-1 copies of this transition's last sequence.
1198 for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) {
1199 // Create a temporary copy the vector could reallocate.
1200 RWSequences.reserve(RWSequences.size() + 1);
1201 RWSequences.push_back(RWSequences[OperIdx]);
1203 // Push each of the N elements of the SelectedRWs onto a copy of the last
1204 // sequence (split the current operand into N operands).
1205 // Note that write sequences should be expanded within this loop--the entire
1206 // sequence belongs to a single operand.
1207 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1208 RWI != RWE; ++RWI, ++OperIdx) {
1211 ExpandedRWs.push_back(*RWI);
1213 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1214 RWSequences[OperIdx].insert(RWSequences[OperIdx].end(),
1215 ExpandedRWs.begin(), ExpandedRWs.end());
1217 assert(OperIdx == RWSequences.size() && "missed a sequence");
1220 // Push this transition's expanded sequence onto this transition's last
1221 // sequence (add to the current operand's sequence).
1222 SmallVectorImpl<unsigned> &Seq = RWSequences.back();
1224 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1225 RWI != RWE; ++RWI) {
1227 ExpandedRWs.push_back(*RWI);
1229 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1231 Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end());
1235 // RWSeq is a sequence of all Reads or all Writes for the next read or write
1236 // operand. StartIdx is an index into TransVec where partial results
1237 // starts. RWSeq must be applied to all transitions between StartIdx and the end
1239 void PredTransitions::substituteVariantOperand(
1240 const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) {
1242 // Visit each original RW within the current sequence.
1243 for (SmallVectorImpl<unsigned>::const_iterator
1244 RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) {
1245 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead);
1246 // Push this RW on all partial PredTransitions or distribute variants.
1247 // New PredTransitions may be pushed within this loop which should not be
1248 // revisited (TransEnd must be loop invariant).
1249 for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size();
1250 TransIdx != TransEnd; ++TransIdx) {
1251 // In the common case, push RW onto the current operand's sequence.
1252 if (!hasAliasedVariants(SchedRW, SchedModels)) {
1254 TransVec[TransIdx].ReadSequences.back().push_back(*RWI);
1256 TransVec[TransIdx].WriteSequences.back().push_back(*RWI);
1259 // Distribute this partial PredTransition across intersecting variants.
1260 // This will push a copies of TransVec[TransIdx] on the back of TransVec.
1261 std::vector<TransVariant> IntersectingVariants;
1262 getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants);
1263 // Now expand each variant on top of its copy of the transition.
1264 for (std::vector<TransVariant>::const_iterator
1265 IVI = IntersectingVariants.begin(),
1266 IVE = IntersectingVariants.end();
1267 IVI != IVE; ++IVI) {
1268 pushVariant(*IVI, IsRead);
1274 // For each variant of a Read/Write in Trans, substitute the sequence of
1275 // Read/Writes guarded by the variant. This is exponential in the number of
1276 // variant Read/Writes, but in practice detection of mutually exclusive
1277 // predicates should result in linear growth in the total number variants.
1279 // This is one step in a breadth-first search of nested variants.
1280 void PredTransitions::substituteVariants(const PredTransition &Trans) {
1281 // Build up a set of partial results starting at the back of
1282 // PredTransitions. Remember the first new transition.
1283 unsigned StartIdx = TransVec.size();
1284 TransVec.resize(TransVec.size() + 1);
1285 TransVec.back().PredTerm = Trans.PredTerm;
1286 TransVec.back().ProcIndices = Trans.ProcIndices;
1288 // Visit each original write sequence.
1289 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1290 WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end();
1291 WSI != WSE; ++WSI) {
1292 // Push a new (empty) write sequence onto all partial Transitions.
1293 for (std::vector<PredTransition>::iterator I =
1294 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1295 I->WriteSequences.resize(I->WriteSequences.size() + 1);
1297 substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx);
1299 // Visit each original read sequence.
1300 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1301 RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end();
1302 RSI != RSE; ++RSI) {
1303 // Push a new (empty) read sequence onto all partial Transitions.
1304 for (std::vector<PredTransition>::iterator I =
1305 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1306 I->ReadSequences.resize(I->ReadSequences.size() + 1);
1308 substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx);
1312 // Create a new SchedClass for each variant found by inferFromRW. Pass
1313 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions,
1314 unsigned FromClassIdx,
1315 CodeGenSchedModels &SchedModels) {
1316 // For each PredTransition, create a new CodeGenSchedTransition, which usually
1317 // requires creating a new SchedClass.
1318 for (ArrayRef<PredTransition>::iterator
1319 I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) {
1320 IdxVec OperWritesVariant;
1321 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1322 WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end();
1323 WSI != WSE; ++WSI) {
1324 // Create a new write representing the expanded sequence.
1325 OperWritesVariant.push_back(
1326 SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false));
1328 IdxVec OperReadsVariant;
1329 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1330 RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end();
1331 RSI != RSE; ++RSI) {
1332 // Create a new read representing the expanded sequence.
1333 OperReadsVariant.push_back(
1334 SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true));
1336 IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end());
1337 CodeGenSchedTransition SCTrans;
1338 SCTrans.ToClassIdx =
1339 SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant,
1340 OperReadsVariant, ProcIndices);
1341 SCTrans.ProcIndices = ProcIndices;
1342 // The final PredTerm is unique set of predicates guarding the transition.
1344 for (SmallVectorImpl<PredCheck>::const_iterator
1345 PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) {
1346 Preds.push_back(PI->Predicate);
1348 RecIter PredsEnd = std::unique(Preds.begin(), Preds.end());
1349 Preds.resize(PredsEnd - Preds.begin());
1350 SCTrans.PredTerm = Preds;
1351 SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans);
1355 // Create new SchedClasses for the given ReadWrite list. If any of the
1356 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant
1357 // of the ReadWrite list, following Aliases if necessary.
1358 void CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites,
1359 ArrayRef<unsigned> OperReads,
1360 unsigned FromClassIdx,
1361 ArrayRef<unsigned> ProcIndices) {
1362 DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); dbgs() << ") ");
1364 // Create a seed transition with an empty PredTerm and the expanded sequences
1365 // of SchedWrites for the current SchedClass.
1366 std::vector<PredTransition> LastTransitions;
1367 LastTransitions.resize(1);
1368 LastTransitions.back().ProcIndices.append(ProcIndices.begin(),
1371 for (unsigned WriteIdx : OperWrites) {
1373 expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false);
1374 unsigned Idx = LastTransitions[0].WriteSequences.size();
1375 LastTransitions[0].WriteSequences.resize(Idx + 1);
1376 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx];
1377 for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI)
1379 DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1381 DEBUG(dbgs() << " Reads: ");
1382 for (unsigned ReadIdx : OperReads) {
1384 expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true);
1385 unsigned Idx = LastTransitions[0].ReadSequences.size();
1386 LastTransitions[0].ReadSequences.resize(Idx + 1);
1387 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx];
1388 for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI)
1390 DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1392 DEBUG(dbgs() << '\n');
1394 // Collect all PredTransitions for individual operands.
1395 // Iterate until no variant writes remain.
1396 while (hasVariant(LastTransitions, *this)) {
1397 PredTransitions Transitions(*this);
1398 for (std::vector<PredTransition>::const_iterator
1399 I = LastTransitions.begin(), E = LastTransitions.end();
1401 Transitions.substituteVariants(*I);
1403 DEBUG(Transitions.dump());
1404 LastTransitions.swap(Transitions.TransVec);
1406 // If the first transition has no variants, nothing to do.
1407 if (LastTransitions[0].PredTerm.empty())
1410 // WARNING: We are about to mutate the SchedClasses vector. Do not refer to
1411 // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions.
1412 inferFromTransitions(LastTransitions, FromClassIdx, *this);
1415 // Check if any processor resource group contains all resource records in
1417 bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) {
1418 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
1419 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
1422 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
1423 RecIter RI = SubUnits.begin(), RE = SubUnits.end();
1424 for ( ; RI != RE; ++RI) {
1425 if (!is_contained(SuperUnits, *RI)) {
1435 // Verify that overlapping groups have a common supergroup.
1436 void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) {
1437 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
1438 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
1441 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
1442 for (unsigned j = i+1; j < e; ++j) {
1443 if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup"))
1446 PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources");
1447 if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(),
1448 OtherUnits.begin(), OtherUnits.end())
1449 != CheckUnits.end()) {
1450 // CheckUnits and OtherUnits overlap
1451 OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(),
1453 if (!hasSuperGroup(OtherUnits, PM)) {
1454 PrintFatalError((PM.ProcResourceDefs[i])->getLoc(),
1455 "proc resource group overlaps with "
1456 + PM.ProcResourceDefs[j]->getName()
1457 + " but no supergroup contains both.");
1464 // Collect and sort WriteRes, ReadAdvance, and ProcResources.
1465 void CodeGenSchedModels::collectProcResources() {
1466 ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits");
1467 ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
1469 // Add any subtarget-specific SchedReadWrites that are directly associated
1470 // with processor resources. Refer to the parent SchedClass's ProcIndices to
1471 // determine which processors they apply to.
1472 for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd();
1473 SCI != SCE; ++SCI) {
1474 if (SCI->ItinClassDef)
1475 collectItinProcResources(SCI->ItinClassDef);
1477 // This class may have a default ReadWrite list which can be overriden by
1478 // InstRW definitions.
1479 if (!SCI->InstRWs.empty()) {
1480 for (RecIter RWI = SCI->InstRWs.begin(), RWE = SCI->InstRWs.end();
1481 RWI != RWE; ++RWI) {
1482 Record *RWModelDef = (*RWI)->getValueAsDef("SchedModel");
1483 IdxVec ProcIndices(1, getProcModel(RWModelDef).Index);
1484 IdxVec Writes, Reads;
1485 findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"),
1487 collectRWResources(Writes, Reads, ProcIndices);
1490 collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices);
1493 // Add resources separately defined by each subtarget.
1494 RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes");
1495 for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) {
1496 Record *ModelDef = (*WRI)->getValueAsDef("SchedModel");
1497 addWriteRes(*WRI, getProcModel(ModelDef).Index);
1499 RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes");
1500 for (RecIter WRI = SWRDefs.begin(), WRE = SWRDefs.end(); WRI != WRE; ++WRI) {
1501 Record *ModelDef = (*WRI)->getValueAsDef("SchedModel");
1502 addWriteRes(*WRI, getProcModel(ModelDef).Index);
1504 RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance");
1505 for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) {
1506 Record *ModelDef = (*RAI)->getValueAsDef("SchedModel");
1507 addReadAdvance(*RAI, getProcModel(ModelDef).Index);
1509 RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance");
1510 for (RecIter RAI = SRADefs.begin(), RAE = SRADefs.end(); RAI != RAE; ++RAI) {
1511 if ((*RAI)->getValueInit("SchedModel")->isComplete()) {
1512 Record *ModelDef = (*RAI)->getValueAsDef("SchedModel");
1513 addReadAdvance(*RAI, getProcModel(ModelDef).Index);
1516 // Add ProcResGroups that are defined within this processor model, which may
1517 // not be directly referenced but may directly specify a buffer size.
1518 RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
1519 for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end();
1521 if (!(*RI)->getValueInit("SchedModel")->isComplete())
1523 CodeGenProcModel &PM = getProcModel((*RI)->getValueAsDef("SchedModel"));
1524 if (!is_contained(PM.ProcResourceDefs, *RI))
1525 PM.ProcResourceDefs.push_back(*RI);
1527 // Finalize each ProcModel by sorting the record arrays.
1528 for (CodeGenProcModel &PM : ProcModels) {
1529 std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(),
1531 std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(),
1533 std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(),
1537 dbgs() << "WriteResDefs: ";
1538 for (RecIter RI = PM.WriteResDefs.begin(),
1539 RE = PM.WriteResDefs.end(); RI != RE; ++RI) {
1540 if ((*RI)->isSubClassOf("WriteRes"))
1541 dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " ";
1543 dbgs() << (*RI)->getName() << " ";
1545 dbgs() << "\nReadAdvanceDefs: ";
1546 for (RecIter RI = PM.ReadAdvanceDefs.begin(),
1547 RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) {
1548 if ((*RI)->isSubClassOf("ReadAdvance"))
1549 dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " ";
1551 dbgs() << (*RI)->getName() << " ";
1553 dbgs() << "\nProcResourceDefs: ";
1554 for (RecIter RI = PM.ProcResourceDefs.begin(),
1555 RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) {
1556 dbgs() << (*RI)->getName() << " ";
1559 verifyProcResourceGroups(PM);
1562 ProcResourceDefs.clear();
1563 ProcResGroups.clear();
1566 void CodeGenSchedModels::checkCompleteness() {
1567 bool Complete = true;
1568 bool HadCompleteModel = false;
1569 for (const CodeGenProcModel &ProcModel : procModels()) {
1570 if (!ProcModel.ModelDef->getValueAsBit("CompleteModel"))
1572 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
1573 if (Inst->hasNoSchedulingInfo)
1575 if (ProcModel.isUnsupported(*Inst))
1577 unsigned SCIdx = getSchedClassIdx(*Inst);
1579 if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) {
1580 PrintError("No schedule information for instruction '"
1581 + Inst->TheDef->getName() + "'");
1587 const CodeGenSchedClass &SC = getSchedClass(SCIdx);
1588 if (!SC.Writes.empty())
1590 if (SC.ItinClassDef != nullptr &&
1591 SC.ItinClassDef->getName() != "NoItinerary")
1594 const RecVec &InstRWs = SC.InstRWs;
1595 auto I = find_if(InstRWs, [&ProcModel](const Record *R) {
1596 return R->getValueAsDef("SchedModel") == ProcModel.ModelDef;
1598 if (I == InstRWs.end()) {
1599 PrintError("'" + ProcModel.ModelName + "' lacks information for '" +
1600 Inst->TheDef->getName() + "'");
1604 HadCompleteModel = true;
1607 errs() << "\n\nIncomplete schedule models found.\n"
1608 << "- Consider setting 'CompleteModel = 0' while developing new models.\n"
1609 << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n"
1610 << "- Instructions should usually have Sched<[...]> as a superclass, "
1611 "you may temporarily use an empty list.\n"
1612 << "- Instructions related to unsupported features can be excluded with "
1613 "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the "
1614 "processor model.\n\n";
1615 PrintFatalError("Incomplete schedule model");
1619 // Collect itinerary class resources for each processor.
1620 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) {
1621 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
1622 const CodeGenProcModel &PM = ProcModels[PIdx];
1623 // For all ItinRW entries.
1624 bool HasMatch = false;
1625 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
1627 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
1628 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
1631 PrintFatalError((*II)->getLoc(), "Duplicate itinerary class "
1632 + ItinClassDef->getName()
1633 + " in ItinResources for " + PM.ModelName);
1635 IdxVec Writes, Reads;
1636 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
1637 IdxVec ProcIndices(1, PIdx);
1638 collectRWResources(Writes, Reads, ProcIndices);
1643 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead,
1644 ArrayRef<unsigned> ProcIndices) {
1645 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
1646 if (SchedRW.TheDef) {
1647 if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) {
1648 for (unsigned Idx : ProcIndices)
1649 addWriteRes(SchedRW.TheDef, Idx);
1651 else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) {
1652 for (unsigned Idx : ProcIndices)
1653 addReadAdvance(SchedRW.TheDef, Idx);
1656 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1658 IdxVec AliasProcIndices;
1659 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1660 AliasProcIndices.push_back(
1661 getProcModel((*AI)->getValueAsDef("SchedModel")).Index);
1664 AliasProcIndices = ProcIndices;
1665 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
1666 assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes");
1669 expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead);
1670 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
1672 collectRWResources(*SI, IsRead, AliasProcIndices);
1677 // Collect resources for a set of read/write types and processor indices.
1678 void CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes,
1679 ArrayRef<unsigned> Reads,
1680 ArrayRef<unsigned> ProcIndices) {
1681 for (unsigned Idx : Writes)
1682 collectRWResources(Idx, /*IsRead=*/false, ProcIndices);
1684 for (unsigned Idx : Reads)
1685 collectRWResources(Idx, /*IsRead=*/true, ProcIndices);
1688 // Find the processor's resource units for this kind of resource.
1689 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind,
1690 const CodeGenProcModel &PM) const {
1691 if (ProcResKind->isSubClassOf("ProcResourceUnits"))
1694 Record *ProcUnitDef = nullptr;
1695 assert(!ProcResourceDefs.empty());
1696 assert(!ProcResGroups.empty());
1698 for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end();
1701 if ((*RI)->getValueAsDef("Kind") == ProcResKind
1702 && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) {
1704 PrintFatalError((*RI)->getLoc(),
1705 "Multiple ProcessorResourceUnits associated with "
1706 + ProcResKind->getName());
1711 for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end();
1714 if (*RI == ProcResKind
1715 && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) {
1717 PrintFatalError((*RI)->getLoc(),
1718 "Multiple ProcessorResourceUnits associated with "
1719 + ProcResKind->getName());
1725 PrintFatalError(ProcResKind->getLoc(),
1726 "No ProcessorResources associated with "
1727 + ProcResKind->getName());
1732 // Iteratively add a resource and its super resources.
1733 void CodeGenSchedModels::addProcResource(Record *ProcResKind,
1734 CodeGenProcModel &PM) {
1736 Record *ProcResUnits = findProcResUnits(ProcResKind, PM);
1738 // See if this ProcResource is already associated with this processor.
1739 if (is_contained(PM.ProcResourceDefs, ProcResUnits))
1742 PM.ProcResourceDefs.push_back(ProcResUnits);
1743 if (ProcResUnits->isSubClassOf("ProcResGroup"))
1746 if (!ProcResUnits->getValueInit("Super")->isComplete())
1749 ProcResKind = ProcResUnits->getValueAsDef("Super");
1753 // Add resources for a SchedWrite to this processor if they don't exist.
1754 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) {
1755 assert(PIdx && "don't add resources to an invalid Processor model");
1757 RecVec &WRDefs = ProcModels[PIdx].WriteResDefs;
1758 if (is_contained(WRDefs, ProcWriteResDef))
1760 WRDefs.push_back(ProcWriteResDef);
1762 // Visit ProcResourceKinds referenced by the newly discovered WriteRes.
1763 RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources");
1764 for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end();
1765 WritePRI != WritePRE; ++WritePRI) {
1766 addProcResource(*WritePRI, ProcModels[PIdx]);
1770 // Add resources for a ReadAdvance to this processor if they don't exist.
1771 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef,
1773 RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs;
1774 if (is_contained(RADefs, ProcReadAdvanceDef))
1776 RADefs.push_back(ProcReadAdvanceDef);
1779 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const {
1780 RecIter PRPos = find(ProcResourceDefs, PRDef);
1781 if (PRPos == ProcResourceDefs.end())
1782 PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in "
1783 "the ProcResources list for " + ModelName);
1784 // Idx=0 is reserved for invalid.
1785 return 1 + (PRPos - ProcResourceDefs.begin());
1788 bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const {
1789 for (const Record *TheDef : UnsupportedFeaturesDefs) {
1790 for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) {
1791 if (TheDef->getName() == PredDef->getName())
1799 void CodeGenProcModel::dump() const {
1800 dbgs() << Index << ": " << ModelName << " "
1801 << (ModelDef ? ModelDef->getName() : "inferred") << " "
1802 << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
1805 void CodeGenSchedRW::dump() const {
1806 dbgs() << Name << (IsVariadic ? " (V) " : " ");
1809 dumpIdxVec(Sequence);
1814 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const {
1815 dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n'
1817 for (unsigned i = 0, N = Writes.size(); i < N; ++i) {
1818 SchedModels->getSchedWrite(Writes[i]).dump();
1824 dbgs() << "\n Reads: ";
1825 for (unsigned i = 0, N = Reads.size(); i < N; ++i) {
1826 SchedModels->getSchedRead(Reads[i]).dump();
1832 dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n';
1833 if (!Transitions.empty()) {
1834 dbgs() << "\n Transitions for Proc ";
1835 for (std::vector<CodeGenSchedTransition>::const_iterator
1836 TI = Transitions.begin(), TE = Transitions.end(); TI != TE; ++TI) {
1837 dumpIdxVec(TI->ProcIndices);
1842 void PredTransitions::dump() const {
1843 dbgs() << "Expanded Variants:\n";
1844 for (std::vector<PredTransition>::const_iterator
1845 TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) {
1847 for (SmallVectorImpl<PredCheck>::const_iterator
1848 PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end();
1849 PCI != PCE; ++PCI) {
1850 if (PCI != TI->PredTerm.begin())
1852 dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name
1853 << ":" << PCI->Predicate->getName();
1855 dbgs() << "},\n => {";
1856 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1857 WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end();
1858 WSI != WSE; ++WSI) {
1860 for (SmallVectorImpl<unsigned>::const_iterator
1861 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
1862 if (WI != WSI->begin())
1864 dbgs() << SchedModels.getSchedWrite(*WI).Name;