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