1 //===----- ScoreboardHazardRecognizer.cpp - Scheduler Support -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
28 const char *ScoreboardHazardRecognizer::DebugType = "";
31 ScoreboardHazardRecognizer::
32 ScoreboardHazardRecognizer(const InstrItineraryData *II,
33 const ScheduleDAG *SchedDAG,
34 const char *ParentDebugType) :
35 ScheduleHazardRecognizer(), ItinData(II), DAG(SchedDAG), IssueWidth(0),
39 DebugType = ParentDebugType;
42 // Determine the maximum depth of any itinerary. This determines the depth of
43 // the scoreboard. We always make the scoreboard at least 1 cycle deep to
44 // avoid dealing with the boundary condition.
45 unsigned ScoreboardDepth = 1;
46 if (ItinData && !ItinData->isEmpty()) {
47 for (unsigned idx = 0; ; ++idx) {
48 if (ItinData->isEndMarker(idx))
51 const InstrStage *IS = ItinData->beginStage(idx);
52 const InstrStage *E = ItinData->endStage(idx);
53 unsigned CurCycle = 0;
54 unsigned ItinDepth = 0;
55 for (; IS != E; ++IS) {
56 unsigned StageDepth = CurCycle + IS->getCycles();
57 if (ItinDepth < StageDepth) ItinDepth = StageDepth;
58 CurCycle += IS->getNextCycles();
61 // Find the next power-of-2 >= ItinDepth
62 while (ItinDepth > ScoreboardDepth) {
64 // Don't set MaxLookAhead until we find at least one nonzero stage.
65 // This way, an itinerary with no stages has MaxLookAhead==0, which
66 // completely bypasses the scoreboard hazard logic.
67 MaxLookAhead = ScoreboardDepth;
72 ReservedScoreboard.reset(ScoreboardDepth);
73 RequiredScoreboard.reset(ScoreboardDepth);
75 // If MaxLookAhead is not set above, then we are not enabled.
77 DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
79 // A nonempty itinerary must have a SchedModel.
80 IssueWidth = ItinData->SchedModel->IssueWidth;
81 DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
82 << ScoreboardDepth << '\n');
86 void ScoreboardHazardRecognizer::Reset() {
88 RequiredScoreboard.reset();
89 ReservedScoreboard.reset();
92 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
93 dbgs() << "Scoreboard:\n";
95 unsigned last = Depth - 1;
96 while ((last > 0) && ((*this)[last] == 0))
99 for (unsigned i = 0; i <= last; i++) {
100 unsigned FUs = (*this)[i];
102 for (int j = 31; j >= 0; j--)
103 dbgs() << ((FUs & (1 << j)) ? '1' : '0');
108 bool ScoreboardHazardRecognizer::atIssueLimit() const {
112 return IssueCount == IssueWidth;
115 ScheduleHazardRecognizer::HazardType
116 ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
117 if (!ItinData || ItinData->isEmpty())
120 // Note that stalls will be negative for bottom-up scheduling.
123 // Use the itinerary for the underlying instruction to check for
124 // free FU's in the scoreboard at the appropriate future cycles.
126 const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
128 // Don't check hazards for non-machineinstr Nodes.
131 unsigned idx = MCID->getSchedClass();
132 for (const InstrStage *IS = ItinData->beginStage(idx),
133 *E = ItinData->endStage(idx); IS != E; ++IS) {
134 // We must find one of the stage's units free for every cycle the
135 // stage is occupied. FIXME it would be more accurate to find the
136 // same unit free in all the cycles.
137 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
138 int StageCycle = cycle + (int)i;
142 if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
143 assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
144 "Scoreboard depth exceeded!");
145 // This stage was stalled beyond pipeline depth, so cannot conflict.
149 unsigned freeUnits = IS->getUnits();
150 switch (IS->getReservationKind()) {
151 case InstrStage::Required:
152 // Required FUs conflict with both reserved and required ones
153 freeUnits &= ~ReservedScoreboard[StageCycle];
155 case InstrStage::Reserved:
156 // Reserved FUs can conflict only with required ones.
157 freeUnits &= ~RequiredScoreboard[StageCycle];
162 DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
163 DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
164 DEBUG(DAG->dumpNode(SU));
169 // Advance the cycle to the next stage.
170 cycle += IS->getNextCycles();
176 void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
177 if (!ItinData || ItinData->isEmpty())
180 // Use the itinerary for the underlying instruction to reserve FU's
181 // in the scoreboard at the appropriate future cycles.
182 const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
183 assert(MCID && "The scheduler must filter non-machineinstrs");
184 if (DAG->TII->isZeroCost(MCID->Opcode))
191 unsigned idx = MCID->getSchedClass();
192 for (const InstrStage *IS = ItinData->beginStage(idx),
193 *E = ItinData->endStage(idx); IS != E; ++IS) {
194 // We must reserve one of the stage's units for every cycle the
195 // stage is occupied. FIXME it would be more accurate to reserve
196 // the same unit free in all the cycles.
197 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
198 assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
199 "Scoreboard depth exceeded!");
201 unsigned freeUnits = IS->getUnits();
202 switch (IS->getReservationKind()) {
203 case InstrStage::Required:
204 // Required FUs conflict with both reserved and required ones
205 freeUnits &= ~ReservedScoreboard[cycle + i];
207 case InstrStage::Reserved:
208 // Reserved FUs can conflict only with required ones.
209 freeUnits &= ~RequiredScoreboard[cycle + i];
213 // reduce to a single unit
214 unsigned freeUnit = 0;
216 freeUnit = freeUnits;
217 freeUnits = freeUnit & (freeUnit - 1);
220 if (IS->getReservationKind() == InstrStage::Required)
221 RequiredScoreboard[cycle + i] |= freeUnit;
223 ReservedScoreboard[cycle + i] |= freeUnit;
226 // Advance the cycle to the next stage.
227 cycle += IS->getNextCycles();
230 DEBUG(ReservedScoreboard.dump());
231 DEBUG(RequiredScoreboard.dump());
234 void ScoreboardHazardRecognizer::AdvanceCycle() {
236 ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
237 RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
240 void ScoreboardHazardRecognizer::RecedeCycle() {
242 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
243 ReservedScoreboard.recede();
244 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
245 RequiredScoreboard.recede();