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