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