LLVM 20.0.0git
MCInstrItineraries.h
Go to the documentation of this file.
1//===- llvm/MC/MCInstrItineraries.h - Scheduling ----------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file describes the structures used for instruction
10// itineraries, stages, and operand reads/writes. This is used by
11// schedulers to determine instruction stages and latencies.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_MC_MCINSTRITINERARIES_H
16#define LLVM_MC_MCINSTRITINERARIES_H
17
18#include "llvm/MC/MCSchedule.h"
19#include <algorithm>
20#include <optional>
21
22namespace 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
59struct InstrStage {
62 Reserved = 1
63 };
64
65 /// Bitmask representing a set of functional units.
67
68 unsigned Cycles_; ///< Length of stage in machine cycles
69 FuncUnits Units_; ///< Choice of functional units
70 int NextCycles_; ///< Number of machine cycles to next stage
71 ReservationKinds Kind_; ///< Kind of the FU reservation
72
73 /// Returns the number of cycles the stage is occupied.
74 unsigned getCycles() const {
75 return Cycles_;
76 }
77
78 /// Returns the choice of FUs.
80 return Units_;
81 }
82
84 return Kind_;
85 }
86
87 /// Returns the number of cycles from the start of this stage to the
88 /// start of the next stage in the itinerary
89 unsigned getNextCycles() const {
90 return (NextCycles_ >= 0) ? (unsigned)NextCycles_ : Cycles_;
91 }
92};
93
94//===----------------------------------------------------------------------===//
95/// An itinerary represents the scheduling information for an instruction.
96/// This includes a set of stages occupied by the instruction and the pipeline
97/// cycle in which operands are read and written.
98///
100 int16_t NumMicroOps; ///< # of micro-ops, -1 means it's variable
101 uint16_t FirstStage; ///< Index of first stage in itinerary
102 uint16_t LastStage; ///< Index of last + 1 stage in itinerary
103 uint16_t FirstOperandCycle; ///< Index of first operand rd/wr
104 uint16_t LastOperandCycle; ///< Index of last + 1 operand rd/wr
105};
106
107//===----------------------------------------------------------------------===//
108/// Itinerary data supplied by a subtarget to be used by a target.
109///
111public:
113 MCSchedModel::Default; ///< Basic machine properties.
114 const InstrStage *Stages = nullptr; ///< Array of stages selected
115 const unsigned *OperandCycles = nullptr; ///< Array of operand cycles selected
116 const unsigned *Forwardings = nullptr; ///< Array of pipeline forwarding paths
118 nullptr; ///< Array of itineraries selected
119
122 const unsigned *OS, const unsigned *F)
124 Itineraries(SchedModel.InstrItineraries) {}
125
126 /// Returns true if there are no itineraries.
127 bool isEmpty() const { return Itineraries == nullptr; }
128
129 /// Returns true if the index is for the end marker itinerary.
130 bool isEndMarker(unsigned ItinClassIndx) const {
131 return ((Itineraries[ItinClassIndx].FirstStage == UINT16_MAX) &&
132 (Itineraries[ItinClassIndx].LastStage == UINT16_MAX));
133 }
134
135 /// Return the first stage of the itinerary.
136 const InstrStage *beginStage(unsigned ItinClassIndx) const {
137 unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage;
138 return Stages + StageIdx;
139 }
140
141 /// Return the last+1 stage of the itinerary.
142 const InstrStage *endStage(unsigned ItinClassIndx) const {
143 unsigned StageIdx = Itineraries[ItinClassIndx].LastStage;
144 return Stages + StageIdx;
145 }
146
147 /// Return the total stage latency of the given class. The latency is
148 /// the maximum completion time for any stage in the itinerary. If no stages
149 /// exist, it defaults to one cycle.
150 unsigned getStageLatency(unsigned ItinClassIndx) const {
151 // If the target doesn't provide itinerary information, use a simple
152 // non-zero default value for all instructions.
153 if (isEmpty())
154 return 1;
155
156 // Calculate the maximum completion time for any stage.
157 unsigned Latency = 0, StartCycle = 0;
158 for (const InstrStage *IS = beginStage(ItinClassIndx),
159 *E = endStage(ItinClassIndx); IS != E; ++IS) {
160 Latency = std::max(Latency, StartCycle + IS->getCycles());
161 StartCycle += IS->getNextCycles();
162 }
163 return Latency;
164 }
165
166 /// Return the cycle for the given class and operand. Return std::nullopt if
167 /// the information is not available for the operand.
168 std::optional<unsigned> getOperandCycle(unsigned ItinClassIndx,
169 unsigned OperandIdx) const {
170 if (isEmpty())
171 return std::nullopt;
172
173 unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle;
174 unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle;
175 if ((FirstIdx + OperandIdx) >= LastIdx)
176 return std::nullopt;
177
178 return OperandCycles[FirstIdx + OperandIdx];
179 }
180
181 /// Return true if there is a pipeline forwarding between instructions
182 /// of itinerary classes DefClass and UseClasses so that value produced by an
183 /// instruction of itinerary class DefClass, operand index DefIdx can be
184 /// bypassed when it's read by an instruction of itinerary class UseClass,
185 /// operand index UseIdx.
186 bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx,
187 unsigned UseClass, unsigned UseIdx) const {
188 unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle;
189 unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle;
190 if ((FirstDefIdx + DefIdx) >= LastDefIdx)
191 return false;
192 if (Forwardings[FirstDefIdx + DefIdx] == 0)
193 return false;
194
195 unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle;
196 unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle;
197 if ((FirstUseIdx + UseIdx) >= LastUseIdx)
198 return false;
199
200 return Forwardings[FirstDefIdx + DefIdx] ==
201 Forwardings[FirstUseIdx + UseIdx];
202 }
203
204 /// Compute and return the use operand latency of a given itinerary
205 /// class and operand index if the value is produced by an instruction of the
206 /// specified itinerary class and def operand index. Return std::nullopt if
207 /// the information is not available for the operand.
208 std::optional<unsigned> getOperandLatency(unsigned DefClass, unsigned DefIdx,
209 unsigned UseClass,
210 unsigned UseIdx) const {
211 if (isEmpty())
212 return std::nullopt;
213
214 std::optional<unsigned> DefCycle = getOperandCycle(DefClass, DefIdx);
215 std::optional<unsigned> UseCycle = getOperandCycle(UseClass, UseIdx);
216 if (!DefCycle || !UseCycle)
217 return std::nullopt;
218
219 if (UseCycle > *DefCycle + 1)
220 return std::nullopt;
221
222 UseCycle = *DefCycle - *UseCycle + 1;
223 if (UseCycle > 0u &&
224 hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx))
225 // FIXME: This assumes one cycle benefit for every pipeline forwarding.
226 UseCycle = *UseCycle - 1;
227 return UseCycle;
228 }
229
230 /// Return the number of micro-ops that the given class decodes to.
231 /// Return -1 for classes that require dynamic lookup via TargetInstrInfo.
232 int getNumMicroOps(unsigned ItinClassIndx) const {
233 if (isEmpty())
234 return 1;
235 return Itineraries[ItinClassIndx].NumMicroOps;
236 }
237};
238
239} // end namespace llvm
240
241#endif // LLVM_MC_MCINSTRITINERARIES_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define F(x, y, z)
Definition: MD5.cpp:55
raw_pwrite_stream & OS
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.
std::optional< unsigned > getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const
Return the cycle for the given class and operand.
const InstrStage * Stages
Array of stages selected.
unsigned getStageLatency(unsigned ItinClassIndx) const
Return the total stage latency of the given class.
bool isEndMarker(unsigned ItinClassIndx) const
Returns true if the index is for the end marker itinerary.
std::optional< unsigned > 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 ...
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
MCSchedModel SchedModel
Basic machine properties.
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 ...
InstrItineraryData(const MCSchedModel &SM, const InstrStage *S, const unsigned *OS, const unsigned *F)
const unsigned * Forwardings
Array of pipeline forwarding paths.
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
const unsigned * OperandCycles
Array of operand cycles selected.
const InstrItinerary * Itineraries
Array of itineraries selected.
bool isEmpty() const
Returns true if there are no itineraries.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
An itinerary represents the scheduling information for an instruction.
uint16_t LastOperandCycle
Index of last + 1 operand rd/wr.
uint16_t FirstOperandCycle
Index of first operand rd/wr.
uint16_t FirstStage
Index of first stage in itinerary.
uint16_t LastStage
Index of last + 1 stage in itinerary.
These values represent a non-pipelined step in the execution of an instruction.
uint64_t FuncUnits
Bitmask representing a set of functional units.
unsigned getNextCycles() const
Returns the number of cycles from the start of this stage to the start of the next stage in the itine...
FuncUnits getUnits() const
Returns the choice of FUs.
ReservationKinds getReservationKind() const
FuncUnits Units_
Choice of functional units.
unsigned Cycles_
Length of stage in machine cycles.
unsigned getCycles() const
Returns the number of cycles the stage is occupied.
int NextCycles_
Number of machine cycles to next stage.
ReservationKinds Kind_
Kind of the FU reservation.
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:253
static const MCSchedModel Default
Returns the default initialized model.
Definition: MCSchedule.h:393