utils/TableGen/CodeGenSchedule.h

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