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