LLVM  6.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/Support/DataTypes.h"
19 #include <cassert>
20 
21 namespace llvm {
22 
23 struct InstrItinerary;
24 
25 /// Define a kind of processor resource that will be modeled by the scheduler.
27 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
28  const char *Name;
29 #endif
30  unsigned NumUnits; // Number of resource of this kind
31  unsigned SuperIdx; // Index of the resources kind that contains this kind.
32 
33  // Number of resources that may be buffered.
34  //
35  // Buffered resources (BufferSize != 0) may be consumed at some indeterminate
36  // cycle after dispatch. This should be used for out-of-order cpus when
37  // instructions that use this resource can be buffered in a reservaton
38  // station.
39  //
40  // Unbuffered resources (BufferSize == 0) always consume their resource some
41  // fixed number of cycles after dispatch. If a resource is unbuffered, then
42  // the scheduler will avoid scheduling instructions with conflicting resources
43  // in the same cycle. This is for in-order cpus, or the in-order portion of
44  // an out-of-order cpus.
46 
47  bool operator==(const MCProcResourceDesc &Other) const {
48  return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx
49  && BufferSize == Other.BufferSize;
50  }
51 };
52 
53 /// Identify one of the processor resource kinds consumed by a particular
54 /// scheduling class for the specified number of cycles.
56  unsigned ProcResourceIdx;
57  unsigned Cycles;
58 
59  bool operator==(const MCWriteProcResEntry &Other) const {
60  return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles;
61  }
62 };
63 
64 /// Specify the latency in cpu cycles for a particular scheduling class and def
65 /// index. -1 indicates an invalid latency. Heuristics would typically consider
66 /// an instruction with invalid latency to have infinite latency. Also identify
67 /// the WriteResources of this def. When the operand expands to a sequence of
68 /// writes, this ID is the last write in the sequence.
70  int Cycles;
71  unsigned WriteResourceID;
72 
73  bool operator==(const MCWriteLatencyEntry &Other) const {
74  return Cycles == Other.Cycles && WriteResourceID == Other.WriteResourceID;
75  }
76 };
77 
78 /// Specify the number of cycles allowed after instruction issue before a
79 /// particular use operand reads its registers. This effectively reduces the
80 /// write's latency. Here we allow negative cycles for corner cases where
81 /// latency increases. This rule only applies when the entry's WriteResource
82 /// matches the write's WriteResource.
83 ///
84 /// MCReadAdvanceEntries are sorted first by operand index (UseIdx), then by
85 /// WriteResourceIdx.
87  unsigned UseIdx;
88  unsigned WriteResourceID;
89  int Cycles;
90 
91  bool operator==(const MCReadAdvanceEntry &Other) const {
92  return UseIdx == Other.UseIdx && WriteResourceID == Other.WriteResourceID
93  && Cycles == Other.Cycles;
94  }
95 };
96 
97 /// Summarize the scheduling resources required for an instruction of a
98 /// particular scheduling class.
99 ///
100 /// Defined as an aggregate struct for creating tables with initializer lists.
102  static const unsigned short InvalidNumMicroOps = UINT16_MAX;
103  static const unsigned short VariantNumMicroOps = UINT16_MAX - 1;
104 
105 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
106  const char* Name;
107 #endif
108  unsigned short NumMicroOps;
110  bool EndGroup;
111  unsigned WriteProcResIdx; // First index into WriteProcResTable.
113  unsigned WriteLatencyIdx; // First index into WriteLatencyTable.
115  unsigned ReadAdvanceIdx; // First index into ReadAdvanceTable.
117 
118  bool isValid() const {
119  return NumMicroOps != InvalidNumMicroOps;
120  }
121  bool isVariant() const {
122  return NumMicroOps == VariantNumMicroOps;
123  }
124 };
125 
126 /// Machine model for scheduling, bundling, and heuristics.
127 ///
128 /// The machine model directly provides basic information about the
129 /// microarchitecture to the scheduler in the form of properties. It also
130 /// optionally refers to scheduler resource tables and itinerary
131 /// tables. Scheduler resource tables model the latency and cost for each
132 /// instruction type. Itinerary tables are an independent mechanism that
133 /// provides a detailed reservation table describing each cycle of instruction
134 /// execution. Subtargets may define any or all of the above categories of data
135 /// depending on the type of CPU and selected scheduler.
136 struct MCSchedModel {
137  // IssueWidth is the maximum number of instructions that may be scheduled in
138  // the same per-cycle group.
139  unsigned IssueWidth;
140  static const unsigned DefaultIssueWidth = 1;
141 
142  // MicroOpBufferSize is the number of micro-ops that the processor may buffer
143  // for out-of-order execution.
144  //
145  // "0" means operations that are not ready in this cycle are not considered
146  // for scheduling (they go in the pending queue). Latency is paramount. This
147  // may be more efficient if many instructions are pending in a schedule.
148  //
149  // "1" means all instructions are considered for scheduling regardless of
150  // whether they are ready in this cycle. Latency still causes issue stalls,
151  // but we balance those stalls against other heuristics.
152  //
153  // "> 1" means the processor is out-of-order. This is a machine independent
154  // estimate of highly machine specific characteristics such as the register
155  // renaming pool and reorder buffer.
157  static const unsigned DefaultMicroOpBufferSize = 0;
158 
159  // LoopMicroOpBufferSize is the number of micro-ops that the processor may
160  // buffer for optimized loop execution. More generally, this represents the
161  // optimal number of micro-ops in a loop body. A loop may be partially
162  // unrolled to bring the count of micro-ops in the loop body closer to this
163  // number.
165  static const unsigned DefaultLoopMicroOpBufferSize = 0;
166 
167  // LoadLatency is the expected latency of load instructions.
168  unsigned LoadLatency;
169  static const unsigned DefaultLoadLatency = 4;
170 
171  // HighLatency is the expected latency of "very high latency" operations.
172  // See TargetInstrInfo::isHighLatencyDef().
173  // By default, this is set to an arbitrarily high number of cycles
174  // likely to have some impact on scheduling heuristics.
175  unsigned HighLatency;
176  static const unsigned DefaultHighLatency = 10;
177 
178  // MispredictPenalty is the typical number of extra cycles the processor
179  // takes to recover from a branch misprediction.
181  static const unsigned DefaultMispredictPenalty = 10;
182 
183  bool PostRAScheduler; // default value is false
184 
186 
187  unsigned ProcID;
191  unsigned NumSchedClasses;
192  // Instruction itinerary tables used by InstrItineraryData.
193  friend class InstrItineraryData;
195 
196  unsigned getProcessorID() const { return ProcID; }
197 
198  /// Does this machine model include instruction-level scheduling.
199  bool hasInstrSchedModel() const { return SchedClassTable; }
200 
201  /// Return true if this machine model data for all instructions with a
202  /// scheduling class (itinerary class or SchedRW list).
203  bool isComplete() const { return CompleteModel; }
204 
205  /// Return true if machine supports out of order execution.
206  bool isOutOfOrder() const { return MicroOpBufferSize > 1; }
207 
208  unsigned getNumProcResourceKinds() const {
209  return NumProcResourceKinds;
210  }
211 
212  const MCProcResourceDesc *getProcResource(unsigned ProcResourceIdx) const {
213  assert(hasInstrSchedModel() && "No scheduling machine model");
214 
215  assert(ProcResourceIdx < NumProcResourceKinds && "bad proc resource idx");
216  return &ProcResourceTable[ProcResourceIdx];
217  }
218 
219  const MCSchedClassDesc *getSchedClassDesc(unsigned SchedClassIdx) const {
220  assert(hasInstrSchedModel() && "No scheduling machine model");
221 
222  assert(SchedClassIdx < NumSchedClasses && "bad scheduling class idx");
223  return &SchedClassTable[SchedClassIdx];
224  }
225 
226  /// Returns the default initialized model.
227  static const MCSchedModel &GetDefaultSchedModel() { return Default; }
228  static const MCSchedModel Default;
229 };
230 
231 } // End llvm namespace
232 
233 #endif
unsigned MispredictPenalty
Definition: MCSchedule.h:180
unsigned NumWriteProcResEntries
Definition: MCSchedule.h:112
unsigned MicroOpBufferSize
Definition: MCSchedule.h:156
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned IssueWidth
Definition: MCSchedule.h:139
unsigned short NumMicroOps
Definition: MCSchedule.h:108
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
Definition: MCSchedule.h:212
unsigned getProcessorID() const
Definition: MCSchedule.h:196
const MCSchedClassDesc * getSchedClassDesc(unsigned SchedClassIdx) const
Definition: MCSchedule.h:219
bool isComplete() const
Return true if this machine model data for all instructions with a scheduling class (itinerary class ...
Definition: MCSchedule.h:203
unsigned NumProcResourceKinds
Definition: MCSchedule.h:190
Itinerary data supplied by a subtarget to be used by a target.
bool isValid() const
Definition: MCSchedule.h:118
const InstrItinerary * InstrItineraries
Definition: MCSchedule.h:194
unsigned NumReadAdvanceEntries
Definition: MCSchedule.h:116
static const MCSchedModel & GetDefaultSchedModel()
Returns the default initialized model.
Definition: MCSchedule.h:227
bool operator==(const MCReadAdvanceEntry &Other) const
Definition: MCSchedule.h:91
unsigned LoadLatency
Definition: MCSchedule.h:168
bool operator==(const MCProcResourceDesc &Other) const
Definition: MCSchedule.h:47
unsigned NumWriteLatencyEntries
Definition: MCSchedule.h:114
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Definition: MCSchedule.h:55
Summarize the scheduling resources required for an instruction of a particular scheduling class...
Definition: MCSchedule.h:101
bool operator==(const MCWriteProcResEntry &Other) const
Definition: MCSchedule.h:59
bool operator==(const MCWriteLatencyEntry &Other) const
Definition: MCSchedule.h:73
bool hasInstrSchedModel() const
Does this machine model include instruction-level scheduling.
Definition: MCSchedule.h:199
Specify the latency in cpu cycles for a particular scheduling class and def index.
Definition: MCSchedule.h:69
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:26
static const MCSchedModel Default
Definition: MCSchedule.h:228
unsigned HighLatency
Definition: MCSchedule.h:175
bool isOutOfOrder() const
Return true if machine supports out of order execution.
Definition: MCSchedule.h:206
bool isVariant() const
Definition: MCSchedule.h:121
const MCSchedClassDesc * SchedClassTable
Definition: MCSchedule.h:189
unsigned LoopMicroOpBufferSize
Definition: MCSchedule.h:164
Specify the number of cycles allowed after instruction issue before a particular use operand reads it...
Definition: MCSchedule.h:86
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
An itinerary represents the scheduling information for an instruction.
const MCProcResourceDesc * ProcResourceTable
Definition: MCSchedule.h:188
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:136
unsigned NumSchedClasses
Definition: MCSchedule.h:191
unsigned getNumProcResourceKinds() const
Definition: MCSchedule.h:208