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