utils/TableGen/CodeGenSchedule.cpp

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