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