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