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