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