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