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