1 //===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//
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
7 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
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"
28 #define DEBUG_TYPE DebugType
30 ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(
31 const InstrItineraryData
*II
, const ScheduleDAG
*SchedDAG
,
32 const char *ParentDebugType
)
33 : DebugType(ParentDebugType
), ItinData(II
), DAG(SchedDAG
) {
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
))
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();
54 // Find the next power-of-2 >= ItinDepth
55 while (ItinDepth
> ScoreboardDepth
) {
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
;
65 ReservedScoreboard
.reset(ScoreboardDepth
);
66 RequiredScoreboard
.reset(ScoreboardDepth
);
68 // If MaxLookAhead is not set above, then we are not enabled.
70 LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
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');
79 void ScoreboardHazardRecognizer::Reset() {
81 RequiredScoreboard
.reset();
82 ReservedScoreboard
.reset();
85 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
86 LLVM_DUMP_METHOD
void ScoreboardHazardRecognizer::Scoreboard::dump() const {
87 dbgs() << "Scoreboard:\n";
89 unsigned last
= Depth
- 1;
90 while ((last
> 0) && ((*this)[last
] == 0))
93 for (unsigned i
= 0; i
<= last
; i
++) {
94 InstrStage::FuncUnits FUs
= (*this)[i
];
96 for (int j
= std::numeric_limits
<InstrStage::FuncUnits
>::digits
- 1;
98 dbgs() << ((FUs
& (1ULL << j
)) ? '1' : '0');
104 bool ScoreboardHazardRecognizer::atIssueLimit() const {
108 return IssueCount
== IssueWidth
;
111 ScheduleHazardRecognizer::HazardType
112 ScoreboardHazardRecognizer::getHazardType(SUnit
*SU
, int Stalls
) {
113 if (!ItinData
|| ItinData
->isEmpty())
116 // Note that stalls will be negative for bottom-up scheduling.
119 // Use the itinerary for the underlying instruction to check for
120 // free FU's in the scoreboard at the appropriate future cycles.
122 const MCInstrDesc
*MCID
= DAG
->getInstrDesc(SU
);
124 // Don't check hazards for non-machineinstr Nodes.
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
;
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.
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
];
151 case InstrStage::Reserved
:
152 // Reserved FUs can conflict only with required ones.
153 freeUnits
&= ~RequiredScoreboard
[StageCycle
];
158 LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle
<< ", ");
159 LLVM_DEBUG(DAG
->dumpNode(*SU
));
164 // Advance the cycle to the next stage.
165 cycle
+= IS
->getNextCycles();
171 void ScoreboardHazardRecognizer::EmitInstruction(SUnit
*SU
) {
172 if (!ItinData
|| ItinData
->isEmpty())
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
))
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!");
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
];
202 case InstrStage::Reserved
:
203 // Reserved FUs can conflict only with required ones.
204 freeUnits
&= ~RequiredScoreboard
[cycle
+ i
];
208 // reduce to a single unit
209 InstrStage::FuncUnits freeUnit
= 0;
211 freeUnit
= freeUnits
;
212 freeUnits
= freeUnit
& (freeUnit
- 1);
215 if (IS
->getReservationKind() == InstrStage::Required
)
216 RequiredScoreboard
[cycle
+ i
] |= freeUnit
;
218 ReservedScoreboard
[cycle
+ i
] |= freeUnit
;
221 // Advance the cycle to the next stage.
222 cycle
+= IS
->getNextCycles();
225 LLVM_DEBUG(ReservedScoreboard
.dump());
226 LLVM_DEBUG(RequiredScoreboard
.dump());
229 void ScoreboardHazardRecognizer::AdvanceCycle() {
231 ReservedScoreboard
[0] = 0; ReservedScoreboard
.advance();
232 RequiredScoreboard
[0] = 0; RequiredScoreboard
.advance();
235 void ScoreboardHazardRecognizer::RecedeCycle() {
237 ReservedScoreboard
[ReservedScoreboard
.getDepth()-1] = 0;
238 ReservedScoreboard
.recede();
239 RequiredScoreboard
[RequiredScoreboard
.getDepth()-1] = 0;
240 RequiredScoreboard
.recede();