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