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