CodeGenSchedule.cpp revision 321369
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 15314564Sdim#include "CodeGenInstruction.h" 16239310Sdim#include "CodeGenSchedule.h" 17239310Sdim#include "CodeGenTarget.h" 18314564Sdim#include "llvm/ADT/SmallPtrSet.h" 19314564Sdim#include "llvm/ADT/SmallSet.h" 20314564Sdim#include "llvm/ADT/SmallVector.h" 21249423Sdim#include "llvm/ADT/STLExtras.h" 22314564Sdim#include "llvm/Support/Casting.h" 23239310Sdim#include "llvm/Support/Debug.h" 24314564Sdim#include "llvm/Support/raw_ostream.h" 25243830Sdim#include "llvm/Support/Regex.h" 26249423Sdim#include "llvm/TableGen/Error.h" 27314564Sdim#include <algorithm> 28314564Sdim#include <iterator> 29314564Sdim#include <utility> 30239310Sdim 31239310Sdimusing namespace llvm; 32239310Sdim 33276479Sdim#define DEBUG_TYPE "subtarget-emitter" 34276479Sdim 35243830Sdim#ifndef NDEBUG 36296417Sdimstatic void dumpIdxVec(ArrayRef<unsigned> V) { 37296417Sdim for (unsigned Idx : V) 38296417Sdim dbgs() << Idx << ", "; 39243830Sdim} 40243830Sdim#endif 41243830Sdim 42261991Sdimnamespace { 43314564Sdim 44243830Sdim// (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp. 45243830Sdimstruct InstrsOp : public SetTheory::Operator { 46276479Sdim void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 47276479Sdim ArrayRef<SMLoc> Loc) override { 48243830Sdim ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc); 49243830Sdim } 50243830Sdim}; 51243830Sdim 52243830Sdim// (instregex "OpcPat",...) Find all instructions matching an opcode pattern. 53243830Sdim// 54243830Sdim// TODO: Since this is a prefix match, perform a binary search over the 55243830Sdim// instruction names using lower_bound. Note that the predefined instrs must be 56243830Sdim// scanned linearly first. However, this is only safe if the regex pattern has 57243830Sdim// no top-level bars. The DAG already has a list of patterns, so there's no 58243830Sdim// reason to use top-level bars, but we need a way to verify they don't exist 59243830Sdim// before implementing the optimization. 60243830Sdimstruct InstRegexOp : public SetTheory::Operator { 61243830Sdim const CodeGenTarget &Target; 62243830Sdim InstRegexOp(const CodeGenTarget &t): Target(t) {} 63243830Sdim 64243830Sdim void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 65276479Sdim ArrayRef<SMLoc> Loc) override { 66276479Sdim SmallVector<Regex, 4> RegexList; 67243830Sdim for (DagInit::const_arg_iterator 68243830Sdim AI = Expr->arg_begin(), AE = Expr->arg_end(); AI != AE; ++AI) { 69243830Sdim StringInit *SI = dyn_cast<StringInit>(*AI); 70243830Sdim if (!SI) 71243830Sdim PrintFatalError(Loc, "instregex requires pattern string: " 72243830Sdim + Expr->getAsString()); 73243830Sdim std::string pat = SI->getValue(); 74243830Sdim // Implement a python-style prefix match. 75243830Sdim if (pat[0] != '^') { 76243830Sdim pat.insert(0, "^("); 77243830Sdim pat.insert(pat.end(), ')'); 78243830Sdim } 79276479Sdim RegexList.push_back(Regex(pat)); 80243830Sdim } 81309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 82276479Sdim for (auto &R : RegexList) { 83280031Sdim if (R.match(Inst->TheDef->getName())) 84280031Sdim Elts.insert(Inst->TheDef); 85243830Sdim } 86243830Sdim } 87243830Sdim } 88243830Sdim}; 89314564Sdim 90261991Sdim} // end anonymous namespace 91243830Sdim 92243830Sdim/// CodeGenModels ctor interprets machine model records and populates maps. 93239310SdimCodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK, 94239310Sdim const CodeGenTarget &TGT): 95249423Sdim Records(RK), Target(TGT) { 96239310Sdim 97243830Sdim Sets.addFieldExpander("InstRW", "Instrs"); 98239310Sdim 99243830Sdim // Allow Set evaluation to recognize the dags used in InstRW records: 100243830Sdim // (instrs Op1, Op1...) 101288943Sdim Sets.addOperator("instrs", llvm::make_unique<InstrsOp>()); 102288943Sdim Sets.addOperator("instregex", llvm::make_unique<InstRegexOp>(Target)); 103243830Sdim 104243830Sdim // Instantiate a CodeGenProcModel for each SchedMachineModel with the values 105243830Sdim // that are explicitly referenced in tablegen records. Resources associated 106243830Sdim // with each processor will be derived later. Populate ProcModelMap with the 107243830Sdim // CodeGenProcModel instances. 108243830Sdim collectProcModels(); 109243830Sdim 110243830Sdim // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly 111243830Sdim // defined, and populate SchedReads and SchedWrites vectors. Implicit 112243830Sdim // SchedReadWrites that represent sequences derived from expanded variant will 113243830Sdim // be inferred later. 114243830Sdim collectSchedRW(); 115243830Sdim 116243830Sdim // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly 117243830Sdim // required by an instruction definition, and populate SchedClassIdxMap. Set 118243830Sdim // NumItineraryClasses to the number of explicit itinerary classes referenced 119243830Sdim // by instructions. Set NumInstrSchedClasses to the number of itinerary 120243830Sdim // classes plus any classes implied by instructions that derive from class 121243830Sdim // Sched and provide SchedRW list. This does not infer any new classes from 122243830Sdim // SchedVariant. 123243830Sdim collectSchedClasses(); 124243830Sdim 125243830Sdim // Find instruction itineraries for each processor. Sort and populate 126243830Sdim // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires 127243830Sdim // all itinerary classes to be discovered. 128243830Sdim collectProcItins(); 129243830Sdim 130243830Sdim // Find ItinRW records for each processor and itinerary class. 131243830Sdim // (For per-operand resources mapped to itinerary classes). 132243830Sdim collectProcItinRW(); 133243830Sdim 134309124Sdim // Find UnsupportedFeatures records for each processor. 135309124Sdim // (For per-operand resources mapped to itinerary classes). 136309124Sdim collectProcUnsupportedFeatures(); 137309124Sdim 138243830Sdim // Infer new SchedClasses from SchedVariant. 139243830Sdim inferSchedClasses(); 140243830Sdim 141243830Sdim // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and 142243830Sdim // ProcResourceDefs. 143321369Sdim DEBUG(dbgs() << "\n+++ RESOURCE DEFINITIONS (collectProcResources) +++\n"); 144243830Sdim collectProcResources(); 145309124Sdim 146309124Sdim checkCompleteness(); 147239310Sdim} 148239310Sdim 149243830Sdim/// Gather all processor models. 150243830Sdimvoid CodeGenSchedModels::collectProcModels() { 151243830Sdim RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor"); 152243830Sdim std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName()); 153239310Sdim 154243830Sdim // Reserve space because we can. Reallocation would be ok. 155243830Sdim ProcModels.reserve(ProcRecords.size()+1); 156243830Sdim 157243830Sdim // Use idx=0 for NoModel/NoItineraries. 158243830Sdim Record *NoModelDef = Records.getDef("NoSchedModel"); 159243830Sdim Record *NoItinsDef = Records.getDef("NoItineraries"); 160288943Sdim ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef); 161243830Sdim ProcModelMap[NoModelDef] = 0; 162243830Sdim 163243830Sdim // For each processor, find a unique machine model. 164321369Sdim DEBUG(dbgs() << "+++ PROCESSOR MODELs (addProcModel) +++\n"); 165243830Sdim for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i) 166243830Sdim addProcModel(ProcRecords[i]); 167243830Sdim} 168243830Sdim 169243830Sdim/// Get a unique processor model based on the defined MachineModel and 170243830Sdim/// ProcessorItineraries. 171243830Sdimvoid CodeGenSchedModels::addProcModel(Record *ProcDef) { 172243830Sdim Record *ModelKey = getModelOrItinDef(ProcDef); 173243830Sdim if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second) 174243830Sdim return; 175243830Sdim 176243830Sdim std::string Name = ModelKey->getName(); 177243830Sdim if (ModelKey->isSubClassOf("SchedMachineModel")) { 178243830Sdim Record *ItinsDef = ModelKey->getValueAsDef("Itineraries"); 179288943Sdim ProcModels.emplace_back(ProcModels.size(), Name, ModelKey, ItinsDef); 180243830Sdim } 181243830Sdim else { 182243830Sdim // An itinerary is defined without a machine model. Infer a new model. 183243830Sdim if (!ModelKey->getValueAsListOfDefs("IID").empty()) 184243830Sdim Name = Name + "Model"; 185288943Sdim ProcModels.emplace_back(ProcModels.size(), Name, 186288943Sdim ProcDef->getValueAsDef("SchedModel"), ModelKey); 187243830Sdim } 188243830Sdim DEBUG(ProcModels.back().dump()); 189243830Sdim} 190243830Sdim 191243830Sdim// Recursively find all reachable SchedReadWrite records. 192243830Sdimstatic void scanSchedRW(Record *RWDef, RecVec &RWDefs, 193243830Sdim SmallPtrSet<Record*, 16> &RWSet) { 194280031Sdim if (!RWSet.insert(RWDef).second) 195243830Sdim return; 196243830Sdim RWDefs.push_back(RWDef); 197243830Sdim // Reads don't current have sequence records, but it can be added later. 198243830Sdim if (RWDef->isSubClassOf("WriteSequence")) { 199243830Sdim RecVec Seq = RWDef->getValueAsListOfDefs("Writes"); 200243830Sdim for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I) 201243830Sdim scanSchedRW(*I, RWDefs, RWSet); 202243830Sdim } 203243830Sdim else if (RWDef->isSubClassOf("SchedVariant")) { 204243830Sdim // Visit each variant (guarded by a different predicate). 205243830Sdim RecVec Vars = RWDef->getValueAsListOfDefs("Variants"); 206243830Sdim for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) { 207243830Sdim // Visit each RW in the sequence selected by the current variant. 208243830Sdim RecVec Selected = (*VI)->getValueAsListOfDefs("Selected"); 209243830Sdim for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I) 210243830Sdim scanSchedRW(*I, RWDefs, RWSet); 211243830Sdim } 212243830Sdim } 213243830Sdim} 214243830Sdim 215243830Sdim// Collect and sort all SchedReadWrites reachable via tablegen records. 216243830Sdim// More may be inferred later when inferring new SchedClasses from variants. 217243830Sdimvoid CodeGenSchedModels::collectSchedRW() { 218243830Sdim // Reserve idx=0 for invalid writes/reads. 219243830Sdim SchedWrites.resize(1); 220243830Sdim SchedReads.resize(1); 221243830Sdim 222243830Sdim SmallPtrSet<Record*, 16> RWSet; 223243830Sdim 224243830Sdim // Find all SchedReadWrites referenced by instruction defs. 225243830Sdim RecVec SWDefs, SRDefs; 226309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 227280031Sdim Record *SchedDef = Inst->TheDef; 228249423Sdim if (SchedDef->isValueUnset("SchedRW")) 229243830Sdim continue; 230243830Sdim RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW"); 231243830Sdim for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) { 232243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 233243830Sdim scanSchedRW(*RWI, SWDefs, RWSet); 234243830Sdim else { 235243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 236243830Sdim scanSchedRW(*RWI, SRDefs, RWSet); 237243830Sdim } 238243830Sdim } 239243830Sdim } 240243830Sdim // Find all ReadWrites referenced by InstRW. 241243830Sdim RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 242243830Sdim for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) { 243243830Sdim // For all OperandReadWrites. 244243830Sdim RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites"); 245243830Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 246243830Sdim RWI != RWE; ++RWI) { 247243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 248243830Sdim scanSchedRW(*RWI, SWDefs, RWSet); 249243830Sdim else { 250243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 251243830Sdim scanSchedRW(*RWI, SRDefs, RWSet); 252243830Sdim } 253243830Sdim } 254243830Sdim } 255243830Sdim // Find all ReadWrites referenced by ItinRW. 256243830Sdim RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 257243830Sdim for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { 258243830Sdim // For all OperandReadWrites. 259243830Sdim RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites"); 260243830Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 261243830Sdim RWI != RWE; ++RWI) { 262243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 263243830Sdim scanSchedRW(*RWI, SWDefs, RWSet); 264243830Sdim else { 265243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 266243830Sdim scanSchedRW(*RWI, SRDefs, RWSet); 267243830Sdim } 268243830Sdim } 269243830Sdim } 270243830Sdim // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted 271243830Sdim // for the loop below that initializes Alias vectors. 272243830Sdim RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias"); 273243830Sdim std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord()); 274243830Sdim for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) { 275243830Sdim Record *MatchDef = (*AI)->getValueAsDef("MatchRW"); 276243830Sdim Record *AliasDef = (*AI)->getValueAsDef("AliasRW"); 277243830Sdim if (MatchDef->isSubClassOf("SchedWrite")) { 278243830Sdim if (!AliasDef->isSubClassOf("SchedWrite")) 279243830Sdim PrintFatalError((*AI)->getLoc(), "SchedWrite Alias must be SchedWrite"); 280243830Sdim scanSchedRW(AliasDef, SWDefs, RWSet); 281243830Sdim } 282243830Sdim else { 283243830Sdim assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 284243830Sdim if (!AliasDef->isSubClassOf("SchedRead")) 285243830Sdim PrintFatalError((*AI)->getLoc(), "SchedRead Alias must be SchedRead"); 286243830Sdim scanSchedRW(AliasDef, SRDefs, RWSet); 287243830Sdim } 288243830Sdim } 289243830Sdim // Sort and add the SchedReadWrites directly referenced by instructions or 290243830Sdim // itinerary resources. Index reads and writes in separate domains. 291243830Sdim std::sort(SWDefs.begin(), SWDefs.end(), LessRecord()); 292243830Sdim for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) { 293243830Sdim assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite"); 294288943Sdim SchedWrites.emplace_back(SchedWrites.size(), *SWI); 295243830Sdim } 296243830Sdim std::sort(SRDefs.begin(), SRDefs.end(), LessRecord()); 297243830Sdim for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) { 298243830Sdim assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite"); 299288943Sdim SchedReads.emplace_back(SchedReads.size(), *SRI); 300243830Sdim } 301243830Sdim // Initialize WriteSequence vectors. 302243830Sdim for (std::vector<CodeGenSchedRW>::iterator WI = SchedWrites.begin(), 303243830Sdim WE = SchedWrites.end(); WI != WE; ++WI) { 304243830Sdim if (!WI->IsSequence) 305243830Sdim continue; 306243830Sdim findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence, 307243830Sdim /*IsRead=*/false); 308243830Sdim } 309243830Sdim // Initialize Aliases vectors. 310243830Sdim for (RecIter AI = AliasDefs.begin(), AE = AliasDefs.end(); AI != AE; ++AI) { 311243830Sdim Record *AliasDef = (*AI)->getValueAsDef("AliasRW"); 312243830Sdim getSchedRW(AliasDef).IsAlias = true; 313243830Sdim Record *MatchDef = (*AI)->getValueAsDef("MatchRW"); 314243830Sdim CodeGenSchedRW &RW = getSchedRW(MatchDef); 315243830Sdim if (RW.IsAlias) 316243830Sdim PrintFatalError((*AI)->getLoc(), "Cannot Alias an Alias"); 317243830Sdim RW.Aliases.push_back(*AI); 318243830Sdim } 319243830Sdim DEBUG( 320321369Sdim dbgs() << "\n+++ SCHED READS and WRITES (collectSchedRW) +++\n"; 321243830Sdim for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) { 322243830Sdim dbgs() << WIdx << ": "; 323243830Sdim SchedWrites[WIdx].dump(); 324243830Sdim dbgs() << '\n'; 325243830Sdim } 326243830Sdim for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) { 327243830Sdim dbgs() << RIdx << ": "; 328243830Sdim SchedReads[RIdx].dump(); 329243830Sdim dbgs() << '\n'; 330243830Sdim } 331243830Sdim RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite"); 332243830Sdim for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); 333243830Sdim RI != RE; ++RI) { 334243830Sdim if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) { 335243830Sdim const std::string &Name = (*RI)->getName(); 336243830Sdim if (Name != "NoWrite" && Name != "ReadDefault") 337243830Sdim dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n'; 338243830Sdim } 339243830Sdim }); 340243830Sdim} 341243830Sdim 342243830Sdim/// Compute a SchedWrite name from a sequence of writes. 343296417Sdimstd::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) { 344243830Sdim std::string Name("("); 345296417Sdim for (auto I = Seq.begin(), E = Seq.end(); I != E; ++I) { 346243830Sdim if (I != Seq.begin()) 347243830Sdim Name += '_'; 348243830Sdim Name += getSchedRW(*I, IsRead).Name; 349243830Sdim } 350243830Sdim Name += ')'; 351243830Sdim return Name; 352243830Sdim} 353243830Sdim 354243830Sdimunsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead, 355243830Sdim unsigned After) const { 356243830Sdim const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 357243830Sdim assert(After < RWVec.size() && "start position out of bounds"); 358243830Sdim for (std::vector<CodeGenSchedRW>::const_iterator I = RWVec.begin() + After, 359243830Sdim E = RWVec.end(); I != E; ++I) { 360243830Sdim if (I->TheDef == Def) 361243830Sdim return I - RWVec.begin(); 362243830Sdim } 363243830Sdim return 0; 364243830Sdim} 365243830Sdim 366243830Sdimbool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const { 367243830Sdim for (unsigned i = 0, e = SchedReads.size(); i < e; ++i) { 368243830Sdim Record *ReadDef = SchedReads[i].TheDef; 369243830Sdim if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance")) 370243830Sdim continue; 371243830Sdim 372243830Sdim RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites"); 373314564Sdim if (is_contained(ValidWrites, WriteDef)) { 374243830Sdim return true; 375243830Sdim } 376243830Sdim } 377243830Sdim return false; 378243830Sdim} 379243830Sdim 380243830Sdimnamespace llvm { 381314564Sdim 382243830Sdimvoid splitSchedReadWrites(const RecVec &RWDefs, 383243830Sdim RecVec &WriteDefs, RecVec &ReadDefs) { 384243830Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) { 385243830Sdim if ((*RWI)->isSubClassOf("SchedWrite")) 386243830Sdim WriteDefs.push_back(*RWI); 387243830Sdim else { 388243830Sdim assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite"); 389243830Sdim ReadDefs.push_back(*RWI); 390243830Sdim } 391243830Sdim } 392243830Sdim} 393243830Sdim 394314564Sdim} // end namespace llvm 395314564Sdim 396243830Sdim// Split the SchedReadWrites defs and call findRWs for each list. 397243830Sdimvoid CodeGenSchedModels::findRWs(const RecVec &RWDefs, 398243830Sdim IdxVec &Writes, IdxVec &Reads) const { 399243830Sdim RecVec WriteDefs; 400243830Sdim RecVec ReadDefs; 401243830Sdim splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs); 402243830Sdim findRWs(WriteDefs, Writes, false); 403243830Sdim findRWs(ReadDefs, Reads, true); 404243830Sdim} 405243830Sdim 406243830Sdim// Call getSchedRWIdx for all elements in a sequence of SchedRW defs. 407243830Sdimvoid CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs, 408243830Sdim bool IsRead) const { 409243830Sdim for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) { 410243830Sdim unsigned Idx = getSchedRWIdx(*RI, IsRead); 411243830Sdim assert(Idx && "failed to collect SchedReadWrite"); 412243830Sdim RWs.push_back(Idx); 413243830Sdim } 414243830Sdim} 415243830Sdim 416243830Sdimvoid CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, 417243830Sdim bool IsRead) const { 418243830Sdim const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 419243830Sdim if (!SchedRW.IsSequence) { 420243830Sdim RWSeq.push_back(RWIdx); 421243830Sdim return; 422243830Sdim } 423243830Sdim int Repeat = 424243830Sdim SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1; 425243830Sdim for (int i = 0; i < Repeat; ++i) { 426243830Sdim for (IdxIter I = SchedRW.Sequence.begin(), E = SchedRW.Sequence.end(); 427243830Sdim I != E; ++I) { 428243830Sdim expandRWSequence(*I, RWSeq, IsRead); 429243830Sdim } 430243830Sdim } 431243830Sdim} 432243830Sdim 433243830Sdim// Expand a SchedWrite as a sequence following any aliases that coincide with 434243830Sdim// the given processor model. 435243830Sdimvoid CodeGenSchedModels::expandRWSeqForProc( 436243830Sdim unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 437243830Sdim const CodeGenProcModel &ProcModel) const { 438243830Sdim 439243830Sdim const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead); 440276479Sdim Record *AliasDef = nullptr; 441243830Sdim for (RecIter AI = SchedWrite.Aliases.begin(), AE = SchedWrite.Aliases.end(); 442243830Sdim AI != AE; ++AI) { 443243830Sdim const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 444243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 445243830Sdim Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 446243830Sdim if (&getProcModel(ModelDef) != &ProcModel) 447243830Sdim continue; 448243830Sdim } 449243830Sdim if (AliasDef) 450243830Sdim PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases " 451243830Sdim "defined for processor " + ProcModel.ModelName + 452243830Sdim " Ensure only one SchedAlias exists per RW."); 453243830Sdim AliasDef = AliasRW.TheDef; 454243830Sdim } 455243830Sdim if (AliasDef) { 456243830Sdim expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead), 457243830Sdim RWSeq, IsRead,ProcModel); 458243830Sdim return; 459243830Sdim } 460243830Sdim if (!SchedWrite.IsSequence) { 461243830Sdim RWSeq.push_back(RWIdx); 462243830Sdim return; 463243830Sdim } 464243830Sdim int Repeat = 465243830Sdim SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1; 466243830Sdim for (int i = 0; i < Repeat; ++i) { 467243830Sdim for (IdxIter I = SchedWrite.Sequence.begin(), E = SchedWrite.Sequence.end(); 468243830Sdim I != E; ++I) { 469243830Sdim expandRWSeqForProc(*I, RWSeq, IsRead, ProcModel); 470243830Sdim } 471243830Sdim } 472243830Sdim} 473243830Sdim 474243830Sdim// Find the existing SchedWrite that models this sequence of writes. 475296417Sdimunsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq, 476243830Sdim bool IsRead) { 477243830Sdim std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 478243830Sdim 479243830Sdim for (std::vector<CodeGenSchedRW>::iterator I = RWVec.begin(), E = RWVec.end(); 480243830Sdim I != E; ++I) { 481296417Sdim if (makeArrayRef(I->Sequence) == Seq) 482243830Sdim return I - RWVec.begin(); 483243830Sdim } 484243830Sdim // Index zero reserved for invalid RW. 485243830Sdim return 0; 486243830Sdim} 487243830Sdim 488243830Sdim/// Add this ReadWrite if it doesn't already exist. 489243830Sdimunsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq, 490243830Sdim bool IsRead) { 491243830Sdim assert(!Seq.empty() && "cannot insert empty sequence"); 492243830Sdim if (Seq.size() == 1) 493243830Sdim return Seq.back(); 494243830Sdim 495243830Sdim unsigned Idx = findRWForSequence(Seq, IsRead); 496243830Sdim if (Idx) 497243830Sdim return Idx; 498243830Sdim 499243830Sdim unsigned RWIdx = IsRead ? SchedReads.size() : SchedWrites.size(); 500243830Sdim CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead)); 501243830Sdim if (IsRead) 502243830Sdim SchedReads.push_back(SchedRW); 503243830Sdim else 504243830Sdim SchedWrites.push_back(SchedRW); 505243830Sdim return RWIdx; 506243830Sdim} 507243830Sdim 508243830Sdim/// Visit all the instruction definitions for this target to gather and 509243830Sdim/// enumerate the itinerary classes. These are the explicitly specified 510243830Sdim/// SchedClasses. More SchedClasses may be inferred. 511243830Sdimvoid CodeGenSchedModels::collectSchedClasses() { 512243830Sdim 513243830Sdim // NoItinerary is always the first class at Idx=0 514239310Sdim SchedClasses.resize(1); 515249423Sdim SchedClasses.back().Index = 0; 516249423Sdim SchedClasses.back().Name = "NoInstrModel"; 517249423Sdim SchedClasses.back().ItinClassDef = Records.getDef("NoItinerary"); 518243830Sdim SchedClasses.back().ProcIndices.push_back(0); 519239310Sdim 520249423Sdim // Create a SchedClass for each unique combination of itinerary class and 521249423Sdim // SchedRW list. 522309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 523280031Sdim Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary"); 524243830Sdim IdxVec Writes, Reads; 525280031Sdim if (!Inst->TheDef->isValueUnset("SchedRW")) 526280031Sdim findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); 527249423Sdim 528243830Sdim // ProcIdx == 0 indicates the class applies to all processors. 529243830Sdim IdxVec ProcIndices(1, 0); 530249423Sdim 531249423Sdim unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, ProcIndices); 532280031Sdim InstrClassMap[Inst->TheDef] = SCIdx; 533243830Sdim } 534243830Sdim // Create classes for InstRW defs. 535243830Sdim RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 536243830Sdim std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord()); 537321369Sdim DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n"); 538243830Sdim for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) 539243830Sdim createInstRWClass(*OI); 540239310Sdim 541243830Sdim NumInstrSchedClasses = SchedClasses.size(); 542243830Sdim 543243830Sdim bool EnableDump = false; 544243830Sdim DEBUG(EnableDump = true); 545243830Sdim if (!EnableDump) 546243830Sdim return; 547249423Sdim 548321369Sdim dbgs() << "\n+++ ITINERARIES and/or MACHINE MODELS (collectSchedClasses) +++\n"; 549309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 550321369Sdim StringRef InstName = Inst->TheDef->getName(); 551280031Sdim unsigned SCIdx = InstrClassMap.lookup(Inst->TheDef); 552249423Sdim if (!SCIdx) { 553309124Sdim if (!Inst->hasNoSchedulingInfo) 554309124Sdim dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n'; 555249423Sdim continue; 556249423Sdim } 557249423Sdim CodeGenSchedClass &SC = getSchedClass(SCIdx); 558249423Sdim if (SC.ProcIndices[0] != 0) 559280031Sdim PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class " 560249423Sdim "must not be subtarget specific."); 561249423Sdim 562249423Sdim IdxVec ProcIndices; 563249423Sdim if (SC.ItinClassDef->getName() != "NoItinerary") { 564249423Sdim ProcIndices.push_back(0); 565249423Sdim dbgs() << "Itinerary for " << InstName << ": " 566249423Sdim << SC.ItinClassDef->getName() << '\n'; 567249423Sdim } 568249423Sdim if (!SC.Writes.empty()) { 569249423Sdim ProcIndices.push_back(0); 570249423Sdim dbgs() << "SchedRW machine model for " << InstName; 571249423Sdim for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE; ++WI) 572249423Sdim dbgs() << " " << SchedWrites[*WI].Name; 573249423Sdim for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI) 574249423Sdim dbgs() << " " << SchedReads[*RI].Name; 575249423Sdim dbgs() << '\n'; 576249423Sdim } 577249423Sdim const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs; 578249423Sdim for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); 579249423Sdim RWI != RWE; ++RWI) { 580249423Sdim const CodeGenProcModel &ProcModel = 581249423Sdim getProcModel((*RWI)->getValueAsDef("SchedModel")); 582249423Sdim ProcIndices.push_back(ProcModel.Index); 583249423Sdim dbgs() << "InstRW on " << ProcModel.ModelName << " for " << InstName; 584243830Sdim IdxVec Writes; 585243830Sdim IdxVec Reads; 586249423Sdim findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), 587249423Sdim Writes, Reads); 588243830Sdim for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI) 589243830Sdim dbgs() << " " << SchedWrites[*WI].Name; 590243830Sdim for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI) 591243830Sdim dbgs() << " " << SchedReads[*RI].Name; 592243830Sdim dbgs() << '\n'; 593243830Sdim } 594314564Sdim // If ProcIndices contains zero, the class applies to all processors. 595314564Sdim if (!std::count(ProcIndices.begin(), ProcIndices.end(), 0)) { 596314564Sdim for (std::vector<CodeGenProcModel>::iterator PI = ProcModels.begin(), 597314564Sdim PE = ProcModels.end(); PI != PE; ++PI) { 598314564Sdim if (!std::count(ProcIndices.begin(), ProcIndices.end(), PI->Index)) 599314564Sdim dbgs() << "No machine model for " << Inst->TheDef->getName() 600314564Sdim << " on processor " << PI->ModelName << '\n'; 601314564Sdim } 602243830Sdim } 603243830Sdim } 604239310Sdim} 605239310Sdim 606243830Sdim/// Find an SchedClass that has been inferred from a per-operand list of 607243830Sdim/// SchedWrites and SchedReads. 608249423Sdimunsigned CodeGenSchedModels::findSchedClassIdx(Record *ItinClassDef, 609296417Sdim ArrayRef<unsigned> Writes, 610296417Sdim ArrayRef<unsigned> Reads) const { 611243830Sdim for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) { 612296417Sdim if (I->ItinClassDef == ItinClassDef && makeArrayRef(I->Writes) == Writes && 613296417Sdim makeArrayRef(I->Reads) == Reads) { 614243830Sdim return I - schedClassBegin(); 615243830Sdim } 616243830Sdim } 617243830Sdim return 0; 618239310Sdim} 619239310Sdim 620243830Sdim// Get the SchedClass index for an instruction. 621243830Sdimunsigned CodeGenSchedModels::getSchedClassIdx( 622243830Sdim const CodeGenInstruction &Inst) const { 623239310Sdim 624249423Sdim return InstrClassMap.lookup(Inst.TheDef); 625243830Sdim} 626239310Sdim 627296417Sdimstd::string 628296417SdimCodeGenSchedModels::createSchedClassName(Record *ItinClassDef, 629296417Sdim ArrayRef<unsigned> OperWrites, 630296417Sdim ArrayRef<unsigned> OperReads) { 631243830Sdim 632243830Sdim std::string Name; 633249423Sdim if (ItinClassDef && ItinClassDef->getName() != "NoItinerary") 634249423Sdim Name = ItinClassDef->getName(); 635296417Sdim for (unsigned Idx : OperWrites) { 636249423Sdim if (!Name.empty()) 637243830Sdim Name += '_'; 638296417Sdim Name += SchedWrites[Idx].Name; 639243830Sdim } 640296417Sdim for (unsigned Idx : OperReads) { 641243830Sdim Name += '_'; 642296417Sdim Name += SchedReads[Idx].Name; 643243830Sdim } 644243830Sdim return Name; 645243830Sdim} 646243830Sdim 647243830Sdimstd::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { 648243830Sdim 649243830Sdim std::string Name; 650243830Sdim for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) { 651243830Sdim if (I != InstDefs.begin()) 652243830Sdim Name += '_'; 653243830Sdim Name += (*I)->getName(); 654243830Sdim } 655243830Sdim return Name; 656243830Sdim} 657243830Sdim 658249423Sdim/// Add an inferred sched class from an itinerary class and per-operand list of 659249423Sdim/// SchedWrites and SchedReads. ProcIndices contains the set of IDs of 660249423Sdim/// processors that may utilize this class. 661249423Sdimunsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef, 662296417Sdim ArrayRef<unsigned> OperWrites, 663296417Sdim ArrayRef<unsigned> OperReads, 664296417Sdim ArrayRef<unsigned> ProcIndices) { 665243830Sdim assert(!ProcIndices.empty() && "expect at least one ProcIdx"); 666243830Sdim 667249423Sdim unsigned Idx = findSchedClassIdx(ItinClassDef, OperWrites, OperReads); 668249423Sdim if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) { 669243830Sdim IdxVec PI; 670243830Sdim std::set_union(SchedClasses[Idx].ProcIndices.begin(), 671243830Sdim SchedClasses[Idx].ProcIndices.end(), 672243830Sdim ProcIndices.begin(), ProcIndices.end(), 673243830Sdim std::back_inserter(PI)); 674243830Sdim SchedClasses[Idx].ProcIndices.swap(PI); 675243830Sdim return Idx; 676243830Sdim } 677243830Sdim Idx = SchedClasses.size(); 678243830Sdim SchedClasses.resize(Idx+1); 679243830Sdim CodeGenSchedClass &SC = SchedClasses.back(); 680249423Sdim SC.Index = Idx; 681249423Sdim SC.Name = createSchedClassName(ItinClassDef, OperWrites, OperReads); 682249423Sdim SC.ItinClassDef = ItinClassDef; 683243830Sdim SC.Writes = OperWrites; 684243830Sdim SC.Reads = OperReads; 685243830Sdim SC.ProcIndices = ProcIndices; 686243830Sdim 687243830Sdim return Idx; 688243830Sdim} 689243830Sdim 690243830Sdim// Create classes for each set of opcodes that are in the same InstReadWrite 691243830Sdim// definition across all processors. 692243830Sdimvoid CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { 693243830Sdim // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that 694243830Sdim // intersects with an existing class via a previous InstRWDef. Instrs that do 695243830Sdim // not intersect with an existing class refer back to their former class as 696243830Sdim // determined from ItinDef or SchedRW. 697314564Sdim SmallVector<std::pair<unsigned, SmallVector<Record *, 8>>, 4> ClassInstrs; 698243830Sdim // Sort Instrs into sets. 699243830Sdim const RecVec *InstDefs = Sets.expand(InstRWDef); 700243830Sdim if (InstDefs->empty()) 701243830Sdim PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes"); 702243830Sdim 703243830Sdim for (RecIter I = InstDefs->begin(), E = InstDefs->end(); I != E; ++I) { 704243830Sdim InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I); 705249423Sdim if (Pos == InstrClassMap.end()) 706249423Sdim PrintFatalError((*I)->getLoc(), "No sched class for instruction."); 707249423Sdim unsigned SCIdx = Pos->second; 708243830Sdim unsigned CIdx = 0, CEnd = ClassInstrs.size(); 709243830Sdim for (; CIdx != CEnd; ++CIdx) { 710243830Sdim if (ClassInstrs[CIdx].first == SCIdx) 711243830Sdim break; 712243830Sdim } 713243830Sdim if (CIdx == CEnd) { 714243830Sdim ClassInstrs.resize(CEnd + 1); 715243830Sdim ClassInstrs[CIdx].first = SCIdx; 716243830Sdim } 717243830Sdim ClassInstrs[CIdx].second.push_back(*I); 718239310Sdim } 719243830Sdim // For each set of Instrs, create a new class if necessary, and map or remap 720243830Sdim // the Instrs to it. 721243830Sdim unsigned CIdx = 0, CEnd = ClassInstrs.size(); 722243830Sdim for (; CIdx != CEnd; ++CIdx) { 723243830Sdim unsigned OldSCIdx = ClassInstrs[CIdx].first; 724243830Sdim ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second; 725243830Sdim // If the all instrs in the current class are accounted for, then leave 726243830Sdim // them mapped to their old class. 727261991Sdim if (OldSCIdx) { 728261991Sdim const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs; 729261991Sdim if (!RWDefs.empty()) { 730261991Sdim const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]); 731261991Sdim unsigned OrigNumInstrs = 0; 732261991Sdim for (RecIter I = OrigInstDefs->begin(), E = OrigInstDefs->end(); 733261991Sdim I != E; ++I) { 734261991Sdim if (InstrClassMap[*I] == OldSCIdx) 735261991Sdim ++OrigNumInstrs; 736261991Sdim } 737261991Sdim if (OrigNumInstrs == InstDefs.size()) { 738261991Sdim assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 && 739261991Sdim "expected a generic SchedClass"); 740261991Sdim DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":" 741261991Sdim << SchedClasses[OldSCIdx].Name << " on " 742261991Sdim << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n"); 743261991Sdim SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef); 744261991Sdim continue; 745261991Sdim } 746261991Sdim } 747243830Sdim } 748243830Sdim unsigned SCIdx = SchedClasses.size(); 749243830Sdim SchedClasses.resize(SCIdx+1); 750243830Sdim CodeGenSchedClass &SC = SchedClasses.back(); 751249423Sdim SC.Index = SCIdx; 752243830Sdim SC.Name = createSchedClassName(InstDefs); 753261991Sdim DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on " 754261991Sdim << InstRWDef->getValueAsDef("SchedModel")->getName() << "\n"); 755261991Sdim 756243830Sdim // Preserve ItinDef and Writes/Reads for processors without an InstRW entry. 757243830Sdim SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef; 758243830Sdim SC.Writes = SchedClasses[OldSCIdx].Writes; 759243830Sdim SC.Reads = SchedClasses[OldSCIdx].Reads; 760243830Sdim SC.ProcIndices.push_back(0); 761243830Sdim // Map each Instr to this new class. 762243830Sdim // Note that InstDefs may be a smaller list than InstRWDef's "Instrs". 763243830Sdim Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 764243830Sdim SmallSet<unsigned, 4> RemappedClassIDs; 765243830Sdim for (ArrayRef<Record*>::const_iterator 766243830Sdim II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) { 767243830Sdim unsigned OldSCIdx = InstrClassMap[*II]; 768280031Sdim if (OldSCIdx && RemappedClassIDs.insert(OldSCIdx).second) { 769243830Sdim for (RecIter RI = SchedClasses[OldSCIdx].InstRWs.begin(), 770243830Sdim RE = SchedClasses[OldSCIdx].InstRWs.end(); RI != RE; ++RI) { 771243830Sdim if ((*RI)->getValueAsDef("SchedModel") == RWModelDef) { 772243830Sdim PrintFatalError(InstRWDef->getLoc(), "Overlapping InstRW def " + 773243830Sdim (*II)->getName() + " also matches " + 774243830Sdim (*RI)->getValue("Instrs")->getValue()->getAsString()); 775243830Sdim } 776243830Sdim assert(*RI != InstRWDef && "SchedClass has duplicate InstRW def"); 777243830Sdim SC.InstRWs.push_back(*RI); 778243830Sdim } 779243830Sdim } 780243830Sdim InstrClassMap[*II] = SCIdx; 781243830Sdim } 782243830Sdim SC.InstRWs.push_back(InstRWDef); 783243830Sdim } 784243830Sdim} 785243830Sdim 786249423Sdim// True if collectProcItins found anything. 787249423Sdimbool CodeGenSchedModels::hasItineraries() const { 788249423Sdim for (CodeGenSchedModels::ProcIter PI = procModelBegin(), PE = procModelEnd(); 789249423Sdim PI != PE; ++PI) { 790249423Sdim if (PI->hasItineraries()) 791249423Sdim return true; 792249423Sdim } 793249423Sdim return false; 794249423Sdim} 795249423Sdim 796243830Sdim// Gather the processor itineraries. 797243830Sdimvoid CodeGenSchedModels::collectProcItins() { 798321369Sdim DEBUG(dbgs() << "\n+++ PROBLEM ITINERARIES (collectProcItins) +++\n"); 799280031Sdim for (CodeGenProcModel &ProcModel : ProcModels) { 800249423Sdim if (!ProcModel.hasItineraries()) 801243830Sdim continue; 802243830Sdim 803249423Sdim RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID"); 804249423Sdim assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect"); 805243830Sdim 806249423Sdim // Populate ItinDefList with Itinerary records. 807249423Sdim ProcModel.ItinDefList.resize(NumInstrSchedClasses); 808249423Sdim 809243830Sdim // Insert each itinerary data record in the correct position within 810243830Sdim // the processor model's ItinDefList. 811243830Sdim for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) { 812243830Sdim Record *ItinData = ItinRecords[i]; 813243830Sdim Record *ItinDef = ItinData->getValueAsDef("TheClass"); 814249423Sdim bool FoundClass = false; 815249423Sdim for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd(); 816249423Sdim SCI != SCE; ++SCI) { 817249423Sdim // Multiple SchedClasses may share an itinerary. Update all of them. 818249423Sdim if (SCI->ItinClassDef == ItinDef) { 819249423Sdim ProcModel.ItinDefList[SCI->Index] = ItinData; 820249423Sdim FoundClass = true; 821249423Sdim } 822249423Sdim } 823249423Sdim if (!FoundClass) { 824243830Sdim DEBUG(dbgs() << ProcModel.ItinsDef->getName() 825249423Sdim << " missing class for itinerary " << ItinDef->getName() << '\n'); 826243830Sdim } 827243830Sdim } 828243830Sdim // Check for missing itinerary entries. 829243830Sdim assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); 830243830Sdim DEBUG( 831243830Sdim for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { 832243830Sdim if (!ProcModel.ItinDefList[i]) 833243830Sdim dbgs() << ProcModel.ItinsDef->getName() 834243830Sdim << " missing itinerary for class " 835243830Sdim << SchedClasses[i].Name << '\n'; 836243830Sdim }); 837243830Sdim } 838243830Sdim} 839243830Sdim 840243830Sdim// Gather the read/write types for each itinerary class. 841243830Sdimvoid CodeGenSchedModels::collectProcItinRW() { 842243830Sdim RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 843243830Sdim std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord()); 844243830Sdim for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { 845243830Sdim if (!(*II)->getValueInit("SchedModel")->isComplete()) 846243830Sdim PrintFatalError((*II)->getLoc(), "SchedModel is undefined"); 847243830Sdim Record *ModelDef = (*II)->getValueAsDef("SchedModel"); 848243830Sdim ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 849243830Sdim if (I == ProcModelMap.end()) { 850243830Sdim PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel " 851243830Sdim + ModelDef->getName()); 852243830Sdim } 853243830Sdim ProcModels[I->second].ItinRWDefs.push_back(*II); 854243830Sdim } 855243830Sdim} 856243830Sdim 857309124Sdim// Gather the unsupported features for processor models. 858309124Sdimvoid CodeGenSchedModels::collectProcUnsupportedFeatures() { 859309124Sdim for (CodeGenProcModel &ProcModel : ProcModels) { 860309124Sdim for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) { 861309124Sdim ProcModel.UnsupportedFeaturesDefs.push_back(Pred); 862309124Sdim } 863309124Sdim } 864309124Sdim} 865309124Sdim 866243830Sdim/// Infer new classes from existing classes. In the process, this may create new 867243830Sdim/// SchedWrites from sequences of existing SchedWrites. 868243830Sdimvoid CodeGenSchedModels::inferSchedClasses() { 869321369Sdim DEBUG(dbgs() << "\n+++ INFERRING SCHED CLASSES (inferSchedClasses) +++\n"); 870249423Sdim DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n"); 871249423Sdim 872243830Sdim // Visit all existing classes and newly created classes. 873243830Sdim for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) { 874249423Sdim assert(SchedClasses[Idx].Index == Idx && "bad SCIdx"); 875249423Sdim 876243830Sdim if (SchedClasses[Idx].ItinClassDef) 877243830Sdim inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx); 878249423Sdim if (!SchedClasses[Idx].InstRWs.empty()) 879243830Sdim inferFromInstRWs(Idx); 880249423Sdim if (!SchedClasses[Idx].Writes.empty()) { 881243830Sdim inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads, 882243830Sdim Idx, SchedClasses[Idx].ProcIndices); 883243830Sdim } 884243830Sdim assert(SchedClasses.size() < (NumInstrSchedClasses*6) && 885243830Sdim "too many SchedVariants"); 886243830Sdim } 887243830Sdim} 888243830Sdim 889243830Sdim/// Infer classes from per-processor itinerary resources. 890243830Sdimvoid CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef, 891243830Sdim unsigned FromClassIdx) { 892243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 893243830Sdim const CodeGenProcModel &PM = ProcModels[PIdx]; 894243830Sdim // For all ItinRW entries. 895243830Sdim bool HasMatch = false; 896243830Sdim for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 897243830Sdim II != IE; ++II) { 898243830Sdim RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 899243830Sdim if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 900243830Sdim continue; 901243830Sdim if (HasMatch) 902243830Sdim PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 903243830Sdim + ItinClassDef->getName() 904243830Sdim + " in ItinResources for " + PM.ModelName); 905243830Sdim HasMatch = true; 906243830Sdim IdxVec Writes, Reads; 907243830Sdim findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 908243830Sdim IdxVec ProcIndices(1, PIdx); 909243830Sdim inferFromRW(Writes, Reads, FromClassIdx, ProcIndices); 910243830Sdim } 911243830Sdim } 912243830Sdim} 913243830Sdim 914243830Sdim/// Infer classes from per-processor InstReadWrite definitions. 915243830Sdimvoid CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) { 916261991Sdim for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) { 917261991Sdim assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!"); 918261991Sdim Record *Rec = SchedClasses[SCIdx].InstRWs[I]; 919261991Sdim const RecVec *InstDefs = Sets.expand(Rec); 920243830Sdim RecIter II = InstDefs->begin(), IE = InstDefs->end(); 921243830Sdim for (; II != IE; ++II) { 922243830Sdim if (InstrClassMap[*II] == SCIdx) 923243830Sdim break; 924243830Sdim } 925243830Sdim // If this class no longer has any instructions mapped to it, it has become 926243830Sdim // irrelevant. 927243830Sdim if (II == IE) 928243830Sdim continue; 929243830Sdim IdxVec Writes, Reads; 930261991Sdim findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 931261991Sdim unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index; 932243830Sdim IdxVec ProcIndices(1, PIdx); 933261991Sdim inferFromRW(Writes, Reads, SCIdx, ProcIndices); // May mutate SchedClasses. 934243830Sdim } 935243830Sdim} 936243830Sdim 937243830Sdimnamespace { 938314564Sdim 939243830Sdim// Helper for substituteVariantOperand. 940243830Sdimstruct TransVariant { 941243830Sdim Record *VarOrSeqDef; // Variant or sequence. 942243830Sdim unsigned RWIdx; // Index of this variant or sequence's matched type. 943243830Sdim unsigned ProcIdx; // Processor model index or zero for any. 944243830Sdim unsigned TransVecIdx; // Index into PredTransitions::TransVec. 945243830Sdim 946243830Sdim TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti): 947243830Sdim VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {} 948243830Sdim}; 949243830Sdim 950243830Sdim// Associate a predicate with the SchedReadWrite that it guards. 951243830Sdim// RWIdx is the index of the read/write variant. 952243830Sdimstruct PredCheck { 953243830Sdim bool IsRead; 954243830Sdim unsigned RWIdx; 955243830Sdim Record *Predicate; 956243830Sdim 957243830Sdim PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {} 958243830Sdim}; 959243830Sdim 960243830Sdim// A Predicate transition is a list of RW sequences guarded by a PredTerm. 961243830Sdimstruct PredTransition { 962243830Sdim // A predicate term is a conjunction of PredChecks. 963243830Sdim SmallVector<PredCheck, 4> PredTerm; 964243830Sdim SmallVector<SmallVector<unsigned,4>, 16> WriteSequences; 965243830Sdim SmallVector<SmallVector<unsigned,4>, 16> ReadSequences; 966243830Sdim SmallVector<unsigned, 4> ProcIndices; 967243830Sdim}; 968243830Sdim 969243830Sdim// Encapsulate a set of partially constructed transitions. 970243830Sdim// The results are built by repeated calls to substituteVariants. 971243830Sdimclass PredTransitions { 972243830Sdim CodeGenSchedModels &SchedModels; 973243830Sdim 974243830Sdimpublic: 975243830Sdim std::vector<PredTransition> TransVec; 976243830Sdim 977243830Sdim PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {} 978243830Sdim 979243830Sdim void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq, 980243830Sdim bool IsRead, unsigned StartIdx); 981243830Sdim 982243830Sdim void substituteVariants(const PredTransition &Trans); 983243830Sdim 984243830Sdim#ifndef NDEBUG 985243830Sdim void dump() const; 986243830Sdim#endif 987243830Sdim 988243830Sdimprivate: 989243830Sdim bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term); 990243830Sdim void getIntersectingVariants( 991243830Sdim const CodeGenSchedRW &SchedRW, unsigned TransIdx, 992243830Sdim std::vector<TransVariant> &IntersectingVariants); 993243830Sdim void pushVariant(const TransVariant &VInfo, bool IsRead); 994243830Sdim}; 995243830Sdim 996314564Sdim} // end anonymous namespace 997314564Sdim 998243830Sdim// Return true if this predicate is mutually exclusive with a PredTerm. This 999243830Sdim// degenerates into checking if the predicate is mutually exclusive with any 1000243830Sdim// predicate in the Term's conjunction. 1001243830Sdim// 1002243830Sdim// All predicates associated with a given SchedRW are considered mutually 1003243830Sdim// exclusive. This should work even if the conditions expressed by the 1004243830Sdim// predicates are not exclusive because the predicates for a given SchedWrite 1005243830Sdim// are always checked in the order they are defined in the .td file. Later 1006243830Sdim// conditions implicitly negate any prior condition. 1007243830Sdimbool PredTransitions::mutuallyExclusive(Record *PredDef, 1008243830Sdim ArrayRef<PredCheck> Term) { 1009243830Sdim for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end(); 1010243830Sdim I != E; ++I) { 1011243830Sdim if (I->Predicate == PredDef) 1012243830Sdim return false; 1013243830Sdim 1014243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead); 1015243830Sdim assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant"); 1016243830Sdim RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1017243830Sdim for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) { 1018243830Sdim if ((*VI)->getValueAsDef("Predicate") == PredDef) 1019243830Sdim return true; 1020243830Sdim } 1021243830Sdim } 1022243830Sdim return false; 1023243830Sdim} 1024243830Sdim 1025243830Sdimstatic bool hasAliasedVariants(const CodeGenSchedRW &RW, 1026243830Sdim CodeGenSchedModels &SchedModels) { 1027243830Sdim if (RW.HasVariants) 1028243830Sdim return true; 1029243830Sdim 1030243830Sdim for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) { 1031243830Sdim const CodeGenSchedRW &AliasRW = 1032243830Sdim SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW")); 1033243830Sdim if (AliasRW.HasVariants) 1034243830Sdim return true; 1035243830Sdim if (AliasRW.IsSequence) { 1036243830Sdim IdxVec ExpandedRWs; 1037243830Sdim SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead); 1038243830Sdim for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 1039243830Sdim SI != SE; ++SI) { 1040243830Sdim if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead), 1041243830Sdim SchedModels)) { 1042243830Sdim return true; 1043243830Sdim } 1044243830Sdim } 1045243830Sdim } 1046243830Sdim } 1047243830Sdim return false; 1048243830Sdim} 1049243830Sdim 1050243830Sdimstatic bool hasVariant(ArrayRef<PredTransition> Transitions, 1051243830Sdim CodeGenSchedModels &SchedModels) { 1052243830Sdim for (ArrayRef<PredTransition>::iterator 1053243830Sdim PTI = Transitions.begin(), PTE = Transitions.end(); 1054243830Sdim PTI != PTE; ++PTI) { 1055314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1056243830Sdim WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end(); 1057243830Sdim WSI != WSE; ++WSI) { 1058243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1059243830Sdim WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 1060243830Sdim if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels)) 1061243830Sdim return true; 1062243830Sdim } 1063243830Sdim } 1064314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1065243830Sdim RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end(); 1066243830Sdim RSI != RSE; ++RSI) { 1067243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1068243830Sdim RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) { 1069243830Sdim if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels)) 1070243830Sdim return true; 1071243830Sdim } 1072243830Sdim } 1073243830Sdim } 1074243830Sdim return false; 1075243830Sdim} 1076243830Sdim 1077243830Sdim// Populate IntersectingVariants with any variants or aliased sequences of the 1078243830Sdim// given SchedRW whose processor indices and predicates are not mutually 1079249423Sdim// exclusive with the given transition. 1080243830Sdimvoid PredTransitions::getIntersectingVariants( 1081243830Sdim const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1082243830Sdim std::vector<TransVariant> &IntersectingVariants) { 1083243830Sdim 1084249423Sdim bool GenericRW = false; 1085249423Sdim 1086243830Sdim std::vector<TransVariant> Variants; 1087243830Sdim if (SchedRW.HasVariants) { 1088243830Sdim unsigned VarProcIdx = 0; 1089243830Sdim if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) { 1090243830Sdim Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel"); 1091243830Sdim VarProcIdx = SchedModels.getProcModel(ModelDef).Index; 1092243830Sdim } 1093243830Sdim // Push each variant. Assign TransVecIdx later. 1094243830Sdim const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1095243830Sdim for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI) 1096243830Sdim Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0)); 1097249423Sdim if (VarProcIdx == 0) 1098249423Sdim GenericRW = true; 1099243830Sdim } 1100243830Sdim for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1101243830Sdim AI != AE; ++AI) { 1102243830Sdim // If either the SchedAlias itself or the SchedReadWrite that it aliases 1103243830Sdim // to is defined within a processor model, constrain all variants to 1104243830Sdim // that processor. 1105243830Sdim unsigned AliasProcIdx = 0; 1106243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1107243830Sdim Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 1108243830Sdim AliasProcIdx = SchedModels.getProcModel(ModelDef).Index; 1109243830Sdim } 1110243830Sdim const CodeGenSchedRW &AliasRW = 1111243830Sdim SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW")); 1112243830Sdim 1113243830Sdim if (AliasRW.HasVariants) { 1114243830Sdim const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants"); 1115243830Sdim for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI) 1116243830Sdim Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0)); 1117243830Sdim } 1118243830Sdim if (AliasRW.IsSequence) { 1119243830Sdim Variants.push_back( 1120243830Sdim TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0)); 1121243830Sdim } 1122249423Sdim if (AliasProcIdx == 0) 1123249423Sdim GenericRW = true; 1124243830Sdim } 1125243830Sdim for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) { 1126243830Sdim TransVariant &Variant = Variants[VIdx]; 1127243830Sdim // Don't expand variants if the processor models don't intersect. 1128243830Sdim // A zero processor index means any processor. 1129261991Sdim SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices; 1130243830Sdim if (ProcIndices[0] && Variants[VIdx].ProcIdx) { 1131243830Sdim unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(), 1132243830Sdim Variant.ProcIdx); 1133243830Sdim if (!Cnt) 1134243830Sdim continue; 1135243830Sdim if (Cnt > 1) { 1136243830Sdim const CodeGenProcModel &PM = 1137243830Sdim *(SchedModels.procModelBegin() + Variant.ProcIdx); 1138243830Sdim PrintFatalError(Variant.VarOrSeqDef->getLoc(), 1139243830Sdim "Multiple variants defined for processor " + 1140243830Sdim PM.ModelName + 1141243830Sdim " Ensure only one SchedAlias exists per RW."); 1142243830Sdim } 1143243830Sdim } 1144243830Sdim if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) { 1145243830Sdim Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate"); 1146243830Sdim if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm)) 1147243830Sdim continue; 1148243830Sdim } 1149243830Sdim if (IntersectingVariants.empty()) { 1150243830Sdim // The first variant builds on the existing transition. 1151243830Sdim Variant.TransVecIdx = TransIdx; 1152243830Sdim IntersectingVariants.push_back(Variant); 1153243830Sdim } 1154243830Sdim else { 1155243830Sdim // Push another copy of the current transition for more variants. 1156243830Sdim Variant.TransVecIdx = TransVec.size(); 1157243830Sdim IntersectingVariants.push_back(Variant); 1158243830Sdim TransVec.push_back(TransVec[TransIdx]); 1159243830Sdim } 1160243830Sdim } 1161249423Sdim if (GenericRW && IntersectingVariants.empty()) { 1162249423Sdim PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has " 1163249423Sdim "a matching predicate on any processor"); 1164249423Sdim } 1165243830Sdim} 1166243830Sdim 1167243830Sdim// Push the Reads/Writes selected by this variant onto the PredTransition 1168243830Sdim// specified by VInfo. 1169243830Sdimvoid PredTransitions:: 1170243830SdimpushVariant(const TransVariant &VInfo, bool IsRead) { 1171243830Sdim PredTransition &Trans = TransVec[VInfo.TransVecIdx]; 1172243830Sdim 1173243830Sdim // If this operand transition is reached through a processor-specific alias, 1174243830Sdim // then the whole transition is specific to this processor. 1175243830Sdim if (VInfo.ProcIdx != 0) 1176243830Sdim Trans.ProcIndices.assign(1, VInfo.ProcIdx); 1177243830Sdim 1178243830Sdim IdxVec SelectedRWs; 1179243830Sdim if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) { 1180243830Sdim Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate"); 1181243830Sdim Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef)); 1182243830Sdim RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected"); 1183243830Sdim SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead); 1184243830Sdim } 1185239310Sdim else { 1186243830Sdim assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") && 1187243830Sdim "variant must be a SchedVariant or aliased WriteSequence"); 1188243830Sdim SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead)); 1189239310Sdim } 1190239310Sdim 1191243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead); 1192239310Sdim 1193314564Sdim SmallVectorImpl<SmallVector<unsigned,4>> &RWSequences = IsRead 1194243830Sdim ? Trans.ReadSequences : Trans.WriteSequences; 1195243830Sdim if (SchedRW.IsVariadic) { 1196243830Sdim unsigned OperIdx = RWSequences.size()-1; 1197243830Sdim // Make N-1 copies of this transition's last sequence. 1198243830Sdim for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) { 1199261991Sdim // Create a temporary copy the vector could reallocate. 1200261991Sdim RWSequences.reserve(RWSequences.size() + 1); 1201243830Sdim RWSequences.push_back(RWSequences[OperIdx]); 1202243830Sdim } 1203243830Sdim // Push each of the N elements of the SelectedRWs onto a copy of the last 1204243830Sdim // sequence (split the current operand into N operands). 1205243830Sdim // Note that write sequences should be expanded within this loop--the entire 1206243830Sdim // sequence belongs to a single operand. 1207243830Sdim for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1208243830Sdim RWI != RWE; ++RWI, ++OperIdx) { 1209243830Sdim IdxVec ExpandedRWs; 1210243830Sdim if (IsRead) 1211243830Sdim ExpandedRWs.push_back(*RWI); 1212243830Sdim else 1213243830Sdim SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1214243830Sdim RWSequences[OperIdx].insert(RWSequences[OperIdx].end(), 1215243830Sdim ExpandedRWs.begin(), ExpandedRWs.end()); 1216243830Sdim } 1217243830Sdim assert(OperIdx == RWSequences.size() && "missed a sequence"); 1218243830Sdim } 1219243830Sdim else { 1220243830Sdim // Push this transition's expanded sequence onto this transition's last 1221243830Sdim // sequence (add to the current operand's sequence). 1222243830Sdim SmallVectorImpl<unsigned> &Seq = RWSequences.back(); 1223243830Sdim IdxVec ExpandedRWs; 1224243830Sdim for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1225243830Sdim RWI != RWE; ++RWI) { 1226243830Sdim if (IsRead) 1227243830Sdim ExpandedRWs.push_back(*RWI); 1228243830Sdim else 1229243830Sdim SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1230243830Sdim } 1231243830Sdim Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end()); 1232243830Sdim } 1233243830Sdim} 1234239310Sdim 1235243830Sdim// RWSeq is a sequence of all Reads or all Writes for the next read or write 1236243830Sdim// operand. StartIdx is an index into TransVec where partial results 1237243830Sdim// starts. RWSeq must be applied to all transitions between StartIdx and the end 1238243830Sdim// of TransVec. 1239243830Sdimvoid PredTransitions::substituteVariantOperand( 1240243830Sdim const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) { 1241243830Sdim 1242243830Sdim // Visit each original RW within the current sequence. 1243243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1244243830Sdim RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) { 1245243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead); 1246243830Sdim // Push this RW on all partial PredTransitions or distribute variants. 1247243830Sdim // New PredTransitions may be pushed within this loop which should not be 1248243830Sdim // revisited (TransEnd must be loop invariant). 1249243830Sdim for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size(); 1250243830Sdim TransIdx != TransEnd; ++TransIdx) { 1251243830Sdim // In the common case, push RW onto the current operand's sequence. 1252243830Sdim if (!hasAliasedVariants(SchedRW, SchedModels)) { 1253243830Sdim if (IsRead) 1254243830Sdim TransVec[TransIdx].ReadSequences.back().push_back(*RWI); 1255243830Sdim else 1256243830Sdim TransVec[TransIdx].WriteSequences.back().push_back(*RWI); 1257243830Sdim continue; 1258243830Sdim } 1259243830Sdim // Distribute this partial PredTransition across intersecting variants. 1260243830Sdim // This will push a copies of TransVec[TransIdx] on the back of TransVec. 1261243830Sdim std::vector<TransVariant> IntersectingVariants; 1262243830Sdim getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants); 1263243830Sdim // Now expand each variant on top of its copy of the transition. 1264243830Sdim for (std::vector<TransVariant>::const_iterator 1265243830Sdim IVI = IntersectingVariants.begin(), 1266243830Sdim IVE = IntersectingVariants.end(); 1267243830Sdim IVI != IVE; ++IVI) { 1268243830Sdim pushVariant(*IVI, IsRead); 1269243830Sdim } 1270243830Sdim } 1271243830Sdim } 1272239310Sdim} 1273239310Sdim 1274243830Sdim// For each variant of a Read/Write in Trans, substitute the sequence of 1275243830Sdim// Read/Writes guarded by the variant. This is exponential in the number of 1276243830Sdim// variant Read/Writes, but in practice detection of mutually exclusive 1277243830Sdim// predicates should result in linear growth in the total number variants. 1278243830Sdim// 1279243830Sdim// This is one step in a breadth-first search of nested variants. 1280243830Sdimvoid PredTransitions::substituteVariants(const PredTransition &Trans) { 1281243830Sdim // Build up a set of partial results starting at the back of 1282243830Sdim // PredTransitions. Remember the first new transition. 1283243830Sdim unsigned StartIdx = TransVec.size(); 1284243830Sdim TransVec.resize(TransVec.size() + 1); 1285243830Sdim TransVec.back().PredTerm = Trans.PredTerm; 1286243830Sdim TransVec.back().ProcIndices = Trans.ProcIndices; 1287243830Sdim 1288243830Sdim // Visit each original write sequence. 1289314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1290243830Sdim WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end(); 1291243830Sdim WSI != WSE; ++WSI) { 1292243830Sdim // Push a new (empty) write sequence onto all partial Transitions. 1293243830Sdim for (std::vector<PredTransition>::iterator I = 1294243830Sdim TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1295243830Sdim I->WriteSequences.resize(I->WriteSequences.size() + 1); 1296243830Sdim } 1297243830Sdim substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx); 1298243830Sdim } 1299243830Sdim // Visit each original read sequence. 1300314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1301243830Sdim RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end(); 1302243830Sdim RSI != RSE; ++RSI) { 1303243830Sdim // Push a new (empty) read sequence onto all partial Transitions. 1304243830Sdim for (std::vector<PredTransition>::iterator I = 1305243830Sdim TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1306243830Sdim I->ReadSequences.resize(I->ReadSequences.size() + 1); 1307243830Sdim } 1308243830Sdim substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx); 1309243830Sdim } 1310243830Sdim} 1311243830Sdim 1312243830Sdim// Create a new SchedClass for each variant found by inferFromRW. Pass 1313243830Sdimstatic void inferFromTransitions(ArrayRef<PredTransition> LastTransitions, 1314243830Sdim unsigned FromClassIdx, 1315243830Sdim CodeGenSchedModels &SchedModels) { 1316243830Sdim // For each PredTransition, create a new CodeGenSchedTransition, which usually 1317243830Sdim // requires creating a new SchedClass. 1318243830Sdim for (ArrayRef<PredTransition>::iterator 1319243830Sdim I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) { 1320243830Sdim IdxVec OperWritesVariant; 1321314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1322243830Sdim WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end(); 1323243830Sdim WSI != WSE; ++WSI) { 1324243830Sdim // Create a new write representing the expanded sequence. 1325243830Sdim OperWritesVariant.push_back( 1326243830Sdim SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false)); 1327243830Sdim } 1328243830Sdim IdxVec OperReadsVariant; 1329314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1330243830Sdim RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end(); 1331243830Sdim RSI != RSE; ++RSI) { 1332243830Sdim // Create a new read representing the expanded sequence. 1333243830Sdim OperReadsVariant.push_back( 1334243830Sdim SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true)); 1335243830Sdim } 1336243830Sdim IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end()); 1337243830Sdim CodeGenSchedTransition SCTrans; 1338243830Sdim SCTrans.ToClassIdx = 1339276479Sdim SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant, 1340249423Sdim OperReadsVariant, ProcIndices); 1341243830Sdim SCTrans.ProcIndices = ProcIndices; 1342243830Sdim // The final PredTerm is unique set of predicates guarding the transition. 1343243830Sdim RecVec Preds; 1344243830Sdim for (SmallVectorImpl<PredCheck>::const_iterator 1345243830Sdim PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) { 1346243830Sdim Preds.push_back(PI->Predicate); 1347243830Sdim } 1348243830Sdim RecIter PredsEnd = std::unique(Preds.begin(), Preds.end()); 1349243830Sdim Preds.resize(PredsEnd - Preds.begin()); 1350243830Sdim SCTrans.PredTerm = Preds; 1351243830Sdim SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans); 1352243830Sdim } 1353243830Sdim} 1354243830Sdim 1355243830Sdim// Create new SchedClasses for the given ReadWrite list. If any of the 1356243830Sdim// ReadWrites refers to a SchedVariant, create a new SchedClass for each variant 1357243830Sdim// of the ReadWrite list, following Aliases if necessary. 1358296417Sdimvoid CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites, 1359296417Sdim ArrayRef<unsigned> OperReads, 1360243830Sdim unsigned FromClassIdx, 1361296417Sdim ArrayRef<unsigned> ProcIndices) { 1362249423Sdim DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); dbgs() << ") "); 1363243830Sdim 1364243830Sdim // Create a seed transition with an empty PredTerm and the expanded sequences 1365243830Sdim // of SchedWrites for the current SchedClass. 1366243830Sdim std::vector<PredTransition> LastTransitions; 1367243830Sdim LastTransitions.resize(1); 1368243830Sdim LastTransitions.back().ProcIndices.append(ProcIndices.begin(), 1369243830Sdim ProcIndices.end()); 1370243830Sdim 1371296417Sdim for (unsigned WriteIdx : OperWrites) { 1372243830Sdim IdxVec WriteSeq; 1373296417Sdim expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false); 1374243830Sdim unsigned Idx = LastTransitions[0].WriteSequences.size(); 1375243830Sdim LastTransitions[0].WriteSequences.resize(Idx + 1); 1376243830Sdim SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx]; 1377243830Sdim for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI) 1378243830Sdim Seq.push_back(*WI); 1379243830Sdim DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1380243830Sdim } 1381243830Sdim DEBUG(dbgs() << " Reads: "); 1382296417Sdim for (unsigned ReadIdx : OperReads) { 1383243830Sdim IdxVec ReadSeq; 1384296417Sdim expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true); 1385243830Sdim unsigned Idx = LastTransitions[0].ReadSequences.size(); 1386243830Sdim LastTransitions[0].ReadSequences.resize(Idx + 1); 1387243830Sdim SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx]; 1388243830Sdim for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI) 1389243830Sdim Seq.push_back(*RI); 1390243830Sdim DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1391243830Sdim } 1392243830Sdim DEBUG(dbgs() << '\n'); 1393243830Sdim 1394243830Sdim // Collect all PredTransitions for individual operands. 1395243830Sdim // Iterate until no variant writes remain. 1396243830Sdim while (hasVariant(LastTransitions, *this)) { 1397243830Sdim PredTransitions Transitions(*this); 1398243830Sdim for (std::vector<PredTransition>::const_iterator 1399243830Sdim I = LastTransitions.begin(), E = LastTransitions.end(); 1400243830Sdim I != E; ++I) { 1401243830Sdim Transitions.substituteVariants(*I); 1402243830Sdim } 1403243830Sdim DEBUG(Transitions.dump()); 1404243830Sdim LastTransitions.swap(Transitions.TransVec); 1405243830Sdim } 1406243830Sdim // If the first transition has no variants, nothing to do. 1407243830Sdim if (LastTransitions[0].PredTerm.empty()) 1408239310Sdim return; 1409239310Sdim 1410243830Sdim // WARNING: We are about to mutate the SchedClasses vector. Do not refer to 1411243830Sdim // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions. 1412243830Sdim inferFromTransitions(LastTransitions, FromClassIdx, *this); 1413243830Sdim} 1414239310Sdim 1415251662Sdim// Check if any processor resource group contains all resource records in 1416251662Sdim// SubUnits. 1417251662Sdimbool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) { 1418251662Sdim for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1419251662Sdim if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1420251662Sdim continue; 1421251662Sdim RecVec SuperUnits = 1422251662Sdim PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1423251662Sdim RecIter RI = SubUnits.begin(), RE = SubUnits.end(); 1424251662Sdim for ( ; RI != RE; ++RI) { 1425314564Sdim if (!is_contained(SuperUnits, *RI)) { 1426251662Sdim break; 1427251662Sdim } 1428251662Sdim } 1429251662Sdim if (RI == RE) 1430251662Sdim return true; 1431251662Sdim } 1432251662Sdim return false; 1433251662Sdim} 1434251662Sdim 1435251662Sdim// Verify that overlapping groups have a common supergroup. 1436251662Sdimvoid CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) { 1437251662Sdim for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1438251662Sdim if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1439251662Sdim continue; 1440251662Sdim RecVec CheckUnits = 1441251662Sdim PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1442251662Sdim for (unsigned j = i+1; j < e; ++j) { 1443251662Sdim if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup")) 1444251662Sdim continue; 1445251662Sdim RecVec OtherUnits = 1446251662Sdim PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources"); 1447251662Sdim if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(), 1448251662Sdim OtherUnits.begin(), OtherUnits.end()) 1449251662Sdim != CheckUnits.end()) { 1450251662Sdim // CheckUnits and OtherUnits overlap 1451251662Sdim OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(), 1452251662Sdim CheckUnits.end()); 1453251662Sdim if (!hasSuperGroup(OtherUnits, PM)) { 1454251662Sdim PrintFatalError((PM.ProcResourceDefs[i])->getLoc(), 1455251662Sdim "proc resource group overlaps with " 1456251662Sdim + PM.ProcResourceDefs[j]->getName() 1457251662Sdim + " but no supergroup contains both."); 1458251662Sdim } 1459251662Sdim } 1460251662Sdim } 1461251662Sdim } 1462251662Sdim} 1463251662Sdim 1464243830Sdim// Collect and sort WriteRes, ReadAdvance, and ProcResources. 1465243830Sdimvoid CodeGenSchedModels::collectProcResources() { 1466309124Sdim ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits"); 1467309124Sdim ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1468309124Sdim 1469243830Sdim // Add any subtarget-specific SchedReadWrites that are directly associated 1470243830Sdim // with processor resources. Refer to the parent SchedClass's ProcIndices to 1471243830Sdim // determine which processors they apply to. 1472243830Sdim for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd(); 1473243830Sdim SCI != SCE; ++SCI) { 1474243830Sdim if (SCI->ItinClassDef) 1475243830Sdim collectItinProcResources(SCI->ItinClassDef); 1476249423Sdim else { 1477249423Sdim // This class may have a default ReadWrite list which can be overriden by 1478249423Sdim // InstRW definitions. 1479249423Sdim if (!SCI->InstRWs.empty()) { 1480249423Sdim for (RecIter RWI = SCI->InstRWs.begin(), RWE = SCI->InstRWs.end(); 1481249423Sdim RWI != RWE; ++RWI) { 1482249423Sdim Record *RWModelDef = (*RWI)->getValueAsDef("SchedModel"); 1483249423Sdim IdxVec ProcIndices(1, getProcModel(RWModelDef).Index); 1484249423Sdim IdxVec Writes, Reads; 1485249423Sdim findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), 1486249423Sdim Writes, Reads); 1487249423Sdim collectRWResources(Writes, Reads, ProcIndices); 1488249423Sdim } 1489249423Sdim } 1490243830Sdim collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices); 1491249423Sdim } 1492243830Sdim } 1493243830Sdim // Add resources separately defined by each subtarget. 1494243830Sdim RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes"); 1495243830Sdim for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) { 1496243830Sdim Record *ModelDef = (*WRI)->getValueAsDef("SchedModel"); 1497243830Sdim addWriteRes(*WRI, getProcModel(ModelDef).Index); 1498243830Sdim } 1499276479Sdim RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes"); 1500276479Sdim for (RecIter WRI = SWRDefs.begin(), WRE = SWRDefs.end(); WRI != WRE; ++WRI) { 1501276479Sdim Record *ModelDef = (*WRI)->getValueAsDef("SchedModel"); 1502276479Sdim addWriteRes(*WRI, getProcModel(ModelDef).Index); 1503276479Sdim } 1504243830Sdim RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance"); 1505243830Sdim for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) { 1506243830Sdim Record *ModelDef = (*RAI)->getValueAsDef("SchedModel"); 1507243830Sdim addReadAdvance(*RAI, getProcModel(ModelDef).Index); 1508243830Sdim } 1509276479Sdim RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance"); 1510276479Sdim for (RecIter RAI = SRADefs.begin(), RAE = SRADefs.end(); RAI != RAE; ++RAI) { 1511276479Sdim if ((*RAI)->getValueInit("SchedModel")->isComplete()) { 1512276479Sdim Record *ModelDef = (*RAI)->getValueAsDef("SchedModel"); 1513276479Sdim addReadAdvance(*RAI, getProcModel(ModelDef).Index); 1514276479Sdim } 1515276479Sdim } 1516261991Sdim // Add ProcResGroups that are defined within this processor model, which may 1517261991Sdim // not be directly referenced but may directly specify a buffer size. 1518261991Sdim RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1519261991Sdim for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end(); 1520261991Sdim RI != RE; ++RI) { 1521261991Sdim if (!(*RI)->getValueInit("SchedModel")->isComplete()) 1522261991Sdim continue; 1523261991Sdim CodeGenProcModel &PM = getProcModel((*RI)->getValueAsDef("SchedModel")); 1524314564Sdim if (!is_contained(PM.ProcResourceDefs, *RI)) 1525261991Sdim PM.ProcResourceDefs.push_back(*RI); 1526261991Sdim } 1527243830Sdim // Finalize each ProcModel by sorting the record arrays. 1528280031Sdim for (CodeGenProcModel &PM : ProcModels) { 1529243830Sdim std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(), 1530243830Sdim LessRecord()); 1531243830Sdim std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(), 1532243830Sdim LessRecord()); 1533243830Sdim std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(), 1534243830Sdim LessRecord()); 1535243830Sdim DEBUG( 1536243830Sdim PM.dump(); 1537243830Sdim dbgs() << "WriteResDefs: "; 1538243830Sdim for (RecIter RI = PM.WriteResDefs.begin(), 1539243830Sdim RE = PM.WriteResDefs.end(); RI != RE; ++RI) { 1540243830Sdim if ((*RI)->isSubClassOf("WriteRes")) 1541243830Sdim dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " "; 1542243830Sdim else 1543243830Sdim dbgs() << (*RI)->getName() << " "; 1544243830Sdim } 1545243830Sdim dbgs() << "\nReadAdvanceDefs: "; 1546243830Sdim for (RecIter RI = PM.ReadAdvanceDefs.begin(), 1547243830Sdim RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) { 1548243830Sdim if ((*RI)->isSubClassOf("ReadAdvance")) 1549243830Sdim dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " "; 1550243830Sdim else 1551243830Sdim dbgs() << (*RI)->getName() << " "; 1552243830Sdim } 1553243830Sdim dbgs() << "\nProcResourceDefs: "; 1554243830Sdim for (RecIter RI = PM.ProcResourceDefs.begin(), 1555243830Sdim RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) { 1556243830Sdim dbgs() << (*RI)->getName() << " "; 1557243830Sdim } 1558243830Sdim dbgs() << '\n'); 1559251662Sdim verifyProcResourceGroups(PM); 1560243830Sdim } 1561309124Sdim 1562309124Sdim ProcResourceDefs.clear(); 1563309124Sdim ProcResGroups.clear(); 1564243830Sdim} 1565239310Sdim 1566309124Sdimvoid CodeGenSchedModels::checkCompleteness() { 1567309124Sdim bool Complete = true; 1568309124Sdim bool HadCompleteModel = false; 1569309124Sdim for (const CodeGenProcModel &ProcModel : procModels()) { 1570309124Sdim if (!ProcModel.ModelDef->getValueAsBit("CompleteModel")) 1571309124Sdim continue; 1572309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 1573309124Sdim if (Inst->hasNoSchedulingInfo) 1574309124Sdim continue; 1575309124Sdim if (ProcModel.isUnsupported(*Inst)) 1576309124Sdim continue; 1577309124Sdim unsigned SCIdx = getSchedClassIdx(*Inst); 1578309124Sdim if (!SCIdx) { 1579309124Sdim if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) { 1580309124Sdim PrintError("No schedule information for instruction '" 1581309124Sdim + Inst->TheDef->getName() + "'"); 1582309124Sdim Complete = false; 1583309124Sdim } 1584309124Sdim continue; 1585309124Sdim } 1586309124Sdim 1587309124Sdim const CodeGenSchedClass &SC = getSchedClass(SCIdx); 1588309124Sdim if (!SC.Writes.empty()) 1589309124Sdim continue; 1590314564Sdim if (SC.ItinClassDef != nullptr && 1591314564Sdim SC.ItinClassDef->getName() != "NoItinerary") 1592309124Sdim continue; 1593309124Sdim 1594309124Sdim const RecVec &InstRWs = SC.InstRWs; 1595314564Sdim auto I = find_if(InstRWs, [&ProcModel](const Record *R) { 1596314564Sdim return R->getValueAsDef("SchedModel") == ProcModel.ModelDef; 1597314564Sdim }); 1598309124Sdim if (I == InstRWs.end()) { 1599309124Sdim PrintError("'" + ProcModel.ModelName + "' lacks information for '" + 1600309124Sdim Inst->TheDef->getName() + "'"); 1601309124Sdim Complete = false; 1602309124Sdim } 1603309124Sdim } 1604309124Sdim HadCompleteModel = true; 1605309124Sdim } 1606309124Sdim if (!Complete) { 1607309124Sdim errs() << "\n\nIncomplete schedule models found.\n" 1608309124Sdim << "- Consider setting 'CompleteModel = 0' while developing new models.\n" 1609309124Sdim << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n" 1610309124Sdim << "- Instructions should usually have Sched<[...]> as a superclass, " 1611309124Sdim "you may temporarily use an empty list.\n" 1612309124Sdim << "- Instructions related to unsupported features can be excluded with " 1613309124Sdim "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the " 1614309124Sdim "processor model.\n\n"; 1615309124Sdim PrintFatalError("Incomplete schedule model"); 1616309124Sdim } 1617309124Sdim} 1618309124Sdim 1619243830Sdim// Collect itinerary class resources for each processor. 1620243830Sdimvoid CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) { 1621243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1622243830Sdim const CodeGenProcModel &PM = ProcModels[PIdx]; 1623243830Sdim // For all ItinRW entries. 1624243830Sdim bool HasMatch = false; 1625243830Sdim for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 1626243830Sdim II != IE; ++II) { 1627243830Sdim RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 1628243830Sdim if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 1629243830Sdim continue; 1630243830Sdim if (HasMatch) 1631243830Sdim PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 1632243830Sdim + ItinClassDef->getName() 1633243830Sdim + " in ItinResources for " + PM.ModelName); 1634243830Sdim HasMatch = true; 1635243830Sdim IdxVec Writes, Reads; 1636243830Sdim findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1637243830Sdim IdxVec ProcIndices(1, PIdx); 1638243830Sdim collectRWResources(Writes, Reads, ProcIndices); 1639239310Sdim } 1640239310Sdim } 1641243830Sdim} 1642243830Sdim 1643243830Sdimvoid CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead, 1644296417Sdim ArrayRef<unsigned> ProcIndices) { 1645243830Sdim const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 1646243830Sdim if (SchedRW.TheDef) { 1647243830Sdim if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) { 1648296417Sdim for (unsigned Idx : ProcIndices) 1649296417Sdim addWriteRes(SchedRW.TheDef, Idx); 1650243830Sdim } 1651243830Sdim else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) { 1652296417Sdim for (unsigned Idx : ProcIndices) 1653296417Sdim addReadAdvance(SchedRW.TheDef, Idx); 1654243830Sdim } 1655243830Sdim } 1656243830Sdim for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1657243830Sdim AI != AE; ++AI) { 1658243830Sdim IdxVec AliasProcIndices; 1659243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1660243830Sdim AliasProcIndices.push_back( 1661243830Sdim getProcModel((*AI)->getValueAsDef("SchedModel")).Index); 1662243830Sdim } 1663243830Sdim else 1664243830Sdim AliasProcIndices = ProcIndices; 1665243830Sdim const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 1666243830Sdim assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes"); 1667243830Sdim 1668243830Sdim IdxVec ExpandedRWs; 1669243830Sdim expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead); 1670243830Sdim for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 1671243830Sdim SI != SE; ++SI) { 1672243830Sdim collectRWResources(*SI, IsRead, AliasProcIndices); 1673243830Sdim } 1674243830Sdim } 1675243830Sdim} 1676243830Sdim 1677243830Sdim// Collect resources for a set of read/write types and processor indices. 1678296417Sdimvoid CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes, 1679296417Sdim ArrayRef<unsigned> Reads, 1680296417Sdim ArrayRef<unsigned> ProcIndices) { 1681296417Sdim for (unsigned Idx : Writes) 1682296417Sdim collectRWResources(Idx, /*IsRead=*/false, ProcIndices); 1683243830Sdim 1684296417Sdim for (unsigned Idx : Reads) 1685296417Sdim collectRWResources(Idx, /*IsRead=*/true, ProcIndices); 1686243830Sdim} 1687243830Sdim 1688243830Sdim// Find the processor's resource units for this kind of resource. 1689243830SdimRecord *CodeGenSchedModels::findProcResUnits(Record *ProcResKind, 1690243830Sdim const CodeGenProcModel &PM) const { 1691243830Sdim if (ProcResKind->isSubClassOf("ProcResourceUnits")) 1692243830Sdim return ProcResKind; 1693243830Sdim 1694276479Sdim Record *ProcUnitDef = nullptr; 1695309124Sdim assert(!ProcResourceDefs.empty()); 1696309124Sdim assert(!ProcResGroups.empty()); 1697243830Sdim 1698243830Sdim for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end(); 1699243830Sdim RI != RE; ++RI) { 1700243830Sdim 1701243830Sdim if ((*RI)->getValueAsDef("Kind") == ProcResKind 1702243830Sdim && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) { 1703243830Sdim if (ProcUnitDef) { 1704243830Sdim PrintFatalError((*RI)->getLoc(), 1705243830Sdim "Multiple ProcessorResourceUnits associated with " 1706243830Sdim + ProcResKind->getName()); 1707243830Sdim } 1708243830Sdim ProcUnitDef = *RI; 1709243830Sdim } 1710243830Sdim } 1711249423Sdim for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end(); 1712249423Sdim RI != RE; ++RI) { 1713249423Sdim 1714249423Sdim if (*RI == ProcResKind 1715249423Sdim && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) { 1716249423Sdim if (ProcUnitDef) { 1717249423Sdim PrintFatalError((*RI)->getLoc(), 1718249423Sdim "Multiple ProcessorResourceUnits associated with " 1719249423Sdim + ProcResKind->getName()); 1720249423Sdim } 1721249423Sdim ProcUnitDef = *RI; 1722249423Sdim } 1723249423Sdim } 1724243830Sdim if (!ProcUnitDef) { 1725243830Sdim PrintFatalError(ProcResKind->getLoc(), 1726243830Sdim "No ProcessorResources associated with " 1727243830Sdim + ProcResKind->getName()); 1728243830Sdim } 1729243830Sdim return ProcUnitDef; 1730243830Sdim} 1731243830Sdim 1732243830Sdim// Iteratively add a resource and its super resources. 1733243830Sdimvoid CodeGenSchedModels::addProcResource(Record *ProcResKind, 1734243830Sdim CodeGenProcModel &PM) { 1735314564Sdim while (true) { 1736243830Sdim Record *ProcResUnits = findProcResUnits(ProcResKind, PM); 1737243830Sdim 1738243830Sdim // See if this ProcResource is already associated with this processor. 1739314564Sdim if (is_contained(PM.ProcResourceDefs, ProcResUnits)) 1740243830Sdim return; 1741243830Sdim 1742243830Sdim PM.ProcResourceDefs.push_back(ProcResUnits); 1743249423Sdim if (ProcResUnits->isSubClassOf("ProcResGroup")) 1744249423Sdim return; 1745249423Sdim 1746243830Sdim if (!ProcResUnits->getValueInit("Super")->isComplete()) 1747243830Sdim return; 1748243830Sdim 1749243830Sdim ProcResKind = ProcResUnits->getValueAsDef("Super"); 1750243830Sdim } 1751243830Sdim} 1752243830Sdim 1753243830Sdim// Add resources for a SchedWrite to this processor if they don't exist. 1754243830Sdimvoid CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) { 1755243830Sdim assert(PIdx && "don't add resources to an invalid Processor model"); 1756243830Sdim 1757243830Sdim RecVec &WRDefs = ProcModels[PIdx].WriteResDefs; 1758314564Sdim if (is_contained(WRDefs, ProcWriteResDef)) 1759243830Sdim return; 1760243830Sdim WRDefs.push_back(ProcWriteResDef); 1761243830Sdim 1762243830Sdim // Visit ProcResourceKinds referenced by the newly discovered WriteRes. 1763243830Sdim RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources"); 1764243830Sdim for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end(); 1765243830Sdim WritePRI != WritePRE; ++WritePRI) { 1766243830Sdim addProcResource(*WritePRI, ProcModels[PIdx]); 1767243830Sdim } 1768243830Sdim} 1769243830Sdim 1770243830Sdim// Add resources for a ReadAdvance to this processor if they don't exist. 1771243830Sdimvoid CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef, 1772243830Sdim unsigned PIdx) { 1773243830Sdim RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs; 1774314564Sdim if (is_contained(RADefs, ProcReadAdvanceDef)) 1775243830Sdim return; 1776243830Sdim RADefs.push_back(ProcReadAdvanceDef); 1777243830Sdim} 1778243830Sdim 1779243830Sdimunsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const { 1780314564Sdim RecIter PRPos = find(ProcResourceDefs, PRDef); 1781243830Sdim if (PRPos == ProcResourceDefs.end()) 1782243830Sdim PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in " 1783243830Sdim "the ProcResources list for " + ModelName); 1784243830Sdim // Idx=0 is reserved for invalid. 1785243830Sdim return 1 + (PRPos - ProcResourceDefs.begin()); 1786243830Sdim} 1787243830Sdim 1788309124Sdimbool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const { 1789309124Sdim for (const Record *TheDef : UnsupportedFeaturesDefs) { 1790309124Sdim for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) { 1791309124Sdim if (TheDef->getName() == PredDef->getName()) 1792309124Sdim return true; 1793309124Sdim } 1794309124Sdim } 1795309124Sdim return false; 1796309124Sdim} 1797309124Sdim 1798239310Sdim#ifndef NDEBUG 1799243830Sdimvoid CodeGenProcModel::dump() const { 1800243830Sdim dbgs() << Index << ": " << ModelName << " " 1801243830Sdim << (ModelDef ? ModelDef->getName() : "inferred") << " " 1802243830Sdim << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n'; 1803243830Sdim} 1804243830Sdim 1805243830Sdimvoid CodeGenSchedRW::dump() const { 1806243830Sdim dbgs() << Name << (IsVariadic ? " (V) " : " "); 1807243830Sdim if (IsSequence) { 1808243830Sdim dbgs() << "("; 1809243830Sdim dumpIdxVec(Sequence); 1810243830Sdim dbgs() << ")"; 1811239310Sdim } 1812239310Sdim} 1813243830Sdim 1814243830Sdimvoid CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const { 1815249423Sdim dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n' 1816243830Sdim << " Writes: "; 1817243830Sdim for (unsigned i = 0, N = Writes.size(); i < N; ++i) { 1818243830Sdim SchedModels->getSchedWrite(Writes[i]).dump(); 1819243830Sdim if (i < N-1) { 1820243830Sdim dbgs() << '\n'; 1821243830Sdim dbgs().indent(10); 1822243830Sdim } 1823243830Sdim } 1824243830Sdim dbgs() << "\n Reads: "; 1825243830Sdim for (unsigned i = 0, N = Reads.size(); i < N; ++i) { 1826243830Sdim SchedModels->getSchedRead(Reads[i]).dump(); 1827243830Sdim if (i < N-1) { 1828243830Sdim dbgs() << '\n'; 1829243830Sdim dbgs().indent(10); 1830243830Sdim } 1831243830Sdim } 1832243830Sdim dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n'; 1833249423Sdim if (!Transitions.empty()) { 1834249423Sdim dbgs() << "\n Transitions for Proc "; 1835249423Sdim for (std::vector<CodeGenSchedTransition>::const_iterator 1836249423Sdim TI = Transitions.begin(), TE = Transitions.end(); TI != TE; ++TI) { 1837249423Sdim dumpIdxVec(TI->ProcIndices); 1838249423Sdim } 1839249423Sdim } 1840243830Sdim} 1841243830Sdim 1842243830Sdimvoid PredTransitions::dump() const { 1843243830Sdim dbgs() << "Expanded Variants:\n"; 1844243830Sdim for (std::vector<PredTransition>::const_iterator 1845243830Sdim TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) { 1846243830Sdim dbgs() << "{"; 1847243830Sdim for (SmallVectorImpl<PredCheck>::const_iterator 1848243830Sdim PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end(); 1849243830Sdim PCI != PCE; ++PCI) { 1850243830Sdim if (PCI != TI->PredTerm.begin()) 1851243830Sdim dbgs() << ", "; 1852243830Sdim dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name 1853243830Sdim << ":" << PCI->Predicate->getName(); 1854243830Sdim } 1855243830Sdim dbgs() << "},\n => {"; 1856314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1857243830Sdim WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end(); 1858243830Sdim WSI != WSE; ++WSI) { 1859243830Sdim dbgs() << "("; 1860243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1861243830Sdim WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 1862243830Sdim if (WI != WSI->begin()) 1863243830Sdim dbgs() << ", "; 1864243830Sdim dbgs() << SchedModels.getSchedWrite(*WI).Name; 1865243830Sdim } 1866243830Sdim dbgs() << "),"; 1867243830Sdim } 1868243830Sdim dbgs() << "}\n"; 1869243830Sdim } 1870243830Sdim} 1871243830Sdim#endif // NDEBUG 1872