contrib/llvm/utils/TableGen/CodeGenSchedule.cpp

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