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
235
236
237
238
239
240
241
| //===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//
//
// 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 implements the ScoreboardHazardRecognizer class, which
// encapsultes hazard-avoidance heuristics for scheduling, based on the
// scheduling itineraries specified for the target.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
using namespace llvm;
#define DEBUG_TYPE DebugType
ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(
const InstrItineraryData *II, const ScheduleDAG *SchedDAG,
const char *ParentDebugType)
: ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II),
DAG(SchedDAG) {
(void)DebugType;
// Determine the maximum depth of any itinerary. This determines the depth of
// the scoreboard. We always make the scoreboard at least 1 cycle deep to
// avoid dealing with the boundary condition.
unsigned ScoreboardDepth = 1;
if (ItinData && !ItinData->isEmpty()) {
for (unsigned idx = 0; ; ++idx) {
if (ItinData->isEndMarker(idx))
break;
const InstrStage *IS = ItinData->beginStage(idx);
const InstrStage *E = ItinData->endStage(idx);
unsigned CurCycle = 0;
unsigned ItinDepth = 0;
for (; IS != E; ++IS) {
unsigned StageDepth = CurCycle + IS->getCycles();
if (ItinDepth < StageDepth) ItinDepth = StageDepth;
CurCycle += IS->getNextCycles();
}
// Find the next power-of-2 >= ItinDepth
while (ItinDepth > ScoreboardDepth) {
ScoreboardDepth *= 2;
// Don't set MaxLookAhead until we find at least one nonzero stage.
// This way, an itinerary with no stages has MaxLookAhead==0, which
// completely bypasses the scoreboard hazard logic.
MaxLookAhead = ScoreboardDepth;
}
}
}
ReservedScoreboard.reset(ScoreboardDepth);
RequiredScoreboard.reset(ScoreboardDepth);
// If MaxLookAhead is not set above, then we are not enabled.
if (!isEnabled())
LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
else {
// A nonempty itinerary must have a SchedModel.
IssueWidth = ItinData->SchedModel.IssueWidth;
LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
<< ScoreboardDepth << '\n');
}
}
void ScoreboardHazardRecognizer::Reset() {
IssueCount = 0;
RequiredScoreboard.reset();
ReservedScoreboard.reset();
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void ScoreboardHazardRecognizer::Scoreboard::dump() const {
dbgs() << "Scoreboard:\n";
unsigned last = Depth - 1;
while ((last > 0) && ((*this)[last] == 0))
last--;
for (unsigned i = 0; i <= last; i++) {
unsigned FUs = (*this)[i];
dbgs() << "\t";
for (int j = 31; j >= 0; j--)
dbgs() << ((FUs & (1 << j)) ? '1' : '0');
dbgs() << '\n';
}
}
#endif
bool ScoreboardHazardRecognizer::atIssueLimit() const {
if (IssueWidth == 0)
return false;
return IssueCount == IssueWidth;
}
ScheduleHazardRecognizer::HazardType
ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
if (!ItinData || ItinData->isEmpty())
return NoHazard;
// Note that stalls will be negative for bottom-up scheduling.
int cycle = Stalls;
// Use the itinerary for the underlying instruction to check for
// free FU's in the scoreboard at the appropriate future cycles.
const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
if (!MCID) {
// Don't check hazards for non-machineinstr Nodes.
return NoHazard;
}
unsigned idx = MCID->getSchedClass();
for (const InstrStage *IS = ItinData->beginStage(idx),
*E = ItinData->endStage(idx); IS != E; ++IS) {
// We must find one of the stage's units free for every cycle the
// stage is occupied. FIXME it would be more accurate to find the
// same unit free in all the cycles.
for (unsigned int i = 0; i < IS->getCycles(); ++i) {
int StageCycle = cycle + (int)i;
if (StageCycle < 0)
continue;
if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
"Scoreboard depth exceeded!");
// This stage was stalled beyond pipeline depth, so cannot conflict.
break;
}
unsigned freeUnits = IS->getUnits();
switch (IS->getReservationKind()) {
case InstrStage::Required:
// Required FUs conflict with both reserved and required ones
freeUnits &= ~ReservedScoreboard[StageCycle];
LLVM_FALLTHROUGH;
case InstrStage::Reserved:
// Reserved FUs can conflict only with required ones.
freeUnits &= ~RequiredScoreboard[StageCycle];
break;
}
if (!freeUnits) {
LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
LLVM_DEBUG(DAG->dumpNode(*SU));
return Hazard;
}
}
// Advance the cycle to the next stage.
cycle += IS->getNextCycles();
}
return NoHazard;
}
void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
if (!ItinData || ItinData->isEmpty())
return;
// Use the itinerary for the underlying instruction to reserve FU's
// in the scoreboard at the appropriate future cycles.
const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
assert(MCID && "The scheduler must filter non-machineinstrs");
if (DAG->TII->isZeroCost(MCID->Opcode))
return;
++IssueCount;
unsigned cycle = 0;
unsigned idx = MCID->getSchedClass();
for (const InstrStage *IS = ItinData->beginStage(idx),
*E = ItinData->endStage(idx); IS != E; ++IS) {
// We must reserve one of the stage's units for every cycle the
// stage is occupied. FIXME it would be more accurate to reserve
// the same unit free in all the cycles.
for (unsigned int i = 0; i < IS->getCycles(); ++i) {
assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
"Scoreboard depth exceeded!");
unsigned freeUnits = IS->getUnits();
switch (IS->getReservationKind()) {
case InstrStage::Required:
// Required FUs conflict with both reserved and required ones
freeUnits &= ~ReservedScoreboard[cycle + i];
LLVM_FALLTHROUGH;
case InstrStage::Reserved:
// Reserved FUs can conflict only with required ones.
freeUnits &= ~RequiredScoreboard[cycle + i];
break;
}
// reduce to a single unit
unsigned freeUnit = 0;
do {
freeUnit = freeUnits;
freeUnits = freeUnit & (freeUnit - 1);
} while (freeUnits);
if (IS->getReservationKind() == InstrStage::Required)
RequiredScoreboard[cycle + i] |= freeUnit;
else
ReservedScoreboard[cycle + i] |= freeUnit;
}
// Advance the cycle to the next stage.
cycle += IS->getNextCycles();
}
LLVM_DEBUG(ReservedScoreboard.dump());
LLVM_DEBUG(RequiredScoreboard.dump());
}
void ScoreboardHazardRecognizer::AdvanceCycle() {
IssueCount = 0;
ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
}
void ScoreboardHazardRecognizer::RecedeCycle() {
IssueCount = 0;
ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
ReservedScoreboard.recede();
RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
RequiredScoreboard.recede();
}
|