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