utils/TableGen/CodeGenSchedule.cpp

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