Home | History | Annotate | Download | only in CodeGen 
      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         // 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         // 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 }
    241