contrib/llvm/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 depth of
  43   // the scoreboard. We always make the scoreboard at least 1 cycle deep to
  44   // avoid dealing with the boundary condition.
  45   unsigned ScoreboardDepth = 1;
  46   if (ItinData && !ItinData->isEmpty()) {
  47     for (unsigned idx = 0; ; ++idx) {
  48       if (ItinData->isEndMarker(idx))
  49         break;
  50
  51       const InstrStage *IS = ItinData->beginStage(idx);
  52       const InstrStage *E = ItinData->endStage(idx);
  53       unsigned CurCycle = 0;
  54       unsigned ItinDepth = 0;
  55       for (; IS != E; ++IS) {
  56         unsigned StageDepth = CurCycle + IS->getCycles();
  57         if (ItinDepth < StageDepth) ItinDepth = StageDepth;
  58         CurCycle += IS->getNextCycles();
  59       }
  60
  61       // Find the next power-of-2 >= ItinDepth
  62       while (ItinDepth > ScoreboardDepth) {
  63         ScoreboardDepth *= 2;
  64         // Don't set MaxLookAhead until we find at least one nonzero stage.
  65         // This way, an itinerary with no stages has MaxLookAhead==0, which
  66         // completely bypasses the scoreboard hazard logic.
  67         MaxLookAhead = ScoreboardDepth;
  68       }
  69     }
  70   }
  71
  72   ReservedScoreboard.reset(ScoreboardDepth);
  73   RequiredScoreboard.reset(ScoreboardDepth);
  74
  75   // If MaxLookAhead is not set above, then we are not enabled.
  76   if (!isEnabled())
  77     DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
  78   else {
  79     // A nonempty itinerary must have a SchedModel.
  80     IssueWidth = ItinData->SchedModel->IssueWidth;
  81     DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
  82           << ScoreboardDepth << '\n');
  83   }
  84 }
  85
  86 void ScoreboardHazardRecognizer::Reset() {
  87   IssueCount = 0;
  88   RequiredScoreboard.reset();
  89   ReservedScoreboard.reset();
  90 }
  91
  92 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  93 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
  94   dbgs() << "Scoreboard:\n";
  95
  96   unsigned last = Depth - 1;
  97   while ((last > 0) && ((*this)[last] == 0))
  98     last--;
  99
 100   for (unsigned i = 0; i <= last; i++) {
 101     unsigned FUs = (*this)[i];
 102     dbgs() << "\t";
 103     for (int j = 31; j >= 0; j--)
 104       dbgs() << ((FUs & (1 << j)) ? '1' : '0');
 105     dbgs() << '\n';
 106   }
 107 }
 108 #endif
 109
 110 bool ScoreboardHazardRecognizer::atIssueLimit() const {
 111   if (IssueWidth == 0)
 112     return false;
 113
 114   return IssueCount == IssueWidth;
 115 }
 116
 117 ScheduleHazardRecognizer::HazardType
 118 ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
 119   if (!ItinData || ItinData->isEmpty())
 120     return NoHazard;
 121
 122   // Note that stalls will be negative for bottom-up scheduling.
 123   int cycle = Stalls;
 124
 125   // Use the itinerary for the underlying instruction to check for
 126   // free FU's in the scoreboard at the appropriate future cycles.
 127
 128   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
 129   if (MCID == NULL) {
 130     // Don't check hazards for non-machineinstr Nodes.
 131     return NoHazard;
 132   }
 133   unsigned idx = MCID->getSchedClass();
 134   for (const InstrStage *IS = ItinData->beginStage(idx),
 135          *E = ItinData->endStage(idx); IS != E; ++IS) {
 136     // We must find one of the stage's units free for every cycle the
 137     // stage is occupied. FIXME it would be more accurate to find the
 138     // same unit free in all the cycles.
 139     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 140       int StageCycle = cycle + (int)i;
 141       if (StageCycle < 0)
 142         continue;
 143
 144       if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
 145         assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
 146                "Scoreboard depth exceeded!");
 147         // This stage was stalled beyond pipeline depth, so cannot conflict.
 148         break;
 149       }
 150
 151       unsigned freeUnits = IS->getUnits();
 152       switch (IS->getReservationKind()) {
 153       case InstrStage::Required:
 154         // Required FUs conflict with both reserved and required ones
 155         freeUnits &= ~ReservedScoreboard[StageCycle];
 156         // FALLTHROUGH
 157       case InstrStage::Reserved:
 158         // Reserved FUs can conflict only with required ones.
 159         freeUnits &= ~RequiredScoreboard[StageCycle];
 160         break;
 161       }
 162
 163       if (!freeUnits) {
 164         DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
 165         DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
 166         DEBUG(DAG->dumpNode(SU));
 167         return Hazard;
 168       }
 169     }
 170
 171     // Advance the cycle to the next stage.
 172     cycle += IS->getNextCycles();
 173   }
 174
 175   return NoHazard;
 176 }
 177
 178 void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
 179   if (!ItinData || ItinData->isEmpty())
 180     return;
 181
 182   // Use the itinerary for the underlying instruction to reserve FU's
 183   // in the scoreboard at the appropriate future cycles.
 184   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
 185   assert(MCID && "The scheduler must filter non-machineinstrs");
 186   if (DAG->TII->isZeroCost(MCID->Opcode))
 187     return;
 188
 189   ++IssueCount;
 190
 191   unsigned cycle = 0;
 192
 193   unsigned idx = MCID->getSchedClass();
 194   for (const InstrStage *IS = ItinData->beginStage(idx),
 195          *E = ItinData->endStage(idx); IS != E; ++IS) {
 196     // We must reserve one of the stage's units for every cycle the
 197     // stage is occupied. FIXME it would be more accurate to reserve
 198     // the same unit free in all the cycles.
 199     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 200       assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
 201              "Scoreboard depth exceeded!");
 202
 203       unsigned freeUnits = IS->getUnits();
 204       switch (IS->getReservationKind()) {
 205       case InstrStage::Required:
 206         // Required FUs conflict with both reserved and required ones
 207         freeUnits &= ~ReservedScoreboard[cycle + i];
 208         // FALLTHROUGH
 209       case InstrStage::Reserved:
 210         // Reserved FUs can conflict only with required ones.
 211         freeUnits &= ~RequiredScoreboard[cycle + i];
 212         break;
 213       }
 214
 215       // reduce to a single unit
 216       unsigned freeUnit = 0;
 217       do {
 218         freeUnit = freeUnits;
 219         freeUnits = freeUnit & (freeUnit - 1);
 220       } while (freeUnits);
 221
 222       if (IS->getReservationKind() == InstrStage::Required)
 223         RequiredScoreboard[cycle + i] |= freeUnit;
 224       else
 225         ReservedScoreboard[cycle + i] |= freeUnit;
 226     }
 227
 228     // Advance the cycle to the next stage.
 229     cycle += IS->getNextCycles();
 230   }
 231
 232   DEBUG(ReservedScoreboard.dump());
 233   DEBUG(RequiredScoreboard.dump());
 234 }
 235
 236 void ScoreboardHazardRecognizer::AdvanceCycle() {
 237   IssueCount = 0;
 238   ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
 239   RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
 240 }
 241
 242 void ScoreboardHazardRecognizer::RecedeCycle() {
 243   IssueCount = 0;
 244   ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
 245   ReservedScoreboard.recede();
 246   RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
 247   RequiredScoreboard.recede();
 248 }