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 default: 144 assert(0 && "Invalid FU reservation"); 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 " << (cycle + i) << ", "); 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 170void 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 default: 198 assert(0 && "Invalid FU reservation"); 199 case InstrStage::Required: 200 // Required FUs conflict with both reserved and required ones 201 freeUnits &= ~ReservedScoreboard[cycle + i]; 202 // FALLTHROUGH 203 case InstrStage::Reserved: 204 // Reserved FUs can conflict only with required ones. 205 freeUnits &= ~RequiredScoreboard[cycle + i]; 206 break; 207 } 208 209 // reduce to a single unit 210 unsigned freeUnit = 0; 211 do { 212 freeUnit = freeUnits; 213 freeUnits = freeUnit & (freeUnit - 1); 214 } while (freeUnits); 215 216 if (IS->getReservationKind() == InstrStage::Required) 217 RequiredScoreboard[cycle + i] |= freeUnit; 218 else 219 ReservedScoreboard[cycle + i] |= freeUnit; 220 } 221 222 // Advance the cycle to the next stage. 223 cycle += IS->getNextCycles(); 224 } 225 226 DEBUG(ReservedScoreboard.dump()); 227 DEBUG(RequiredScoreboard.dump()); 228} 229 230void ScoreboardHazardRecognizer::AdvanceCycle() { 231 IssueCount = 0; 232 ReservedScoreboard[0] = 0; ReservedScoreboard.advance(); 233 RequiredScoreboard[0] = 0; RequiredScoreboard.advance(); 234} 235 236void ScoreboardHazardRecognizer::RecedeCycle() { 237 IssueCount = 0; 238 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0; 239 ReservedScoreboard.recede(); 240 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0; 241 RequiredScoreboard.recede(); 242} 243