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