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