utils/TableGen/CodeGenSchedule.cpp

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