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