contrib/llvm/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 described in
  11 // the target description.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_UTILS_TABLEGEN_CODEGENSCHEDULE_H
  16 #define LLVM_UTILS_TABLEGEN_CODEGENSCHEDULE_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 using RecVec = std::vector<Record*>;
  31 using RecIter = std::vector<Record*>::const_iterator;
  32
  33 using IdxVec = std::vector<unsigned>;
  34 using IdxIter = std::vector<unsigned>::const_iterator;
  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, ArrayRef<unsigned> 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, ArrayRef<unsigned> W, ArrayRef<unsigned> R) {
 148     return ItinClassDef == IC && makeArrayRef(Writes) == W &&
 149            makeArrayRef(Reads) == R;
 150   }
 151
 152   // Is this class generated from a variants if existing classes? Instructions
 153   // are never mapped directly to inferred scheduling classes.
 154   bool isInferred() const { return !ItinClassDef; }
 155
 156 #ifndef NDEBUG
 157   void dump(const CodeGenSchedModels *SchedModels) const;
 158 #endif
 159 };
 160
 161 // Processor model.
 162 //
 163 // ModelName is a unique name used to name an instantiation of MCSchedModel.
 164 //
 165 // ModelDef is NULL for inferred Models. This happens when a processor defines
 166 // an itinerary but no machine model. If the processor defines neither a machine
 167 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
 168 // the special "NoModel" field set to true.
 169 //
 170 // ItinsDef always points to a valid record definition, but may point to the
 171 // default NoItineraries. NoItineraries has an empty list of InstrItinData
 172 // records.
 173 //
 174 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
 175 struct CodeGenProcModel {
 176   unsigned Index;
 177   std::string ModelName;
 178   Record *ModelDef;
 179   Record *ItinsDef;
 180
 181   // Derived members...
 182
 183   // Array of InstrItinData records indexed by a CodeGenSchedClass index.
 184   // This list is empty if the Processor has no value for Itineraries.
 185   // Initialized by collectProcItins().
 186   RecVec ItinDefList;
 187
 188   // Map itinerary classes to per-operand resources.
 189   // This list is empty if no ItinRW refers to this Processor.
 190   RecVec ItinRWDefs;
 191
 192   // List of unsupported feature.
 193   // This list is empty if the Processor has no UnsupportedFeatures.
 194   RecVec UnsupportedFeaturesDefs;
 195
 196   // All read/write resources associated with this processor.
 197   RecVec WriteResDefs;
 198   RecVec ReadAdvanceDefs;
 199
 200   // Per-operand machine model resources associated with this processor.
 201   RecVec ProcResourceDefs;
 202   RecVec ProcResGroupDefs;
 203
 204   CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
 205                    Record *IDef) :
 206     Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
 207
 208   bool hasItineraries() const {
 209     return !ItinsDef->getValueAsListOfDefs("IID").empty();
 210   }
 211
 212   bool hasInstrSchedModel() const {
 213     return !WriteResDefs.empty() || !ItinRWDefs.empty();
 214   }
 215
 216   unsigned getProcResourceIdx(Record *PRDef) const;
 217
 218   bool isUnsupported(const CodeGenInstruction &Inst) const;
 219
 220 #ifndef NDEBUG
 221   void dump() const;
 222 #endif
 223 };
 224
 225 /// Top level container for machine model data.
 226 class CodeGenSchedModels {
 227   RecordKeeper &Records;
 228   const CodeGenTarget &Target;
 229
 230   // Map dag expressions to Instruction lists.
 231   SetTheory Sets;
 232
 233   // List of unique processor models.
 234   std::vector<CodeGenProcModel> ProcModels;
 235
 236   // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
 237   using ProcModelMapTy = DenseMap<Record*, unsigned>;
 238   ProcModelMapTy ProcModelMap;
 239
 240   // Per-operand SchedReadWrite types.
 241   std::vector<CodeGenSchedRW> SchedWrites;
 242   std::vector<CodeGenSchedRW> SchedReads;
 243
 244   // List of unique SchedClasses.
 245   std::vector<CodeGenSchedClass> SchedClasses;
 246
 247   // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
 248   unsigned NumInstrSchedClasses;
 249
 250   RecVec ProcResourceDefs;
 251   RecVec ProcResGroups;
 252
 253   // Map each instruction to its unique SchedClass index considering the
 254   // combination of it's itinerary class, SchedRW list, and InstRW records.
 255   using InstClassMapTy = DenseMap<Record*, unsigned>;
 256   InstClassMapTy InstrClassMap;
 257
 258 public:
 259   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
 260
 261   // iterator access to the scheduling classes.
 262   using class_iterator = std::vector<CodeGenSchedClass>::iterator;
 263   using const_class_iterator = std::vector<CodeGenSchedClass>::const_iterator;
 264   class_iterator classes_begin() { return SchedClasses.begin(); }
 265   const_class_iterator classes_begin() const { return SchedClasses.begin(); }
 266   class_iterator classes_end() { return SchedClasses.end(); }
 267   const_class_iterator classes_end() const { return SchedClasses.end(); }
 268   iterator_range<class_iterator> classes() {
 269    return make_range(classes_begin(), classes_end());
 270   }
 271   iterator_range<const_class_iterator> classes() const {
 272    return make_range(classes_begin(), classes_end());
 273   }
 274   iterator_range<class_iterator> explicit_classes() {
 275     return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
 276   }
 277   iterator_range<const_class_iterator> explicit_classes() const {
 278     return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
 279   }
 280
 281   Record *getModelOrItinDef(Record *ProcDef) const {
 282     Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
 283     Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
 284     if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
 285       assert(ModelDef->getValueAsBit("NoModel")
 286              && "Itineraries must be defined within SchedMachineModel");
 287       return ItinsDef;
 288     }
 289     return ModelDef;
 290   }
 291
 292   const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
 293     Record *ModelDef = getModelOrItinDef(ProcDef);
 294     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
 295     assert(I != ProcModelMap.end() && "missing machine model");
 296     return ProcModels[I->second];
 297   }
 298
 299   CodeGenProcModel &getProcModel(Record *ModelDef) {
 300     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
 301     assert(I != ProcModelMap.end() && "missing machine model");
 302     return ProcModels[I->second];
 303   }
 304   const CodeGenProcModel &getProcModel(Record *ModelDef) const {
 305     return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef);
 306   }
 307
 308   // Iterate over the unique processor models.
 309   using ProcIter = std::vector<CodeGenProcModel>::const_iterator;
 310   ProcIter procModelBegin() const { return ProcModels.begin(); }
 311   ProcIter procModelEnd() const { return ProcModels.end(); }
 312   ArrayRef<CodeGenProcModel> procModels() const { return ProcModels; }
 313
 314   // Return true if any processors have itineraries.
 315   bool hasItineraries() const;
 316
 317   // Get a SchedWrite from its index.
 318   const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
 319     assert(Idx < SchedWrites.size() && "bad SchedWrite index");
 320     assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
 321     return SchedWrites[Idx];
 322   }
 323   // Get a SchedWrite from its index.
 324   const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
 325     assert(Idx < SchedReads.size() && "bad SchedRead index");
 326     assert(SchedReads[Idx].isValid() && "invalid SchedRead");
 327     return SchedReads[Idx];
 328   }
 329
 330   const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
 331     return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
 332   }
 333   CodeGenSchedRW &getSchedRW(Record *Def) {
 334     bool IsRead = Def->isSubClassOf("SchedRead");
 335     unsigned Idx = getSchedRWIdx(Def, IsRead);
 336     return const_cast<CodeGenSchedRW&>(
 337       IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
 338   }
 339   const CodeGenSchedRW &getSchedRW(Record*Def) const {
 340     return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
 341   }
 342
 343   unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
 344
 345   // Return true if the given write record is referenced by a ReadAdvance.
 346   bool hasReadOfWrite(Record *WriteDef) const;
 347
 348   // Get a SchedClass from its index.
 349   CodeGenSchedClass &getSchedClass(unsigned Idx) {
 350     assert(Idx < SchedClasses.size() && "bad SchedClass index");
 351     return SchedClasses[Idx];
 352   }
 353   const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
 354     assert(Idx < SchedClasses.size() && "bad SchedClass index");
 355     return SchedClasses[Idx];
 356   }
 357
 358   // Get the SchedClass index for an instruction. Instructions with no
 359   // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
 360   // for NoItinerary.
 361   unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
 362
 363   using SchedClassIter = std::vector<CodeGenSchedClass>::const_iterator;
 364   SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
 365   SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
 366   ArrayRef<CodeGenSchedClass> schedClasses() const { return SchedClasses; }
 367
 368   unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
 369
 370   void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
 371   void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
 372   void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
 373   void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
 374                           const CodeGenProcModel &ProcModel) const;
 375
 376   unsigned addSchedClass(Record *ItinDef, ArrayRef<unsigned> OperWrites,
 377                          ArrayRef<unsigned> OperReads,
 378                          ArrayRef<unsigned> ProcIndices);
 379
 380   unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
 381
 382   unsigned findSchedClassIdx(Record *ItinClassDef, ArrayRef<unsigned> Writes,
 383                              ArrayRef<unsigned> Reads) const;
 384
 385   Record *findProcResUnits(Record *ProcResKind, const CodeGenProcModel &PM,
 386                            ArrayRef<SMLoc> Loc) const;
 387
 388 private:
 389   void collectProcModels();
 390
 391   // Initialize a new processor model if it is unique.
 392   void addProcModel(Record *ProcDef);
 393
 394   void collectSchedRW();
 395
 396   std::string genRWName(ArrayRef<unsigned> Seq, bool IsRead);
 397   unsigned findRWForSequence(ArrayRef<unsigned> Seq, bool IsRead);
 398
 399   void collectSchedClasses();
 400
 401   std::string createSchedClassName(Record *ItinClassDef,
 402                                    ArrayRef<unsigned> OperWrites,
 403                                    ArrayRef<unsigned> OperReads);
 404   std::string createSchedClassName(const RecVec &InstDefs);
 405   void createInstRWClass(Record *InstRWDef);
 406
 407   void collectProcItins();
 408
 409   void collectProcItinRW();
 410
 411   void collectProcUnsupportedFeatures();
 412
 413   void inferSchedClasses();
 414
 415   void checkCompleteness();
 416
 417   void inferFromRW(ArrayRef<unsigned> OperWrites, ArrayRef<unsigned> OperReads,
 418                    unsigned FromClassIdx, ArrayRef<unsigned> ProcIndices);
 419   void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
 420   void inferFromInstRWs(unsigned SCIdx);
 421
 422   bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
 423   void verifyProcResourceGroups(CodeGenProcModel &PM);
 424
 425   void collectProcResources();
 426
 427   void collectItinProcResources(Record *ItinClassDef);
 428
 429   void collectRWResources(unsigned RWIdx, bool IsRead,
 430                           ArrayRef<unsigned> ProcIndices);
 431
 432   void collectRWResources(ArrayRef<unsigned> Writes, ArrayRef<unsigned> Reads,
 433                           ArrayRef<unsigned> ProcIndices);
 434
 435   void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM,
 436                        ArrayRef<SMLoc> Loc);
 437
 438   void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
 439
 440   void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);
 441 };
 442
 443 } // namespace llvm
 444
 445 #endif