Home | History | Annotate | Download | only in TableGen
      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   for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) {
    894     assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!");
    895     Record *Rec = SchedClasses[SCIdx].InstRWs[I];
    896     const RecVec *InstDefs = Sets.expand(Rec);
    897     RecIter II = InstDefs->begin(), IE = InstDefs->end();
    898     for (; II != IE; ++II) {
    899       if (InstrClassMap[*II] == SCIdx)
    900         break;
    901     }
    902     // If this class no longer has any instructions mapped to it, it has become
    903     // irrelevant.
    904     if (II == IE)
    905       continue;
    906     IdxVec Writes, Reads;
    907     findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
    908     unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index;
    909     IdxVec ProcIndices(1, PIdx);
    910     inferFromRW(Writes, Reads, SCIdx, ProcIndices); // May mutate SchedClasses.
    911   }
    912 }
    913 
    914 namespace {
    915 // Helper for substituteVariantOperand.
    916 struct TransVariant {
    917   Record *VarOrSeqDef;  // Variant or sequence.
    918   unsigned RWIdx;       // Index of this variant or sequence's matched type.
    919   unsigned ProcIdx;     // Processor model index or zero for any.
    920   unsigned TransVecIdx; // Index into PredTransitions::TransVec.
    921 
    922   TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti):
    923     VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {}
    924 };
    925 
    926 // Associate a predicate with the SchedReadWrite that it guards.
    927 // RWIdx is the index of the read/write variant.
    928 struct PredCheck {
    929   bool IsRead;
    930   unsigned RWIdx;
    931   Record *Predicate;
    932 
    933   PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {}
    934 };
    935 
    936 // A Predicate transition is a list of RW sequences guarded by a PredTerm.
    937 struct PredTransition {
    938   // A predicate term is a conjunction of PredChecks.
    939   SmallVector<PredCheck, 4> PredTerm;
    940   SmallVector<SmallVector<unsigned,4>, 16> WriteSequences;
    941   SmallVector<SmallVector<unsigned,4>, 16> ReadSequences;
    942   SmallVector<unsigned, 4> ProcIndices;
    943 };
    944 
    945 // Encapsulate a set of partially constructed transitions.
    946 // The results are built by repeated calls to substituteVariants.
    947 class PredTransitions {
    948   CodeGenSchedModels &SchedModels;
    949 
    950 public:
    951   std::vector<PredTransition> TransVec;
    952 
    953   PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {}
    954 
    955   void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq,
    956                                 bool IsRead, unsigned StartIdx);
    957 
    958   void substituteVariants(const PredTransition &Trans);
    959 
    960 #ifndef NDEBUG
    961   void dump() const;
    962 #endif
    963 
    964 private:
    965   bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term);
    966   void getIntersectingVariants(
    967     const CodeGenSchedRW &SchedRW, unsigned TransIdx,
    968     std::vector<TransVariant> &IntersectingVariants);
    969   void pushVariant(const TransVariant &VInfo, bool IsRead);
    970 };
    971 } // anonymous
    972 
    973 // Return true if this predicate is mutually exclusive with a PredTerm. This
    974 // degenerates into checking if the predicate is mutually exclusive with any
    975 // predicate in the Term's conjunction.
    976 //
    977 // All predicates associated with a given SchedRW are considered mutually
    978 // exclusive. This should work even if the conditions expressed by the
    979 // predicates are not exclusive because the predicates for a given SchedWrite
    980 // are always checked in the order they are defined in the .td file. Later
    981 // conditions implicitly negate any prior condition.
    982 bool PredTransitions::mutuallyExclusive(Record *PredDef,
    983                                         ArrayRef<PredCheck> Term) {
    984 
    985   for (ArrayRef<PredCheck>::iterator I = Term.begin(), E = Term.end();
    986        I != E; ++I) {
    987     if (I->Predicate == PredDef)
    988       return false;
    989 
    990     const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(I->RWIdx, I->IsRead);
    991     assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant");
    992     RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants");
    993     for (RecIter VI = Variants.begin(), VE = Variants.end(); VI != VE; ++VI) {
    994       if ((*VI)->getValueAsDef("Predicate") == PredDef)
    995         return true;
    996     }
    997   }
    998   return false;
    999 }
   1000 
   1001 static bool hasAliasedVariants(const CodeGenSchedRW &RW,
   1002                                CodeGenSchedModels &SchedModels) {
   1003   if (RW.HasVariants)
   1004     return true;
   1005 
   1006   for (RecIter I = RW.Aliases.begin(), E = RW.Aliases.end(); I != E; ++I) {
   1007     const CodeGenSchedRW &AliasRW =
   1008       SchedModels.getSchedRW((*I)->getValueAsDef("AliasRW"));
   1009     if (AliasRW.HasVariants)
   1010       return true;
   1011     if (AliasRW.IsSequence) {
   1012       IdxVec ExpandedRWs;
   1013       SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead);
   1014       for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
   1015            SI != SE; ++SI) {
   1016         if (hasAliasedVariants(SchedModels.getSchedRW(*SI, AliasRW.IsRead),
   1017                                SchedModels)) {
   1018           return true;
   1019         }
   1020       }
   1021     }
   1022   }
   1023   return false;
   1024 }
   1025 
   1026 static bool hasVariant(ArrayRef<PredTransition> Transitions,
   1027                        CodeGenSchedModels &SchedModels) {
   1028   for (ArrayRef<PredTransition>::iterator
   1029          PTI = Transitions.begin(), PTE = Transitions.end();
   1030        PTI != PTE; ++PTI) {
   1031     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1032            WSI = PTI->WriteSequences.begin(), WSE = PTI->WriteSequences.end();
   1033          WSI != WSE; ++WSI) {
   1034       for (SmallVectorImpl<unsigned>::const_iterator
   1035              WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
   1036         if (hasAliasedVariants(SchedModels.getSchedWrite(*WI), SchedModels))
   1037           return true;
   1038       }
   1039     }
   1040     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1041            RSI = PTI->ReadSequences.begin(), RSE = PTI->ReadSequences.end();
   1042          RSI != RSE; ++RSI) {
   1043       for (SmallVectorImpl<unsigned>::const_iterator
   1044              RI = RSI->begin(), RE = RSI->end(); RI != RE; ++RI) {
   1045         if (hasAliasedVariants(SchedModels.getSchedRead(*RI), SchedModels))
   1046           return true;
   1047       }
   1048     }
   1049   }
   1050   return false;
   1051 }
   1052 
   1053 // Populate IntersectingVariants with any variants or aliased sequences of the
   1054 // given SchedRW whose processor indices and predicates are not mutually
   1055 // exclusive with the given transition.
   1056 void PredTransitions::getIntersectingVariants(
   1057   const CodeGenSchedRW &SchedRW, unsigned TransIdx,
   1058   std::vector<TransVariant> &IntersectingVariants) {
   1059 
   1060   bool GenericRW = false;
   1061 
   1062   std::vector<TransVariant> Variants;
   1063   if (SchedRW.HasVariants) {
   1064     unsigned VarProcIdx = 0;
   1065     if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) {
   1066       Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel");
   1067       VarProcIdx = SchedModels.getProcModel(ModelDef).Index;
   1068     }
   1069     // Push each variant. Assign TransVecIdx later.
   1070     const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants");
   1071     for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
   1072       Variants.push_back(TransVariant(*RI, SchedRW.Index, VarProcIdx, 0));
   1073     if (VarProcIdx == 0)
   1074       GenericRW = true;
   1075   }
   1076   for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
   1077        AI != AE; ++AI) {
   1078     // If either the SchedAlias itself or the SchedReadWrite that it aliases
   1079     // to is defined within a processor model, constrain all variants to
   1080     // that processor.
   1081     unsigned AliasProcIdx = 0;
   1082     if ((*AI)->getValueInit("SchedModel")->isComplete()) {
   1083       Record *ModelDef = (*AI)->getValueAsDef("SchedModel");
   1084       AliasProcIdx = SchedModels.getProcModel(ModelDef).Index;
   1085     }
   1086     const CodeGenSchedRW &AliasRW =
   1087       SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW"));
   1088 
   1089     if (AliasRW.HasVariants) {
   1090       const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants");
   1091       for (RecIter RI = VarDefs.begin(), RE = VarDefs.end(); RI != RE; ++RI)
   1092         Variants.push_back(TransVariant(*RI, AliasRW.Index, AliasProcIdx, 0));
   1093     }
   1094     if (AliasRW.IsSequence) {
   1095       Variants.push_back(
   1096         TransVariant(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0));
   1097     }
   1098     if (AliasProcIdx == 0)
   1099       GenericRW = true;
   1100   }
   1101   for (unsigned VIdx = 0, VEnd = Variants.size(); VIdx != VEnd; ++VIdx) {
   1102     TransVariant &Variant = Variants[VIdx];
   1103     // Don't expand variants if the processor models don't intersect.
   1104     // A zero processor index means any processor.
   1105     SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices;
   1106     if (ProcIndices[0] && Variants[VIdx].ProcIdx) {
   1107       unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(),
   1108                                 Variant.ProcIdx);
   1109       if (!Cnt)
   1110         continue;
   1111       if (Cnt > 1) {
   1112         const CodeGenProcModel &PM =
   1113           *(SchedModels.procModelBegin() + Variant.ProcIdx);
   1114         PrintFatalError(Variant.VarOrSeqDef->getLoc(),
   1115                         "Multiple variants defined for processor " +
   1116                         PM.ModelName +
   1117                         " Ensure only one SchedAlias exists per RW.");
   1118       }
   1119     }
   1120     if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) {
   1121       Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate");
   1122       if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm))
   1123         continue;
   1124     }
   1125     if (IntersectingVariants.empty()) {
   1126       // The first variant builds on the existing transition.
   1127       Variant.TransVecIdx = TransIdx;
   1128       IntersectingVariants.push_back(Variant);
   1129     }
   1130     else {
   1131       // Push another copy of the current transition for more variants.
   1132       Variant.TransVecIdx = TransVec.size();
   1133       IntersectingVariants.push_back(Variant);
   1134       TransVec.push_back(TransVec[TransIdx]);
   1135     }
   1136   }
   1137   if (GenericRW && IntersectingVariants.empty()) {
   1138     PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has "
   1139                     "a matching predicate on any processor");
   1140   }
   1141 }
   1142 
   1143 // Push the Reads/Writes selected by this variant onto the PredTransition
   1144 // specified by VInfo.
   1145 void PredTransitions::
   1146 pushVariant(const TransVariant &VInfo, bool IsRead) {
   1147 
   1148   PredTransition &Trans = TransVec[VInfo.TransVecIdx];
   1149 
   1150   // If this operand transition is reached through a processor-specific alias,
   1151   // then the whole transition is specific to this processor.
   1152   if (VInfo.ProcIdx != 0)
   1153     Trans.ProcIndices.assign(1, VInfo.ProcIdx);
   1154 
   1155   IdxVec SelectedRWs;
   1156   if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) {
   1157     Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate");
   1158     Trans.PredTerm.push_back(PredCheck(IsRead, VInfo.RWIdx,PredDef));
   1159     RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected");
   1160     SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead);
   1161   }
   1162   else {
   1163     assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") &&
   1164            "variant must be a SchedVariant or aliased WriteSequence");
   1165     SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead));
   1166   }
   1167 
   1168   const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead);
   1169 
   1170   SmallVectorImpl<SmallVector<unsigned,4> > &RWSequences = IsRead
   1171     ? Trans.ReadSequences : Trans.WriteSequences;
   1172   if (SchedRW.IsVariadic) {
   1173     unsigned OperIdx = RWSequences.size()-1;
   1174     // Make N-1 copies of this transition's last sequence.
   1175     for (unsigned i = 1, e = SelectedRWs.size(); i != e; ++i) {
   1176       // Create a temporary copy the vector could reallocate.
   1177       RWSequences.reserve(RWSequences.size() + 1);
   1178       RWSequences.push_back(RWSequences[OperIdx]);
   1179     }
   1180     // Push each of the N elements of the SelectedRWs onto a copy of the last
   1181     // sequence (split the current operand into N operands).
   1182     // Note that write sequences should be expanded within this loop--the entire
   1183     // sequence belongs to a single operand.
   1184     for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
   1185          RWI != RWE; ++RWI, ++OperIdx) {
   1186       IdxVec ExpandedRWs;
   1187       if (IsRead)
   1188         ExpandedRWs.push_back(*RWI);
   1189       else
   1190         SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
   1191       RWSequences[OperIdx].insert(RWSequences[OperIdx].end(),
   1192                                   ExpandedRWs.begin(), ExpandedRWs.end());
   1193     }
   1194     assert(OperIdx == RWSequences.size() && "missed a sequence");
   1195   }
   1196   else {
   1197     // Push this transition's expanded sequence onto this transition's last
   1198     // sequence (add to the current operand's sequence).
   1199     SmallVectorImpl<unsigned> &Seq = RWSequences.back();
   1200     IdxVec ExpandedRWs;
   1201     for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
   1202          RWI != RWE; ++RWI) {
   1203       if (IsRead)
   1204         ExpandedRWs.push_back(*RWI);
   1205       else
   1206         SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead);
   1207     }
   1208     Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end());
   1209   }
   1210 }
   1211 
   1212 // RWSeq is a sequence of all Reads or all Writes for the next read or write
   1213 // operand. StartIdx is an index into TransVec where partial results
   1214 // starts. RWSeq must be applied to all transitions between StartIdx and the end
   1215 // of TransVec.
   1216 void PredTransitions::substituteVariantOperand(
   1217   const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) {
   1218 
   1219   // Visit each original RW within the current sequence.
   1220   for (SmallVectorImpl<unsigned>::const_iterator
   1221          RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) {
   1222     const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead);
   1223     // Push this RW on all partial PredTransitions or distribute variants.
   1224     // New PredTransitions may be pushed within this loop which should not be
   1225     // revisited (TransEnd must be loop invariant).
   1226     for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size();
   1227          TransIdx != TransEnd; ++TransIdx) {
   1228       // In the common case, push RW onto the current operand's sequence.
   1229       if (!hasAliasedVariants(SchedRW, SchedModels)) {
   1230         if (IsRead)
   1231           TransVec[TransIdx].ReadSequences.back().push_back(*RWI);
   1232         else
   1233           TransVec[TransIdx].WriteSequences.back().push_back(*RWI);
   1234         continue;
   1235       }
   1236       // Distribute this partial PredTransition across intersecting variants.
   1237       // This will push a copies of TransVec[TransIdx] on the back of TransVec.
   1238       std::vector<TransVariant> IntersectingVariants;
   1239       getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants);
   1240       // Now expand each variant on top of its copy of the transition.
   1241       for (std::vector<TransVariant>::const_iterator
   1242              IVI = IntersectingVariants.begin(),
   1243              IVE = IntersectingVariants.end();
   1244            IVI != IVE; ++IVI) {
   1245         pushVariant(*IVI, IsRead);
   1246       }
   1247     }
   1248   }
   1249 }
   1250 
   1251 // For each variant of a Read/Write in Trans, substitute the sequence of
   1252 // Read/Writes guarded by the variant. This is exponential in the number of
   1253 // variant Read/Writes, but in practice detection of mutually exclusive
   1254 // predicates should result in linear growth in the total number variants.
   1255 //
   1256 // This is one step in a breadth-first search of nested variants.
   1257 void PredTransitions::substituteVariants(const PredTransition &Trans) {
   1258   // Build up a set of partial results starting at the back of
   1259   // PredTransitions. Remember the first new transition.
   1260   unsigned StartIdx = TransVec.size();
   1261   TransVec.resize(TransVec.size() + 1);
   1262   TransVec.back().PredTerm = Trans.PredTerm;
   1263   TransVec.back().ProcIndices = Trans.ProcIndices;
   1264 
   1265   // Visit each original write sequence.
   1266   for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1267          WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end();
   1268        WSI != WSE; ++WSI) {
   1269     // Push a new (empty) write sequence onto all partial Transitions.
   1270     for (std::vector<PredTransition>::iterator I =
   1271            TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
   1272       I->WriteSequences.resize(I->WriteSequences.size() + 1);
   1273     }
   1274     substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx);
   1275   }
   1276   // Visit each original read sequence.
   1277   for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1278          RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end();
   1279        RSI != RSE; ++RSI) {
   1280     // Push a new (empty) read sequence onto all partial Transitions.
   1281     for (std::vector<PredTransition>::iterator I =
   1282            TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) {
   1283       I->ReadSequences.resize(I->ReadSequences.size() + 1);
   1284     }
   1285     substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx);
   1286   }
   1287 }
   1288 
   1289 // Create a new SchedClass for each variant found by inferFromRW. Pass
   1290 static void inferFromTransitions(ArrayRef<PredTransition> LastTransitions,
   1291                                  unsigned FromClassIdx,
   1292                                  CodeGenSchedModels &SchedModels) {
   1293   // For each PredTransition, create a new CodeGenSchedTransition, which usually
   1294   // requires creating a new SchedClass.
   1295   for (ArrayRef<PredTransition>::iterator
   1296          I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) {
   1297     IdxVec OperWritesVariant;
   1298     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1299            WSI = I->WriteSequences.begin(), WSE = I->WriteSequences.end();
   1300          WSI != WSE; ++WSI) {
   1301       // Create a new write representing the expanded sequence.
   1302       OperWritesVariant.push_back(
   1303         SchedModels.findOrInsertRW(*WSI, /*IsRead=*/false));
   1304     }
   1305     IdxVec OperReadsVariant;
   1306     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1307            RSI = I->ReadSequences.begin(), RSE = I->ReadSequences.end();
   1308          RSI != RSE; ++RSI) {
   1309       // Create a new read representing the expanded sequence.
   1310       OperReadsVariant.push_back(
   1311         SchedModels.findOrInsertRW(*RSI, /*IsRead=*/true));
   1312     }
   1313     IdxVec ProcIndices(I->ProcIndices.begin(), I->ProcIndices.end());
   1314     CodeGenSchedTransition SCTrans;
   1315     SCTrans.ToClassIdx =
   1316       SchedModels.addSchedClass(/*ItinClassDef=*/0, OperWritesVariant,
   1317                                 OperReadsVariant, ProcIndices);
   1318     SCTrans.ProcIndices = ProcIndices;
   1319     // The final PredTerm is unique set of predicates guarding the transition.
   1320     RecVec Preds;
   1321     for (SmallVectorImpl<PredCheck>::const_iterator
   1322            PI = I->PredTerm.begin(), PE = I->PredTerm.end(); PI != PE; ++PI) {
   1323       Preds.push_back(PI->Predicate);
   1324     }
   1325     RecIter PredsEnd = std::unique(Preds.begin(), Preds.end());
   1326     Preds.resize(PredsEnd - Preds.begin());
   1327     SCTrans.PredTerm = Preds;
   1328     SchedModels.getSchedClass(FromClassIdx).Transitions.push_back(SCTrans);
   1329   }
   1330 }
   1331 
   1332 // Create new SchedClasses for the given ReadWrite list. If any of the
   1333 // ReadWrites refers to a SchedVariant, create a new SchedClass for each variant
   1334 // of the ReadWrite list, following Aliases if necessary.
   1335 void CodeGenSchedModels::inferFromRW(const IdxVec &OperWrites,
   1336                                      const IdxVec &OperReads,
   1337                                      unsigned FromClassIdx,
   1338                                      const IdxVec &ProcIndices) {
   1339   DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); dbgs() << ") ");
   1340 
   1341   // Create a seed transition with an empty PredTerm and the expanded sequences
   1342   // of SchedWrites for the current SchedClass.
   1343   std::vector<PredTransition> LastTransitions;
   1344   LastTransitions.resize(1);
   1345   LastTransitions.back().ProcIndices.append(ProcIndices.begin(),
   1346                                             ProcIndices.end());
   1347 
   1348   for (IdxIter I = OperWrites.begin(), E = OperWrites.end(); I != E; ++I) {
   1349     IdxVec WriteSeq;
   1350     expandRWSequence(*I, WriteSeq, /*IsRead=*/false);
   1351     unsigned Idx = LastTransitions[0].WriteSequences.size();
   1352     LastTransitions[0].WriteSequences.resize(Idx + 1);
   1353     SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences[Idx];
   1354     for (IdxIter WI = WriteSeq.begin(), WE = WriteSeq.end(); WI != WE; ++WI)
   1355       Seq.push_back(*WI);
   1356     DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
   1357   }
   1358   DEBUG(dbgs() << " Reads: ");
   1359   for (IdxIter I = OperReads.begin(), E = OperReads.end(); I != E; ++I) {
   1360     IdxVec ReadSeq;
   1361     expandRWSequence(*I, ReadSeq, /*IsRead=*/true);
   1362     unsigned Idx = LastTransitions[0].ReadSequences.size();
   1363     LastTransitions[0].ReadSequences.resize(Idx + 1);
   1364     SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences[Idx];
   1365     for (IdxIter RI = ReadSeq.begin(), RE = ReadSeq.end(); RI != RE; ++RI)
   1366       Seq.push_back(*RI);
   1367     DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") ");
   1368   }
   1369   DEBUG(dbgs() << '\n');
   1370 
   1371   // Collect all PredTransitions for individual operands.
   1372   // Iterate until no variant writes remain.
   1373   while (hasVariant(LastTransitions, *this)) {
   1374     PredTransitions Transitions(*this);
   1375     for (std::vector<PredTransition>::const_iterator
   1376            I = LastTransitions.begin(), E = LastTransitions.end();
   1377          I != E; ++I) {
   1378       Transitions.substituteVariants(*I);
   1379     }
   1380     DEBUG(Transitions.dump());
   1381     LastTransitions.swap(Transitions.TransVec);
   1382   }
   1383   // If the first transition has no variants, nothing to do.
   1384   if (LastTransitions[0].PredTerm.empty())
   1385     return;
   1386 
   1387   // WARNING: We are about to mutate the SchedClasses vector. Do not refer to
   1388   // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions.
   1389   inferFromTransitions(LastTransitions, FromClassIdx, *this);
   1390 }
   1391 
   1392 // Check if any processor resource group contains all resource records in
   1393 // SubUnits.
   1394 bool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) {
   1395   for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
   1396     if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
   1397       continue;
   1398     RecVec SuperUnits =
   1399       PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
   1400     RecIter RI = SubUnits.begin(), RE = SubUnits.end();
   1401     for ( ; RI != RE; ++RI) {
   1402       if (std::find(SuperUnits.begin(), SuperUnits.end(), *RI)
   1403           == SuperUnits.end()) {
   1404         break;
   1405       }
   1406     }
   1407     if (RI == RE)
   1408       return true;
   1409   }
   1410   return false;
   1411 }
   1412 
   1413 // Verify that overlapping groups have a common supergroup.
   1414 void CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) {
   1415   for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) {
   1416     if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup"))
   1417       continue;
   1418     RecVec CheckUnits =
   1419       PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources");
   1420     for (unsigned j = i+1; j < e; ++j) {
   1421       if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup"))
   1422         continue;
   1423       RecVec OtherUnits =
   1424         PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources");
   1425       if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(),
   1426                              OtherUnits.begin(), OtherUnits.end())
   1427           != CheckUnits.end()) {
   1428         // CheckUnits and OtherUnits overlap
   1429         OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(),
   1430                           CheckUnits.end());
   1431         if (!hasSuperGroup(OtherUnits, PM)) {
   1432           PrintFatalError((PM.ProcResourceDefs[i])->getLoc(),
   1433                           "proc resource group overlaps with "
   1434                           + PM.ProcResourceDefs[j]->getName()
   1435                           + " but no supergroup contains both.");
   1436         }
   1437       }
   1438     }
   1439   }
   1440 }
   1441 
   1442 // Collect and sort WriteRes, ReadAdvance, and ProcResources.
   1443 void CodeGenSchedModels::collectProcResources() {
   1444   // Add any subtarget-specific SchedReadWrites that are directly associated
   1445   // with processor resources. Refer to the parent SchedClass's ProcIndices to
   1446   // determine which processors they apply to.
   1447   for (SchedClassIter SCI = schedClassBegin(), SCE = schedClassEnd();
   1448        SCI != SCE; ++SCI) {
   1449     if (SCI->ItinClassDef)
   1450       collectItinProcResources(SCI->ItinClassDef);
   1451     else {
   1452       // This class may have a default ReadWrite list which can be overriden by
   1453       // InstRW definitions.
   1454       if (!SCI->InstRWs.empty()) {
   1455         for (RecIter RWI = SCI->InstRWs.begin(), RWE = SCI->InstRWs.end();
   1456              RWI != RWE; ++RWI) {
   1457           Record *RWModelDef = (*RWI)->getValueAsDef("SchedModel");
   1458           IdxVec ProcIndices(1, getProcModel(RWModelDef).Index);
   1459           IdxVec Writes, Reads;
   1460           findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"),
   1461                   Writes, Reads);
   1462           collectRWResources(Writes, Reads, ProcIndices);
   1463         }
   1464       }
   1465       collectRWResources(SCI->Writes, SCI->Reads, SCI->ProcIndices);
   1466     }
   1467   }
   1468   // Add resources separately defined by each subtarget.
   1469   RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes");
   1470   for (RecIter WRI = WRDefs.begin(), WRE = WRDefs.end(); WRI != WRE; ++WRI) {
   1471     Record *ModelDef = (*WRI)->getValueAsDef("SchedModel");
   1472     addWriteRes(*WRI, getProcModel(ModelDef).Index);
   1473   }
   1474   RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance");
   1475   for (RecIter RAI = RADefs.begin(), RAE = RADefs.end(); RAI != RAE; ++RAI) {
   1476     Record *ModelDef = (*RAI)->getValueAsDef("SchedModel");
   1477     addReadAdvance(*RAI, getProcModel(ModelDef).Index);
   1478   }
   1479   // Add ProcResGroups that are defined within this processor model, which may
   1480   // not be directly referenced but may directly specify a buffer size.
   1481   RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
   1482   for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end();
   1483        RI != RE; ++RI) {
   1484     if (!(*RI)->getValueInit("SchedModel")->isComplete())
   1485       continue;
   1486     CodeGenProcModel &PM = getProcModel((*RI)->getValueAsDef("SchedModel"));
   1487     RecIter I = std::find(PM.ProcResourceDefs.begin(),
   1488                           PM.ProcResourceDefs.end(), *RI);
   1489     if (I == PM.ProcResourceDefs.end())
   1490       PM.ProcResourceDefs.push_back(*RI);
   1491   }
   1492   // Finalize each ProcModel by sorting the record arrays.
   1493   for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
   1494     CodeGenProcModel &PM = ProcModels[PIdx];
   1495     std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(),
   1496               LessRecord());
   1497     std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(),
   1498               LessRecord());
   1499     std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(),
   1500               LessRecord());
   1501     DEBUG(
   1502       PM.dump();
   1503       dbgs() << "WriteResDefs: ";
   1504       for (RecIter RI = PM.WriteResDefs.begin(),
   1505              RE = PM.WriteResDefs.end(); RI != RE; ++RI) {
   1506         if ((*RI)->isSubClassOf("WriteRes"))
   1507           dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " ";
   1508         else
   1509           dbgs() << (*RI)->getName() << " ";
   1510       }
   1511       dbgs() << "\nReadAdvanceDefs: ";
   1512       for (RecIter RI = PM.ReadAdvanceDefs.begin(),
   1513              RE = PM.ReadAdvanceDefs.end(); RI != RE; ++RI) {
   1514         if ((*RI)->isSubClassOf("ReadAdvance"))
   1515           dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " ";
   1516         else
   1517           dbgs() << (*RI)->getName() << " ";
   1518       }
   1519       dbgs() << "\nProcResourceDefs: ";
   1520       for (RecIter RI = PM.ProcResourceDefs.begin(),
   1521              RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) {
   1522         dbgs() << (*RI)->getName() << " ";
   1523       }
   1524       dbgs() << '\n');
   1525     verifyProcResourceGroups(PM);
   1526   }
   1527 }
   1528 
   1529 // Collect itinerary class resources for each processor.
   1530 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) {
   1531   for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
   1532     const CodeGenProcModel &PM = ProcModels[PIdx];
   1533     // For all ItinRW entries.
   1534     bool HasMatch = false;
   1535     for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
   1536          II != IE; ++II) {
   1537       RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses");
   1538       if (!std::count(Matched.begin(), Matched.end(), ItinClassDef))
   1539         continue;
   1540       if (HasMatch)
   1541         PrintFatalError((*II)->getLoc(), "Duplicate itinerary class "
   1542                         + ItinClassDef->getName()
   1543                         + " in ItinResources for " + PM.ModelName);
   1544       HasMatch = true;
   1545       IdxVec Writes, Reads;
   1546       findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);
   1547       IdxVec ProcIndices(1, PIdx);
   1548       collectRWResources(Writes, Reads, ProcIndices);
   1549     }
   1550   }
   1551 }
   1552 
   1553 void CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead,
   1554                                             const IdxVec &ProcIndices) {
   1555   const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead);
   1556   if (SchedRW.TheDef) {
   1557     if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) {
   1558       for (IdxIter PI = ProcIndices.begin(), PE = ProcIndices.end();
   1559            PI != PE; ++PI) {
   1560         addWriteRes(SchedRW.TheDef, *PI);
   1561       }
   1562     }
   1563     else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) {
   1564       for (IdxIter PI = ProcIndices.begin(), PE = ProcIndices.end();
   1565            PI != PE; ++PI) {
   1566         addReadAdvance(SchedRW.TheDef, *PI);
   1567       }
   1568     }
   1569   }
   1570   for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end();
   1571        AI != AE; ++AI) {
   1572     IdxVec AliasProcIndices;
   1573     if ((*AI)->getValueInit("SchedModel")->isComplete()) {
   1574       AliasProcIndices.push_back(
   1575         getProcModel((*AI)->getValueAsDef("SchedModel")).Index);
   1576     }
   1577     else
   1578       AliasProcIndices = ProcIndices;
   1579     const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW"));
   1580     assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes");
   1581 
   1582     IdxVec ExpandedRWs;
   1583     expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead);
   1584     for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end();
   1585          SI != SE; ++SI) {
   1586       collectRWResources(*SI, IsRead, AliasProcIndices);
   1587     }
   1588   }
   1589 }
   1590 
   1591 // Collect resources for a set of read/write types and processor indices.
   1592 void CodeGenSchedModels::collectRWResources(const IdxVec &Writes,
   1593                                             const IdxVec &Reads,
   1594                                             const IdxVec &ProcIndices) {
   1595 
   1596   for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI)
   1597     collectRWResources(*WI, /*IsRead=*/false, ProcIndices);
   1598 
   1599   for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI)
   1600     collectRWResources(*RI, /*IsRead=*/true, ProcIndices);
   1601 }
   1602 
   1603 
   1604 // Find the processor's resource units for this kind of resource.
   1605 Record *CodeGenSchedModels::findProcResUnits(Record *ProcResKind,
   1606                                              const CodeGenProcModel &PM) const {
   1607   if (ProcResKind->isSubClassOf("ProcResourceUnits"))
   1608     return ProcResKind;
   1609 
   1610   Record *ProcUnitDef = 0;
   1611   RecVec ProcResourceDefs =
   1612     Records.getAllDerivedDefinitions("ProcResourceUnits");
   1613 
   1614   for (RecIter RI = ProcResourceDefs.begin(), RE = ProcResourceDefs.end();
   1615        RI != RE; ++RI) {
   1616 
   1617     if ((*RI)->getValueAsDef("Kind") == 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   RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup");
   1628   for (RecIter RI = ProcResGroups.begin(), RE = ProcResGroups.end();
   1629        RI != RE; ++RI) {
   1630 
   1631     if (*RI == ProcResKind
   1632         && (*RI)->getValueAsDef("SchedModel") == PM.ModelDef) {
   1633       if (ProcUnitDef) {
   1634         PrintFatalError((*RI)->getLoc(),
   1635                         "Multiple ProcessorResourceUnits associated with "
   1636                         + ProcResKind->getName());
   1637       }
   1638       ProcUnitDef = *RI;
   1639     }
   1640   }
   1641   if (!ProcUnitDef) {
   1642     PrintFatalError(ProcResKind->getLoc(),
   1643                     "No ProcessorResources associated with "
   1644                     + ProcResKind->getName());
   1645   }
   1646   return ProcUnitDef;
   1647 }
   1648 
   1649 // Iteratively add a resource and its super resources.
   1650 void CodeGenSchedModels::addProcResource(Record *ProcResKind,
   1651                                          CodeGenProcModel &PM) {
   1652   for (;;) {
   1653     Record *ProcResUnits = findProcResUnits(ProcResKind, PM);
   1654 
   1655     // See if this ProcResource is already associated with this processor.
   1656     RecIter I = std::find(PM.ProcResourceDefs.begin(),
   1657                           PM.ProcResourceDefs.end(), ProcResUnits);
   1658     if (I != PM.ProcResourceDefs.end())
   1659       return;
   1660 
   1661     PM.ProcResourceDefs.push_back(ProcResUnits);
   1662     if (ProcResUnits->isSubClassOf("ProcResGroup"))
   1663       return;
   1664 
   1665     if (!ProcResUnits->getValueInit("Super")->isComplete())
   1666       return;
   1667 
   1668     ProcResKind = ProcResUnits->getValueAsDef("Super");
   1669   }
   1670 }
   1671 
   1672 // Add resources for a SchedWrite to this processor if they don't exist.
   1673 void CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) {
   1674   assert(PIdx && "don't add resources to an invalid Processor model");
   1675 
   1676   RecVec &WRDefs = ProcModels[PIdx].WriteResDefs;
   1677   RecIter WRI = std::find(WRDefs.begin(), WRDefs.end(), ProcWriteResDef);
   1678   if (WRI != WRDefs.end())
   1679     return;
   1680   WRDefs.push_back(ProcWriteResDef);
   1681 
   1682   // Visit ProcResourceKinds referenced by the newly discovered WriteRes.
   1683   RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources");
   1684   for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end();
   1685        WritePRI != WritePRE; ++WritePRI) {
   1686     addProcResource(*WritePRI, ProcModels[PIdx]);
   1687   }
   1688 }
   1689 
   1690 // Add resources for a ReadAdvance to this processor if they don't exist.
   1691 void CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef,
   1692                                         unsigned PIdx) {
   1693   RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs;
   1694   RecIter I = std::find(RADefs.begin(), RADefs.end(), ProcReadAdvanceDef);
   1695   if (I != RADefs.end())
   1696     return;
   1697   RADefs.push_back(ProcReadAdvanceDef);
   1698 }
   1699 
   1700 unsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const {
   1701   RecIter PRPos = std::find(ProcResourceDefs.begin(), ProcResourceDefs.end(),
   1702                             PRDef);
   1703   if (PRPos == ProcResourceDefs.end())
   1704     PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in "
   1705                     "the ProcResources list for " + ModelName);
   1706   // Idx=0 is reserved for invalid.
   1707   return 1 + (PRPos - ProcResourceDefs.begin());
   1708 }
   1709 
   1710 #ifndef NDEBUG
   1711 void CodeGenProcModel::dump() const {
   1712   dbgs() << Index << ": " << ModelName << " "
   1713          << (ModelDef ? ModelDef->getName() : "inferred") << " "
   1714          << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
   1715 }
   1716 
   1717 void CodeGenSchedRW::dump() const {
   1718   dbgs() << Name << (IsVariadic ? " (V) " : " ");
   1719   if (IsSequence) {
   1720     dbgs() << "(";
   1721     dumpIdxVec(Sequence);
   1722     dbgs() << ")";
   1723   }
   1724 }
   1725 
   1726 void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const {
   1727   dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n'
   1728          << "  Writes: ";
   1729   for (unsigned i = 0, N = Writes.size(); i < N; ++i) {
   1730     SchedModels->getSchedWrite(Writes[i]).dump();
   1731     if (i < N-1) {
   1732       dbgs() << '\n';
   1733       dbgs().indent(10);
   1734     }
   1735   }
   1736   dbgs() << "\n  Reads: ";
   1737   for (unsigned i = 0, N = Reads.size(); i < N; ++i) {
   1738     SchedModels->getSchedRead(Reads[i]).dump();
   1739     if (i < N-1) {
   1740       dbgs() << '\n';
   1741       dbgs().indent(10);
   1742     }
   1743   }
   1744   dbgs() << "\n  ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n';
   1745   if (!Transitions.empty()) {
   1746     dbgs() << "\n Transitions for Proc ";
   1747     for (std::vector<CodeGenSchedTransition>::const_iterator
   1748            TI = Transitions.begin(), TE = Transitions.end(); TI != TE; ++TI) {
   1749       dumpIdxVec(TI->ProcIndices);
   1750     }
   1751   }
   1752 }
   1753 
   1754 void PredTransitions::dump() const {
   1755   dbgs() << "Expanded Variants:\n";
   1756   for (std::vector<PredTransition>::const_iterator
   1757          TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) {
   1758     dbgs() << "{";
   1759     for (SmallVectorImpl<PredCheck>::const_iterator
   1760            PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end();
   1761          PCI != PCE; ++PCI) {
   1762       if (PCI != TI->PredTerm.begin())
   1763         dbgs() << ", ";
   1764       dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name
   1765              << ":" << PCI->Predicate->getName();
   1766     }
   1767     dbgs() << "},\n  => {";
   1768     for (SmallVectorImpl<SmallVector<unsigned,4> >::const_iterator
   1769            WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end();
   1770          WSI != WSE; ++WSI) {
   1771       dbgs() << "(";
   1772       for (SmallVectorImpl<unsigned>::const_iterator
   1773              WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) {
   1774         if (WI != WSI->begin())
   1775           dbgs() << ", ";
   1776         dbgs() << SchedModels.getSchedWrite(*WI).Name;
   1777       }
   1778       dbgs() << "),";
   1779     }
   1780     dbgs() << "}\n";
   1781   }
   1782 }
   1783 #endif // NDEBUG
   1784