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