1 //===----- PostRAHazardRecognizer.cpp - hazard recognizer -------- ---------===// 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 implements a hazard recognizer using the instructions itineraries 11 // defined for the current target. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "post-RA-sched" 16 #include "llvm/CodeGen/PostRAHazardRecognizer.h" 17 #include "llvm/CodeGen/ScheduleDAG.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Support/ErrorHandling.h" 20 #include "llvm/Support/raw_ostream.h" 21 #include "llvm/Target/TargetInstrItineraries.h" 22 23 using namespace llvm; 24 25 PostRAHazardRecognizer:: 26 PostRAHazardRecognizer(const InstrItineraryData &LItinData) : 27 ScheduleHazardRecognizer(), ItinData(LItinData) { 28 // Determine the maximum depth of any itinerary. This determines the 29 // depth of the scoreboard. We always make the scoreboard at least 1 30 // cycle deep to avoid dealing with the boundary condition. 31 unsigned ScoreboardDepth = 1; 32 if (!ItinData.isEmpty()) { 33 for (unsigned idx = 0; ; ++idx) { 34 if (ItinData.isEndMarker(idx)) 35 break; 36 37 const InstrStage *IS = ItinData.beginStage(idx); 38 const InstrStage *E = ItinData.endStage(idx); 39 unsigned ItinDepth = 0; 40 for (; IS != E; ++IS) 41 ItinDepth += IS->getCycles(); 42 43 ScoreboardDepth = std::max(ScoreboardDepth, ItinDepth); 44 } 45 } 46 47 ReservedScoreboard.reset(ScoreboardDepth); 48 RequiredScoreboard.reset(ScoreboardDepth); 49 50 DEBUG(dbgs() << "Using post-ra hazard recognizer: ScoreboardDepth = " 51 << ScoreboardDepth << '\n'); 52 } 53 54 void PostRAHazardRecognizer::Reset() { 55 RequiredScoreboard.reset(); 56 ReservedScoreboard.reset(); 57 } 58 59 void PostRAHazardRecognizer::ScoreBoard::dump() const { 60 dbgs() << "Scoreboard:\n"; 61 62 unsigned last = Depth - 1; 63 while ((last > 0) && ((*this)[last] == 0)) 64 last--; 65 66 for (unsigned i = 0; i <= last; i++) { 67 unsigned FUs = (*this)[i]; 68 dbgs() << "\t"; 69 for (int j = 31; j >= 0; j--) 70 dbgs() << ((FUs & (1 << j)) ? '1' : '0'); 71 dbgs() << '\n'; 72 } 73 } 74 75 ScheduleHazardRecognizer::HazardType 76 PostRAHazardRecognizer::getHazardType(SUnit *SU) { 77 if (ItinData.isEmpty()) 78 return NoHazard; 79 80 unsigned cycle = 0; 81 82 // Use the itinerary for the underlying instruction to check for 83 // free FU's in the scoreboard at the appropriate future cycles. 84 unsigned idx = SU->getInstr()->getDesc().getSchedClass(); 85 for (const InstrStage *IS = ItinData.beginStage(idx), 86 *E = ItinData.endStage(idx); IS != E; ++IS) { 87 // We must find one of the stage's units free for every cycle the 88 // stage is occupied. FIXME it would be more accurate to find the 89 // same unit free in all the cycles. 90 for (unsigned int i = 0; i < IS->getCycles(); ++i) { 91 assert(((cycle + i) < RequiredScoreboard.getDepth()) && 92 "Scoreboard depth exceeded!"); 93 94 unsigned freeUnits = IS->getUnits(); 95 switch (IS->getReservationKind()) { 96 default: 97 assert(0 && "Invalid FU reservation"); 98 case InstrStage::Required: 99 // Required FUs conflict with both reserved and required ones 100 freeUnits &= ~ReservedScoreboard[cycle + i]; 101 // FALLTHROUGH 102 case InstrStage::Reserved: 103 // Reserved FUs can conflict only with required ones. 104 freeUnits &= ~RequiredScoreboard[cycle + i]; 105 break; 106 } 107 108 if (!freeUnits) { 109 DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", "); 110 DEBUG(dbgs() << "SU(" << SU->NodeNum << "): "); 111 DEBUG(SU->getInstr()->dump()); 112 return Hazard; 113 } 114 } 115 116 // Advance the cycle to the next stage. 117 cycle += IS->getNextCycles(); 118 } 119 120 return NoHazard; 121 } 122 123 void PostRAHazardRecognizer::EmitInstruction(SUnit *SU) { 124 if (ItinData.isEmpty()) 125 return; 126 127 unsigned cycle = 0; 128 129 // Use the itinerary for the underlying instruction to reserve FU's 130 // in the scoreboard at the appropriate future cycles. 131 unsigned idx = SU->getInstr()->getDesc().getSchedClass(); 132 for (const InstrStage *IS = ItinData.beginStage(idx), 133 *E = ItinData.endStage(idx); IS != E; ++IS) { 134 // We must reserve one of the stage's units for every cycle the 135 // stage is occupied. FIXME it would be more accurate to reserve 136 // the same unit free in all the cycles. 137 for (unsigned int i = 0; i < IS->getCycles(); ++i) { 138 assert(((cycle + i) < RequiredScoreboard.getDepth()) && 139 "Scoreboard depth exceeded!"); 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[cycle + i]; 148 // FALLTHROUGH 149 case InstrStage::Reserved: 150 // Reserved FUs can conflict only with required ones. 151 freeUnits &= ~RequiredScoreboard[cycle + i]; 152 break; 153 } 154 155 // reduce to a single unit 156 unsigned freeUnit = 0; 157 do { 158 freeUnit = freeUnits; 159 freeUnits = freeUnit & (freeUnit - 1); 160 } while (freeUnits); 161 162 assert(freeUnit && "No function unit available!"); 163 if (IS->getReservationKind() == InstrStage::Required) 164 RequiredScoreboard[cycle + i] |= freeUnit; 165 else 166 ReservedScoreboard[cycle + i] |= freeUnit; 167 } 168 169 // Advance the cycle to the next stage. 170 cycle += IS->getNextCycles(); 171 } 172 173 DEBUG(ReservedScoreboard.dump()); 174 DEBUG(RequiredScoreboard.dump()); 175 } 176 177 void PostRAHazardRecognizer::AdvanceCycle() { 178 ReservedScoreboard[0] = 0; ReservedScoreboard.advance(); 179 RequiredScoreboard[0] = 0; RequiredScoreboard.advance(); 180 } 181