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 Optional<Regex> Regexpr = None; 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.LoadQueue->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 (const CodeGenSchedRW &Read : SchedReads) { 738 Record *ReadDef = Read.TheDef; 739 if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance")) 740 continue; 741 742 RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites"); 743 if (is_contained(ValidWrites, WriteDef)) { 744 return true; 745 } 746 } 747 return false; 748 } 749 750 static void splitSchedReadWrites(const RecVec &RWDefs, 751 RecVec &WriteDefs, RecVec &ReadDefs) { 752 for (Record *RWDef : RWDefs) { 753 if (RWDef->isSubClassOf("SchedWrite")) 754 WriteDefs.push_back(RWDef); 755 else { 756 assert(RWDef->isSubClassOf("SchedRead") && "unknown SchedReadWrite"); 757 ReadDefs.push_back(RWDef); 758 } 759 } 760 } 761 762 // Split the SchedReadWrites defs and call findRWs for each list. 763 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, 764 IdxVec &Writes, IdxVec &Reads) const { 765 RecVec WriteDefs; 766 RecVec ReadDefs; 767 splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs); 768 findRWs(WriteDefs, Writes, false); 769 findRWs(ReadDefs, Reads, true); 770 } 771 772 // Call getSchedRWIdx for all elements in a sequence of SchedRW defs. 773 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs, 774 bool IsRead) const { 775 for (Record *RWDef : RWDefs) { 776 unsigned Idx = getSchedRWIdx(RWDef, IsRead); 777 assert(Idx && "failed to collect SchedReadWrite"); 778 RWs.push_back(Idx); 779 } 780 } 781 782 void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, 783 bool IsRead) const { 784 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 785 if (!SchedRW.IsSequence) { 786 RWSeq.push_back(RWIdx); 787 return; 788 } 789 int Repeat = 790 SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1; 791 for (int i = 0; i < Repeat; ++i) { 792 for (unsigned I : SchedRW.Sequence) { 793 expandRWSequence(I, RWSeq, IsRead); 794 } 795 } 796 } 797 798 // Expand a SchedWrite as a sequence following any aliases that coincide with 799 // the given processor model. 800 void CodeGenSchedModels::expandRWSeqForProc( 801 unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 802 const CodeGenProcModel &ProcModel) const { 803 804 const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead); 805 Record *AliasDef = nullptr; 806 for (const Record *Rec : SchedWrite.Aliases) { 807 const CodeGenSchedRW &AliasRW = getSchedRW(Rec->getValueAsDef("AliasRW")); 808 if (Rec->getValueInit("SchedModel")->isComplete()) { 809 Record *ModelDef = Rec->getValueAsDef("SchedModel"); 810 if (&getProcModel(ModelDef) != &ProcModel) 811 continue; 812 } 813 if (AliasDef) 814 PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases " 815 "defined for processor " + ProcModel.ModelName + 816 " Ensure only one SchedAlias exists per RW."); 817 AliasDef = AliasRW.TheDef; 818 } 819 if (AliasDef) { 820 expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead), 821 RWSeq, IsRead,ProcModel); 822 return; 823 } 824 if (!SchedWrite.IsSequence) { 825 RWSeq.push_back(RWIdx); 826 return; 827 } 828 int Repeat = 829 SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1; 830 for (int I = 0, E = Repeat; I < E; ++I) { 831 for (unsigned Idx : SchedWrite.Sequence) { 832 expandRWSeqForProc(Idx, RWSeq, IsRead, ProcModel); 833 } 834 } 835 } 836 837 // Find the existing SchedWrite that models this sequence of writes. 838 unsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq, 839 bool IsRead) { 840 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 841 842 auto I = find_if(RWVec, [Seq](CodeGenSchedRW &RW) { 843 return makeArrayRef(RW.Sequence) == Seq; 844 }); 845 // Index zero reserved for invalid RW. 846 return I == RWVec.end() ? 0 : std::distance(RWVec.begin(), I); 847 } 848 849 /// Add this ReadWrite if it doesn't already exist. 850 unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq, 851 bool IsRead) { 852 assert(!Seq.empty() && "cannot insert empty sequence"); 853 if (Seq.size() == 1) 854 return Seq.back(); 855 856 unsigned Idx = findRWForSequence(Seq, IsRead); 857 if (Idx) 858 return Idx; 859 860 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 861 unsigned RWIdx = RWVec.size(); 862 CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead)); 863 RWVec.push_back(SchedRW); 864 return RWIdx; 865 } 866 867 /// Visit all the instruction definitions for this target to gather and 868 /// enumerate the itinerary classes. These are the explicitly specified 869 /// SchedClasses. More SchedClasses may be inferred. 870 void CodeGenSchedModels::collectSchedClasses() { 871 872 // NoItinerary is always the first class at Idx=0 873 assert(SchedClasses.empty() && "Expected empty sched class"); 874 SchedClasses.emplace_back(0, "NoInstrModel", 875 Records.getDef("NoItinerary")); 876 SchedClasses.back().ProcIndices.push_back(0); 877 878 // Create a SchedClass for each unique combination of itinerary class and 879 // SchedRW list. 880 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 881 Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary"); 882 IdxVec Writes, Reads; 883 if (!Inst->TheDef->isValueUnset("SchedRW")) 884 findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); 885 886 // ProcIdx == 0 indicates the class applies to all processors. 887 unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, /*ProcIndices*/{0}); 888 InstrClassMap[Inst->TheDef] = SCIdx; 889 } 890 // Create classes for InstRW defs. 891 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 892 llvm::sort(InstRWDefs, LessRecord()); 893 LLVM_DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n"); 894 for (Record *RWDef : InstRWDefs) 895 createInstRWClass(RWDef); 896 897 NumInstrSchedClasses = SchedClasses.size(); 898 899 bool EnableDump = false; 900 LLVM_DEBUG(EnableDump = true); 901 if (!EnableDump) 902 return; 903 904 LLVM_DEBUG( 905 dbgs() 906 << "\n+++ ITINERARIES and/or MACHINE MODELS (collectSchedClasses) +++\n"); 907 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 908 StringRef InstName = Inst->TheDef->getName(); 909 unsigned SCIdx = getSchedClassIdx(*Inst); 910 if (!SCIdx) { 911 LLVM_DEBUG({ 912 if (!Inst->hasNoSchedulingInfo) 913 dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n'; 914 }); 915 continue; 916 } 917 CodeGenSchedClass &SC = getSchedClass(SCIdx); 918 if (SC.ProcIndices[0] != 0) 919 PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class " 920 "must not be subtarget specific."); 921 922 IdxVec ProcIndices; 923 if (SC.ItinClassDef->getName() != "NoItinerary") { 924 ProcIndices.push_back(0); 925 dbgs() << "Itinerary for " << InstName << ": " 926 << SC.ItinClassDef->getName() << '\n'; 927 } 928 if (!SC.Writes.empty()) { 929 ProcIndices.push_back(0); 930 LLVM_DEBUG({ 931 dbgs() << "SchedRW machine model for " << InstName; 932 for (unsigned int Write : SC.Writes) 933 dbgs() << " " << SchedWrites[Write].Name; 934 for (unsigned int Read : SC.Reads) 935 dbgs() << " " << SchedReads[Read].Name; 936 dbgs() << '\n'; 937 }); 938 } 939 const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs; 940 for (Record *RWDef : RWDefs) { 941 const CodeGenProcModel &ProcModel = 942 getProcModel(RWDef->getValueAsDef("SchedModel")); 943 ProcIndices.push_back(ProcModel.Index); 944 LLVM_DEBUG(dbgs() << "InstRW on " << ProcModel.ModelName << " for " 945 << InstName); 946 IdxVec Writes; 947 IdxVec Reads; 948 findRWs(RWDef->getValueAsListOfDefs("OperandReadWrites"), 949 Writes, Reads); 950 LLVM_DEBUG({ 951 for (unsigned WIdx : Writes) 952 dbgs() << " " << SchedWrites[WIdx].Name; 953 for (unsigned RIdx : Reads) 954 dbgs() << " " << SchedReads[RIdx].Name; 955 dbgs() << '\n'; 956 }); 957 } 958 // If ProcIndices contains zero, the class applies to all processors. 959 LLVM_DEBUG({ 960 if (!llvm::is_contained(ProcIndices, 0)) { 961 for (const CodeGenProcModel &PM : ProcModels) { 962 if (!llvm::is_contained(ProcIndices, PM.Index)) 963 dbgs() << "No machine model for " << Inst->TheDef->getName() 964 << " on processor " << PM.ModelName << '\n'; 965 } 966 } 967 }); 968 } 969 } 970 971 // Get the SchedClass index for an instruction. 972 unsigned 973 CodeGenSchedModels::getSchedClassIdx(const CodeGenInstruction &Inst) const { 974 return InstrClassMap.lookup(Inst.TheDef); 975 } 976 977 std::string 978 CodeGenSchedModels::createSchedClassName(Record *ItinClassDef, 979 ArrayRef<unsigned> OperWrites, 980 ArrayRef<unsigned> OperReads) { 981 982 std::string Name; 983 if (ItinClassDef && ItinClassDef->getName() != "NoItinerary") 984 Name = std::string(ItinClassDef->getName()); 985 for (unsigned Idx : OperWrites) { 986 if (!Name.empty()) 987 Name += '_'; 988 Name += SchedWrites[Idx].Name; 989 } 990 for (unsigned Idx : OperReads) { 991 Name += '_'; 992 Name += SchedReads[Idx].Name; 993 } 994 return Name; 995 } 996 997 std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { 998 999 std::string Name; 1000 ListSeparator LS("_"); 1001 for (const Record *InstDef : InstDefs) { 1002 Name += LS; 1003 Name += InstDef->getName(); 1004 } 1005 return Name; 1006 } 1007 1008 /// Add an inferred sched class from an itinerary class and per-operand list of 1009 /// SchedWrites and SchedReads. ProcIndices contains the set of IDs of 1010 /// processors that may utilize this class. 1011 unsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef, 1012 ArrayRef<unsigned> OperWrites, 1013 ArrayRef<unsigned> OperReads, 1014 ArrayRef<unsigned> ProcIndices) { 1015 assert(!ProcIndices.empty() && "expect at least one ProcIdx"); 1016 1017 auto IsKeyEqual = [=](const CodeGenSchedClass &SC) { 1018 return SC.isKeyEqual(ItinClassDef, OperWrites, OperReads); 1019 }; 1020 1021 auto I = find_if(make_range(schedClassBegin(), schedClassEnd()), IsKeyEqual); 1022 unsigned Idx = I == schedClassEnd() ? 0 : std::distance(schedClassBegin(), I); 1023 if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) { 1024 IdxVec PI; 1025 std::set_union(SchedClasses[Idx].ProcIndices.begin(), 1026 SchedClasses[Idx].ProcIndices.end(), 1027 ProcIndices.begin(), ProcIndices.end(), 1028 std::back_inserter(PI)); 1029 SchedClasses[Idx].ProcIndices = std::move(PI); 1030 return Idx; 1031 } 1032 Idx = SchedClasses.size(); 1033 SchedClasses.emplace_back(Idx, 1034 createSchedClassName(ItinClassDef, OperWrites, 1035 OperReads), 1036 ItinClassDef); 1037 CodeGenSchedClass &SC = SchedClasses.back(); 1038 SC.Writes = OperWrites; 1039 SC.Reads = OperReads; 1040 SC.ProcIndices = ProcIndices; 1041 1042 return Idx; 1043 } 1044 1045 // Create classes for each set of opcodes that are in the same InstReadWrite 1046 // definition across all processors. 1047 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { 1048 // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that 1049 // intersects with an existing class via a previous InstRWDef. Instrs that do 1050 // not intersect with an existing class refer back to their former class as 1051 // determined from ItinDef or SchedRW. 1052 SmallMapVector<unsigned, SmallVector<Record *, 8>, 4> ClassInstrs; 1053 // Sort Instrs into sets. 1054 const RecVec *InstDefs = Sets.expand(InstRWDef); 1055 if (InstDefs->empty()) 1056 PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes"); 1057 1058 for (Record *InstDef : *InstDefs) { 1059 InstClassMapTy::const_iterator Pos = InstrClassMap.find(InstDef); 1060 if (Pos == InstrClassMap.end()) 1061 PrintFatalError(InstDef->getLoc(), "No sched class for instruction."); 1062 unsigned SCIdx = Pos->second; 1063 ClassInstrs[SCIdx].push_back(InstDef); 1064 } 1065 // For each set of Instrs, create a new class if necessary, and map or remap 1066 // the Instrs to it. 1067 for (auto &Entry : ClassInstrs) { 1068 unsigned OldSCIdx = Entry.first; 1069 ArrayRef<Record*> InstDefs = Entry.second; 1070 // If the all instrs in the current class are accounted for, then leave 1071 // them mapped to their old class. 1072 if (OldSCIdx) { 1073 const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs; 1074 if (!RWDefs.empty()) { 1075 const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]); 1076 unsigned OrigNumInstrs = 1077 count_if(*OrigInstDefs, [&](Record *OIDef) { 1078 return InstrClassMap[OIDef] == OldSCIdx; 1079 }); 1080 if (OrigNumInstrs == InstDefs.size()) { 1081 assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 && 1082 "expected a generic SchedClass"); 1083 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 1084 // Make sure we didn't already have a InstRW containing this 1085 // instruction on this model. 1086 for (Record *RWD : RWDefs) { 1087 if (RWD->getValueAsDef("SchedModel") == RWModelDef && 1088 RWModelDef->getValueAsBit("FullInstRWOverlapCheck")) { 1089 assert(!InstDefs.empty()); // Checked at function start. 1090 PrintError( 1091 InstRWDef->getLoc(), 1092 "Overlapping InstRW definition for \"" + 1093 InstDefs.front()->getName() + 1094 "\" also matches previous \"" + 1095 RWD->getValue("Instrs")->getValue()->getAsString() + 1096 "\"."); 1097 PrintFatalNote(RWD->getLoc(), "Previous match was here."); 1098 } 1099 } 1100 LLVM_DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":" 1101 << SchedClasses[OldSCIdx].Name << " on " 1102 << RWModelDef->getName() << "\n"); 1103 SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef); 1104 continue; 1105 } 1106 } 1107 } 1108 unsigned SCIdx = SchedClasses.size(); 1109 SchedClasses.emplace_back(SCIdx, createSchedClassName(InstDefs), nullptr); 1110 CodeGenSchedClass &SC = SchedClasses.back(); 1111 LLVM_DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on " 1112 << InstRWDef->getValueAsDef("SchedModel")->getName() 1113 << "\n"); 1114 1115 // Preserve ItinDef and Writes/Reads for processors without an InstRW entry. 1116 SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef; 1117 SC.Writes = SchedClasses[OldSCIdx].Writes; 1118 SC.Reads = SchedClasses[OldSCIdx].Reads; 1119 SC.ProcIndices.push_back(0); 1120 // If we had an old class, copy it's InstRWs to this new class. 1121 if (OldSCIdx) { 1122 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 1123 for (Record *OldRWDef : SchedClasses[OldSCIdx].InstRWs) { 1124 if (OldRWDef->getValueAsDef("SchedModel") == RWModelDef) { 1125 assert(!InstDefs.empty()); // Checked at function start. 1126 PrintError( 1127 InstRWDef->getLoc(), 1128 "Overlapping InstRW definition for \"" + 1129 InstDefs.front()->getName() + "\" also matches previous \"" + 1130 OldRWDef->getValue("Instrs")->getValue()->getAsString() + 1131 "\"."); 1132 PrintFatalNote(OldRWDef->getLoc(), "Previous match was here."); 1133 } 1134 assert(OldRWDef != InstRWDef && 1135 "SchedClass has duplicate InstRW def"); 1136 SC.InstRWs.push_back(OldRWDef); 1137 } 1138 } 1139 // Map each Instr to this new class. 1140 for (Record *InstDef : InstDefs) 1141 InstrClassMap[InstDef] = SCIdx; 1142 SC.InstRWs.push_back(InstRWDef); 1143 } 1144 } 1145 1146 // True if collectProcItins found anything. 1147 bool CodeGenSchedModels::hasItineraries() const { 1148 for (const CodeGenProcModel &PM : make_range(procModelBegin(),procModelEnd())) 1149 if (PM.hasItineraries()) 1150 return true; 1151 return false; 1152 } 1153 1154 // Gather the processor itineraries. 1155 void CodeGenSchedModels::collectProcItins() { 1156 LLVM_DEBUG(dbgs() << "\n+++ PROBLEM ITINERARIES (collectProcItins) +++\n"); 1157 for (CodeGenProcModel &ProcModel : ProcModels) { 1158 if (!ProcModel.hasItineraries()) 1159 continue; 1160 1161 RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID"); 1162 assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect"); 1163 1164 // Populate ItinDefList with Itinerary records. 1165 ProcModel.ItinDefList.resize(NumInstrSchedClasses); 1166 1167 // Insert each itinerary data record in the correct position within 1168 // the processor model's ItinDefList. 1169 for (Record *ItinData : ItinRecords) { 1170 const Record *ItinDef = ItinData->getValueAsDef("TheClass"); 1171 bool FoundClass = false; 1172 1173 for (const CodeGenSchedClass &SC : 1174 make_range(schedClassBegin(), schedClassEnd())) { 1175 // Multiple SchedClasses may share an itinerary. Update all of them. 1176 if (SC.ItinClassDef == ItinDef) { 1177 ProcModel.ItinDefList[SC.Index] = ItinData; 1178 FoundClass = true; 1179 } 1180 } 1181 if (!FoundClass) { 1182 LLVM_DEBUG(dbgs() << ProcModel.ItinsDef->getName() 1183 << " missing class for itinerary " 1184 << ItinDef->getName() << '\n'); 1185 } 1186 } 1187 // Check for missing itinerary entries. 1188 assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); 1189 LLVM_DEBUG( 1190 for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { 1191 if (!ProcModel.ItinDefList[i]) 1192 dbgs() << ProcModel.ItinsDef->getName() 1193 << " missing itinerary for class " << SchedClasses[i].Name 1194 << '\n'; 1195 }); 1196 } 1197 } 1198 1199 // Gather the read/write types for each itinerary class. 1200 void CodeGenSchedModels::collectProcItinRW() { 1201 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 1202 llvm::sort(ItinRWDefs, LessRecord()); 1203 for (Record *RWDef : ItinRWDefs) { 1204 if (!RWDef->getValueInit("SchedModel")->isComplete()) 1205 PrintFatalError(RWDef->getLoc(), "SchedModel is undefined"); 1206 Record *ModelDef = RWDef->getValueAsDef("SchedModel"); 1207 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 1208 if (I == ProcModelMap.end()) { 1209 PrintFatalError(RWDef->getLoc(), "Undefined SchedMachineModel " 1210 + ModelDef->getName()); 1211 } 1212 ProcModels[I->second].ItinRWDefs.push_back(RWDef); 1213 } 1214 } 1215 1216 // Gather the unsupported features for processor models. 1217 void CodeGenSchedModels::collectProcUnsupportedFeatures() { 1218 for (CodeGenProcModel &ProcModel : ProcModels) 1219 append_range( 1220 ProcModel.UnsupportedFeaturesDefs, 1221 ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")); 1222 } 1223 1224 /// Infer new classes from existing classes. In the process, this may create new 1225 /// SchedWrites from sequences of existing SchedWrites. 1226 void CodeGenSchedModels::inferSchedClasses() { 1227 LLVM_DEBUG( 1228 dbgs() << "\n+++ INFERRING SCHED CLASSES (inferSchedClasses) +++\n"); 1229 LLVM_DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n"); 1230 1231 // Visit all existing classes and newly created classes. 1232 for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) { 1233 assert(SchedClasses[Idx].Index == Idx && "bad SCIdx"); 1234 1235 if (SchedClasses[Idx].ItinClassDef) 1236 inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx); 1237 if (!SchedClasses[Idx].InstRWs.empty()) 1238 inferFromInstRWs(Idx); 1239 if (!SchedClasses[Idx].Writes.empty()) { 1240 inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads, 1241 Idx, SchedClasses[Idx].ProcIndices); 1242 } 1243 assert(SchedClasses.size() < (NumInstrSchedClasses*6) && 1244 "too many SchedVariants"); 1245 } 1246 } 1247 1248 /// Infer classes from per-processor itinerary resources. 1249 void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef, 1250 unsigned FromClassIdx) { 1251 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1252 const CodeGenProcModel &PM = ProcModels[PIdx]; 1253 // For all ItinRW entries. 1254 bool HasMatch = false; 1255 for (const Record *Rec : PM.ItinRWDefs) { 1256 RecVec Matched = Rec->getValueAsListOfDefs("MatchedItinClasses"); 1257 if (!llvm::is_contained(Matched, ItinClassDef)) 1258 continue; 1259 if (HasMatch) 1260 PrintFatalError(Rec->getLoc(), "Duplicate itinerary class " 1261 + ItinClassDef->getName() 1262 + " in ItinResources for " + PM.ModelName); 1263 HasMatch = true; 1264 IdxVec Writes, Reads; 1265 findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1266 inferFromRW(Writes, Reads, FromClassIdx, PIdx); 1267 } 1268 } 1269 } 1270 1271 /// Infer classes from per-processor InstReadWrite definitions. 1272 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) { 1273 for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) { 1274 assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!"); 1275 Record *Rec = SchedClasses[SCIdx].InstRWs[I]; 1276 const RecVec *InstDefs = Sets.expand(Rec); 1277 RecIter II = InstDefs->begin(), IE = InstDefs->end(); 1278 for (; II != IE; ++II) { 1279 if (InstrClassMap[*II] == SCIdx) 1280 break; 1281 } 1282 // If this class no longer has any instructions mapped to it, it has become 1283 // irrelevant. 1284 if (II == IE) 1285 continue; 1286 IdxVec Writes, Reads; 1287 findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1288 unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index; 1289 inferFromRW(Writes, Reads, SCIdx, PIdx); // May mutate SchedClasses. 1290 SchedClasses[SCIdx].InstRWProcIndices.insert(PIdx); 1291 } 1292 } 1293 1294 namespace { 1295 1296 // Helper for substituteVariantOperand. 1297 struct TransVariant { 1298 Record *VarOrSeqDef; // Variant or sequence. 1299 unsigned RWIdx; // Index of this variant or sequence's matched type. 1300 unsigned ProcIdx; // Processor model index or zero for any. 1301 unsigned TransVecIdx; // Index into PredTransitions::TransVec. 1302 1303 TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti): 1304 VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {} 1305 }; 1306 1307 // Associate a predicate with the SchedReadWrite that it guards. 1308 // RWIdx is the index of the read/write variant. 1309 struct PredCheck { 1310 bool IsRead; 1311 unsigned RWIdx; 1312 Record *Predicate; 1313 1314 PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {} 1315 }; 1316 1317 // A Predicate transition is a list of RW sequences guarded by a PredTerm. 1318 struct PredTransition { 1319 // A predicate term is a conjunction of PredChecks. 1320 SmallVector<PredCheck, 4> PredTerm; 1321 SmallVector<SmallVector<unsigned,4>, 16> WriteSequences; 1322 SmallVector<SmallVector<unsigned,4>, 16> ReadSequences; 1323 unsigned ProcIndex = 0; 1324 1325 PredTransition() = default; 1326 PredTransition(ArrayRef<PredCheck> PT, unsigned ProcId) { 1327 PredTerm.assign(PT.begin(), PT.end()); 1328 ProcIndex = ProcId; 1329 } 1330 }; 1331 1332 // Encapsulate a set of partially constructed transitions. 1333 // The results are built by repeated calls to substituteVariants. 1334 class PredTransitions { 1335 CodeGenSchedModels &SchedModels; 1336 1337 public: 1338 std::vector<PredTransition> TransVec; 1339 1340 PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {} 1341 1342 bool substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq, 1343 bool IsRead, unsigned StartIdx); 1344 1345 bool substituteVariants(const PredTransition &Trans); 1346 1347 #ifndef NDEBUG 1348 void dump() const; 1349 #endif 1350 1351 private: 1352 bool mutuallyExclusive(Record *PredDef, ArrayRef<Record *> Preds, 1353 ArrayRef<PredCheck> Term); 1354 void getIntersectingVariants( 1355 const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1356 std::vector<TransVariant> &IntersectingVariants); 1357 void pushVariant(const TransVariant &VInfo, bool IsRead); 1358 }; 1359 1360 } // end anonymous namespace 1361 1362 // Return true if this predicate is mutually exclusive with a PredTerm. This 1363 // degenerates into checking if the predicate is mutually exclusive with any 1364 // predicate in the Term's conjunction. 1365 // 1366 // All predicates associated with a given SchedRW are considered mutually 1367 // exclusive. This should work even if the conditions expressed by the 1368 // predicates are not exclusive because the predicates for a given SchedWrite 1369 // are always checked in the order they are defined in the .td file. Later 1370 // conditions implicitly negate any prior condition. 1371 bool PredTransitions::mutuallyExclusive(Record *PredDef, 1372 ArrayRef<Record *> Preds, 1373 ArrayRef<PredCheck> Term) { 1374 for (const PredCheck &PC: Term) { 1375 if (PC.Predicate == PredDef) 1376 return false; 1377 1378 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(PC.RWIdx, PC.IsRead); 1379 assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant"); 1380 RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1381 if (any_of(Variants, [PredDef](const Record *R) { 1382 return R->getValueAsDef("Predicate") == PredDef; 1383 })) { 1384 // To check if PredDef is mutually exclusive with PC we also need to 1385 // check that PC.Predicate is exclusive with all predicates from variant 1386 // we're expanding. Consider following RW sequence with two variants 1387 // (1 & 2), where A, B and C are predicates from corresponding SchedVars: 1388 // 1389 // 1:A/B - 2:C/B 1390 // 1391 // Here C is not mutually exclusive with variant (1), because A doesn't 1392 // exist in variant (2). This means we have possible transitions from A 1393 // to C and from A to B, and fully expanded sequence would look like: 1394 // 1395 // if (A & C) return ...; 1396 // if (A & B) return ...; 1397 // if (B) return ...; 1398 // 1399 // Now let's consider another sequence: 1400 // 1401 // 1:A/B - 2:A/B 1402 // 1403 // Here A in variant (2) is mutually exclusive with variant (1), because 1404 // A also exists in (2). This means A->B transition is impossible and 1405 // expanded sequence would look like: 1406 // 1407 // if (A) return ...; 1408 // if (B) return ...; 1409 if (!llvm::is_contained(Preds, PC.Predicate)) 1410 continue; 1411 return true; 1412 } 1413 } 1414 return false; 1415 } 1416 1417 static std::vector<Record *> getAllPredicates(ArrayRef<TransVariant> Variants, 1418 unsigned ProcId) { 1419 std::vector<Record *> Preds; 1420 for (auto &Variant : Variants) { 1421 if (!Variant.VarOrSeqDef->isSubClassOf("SchedVar")) 1422 continue; 1423 Preds.push_back(Variant.VarOrSeqDef->getValueAsDef("Predicate")); 1424 } 1425 return Preds; 1426 } 1427 1428 // Populate IntersectingVariants with any variants or aliased sequences of the 1429 // given SchedRW whose processor indices and predicates are not mutually 1430 // exclusive with the given transition. 1431 void PredTransitions::getIntersectingVariants( 1432 const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1433 std::vector<TransVariant> &IntersectingVariants) { 1434 1435 bool GenericRW = false; 1436 1437 std::vector<TransVariant> Variants; 1438 if (SchedRW.HasVariants) { 1439 unsigned VarProcIdx = 0; 1440 if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) { 1441 Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel"); 1442 VarProcIdx = SchedModels.getProcModel(ModelDef).Index; 1443 } 1444 if (VarProcIdx == 0 || VarProcIdx == TransVec[TransIdx].ProcIndex) { 1445 // Push each variant. Assign TransVecIdx later. 1446 const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1447 for (Record *VarDef : VarDefs) 1448 Variants.emplace_back(VarDef, SchedRW.Index, VarProcIdx, 0); 1449 if (VarProcIdx == 0) 1450 GenericRW = true; 1451 } 1452 } 1453 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1454 AI != AE; ++AI) { 1455 // If either the SchedAlias itself or the SchedReadWrite that it aliases 1456 // to is defined within a processor model, constrain all variants to 1457 // that processor. 1458 unsigned AliasProcIdx = 0; 1459 if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1460 Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 1461 AliasProcIdx = SchedModels.getProcModel(ModelDef).Index; 1462 } 1463 if (AliasProcIdx && AliasProcIdx != TransVec[TransIdx].ProcIndex) 1464 continue; 1465 if (!Variants.empty()) { 1466 const CodeGenProcModel &PM = 1467 *(SchedModels.procModelBegin() + AliasProcIdx); 1468 PrintFatalError((*AI)->getLoc(), 1469 "Multiple variants defined for processor " + 1470 PM.ModelName + 1471 " Ensure only one SchedAlias exists per RW."); 1472 } 1473 1474 const CodeGenSchedRW &AliasRW = 1475 SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW")); 1476 1477 if (AliasRW.HasVariants) { 1478 const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants"); 1479 for (Record *VD : VarDefs) 1480 Variants.emplace_back(VD, AliasRW.Index, AliasProcIdx, 0); 1481 } 1482 if (AliasRW.IsSequence) 1483 Variants.emplace_back(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0); 1484 if (AliasProcIdx == 0) 1485 GenericRW = true; 1486 } 1487 std::vector<Record *> AllPreds = 1488 getAllPredicates(Variants, TransVec[TransIdx].ProcIndex); 1489 for (TransVariant &Variant : Variants) { 1490 // Don't expand variants if the processor models don't intersect. 1491 // A zero processor index means any processor. 1492 if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) { 1493 Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate"); 1494 if (mutuallyExclusive(PredDef, AllPreds, TransVec[TransIdx].PredTerm)) 1495 continue; 1496 } 1497 1498 if (IntersectingVariants.empty()) { 1499 // The first variant builds on the existing transition. 1500 Variant.TransVecIdx = TransIdx; 1501 IntersectingVariants.push_back(Variant); 1502 } 1503 else { 1504 // Push another copy of the current transition for more variants. 1505 Variant.TransVecIdx = TransVec.size(); 1506 IntersectingVariants.push_back(Variant); 1507 TransVec.push_back(TransVec[TransIdx]); 1508 } 1509 } 1510 if (GenericRW && IntersectingVariants.empty()) { 1511 PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has " 1512 "a matching predicate on any processor"); 1513 } 1514 } 1515 1516 // Push the Reads/Writes selected by this variant onto the PredTransition 1517 // specified by VInfo. 1518 void PredTransitions:: 1519 pushVariant(const TransVariant &VInfo, bool IsRead) { 1520 PredTransition &Trans = TransVec[VInfo.TransVecIdx]; 1521 1522 // If this operand transition is reached through a processor-specific alias, 1523 // then the whole transition is specific to this processor. 1524 IdxVec SelectedRWs; 1525 if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) { 1526 Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate"); 1527 Trans.PredTerm.emplace_back(IsRead, VInfo.RWIdx,PredDef); 1528 RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected"); 1529 SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead); 1530 } 1531 else { 1532 assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") && 1533 "variant must be a SchedVariant or aliased WriteSequence"); 1534 SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead)); 1535 } 1536 1537 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead); 1538 1539 SmallVectorImpl<SmallVector<unsigned,4>> &RWSequences = IsRead 1540 ? Trans.ReadSequences : Trans.WriteSequences; 1541 if (SchedRW.IsVariadic) { 1542 unsigned OperIdx = RWSequences.size()-1; 1543 // Make N-1 copies of this transition's last sequence. 1544 RWSequences.reserve(RWSequences.size() + SelectedRWs.size() - 1); 1545 RWSequences.insert(RWSequences.end(), SelectedRWs.size() - 1, 1546 RWSequences[OperIdx]); 1547 // Push each of the N elements of the SelectedRWs onto a copy of the last 1548 // sequence (split the current operand into N operands). 1549 // Note that write sequences should be expanded within this loop--the entire 1550 // sequence belongs to a single operand. 1551 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1552 RWI != RWE; ++RWI, ++OperIdx) { 1553 IdxVec ExpandedRWs; 1554 if (IsRead) 1555 ExpandedRWs.push_back(*RWI); 1556 else 1557 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1558 llvm::append_range(RWSequences[OperIdx], ExpandedRWs); 1559 } 1560 assert(OperIdx == RWSequences.size() && "missed a sequence"); 1561 } 1562 else { 1563 // Push this transition's expanded sequence onto this transition's last 1564 // sequence (add to the current operand's sequence). 1565 SmallVectorImpl<unsigned> &Seq = RWSequences.back(); 1566 IdxVec ExpandedRWs; 1567 for (unsigned int SelectedRW : SelectedRWs) { 1568 if (IsRead) 1569 ExpandedRWs.push_back(SelectedRW); 1570 else 1571 SchedModels.expandRWSequence(SelectedRW, ExpandedRWs, IsRead); 1572 } 1573 llvm::append_range(Seq, ExpandedRWs); 1574 } 1575 } 1576 1577 // RWSeq is a sequence of all Reads or all Writes for the next read or write 1578 // operand. StartIdx is an index into TransVec where partial results 1579 // starts. RWSeq must be applied to all transitions between StartIdx and the end 1580 // of TransVec. 1581 bool PredTransitions::substituteVariantOperand( 1582 const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) { 1583 bool Subst = false; 1584 // Visit each original RW within the current sequence. 1585 for (unsigned int RWI : RWSeq) { 1586 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(RWI, IsRead); 1587 // Push this RW on all partial PredTransitions or distribute variants. 1588 // New PredTransitions may be pushed within this loop which should not be 1589 // revisited (TransEnd must be loop invariant). 1590 for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size(); 1591 TransIdx != TransEnd; ++TransIdx) { 1592 // Distribute this partial PredTransition across intersecting variants. 1593 // This will push a copies of TransVec[TransIdx] on the back of TransVec. 1594 std::vector<TransVariant> IntersectingVariants; 1595 getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants); 1596 // Now expand each variant on top of its copy of the transition. 1597 for (const TransVariant &IV : IntersectingVariants) 1598 pushVariant(IV, IsRead); 1599 if (IntersectingVariants.empty()) { 1600 if (IsRead) 1601 TransVec[TransIdx].ReadSequences.back().push_back(RWI); 1602 else 1603 TransVec[TransIdx].WriteSequences.back().push_back(RWI); 1604 continue; 1605 } else { 1606 Subst = true; 1607 } 1608 } 1609 } 1610 return Subst; 1611 } 1612 1613 // For each variant of a Read/Write in Trans, substitute the sequence of 1614 // Read/Writes guarded by the variant. This is exponential in the number of 1615 // variant Read/Writes, but in practice detection of mutually exclusive 1616 // predicates should result in linear growth in the total number variants. 1617 // 1618 // This is one step in a breadth-first search of nested variants. 1619 bool PredTransitions::substituteVariants(const PredTransition &Trans) { 1620 // Build up a set of partial results starting at the back of 1621 // PredTransitions. Remember the first new transition. 1622 unsigned StartIdx = TransVec.size(); 1623 bool Subst = false; 1624 assert(Trans.ProcIndex != 0); 1625 TransVec.emplace_back(Trans.PredTerm, Trans.ProcIndex); 1626 1627 // Visit each original write sequence. 1628 for (const auto &WriteSequence : Trans.WriteSequences) { 1629 // Push a new (empty) write sequence onto all partial Transitions. 1630 for (std::vector<PredTransition>::iterator I = 1631 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1632 I->WriteSequences.emplace_back(); 1633 } 1634 Subst |= 1635 substituteVariantOperand(WriteSequence, /*IsRead=*/false, StartIdx); 1636 } 1637 // Visit each original read sequence. 1638 for (const auto &ReadSequence : Trans.ReadSequences) { 1639 // Push a new (empty) read sequence onto all partial Transitions. 1640 for (std::vector<PredTransition>::iterator I = 1641 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1642 I->ReadSequences.emplace_back(); 1643 } 1644 Subst |= substituteVariantOperand(ReadSequence, /*IsRead=*/true, StartIdx); 1645 } 1646 return Subst; 1647 } 1648 1649 static void addSequences(CodeGenSchedModels &SchedModels, 1650 const SmallVectorImpl<SmallVector<unsigned, 4>> &Seqs, 1651 IdxVec &Result, bool IsRead) { 1652 for (const auto &S : Seqs) 1653 if (!S.empty()) 1654 Result.push_back(SchedModels.findOrInsertRW(S, IsRead)); 1655 } 1656 1657 #ifndef NDEBUG 1658 static void dumpRecVec(const RecVec &RV) { 1659 for (const Record *R : RV) 1660 dbgs() << R->getName() << ", "; 1661 } 1662 #endif 1663 1664 static void dumpTransition(const CodeGenSchedModels &SchedModels, 1665 const CodeGenSchedClass &FromSC, 1666 const CodeGenSchedTransition &SCTrans, 1667 const RecVec &Preds) { 1668 LLVM_DEBUG(dbgs() << "Adding transition from " << FromSC.Name << "(" 1669 << FromSC.Index << ") to " 1670 << SchedModels.getSchedClass(SCTrans.ToClassIdx).Name << "(" 1671 << SCTrans.ToClassIdx << ") on pred term: ("; 1672 dumpRecVec(Preds); 1673 dbgs() << ") on processor (" << SCTrans.ProcIndex << ")\n"); 1674 } 1675 // Create a new SchedClass for each variant found by inferFromRW. Pass 1676 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions, 1677 unsigned FromClassIdx, 1678 CodeGenSchedModels &SchedModels) { 1679 // For each PredTransition, create a new CodeGenSchedTransition, which usually 1680 // requires creating a new SchedClass. 1681 for (const auto &LastTransition : LastTransitions) { 1682 // Variant expansion (substituteVariants) may create unconditional 1683 // transitions. We don't need to build sched classes for them. 1684 if (LastTransition.PredTerm.empty()) 1685 continue; 1686 IdxVec OperWritesVariant, OperReadsVariant; 1687 addSequences(SchedModels, LastTransition.WriteSequences, OperWritesVariant, 1688 false); 1689 addSequences(SchedModels, LastTransition.ReadSequences, OperReadsVariant, 1690 true); 1691 CodeGenSchedTransition SCTrans; 1692 1693 // Transition should not contain processor indices already assigned to 1694 // InstRWs in this scheduling class. 1695 const CodeGenSchedClass &FromSC = SchedModels.getSchedClass(FromClassIdx); 1696 if (FromSC.InstRWProcIndices.count(LastTransition.ProcIndex)) 1697 continue; 1698 SCTrans.ProcIndex = LastTransition.ProcIndex; 1699 SCTrans.ToClassIdx = 1700 SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant, 1701 OperReadsVariant, LastTransition.ProcIndex); 1702 1703 // The final PredTerm is unique set of predicates guarding the transition. 1704 RecVec Preds; 1705 transform(LastTransition.PredTerm, std::back_inserter(Preds), 1706 [](const PredCheck &P) { return P.Predicate; }); 1707 Preds.erase(std::unique(Preds.begin(), Preds.end()), Preds.end()); 1708 dumpTransition(SchedModels, FromSC, SCTrans, Preds); 1709 SCTrans.PredTerm = std::move(Preds); 1710 SchedModels.getSchedClass(FromClassIdx) 1711 .Transitions.push_back(std::move(SCTrans)); 1712 } 1713 } 1714 1715 std::vector<unsigned> CodeGenSchedModels::getAllProcIndices() const { 1716 std::vector<unsigned> ProcIdVec; 1717 for (const auto &PM : ProcModelMap) 1718 if (PM.second != 0) 1719 ProcIdVec.push_back(PM.second); 1720 // The order of the keys (Record pointers) of ProcModelMap are not stable. 1721 // Sort to stabalize the values. 1722 llvm::sort(ProcIdVec); 1723 return ProcIdVec; 1724 } 1725 1726 static std::vector<PredTransition> 1727 makePerProcessorTransitions(const PredTransition &Trans, 1728 ArrayRef<unsigned> ProcIndices) { 1729 std::vector<PredTransition> PerCpuTransVec; 1730 for (unsigned ProcId : ProcIndices) { 1731 assert(ProcId != 0); 1732 PerCpuTransVec.push_back(Trans); 1733 PerCpuTransVec.back().ProcIndex = ProcId; 1734 } 1735 return PerCpuTransVec; 1736 } 1737 1738 // Create new SchedClasses for the given ReadWrite list. If any of the 1739 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant 1740 // of the ReadWrite list, following Aliases if necessary. 1741 void CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites, 1742 ArrayRef<unsigned> OperReads, 1743 unsigned FromClassIdx, 1744 ArrayRef<unsigned> ProcIndices) { 1745 LLVM_DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); 1746 dbgs() << ") "); 1747 // Create a seed transition with an empty PredTerm and the expanded sequences 1748 // of SchedWrites for the current SchedClass. 1749 std::vector<PredTransition> LastTransitions; 1750 LastTransitions.emplace_back(); 1751 1752 for (unsigned WriteIdx : OperWrites) { 1753 IdxVec WriteSeq; 1754 expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false); 1755 LastTransitions[0].WriteSequences.emplace_back(); 1756 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences.back(); 1757 Seq.append(WriteSeq.begin(), WriteSeq.end()); 1758 LLVM_DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1759 } 1760 LLVM_DEBUG(dbgs() << " Reads: "); 1761 for (unsigned ReadIdx : OperReads) { 1762 IdxVec ReadSeq; 1763 expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true); 1764 LastTransitions[0].ReadSequences.emplace_back(); 1765 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences.back(); 1766 Seq.append(ReadSeq.begin(), ReadSeq.end()); 1767 LLVM_DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1768 } 1769 LLVM_DEBUG(dbgs() << '\n'); 1770 1771 LastTransitions = makePerProcessorTransitions( 1772 LastTransitions[0], llvm::is_contained(ProcIndices, 0) 1773 ? ArrayRef<unsigned>(getAllProcIndices()) 1774 : ProcIndices); 1775 // Collect all PredTransitions for individual operands. 1776 // Iterate until no variant writes remain. 1777 bool SubstitutedAny; 1778 do { 1779 SubstitutedAny = false; 1780 PredTransitions Transitions(*this); 1781 for (const PredTransition &Trans : LastTransitions) 1782 SubstitutedAny |= Transitions.substituteVariants(Trans); 1783 LLVM_DEBUG(Transitions.dump()); 1784 LastTransitions.swap(Transitions.TransVec); 1785 } while (SubstitutedAny); 1786 1787 // WARNING: We are about to mutate the SchedClasses vector. Do not refer to 1788 // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions. 1789 inferFromTransitions(LastTransitions, FromClassIdx, *this); 1790 } 1791 1792 // Check if any processor resource group contains all resource records in 1793 // SubUnits. 1794 bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) { 1795 for (Record *ProcResourceDef : PM.ProcResourceDefs) { 1796 if (!ProcResourceDef->isSubClassOf("ProcResGroup")) 1797 continue; 1798 RecVec SuperUnits = ProcResourceDef->getValueAsListOfDefs("Resources"); 1799 RecIter RI = SubUnits.begin(), RE = SubUnits.end(); 1800 for ( ; RI != RE; ++RI) { 1801 if (!is_contained(SuperUnits, *RI)) { 1802 break; 1803 } 1804 } 1805 if (RI == RE) 1806 return true; 1807 } 1808 return false; 1809 } 1810 1811 // Verify that overlapping groups have a common supergroup. 1812 void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) { 1813 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1814 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1815 continue; 1816 RecVec CheckUnits = 1817 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1818 for (unsigned j = i+1; j < e; ++j) { 1819 if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup")) 1820 continue; 1821 RecVec OtherUnits = 1822 PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources"); 1823 if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(), 1824 OtherUnits.begin(), OtherUnits.end()) 1825 != CheckUnits.end()) { 1826 // CheckUnits and OtherUnits overlap 1827 llvm::append_range(OtherUnits, CheckUnits); 1828 if (!hasSuperGroup(OtherUnits, PM)) { 1829 PrintFatalError((PM.ProcResourceDefs[i])->getLoc(), 1830 "proc resource group overlaps with " 1831 + PM.ProcResourceDefs[j]->getName() 1832 + " but no supergroup contains both."); 1833 } 1834 } 1835 } 1836 } 1837 } 1838 1839 // Collect all the RegisterFile definitions available in this target. 1840 void CodeGenSchedModels::collectRegisterFiles() { 1841 RecVec RegisterFileDefs = Records.getAllDerivedDefinitions("RegisterFile"); 1842 1843 // RegisterFiles is the vector of CodeGenRegisterFile. 1844 for (Record *RF : RegisterFileDefs) { 1845 // For each register file definition, construct a CodeGenRegisterFile object 1846 // and add it to the appropriate scheduling model. 1847 CodeGenProcModel &PM = getProcModel(RF->getValueAsDef("SchedModel")); 1848 PM.RegisterFiles.emplace_back(CodeGenRegisterFile(RF->getName(),RF)); 1849 CodeGenRegisterFile &CGRF = PM.RegisterFiles.back(); 1850 CGRF.MaxMovesEliminatedPerCycle = 1851 RF->getValueAsInt("MaxMovesEliminatedPerCycle"); 1852 CGRF.AllowZeroMoveEliminationOnly = 1853 RF->getValueAsBit("AllowZeroMoveEliminationOnly"); 1854 1855 // Now set the number of physical registers as well as the cost of registers 1856 // in each register class. 1857 CGRF.NumPhysRegs = RF->getValueAsInt("NumPhysRegs"); 1858 if (!CGRF.NumPhysRegs) { 1859 PrintFatalError(RF->getLoc(), 1860 "Invalid RegisterFile with zero physical registers"); 1861 } 1862 1863 RecVec RegisterClasses = RF->getValueAsListOfDefs("RegClasses"); 1864 std::vector<int64_t> RegisterCosts = RF->getValueAsListOfInts("RegCosts"); 1865 ListInit *MoveElimInfo = RF->getValueAsListInit("AllowMoveElimination"); 1866 for (unsigned I = 0, E = RegisterClasses.size(); I < E; ++I) { 1867 int Cost = RegisterCosts.size() > I ? RegisterCosts[I] : 1; 1868 1869 bool AllowMoveElim = false; 1870 if (MoveElimInfo->size() > I) { 1871 BitInit *Val = cast<BitInit>(MoveElimInfo->getElement(I)); 1872 AllowMoveElim = Val->getValue(); 1873 } 1874 1875 CGRF.Costs.emplace_back(RegisterClasses[I], Cost, AllowMoveElim); 1876 } 1877 } 1878 } 1879 1880 // Collect and sort WriteRes, ReadAdvance, and ProcResources. 1881 void CodeGenSchedModels::collectProcResources() { 1882 ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits"); 1883 ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1884 1885 // Add any subtarget-specific SchedReadWrites that are directly associated 1886 // with processor resources. Refer to the parent SchedClass's ProcIndices to 1887 // determine which processors they apply to. 1888 for (const CodeGenSchedClass &SC : 1889 make_range(schedClassBegin(), schedClassEnd())) { 1890 if (SC.ItinClassDef) { 1891 collectItinProcResources(SC.ItinClassDef); 1892 continue; 1893 } 1894 1895 // This class may have a default ReadWrite list which can be overriden by 1896 // InstRW definitions. 1897 for (Record *RW : SC.InstRWs) { 1898 Record *RWModelDef = RW->getValueAsDef("SchedModel"); 1899 unsigned PIdx = getProcModel(RWModelDef).Index; 1900 IdxVec Writes, Reads; 1901 findRWs(RW->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1902 collectRWResources(Writes, Reads, PIdx); 1903 } 1904 1905 collectRWResources(SC.Writes, SC.Reads, SC.ProcIndices); 1906 } 1907 // Add resources separately defined by each subtarget. 1908 RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes"); 1909 for (Record *WR : WRDefs) { 1910 Record *ModelDef = WR->getValueAsDef("SchedModel"); 1911 addWriteRes(WR, getProcModel(ModelDef).Index); 1912 } 1913 RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes"); 1914 for (Record *SWR : SWRDefs) { 1915 Record *ModelDef = SWR->getValueAsDef("SchedModel"); 1916 addWriteRes(SWR, getProcModel(ModelDef).Index); 1917 } 1918 RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance"); 1919 for (Record *RA : RADefs) { 1920 Record *ModelDef = RA->getValueAsDef("SchedModel"); 1921 addReadAdvance(RA, getProcModel(ModelDef).Index); 1922 } 1923 RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance"); 1924 for (Record *SRA : SRADefs) { 1925 if (SRA->getValueInit("SchedModel")->isComplete()) { 1926 Record *ModelDef = SRA->getValueAsDef("SchedModel"); 1927 addReadAdvance(SRA, getProcModel(ModelDef).Index); 1928 } 1929 } 1930 // Add ProcResGroups that are defined within this processor model, which may 1931 // not be directly referenced but may directly specify a buffer size. 1932 RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1933 for (Record *PRG : ProcResGroups) { 1934 if (!PRG->getValueInit("SchedModel")->isComplete()) 1935 continue; 1936 CodeGenProcModel &PM = getProcModel(PRG->getValueAsDef("SchedModel")); 1937 if (!is_contained(PM.ProcResourceDefs, PRG)) 1938 PM.ProcResourceDefs.push_back(PRG); 1939 } 1940 // Add ProcResourceUnits unconditionally. 1941 for (Record *PRU : Records.getAllDerivedDefinitions("ProcResourceUnits")) { 1942 if (!PRU->getValueInit("SchedModel")->isComplete()) 1943 continue; 1944 CodeGenProcModel &PM = getProcModel(PRU->getValueAsDef("SchedModel")); 1945 if (!is_contained(PM.ProcResourceDefs, PRU)) 1946 PM.ProcResourceDefs.push_back(PRU); 1947 } 1948 // Finalize each ProcModel by sorting the record arrays. 1949 for (CodeGenProcModel &PM : ProcModels) { 1950 llvm::sort(PM.WriteResDefs, LessRecord()); 1951 llvm::sort(PM.ReadAdvanceDefs, LessRecord()); 1952 llvm::sort(PM.ProcResourceDefs, LessRecord()); 1953 LLVM_DEBUG( 1954 PM.dump(); dbgs() << "WriteResDefs: "; for (auto WriteResDef 1955 : PM.WriteResDefs) { 1956 if (WriteResDef->isSubClassOf("WriteRes")) 1957 dbgs() << WriteResDef->getValueAsDef("WriteType")->getName() << " "; 1958 else 1959 dbgs() << WriteResDef->getName() << " "; 1960 } dbgs() << "\nReadAdvanceDefs: "; 1961 for (Record *ReadAdvanceDef 1962 : PM.ReadAdvanceDefs) { 1963 if (ReadAdvanceDef->isSubClassOf("ReadAdvance")) 1964 dbgs() << ReadAdvanceDef->getValueAsDef("ReadType")->getName() 1965 << " "; 1966 else 1967 dbgs() << ReadAdvanceDef->getName() << " "; 1968 } dbgs() 1969 << "\nProcResourceDefs: "; 1970 for (Record *ProcResourceDef 1971 : PM.ProcResourceDefs) { 1972 dbgs() << ProcResourceDef->getName() << " "; 1973 } dbgs() 1974 << '\n'); 1975 verifyProcResourceGroups(PM); 1976 } 1977 1978 ProcResourceDefs.clear(); 1979 ProcResGroups.clear(); 1980 } 1981 1982 void CodeGenSchedModels::checkCompleteness() { 1983 bool Complete = true; 1984 for (const CodeGenProcModel &ProcModel : procModels()) { 1985 const bool HasItineraries = ProcModel.hasItineraries(); 1986 if (!ProcModel.ModelDef->getValueAsBit("CompleteModel")) 1987 continue; 1988 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 1989 if (Inst->hasNoSchedulingInfo) 1990 continue; 1991 if (ProcModel.isUnsupported(*Inst)) 1992 continue; 1993 unsigned SCIdx = getSchedClassIdx(*Inst); 1994 if (!SCIdx) { 1995 if (Inst->TheDef->isValueUnset("SchedRW")) { 1996 PrintError(Inst->TheDef->getLoc(), 1997 "No schedule information for instruction '" + 1998 Inst->TheDef->getName() + "' in SchedMachineModel '" + 1999 ProcModel.ModelDef->getName() + "'"); 2000 Complete = false; 2001 } 2002 continue; 2003 } 2004 2005 const CodeGenSchedClass &SC = getSchedClass(SCIdx); 2006 if (!SC.Writes.empty()) 2007 continue; 2008 if (HasItineraries && SC.ItinClassDef != nullptr && 2009 SC.ItinClassDef->getName() != "NoItinerary") 2010 continue; 2011 2012 const RecVec &InstRWs = SC.InstRWs; 2013 auto I = find_if(InstRWs, [&ProcModel](const Record *R) { 2014 return R->getValueAsDef("SchedModel") == ProcModel.ModelDef; 2015 }); 2016 if (I == InstRWs.end()) { 2017 PrintError(Inst->TheDef->getLoc(), "'" + ProcModel.ModelName + 2018 "' lacks information for '" + 2019 Inst->TheDef->getName() + "'"); 2020 Complete = false; 2021 } 2022 } 2023 } 2024 if (!Complete) { 2025 errs() << "\n\nIncomplete schedule models found.\n" 2026 << "- Consider setting 'CompleteModel = 0' while developing new models.\n" 2027 << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n" 2028 << "- Instructions should usually have Sched<[...]> as a superclass, " 2029 "you may temporarily use an empty list.\n" 2030 << "- Instructions related to unsupported features can be excluded with " 2031 "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the " 2032 "processor model.\n\n"; 2033 PrintFatalError("Incomplete schedule model"); 2034 } 2035 } 2036 2037 // Collect itinerary class resources for each processor. 2038 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) { 2039 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 2040 const CodeGenProcModel &PM = ProcModels[PIdx]; 2041 // For all ItinRW entries. 2042 bool HasMatch = false; 2043 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 2044 II != IE; ++II) { 2045 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 2046 if (!llvm::is_contained(Matched, ItinClassDef)) 2047 continue; 2048 if (HasMatch) 2049 PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 2050 + ItinClassDef->getName() 2051 + " in ItinResources for " + PM.ModelName); 2052 HasMatch = true; 2053 IdxVec Writes, Reads; 2054 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 2055 collectRWResources(Writes, Reads, PIdx); 2056 } 2057 } 2058 } 2059 2060 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead, 2061 ArrayRef<unsigned> ProcIndices) { 2062 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 2063 if (SchedRW.TheDef) { 2064 if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) { 2065 for (unsigned Idx : ProcIndices) 2066 addWriteRes(SchedRW.TheDef, Idx); 2067 } 2068 else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) { 2069 for (unsigned Idx : ProcIndices) 2070 addReadAdvance(SchedRW.TheDef, Idx); 2071 } 2072 } 2073 for (auto *Alias : SchedRW.Aliases) { 2074 IdxVec AliasProcIndices; 2075 if (Alias->getValueInit("SchedModel")->isComplete()) { 2076 AliasProcIndices.push_back( 2077 getProcModel(Alias->getValueAsDef("SchedModel")).Index); 2078 } else 2079 AliasProcIndices = ProcIndices; 2080 const CodeGenSchedRW &AliasRW = getSchedRW(Alias->getValueAsDef("AliasRW")); 2081 assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes"); 2082 2083 IdxVec ExpandedRWs; 2084 expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead); 2085 for (unsigned int ExpandedRW : ExpandedRWs) { 2086 collectRWResources(ExpandedRW, IsRead, AliasProcIndices); 2087 } 2088 } 2089 } 2090 2091 // Collect resources for a set of read/write types and processor indices. 2092 void CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes, 2093 ArrayRef<unsigned> Reads, 2094 ArrayRef<unsigned> ProcIndices) { 2095 for (unsigned Idx : Writes) 2096 collectRWResources(Idx, /*IsRead=*/false, ProcIndices); 2097 2098 for (unsigned Idx : Reads) 2099 collectRWResources(Idx, /*IsRead=*/true, ProcIndices); 2100 } 2101 2102 // Find the processor's resource units for this kind of resource. 2103 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind, 2104 const CodeGenProcModel &PM, 2105 ArrayRef<SMLoc> Loc) const { 2106 if (ProcResKind->isSubClassOf("ProcResourceUnits")) 2107 return ProcResKind; 2108 2109 Record *ProcUnitDef = nullptr; 2110 assert(!ProcResourceDefs.empty()); 2111 assert(!ProcResGroups.empty()); 2112 2113 for (Record *ProcResDef : ProcResourceDefs) { 2114 if (ProcResDef->getValueAsDef("Kind") == ProcResKind 2115 && ProcResDef->getValueAsDef("SchedModel") == PM.ModelDef) { 2116 if (ProcUnitDef) { 2117 PrintFatalError(Loc, 2118 "Multiple ProcessorResourceUnits associated with " 2119 + ProcResKind->getName()); 2120 } 2121 ProcUnitDef = ProcResDef; 2122 } 2123 } 2124 for (Record *ProcResGroup : ProcResGroups) { 2125 if (ProcResGroup == ProcResKind 2126 && ProcResGroup->getValueAsDef("SchedModel") == PM.ModelDef) { 2127 if (ProcUnitDef) { 2128 PrintFatalError(Loc, 2129 "Multiple ProcessorResourceUnits associated with " 2130 + ProcResKind->getName()); 2131 } 2132 ProcUnitDef = ProcResGroup; 2133 } 2134 } 2135 if (!ProcUnitDef) { 2136 PrintFatalError(Loc, 2137 "No ProcessorResources associated with " 2138 + ProcResKind->getName()); 2139 } 2140 return ProcUnitDef; 2141 } 2142 2143 // Iteratively add a resource and its super resources. 2144 void CodeGenSchedModels::addProcResource(Record *ProcResKind, 2145 CodeGenProcModel &PM, 2146 ArrayRef<SMLoc> Loc) { 2147 while (true) { 2148 Record *ProcResUnits = findProcResUnits(ProcResKind, PM, Loc); 2149 2150 // See if this ProcResource is already associated with this processor. 2151 if (is_contained(PM.ProcResourceDefs, ProcResUnits)) 2152 return; 2153 2154 PM.ProcResourceDefs.push_back(ProcResUnits); 2155 if (ProcResUnits->isSubClassOf("ProcResGroup")) 2156 return; 2157 2158 if (!ProcResUnits->getValueInit("Super")->isComplete()) 2159 return; 2160 2161 ProcResKind = ProcResUnits->getValueAsDef("Super"); 2162 } 2163 } 2164 2165 // Add resources for a SchedWrite to this processor if they don't exist. 2166 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) { 2167 assert(PIdx && "don't add resources to an invalid Processor model"); 2168 2169 RecVec &WRDefs = ProcModels[PIdx].WriteResDefs; 2170 if (is_contained(WRDefs, ProcWriteResDef)) 2171 return; 2172 WRDefs.push_back(ProcWriteResDef); 2173 2174 // Visit ProcResourceKinds referenced by the newly discovered WriteRes. 2175 RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources"); 2176 for (auto *ProcResDef : ProcResDefs) { 2177 addProcResource(ProcResDef, ProcModels[PIdx], ProcWriteResDef->getLoc()); 2178 } 2179 } 2180 2181 // Add resources for a ReadAdvance to this processor if they don't exist. 2182 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef, 2183 unsigned PIdx) { 2184 RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs; 2185 if (is_contained(RADefs, ProcReadAdvanceDef)) 2186 return; 2187 RADefs.push_back(ProcReadAdvanceDef); 2188 } 2189 2190 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const { 2191 RecIter PRPos = find(ProcResourceDefs, PRDef); 2192 if (PRPos == ProcResourceDefs.end()) 2193 PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in " 2194 "the ProcResources list for " + ModelName); 2195 // Idx=0 is reserved for invalid. 2196 return 1 + (PRPos - ProcResourceDefs.begin()); 2197 } 2198 2199 bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const { 2200 for (const Record *TheDef : UnsupportedFeaturesDefs) { 2201 for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) { 2202 if (TheDef->getName() == PredDef->getName()) 2203 return true; 2204 } 2205 } 2206 return false; 2207 } 2208 2209 #ifndef NDEBUG 2210 void CodeGenProcModel::dump() const { 2211 dbgs() << Index << ": " << ModelName << " " 2212 << (ModelDef ? ModelDef->getName() : "inferred") << " " 2213 << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n'; 2214 } 2215 2216 void CodeGenSchedRW::dump() const { 2217 dbgs() << Name << (IsVariadic ? " (V) " : " "); 2218 if (IsSequence) { 2219 dbgs() << "("; 2220 dumpIdxVec(Sequence); 2221 dbgs() << ")"; 2222 } 2223 } 2224 2225 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const { 2226 dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n' 2227 << " Writes: "; 2228 for (unsigned i = 0, N = Writes.size(); i < N; ++i) { 2229 SchedModels->getSchedWrite(Writes[i]).dump(); 2230 if (i < N-1) { 2231 dbgs() << '\n'; 2232 dbgs().indent(10); 2233 } 2234 } 2235 dbgs() << "\n Reads: "; 2236 for (unsigned i = 0, N = Reads.size(); i < N; ++i) { 2237 SchedModels->getSchedRead(Reads[i]).dump(); 2238 if (i < N-1) { 2239 dbgs() << '\n'; 2240 dbgs().indent(10); 2241 } 2242 } 2243 dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); 2244 if (!Transitions.empty()) { 2245 dbgs() << "\n Transitions for Proc "; 2246 for (const CodeGenSchedTransition &Transition : Transitions) { 2247 dbgs() << Transition.ProcIndex << ", "; 2248 } 2249 } 2250 dbgs() << '\n'; 2251 } 2252 2253 void PredTransitions::dump() const { 2254 dbgs() << "Expanded Variants:\n"; 2255 for (const auto &TI : TransVec) { 2256 dbgs() << "{"; 2257 ListSeparator LS; 2258 for (const PredCheck &PC : TI.PredTerm) 2259 dbgs() << LS << SchedModels.getSchedRW(PC.RWIdx, PC.IsRead).Name << ":" 2260 << PC.Predicate->getName(); 2261 dbgs() << "},\n => {"; 2262 for (SmallVectorImpl<SmallVector<unsigned, 4>>::const_iterator 2263 WSI = TI.WriteSequences.begin(), 2264 WSE = TI.WriteSequences.end(); 2265 WSI != WSE; ++WSI) { 2266 dbgs() << "("; 2267 ListSeparator LS; 2268 for (unsigned N : *WSI) 2269 dbgs() << LS << SchedModels.getSchedWrite(N).Name; 2270 dbgs() << "),"; 2271 } 2272 dbgs() << "}\n"; 2273 } 2274 } 2275 #endif // NDEBUG 2276