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