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 hazard recognizer using the instructions itineraries
  11 // defined for the current target.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "post-RA-sched"
  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::
  26 ExactHazardRecognizer(const InstrItineraryData &LItinData) :
  27   ScheduleHazardRecognizer(), ItinData(LItinData)
  28 {
  29   // Determine the maximum depth of any itinerary. This determines the
  30   // depth of the scoreboard. We always make the scoreboard at least 1
  31   // cycle deep to avoid dealing with the boundary condition.
  32   unsigned ScoreboardDepth = 1;
  33   if (!ItinData.isEmpty()) {
  34     for (unsigned idx = 0; ; ++idx) {
  35       if (ItinData.isEndMarker(idx))
  36         break;
  37
  38       const InstrStage *IS = ItinData.beginStage(idx);
  39       const InstrStage *E = ItinData.endStage(idx);
  40       unsigned ItinDepth = 0;
  41       for (; IS != E; ++IS)
  42         ItinDepth += IS->getCycles();
  43
  44       ScoreboardDepth = std::max(ScoreboardDepth, ItinDepth);
  45     }
  46   }
  47
  48   ReservedScoreboard.reset(ScoreboardDepth);
  49   RequiredScoreboard.reset(ScoreboardDepth);
  50
  51   DEBUG(dbgs() << "Using exact hazard recognizer: ScoreboardDepth = "
  52                << ScoreboardDepth << '\n');
  53 }
  54
  55 void ExactHazardRecognizer::Reset() {
  56   RequiredScoreboard.reset();
  57   ReservedScoreboard.reset();
  58 }
  59
  60 void ExactHazardRecognizer::ScoreBoard::dump() const {
  61   dbgs() << "Scoreboard:\n";
  62
  63   unsigned last = Depth - 1;
  64   while ((last > 0) && ((*this)[last] == 0))
  65     last--;
  66
  67   for (unsigned i = 0; i <= last; i++) {
  68     unsigned FUs = (*this)[i];
  69     dbgs() << "\t";
  70     for (int j = 31; j >= 0; j--)
  71       dbgs() << ((FUs & (1 << j)) ? '1' : '0');
  72     dbgs() << '\n';
  73   }
  74 }
  75
  76 ExactHazardRecognizer::HazardType ExactHazardRecognizer::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 ExactHazardRecognizer::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 ExactHazardRecognizer::AdvanceCycle() {
 178   ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
 179   RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
 180 }