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