1//===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//
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 implements the ScoreboardHazardRecognizer class, which
10// encapsultes hazard-avoidance heuristics for scheduling, based on the
11// scheduling itineraries specified for the target.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
16#include "llvm/CodeGen/ScheduleDAG.h"
17#include "llvm/CodeGen/TargetInstrInfo.h"
18#include "llvm/Config/llvm-config.h"
19#include "llvm/MC/MCInstrDesc.h"
20#include "llvm/MC/MCInstrItineraries.h"
21#include "llvm/Support/Compiler.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/raw_ostream.h"
24#include <cassert>
25
26using namespace llvm;
27
28#define DEBUG_TYPE DebugType
29
30ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(
31 const InstrItineraryData *II, const ScheduleDAG *SchedDAG,
32 const char *ParentDebugType)
33 : DebugType(ParentDebugType), ItinData(II), DAG(SchedDAG) {
34 (void)DebugType;
35 // Determine the maximum depth of any itinerary. This determines the depth of
36 // the scoreboard. We always make the scoreboard at least 1 cycle deep to
37 // avoid dealing with the boundary condition.
38 unsigned ScoreboardDepth = 1;
39 if (ItinData && !ItinData->isEmpty()) {
40 for (unsigned idx = 0; ; ++idx) {
41 if (ItinData->isEndMarker(ItinClassIndx: idx))
42 break;
43
44 const InstrStage *IS = ItinData->beginStage(ItinClassIndx: idx);
45 const InstrStage *E = ItinData->endStage(ItinClassIndx: idx);
46 unsigned CurCycle = 0;
47 unsigned ItinDepth = 0;
48 for (; IS != E; ++IS) {
49 unsigned StageDepth = CurCycle + IS->getCycles();
50 if (ItinDepth < StageDepth) ItinDepth = StageDepth;
51 CurCycle += IS->getNextCycles();
52 }
53
54 // Find the next power-of-2 >= ItinDepth
55 while (ItinDepth > ScoreboardDepth) {
56 ScoreboardDepth *= 2;
57 // Don't set MaxLookAhead until we find at least one nonzero stage.
58 // This way, an itinerary with no stages has MaxLookAhead==0, which
59 // completely bypasses the scoreboard hazard logic.
60 MaxLookAhead = ScoreboardDepth;
61 }
62 }
63 }
64
65 ReservedScoreboard.reset(d: ScoreboardDepth);
66 RequiredScoreboard.reset(d: ScoreboardDepth);
67
68 // If MaxLookAhead is not set above, then we are not enabled.
69 if (!isEnabled())
70 LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
71 else {
72 // A nonempty itinerary must have a SchedModel.
73 IssueWidth = ItinData->SchedModel.IssueWidth;
74 LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
75 << ScoreboardDepth << '\n');
76 }
77}
78
79void ScoreboardHazardRecognizer::Reset() {
80 IssueCount = 0;
81 RequiredScoreboard.reset();
82 ReservedScoreboard.reset();
83}
84
85#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
86LLVM_DUMP_METHOD void ScoreboardHazardRecognizer::Scoreboard::dump() const {
87 dbgs() << "Scoreboard:\n";
88
89 unsigned last = Depth - 1;
90 while ((last > 0) && ((*this)[last] == 0))
91 last--;
92
93 for (unsigned i = 0; i <= last; i++) {
94 InstrStage::FuncUnits FUs = (*this)[i];
95 dbgs() << "\t";
96 for (int j = std::numeric_limits<InstrStage::FuncUnits>::digits - 1;
97 j >= 0; j--)
98 dbgs() << ((FUs & (1ULL << j)) ? '1' : '0');
99 dbgs() << '\n';
100 }
101}
102#endif
103
104bool ScoreboardHazardRecognizer::atIssueLimit() const {
105 if (IssueWidth == 0)
106 return false;
107
108 return IssueCount == IssueWidth;
109}
110
111ScheduleHazardRecognizer::HazardType
112ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
113 if (!ItinData || ItinData->isEmpty())
114 return NoHazard;
115
116 // Note that stalls will be negative for bottom-up scheduling.
117 int cycle = Stalls;
118
119 // Use the itinerary for the underlying instruction to check for
120 // free FU's in the scoreboard at the appropriate future cycles.
121
122 const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
123 if (!MCID) {
124 // Don't check hazards for non-machineinstr Nodes.
125 return NoHazard;
126 }
127 unsigned idx = MCID->getSchedClass();
128 for (const InstrStage *IS = ItinData->beginStage(ItinClassIndx: idx),
129 *E = ItinData->endStage(ItinClassIndx: idx); IS != E; ++IS) {
130 // We must find one of the stage's units free for every cycle the
131 // stage is occupied. FIXME it would be more accurate to find the
132 // same unit free in all the cycles.
133 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
134 int StageCycle = cycle + (int)i;
135 if (StageCycle < 0)
136 continue;
137
138 if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
139 assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
140 "Scoreboard depth exceeded!");
141 // This stage was stalled beyond pipeline depth, so cannot conflict.
142 break;
143 }
144
145 InstrStage::FuncUnits freeUnits = IS->getUnits();
146 switch (IS->getReservationKind()) {
147 case InstrStage::Required:
148 // Required FUs conflict with both reserved and required ones
149 freeUnits &= ~ReservedScoreboard[StageCycle];
150 [[fallthrough]];
151 case InstrStage::Reserved:
152 // Reserved FUs can conflict only with required ones.
153 freeUnits &= ~RequiredScoreboard[StageCycle];
154 break;
155 }
156
157 if (!freeUnits) {
158 LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
159 LLVM_DEBUG(DAG->dumpNode(*SU));
160 return Hazard;
161 }
162 }
163
164 // Advance the cycle to the next stage.
165 cycle += IS->getNextCycles();
166 }
167
168 return NoHazard;
169}
170
171void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
172 if (!ItinData || ItinData->isEmpty())
173 return;
174
175 // Use the itinerary for the underlying instruction to reserve FU's
176 // in the scoreboard at the appropriate future cycles.
177 const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
178 assert(MCID && "The scheduler must filter non-machineinstrs");
179 if (DAG->TII->isZeroCost(Opcode: MCID->Opcode))
180 return;
181
182 ++IssueCount;
183
184 unsigned cycle = 0;
185
186 unsigned idx = MCID->getSchedClass();
187 for (const InstrStage *IS = ItinData->beginStage(ItinClassIndx: idx),
188 *E = ItinData->endStage(ItinClassIndx: idx); IS != E; ++IS) {
189 // We must reserve one of the stage's units for every cycle the
190 // stage is occupied. FIXME it would be more accurate to reserve
191 // the same unit free in all the cycles.
192 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
193 assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
194 "Scoreboard depth exceeded!");
195
196 InstrStage::FuncUnits freeUnits = IS->getUnits();
197 switch (IS->getReservationKind()) {
198 case InstrStage::Required:
199 // Required FUs conflict with both reserved and required ones
200 freeUnits &= ~ReservedScoreboard[cycle + i];
201 [[fallthrough]];
202 case InstrStage::Reserved:
203 // Reserved FUs can conflict only with required ones.
204 freeUnits &= ~RequiredScoreboard[cycle + i];
205 break;
206 }
207
208 // reduce to a single unit
209 InstrStage::FuncUnits freeUnit = 0;
210 do {
211 freeUnit = freeUnits;
212 freeUnits = freeUnit & (freeUnit - 1);
213 } while (freeUnits);
214
215 if (IS->getReservationKind() == InstrStage::Required)
216 RequiredScoreboard[cycle + i] |= freeUnit;
217 else
218 ReservedScoreboard[cycle + i] |= freeUnit;
219 }
220
221 // Advance the cycle to the next stage.
222 cycle += IS->getNextCycles();
223 }
224
225 LLVM_DEBUG(ReservedScoreboard.dump());
226 LLVM_DEBUG(RequiredScoreboard.dump());
227}
228
229void ScoreboardHazardRecognizer::AdvanceCycle() {
230 IssueCount = 0;
231 ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
232 RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
233}
234
235void ScoreboardHazardRecognizer::RecedeCycle() {
236 IssueCount = 0;
237 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
238 ReservedScoreboard.recede();
239 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
240 RequiredScoreboard.recede();
241}
242