LCOV - code coverage report
Current view: top level - lib/CodeGen - ScoreboardHazardRecognizer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 80 80 100.0 %
Date: 2018-07-13 00:08:38 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13