ScoreboardHazardRecognizer.cpp revision 77e300e8f0b8db8eec448cae9c87d7c5bfad9757 
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
25using namespace llvm;
26
27#ifndef NDEBUG
28const char *ScoreboardHazardRecognizer::DebugType = "";
29#endif
30
31ScoreboardHazardRecognizer::
32ScoreboardHazardRecognizer(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
86void ScoreboardHazardRecognizer::Reset() {
87  IssueCount = 0;
88  RequiredScoreboard.reset();
89  ReservedScoreboard.reset();
90}
91
92#ifndef NDEBUG
93void ScoreboardHazardRecognizer::Scoreboard::dump() const {
94  dbgs() << "Scoreboard:\n";
95
96  unsigned last = Depth - 1;
97  while ((last > 0) && ((*this)[last] == 0))
98    last--;
99
100  for (unsigned i = 0; i <= last; i++) {
101    unsigned FUs = (*this)[i];
102    dbgs() << "\t";
103    for (int j = 31; j >= 0; j--)
104      dbgs() << ((FUs & (1 << j)) ? '1' : '0');
105    dbgs() << '\n';
106  }
107}
108#endif
109
110bool ScoreboardHazardRecognizer::atIssueLimit() const {
111  if (IssueWidth == 0)
112    return false;
113
114  return IssueCount == IssueWidth;
115}
116
117ScheduleHazardRecognizer::HazardType
118ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
119  if (!ItinData || ItinData->isEmpty())
120    return NoHazard;
121
122  // Note that stalls will be negative for bottom-up scheduling.
123  int cycle = Stalls;
124
125  // Use the itinerary for the underlying instruction to check for
126  // free FU's in the scoreboard at the appropriate future cycles.
127
128  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
129  if (MCID == NULL) {
130    // Don't check hazards for non-machineinstr Nodes.
131    return NoHazard;
132  }
133  unsigned idx = MCID->getSchedClass();
134  for (const InstrStage *IS = ItinData->beginStage(idx),
135         *E = ItinData->endStage(idx); IS != E; ++IS) {
136    // We must find one of the stage's units free for every cycle the
137    // stage is occupied. FIXME it would be more accurate to find the
138    // same unit free in all the cycles.
139    for (unsigned int i = 0; i < IS->getCycles(); ++i) {
140      int StageCycle = cycle + (int)i;
141      if (StageCycle < 0)
142        continue;
143
144      if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
145        assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
146               "Scoreboard depth exceeded!");
147        // This stage was stalled beyond pipeline depth, so cannot conflict.
148        break;
149      }
150
151      unsigned freeUnits = IS->getUnits();
152      switch (IS->getReservationKind()) {
153      case InstrStage::Required:
154        // Required FUs conflict with both reserved and required ones
155        freeUnits &= ~ReservedScoreboard[StageCycle];
156        // FALLTHROUGH
157      case InstrStage::Reserved:
158        // Reserved FUs can conflict only with required ones.
159        freeUnits &= ~RequiredScoreboard[StageCycle];
160        break;
161      }
162
163      if (!freeUnits) {
164        DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
165        DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
166        DEBUG(DAG->dumpNode(SU));
167        return Hazard;
168      }
169    }
170
171    // Advance the cycle to the next stage.
172    cycle += IS->getNextCycles();
173  }
174
175  return NoHazard;
176}
177
178void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
179  if (!ItinData || ItinData->isEmpty())
180    return;
181
182  // Use the itinerary for the underlying instruction to reserve FU's
183  // in the scoreboard at the appropriate future cycles.
184  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
185  assert(MCID && "The scheduler must filter non-machineinstrs");
186  if (DAG->TII->isZeroCost(MCID->Opcode))
187    return;
188
189  ++IssueCount;
190
191  unsigned cycle = 0;
192
193  unsigned idx = MCID->getSchedClass();
194  for (const InstrStage *IS = ItinData->beginStage(idx),
195         *E = ItinData->endStage(idx); IS != E; ++IS) {
196    // We must reserve one of the stage's units for every cycle the
197    // stage is occupied. FIXME it would be more accurate to reserve
198    // the same unit free in all the cycles.
199    for (unsigned int i = 0; i < IS->getCycles(); ++i) {
200      assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
201             "Scoreboard depth exceeded!");
202
203      unsigned freeUnits = IS->getUnits();
204      switch (IS->getReservationKind()) {
205      case InstrStage::Required:
206        // Required FUs conflict with both reserved and required ones
207        freeUnits &= ~ReservedScoreboard[cycle + i];
208        // FALLTHROUGH
209      case InstrStage::Reserved:
210        // Reserved FUs can conflict only with required ones.
211        freeUnits &= ~RequiredScoreboard[cycle + i];
212        break;
213      }
214
215      // reduce to a single unit
216      unsigned freeUnit = 0;
217      do {
218        freeUnit = freeUnits;
219        freeUnits = freeUnit & (freeUnit - 1);
220      } while (freeUnits);
221
222      if (IS->getReservationKind() == InstrStage::Required)
223        RequiredScoreboard[cycle + i] |= freeUnit;
224      else
225        ReservedScoreboard[cycle + i] |= freeUnit;
226    }
227
228    // Advance the cycle to the next stage.
229    cycle += IS->getNextCycles();
230  }
231
232  DEBUG(ReservedScoreboard.dump());
233  DEBUG(RequiredScoreboard.dump());
234}
235
236void ScoreboardHazardRecognizer::AdvanceCycle() {
237  IssueCount = 0;
238  ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
239  RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
240}
241
242void ScoreboardHazardRecognizer::RecedeCycle() {
243  IssueCount = 0;
244  ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
245  ReservedScoreboard.recede();
246  RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
247  RequiredScoreboard.recede();
248}
249