LLVM API Documentation

ExactHazardRecognizer.cpp

Go to the documentation of this file.
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 */