CodeGenSchedule.cpp revision 276479
1239310Sdim//===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim// 10276479Sdim// This file defines structures to encapsulate the machine model as described in 11239310Sdim// the target description. 12239310Sdim// 13239310Sdim//===----------------------------------------------------------------------===// 14239310Sdim 15239310Sdim#include "CodeGenSchedule.h" 16239310Sdim#include "CodeGenTarget.h" 17249423Sdim#include "llvm/ADT/STLExtras.h" 18239310Sdim#include "llvm/Support/Debug.h" 19243830Sdim#include "llvm/Support/Regex.h" 20249423Sdim#include "llvm/TableGen/Error.h" 21239310Sdim 22239310Sdimusing namespace llvm; 23239310Sdim 24276479Sdim#define DEBUG_TYPE "subtarget-emitter" 25276479Sdim 26243830Sdim#ifndef NDEBUG 27243830Sdimstatic void dumpIdxVec(const IdxVec &V) { 28243830Sdim for (unsigned i = 0, e = V.size(); i < e; ++i) { 29243830Sdim dbgs() << V[i] << ", "; 30243830Sdim } 31243830Sdim} 32243830Sdimstatic void dumpIdxVec(const SmallVectorImpl<unsigned> &V) { 33243830Sdim for (unsigned i = 0, e = V.size(); i < e; ++i) { 34243830Sdim dbgs() << V[i] << ", "; 35243830Sdim } 36243830Sdim} 37243830Sdim#endif 38243830Sdim 39261991Sdimnamespace { 40243830Sdim// (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp. 41243830Sdimstruct InstrsOp : public SetTheory::Operator { 42276479Sdim void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 43276479Sdim ArrayRef<SMLoc> Loc) override { 44243830Sdim ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc); 45243830Sdim } 46243830Sdim}; 47243830Sdim 48243830Sdim// (instregex "OpcPat",...) Find all instructions matching an opcode pattern. 49243830Sdim// 50243830Sdim// TODO: Since this is a prefix match, perform a binary search over the 51243830Sdim// instruction names using lower_bound. Note that the predefined instrs must be 52243830Sdim// scanned linearly first. However, this is only safe if the regex pattern has 53243830Sdim// no top-level bars. The DAG already has a list of patterns, so there's no 54243830Sdim// reason to use top-level bars, but we need a way to verify they don't exist 55243830Sdim// before implementing the optimization. 56243830Sdimstruct InstRegexOp : public SetTheory::Operator { 57243830Sdim const CodeGenTarget &Target; 58243830Sdim InstRegexOp(const CodeGenTarget &t): Target(t) {} 59243830Sdim 60243830Sdim void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 61276479Sdim ArrayRef<SMLoc> Loc) override { 62276479Sdim SmallVector<Regex, 4> RegexList; 63243830Sdim for (DagInit::const_arg_iterator 64243830Sdim AI = Expr->arg_begin(), AE = Expr->arg_end(); AI != AE; ++AI) { 65243830Sdim StringInit *SI = dyn_cast<StringInit>(*AI); 66243830Sdim if (!SI) 67243830Sdim PrintFatalError(Loc, "instregex requires pattern string: " 68243830Sdim + Expr->getAsString()); 69243830Sdim std::string pat = SI->getValue(); 70243830Sdim // Implement a python-style prefix match. 71243830Sdim if (pat[0] != '^') { 72243830Sdim pat.insert(0, "^("); 73243830Sdim pat.insert(pat.end(), ')'); 74243830Sdim } 75276479Sdim RegexList.push_back(Regex(pat)); 76243830Sdim } 77243830Sdim for (CodeGenTarget::inst_iterator I = Target.inst_begin(), 78243830Sdim E = Target.inst_end(); I != E; ++I) { 79276479Sdim for (auto &R : RegexList) { 80276479Sdim if (R.match((*I)->TheDef->getName())) 81243830Sdim Elts.insert((*I)->TheDef); 82243830Sdim } 83243830Sdim } 84243830Sdim } 85243830Sdim}; 86261991Sdim} // end anonymous namespace 87243830Sdim 88243830Sdim/// CodeGenModels ctor interprets machine model records and populates maps. 89239310SdimCodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK, 90239310Sdim const CodeGenTarget &TGT): 91249423Sdim Records(RK), Target(TGT) { 92239310Sdim 93243830Sdim Sets.addFieldExpander("InstRW", "Instrs"); 94239310Sdim 95243830Sdim // Allow Set evaluation to recognize the dags used in InstRW records: 96243830Sdim // (instrs Op1, Op1...) 97243830Sdim Sets.addOperator("instrs", new InstrsOp); 98243830Sdim Sets.addOperator("instregex", new InstRegexOp(Target)); 99243830Sdim 100243830Sdim // Instantiate a CodeGenProcModel for each SchedMachineModel with the values 101243830Sdim // that are explicitly referenced in tablegen records. Resources associated 102243830Sdim // with each processor will be derived later. Populate ProcModelMap with the 103243830Sdim // CodeGenProcModel instances. 104243830Sdim collectProcModels(); 105243830Sdim 106243830Sdim // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly 107243830Sdim // defined, and populate SchedReads and SchedWrites vectors. Implicit 108243830Sdim // SchedReadWrites that represent sequences derived from expanded variant will 109243830Sdim // be inferred later. 110243830Sdim collectSchedRW(); 111243830Sdim 112243830Sdim // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly 113243830Sdim // required by an instruction definition, and populate SchedClassIdxMap. Set 114243830Sdim // NumItineraryClasses to the number of explicit itinerary classes referenced 115243830Sdim // by instructions. Set NumInstrSchedClasses to the number of itinerary 116243830Sdim // classes plus any classes implied by instructions that derive from class 117243830Sdim // Sched and provide SchedRW list. This does not infer any new classes from 118243830Sdim // SchedVariant. 119243830Sdim collectSchedClasses(); 120243830Sdim 121243830Sdim // Find instruction itineraries for each processor. Sort and populate 122243830Sdim // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires 123243830Sdim // all itinerary classes to be discovered. 124243830Sdim collectProcItins(); 125243830Sdim 126243830Sdim // Find ItinRW records for each processor and itinerary class. 127243830Sdim // (For per-operand resources mapped to itinerary classes). 128243830Sdim collectProcItinRW(); 129243830Sdim 130243830Sdim // Infer new SchedClasses from SchedVariant. 131243830Sdim inferSchedClasses(); 132243830Sdim 133243830Sdim // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and 134243830Sdim // ProcResourceDefs. 135243830Sdim collectProcResources(); 136239310Sdim} 137239310Sdim 138243830Sdim/// Gather all processor models. 139243830Sdimvoid CodeGenSchedModels::collectProcModels() { 140243830Sdim RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor"); 141243830Sdim std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName()); 142239310Sdim 143243830Sdim // Reserve space because we can. Reallocation would be ok. 144243830Sdim ProcModels.reserve(ProcRecords.size()+1); 145243830Sdim 146243830Sdim // Use idx=0 for NoModel/NoItineraries. 147243830Sdim Record *NoModelDef = Records.getDef("NoSchedModel"); 148243830Sdim Record *NoItinsDef = Records.getDef("NoItineraries"); 149243830Sdim ProcModels.push_back(CodeGenProcModel(0, "NoSchedModel", 150243830Sdim NoModelDef, NoItinsDef)); 151243830Sdim ProcModelMap[NoModelDef] = 0; 152243830Sdim 153243830Sdim // For each processor, find a unique machine model. 154243830Sdim for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i) 155243830Sdim addProcModel(ProcRecords[i]); 156243830Sdim} 157243830Sdim 158243830Sdim/// Get a unique processor model based on the defined MachineModel and 159243830Sdim/// ProcessorItineraries. 160243830Sdimvoid CodeGenSchedModels::addProcModel(Record *ProcDef) { 161243830Sdim Record *ModelKey = getModelOrItinDef(ProcDef); 162243830Sdim if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second) 163243830Sdim return; 164243830Sdim 165243830Sdim std::string Name = ModelKey->getName(); 166243830Sdim if (ModelKey->isSubClassOf("SchedMachineModel")) { 167243830Sdim Record *ItinsDef = ModelKey->getValueAsDef("Itineraries"); 168243830Sdim ProcModels.push_back( 169243830Sdim CodeGenProcModel(ProcModels.size(), Name, ModelKey, ItinsDef)); 170243830Sdim } 171243830Sdim else { 172243830Sdim // An itinerary is defined without a machine model. Infer a new model. 173243830Sdim if (!ModelKey->getValueAsListOfDefs("IID").empty()) 174243830Sdim Name = Name + "Model"; 175243830Sdim ProcModels.push_back( 176243830Sdim CodeGenProcModel(ProcModels.size(), Name, 177243830Sdim ProcDef->getValueAsDef("SchedModel"), ModelKey)); 178243830Sdim } 179243830Sdim DEBUG(ProcModels.back().dump()); 180243830Sdim} 181243830Sdim 182243830Sdim// Recursively find all reachable SchedReadWrite records. 183243830Sdimstatic void scanSchedRW(Record *RWDef, RecVec &RWDefs, 184243830Sdim SmallPtrSet<Record*, 16> &RWSet) { 185243830Sdim if (!RWSet.insert(RWDef)) 186243830Sdim return; 187243830Sdim RWDefs.push_back(RWDef); 188243830Sdim // Reads don't current have sequence records, but it can be added later. 189243830Sdim if (RWDef->isSubClassOf("WriteSequence")) { 190243830Sdim RecVec Seq = RWDef->getValueAsListOfDefs("Writes"); 191243830Sdim for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I) 192243830Sdim scanSchedRW(*I, RWDefs, RWSet); 193243830Sdim } 194243830Sdim else if (RWDef->isSubClassOf("SchedVariant")) { 195243830Sdim // Visit each variant (guarded by a different predicate). 196243830Sdim RecVec Vars = RWDef->getValueAsListOfDefs("Variants"); 197243830Sdim for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) { 198243830Sdim // Visit each RW in the sequence selected by the current variant. 199243830Sdim RecVec Selected = (*VI)->getValueAsListOfDefs("Selected"); 200243830Sdim for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I) 201243830Sdim scanSchedRW(*I, RWDefs, RWSet); 202243830Sdim } 203243830Sdim } 204243830Sdim} 205243830Sdim 206243830Sdim// Collect and sort all SchedReadWrites reachable via tablegen records. 207243830Sdim// More may be inferred later when inferring new SchedClasses from variants. 208243830Sdimvoid CodeGenSchedModels::collectSchedRW() { 209243830Sdim // Reserve idx=0 for invalid writes/reads. 210243830Sdim SchedWrites.resize(1); 211243830Sdim SchedReads.resize(1); 212243830Sdim 213243830Sdim SmallPtrSet<Record*, 16> RWSet; 214243830Sdim 215243830Sdim // Find all SchedReadWrites referenced by instruction defs. 216243830Sdim RecVec SWDefs, SRDefs; 217243830Sdim for (CodeGenTarget::inst_iterator I = Target.inst_begin(), 218243830Sdim E = Target.inst_end(); I != E; ++I) { 219243830Sdim Record *SchedDef = (*I)->TheDef; 220249423Sdim if (SchedDef->isValueUnset("SchedRW")) 221243830Sdim continue; 222243830Sdim RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW"); 223243830Sdim for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) { 224243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 225243830Sdim scanSchedRW(*RWI, SWDefs, RWSet); 226243830Sdim else { 227243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 228243830Sdim scanSchedRW(*RWI, SRDefs, RWSet); 229243830Sdim } 230243830Sdim } 231243830Sdim } 232243830Sdim // Find all ReadWrites referenced by InstRW. 233243830Sdim RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 234243830Sdim for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) { 235243830Sdim // For all OperandReadWrites. 236243830Sdim RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites"); 237243830Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 238243830Sdim RWI != RWE; ++RWI) { 239243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 240243830Sdim scanSchedRW(*RWI, SWDefs, RWSet); 241243830Sdim else { 242243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 243243830Sdim scanSchedRW(*RWI, SRDefs, RWSet); 244243830Sdim } 245243830Sdim } 246243830Sdim } 247243830Sdim // Find all ReadWrites referenced by ItinRW. 248243830Sdim RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 249243830Sdim for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { 250243830Sdim // For all OperandReadWrites. 251243830Sdim RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites"); 252243830Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 253243830Sdim RWI != RWE; ++RWI) { 254243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 255243830Sdim scanSchedRW(*RWI, SWDefs, RWSet); 256243830Sdim else { 257243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 258243830Sdim scanSchedRW(*RWI, SRDefs, RWSet); 259243830Sdim } 260243830Sdim } 261243830Sdim } 262243830Sdim // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted 263243830Sdim // for the loop below that initializes Alias vectors. 264243830Sdim RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias"); 265243830Sdim std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord()); 266243830Sdim for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) { 267243830Sdim Record *MatchDef = (*AI)->getValueAsDef("MatchRW"); 268243830Sdim Record *AliasDef = (*AI)->getValueAsDef("AliasRW"); 269243830Sdim if (MatchDef->isSubClassOf("SchedWrite")) { 270243830Sdim if (!AliasDef->isSubClassOf("SchedWrite")) 271243830Sdim PrintFatalError((*AI)->getLoc(), "SchedWrite Alias must be SchedWrite"); 272243830Sdim scanSchedRW(AliasDef, SWDefs, RWSet); 273243830Sdim } 274243830Sdim else { 275243830Sdim assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 276243830Sdim if (!AliasDef->isSubClassOf("SchedRead")) 277243830Sdim PrintFatalError((*AI)->getLoc(), "SchedRead Alias must be SchedRead"); 278243830Sdim scanSchedRW(AliasDef, SRDefs, RWSet); 279243830Sdim } 280243830Sdim } 281243830Sdim // Sort and add the SchedReadWrites directly referenced by instructions or 282243830Sdim // itinerary resources. Index reads and writes in separate domains. 283243830Sdim std::sort(SWDefs.begin(), SWDefs.end(), LessRecord()); 284243830Sdim for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) { 285243830Sdim assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite"); 286243830Sdim SchedWrites.push_back(CodeGenSchedRW(SchedWrites.size(), *SWI)); 287243830Sdim } 288243830Sdim std::sort(SRDefs.begin(), SRDefs.end(), LessRecord()); 289243830Sdim for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) { 290243830Sdim assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite"); 291243830Sdim SchedReads.push_back(CodeGenSchedRW(SchedReads.size(), *SRI)); 292243830Sdim } 293243830Sdim // Initialize WriteSequence vectors. 294243830Sdim for (std::vector<CodeGenSchedRW>::iterator WI = SchedWrites.begin(), 295243830Sdim WE = SchedWrites.end(); WI != WE; ++WI) { 296243830Sdim if (!WI->IsSequence) 297243830Sdim continue; 298243830Sdim findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence, 299243830Sdim /*IsRead=*/false); 300243830Sdim } 301243830Sdim // Initialize Aliases vectors. 302243830Sdim for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) { 303243830Sdim Record *AliasDef = (*AI)->getValueAsDef("AliasRW"); 304243830Sdim getSchedRW(AliasDef).IsAlias = true; 305243830Sdim Record *MatchDef = (*AI)->getValueAsDef("MatchRW"); 306243830Sdim CodeGenSchedRW &RW = getSchedRW(MatchDef); 307243830Sdim if (RW.IsAlias) 308243830Sdim PrintFatalError((*AI)->getLoc(), "Cannot Alias an Alias"); 309243830Sdim RW.Aliases.push_back(*AI); 310243830Sdim } 311243830Sdim DEBUG( 312243830Sdim for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) { 313243830Sdim dbgs() << WIdx << ": "; 314243830Sdim SchedWrites[WIdx].dump(); 315243830Sdim dbgs() << '\n'; 316243830Sdim } 317243830Sdim for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) { 318243830Sdim dbgs() << RIdx << ": "; 319243830Sdim SchedReads[RIdx].dump(); 320243830Sdim dbgs() << '\n'; 321243830Sdim } 322243830Sdim RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite"); 323243830Sdim for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); 324243830Sdim RI != RE; ++RI) { 325243830Sdim if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) { 326243830Sdim const std::string &Name = (*RI)->getName(); 327243830Sdim if (Name != "NoWrite" && Name != "ReadDefault") 328243830Sdim dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n'; 329243830Sdim } 330243830Sdim }); 331243830Sdim} 332243830Sdim 333243830Sdim/// Compute a SchedWrite name from a sequence of writes. 334243830Sdimstd::string CodeGenSchedModels::genRWName(const IdxVec& Seq, bool IsRead) { 335243830Sdim std::string Name("("); 336243830Sdim for (IdxIter I = Seq.begin(), E = Seq.end(); I != E; ++I) { 337243830Sdim if (I != Seq.begin()) 338243830Sdim Name += '_'; 339243830Sdim Name += getSchedRW(*I, IsRead).Name; 340243830Sdim } 341243830Sdim Name += ')'; 342243830Sdim return Name; 343243830Sdim} 344243830Sdim 345243830Sdimunsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead, 346243830Sdim unsigned After) const { 347243830Sdim const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 348243830Sdim assert(After < RWVec.size() && "start position out of bounds"); 349243830Sdim for (std::vector<CodeGenSchedRW>::const_iterator I = RWVec.begin() + After, 350243830Sdim E = RWVec.end(); I != E; ++I) { 351243830Sdim if (I->TheDef == Def) 352243830Sdim return I - RWVec.begin(); 353243830Sdim } 354243830Sdim return 0; 355243830Sdim} 356243830Sdim 357243830Sdimbool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const { 358243830Sdim for (unsigned i = 0, e = SchedReads.size(); i < e; ++i) { 359243830Sdim Record *ReadDef = SchedReads[i].TheDef; 360243830Sdim if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance")) 361243830Sdim continue; 362243830Sdim 363243830Sdim RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites"); 364243830Sdim if (std::find(ValidWrites.begin(), ValidWrites.end(), WriteDef) 365243830Sdim != ValidWrites.end()) { 366243830Sdim return true; 367243830Sdim } 368243830Sdim } 369243830Sdim return false; 370243830Sdim} 371243830Sdim 372243830Sdimnamespace llvm { 373243830Sdimvoid splitSchedReadWrites(const RecVec &RWDefs, 374243830Sdim RecVec &WriteDefs, RecVec &ReadDefs) { 375243830Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) { 376243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 377243830Sdim WriteDefs.push_back(*RWI); 378243830Sdim else { 379243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite"); 380243830Sdim ReadDefs.push_back(*RWI); 381243830Sdim } 382243830Sdim } 383243830Sdim} 384243830Sdim} // namespace llvm 385243830Sdim 386243830Sdim// Split the SchedReadWrites defs and call findRWs for each list. 387243830Sdimvoid CodeGenSchedModels::findRWs(const RecVec &RWDefs, 388243830Sdim IdxVec &Writes, IdxVec &Reads) const { 389243830Sdim RecVec WriteDefs; 390243830Sdim RecVec ReadDefs; 391243830Sdim splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs); 392243830Sdim findRWs(WriteDefs, Writes, false); 393243830Sdim findRWs(ReadDefs, Reads, true); 394243830Sdim} 395243830Sdim 396243830Sdim// Call getSchedRWIdx for all elements in a sequence of SchedRW defs. 397243830Sdimvoid CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs, 398243830Sdim bool IsRead) const { 399243830Sdim for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) { 400243830Sdim unsigned Idx = getSchedRWIdx(*RI, IsRead); 401243830Sdim assert(Idx && "failed to collect SchedReadWrite"); 402243830Sdim RWs.push_back(Idx); 403243830Sdim } 404243830Sdim} 405243830Sdim 406243830Sdimvoid CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, 407243830Sdim bool IsRead) const { 408243830Sdim const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 409243830Sdim if (!SchedRW.IsSequence) { 410243830Sdim RWSeq.push_back(RWIdx); 411243830Sdim return; 412243830Sdim } 413243830Sdim int Repeat = 414243830Sdim SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1; 415243830Sdim for (int i = 0; i < Repeat; ++i) { 416243830Sdim for (IdxIter I = SchedRW.Sequence.begin(), E = SchedRW.Sequence.end(); 417243830Sdim I != E; ++I) { 418243830Sdim expandRWSequence(*I, RWSeq, IsRead); 419243830Sdim } 420243830Sdim } 421243830Sdim} 422243830Sdim 423243830Sdim// Expand a SchedWrite as a sequence following any aliases that coincide with 424243830Sdim// the given processor model. 425243830Sdimvoid CodeGenSchedModels::expandRWSeqForProc( 426243830Sdim unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 427243830Sdim const CodeGenProcModel &ProcModel) const { 428243830Sdim 429243830Sdim const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead); 430276479Sdim Record *AliasDef = nullptr; 431243830Sdim for (RecIter AI = SchedWrite.Aliases.begin(), AE = SchedWrite.Aliases.end(); 432243830Sdim AI != AE; ++AI) { 433243830Sdim const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 434243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 435243830Sdim Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 436243830Sdim if (&getProcModel(ModelDef) != &ProcModel) 437243830Sdim continue; 438243830Sdim } 439243830Sdim if (AliasDef) 440243830Sdim PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases " 441243830Sdim "defined for processor " + ProcModel.ModelName + 442243830Sdim " Ensure only one SchedAlias exists per RW."); 443243830Sdim AliasDef = AliasRW.TheDef; 444243830Sdim } 445243830Sdim if (AliasDef) { 446243830Sdim expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead), 447243830Sdim RWSeq, IsRead,ProcModel); 448243830Sdim return; 449243830Sdim } 450243830Sdim if (!SchedWrite.IsSequence) { 451243830Sdim RWSeq.push_back(RWIdx); 452243830Sdim return; 453243830Sdim } 454243830Sdim int Repeat = 455243830Sdim SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1; 456243830Sdim for (int i = 0; i < Repeat; ++i) { 457243830Sdim for (IdxIter I = SchedWrite.Sequence.begin(), E = SchedWrite.Sequence.end(); 458243830Sdim I != E; ++I) { 459243830Sdim expandRWSeqForProc(*I, RWSeq, IsRead, ProcModel); 460243830Sdim } 461243830Sdim } 462243830Sdim} 463243830Sdim 464243830Sdim// Find the existing SchedWrite that models this sequence of writes. 465243830Sdimunsigned CodeGenSchedModels::findRWForSequence(const IdxVec &Seq, 466243830Sdim bool IsRead) { 467243830Sdim std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 468243830Sdim 469243830Sdim for (std::vector<CodeGenSchedRW>::iterator I = RWVec.begin(), E = RWVec.end(); 470243830Sdim I != E; ++I) { 471243830Sdim if (I->Sequence == Seq) 472243830Sdim return I - RWVec.begin(); 473243830Sdim } 474243830Sdim // Index zero reserved for invalid RW. 475243830Sdim return 0; 476243830Sdim} 477243830Sdim 478243830Sdim/// Add this ReadWrite if it doesn't already exist. 479243830Sdimunsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq, 480243830Sdim bool IsRead) { 481243830Sdim assert(!Seq.empty() && "cannot insert empty sequence"); 482243830Sdim if (Seq.size() == 1) 483243830Sdim return Seq.back(); 484243830Sdim 485243830Sdim unsigned Idx = findRWForSequence(Seq, IsRead); 486243830Sdim if (Idx) 487243830Sdim return Idx; 488243830Sdim 489243830Sdim unsigned RWIdx = IsRead ? SchedReads.size() : SchedWrites.size(); 490243830Sdim CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead)); 491243830Sdim if (IsRead) 492243830Sdim SchedReads.push_back(SchedRW); 493243830Sdim else 494243830Sdim SchedWrites.push_back(SchedRW); 495243830Sdim return RWIdx; 496243830Sdim} 497243830Sdim 498243830Sdim/// Visit all the instruction definitions for this target to gather and 499243830Sdim/// enumerate the itinerary classes. These are the explicitly specified 500243830Sdim/// SchedClasses. More SchedClasses may be inferred. 501243830Sdimvoid CodeGenSchedModels::collectSchedClasses() { 502243830Sdim 503243830Sdim // NoItinerary is always the first class at Idx=0 504239310Sdim SchedClasses.resize(1); 505249423Sdim SchedClasses.back().Index = 0; 506249423Sdim SchedClasses.back().Name = "NoInstrModel"; 507249423Sdim SchedClasses.back().ItinClassDef = Records.getDef("NoItinerary"); 508243830Sdim SchedClasses.back().ProcIndices.push_back(0); 509239310Sdim 510249423Sdim // Create a SchedClass for each unique combination of itinerary class and 511249423Sdim // SchedRW list. 512239310Sdim for (CodeGenTarget::inst_iterator I = Target.inst_begin(), 513239310Sdim E = Target.inst_end(); I != E; ++I) { 514243830Sdim Record *ItinDef = (*I)->TheDef->getValueAsDef("Itinerary"); 515243830Sdim IdxVec Writes, Reads; 516249423Sdim if (!(*I)->TheDef->isValueUnset("SchedRW")) 517249423Sdim findRWs((*I)->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); 518249423Sdim 519243830Sdim // ProcIdx == 0 indicates the class applies to all processors. 520243830Sdim IdxVec ProcIndices(1, 0); 521249423Sdim 522249423Sdim unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, ProcIndices); 523249423Sdim InstrClassMap[(*I)->TheDef] = SCIdx; 524243830Sdim } 525243830Sdim // Create classes for InstRW defs. 526243830Sdim RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 527243830Sdim std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord()); 528243830Sdim for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) 529243830Sdim createInstRWClass(*OI); 530239310Sdim 531243830Sdim NumInstrSchedClasses = SchedClasses.size(); 532243830Sdim 533243830Sdim bool EnableDump = false; 534243830Sdim DEBUG(EnableDump = true); 535243830Sdim if (!EnableDump) 536243830Sdim return; 537249423Sdim 538243830Sdim for (CodeGenTarget::inst_iterator I = Target.inst_begin(), 539243830Sdim E = Target.inst_end(); I != E; ++I) { 540249423Sdim 541243830Sdim std::string InstName = (*I)->TheDef->getName(); 542249423Sdim unsigned SCIdx = InstrClassMap.lookup((*I)->TheDef); 543249423Sdim if (!SCIdx) { 544249423Sdim dbgs() << "No machine model for " << (*I)->TheDef->getName() << '\n'; 545249423Sdim continue; 546249423Sdim } 547249423Sdim CodeGenSchedClass &SC = getSchedClass(SCIdx); 548249423Sdim if (SC.ProcIndices[0] != 0) 549249423Sdim PrintFatalError((*I)->TheDef->getLoc(), "Instruction's sched class " 550249423Sdim "must not be subtarget specific."); 551249423Sdim 552249423Sdim IdxVec ProcIndices; 553249423Sdim if (SC.ItinClassDef->getName() != "NoItinerary") { 554249423Sdim ProcIndices.push_back(0); 555249423Sdim dbgs() << "Itinerary for " << InstName << ": " 556249423Sdim << SC.ItinClassDef->getName() << '\n'; 557249423Sdim } 558249423Sdim if (!SC.Writes.empty()) { 559249423Sdim ProcIndices.push_back(0); 560249423Sdim dbgs() << "SchedRW machine model for " << InstName; 561249423Sdim for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE; ++WI) 562249423Sdim dbgs() << " " << SchedWrites[*WI].Name; 563249423Sdim for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI) 564249423Sdim dbgs() << " " << SchedReads[*RI].Name; 565249423Sdim dbgs() << '\n'; 566249423Sdim } 567249423Sdim const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs; 568249423Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 569249423Sdim RWI != RWE; ++RWI) { 570249423Sdim const CodeGenProcModel &ProcModel = 571249423Sdim getProcModel((*RWI)->getValueAsDef("SchedModel")); 572249423Sdim ProcIndices.push_back(ProcModel.Index); 573249423Sdim dbgs() << "InstRW on " << ProcModel.ModelName << " for " << InstName; 574243830Sdim IdxVec Writes; 575243830Sdim IdxVec Reads; 576249423Sdim findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), 577249423Sdim Writes, Reads); 578243830Sdim for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI) 579243830Sdim dbgs() << " " << SchedWrites[*WI].Name; 580243830Sdim for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI) 581243830Sdim dbgs() << " " << SchedReads[*RI].Name; 582243830Sdim dbgs() << '\n'; 583243830Sdim } 584249423Sdim for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(), 585249423Sdim PE = ProcModels.end(); PI != PE; ++PI) { 586249423Sdim if (!std::count(ProcIndices.begin(), ProcIndices.end(), PI->Index)) 587249423Sdim dbgs() << "No machine model for " << (*I)->TheDef->getName() 588249423Sdim << " on processor " << PI->ModelName << '\n'; 589243830Sdim } 590243830Sdim } 591239310Sdim} 592239310Sdim 593243830Sdim/// Find an SchedClass that has been inferred from a per-operand list of 594243830Sdim/// SchedWrites and SchedReads. 595249423Sdimunsigned CodeGenSchedModels::findSchedClassIdx(Record *ItinClassDef, 596249423Sdim const IdxVec &Writes, 597243830Sdim const IdxVec &Reads) const { 598243830Sdim for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) { 599249423Sdim if (I->ItinClassDef == ItinClassDef 600249423Sdim && I->Writes == Writes && I->Reads == Reads) { 601243830Sdim return I - schedClassBegin(); 602243830Sdim } 603243830Sdim } 604243830Sdim return 0; 605239310Sdim} 606239310Sdim 607243830Sdim// Get the SchedClass index for an instruction. 608243830Sdimunsigned CodeGenSchedModels::getSchedClassIdx( 609243830Sdim const CodeGenInstruction &Inst) const { 610239310Sdim 611249423Sdim return InstrClassMap.lookup(Inst.TheDef); 612243830Sdim} 613239310Sdim 614243830Sdimstd::string CodeGenSchedModels::createSchedClassName( 615249423Sdim Record *ItinClassDef, const IdxVec &OperWrites, const IdxVec &OperReads) { 616243830Sdim 617243830Sdim std::string Name; 618249423Sdim if (ItinClassDef && ItinClassDef->getName() != "NoItinerary") 619249423Sdim Name = ItinClassDef->getName(); 620243830Sdim for (IdxIter WI = OperWrites.begin(), WE = OperWrites.end(); WI != WE; ++WI) { 621249423Sdim if (!Name.empty()) 622243830Sdim Name += '_'; 623243830Sdim Name += SchedWrites[*WI].Name; 624243830Sdim } 625243830Sdim for (IdxIter RI = OperReads.begin(), RE = OperReads.end(); RI != RE; ++RI) { 626243830Sdim Name += '_'; 627243830Sdim Name += SchedReads[*RI].Name; 628243830Sdim } 629243830Sdim return Name; 630243830Sdim} 631243830Sdim 632243830Sdimstd::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { 633243830Sdim 634243830Sdim std::string Name; 635243830Sdim for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) { 636243830Sdim if (I != InstDefs.begin()) 637243830Sdim Name += '_'; 638243830Sdim Name += (*I)->getName(); 639243830Sdim } 640243830Sdim return Name; 641243830Sdim} 642243830Sdim 643249423Sdim/// Add an inferred sched class from an itinerary class and per-operand list of 644249423Sdim/// SchedWrites and SchedReads. ProcIndices contains the set of IDs of 645249423Sdim/// processors that may utilize this class. 646249423Sdimunsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef, 647249423Sdim const IdxVec &OperWrites, 648243830Sdim const IdxVec &OperReads, 649243830Sdim const IdxVec &ProcIndices) 650243830Sdim{ 651243830Sdim assert(!ProcIndices.empty() && "expect at least one ProcIdx"); 652243830Sdim 653249423Sdim unsigned Idx = findSchedClassIdx(ItinClassDef, OperWrites, OperReads); 654249423Sdim if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) { 655243830Sdim IdxVec PI; 656243830Sdim std::set_union(SchedClasses[Idx].ProcIndices.begin(), 657243830Sdim SchedClasses[Idx].ProcIndices.end(), 658243830Sdim ProcIndices.begin(), ProcIndices.end(), 659243830Sdim std::back_inserter(PI)); 660243830Sdim SchedClasses[Idx].ProcIndices.swap(PI); 661243830Sdim return Idx; 662243830Sdim } 663243830Sdim Idx = SchedClasses.size(); 664243830Sdim SchedClasses.resize(Idx+1); 665243830Sdim CodeGenSchedClass &SC = SchedClasses.back(); 666249423Sdim SC.Index = Idx; 667249423Sdim SC.Name = createSchedClassName(ItinClassDef, OperWrites, OperReads); 668249423Sdim SC.ItinClassDef = ItinClassDef; 669243830Sdim SC.Writes = OperWrites; 670243830Sdim SC.Reads = OperReads; 671243830Sdim SC.ProcIndices = ProcIndices; 672243830Sdim 673243830Sdim return Idx; 674243830Sdim} 675243830Sdim 676243830Sdim// Create classes for each set of opcodes that are in the same InstReadWrite 677243830Sdim// definition across all processors. 678243830Sdimvoid CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { 679243830Sdim // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that 680243830Sdim // intersects with an existing class via a previous InstRWDef. Instrs that do 681243830Sdim // not intersect with an existing class refer back to their former class as 682243830Sdim // determined from ItinDef or SchedRW. 683243830Sdim SmallVector<std::pair<unsigned, SmallVector<Record *, 8> >, 4> ClassInstrs; 684243830Sdim // Sort Instrs into sets. 685243830Sdim const RecVec *InstDefs = Sets.expand(InstRWDef); 686243830Sdim if (InstDefs->empty()) 687243830Sdim PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes"); 688243830Sdim 689243830Sdim for (RecIter I = InstDefs->begin(), E = InstDefs->end(); I != E; ++I) { 690243830Sdim InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I); 691249423Sdim if (Pos == InstrClassMap.end()) 692249423Sdim PrintFatalError((*I)->getLoc(), "No sched class for instruction."); 693249423Sdim unsigned SCIdx = Pos->second; 694243830Sdim unsigned CIdx = 0, CEnd = ClassInstrs.size(); 695243830Sdim for (; CIdx != CEnd; ++CIdx) { 696243830Sdim if (ClassInstrs[CIdx].first == SCIdx) 697243830Sdim break; 698243830Sdim } 699243830Sdim if (CIdx == CEnd) { 700243830Sdim ClassInstrs.resize(CEnd + 1); 701243830Sdim ClassInstrs[CIdx].first = SCIdx; 702243830Sdim } 703243830Sdim ClassInstrs[CIdx].second.push_back(*I); 704239310Sdim } 705243830Sdim // For each set of Instrs, create a new class if necessary, and map or remap 706243830Sdim // the Instrs to it. 707243830Sdim unsigned CIdx = 0, CEnd = ClassInstrs.size(); 708243830Sdim for (; CIdx != CEnd; ++CIdx) { 709243830Sdim unsigned OldSCIdx = ClassInstrs[CIdx].first; 710243830Sdim ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second; 711243830Sdim // If the all instrs in the current class are accounted for, then leave 712243830Sdim // them mapped to their old class. 713261991Sdim if (OldSCIdx) { 714261991Sdim const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs; 715261991Sdim if (!RWDefs.empty()) { 716261991Sdim const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]); 717261991Sdim unsigned OrigNumInstrs = 0; 718261991Sdim for (RecIter I = OrigInstDefs->begin(), E = OrigInstDefs->end(); 719261991Sdim I != E; ++I) { 720261991Sdim if (InstrClassMap[*I] == OldSCIdx) 721261991Sdim ++OrigNumInstrs; 722261991Sdim } 723261991Sdim if (OrigNumInstrs == InstDefs.size()) { 724261991Sdim assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 && 725261991Sdim "expected a generic SchedClass"); 726261991Sdim DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":" 727261991Sdim << SchedClasses[OldSCIdx].Name << " on " 728261991Sdim << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n"); 729261991Sdim SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef); 730261991Sdim continue; 731261991Sdim } 732261991Sdim } 733243830Sdim } 734243830Sdim unsigned SCIdx = SchedClasses.size(); 735243830Sdim SchedClasses.resize(SCIdx+1); 736243830Sdim CodeGenSchedClass &SC = SchedClasses.back(); 737249423Sdim SC.Index = SCIdx; 738243830Sdim SC.Name = createSchedClassName(InstDefs); 739261991Sdim DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on " 740261991Sdim << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n"); 741261991Sdim 742243830Sdim // Preserve ItinDef and Writes/Reads for processors without an InstRW entry. 743243830Sdim SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef; 744243830Sdim SC.Writes = SchedClasses[OldSCIdx].Writes; 745243830Sdim SC.Reads = SchedClasses[OldSCIdx].Reads; 746243830Sdim SC.ProcIndices.push_back(0); 747243830Sdim // Map each Instr to this new class. 748243830Sdim // Note that InstDefs may be a smaller list than InstRWDef's "Instrs". 749243830Sdim Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 750243830Sdim SmallSet<unsigned, 4> RemappedClassIDs; 751243830Sdim for (ArrayRef<Record*>::const_iterator 752243830Sdim II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) { 753243830Sdim unsigned OldSCIdx = InstrClassMap[*II]; 754243830Sdim if (OldSCIdx && RemappedClassIDs.insert(OldSCIdx)) { 755243830Sdim for (RecIter RI = SchedClasses[OldSCIdx].InstRWs.begin(), 756243830Sdim RE = SchedClasses[OldSCIdx].InstRWs.end(); RI != RE; ++RI) { 757243830Sdim if ((*RI)->getValueAsDef("SchedModel") == RWModelDef) { 758243830Sdim PrintFatalError(InstRWDef->getLoc(), "Overlapping InstRW def " + 759243830Sdim (*II)->getName() + " also matches " + 760243830Sdim (*RI)->getValue("Instrs")->getValue()->getAsString()); 761243830Sdim } 762243830Sdim assert(*RI != InstRWDef && "SchedClass has duplicate InstRW def"); 763243830Sdim SC.InstRWs.push_back(*RI); 764243830Sdim } 765243830Sdim } 766243830Sdim InstrClassMap[*II] = SCIdx; 767243830Sdim } 768243830Sdim SC.InstRWs.push_back(InstRWDef); 769243830Sdim } 770243830Sdim} 771243830Sdim 772249423Sdim// True if collectProcItins found anything. 773249423Sdimbool CodeGenSchedModels::hasItineraries() const { 774249423Sdim for (CodeGenSchedModels::ProcIter PI = procModelBegin(), PE = procModelEnd(); 775249423Sdim PI != PE; ++PI) { 776249423Sdim if (PI->hasItineraries()) 777249423Sdim return true; 778249423Sdim } 779249423Sdim return false; 780249423Sdim} 781249423Sdim 782243830Sdim// Gather the processor itineraries. 783243830Sdimvoid CodeGenSchedModels::collectProcItins() { 784243830Sdim for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(), 785243830Sdim PE = ProcModels.end(); PI != PE; ++PI) { 786243830Sdim CodeGenProcModel &ProcModel = *PI; 787249423Sdim if (!ProcModel.hasItineraries()) 788243830Sdim continue; 789243830Sdim 790249423Sdim RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID"); 791249423Sdim assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect"); 792243830Sdim 793249423Sdim // Populate ItinDefList with Itinerary records. 794249423Sdim ProcModel.ItinDefList.resize(NumInstrSchedClasses); 795249423Sdim 796243830Sdim // Insert each itinerary data record in the correct position within 797243830Sdim // the processor model's ItinDefList. 798243830Sdim for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) { 799243830Sdim Record *ItinData = ItinRecords[i]; 800243830Sdim Record *ItinDef = ItinData->getValueAsDef("TheClass"); 801249423Sdim bool FoundClass = false; 802249423Sdim for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd(); 803249423Sdim SCI != SCE; ++SCI) { 804249423Sdim // Multiple SchedClasses may share an itinerary. Update all of them. 805249423Sdim if (SCI->ItinClassDef == ItinDef) { 806249423Sdim ProcModel.ItinDefList[SCI->Index] = ItinData; 807249423Sdim FoundClass = true; 808249423Sdim } 809249423Sdim } 810249423Sdim if (!FoundClass) { 811243830Sdim DEBUG(dbgs() << ProcModel.ItinsDef->getName() 812249423Sdim << " missing class for itinerary " << ItinDef->getName() << '\n'); 813243830Sdim } 814243830Sdim } 815243830Sdim // Check for missing itinerary entries. 816243830Sdim assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); 817243830Sdim DEBUG( 818243830Sdim for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { 819243830Sdim if (!ProcModel.ItinDefList[i]) 820243830Sdim dbgs() << ProcModel.ItinsDef->getName() 821243830Sdim << " missing itinerary for class " 822243830Sdim << SchedClasses[i].Name << '\n'; 823243830Sdim }); 824243830Sdim } 825243830Sdim} 826243830Sdim 827243830Sdim// Gather the read/write types for each itinerary class. 828243830Sdimvoid CodeGenSchedModels::collectProcItinRW() { 829243830Sdim RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 830243830Sdim std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord()); 831243830Sdim for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { 832243830Sdim if (!(*II)->getValueInit("SchedModel")->isComplete()) 833243830Sdim PrintFatalError((*II)->getLoc(), "SchedModel is undefined"); 834243830Sdim Record *ModelDef = (*II)->getValueAsDef("SchedModel"); 835243830Sdim ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 836243830Sdim if (I == ProcModelMap.end()) { 837243830Sdim PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel " 838243830Sdim + ModelDef->getName()); 839243830Sdim } 840243830Sdim ProcModels[I->second].ItinRWDefs.push_back(*II); 841243830Sdim } 842243830Sdim} 843243830Sdim 844243830Sdim/// Infer new classes from existing classes. In the process, this may create new 845243830Sdim/// SchedWrites from sequences of existing SchedWrites. 846243830Sdimvoid CodeGenSchedModels::inferSchedClasses() { 847249423Sdim DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n"); 848249423Sdim 849243830Sdim // Visit all existing classes and newly created classes. 850243830Sdim for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) { 851249423Sdim assert(SchedClasses[Idx].Index == Idx && "bad SCIdx"); 852249423Sdim 853243830Sdim if (SchedClasses[Idx].ItinClassDef) 854243830Sdim inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx); 855249423Sdim if (!SchedClasses[Idx].InstRWs.empty()) 856243830Sdim inferFromInstRWs(Idx); 857249423Sdim if (!SchedClasses[Idx].Writes.empty()) { 858243830Sdim inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads, 859243830Sdim Idx, SchedClasses[Idx].ProcIndices); 860243830Sdim } 861243830Sdim assert(SchedClasses.size() < (NumInstrSchedClasses*6) && 862243830Sdim "too many SchedVariants"); 863243830Sdim } 864243830Sdim} 865243830Sdim 866243830Sdim/// Infer classes from per-processor itinerary resources. 867243830Sdimvoid CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef, 868243830Sdim unsigned FromClassIdx) { 869243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 870243830Sdim const CodeGenProcModel &PM = ProcModels[PIdx]; 871243830Sdim // For all ItinRW entries. 872243830Sdim bool HasMatch = false; 873243830Sdim for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 874243830Sdim II != IE; ++II) { 875243830Sdim RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 876243830Sdim if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 877243830Sdim continue; 878243830Sdim if (HasMatch) 879243830Sdim PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 880243830Sdim + ItinClassDef->getName() 881243830Sdim + " in ItinResources for " + PM.ModelName); 882243830Sdim HasMatch = true; 883243830Sdim IdxVec Writes, Reads; 884243830Sdim findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 885243830Sdim IdxVec ProcIndices(1, PIdx); 886243830Sdim inferFromRW(Writes, Reads, FromClassIdx, ProcIndices); 887243830Sdim } 888243830Sdim } 889243830Sdim} 890243830Sdim 891243830Sdim/// Infer classes from per-processor InstReadWrite definitions. 892243830Sdimvoid CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) { 893261991Sdim for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) { 894261991Sdim assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!"); 895261991Sdim Record *Rec = SchedClasses[SCIdx].InstRWs[I]; 896261991Sdim const RecVec *InstDefs = Sets.expand(Rec); 897243830Sdim RecIter II = InstDefs->begin(), IE = InstDefs->end(); 898243830Sdim for (; II != IE; ++II) { 899243830Sdim if (InstrClassMap[*II] == SCIdx) 900243830Sdim break; 901243830Sdim } 902243830Sdim // If this class no longer has any instructions mapped to it, it has become 903243830Sdim // irrelevant. 904243830Sdim if (II == IE) 905243830Sdim continue; 906243830Sdim IdxVec Writes, Reads; 907261991Sdim findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 908261991Sdim unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index; 909243830Sdim IdxVec ProcIndices(1, PIdx); 910261991Sdim inferFromRW(Writes, Reads, SCIdx, ProcIndices); // May mutate SchedClasses. 911243830Sdim } 912243830Sdim} 913243830Sdim 914243830Sdimnamespace { 915243830Sdim// Helper for substituteVariantOperand. 916243830Sdimstruct TransVariant { 917243830Sdim Record *VarOrSeqDef; // Variant or sequence. 918243830Sdim unsigned RWIdx; // Index of this variant or sequence's matched type. 919243830Sdim unsigned ProcIdx; // Processor model index or zero for any. 920243830Sdim unsigned TransVecIdx; // Index into PredTransitions::TransVec. 921243830Sdim 922243830Sdim TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti): 923243830Sdim VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {} 924243830Sdim}; 925243830Sdim 926243830Sdim// Associate a predicate with the SchedReadWrite that it guards. 927243830Sdim// RWIdx is the index of the read/write variant. 928243830Sdimstruct PredCheck { 929243830Sdim bool IsRead; 930243830Sdim unsigned RWIdx; 931243830Sdim Record *Predicate; 932243830Sdim 933243830Sdim PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {} 934243830Sdim}; 935243830Sdim 936243830Sdim// A Predicate transition is a list of RW sequences guarded by a PredTerm. 937243830Sdimstruct PredTransition { 938243830Sdim // A predicate term is a conjunction of PredChecks. 939243830Sdim SmallVector<PredCheck, 4> PredTerm; 940243830Sdim SmallVector<SmallVector<unsigned,4>, 16> WriteSequences; 941243830Sdim SmallVector<SmallVector<unsigned,4>, 16> ReadSequences; 942243830Sdim SmallVector<unsigned, 4> ProcIndices; 943243830Sdim}; 944243830Sdim 945243830Sdim// Encapsulate a set of partially constructed transitions. 946243830Sdim// The results are built by repeated calls to substituteVariants. 947243830Sdimclass PredTransitions { 948243830Sdim CodeGenSchedModels &SchedModels; 949243830Sdim 950243830Sdimpublic: 951243830Sdim std::vector<PredTransition> TransVec; 952243830Sdim 953243830Sdim PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {} 954243830Sdim 955243830Sdim void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq, 956243830Sdim bool IsRead, unsigned StartIdx); 957243830Sdim 958243830Sdim void substituteVariants(const PredTransition &Trans); 959243830Sdim 960243830Sdim#ifndef NDEBUG 961243830Sdim void dump() const; 962243830Sdim#endif 963243830Sdim 964243830Sdimprivate: 965243830Sdim bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term); 966243830Sdim void getIntersectingVariants( 967243830Sdim const CodeGenSchedRW &SchedRW, unsigned TransIdx, 968243830Sdim std::vector<TransVariant> &IntersectingVariants); 969243830Sdim void pushVariant(const TransVariant &VInfo, bool IsRead); 970243830Sdim}; 971243830Sdim} // anonymous 972243830Sdim 973243830Sdim// Return true if this predicate is mutually exclusive with a PredTerm. This 974243830Sdim// degenerates into checking if the predicate is mutually exclusive with any 975243830Sdim// predicate in the Term's conjunction. 976243830Sdim// 977243830Sdim// All predicates associated with a given SchedRW are considered mutually 978243830Sdim// exclusive. This should work even if the conditions expressed by the 979243830Sdim// predicates are not exclusive because the predicates for a given SchedWrite 980243830Sdim// are always checked in the order they are defined in the .td file. Later 981243830Sdim// conditions implicitly negate any prior condition. 982243830Sdimbool PredTransitions::mutuallyExclusive(Record *PredDef, 983243830Sdim ArrayRef<PredCheck> Term) { 984243830Sdim 985243830Sdim for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end(); 986243830Sdim I != E; ++I) { 987243830Sdim if (I->Predicate == PredDef) 988243830Sdim return false; 989243830Sdim 990243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead); 991243830Sdim assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant"); 992243830Sdim RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 993243830Sdim for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) { 994243830Sdim if ((*VI)->getValueAsDef("Predicate") == PredDef) 995243830Sdim return true; 996243830Sdim } 997243830Sdim } 998243830Sdim return false; 999243830Sdim} 1000243830Sdim 1001243830Sdimstatic bool hasAliasedVariants(const CodeGenSchedRW &RW, 1002243830Sdim CodeGenSchedModels &SchedModels) { 1003243830Sdim if (RW.HasVariants) 1004243830Sdim return true; 1005243830Sdim 1006243830Sdim for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) { 1007243830Sdim const CodeGenSchedRW &AliasRW = 1008243830Sdim SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW")); 1009243830Sdim if (AliasRW.HasVariants) 1010243830Sdim return true; 1011243830Sdim if (AliasRW.IsSequence) { 1012243830Sdim IdxVec ExpandedRWs; 1013243830Sdim SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead); 1014243830Sdim for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 1015243830Sdim SI != SE; ++SI) { 1016243830Sdim if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead), 1017243830Sdim SchedModels)) { 1018243830Sdim return true; 1019243830Sdim } 1020243830Sdim } 1021243830Sdim } 1022243830Sdim } 1023243830Sdim return false; 1024243830Sdim} 1025243830Sdim 1026243830Sdimstatic bool hasVariant(ArrayRef<PredTransition> Transitions, 1027243830Sdim CodeGenSchedModels &SchedModels) { 1028243830Sdim for (ArrayRef<PredTransition>::iterator 1029243830Sdim PTI = Transitions.begin(), PTE = Transitions.end(); 1030243830Sdim PTI != PTE; ++PTI) { 1031243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1032243830Sdim WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end(); 1033243830Sdim WSI != WSE; ++WSI) { 1034243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1035243830Sdim WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 1036243830Sdim if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels)) 1037243830Sdim return true; 1038243830Sdim } 1039243830Sdim } 1040243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1041243830Sdim RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end(); 1042243830Sdim RSI != RSE; ++RSI) { 1043243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1044243830Sdim RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) { 1045243830Sdim if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels)) 1046243830Sdim return true; 1047243830Sdim } 1048243830Sdim } 1049243830Sdim } 1050243830Sdim return false; 1051243830Sdim} 1052243830Sdim 1053243830Sdim// Populate IntersectingVariants with any variants or aliased sequences of the 1054243830Sdim// given SchedRW whose processor indices and predicates are not mutually 1055249423Sdim// exclusive with the given transition. 1056243830Sdimvoid PredTransitions::getIntersectingVariants( 1057243830Sdim const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1058243830Sdim std::vector<TransVariant> &IntersectingVariants) { 1059243830Sdim 1060249423Sdim bool GenericRW = false; 1061249423Sdim 1062243830Sdim std::vector<TransVariant> Variants; 1063243830Sdim if (SchedRW.HasVariants) { 1064243830Sdim unsigned VarProcIdx = 0; 1065243830Sdim if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) { 1066243830Sdim Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel"); 1067243830Sdim VarProcIdx = SchedModels.getProcModel(ModelDef).Index; 1068243830Sdim } 1069243830Sdim // Push each variant. Assign TransVecIdx later. 1070243830Sdim const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1071243830Sdim for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI) 1072243830Sdim Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0)); 1073249423Sdim if (VarProcIdx == 0) 1074249423Sdim GenericRW = true; 1075243830Sdim } 1076243830Sdim for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1077243830Sdim AI != AE; ++AI) { 1078243830Sdim // If either the SchedAlias itself or the SchedReadWrite that it aliases 1079243830Sdim // to is defined within a processor model, constrain all variants to 1080243830Sdim // that processor. 1081243830Sdim unsigned AliasProcIdx = 0; 1082243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1083243830Sdim Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 1084243830Sdim AliasProcIdx = SchedModels.getProcModel(ModelDef).Index; 1085243830Sdim } 1086243830Sdim const CodeGenSchedRW &AliasRW = 1087243830Sdim SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW")); 1088243830Sdim 1089243830Sdim if (AliasRW.HasVariants) { 1090243830Sdim const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants"); 1091243830Sdim for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI) 1092243830Sdim Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0)); 1093243830Sdim } 1094243830Sdim if (AliasRW.IsSequence) { 1095243830Sdim Variants.push_back( 1096243830Sdim TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0)); 1097243830Sdim } 1098249423Sdim if (AliasProcIdx == 0) 1099249423Sdim GenericRW = true; 1100243830Sdim } 1101243830Sdim for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) { 1102243830Sdim TransVariant &Variant = Variants[VIdx]; 1103243830Sdim // Don't expand variants if the processor models don't intersect. 1104243830Sdim // A zero processor index means any processor. 1105261991Sdim SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices; 1106243830Sdim if (ProcIndices[0] && Variants[VIdx].ProcIdx) { 1107243830Sdim unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(), 1108243830Sdim Variant.ProcIdx); 1109243830Sdim if (!Cnt) 1110243830Sdim continue; 1111243830Sdim if (Cnt > 1) { 1112243830Sdim const CodeGenProcModel &PM = 1113243830Sdim *(SchedModels.procModelBegin() + Variant.ProcIdx); 1114243830Sdim PrintFatalError(Variant.VarOrSeqDef->getLoc(), 1115243830Sdim "Multiple variants defined for processor " + 1116243830Sdim PM.ModelName + 1117243830Sdim " Ensure only one SchedAlias exists per RW."); 1118243830Sdim } 1119243830Sdim } 1120243830Sdim if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) { 1121243830Sdim Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate"); 1122243830Sdim if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm)) 1123243830Sdim continue; 1124243830Sdim } 1125243830Sdim if (IntersectingVariants.empty()) { 1126243830Sdim // The first variant builds on the existing transition. 1127243830Sdim Variant.TransVecIdx = TransIdx; 1128243830Sdim IntersectingVariants.push_back(Variant); 1129243830Sdim } 1130243830Sdim else { 1131243830Sdim // Push another copy of the current transition for more variants. 1132243830Sdim Variant.TransVecIdx = TransVec.size(); 1133243830Sdim IntersectingVariants.push_back(Variant); 1134243830Sdim TransVec.push_back(TransVec[TransIdx]); 1135243830Sdim } 1136243830Sdim } 1137249423Sdim if (GenericRW && IntersectingVariants.empty()) { 1138249423Sdim PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has " 1139249423Sdim "a matching predicate on any processor"); 1140249423Sdim } 1141243830Sdim} 1142243830Sdim 1143243830Sdim// Push the Reads/Writes selected by this variant onto the PredTransition 1144243830Sdim// specified by VInfo. 1145243830Sdimvoid PredTransitions:: 1146243830SdimpushVariant(const TransVariant &VInfo, bool IsRead) { 1147243830Sdim 1148243830Sdim PredTransition &Trans = TransVec[VInfo.TransVecIdx]; 1149243830Sdim 1150243830Sdim // If this operand transition is reached through a processor-specific alias, 1151243830Sdim // then the whole transition is specific to this processor. 1152243830Sdim if (VInfo.ProcIdx != 0) 1153243830Sdim Trans.ProcIndices.assign(1, VInfo.ProcIdx); 1154243830Sdim 1155243830Sdim IdxVec SelectedRWs; 1156243830Sdim if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) { 1157243830Sdim Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate"); 1158243830Sdim Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef)); 1159243830Sdim RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected"); 1160243830Sdim SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead); 1161243830Sdim } 1162239310Sdim else { 1163243830Sdim assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") && 1164243830Sdim "variant must be a SchedVariant or aliased WriteSequence"); 1165243830Sdim SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead)); 1166239310Sdim } 1167239310Sdim 1168243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead); 1169239310Sdim 1170243830Sdim SmallVectorImpl<SmallVector<unsigned,4> > &RWSequences = IsRead 1171243830Sdim ? Trans.ReadSequences : Trans.WriteSequences; 1172243830Sdim if (SchedRW.IsVariadic) { 1173243830Sdim unsigned OperIdx = RWSequences.size()-1; 1174243830Sdim // Make N-1 copies of this transition's last sequence. 1175243830Sdim for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) { 1176261991Sdim // Create a temporary copy the vector could reallocate. 1177261991Sdim RWSequences.reserve(RWSequences.size() + 1); 1178243830Sdim RWSequences.push_back(RWSequences[OperIdx]); 1179243830Sdim } 1180243830Sdim // Push each of the N elements of the SelectedRWs onto a copy of the last 1181243830Sdim // sequence (split the current operand into N operands). 1182243830Sdim // Note that write sequences should be expanded within this loop--the entire 1183243830Sdim // sequence belongs to a single operand. 1184243830Sdim for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1185243830Sdim RWI != RWE; ++RWI, ++OperIdx) { 1186243830Sdim IdxVec ExpandedRWs; 1187243830Sdim if (IsRead) 1188243830Sdim ExpandedRWs.push_back(*RWI); 1189243830Sdim else 1190243830Sdim SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1191243830Sdim RWSequences[OperIdx].insert(RWSequences[OperIdx].end(), 1192243830Sdim ExpandedRWs.begin(), ExpandedRWs.end()); 1193243830Sdim } 1194243830Sdim assert(OperIdx == RWSequences.size() && "missed a sequence"); 1195243830Sdim } 1196243830Sdim else { 1197243830Sdim // Push this transition's expanded sequence onto this transition's last 1198243830Sdim // sequence (add to the current operand's sequence). 1199243830Sdim SmallVectorImpl<unsigned> &Seq = RWSequences.back(); 1200243830Sdim IdxVec ExpandedRWs; 1201243830Sdim for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1202243830Sdim RWI != RWE; ++RWI) { 1203243830Sdim if (IsRead) 1204243830Sdim ExpandedRWs.push_back(*RWI); 1205243830Sdim else 1206243830Sdim SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1207243830Sdim } 1208243830Sdim Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end()); 1209243830Sdim } 1210243830Sdim} 1211239310Sdim 1212243830Sdim// RWSeq is a sequence of all Reads or all Writes for the next read or write 1213243830Sdim// operand. StartIdx is an index into TransVec where partial results 1214243830Sdim// starts. RWSeq must be applied to all transitions between StartIdx and the end 1215243830Sdim// of TransVec. 1216243830Sdimvoid PredTransitions::substituteVariantOperand( 1217243830Sdim const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) { 1218243830Sdim 1219243830Sdim // Visit each original RW within the current sequence. 1220243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1221243830Sdim RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) { 1222243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead); 1223243830Sdim // Push this RW on all partial PredTransitions or distribute variants. 1224243830Sdim // New PredTransitions may be pushed within this loop which should not be 1225243830Sdim // revisited (TransEnd must be loop invariant). 1226243830Sdim for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size(); 1227243830Sdim TransIdx != TransEnd; ++TransIdx) { 1228243830Sdim // In the common case, push RW onto the current operand's sequence. 1229243830Sdim if (!hasAliasedVariants(SchedRW, SchedModels)) { 1230243830Sdim if (IsRead) 1231243830Sdim TransVec[TransIdx].ReadSequences.back().push_back(*RWI); 1232243830Sdim else 1233243830Sdim TransVec[TransIdx].WriteSequences.back().push_back(*RWI); 1234243830Sdim continue; 1235243830Sdim } 1236243830Sdim // Distribute this partial PredTransition across intersecting variants. 1237243830Sdim // This will push a copies of TransVec[TransIdx] on the back of TransVec. 1238243830Sdim std::vector<TransVariant> IntersectingVariants; 1239243830Sdim getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants); 1240243830Sdim // Now expand each variant on top of its copy of the transition. 1241243830Sdim for (std::vector<TransVariant>::const_iterator 1242243830Sdim IVI = IntersectingVariants.begin(), 1243243830Sdim IVE = IntersectingVariants.end(); 1244243830Sdim IVI != IVE; ++IVI) { 1245243830Sdim pushVariant(*IVI, IsRead); 1246243830Sdim } 1247243830Sdim } 1248243830Sdim } 1249239310Sdim} 1250239310Sdim 1251243830Sdim// For each variant of a Read/Write in Trans, substitute the sequence of 1252243830Sdim// Read/Writes guarded by the variant. This is exponential in the number of 1253243830Sdim// variant Read/Writes, but in practice detection of mutually exclusive 1254243830Sdim// predicates should result in linear growth in the total number variants. 1255243830Sdim// 1256243830Sdim// This is one step in a breadth-first search of nested variants. 1257243830Sdimvoid PredTransitions::substituteVariants(const PredTransition &Trans) { 1258243830Sdim // Build up a set of partial results starting at the back of 1259243830Sdim // PredTransitions. Remember the first new transition. 1260243830Sdim unsigned StartIdx = TransVec.size(); 1261243830Sdim TransVec.resize(TransVec.size() + 1); 1262243830Sdim TransVec.back().PredTerm = Trans.PredTerm; 1263243830Sdim TransVec.back().ProcIndices = Trans.ProcIndices; 1264243830Sdim 1265243830Sdim // Visit each original write sequence. 1266243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1267243830Sdim WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end(); 1268243830Sdim WSI != WSE; ++WSI) { 1269243830Sdim // Push a new (empty) write sequence onto all partial Transitions. 1270243830Sdim for (std::vector<PredTransition>::iterator I = 1271243830Sdim TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1272243830Sdim I->WriteSequences.resize(I->WriteSequences.size() + 1); 1273243830Sdim } 1274243830Sdim substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx); 1275243830Sdim } 1276243830Sdim // Visit each original read sequence. 1277243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1278243830Sdim RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end(); 1279243830Sdim RSI != RSE; ++RSI) { 1280243830Sdim // Push a new (empty) read sequence onto all partial Transitions. 1281243830Sdim for (std::vector<PredTransition>::iterator I = 1282243830Sdim TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1283243830Sdim I->ReadSequences.resize(I->ReadSequences.size() + 1); 1284243830Sdim } 1285243830Sdim substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx); 1286243830Sdim } 1287243830Sdim} 1288243830Sdim 1289243830Sdim// Create a new SchedClass for each variant found by inferFromRW. Pass 1290243830Sdimstatic void inferFromTransitions(ArrayRef<PredTransition> LastTransitions, 1291243830Sdim unsigned FromClassIdx, 1292243830Sdim CodeGenSchedModels &SchedModels) { 1293243830Sdim // For each PredTransition, create a new CodeGenSchedTransition, which usually 1294243830Sdim // requires creating a new SchedClass. 1295243830Sdim for (ArrayRef<PredTransition>::iterator 1296243830Sdim I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) { 1297243830Sdim IdxVec OperWritesVariant; 1298243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1299243830Sdim WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end(); 1300243830Sdim WSI != WSE; ++WSI) { 1301243830Sdim // Create a new write representing the expanded sequence. 1302243830Sdim OperWritesVariant.push_back( 1303243830Sdim SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false)); 1304243830Sdim } 1305243830Sdim IdxVec OperReadsVariant; 1306243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1307243830Sdim RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end(); 1308243830Sdim RSI != RSE; ++RSI) { 1309243830Sdim // Create a new read representing the expanded sequence. 1310243830Sdim OperReadsVariant.push_back( 1311243830Sdim SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true)); 1312243830Sdim } 1313243830Sdim IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end()); 1314243830Sdim CodeGenSchedTransition SCTrans; 1315243830Sdim SCTrans.ToClassIdx = 1316276479Sdim SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant, 1317249423Sdim OperReadsVariant, ProcIndices); 1318243830Sdim SCTrans.ProcIndices = ProcIndices; 1319243830Sdim // The final PredTerm is unique set of predicates guarding the transition. 1320243830Sdim RecVec Preds; 1321243830Sdim for (SmallVectorImpl<PredCheck>::const_iterator 1322243830Sdim PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) { 1323243830Sdim Preds.push_back(PI->Predicate); 1324243830Sdim } 1325243830Sdim RecIter PredsEnd = std::unique(Preds.begin(), Preds.end()); 1326243830Sdim Preds.resize(PredsEnd - Preds.begin()); 1327243830Sdim SCTrans.PredTerm = Preds; 1328243830Sdim SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans); 1329243830Sdim } 1330243830Sdim} 1331243830Sdim 1332243830Sdim// Create new SchedClasses for the given ReadWrite list. If any of the 1333243830Sdim// ReadWrites refers to a SchedVariant, create a new SchedClass for each variant 1334243830Sdim// of the ReadWrite list, following Aliases if necessary. 1335243830Sdimvoid CodeGenSchedModels::inferFromRW(const IdxVec &OperWrites, 1336243830Sdim const IdxVec &OperReads, 1337243830Sdim unsigned FromClassIdx, 1338243830Sdim const IdxVec &ProcIndices) { 1339249423Sdim DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); dbgs() << ") "); 1340243830Sdim 1341243830Sdim // Create a seed transition with an empty PredTerm and the expanded sequences 1342243830Sdim // of SchedWrites for the current SchedClass. 1343243830Sdim std::vector<PredTransition> LastTransitions; 1344243830Sdim LastTransitions.resize(1); 1345243830Sdim LastTransitions.back().ProcIndices.append(ProcIndices.begin(), 1346243830Sdim ProcIndices.end()); 1347243830Sdim 1348243830Sdim for (IdxIter I = OperWrites.begin(), E = OperWrites.end(); I != E; ++I) { 1349243830Sdim IdxVec WriteSeq; 1350243830Sdim expandRWSequence(*I, WriteSeq, /*IsRead=*/false); 1351243830Sdim unsigned Idx = LastTransitions[0].WriteSequences.size(); 1352243830Sdim LastTransitions[0].WriteSequences.resize(Idx + 1); 1353243830Sdim SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx]; 1354243830Sdim for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI) 1355243830Sdim Seq.push_back(*WI); 1356243830Sdim DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1357243830Sdim } 1358243830Sdim DEBUG(dbgs() << " Reads: "); 1359243830Sdim for (IdxIter I = OperReads.begin(), E = OperReads.end(); I != E; ++I) { 1360243830Sdim IdxVec ReadSeq; 1361243830Sdim expandRWSequence(*I, ReadSeq, /*IsRead=*/true); 1362243830Sdim unsigned Idx = LastTransitions[0].ReadSequences.size(); 1363243830Sdim LastTransitions[0].ReadSequences.resize(Idx + 1); 1364243830Sdim SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx]; 1365243830Sdim for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI) 1366243830Sdim Seq.push_back(*RI); 1367243830Sdim DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1368243830Sdim } 1369243830Sdim DEBUG(dbgs() << '\n'); 1370243830Sdim 1371243830Sdim // Collect all PredTransitions for individual operands. 1372243830Sdim // Iterate until no variant writes remain. 1373243830Sdim while (hasVariant(LastTransitions, *this)) { 1374243830Sdim PredTransitions Transitions(*this); 1375243830Sdim for (std::vector<PredTransition>::const_iterator 1376243830Sdim I = LastTransitions.begin(), E = LastTransitions.end(); 1377243830Sdim I != E; ++I) { 1378243830Sdim Transitions.substituteVariants(*I); 1379243830Sdim } 1380243830Sdim DEBUG(Transitions.dump()); 1381243830Sdim LastTransitions.swap(Transitions.TransVec); 1382243830Sdim } 1383243830Sdim // If the first transition has no variants, nothing to do. 1384243830Sdim if (LastTransitions[0].PredTerm.empty()) 1385239310Sdim return; 1386239310Sdim 1387243830Sdim // WARNING: We are about to mutate the SchedClasses vector. Do not refer to 1388243830Sdim // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions. 1389243830Sdim inferFromTransitions(LastTransitions, FromClassIdx, *this); 1390243830Sdim} 1391239310Sdim 1392251662Sdim// Check if any processor resource group contains all resource records in 1393251662Sdim// SubUnits. 1394251662Sdimbool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) { 1395251662Sdim for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1396251662Sdim if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1397251662Sdim continue; 1398251662Sdim RecVec SuperUnits = 1399251662Sdim PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1400251662Sdim RecIter RI = SubUnits.begin(), RE = SubUnits.end(); 1401251662Sdim for ( ; RI != RE; ++RI) { 1402251662Sdim if (std::find(SuperUnits.begin(), SuperUnits.end(), *RI) 1403251662Sdim == SuperUnits.end()) { 1404251662Sdim break; 1405251662Sdim } 1406251662Sdim } 1407251662Sdim if (RI == RE) 1408251662Sdim return true; 1409251662Sdim } 1410251662Sdim return false; 1411251662Sdim} 1412251662Sdim 1413251662Sdim// Verify that overlapping groups have a common supergroup. 1414251662Sdimvoid CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) { 1415251662Sdim for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1416251662Sdim if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1417251662Sdim continue; 1418251662Sdim RecVec CheckUnits = 1419251662Sdim PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1420251662Sdim for (unsigned j = i+1; j < e; ++j) { 1421251662Sdim if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup")) 1422251662Sdim continue; 1423251662Sdim RecVec OtherUnits = 1424251662Sdim PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources"); 1425251662Sdim if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(), 1426251662Sdim OtherUnits.begin(), OtherUnits.end()) 1427251662Sdim != CheckUnits.end()) { 1428251662Sdim // CheckUnits and OtherUnits overlap 1429251662Sdim OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(), 1430251662Sdim CheckUnits.end()); 1431251662Sdim if (!hasSuperGroup(OtherUnits, PM)) { 1432251662Sdim PrintFatalError((PM.ProcResourceDefs[i])->getLoc(), 1433251662Sdim "proc resource group overlaps with " 1434251662Sdim + PM.ProcResourceDefs[j]->getName() 1435251662Sdim + " but no supergroup contains both."); 1436251662Sdim } 1437251662Sdim } 1438251662Sdim } 1439251662Sdim } 1440251662Sdim} 1441251662Sdim 1442243830Sdim// Collect and sort WriteRes, ReadAdvance, and ProcResources. 1443243830Sdimvoid CodeGenSchedModels::collectProcResources() { 1444243830Sdim // Add any subtarget-specific SchedReadWrites that are directly associated 1445243830Sdim // with processor resources. Refer to the parent SchedClass's ProcIndices to 1446243830Sdim // determine which processors they apply to. 1447243830Sdim for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd(); 1448243830Sdim SCI != SCE; ++SCI) { 1449243830Sdim if (SCI->ItinClassDef) 1450243830Sdim collectItinProcResources(SCI->ItinClassDef); 1451249423Sdim else { 1452249423Sdim // This class may have a default ReadWrite list which can be overriden by 1453249423Sdim // InstRW definitions. 1454249423Sdim if (!SCI->InstRWs.empty()) { 1455249423Sdim for (RecIter RWI = SCI->InstRWs.begin(), RWE = SCI->InstRWs.end(); 1456249423Sdim RWI != RWE; ++RWI) { 1457249423Sdim Record *RWModelDef = (*RWI)->getValueAsDef("SchedModel"); 1458249423Sdim IdxVec ProcIndices(1, getProcModel(RWModelDef).Index); 1459249423Sdim IdxVec Writes, Reads; 1460249423Sdim findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), 1461249423Sdim Writes, Reads); 1462249423Sdim collectRWResources(Writes, Reads, ProcIndices); 1463249423Sdim } 1464249423Sdim } 1465243830Sdim collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices); 1466249423Sdim } 1467243830Sdim } 1468243830Sdim // Add resources separately defined by each subtarget. 1469243830Sdim RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes"); 1470243830Sdim for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) { 1471243830Sdim Record *ModelDef = (*WRI)->getValueAsDef("SchedModel"); 1472243830Sdim addWriteRes(*WRI, getProcModel(ModelDef).Index); 1473243830Sdim } 1474276479Sdim RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes"); 1475276479Sdim for (RecIter WRI = SWRDefs.begin(), WRE = SWRDefs.end(); WRI != WRE; ++WRI) { 1476276479Sdim Record *ModelDef = (*WRI)->getValueAsDef("SchedModel"); 1477276479Sdim addWriteRes(*WRI, getProcModel(ModelDef).Index); 1478276479Sdim } 1479243830Sdim RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance"); 1480243830Sdim for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) { 1481243830Sdim Record *ModelDef = (*RAI)->getValueAsDef("SchedModel"); 1482243830Sdim addReadAdvance(*RAI, getProcModel(ModelDef).Index); 1483243830Sdim } 1484276479Sdim RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance"); 1485276479Sdim for (RecIter RAI = SRADefs.begin(), RAE = SRADefs.end(); RAI != RAE; ++RAI) { 1486276479Sdim if ((*RAI)->getValueInit("SchedModel")->isComplete()) { 1487276479Sdim Record *ModelDef = (*RAI)->getValueAsDef("SchedModel"); 1488276479Sdim addReadAdvance(*RAI, getProcModel(ModelDef).Index); 1489276479Sdim } 1490276479Sdim } 1491261991Sdim // Add ProcResGroups that are defined within this processor model, which may 1492261991Sdim // not be directly referenced but may directly specify a buffer size. 1493261991Sdim RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1494261991Sdim for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end(); 1495261991Sdim RI != RE; ++RI) { 1496261991Sdim if (!(*RI)->getValueInit("SchedModel")->isComplete()) 1497261991Sdim continue; 1498261991Sdim CodeGenProcModel &PM = getProcModel((*RI)->getValueAsDef("SchedModel")); 1499261991Sdim RecIter I = std::find(PM.ProcResourceDefs.begin(), 1500261991Sdim PM.ProcResourceDefs.end(), *RI); 1501261991Sdim if (I == PM.ProcResourceDefs.end()) 1502261991Sdim PM.ProcResourceDefs.push_back(*RI); 1503261991Sdim } 1504243830Sdim // Finalize each ProcModel by sorting the record arrays. 1505243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1506243830Sdim CodeGenProcModel &PM = ProcModels[PIdx]; 1507243830Sdim std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(), 1508243830Sdim LessRecord()); 1509243830Sdim std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(), 1510243830Sdim LessRecord()); 1511243830Sdim std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(), 1512243830Sdim LessRecord()); 1513243830Sdim DEBUG( 1514243830Sdim PM.dump(); 1515243830Sdim dbgs() << "WriteResDefs: "; 1516243830Sdim for (RecIter RI = PM.WriteResDefs.begin(), 1517243830Sdim RE = PM.WriteResDefs.end(); RI != RE; ++RI) { 1518243830Sdim if ((*RI)->isSubClassOf("WriteRes")) 1519243830Sdim dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " "; 1520243830Sdim else 1521243830Sdim dbgs() << (*RI)->getName() << " "; 1522243830Sdim } 1523243830Sdim dbgs() << "\nReadAdvanceDefs: "; 1524243830Sdim for (RecIter RI = PM.ReadAdvanceDefs.begin(), 1525243830Sdim RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) { 1526243830Sdim if ((*RI)->isSubClassOf("ReadAdvance")) 1527243830Sdim dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " "; 1528243830Sdim else 1529243830Sdim dbgs() << (*RI)->getName() << " "; 1530243830Sdim } 1531243830Sdim dbgs() << "\nProcResourceDefs: "; 1532243830Sdim for (RecIter RI = PM.ProcResourceDefs.begin(), 1533243830Sdim RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) { 1534243830Sdim dbgs() << (*RI)->getName() << " "; 1535243830Sdim } 1536243830Sdim dbgs() << '\n'); 1537251662Sdim verifyProcResourceGroups(PM); 1538243830Sdim } 1539243830Sdim} 1540239310Sdim 1541243830Sdim// Collect itinerary class resources for each processor. 1542243830Sdimvoid CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) { 1543243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1544243830Sdim const CodeGenProcModel &PM = ProcModels[PIdx]; 1545243830Sdim // For all ItinRW entries. 1546243830Sdim bool HasMatch = false; 1547243830Sdim for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 1548243830Sdim II != IE; ++II) { 1549243830Sdim RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 1550243830Sdim if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 1551243830Sdim continue; 1552243830Sdim if (HasMatch) 1553243830Sdim PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 1554243830Sdim + ItinClassDef->getName() 1555243830Sdim + " in ItinResources for " + PM.ModelName); 1556243830Sdim HasMatch = true; 1557243830Sdim IdxVec Writes, Reads; 1558243830Sdim findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1559243830Sdim IdxVec ProcIndices(1, PIdx); 1560243830Sdim collectRWResources(Writes, Reads, ProcIndices); 1561239310Sdim } 1562239310Sdim } 1563243830Sdim} 1564243830Sdim 1565243830Sdimvoid CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead, 1566243830Sdim const IdxVec &ProcIndices) { 1567243830Sdim const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 1568243830Sdim if (SchedRW.TheDef) { 1569243830Sdim if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) { 1570243830Sdim for (IdxIter PI = ProcIndices.begin(), PE = ProcIndices.end(); 1571243830Sdim PI != PE; ++PI) { 1572243830Sdim addWriteRes(SchedRW.TheDef, *PI); 1573243830Sdim } 1574243830Sdim } 1575243830Sdim else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) { 1576243830Sdim for (IdxIter PI = ProcIndices.begin(), PE = ProcIndices.end(); 1577243830Sdim PI != PE; ++PI) { 1578243830Sdim addReadAdvance(SchedRW.TheDef, *PI); 1579243830Sdim } 1580243830Sdim } 1581243830Sdim } 1582243830Sdim for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1583243830Sdim AI != AE; ++AI) { 1584243830Sdim IdxVec AliasProcIndices; 1585243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1586243830Sdim AliasProcIndices.push_back( 1587243830Sdim getProcModel((*AI)->getValueAsDef("SchedModel")).Index); 1588243830Sdim } 1589243830Sdim else 1590243830Sdim AliasProcIndices = ProcIndices; 1591243830Sdim const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 1592243830Sdim assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes"); 1593243830Sdim 1594243830Sdim IdxVec ExpandedRWs; 1595243830Sdim expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead); 1596243830Sdim for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 1597243830Sdim SI != SE; ++SI) { 1598243830Sdim collectRWResources(*SI, IsRead, AliasProcIndices); 1599243830Sdim } 1600243830Sdim } 1601243830Sdim} 1602243830Sdim 1603243830Sdim// Collect resources for a set of read/write types and processor indices. 1604243830Sdimvoid CodeGenSchedModels::collectRWResources(const IdxVec &Writes, 1605243830Sdim const IdxVec &Reads, 1606243830Sdim const IdxVec &ProcIndices) { 1607243830Sdim 1608243830Sdim for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI) 1609243830Sdim collectRWResources(*WI, /*IsRead=*/false, ProcIndices); 1610243830Sdim 1611243830Sdim for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI) 1612243830Sdim collectRWResources(*RI, /*IsRead=*/true, ProcIndices); 1613243830Sdim} 1614243830Sdim 1615243830Sdim 1616243830Sdim// Find the processor's resource units for this kind of resource. 1617243830SdimRecord *CodeGenSchedModels::findProcResUnits(Record *ProcResKind, 1618243830Sdim const CodeGenProcModel &PM) const { 1619243830Sdim if (ProcResKind->isSubClassOf("ProcResourceUnits")) 1620243830Sdim return ProcResKind; 1621243830Sdim 1622276479Sdim Record *ProcUnitDef = nullptr; 1623243830Sdim RecVec ProcResourceDefs = 1624243830Sdim Records.getAllDerivedDefinitions("ProcResourceUnits"); 1625243830Sdim 1626243830Sdim for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end(); 1627243830Sdim RI != RE; ++RI) { 1628243830Sdim 1629243830Sdim if ((*RI)->getValueAsDef("Kind") == ProcResKind 1630243830Sdim && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) { 1631243830Sdim if (ProcUnitDef) { 1632243830Sdim PrintFatalError((*RI)->getLoc(), 1633243830Sdim "Multiple ProcessorResourceUnits associated with " 1634243830Sdim + ProcResKind->getName()); 1635243830Sdim } 1636243830Sdim ProcUnitDef = *RI; 1637243830Sdim } 1638243830Sdim } 1639249423Sdim RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1640249423Sdim for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end(); 1641249423Sdim RI != RE; ++RI) { 1642249423Sdim 1643249423Sdim if (*RI == ProcResKind 1644249423Sdim && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) { 1645249423Sdim if (ProcUnitDef) { 1646249423Sdim PrintFatalError((*RI)->getLoc(), 1647249423Sdim "Multiple ProcessorResourceUnits associated with " 1648249423Sdim + ProcResKind->getName()); 1649249423Sdim } 1650249423Sdim ProcUnitDef = *RI; 1651249423Sdim } 1652249423Sdim } 1653243830Sdim if (!ProcUnitDef) { 1654243830Sdim PrintFatalError(ProcResKind->getLoc(), 1655243830Sdim "No ProcessorResources associated with " 1656243830Sdim + ProcResKind->getName()); 1657243830Sdim } 1658243830Sdim return ProcUnitDef; 1659243830Sdim} 1660243830Sdim 1661243830Sdim// Iteratively add a resource and its super resources. 1662243830Sdimvoid CodeGenSchedModels::addProcResource(Record *ProcResKind, 1663243830Sdim CodeGenProcModel &PM) { 1664243830Sdim for (;;) { 1665243830Sdim Record *ProcResUnits = findProcResUnits(ProcResKind, PM); 1666243830Sdim 1667243830Sdim // See if this ProcResource is already associated with this processor. 1668243830Sdim RecIter I = std::find(PM.ProcResourceDefs.begin(), 1669243830Sdim PM.ProcResourceDefs.end(), ProcResUnits); 1670243830Sdim if (I != PM.ProcResourceDefs.end()) 1671243830Sdim return; 1672243830Sdim 1673243830Sdim PM.ProcResourceDefs.push_back(ProcResUnits); 1674249423Sdim if (ProcResUnits->isSubClassOf("ProcResGroup")) 1675249423Sdim return; 1676249423Sdim 1677243830Sdim if (!ProcResUnits->getValueInit("Super")->isComplete()) 1678243830Sdim return; 1679243830Sdim 1680243830Sdim ProcResKind = ProcResUnits->getValueAsDef("Super"); 1681243830Sdim } 1682243830Sdim} 1683243830Sdim 1684243830Sdim// Add resources for a SchedWrite to this processor if they don't exist. 1685243830Sdimvoid CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) { 1686243830Sdim assert(PIdx && "don't add resources to an invalid Processor model"); 1687243830Sdim 1688243830Sdim RecVec &WRDefs = ProcModels[PIdx].WriteResDefs; 1689243830Sdim RecIter WRI = std::find(WRDefs.begin(), WRDefs.end(), ProcWriteResDef); 1690243830Sdim if (WRI != WRDefs.end()) 1691243830Sdim return; 1692243830Sdim WRDefs.push_back(ProcWriteResDef); 1693243830Sdim 1694243830Sdim // Visit ProcResourceKinds referenced by the newly discovered WriteRes. 1695243830Sdim RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources"); 1696243830Sdim for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end(); 1697243830Sdim WritePRI != WritePRE; ++WritePRI) { 1698243830Sdim addProcResource(*WritePRI, ProcModels[PIdx]); 1699243830Sdim } 1700243830Sdim} 1701243830Sdim 1702243830Sdim// Add resources for a ReadAdvance to this processor if they don't exist. 1703243830Sdimvoid CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef, 1704243830Sdim unsigned PIdx) { 1705243830Sdim RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs; 1706243830Sdim RecIter I = std::find(RADefs.begin(), RADefs.end(), ProcReadAdvanceDef); 1707243830Sdim if (I != RADefs.end()) 1708243830Sdim return; 1709243830Sdim RADefs.push_back(ProcReadAdvanceDef); 1710243830Sdim} 1711243830Sdim 1712243830Sdimunsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const { 1713243830Sdim RecIter PRPos = std::find(ProcResourceDefs.begin(), ProcResourceDefs.end(), 1714243830Sdim PRDef); 1715243830Sdim if (PRPos == ProcResourceDefs.end()) 1716243830Sdim PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in " 1717243830Sdim "the ProcResources list for " + ModelName); 1718243830Sdim // Idx=0 is reserved for invalid. 1719243830Sdim return 1 + (PRPos - ProcResourceDefs.begin()); 1720243830Sdim} 1721243830Sdim 1722239310Sdim#ifndef NDEBUG 1723243830Sdimvoid CodeGenProcModel::dump() const { 1724243830Sdim dbgs() << Index << ": " << ModelName << " " 1725243830Sdim << (ModelDef ? ModelDef->getName() : "inferred") << " " 1726243830Sdim << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n'; 1727243830Sdim} 1728243830Sdim 1729243830Sdimvoid CodeGenSchedRW::dump() const { 1730243830Sdim dbgs() << Name << (IsVariadic ? " (V) " : " "); 1731243830Sdim if (IsSequence) { 1732243830Sdim dbgs() << "("; 1733243830Sdim dumpIdxVec(Sequence); 1734243830Sdim dbgs() << ")"; 1735239310Sdim } 1736239310Sdim} 1737243830Sdim 1738243830Sdimvoid CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const { 1739249423Sdim dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n' 1740243830Sdim << " Writes: "; 1741243830Sdim for (unsigned i = 0, N = Writes.size(); i < N; ++i) { 1742243830Sdim SchedModels->getSchedWrite(Writes[i]).dump(); 1743243830Sdim if (i < N-1) { 1744243830Sdim dbgs() << '\n'; 1745243830Sdim dbgs().indent(10); 1746243830Sdim } 1747243830Sdim } 1748243830Sdim dbgs() << "\n Reads: "; 1749243830Sdim for (unsigned i = 0, N = Reads.size(); i < N; ++i) { 1750243830Sdim SchedModels->getSchedRead(Reads[i]).dump(); 1751243830Sdim if (i < N-1) { 1752243830Sdim dbgs() << '\n'; 1753243830Sdim dbgs().indent(10); 1754243830Sdim } 1755243830Sdim } 1756243830Sdim dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n'; 1757249423Sdim if (!Transitions.empty()) { 1758249423Sdim dbgs() << "\n Transitions for Proc "; 1759249423Sdim for (std::vector<CodeGenSchedTransition>::const_iterator 1760249423Sdim TI = Transitions.begin(), TE = Transitions.end(); TI != TE; ++TI) { 1761249423Sdim dumpIdxVec(TI->ProcIndices); 1762249423Sdim } 1763249423Sdim } 1764243830Sdim} 1765243830Sdim 1766243830Sdimvoid PredTransitions::dump() const { 1767243830Sdim dbgs() << "Expanded Variants:\n"; 1768243830Sdim for (std::vector<PredTransition>::const_iterator 1769243830Sdim TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) { 1770243830Sdim dbgs() << "{"; 1771243830Sdim for (SmallVectorImpl<PredCheck>::const_iterator 1772243830Sdim PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end(); 1773243830Sdim PCI != PCE; ++PCI) { 1774243830Sdim if (PCI != TI->PredTerm.begin()) 1775243830Sdim dbgs() << ", "; 1776243830Sdim dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name 1777243830Sdim << ":" << PCI->Predicate->getName(); 1778243830Sdim } 1779243830Sdim dbgs() << "},\n => {"; 1780243830Sdim for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator 1781243830Sdim WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end(); 1782243830Sdim WSI != WSE; ++WSI) { 1783243830Sdim dbgs() << "("; 1784243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1785243830Sdim WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 1786243830Sdim if (WI != WSI->begin()) 1787243830Sdim dbgs() << ", "; 1788243830Sdim dbgs() << SchedModels.getSchedWrite(*WI).Name; 1789243830Sdim } 1790243830Sdim dbgs() << "),"; 1791243830Sdim } 1792243830Sdim dbgs() << "}\n"; 1793243830Sdim } 1794243830Sdim} 1795243830Sdim#endif // NDEBUG 1796