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