LLVM API Documentation
00001 //===----- ExactHazardRecognizer.cpp - hazard recognizer -------- ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements a a hazard recognizer using the instructions itineraries 00011 // defined for the current target. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "exact-hazards" 00016 #include "ExactHazardRecognizer.h" 00017 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 00018 #include "llvm/Support/Debug.h" 00019 #include "llvm/Support/ErrorHandling.h" 00020 #include "llvm/Support/raw_ostream.h" 00021 #include "llvm/Target/TargetInstrItineraries.h" 00022 00023 namespace llvm { 00024 00025 ExactHazardRecognizer::ExactHazardRecognizer(const InstrItineraryData &LItinData) : 00026 ScheduleHazardRecognizer(), ItinData(LItinData) 00027 { 00028 // Determine the maximum depth of any itinerary. This determines the 00029 // depth of the scoreboard. We always make the scoreboard at least 1 00030 // cycle deep to avoid dealing with the boundary condition. 00031 ScoreboardDepth = 1; 00032 if (!ItinData.isEmpty()) { 00033 for (unsigned idx = 0; ; ++idx) { 00034 // If the begin stage of an itinerary has 0 cycles and units, 00035 // then we have reached the end of the itineraries. 00036 const InstrStage *IS = ItinData.beginStage(idx); 00037 const InstrStage *E = ItinData.endStage(idx); 00038 if ((IS->getCycles() == 0) && (IS->getUnits() == 0)) 00039 break; 00040 00041 unsigned ItinDepth = 0; 00042 for (; IS != E; ++IS) 00043 ItinDepth += IS->getCycles(); 00044 00045 ScoreboardDepth = std::max(ScoreboardDepth, ItinDepth); 00046 } 00047 } 00048 00049 Scoreboard = new unsigned[ScoreboardDepth]; 00050 ScoreboardHead = 0; 00051 00052 DEBUG(errs() << "Using exact hazard recognizer: ScoreboardDepth = " 00053 << ScoreboardDepth << '\n'); 00054 } 00055 00056 ExactHazardRecognizer::~ExactHazardRecognizer() { 00057 delete Scoreboard; 00058 } 00059 00060 void ExactHazardRecognizer::Reset() { 00061 memset(Scoreboard, 0, ScoreboardDepth * sizeof(unsigned)); 00062 ScoreboardHead = 0; 00063 } 00064 00065 unsigned ExactHazardRecognizer::getFutureIndex(unsigned offset) { 00066 return (ScoreboardHead + offset) % ScoreboardDepth; 00067 } 00068 00069 void ExactHazardRecognizer::dumpScoreboard() { 00070 errs() << "Scoreboard:\n"; 00071 00072 unsigned last = ScoreboardDepth - 1; 00073 while ((last > 0) && (Scoreboard[getFutureIndex(last)] == 0)) 00074 last--; 00075 00076 for (unsigned i = 0; i <= last; i++) { 00077 unsigned FUs = Scoreboard[getFutureIndex(i)]; 00078 errs() << "\t"; 00079 for (int j = 31; j >= 0; j--) 00080 errs() << ((FUs & (1 << j)) ? '1' : '0'); 00081 errs() << '\n'; 00082 } 00083 } 00084 00085 ExactHazardRecognizer::HazardType ExactHazardRecognizer::getHazardType(SUnit *SU) { 00086 unsigned cycle = 0; 00087 00088 // Use the itinerary for the underlying instruction to check for 00089 // free FU's in the scoreboard at the appropriate future cycles. 00090 unsigned idx = SU->getInstr()->getDesc().getSchedClass(); 00091 for (const InstrStage *IS = ItinData.beginStage(idx), 00092 *E = ItinData.endStage(idx); IS != E; ++IS) { 00093 // We must find one of the stage's units free for every cycle the 00094 // stage is occupied. FIXME it would be more accurate to find the 00095 // same unit free in all the cycles. 00096 for (unsigned int i = 0; i < IS->getCycles(); ++i) { 00097 assert(((cycle + i) < ScoreboardDepth) && 00098 "Scoreboard depth exceeded!"); 00099 00100 unsigned index = getFutureIndex(cycle + i); 00101 unsigned freeUnits = IS->getUnits() & ~Scoreboard[index]; 00102 if (!freeUnits) { 00103 DEBUG(errs() << "*** Hazard in cycle " << (cycle + i) << ", "); 00104 DEBUG(errs() << "SU(" << SU->NodeNum << "): "); 00105 DEBUG(SU->getInstr()->dump()); 00106 return Hazard; 00107 } 00108 } 00109 00110 // Advance the cycle to the next stage. 00111 cycle += IS->getNextCycles(); 00112 } 00113 00114 return NoHazard; 00115 } 00116 00117 void ExactHazardRecognizer::EmitInstruction(SUnit *SU) { 00118 unsigned cycle = 0; 00119 00120 // Use the itinerary for the underlying instruction to reserve FU's 00121 // in the scoreboard at the appropriate future cycles. 00122 unsigned idx = SU->getInstr()->getDesc().getSchedClass(); 00123 for (const InstrStage *IS = ItinData.beginStage(idx), 00124 *E = ItinData.endStage(idx); IS != E; ++IS) { 00125 // We must reserve one of the stage's units for every cycle the 00126 // stage is occupied. FIXME it would be more accurate to reserve 00127 // the same unit free in all the cycles. 00128 for (unsigned int i = 0; i < IS->getCycles(); ++i) { 00129 assert(((cycle + i) < ScoreboardDepth) && 00130 "Scoreboard depth exceeded!"); 00131 00132 unsigned index = getFutureIndex(cycle + i); 00133 unsigned freeUnits = IS->getUnits() & ~Scoreboard[index]; 00134 00135 // reduce to a single unit 00136 unsigned freeUnit = 0; 00137 do { 00138 freeUnit = freeUnits; 00139 freeUnits = freeUnit & (freeUnit - 1); 00140 } while (freeUnits); 00141 00142 assert(freeUnit && "No function unit available!"); 00143 Scoreboard[index] |= freeUnit; 00144 } 00145 00146 // Advance the cycle to the next stage. 00147 cycle += IS->getNextCycles(); 00148 } 00149 00150 DEBUG(dumpScoreboard()); 00151 } 00152 00153 void ExactHazardRecognizer::AdvanceCycle() { 00154 Scoreboard[ScoreboardHead] = 0; 00155 ScoreboardHead = getFutureIndex(1); 00156 } 00157 00158 } /* namespace llvm */