1 //===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the ScoreboardHazardRecognizer class, which
11 // encapsultes hazard-avoidance heuristics for scheduling, based on the
12 // scheduling itineraries specified for the target.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
17 #include "llvm/CodeGen/ScheduleDAG.h"
18 #include "llvm/MC/MCInstrDesc.h"
19 #include "llvm/MC/MCInstrItineraries.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/Target/TargetInstrInfo.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   // 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     DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
71   else {
72     // A nonempty itinerary must have a SchedModel.
73     IssueWidth = ItinData->SchedModel.IssueWidth;
74     DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
75           << ScoreboardDepth << '\n');
76   }
77 }
78 
79 void ScoreboardHazardRecognizer::Reset() {
80   IssueCount = 0;
81   RequiredScoreboard.reset();
82   ReservedScoreboard.reset();
83 }
84 
85 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
86 LLVM_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     unsigned FUs = (*this)[i];
95     dbgs() << "\t";
96     for (int j = 31; j >= 0; j--)
97       dbgs() << ((FUs & (1 << j)) ? '1' : '0');
98     dbgs() << '\n';
99   }
100 }
101 #endif
102 
103 bool ScoreboardHazardRecognizer::atIssueLimit() const {
104   if (IssueWidth == 0)
105     return false;
106 
107   return IssueCount == IssueWidth;
108 }
109 
110 ScheduleHazardRecognizer::HazardType
111 ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
112   if (!ItinData || ItinData->isEmpty())
113     return NoHazard;
114 
115   // Note that stalls will be negative for bottom-up scheduling.
116   int cycle = Stalls;
117 
118   // Use the itinerary for the underlying instruction to check for
119   // free FU's in the scoreboard at the appropriate future cycles.
120 
121   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
122   if (!MCID) {
123     // Don't check hazards for non-machineinstr Nodes.
124     return NoHazard;
125   }
126   unsigned idx = MCID->getSchedClass();
127   for (const InstrStage *IS = ItinData->beginStage(idx),
128          *E = ItinData->endStage(idx); IS != E; ++IS) {
129     // We must find one of the stage's units free for every cycle the
130     // stage is occupied. FIXME it would be more accurate to find the
131     // same unit free in all the cycles.
132     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
133       int StageCycle = cycle + (int)i;
134       if (StageCycle < 0)
135         continue;
136 
137       if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
138         assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
139                "Scoreboard depth exceeded!");
140         // This stage was stalled beyond pipeline depth, so cannot conflict.
141         break;
142       }
143 
144       unsigned freeUnits = IS->getUnits();
145       switch (IS->getReservationKind()) {
146       case InstrStage::Required:
147         // Required FUs conflict with both reserved and required ones
148         freeUnits &= ~ReservedScoreboard[StageCycle];
149         LLVM_FALLTHROUGH;
150       case InstrStage::Reserved:
151         // Reserved FUs can conflict only with required ones.
152         freeUnits &= ~RequiredScoreboard[StageCycle];
153         break;
154       }
155 
156       if (!freeUnits) {
157         DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
158         DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
159         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 
171 void 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(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       unsigned 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         LLVM_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       unsigned 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   DEBUG(ReservedScoreboard.dump());
226   DEBUG(RequiredScoreboard.dump());
227 }
228 
229 void ScoreboardHazardRecognizer::AdvanceCycle() {
230   IssueCount = 0;
231   ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
232   RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
233 }
234 
235 void 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