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