• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines structures to encapsulate the machine model as described in
11 // the target description.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "CodeGenSchedule.h"
16 #include "CodeGenTarget.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/Regex.h"
20 #include "llvm/TableGen/Error.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "subtarget-emitter"
25 
26 #ifndef NDEBUG
dumpIdxVec(ArrayRef<unsigned> V)27 static void dumpIdxVec(ArrayRef<unsigned> V) {
28   for (unsigned Idx : V)
29     dbgs() << Idx << ", ";
30 }
31 #endif
32 
33 namespace {
34 // (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp.
35 struct InstrsOp : public SetTheory::Operator {
apply__anon4cc2b93e0111::InstrsOp36   void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
37              ArrayRef<SMLoc> Loc) override {
38     ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc);
39   }
40 };
41 
42 // (instregex "OpcPat",...) Find all instructions matching an opcode pattern.
43 //
44 // TODO: Since this is a prefix match, perform a binary search over the
45 // instruction names using lower_bound. Note that the predefined instrs must be
46 // scanned linearly first. However, this is only safe if the regex pattern has
47 // no top-level bars. The DAG already has a list of patterns, so there's no
48 // reason to use top-level bars, but we need a way to verify they don't exist
49 // before implementing the optimization.
50 struct InstRegexOp : public SetTheory::Operator {
51   const CodeGenTarget &Target;
InstRegexOp__anon4cc2b93e0111::InstRegexOp52   InstRegexOp(const CodeGenTarget &t): Target(t) {}
53 
apply__anon4cc2b93e0111::InstRegexOp54   void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
55              ArrayRef<SMLoc> Loc) override {
56     SmallVector<Regex, 4> RegexList;
57     for (DagInit::const_arg_iterator
58            AI = Expr->arg_begin(), AE = Expr->arg_end(); AI != AE; ++AI) {
59       StringInit *SI = dyn_cast<StringInit>(*AI);
60       if (!SI)
61         PrintFatalError(Loc, "instregex requires pattern string: "
62           + Expr->getAsString());
63       std::string pat = SI->getValue();
64       // Implement a python-style prefix match.
65       if (pat[0] != '^') {
66         pat.insert(0, "^(");
67         pat.insert(pat.end(), ')');
68       }
69       RegexList.push_back(Regex(pat));
70     }
71     for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
72       for (auto &R : RegexList) {
73         if (R.match(Inst->TheDef->getName()))
74           Elts.insert(Inst->TheDef);
75       }
76     }
77   }
78 };
79 } // end anonymous namespace
80 
81 /// CodeGenModels ctor interprets machine model records and populates maps.
CodeGenSchedModels(RecordKeeper & RK,const CodeGenTarget & TGT)82 CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
83                                        const CodeGenTarget &TGT):
84   Records(RK), Target(TGT) {
85 
86   Sets.addFieldExpander("InstRW", "Instrs");
87 
88   // Allow Set evaluation to recognize the dags used in InstRW records:
89   // (instrs Op1, Op1...)
90   Sets.addOperator("instrs", llvm::make_unique<InstrsOp>());
91   Sets.addOperator("instregex", llvm::make_unique<InstRegexOp>(Target));
92 
93   // Instantiate a CodeGenProcModel for each SchedMachineModel with the values
94   // that are explicitly referenced in tablegen records. Resources associated
95   // with each processor will be derived later. Populate ProcModelMap with the
96   // CodeGenProcModel instances.
97   collectProcModels();
98 
99   // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly
100   // defined, and populate SchedReads and SchedWrites vectors. Implicit
101   // SchedReadWrites that represent sequences derived from expanded variant will
102   // be inferred later.
103   collectSchedRW();
104 
105   // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly
106   // required by an instruction definition, and populate SchedClassIdxMap. Set
107   // NumItineraryClasses to the number of explicit itinerary classes referenced
108   // by instructions. Set NumInstrSchedClasses to the number of itinerary
109   // classes plus any classes implied by instructions that derive from class
110   // Sched and provide SchedRW list. This does not infer any new classes from
111   // SchedVariant.
112   collectSchedClasses();
113 
114   // Find instruction itineraries for each processor. Sort and populate
115   // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires
116   // all itinerary classes to be discovered.
117   collectProcItins();
118 
119   // Find ItinRW records for each processor and itinerary class.
120   // (For per-operand resources mapped to itinerary classes).
121   collectProcItinRW();
122 
123   // Find UnsupportedFeatures records for each processor.
124   // (For per-operand resources mapped to itinerary classes).
125   collectProcUnsupportedFeatures();
126 
127   // Infer new SchedClasses from SchedVariant.
128   inferSchedClasses();
129 
130   // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and
131   // ProcResourceDefs.
132   collectProcResources();
133 
134   checkCompleteness();
135 }
136 
137 /// Gather all processor models.
collectProcModels()138 void CodeGenSchedModels::collectProcModels() {
139   RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor");
140   std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName());
141 
142   // Reserve space because we can. Reallocation would be ok.
143   ProcModels.reserve(ProcRecords.size()+1);
144 
145   // Use idx=0 for NoModel/NoItineraries.
146   Record *NoModelDef = Records.getDef("NoSchedModel");
147   Record *NoItinsDef = Records.getDef("NoItineraries");
148   ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef);
149   ProcModelMap[NoModelDef] = 0;
150 
151   // For each processor, find a unique machine model.
152   for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i)
153     addProcModel(ProcRecords[i]);
154 }
155 
156 /// Get a unique processor model based on the defined MachineModel and
157 /// ProcessorItineraries.
addProcModel(Record * ProcDef)158 void CodeGenSchedModels::addProcModel(Record *ProcDef) {
159   Record *ModelKey = getModelOrItinDef(ProcDef);
160   if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second)
161     return;
162 
163   std::string Name = ModelKey->getName();
164   if (ModelKey->isSubClassOf("SchedMachineModel")) {
165     Record *ItinsDef = ModelKey->getValueAsDef("Itineraries");
166     ProcModels.emplace_back(ProcModels.size(), Name, ModelKey, ItinsDef);
167   }
168   else {
169     // An itinerary is defined without a machine model. Infer a new model.
170     if (!ModelKey->getValueAsListOfDefs("IID").empty())
171       Name = Name + "Model";
172     ProcModels.emplace_back(ProcModels.size(), Name,
173                             ProcDef->getValueAsDef("SchedModel"), ModelKey);
174   }
175   DEBUG(ProcModels.back().dump());
176 }
177 
178 // Recursively find all reachable SchedReadWrite records.
scanSchedRW(Record * RWDef,RecVec & RWDefs,SmallPtrSet<Record *,16> & RWSet)179 static void scanSchedRW(Record *RWDef, RecVec &RWDefs,
180                         SmallPtrSet<Record*, 16> &RWSet) {
181   if (!RWSet.insert(RWDef).second)
182     return;
183   RWDefs.push_back(RWDef);
184   // Reads don't current have sequence records, but it can be added later.
185   if (RWDef->isSubClassOf("WriteSequence")) {
186     RecVec Seq = RWDef->getValueAsListOfDefs("Writes");
187     for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I)
188       scanSchedRW(*I, RWDefs, RWSet);
189   }
190   else if (RWDef->isSubClassOf("SchedVariant")) {
191     // Visit each variant (guarded by a different predicate).
192     RecVec Vars = RWDef->getValueAsListOfDefs("Variants");
193     for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) {
194       // Visit each RW in the sequence selected by the current variant.
195       RecVec Selected = (*VI)->getValueAsListOfDefs("Selected");
196       for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I)
197         scanSchedRW(*I, RWDefs, RWSet);
198     }
199   }
200 }
201 
202 // Collect and sort all SchedReadWrites reachable via tablegen records.
203 // More may be inferred later when inferring new SchedClasses from variants.
collectSchedRW()204 void CodeGenSchedModels::collectSchedRW() {
205   // Reserve idx=0 for invalid writes/reads.
206   SchedWrites.resize(1);
207   SchedReads.resize(1);
208 
209   SmallPtrSet<Record*, 16> RWSet;
210 
211   // Find all SchedReadWrites referenced by instruction defs.
212   RecVec SWDefs, SRDefs;
213   for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
214     Record *SchedDef = Inst->TheDef;
215     if (SchedDef->isValueUnset("SchedRW"))
216       continue;
217     RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW");
218     for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) {
219       if ((*RWI)->isSubClassOf("SchedWrite"))
220         scanSchedRW(*RWI, SWDefs, RWSet);
221       else {
222         assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
223         scanSchedRW(*RWI, SRDefs, RWSet);
224       }
225     }
226   }
227   // Find all ReadWrites referenced by InstRW.
228   RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
229   for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) {
230     // For all OperandReadWrites.
231     RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites");
232     for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
233          RWI != RWE; ++RWI) {
234       if ((*RWI)->isSubClassOf("SchedWrite"))
235         scanSchedRW(*RWI, SWDefs, RWSet);
236       else {
237         assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
238         scanSchedRW(*RWI, SRDefs, RWSet);
239       }
240     }
241   }
242   // Find all ReadWrites referenced by ItinRW.
243   RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
244   for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
245     // For all OperandReadWrites.
246     RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites");
247     for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
248          RWI != RWE; ++RWI) {
249       if ((*RWI)->isSubClassOf("SchedWrite"))
250         scanSchedRW(*RWI, SWDefs, RWSet);
251       else {
252         assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
253         scanSchedRW(*RWI, SRDefs, RWSet);
254       }
255     }
256   }
257   // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted
258   // for the loop below that initializes Alias vectors.
259   RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias");
260   std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord());
261   for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) {
262     Record *MatchDef = (*AI)->getValueAsDef("MatchRW");
263     Record *AliasDef = (*AI)->getValueAsDef("AliasRW");
264     if (MatchDef->isSubClassOf("SchedWrite")) {
265       if (!AliasDef->isSubClassOf("SchedWrite"))
266         PrintFatalError((*AI)->getLoc(), "SchedWrite Alias must be SchedWrite");
267       scanSchedRW(AliasDef, SWDefs, RWSet);
268     }
269     else {
270       assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
271       if (!AliasDef->isSubClassOf("SchedRead"))
272         PrintFatalError((*AI)->getLoc(), "SchedRead Alias must be SchedRead");
273       scanSchedRW(AliasDef, SRDefs, RWSet);
274     }
275   }
276   // Sort and add the SchedReadWrites directly referenced by instructions or
277   // itinerary resources. Index reads and writes in separate domains.
278   std::sort(SWDefs.begin(), SWDefs.end(), LessRecord());
279   for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) {
280     assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite");
281     SchedWrites.emplace_back(SchedWrites.size(), *SWI);
282   }
283   std::sort(SRDefs.begin(), SRDefs.end(), LessRecord());
284   for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) {
285     assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite");
286     SchedReads.emplace_back(SchedReads.size(), *SRI);
287   }
288   // Initialize WriteSequence vectors.
289   for (std::vector<CodeGenSchedRW>::iterator WI = SchedWrites.begin(),
290          WE = SchedWrites.end(); WI != WE; ++WI) {
291     if (!WI->IsSequence)
292       continue;
293     findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence,
294             /*IsRead=*/false);
295   }
296   // Initialize Aliases vectors.
297   for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) {
298     Record *AliasDef = (*AI)->getValueAsDef("AliasRW");
299     getSchedRW(AliasDef).IsAlias = true;
300     Record *MatchDef = (*AI)->getValueAsDef("MatchRW");
301     CodeGenSchedRW &RW = getSchedRW(MatchDef);
302     if (RW.IsAlias)
303       PrintFatalError((*AI)->getLoc(), "Cannot Alias an Alias");
304     RW.Aliases.push_back(*AI);
305   }
306   DEBUG(
307     for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) {
308       dbgs() << WIdx << ": ";
309       SchedWrites[WIdx].dump();
310       dbgs() << '\n';
311     }
312     for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) {
313       dbgs() << RIdx << ": ";
314       SchedReads[RIdx].dump();
315       dbgs() << '\n';
316     }
317     RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite");
318     for (RecIter RI = RWDefs.begin(), RE = RWDefs.end();
319          RI != RE; ++RI) {
320       if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) {
321         const std::string &Name = (*RI)->getName();
322         if (Name != "NoWrite" && Name != "ReadDefault")
323           dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n';
324       }
325     });
326 }
327 
328 /// Compute a SchedWrite name from a sequence of writes.
genRWName(ArrayRef<unsigned> Seq,bool IsRead)329 std::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) {
330   std::string Name("(");
331   for (auto I = Seq.begin(), E = Seq.end(); I != E; ++I) {
332     if (I != Seq.begin())
333       Name += '_';
334     Name += getSchedRW(*I, IsRead).Name;
335   }
336   Name += ')';
337   return Name;
338 }
339 
getSchedRWIdx(Record * Def,bool IsRead,unsigned After) const340 unsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead,
341                                            unsigned After) const {
342   const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
343   assert(After < RWVec.size() && "start position out of bounds");
344   for (std::vector<CodeGenSchedRW>::const_iterator I = RWVec.begin() + After,
345          E = RWVec.end(); I != E; ++I) {
346     if (I->TheDef == Def)
347       return I - RWVec.begin();
348   }
349   return 0;
350 }
351 
hasReadOfWrite(Record * WriteDef) const352 bool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const {
353   for (unsigned i = 0, e = SchedReads.size(); i < e; ++i) {
354     Record *ReadDef = SchedReads[i].TheDef;
355     if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance"))
356       continue;
357 
358     RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites");
359     if (std::find(ValidWrites.begin(), ValidWrites.end(), WriteDef)
360         != ValidWrites.end()) {
361       return true;
362     }
363   }
364   return false;
365 }
366 
367 namespace llvm {
splitSchedReadWrites(const RecVec & RWDefs,RecVec & WriteDefs,RecVec & ReadDefs)368 void splitSchedReadWrites(const RecVec &RWDefs,
369                           RecVec &WriteDefs, RecVec &ReadDefs) {
370   for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) {
371     if ((*RWI)->isSubClassOf("SchedWrite"))
372       WriteDefs.push_back(*RWI);
373     else {
374       assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite");
375       ReadDefs.push_back(*RWI);
376     }
377   }
378 }
379 } // namespace llvm
380 
381 // Split the SchedReadWrites defs and call findRWs for each list.
findRWs(const RecVec & RWDefs,IdxVec & Writes,IdxVec & Reads) const382 void CodeGenSchedModels::findRWs(const RecVec &RWDefs,
383                                  IdxVec &Writes, IdxVec &Reads) const {
384     RecVec WriteDefs;
385     RecVec ReadDefs;
386     splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs);
387     findRWs(WriteDefs, Writes, false);
388     findRWs(ReadDefs, Reads, true);
389 }
390 
391 // Call getSchedRWIdx for all elements in a sequence of SchedRW defs.
findRWs(const RecVec & RWDefs,IdxVec & RWs,bool IsRead) const392 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs,
393                                  bool IsRead) const {
394   for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) {
395     unsigned Idx = getSchedRWIdx(*RI, IsRead);
396     assert(Idx && "failed to collect SchedReadWrite");
397     RWs.push_back(Idx);
398   }
399 }
400 
expandRWSequence(unsigned RWIdx,IdxVec & RWSeq,bool IsRead) const401 void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq,
402                                           bool IsRead) const {
403   const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
404   if (!SchedRW.IsSequence) {
405     RWSeq.push_back(RWIdx);
406     return;
407   }
408   int Repeat =
409     SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1;
410   for (int i = 0; i < Repeat; ++i) {
411     for (IdxIter I = SchedRW.Sequence.begin(), E = SchedRW.Sequence.end();
412          I != E; ++I) {
413       expandRWSequence(*I, RWSeq, IsRead);
414     }
415   }
416 }
417 
418 // Expand a SchedWrite as a sequence following any aliases that coincide with
419 // the given processor model.
expandRWSeqForProc(unsigned RWIdx,IdxVec & RWSeq,bool IsRead,const CodeGenProcModel & ProcModel) const420 void CodeGenSchedModels::expandRWSeqForProc(
421   unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
422   const CodeGenProcModel &ProcModel) const {
423 
424   const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead);
425   Record *AliasDef = nullptr;
426   for (RecIter AI = SchedWrite.Aliases.begin(), AE = SchedWrite.Aliases.end();
427        AI != AE; ++AI) {
428     const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
429     if ((*AI)->getValueInit("SchedModel")->isComplete()) {
430       Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
431       if (&getProcModel(ModelDef) != &ProcModel)
432         continue;
433     }
434     if (AliasDef)
435       PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases "
436                       "defined for processor " + ProcModel.ModelName +
437                       " Ensure only one SchedAlias exists per RW.");
438     AliasDef = AliasRW.TheDef;
439   }
440   if (AliasDef) {
441     expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead),
442                        RWSeq, IsRead,ProcModel);
443     return;
444   }
445   if (!SchedWrite.IsSequence) {
446     RWSeq.push_back(RWIdx);
447     return;
448   }
449   int Repeat =
450     SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1;
451   for (int i = 0; i < Repeat; ++i) {
452     for (IdxIter I = SchedWrite.Sequence.begin(), E = SchedWrite.Sequence.end();
453          I != E; ++I) {
454       expandRWSeqForProc(*I, RWSeq, IsRead, ProcModel);
455     }
456   }
457 }
458 
459 // Find the existing SchedWrite that models this sequence of writes.
findRWForSequence(ArrayRef<unsigned> Seq,bool IsRead)460 unsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq,
461                                                bool IsRead) {
462   std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
463 
464   for (std::vector<CodeGenSchedRW>::iterator I = RWVec.begin(), E = RWVec.end();
465        I != E; ++I) {
466     if (makeArrayRef(I->Sequence) == Seq)
467       return I - RWVec.begin();
468   }
469   // Index zero reserved for invalid RW.
470   return 0;
471 }
472 
473 /// Add this ReadWrite if it doesn't already exist.
findOrInsertRW(ArrayRef<unsigned> Seq,bool IsRead)474 unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq,
475                                             bool IsRead) {
476   assert(!Seq.empty() && "cannot insert empty sequence");
477   if (Seq.size() == 1)
478     return Seq.back();
479 
480   unsigned Idx = findRWForSequence(Seq, IsRead);
481   if (Idx)
482     return Idx;
483 
484   unsigned RWIdx = IsRead ? SchedReads.size() : SchedWrites.size();
485   CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead));
486   if (IsRead)
487     SchedReads.push_back(SchedRW);
488   else
489     SchedWrites.push_back(SchedRW);
490   return RWIdx;
491 }
492 
493 /// Visit all the instruction definitions for this target to gather and
494 /// enumerate the itinerary classes. These are the explicitly specified
495 /// SchedClasses. More SchedClasses may be inferred.
collectSchedClasses()496 void CodeGenSchedModels::collectSchedClasses() {
497 
498   // NoItinerary is always the first class at Idx=0
499   SchedClasses.resize(1);
500   SchedClasses.back().Index = 0;
501   SchedClasses.back().Name = "NoInstrModel";
502   SchedClasses.back().ItinClassDef = Records.getDef("NoItinerary");
503   SchedClasses.back().ProcIndices.push_back(0);
504 
505   // Create a SchedClass for each unique combination of itinerary class and
506   // SchedRW list.
507   for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
508     Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary");
509     IdxVec Writes, Reads;
510     if (!Inst->TheDef->isValueUnset("SchedRW"))
511       findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
512 
513     // ProcIdx == 0 indicates the class applies to all processors.
514     IdxVec ProcIndices(1, 0);
515 
516     unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, ProcIndices);
517     InstrClassMap[Inst->TheDef] = SCIdx;
518   }
519   // Create classes for InstRW defs.
520   RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
521   std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord());
522   for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI)
523     createInstRWClass(*OI);
524 
525   NumInstrSchedClasses = SchedClasses.size();
526 
527   bool EnableDump = false;
528   DEBUG(EnableDump = true);
529   if (!EnableDump)
530     return;
531 
532   for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
533     std::string InstName = Inst->TheDef->getName();
534     unsigned SCIdx = InstrClassMap.lookup(Inst->TheDef);
535     if (!SCIdx) {
536       if (!Inst->hasNoSchedulingInfo)
537         dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n';
538       continue;
539     }
540     CodeGenSchedClass &SC = getSchedClass(SCIdx);
541     if (SC.ProcIndices[0] != 0)
542       PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class "
543                       "must not be subtarget specific.");
544 
545     IdxVec ProcIndices;
546     if (SC.ItinClassDef->getName() != "NoItinerary") {
547       ProcIndices.push_back(0);
548       dbgs() << "Itinerary for " << InstName << ": "
549              << SC.ItinClassDef->getName() << '\n';
550     }
551     if (!SC.Writes.empty()) {
552       ProcIndices.push_back(0);
553       dbgs() << "SchedRW machine model for " << InstName;
554       for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE; ++WI)
555         dbgs() << " " << SchedWrites[*WI].Name;
556       for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI)
557         dbgs() << " " << SchedReads[*RI].Name;
558       dbgs() << '\n';
559     }
560     const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs;
561     for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end();
562          RWI != RWE; ++RWI) {
563       const CodeGenProcModel &ProcModel =
564         getProcModel((*RWI)->getValueAsDef("SchedModel"));
565       ProcIndices.push_back(ProcModel.Index);
566       dbgs() << "InstRW on " << ProcModel.ModelName << " for " << InstName;
567       IdxVec Writes;
568       IdxVec Reads;
569       findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"),
570               Writes, Reads);
571       for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI)
572         dbgs() << " " << SchedWrites[*WI].Name;
573       for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI)
574         dbgs() << " " << SchedReads[*RI].Name;
575       dbgs() << '\n';
576     }
577     for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(),
578            PE = ProcModels.end(); PI != PE; ++PI) {
579       if (!std::count(ProcIndices.begin(), ProcIndices.end(), PI->Index))
580         dbgs() << "No machine model for " << Inst->TheDef->getName()
581                << " on processor " << PI->ModelName << '\n';
582     }
583   }
584 }
585 
586 /// Find an SchedClass that has been inferred from a per-operand list of
587 /// SchedWrites and SchedReads.
findSchedClassIdx(Record * ItinClassDef,ArrayRef<unsigned> Writes,ArrayRef<unsigned> Reads) const588 unsigned CodeGenSchedModels::findSchedClassIdx(Record *ItinClassDef,
589                                                ArrayRef<unsigned> Writes,
590                                                ArrayRef<unsigned> Reads) const {
591   for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) {
592     if (I->ItinClassDef == ItinClassDef && makeArrayRef(I->Writes) == Writes &&
593         makeArrayRef(I->Reads) == Reads) {
594       return I - schedClassBegin();
595     }
596   }
597   return 0;
598 }
599 
600 // Get the SchedClass index for an instruction.
getSchedClassIdx(const CodeGenInstruction & Inst) const601 unsigned CodeGenSchedModels::getSchedClassIdx(
602   const CodeGenInstruction &Inst) const {
603 
604   return InstrClassMap.lookup(Inst.TheDef);
605 }
606 
607 std::string
createSchedClassName(Record * ItinClassDef,ArrayRef<unsigned> OperWrites,ArrayRef<unsigned> OperReads)608 CodeGenSchedModels::createSchedClassName(Record *ItinClassDef,
609                                          ArrayRef<unsigned> OperWrites,
610                                          ArrayRef<unsigned> OperReads) {
611 
612   std::string Name;
613   if (ItinClassDef && ItinClassDef->getName() != "NoItinerary")
614     Name = ItinClassDef->getName();
615   for (unsigned Idx : OperWrites) {
616     if (!Name.empty())
617       Name += '_';
618     Name += SchedWrites[Idx].Name;
619   }
620   for (unsigned Idx : OperReads) {
621     Name += '_';
622     Name += SchedReads[Idx].Name;
623   }
624   return Name;
625 }
626 
createSchedClassName(const RecVec & InstDefs)627 std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) {
628 
629   std::string Name;
630   for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) {
631     if (I != InstDefs.begin())
632       Name += '_';
633     Name += (*I)->getName();
634   }
635   return Name;
636 }
637 
638 /// Add an inferred sched class from an itinerary class and per-operand list of
639 /// SchedWrites and SchedReads. ProcIndices contains the set of IDs of
640 /// processors that may utilize this class.
addSchedClass(Record * ItinClassDef,ArrayRef<unsigned> OperWrites,ArrayRef<unsigned> OperReads,ArrayRef<unsigned> ProcIndices)641 unsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef,
642                                            ArrayRef<unsigned> OperWrites,
643                                            ArrayRef<unsigned> OperReads,
644                                            ArrayRef<unsigned> ProcIndices) {
645   assert(!ProcIndices.empty() && "expect at least one ProcIdx");
646 
647   unsigned Idx = findSchedClassIdx(ItinClassDef, OperWrites, OperReads);
648   if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) {
649     IdxVec PI;
650     std::set_union(SchedClasses[Idx].ProcIndices.begin(),
651                    SchedClasses[Idx].ProcIndices.end(),
652                    ProcIndices.begin(), ProcIndices.end(),
653                    std::back_inserter(PI));
654     SchedClasses[Idx].ProcIndices.swap(PI);
655     return Idx;
656   }
657   Idx = SchedClasses.size();
658   SchedClasses.resize(Idx+1);
659   CodeGenSchedClass &SC = SchedClasses.back();
660   SC.Index = Idx;
661   SC.Name = createSchedClassName(ItinClassDef, OperWrites, OperReads);
662   SC.ItinClassDef = ItinClassDef;
663   SC.Writes = OperWrites;
664   SC.Reads = OperReads;
665   SC.ProcIndices = ProcIndices;
666 
667   return Idx;
668 }
669 
670 // Create classes for each set of opcodes that are in the same InstReadWrite
671 // definition across all processors.
createInstRWClass(Record * InstRWDef)672 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) {
673   // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that
674   // intersects with an existing class via a previous InstRWDef. Instrs that do
675   // not intersect with an existing class refer back to their former class as
676   // determined from ItinDef or SchedRW.
677   SmallVector<std::pair<unsigned, SmallVector<Record *, 8> >, 4> ClassInstrs;
678   // Sort Instrs into sets.
679   const RecVec *InstDefs = Sets.expand(InstRWDef);
680   if (InstDefs->empty())
681     PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes");
682 
683   for (RecIter I = InstDefs->begin(), E = InstDefs->end(); I != E; ++I) {
684     InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I);
685     if (Pos == InstrClassMap.end())
686       PrintFatalError((*I)->getLoc(), "No sched class for instruction.");
687     unsigned SCIdx = Pos->second;
688     unsigned CIdx = 0, CEnd = ClassInstrs.size();
689     for (; CIdx != CEnd; ++CIdx) {
690       if (ClassInstrs[CIdx].first == SCIdx)
691         break;
692     }
693     if (CIdx == CEnd) {
694       ClassInstrs.resize(CEnd + 1);
695       ClassInstrs[CIdx].first = SCIdx;
696     }
697     ClassInstrs[CIdx].second.push_back(*I);
698   }
699   // For each set of Instrs, create a new class if necessary, and map or remap
700   // the Instrs to it.
701   unsigned CIdx = 0, CEnd = ClassInstrs.size();
702   for (; CIdx != CEnd; ++CIdx) {
703     unsigned OldSCIdx = ClassInstrs[CIdx].first;
704     ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second;
705     // If the all instrs in the current class are accounted for, then leave
706     // them mapped to their old class.
707     if (OldSCIdx) {
708       const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs;
709       if (!RWDefs.empty()) {
710         const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]);
711         unsigned OrigNumInstrs = 0;
712         for (RecIter I = OrigInstDefs->begin(), E = OrigInstDefs->end();
713              I != E; ++I) {
714           if (InstrClassMap[*I] == OldSCIdx)
715             ++OrigNumInstrs;
716         }
717         if (OrigNumInstrs == InstDefs.size()) {
718           assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 &&
719                  "expected a generic SchedClass");
720           DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":"
721                 << SchedClasses[OldSCIdx].Name << " on "
722                 << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n");
723           SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef);
724           continue;
725         }
726       }
727     }
728     unsigned SCIdx = SchedClasses.size();
729     SchedClasses.resize(SCIdx+1);
730     CodeGenSchedClass &SC = SchedClasses.back();
731     SC.Index = SCIdx;
732     SC.Name = createSchedClassName(InstDefs);
733     DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on "
734           << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n");
735 
736     // Preserve ItinDef and Writes/Reads for processors without an InstRW entry.
737     SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef;
738     SC.Writes = SchedClasses[OldSCIdx].Writes;
739     SC.Reads = SchedClasses[OldSCIdx].Reads;
740     SC.ProcIndices.push_back(0);
741     // Map each Instr to this new class.
742     // Note that InstDefs may be a smaller list than InstRWDef's "Instrs".
743     Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel");
744     SmallSet<unsigned, 4> RemappedClassIDs;
745     for (ArrayRef<Record*>::const_iterator
746            II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) {
747       unsigned OldSCIdx = InstrClassMap[*II];
748       if (OldSCIdx && RemappedClassIDs.insert(OldSCIdx).second) {
749         for (RecIter RI = SchedClasses[OldSCIdx].InstRWs.begin(),
750                RE = SchedClasses[OldSCIdx].InstRWs.end(); RI != RE; ++RI) {
751           if ((*RI)->getValueAsDef("SchedModel") == RWModelDef) {
752             PrintFatalError(InstRWDef->getLoc(), "Overlapping InstRW def " +
753                           (*II)->getName() + " also matches " +
754                           (*RI)->getValue("Instrs")->getValue()->getAsString());
755           }
756           assert(*RI != InstRWDef && "SchedClass has duplicate InstRW def");
757           SC.InstRWs.push_back(*RI);
758         }
759       }
760       InstrClassMap[*II] = SCIdx;
761     }
762     SC.InstRWs.push_back(InstRWDef);
763   }
764 }
765 
766 // True if collectProcItins found anything.
hasItineraries() const767 bool CodeGenSchedModels::hasItineraries() const {
768   for (CodeGenSchedModels::ProcIter PI = procModelBegin(), PE = procModelEnd();
769        PI != PE; ++PI) {
770     if (PI->hasItineraries())
771       return true;
772   }
773   return false;
774 }
775 
776 // Gather the processor itineraries.
collectProcItins()777 void CodeGenSchedModels::collectProcItins() {
778   for (CodeGenProcModel &ProcModel : ProcModels) {
779     if (!ProcModel.hasItineraries())
780       continue;
781 
782     RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID");
783     assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect");
784 
785     // Populate ItinDefList with Itinerary records.
786     ProcModel.ItinDefList.resize(NumInstrSchedClasses);
787 
788     // Insert each itinerary data record in the correct position within
789     // the processor model's ItinDefList.
790     for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) {
791       Record *ItinData = ItinRecords[i];
792       Record *ItinDef = ItinData->getValueAsDef("TheClass");
793       bool FoundClass = false;
794       for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd();
795            SCI != SCE; ++SCI) {
796         // Multiple SchedClasses may share an itinerary. Update all of them.
797         if (SCI->ItinClassDef == ItinDef) {
798           ProcModel.ItinDefList[SCI->Index] = ItinData;
799           FoundClass = true;
800         }
801       }
802       if (!FoundClass) {
803         DEBUG(dbgs() << ProcModel.ItinsDef->getName()
804               << " missing class for itinerary " << ItinDef->getName() << '\n');
805       }
806     }
807     // Check for missing itinerary entries.
808     assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec");
809     DEBUG(
810       for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) {
811         if (!ProcModel.ItinDefList[i])
812           dbgs() << ProcModel.ItinsDef->getName()
813                  << " missing itinerary for class "
814                  << SchedClasses[i].Name << '\n';
815       });
816   }
817 }
818 
819 // Gather the read/write types for each itinerary class.
collectProcItinRW()820 void CodeGenSchedModels::collectProcItinRW() {
821   RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
822   std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord());
823   for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
824     if (!(*II)->getValueInit("SchedModel")->isComplete())
825       PrintFatalError((*II)->getLoc(), "SchedModel is undefined");
826     Record *ModelDef = (*II)->getValueAsDef("SchedModel");
827     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
828     if (I == ProcModelMap.end()) {
829       PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel "
830                     + ModelDef->getName());
831     }
832     ProcModels[I->second].ItinRWDefs.push_back(*II);
833   }
834 }
835 
836 // Gather the unsupported features for processor models.
collectProcUnsupportedFeatures()837 void CodeGenSchedModels::collectProcUnsupportedFeatures() {
838   for (CodeGenProcModel &ProcModel : ProcModels) {
839     for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) {
840        ProcModel.UnsupportedFeaturesDefs.push_back(Pred);
841     }
842   }
843 }
844 
845 /// Infer new classes from existing classes. In the process, this may create new
846 /// SchedWrites from sequences of existing SchedWrites.
inferSchedClasses()847 void CodeGenSchedModels::inferSchedClasses() {
848   DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n");
849 
850   // Visit all existing classes and newly created classes.
851   for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) {
852     assert(SchedClasses[Idx].Index == Idx && "bad SCIdx");
853 
854     if (SchedClasses[Idx].ItinClassDef)
855       inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx);
856     if (!SchedClasses[Idx].InstRWs.empty())
857       inferFromInstRWs(Idx);
858     if (!SchedClasses[Idx].Writes.empty()) {
859       inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads,
860                   Idx, SchedClasses[Idx].ProcIndices);
861     }
862     assert(SchedClasses.size() < (NumInstrSchedClasses*6) &&
863            "too many SchedVariants");
864   }
865 }
866 
867 /// Infer classes from per-processor itinerary resources.
inferFromItinClass(Record * ItinClassDef,unsigned FromClassIdx)868 void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef,
869                                             unsigned FromClassIdx) {
870   for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
871     const CodeGenProcModel &PM = ProcModels[PIdx];
872     // For all ItinRW entries.
873     bool HasMatch = false;
874     for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
875          II != IE; ++II) {
876       RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
877       if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
878         continue;
879       if (HasMatch)
880         PrintFatalError((*II)->getLoc(), "Duplicate itinerary class "
881                       + ItinClassDef->getName()
882                       + " in ItinResources for " + PM.ModelName);
883       HasMatch = true;
884       IdxVec Writes, Reads;
885       findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
886       IdxVec ProcIndices(1, PIdx);
887       inferFromRW(Writes, Reads, FromClassIdx, ProcIndices);
888     }
889   }
890 }
891 
892 /// Infer classes from per-processor InstReadWrite definitions.
inferFromInstRWs(unsigned SCIdx)893 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) {
894   for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) {
895     assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!");
896     Record *Rec = SchedClasses[SCIdx].InstRWs[I];
897     const RecVec *InstDefs = Sets.expand(Rec);
898     RecIter II = InstDefs->begin(), IE = InstDefs->end();
899     for (; II != IE; ++II) {
900       if (InstrClassMap[*II] == SCIdx)
901         break;
902     }
903     // If this class no longer has any instructions mapped to it, it has become
904     // irrelevant.
905     if (II == IE)
906       continue;
907     IdxVec Writes, Reads;
908     findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
909     unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index;
910     IdxVec ProcIndices(1, PIdx);
911     inferFromRW(Writes, Reads, SCIdx, ProcIndices); // May mutate SchedClasses.
912   }
913 }
914 
915 namespace {
916 // Helper for substituteVariantOperand.
917 struct TransVariant {
918   Record *VarOrSeqDef;  // Variant or sequence.
919   unsigned RWIdx;       // Index of this variant or sequence's matched type.
920   unsigned ProcIdx;     // Processor model index or zero for any.
921   unsigned TransVecIdx; // Index into PredTransitions::TransVec.
922 
TransVariant__anon4cc2b93e0211::TransVariant923   TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti):
924     VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {}
925 };
926 
927 // Associate a predicate with the SchedReadWrite that it guards.
928 // RWIdx is the index of the read/write variant.
929 struct PredCheck {
930   bool IsRead;
931   unsigned RWIdx;
932   Record *Predicate;
933 
PredCheck__anon4cc2b93e0211::PredCheck934   PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {}
935 };
936 
937 // A Predicate transition is a list of RW sequences guarded by a PredTerm.
938 struct PredTransition {
939   // A predicate term is a conjunction of PredChecks.
940   SmallVector<PredCheck, 4> PredTerm;
941   SmallVector<SmallVector<unsigned,4>, 16> WriteSequences;
942   SmallVector<SmallVector<unsigned,4>, 16> ReadSequences;
943   SmallVector<unsigned, 4> ProcIndices;
944 };
945 
946 // Encapsulate a set of partially constructed transitions.
947 // The results are built by repeated calls to substituteVariants.
948 class PredTransitions {
949   CodeGenSchedModels &SchedModels;
950 
951 public:
952   std::vector<PredTransition> TransVec;
953 
PredTransitions(CodeGenSchedModels & sm)954   PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {}
955 
956   void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq,
957                                 bool IsRead, unsigned StartIdx);
958 
959   void substituteVariants(const PredTransition &Trans);
960 
961 #ifndef NDEBUG
962   void dump() const;
963 #endif
964 
965 private:
966   bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term);
967   void getIntersectingVariants(
968     const CodeGenSchedRW &SchedRW, unsigned TransIdx,
969     std::vector<TransVariant> &IntersectingVariants);
970   void pushVariant(const TransVariant &VInfo, bool IsRead);
971 };
972 } // anonymous
973 
974 // Return true if this predicate is mutually exclusive with a PredTerm. This
975 // degenerates into checking if the predicate is mutually exclusive with any
976 // predicate in the Term's conjunction.
977 //
978 // All predicates associated with a given SchedRW are considered mutually
979 // exclusive. This should work even if the conditions expressed by the
980 // predicates are not exclusive because the predicates for a given SchedWrite
981 // are always checked in the order they are defined in the .td file. Later
982 // conditions implicitly negate any prior condition.
mutuallyExclusive(Record * PredDef,ArrayRef<PredCheck> Term)983 bool PredTransitions::mutuallyExclusive(Record *PredDef,
984                                         ArrayRef<PredCheck> Term) {
985 
986   for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end();
987        I != E; ++I) {
988     if (I->Predicate == PredDef)
989       return false;
990 
991     const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead);
992     assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant");
993     RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants");
994     for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) {
995       if ((*VI)->getValueAsDef("Predicate") == PredDef)
996         return true;
997     }
998   }
999   return false;
1000 }
1001 
hasAliasedVariants(const CodeGenSchedRW & RW,CodeGenSchedModels & SchedModels)1002 static bool hasAliasedVariants(const CodeGenSchedRW &RW,
1003                                CodeGenSchedModels &SchedModels) {
1004   if (RW.HasVariants)
1005     return true;
1006 
1007   for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) {
1008     const CodeGenSchedRW &AliasRW =
1009       SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW"));
1010     if (AliasRW.HasVariants)
1011       return true;
1012     if (AliasRW.IsSequence) {
1013       IdxVec ExpandedRWs;
1014       SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead);
1015       for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
1016            SI != SE; ++SI) {
1017         if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead),
1018                                SchedModels)) {
1019           return true;
1020         }
1021       }
1022     }
1023   }
1024   return false;
1025 }
1026 
hasVariant(ArrayRef<PredTransition> Transitions,CodeGenSchedModels & SchedModels)1027 static bool hasVariant(ArrayRef<PredTransition> Transitions,
1028                        CodeGenSchedModels &SchedModels) {
1029   for (ArrayRef<PredTransition>::iterator
1030          PTI = Transitions.begin(), PTE = Transitions.end();
1031        PTI != PTE; ++PTI) {
1032     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1033            WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end();
1034          WSI != WSE; ++WSI) {
1035       for (SmallVectorImpl<unsigned>::const_iterator
1036              WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
1037         if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels))
1038           return true;
1039       }
1040     }
1041     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1042            RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end();
1043          RSI != RSE; ++RSI) {
1044       for (SmallVectorImpl<unsigned>::const_iterator
1045              RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) {
1046         if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels))
1047           return true;
1048       }
1049     }
1050   }
1051   return false;
1052 }
1053 
1054 // Populate IntersectingVariants with any variants or aliased sequences of the
1055 // given SchedRW whose processor indices and predicates are not mutually
1056 // exclusive with the given transition.
getIntersectingVariants(const CodeGenSchedRW & SchedRW,unsigned TransIdx,std::vector<TransVariant> & IntersectingVariants)1057 void PredTransitions::getIntersectingVariants(
1058   const CodeGenSchedRW &SchedRW, unsigned TransIdx,
1059   std::vector<TransVariant> &IntersectingVariants) {
1060 
1061   bool GenericRW = false;
1062 
1063   std::vector<TransVariant> Variants;
1064   if (SchedRW.HasVariants) {
1065     unsigned VarProcIdx = 0;
1066     if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) {
1067       Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel");
1068       VarProcIdx = SchedModels.getProcModel(ModelDef).Index;
1069     }
1070     // Push each variant. Assign TransVecIdx later.
1071     const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants");
1072     for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
1073       Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0));
1074     if (VarProcIdx == 0)
1075       GenericRW = true;
1076   }
1077   for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1078        AI != AE; ++AI) {
1079     // If either the SchedAlias itself or the SchedReadWrite that it aliases
1080     // to is defined within a processor model, constrain all variants to
1081     // that processor.
1082     unsigned AliasProcIdx = 0;
1083     if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1084       Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
1085       AliasProcIdx = SchedModels.getProcModel(ModelDef).Index;
1086     }
1087     const CodeGenSchedRW &AliasRW =
1088       SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW"));
1089 
1090     if (AliasRW.HasVariants) {
1091       const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants");
1092       for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
1093         Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0));
1094     }
1095     if (AliasRW.IsSequence) {
1096       Variants.push_back(
1097         TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0));
1098     }
1099     if (AliasProcIdx == 0)
1100       GenericRW = true;
1101   }
1102   for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) {
1103     TransVariant &Variant = Variants[VIdx];
1104     // Don't expand variants if the processor models don't intersect.
1105     // A zero processor index means any processor.
1106     SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices;
1107     if (ProcIndices[0] && Variants[VIdx].ProcIdx) {
1108       unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(),
1109                                 Variant.ProcIdx);
1110       if (!Cnt)
1111         continue;
1112       if (Cnt > 1) {
1113         const CodeGenProcModel &PM =
1114           *(SchedModels.procModelBegin() + Variant.ProcIdx);
1115         PrintFatalError(Variant.VarOrSeqDef->getLoc(),
1116                         "Multiple variants defined for processor " +
1117                         PM.ModelName +
1118                         " Ensure only one SchedAlias exists per RW.");
1119       }
1120     }
1121     if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) {
1122       Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate");
1123       if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm))
1124         continue;
1125     }
1126     if (IntersectingVariants.empty()) {
1127       // The first variant builds on the existing transition.
1128       Variant.TransVecIdx = TransIdx;
1129       IntersectingVariants.push_back(Variant);
1130     }
1131     else {
1132       // Push another copy of the current transition for more variants.
1133       Variant.TransVecIdx = TransVec.size();
1134       IntersectingVariants.push_back(Variant);
1135       TransVec.push_back(TransVec[TransIdx]);
1136     }
1137   }
1138   if (GenericRW && IntersectingVariants.empty()) {
1139     PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has "
1140                     "a matching predicate on any processor");
1141   }
1142 }
1143 
1144 // Push the Reads/Writes selected by this variant onto the PredTransition
1145 // specified by VInfo.
1146 void PredTransitions::
pushVariant(const TransVariant & VInfo,bool IsRead)1147 pushVariant(const TransVariant &VInfo, bool IsRead) {
1148 
1149   PredTransition &Trans = TransVec[VInfo.TransVecIdx];
1150 
1151   // If this operand transition is reached through a processor-specific alias,
1152   // then the whole transition is specific to this processor.
1153   if (VInfo.ProcIdx != 0)
1154     Trans.ProcIndices.assign(1, VInfo.ProcIdx);
1155 
1156   IdxVec SelectedRWs;
1157   if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) {
1158     Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate");
1159     Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef));
1160     RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected");
1161     SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead);
1162   }
1163   else {
1164     assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") &&
1165            "variant must be a SchedVariant or aliased WriteSequence");
1166     SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead));
1167   }
1168 
1169   const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead);
1170 
1171   SmallVectorImpl<SmallVector<unsigned,4> > &RWSequences = IsRead
1172     ? Trans.ReadSequences : Trans.WriteSequences;
1173   if (SchedRW.IsVariadic) {
1174     unsigned OperIdx = RWSequences.size()-1;
1175     // Make N-1 copies of this transition's last sequence.
1176     for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) {
1177       // Create a temporary copy the vector could reallocate.
1178       RWSequences.reserve(RWSequences.size() + 1);
1179       RWSequences.push_back(RWSequences[OperIdx]);
1180     }
1181     // Push each of the N elements of the SelectedRWs onto a copy of the last
1182     // sequence (split the current operand into N operands).
1183     // Note that write sequences should be expanded within this loop--the entire
1184     // sequence belongs to a single operand.
1185     for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1186          RWI != RWE; ++RWI, ++OperIdx) {
1187       IdxVec ExpandedRWs;
1188       if (IsRead)
1189         ExpandedRWs.push_back(*RWI);
1190       else
1191         SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1192       RWSequences[OperIdx].insert(RWSequences[OperIdx].end(),
1193                                   ExpandedRWs.begin(), ExpandedRWs.end());
1194     }
1195     assert(OperIdx == RWSequences.size() && "missed a sequence");
1196   }
1197   else {
1198     // Push this transition's expanded sequence onto this transition's last
1199     // sequence (add to the current operand's sequence).
1200     SmallVectorImpl<unsigned> &Seq = RWSequences.back();
1201     IdxVec ExpandedRWs;
1202     for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1203          RWI != RWE; ++RWI) {
1204       if (IsRead)
1205         ExpandedRWs.push_back(*RWI);
1206       else
1207         SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1208     }
1209     Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end());
1210   }
1211 }
1212 
1213 // RWSeq is a sequence of all Reads or all Writes for the next read or write
1214 // operand. StartIdx is an index into TransVec where partial results
1215 // starts. RWSeq must be applied to all transitions between StartIdx and the end
1216 // of TransVec.
substituteVariantOperand(const SmallVectorImpl<unsigned> & RWSeq,bool IsRead,unsigned StartIdx)1217 void PredTransitions::substituteVariantOperand(
1218   const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) {
1219 
1220   // Visit each original RW within the current sequence.
1221   for (SmallVectorImpl<unsigned>::const_iterator
1222          RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) {
1223     const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead);
1224     // Push this RW on all partial PredTransitions or distribute variants.
1225     // New PredTransitions may be pushed within this loop which should not be
1226     // revisited (TransEnd must be loop invariant).
1227     for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size();
1228          TransIdx != TransEnd; ++TransIdx) {
1229       // In the common case, push RW onto the current operand's sequence.
1230       if (!hasAliasedVariants(SchedRW, SchedModels)) {
1231         if (IsRead)
1232           TransVec[TransIdx].ReadSequences.back().push_back(*RWI);
1233         else
1234           TransVec[TransIdx].WriteSequences.back().push_back(*RWI);
1235         continue;
1236       }
1237       // Distribute this partial PredTransition across intersecting variants.
1238       // This will push a copies of TransVec[TransIdx] on the back of TransVec.
1239       std::vector<TransVariant> IntersectingVariants;
1240       getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants);
1241       // Now expand each variant on top of its copy of the transition.
1242       for (std::vector<TransVariant>::const_iterator
1243              IVI = IntersectingVariants.begin(),
1244              IVE = IntersectingVariants.end();
1245            IVI != IVE; ++IVI) {
1246         pushVariant(*IVI, IsRead);
1247       }
1248     }
1249   }
1250 }
1251 
1252 // For each variant of a Read/Write in Trans, substitute the sequence of
1253 // Read/Writes guarded by the variant. This is exponential in the number of
1254 // variant Read/Writes, but in practice detection of mutually exclusive
1255 // predicates should result in linear growth in the total number variants.
1256 //
1257 // This is one step in a breadth-first search of nested variants.
substituteVariants(const PredTransition & Trans)1258 void PredTransitions::substituteVariants(const PredTransition &Trans) {
1259   // Build up a set of partial results starting at the back of
1260   // PredTransitions. Remember the first new transition.
1261   unsigned StartIdx = TransVec.size();
1262   TransVec.resize(TransVec.size() + 1);
1263   TransVec.back().PredTerm = Trans.PredTerm;
1264   TransVec.back().ProcIndices = Trans.ProcIndices;
1265 
1266   // Visit each original write sequence.
1267   for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1268          WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end();
1269        WSI != WSE; ++WSI) {
1270     // Push a new (empty) write sequence onto all partial Transitions.
1271     for (std::vector<PredTransition>::iterator I =
1272            TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1273       I->WriteSequences.resize(I->WriteSequences.size() + 1);
1274     }
1275     substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx);
1276   }
1277   // Visit each original read sequence.
1278   for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1279          RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end();
1280        RSI != RSE; ++RSI) {
1281     // Push a new (empty) read sequence onto all partial Transitions.
1282     for (std::vector<PredTransition>::iterator I =
1283            TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1284       I->ReadSequences.resize(I->ReadSequences.size() + 1);
1285     }
1286     substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx);
1287   }
1288 }
1289 
1290 // Create a new SchedClass for each variant found by inferFromRW. Pass
inferFromTransitions(ArrayRef<PredTransition> LastTransitions,unsigned FromClassIdx,CodeGenSchedModels & SchedModels)1291 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions,
1292                                  unsigned FromClassIdx,
1293                                  CodeGenSchedModels &SchedModels) {
1294   // For each PredTransition, create a new CodeGenSchedTransition, which usually
1295   // requires creating a new SchedClass.
1296   for (ArrayRef<PredTransition>::iterator
1297          I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) {
1298     IdxVec OperWritesVariant;
1299     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1300            WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end();
1301          WSI != WSE; ++WSI) {
1302       // Create a new write representing the expanded sequence.
1303       OperWritesVariant.push_back(
1304         SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false));
1305     }
1306     IdxVec OperReadsVariant;
1307     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1308            RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end();
1309          RSI != RSE; ++RSI) {
1310       // Create a new read representing the expanded sequence.
1311       OperReadsVariant.push_back(
1312         SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true));
1313     }
1314     IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end());
1315     CodeGenSchedTransition SCTrans;
1316     SCTrans.ToClassIdx =
1317       SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant,
1318                                 OperReadsVariant, ProcIndices);
1319     SCTrans.ProcIndices = ProcIndices;
1320     // The final PredTerm is unique set of predicates guarding the transition.
1321     RecVec Preds;
1322     for (SmallVectorImpl<PredCheck>::const_iterator
1323            PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) {
1324       Preds.push_back(PI->Predicate);
1325     }
1326     RecIter PredsEnd = std::unique(Preds.begin(), Preds.end());
1327     Preds.resize(PredsEnd - Preds.begin());
1328     SCTrans.PredTerm = Preds;
1329     SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans);
1330   }
1331 }
1332 
1333 // Create new SchedClasses for the given ReadWrite list. If any of the
1334 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant
1335 // of the ReadWrite list, following Aliases if necessary.
inferFromRW(ArrayRef<unsigned> OperWrites,ArrayRef<unsigned> OperReads,unsigned FromClassIdx,ArrayRef<unsigned> ProcIndices)1336 void CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites,
1337                                      ArrayRef<unsigned> OperReads,
1338                                      unsigned FromClassIdx,
1339                                      ArrayRef<unsigned> ProcIndices) {
1340   DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); dbgs() << ") ");
1341 
1342   // Create a seed transition with an empty PredTerm and the expanded sequences
1343   // of SchedWrites for the current SchedClass.
1344   std::vector<PredTransition> LastTransitions;
1345   LastTransitions.resize(1);
1346   LastTransitions.back().ProcIndices.append(ProcIndices.begin(),
1347                                             ProcIndices.end());
1348 
1349   for (unsigned WriteIdx : OperWrites) {
1350     IdxVec WriteSeq;
1351     expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false);
1352     unsigned Idx = LastTransitions[0].WriteSequences.size();
1353     LastTransitions[0].WriteSequences.resize(Idx + 1);
1354     SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx];
1355     for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI)
1356       Seq.push_back(*WI);
1357     DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1358   }
1359   DEBUG(dbgs() << " Reads: ");
1360   for (unsigned ReadIdx : OperReads) {
1361     IdxVec ReadSeq;
1362     expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true);
1363     unsigned Idx = LastTransitions[0].ReadSequences.size();
1364     LastTransitions[0].ReadSequences.resize(Idx + 1);
1365     SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx];
1366     for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI)
1367       Seq.push_back(*RI);
1368     DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1369   }
1370   DEBUG(dbgs() << '\n');
1371 
1372   // Collect all PredTransitions for individual operands.
1373   // Iterate until no variant writes remain.
1374   while (hasVariant(LastTransitions, *this)) {
1375     PredTransitions Transitions(*this);
1376     for (std::vector<PredTransition>::const_iterator
1377            I = LastTransitions.begin(), E = LastTransitions.end();
1378          I != E; ++I) {
1379       Transitions.substituteVariants(*I);
1380     }
1381     DEBUG(Transitions.dump());
1382     LastTransitions.swap(Transitions.TransVec);
1383   }
1384   // If the first transition has no variants, nothing to do.
1385   if (LastTransitions[0].PredTerm.empty())
1386     return;
1387 
1388   // WARNING: We are about to mutate the SchedClasses vector. Do not refer to
1389   // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions.
1390   inferFromTransitions(LastTransitions, FromClassIdx, *this);
1391 }
1392 
1393 // Check if any processor resource group contains all resource records in
1394 // SubUnits.
hasSuperGroup(RecVec & SubUnits,CodeGenProcModel & PM)1395 bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) {
1396   for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
1397     if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
1398       continue;
1399     RecVec SuperUnits =
1400       PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
1401     RecIter RI = SubUnits.begin(), RE = SubUnits.end();
1402     for ( ; RI != RE; ++RI) {
1403       if (std::find(SuperUnits.begin(), SuperUnits.end(), *RI)
1404           == SuperUnits.end()) {
1405         break;
1406       }
1407     }
1408     if (RI == RE)
1409       return true;
1410   }
1411   return false;
1412 }
1413 
1414 // Verify that overlapping groups have a common supergroup.
verifyProcResourceGroups(CodeGenProcModel & PM)1415 void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) {
1416   for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
1417     if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
1418       continue;
1419     RecVec CheckUnits =
1420       PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
1421     for (unsigned j = i+1; j < e; ++j) {
1422       if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup"))
1423         continue;
1424       RecVec OtherUnits =
1425         PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources");
1426       if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(),
1427                              OtherUnits.begin(), OtherUnits.end())
1428           != CheckUnits.end()) {
1429         // CheckUnits and OtherUnits overlap
1430         OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(),
1431                           CheckUnits.end());
1432         if (!hasSuperGroup(OtherUnits, PM)) {
1433           PrintFatalError((PM.ProcResourceDefs[i])->getLoc(),
1434                           "proc resource group overlaps with "
1435                           + PM.ProcResourceDefs[j]->getName()
1436                           + " but no supergroup contains both.");
1437         }
1438       }
1439     }
1440   }
1441 }
1442 
1443 // Collect and sort WriteRes, ReadAdvance, and ProcResources.
collectProcResources()1444 void CodeGenSchedModels::collectProcResources() {
1445   ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits");
1446   ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
1447 
1448   // Add any subtarget-specific SchedReadWrites that are directly associated
1449   // with processor resources. Refer to the parent SchedClass's ProcIndices to
1450   // determine which processors they apply to.
1451   for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd();
1452        SCI != SCE; ++SCI) {
1453     if (SCI->ItinClassDef)
1454       collectItinProcResources(SCI->ItinClassDef);
1455     else {
1456       // This class may have a default ReadWrite list which can be overriden by
1457       // InstRW definitions.
1458       if (!SCI->InstRWs.empty()) {
1459         for (RecIter RWI = SCI->InstRWs.begin(), RWE = SCI->InstRWs.end();
1460              RWI != RWE; ++RWI) {
1461           Record *RWModelDef = (*RWI)->getValueAsDef("SchedModel");
1462           IdxVec ProcIndices(1, getProcModel(RWModelDef).Index);
1463           IdxVec Writes, Reads;
1464           findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"),
1465                   Writes, Reads);
1466           collectRWResources(Writes, Reads, ProcIndices);
1467         }
1468       }
1469       collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices);
1470     }
1471   }
1472   // Add resources separately defined by each subtarget.
1473   RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes");
1474   for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) {
1475     Record *ModelDef = (*WRI)->getValueAsDef("SchedModel");
1476     addWriteRes(*WRI, getProcModel(ModelDef).Index);
1477   }
1478   RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes");
1479   for (RecIter WRI = SWRDefs.begin(), WRE = SWRDefs.end(); WRI != WRE; ++WRI) {
1480     Record *ModelDef = (*WRI)->getValueAsDef("SchedModel");
1481     addWriteRes(*WRI, getProcModel(ModelDef).Index);
1482   }
1483   RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance");
1484   for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) {
1485     Record *ModelDef = (*RAI)->getValueAsDef("SchedModel");
1486     addReadAdvance(*RAI, getProcModel(ModelDef).Index);
1487   }
1488   RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance");
1489   for (RecIter RAI = SRADefs.begin(), RAE = SRADefs.end(); RAI != RAE; ++RAI) {
1490     if ((*RAI)->getValueInit("SchedModel")->isComplete()) {
1491       Record *ModelDef = (*RAI)->getValueAsDef("SchedModel");
1492       addReadAdvance(*RAI, getProcModel(ModelDef).Index);
1493     }
1494   }
1495   // Add ProcResGroups that are defined within this processor model, which may
1496   // not be directly referenced but may directly specify a buffer size.
1497   RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
1498   for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end();
1499        RI != RE; ++RI) {
1500     if (!(*RI)->getValueInit("SchedModel")->isComplete())
1501       continue;
1502     CodeGenProcModel &PM = getProcModel((*RI)->getValueAsDef("SchedModel"));
1503     RecIter I = std::find(PM.ProcResourceDefs.begin(),
1504                           PM.ProcResourceDefs.end(), *RI);
1505     if (I == PM.ProcResourceDefs.end())
1506       PM.ProcResourceDefs.push_back(*RI);
1507   }
1508   // Finalize each ProcModel by sorting the record arrays.
1509   for (CodeGenProcModel &PM : ProcModels) {
1510     std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(),
1511               LessRecord());
1512     std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(),
1513               LessRecord());
1514     std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(),
1515               LessRecord());
1516     DEBUG(
1517       PM.dump();
1518       dbgs() << "WriteResDefs: ";
1519       for (RecIter RI = PM.WriteResDefs.begin(),
1520              RE = PM.WriteResDefs.end(); RI != RE; ++RI) {
1521         if ((*RI)->isSubClassOf("WriteRes"))
1522           dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " ";
1523         else
1524           dbgs() << (*RI)->getName() << " ";
1525       }
1526       dbgs() << "\nReadAdvanceDefs: ";
1527       for (RecIter RI = PM.ReadAdvanceDefs.begin(),
1528              RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) {
1529         if ((*RI)->isSubClassOf("ReadAdvance"))
1530           dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " ";
1531         else
1532           dbgs() << (*RI)->getName() << " ";
1533       }
1534       dbgs() << "\nProcResourceDefs: ";
1535       for (RecIter RI = PM.ProcResourceDefs.begin(),
1536              RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) {
1537         dbgs() << (*RI)->getName() << " ";
1538       }
1539       dbgs() << '\n');
1540     verifyProcResourceGroups(PM);
1541   }
1542 
1543   ProcResourceDefs.clear();
1544   ProcResGroups.clear();
1545 }
1546 
checkCompleteness()1547 void CodeGenSchedModels::checkCompleteness() {
1548   bool Complete = true;
1549   bool HadCompleteModel = false;
1550   for (const CodeGenProcModel &ProcModel : procModels()) {
1551     if (!ProcModel.ModelDef->getValueAsBit("CompleteModel"))
1552       continue;
1553     for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
1554       if (Inst->hasNoSchedulingInfo)
1555         continue;
1556       if (ProcModel.isUnsupported(*Inst))
1557         continue;
1558       unsigned SCIdx = getSchedClassIdx(*Inst);
1559       if (!SCIdx) {
1560         if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) {
1561           PrintError("No schedule information for instruction '"
1562                      + Inst->TheDef->getName() + "'");
1563           Complete = false;
1564         }
1565         continue;
1566       }
1567 
1568       const CodeGenSchedClass &SC = getSchedClass(SCIdx);
1569       if (!SC.Writes.empty())
1570         continue;
1571       if (SC.ItinClassDef != nullptr)
1572         continue;
1573 
1574       const RecVec &InstRWs = SC.InstRWs;
1575       auto I = std::find_if(InstRWs.begin(), InstRWs.end(),
1576                             [&ProcModel] (const Record *R) {
1577                               return R->getValueAsDef("SchedModel") ==
1578                                      ProcModel.ModelDef;
1579                             });
1580       if (I == InstRWs.end()) {
1581         PrintError("'" + ProcModel.ModelName + "' lacks information for '" +
1582                    Inst->TheDef->getName() + "'");
1583         Complete = false;
1584       }
1585     }
1586     HadCompleteModel = true;
1587   }
1588   if (!Complete) {
1589     errs() << "\n\nIncomplete schedule models found.\n"
1590       << "- Consider setting 'CompleteModel = 0' while developing new models.\n"
1591       << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n"
1592       << "- Instructions should usually have Sched<[...]> as a superclass, "
1593          "you may temporarily use an empty list.\n"
1594       << "- Instructions related to unsupported features can be excluded with "
1595          "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the "
1596          "processor model.\n\n";
1597     PrintFatalError("Incomplete schedule model");
1598   }
1599 }
1600 
1601 // Collect itinerary class resources for each processor.
collectItinProcResources(Record * ItinClassDef)1602 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) {
1603   for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
1604     const CodeGenProcModel &PM = ProcModels[PIdx];
1605     // For all ItinRW entries.
1606     bool HasMatch = false;
1607     for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
1608          II != IE; ++II) {
1609       RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
1610       if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
1611         continue;
1612       if (HasMatch)
1613         PrintFatalError((*II)->getLoc(), "Duplicate itinerary class "
1614                         + ItinClassDef->getName()
1615                         + " in ItinResources for " + PM.ModelName);
1616       HasMatch = true;
1617       IdxVec Writes, Reads;
1618       findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
1619       IdxVec ProcIndices(1, PIdx);
1620       collectRWResources(Writes, Reads, ProcIndices);
1621     }
1622   }
1623 }
1624 
collectRWResources(unsigned RWIdx,bool IsRead,ArrayRef<unsigned> ProcIndices)1625 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead,
1626                                             ArrayRef<unsigned> ProcIndices) {
1627   const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
1628   if (SchedRW.TheDef) {
1629     if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) {
1630       for (unsigned Idx : ProcIndices)
1631         addWriteRes(SchedRW.TheDef, Idx);
1632     }
1633     else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) {
1634       for (unsigned Idx : ProcIndices)
1635         addReadAdvance(SchedRW.TheDef, Idx);
1636     }
1637   }
1638   for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1639        AI != AE; ++AI) {
1640     IdxVec AliasProcIndices;
1641     if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1642       AliasProcIndices.push_back(
1643         getProcModel((*AI)->getValueAsDef("SchedModel")).Index);
1644     }
1645     else
1646       AliasProcIndices = ProcIndices;
1647     const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
1648     assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes");
1649 
1650     IdxVec ExpandedRWs;
1651     expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead);
1652     for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
1653          SI != SE; ++SI) {
1654       collectRWResources(*SI, IsRead, AliasProcIndices);
1655     }
1656   }
1657 }
1658 
1659 // Collect resources for a set of read/write types and processor indices.
collectRWResources(ArrayRef<unsigned> Writes,ArrayRef<unsigned> Reads,ArrayRef<unsigned> ProcIndices)1660 void CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes,
1661                                             ArrayRef<unsigned> Reads,
1662                                             ArrayRef<unsigned> ProcIndices) {
1663 
1664   for (unsigned Idx : Writes)
1665     collectRWResources(Idx, /*IsRead=*/false, ProcIndices);
1666 
1667   for (unsigned Idx : Reads)
1668     collectRWResources(Idx, /*IsRead=*/true, ProcIndices);
1669 }
1670 
1671 
1672 // Find the processor's resource units for this kind of resource.
findProcResUnits(Record * ProcResKind,const CodeGenProcModel & PM) const1673 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind,
1674                                              const CodeGenProcModel &PM) const {
1675   if (ProcResKind->isSubClassOf("ProcResourceUnits"))
1676     return ProcResKind;
1677 
1678   Record *ProcUnitDef = nullptr;
1679   assert(!ProcResourceDefs.empty());
1680   assert(!ProcResGroups.empty());
1681 
1682   for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end();
1683        RI != RE; ++RI) {
1684 
1685     if ((*RI)->getValueAsDef("Kind") == ProcResKind
1686         && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) {
1687       if (ProcUnitDef) {
1688         PrintFatalError((*RI)->getLoc(),
1689                         "Multiple ProcessorResourceUnits associated with "
1690                         + ProcResKind->getName());
1691       }
1692       ProcUnitDef = *RI;
1693     }
1694   }
1695   for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end();
1696        RI != RE; ++RI) {
1697 
1698     if (*RI == ProcResKind
1699         && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) {
1700       if (ProcUnitDef) {
1701         PrintFatalError((*RI)->getLoc(),
1702                         "Multiple ProcessorResourceUnits associated with "
1703                         + ProcResKind->getName());
1704       }
1705       ProcUnitDef = *RI;
1706     }
1707   }
1708   if (!ProcUnitDef) {
1709     PrintFatalError(ProcResKind->getLoc(),
1710                     "No ProcessorResources associated with "
1711                     + ProcResKind->getName());
1712   }
1713   return ProcUnitDef;
1714 }
1715 
1716 // Iteratively add a resource and its super resources.
addProcResource(Record * ProcResKind,CodeGenProcModel & PM)1717 void CodeGenSchedModels::addProcResource(Record *ProcResKind,
1718                                          CodeGenProcModel &PM) {
1719   for (;;) {
1720     Record *ProcResUnits = findProcResUnits(ProcResKind, PM);
1721 
1722     // See if this ProcResource is already associated with this processor.
1723     RecIter I = std::find(PM.ProcResourceDefs.begin(),
1724                           PM.ProcResourceDefs.end(), ProcResUnits);
1725     if (I != PM.ProcResourceDefs.end())
1726       return;
1727 
1728     PM.ProcResourceDefs.push_back(ProcResUnits);
1729     if (ProcResUnits->isSubClassOf("ProcResGroup"))
1730       return;
1731 
1732     if (!ProcResUnits->getValueInit("Super")->isComplete())
1733       return;
1734 
1735     ProcResKind = ProcResUnits->getValueAsDef("Super");
1736   }
1737 }
1738 
1739 // Add resources for a SchedWrite to this processor if they don't exist.
addWriteRes(Record * ProcWriteResDef,unsigned PIdx)1740 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) {
1741   assert(PIdx && "don't add resources to an invalid Processor model");
1742 
1743   RecVec &WRDefs = ProcModels[PIdx].WriteResDefs;
1744   RecIter WRI = std::find(WRDefs.begin(), WRDefs.end(), ProcWriteResDef);
1745   if (WRI != WRDefs.end())
1746     return;
1747   WRDefs.push_back(ProcWriteResDef);
1748 
1749   // Visit ProcResourceKinds referenced by the newly discovered WriteRes.
1750   RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources");
1751   for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end();
1752        WritePRI != WritePRE; ++WritePRI) {
1753     addProcResource(*WritePRI, ProcModels[PIdx]);
1754   }
1755 }
1756 
1757 // Add resources for a ReadAdvance to this processor if they don't exist.
addReadAdvance(Record * ProcReadAdvanceDef,unsigned PIdx)1758 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef,
1759                                         unsigned PIdx) {
1760   RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs;
1761   RecIter I = std::find(RADefs.begin(), RADefs.end(), ProcReadAdvanceDef);
1762   if (I != RADefs.end())
1763     return;
1764   RADefs.push_back(ProcReadAdvanceDef);
1765 }
1766 
getProcResourceIdx(Record * PRDef) const1767 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const {
1768   RecIter PRPos = std::find(ProcResourceDefs.begin(), ProcResourceDefs.end(),
1769                             PRDef);
1770   if (PRPos == ProcResourceDefs.end())
1771     PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in "
1772                     "the ProcResources list for " + ModelName);
1773   // Idx=0 is reserved for invalid.
1774   return 1 + (PRPos - ProcResourceDefs.begin());
1775 }
1776 
isUnsupported(const CodeGenInstruction & Inst) const1777 bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const {
1778   for (const Record *TheDef : UnsupportedFeaturesDefs) {
1779     for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) {
1780       if (TheDef->getName() == PredDef->getName())
1781         return true;
1782     }
1783   }
1784   return false;
1785 }
1786 
1787 #ifndef NDEBUG
dump() const1788 void CodeGenProcModel::dump() const {
1789   dbgs() << Index << ": " << ModelName << " "
1790          << (ModelDef ? ModelDef->getName() : "inferred") << " "
1791          << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
1792 }
1793 
dump() const1794 void CodeGenSchedRW::dump() const {
1795   dbgs() << Name << (IsVariadic ? " (V) " : " ");
1796   if (IsSequence) {
1797     dbgs() << "(";
1798     dumpIdxVec(Sequence);
1799     dbgs() << ")";
1800   }
1801 }
1802 
dump(const CodeGenSchedModels * SchedModels) const1803 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const {
1804   dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n'
1805          << "  Writes: ";
1806   for (unsigned i = 0, N = Writes.size(); i < N; ++i) {
1807     SchedModels->getSchedWrite(Writes[i]).dump();
1808     if (i < N-1) {
1809       dbgs() << '\n';
1810       dbgs().indent(10);
1811     }
1812   }
1813   dbgs() << "\n  Reads: ";
1814   for (unsigned i = 0, N = Reads.size(); i < N; ++i) {
1815     SchedModels->getSchedRead(Reads[i]).dump();
1816     if (i < N-1) {
1817       dbgs() << '\n';
1818       dbgs().indent(10);
1819     }
1820   }
1821   dbgs() << "\n  ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n';
1822   if (!Transitions.empty()) {
1823     dbgs() << "\n Transitions for Proc ";
1824     for (std::vector<CodeGenSchedTransition>::const_iterator
1825            TI = Transitions.begin(), TE = Transitions.end(); TI != TE; ++TI) {
1826       dumpIdxVec(TI->ProcIndices);
1827     }
1828   }
1829 }
1830 
dump() const1831 void PredTransitions::dump() const {
1832   dbgs() << "Expanded Variants:\n";
1833   for (std::vector<PredTransition>::const_iterator
1834          TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) {
1835     dbgs() << "{";
1836     for (SmallVectorImpl<PredCheck>::const_iterator
1837            PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end();
1838          PCI != PCE; ++PCI) {
1839       if (PCI != TI->PredTerm.begin())
1840         dbgs() << ", ";
1841       dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name
1842              << ":" << PCI->Predicate->getName();
1843     }
1844     dbgs() << "},\n  => {";
1845     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
1846            WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end();
1847          WSI != WSE; ++WSI) {
1848       dbgs() << "(";
1849       for (SmallVectorImpl<unsigned>::const_iterator
1850              WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
1851         if (WI != WSI->begin())
1852           dbgs() << ", ";
1853         dbgs() << SchedModels.getSchedWrite(*WI).Name;
1854       }
1855       dbgs() << "),";
1856     }
1857     dbgs() << "}\n";
1858   }
1859 }
1860 #endif // NDEBUG
1861