Home | History | Annotate | Download | only in TableGen
      1 //===- CodeGenSchedule.h - Scheduling Machine Models ------------*- C++ -*-===//
      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 described in
     11 // the target description.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef CODEGEN_SCHEDULE_H
     16 #define CODEGEN_SCHEDULE_H
     17 
     18 #include "llvm/ADT/DenseMap.h"
     19 #include "llvm/ADT/StringMap.h"
     20 #include "llvm/Support/ErrorHandling.h"
     21 #include "llvm/TableGen/Record.h"
     22 #include "llvm/TableGen/SetTheory.h"
     23 
     24 namespace llvm {
     25 
     26 class CodeGenTarget;
     27 class CodeGenSchedModels;
     28 class CodeGenInstruction;
     29 
     30 typedef std::vector<Record*> RecVec;
     31 typedef std::vector<Record*>::const_iterator RecIter;
     32 
     33 typedef std::vector<unsigned> IdxVec;
     34 typedef std::vector<unsigned>::const_iterator IdxIter;
     35 
     36 void splitSchedReadWrites(const RecVec &RWDefs,
     37                           RecVec &WriteDefs, RecVec &ReadDefs);
     38 
     39 /// We have two kinds of SchedReadWrites. Explicitly defined and inferred
     40 /// sequences.  TheDef is nonnull for explicit SchedWrites, but Sequence may or
     41 /// may not be empty. TheDef is null for inferred sequences, and Sequence must
     42 /// be nonempty.
     43 ///
     44 /// IsVariadic controls whether the variants are expanded into multiple operands
     45 /// or a sequence of writes on one operand.
     46 struct CodeGenSchedRW {
     47   unsigned Index;
     48   std::string Name;
     49   Record *TheDef;
     50   bool IsRead;
     51   bool IsAlias;
     52   bool HasVariants;
     53   bool IsVariadic;
     54   bool IsSequence;
     55   IdxVec Sequence;
     56   RecVec Aliases;
     57 
     58   CodeGenSchedRW()
     59     : Index(0), TheDef(nullptr), IsRead(false), IsAlias(false),
     60       HasVariants(false), IsVariadic(false), IsSequence(false) {}
     61   CodeGenSchedRW(unsigned Idx, Record *Def)
     62     : Index(Idx), TheDef(Def), IsAlias(false), IsVariadic(false) {
     63     Name = Def->getName();
     64     IsRead = Def->isSubClassOf("SchedRead");
     65     HasVariants = Def->isSubClassOf("SchedVariant");
     66     if (HasVariants)
     67       IsVariadic = Def->getValueAsBit("Variadic");
     68 
     69     // Read records don't currently have sequences, but it can be easily
     70     // added. Note that implicit Reads (from ReadVariant) may have a Sequence
     71     // (but no record).
     72     IsSequence = Def->isSubClassOf("WriteSequence");
     73   }
     74 
     75   CodeGenSchedRW(unsigned Idx, bool Read, const IdxVec &Seq,
     76                  const std::string &Name)
     77     : Index(Idx), Name(Name), TheDef(nullptr), IsRead(Read), IsAlias(false),
     78       HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) {
     79     assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
     80   }
     81 
     82   bool isValid() const {
     83     assert((!HasVariants || TheDef) && "Variant write needs record def");
     84     assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
     85     assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
     86     assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
     87     assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases");
     88     return TheDef || !Sequence.empty();
     89   }
     90 
     91 #ifndef NDEBUG
     92   void dump() const;
     93 #endif
     94 };
     95 
     96 /// Represent a transition between SchedClasses induced by SchedVariant.
     97 struct CodeGenSchedTransition {
     98   unsigned ToClassIdx;
     99   IdxVec ProcIndices;
    100   RecVec PredTerm;
    101 };
    102 
    103 /// Scheduling class.
    104 ///
    105 /// Each instruction description will be mapped to a scheduling class. There are
    106 /// four types of classes:
    107 ///
    108 /// 1) An explicitly defined itinerary class with ItinClassDef set.
    109 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
    110 ///
    111 /// 2) An implied class with a list of SchedWrites and SchedReads that are
    112 /// defined in an instruction definition and which are common across all
    113 /// subtargets. ProcIndices contains 0 for any processor.
    114 ///
    115 /// 3) An implied class with a list of InstRW records that map instructions to
    116 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
    117 /// instructions to this class. ProcIndices contains all the processors that
    118 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
    119 /// still be defined for processors with no InstRW entry.
    120 ///
    121 /// 4) An inferred class represents a variant of another class that may be
    122 /// resolved at runtime. ProcIndices contains the set of processors that may
    123 /// require the class. ProcIndices are propagated through SchedClasses as
    124 /// variants are expanded. Multiple SchedClasses may be inferred from an
    125 /// itinerary class. Each inherits the processor index from the ItinRW record
    126 /// that mapped the itinerary class to the variant Writes or Reads.
    127 struct CodeGenSchedClass {
    128   unsigned Index;
    129   std::string Name;
    130   Record *ItinClassDef;
    131 
    132   IdxVec Writes;
    133   IdxVec Reads;
    134   // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
    135   IdxVec ProcIndices;
    136 
    137   std::vector<CodeGenSchedTransition> Transitions;
    138 
    139   // InstRW records associated with this class. These records may refer to an
    140   // Instruction no longer mapped to this class by InstrClassMap. These
    141   // Instructions should be ignored by this class because they have been split
    142   // off to join another inferred class.
    143   RecVec InstRWs;
    144 
    145   CodeGenSchedClass(): Index(0), ItinClassDef(nullptr) {}
    146 
    147   bool isKeyEqual(Record *IC, const IdxVec &W, const IdxVec &R) {
    148     return ItinClassDef == IC && Writes == W && Reads == R;
    149   }
    150 
    151   // Is this class generated from a variants if existing classes? Instructions
    152   // are never mapped directly to inferred scheduling classes.
    153   bool isInferred() const { return !ItinClassDef; }
    154 
    155 #ifndef NDEBUG
    156   void dump(const CodeGenSchedModels *SchedModels) const;
    157 #endif
    158 };
    159 
    160 // Processor model.
    161 //
    162 // ModelName is a unique name used to name an instantiation of MCSchedModel.
    163 //
    164 // ModelDef is NULL for inferred Models. This happens when a processor defines
    165 // an itinerary but no machine model. If the processor defines neither a machine
    166 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
    167 // the special "NoModel" field set to true.
    168 //
    169 // ItinsDef always points to a valid record definition, but may point to the
    170 // default NoItineraries. NoItineraries has an empty list of InstrItinData
    171 // records.
    172 //
    173 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
    174 struct CodeGenProcModel {
    175   unsigned Index;
    176   std::string ModelName;
    177   Record *ModelDef;
    178   Record *ItinsDef;
    179 
    180   // Derived members...
    181 
    182   // Array of InstrItinData records indexed by a CodeGenSchedClass index.
    183   // This list is empty if the Processor has no value for Itineraries.
    184   // Initialized by collectProcItins().
    185   RecVec ItinDefList;
    186 
    187   // Map itinerary classes to per-operand resources.
    188   // This list is empty if no ItinRW refers to this Processor.
    189   RecVec ItinRWDefs;
    190 
    191   // All read/write resources associated with this processor.
    192   RecVec WriteResDefs;
    193   RecVec ReadAdvanceDefs;
    194 
    195   // Per-operand machine model resources associated with this processor.
    196   RecVec ProcResourceDefs;
    197   RecVec ProcResGroupDefs;
    198 
    199   CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
    200                    Record *IDef) :
    201     Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
    202 
    203   bool hasItineraries() const {
    204     return !ItinsDef->getValueAsListOfDefs("IID").empty();
    205   }
    206 
    207   bool hasInstrSchedModel() const {
    208     return !WriteResDefs.empty() || !ItinRWDefs.empty();
    209   }
    210 
    211   unsigned getProcResourceIdx(Record *PRDef) const;
    212 
    213 #ifndef NDEBUG
    214   void dump() const;
    215 #endif
    216 };
    217 
    218 /// Top level container for machine model data.
    219 class CodeGenSchedModels {
    220   RecordKeeper &Records;
    221   const CodeGenTarget &Target;
    222 
    223   // Map dag expressions to Instruction lists.
    224   SetTheory Sets;
    225 
    226   // List of unique processor models.
    227   std::vector<CodeGenProcModel> ProcModels;
    228 
    229   // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
    230   typedef DenseMap<Record*, unsigned> ProcModelMapTy;
    231   ProcModelMapTy ProcModelMap;
    232 
    233   // Per-operand SchedReadWrite types.
    234   std::vector<CodeGenSchedRW> SchedWrites;
    235   std::vector<CodeGenSchedRW> SchedReads;
    236 
    237   // List of unique SchedClasses.
    238   std::vector<CodeGenSchedClass> SchedClasses;
    239 
    240   // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
    241   unsigned NumInstrSchedClasses;
    242 
    243   // Map each instruction to its unique SchedClass index considering the
    244   // combination of it's itinerary class, SchedRW list, and InstRW records.
    245   typedef DenseMap<Record*, unsigned> InstClassMapTy;
    246   InstClassMapTy InstrClassMap;
    247 
    248 public:
    249   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
    250 
    251   // iterator access to the scheduling classes.
    252   typedef std::vector<CodeGenSchedClass>::iterator class_iterator;
    253   typedef std::vector<CodeGenSchedClass>::const_iterator const_class_iterator;
    254   class_iterator classes_begin() { return SchedClasses.begin(); }
    255   const_class_iterator classes_begin() const { return SchedClasses.begin(); }
    256   class_iterator classes_end() { return SchedClasses.end(); }
    257   const_class_iterator classes_end() const { return SchedClasses.end(); }
    258   iterator_range<class_iterator> classes() {
    259    return iterator_range<class_iterator>(classes_begin(), classes_end());
    260   }
    261   iterator_range<const_class_iterator> classes() const {
    262    return iterator_range<const_class_iterator>(classes_begin(), classes_end());
    263   }
    264   iterator_range<class_iterator> explicit_classes() {
    265     return iterator_range<class_iterator>(
    266         classes_begin(), classes_begin() + NumInstrSchedClasses);
    267   }
    268   iterator_range<const_class_iterator> explicit_classes() const {
    269     return iterator_range<const_class_iterator>(
    270         classes_begin(), classes_begin() + NumInstrSchedClasses);
    271   }
    272 
    273   Record *getModelOrItinDef(Record *ProcDef) const {
    274     Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
    275     Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
    276     if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
    277       assert(ModelDef->getValueAsBit("NoModel")
    278              && "Itineraries must be defined within SchedMachineModel");
    279       return ItinsDef;
    280     }
    281     return ModelDef;
    282   }
    283 
    284   const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
    285     Record *ModelDef = getModelOrItinDef(ProcDef);
    286     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
    287     assert(I != ProcModelMap.end() && "missing machine model");
    288     return ProcModels[I->second];
    289   }
    290 
    291   CodeGenProcModel &getProcModel(Record *ModelDef) {
    292     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
    293     assert(I != ProcModelMap.end() && "missing machine model");
    294     return ProcModels[I->second];
    295   }
    296   const CodeGenProcModel &getProcModel(Record *ModelDef) const {
    297     return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef);
    298   }
    299 
    300   // Iterate over the unique processor models.
    301   typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
    302   ProcIter procModelBegin() const { return ProcModels.begin(); }
    303   ProcIter procModelEnd() const { return ProcModels.end(); }
    304 
    305   // Return true if any processors have itineraries.
    306   bool hasItineraries() const;
    307 
    308   // Get a SchedWrite from its index.
    309   const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
    310     assert(Idx < SchedWrites.size() && "bad SchedWrite index");
    311     assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
    312     return SchedWrites[Idx];
    313   }
    314   // Get a SchedWrite from its index.
    315   const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
    316     assert(Idx < SchedReads.size() && "bad SchedRead index");
    317     assert(SchedReads[Idx].isValid() && "invalid SchedRead");
    318     return SchedReads[Idx];
    319   }
    320 
    321   const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
    322     return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
    323   }
    324   CodeGenSchedRW &getSchedRW(Record *Def) {
    325     bool IsRead = Def->isSubClassOf("SchedRead");
    326     unsigned Idx = getSchedRWIdx(Def, IsRead);
    327     return const_cast<CodeGenSchedRW&>(
    328       IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
    329   }
    330   const CodeGenSchedRW &getSchedRW(Record*Def) const {
    331     return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
    332   }
    333 
    334   unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
    335 
    336   // Return true if the given write record is referenced by a ReadAdvance.
    337   bool hasReadOfWrite(Record *WriteDef) const;
    338 
    339   // Get a SchedClass from its index.
    340   CodeGenSchedClass &getSchedClass(unsigned Idx) {
    341     assert(Idx < SchedClasses.size() && "bad SchedClass index");
    342     return SchedClasses[Idx];
    343   }
    344   const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
    345     assert(Idx < SchedClasses.size() && "bad SchedClass index");
    346     return SchedClasses[Idx];
    347   }
    348 
    349   // Get the SchedClass index for an instruction. Instructions with no
    350   // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
    351   // for NoItinerary.
    352   unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
    353 
    354   typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
    355   SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
    356   SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
    357 
    358   unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
    359 
    360   void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
    361   void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
    362   void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
    363   void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
    364                           const CodeGenProcModel &ProcModel) const;
    365 
    366   unsigned addSchedClass(Record *ItinDef, const IdxVec &OperWrites,
    367                          const IdxVec &OperReads, const IdxVec &ProcIndices);
    368 
    369   unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
    370 
    371   unsigned findSchedClassIdx(Record *ItinClassDef,
    372                              const IdxVec &Writes,
    373                              const IdxVec &Reads) const;
    374 
    375   Record *findProcResUnits(Record *ProcResKind,
    376                            const CodeGenProcModel &PM) const;
    377 
    378 private:
    379   void collectProcModels();
    380 
    381   // Initialize a new processor model if it is unique.
    382   void addProcModel(Record *ProcDef);
    383 
    384   void collectSchedRW();
    385 
    386   std::string genRWName(const IdxVec& Seq, bool IsRead);
    387   unsigned findRWForSequence(const IdxVec &Seq, bool IsRead);
    388 
    389   void collectSchedClasses();
    390 
    391   std::string createSchedClassName(Record *ItinClassDef,
    392                                    const IdxVec &OperWrites,
    393                                    const IdxVec &OperReads);
    394   std::string createSchedClassName(const RecVec &InstDefs);
    395   void createInstRWClass(Record *InstRWDef);
    396 
    397   void collectProcItins();
    398 
    399   void collectProcItinRW();
    400 
    401   void inferSchedClasses();
    402 
    403   void inferFromRW(const IdxVec &OperWrites, const IdxVec &OperReads,
    404                    unsigned FromClassIdx, const IdxVec &ProcIndices);
    405   void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
    406   void inferFromInstRWs(unsigned SCIdx);
    407 
    408   bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
    409   void verifyProcResourceGroups(CodeGenProcModel &PM);
    410 
    411   void collectProcResources();
    412 
    413   void collectItinProcResources(Record *ItinClassDef);
    414 
    415   void collectRWResources(unsigned RWIdx, bool IsRead,
    416                           const IdxVec &ProcIndices);
    417 
    418   void collectRWResources(const IdxVec &Writes, const IdxVec &Reads,
    419                           const IdxVec &ProcIndices);
    420 
    421   void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM);
    422 
    423   void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
    424 
    425   void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);
    426 };
    427 
    428 } // namespace llvm
    429 
    430 #endif
    431