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