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 #define DEBUG_TYPE ::llvm::ScoreboardHazardRecognizer::DebugType
     17 #include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
     18 #include "llvm/CodeGen/ScheduleDAG.h"
     19 #include "llvm/MC/MCInstrItineraries.h"
     20 #include "llvm/Support/Debug.h"
     21 #include "llvm/Support/ErrorHandling.h"
     22 #include "llvm/Support/raw_ostream.h"
     23 #include "llvm/Target/TargetInstrInfo.h"
     24 
     25 using namespace llvm;
     26 
     27 #ifndef NDEBUG
     28 const char *ScoreboardHazardRecognizer::DebugType = "";
     29 #endif
     30 
     31 ScoreboardHazardRecognizer::
     32 ScoreboardHazardRecognizer(const InstrItineraryData *II,
     33                            const ScheduleDAG *SchedDAG,
     34                            const char *ParentDebugType) :
     35   ScheduleHazardRecognizer(), ItinData(II), DAG(SchedDAG), IssueWidth(0),
     36   IssueCount(0) {
     37 
     38 #ifndef NDEBUG
     39   DebugType = ParentDebugType;
     40 #endif
     41 
     42   // Determine the maximum depth of any itinerary. This determines the
     43   // depth of the scoreboard. We always make the scoreboard at least 1
     44   // cycle deep to avoid dealing with the boundary condition.
     45   unsigned ScoreboardDepth = 1;
     46   if (ItinData && !ItinData->isEmpty()) {
     47     IssueWidth = ItinData->IssueWidth;
     48 
     49     for (unsigned idx = 0; ; ++idx) {
     50       if (ItinData->isEndMarker(idx))
     51         break;
     52 
     53       const InstrStage *IS = ItinData->beginStage(idx);
     54       const InstrStage *E = ItinData->endStage(idx);
     55       unsigned CurCycle = 0;
     56       unsigned ItinDepth = 0;
     57       for (; IS != E; ++IS) {
     58         unsigned StageDepth = CurCycle + IS->getCycles();
     59         if (ItinDepth < StageDepth) ItinDepth = StageDepth;
     60         CurCycle += IS->getNextCycles();
     61       }
     62 
     63       // Find the next power-of-2 >= ItinDepth
     64       while (ItinDepth > ScoreboardDepth) {
     65         ScoreboardDepth *= 2;
     66       }
     67     }
     68     MaxLookAhead = ScoreboardDepth;
     69   }
     70 
     71   ReservedScoreboard.reset(ScoreboardDepth);
     72   RequiredScoreboard.reset(ScoreboardDepth);
     73 
     74   DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
     75                << ScoreboardDepth << '\n');
     76 }
     77 
     78 void ScoreboardHazardRecognizer::Reset() {
     79   IssueCount = 0;
     80   RequiredScoreboard.reset();
     81   ReservedScoreboard.reset();
     82 }
     83 
     84 void ScoreboardHazardRecognizer::Scoreboard::dump() const {
     85   dbgs() << "Scoreboard:\n";
     86 
     87   unsigned last = Depth - 1;
     88   while ((last > 0) && ((*this)[last] == 0))
     89     last--;
     90 
     91   for (unsigned i = 0; i <= last; i++) {
     92     unsigned FUs = (*this)[i];
     93     dbgs() << "\t";
     94     for (int j = 31; j >= 0; j--)
     95       dbgs() << ((FUs & (1 << j)) ? '1' : '0');
     96     dbgs() << '\n';
     97   }
     98 }
     99 
    100 bool ScoreboardHazardRecognizer::atIssueLimit() const {
    101   if (IssueWidth == 0)
    102     return false;
    103 
    104   return IssueCount == IssueWidth;
    105 }
    106 
    107 ScheduleHazardRecognizer::HazardType
    108 ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
    109   if (!ItinData || ItinData->isEmpty())
    110     return NoHazard;
    111 
    112   // Note that stalls will be negative for bottom-up scheduling.
    113   int cycle = Stalls;
    114 
    115   // Use the itinerary for the underlying instruction to check for
    116   // free FU's in the scoreboard at the appropriate future cycles.
    117 
    118   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
    119   if (MCID == NULL) {
    120     // Don't check hazards for non-machineinstr Nodes.
    121     return NoHazard;
    122   }
    123   unsigned idx = MCID->getSchedClass();
    124   for (const InstrStage *IS = ItinData->beginStage(idx),
    125          *E = ItinData->endStage(idx); IS != E; ++IS) {
    126     // We must find one of the stage's units free for every cycle the
    127     // stage is occupied. FIXME it would be more accurate to find the
    128     // same unit free in all the cycles.
    129     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
    130       int StageCycle = cycle + (int)i;
    131       if (StageCycle < 0)
    132         continue;
    133 
    134       if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
    135         assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
    136                "Scoreboard depth exceeded!");
    137         // This stage was stalled beyond pipeline depth, so cannot conflict.
    138         break;
    139       }
    140 
    141       unsigned freeUnits = IS->getUnits();
    142       switch (IS->getReservationKind()) {
    143       default:
    144        assert(0 && "Invalid FU reservation");
    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 " << (cycle + i) << ", ");
    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       default:
    198        assert(0 && "Invalid FU reservation");
    199       case InstrStage::Required:
    200         // Required FUs conflict with both reserved and required ones
    201         freeUnits &= ~ReservedScoreboard[cycle + i];
    202         // 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   DEBUG(ReservedScoreboard.dump());
    227   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 }
    243