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