]> git.proxmox.com Git - rustc.git/blame - src/llvm/lib/CodeGen/ScoreboardHazardRecognizer.cpp
Imported Upstream version 1.0.0+dfsg1
[rustc.git] / src / llvm / lib / CodeGen / ScoreboardHazardRecognizer.cpp
CommitLineData
223e47cc
LB
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
223e47cc
LB
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
1a4d82fc
JJ
26#define DEBUG_TYPE ::llvm::ScoreboardHazardRecognizer::DebugType
27
223e47cc
LB
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.
1a4d82fc 81 IssueWidth = ItinData->SchedModel.IssueWidth;
223e47cc
LB
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);
1a4d82fc 130 if (!MCID) {
223e47cc
LB
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}