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