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 class CodeGenRegisterClass;
  30
  31 using RecVec = std::vector<Record*>;
  32 using RecIter = std::vector<Record*>::const_iterator;
  33
  34 using IdxVec = std::vector<unsigned>;
  35 using IdxIter = std::vector<unsigned>::const_iterator;
  36
  37 /// We have two kinds of SchedReadWrites. Explicitly defined and inferred
  38 /// sequences.  TheDef is nonnull for explicit SchedWrites, but Sequence may or
  39 /// may not be empty. TheDef is null for inferred sequences, and Sequence must
  40 /// be nonempty.
  41 ///
  42 /// IsVariadic controls whether the variants are expanded into multiple operands
  43 /// or a sequence of writes on one operand.
  44 struct CodeGenSchedRW {
  45   unsigned Index;
  46   std::string Name;
  47   Record *TheDef;
  48   bool IsRead;
  49   bool IsAlias;
  50   bool HasVariants;
  51   bool IsVariadic;
  52   bool IsSequence;
  53   IdxVec Sequence;
  54   RecVec Aliases;
  55
  56   CodeGenSchedRW()
  57     : Index(0), TheDef(nullptr), IsRead(false), IsAlias(false),
  58       HasVariants(false), IsVariadic(false), IsSequence(false) {}
  59   CodeGenSchedRW(unsigned Idx, Record *Def)
  60     : Index(Idx), TheDef(Def), IsAlias(false), IsVariadic(false) {
  61     Name = Def->getName();
  62     IsRead = Def->isSubClassOf("SchedRead");
  63     HasVariants = Def->isSubClassOf("SchedVariant");
  64     if (HasVariants)
  65       IsVariadic = Def->getValueAsBit("Variadic");
  66
  67     // Read records don't currently have sequences, but it can be easily
  68     // added. Note that implicit Reads (from ReadVariant) may have a Sequence
  69     // (but no record).
  70     IsSequence = Def->isSubClassOf("WriteSequence");
  71   }
  72
  73   CodeGenSchedRW(unsigned Idx, bool Read, ArrayRef<unsigned> Seq,
  74                  const std::string &Name)
  75       : Index(Idx), Name(Name), TheDef(nullptr), IsRead(Read), IsAlias(false),
  76         HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) {
  77     assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
  78   }
  79
  80   bool isValid() const {
  81     assert((!HasVariants || TheDef) && "Variant write needs record def");
  82     assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
  83     assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
  84     assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
  85     assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases");
  86     return TheDef || !Sequence.empty();
  87   }
  88
  89 #ifndef NDEBUG
  90   void dump() const;
  91 #endif
  92 };
  93
  94 /// Represent a transition between SchedClasses induced by SchedVariant.
  95 struct CodeGenSchedTransition {
  96   unsigned ToClassIdx;
  97   IdxVec ProcIndices;
  98   RecVec PredTerm;
  99 };
 100
 101 /// Scheduling class.
 102 ///
 103 /// Each instruction description will be mapped to a scheduling class. There are
 104 /// four types of classes:
 105 ///
 106 /// 1) An explicitly defined itinerary class with ItinClassDef set.
 107 /// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
 108 ///
 109 /// 2) An implied class with a list of SchedWrites and SchedReads that are
 110 /// defined in an instruction definition and which are common across all
 111 /// subtargets. ProcIndices contains 0 for any processor.
 112 ///
 113 /// 3) An implied class with a list of InstRW records that map instructions to
 114 /// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
 115 /// instructions to this class. ProcIndices contains all the processors that
 116 /// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
 117 /// still be defined for processors with no InstRW entry.
 118 ///
 119 /// 4) An inferred class represents a variant of another class that may be
 120 /// resolved at runtime. ProcIndices contains the set of processors that may
 121 /// require the class. ProcIndices are propagated through SchedClasses as
 122 /// variants are expanded. Multiple SchedClasses may be inferred from an
 123 /// itinerary class. Each inherits the processor index from the ItinRW record
 124 /// that mapped the itinerary class to the variant Writes or Reads.
 125 struct CodeGenSchedClass {
 126   unsigned Index;
 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(unsigned Index, std::string Name, Record *ItinClassDef)
 144     : Index(Index), Name(std::move(Name)), ItinClassDef(ItinClassDef) {}
 145
 146   bool isKeyEqual(Record *IC, ArrayRef<unsigned> W,
 147                   ArrayRef<unsigned> R) const {
 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 /// Represent the cost of allocating a register of register class RCDef.
 162 ///
 163 /// The cost of allocating a register is equivalent to the number of physical
 164 /// registers used by the register renamer. Register costs are defined at
 165 /// register class granularity.
 166 struct CodeGenRegisterCost {
 167   Record *RCDef;
 168   unsigned Cost;
 169   CodeGenRegisterCost(Record *RC, unsigned RegisterCost)
 170       : RCDef(RC), Cost(RegisterCost) {}
 171   CodeGenRegisterCost(const CodeGenRegisterCost &) = default;
 172   CodeGenRegisterCost &operator=(const CodeGenRegisterCost &) = delete;
 173 };
 174
 175 /// A processor register file.
 176 ///
 177 /// This class describes a processor register file. Register file information is
 178 /// currently consumed by external tools like llvm-mca to predict dispatch
 179 /// stalls due to register pressure.
 180 struct CodeGenRegisterFile {
 181   std::string Name;
 182   Record *RegisterFileDef;
 183
 184   unsigned NumPhysRegs;
 185   std::vector<CodeGenRegisterCost> Costs;
 186
 187   CodeGenRegisterFile(StringRef name, Record *def)
 188       : Name(name), RegisterFileDef(def), NumPhysRegs(0) {}
 189
 190   bool hasDefaultCosts() const { return Costs.empty(); }
 191 };
 192
 193 // Processor model.
 194 //
 195 // ModelName is a unique name used to name an instantiation of MCSchedModel.
 196 //
 197 // ModelDef is NULL for inferred Models. This happens when a processor defines
 198 // an itinerary but no machine model. If the processor defines neither a machine
 199 // model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has
 200 // the special "NoModel" field set to true.
 201 //
 202 // ItinsDef always points to a valid record definition, but may point to the
 203 // default NoItineraries. NoItineraries has an empty list of InstrItinData
 204 // records.
 205 //
 206 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
 207 struct CodeGenProcModel {
 208   unsigned Index;
 209   std::string ModelName;
 210   Record *ModelDef;
 211   Record *ItinsDef;
 212
 213   // Derived members...
 214
 215   // Array of InstrItinData records indexed by a CodeGenSchedClass index.
 216   // This list is empty if the Processor has no value for Itineraries.
 217   // Initialized by collectProcItins().
 218   RecVec ItinDefList;
 219
 220   // Map itinerary classes to per-operand resources.
 221   // This list is empty if no ItinRW refers to this Processor.
 222   RecVec ItinRWDefs;
 223
 224   // List of unsupported feature.
 225   // This list is empty if the Processor has no UnsupportedFeatures.
 226   RecVec UnsupportedFeaturesDefs;
 227
 228   // All read/write resources associated with this processor.
 229   RecVec WriteResDefs;
 230   RecVec ReadAdvanceDefs;
 231
 232   // Per-operand machine model resources associated with this processor.
 233   RecVec ProcResourceDefs;
 234
 235   // List of Register Files.
 236   std::vector<CodeGenRegisterFile> RegisterFiles;
 237
 238   // Optional Retire Control Unit definition.
 239   Record *RetireControlUnit;
 240
 241   // List of PfmCounters.
 242   RecVec PfmIssueCounterDefs;
 243   Record *PfmCycleCounterDef = nullptr;
 244
 245   CodeGenProcModel(unsigned Idx, std::string Name, Record *MDef,
 246                    Record *IDef) :
 247     Index(Idx), ModelName(std::move(Name)), ModelDef(MDef), ItinsDef(IDef),
 248     RetireControlUnit(nullptr) {}
 249
 250   bool hasItineraries() const {
 251     return !ItinsDef->getValueAsListOfDefs("IID").empty();
 252   }
 253
 254   bool hasInstrSchedModel() const {
 255     return !WriteResDefs.empty() || !ItinRWDefs.empty();
 256   }
 257
 258   bool hasExtraProcessorInfo() const {
 259     return RetireControlUnit || !RegisterFiles.empty() ||
 260         !PfmIssueCounterDefs.empty() ||
 261         PfmCycleCounterDef != nullptr;
 262   }
 263
 264   unsigned getProcResourceIdx(Record *PRDef) const;
 265
 266   bool isUnsupported(const CodeGenInstruction &Inst) const;
 267
 268 #ifndef NDEBUG
 269   void dump() const;
 270 #endif
 271 };
 272
 273 /// Top level container for machine model data.
 274 class CodeGenSchedModels {
 275   RecordKeeper &Records;
 276   const CodeGenTarget &Target;
 277
 278   // Map dag expressions to Instruction lists.
 279   SetTheory Sets;
 280
 281   // List of unique processor models.
 282   std::vector<CodeGenProcModel> ProcModels;
 283
 284   // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
 285   using ProcModelMapTy = DenseMap<Record*, unsigned>;
 286   ProcModelMapTy ProcModelMap;
 287
 288   // Per-operand SchedReadWrite types.
 289   std::vector<CodeGenSchedRW> SchedWrites;
 290   std::vector<CodeGenSchedRW> SchedReads;
 291
 292   // List of unique SchedClasses.
 293   std::vector<CodeGenSchedClass> SchedClasses;
 294
 295   // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
 296   unsigned NumInstrSchedClasses;
 297
 298   RecVec ProcResourceDefs;
 299   RecVec ProcResGroups;
 300
 301   // Map each instruction to its unique SchedClass index considering the
 302   // combination of it's itinerary class, SchedRW list, and InstRW records.
 303   using InstClassMapTy = DenseMap<Record*, unsigned>;
 304   InstClassMapTy InstrClassMap;
 305
 306 public:
 307   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
 308
 309   // iterator access to the scheduling classes.
 310   using class_iterator = std::vector<CodeGenSchedClass>::iterator;
 311   using const_class_iterator = std::vector<CodeGenSchedClass>::const_iterator;
 312   class_iterator classes_begin() { return SchedClasses.begin(); }
 313   const_class_iterator classes_begin() const { return SchedClasses.begin(); }
 314   class_iterator classes_end() { return SchedClasses.end(); }
 315   const_class_iterator classes_end() const { return SchedClasses.end(); }
 316   iterator_range<class_iterator> classes() {
 317    return make_range(classes_begin(), classes_end());
 318   }
 319   iterator_range<const_class_iterator> classes() const {
 320    return make_range(classes_begin(), classes_end());
 321   }
 322   iterator_range<class_iterator> explicit_classes() {
 323     return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
 324   }
 325   iterator_range<const_class_iterator> explicit_classes() const {
 326     return make_range(classes_begin(), classes_begin() + NumInstrSchedClasses);
 327   }
 328
 329   Record *getModelOrItinDef(Record *ProcDef) const {
 330     Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
 331     Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
 332     if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
 333       assert(ModelDef->getValueAsBit("NoModel")
 334              && "Itineraries must be defined within SchedMachineModel");
 335       return ItinsDef;
 336     }
 337     return ModelDef;
 338   }
 339
 340   const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
 341     Record *ModelDef = getModelOrItinDef(ProcDef);
 342     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
 343     assert(I != ProcModelMap.end() && "missing machine model");
 344     return ProcModels[I->second];
 345   }
 346
 347   CodeGenProcModel &getProcModel(Record *ModelDef) {
 348     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
 349     assert(I != ProcModelMap.end() && "missing machine model");
 350     return ProcModels[I->second];
 351   }
 352   const CodeGenProcModel &getProcModel(Record *ModelDef) const {
 353     return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef);
 354   }
 355
 356   // Iterate over the unique processor models.
 357   using ProcIter = std::vector<CodeGenProcModel>::const_iterator;
 358   ProcIter procModelBegin() const { return ProcModels.begin(); }
 359   ProcIter procModelEnd() const { return ProcModels.end(); }
 360   ArrayRef<CodeGenProcModel> procModels() const { return ProcModels; }
 361
 362   // Return true if any processors have itineraries.
 363   bool hasItineraries() const;
 364
 365   // Get a SchedWrite from its index.
 366   const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
 367     assert(Idx < SchedWrites.size() && "bad SchedWrite index");
 368     assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
 369     return SchedWrites[Idx];
 370   }
 371   // Get a SchedWrite from its index.
 372   const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
 373     assert(Idx < SchedReads.size() && "bad SchedRead index");
 374     assert(SchedReads[Idx].isValid() && "invalid SchedRead");
 375     return SchedReads[Idx];
 376   }
 377
 378   const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
 379     return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
 380   }
 381   CodeGenSchedRW &getSchedRW(Record *Def) {
 382     bool IsRead = Def->isSubClassOf("SchedRead");
 383     unsigned Idx = getSchedRWIdx(Def, IsRead);
 384     return const_cast<CodeGenSchedRW&>(
 385       IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
 386   }
 387   const CodeGenSchedRW &getSchedRW(Record *Def) const {
 388     return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
 389   }
 390
 391   unsigned getSchedRWIdx(const Record *Def, bool IsRead) const;
 392
 393   // Return true if the given write record is referenced by a ReadAdvance.
 394   bool hasReadOfWrite(Record *WriteDef) const;
 395
 396   // Get a SchedClass from its index.
 397   CodeGenSchedClass &getSchedClass(unsigned Idx) {
 398     assert(Idx < SchedClasses.size() && "bad SchedClass index");
 399     return SchedClasses[Idx];
 400   }
 401   const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
 402     assert(Idx < SchedClasses.size() && "bad SchedClass index");
 403     return SchedClasses[Idx];
 404   }
 405
 406   // Get the SchedClass index for an instruction. Instructions with no
 407   // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
 408   // for NoItinerary.
 409   unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
 410
 411   using SchedClassIter = std::vector<CodeGenSchedClass>::const_iterator;
 412   SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
 413   SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
 414   ArrayRef<CodeGenSchedClass> schedClasses() const { return SchedClasses; }
 415
 416   unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
 417
 418   void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
 419   void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
 420   void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
 421   void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
 422                           const CodeGenProcModel &ProcModel) const;
 423
 424   unsigned addSchedClass(Record *ItinDef, ArrayRef<unsigned> OperWrites,
 425                          ArrayRef<unsigned> OperReads,
 426                          ArrayRef<unsigned> ProcIndices);
 427
 428   unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
 429
 430   Record *findProcResUnits(Record *ProcResKind, const CodeGenProcModel &PM,
 431                            ArrayRef<SMLoc> Loc) const;
 432
 433 private:
 434   void collectProcModels();
 435
 436   // Initialize a new processor model if it is unique.
 437   void addProcModel(Record *ProcDef);
 438
 439   void collectSchedRW();
 440
 441   std::string genRWName(ArrayRef<unsigned> Seq, bool IsRead);
 442   unsigned findRWForSequence(ArrayRef<unsigned> Seq, bool IsRead);
 443
 444   void collectSchedClasses();
 445
 446   void collectRetireControlUnits();
 447
 448   void collectRegisterFiles();
 449
 450   void collectPfmCounters();
 451
 452   void collectOptionalProcessorInfo();
 453
 454   std::string createSchedClassName(Record *ItinClassDef,
 455                                    ArrayRef<unsigned> OperWrites,
 456                                    ArrayRef<unsigned> OperReads);
 457   std::string createSchedClassName(const RecVec &InstDefs);
 458   void createInstRWClass(Record *InstRWDef);
 459
 460   void collectProcItins();
 461
 462   void collectProcItinRW();
 463
 464   void collectProcUnsupportedFeatures();
 465
 466   void inferSchedClasses();
 467
 468   void checkCompleteness();
 469
 470   void inferFromRW(ArrayRef<unsigned> OperWrites, ArrayRef<unsigned> OperReads,
 471                    unsigned FromClassIdx, ArrayRef<unsigned> ProcIndices);
 472   void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
 473   void inferFromInstRWs(unsigned SCIdx);
 474
 475   bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
 476   void verifyProcResourceGroups(CodeGenProcModel &PM);
 477
 478   void collectProcResources();
 479
 480   void collectItinProcResources(Record *ItinClassDef);
 481
 482   void collectRWResources(unsigned RWIdx, bool IsRead,
 483                           ArrayRef<unsigned> ProcIndices);
 484
 485   void collectRWResources(ArrayRef<unsigned> Writes, ArrayRef<unsigned> Reads,
 486                           ArrayRef<unsigned> ProcIndices);
 487
 488   void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM,
 489                        ArrayRef<SMLoc> Loc);
 490
 491   void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
 492
 493   void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);
 494 };
 495
 496 } // namespace llvm
 497
 498 #endif