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