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