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