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