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