LLVM 19.0.0git
ScoreboardHazardRecognizer.cpp
Go to the documentation of this file.
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
18#include "llvm/Config/llvm-config.h"
19#include "llvm/MC/MCInstrDesc.h"
22#include "llvm/Support/Debug.h"
24#include <cassert>
25
26using namespace llvm;
27
28#define DEBUG_TYPE DebugType
29
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(idx))
42 break;
43
44 const InstrStage *IS = ItinData->beginStage(idx);
45 const InstrStage *E = ItinData->endStage(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(ScoreboardDepth);
66 RequiredScoreboard.reset(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
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
105 if (IssueWidth == 0)
106 return false;
107
108 return IssueCount == IssueWidth;
109}
110
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(idx),
129 *E = ItinData->endStage(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()) {
148 // Required FUs conflict with both reserved and required ones
149 freeUnits &= ~ReservedScoreboard[StageCycle];
150 [[fallthrough]];
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
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(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(idx),
188 *E = ItinData->endStage(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()) {
199 // Required FUs conflict with both reserved and required ones
200 freeUnits &= ~ReservedScoreboard[cycle + i];
201 [[fallthrough]];
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
230 IssueCount = 0;
231 ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
232 RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
233}
234
236 IssueCount = 0;
237 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
238 ReservedScoreboard.recede();
239 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
240 RequiredScoreboard.recede();
241}
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
#define LLVM_DEBUG(X)
Definition: Debug.h:101
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Itinerary data supplied by a subtarget to be used by a target.
bool isEndMarker(unsigned ItinClassIndx) const
Returns true if the index is for the end marker itinerary.
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
MCSchedModel SchedModel
Basic machine properties.
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
bool isEmpty() const
Returns true if there are no itineraries.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:600
unsigned short Opcode
Definition: MCInstrDesc.h:205
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:589
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:557
virtual void dumpNode(const SUnit &SU) const =0
unsigned MaxLookAhead
MaxLookAhead - Indicate the number of cycles in the scoreboard state.
void Reset() override
Reset - This callback is invoked when a new block of instructions is about to be schedule.
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
void RecedeCycle() override
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - Return the hazard type of emitting this node.
ScoreboardHazardRecognizer(const InstrItineraryData *II, const ScheduleDAG *DAG, const char *ParentDebugType="")
bool atIssueLimit() const override
atIssueLimit - Return true if no more instructions may be issued in this cycle.
void AdvanceCycle() override
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
bool isZeroCost(unsigned Opcode) const
Return true for pseudo instructions that don't consume any machine resources in their current form.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
These values represent a non-pipelined step in the execution of an instruction.
unsigned getNextCycles() const
Returns the number of cycles from the start of this stage to the start of the next stage in the itine...
unsigned getCycles() const
Returns the number of cycles the stage is occupied.
unsigned IssueWidth
Definition: MCSchedule.h:265