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