lib/CodeGen/ExactHazardRecognizer.cpp

   1 //===----- ExactHazardRecognizer.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 a hazard recognizer using the instructions itineraries
  11 // defined for the current target.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "exact-hazards"
  16 #include "ExactHazardRecognizer.h"
  17 #include "llvm/CodeGen/ScheduleHazardRecognizer.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 ExactHazardRecognizer::ExactHazardRecognizer(const InstrItineraryData &LItinData) :
  26   ScheduleHazardRecognizer(), ItinData(LItinData)
  27 {
  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   ScoreboardDepth = 1;
  32   if (!ItinData.isEmpty()) {
  33     for (unsigned idx = 0; ; ++idx) {
  34       // If the begin stage of an itinerary has 0 cycles and units,
  35       // then we have reached the end of the itineraries.
  36       const InstrStage *IS = ItinData.beginStage(idx);
  37       const InstrStage *E = ItinData.endStage(idx);
  38       if ((IS->getCycles() == 0) && (IS->getUnits() == 0))
  39         break;
  40
  41       unsigned ItinDepth = 0;
  42       for (; IS != E; ++IS)
  43         ItinDepth += IS->getCycles();
  44
  45       ScoreboardDepth = std::max(ScoreboardDepth, ItinDepth);
  46     }
  47   }
  48
  49   Scoreboard = new unsigned[ScoreboardDepth];
  50   ScoreboardHead = 0;
  51
  52   DEBUG(errs() << "Using exact hazard recognizer: ScoreboardDepth = "
  53                << ScoreboardDepth << '\n');
  54 }
  55
  56 ExactHazardRecognizer::~ExactHazardRecognizer() {
  57   delete [] Scoreboard;
  58 }
  59
  60 void ExactHazardRecognizer::Reset() {
  61   memset(Scoreboard, 0, ScoreboardDepth * sizeof(unsigned));
  62   ScoreboardHead = 0;
  63 }
  64
  65 unsigned ExactHazardRecognizer::getFutureIndex(unsigned offset) {
  66   return (ScoreboardHead + offset) % ScoreboardDepth;
  67 }
  68
  69 void ExactHazardRecognizer::dumpScoreboard() {
  70   errs() << "Scoreboard:\n";
  71
  72   unsigned last = ScoreboardDepth - 1;
  73   while ((last > 0) && (Scoreboard[getFutureIndex(last)] == 0))
  74     last--;
  75
  76   for (unsigned i = 0; i <= last; i++) {
  77     unsigned FUs = Scoreboard[getFutureIndex(i)];
  78     errs() << "\t";
  79     for (int j = 31; j >= 0; j--)
  80       errs() << ((FUs & (1 << j)) ? '1' : '0');
  81     errs() << '\n';
  82   }
  83 }
  84
  85 ExactHazardRecognizer::HazardType ExactHazardRecognizer::getHazardType(SUnit *SU) {
  86   if (ItinData.isEmpty())
  87     return NoHazard;
  88
  89   unsigned cycle = 0;
  90
  91   // Use the itinerary for the underlying instruction to check for
  92   // free FU's in the scoreboard at the appropriate future cycles.
  93   unsigned idx = SU->getInstr()->getDesc().getSchedClass();
  94   for (const InstrStage *IS = ItinData.beginStage(idx),
  95          *E = ItinData.endStage(idx); IS != E; ++IS) {
  96     // We must find one of the stage's units free for every cycle the
  97     // stage is occupied. FIXME it would be more accurate to find the
  98     // same unit free in all the cycles.
  99     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 100       assert(((cycle + i) < ScoreboardDepth) &&
 101              "Scoreboard depth exceeded!");
 102
 103       unsigned index = getFutureIndex(cycle + i);
 104       unsigned freeUnits = IS->getUnits() & ~Scoreboard[index];
 105       if (!freeUnits) {
 106         DEBUG(errs() << "*** Hazard in cycle " << (cycle + i) << ", ");
 107         DEBUG(errs() << "SU(" << SU->NodeNum << "): ");
 108         DEBUG(SU->getInstr()->dump());
 109         return Hazard;
 110       }
 111     }
 112
 113     // Advance the cycle to the next stage.
 114     cycle += IS->getNextCycles();
 115   }
 116
 117   return NoHazard;
 118 }
 119
 120 void ExactHazardRecognizer::EmitInstruction(SUnit *SU) {
 121   if (ItinData.isEmpty())
 122     return;
 123
 124   unsigned cycle = 0;
 125
 126   // Use the itinerary for the underlying instruction to reserve FU's
 127   // in the scoreboard at the appropriate future cycles.
 128   unsigned idx = SU->getInstr()->getDesc().getSchedClass();
 129   for (const InstrStage *IS = ItinData.beginStage(idx),
 130          *E = ItinData.endStage(idx); IS != E; ++IS) {
 131     // We must reserve one of the stage's units for every cycle the
 132     // stage is occupied. FIXME it would be more accurate to reserve
 133     // the same unit free in all the cycles.
 134     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 135       assert(((cycle + i) < ScoreboardDepth) &&
 136              "Scoreboard depth exceeded!");
 137
 138       unsigned index = getFutureIndex(cycle + i);
 139       unsigned freeUnits = IS->getUnits() & ~Scoreboard[index];
 140
 141       // reduce to a single unit
 142       unsigned freeUnit = 0;
 143       do {
 144         freeUnit = freeUnits;
 145         freeUnits = freeUnit & (freeUnit - 1);
 146       } while (freeUnits);
 147
 148       assert(freeUnit && "No function unit available!");
 149       Scoreboard[index] |= freeUnit;
 150     }
 151
 152     // Advance the cycle to the next stage.
 153     cycle += IS->getNextCycles();
 154   }
 155
 156   DEBUG(dumpScoreboard());
 157 }
 158
 159 void ExactHazardRecognizer::AdvanceCycle() {
 160   Scoreboard[ScoreboardHead] = 0;
 161   ScoreboardHead = getFutureIndex(1);
 162 }