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