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