Line data Source code
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/CodeGen/TargetInstrInfo.h"
19 : #include "llvm/Config/llvm-config.h"
20 : #include "llvm/MC/MCInstrDesc.h"
21 : #include "llvm/MC/MCInstrItineraries.h"
22 : #include "llvm/Support/Compiler.h"
23 : #include "llvm/Support/Debug.h"
24 : #include "llvm/Support/raw_ostream.h"
25 : #include <cassert>
26 :
27 : using namespace llvm;
28 :
29 : #define DEBUG_TYPE DebugType
30 :
31 369959 : ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(
32 : const InstrItineraryData *II, const ScheduleDAG *SchedDAG,
33 369959 : const char *ParentDebugType)
34 : : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II),
35 739918 : DAG(SchedDAG) {
36 : (void)DebugType;
37 : // Determine the maximum depth of any itinerary. This determines the depth of
38 : // the scoreboard. We always make the scoreboard at least 1 cycle deep to
39 : // avoid dealing with the boundary condition.
40 : unsigned ScoreboardDepth = 1;
41 369959 : if (ItinData && !ItinData->isEmpty()) {
42 31891346 : for (unsigned idx = 0; ; ++idx) {
43 : if (ItinData->isEndMarker(idx))
44 : break;
45 :
46 31891346 : const InstrStage *IS = ItinData->beginStage(idx);
47 : const InstrStage *E = ItinData->endStage(idx);
48 : unsigned CurCycle = 0;
49 : unsigned ItinDepth = 0;
50 87303524 : for (; IS != E; ++IS) {
51 55412178 : unsigned StageDepth = CurCycle + IS->getCycles();
52 55412178 : if (ItinDepth < StageDepth) ItinDepth = StageDepth;
53 82517585 : CurCycle += IS->getNextCycles();
54 : }
55 :
56 : // Find the next power-of-2 >= ItinDepth
57 32141288 : while (ItinDepth > ScoreboardDepth) {
58 249942 : ScoreboardDepth *= 2;
59 : // Don't set MaxLookAhead until we find at least one nonzero stage.
60 : // This way, an itinerary with no stages has MaxLookAhead==0, which
61 : // completely bypasses the scoreboard hazard logic.
62 249942 : MaxLookAhead = ScoreboardDepth;
63 : }
64 31891346 : }
65 : }
66 :
67 369959 : ReservedScoreboard.reset(ScoreboardDepth);
68 369959 : RequiredScoreboard.reset(ScoreboardDepth);
69 :
70 : // If MaxLookAhead is not set above, then we are not enabled.
71 369959 : if (!isEnabled())
72 : LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
73 : else {
74 : // A nonempty itinerary must have a SchedModel.
75 46838 : IssueWidth = ItinData->SchedModel.IssueWidth;
76 : LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
77 : << ScoreboardDepth << '\n');
78 : }
79 369959 : }
80 :
81 498080 : void ScoreboardHazardRecognizer::Reset() {
82 498080 : IssueCount = 0;
83 498080 : RequiredScoreboard.reset();
84 498080 : ReservedScoreboard.reset();
85 498080 : }
86 :
87 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
88 : LLVM_DUMP_METHOD void ScoreboardHazardRecognizer::Scoreboard::dump() const {
89 : dbgs() << "Scoreboard:\n";
90 :
91 : unsigned last = Depth - 1;
92 : while ((last > 0) && ((*this)[last] == 0))
93 : last--;
94 :
95 : for (unsigned i = 0; i <= last; i++) {
96 : unsigned FUs = (*this)[i];
97 : dbgs() << "\t";
98 : for (int j = 31; j >= 0; j--)
99 : dbgs() << ((FUs & (1 << j)) ? '1' : '0');
100 : dbgs() << '\n';
101 : }
102 : }
103 : #endif
104 :
105 744577 : bool ScoreboardHazardRecognizer::atIssueLimit() const {
106 744577 : if (IssueWidth == 0)
107 : return false;
108 :
109 143240 : return IssueCount == IssueWidth;
110 : }
111 :
112 : ScheduleHazardRecognizer::HazardType
113 1165282 : ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
114 1165282 : if (!ItinData || ItinData->isEmpty())
115 : return NoHazard;
116 :
117 : // Note that stalls will be negative for bottom-up scheduling.
118 : int cycle = Stalls;
119 :
120 : // Use the itinerary for the underlying instruction to check for
121 : // free FU's in the scoreboard at the appropriate future cycles.
122 :
123 552697 : const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
124 552697 : if (!MCID) {
125 : // Don't check hazards for non-machineinstr Nodes.
126 : return NoHazard;
127 : }
128 433087 : unsigned idx = MCID->getSchedClass();
129 433087 : for (const InstrStage *IS = ItinData->beginStage(idx),
130 1032525 : *E = ItinData->endStage(idx); IS != E; ++IS) {
131 : // We must find one of the stage's units free for every cycle the
132 : // stage is occupied. FIXME it would be more accurate to find the
133 : // same unit free in all the cycles.
134 1480544 : for (unsigned int i = 0; i < IS->getCycles(); ++i) {
135 881106 : int StageCycle = cycle + (int)i;
136 881106 : if (StageCycle < 0)
137 : continue;
138 :
139 807086 : if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
140 : assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
141 : "Scoreboard depth exceeded!");
142 : // This stage was stalled beyond pipeline depth, so cannot conflict.
143 : break;
144 : }
145 :
146 807086 : unsigned freeUnits = IS->getUnits();
147 807086 : switch (IS->getReservationKind()) {
148 797059 : case InstrStage::Required:
149 : // Required FUs conflict with both reserved and required ones
150 1594118 : freeUnits &= ~ReservedScoreboard[StageCycle];
151 : LLVM_FALLTHROUGH;
152 807086 : case InstrStage::Reserved:
153 : // Reserved FUs can conflict only with required ones.
154 807086 : freeUnits &= ~RequiredScoreboard[StageCycle];
155 807086 : break;
156 : }
157 :
158 807086 : if (!freeUnits) {
159 : LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
160 : LLVM_DEBUG(DAG->dumpNode(*SU));
161 : return Hazard;
162 : }
163 : }
164 :
165 : // Advance the cycle to the next stage.
166 927534 : cycle += IS->getNextCycles();
167 : }
168 :
169 : return NoHazard;
170 : }
171 :
172 811396 : void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
173 811396 : if (!ItinData || ItinData->isEmpty())
174 : return;
175 :
176 : // Use the itinerary for the underlying instruction to reserve FU's
177 : // in the scoreboard at the appropriate future cycles.
178 210059 : const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
179 : assert(MCID && "The scheduler must filter non-machineinstrs");
180 210059 : if (DAG->TII->isZeroCost(MCID->Opcode))
181 : return;
182 :
183 183879 : ++IssueCount;
184 :
185 : unsigned cycle = 0;
186 :
187 183879 : unsigned idx = MCID->getSchedClass();
188 183879 : for (const InstrStage *IS = ItinData->beginStage(idx),
189 479963 : *E = ItinData->endStage(idx); IS != E; ++IS) {
190 : // We must reserve one of the stage's units for every cycle the
191 : // stage is occupied. FIXME it would be more accurate to reserve
192 : // the same unit free in all the cycles.
193 686385 : for (unsigned int i = 0; i < IS->getCycles(); ++i) {
194 : assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
195 : "Scoreboard depth exceeded!");
196 :
197 390301 : unsigned freeUnits = IS->getUnits();
198 390301 : switch (IS->getReservationKind()) {
199 384947 : case InstrStage::Required:
200 : // Required FUs conflict with both reserved and required ones
201 769894 : freeUnits &= ~ReservedScoreboard[cycle + i];
202 : LLVM_FALLTHROUGH;
203 390301 : case InstrStage::Reserved:
204 : // Reserved FUs can conflict only with required ones.
205 390301 : freeUnits &= ~RequiredScoreboard[cycle + i];
206 390301 : break;
207 : }
208 :
209 : // reduce to a single unit
210 : unsigned freeUnit = 0;
211 : do {
212 : freeUnit = freeUnits;
213 723822 : freeUnits = freeUnit & (freeUnit - 1);
214 723822 : } while (freeUnits);
215 :
216 390301 : if (IS->getReservationKind() == InstrStage::Required)
217 769894 : RequiredScoreboard[cycle + i] |= freeUnit;
218 : else
219 10708 : ReservedScoreboard[cycle + i] |= freeUnit;
220 : }
221 :
222 : // Advance the cycle to the next stage.
223 423797 : cycle += IS->getNextCycles();
224 : }
225 :
226 : LLVM_DEBUG(ReservedScoreboard.dump());
227 : LLVM_DEBUG(RequiredScoreboard.dump());
228 : }
229 :
230 646651 : void ScoreboardHazardRecognizer::AdvanceCycle() {
231 646651 : IssueCount = 0;
232 646651 : ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
233 646651 : RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
234 646651 : }
235 :
236 171853 : void ScoreboardHazardRecognizer::RecedeCycle() {
237 171853 : IssueCount = 0;
238 343706 : ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
239 : ReservedScoreboard.recede();
240 343706 : RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
241 : RequiredScoreboard.recede();
242 171853 : }
|
