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 "sched-hazard"
  17 #include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
  18 #include "llvm/CodeGen/ScheduleDAG.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include "llvm/Target/TargetInstrItineraries.h"
  23
  24 using namespace llvm;
  25
  26 ScoreboardHazardRecognizer::
  27 ScoreboardHazardRecognizer(const InstrItineraryData *LItinData) :
  28   ScheduleHazardRecognizer(), ItinData(LItinData) {
  29   // Determine the maximum depth of any itinerary. This determines the
  30   // depth of the scoreboard. We always make the scoreboard at least 1
  31   // cycle deep to avoid dealing with the boundary condition.
  32   unsigned ScoreboardDepth = 1;
  33   if (ItinData && !ItinData->isEmpty()) {
  34     for (unsigned idx = 0; ; ++idx) {
  35       if (ItinData->isEndMarker(idx))
  36         break;
  37
  38       const InstrStage *IS = ItinData->beginStage(idx);
  39       const InstrStage *E = ItinData->endStage(idx);
  40       unsigned ItinDepth = 0;
  41       for (; IS != E; ++IS)
  42         ItinDepth += IS->getCycles();
  43
  44       // Find the next power-of-2 >= ItinDepth
  45       while (ItinDepth > ScoreboardDepth) {
  46         ScoreboardDepth *= 2;
  47       }
  48     }
  49   }
  50
  51   ReservedScoreboard.reset(ScoreboardDepth);
  52   RequiredScoreboard.reset(ScoreboardDepth);
  53
  54   DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
  55                << ScoreboardDepth << '\n');
  56 }
  57
  58 void ScoreboardHazardRecognizer::Reset() {
  59   RequiredScoreboard.reset();
  60   ReservedScoreboard.reset();
  61 }
  62
  63 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
  64   dbgs() << "Scoreboard:\n";
  65
  66   unsigned last = Depth - 1;
  67   while ((last > 0) && ((*this)[last] == 0))
  68     last--;
  69
  70   for (unsigned i = 0; i <= last; i++) {
  71     unsigned FUs = (*this)[i];
  72     dbgs() << "\t";
  73     for (int j = 31; j >= 0; j--)
  74       dbgs() << ((FUs & (1 << j)) ? '1' : '0');
  75     dbgs() << '\n';
  76   }
  77 }
  78
  79 ScheduleHazardRecognizer::HazardType
  80 ScoreboardHazardRecognizer::getHazardType(SUnit *SU) {
  81   if (!ItinData || ItinData->isEmpty())
  82     return NoHazard;
  83
  84   unsigned cycle = 0;
  85
  86   // Use the itinerary for the underlying instruction to check for
  87   // free FU's in the scoreboard at the appropriate future cycles.
  88   unsigned idx = SU->getInstr()->getDesc().getSchedClass();
  89   for (const InstrStage *IS = ItinData->beginStage(idx),
  90          *E = ItinData->endStage(idx); IS != E; ++IS) {
  91     // We must find one of the stage's units free for every cycle the
  92     // stage is occupied. FIXME it would be more accurate to find the
  93     // same unit free in all the cycles.
  94     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
  95       assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
  96              "Scoreboard depth exceeded!");
  97
  98       unsigned freeUnits = IS->getUnits();
  99       switch (IS->getReservationKind()) {
 100       default:
 101        assert(0 && "Invalid FU reservation");
 102       case InstrStage::Required:
 103         // Required FUs conflict with both reserved and required ones
 104         freeUnits &= ~ReservedScoreboard[cycle + i];
 105         // FALLTHROUGH
 106       case InstrStage::Reserved:
 107         // Reserved FUs can conflict only with required ones.
 108         freeUnits &= ~RequiredScoreboard[cycle + i];
 109         break;
 110       }
 111
 112       if (!freeUnits) {
 113         DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", ");
 114         DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
 115         DEBUG(SU->getInstr()->dump());
 116         return Hazard;
 117       }
 118     }
 119
 120     // Advance the cycle to the next stage.
 121     cycle += IS->getNextCycles();
 122   }
 123
 124   return NoHazard;
 125 }
 126
 127 void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
 128   if (!ItinData || ItinData->isEmpty())
 129     return;
 130
 131   unsigned cycle = 0;
 132
 133   // Use the itinerary for the underlying instruction to reserve FU's
 134   // in the scoreboard at the appropriate future cycles.
 135   unsigned idx = SU->getInstr()->getDesc().getSchedClass();
 136   for (const InstrStage *IS = ItinData->beginStage(idx),
 137          *E = ItinData->endStage(idx); IS != E; ++IS) {
 138     // We must reserve one of the stage's units for every cycle the
 139     // stage is occupied. FIXME it would be more accurate to reserve
 140     // the same unit free in all the cycles.
 141     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
 142       assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
 143              "Scoreboard depth exceeded!");
 144
 145       unsigned freeUnits = IS->getUnits();
 146       switch (IS->getReservationKind()) {
 147       default:
 148        assert(0 && "Invalid FU reservation");
 149       case InstrStage::Required:
 150         // Required FUs conflict with both reserved and required ones
 151         freeUnits &= ~ReservedScoreboard[cycle + i];
 152         // FALLTHROUGH
 153       case InstrStage::Reserved:
 154         // Reserved FUs can conflict only with required ones.
 155         freeUnits &= ~RequiredScoreboard[cycle + i];
 156         break;
 157       }
 158
 159       // reduce to a single unit
 160       unsigned freeUnit = 0;
 161       do {
 162         freeUnit = freeUnits;
 163         freeUnits = freeUnit & (freeUnit - 1);
 164       } while (freeUnits);
 165
 166       assert(freeUnit && "No function unit available!");
 167       if (IS->getReservationKind() == InstrStage::Required)
 168         RequiredScoreboard[cycle + i] |= freeUnit;
 169       else
 170         ReservedScoreboard[cycle + i] |= freeUnit;
 171     }
 172
 173     // Advance the cycle to the next stage.
 174     cycle += IS->getNextCycles();
 175   }
 176
 177   DEBUG(ReservedScoreboard.dump());
 178   DEBUG(RequiredScoreboard.dump());
 179 }
 180
 181 void ScoreboardHazardRecognizer::AdvanceCycle() {
 182   ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
 183   RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
 184 }
 185
 186 void ScoreboardHazardRecognizer::RecedeCycle() {
 187   ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
 188   ReservedScoreboard.recede();
 189   RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
 190   RequiredScoreboard.recede();
 191 }