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/Support/Debug.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include "llvm/Target/TargetInstrItineraries.h"
27 const char *ScoreboardHazardRecognizer::DebugType = "";
30 ScoreboardHazardRecognizer::
31 ScoreboardHazardRecognizer(const InstrItineraryData *II,
32 const ScheduleDAG *SchedDAG,
33 const char *ParentDebugType) :
34 ScheduleHazardRecognizer(), ItinData(II), DAG(SchedDAG), IssueWidth(0),
38 DebugType = ParentDebugType;
41 // Determine the maximum depth of any itinerary. This determines the
42 // depth of the scoreboard. We always make the scoreboard at least 1
43 // cycle deep to avoid dealing with the boundary condition.
44 unsigned ScoreboardDepth = 1;
45 if (ItinData && !ItinData->isEmpty()) {
46 IssueWidth = ItinData->IssueWidth;
48 for (unsigned idx = 0; ; ++idx) {
49 if (ItinData->isEndMarker(idx))
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();
62 // Find the next power-of-2 >= ItinDepth
63 while (ItinDepth > ScoreboardDepth) {
67 MaxLookAhead = ScoreboardDepth;
70 ReservedScoreboard.reset(ScoreboardDepth);
71 RequiredScoreboard.reset(ScoreboardDepth);
73 DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
74 << ScoreboardDepth << '\n');
77 void ScoreboardHazardRecognizer::Reset() {
79 RequiredScoreboard.reset();
80 ReservedScoreboard.reset();
83 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
84 dbgs() << "Scoreboard:\n";
86 unsigned last = Depth - 1;
87 while ((last > 0) && ((*this)[last] == 0))
90 for (unsigned i = 0; i <= last; i++) {
91 unsigned FUs = (*this)[i];
93 for (int j = 31; j >= 0; j--)
94 dbgs() << ((FUs & (1 << j)) ? '1' : '0');
99 bool ScoreboardHazardRecognizer::atIssueLimit() const {
103 return IssueCount == IssueWidth;
106 ScheduleHazardRecognizer::HazardType
107 ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
108 if (!ItinData || ItinData->isEmpty())
111 // Note that stalls will be negative for bottom-up scheduling.
114 // Use the itinerary for the underlying instruction to check for
115 // free FU's in the scoreboard at the appropriate future cycles.
117 const TargetInstrDesc *TID = DAG->getInstrDesc(SU);
119 // Don't check hazards for non-machineinstr Nodes.
122 unsigned idx = TID->getSchedClass();
123 for (const InstrStage *IS = ItinData->beginStage(idx),
124 *E = ItinData->endStage(idx); IS != E; ++IS) {
125 // We must find one of the stage's units free for every cycle the
126 // stage is occupied. FIXME it would be more accurate to find the
127 // same unit free in all the cycles.
128 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
129 int StageCycle = cycle + (int)i;
133 if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
134 assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
135 "Scoreboard depth exceeded!");
136 // This stage was stalled beyond pipeline depth, so cannot conflict.
140 unsigned freeUnits = IS->getUnits();
141 switch (IS->getReservationKind()) {
143 assert(0 && "Invalid FU reservation");
144 case InstrStage::Required:
145 // Required FUs conflict with both reserved and required ones
146 freeUnits &= ~ReservedScoreboard[StageCycle];
148 case InstrStage::Reserved:
149 // Reserved FUs can conflict only with required ones.
150 freeUnits &= ~RequiredScoreboard[StageCycle];
155 DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", ");
156 DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
157 DEBUG(DAG->dumpNode(SU));
162 // Advance the cycle to the next stage.
163 cycle += IS->getNextCycles();
169 void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
170 if (!ItinData || ItinData->isEmpty())
177 // Use the itinerary for the underlying instruction to reserve FU's
178 // in the scoreboard at the appropriate future cycles.
179 const TargetInstrDesc *TID = DAG->getInstrDesc(SU);
180 assert(TID && "The scheduler must filter non-machineinstrs");
181 unsigned idx = TID->getSchedClass();
182 for (const InstrStage *IS = ItinData->beginStage(idx),
183 *E = ItinData->endStage(idx); IS != E; ++IS) {
184 // We must reserve one of the stage's units for every cycle the
185 // stage is occupied. FIXME it would be more accurate to reserve
186 // the same unit free in all the cycles.
187 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
188 assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
189 "Scoreboard depth exceeded!");
191 unsigned freeUnits = IS->getUnits();
192 switch (IS->getReservationKind()) {
194 assert(0 && "Invalid FU reservation");
195 case InstrStage::Required:
196 // Required FUs conflict with both reserved and required ones
197 freeUnits &= ~ReservedScoreboard[cycle + i];
199 case InstrStage::Reserved:
200 // Reserved FUs can conflict only with required ones.
201 freeUnits &= ~RequiredScoreboard[cycle + i];
205 // reduce to a single unit
206 unsigned freeUnit = 0;
208 freeUnit = freeUnits;
209 freeUnits = freeUnit & (freeUnit - 1);
212 assert(freeUnit && "No function unit available!");
213 if (IS->getReservationKind() == InstrStage::Required)
214 RequiredScoreboard[cycle + i] |= freeUnit;
216 ReservedScoreboard[cycle + i] |= freeUnit;
219 // Advance the cycle to the next stage.
220 cycle += IS->getNextCycles();
223 DEBUG(ReservedScoreboard.dump());
224 DEBUG(RequiredScoreboard.dump());
227 void ScoreboardHazardRecognizer::AdvanceCycle() {
229 ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
230 RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
233 void ScoreboardHazardRecognizer::RecedeCycle() {
235 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
236 ReservedScoreboard.recede();
237 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
238 RequiredScoreboard.recede();