← Back to branch summary

~ubuntu-branches/ubuntu/quantal/llvm-3.1/quantal

« back to all changes in this revision

Viewing changes to lib/CodeGen/ScoreboardHazardRecognizer.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2012-03-29 19:09:51 UTC
  • Revision ID: package-import@ubuntu.com-20120329190951-aq83ivog4cg8bxun
Tags: upstream-3.1~svn153643
Import upstream version 3.1~svn153643

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/CodeGen/ScoreboardHazardRecognizer.cpp
 
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
 
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
 
 
78
void ScoreboardHazardRecognizer::Reset() {
 
79
  IssueCount = 0;
 
80
  RequiredScoreboard.reset();
 
81
  ReservedScoreboard.reset();
 
82
}
 
83
 
 
84
void 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
 
 
100
bool ScoreboardHazardRecognizer::atIssueLimit() const {
 
101
  if (IssueWidth == 0)
 
102
    return false;
 
103
 
 
104
  return IssueCount == IssueWidth;
 
105
}
 
106
 
 
107
ScheduleHazardRecognizer::HazardType
 
108
ScoreboardHazardRecognizer::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
      case InstrStage::Required:
 
144
        // Required FUs conflict with both reserved and required ones
 
145
        freeUnits &= ~ReservedScoreboard[StageCycle];
 
146
        // FALLTHROUGH
 
147
      case InstrStage::Reserved:
 
148
        // Reserved FUs can conflict only with required ones.
 
149
        freeUnits &= ~RequiredScoreboard[StageCycle];
 
150
        break;
 
151
      }
 
152
 
 
153
      if (!freeUnits) {
 
154
        DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", ");
 
155
        DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
 
156
        DEBUG(DAG->dumpNode(SU));
 
157
        return Hazard;
 
158
      }
 
159
    }
 
160
 
 
161
    // Advance the cycle to the next stage.
 
162
    cycle += IS->getNextCycles();
 
163
  }
 
164
 
 
165
  return NoHazard;
 
166
}
 
167
 
 
168
void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
 
169
  if (!ItinData || ItinData->isEmpty())
 
170
    return;
 
171
 
 
172
  // Use the itinerary for the underlying instruction to reserve FU's
 
173
  // in the scoreboard at the appropriate future cycles.
 
174
  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
 
175
  assert(MCID && "The scheduler must filter non-machineinstrs");
 
176
  if (DAG->TII->isZeroCost(MCID->Opcode))
 
177
    return;
 
178
 
 
179
  ++IssueCount;
 
180
 
 
181
  unsigned cycle = 0;
 
182
 
 
183
  unsigned idx = MCID->getSchedClass();
 
184
  for (const InstrStage *IS = ItinData->beginStage(idx),
 
185
         *E = ItinData->endStage(idx); IS != E; ++IS) {
 
186
    // We must reserve one of the stage's units for every cycle the
 
187
    // stage is occupied. FIXME it would be more accurate to reserve
 
188
    // the same unit free in all the cycles.
 
189
    for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 
190
      assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
 
191
             "Scoreboard depth exceeded!");
 
192
 
 
193
      unsigned freeUnits = IS->getUnits();
 
194
      switch (IS->getReservationKind()) {
 
195
      case InstrStage::Required:
 
196
        // Required FUs conflict with both reserved and required ones
 
197
        freeUnits &= ~ReservedScoreboard[cycle + i];
 
198
        // FALLTHROUGH
 
199
      case InstrStage::Reserved:
 
200
        // Reserved FUs can conflict only with required ones.
 
201
        freeUnits &= ~RequiredScoreboard[cycle + i];
 
202
        break;
 
203
      }
 
204
 
 
205
      // reduce to a single unit
 
206
      unsigned freeUnit = 0;
 
207
      do {
 
208
        freeUnit = freeUnits;
 
209
        freeUnits = freeUnit & (freeUnit - 1);
 
210
      } while (freeUnits);
 
211
 
 
212
      if (IS->getReservationKind() == InstrStage::Required)
 
213
        RequiredScoreboard[cycle + i] |= freeUnit;
 
214
      else
 
215
        ReservedScoreboard[cycle + i] |= freeUnit;
 
216
    }
 
217
 
 
218
    // Advance the cycle to the next stage.
 
219
    cycle += IS->getNextCycles();
 
220
  }
 
221
 
 
222
  DEBUG(ReservedScoreboard.dump());
 
223
  DEBUG(RequiredScoreboard.dump());
 
224
}
 
225
 
 
226
void ScoreboardHazardRecognizer::AdvanceCycle() {
 
227
  IssueCount = 0;
 
228
  ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
 
229
  RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
 
230
}
 
231
 
 
232
void ScoreboardHazardRecognizer::RecedeCycle() {
 
233
  IssueCount = 0;
 
234
  ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
 
235
  ReservedScoreboard.recede();
 
236
  RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
 
237
  RequiredScoreboard.recede();
 
238
}