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
24namespace llvm {
25
26class CodeGenTarget;
27class CodeGenSchedModels;
28class CodeGenInstruction;
29
30typedef std::vector<Record*> RecVec;
31typedef std::vector<Record*>::const_iterator RecIter;
32
33typedef std::vector<unsigned> IdxVec;
34typedef std::vector<unsigned>::const_iterator IdxIter;
35
36void 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.
46struct 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.
97struct 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.
127struct 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.
175struct 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.
226class 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  typedef DenseMap<Record*, unsigned> ProcModelMapTy;
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  typedef DenseMap<Record*, unsigned> InstClassMapTy;
256  InstClassMapTy InstrClassMap;
257
258public:
259  CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
260
261  // iterator access to the scheduling classes.
262  typedef std::vector<CodeGenSchedClass>::iterator class_iterator;
263  typedef std::vector<CodeGenSchedClass>::const_iterator const_class_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  typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
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  typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
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,
386                           const CodeGenProcModel &PM) const;
387
388private:
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
437  void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
438
439  void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);
440};
441
442} // namespace llvm
443
444#endif
445