• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
26 struct MCProcResourceDesc {
27 #ifndef NDEBUG
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.
45   int BufferSize;
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.
55 struct MCWriteProcResEntry {
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.
69 struct MCWriteLatencyEntry {
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.
86 struct MCReadAdvanceEntry {
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.
101 struct MCSchedClassDesc {
102   static const unsigned short InvalidNumMicroOps = UINT16_MAX;
103   static const unsigned short VariantNumMicroOps = UINT16_MAX - 1;
104 
105 #ifndef NDEBUG
106   const char* Name;
107 #endif
108   unsigned short NumMicroOps;
109   bool     BeginGroup;
110   bool     EndGroup;
111   unsigned WriteProcResIdx; // First index into WriteProcResTable.
112   unsigned NumWriteProcResEntries;
113   unsigned WriteLatencyIdx; // First index into WriteLatencyTable.
114   unsigned NumWriteLatencyEntries;
115   unsigned ReadAdvanceIdx; // First index into ReadAdvanceTable.
116   unsigned NumReadAdvanceEntries;
117 
isValidMCSchedClassDesc118   bool isValid() const {
119     return NumMicroOps != InvalidNumMicroOps;
120   }
isVariantMCSchedClassDesc121   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.
156   unsigned MicroOpBufferSize;
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.
164   unsigned LoopMicroOpBufferSize;
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.
180   unsigned MispredictPenalty;
181   static const unsigned DefaultMispredictPenalty = 10;
182 
183   bool PostRAScheduler; // default value is false
184 
185   bool CompleteModel;
186 
187   unsigned ProcID;
188   const MCProcResourceDesc *ProcResourceTable;
189   const MCSchedClassDesc *SchedClassTable;
190   unsigned NumProcResourceKinds;
191   unsigned NumSchedClasses;
192   // Instruction itinerary tables used by InstrItineraryData.
193   friend class InstrItineraryData;
194   const InstrItinerary *InstrItineraries;
195 
getProcessorIDMCSchedModel196   unsigned getProcessorID() const { return ProcID; }
197 
198   /// Does this machine model include instruction-level scheduling.
hasInstrSchedModelMCSchedModel199   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).
isCompleteMCSchedModel203   bool isComplete() const { return CompleteModel; }
204 
205   /// Return true if machine supports out of order execution.
isOutOfOrderMCSchedModel206   bool isOutOfOrder() const { return MicroOpBufferSize > 1; }
207 
getNumProcResourceKindsMCSchedModel208   unsigned getNumProcResourceKinds() const {
209     return NumProcResourceKinds;
210   }
211 
getProcResourceMCSchedModel212   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 
getSchedClassDescMCSchedModel219   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.
GetDefaultSchedModelMCSchedModel227   static const MCSchedModel &GetDefaultSchedModel() { return Default; }
228   static const MCSchedModel Default;
229 };
230 
231 } // End llvm namespace
232 
233 #endif
234