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