1 //===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines structures to encapsulate the machine model as described in 11 // the target description. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "CodeGenSchedule.h" 16 #include "CodeGenTarget.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Support/Regex.h" 20 #include "llvm/TableGen/Error.h" 21 22 using namespace llvm; 23 24 #define DEBUG_TYPE "subtarget-emitter" 25 26 #ifndef NDEBUG 27 static void dumpIdxVec(ArrayRef<unsigned> V) { 28 for (unsigned Idx : V) 29 dbgs() << Idx << ", "; 30 } 31 #endif 32 33 namespace { 34 // (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp. 35 struct InstrsOp : public SetTheory::Operator { 36 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 37 ArrayRef<SMLoc> Loc) override { 38 ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc); 39 } 40 }; 41 42 // (instregex "OpcPat",...) Find all instructions matching an opcode pattern. 43 // 44 // TODO: Since this is a prefix match, perform a binary search over the 45 // instruction names using lower_bound. Note that the predefined instrs must be 46 // scanned linearly first. However, this is only safe if the regex pattern has 47 // no top-level bars. The DAG already has a list of patterns, so there's no 48 // reason to use top-level bars, but we need a way to verify they don't exist 49 // before implementing the optimization. 50 struct InstRegexOp : public SetTheory::Operator { 51 const CodeGenTarget &Target; 52 InstRegexOp(const CodeGenTarget &t): Target(t) {} 53 54 void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 55 ArrayRef<SMLoc> Loc) override { 56 SmallVector<Regex, 4> RegexList; 57 for (DagInit::const_arg_iterator 58 AI = Expr->arg_begin(), AE = Expr->arg_end(); AI != AE; ++AI) { 59 StringInit *SI = dyn_cast<StringInit>(*AI); 60 if (!SI) 61 PrintFatalError(Loc, "instregex requires pattern string: " 62 + Expr->getAsString()); 63 std::string pat = SI->getValue(); 64 // Implement a python-style prefix match. 65 if (pat[0] != '^') { 66 pat.insert(0, "^("); 67 pat.insert(pat.end(), ')'); 68 } 69 RegexList.push_back(Regex(pat)); 70 } 71 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 72 for (auto &R : RegexList) { 73 if (R.match(Inst->TheDef->getName())) 74 Elts.insert(Inst->TheDef); 75 } 76 } 77 } 78 }; 79 } // end anonymous namespace 80 81 /// CodeGenModels ctor interprets machine model records and populates maps. 82 CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK, 83 const CodeGenTarget &TGT): 84 Records(RK), Target(TGT) { 85 86 Sets.addFieldExpander("InstRW", "Instrs"); 87 88 // Allow Set evaluation to recognize the dags used in InstRW records: 89 // (instrs Op1, Op1...) 90 Sets.addOperator("instrs", llvm::make_unique<InstrsOp>()); 91 Sets.addOperator("instregex", llvm::make_unique<InstRegexOp>(Target)); 92 93 // Instantiate a CodeGenProcModel for each SchedMachineModel with the values 94 // that are explicitly referenced in tablegen records. Resources associated 95 // with each processor will be derived later. Populate ProcModelMap with the 96 // CodeGenProcModel instances. 97 collectProcModels(); 98 99 // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly 100 // defined, and populate SchedReads and SchedWrites vectors. Implicit 101 // SchedReadWrites that represent sequences derived from expanded variant will 102 // be inferred later. 103 collectSchedRW(); 104 105 // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly 106 // required by an instruction definition, and populate SchedClassIdxMap. Set 107 // NumItineraryClasses to the number of explicit itinerary classes referenced 108 // by instructions. Set NumInstrSchedClasses to the number of itinerary 109 // classes plus any classes implied by instructions that derive from class 110 // Sched and provide SchedRW list. This does not infer any new classes from 111 // SchedVariant. 112 collectSchedClasses(); 113 114 // Find instruction itineraries for each processor. Sort and populate 115 // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires 116 // all itinerary classes to be discovered. 117 collectProcItins(); 118 119 // Find ItinRW records for each processor and itinerary class. 120 // (For per-operand resources mapped to itinerary classes). 121 collectProcItinRW(); 122 123 // Find UnsupportedFeatures records for each processor. 124 // (For per-operand resources mapped to itinerary classes). 125 collectProcUnsupportedFeatures(); 126 127 // Infer new SchedClasses from SchedVariant. 128 inferSchedClasses(); 129 130 // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and 131 // ProcResourceDefs. 132 collectProcResources(); 133 134 checkCompleteness(); 135 } 136 137 /// Gather all processor models. 138 void CodeGenSchedModels::collectProcModels() { 139 RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor"); 140 std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName()); 141 142 // Reserve space because we can. Reallocation would be ok. 143 ProcModels.reserve(ProcRecords.size()+1); 144 145 // Use idx=0 for NoModel/NoItineraries. 146 Record *NoModelDef = Records.getDef("NoSchedModel"); 147 Record *NoItinsDef = Records.getDef("NoItineraries"); 148 ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef); 149 ProcModelMap[NoModelDef] = 0; 150 151 // For each processor, find a unique machine model. 152 for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i) 153 addProcModel(ProcRecords[i]); 154 } 155 156 /// Get a unique processor model based on the defined MachineModel and 157 /// ProcessorItineraries. 158 void CodeGenSchedModels::addProcModel(Record *ProcDef) { 159 Record *ModelKey = getModelOrItinDef(ProcDef); 160 if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second) 161 return; 162 163 std::string Name = ModelKey->getName(); 164 if (ModelKey->isSubClassOf("SchedMachineModel")) { 165 Record *ItinsDef = ModelKey->getValueAsDef("Itineraries"); 166 ProcModels.emplace_back(ProcModels.size(), Name, ModelKey, ItinsDef); 167 } 168 else { 169 // An itinerary is defined without a machine model. Infer a new model. 170 if (!ModelKey->getValueAsListOfDefs("IID").empty()) 171 Name = Name + "Model"; 172 ProcModels.emplace_back(ProcModels.size(), Name, 173 ProcDef->getValueAsDef("SchedModel"), ModelKey); 174 } 175 DEBUG(ProcModels.back().dump()); 176 } 177 178 // Recursively find all reachable SchedReadWrite records. 179 static void scanSchedRW(Record *RWDef, RecVec &RWDefs, 180 SmallPtrSet<Record*, 16> &RWSet) { 181 if (!RWSet.insert(RWDef).second) 182 return; 183 RWDefs.push_back(RWDef); 184 // Reads don't current have sequence records, but it can be added later. 185 if (RWDef->isSubClassOf("WriteSequence")) { 186 RecVec Seq = RWDef->getValueAsListOfDefs("Writes"); 187 for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I) 188 scanSchedRW(*I, RWDefs, RWSet); 189 } 190 else if (RWDef->isSubClassOf("SchedVariant")) { 191 // Visit each variant (guarded by a different predicate). 192 RecVec Vars = RWDef->getValueAsListOfDefs("Variants"); 193 for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) { 194 // Visit each RW in the sequence selected by the current variant. 195 RecVec Selected = (*VI)->getValueAsListOfDefs("Selected"); 196 for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I) 197 scanSchedRW(*I, RWDefs, RWSet); 198 } 199 } 200 } 201 202 // Collect and sort all SchedReadWrites reachable via tablegen records. 203 // More may be inferred later when inferring new SchedClasses from variants. 204 void CodeGenSchedModels::collectSchedRW() { 205 // Reserve idx=0 for invalid writes/reads. 206 SchedWrites.resize(1); 207 SchedReads.resize(1); 208 209 SmallPtrSet<Record*, 16> RWSet; 210 211 // Find all SchedReadWrites referenced by instruction defs. 212 RecVec SWDefs, SRDefs; 213 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 214 Record *SchedDef = Inst->TheDef; 215 if (SchedDef->isValueUnset("SchedRW")) 216 continue; 217 RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW"); 218 for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) { 219 if ((*RWI)->isSubClassOf("SchedWrite")) 220 scanSchedRW(*RWI, SWDefs, RWSet); 221 else { 222 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 223 scanSchedRW(*RWI, SRDefs, RWSet); 224 } 225 } 226 } 227 // Find all ReadWrites referenced by InstRW. 228 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 229 for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) { 230 // For all OperandReadWrites. 231 RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites"); 232 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 233 RWI != RWE; ++RWI) { 234 if ((*RWI)->isSubClassOf("SchedWrite")) 235 scanSchedRW(*RWI, SWDefs, RWSet); 236 else { 237 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 238 scanSchedRW(*RWI, SRDefs, RWSet); 239 } 240 } 241 } 242 // Find all ReadWrites referenced by ItinRW. 243 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 244 for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { 245 // For all OperandReadWrites. 246 RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites"); 247 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 248 RWI != RWE; ++RWI) { 249 if ((*RWI)->isSubClassOf("SchedWrite")) 250 scanSchedRW(*RWI, SWDefs, RWSet); 251 else { 252 assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 253 scanSchedRW(*RWI, SRDefs, RWSet); 254 } 255 } 256 } 257 // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted 258 // for the loop below that initializes Alias vectors. 259 RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias"); 260 std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord()); 261 for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) { 262 Record *MatchDef = (*AI)->getValueAsDef("MatchRW"); 263 Record *AliasDef = (*AI)->getValueAsDef("AliasRW"); 264 if (MatchDef->isSubClassOf("SchedWrite")) { 265 if (!AliasDef->isSubClassOf("SchedWrite")) 266 PrintFatalError((*AI)->getLoc(), "SchedWrite Alias must be SchedWrite"); 267 scanSchedRW(AliasDef, SWDefs, RWSet); 268 } 269 else { 270 assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 271 if (!AliasDef->isSubClassOf("SchedRead")) 272 PrintFatalError((*AI)->getLoc(), "SchedRead Alias must be SchedRead"); 273 scanSchedRW(AliasDef, SRDefs, RWSet); 274 } 275 } 276 // Sort and add the SchedReadWrites directly referenced by instructions or 277 // itinerary resources. Index reads and writes in separate domains. 278 std::sort(SWDefs.begin(), SWDefs.end(), LessRecord()); 279 for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) { 280 assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite"); 281 SchedWrites.emplace_back(SchedWrites.size(), *SWI); 282 } 283 std::sort(SRDefs.begin(), SRDefs.end(), LessRecord()); 284 for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) { 285 assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite"); 286 SchedReads.emplace_back(SchedReads.size(), *SRI); 287 } 288 // Initialize WriteSequence vectors. 289 for (std::vector<CodeGenSchedRW>::iterator WI = SchedWrites.begin(), 290 WE = SchedWrites.end(); WI != WE; ++WI) { 291 if (!WI->IsSequence) 292 continue; 293 findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence, 294 /*IsRead=*/false); 295 } 296 // Initialize Aliases vectors. 297 for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) { 298 Record *AliasDef = (*AI)->getValueAsDef("AliasRW"); 299 getSchedRW(AliasDef).IsAlias = true; 300 Record *MatchDef = (*AI)->getValueAsDef("MatchRW"); 301 CodeGenSchedRW &RW = getSchedRW(MatchDef); 302 if (RW.IsAlias) 303 PrintFatalError((*AI)->getLoc(), "Cannot Alias an Alias"); 304 RW.Aliases.push_back(*AI); 305 } 306 DEBUG( 307 for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) { 308 dbgs() << WIdx << ": "; 309 SchedWrites[WIdx].dump(); 310 dbgs() << '\n'; 311 } 312 for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) { 313 dbgs() << RIdx << ": "; 314 SchedReads[RIdx].dump(); 315 dbgs() << '\n'; 316 } 317 RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite"); 318 for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); 319 RI != RE; ++RI) { 320 if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) { 321 const std::string &Name = (*RI)->getName(); 322 if (Name != "NoWrite" && Name != "ReadDefault") 323 dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n'; 324 } 325 }); 326 } 327 328 /// Compute a SchedWrite name from a sequence of writes. 329 std::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) { 330 std::string Name("("); 331 for (auto I = Seq.begin(), E = Seq.end(); I != E; ++I) { 332 if (I != Seq.begin()) 333 Name += '_'; 334 Name += getSchedRW(*I, IsRead).Name; 335 } 336 Name += ')'; 337 return Name; 338 } 339 340 unsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead, 341 unsigned After) const { 342 const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 343 assert(After < RWVec.size() && "start position out of bounds"); 344 for (std::vector<CodeGenSchedRW>::const_iterator I = RWVec.begin() + After, 345 E = RWVec.end(); I != E; ++I) { 346 if (I->TheDef == Def) 347 return I - RWVec.begin(); 348 } 349 return 0; 350 } 351 352 bool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const { 353 for (unsigned i = 0, e = SchedReads.size(); i < e; ++i) { 354 Record *ReadDef = SchedReads[i].TheDef; 355 if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance")) 356 continue; 357 358 RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites"); 359 if (std::find(ValidWrites.begin(), ValidWrites.end(), WriteDef) 360 != ValidWrites.end()) { 361 return true; 362 } 363 } 364 return false; 365 } 366 367 namespace llvm { 368 void splitSchedReadWrites(const RecVec &RWDefs, 369 RecVec &WriteDefs, RecVec &ReadDefs) { 370 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) { 371 if ((*RWI)->isSubClassOf("SchedWrite")) 372 WriteDefs.push_back(*RWI); 373 else { 374 assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite"); 375 ReadDefs.push_back(*RWI); 376 } 377 } 378 } 379 } // namespace llvm 380 381 // Split the SchedReadWrites defs and call findRWs for each list. 382 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, 383 IdxVec &Writes, IdxVec &Reads) const { 384 RecVec WriteDefs; 385 RecVec ReadDefs; 386 splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs); 387 findRWs(WriteDefs, Writes, false); 388 findRWs(ReadDefs, Reads, true); 389 } 390 391 // Call getSchedRWIdx for all elements in a sequence of SchedRW defs. 392 void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs, 393 bool IsRead) const { 394 for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) { 395 unsigned Idx = getSchedRWIdx(*RI, IsRead); 396 assert(Idx && "failed to collect SchedReadWrite"); 397 RWs.push_back(Idx); 398 } 399 } 400 401 void CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, 402 bool IsRead) const { 403 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 404 if (!SchedRW.IsSequence) { 405 RWSeq.push_back(RWIdx); 406 return; 407 } 408 int Repeat = 409 SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1; 410 for (int i = 0; i < Repeat; ++i) { 411 for (IdxIter I = SchedRW.Sequence.begin(), E = SchedRW.Sequence.end(); 412 I != E; ++I) { 413 expandRWSequence(*I, RWSeq, IsRead); 414 } 415 } 416 } 417 418 // Expand a SchedWrite as a sequence following any aliases that coincide with 419 // the given processor model. 420 void CodeGenSchedModels::expandRWSeqForProc( 421 unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 422 const CodeGenProcModel &ProcModel) const { 423 424 const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead); 425 Record *AliasDef = nullptr; 426 for (RecIter AI = SchedWrite.Aliases.begin(), AE = SchedWrite.Aliases.end(); 427 AI != AE; ++AI) { 428 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 429 if ((*AI)->getValueInit("SchedModel")->isComplete()) { 430 Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 431 if (&getProcModel(ModelDef) != &ProcModel) 432 continue; 433 } 434 if (AliasDef) 435 PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases " 436 "defined for processor " + ProcModel.ModelName + 437 " Ensure only one SchedAlias exists per RW."); 438 AliasDef = AliasRW.TheDef; 439 } 440 if (AliasDef) { 441 expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead), 442 RWSeq, IsRead,ProcModel); 443 return; 444 } 445 if (!SchedWrite.IsSequence) { 446 RWSeq.push_back(RWIdx); 447 return; 448 } 449 int Repeat = 450 SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1; 451 for (int i = 0; i < Repeat; ++i) { 452 for (IdxIter I = SchedWrite.Sequence.begin(), E = SchedWrite.Sequence.end(); 453 I != E; ++I) { 454 expandRWSeqForProc(*I, RWSeq, IsRead, ProcModel); 455 } 456 } 457 } 458 459 // Find the existing SchedWrite that models this sequence of writes. 460 unsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq, 461 bool IsRead) { 462 std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 463 464 for (std::vector<CodeGenSchedRW>::iterator I = RWVec.begin(), E = RWVec.end(); 465 I != E; ++I) { 466 if (makeArrayRef(I->Sequence) == Seq) 467 return I - RWVec.begin(); 468 } 469 // Index zero reserved for invalid RW. 470 return 0; 471 } 472 473 /// Add this ReadWrite if it doesn't already exist. 474 unsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq, 475 bool IsRead) { 476 assert(!Seq.empty() && "cannot insert empty sequence"); 477 if (Seq.size() == 1) 478 return Seq.back(); 479 480 unsigned Idx = findRWForSequence(Seq, IsRead); 481 if (Idx) 482 return Idx; 483 484 unsigned RWIdx = IsRead ? SchedReads.size() : SchedWrites.size(); 485 CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead)); 486 if (IsRead) 487 SchedReads.push_back(SchedRW); 488 else 489 SchedWrites.push_back(SchedRW); 490 return RWIdx; 491 } 492 493 /// Visit all the instruction definitions for this target to gather and 494 /// enumerate the itinerary classes. These are the explicitly specified 495 /// SchedClasses. More SchedClasses may be inferred. 496 void CodeGenSchedModels::collectSchedClasses() { 497 498 // NoItinerary is always the first class at Idx=0 499 SchedClasses.resize(1); 500 SchedClasses.back().Index = 0; 501 SchedClasses.back().Name = "NoInstrModel"; 502 SchedClasses.back().ItinClassDef = Records.getDef("NoItinerary"); 503 SchedClasses.back().ProcIndices.push_back(0); 504 505 // Create a SchedClass for each unique combination of itinerary class and 506 // SchedRW list. 507 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 508 Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary"); 509 IdxVec Writes, Reads; 510 if (!Inst->TheDef->isValueUnset("SchedRW")) 511 findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); 512 513 // ProcIdx == 0 indicates the class applies to all processors. 514 IdxVec ProcIndices(1, 0); 515 516 unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, ProcIndices); 517 InstrClassMap[Inst->TheDef] = SCIdx; 518 } 519 // Create classes for InstRW defs. 520 RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 521 std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord()); 522 for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) 523 createInstRWClass(*OI); 524 525 NumInstrSchedClasses = SchedClasses.size(); 526 527 bool EnableDump = false; 528 DEBUG(EnableDump = true); 529 if (!EnableDump) 530 return; 531 532 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 533 std::string InstName = Inst->TheDef->getName(); 534 unsigned SCIdx = InstrClassMap.lookup(Inst->TheDef); 535 if (!SCIdx) { 536 if (!Inst->hasNoSchedulingInfo) 537 dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n'; 538 continue; 539 } 540 CodeGenSchedClass &SC = getSchedClass(SCIdx); 541 if (SC.ProcIndices[0] != 0) 542 PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class " 543 "must not be subtarget specific."); 544 545 IdxVec ProcIndices; 546 if (SC.ItinClassDef->getName() != "NoItinerary") { 547 ProcIndices.push_back(0); 548 dbgs() << "Itinerary for " << InstName << ": " 549 << SC.ItinClassDef->getName() << '\n'; 550 } 551 if (!SC.Writes.empty()) { 552 ProcIndices.push_back(0); 553 dbgs() << "SchedRW machine model for " << InstName; 554 for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE; ++WI) 555 dbgs() << " " << SchedWrites[*WI].Name; 556 for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI) 557 dbgs() << " " << SchedReads[*RI].Name; 558 dbgs() << '\n'; 559 } 560 const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs; 561 for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 562 RWI != RWE; ++RWI) { 563 const CodeGenProcModel &ProcModel = 564 getProcModel((*RWI)->getValueAsDef("SchedModel")); 565 ProcIndices.push_back(ProcModel.Index); 566 dbgs() << "InstRW on " << ProcModel.ModelName << " for " << InstName; 567 IdxVec Writes; 568 IdxVec Reads; 569 findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), 570 Writes, Reads); 571 for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI) 572 dbgs() << " " << SchedWrites[*WI].Name; 573 for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI) 574 dbgs() << " " << SchedReads[*RI].Name; 575 dbgs() << '\n'; 576 } 577 for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(), 578 PE = ProcModels.end(); PI != PE; ++PI) { 579 if (!std::count(ProcIndices.begin(), ProcIndices.end(), PI->Index)) 580 dbgs() << "No machine model for " << Inst->TheDef->getName() 581 << " on processor " << PI->ModelName << '\n'; 582 } 583 } 584 } 585 586 /// Find an SchedClass that has been inferred from a per-operand list of 587 /// SchedWrites and SchedReads. 588 unsigned CodeGenSchedModels::findSchedClassIdx(Record *ItinClassDef, 589 ArrayRef<unsigned> Writes, 590 ArrayRef<unsigned> Reads) const { 591 for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) { 592 if (I->ItinClassDef == ItinClassDef && makeArrayRef(I->Writes) == Writes && 593 makeArrayRef(I->Reads) == Reads) { 594 return I - schedClassBegin(); 595 } 596 } 597 return 0; 598 } 599 600 // Get the SchedClass index for an instruction. 601 unsigned CodeGenSchedModels::getSchedClassIdx( 602 const CodeGenInstruction &Inst) const { 603 604 return InstrClassMap.lookup(Inst.TheDef); 605 } 606 607 std::string 608 CodeGenSchedModels::createSchedClassName(Record *ItinClassDef, 609 ArrayRef<unsigned> OperWrites, 610 ArrayRef<unsigned> OperReads) { 611 612 std::string Name; 613 if (ItinClassDef && ItinClassDef->getName() != "NoItinerary") 614 Name = ItinClassDef->getName(); 615 for (unsigned Idx : OperWrites) { 616 if (!Name.empty()) 617 Name += '_'; 618 Name += SchedWrites[Idx].Name; 619 } 620 for (unsigned Idx : OperReads) { 621 Name += '_'; 622 Name += SchedReads[Idx].Name; 623 } 624 return Name; 625 } 626 627 std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { 628 629 std::string Name; 630 for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) { 631 if (I != InstDefs.begin()) 632 Name += '_'; 633 Name += (*I)->getName(); 634 } 635 return Name; 636 } 637 638 /// Add an inferred sched class from an itinerary class and per-operand list of 639 /// SchedWrites and SchedReads. ProcIndices contains the set of IDs of 640 /// processors that may utilize this class. 641 unsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef, 642 ArrayRef<unsigned> OperWrites, 643 ArrayRef<unsigned> OperReads, 644 ArrayRef<unsigned> ProcIndices) { 645 assert(!ProcIndices.empty() && "expect at least one ProcIdx"); 646 647 unsigned Idx = findSchedClassIdx(ItinClassDef, OperWrites, OperReads); 648 if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) { 649 IdxVec PI; 650 std::set_union(SchedClasses[Idx].ProcIndices.begin(), 651 SchedClasses[Idx].ProcIndices.end(), 652 ProcIndices.begin(), ProcIndices.end(), 653 std::back_inserter(PI)); 654 SchedClasses[Idx].ProcIndices.swap(PI); 655 return Idx; 656 } 657 Idx = SchedClasses.size(); 658 SchedClasses.resize(Idx+1); 659 CodeGenSchedClass &SC = SchedClasses.back(); 660 SC.Index = Idx; 661 SC.Name = createSchedClassName(ItinClassDef, OperWrites, OperReads); 662 SC.ItinClassDef = ItinClassDef; 663 SC.Writes = OperWrites; 664 SC.Reads = OperReads; 665 SC.ProcIndices = ProcIndices; 666 667 return Idx; 668 } 669 670 // Create classes for each set of opcodes that are in the same InstReadWrite 671 // definition across all processors. 672 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { 673 // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that 674 // intersects with an existing class via a previous InstRWDef. Instrs that do 675 // not intersect with an existing class refer back to their former class as 676 // determined from ItinDef or SchedRW. 677 SmallVector<std::pair<unsigned, SmallVector<Record *, 8> >, 4> ClassInstrs; 678 // Sort Instrs into sets. 679 const RecVec *InstDefs = Sets.expand(InstRWDef); 680 if (InstDefs->empty()) 681 PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes"); 682 683 for (RecIter I = InstDefs->begin(), E = InstDefs->end(); I != E; ++I) { 684 InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I); 685 if (Pos == InstrClassMap.end()) 686 PrintFatalError((*I)->getLoc(), "No sched class for instruction."); 687 unsigned SCIdx = Pos->second; 688 unsigned CIdx = 0, CEnd = ClassInstrs.size(); 689 for (; CIdx != CEnd; ++CIdx) { 690 if (ClassInstrs[CIdx].first == SCIdx) 691 break; 692 } 693 if (CIdx == CEnd) { 694 ClassInstrs.resize(CEnd + 1); 695 ClassInstrs[CIdx].first = SCIdx; 696 } 697 ClassInstrs[CIdx].second.push_back(*I); 698 } 699 // For each set of Instrs, create a new class if necessary, and map or remap 700 // the Instrs to it. 701 unsigned CIdx = 0, CEnd = ClassInstrs.size(); 702 for (; CIdx != CEnd; ++CIdx) { 703 unsigned OldSCIdx = ClassInstrs[CIdx].first; 704 ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second; 705 // If the all instrs in the current class are accounted for, then leave 706 // them mapped to their old class. 707 if (OldSCIdx) { 708 const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs; 709 if (!RWDefs.empty()) { 710 const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]); 711 unsigned OrigNumInstrs = 0; 712 for (RecIter I = OrigInstDefs->begin(), E = OrigInstDefs->end(); 713 I != E; ++I) { 714 if (InstrClassMap[*I] == OldSCIdx) 715 ++OrigNumInstrs; 716 } 717 if (OrigNumInstrs == InstDefs.size()) { 718 assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 && 719 "expected a generic SchedClass"); 720 DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":" 721 << SchedClasses[OldSCIdx].Name << " on " 722 << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n"); 723 SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef); 724 continue; 725 } 726 } 727 } 728 unsigned SCIdx = SchedClasses.size(); 729 SchedClasses.resize(SCIdx+1); 730 CodeGenSchedClass &SC = SchedClasses.back(); 731 SC.Index = SCIdx; 732 SC.Name = createSchedClassName(InstDefs); 733 DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on " 734 << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n"); 735 736 // Preserve ItinDef and Writes/Reads for processors without an InstRW entry. 737 SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef; 738 SC.Writes = SchedClasses[OldSCIdx].Writes; 739 SC.Reads = SchedClasses[OldSCIdx].Reads; 740 SC.ProcIndices.push_back(0); 741 // Map each Instr to this new class. 742 // Note that InstDefs may be a smaller list than InstRWDef's "Instrs". 743 Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 744 SmallSet<unsigned, 4> RemappedClassIDs; 745 for (ArrayRef<Record*>::const_iterator 746 II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) { 747 unsigned OldSCIdx = InstrClassMap[*II]; 748 if (OldSCIdx && RemappedClassIDs.insert(OldSCIdx).second) { 749 for (RecIter RI = SchedClasses[OldSCIdx].InstRWs.begin(), 750 RE = SchedClasses[OldSCIdx].InstRWs.end(); RI != RE; ++RI) { 751 if ((*RI)->getValueAsDef("SchedModel") == RWModelDef) { 752 PrintFatalError(InstRWDef->getLoc(), "Overlapping InstRW def " + 753 (*II)->getName() + " also matches " + 754 (*RI)->getValue("Instrs")->getValue()->getAsString()); 755 } 756 assert(*RI != InstRWDef && "SchedClass has duplicate InstRW def"); 757 SC.InstRWs.push_back(*RI); 758 } 759 } 760 InstrClassMap[*II] = SCIdx; 761 } 762 SC.InstRWs.push_back(InstRWDef); 763 } 764 } 765 766 // True if collectProcItins found anything. 767 bool CodeGenSchedModels::hasItineraries() const { 768 for (CodeGenSchedModels::ProcIter PI = procModelBegin(), PE = procModelEnd(); 769 PI != PE; ++PI) { 770 if (PI->hasItineraries()) 771 return true; 772 } 773 return false; 774 } 775 776 // Gather the processor itineraries. 777 void CodeGenSchedModels::collectProcItins() { 778 for (CodeGenProcModel &ProcModel : ProcModels) { 779 if (!ProcModel.hasItineraries()) 780 continue; 781 782 RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID"); 783 assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect"); 784 785 // Populate ItinDefList with Itinerary records. 786 ProcModel.ItinDefList.resize(NumInstrSchedClasses); 787 788 // Insert each itinerary data record in the correct position within 789 // the processor model's ItinDefList. 790 for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) { 791 Record *ItinData = ItinRecords[i]; 792 Record *ItinDef = ItinData->getValueAsDef("TheClass"); 793 bool FoundClass = false; 794 for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd(); 795 SCI != SCE; ++SCI) { 796 // Multiple SchedClasses may share an itinerary. Update all of them. 797 if (SCI->ItinClassDef == ItinDef) { 798 ProcModel.ItinDefList[SCI->Index] = ItinData; 799 FoundClass = true; 800 } 801 } 802 if (!FoundClass) { 803 DEBUG(dbgs() << ProcModel.ItinsDef->getName() 804 << " missing class for itinerary " << ItinDef->getName() << '\n'); 805 } 806 } 807 // Check for missing itinerary entries. 808 assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); 809 DEBUG( 810 for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { 811 if (!ProcModel.ItinDefList[i]) 812 dbgs() << ProcModel.ItinsDef->getName() 813 << " missing itinerary for class " 814 << SchedClasses[i].Name << '\n'; 815 }); 816 } 817 } 818 819 // Gather the read/write types for each itinerary class. 820 void CodeGenSchedModels::collectProcItinRW() { 821 RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 822 std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord()); 823 for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { 824 if (!(*II)->getValueInit("SchedModel")->isComplete()) 825 PrintFatalError((*II)->getLoc(), "SchedModel is undefined"); 826 Record *ModelDef = (*II)->getValueAsDef("SchedModel"); 827 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 828 if (I == ProcModelMap.end()) { 829 PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel " 830 + ModelDef->getName()); 831 } 832 ProcModels[I->second].ItinRWDefs.push_back(*II); 833 } 834 } 835 836 // Gather the unsupported features for processor models. 837 void CodeGenSchedModels::collectProcUnsupportedFeatures() { 838 for (CodeGenProcModel &ProcModel : ProcModels) { 839 for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) { 840 ProcModel.UnsupportedFeaturesDefs.push_back(Pred); 841 } 842 } 843 } 844 845 /// Infer new classes from existing classes. In the process, this may create new 846 /// SchedWrites from sequences of existing SchedWrites. 847 void CodeGenSchedModels::inferSchedClasses() { 848 DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n"); 849 850 // Visit all existing classes and newly created classes. 851 for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) { 852 assert(SchedClasses[Idx].Index == Idx && "bad SCIdx"); 853 854 if (SchedClasses[Idx].ItinClassDef) 855 inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx); 856 if (!SchedClasses[Idx].InstRWs.empty()) 857 inferFromInstRWs(Idx); 858 if (!SchedClasses[Idx].Writes.empty()) { 859 inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads, 860 Idx, SchedClasses[Idx].ProcIndices); 861 } 862 assert(SchedClasses.size() < (NumInstrSchedClasses*6) && 863 "too many SchedVariants"); 864 } 865 } 866 867 /// Infer classes from per-processor itinerary resources. 868 void CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef, 869 unsigned FromClassIdx) { 870 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 871 const CodeGenProcModel &PM = ProcModels[PIdx]; 872 // For all ItinRW entries. 873 bool HasMatch = false; 874 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 875 II != IE; ++II) { 876 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 877 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 878 continue; 879 if (HasMatch) 880 PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 881 + ItinClassDef->getName() 882 + " in ItinResources for " + PM.ModelName); 883 HasMatch = true; 884 IdxVec Writes, Reads; 885 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 886 IdxVec ProcIndices(1, PIdx); 887 inferFromRW(Writes, Reads, FromClassIdx, ProcIndices); 888 } 889 } 890 } 891 892 /// Infer classes from per-processor InstReadWrite definitions. 893 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) { 894 for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) { 895 assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!"); 896 Record *Rec = SchedClasses[SCIdx].InstRWs[I]; 897 const RecVec *InstDefs = Sets.expand(Rec); 898 RecIter II = InstDefs->begin(), IE = InstDefs->end(); 899 for (; II != IE; ++II) { 900 if (InstrClassMap[*II] == SCIdx) 901 break; 902 } 903 // If this class no longer has any instructions mapped to it, it has become 904 // irrelevant. 905 if (II == IE) 906 continue; 907 IdxVec Writes, Reads; 908 findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 909 unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index; 910 IdxVec ProcIndices(1, PIdx); 911 inferFromRW(Writes, Reads, SCIdx, ProcIndices); // May mutate SchedClasses. 912 } 913 } 914 915 namespace { 916 // Helper for substituteVariantOperand. 917 struct TransVariant { 918 Record *VarOrSeqDef; // Variant or sequence. 919 unsigned RWIdx; // Index of this variant or sequence's matched type. 920 unsigned ProcIdx; // Processor model index or zero for any. 921 unsigned TransVecIdx; // Index into PredTransitions::TransVec. 922 923 TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti): 924 VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {} 925 }; 926 927 // Associate a predicate with the SchedReadWrite that it guards. 928 // RWIdx is the index of the read/write variant. 929 struct PredCheck { 930 bool IsRead; 931 unsigned RWIdx; 932 Record *Predicate; 933 934 PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {} 935 }; 936 937 // A Predicate transition is a list of RW sequences guarded by a PredTerm. 938 struct PredTransition { 939 // A predicate term is a conjunction of PredChecks. 940 SmallVector<PredCheck, 4> PredTerm; 941 SmallVector<SmallVector<unsigned,4>, 16> WriteSequences; 942 SmallVector<SmallVector<unsigned,4>, 16> ReadSequences; 943 SmallVector<unsigned, 4> ProcIndices; 944 }; 945 946 // Encapsulate a set of partially constructed transitions. 947 // The results are built by repeated calls to substituteVariants. 948 class PredTransitions { 949 CodeGenSchedModels &SchedModels; 950 951 public: 952 std::vector<PredTransition> TransVec; 953 954 PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {} 955 956 void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq, 957 bool IsRead, unsigned StartIdx); 958 959 void substituteVariants(const PredTransition &Trans); 960 961 #ifndef NDEBUG 962 void dump() const; 963 #endif 964 965 private: 966 bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term); 967 void getIntersectingVariants( 968 const CodeGenSchedRW &SchedRW, unsigned TransIdx, 969 std::vector<TransVariant> &IntersectingVariants); 970 void pushVariant(const TransVariant &VInfo, bool IsRead); 971 }; 972 } // anonymous 973 974 // Return true if this predicate is mutually exclusive with a PredTerm. This 975 // degenerates into checking if the predicate is mutually exclusive with any 976 // predicate in the Term's conjunction. 977 // 978 // All predicates associated with a given SchedRW are considered mutually 979 // exclusive. This should work even if the conditions expressed by the 980 // predicates are not exclusive because the predicates for a given SchedWrite 981 // are always checked in the order they are defined in the .td file. Later 982 // conditions implicitly negate any prior condition. 983 bool PredTransitions::mutuallyExclusive(Record *PredDef, 984 ArrayRef<PredCheck> Term) { 985 986 for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end(); 987 I != E; ++I) { 988 if (I->Predicate == PredDef) 989 return false; 990 991 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead); 992 assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant"); 993 RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 994 for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) { 995 if ((*VI)->getValueAsDef("Predicate") == PredDef) 996 return true; 997 } 998 } 999 return false; 1000 } 1001 1002 static bool hasAliasedVariants(const CodeGenSchedRW &RW, 1003 CodeGenSchedModels &SchedModels) { 1004 if (RW.HasVariants) 1005 return true; 1006 1007 for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) { 1008 const CodeGenSchedRW &AliasRW = 1009 SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW")); 1010 if (AliasRW.HasVariants) 1011 return true; 1012 if (AliasRW.IsSequence) { 1013 IdxVec ExpandedRWs; 1014 SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead); 1015 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 1016 SI != SE; ++SI) { 1017 if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead), 1018 SchedModels)) { 1019 return true; 1020 } 1021 } 1022 } 1023 } 1024 return false; 1025 } 1026 1027 static bool hasVariant(ArrayRef<PredTransition> Transitions, 1028 CodeGenSchedModels &SchedModels) { 1029 for (ArrayRef<PredTransition>::iterator 1030 PTI = Transitions.begin(), PTE = Transitions.end(); 1031 PTI != PTE; ++PTI) { 1032 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1033 WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end(); 1034 WSI != WSE; ++WSI) { 1035 for (SmallVectorImpl<unsigned>::const_iterator 1036 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 1037 if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels)) 1038 return true; 1039 } 1040 } 1041 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1042 RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end(); 1043 RSI != RSE; ++RSI) { 1044 for (SmallVectorImpl<unsigned>::const_iterator 1045 RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) { 1046 if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels)) 1047 return true; 1048 } 1049 } 1050 } 1051 return false; 1052 } 1053 1054 // Populate IntersectingVariants with any variants or aliased sequences of the 1055 // given SchedRW whose processor indices and predicates are not mutually 1056 // exclusive with the given transition. 1057 void PredTransitions::getIntersectingVariants( 1058 const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1059 std::vector<TransVariant> &IntersectingVariants) { 1060 1061 bool GenericRW = false; 1062 1063 std::vector<TransVariant> Variants; 1064 if (SchedRW.HasVariants) { 1065 unsigned VarProcIdx = 0; 1066 if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) { 1067 Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel"); 1068 VarProcIdx = SchedModels.getProcModel(ModelDef).Index; 1069 } 1070 // Push each variant. Assign TransVecIdx later. 1071 const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1072 for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI) 1073 Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0)); 1074 if (VarProcIdx == 0) 1075 GenericRW = true; 1076 } 1077 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1078 AI != AE; ++AI) { 1079 // If either the SchedAlias itself or the SchedReadWrite that it aliases 1080 // to is defined within a processor model, constrain all variants to 1081 // that processor. 1082 unsigned AliasProcIdx = 0; 1083 if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1084 Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 1085 AliasProcIdx = SchedModels.getProcModel(ModelDef).Index; 1086 } 1087 const CodeGenSchedRW &AliasRW = 1088 SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW")); 1089 1090 if (AliasRW.HasVariants) { 1091 const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants"); 1092 for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI) 1093 Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0)); 1094 } 1095 if (AliasRW.IsSequence) { 1096 Variants.push_back( 1097 TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0)); 1098 } 1099 if (AliasProcIdx == 0) 1100 GenericRW = true; 1101 } 1102 for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) { 1103 TransVariant &Variant = Variants[VIdx]; 1104 // Don't expand variants if the processor models don't intersect. 1105 // A zero processor index means any processor. 1106 SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices; 1107 if (ProcIndices[0] && Variants[VIdx].ProcIdx) { 1108 unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(), 1109 Variant.ProcIdx); 1110 if (!Cnt) 1111 continue; 1112 if (Cnt > 1) { 1113 const CodeGenProcModel &PM = 1114 *(SchedModels.procModelBegin() + Variant.ProcIdx); 1115 PrintFatalError(Variant.VarOrSeqDef->getLoc(), 1116 "Multiple variants defined for processor " + 1117 PM.ModelName + 1118 " Ensure only one SchedAlias exists per RW."); 1119 } 1120 } 1121 if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) { 1122 Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate"); 1123 if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm)) 1124 continue; 1125 } 1126 if (IntersectingVariants.empty()) { 1127 // The first variant builds on the existing transition. 1128 Variant.TransVecIdx = TransIdx; 1129 IntersectingVariants.push_back(Variant); 1130 } 1131 else { 1132 // Push another copy of the current transition for more variants. 1133 Variant.TransVecIdx = TransVec.size(); 1134 IntersectingVariants.push_back(Variant); 1135 TransVec.push_back(TransVec[TransIdx]); 1136 } 1137 } 1138 if (GenericRW && IntersectingVariants.empty()) { 1139 PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has " 1140 "a matching predicate on any processor"); 1141 } 1142 } 1143 1144 // Push the Reads/Writes selected by this variant onto the PredTransition 1145 // specified by VInfo. 1146 void PredTransitions:: 1147 pushVariant(const TransVariant &VInfo, bool IsRead) { 1148 1149 PredTransition &Trans = TransVec[VInfo.TransVecIdx]; 1150 1151 // If this operand transition is reached through a processor-specific alias, 1152 // then the whole transition is specific to this processor. 1153 if (VInfo.ProcIdx != 0) 1154 Trans.ProcIndices.assign(1, VInfo.ProcIdx); 1155 1156 IdxVec SelectedRWs; 1157 if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) { 1158 Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate"); 1159 Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef)); 1160 RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected"); 1161 SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead); 1162 } 1163 else { 1164 assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") && 1165 "variant must be a SchedVariant or aliased WriteSequence"); 1166 SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead)); 1167 } 1168 1169 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead); 1170 1171 SmallVectorImpl<SmallVector<unsigned,4> > &RWSequences = IsRead 1172 ? Trans.ReadSequences : Trans.WriteSequences; 1173 if (SchedRW.IsVariadic) { 1174 unsigned OperIdx = RWSequences.size()-1; 1175 // Make N-1 copies of this transition's last sequence. 1176 for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) { 1177 // Create a temporary copy the vector could reallocate. 1178 RWSequences.reserve(RWSequences.size() + 1); 1179 RWSequences.push_back(RWSequences[OperIdx]); 1180 } 1181 // Push each of the N elements of the SelectedRWs onto a copy of the last 1182 // sequence (split the current operand into N operands). 1183 // Note that write sequences should be expanded within this loop--the entire 1184 // sequence belongs to a single operand. 1185 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1186 RWI != RWE; ++RWI, ++OperIdx) { 1187 IdxVec ExpandedRWs; 1188 if (IsRead) 1189 ExpandedRWs.push_back(*RWI); 1190 else 1191 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1192 RWSequences[OperIdx].insert(RWSequences[OperIdx].end(), 1193 ExpandedRWs.begin(), ExpandedRWs.end()); 1194 } 1195 assert(OperIdx == RWSequences.size() && "missed a sequence"); 1196 } 1197 else { 1198 // Push this transition's expanded sequence onto this transition's last 1199 // sequence (add to the current operand's sequence). 1200 SmallVectorImpl<unsigned> &Seq = RWSequences.back(); 1201 IdxVec ExpandedRWs; 1202 for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1203 RWI != RWE; ++RWI) { 1204 if (IsRead) 1205 ExpandedRWs.push_back(*RWI); 1206 else 1207 SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1208 } 1209 Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end()); 1210 } 1211 } 1212 1213 // RWSeq is a sequence of all Reads or all Writes for the next read or write 1214 // operand. StartIdx is an index into TransVec where partial results 1215 // starts. RWSeq must be applied to all transitions between StartIdx and the end 1216 // of TransVec. 1217 void PredTransitions::substituteVariantOperand( 1218 const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) { 1219 1220 // Visit each original RW within the current sequence. 1221 for (SmallVectorImpl<unsigned>::const_iterator 1222 RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) { 1223 const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead); 1224 // Push this RW on all partial PredTransitions or distribute variants. 1225 // New PredTransitions may be pushed within this loop which should not be 1226 // revisited (TransEnd must be loop invariant). 1227 for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size(); 1228 TransIdx != TransEnd; ++TransIdx) { 1229 // In the common case, push RW onto the current operand's sequence. 1230 if (!hasAliasedVariants(SchedRW, SchedModels)) { 1231 if (IsRead) 1232 TransVec[TransIdx].ReadSequences.back().push_back(*RWI); 1233 else 1234 TransVec[TransIdx].WriteSequences.back().push_back(*RWI); 1235 continue; 1236 } 1237 // Distribute this partial PredTransition across intersecting variants. 1238 // This will push a copies of TransVec[TransIdx] on the back of TransVec. 1239 std::vector<TransVariant> IntersectingVariants; 1240 getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants); 1241 // Now expand each variant on top of its copy of the transition. 1242 for (std::vector<TransVariant>::const_iterator 1243 IVI = IntersectingVariants.begin(), 1244 IVE = IntersectingVariants.end(); 1245 IVI != IVE; ++IVI) { 1246 pushVariant(*IVI, IsRead); 1247 } 1248 } 1249 } 1250 } 1251 1252 // For each variant of a Read/Write in Trans, substitute the sequence of 1253 // Read/Writes guarded by the variant. This is exponential in the number of 1254 // variant Read/Writes, but in practice detection of mutually exclusive 1255 // predicates should result in linear growth in the total number variants. 1256 // 1257 // This is one step in a breadth-first search of nested variants. 1258 void PredTransitions::substituteVariants(const PredTransition &Trans) { 1259 // Build up a set of partial results starting at the back of 1260 // PredTransitions. Remember the first new transition. 1261 unsigned StartIdx = TransVec.size(); 1262 TransVec.resize(TransVec.size() + 1); 1263 TransVec.back().PredTerm = Trans.PredTerm; 1264 TransVec.back().ProcIndices = Trans.ProcIndices; 1265 1266 // Visit each original write sequence. 1267 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1268 WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end(); 1269 WSI != WSE; ++WSI) { 1270 // Push a new (empty) write sequence onto all partial Transitions. 1271 for (std::vector<PredTransition>::iterator I = 1272 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1273 I->WriteSequences.resize(I->WriteSequences.size() + 1); 1274 } 1275 substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx); 1276 } 1277 // Visit each original read sequence. 1278 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1279 RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end(); 1280 RSI != RSE; ++RSI) { 1281 // Push a new (empty) read sequence onto all partial Transitions. 1282 for (std::vector<PredTransition>::iterator I = 1283 TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1284 I->ReadSequences.resize(I->ReadSequences.size() + 1); 1285 } 1286 substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx); 1287 } 1288 } 1289 1290 // Create a new SchedClass for each variant found by inferFromRW. Pass 1291 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions, 1292 unsigned FromClassIdx, 1293 CodeGenSchedModels &SchedModels) { 1294 // For each PredTransition, create a new CodeGenSchedTransition, which usually 1295 // requires creating a new SchedClass. 1296 for (ArrayRef<PredTransition>::iterator 1297 I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) { 1298 IdxVec OperWritesVariant; 1299 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1300 WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end(); 1301 WSI != WSE; ++WSI) { 1302 // Create a new write representing the expanded sequence. 1303 OperWritesVariant.push_back( 1304 SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false)); 1305 } 1306 IdxVec OperReadsVariant; 1307 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1308 RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end(); 1309 RSI != RSE; ++RSI) { 1310 // Create a new read representing the expanded sequence. 1311 OperReadsVariant.push_back( 1312 SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true)); 1313 } 1314 IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end()); 1315 CodeGenSchedTransition SCTrans; 1316 SCTrans.ToClassIdx = 1317 SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant, 1318 OperReadsVariant, ProcIndices); 1319 SCTrans.ProcIndices = ProcIndices; 1320 // The final PredTerm is unique set of predicates guarding the transition. 1321 RecVec Preds; 1322 for (SmallVectorImpl<PredCheck>::const_iterator 1323 PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) { 1324 Preds.push_back(PI->Predicate); 1325 } 1326 RecIter PredsEnd = std::unique(Preds.begin(), Preds.end()); 1327 Preds.resize(PredsEnd - Preds.begin()); 1328 SCTrans.PredTerm = Preds; 1329 SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans); 1330 } 1331 } 1332 1333 // Create new SchedClasses for the given ReadWrite list. If any of the 1334 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant 1335 // of the ReadWrite list, following Aliases if necessary. 1336 void CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites, 1337 ArrayRef<unsigned> OperReads, 1338 unsigned FromClassIdx, 1339 ArrayRef<unsigned> ProcIndices) { 1340 DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); dbgs() << ") "); 1341 1342 // Create a seed transition with an empty PredTerm and the expanded sequences 1343 // of SchedWrites for the current SchedClass. 1344 std::vector<PredTransition> LastTransitions; 1345 LastTransitions.resize(1); 1346 LastTransitions.back().ProcIndices.append(ProcIndices.begin(), 1347 ProcIndices.end()); 1348 1349 for (unsigned WriteIdx : OperWrites) { 1350 IdxVec WriteSeq; 1351 expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false); 1352 unsigned Idx = LastTransitions[0].WriteSequences.size(); 1353 LastTransitions[0].WriteSequences.resize(Idx + 1); 1354 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx]; 1355 for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI) 1356 Seq.push_back(*WI); 1357 DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1358 } 1359 DEBUG(dbgs() << " Reads: "); 1360 for (unsigned ReadIdx : OperReads) { 1361 IdxVec ReadSeq; 1362 expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true); 1363 unsigned Idx = LastTransitions[0].ReadSequences.size(); 1364 LastTransitions[0].ReadSequences.resize(Idx + 1); 1365 SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx]; 1366 for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI) 1367 Seq.push_back(*RI); 1368 DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1369 } 1370 DEBUG(dbgs() << '\n'); 1371 1372 // Collect all PredTransitions for individual operands. 1373 // Iterate until no variant writes remain. 1374 while (hasVariant(LastTransitions, *this)) { 1375 PredTransitions Transitions(*this); 1376 for (std::vector<PredTransition>::const_iterator 1377 I = LastTransitions.begin(), E = LastTransitions.end(); 1378 I != E; ++I) { 1379 Transitions.substituteVariants(*I); 1380 } 1381 DEBUG(Transitions.dump()); 1382 LastTransitions.swap(Transitions.TransVec); 1383 } 1384 // If the first transition has no variants, nothing to do. 1385 if (LastTransitions[0].PredTerm.empty()) 1386 return; 1387 1388 // WARNING: We are about to mutate the SchedClasses vector. Do not refer to 1389 // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions. 1390 inferFromTransitions(LastTransitions, FromClassIdx, *this); 1391 } 1392 1393 // Check if any processor resource group contains all resource records in 1394 // SubUnits. 1395 bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) { 1396 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1397 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1398 continue; 1399 RecVec SuperUnits = 1400 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1401 RecIter RI = SubUnits.begin(), RE = SubUnits.end(); 1402 for ( ; RI != RE; ++RI) { 1403 if (std::find(SuperUnits.begin(), SuperUnits.end(), *RI) 1404 == SuperUnits.end()) { 1405 break; 1406 } 1407 } 1408 if (RI == RE) 1409 return true; 1410 } 1411 return false; 1412 } 1413 1414 // Verify that overlapping groups have a common supergroup. 1415 void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) { 1416 for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1417 if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1418 continue; 1419 RecVec CheckUnits = 1420 PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1421 for (unsigned j = i+1; j < e; ++j) { 1422 if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup")) 1423 continue; 1424 RecVec OtherUnits = 1425 PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources"); 1426 if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(), 1427 OtherUnits.begin(), OtherUnits.end()) 1428 != CheckUnits.end()) { 1429 // CheckUnits and OtherUnits overlap 1430 OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(), 1431 CheckUnits.end()); 1432 if (!hasSuperGroup(OtherUnits, PM)) { 1433 PrintFatalError((PM.ProcResourceDefs[i])->getLoc(), 1434 "proc resource group overlaps with " 1435 + PM.ProcResourceDefs[j]->getName() 1436 + " but no supergroup contains both."); 1437 } 1438 } 1439 } 1440 } 1441 } 1442 1443 // Collect and sort WriteRes, ReadAdvance, and ProcResources. 1444 void CodeGenSchedModels::collectProcResources() { 1445 ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits"); 1446 ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1447 1448 // Add any subtarget-specific SchedReadWrites that are directly associated 1449 // with processor resources. Refer to the parent SchedClass's ProcIndices to 1450 // determine which processors they apply to. 1451 for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd(); 1452 SCI != SCE; ++SCI) { 1453 if (SCI->ItinClassDef) 1454 collectItinProcResources(SCI->ItinClassDef); 1455 else { 1456 // This class may have a default ReadWrite list which can be overriden by 1457 // InstRW definitions. 1458 if (!SCI->InstRWs.empty()) { 1459 for (RecIter RWI = SCI->InstRWs.begin(), RWE = SCI->InstRWs.end(); 1460 RWI != RWE; ++RWI) { 1461 Record *RWModelDef = (*RWI)->getValueAsDef("SchedModel"); 1462 IdxVec ProcIndices(1, getProcModel(RWModelDef).Index); 1463 IdxVec Writes, Reads; 1464 findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), 1465 Writes, Reads); 1466 collectRWResources(Writes, Reads, ProcIndices); 1467 } 1468 } 1469 collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices); 1470 } 1471 } 1472 // Add resources separately defined by each subtarget. 1473 RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes"); 1474 for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) { 1475 Record *ModelDef = (*WRI)->getValueAsDef("SchedModel"); 1476 addWriteRes(*WRI, getProcModel(ModelDef).Index); 1477 } 1478 RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes"); 1479 for (RecIter WRI = SWRDefs.begin(), WRE = SWRDefs.end(); WRI != WRE; ++WRI) { 1480 Record *ModelDef = (*WRI)->getValueAsDef("SchedModel"); 1481 addWriteRes(*WRI, getProcModel(ModelDef).Index); 1482 } 1483 RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance"); 1484 for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) { 1485 Record *ModelDef = (*RAI)->getValueAsDef("SchedModel"); 1486 addReadAdvance(*RAI, getProcModel(ModelDef).Index); 1487 } 1488 RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance"); 1489 for (RecIter RAI = SRADefs.begin(), RAE = SRADefs.end(); RAI != RAE; ++RAI) { 1490 if ((*RAI)->getValueInit("SchedModel")->isComplete()) { 1491 Record *ModelDef = (*RAI)->getValueAsDef("SchedModel"); 1492 addReadAdvance(*RAI, getProcModel(ModelDef).Index); 1493 } 1494 } 1495 // Add ProcResGroups that are defined within this processor model, which may 1496 // not be directly referenced but may directly specify a buffer size. 1497 RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1498 for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end(); 1499 RI != RE; ++RI) { 1500 if (!(*RI)->getValueInit("SchedModel")->isComplete()) 1501 continue; 1502 CodeGenProcModel &PM = getProcModel((*RI)->getValueAsDef("SchedModel")); 1503 RecIter I = std::find(PM.ProcResourceDefs.begin(), 1504 PM.ProcResourceDefs.end(), *RI); 1505 if (I == PM.ProcResourceDefs.end()) 1506 PM.ProcResourceDefs.push_back(*RI); 1507 } 1508 // Finalize each ProcModel by sorting the record arrays. 1509 for (CodeGenProcModel &PM : ProcModels) { 1510 std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(), 1511 LessRecord()); 1512 std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(), 1513 LessRecord()); 1514 std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(), 1515 LessRecord()); 1516 DEBUG( 1517 PM.dump(); 1518 dbgs() << "WriteResDefs: "; 1519 for (RecIter RI = PM.WriteResDefs.begin(), 1520 RE = PM.WriteResDefs.end(); RI != RE; ++RI) { 1521 if ((*RI)->isSubClassOf("WriteRes")) 1522 dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " "; 1523 else 1524 dbgs() << (*RI)->getName() << " "; 1525 } 1526 dbgs() << "\nReadAdvanceDefs: "; 1527 for (RecIter RI = PM.ReadAdvanceDefs.begin(), 1528 RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) { 1529 if ((*RI)->isSubClassOf("ReadAdvance")) 1530 dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " "; 1531 else 1532 dbgs() << (*RI)->getName() << " "; 1533 } 1534 dbgs() << "\nProcResourceDefs: "; 1535 for (RecIter RI = PM.ProcResourceDefs.begin(), 1536 RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) { 1537 dbgs() << (*RI)->getName() << " "; 1538 } 1539 dbgs() << '\n'); 1540 verifyProcResourceGroups(PM); 1541 } 1542 1543 ProcResourceDefs.clear(); 1544 ProcResGroups.clear(); 1545 } 1546 1547 void CodeGenSchedModels::checkCompleteness() { 1548 bool Complete = true; 1549 bool HadCompleteModel = false; 1550 for (const CodeGenProcModel &ProcModel : procModels()) { 1551 if (!ProcModel.ModelDef->getValueAsBit("CompleteModel")) 1552 continue; 1553 for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 1554 if (Inst->hasNoSchedulingInfo) 1555 continue; 1556 if (ProcModel.isUnsupported(*Inst)) 1557 continue; 1558 unsigned SCIdx = getSchedClassIdx(*Inst); 1559 if (!SCIdx) { 1560 if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) { 1561 PrintError("No schedule information for instruction '" 1562 + Inst->TheDef->getName() + "'"); 1563 Complete = false; 1564 } 1565 continue; 1566 } 1567 1568 const CodeGenSchedClass &SC = getSchedClass(SCIdx); 1569 if (!SC.Writes.empty()) 1570 continue; 1571 if (SC.ItinClassDef != nullptr) 1572 continue; 1573 1574 const RecVec &InstRWs = SC.InstRWs; 1575 auto I = std::find_if(InstRWs.begin(), InstRWs.end(), 1576 [&ProcModel] (const Record *R) { 1577 return R->getValueAsDef("SchedModel") == 1578 ProcModel.ModelDef; 1579 }); 1580 if (I == InstRWs.end()) { 1581 PrintError("'" + ProcModel.ModelName + "' lacks information for '" + 1582 Inst->TheDef->getName() + "'"); 1583 Complete = false; 1584 } 1585 } 1586 HadCompleteModel = true; 1587 } 1588 if (!Complete) { 1589 errs() << "\n\nIncomplete schedule models found.\n" 1590 << "- Consider setting 'CompleteModel = 0' while developing new models.\n" 1591 << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n" 1592 << "- Instructions should usually have Sched<[...]> as a superclass, " 1593 "you may temporarily use an empty list.\n" 1594 << "- Instructions related to unsupported features can be excluded with " 1595 "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the " 1596 "processor model.\n\n"; 1597 PrintFatalError("Incomplete schedule model"); 1598 } 1599 } 1600 1601 // Collect itinerary class resources for each processor. 1602 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) { 1603 for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1604 const CodeGenProcModel &PM = ProcModels[PIdx]; 1605 // For all ItinRW entries. 1606 bool HasMatch = false; 1607 for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 1608 II != IE; ++II) { 1609 RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 1610 if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 1611 continue; 1612 if (HasMatch) 1613 PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 1614 + ItinClassDef->getName() 1615 + " in ItinResources for " + PM.ModelName); 1616 HasMatch = true; 1617 IdxVec Writes, Reads; 1618 findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1619 IdxVec ProcIndices(1, PIdx); 1620 collectRWResources(Writes, Reads, ProcIndices); 1621 } 1622 } 1623 } 1624 1625 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead, 1626 ArrayRef<unsigned> ProcIndices) { 1627 const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 1628 if (SchedRW.TheDef) { 1629 if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) { 1630 for (unsigned Idx : ProcIndices) 1631 addWriteRes(SchedRW.TheDef, Idx); 1632 } 1633 else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) { 1634 for (unsigned Idx : ProcIndices) 1635 addReadAdvance(SchedRW.TheDef, Idx); 1636 } 1637 } 1638 for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1639 AI != AE; ++AI) { 1640 IdxVec AliasProcIndices; 1641 if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1642 AliasProcIndices.push_back( 1643 getProcModel((*AI)->getValueAsDef("SchedModel")).Index); 1644 } 1645 else 1646 AliasProcIndices = ProcIndices; 1647 const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 1648 assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes"); 1649 1650 IdxVec ExpandedRWs; 1651 expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead); 1652 for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 1653 SI != SE; ++SI) { 1654 collectRWResources(*SI, IsRead, AliasProcIndices); 1655 } 1656 } 1657 } 1658 1659 // Collect resources for a set of read/write types and processor indices. 1660 void CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes, 1661 ArrayRef<unsigned> Reads, 1662 ArrayRef<unsigned> ProcIndices) { 1663 1664 for (unsigned Idx : Writes) 1665 collectRWResources(Idx, /*IsRead=*/false, ProcIndices); 1666 1667 for (unsigned Idx : Reads) 1668 collectRWResources(Idx, /*IsRead=*/true, ProcIndices); 1669 } 1670 1671 1672 // Find the processor's resource units for this kind of resource. 1673 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind, 1674 const CodeGenProcModel &PM) const { 1675 if (ProcResKind->isSubClassOf("ProcResourceUnits")) 1676 return ProcResKind; 1677 1678 Record *ProcUnitDef = nullptr; 1679 assert(!ProcResourceDefs.empty()); 1680 assert(!ProcResGroups.empty()); 1681 1682 for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end(); 1683 RI != RE; ++RI) { 1684 1685 if ((*RI)->getValueAsDef("Kind") == ProcResKind 1686 && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) { 1687 if (ProcUnitDef) { 1688 PrintFatalError((*RI)->getLoc(), 1689 "Multiple ProcessorResourceUnits associated with " 1690 + ProcResKind->getName()); 1691 } 1692 ProcUnitDef = *RI; 1693 } 1694 } 1695 for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end(); 1696 RI != RE; ++RI) { 1697 1698 if (*RI == ProcResKind 1699 && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) { 1700 if (ProcUnitDef) { 1701 PrintFatalError((*RI)->getLoc(), 1702 "Multiple ProcessorResourceUnits associated with " 1703 + ProcResKind->getName()); 1704 } 1705 ProcUnitDef = *RI; 1706 } 1707 } 1708 if (!ProcUnitDef) { 1709 PrintFatalError(ProcResKind->getLoc(), 1710 "No ProcessorResources associated with " 1711 + ProcResKind->getName()); 1712 } 1713 return ProcUnitDef; 1714 } 1715 1716 // Iteratively add a resource and its super resources. 1717 void CodeGenSchedModels::addProcResource(Record *ProcResKind, 1718 CodeGenProcModel &PM) { 1719 for (;;) { 1720 Record *ProcResUnits = findProcResUnits(ProcResKind, PM); 1721 1722 // See if this ProcResource is already associated with this processor. 1723 RecIter I = std::find(PM.ProcResourceDefs.begin(), 1724 PM.ProcResourceDefs.end(), ProcResUnits); 1725 if (I != PM.ProcResourceDefs.end()) 1726 return; 1727 1728 PM.ProcResourceDefs.push_back(ProcResUnits); 1729 if (ProcResUnits->isSubClassOf("ProcResGroup")) 1730 return; 1731 1732 if (!ProcResUnits->getValueInit("Super")->isComplete()) 1733 return; 1734 1735 ProcResKind = ProcResUnits->getValueAsDef("Super"); 1736 } 1737 } 1738 1739 // Add resources for a SchedWrite to this processor if they don't exist. 1740 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) { 1741 assert(PIdx && "don't add resources to an invalid Processor model"); 1742 1743 RecVec &WRDefs = ProcModels[PIdx].WriteResDefs; 1744 RecIter WRI = std::find(WRDefs.begin(), WRDefs.end(), ProcWriteResDef); 1745 if (WRI != WRDefs.end()) 1746 return; 1747 WRDefs.push_back(ProcWriteResDef); 1748 1749 // Visit ProcResourceKinds referenced by the newly discovered WriteRes. 1750 RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources"); 1751 for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end(); 1752 WritePRI != WritePRE; ++WritePRI) { 1753 addProcResource(*WritePRI, ProcModels[PIdx]); 1754 } 1755 } 1756 1757 // Add resources for a ReadAdvance to this processor if they don't exist. 1758 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef, 1759 unsigned PIdx) { 1760 RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs; 1761 RecIter I = std::find(RADefs.begin(), RADefs.end(), ProcReadAdvanceDef); 1762 if (I != RADefs.end()) 1763 return; 1764 RADefs.push_back(ProcReadAdvanceDef); 1765 } 1766 1767 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const { 1768 RecIter PRPos = std::find(ProcResourceDefs.begin(), ProcResourceDefs.end(), 1769 PRDef); 1770 if (PRPos == ProcResourceDefs.end()) 1771 PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in " 1772 "the ProcResources list for " + ModelName); 1773 // Idx=0 is reserved for invalid. 1774 return 1 + (PRPos - ProcResourceDefs.begin()); 1775 } 1776 1777 bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const { 1778 for (const Record *TheDef : UnsupportedFeaturesDefs) { 1779 for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) { 1780 if (TheDef->getName() == PredDef->getName()) 1781 return true; 1782 } 1783 } 1784 return false; 1785 } 1786 1787 #ifndef NDEBUG 1788 void CodeGenProcModel::dump() const { 1789 dbgs() << Index << ": " << ModelName << " " 1790 << (ModelDef ? ModelDef->getName() : "inferred") << " " 1791 << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n'; 1792 } 1793 1794 void CodeGenSchedRW::dump() const { 1795 dbgs() << Name << (IsVariadic ? " (V) " : " "); 1796 if (IsSequence) { 1797 dbgs() << "("; 1798 dumpIdxVec(Sequence); 1799 dbgs() << ")"; 1800 } 1801 } 1802 1803 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const { 1804 dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n' 1805 << " Writes: "; 1806 for (unsigned i = 0, N = Writes.size(); i < N; ++i) { 1807 SchedModels->getSchedWrite(Writes[i]).dump(); 1808 if (i < N-1) { 1809 dbgs() << '\n'; 1810 dbgs().indent(10); 1811 } 1812 } 1813 dbgs() << "\n Reads: "; 1814 for (unsigned i = 0, N = Reads.size(); i < N; ++i) { 1815 SchedModels->getSchedRead(Reads[i]).dump(); 1816 if (i < N-1) { 1817 dbgs() << '\n'; 1818 dbgs().indent(10); 1819 } 1820 } 1821 dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n'; 1822 if (!Transitions.empty()) { 1823 dbgs() << "\n Transitions for Proc "; 1824 for (std::vector<CodeGenSchedTransition>::const_iterator 1825 TI = Transitions.begin(), TE = Transitions.end(); TI != TE; ++TI) { 1826 dumpIdxVec(TI->ProcIndices); 1827 } 1828 } 1829 } 1830 1831 void PredTransitions::dump() const { 1832 dbgs() << "Expanded Variants:\n"; 1833 for (std::vector<PredTransition>::const_iterator 1834 TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) { 1835 dbgs() << "{"; 1836 for (SmallVectorImpl<PredCheck>::const_iterator 1837 PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end(); 1838 PCI != PCE; ++PCI) { 1839 if (PCI != TI->PredTerm.begin()) 1840 dbgs() << ", "; 1841 dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name 1842 << ":" << PCI->Predicate->getName(); 1843 } 1844 dbgs() << "},\n => {"; 1845 for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1846 WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end(); 1847 WSI != WSE; ++WSI) { 1848 dbgs() << "("; 1849 for (SmallVectorImpl<unsigned>::const_iterator 1850 WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 1851 if (WI != WSI->begin()) 1852 dbgs() << ", "; 1853 dbgs() << SchedModels.getSchedWrite(*WI).Name; 1854 } 1855 dbgs() << "),"; 1856 } 1857 dbgs() << "}\n"; 1858 } 1859 } 1860 #endif // NDEBUG 1861