ScoreboardHazardRecognizer.cpp revision fc992996f751e0941951b6d08d8f1e80ebec1385
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#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" 24 25using namespace llvm; 26 27#ifndef NDEBUG 28const char *ScoreboardHazardRecognizer::DebugType = ""; 29#endif 30 31ScoreboardHazardRecognizer:: 32ScoreboardHazardRecognizer(const InstrItineraryData *II, 33 const ScheduleDAG *SchedDAG, 34 const char *ParentDebugType) : 35 ScheduleHazardRecognizer(), ItinData(II), DAG(SchedDAG), IssueWidth(0), 36 IssueCount(0) { 37 38#ifndef NDEBUG 39 DebugType = ParentDebugType; 40#endif 41 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)) 49 break; 50 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(); 59 } 60 61 // Find the next power-of-2 >= ItinDepth 62 while (ItinDepth > ScoreboardDepth) { 63 ScoreboardDepth *= 2; 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; 68 } 69 } 70 } 71 72 ReservedScoreboard.reset(ScoreboardDepth); 73 RequiredScoreboard.reset(ScoreboardDepth); 74 75 if (!isEnabled()) 76 DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n"); 77 else { 78 IssueWidth = ItinData->Props.IssueWidth; 79 DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = " 80 << ScoreboardDepth << '\n'); 81 } 82} 83 84void ScoreboardHazardRecognizer::Reset() { 85 IssueCount = 0; 86 RequiredScoreboard.reset(); 87 ReservedScoreboard.reset(); 88} 89 90void ScoreboardHazardRecognizer::Scoreboard::dump() const { 91 dbgs() << "Scoreboard:\n"; 92 93 unsigned last = Depth - 1; 94 while ((last > 0) && ((*this)[last] == 0)) 95 last--; 96 97 for (unsigned i = 0; i <= last; i++) { 98 unsigned FUs = (*this)[i]; 99 dbgs() << "\t"; 100 for (int j = 31; j >= 0; j--) 101 dbgs() << ((FUs & (1 << j)) ? '1' : '0'); 102 dbgs() << '\n'; 103 } 104} 105 106bool ScoreboardHazardRecognizer::atIssueLimit() const { 107 if (IssueWidth == 0) 108 return false; 109 110 return IssueCount == IssueWidth; 111} 112 113ScheduleHazardRecognizer::HazardType 114ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) { 115 if (!ItinData || ItinData->isEmpty()) 116 return NoHazard; 117 118 // Note that stalls will be negative for bottom-up scheduling. 119 int cycle = Stalls; 120 121 // Use the itinerary for the underlying instruction to check for 122 // free FU's in the scoreboard at the appropriate future cycles. 123 124 const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 125 if (MCID == NULL) { 126 // Don't check hazards for non-machineinstr Nodes. 127 return NoHazard; 128 } 129 unsigned idx = MCID->getSchedClass(); 130 for (const InstrStage *IS = ItinData->beginStage(idx), 131 *E = ItinData->endStage(idx); IS != E; ++IS) { 132 // We must find one of the stage's units free for every cycle the 133 // stage is occupied. FIXME it would be more accurate to find the 134 // same unit free in all the cycles. 135 for (unsigned int i = 0; i < IS->getCycles(); ++i) { 136 int StageCycle = cycle + (int)i; 137 if (StageCycle < 0) 138 continue; 139 140 if (StageCycle >= (int)RequiredScoreboard.getDepth()) { 141 assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() && 142 "Scoreboard depth exceeded!"); 143 // This stage was stalled beyond pipeline depth, so cannot conflict. 144 break; 145 } 146 147 unsigned freeUnits = IS->getUnits(); 148 switch (IS->getReservationKind()) { 149 case InstrStage::Required: 150 // Required FUs conflict with both reserved and required ones 151 freeUnits &= ~ReservedScoreboard[StageCycle]; 152 // FALLTHROUGH 153 case InstrStage::Reserved: 154 // Reserved FUs can conflict only with required ones. 155 freeUnits &= ~RequiredScoreboard[StageCycle]; 156 break; 157 } 158 159 if (!freeUnits) { 160 DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", "); 161 DEBUG(dbgs() << "SU(" << SU->NodeNum << "): "); 162 DEBUG(DAG->dumpNode(SU)); 163 return Hazard; 164 } 165 } 166 167 // Advance the cycle to the next stage. 168 cycle += IS->getNextCycles(); 169 } 170 171 return NoHazard; 172} 173 174void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) { 175 if (!ItinData || ItinData->isEmpty()) 176 return; 177 178 // Use the itinerary for the underlying instruction to reserve FU's 179 // in the scoreboard at the appropriate future cycles. 180 const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 181 assert(MCID && "The scheduler must filter non-machineinstrs"); 182 if (DAG->TII->isZeroCost(MCID->Opcode)) 183 return; 184 185 ++IssueCount; 186 187 unsigned cycle = 0; 188 189 unsigned idx = MCID->getSchedClass(); 190 for (const InstrStage *IS = ItinData->beginStage(idx), 191 *E = ItinData->endStage(idx); IS != E; ++IS) { 192 // We must reserve one of the stage's units for every cycle the 193 // stage is occupied. FIXME it would be more accurate to reserve 194 // the same unit free in all the cycles. 195 for (unsigned int i = 0; i < IS->getCycles(); ++i) { 196 assert(((cycle + i) < RequiredScoreboard.getDepth()) && 197 "Scoreboard depth exceeded!"); 198 199 unsigned freeUnits = IS->getUnits(); 200 switch (IS->getReservationKind()) { 201 case InstrStage::Required: 202 // Required FUs conflict with both reserved and required ones 203 freeUnits &= ~ReservedScoreboard[cycle + i]; 204 // FALLTHROUGH 205 case InstrStage::Reserved: 206 // Reserved FUs can conflict only with required ones. 207 freeUnits &= ~RequiredScoreboard[cycle + i]; 208 break; 209 } 210 211 // reduce to a single unit 212 unsigned freeUnit = 0; 213 do { 214 freeUnit = freeUnits; 215 freeUnits = freeUnit & (freeUnit - 1); 216 } while (freeUnits); 217 218 if (IS->getReservationKind() == InstrStage::Required) 219 RequiredScoreboard[cycle + i] |= freeUnit; 220 else 221 ReservedScoreboard[cycle + i] |= freeUnit; 222 } 223 224 // Advance the cycle to the next stage. 225 cycle += IS->getNextCycles(); 226 } 227 228 DEBUG(ReservedScoreboard.dump()); 229 DEBUG(RequiredScoreboard.dump()); 230} 231 232void ScoreboardHazardRecognizer::AdvanceCycle() { 233 IssueCount = 0; 234 ReservedScoreboard[0] = 0; ReservedScoreboard.advance(); 235 RequiredScoreboard[0] = 0; RequiredScoreboard.advance(); 236} 237 238void ScoreboardHazardRecognizer::RecedeCycle() { 239 IssueCount = 0; 240 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0; 241 ReservedScoreboard.recede(); 242 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0; 243 RequiredScoreboard.recede(); 244} 245