LLVM  6.0.0svn
MCInstrItineraries.h
Go to the documentation of this file.
1 //===- llvm/MC/MCInstrItineraries.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 describes the structures used for instruction
11 // itineraries, stages, and operand reads/writes. This is used by
12 // schedulers to determine instruction stages and latencies.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_MC_MCINSTRITINERARIES_H
17 #define LLVM_MC_MCINSTRITINERARIES_H
18 
19 #include "llvm/MC/MCSchedule.h"
20 #include <algorithm>
21 
22 namespace llvm {
23 
24 //===----------------------------------------------------------------------===//
25 /// These values represent a non-pipelined step in
26 /// the execution of an instruction. Cycles represents the number of
27 /// discrete time slots needed to complete the stage. Units represent
28 /// the choice of functional units that can be used to complete the
29 /// stage. Eg. IntUnit1, IntUnit2. NextCycles indicates how many
30 /// cycles should elapse from the start of this stage to the start of
31 /// the next stage in the itinerary. A value of -1 indicates that the
32 /// next stage should start immediately after the current one.
33 /// For example:
34 ///
35 /// { 1, x, -1 }
36 /// indicates that the stage occupies FU x for 1 cycle and that
37 /// the next stage starts immediately after this one.
38 ///
39 /// { 2, x|y, 1 }
40 /// indicates that the stage occupies either FU x or FU y for 2
41 /// consecutive cycles and that the next stage starts one cycle
42 /// after this stage starts. That is, the stage requirements
43 /// overlap in time.
44 ///
45 /// { 1, x, 0 }
46 /// indicates that the stage occupies FU x for 1 cycle and that
47 /// the next stage starts in this same cycle. This can be used to
48 /// indicate that the instruction requires multiple stages at the
49 /// same time.
50 ///
51 /// FU reservation can be of two different kinds:
52 /// - FUs which instruction actually requires
53 /// - FUs which instruction just reserves. Reserved unit is not available for
54 /// execution of other instruction. However, several instructions can reserve
55 /// the same unit several times.
56 /// Such two types of units reservation is used to model instruction domain
57 /// change stalls, FUs using the same resource (e.g. same register file), etc.
58 
59 struct InstrStage {
61  Required = 0,
63  };
64 
65  unsigned Cycles_; ///< Length of stage in machine cycles
66  unsigned Units_; ///< Choice of functional units
67  int NextCycles_; ///< Number of machine cycles to next stage
68  ReservationKinds Kind_; ///< Kind of the FU reservation
69 
70  /// \brief Returns the number of cycles the stage is occupied.
71  unsigned getCycles() const {
72  return Cycles_;
73  }
74 
75  /// \brief Returns the choice of FUs.
76  unsigned getUnits() const {
77  return Units_;
78  }
79 
81  return Kind_;
82  }
83 
84  /// \brief Returns the number of cycles from the start of this stage to the
85  /// start of the next stage in the itinerary
86  unsigned getNextCycles() const {
87  return (NextCycles_ >= 0) ? (unsigned)NextCycles_ : Cycles_;
88  }
89 };
90 
91 //===----------------------------------------------------------------------===//
92 /// An itinerary represents the scheduling information for an instruction.
93 /// This includes a set of stages occupied by the instruction and the pipeline
94 /// cycle in which operands are read and written.
95 ///
97  int NumMicroOps; ///< # of micro-ops, -1 means it's variable
98  unsigned FirstStage; ///< Index of first stage in itinerary
99  unsigned LastStage; ///< Index of last + 1 stage in itinerary
100  unsigned FirstOperandCycle; ///< Index of first operand rd/wr
101  unsigned LastOperandCycle; ///< Index of last + 1 operand rd/wr
102 };
103 
104 //===----------------------------------------------------------------------===//
105 /// Itinerary data supplied by a subtarget to be used by a target.
106 ///
108 public:
109  MCSchedModel SchedModel =
110  MCSchedModel::GetDefaultSchedModel(); ///< Basic machine properties.
111  const InstrStage *Stages = nullptr; ///< Array of stages selected
112  const unsigned *OperandCycles = nullptr; ///< Array of operand cycles selected
113  const unsigned *Forwardings = nullptr; ///< Array of pipeline forwarding paths
114  const InstrItinerary *Itineraries =
115  nullptr; ///< Array of itineraries selected
116 
117  InstrItineraryData() = default;
119  const unsigned *OS, const unsigned *F)
120  : SchedModel(SM), Stages(S), OperandCycles(OS), Forwardings(F),
121  Itineraries(SchedModel.InstrItineraries) {}
122 
123  /// \brief Returns true if there are no itineraries.
124  bool isEmpty() const { return Itineraries == nullptr; }
125 
126  /// \brief Returns true if the index is for the end marker itinerary.
127  bool isEndMarker(unsigned ItinClassIndx) const {
128  return ((Itineraries[ItinClassIndx].FirstStage == ~0U) &&
129  (Itineraries[ItinClassIndx].LastStage == ~0U));
130  }
131 
132  /// \brief Return the first stage of the itinerary.
133  const InstrStage *beginStage(unsigned ItinClassIndx) const {
134  unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage;
135  return Stages + StageIdx;
136  }
137 
138  /// \brief Return the last+1 stage of the itinerary.
139  const InstrStage *endStage(unsigned ItinClassIndx) const {
140  unsigned StageIdx = Itineraries[ItinClassIndx].LastStage;
141  return Stages + StageIdx;
142  }
143 
144  /// \brief Return the total stage latency of the given class. The latency is
145  /// the maximum completion time for any stage in the itinerary. If no stages
146  /// exist, it defaults to one cycle.
147  unsigned getStageLatency(unsigned ItinClassIndx) const {
148  // If the target doesn't provide itinerary information, use a simple
149  // non-zero default value for all instructions.
150  if (isEmpty())
151  return 1;
152 
153  // Calculate the maximum completion time for any stage.
154  unsigned Latency = 0, StartCycle = 0;
155  for (const InstrStage *IS = beginStage(ItinClassIndx),
156  *E = endStage(ItinClassIndx); IS != E; ++IS) {
157  Latency = std::max(Latency, StartCycle + IS->getCycles());
158  StartCycle += IS->getNextCycles();
159  }
160  return Latency;
161  }
162 
163  /// \brief Return the cycle for the given class and operand. Return -1 if no
164  /// cycle is specified for the operand.
165  int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const {
166  if (isEmpty())
167  return -1;
168 
169  unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle;
170  unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle;
171  if ((FirstIdx + OperandIdx) >= LastIdx)
172  return -1;
173 
174  return (int)OperandCycles[FirstIdx + OperandIdx];
175  }
176 
177  /// \brief Return true if there is a pipeline forwarding between instructions
178  /// of itinerary classes DefClass and UseClasses so that value produced by an
179  /// instruction of itinerary class DefClass, operand index DefIdx can be
180  /// bypassed when it's read by an instruction of itinerary class UseClass,
181  /// operand index UseIdx.
182  bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx,
183  unsigned UseClass, unsigned UseIdx) const {
184  unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle;
185  unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle;
186  if ((FirstDefIdx + DefIdx) >= LastDefIdx)
187  return false;
188  if (Forwardings[FirstDefIdx + DefIdx] == 0)
189  return false;
190 
191  unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle;
192  unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle;
193  if ((FirstUseIdx + UseIdx) >= LastUseIdx)
194  return false;
195 
196  return Forwardings[FirstDefIdx + DefIdx] ==
197  Forwardings[FirstUseIdx + UseIdx];
198  }
199 
200  /// \brief Compute and return the use operand latency of a given itinerary
201  /// class and operand index if the value is produced by an instruction of the
202  /// specified itinerary class and def operand index.
203  int getOperandLatency(unsigned DefClass, unsigned DefIdx,
204  unsigned UseClass, unsigned UseIdx) const {
205  if (isEmpty())
206  return -1;
207 
208  int DefCycle = getOperandCycle(DefClass, DefIdx);
209  if (DefCycle == -1)
210  return -1;
211 
212  int UseCycle = getOperandCycle(UseClass, UseIdx);
213  if (UseCycle == -1)
214  return -1;
215 
216  UseCycle = DefCycle - UseCycle + 1;
217  if (UseCycle > 0 &&
218  hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx))
219  // FIXME: This assumes one cycle benefit for every pipeline forwarding.
220  --UseCycle;
221  return UseCycle;
222  }
223 
224  /// \brief Return the number of micro-ops that the given class decodes to.
225  /// Return -1 for classes that require dynamic lookup via TargetInstrInfo.
226  int getNumMicroOps(unsigned ItinClassIndx) const {
227  if (isEmpty())
228  return 1;
229  return Itineraries[ItinClassIndx].NumMicroOps;
230  }
231 };
232 
233 } // end namespace llvm
234 
235 #endif // LLVM_MC_MCINSTRITINERARIES_H
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
unsigned Units_
Choice of functional units.
unsigned getUnits() const
Returns the choice of FUs.
int NextCycles_
Number of machine cycles to next stage.
F(f)
int NumMicroOps
of micro-ops, -1 means it&#39;s variable
unsigned FirstOperandCycle
Index of first operand rd/wr.
InstrItineraryData(const MCSchedModel &SM, const InstrStage *S, const unsigned *OS, const unsigned *F)
Itinerary data supplied by a subtarget to be used by a target.
int getNumMicroOps(unsigned ItinClassIndx) const
Return the number of micro-ops that the given class decodes to.
unsigned getStageLatency(unsigned ItinClassIndx) const
Return the total stage latency of the given class.
unsigned LastOperandCycle
Index of last + 1 operand rd/wr.
static const MCSchedModel & GetDefaultSchedModel()
Returns the default initialized model.
Definition: MCSchedule.h:227
unsigned getNextCycles() const
Returns the number of cycles from the start of this stage to the start of the next stage in the itine...
unsigned FirstStage
Index of first stage in itinerary.
ReservationKinds getReservationKind() const
int getOperandLatency(unsigned DefClass, unsigned DefIdx, unsigned UseClass, unsigned UseIdx) const
Compute and return the use operand latency of a given itinerary class and operand index if the value ...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ReservationKinds Kind_
Kind of the FU reservation.
unsigned Cycles_
Length of stage in machine cycles.
bool isEndMarker(unsigned ItinClassIndx) const
Returns true if the index is for the end marker itinerary.
unsigned LastStage
Index of last + 1 stage in itinerary.
unsigned getCycles() const
Returns the number of cycles the stage is occupied.
bool isEmpty() const
Returns true if there are no itineraries.
These values represent a non-pipelined step in the execution of an instruction.
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx, unsigned UseClass, unsigned UseIdx) const
Return true if there is a pipeline forwarding between instructions of itinerary classes DefClass and ...
An itinerary represents the scheduling information for an instruction.
int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const
Return the cycle for the given class and operand.
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:136