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 "sched-hazard"
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"
26 ScoreboardHazardRecognizer::
27 ScoreboardHazardRecognizer(const InstrItineraryData *LItinData) :
28 ScheduleHazardRecognizer(), ItinData(LItinData) {
29 // Determine the maximum depth of any itinerary. This determines the
30 // depth of the scoreboard. We always make the scoreboard at least 1
31 // cycle deep to avoid dealing with the boundary condition.
32 unsigned ScoreboardDepth = 1;
33 if (ItinData && !ItinData->isEmpty()) {
34 for (unsigned idx = 0; ; ++idx) {
35 if (ItinData->isEndMarker(idx))
38 const InstrStage *IS = ItinData->beginStage(idx);
39 const InstrStage *E = ItinData->endStage(idx);
40 unsigned ItinDepth = 0;
42 ItinDepth += IS->getCycles();
44 // Find the next power-of-2 >= ItinDepth
45 while (ItinDepth > ScoreboardDepth) {
51 ReservedScoreboard.reset(ScoreboardDepth);
52 RequiredScoreboard.reset(ScoreboardDepth);
54 DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
55 << ScoreboardDepth << '\n');
58 void ScoreboardHazardRecognizer::Reset() {
59 RequiredScoreboard.reset();
60 ReservedScoreboard.reset();
63 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
64 dbgs() << "Scoreboard:\n";
66 unsigned last = Depth - 1;
67 while ((last > 0) && ((*this)[last] == 0))
70 for (unsigned i = 0; i <= last; i++) {
71 unsigned FUs = (*this)[i];
73 for (int j = 31; j >= 0; j--)
74 dbgs() << ((FUs & (1 << j)) ? '1' : '0');
79 ScheduleHazardRecognizer::HazardType
80 ScoreboardHazardRecognizer::getHazardType(SUnit *SU) {
81 if (!ItinData || ItinData->isEmpty())
86 // Use the itinerary for the underlying instruction to check for
87 // free FU's in the scoreboard at the appropriate future cycles.
88 unsigned idx = SU->getInstr()->getDesc().getSchedClass();
89 for (const InstrStage *IS = ItinData->beginStage(idx),
90 *E = ItinData->endStage(idx); IS != E; ++IS) {
91 // We must find one of the stage's units free for every cycle the
92 // stage is occupied. FIXME it would be more accurate to find the
93 // same unit free in all the cycles.
94 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
95 assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
96 "Scoreboard depth exceeded!");
98 unsigned freeUnits = IS->getUnits();
99 switch (IS->getReservationKind()) {
101 assert(0 && "Invalid FU reservation");
102 case InstrStage::Required:
103 // Required FUs conflict with both reserved and required ones
104 freeUnits &= ~ReservedScoreboard[cycle + i];
106 case InstrStage::Reserved:
107 // Reserved FUs can conflict only with required ones.
108 freeUnits &= ~RequiredScoreboard[cycle + i];
113 DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", ");
114 DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
115 DEBUG(SU->getInstr()->dump());
120 // Advance the cycle to the next stage.
121 cycle += IS->getNextCycles();
127 void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
128 if (!ItinData || ItinData->isEmpty())
133 // Use the itinerary for the underlying instruction to reserve FU's
134 // in the scoreboard at the appropriate future cycles.
135 unsigned idx = SU->getInstr()->getDesc().getSchedClass();
136 for (const InstrStage *IS = ItinData->beginStage(idx),
137 *E = ItinData->endStage(idx); IS != E; ++IS) {
138 // We must reserve one of the stage's units for every cycle the
139 // stage is occupied. FIXME it would be more accurate to reserve
140 // the same unit free in all the cycles.
141 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
142 assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
143 "Scoreboard depth exceeded!");
145 unsigned freeUnits = IS->getUnits();
146 switch (IS->getReservationKind()) {
148 assert(0 && "Invalid FU reservation");
149 case InstrStage::Required:
150 // Required FUs conflict with both reserved and required ones
151 freeUnits &= ~ReservedScoreboard[cycle + i];
153 case InstrStage::Reserved:
154 // Reserved FUs can conflict only with required ones.
155 freeUnits &= ~RequiredScoreboard[cycle + i];
159 // reduce to a single unit
160 unsigned freeUnit = 0;
162 freeUnit = freeUnits;
163 freeUnits = freeUnit & (freeUnit - 1);
166 assert(freeUnit && "No function unit available!");
167 if (IS->getReservationKind() == InstrStage::Required)
168 RequiredScoreboard[cycle + i] |= freeUnit;
170 ReservedScoreboard[cycle + i] |= freeUnit;
173 // Advance the cycle to the next stage.
174 cycle += IS->getNextCycles();
177 DEBUG(ReservedScoreboard.dump());
178 DEBUG(RequiredScoreboard.dump());
181 void ScoreboardHazardRecognizer::AdvanceCycle() {
182 ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
183 RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
186 void ScoreboardHazardRecognizer::RecedeCycle() {
187 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
188 ReservedScoreboard.recede();
189 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
190 RequiredScoreboard.recede();