Line data Source code
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 {
60 : enum ReservationKinds {
61 : Required = 0,
62 : Reserved = 1
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 : /// Returns the number of cycles the stage is occupied.
71 0 : unsigned getCycles() const {
72 0 : return Cycles_;
73 : }
74 :
75 : /// Returns the choice of FUs.
76 0 : unsigned getUnits() const {
77 0 : return Units_;
78 : }
79 :
80 0 : ReservationKinds getReservationKind() const {
81 0 : return Kind_;
82 : }
83 :
84 : /// Returns the number of cycles from the start of this stage to the
85 : /// start of the next stage in the itinerary
86 0 : unsigned getNextCycles() const {
87 56459262 : 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 : ///
96 : struct InstrItinerary {
97 : int16_t NumMicroOps; ///< # of micro-ops, -1 means it's variable
98 : uint16_t FirstStage; ///< Index of first stage in itinerary
99 : uint16_t LastStage; ///< Index of last + 1 stage in itinerary
100 : uint16_t FirstOperandCycle; ///< Index of first operand rd/wr
101 : uint16_t 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 : ///
107 : class InstrItineraryData {
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 418395 : InstrItineraryData() = default;
118 : InstrItineraryData(const MCSchedModel &SM, const InstrStage *S,
119 : const unsigned *OS, const unsigned *F)
120 20780 : : SchedModel(SM), Stages(S), OperandCycles(OS), Forwardings(F),
121 1307248 : Itineraries(SchedModel.InstrItineraries) {}
122 :
123 : /// Returns true if there are no itineraries.
124 0 : bool isEmpty() const { return Itineraries == nullptr; }
125 :
126 : /// Returns true if the index is for the end marker itinerary.
127 0 : bool isEndMarker(unsigned ItinClassIndx) const {
128 31948914 : return ((Itineraries[ItinClassIndx].FirstStage == UINT16_MAX) &&
129 57568 : (Itineraries[ItinClassIndx].LastStage == UINT16_MAX));
130 : }
131 :
132 : /// Return the first stage of the itinerary.
133 0 : const InstrStage *beginStage(unsigned ItinClassIndx) const {
134 1384830 : unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage;
135 33276176 : return Stages + StageIdx;
136 : }
137 :
138 : /// Return the last+1 stage of the itinerary.
139 0 : const InstrStage *endStage(unsigned ItinClassIndx) const {
140 33236431 : unsigned StageIdx = Itineraries[ItinClassIndx].LastStage;
141 33236431 : return Stages + StageIdx;
142 : }
143 :
144 : /// 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 330005 : 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 330005 : if (isEmpty())
151 : return 1;
152 :
153 : // Calculate the maximum completion time for any stage.
154 318265 : unsigned Latency = 0, StartCycle = 0;
155 318265 : for (const InstrStage *IS = beginStage(ItinClassIndx),
156 761679 : *E = endStage(ItinClassIndx); IS != E; ++IS) {
157 443414 : Latency = std::max(Latency, StartCycle + IS->getCycles());
158 594976 : StartCycle += IS->getNextCycles();
159 : }
160 318265 : return Latency;
161 : }
162 :
163 : /// 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 220046 : if (isEmpty())
167 : return -1;
168 :
169 810581 : unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle;
170 810581 : unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle;
171 810581 : if ((FirstIdx + OperandIdx) >= LastIdx)
172 : return -1;
173 :
174 142560 : return (int)OperandCycles[FirstIdx + OperandIdx];
175 : }
176 :
177 : /// 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 138682 : bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx,
183 : unsigned UseClass, unsigned UseIdx) const {
184 138682 : unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle;
185 138682 : unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle;
186 138682 : if ((FirstDefIdx + DefIdx) >= LastDefIdx)
187 : return false;
188 138363 : if (Forwardings[FirstDefIdx + DefIdx] == 0)
189 : return false;
190 :
191 60046 : unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle;
192 60046 : unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle;
193 60046 : if ((FirstUseIdx + UseIdx) >= LastUseIdx)
194 : return false;
195 :
196 : return Forwardings[FirstDefIdx + DefIdx] ==
197 60046 : Forwardings[FirstUseIdx + UseIdx];
198 : }
199 :
200 : /// 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 373103 : int getOperandLatency(unsigned DefClass, unsigned DefIdx,
204 : unsigned UseClass, unsigned UseIdx) const {
205 373103 : if (isEmpty())
206 : return -1;
207 :
208 : int DefCycle = getOperandCycle(DefClass, DefIdx);
209 168781 : if (DefCycle == -1)
210 : return -1;
211 :
212 : int UseCycle = getOperandCycle(UseClass, UseIdx);
213 142312 : if (UseCycle == -1)
214 : return -1;
215 :
216 142312 : UseCycle = DefCycle - UseCycle + 1;
217 142312 : if (UseCycle > 0 &&
218 136402 : hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx))
219 : // FIXME: This assumes one cycle benefit for every pipeline forwarding.
220 : --UseCycle;
221 : return UseCycle;
222 : }
223 :
224 : /// 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 331990 : if (isEmpty())
228 : return 1;
229 463687 : return Itineraries[ItinClassIndx].NumMicroOps;
230 : }
231 : };
232 :
233 : } // end namespace llvm
234 :
235 : #endif // LLVM_MC_MCINSTRITINERARIES_H
|
