1 //===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines structures to encapsulate the machine model as described in
10 // the target description.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "CodeGenSchedule.h"
15 #include "CodeGenInstruction.h"
16 #include "CodeGenTarget.h"
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/Regex.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/TableGen/Error.h"
27 #include <algorithm>
28 #include <iterator>
29 #include <utility>
30
31 using namespace llvm;
32
33 #define DEBUG_TYPE "subtarget-emitter"
34
35 #ifndef NDEBUG
dumpIdxVec(ArrayRef<unsigned> V)36 static void dumpIdxVec(ArrayRef<unsigned> V) {
37 for (unsigned Idx : V)
38 dbgs() << Idx << ", ";
39 }
40 #endif
41
42 namespace {
43
44 // (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp.
45 struct InstrsOp : public SetTheory::Operator {
apply__anon2dd1d4cd0111::InstrsOp46 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);
49 }
50 };
51
52 // (instregex "OpcPat",...) Find all instructions matching an opcode pattern.
53 struct InstRegexOp : public SetTheory::Operator {
54 const CodeGenTarget &Target;
InstRegexOp__anon2dd1d4cd0111::InstRegexOp55 InstRegexOp(const CodeGenTarget &t): Target(t) {}
56
57 /// Remove any text inside of parentheses from S.
removeParens__anon2dd1d4cd0111::InstRegexOp58 static std::string removeParens(llvm::StringRef S) {
59 std::string Result;
60 unsigned Paren = 0;
61 // NB: We don't care about escaped parens here.
62 for (char C : S) {
63 switch (C) {
64 case '(':
65 ++Paren;
66 break;
67 case ')':
68 --Paren;
69 break;
70 default:
71 if (Paren == 0)
72 Result += C;
73 }
74 }
75 return Result;
76 }
77
apply__anon2dd1d4cd0111::InstRegexOp78 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
79 ArrayRef<SMLoc> Loc) override {
80 ArrayRef<const CodeGenInstruction *> Instructions =
81 Target.getInstructionsByEnumValue();
82
83 unsigned NumGeneric = Target.getNumFixedInstructions();
84 unsigned NumPseudos = Target.getNumPseudoInstructions();
85 auto Generics = Instructions.slice(0, NumGeneric);
86 auto Pseudos = Instructions.slice(NumGeneric, NumPseudos);
87 auto NonPseudos = Instructions.slice(NumGeneric + NumPseudos);
88
89 for (Init *Arg : make_range(Expr->arg_begin(), Expr->arg_end())) {
90 StringInit *SI = dyn_cast<StringInit>(Arg);
91 if (!SI)
92 PrintFatalError(Loc, "instregex requires pattern string: " +
93 Expr->getAsString());
94 StringRef Original = SI->getValue();
95
96 // Extract a prefix that we can binary search on.
97 static const char RegexMetachars[] = "()^$|*+?.[]\\{}";
98 auto FirstMeta = Original.find_first_of(RegexMetachars);
99
100 // Look for top-level | or ?. We cannot optimize them to binary search.
101 if (removeParens(Original).find_first_of("|?") != std::string::npos)
102 FirstMeta = 0;
103
104 Optional<Regex> Regexpr = None;
105 StringRef Prefix = Original.substr(0, FirstMeta);
106 StringRef PatStr = Original.substr(FirstMeta);
107 if (!PatStr.empty()) {
108 // For the rest use a python-style prefix match.
109 std::string pat = std::string(PatStr);
110 if (pat[0] != '^') {
111 pat.insert(0, "^(");
112 pat.insert(pat.end(), ')');
113 }
114 Regexpr = Regex(pat);
115 }
116
117 int NumMatches = 0;
118
119 // The generic opcodes are unsorted, handle them manually.
120 for (auto *Inst : Generics) {
121 StringRef InstName = Inst->TheDef->getName();
122 if (InstName.startswith(Prefix) &&
123 (!Regexpr || Regexpr->match(InstName.substr(Prefix.size())))) {
124 Elts.insert(Inst->TheDef);
125 NumMatches++;
126 }
127 }
128
129 // Target instructions are split into two ranges: pseudo instructions
130 // first, than non-pseudos. Each range is in lexicographical order
131 // sorted by name. Find the sub-ranges that start with our prefix.
132 struct Comp {
133 bool operator()(const CodeGenInstruction *LHS, StringRef RHS) {
134 return LHS->TheDef->getName() < RHS;
135 }
136 bool operator()(StringRef LHS, const CodeGenInstruction *RHS) {
137 return LHS < RHS->TheDef->getName() &&
138 !RHS->TheDef->getName().startswith(LHS);
139 }
140 };
141 auto Range1 =
142 std::equal_range(Pseudos.begin(), Pseudos.end(), Prefix, Comp());
143 auto Range2 = std::equal_range(NonPseudos.begin(), NonPseudos.end(),
144 Prefix, Comp());
145
146 // For these ranges we know that instruction names start with the prefix.
147 // Check if there's a regex that needs to be checked.
148 const auto HandleNonGeneric = [&](const CodeGenInstruction *Inst) {
149 StringRef InstName = Inst->TheDef->getName();
150 if (!Regexpr || Regexpr->match(InstName.substr(Prefix.size()))) {
151 Elts.insert(Inst->TheDef);
152 NumMatches++;
153 }
154 };
155 std::for_each(Range1.first, Range1.second, HandleNonGeneric);
156 std::for_each(Range2.first, Range2.second, HandleNonGeneric);
157
158 if (0 == NumMatches)
159 PrintFatalError(Loc, "instregex has no matches: " + Original);
160 }
161 }
162 };
163
164 } // end anonymous namespace
165
166 /// CodeGenModels ctor interprets machine model records and populates maps.
CodeGenSchedModels(RecordKeeper & RK,const CodeGenTarget & TGT)167 CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
168 const CodeGenTarget &TGT):
169 Records(RK), Target(TGT) {
170
171 Sets.addFieldExpander("InstRW", "Instrs");
172
173 // Allow Set evaluation to recognize the dags used in InstRW records:
174 // (instrs Op1, Op1...)
175 Sets.addOperator("instrs", std::make_unique<InstrsOp>());
176 Sets.addOperator("instregex", std::make_unique<InstRegexOp>(Target));
177
178 // Instantiate a CodeGenProcModel for each SchedMachineModel with the values
179 // that are explicitly referenced in tablegen records. Resources associated
180 // with each processor will be derived later. Populate ProcModelMap with the
181 // CodeGenProcModel instances.
182 collectProcModels();
183
184 // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly
185 // defined, and populate SchedReads and SchedWrites vectors. Implicit
186 // SchedReadWrites that represent sequences derived from expanded variant will
187 // be inferred later.
188 collectSchedRW();
189
190 // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly
191 // required by an instruction definition, and populate SchedClassIdxMap. Set
192 // NumItineraryClasses to the number of explicit itinerary classes referenced
193 // by instructions. Set NumInstrSchedClasses to the number of itinerary
194 // classes plus any classes implied by instructions that derive from class
195 // Sched and provide SchedRW list. This does not infer any new classes from
196 // SchedVariant.
197 collectSchedClasses();
198
199 // Find instruction itineraries for each processor. Sort and populate
200 // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires
201 // all itinerary classes to be discovered.
202 collectProcItins();
203
204 // Find ItinRW records for each processor and itinerary class.
205 // (For per-operand resources mapped to itinerary classes).
206 collectProcItinRW();
207
208 // Find UnsupportedFeatures records for each processor.
209 // (For per-operand resources mapped to itinerary classes).
210 collectProcUnsupportedFeatures();
211
212 // Infer new SchedClasses from SchedVariant.
213 inferSchedClasses();
214
215 // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and
216 // ProcResourceDefs.
217 LLVM_DEBUG(
218 dbgs() << "\n+++ RESOURCE DEFINITIONS (collectProcResources) +++\n");
219 collectProcResources();
220
221 // Collect optional processor description.
222 collectOptionalProcessorInfo();
223
224 // Check MCInstPredicate definitions.
225 checkMCInstPredicates();
226
227 // Check STIPredicate definitions.
228 checkSTIPredicates();
229
230 // Find STIPredicate definitions for each processor model, and construct
231 // STIPredicateFunction objects.
232 collectSTIPredicates();
233
234 checkCompleteness();
235 }
236
checkSTIPredicates() const237 void CodeGenSchedModels::checkSTIPredicates() const {
238 DenseMap<StringRef, const Record *> Declarations;
239
240 // There cannot be multiple declarations with the same name.
241 const RecVec Decls = Records.getAllDerivedDefinitions("STIPredicateDecl");
242 for (const Record *R : Decls) {
243 StringRef Name = R->getValueAsString("Name");
244 const auto It = Declarations.find(Name);
245 if (It == Declarations.end()) {
246 Declarations[Name] = R;
247 continue;
248 }
249
250 PrintError(R->getLoc(), "STIPredicate " + Name + " multiply declared.");
251 PrintFatalNote(It->second->getLoc(), "Previous declaration was here.");
252 }
253
254 // Disallow InstructionEquivalenceClasses with an empty instruction list.
255 const RecVec Defs =
256 Records.getAllDerivedDefinitions("InstructionEquivalenceClass");
257 for (const Record *R : Defs) {
258 RecVec Opcodes = R->getValueAsListOfDefs("Opcodes");
259 if (Opcodes.empty()) {
260 PrintFatalError(R->getLoc(), "Invalid InstructionEquivalenceClass "
261 "defined with an empty opcode list.");
262 }
263 }
264 }
265
266 // Used by function `processSTIPredicate` to construct a mask of machine
267 // instruction operands.
constructOperandMask(ArrayRef<int64_t> Indices)268 static APInt constructOperandMask(ArrayRef<int64_t> Indices) {
269 APInt OperandMask;
270 if (Indices.empty())
271 return OperandMask;
272
273 int64_t MaxIndex = *std::max_element(Indices.begin(), Indices.end());
274 assert(MaxIndex >= 0 && "Invalid negative indices in input!");
275 OperandMask = OperandMask.zext(MaxIndex + 1);
276 for (const int64_t Index : Indices) {
277 assert(Index >= 0 && "Invalid negative indices!");
278 OperandMask.setBit(Index);
279 }
280
281 return OperandMask;
282 }
283
284 static void
processSTIPredicate(STIPredicateFunction & Fn,const ProcModelMapTy & ProcModelMap)285 processSTIPredicate(STIPredicateFunction &Fn,
286 const ProcModelMapTy &ProcModelMap) {
287 DenseMap<const Record *, unsigned> Opcode2Index;
288 using OpcodeMapPair = std::pair<const Record *, OpcodeInfo>;
289 std::vector<OpcodeMapPair> OpcodeMappings;
290 std::vector<std::pair<APInt, APInt>> OpcodeMasks;
291
292 DenseMap<const Record *, unsigned> Predicate2Index;
293 unsigned NumUniquePredicates = 0;
294
295 // Number unique predicates and opcodes used by InstructionEquivalenceClass
296 // definitions. Each unique opcode will be associated with an OpcodeInfo
297 // object.
298 for (const Record *Def : Fn.getDefinitions()) {
299 RecVec Classes = Def->getValueAsListOfDefs("Classes");
300 for (const Record *EC : Classes) {
301 const Record *Pred = EC->getValueAsDef("Predicate");
302 if (Predicate2Index.find(Pred) == Predicate2Index.end())
303 Predicate2Index[Pred] = NumUniquePredicates++;
304
305 RecVec Opcodes = EC->getValueAsListOfDefs("Opcodes");
306 for (const Record *Opcode : Opcodes) {
307 if (Opcode2Index.find(Opcode) == Opcode2Index.end()) {
308 Opcode2Index[Opcode] = OpcodeMappings.size();
309 OpcodeMappings.emplace_back(Opcode, OpcodeInfo());
310 }
311 }
312 }
313 }
314
315 // Initialize vector `OpcodeMasks` with default values. We want to keep track
316 // of which processors "use" which opcodes. We also want to be able to
317 // identify predicates that are used by different processors for a same
318 // opcode.
319 // This information is used later on by this algorithm to sort OpcodeMapping
320 // elements based on their processor and predicate sets.
321 OpcodeMasks.resize(OpcodeMappings.size());
322 APInt DefaultProcMask(ProcModelMap.size(), 0);
323 APInt DefaultPredMask(NumUniquePredicates, 0);
324 for (std::pair<APInt, APInt> &MaskPair : OpcodeMasks)
325 MaskPair = std::make_pair(DefaultProcMask, DefaultPredMask);
326
327 // Construct a OpcodeInfo object for every unique opcode declared by an
328 // InstructionEquivalenceClass definition.
329 for (const Record *Def : Fn.getDefinitions()) {
330 RecVec Classes = Def->getValueAsListOfDefs("Classes");
331 const Record *SchedModel = Def->getValueAsDef("SchedModel");
332 unsigned ProcIndex = ProcModelMap.find(SchedModel)->second;
333 APInt ProcMask(ProcModelMap.size(), 0);
334 ProcMask.setBit(ProcIndex);
335
336 for (const Record *EC : Classes) {
337 RecVec Opcodes = EC->getValueAsListOfDefs("Opcodes");
338
339 std::vector<int64_t> OpIndices =
340 EC->getValueAsListOfInts("OperandIndices");
341 APInt OperandMask = constructOperandMask(OpIndices);
342
343 const Record *Pred = EC->getValueAsDef("Predicate");
344 APInt PredMask(NumUniquePredicates, 0);
345 PredMask.setBit(Predicate2Index[Pred]);
346
347 for (const Record *Opcode : Opcodes) {
348 unsigned OpcodeIdx = Opcode2Index[Opcode];
349 if (OpcodeMasks[OpcodeIdx].first[ProcIndex]) {
350 std::string Message =
351 "Opcode " + Opcode->getName().str() +
352 " used by multiple InstructionEquivalenceClass definitions.";
353 PrintFatalError(EC->getLoc(), Message);
354 }
355 OpcodeMasks[OpcodeIdx].first |= ProcMask;
356 OpcodeMasks[OpcodeIdx].second |= PredMask;
357 OpcodeInfo &OI = OpcodeMappings[OpcodeIdx].second;
358
359 OI.addPredicateForProcModel(ProcMask, OperandMask, Pred);
360 }
361 }
362 }
363
364 // Sort OpcodeMappings elements based on their CPU and predicate masks.
365 // As a last resort, order elements by opcode identifier.
366 llvm::sort(OpcodeMappings,
367 [&](const OpcodeMapPair &Lhs, const OpcodeMapPair &Rhs) {
368 unsigned LhsIdx = Opcode2Index[Lhs.first];
369 unsigned RhsIdx = Opcode2Index[Rhs.first];
370 const std::pair<APInt, APInt> &LhsMasks = OpcodeMasks[LhsIdx];
371 const std::pair<APInt, APInt> &RhsMasks = OpcodeMasks[RhsIdx];
372
373 auto LessThan = [](const APInt &Lhs, const APInt &Rhs) {
374 unsigned LhsCountPopulation = Lhs.countPopulation();
375 unsigned RhsCountPopulation = Rhs.countPopulation();
376 return ((LhsCountPopulation < RhsCountPopulation) ||
377 ((LhsCountPopulation == RhsCountPopulation) &&
378 (Lhs.countLeadingZeros() > Rhs.countLeadingZeros())));
379 };
380
381 if (LhsMasks.first != RhsMasks.first)
382 return LessThan(LhsMasks.first, RhsMasks.first);
383
384 if (LhsMasks.second != RhsMasks.second)
385 return LessThan(LhsMasks.second, RhsMasks.second);
386
387 return LhsIdx < RhsIdx;
388 });
389
390 // Now construct opcode groups. Groups are used by the SubtargetEmitter when
391 // expanding the body of a STIPredicate function. In particular, each opcode
392 // group is expanded into a sequence of labels in a switch statement.
393 // It identifies opcodes for which different processors define same predicates
394 // and same opcode masks.
395 for (OpcodeMapPair &Info : OpcodeMappings)
396 Fn.addOpcode(Info.first, std::move(Info.second));
397 }
398
collectSTIPredicates()399 void CodeGenSchedModels::collectSTIPredicates() {
400 // Map STIPredicateDecl records to elements of vector
401 // CodeGenSchedModels::STIPredicates.
402 DenseMap<const Record *, unsigned> Decl2Index;
403
404 RecVec RV = Records.getAllDerivedDefinitions("STIPredicate");
405 for (const Record *R : RV) {
406 const Record *Decl = R->getValueAsDef("Declaration");
407
408 const auto It = Decl2Index.find(Decl);
409 if (It == Decl2Index.end()) {
410 Decl2Index[Decl] = STIPredicates.size();
411 STIPredicateFunction Predicate(Decl);
412 Predicate.addDefinition(R);
413 STIPredicates.emplace_back(std::move(Predicate));
414 continue;
415 }
416
417 STIPredicateFunction &PreviousDef = STIPredicates[It->second];
418 PreviousDef.addDefinition(R);
419 }
420
421 for (STIPredicateFunction &Fn : STIPredicates)
422 processSTIPredicate(Fn, ProcModelMap);
423 }
424
addPredicateForProcModel(const llvm::APInt & CpuMask,const llvm::APInt & OperandMask,const Record * Predicate)425 void OpcodeInfo::addPredicateForProcModel(const llvm::APInt &CpuMask,
426 const llvm::APInt &OperandMask,
427 const Record *Predicate) {
428 auto It = llvm::find_if(
429 Predicates, [&OperandMask, &Predicate](const PredicateInfo &P) {
430 return P.Predicate == Predicate && P.OperandMask == OperandMask;
431 });
432 if (It == Predicates.end()) {
433 Predicates.emplace_back(CpuMask, OperandMask, Predicate);
434 return;
435 }
436 It->ProcModelMask |= CpuMask;
437 }
438
checkMCInstPredicates() const439 void CodeGenSchedModels::checkMCInstPredicates() const {
440 RecVec MCPredicates = Records.getAllDerivedDefinitions("TIIPredicate");
441 if (MCPredicates.empty())
442 return;
443
444 // A target cannot have multiple TIIPredicate definitions with a same name.
445 llvm::StringMap<const Record *> TIIPredicates(MCPredicates.size());
446 for (const Record *TIIPred : MCPredicates) {
447 StringRef Name = TIIPred->getValueAsString("FunctionName");
448 StringMap<const Record *>::const_iterator It = TIIPredicates.find(Name);
449 if (It == TIIPredicates.end()) {
450 TIIPredicates[Name] = TIIPred;
451 continue;
452 }
453
454 PrintError(TIIPred->getLoc(),
455 "TIIPredicate " + Name + " is multiply defined.");
456 PrintFatalNote(It->second->getLoc(),
457 " Previous definition of " + Name + " was here.");
458 }
459 }
460
collectRetireControlUnits()461 void CodeGenSchedModels::collectRetireControlUnits() {
462 RecVec Units = Records.getAllDerivedDefinitions("RetireControlUnit");
463
464 for (Record *RCU : Units) {
465 CodeGenProcModel &PM = getProcModel(RCU->getValueAsDef("SchedModel"));
466 if (PM.RetireControlUnit) {
467 PrintError(RCU->getLoc(),
468 "Expected a single RetireControlUnit definition");
469 PrintNote(PM.RetireControlUnit->getLoc(),
470 "Previous definition of RetireControlUnit was here");
471 }
472 PM.RetireControlUnit = RCU;
473 }
474 }
475
collectLoadStoreQueueInfo()476 void CodeGenSchedModels::collectLoadStoreQueueInfo() {
477 RecVec Queues = Records.getAllDerivedDefinitions("MemoryQueue");
478
479 for (Record *Queue : Queues) {
480 CodeGenProcModel &PM = getProcModel(Queue->getValueAsDef("SchedModel"));
481 if (Queue->isSubClassOf("LoadQueue")) {
482 if (PM.LoadQueue) {
483 PrintError(Queue->getLoc(),
484 "Expected a single LoadQueue definition");
485 PrintNote(PM.LoadQueue->getLoc(),
486 "Previous definition of LoadQueue was here");
487 }
488
489 PM.LoadQueue = Queue;
490 }
491
492 if (Queue->isSubClassOf("StoreQueue")) {
493 if (PM.StoreQueue) {
494 PrintError(Queue->getLoc(),
495 "Expected a single StoreQueue definition");
496 PrintNote(PM.LoadQueue->getLoc(),
497 "Previous definition of StoreQueue was here");
498 }
499
500 PM.StoreQueue = Queue;
501 }
502 }
503 }
504
505 /// Collect optional processor information.
collectOptionalProcessorInfo()506 void CodeGenSchedModels::collectOptionalProcessorInfo() {
507 // Find register file definitions for each processor.
508 collectRegisterFiles();
509
510 // Collect processor RetireControlUnit descriptors if available.
511 collectRetireControlUnits();
512
513 // Collect information about load/store queues.
514 collectLoadStoreQueueInfo();
515
516 checkCompleteness();
517 }
518
519 /// Gather all processor models.
collectProcModels()520 void CodeGenSchedModels::collectProcModels() {
521 RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor");
522 llvm::sort(ProcRecords, LessRecordFieldName());
523
524 // Reserve space because we can. Reallocation would be ok.
525 ProcModels.reserve(ProcRecords.size()+1);
526
527 // Use idx=0 for NoModel/NoItineraries.
528 Record *NoModelDef = Records.getDef("NoSchedModel");
529 Record *NoItinsDef = Records.getDef("NoItineraries");
530 ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef);
531 ProcModelMap[NoModelDef] = 0;
532
533 // For each processor, find a unique machine model.
534 LLVM_DEBUG(dbgs() << "+++ PROCESSOR MODELs (addProcModel) +++\n");
535 for (Record *ProcRecord : ProcRecords)
536 addProcModel(ProcRecord);
537 }
538
539 /// Get a unique processor model based on the defined MachineModel and
540 /// ProcessorItineraries.
addProcModel(Record * ProcDef)541 void CodeGenSchedModels::addProcModel(Record *ProcDef) {
542 Record *ModelKey = getModelOrItinDef(ProcDef);
543 if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second)
544 return;
545
546 std::string Name = std::string(ModelKey->getName());
547 if (ModelKey->isSubClassOf("SchedMachineModel")) {
548 Record *ItinsDef = ModelKey->getValueAsDef("Itineraries");
549 ProcModels.emplace_back(ProcModels.size(), Name, ModelKey, ItinsDef);
550 }
551 else {
552 // An itinerary is defined without a machine model. Infer a new model.
553 if (!ModelKey->getValueAsListOfDefs("IID").empty())
554 Name = Name + "Model";
555 ProcModels.emplace_back(ProcModels.size(), Name,
556 ProcDef->getValueAsDef("SchedModel"), ModelKey);
557 }
558 LLVM_DEBUG(ProcModels.back().dump());
559 }
560
561 // Recursively find all reachable SchedReadWrite records.
scanSchedRW(Record * RWDef,RecVec & RWDefs,SmallPtrSet<Record *,16> & RWSet)562 static void scanSchedRW(Record *RWDef, RecVec &RWDefs,
563 SmallPtrSet<Record*, 16> &RWSet) {
564 if (!RWSet.insert(RWDef).second)
565 return;
566 RWDefs.push_back(RWDef);
567 // Reads don't currently have sequence records, but it can be added later.
568 if (RWDef->isSubClassOf("WriteSequence")) {
569 RecVec Seq = RWDef->getValueAsListOfDefs("Writes");
570 for (Record *WSRec : Seq)
571 scanSchedRW(WSRec, RWDefs, RWSet);
572 }
573 else if (RWDef->isSubClassOf("SchedVariant")) {
574 // Visit each variant (guarded by a different predicate).
575 RecVec Vars = RWDef->getValueAsListOfDefs("Variants");
576 for (Record *Variant : Vars) {
577 // Visit each RW in the sequence selected by the current variant.
578 RecVec Selected = Variant->getValueAsListOfDefs("Selected");
579 for (Record *SelDef : Selected)
580 scanSchedRW(SelDef, RWDefs, RWSet);
581 }
582 }
583 }
584
585 // Collect and sort all SchedReadWrites reachable via tablegen records.
586 // More may be inferred later when inferring new SchedClasses from variants.
collectSchedRW()587 void CodeGenSchedModels::collectSchedRW() {
588 // Reserve idx=0 for invalid writes/reads.
589 SchedWrites.resize(1);
590 SchedReads.resize(1);
591
592 SmallPtrSet<Record*, 16> RWSet;
593
594 // Find all SchedReadWrites referenced by instruction defs.
595 RecVec SWDefs, SRDefs;
596 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
597 Record *SchedDef = Inst->TheDef;
598 if (SchedDef->isValueUnset("SchedRW"))
599 continue;
600 RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW");
601 for (Record *RW : RWs) {
602 if (RW->isSubClassOf("SchedWrite"))
603 scanSchedRW(RW, SWDefs, RWSet);
604 else {
605 assert(RW->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
606 scanSchedRW(RW, SRDefs, RWSet);
607 }
608 }
609 }
610 // Find all ReadWrites referenced by InstRW.
611 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
612 for (Record *InstRWDef : InstRWDefs) {
613 // For all OperandReadWrites.
614 RecVec RWDefs = InstRWDef->getValueAsListOfDefs("OperandReadWrites");
615 for (Record *RWDef : RWDefs) {
616 if (RWDef->isSubClassOf("SchedWrite"))
617 scanSchedRW(RWDef, SWDefs, RWSet);
618 else {
619 assert(RWDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
620 scanSchedRW(RWDef, SRDefs, RWSet);
621 }
622 }
623 }
624 // Find all ReadWrites referenced by ItinRW.
625 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
626 for (Record *ItinRWDef : ItinRWDefs) {
627 // For all OperandReadWrites.
628 RecVec RWDefs = ItinRWDef->getValueAsListOfDefs("OperandReadWrites");
629 for (Record *RWDef : RWDefs) {
630 if (RWDef->isSubClassOf("SchedWrite"))
631 scanSchedRW(RWDef, SWDefs, RWSet);
632 else {
633 assert(RWDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
634 scanSchedRW(RWDef, SRDefs, RWSet);
635 }
636 }
637 }
638 // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted
639 // for the loop below that initializes Alias vectors.
640 RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias");
641 llvm::sort(AliasDefs, LessRecord());
642 for (Record *ADef : AliasDefs) {
643 Record *MatchDef = ADef->getValueAsDef("MatchRW");
644 Record *AliasDef = ADef->getValueAsDef("AliasRW");
645 if (MatchDef->isSubClassOf("SchedWrite")) {
646 if (!AliasDef->isSubClassOf("SchedWrite"))
647 PrintFatalError(ADef->getLoc(), "SchedWrite Alias must be SchedWrite");
648 scanSchedRW(AliasDef, SWDefs, RWSet);
649 }
650 else {
651 assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
652 if (!AliasDef->isSubClassOf("SchedRead"))
653 PrintFatalError(ADef->getLoc(), "SchedRead Alias must be SchedRead");
654 scanSchedRW(AliasDef, SRDefs, RWSet);
655 }
656 }
657 // Sort and add the SchedReadWrites directly referenced by instructions or
658 // itinerary resources. Index reads and writes in separate domains.
659 llvm::sort(SWDefs, LessRecord());
660 for (Record *SWDef : SWDefs) {
661 assert(!getSchedRWIdx(SWDef, /*IsRead=*/false) && "duplicate SchedWrite");
662 SchedWrites.emplace_back(SchedWrites.size(), SWDef);
663 }
664 llvm::sort(SRDefs, LessRecord());
665 for (Record *SRDef : SRDefs) {
666 assert(!getSchedRWIdx(SRDef, /*IsRead-*/true) && "duplicate SchedWrite");
667 SchedReads.emplace_back(SchedReads.size(), SRDef);
668 }
669 // Initialize WriteSequence vectors.
670 for (CodeGenSchedRW &CGRW : SchedWrites) {
671 if (!CGRW.IsSequence)
672 continue;
673 findRWs(CGRW.TheDef->getValueAsListOfDefs("Writes"), CGRW.Sequence,
674 /*IsRead=*/false);
675 }
676 // Initialize Aliases vectors.
677 for (Record *ADef : AliasDefs) {
678 Record *AliasDef = ADef->getValueAsDef("AliasRW");
679 getSchedRW(AliasDef).IsAlias = true;
680 Record *MatchDef = ADef->getValueAsDef("MatchRW");
681 CodeGenSchedRW &RW = getSchedRW(MatchDef);
682 if (RW.IsAlias)
683 PrintFatalError(ADef->getLoc(), "Cannot Alias an Alias");
684 RW.Aliases.push_back(ADef);
685 }
686 LLVM_DEBUG(
687 dbgs() << "\n+++ SCHED READS and WRITES (collectSchedRW) +++\n";
688 for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) {
689 dbgs() << WIdx << ": ";
690 SchedWrites[WIdx].dump();
691 dbgs() << '\n';
692 } for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd;
693 ++RIdx) {
694 dbgs() << RIdx << ": ";
695 SchedReads[RIdx].dump();
696 dbgs() << '\n';
697 } RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite");
698 for (Record *RWDef
699 : RWDefs) {
700 if (!getSchedRWIdx(RWDef, RWDef->isSubClassOf("SchedRead"))) {
701 StringRef Name = RWDef->getName();
702 if (Name != "NoWrite" && Name != "ReadDefault")
703 dbgs() << "Unused SchedReadWrite " << Name << '\n';
704 }
705 });
706 }
707
708 /// Compute a SchedWrite name from a sequence of writes.
genRWName(ArrayRef<unsigned> Seq,bool IsRead)709 std::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) {
710 std::string Name("(");
711 for (auto I = Seq.begin(), E = Seq.end(); I != E; ++I) {
712 if (I != Seq.begin())
713 Name += '_';
714 Name += getSchedRW(*I, IsRead).Name;
715 }
716 Name += ')';
717 return Name;
718 }
719
getSchedRWIdx(const Record * Def,bool IsRead) const720 unsigned CodeGenSchedModels::getSchedRWIdx(const Record *Def,
721 bool IsRead) const {
722 const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
723 const auto I = find_if(
724 RWVec, [Def](const CodeGenSchedRW &RW) { return RW.TheDef == Def; });
725 return I == RWVec.end() ? 0 : std::distance(RWVec.begin(), I);
726 }
727
hasReadOfWrite(Record * WriteDef) const728 bool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const {
729 for (const CodeGenSchedRW &Read : SchedReads) {
730 Record *ReadDef = Read.TheDef;
731 if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance"))
732 continue;
733
734 RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites");
735 if (is_contained(ValidWrites, WriteDef)) {
736 return true;
737 }
738 }
739 return false;
740 }
741
splitSchedReadWrites(const RecVec & RWDefs,RecVec & WriteDefs,RecVec & ReadDefs)742 static void splitSchedReadWrites(const RecVec &RWDefs,
743 RecVec &WriteDefs, RecVec &ReadDefs) {
744 for (Record *RWDef : RWDefs) {
745 if (RWDef->isSubClassOf("SchedWrite"))
746 WriteDefs.push_back(RWDef);
747 else {
748 assert(RWDef->isSubClassOf("SchedRead") && "unknown SchedReadWrite");
749 ReadDefs.push_back(RWDef);
750 }
751 }
752 }
753
754 // Split the SchedReadWrites defs and call findRWs for each list.
findRWs(const RecVec & RWDefs,IdxVec & Writes,IdxVec & Reads) const755 void CodeGenSchedModels::findRWs(const RecVec &RWDefs,
756 IdxVec &Writes, IdxVec &Reads) const {
757 RecVec WriteDefs;
758 RecVec ReadDefs;
759 splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs);
760 findRWs(WriteDefs, Writes, false);
761 findRWs(ReadDefs, Reads, true);
762 }
763
764 // Call getSchedRWIdx for all elements in a sequence of SchedRW defs.
findRWs(const RecVec & RWDefs,IdxVec & RWs,bool IsRead) const765 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs,
766 bool IsRead) const {
767 for (Record *RWDef : RWDefs) {
768 unsigned Idx = getSchedRWIdx(RWDef, IsRead);
769 assert(Idx && "failed to collect SchedReadWrite");
770 RWs.push_back(Idx);
771 }
772 }
773
expandRWSequence(unsigned RWIdx,IdxVec & RWSeq,bool IsRead) const774 void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq,
775 bool IsRead) const {
776 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
777 if (!SchedRW.IsSequence) {
778 RWSeq.push_back(RWIdx);
779 return;
780 }
781 int Repeat =
782 SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1;
783 for (int i = 0; i < Repeat; ++i) {
784 for (unsigned I : SchedRW.Sequence) {
785 expandRWSequence(I, RWSeq, IsRead);
786 }
787 }
788 }
789
790 // Expand a SchedWrite as a sequence following any aliases that coincide with
791 // the given processor model.
expandRWSeqForProc(unsigned RWIdx,IdxVec & RWSeq,bool IsRead,const CodeGenProcModel & ProcModel) const792 void CodeGenSchedModels::expandRWSeqForProc(
793 unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
794 const CodeGenProcModel &ProcModel) const {
795
796 const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead);
797 Record *AliasDef = nullptr;
798 for (const Record *Rec : SchedWrite.Aliases) {
799 const CodeGenSchedRW &AliasRW = getSchedRW(Rec->getValueAsDef("AliasRW"));
800 if (Rec->getValueInit("SchedModel")->isComplete()) {
801 Record *ModelDef = Rec->getValueAsDef("SchedModel");
802 if (&getProcModel(ModelDef) != &ProcModel)
803 continue;
804 }
805 if (AliasDef)
806 PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases "
807 "defined for processor " + ProcModel.ModelName +
808 " Ensure only one SchedAlias exists per RW.");
809 AliasDef = AliasRW.TheDef;
810 }
811 if (AliasDef) {
812 expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead),
813 RWSeq, IsRead,ProcModel);
814 return;
815 }
816 if (!SchedWrite.IsSequence) {
817 RWSeq.push_back(RWIdx);
818 return;
819 }
820 int Repeat =
821 SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1;
822 for (int I = 0, E = Repeat; I < E; ++I) {
823 for (unsigned Idx : SchedWrite.Sequence) {
824 expandRWSeqForProc(Idx, RWSeq, IsRead, ProcModel);
825 }
826 }
827 }
828
829 // Find the existing SchedWrite that models this sequence of writes.
findRWForSequence(ArrayRef<unsigned> Seq,bool IsRead)830 unsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq,
831 bool IsRead) {
832 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
833
834 auto I = find_if(RWVec, [Seq](CodeGenSchedRW &RW) {
835 return makeArrayRef(RW.Sequence) == Seq;
836 });
837 // Index zero reserved for invalid RW.
838 return I == RWVec.end() ? 0 : std::distance(RWVec.begin(), I);
839 }
840
841 /// Add this ReadWrite if it doesn't already exist.
findOrInsertRW(ArrayRef<unsigned> Seq,bool IsRead)842 unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq,
843 bool IsRead) {
844 assert(!Seq.empty() && "cannot insert empty sequence");
845 if (Seq.size() == 1)
846 return Seq.back();
847
848 unsigned Idx = findRWForSequence(Seq, IsRead);
849 if (Idx)
850 return Idx;
851
852 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites;
853 unsigned RWIdx = RWVec.size();
854 CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead));
855 RWVec.push_back(SchedRW);
856 return RWIdx;
857 }
858
859 /// Visit all the instruction definitions for this target to gather and
860 /// enumerate the itinerary classes. These are the explicitly specified
861 /// SchedClasses. More SchedClasses may be inferred.
collectSchedClasses()862 void CodeGenSchedModels::collectSchedClasses() {
863
864 // NoItinerary is always the first class at Idx=0
865 assert(SchedClasses.empty() && "Expected empty sched class");
866 SchedClasses.emplace_back(0, "NoInstrModel",
867 Records.getDef("NoItinerary"));
868 SchedClasses.back().ProcIndices.push_back(0);
869
870 // Create a SchedClass for each unique combination of itinerary class and
871 // SchedRW list.
872 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
873 Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary");
874 IdxVec Writes, Reads;
875 if (!Inst->TheDef->isValueUnset("SchedRW"))
876 findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
877
878 // ProcIdx == 0 indicates the class applies to all processors.
879 unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, /*ProcIndices*/{0});
880 InstrClassMap[Inst->TheDef] = SCIdx;
881 }
882 // Create classes for InstRW defs.
883 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
884 llvm::sort(InstRWDefs, LessRecord());
885 LLVM_DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n");
886 for (Record *RWDef : InstRWDefs)
887 createInstRWClass(RWDef);
888
889 NumInstrSchedClasses = SchedClasses.size();
890
891 bool EnableDump = false;
892 LLVM_DEBUG(EnableDump = true);
893 if (!EnableDump)
894 return;
895
896 LLVM_DEBUG(
897 dbgs()
898 << "\n+++ ITINERARIES and/or MACHINE MODELS (collectSchedClasses) +++\n");
899 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
900 StringRef InstName = Inst->TheDef->getName();
901 unsigned SCIdx = getSchedClassIdx(*Inst);
902 if (!SCIdx) {
903 LLVM_DEBUG({
904 if (!Inst->hasNoSchedulingInfo)
905 dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n';
906 });
907 continue;
908 }
909 CodeGenSchedClass &SC = getSchedClass(SCIdx);
910 if (SC.ProcIndices[0] != 0)
911 PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class "
912 "must not be subtarget specific.");
913
914 IdxVec ProcIndices;
915 if (SC.ItinClassDef->getName() != "NoItinerary") {
916 ProcIndices.push_back(0);
917 dbgs() << "Itinerary for " << InstName << ": "
918 << SC.ItinClassDef->getName() << '\n';
919 }
920 if (!SC.Writes.empty()) {
921 ProcIndices.push_back(0);
922 LLVM_DEBUG({
923 dbgs() << "SchedRW machine model for " << InstName;
924 for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE;
925 ++WI)
926 dbgs() << " " << SchedWrites[*WI].Name;
927 for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI)
928 dbgs() << " " << SchedReads[*RI].Name;
929 dbgs() << '\n';
930 });
931 }
932 const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs;
933 for (Record *RWDef : RWDefs) {
934 const CodeGenProcModel &ProcModel =
935 getProcModel(RWDef->getValueAsDef("SchedModel"));
936 ProcIndices.push_back(ProcModel.Index);
937 LLVM_DEBUG(dbgs() << "InstRW on " << ProcModel.ModelName << " for "
938 << InstName);
939 IdxVec Writes;
940 IdxVec Reads;
941 findRWs(RWDef->getValueAsListOfDefs("OperandReadWrites"),
942 Writes, Reads);
943 LLVM_DEBUG({
944 for (unsigned WIdx : Writes)
945 dbgs() << " " << SchedWrites[WIdx].Name;
946 for (unsigned RIdx : Reads)
947 dbgs() << " " << SchedReads[RIdx].Name;
948 dbgs() << '\n';
949 });
950 }
951 // If ProcIndices contains zero, the class applies to all processors.
952 LLVM_DEBUG({
953 if (!std::count(ProcIndices.begin(), ProcIndices.end(), 0)) {
954 for (const CodeGenProcModel &PM : ProcModels) {
955 if (!std::count(ProcIndices.begin(), ProcIndices.end(), PM.Index))
956 dbgs() << "No machine model for " << Inst->TheDef->getName()
957 << " on processor " << PM.ModelName << '\n';
958 }
959 }
960 });
961 }
962 }
963
964 // Get the SchedClass index for an instruction.
965 unsigned
getSchedClassIdx(const CodeGenInstruction & Inst) const966 CodeGenSchedModels::getSchedClassIdx(const CodeGenInstruction &Inst) const {
967 return InstrClassMap.lookup(Inst.TheDef);
968 }
969
970 std::string
createSchedClassName(Record * ItinClassDef,ArrayRef<unsigned> OperWrites,ArrayRef<unsigned> OperReads)971 CodeGenSchedModels::createSchedClassName(Record *ItinClassDef,
972 ArrayRef<unsigned> OperWrites,
973 ArrayRef<unsigned> OperReads) {
974
975 std::string Name;
976 if (ItinClassDef && ItinClassDef->getName() != "NoItinerary")
977 Name = std::string(ItinClassDef->getName());
978 for (unsigned Idx : OperWrites) {
979 if (!Name.empty())
980 Name += '_';
981 Name += SchedWrites[Idx].Name;
982 }
983 for (unsigned Idx : OperReads) {
984 Name += '_';
985 Name += SchedReads[Idx].Name;
986 }
987 return Name;
988 }
989
createSchedClassName(const RecVec & InstDefs)990 std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) {
991
992 std::string Name;
993 for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) {
994 if (I != InstDefs.begin())
995 Name += '_';
996 Name += (*I)->getName();
997 }
998 return Name;
999 }
1000
1001 /// Add an inferred sched class from an itinerary class and per-operand list of
1002 /// SchedWrites and SchedReads. ProcIndices contains the set of IDs of
1003 /// processors that may utilize this class.
addSchedClass(Record * ItinClassDef,ArrayRef<unsigned> OperWrites,ArrayRef<unsigned> OperReads,ArrayRef<unsigned> ProcIndices)1004 unsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef,
1005 ArrayRef<unsigned> OperWrites,
1006 ArrayRef<unsigned> OperReads,
1007 ArrayRef<unsigned> ProcIndices) {
1008 assert(!ProcIndices.empty() && "expect at least one ProcIdx");
1009
1010 auto IsKeyEqual = [=](const CodeGenSchedClass &SC) {
1011 return SC.isKeyEqual(ItinClassDef, OperWrites, OperReads);
1012 };
1013
1014 auto I = find_if(make_range(schedClassBegin(), schedClassEnd()), IsKeyEqual);
1015 unsigned Idx = I == schedClassEnd() ? 0 : std::distance(schedClassBegin(), I);
1016 if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) {
1017 IdxVec PI;
1018 std::set_union(SchedClasses[Idx].ProcIndices.begin(),
1019 SchedClasses[Idx].ProcIndices.end(),
1020 ProcIndices.begin(), ProcIndices.end(),
1021 std::back_inserter(PI));
1022 SchedClasses[Idx].ProcIndices = std::move(PI);
1023 return Idx;
1024 }
1025 Idx = SchedClasses.size();
1026 SchedClasses.emplace_back(Idx,
1027 createSchedClassName(ItinClassDef, OperWrites,
1028 OperReads),
1029 ItinClassDef);
1030 CodeGenSchedClass &SC = SchedClasses.back();
1031 SC.Writes = OperWrites;
1032 SC.Reads = OperReads;
1033 SC.ProcIndices = ProcIndices;
1034
1035 return Idx;
1036 }
1037
1038 // Create classes for each set of opcodes that are in the same InstReadWrite
1039 // definition across all processors.
createInstRWClass(Record * InstRWDef)1040 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) {
1041 // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that
1042 // intersects with an existing class via a previous InstRWDef. Instrs that do
1043 // not intersect with an existing class refer back to their former class as
1044 // determined from ItinDef or SchedRW.
1045 SmallMapVector<unsigned, SmallVector<Record *, 8>, 4> ClassInstrs;
1046 // Sort Instrs into sets.
1047 const RecVec *InstDefs = Sets.expand(InstRWDef);
1048 if (InstDefs->empty())
1049 PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes");
1050
1051 for (Record *InstDef : *InstDefs) {
1052 InstClassMapTy::const_iterator Pos = InstrClassMap.find(InstDef);
1053 if (Pos == InstrClassMap.end())
1054 PrintFatalError(InstDef->getLoc(), "No sched class for instruction.");
1055 unsigned SCIdx = Pos->second;
1056 ClassInstrs[SCIdx].push_back(InstDef);
1057 }
1058 // For each set of Instrs, create a new class if necessary, and map or remap
1059 // the Instrs to it.
1060 for (auto &Entry : ClassInstrs) {
1061 unsigned OldSCIdx = Entry.first;
1062 ArrayRef<Record*> InstDefs = Entry.second;
1063 // If the all instrs in the current class are accounted for, then leave
1064 // them mapped to their old class.
1065 if (OldSCIdx) {
1066 const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs;
1067 if (!RWDefs.empty()) {
1068 const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]);
1069 unsigned OrigNumInstrs =
1070 count_if(*OrigInstDefs, [&](Record *OIDef) {
1071 return InstrClassMap[OIDef] == OldSCIdx;
1072 });
1073 if (OrigNumInstrs == InstDefs.size()) {
1074 assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 &&
1075 "expected a generic SchedClass");
1076 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel");
1077 // Make sure we didn't already have a InstRW containing this
1078 // instruction on this model.
1079 for (Record *RWD : RWDefs) {
1080 if (RWD->getValueAsDef("SchedModel") == RWModelDef &&
1081 RWModelDef->getValueAsBit("FullInstRWOverlapCheck")) {
1082 assert(!InstDefs.empty()); // Checked at function start.
1083 PrintError(
1084 InstRWDef->getLoc(),
1085 "Overlapping InstRW definition for \"" +
1086 InstDefs.front()->getName() +
1087 "\" also matches previous \"" +
1088 RWD->getValue("Instrs")->getValue()->getAsString() +
1089 "\".");
1090 PrintFatalNote(RWD->getLoc(), "Previous match was here.");
1091 }
1092 }
1093 LLVM_DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":"
1094 << SchedClasses[OldSCIdx].Name << " on "
1095 << RWModelDef->getName() << "\n");
1096 SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef);
1097 continue;
1098 }
1099 }
1100 }
1101 unsigned SCIdx = SchedClasses.size();
1102 SchedClasses.emplace_back(SCIdx, createSchedClassName(InstDefs), nullptr);
1103 CodeGenSchedClass &SC = SchedClasses.back();
1104 LLVM_DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on "
1105 << InstRWDef->getValueAsDef("SchedModel")->getName()
1106 << "\n");
1107
1108 // Preserve ItinDef and Writes/Reads for processors without an InstRW entry.
1109 SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef;
1110 SC.Writes = SchedClasses[OldSCIdx].Writes;
1111 SC.Reads = SchedClasses[OldSCIdx].Reads;
1112 SC.ProcIndices.push_back(0);
1113 // If we had an old class, copy it's InstRWs to this new class.
1114 if (OldSCIdx) {
1115 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel");
1116 for (Record *OldRWDef : SchedClasses[OldSCIdx].InstRWs) {
1117 if (OldRWDef->getValueAsDef("SchedModel") == RWModelDef) {
1118 assert(!InstDefs.empty()); // Checked at function start.
1119 PrintError(
1120 InstRWDef->getLoc(),
1121 "Overlapping InstRW definition for \"" +
1122 InstDefs.front()->getName() + "\" also matches previous \"" +
1123 OldRWDef->getValue("Instrs")->getValue()->getAsString() +
1124 "\".");
1125 PrintFatalNote(OldRWDef->getLoc(), "Previous match was here.");
1126 }
1127 assert(OldRWDef != InstRWDef &&
1128 "SchedClass has duplicate InstRW def");
1129 SC.InstRWs.push_back(OldRWDef);
1130 }
1131 }
1132 // Map each Instr to this new class.
1133 for (Record *InstDef : InstDefs)
1134 InstrClassMap[InstDef] = SCIdx;
1135 SC.InstRWs.push_back(InstRWDef);
1136 }
1137 }
1138
1139 // True if collectProcItins found anything.
hasItineraries() const1140 bool CodeGenSchedModels::hasItineraries() const {
1141 for (const CodeGenProcModel &PM : make_range(procModelBegin(),procModelEnd()))
1142 if (PM.hasItineraries())
1143 return true;
1144 return false;
1145 }
1146
1147 // Gather the processor itineraries.
collectProcItins()1148 void CodeGenSchedModels::collectProcItins() {
1149 LLVM_DEBUG(dbgs() << "\n+++ PROBLEM ITINERARIES (collectProcItins) +++\n");
1150 for (CodeGenProcModel &ProcModel : ProcModels) {
1151 if (!ProcModel.hasItineraries())
1152 continue;
1153
1154 RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID");
1155 assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect");
1156
1157 // Populate ItinDefList with Itinerary records.
1158 ProcModel.ItinDefList.resize(NumInstrSchedClasses);
1159
1160 // Insert each itinerary data record in the correct position within
1161 // the processor model's ItinDefList.
1162 for (Record *ItinData : ItinRecords) {
1163 const Record *ItinDef = ItinData->getValueAsDef("TheClass");
1164 bool FoundClass = false;
1165
1166 for (const CodeGenSchedClass &SC :
1167 make_range(schedClassBegin(), schedClassEnd())) {
1168 // Multiple SchedClasses may share an itinerary. Update all of them.
1169 if (SC.ItinClassDef == ItinDef) {
1170 ProcModel.ItinDefList[SC.Index] = ItinData;
1171 FoundClass = true;
1172 }
1173 }
1174 if (!FoundClass) {
1175 LLVM_DEBUG(dbgs() << ProcModel.ItinsDef->getName()
1176 << " missing class for itinerary "
1177 << ItinDef->getName() << '\n');
1178 }
1179 }
1180 // Check for missing itinerary entries.
1181 assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec");
1182 LLVM_DEBUG(
1183 for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) {
1184 if (!ProcModel.ItinDefList[i])
1185 dbgs() << ProcModel.ItinsDef->getName()
1186 << " missing itinerary for class " << SchedClasses[i].Name
1187 << '\n';
1188 });
1189 }
1190 }
1191
1192 // Gather the read/write types for each itinerary class.
collectProcItinRW()1193 void CodeGenSchedModels::collectProcItinRW() {
1194 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
1195 llvm::sort(ItinRWDefs, LessRecord());
1196 for (Record *RWDef : ItinRWDefs) {
1197 if (!RWDef->getValueInit("SchedModel")->isComplete())
1198 PrintFatalError(RWDef->getLoc(), "SchedModel is undefined");
1199 Record *ModelDef = RWDef->getValueAsDef("SchedModel");
1200 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
1201 if (I == ProcModelMap.end()) {
1202 PrintFatalError(RWDef->getLoc(), "Undefined SchedMachineModel "
1203 + ModelDef->getName());
1204 }
1205 ProcModels[I->second].ItinRWDefs.push_back(RWDef);
1206 }
1207 }
1208
1209 // Gather the unsupported features for processor models.
collectProcUnsupportedFeatures()1210 void CodeGenSchedModels::collectProcUnsupportedFeatures() {
1211 for (CodeGenProcModel &ProcModel : ProcModels) {
1212 for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) {
1213 ProcModel.UnsupportedFeaturesDefs.push_back(Pred);
1214 }
1215 }
1216 }
1217
1218 /// Infer new classes from existing classes. In the process, this may create new
1219 /// SchedWrites from sequences of existing SchedWrites.
inferSchedClasses()1220 void CodeGenSchedModels::inferSchedClasses() {
1221 LLVM_DEBUG(
1222 dbgs() << "\n+++ INFERRING SCHED CLASSES (inferSchedClasses) +++\n");
1223 LLVM_DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n");
1224
1225 // Visit all existing classes and newly created classes.
1226 for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) {
1227 assert(SchedClasses[Idx].Index == Idx && "bad SCIdx");
1228
1229 if (SchedClasses[Idx].ItinClassDef)
1230 inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx);
1231 if (!SchedClasses[Idx].InstRWs.empty())
1232 inferFromInstRWs(Idx);
1233 if (!SchedClasses[Idx].Writes.empty()) {
1234 inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads,
1235 Idx, SchedClasses[Idx].ProcIndices);
1236 }
1237 assert(SchedClasses.size() < (NumInstrSchedClasses*6) &&
1238 "too many SchedVariants");
1239 }
1240 }
1241
1242 /// Infer classes from per-processor itinerary resources.
inferFromItinClass(Record * ItinClassDef,unsigned FromClassIdx)1243 void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef,
1244 unsigned FromClassIdx) {
1245 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
1246 const CodeGenProcModel &PM = ProcModels[PIdx];
1247 // For all ItinRW entries.
1248 bool HasMatch = false;
1249 for (const Record *Rec : PM.ItinRWDefs) {
1250 RecVec Matched = Rec->getValueAsListOfDefs("MatchedItinClasses");
1251 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
1252 continue;
1253 if (HasMatch)
1254 PrintFatalError(Rec->getLoc(), "Duplicate itinerary class "
1255 + ItinClassDef->getName()
1256 + " in ItinResources for " + PM.ModelName);
1257 HasMatch = true;
1258 IdxVec Writes, Reads;
1259 findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
1260 inferFromRW(Writes, Reads, FromClassIdx, PIdx);
1261 }
1262 }
1263 }
1264
1265 /// Infer classes from per-processor InstReadWrite definitions.
inferFromInstRWs(unsigned SCIdx)1266 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) {
1267 for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) {
1268 assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!");
1269 Record *Rec = SchedClasses[SCIdx].InstRWs[I];
1270 const RecVec *InstDefs = Sets.expand(Rec);
1271 RecIter II = InstDefs->begin(), IE = InstDefs->end();
1272 for (; II != IE; ++II) {
1273 if (InstrClassMap[*II] == SCIdx)
1274 break;
1275 }
1276 // If this class no longer has any instructions mapped to it, it has become
1277 // irrelevant.
1278 if (II == IE)
1279 continue;
1280 IdxVec Writes, Reads;
1281 findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
1282 unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index;
1283 inferFromRW(Writes, Reads, SCIdx, PIdx); // May mutate SchedClasses.
1284 SchedClasses[SCIdx].InstRWProcIndices.insert(PIdx);
1285 }
1286 }
1287
1288 namespace {
1289
1290 // Helper for substituteVariantOperand.
1291 struct TransVariant {
1292 Record *VarOrSeqDef; // Variant or sequence.
1293 unsigned RWIdx; // Index of this variant or sequence's matched type.
1294 unsigned ProcIdx; // Processor model index or zero for any.
1295 unsigned TransVecIdx; // Index into PredTransitions::TransVec.
1296
TransVariant__anon2dd1d4cd0a11::TransVariant1297 TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti):
1298 VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {}
1299 };
1300
1301 // Associate a predicate with the SchedReadWrite that it guards.
1302 // RWIdx is the index of the read/write variant.
1303 struct PredCheck {
1304 bool IsRead;
1305 unsigned RWIdx;
1306 Record *Predicate;
1307
PredCheck__anon2dd1d4cd0a11::PredCheck1308 PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {}
1309 };
1310
1311 // A Predicate transition is a list of RW sequences guarded by a PredTerm.
1312 struct PredTransition {
1313 // A predicate term is a conjunction of PredChecks.
1314 SmallVector<PredCheck, 4> PredTerm;
1315 SmallVector<SmallVector<unsigned,4>, 16> WriteSequences;
1316 SmallVector<SmallVector<unsigned,4>, 16> ReadSequences;
1317 unsigned ProcIndex = 0;
1318
1319 PredTransition() = default;
PredTransition__anon2dd1d4cd0a11::PredTransition1320 PredTransition(ArrayRef<PredCheck> PT, unsigned ProcId) {
1321 PredTerm.assign(PT.begin(), PT.end());
1322 ProcIndex = ProcId;
1323 }
1324 };
1325
1326 // Encapsulate a set of partially constructed transitions.
1327 // The results are built by repeated calls to substituteVariants.
1328 class PredTransitions {
1329 CodeGenSchedModels &SchedModels;
1330
1331 public:
1332 std::vector<PredTransition> TransVec;
1333
PredTransitions(CodeGenSchedModels & sm)1334 PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {}
1335
1336 bool substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq,
1337 bool IsRead, unsigned StartIdx);
1338
1339 bool substituteVariants(const PredTransition &Trans);
1340
1341 #ifndef NDEBUG
1342 void dump() const;
1343 #endif
1344
1345 private:
1346 bool mutuallyExclusive(Record *PredDef, ArrayRef<Record *> Preds,
1347 ArrayRef<PredCheck> Term);
1348 void getIntersectingVariants(
1349 const CodeGenSchedRW &SchedRW, unsigned TransIdx,
1350 std::vector<TransVariant> &IntersectingVariants);
1351 void pushVariant(const TransVariant &VInfo, bool IsRead);
1352 };
1353
1354 } // end anonymous namespace
1355
1356 // Return true if this predicate is mutually exclusive with a PredTerm. This
1357 // degenerates into checking if the predicate is mutually exclusive with any
1358 // predicate in the Term's conjunction.
1359 //
1360 // All predicates associated with a given SchedRW are considered mutually
1361 // exclusive. This should work even if the conditions expressed by the
1362 // predicates are not exclusive because the predicates for a given SchedWrite
1363 // are always checked in the order they are defined in the .td file. Later
1364 // conditions implicitly negate any prior condition.
mutuallyExclusive(Record * PredDef,ArrayRef<Record * > Preds,ArrayRef<PredCheck> Term)1365 bool PredTransitions::mutuallyExclusive(Record *PredDef,
1366 ArrayRef<Record *> Preds,
1367 ArrayRef<PredCheck> Term) {
1368 for (const PredCheck &PC: Term) {
1369 if (PC.Predicate == PredDef)
1370 return false;
1371
1372 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(PC.RWIdx, PC.IsRead);
1373 assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant");
1374 RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants");
1375 if (any_of(Variants, [PredDef](const Record *R) {
1376 return R->getValueAsDef("Predicate") == PredDef;
1377 })) {
1378 // To check if PredDef is mutually exclusive with PC we also need to
1379 // check that PC.Predicate is exclusive with all predicates from variant
1380 // we're expanding. Consider following RW sequence with two variants
1381 // (1 & 2), where A, B and C are predicates from corresponding SchedVars:
1382 //
1383 // 1:A/B - 2:C/B
1384 //
1385 // Here C is not mutually exclusive with variant (1), because A doesn't
1386 // exist in variant (2). This means we have possible transitions from A
1387 // to C and from A to B, and fully expanded sequence would look like:
1388 //
1389 // if (A & C) return ...;
1390 // if (A & B) return ...;
1391 // if (B) return ...;
1392 //
1393 // Now let's consider another sequence:
1394 //
1395 // 1:A/B - 2:A/B
1396 //
1397 // Here A in variant (2) is mutually exclusive with variant (1), because
1398 // A also exists in (2). This means A->B transition is impossible and
1399 // expanded sequence would look like:
1400 //
1401 // if (A) return ...;
1402 // if (B) return ...;
1403 if (!count(Preds, PC.Predicate))
1404 continue;
1405 return true;
1406 }
1407 }
1408 return false;
1409 }
1410
getAllPredicates(ArrayRef<TransVariant> Variants,unsigned ProcId)1411 static std::vector<Record *> getAllPredicates(ArrayRef<TransVariant> Variants,
1412 unsigned ProcId) {
1413 std::vector<Record *> Preds;
1414 for (auto &Variant : Variants) {
1415 if (!Variant.VarOrSeqDef->isSubClassOf("SchedVar"))
1416 continue;
1417 Preds.push_back(Variant.VarOrSeqDef->getValueAsDef("Predicate"));
1418 }
1419 return Preds;
1420 }
1421
1422 // Populate IntersectingVariants with any variants or aliased sequences of the
1423 // given SchedRW whose processor indices and predicates are not mutually
1424 // exclusive with the given transition.
getIntersectingVariants(const CodeGenSchedRW & SchedRW,unsigned TransIdx,std::vector<TransVariant> & IntersectingVariants)1425 void PredTransitions::getIntersectingVariants(
1426 const CodeGenSchedRW &SchedRW, unsigned TransIdx,
1427 std::vector<TransVariant> &IntersectingVariants) {
1428
1429 bool GenericRW = false;
1430
1431 std::vector<TransVariant> Variants;
1432 if (SchedRW.HasVariants) {
1433 unsigned VarProcIdx = 0;
1434 if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) {
1435 Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel");
1436 VarProcIdx = SchedModels.getProcModel(ModelDef).Index;
1437 }
1438 if (VarProcIdx == 0 || VarProcIdx == TransVec[TransIdx].ProcIndex) {
1439 // Push each variant. Assign TransVecIdx later.
1440 const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants");
1441 for (Record *VarDef : VarDefs)
1442 Variants.emplace_back(VarDef, SchedRW.Index, VarProcIdx, 0);
1443 if (VarProcIdx == 0)
1444 GenericRW = true;
1445 }
1446 }
1447 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
1448 AI != AE; ++AI) {
1449 // If either the SchedAlias itself or the SchedReadWrite that it aliases
1450 // to is defined within a processor model, constrain all variants to
1451 // that processor.
1452 unsigned AliasProcIdx = 0;
1453 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
1454 Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
1455 AliasProcIdx = SchedModels.getProcModel(ModelDef).Index;
1456 }
1457 if (AliasProcIdx && AliasProcIdx != TransVec[TransIdx].ProcIndex)
1458 continue;
1459 if (!Variants.empty()) {
1460 const CodeGenProcModel &PM =
1461 *(SchedModels.procModelBegin() + AliasProcIdx);
1462 PrintFatalError((*AI)->getLoc(),
1463 "Multiple variants defined for processor " +
1464 PM.ModelName +
1465 " Ensure only one SchedAlias exists per RW.");
1466 }
1467
1468 const CodeGenSchedRW &AliasRW =
1469 SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW"));
1470
1471 if (AliasRW.HasVariants) {
1472 const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants");
1473 for (Record *VD : VarDefs)
1474 Variants.emplace_back(VD, AliasRW.Index, AliasProcIdx, 0);
1475 }
1476 if (AliasRW.IsSequence)
1477 Variants.emplace_back(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0);
1478 if (AliasProcIdx == 0)
1479 GenericRW = true;
1480 }
1481 std::vector<Record *> AllPreds =
1482 getAllPredicates(Variants, TransVec[TransIdx].ProcIndex);
1483 for (TransVariant &Variant : Variants) {
1484 // Don't expand variants if the processor models don't intersect.
1485 // A zero processor index means any processor.
1486 if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) {
1487 Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate");
1488 if (mutuallyExclusive(PredDef, AllPreds, TransVec[TransIdx].PredTerm))
1489 continue;
1490 }
1491
1492 if (IntersectingVariants.empty()) {
1493 // The first variant builds on the existing transition.
1494 Variant.TransVecIdx = TransIdx;
1495 IntersectingVariants.push_back(Variant);
1496 }
1497 else {
1498 // Push another copy of the current transition for more variants.
1499 Variant.TransVecIdx = TransVec.size();
1500 IntersectingVariants.push_back(Variant);
1501 TransVec.push_back(TransVec[TransIdx]);
1502 }
1503 }
1504 if (GenericRW && IntersectingVariants.empty()) {
1505 PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has "
1506 "a matching predicate on any processor");
1507 }
1508 }
1509
1510 // Push the Reads/Writes selected by this variant onto the PredTransition
1511 // specified by VInfo.
1512 void PredTransitions::
pushVariant(const TransVariant & VInfo,bool IsRead)1513 pushVariant(const TransVariant &VInfo, bool IsRead) {
1514 PredTransition &Trans = TransVec[VInfo.TransVecIdx];
1515
1516 // If this operand transition is reached through a processor-specific alias,
1517 // then the whole transition is specific to this processor.
1518 IdxVec SelectedRWs;
1519 if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) {
1520 Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate");
1521 Trans.PredTerm.emplace_back(IsRead, VInfo.RWIdx,PredDef);
1522 RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected");
1523 SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead);
1524 }
1525 else {
1526 assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") &&
1527 "variant must be a SchedVariant or aliased WriteSequence");
1528 SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead));
1529 }
1530
1531 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead);
1532
1533 SmallVectorImpl<SmallVector<unsigned,4>> &RWSequences = IsRead
1534 ? Trans.ReadSequences : Trans.WriteSequences;
1535 if (SchedRW.IsVariadic) {
1536 unsigned OperIdx = RWSequences.size()-1;
1537 // Make N-1 copies of this transition's last sequence.
1538 RWSequences.reserve(RWSequences.size() + SelectedRWs.size() - 1);
1539 RWSequences.insert(RWSequences.end(), SelectedRWs.size() - 1,
1540 RWSequences[OperIdx]);
1541 // Push each of the N elements of the SelectedRWs onto a copy of the last
1542 // sequence (split the current operand into N operands).
1543 // Note that write sequences should be expanded within this loop--the entire
1544 // sequence belongs to a single operand.
1545 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1546 RWI != RWE; ++RWI, ++OperIdx) {
1547 IdxVec ExpandedRWs;
1548 if (IsRead)
1549 ExpandedRWs.push_back(*RWI);
1550 else
1551 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1552 RWSequences[OperIdx].insert(RWSequences[OperIdx].end(),
1553 ExpandedRWs.begin(), ExpandedRWs.end());
1554 }
1555 assert(OperIdx == RWSequences.size() && "missed a sequence");
1556 }
1557 else {
1558 // Push this transition's expanded sequence onto this transition's last
1559 // sequence (add to the current operand's sequence).
1560 SmallVectorImpl<unsigned> &Seq = RWSequences.back();
1561 IdxVec ExpandedRWs;
1562 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
1563 RWI != RWE; ++RWI) {
1564 if (IsRead)
1565 ExpandedRWs.push_back(*RWI);
1566 else
1567 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
1568 }
1569 Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end());
1570 }
1571 }
1572
1573 // RWSeq is a sequence of all Reads or all Writes for the next read or write
1574 // operand. StartIdx is an index into TransVec where partial results
1575 // starts. RWSeq must be applied to all transitions between StartIdx and the end
1576 // of TransVec.
substituteVariantOperand(const SmallVectorImpl<unsigned> & RWSeq,bool IsRead,unsigned StartIdx)1577 bool PredTransitions::substituteVariantOperand(
1578 const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) {
1579 bool Subst = false;
1580 // Visit each original RW within the current sequence.
1581 for (SmallVectorImpl<unsigned>::const_iterator
1582 RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) {
1583 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead);
1584 // Push this RW on all partial PredTransitions or distribute variants.
1585 // New PredTransitions may be pushed within this loop which should not be
1586 // revisited (TransEnd must be loop invariant).
1587 for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size();
1588 TransIdx != TransEnd; ++TransIdx) {
1589 // Distribute this partial PredTransition across intersecting variants.
1590 // This will push a copies of TransVec[TransIdx] on the back of TransVec.
1591 std::vector<TransVariant> IntersectingVariants;
1592 getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants);
1593 // Now expand each variant on top of its copy of the transition.
1594 for (const TransVariant &IV : IntersectingVariants)
1595 pushVariant(IV, IsRead);
1596 if (IntersectingVariants.empty()) {
1597 if (IsRead)
1598 TransVec[TransIdx].ReadSequences.back().push_back(*RWI);
1599 else
1600 TransVec[TransIdx].WriteSequences.back().push_back(*RWI);
1601 continue;
1602 } else {
1603 Subst = true;
1604 }
1605 }
1606 }
1607 return Subst;
1608 }
1609
1610 // For each variant of a Read/Write in Trans, substitute the sequence of
1611 // Read/Writes guarded by the variant. This is exponential in the number of
1612 // variant Read/Writes, but in practice detection of mutually exclusive
1613 // predicates should result in linear growth in the total number variants.
1614 //
1615 // This is one step in a breadth-first search of nested variants.
substituteVariants(const PredTransition & Trans)1616 bool PredTransitions::substituteVariants(const PredTransition &Trans) {
1617 // Build up a set of partial results starting at the back of
1618 // PredTransitions. Remember the first new transition.
1619 unsigned StartIdx = TransVec.size();
1620 bool Subst = false;
1621 assert(Trans.ProcIndex != 0);
1622 TransVec.emplace_back(Trans.PredTerm, Trans.ProcIndex);
1623
1624 // Visit each original write sequence.
1625 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1626 WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end();
1627 WSI != WSE; ++WSI) {
1628 // Push a new (empty) write sequence onto all partial Transitions.
1629 for (std::vector<PredTransition>::iterator I =
1630 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1631 I->WriteSequences.emplace_back();
1632 }
1633 Subst |= substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx);
1634 }
1635 // Visit each original read sequence.
1636 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
1637 RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end();
1638 RSI != RSE; ++RSI) {
1639 // Push a new (empty) read sequence onto all partial Transitions.
1640 for (std::vector<PredTransition>::iterator I =
1641 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
1642 I->ReadSequences.emplace_back();
1643 }
1644 Subst |= substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx);
1645 }
1646 return Subst;
1647 }
1648
addSequences(CodeGenSchedModels & SchedModels,const SmallVectorImpl<SmallVector<unsigned,4>> & Seqs,IdxVec & Result,bool IsRead)1649 static void addSequences(CodeGenSchedModels &SchedModels,
1650 const SmallVectorImpl<SmallVector<unsigned, 4>> &Seqs,
1651 IdxVec &Result, bool IsRead) {
1652 for (const auto &S : Seqs)
1653 if (!S.empty())
1654 Result.push_back(SchedModels.findOrInsertRW(S, IsRead));
1655 }
1656
1657 #ifndef NDEBUG
dumpRecVec(const RecVec & RV)1658 static void dumpRecVec(const RecVec &RV) {
1659 for (const Record *R : RV)
1660 dbgs() << R->getName() << ", ";
1661 }
1662 #endif
1663
dumpTransition(const CodeGenSchedModels & SchedModels,const CodeGenSchedClass & FromSC,const CodeGenSchedTransition & SCTrans,const RecVec & Preds)1664 static void dumpTransition(const CodeGenSchedModels &SchedModels,
1665 const CodeGenSchedClass &FromSC,
1666 const CodeGenSchedTransition &SCTrans,
1667 const RecVec &Preds) {
1668 LLVM_DEBUG(dbgs() << "Adding transition from " << FromSC.Name << "("
1669 << FromSC.Index << ") to "
1670 << SchedModels.getSchedClass(SCTrans.ToClassIdx).Name << "("
1671 << SCTrans.ToClassIdx << ") on pred term: (";
1672 dumpRecVec(Preds);
1673 dbgs() << ") on processor (" << SCTrans.ProcIndex << ")\n");
1674 }
1675 // Create a new SchedClass for each variant found by inferFromRW. Pass
inferFromTransitions(ArrayRef<PredTransition> LastTransitions,unsigned FromClassIdx,CodeGenSchedModels & SchedModels)1676 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions,
1677 unsigned FromClassIdx,
1678 CodeGenSchedModels &SchedModels) {
1679 // For each PredTransition, create a new CodeGenSchedTransition, which usually
1680 // requires creating a new SchedClass.
1681 for (ArrayRef<PredTransition>::iterator
1682 I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) {
1683 // Variant expansion (substituteVariants) may create unconditional
1684 // transitions. We don't need to build sched classes for them.
1685 if (I->PredTerm.empty())
1686 continue;
1687 IdxVec OperWritesVariant, OperReadsVariant;
1688 addSequences(SchedModels, I->WriteSequences, OperWritesVariant, false);
1689 addSequences(SchedModels, I->ReadSequences, OperReadsVariant, true);
1690 CodeGenSchedTransition SCTrans;
1691
1692 // Transition should not contain processor indices already assigned to
1693 // InstRWs in this scheduling class.
1694 const CodeGenSchedClass &FromSC = SchedModels.getSchedClass(FromClassIdx);
1695 if (FromSC.InstRWProcIndices.count(I->ProcIndex))
1696 continue;
1697 SCTrans.ProcIndex = I->ProcIndex;
1698 SCTrans.ToClassIdx =
1699 SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant,
1700 OperReadsVariant, I->ProcIndex);
1701
1702 // The final PredTerm is unique set of predicates guarding the transition.
1703 RecVec Preds;
1704 transform(I->PredTerm, std::back_inserter(Preds),
1705 [](const PredCheck &P) {
1706 return P.Predicate;
1707 });
1708 Preds.erase(std::unique(Preds.begin(), Preds.end()), Preds.end());
1709 dumpTransition(SchedModels, FromSC, SCTrans, Preds);
1710 SCTrans.PredTerm = std::move(Preds);
1711 SchedModels.getSchedClass(FromClassIdx)
1712 .Transitions.push_back(std::move(SCTrans));
1713 }
1714 }
1715
getAllProcIndices() const1716 std::vector<unsigned> CodeGenSchedModels::getAllProcIndices() const {
1717 std::vector<unsigned> ProcIdVec;
1718 for (const auto &PM : ProcModelMap)
1719 if (PM.second != 0)
1720 ProcIdVec.push_back(PM.second);
1721 return ProcIdVec;
1722 }
1723
1724 static std::vector<PredTransition>
makePerProcessorTransitions(const PredTransition & Trans,ArrayRef<unsigned> ProcIndices)1725 makePerProcessorTransitions(const PredTransition &Trans,
1726 ArrayRef<unsigned> ProcIndices) {
1727 std::vector<PredTransition> PerCpuTransVec;
1728 for (unsigned ProcId : ProcIndices) {
1729 assert(ProcId != 0);
1730 PerCpuTransVec.push_back(Trans);
1731 PerCpuTransVec.back().ProcIndex = ProcId;
1732 }
1733 return PerCpuTransVec;
1734 }
1735
1736 // Create new SchedClasses for the given ReadWrite list. If any of the
1737 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant
1738 // of the ReadWrite list, following Aliases if necessary.
inferFromRW(ArrayRef<unsigned> OperWrites,ArrayRef<unsigned> OperReads,unsigned FromClassIdx,ArrayRef<unsigned> ProcIndices)1739 void CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites,
1740 ArrayRef<unsigned> OperReads,
1741 unsigned FromClassIdx,
1742 ArrayRef<unsigned> ProcIndices) {
1743 LLVM_DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices);
1744 dbgs() << ") ");
1745 // Create a seed transition with an empty PredTerm and the expanded sequences
1746 // of SchedWrites for the current SchedClass.
1747 std::vector<PredTransition> LastTransitions;
1748 LastTransitions.emplace_back();
1749
1750 for (unsigned WriteIdx : OperWrites) {
1751 IdxVec WriteSeq;
1752 expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false);
1753 LastTransitions[0].WriteSequences.emplace_back();
1754 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences.back();
1755 Seq.append(WriteSeq.begin(), WriteSeq.end());
1756 LLVM_DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1757 }
1758 LLVM_DEBUG(dbgs() << " Reads: ");
1759 for (unsigned ReadIdx : OperReads) {
1760 IdxVec ReadSeq;
1761 expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true);
1762 LastTransitions[0].ReadSequences.emplace_back();
1763 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences.back();
1764 Seq.append(ReadSeq.begin(), ReadSeq.end());
1765 LLVM_DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
1766 }
1767 LLVM_DEBUG(dbgs() << '\n');
1768
1769 LastTransitions = makePerProcessorTransitions(
1770 LastTransitions[0], llvm::count(ProcIndices, 0)
1771 ? ArrayRef<unsigned>(getAllProcIndices())
1772 : ProcIndices);
1773 // Collect all PredTransitions for individual operands.
1774 // Iterate until no variant writes remain.
1775 bool SubstitutedAny;
1776 do {
1777 SubstitutedAny = false;
1778 PredTransitions Transitions(*this);
1779 for (const PredTransition &Trans : LastTransitions)
1780 SubstitutedAny |= Transitions.substituteVariants(Trans);
1781 LLVM_DEBUG(Transitions.dump());
1782 LastTransitions.swap(Transitions.TransVec);
1783 } while (SubstitutedAny);
1784
1785 // WARNING: We are about to mutate the SchedClasses vector. Do not refer to
1786 // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions.
1787 inferFromTransitions(LastTransitions, FromClassIdx, *this);
1788 }
1789
1790 // Check if any processor resource group contains all resource records in
1791 // SubUnits.
hasSuperGroup(RecVec & SubUnits,CodeGenProcModel & PM)1792 bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) {
1793 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
1794 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
1795 continue;
1796 RecVec SuperUnits =
1797 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
1798 RecIter RI = SubUnits.begin(), RE = SubUnits.end();
1799 for ( ; RI != RE; ++RI) {
1800 if (!is_contained(SuperUnits, *RI)) {
1801 break;
1802 }
1803 }
1804 if (RI == RE)
1805 return true;
1806 }
1807 return false;
1808 }
1809
1810 // Verify that overlapping groups have a common supergroup.
verifyProcResourceGroups(CodeGenProcModel & PM)1811 void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) {
1812 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
1813 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
1814 continue;
1815 RecVec CheckUnits =
1816 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
1817 for (unsigned j = i+1; j < e; ++j) {
1818 if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup"))
1819 continue;
1820 RecVec OtherUnits =
1821 PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources");
1822 if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(),
1823 OtherUnits.begin(), OtherUnits.end())
1824 != CheckUnits.end()) {
1825 // CheckUnits and OtherUnits overlap
1826 OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(),
1827 CheckUnits.end());
1828 if (!hasSuperGroup(OtherUnits, PM)) {
1829 PrintFatalError((PM.ProcResourceDefs[i])->getLoc(),
1830 "proc resource group overlaps with "
1831 + PM.ProcResourceDefs[j]->getName()
1832 + " but no supergroup contains both.");
1833 }
1834 }
1835 }
1836 }
1837 }
1838
1839 // Collect all the RegisterFile definitions available in this target.
collectRegisterFiles()1840 void CodeGenSchedModels::collectRegisterFiles() {
1841 RecVec RegisterFileDefs = Records.getAllDerivedDefinitions("RegisterFile");
1842
1843 // RegisterFiles is the vector of CodeGenRegisterFile.
1844 for (Record *RF : RegisterFileDefs) {
1845 // For each register file definition, construct a CodeGenRegisterFile object
1846 // and add it to the appropriate scheduling model.
1847 CodeGenProcModel &PM = getProcModel(RF->getValueAsDef("SchedModel"));
1848 PM.RegisterFiles.emplace_back(CodeGenRegisterFile(RF->getName(),RF));
1849 CodeGenRegisterFile &CGRF = PM.RegisterFiles.back();
1850 CGRF.MaxMovesEliminatedPerCycle =
1851 RF->getValueAsInt("MaxMovesEliminatedPerCycle");
1852 CGRF.AllowZeroMoveEliminationOnly =
1853 RF->getValueAsBit("AllowZeroMoveEliminationOnly");
1854
1855 // Now set the number of physical registers as well as the cost of registers
1856 // in each register class.
1857 CGRF.NumPhysRegs = RF->getValueAsInt("NumPhysRegs");
1858 if (!CGRF.NumPhysRegs) {
1859 PrintFatalError(RF->getLoc(),
1860 "Invalid RegisterFile with zero physical registers");
1861 }
1862
1863 RecVec RegisterClasses = RF->getValueAsListOfDefs("RegClasses");
1864 std::vector<int64_t> RegisterCosts = RF->getValueAsListOfInts("RegCosts");
1865 ListInit *MoveElimInfo = RF->getValueAsListInit("AllowMoveElimination");
1866 for (unsigned I = 0, E = RegisterClasses.size(); I < E; ++I) {
1867 int Cost = RegisterCosts.size() > I ? RegisterCosts[I] : 1;
1868
1869 bool AllowMoveElim = false;
1870 if (MoveElimInfo->size() > I) {
1871 BitInit *Val = cast<BitInit>(MoveElimInfo->getElement(I));
1872 AllowMoveElim = Val->getValue();
1873 }
1874
1875 CGRF.Costs.emplace_back(RegisterClasses[I], Cost, AllowMoveElim);
1876 }
1877 }
1878 }
1879
1880 // Collect and sort WriteRes, ReadAdvance, and ProcResources.
collectProcResources()1881 void CodeGenSchedModels::collectProcResources() {
1882 ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits");
1883 ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
1884
1885 // Add any subtarget-specific SchedReadWrites that are directly associated
1886 // with processor resources. Refer to the parent SchedClass's ProcIndices to
1887 // determine which processors they apply to.
1888 for (const CodeGenSchedClass &SC :
1889 make_range(schedClassBegin(), schedClassEnd())) {
1890 if (SC.ItinClassDef) {
1891 collectItinProcResources(SC.ItinClassDef);
1892 continue;
1893 }
1894
1895 // This class may have a default ReadWrite list which can be overriden by
1896 // InstRW definitions.
1897 for (Record *RW : SC.InstRWs) {
1898 Record *RWModelDef = RW->getValueAsDef("SchedModel");
1899 unsigned PIdx = getProcModel(RWModelDef).Index;
1900 IdxVec Writes, Reads;
1901 findRWs(RW->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
1902 collectRWResources(Writes, Reads, PIdx);
1903 }
1904
1905 collectRWResources(SC.Writes, SC.Reads, SC.ProcIndices);
1906 }
1907 // Add resources separately defined by each subtarget.
1908 RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes");
1909 for (Record *WR : WRDefs) {
1910 Record *ModelDef = WR->getValueAsDef("SchedModel");
1911 addWriteRes(WR, getProcModel(ModelDef).Index);
1912 }
1913 RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes");
1914 for (Record *SWR : SWRDefs) {
1915 Record *ModelDef = SWR->getValueAsDef("SchedModel");
1916 addWriteRes(SWR, getProcModel(ModelDef).Index);
1917 }
1918 RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance");
1919 for (Record *RA : RADefs) {
1920 Record *ModelDef = RA->getValueAsDef("SchedModel");
1921 addReadAdvance(RA, getProcModel(ModelDef).Index);
1922 }
1923 RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance");
1924 for (Record *SRA : SRADefs) {
1925 if (SRA->getValueInit("SchedModel")->isComplete()) {
1926 Record *ModelDef = SRA->getValueAsDef("SchedModel");
1927 addReadAdvance(SRA, getProcModel(ModelDef).Index);
1928 }
1929 }
1930 // Add ProcResGroups that are defined within this processor model, which may
1931 // not be directly referenced but may directly specify a buffer size.
1932 RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
1933 for (Record *PRG : ProcResGroups) {
1934 if (!PRG->getValueInit("SchedModel")->isComplete())
1935 continue;
1936 CodeGenProcModel &PM = getProcModel(PRG->getValueAsDef("SchedModel"));
1937 if (!is_contained(PM.ProcResourceDefs, PRG))
1938 PM.ProcResourceDefs.push_back(PRG);
1939 }
1940 // Add ProcResourceUnits unconditionally.
1941 for (Record *PRU : Records.getAllDerivedDefinitions("ProcResourceUnits")) {
1942 if (!PRU->getValueInit("SchedModel")->isComplete())
1943 continue;
1944 CodeGenProcModel &PM = getProcModel(PRU->getValueAsDef("SchedModel"));
1945 if (!is_contained(PM.ProcResourceDefs, PRU))
1946 PM.ProcResourceDefs.push_back(PRU);
1947 }
1948 // Finalize each ProcModel by sorting the record arrays.
1949 for (CodeGenProcModel &PM : ProcModels) {
1950 llvm::sort(PM.WriteResDefs, LessRecord());
1951 llvm::sort(PM.ReadAdvanceDefs, LessRecord());
1952 llvm::sort(PM.ProcResourceDefs, LessRecord());
1953 LLVM_DEBUG(
1954 PM.dump();
1955 dbgs() << "WriteResDefs: "; for (RecIter RI = PM.WriteResDefs.begin(),
1956 RE = PM.WriteResDefs.end();
1957 RI != RE; ++RI) {
1958 if ((*RI)->isSubClassOf("WriteRes"))
1959 dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " ";
1960 else
1961 dbgs() << (*RI)->getName() << " ";
1962 } dbgs() << "\nReadAdvanceDefs: ";
1963 for (RecIter RI = PM.ReadAdvanceDefs.begin(),
1964 RE = PM.ReadAdvanceDefs.end();
1965 RI != RE; ++RI) {
1966 if ((*RI)->isSubClassOf("ReadAdvance"))
1967 dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " ";
1968 else
1969 dbgs() << (*RI)->getName() << " ";
1970 } dbgs()
1971 << "\nProcResourceDefs: ";
1972 for (RecIter RI = PM.ProcResourceDefs.begin(),
1973 RE = PM.ProcResourceDefs.end();
1974 RI != RE; ++RI) { dbgs() << (*RI)->getName() << " "; } dbgs()
1975 << '\n');
1976 verifyProcResourceGroups(PM);
1977 }
1978
1979 ProcResourceDefs.clear();
1980 ProcResGroups.clear();
1981 }
1982
checkCompleteness()1983 void CodeGenSchedModels::checkCompleteness() {
1984 bool Complete = true;
1985 bool HadCompleteModel = false;
1986 for (const CodeGenProcModel &ProcModel : procModels()) {
1987 const bool HasItineraries = ProcModel.hasItineraries();
1988 if (!ProcModel.ModelDef->getValueAsBit("CompleteModel"))
1989 continue;
1990 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
1991 if (Inst->hasNoSchedulingInfo)
1992 continue;
1993 if (ProcModel.isUnsupported(*Inst))
1994 continue;
1995 unsigned SCIdx = getSchedClassIdx(*Inst);
1996 if (!SCIdx) {
1997 if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) {
1998 PrintError(Inst->TheDef->getLoc(),
1999 "No schedule information for instruction '" +
2000 Inst->TheDef->getName() + "' in SchedMachineModel '" +
2001 ProcModel.ModelDef->getName() + "'");
2002 Complete = false;
2003 }
2004 continue;
2005 }
2006
2007 const CodeGenSchedClass &SC = getSchedClass(SCIdx);
2008 if (!SC.Writes.empty())
2009 continue;
2010 if (HasItineraries && SC.ItinClassDef != nullptr &&
2011 SC.ItinClassDef->getName() != "NoItinerary")
2012 continue;
2013
2014 const RecVec &InstRWs = SC.InstRWs;
2015 auto I = find_if(InstRWs, [&ProcModel](const Record *R) {
2016 return R->getValueAsDef("SchedModel") == ProcModel.ModelDef;
2017 });
2018 if (I == InstRWs.end()) {
2019 PrintError(Inst->TheDef->getLoc(), "'" + ProcModel.ModelName +
2020 "' lacks information for '" +
2021 Inst->TheDef->getName() + "'");
2022 Complete = false;
2023 }
2024 }
2025 HadCompleteModel = true;
2026 }
2027 if (!Complete) {
2028 errs() << "\n\nIncomplete schedule models found.\n"
2029 << "- Consider setting 'CompleteModel = 0' while developing new models.\n"
2030 << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n"
2031 << "- Instructions should usually have Sched<[...]> as a superclass, "
2032 "you may temporarily use an empty list.\n"
2033 << "- Instructions related to unsupported features can be excluded with "
2034 "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the "
2035 "processor model.\n\n";
2036 PrintFatalError("Incomplete schedule model");
2037 }
2038 }
2039
2040 // Collect itinerary class resources for each processor.
collectItinProcResources(Record * ItinClassDef)2041 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) {
2042 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
2043 const CodeGenProcModel &PM = ProcModels[PIdx];
2044 // For all ItinRW entries.
2045 bool HasMatch = false;
2046 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
2047 II != IE; ++II) {
2048 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
2049 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
2050 continue;
2051 if (HasMatch)
2052 PrintFatalError((*II)->getLoc(), "Duplicate itinerary class "
2053 + ItinClassDef->getName()
2054 + " in ItinResources for " + PM.ModelName);
2055 HasMatch = true;
2056 IdxVec Writes, Reads;
2057 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
2058 collectRWResources(Writes, Reads, PIdx);
2059 }
2060 }
2061 }
2062
collectRWResources(unsigned RWIdx,bool IsRead,ArrayRef<unsigned> ProcIndices)2063 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead,
2064 ArrayRef<unsigned> ProcIndices) {
2065 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
2066 if (SchedRW.TheDef) {
2067 if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) {
2068 for (unsigned Idx : ProcIndices)
2069 addWriteRes(SchedRW.TheDef, Idx);
2070 }
2071 else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) {
2072 for (unsigned Idx : ProcIndices)
2073 addReadAdvance(SchedRW.TheDef, Idx);
2074 }
2075 }
2076 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
2077 AI != AE; ++AI) {
2078 IdxVec AliasProcIndices;
2079 if ((*AI)->getValueInit("SchedModel")->isComplete()) {
2080 AliasProcIndices.push_back(
2081 getProcModel((*AI)->getValueAsDef("SchedModel")).Index);
2082 }
2083 else
2084 AliasProcIndices = ProcIndices;
2085 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
2086 assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes");
2087
2088 IdxVec ExpandedRWs;
2089 expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead);
2090 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
2091 SI != SE; ++SI) {
2092 collectRWResources(*SI, IsRead, AliasProcIndices);
2093 }
2094 }
2095 }
2096
2097 // Collect resources for a set of read/write types and processor indices.
collectRWResources(ArrayRef<unsigned> Writes,ArrayRef<unsigned> Reads,ArrayRef<unsigned> ProcIndices)2098 void CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes,
2099 ArrayRef<unsigned> Reads,
2100 ArrayRef<unsigned> ProcIndices) {
2101 for (unsigned Idx : Writes)
2102 collectRWResources(Idx, /*IsRead=*/false, ProcIndices);
2103
2104 for (unsigned Idx : Reads)
2105 collectRWResources(Idx, /*IsRead=*/true, ProcIndices);
2106 }
2107
2108 // Find the processor's resource units for this kind of resource.
findProcResUnits(Record * ProcResKind,const CodeGenProcModel & PM,ArrayRef<SMLoc> Loc) const2109 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind,
2110 const CodeGenProcModel &PM,
2111 ArrayRef<SMLoc> Loc) const {
2112 if (ProcResKind->isSubClassOf("ProcResourceUnits"))
2113 return ProcResKind;
2114
2115 Record *ProcUnitDef = nullptr;
2116 assert(!ProcResourceDefs.empty());
2117 assert(!ProcResGroups.empty());
2118
2119 for (Record *ProcResDef : ProcResourceDefs) {
2120 if (ProcResDef->getValueAsDef("Kind") == ProcResKind
2121 && ProcResDef->getValueAsDef("SchedModel") == PM.ModelDef) {
2122 if (ProcUnitDef) {
2123 PrintFatalError(Loc,
2124 "Multiple ProcessorResourceUnits associated with "
2125 + ProcResKind->getName());
2126 }
2127 ProcUnitDef = ProcResDef;
2128 }
2129 }
2130 for (Record *ProcResGroup : ProcResGroups) {
2131 if (ProcResGroup == ProcResKind
2132 && ProcResGroup->getValueAsDef("SchedModel") == PM.ModelDef) {
2133 if (ProcUnitDef) {
2134 PrintFatalError(Loc,
2135 "Multiple ProcessorResourceUnits associated with "
2136 + ProcResKind->getName());
2137 }
2138 ProcUnitDef = ProcResGroup;
2139 }
2140 }
2141 if (!ProcUnitDef) {
2142 PrintFatalError(Loc,
2143 "No ProcessorResources associated with "
2144 + ProcResKind->getName());
2145 }
2146 return ProcUnitDef;
2147 }
2148
2149 // Iteratively add a resource and its super resources.
addProcResource(Record * ProcResKind,CodeGenProcModel & PM,ArrayRef<SMLoc> Loc)2150 void CodeGenSchedModels::addProcResource(Record *ProcResKind,
2151 CodeGenProcModel &PM,
2152 ArrayRef<SMLoc> Loc) {
2153 while (true) {
2154 Record *ProcResUnits = findProcResUnits(ProcResKind, PM, Loc);
2155
2156 // See if this ProcResource is already associated with this processor.
2157 if (is_contained(PM.ProcResourceDefs, ProcResUnits))
2158 return;
2159
2160 PM.ProcResourceDefs.push_back(ProcResUnits);
2161 if (ProcResUnits->isSubClassOf("ProcResGroup"))
2162 return;
2163
2164 if (!ProcResUnits->getValueInit("Super")->isComplete())
2165 return;
2166
2167 ProcResKind = ProcResUnits->getValueAsDef("Super");
2168 }
2169 }
2170
2171 // Add resources for a SchedWrite to this processor if they don't exist.
addWriteRes(Record * ProcWriteResDef,unsigned PIdx)2172 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) {
2173 assert(PIdx && "don't add resources to an invalid Processor model");
2174
2175 RecVec &WRDefs = ProcModels[PIdx].WriteResDefs;
2176 if (is_contained(WRDefs, ProcWriteResDef))
2177 return;
2178 WRDefs.push_back(ProcWriteResDef);
2179
2180 // Visit ProcResourceKinds referenced by the newly discovered WriteRes.
2181 RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources");
2182 for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end();
2183 WritePRI != WritePRE; ++WritePRI) {
2184 addProcResource(*WritePRI, ProcModels[PIdx], ProcWriteResDef->getLoc());
2185 }
2186 }
2187
2188 // Add resources for a ReadAdvance to this processor if they don't exist.
addReadAdvance(Record * ProcReadAdvanceDef,unsigned PIdx)2189 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef,
2190 unsigned PIdx) {
2191 RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs;
2192 if (is_contained(RADefs, ProcReadAdvanceDef))
2193 return;
2194 RADefs.push_back(ProcReadAdvanceDef);
2195 }
2196
getProcResourceIdx(Record * PRDef) const2197 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const {
2198 RecIter PRPos = find(ProcResourceDefs, PRDef);
2199 if (PRPos == ProcResourceDefs.end())
2200 PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in "
2201 "the ProcResources list for " + ModelName);
2202 // Idx=0 is reserved for invalid.
2203 return 1 + (PRPos - ProcResourceDefs.begin());
2204 }
2205
isUnsupported(const CodeGenInstruction & Inst) const2206 bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const {
2207 for (const Record *TheDef : UnsupportedFeaturesDefs) {
2208 for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) {
2209 if (TheDef->getName() == PredDef->getName())
2210 return true;
2211 }
2212 }
2213 return false;
2214 }
2215
2216 #ifndef NDEBUG
dump() const2217 void CodeGenProcModel::dump() const {
2218 dbgs() << Index << ": " << ModelName << " "
2219 << (ModelDef ? ModelDef->getName() : "inferred") << " "
2220 << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
2221 }
2222
dump() const2223 void CodeGenSchedRW::dump() const {
2224 dbgs() << Name << (IsVariadic ? " (V) " : " ");
2225 if (IsSequence) {
2226 dbgs() << "(";
2227 dumpIdxVec(Sequence);
2228 dbgs() << ")";
2229 }
2230 }
2231
dump(const CodeGenSchedModels * SchedModels) const2232 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const {
2233 dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n'
2234 << " Writes: ";
2235 for (unsigned i = 0, N = Writes.size(); i < N; ++i) {
2236 SchedModels->getSchedWrite(Writes[i]).dump();
2237 if (i < N-1) {
2238 dbgs() << '\n';
2239 dbgs().indent(10);
2240 }
2241 }
2242 dbgs() << "\n Reads: ";
2243 for (unsigned i = 0, N = Reads.size(); i < N; ++i) {
2244 SchedModels->getSchedRead(Reads[i]).dump();
2245 if (i < N-1) {
2246 dbgs() << '\n';
2247 dbgs().indent(10);
2248 }
2249 }
2250 dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices);
2251 if (!Transitions.empty()) {
2252 dbgs() << "\n Transitions for Proc ";
2253 for (const CodeGenSchedTransition &Transition : Transitions) {
2254 dbgs() << Transition.ProcIndex << ", ";
2255 }
2256 }
2257 dbgs() << '\n';
2258 }
2259
dump() const2260 void PredTransitions::dump() const {
2261 dbgs() << "Expanded Variants:\n";
2262 for (std::vector<PredTransition>::const_iterator
2263 TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) {
2264 dbgs() << "{";
2265 for (SmallVectorImpl<PredCheck>::const_iterator
2266 PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end();
2267 PCI != PCE; ++PCI) {
2268 if (PCI != TI->PredTerm.begin())
2269 dbgs() << ", ";
2270 dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name
2271 << ":" << PCI->Predicate->getName();
2272 }
2273 dbgs() << "},\n => {";
2274 for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator
2275 WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end();
2276 WSI != WSE; ++WSI) {
2277 dbgs() << "(";
2278 for (SmallVectorImpl<unsigned>::const_iterator
2279 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
2280 if (WI != WSI->begin())
2281 dbgs() << ", ";
2282 dbgs() << SchedModels.getSchedWrite(*WI).Name;
2283 }
2284 dbgs() << "),";
2285 }
2286 dbgs() << "}\n";
2287 }
2288 }
2289 #endif // NDEBUG
2290