utils/TableGen/CodeGenSchedule.cpp

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