lib/CodeGen/ScoreboardHazardRecognizer.cpp

   1 //===----- ScoreboardHazardRecognizer.cpp - Scheduler Support -------------===//
   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 file implements the ScoreboardHazardRecognizer class, which
  11 // encapsultes hazard-avoidance heuristics for scheduling, based on the
  12 // scheduling itineraries specified for the target.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE ::llvm::ScoreboardHazardRecognizer::DebugType
  17 #include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
  18 #include "llvm/CodeGen/ScheduleDAG.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include "llvm/Target/TargetInstrItineraries.h"
  23
  24 using namespace llvm;
  25
  26 #ifndef NDEBUG
  27 const char *ScoreboardHazardRecognizer::DebugType = "";
  28 #endif
  29
  30 ScoreboardHazardRecognizer::
  31 ScoreboardHazardRecognizer(const InstrItineraryData *II,
  32                            const ScheduleDAG *SchedDAG,
  33                            const char *ParentDebugType) :
  34   ScheduleHazardRecognizer(), ItinData(II), DAG(SchedDAG), IssueWidth(0),
  35   IssueCount(0) {
  36
  37 #ifndef NDEBUG
  38   DebugType = ParentDebugType;
  39 #endif
  40
  41   // Determine the maximum depth of any itinerary. This determines the
  42   // depth of the scoreboard. We always make the scoreboard at least 1
  43   // cycle deep to avoid dealing with the boundary condition.
  44   unsigned ScoreboardDepth = 1;
  45   if (ItinData && !ItinData->isEmpty()) {
  46     IssueWidth = ItinData->IssueWidth;
  47
  48     for (unsigned idx = 0; ; ++idx) {
  49       if (ItinData->isEndMarker(idx))
  50         break;
  51
  52       const InstrStage *IS = ItinData->beginStage(idx);
  53       const InstrStage *E = ItinData->endStage(idx);
  54       unsigned CurCycle = 0;
  55       unsigned ItinDepth = 0;
  56       for (; IS != E; ++IS) {
  57         unsigned StageDepth = CurCycle + IS->getCycles();
  58         if (ItinDepth < StageDepth) ItinDepth = StageDepth;
  59         CurCycle += IS->getNextCycles();
  60       }
  61
  62       // Find the next power-of-2 >= ItinDepth
  63       while (ItinDepth > ScoreboardDepth) {
  64         ScoreboardDepth *= 2;
  65       }
  66     }
  67     MaxLookAhead = ScoreboardDepth;
  68   }
  69
  70   ReservedScoreboard.reset(ScoreboardDepth);
  71   RequiredScoreboard.reset(ScoreboardDepth);
  72
  73   DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
  74                << ScoreboardDepth << '\n');
  75 }
  76
  77 void ScoreboardHazardRecognizer::Reset() {
  78   IssueCount = 0;
  79   RequiredScoreboard.reset();
  80   ReservedScoreboard.reset();
  81 }
  82
  83 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
  84   dbgs() << "Scoreboard:\n";
  85
  86   unsigned last = Depth - 1;
  87   while ((last > 0) && ((*this)[last] == 0))
  88     last--;
  89
  90   for (unsigned i = 0; i <= last; i++) {
  91     unsigned FUs = (*this)[i];
  92     dbgs() << "\t";
  93     for (int j = 31; j >= 0; j--)
  94       dbgs() << ((FUs & (1 << j)) ? '1' : '0');
  95     dbgs() << '\n';
  96   }
  97 }
  98
  99 bool ScoreboardHazardRecognizer::atIssueLimit() const {
 100   if (IssueWidth == 0)
 101     return false;
 102
 103   return IssueCount == IssueWidth;
 104 }
 105
 106 ScheduleHazardRecognizer::HazardType
 107 ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
 108   if (!ItinData || ItinData->isEmpty())
 109     return NoHazard;
 110
 111   // Note that stalls will be negative for bottom-up scheduling.
 112   int cycle = Stalls;
 113
 114   // Use the itinerary for the underlying instruction to check for
 115   // free FU's in the scoreboard at the appropriate future cycles.
 116
 117   const TargetInstrDesc *TID = DAG->getInstrDesc(SU);
 118   if (TID == NULL) {
 119     // Don't check hazards for non-machineinstr Nodes.
 120     return NoHazard;
 121   }
 122   unsigned idx = TID->getSchedClass();
 123   for (const InstrStage *IS = ItinData->beginStage(idx),
 124          *E = ItinData->endStage(idx); IS != E; ++IS) {
 125     // We must find one of the stage's units free for every cycle the
 126     // stage is occupied. FIXME it would be more accurate to find the
 127     // same unit free in all the cycles.
 128     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 129       int StageCycle = cycle + (int)i;
 130       if (StageCycle < 0)
 131         continue;
 132
 133       if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
 134         assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
 135                "Scoreboard depth exceeded!");
 136         // This stage was stalled beyond pipeline depth, so cannot conflict.
 137         break;
 138       }
 139
 140       unsigned freeUnits = IS->getUnits();
 141       switch (IS->getReservationKind()) {
 142       default:
 143        assert(0 && "Invalid FU reservation");
 144       case InstrStage::Required:
 145         // Required FUs conflict with both reserved and required ones
 146         freeUnits &= ~ReservedScoreboard[StageCycle];
 147         // FALLTHROUGH
 148       case InstrStage::Reserved:
 149         // Reserved FUs can conflict only with required ones.
 150         freeUnits &= ~RequiredScoreboard[StageCycle];
 151         break;
 152       }
 153
 154       if (!freeUnits) {
 155         DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", ");
 156         DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
 157         DEBUG(DAG->dumpNode(SU));
 158         return Hazard;
 159       }
 160     }
 161
 162     // Advance the cycle to the next stage.
 163     cycle += IS->getNextCycles();
 164   }
 165
 166   return NoHazard;
 167 }
 168
 169 void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
 170   if (!ItinData || ItinData->isEmpty())
 171     return;
 172
 173   ++IssueCount;
 174
 175   unsigned cycle = 0;
 176
 177   // Use the itinerary for the underlying instruction to reserve FU's
 178   // in the scoreboard at the appropriate future cycles.
 179   const TargetInstrDesc *TID = DAG->getInstrDesc(SU);
 180   assert(TID && "The scheduler must filter non-machineinstrs");
 181   unsigned idx = TID->getSchedClass();
 182   for (const InstrStage *IS = ItinData->beginStage(idx),
 183          *E = ItinData->endStage(idx); IS != E; ++IS) {
 184     // We must reserve one of the stage's units for every cycle the
 185     // stage is occupied. FIXME it would be more accurate to reserve
 186     // the same unit free in all the cycles.
 187     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 188       assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
 189              "Scoreboard depth exceeded!");
 190
 191       unsigned freeUnits = IS->getUnits();
 192       switch (IS->getReservationKind()) {
 193       default:
 194        assert(0 && "Invalid FU reservation");
 195       case InstrStage::Required:
 196         // Required FUs conflict with both reserved and required ones
 197         freeUnits &= ~ReservedScoreboard[cycle + i];
 198         // FALLTHROUGH
 199       case InstrStage::Reserved:
 200         // Reserved FUs can conflict only with required ones.
 201         freeUnits &= ~RequiredScoreboard[cycle + i];
 202         break;
 203       }
 204
 205       // reduce to a single unit
 206       unsigned freeUnit = 0;
 207       do {
 208         freeUnit = freeUnits;
 209         freeUnits = freeUnit & (freeUnit - 1);
 210       } while (freeUnits);
 211
 212       assert(freeUnit && "No function unit available!");
 213       if (IS->getReservationKind() == InstrStage::Required)
 214         RequiredScoreboard[cycle + i] |= freeUnit;
 215       else
 216         ReservedScoreboard[cycle + i] |= freeUnit;
 217     }
 218
 219     // Advance the cycle to the next stage.
 220     cycle += IS->getNextCycles();
 221   }
 222
 223   DEBUG(ReservedScoreboard.dump());
 224   DEBUG(RequiredScoreboard.dump());
 225 }
 226
 227 void ScoreboardHazardRecognizer::AdvanceCycle() {
 228   IssueCount = 0;
 229   ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
 230   RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
 231 }
 232
 233 void ScoreboardHazardRecognizer::RecedeCycle() {
 234   IssueCount = 0;
 235   ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
 236   ReservedScoreboard.recede();
 237   RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
 238   RequiredScoreboard.recede();
 239 }