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 /// Scheduling class.
  87 ///
  88 /// Each instruction description will be mapped to a scheduling class. There are
  89 /// four types of classes:
  90 ///
  91 /// 1) An explicitly defined itinerary class with ItinClassDef set.
  92 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
  93 ///
  94 /// 2) An implied class with a list of SchedWrites and SchedReads that are
  95 /// defined in an instruction definition and which are common across all
  96 /// subtargets. ProcIndices contains 0 for any processor.
  97 ///
  98 /// 3) An implied class with a list of InstRW records that map instructions to
  99 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
 100 /// instructions to this class. ProcIndices contains all the processors that
 101 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
 102 /// still be defined for processors with no InstRW entry.
 103 ///
 104 /// 4) An inferred class represents a variant of another class that may be
 105 /// resolved at runtime. ProcIndices contains the set of processors that may
 106 /// require the class. ProcIndices are propagated through SchedClasses as
 107 /// variants are expanded. Multiple SchedClasses may be inferred from an
 108 /// itinerary class. Each inherits the processor index from the ItinRW record
 109 /// that mapped the itinerary class to the variant Writes or Reads.
 110 struct CodeGenSchedClass {
 111   std::string Name;
 112   Record *ItinClassDef;
 113
 114   IdxVec Writes;
 115   IdxVec Reads;
 116   // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
 117   IdxVec ProcIndices;
 118
 119   // InstReadWrite records associated with this class. Any Instrs that the
 120   // definitions refer to that are not mapped to this class should be ignored.
 121   RecVec InstRWs;
 122
 123   CodeGenSchedClass(): ItinClassDef(0) {}
 124   CodeGenSchedClass(Record *rec): ItinClassDef(rec) {
 125     Name = rec->getName();
 126     ProcIndices.push_back(0);
 127   }
 128
 129 #ifndef NDEBUG
 130   void dump(const CodeGenSchedModels *SchedModels) const;
 131 #endif
 132 };
 133
 134 // Processor model.
 135 //
 136 // ModelName is a unique name used to name an instantiation of MCSchedModel.
 137 //
 138 // ModelDef is NULL for inferred Models. This happens when a processor defines
 139 // an itinerary but no machine model. If the processer defines neither a machine
 140 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
 141 // the special "NoModel" field set to true.
 142 //
 143 // ItinsDef always points to a valid record definition, but may point to the
 144 // default NoItineraries. NoItineraries has an empty list of InstrItinData
 145 // records.
 146 //
 147 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
 148 struct CodeGenProcModel {
 149   unsigned Index;
 150   std::string ModelName;
 151   Record *ModelDef;
 152   Record *ItinsDef;
 153
 154   // Derived members...
 155
 156   // Array of InstrItinData records indexed by a CodeGenSchedClass index.
 157   // This list is empty if the Processor has no value for Itineraries.
 158   // Initialized by collectProcItins().
 159   RecVec ItinDefList;
 160
 161   // Map itinerary classes to per-operand resources.
 162   // This list is empty if no ItinRW refers to this Processor.
 163   RecVec ItinRWDefs;
 164
 165   CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
 166                    Record *IDef) :
 167     Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
 168
 169 #ifndef NDEBUG
 170   void dump() const;
 171 #endif
 172 };
 173
 174 /// Top level container for machine model data.
 175 class CodeGenSchedModels {
 176   RecordKeeper &Records;
 177   const CodeGenTarget &Target;
 178
 179   // List of unique processor models.
 180   std::vector<CodeGenProcModel> ProcModels;
 181
 182   // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
 183   typedef DenseMap<Record*, unsigned> ProcModelMapTy;
 184   ProcModelMapTy ProcModelMap;
 185
 186   // Per-operand SchedReadWrite types.
 187   std::vector<CodeGenSchedRW> SchedWrites;
 188   std::vector<CodeGenSchedRW> SchedReads;
 189
 190   // List of unique SchedClasses.
 191   std::vector<CodeGenSchedClass> SchedClasses;
 192
 193   // Map SchedClass name to itinerary index.
 194   // These are either explicit itinerary classes or classes implied by
 195   // instruction definitions with SchedReadWrite lists.
 196   StringMap<unsigned> SchedClassIdxMap;
 197
 198   // SchedClass indices 1 up to and including NumItineraryClasses identify
 199   // itinerary classes that are explicitly used for this target's instruction
 200   // definitions. NoItinerary always has index 0 regardless of whether it is
 201   // explicitly referenced.
 202   //
 203   // Any implied SchedClass has an index greater than NumItineraryClasses.
 204   unsigned NumItineraryClasses;
 205
 206   // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
 207   unsigned NumInstrSchedClasses;
 208
 209   // Map Instruction to SchedClass index. Only for Instructions mentioned in
 210   // OpReadWrites.
 211   typedef DenseMap<Record*, unsigned> InstClassMapTy;
 212   InstClassMapTy InstrClassMap;
 213
 214 public:
 215   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
 216
 217   Record *getModelOrItinDef(Record *ProcDef) const {
 218     Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
 219     Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
 220     if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
 221       assert(ModelDef->getValueAsBit("NoModel")
 222              && "Itineraries must be defined within SchedMachineModel");
 223       return ItinsDef;
 224     }
 225     return ModelDef;
 226   }
 227
 228   const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
 229     Record *ModelDef = getModelOrItinDef(ProcDef);
 230     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
 231     assert(I != ProcModelMap.end() && "missing machine model");
 232     return ProcModels[I->second];
 233   }
 234
 235   const CodeGenProcModel &getProcModel(Record *ModelDef) const {
 236     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
 237     assert(I != ProcModelMap.end() && "missing machine model");
 238     return ProcModels[I->second];
 239   }
 240
 241   // Iterate over the unique processor models.
 242   typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
 243   ProcIter procModelBegin() const { return ProcModels.begin(); }
 244   ProcIter procModelEnd() const { return ProcModels.end(); }
 245
 246   // Get a SchedWrite from its index.
 247   const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
 248     assert(Idx < SchedWrites.size() && "bad SchedWrite index");
 249     assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
 250     return SchedWrites[Idx];
 251   }
 252   // Get a SchedWrite from its index.
 253   const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
 254     assert(Idx < SchedReads.size() && "bad SchedRead index");
 255     assert(SchedReads[Idx].isValid() && "invalid SchedRead");
 256     return SchedReads[Idx];
 257   }
 258
 259   const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
 260     return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
 261   }
 262
 263   unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
 264
 265   // Check if any instructions are assigned to an explicit itinerary class other
 266   // than NoItinerary.
 267   bool hasItineraryClasses() const { return NumItineraryClasses > 0; }
 268
 269   // Return the number of itinerary classes in use by this target's instruction
 270   // descriptions, not including "NoItinerary".
 271   unsigned numItineraryClasses() const {
 272     return NumItineraryClasses;
 273   }
 274
 275   // Get a SchedClass from its index.
 276   CodeGenSchedClass &getSchedClass(unsigned Idx) {
 277     assert(Idx < SchedClasses.size() && "bad SchedClass index");
 278     return SchedClasses[Idx];
 279   }
 280   const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
 281     assert(Idx < SchedClasses.size() && "bad SchedClass index");
 282     return SchedClasses[Idx];
 283   }
 284
 285   // Get an itinerary class's index. Value indices are '0' for NoItinerary up to
 286   // and including numItineraryClasses().
 287   unsigned getItinClassIdx(Record *ItinDef) const {
 288     assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass");
 289     unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName());
 290     assert(Idx <= NumItineraryClasses && "bad ItinClass index");
 291     return Idx;
 292   }
 293
 294   // Get the SchedClass index for an instruction. Instructions with no
 295   // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
 296   // for NoItinerary.
 297   unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
 298
 299   unsigned getSchedClassIdx(const RecVec &RWDefs) const;
 300
 301   unsigned getSchedClassIdxForItin(const Record *ItinDef) {
 302     return SchedClassIdxMap[ItinDef->getName()];
 303   }
 304
 305   typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
 306   SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
 307   SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
 308
 309   void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
 310   void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
 311
 312   unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads,
 313                          const IdxVec &ProcIndices);
 314
 315   unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
 316
 317   unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const;
 318
 319 private:
 320   void collectProcModels();
 321
 322   // Initialize a new processor model if it is unique.
 323   void addProcModel(Record *ProcDef);
 324
 325   void collectSchedRW();
 326
 327   std::string genRWName(const IdxVec& Seq, bool IsRead);
 328   unsigned findRWForSequence(const IdxVec &Seq, bool IsRead);
 329
 330   void collectSchedClasses();
 331
 332   std::string createSchedClassName(const IdxVec &OperWrites,
 333                                    const IdxVec &OperReads);
 334   std::string createSchedClassName(const RecVec &InstDefs);
 335   void createInstRWClass(Record *InstRWDef);
 336
 337   void collectProcItins();
 338
 339   void collectProcItinRW();
 340 };
 341
 342 } // namespace llvm
 343
 344 #endif