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