LLVM  7.0.0svn
MCSchedule.h
Go to the documentation of this file.
1 //===-- llvm/MC/MCSchedule.h - Scheduling -----------------------*- 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 the classes used to describe a subtarget's machine model
11 // for scheduling and other instruction cost heuristics.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_MC_MCSCHEDULE_H
16 #define LLVM_MC_MCSCHEDULE_H
17 
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/Support/DataTypes.h"
20 #include <cassert>
21 
22 namespace llvm {
23 
24 struct InstrItinerary;
25 class MCSubtargetInfo;
26 class MCInstrInfo;
27 class InstrItineraryData;
28 
29 /// Define a kind of processor resource that will be modeled by the scheduler.
31  const char *Name;
32  unsigned NumUnits; // Number of resource of this kind
33  unsigned SuperIdx; // Index of the resources kind that contains this kind.
34 
35  // Number of resources that may be buffered.
36  //
37  // Buffered resources (BufferSize != 0) may be consumed at some indeterminate
38  // cycle after dispatch. This should be used for out-of-order cpus when
39  // instructions that use this resource can be buffered in a reservaton
40  // station.
41  //
42  // Unbuffered resources (BufferSize == 0) always consume their resource some
43  // fixed number of cycles after dispatch. If a resource is unbuffered, then
44  // the scheduler will avoid scheduling instructions with conflicting resources
45  // in the same cycle. This is for in-order cpus, or the in-order portion of
46  // an out-of-order cpus.
48 
49  // If the resource has sub-units, a pointer to the first element of an array
50  // of `NumUnits` elements containing the ProcResourceIdx of the sub units.
51  // nullptr if the resource does not have sub-units.
52  const unsigned *SubUnitsIdxBegin;
53 
54  bool operator==(const MCProcResourceDesc &Other) const {
55  return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx
56  && BufferSize == Other.BufferSize;
57  }
58 };
59 
60 /// Identify one of the processor resource kinds consumed by a particular
61 /// scheduling class for the specified number of cycles.
63  uint16_t ProcResourceIdx;
64  uint16_t Cycles;
65 
66  bool operator==(const MCWriteProcResEntry &Other) const {
67  return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles;
68  }
69 };
70 
71 /// Specify the latency in cpu cycles for a particular scheduling class and def
72 /// index. -1 indicates an invalid latency. Heuristics would typically consider
73 /// an instruction with invalid latency to have infinite latency. Also identify
74 /// the WriteResources of this def. When the operand expands to a sequence of
75 /// writes, this ID is the last write in the sequence.
77  int16_t Cycles;
78  uint16_t WriteResourceID;
79 
80  bool operator==(const MCWriteLatencyEntry &Other) const {
81  return Cycles == Other.Cycles && WriteResourceID == Other.WriteResourceID;
82  }
83 };
84 
85 /// Specify the number of cycles allowed after instruction issue before a
86 /// particular use operand reads its registers. This effectively reduces the
87 /// write's latency. Here we allow negative cycles for corner cases where
88 /// latency increases. This rule only applies when the entry's WriteResource
89 /// matches the write's WriteResource.
90 ///
91 /// MCReadAdvanceEntries are sorted first by operand index (UseIdx), then by
92 /// WriteResourceIdx.
94  unsigned UseIdx;
95  unsigned WriteResourceID;
96  int Cycles;
97 
98  bool operator==(const MCReadAdvanceEntry &Other) const {
99  return UseIdx == Other.UseIdx && WriteResourceID == Other.WriteResourceID
100  && Cycles == Other.Cycles;
101  }
102 };
103 
104 /// Summarize the scheduling resources required for an instruction of a
105 /// particular scheduling class.
106 ///
107 /// Defined as an aggregate struct for creating tables with initializer lists.
109  static const unsigned short InvalidNumMicroOps = (1U << 14) - 1;
110  static const unsigned short VariantNumMicroOps = InvalidNumMicroOps - 1;
111 
112 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
113  const char* Name;
114 #endif
115  uint16_t NumMicroOps : 14;
116  bool BeginGroup : 1;
117  bool EndGroup : 1;
118  uint16_t WriteProcResIdx; // First index into WriteProcResTable.
120  uint16_t WriteLatencyIdx; // First index into WriteLatencyTable.
122  uint16_t ReadAdvanceIdx; // First index into ReadAdvanceTable.
124 
125  bool isValid() const {
126  return NumMicroOps != InvalidNumMicroOps;
127  }
128  bool isVariant() const {
129  return NumMicroOps == VariantNumMicroOps;
130  }
131 };
132 
133 /// Specify the cost of a register definition in terms of number of physical
134 /// register allocated at register renaming stage. For example, AMD Jaguar.
135 /// natively supports 128-bit data types, and operations on 256-bit registers
136 /// (i.e. YMM registers) are internally split into two COPs (complex operations)
137 /// and each COP updates a physical register. Basically, on Jaguar, a YMM
138 /// register write effectively consumes two physical registers. That means,
139 /// the cost of a YMM write in the BtVer2 model is 2.
141  unsigned RegisterClassID;
142  unsigned Cost;
143 };
144 
145 /// A register file descriptor.
146 ///
147 /// This struct allows to describe processor register files. In particular, it
148 /// helps describing the size of the register file, as well as the cost of
149 /// allocating a register file at register renaming stage.
150 /// FIXME: this struct can be extended to provide information about the number
151 /// of read/write ports to the register file. A value of zero for field
152 /// 'NumPhysRegs' means: this register file has an unbounded number of physical
153 /// registers.
155  const char *Name;
156  uint16_t NumPhysRegs;
158  // Index of the first cost entry in MCExtraProcessorInfo::RegisterCostTable.
160 };
161 
162 /// Provide extra details about the machine processor.
163 ///
164 /// This is a collection of "optional" processor information that is not
165 /// normally used by the LLVM machine schedulers, but that can be consumed by
166 /// external tools like llvm-mca to improve the quality of the peformance
167 /// analysis.
169  // Actual size of the reorder buffer in hardware.
171  // Number of instructions retired per cycle.
177 
179  // An optional name of a performance counter that can be used to measure
180  // cycles.
181  const char *CycleCounter;
182 
183  // For each MCProcResourceDesc defined by the processor, an optional list of
184  // names of performance counters that can be used to measure the resource
185  // utilization.
186  const char **IssueCounters;
187  };
189 };
190 
191 /// Machine model for scheduling, bundling, and heuristics.
192 ///
193 /// The machine model directly provides basic information about the
194 /// microarchitecture to the scheduler in the form of properties. It also
195 /// optionally refers to scheduler resource tables and itinerary
196 /// tables. Scheduler resource tables model the latency and cost for each
197 /// instruction type. Itinerary tables are an independent mechanism that
198 /// provides a detailed reservation table describing each cycle of instruction
199 /// execution. Subtargets may define any or all of the above categories of data
200 /// depending on the type of CPU and selected scheduler.
201 struct MCSchedModel {
202  // IssueWidth is the maximum number of instructions that may be scheduled in
203  // the same per-cycle group.
204  unsigned IssueWidth;
205  static const unsigned DefaultIssueWidth = 1;
206 
207  // MicroOpBufferSize is the number of micro-ops that the processor may buffer
208  // for out-of-order execution.
209  //
210  // "0" means operations that are not ready in this cycle are not considered
211  // for scheduling (they go in the pending queue). Latency is paramount. This
212  // may be more efficient if many instructions are pending in a schedule.
213  //
214  // "1" means all instructions are considered for scheduling regardless of
215  // whether they are ready in this cycle. Latency still causes issue stalls,
216  // but we balance those stalls against other heuristics.
217  //
218  // "> 1" means the processor is out-of-order. This is a machine independent
219  // estimate of highly machine specific characteristics such as the register
220  // renaming pool and reorder buffer.
222  static const unsigned DefaultMicroOpBufferSize = 0;
223 
224  // LoopMicroOpBufferSize is the number of micro-ops that the processor may
225  // buffer for optimized loop execution. More generally, this represents the
226  // optimal number of micro-ops in a loop body. A loop may be partially
227  // unrolled to bring the count of micro-ops in the loop body closer to this
228  // number.
230  static const unsigned DefaultLoopMicroOpBufferSize = 0;
231 
232  // LoadLatency is the expected latency of load instructions.
233  unsigned LoadLatency;
234  static const unsigned DefaultLoadLatency = 4;
235 
236  // HighLatency is the expected latency of "very high latency" operations.
237  // See TargetInstrInfo::isHighLatencyDef().
238  // By default, this is set to an arbitrarily high number of cycles
239  // likely to have some impact on scheduling heuristics.
240  unsigned HighLatency;
241  static const unsigned DefaultHighLatency = 10;
242 
243  // MispredictPenalty is the typical number of extra cycles the processor
244  // takes to recover from a branch misprediction.
246  static const unsigned DefaultMispredictPenalty = 10;
247 
248  bool PostRAScheduler; // default value is false
249 
251 
252  unsigned ProcID;
256  unsigned NumSchedClasses;
257  // Instruction itinerary tables used by InstrItineraryData.
258  friend class InstrItineraryData;
260 
262 
263  bool hasExtraProcessorInfo() const { return ExtraProcessorInfo; }
264 
265  unsigned getProcessorID() const { return ProcID; }
266 
267  /// Does this machine model include instruction-level scheduling.
268  bool hasInstrSchedModel() const { return SchedClassTable; }
269 
271  assert(hasExtraProcessorInfo() &&
272  "No extra information available for this model");
273  return *ExtraProcessorInfo;
274  }
275 
276  /// Return true if this machine model data for all instructions with a
277  /// scheduling class (itinerary class or SchedRW list).
278  bool isComplete() const { return CompleteModel; }
279 
280  /// Return true if machine supports out of order execution.
281  bool isOutOfOrder() const { return MicroOpBufferSize > 1; }
282 
283  unsigned getNumProcResourceKinds() const {
284  return NumProcResourceKinds;
285  }
286 
287  const MCProcResourceDesc *getProcResource(unsigned ProcResourceIdx) const {
288  assert(hasInstrSchedModel() && "No scheduling machine model");
289 
290  assert(ProcResourceIdx < NumProcResourceKinds && "bad proc resource idx");
291  return &ProcResourceTable[ProcResourceIdx];
292  }
293 
294  const MCSchedClassDesc *getSchedClassDesc(unsigned SchedClassIdx) const {
295  assert(hasInstrSchedModel() && "No scheduling machine model");
296 
297  assert(SchedClassIdx < NumSchedClasses && "bad scheduling class idx");
298  return &SchedClassTable[SchedClassIdx];
299  }
300 
301  /// Returns the latency value for the scheduling class.
302  static int computeInstrLatency(const MCSubtargetInfo &STI,
303  const MCSchedClassDesc &SCDesc);
304 
305  int computeInstrLatency(const MCSubtargetInfo &STI, unsigned SClass) const;
306 
307  // Returns the reciprocal throughput information from a MCSchedClassDesc.
308  static Optional<double>
309  getReciprocalThroughput(const MCSubtargetInfo &STI,
310  const MCSchedClassDesc &SCDesc);
311 
312  static Optional<double>
313  getReciprocalThroughput(unsigned SchedClass, const InstrItineraryData &IID);
314 
315  Optional<double> computeReciprocalThroughput(const MCSubtargetInfo &STI,
316  const MCInstrInfo &MCII,
317  unsigned Opcode) const;
318 
319  /// Returns the default initialized model.
320  static const MCSchedModel &GetDefaultSchedModel() { return Default; }
321  static const MCSchedModel Default;
322 };
323 
324 } // namespace llvm
325 
326 #endif
unsigned MispredictPenalty
Definition: MCSchedule.h:245
unsigned MicroOpBufferSize
Definition: MCSchedule.h:221
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned IssueWidth
Definition: MCSchedule.h:204
uint16_t NumReadAdvanceEntries
Definition: MCSchedule.h:123
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
Definition: MCSchedule.h:287
unsigned getProcessorID() const
Definition: MCSchedule.h:265
const MCSchedClassDesc * getSchedClassDesc(unsigned SchedClassIdx) const
Definition: MCSchedule.h:294
bool isComplete() const
Return true if this machine model data for all instructions with a scheduling class (itinerary class ...
Definition: MCSchedule.h:278
A register file descriptor.
Definition: MCSchedule.h:154
unsigned NumProcResourceKinds
Definition: MCSchedule.h:255
Specify the cost of a register definition in terms of number of physical register allocated at regist...
Definition: MCSchedule.h:140
Provide extra details about the machine processor.
Definition: MCSchedule.h:168
uint16_t NumWriteProcResEntries
Definition: MCSchedule.h:119
Itinerary data supplied by a subtarget to be used by a target.
bool isValid() const
Definition: MCSchedule.h:125
const InstrItinerary * InstrItineraries
Definition: MCSchedule.h:259
static const MCSchedModel & GetDefaultSchedModel()
Returns the default initialized model.
Definition: MCSchedule.h:320
bool operator==(const MCReadAdvanceEntry &Other) const
Definition: MCSchedule.h:98
unsigned LoadLatency
Definition: MCSchedule.h:233
bool operator==(const MCProcResourceDesc &Other) const
Definition: MCSchedule.h:54
bool hasExtraProcessorInfo() const
Definition: MCSchedule.h:263
const MCRegisterFileDesc * RegisterFiles
Definition: MCSchedule.h:173
const unsigned * SubUnitsIdxBegin
Definition: MCSchedule.h:52
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Definition: MCSchedule.h:62
Summarize the scheduling resources required for an instruction of a particular scheduling class...
Definition: MCSchedule.h:108
Interface to description of machine instruction set.
Definition: MCInstrInfo.h:24
bool operator==(const MCWriteProcResEntry &Other) const
Definition: MCSchedule.h:66
bool operator==(const MCWriteLatencyEntry &Other) const
Definition: MCSchedule.h:80
const MCRegisterCostEntry * RegisterCostTable
Definition: MCSchedule.h:175
bool hasInstrSchedModel() const
Does this machine model include instruction-level scheduling.
Definition: MCSchedule.h:268
Specify the latency in cpu cycles for a particular scheduling class and def index.
Definition: MCSchedule.h:76
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:30
static const MCSchedModel Default
Definition: MCSchedule.h:321
unsigned HighLatency
Definition: MCSchedule.h:240
bool isOutOfOrder() const
Return true if machine supports out of order execution.
Definition: MCSchedule.h:281
PfmCountersInfo PfmCounters
Definition: MCSchedule.h:188
bool isVariant() const
Definition: MCSchedule.h:128
const MCSchedClassDesc * SchedClassTable
Definition: MCSchedule.h:254
unsigned LoopMicroOpBufferSize
Definition: MCSchedule.h:229
Specify the number of cycles allowed after instruction issue before a particular use operand reads it...
Definition: MCSchedule.h:93
Generic base class for all target subtargets.
const MCExtraProcessorInfo & getExtraProcessorInfo() const
Definition: MCSchedule.h:270
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
An itinerary represents the scheduling information for an instruction.
uint16_t NumRegisterCostEntries
Definition: MCSchedule.h:157
uint16_t NumWriteLatencyEntries
Definition: MCSchedule.h:121
const MCProcResourceDesc * ProcResourceTable
Definition: MCSchedule.h:253
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:201
unsigned NumSchedClasses
Definition: MCSchedule.h:256
const MCExtraProcessorInfo * ExtraProcessorInfo
Definition: MCSchedule.h:261
unsigned getNumProcResourceKinds() const
Definition: MCSchedule.h:283