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
24using namespace llvm;
25
26#define DEBUG_TYPE ::llvm::ScoreboardHazardRecognizer::DebugType
27
28#ifndef NDEBUG
29const char *ScoreboardHazardRecognizer::DebugType = "";
30#endif
31
32ScoreboardHazardRecognizer::
33ScoreboardHazardRecognizer(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
87void ScoreboardHazardRecognizer::Reset() {
88  IssueCount = 0;
89  RequiredScoreboard.reset();
90  ReservedScoreboard.reset();
91}
92
93#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
94void 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
111bool ScoreboardHazardRecognizer::atIssueLimit() const {
112  if (IssueWidth == 0)
113    return false;
114
115  return IssueCount == IssueWidth;
116}
117
118ScheduleHazardRecognizer::HazardType
119ScoreboardHazardRecognizer::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
179void 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
237void ScoreboardHazardRecognizer::AdvanceCycle() {
238  IssueCount = 0;
239  ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
240  RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
241}
242
243void 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