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-06-17 00:07:59 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      332967 : ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(
      32             :     const InstrItineraryData *II, const ScheduleDAG *SchedDAG,
      33      332967 :     const char *ParentDebugType)
      34             :     : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II),
      35      665934 :       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      332967 :   if (ItinData && !ItinData->isEmpty()) {
      42    27948574 :     for (unsigned idx = 0; ; ++idx) {
      43             :       if (ItinData->isEndMarker(idx))
      44             :         break;
      45             : 
      46    27948574 :       const InstrStage *IS = ItinData->beginStage(idx);
      47             :       const InstrStage *E = ItinData->endStage(idx);
      48             :       unsigned CurCycle = 0;
      49             :       unsigned ItinDepth = 0;
      50   128956988 :       for (; IS != E; ++IS) {
      51    50504207 :         unsigned StageDepth = CurCycle + IS->getCycles();
      52    50504207 :         if (ItinDepth < StageDepth) ItinDepth = StageDepth;
      53   101008414 :         CurCycle += IS->getNextCycles();
      54             :       }
      55             : 
      56             :       // Find the next power-of-2 >= ItinDepth
      57    28337560 :       while (ItinDepth > ScoreboardDepth) {
      58      194493 :         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      194493 :         MaxLookAhead = ScoreboardDepth;
      63             :       }
      64    27948574 :     }
      65             :   }
      66             : 
      67      332967 :   ReservedScoreboard.reset(ScoreboardDepth);
      68      332967 :   RequiredScoreboard.reset(ScoreboardDepth);
      69             : 
      70             :   // If MaxLookAhead is not set above, then we are not enabled.
      71      332967 :   if (!isEnabled())
      72             :     LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
      73             :   else {
      74             :     // A nonempty itinerary must have a SchedModel.
      75       37386 :     IssueWidth = ItinData->SchedModel.IssueWidth;
      76             :     LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
      77             :                       << ScoreboardDepth << '\n');
      78             :   }
      79      332967 : }
      80             : 
      81      471996 : void ScoreboardHazardRecognizer::Reset() {
      82      471996 :   IssueCount = 0;
      83      471996 :   RequiredScoreboard.reset();
      84      471996 :   ReservedScoreboard.reset();
      85      471996 : }
      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      726162 : bool ScoreboardHazardRecognizer::atIssueLimit() const {
     106      726162 :   if (IssueWidth == 0)
     107             :     return false;
     108             : 
     109      165634 :   return IssueCount == IssueWidth;
     110             : }
     111             : 
     112             : ScheduleHazardRecognizer::HazardType
     113     1045891 : ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
     114     1045891 :   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      484186 :   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
     124      484186 :   if (!MCID) {
     125             :     // Don't check hazards for non-machineinstr Nodes.
     126             :     return NoHazard;
     127             :   }
     128      365871 :   unsigned idx = MCID->getSchedClass();
     129      860482 :   for (const InstrStage *IS = ItinData->beginStage(idx),
     130      860482 :          *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     1861356 :     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
     135      737755 :       int StageCycle = cycle + (int)i;
     136      737755 :       if (StageCycle < 0)
     137       70820 :         continue;
     138             : 
     139      666935 :       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      666935 :       unsigned freeUnits = IS->getUnits();
     147      666935 :       switch (IS->getReservationKind()) {
     148      656802 :       case InstrStage::Required:
     149             :         // Required FUs conflict with both reserved and required ones
     150     1313604 :         freeUnits &= ~ReservedScoreboard[StageCycle];
     151             :         LLVM_FALLTHROUGH;
     152      666935 :       case InstrStage::Reserved:
     153             :         // Reserved FUs can conflict only with required ones.
     154     1333870 :         freeUnits &= ~RequiredScoreboard[StageCycle];
     155      666935 :         break;
     156             :       }
     157             : 
     158      666935 :       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      989222 :     cycle += IS->getNextCycles();
     168             :   }
     169             : 
     170             :   return NoHazard;
     171             : }
     172             : 
     173      739741 : void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
     174      739741 :   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      182404 :   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
     180             :   assert(MCID && "The scheduler must filter non-machineinstrs");
     181      182404 :   if (DAG->TII->isZeroCost(MCID->Opcode))
     182             :     return;
     183             : 
     184      161971 :   ++IssueCount;
     185             : 
     186             :   unsigned cycle = 0;
     187             : 
     188      161971 :   unsigned idx = MCID->getSchedClass();
     189      433619 :   for (const InstrStage *IS = ItinData->beginStage(idx),
     190      433619 :          *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      959398 :     for (unsigned int i = 0; i < IS->getCycles(); ++i) {
     195             :       assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
     196             :              "Scoreboard depth exceeded!");
     197             : 
     198      343875 :       unsigned freeUnits = IS->getUnits();
     199      343875 :       switch (IS->getReservationKind()) {
     200      338413 :       case InstrStage::Required:
     201             :         // Required FUs conflict with both reserved and required ones
     202      676826 :         freeUnits &= ~ReservedScoreboard[cycle + i];
     203             :         LLVM_FALLTHROUGH;
     204      343875 :       case InstrStage::Reserved:
     205             :         // Reserved FUs can conflict only with required ones.
     206      687750 :         freeUnits &= ~RequiredScoreboard[cycle + i];
     207      343875 :         break;
     208             :       }
     209             : 
     210             :       // reduce to a single unit
     211             :       unsigned freeUnit = 0;
     212             :       do {
     213             :         freeUnit = freeUnits;
     214      649101 :         freeUnits = freeUnit & (freeUnit - 1);
     215      649101 :       } while (freeUnits);
     216             : 
     217      343875 :       if (IS->getReservationKind() == InstrStage::Required)
     218      676826 :         RequiredScoreboard[cycle + i] |= freeUnit;
     219             :       else
     220       10924 :         ReservedScoreboard[cycle + i] |= freeUnit;
     221             :     }
     222             : 
     223             :     // Advance the cycle to the next stage.
     224      543296 :     cycle += IS->getNextCycles();
     225             :   }
     226             : 
     227             :   LLVM_DEBUG(ReservedScoreboard.dump());
     228             :   LLVM_DEBUG(RequiredScoreboard.dump());
     229             : }
     230             : 
     231      544985 : void ScoreboardHazardRecognizer::AdvanceCycle() {
     232      544985 :   IssueCount = 0;
     233      544985 :   ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
     234      544985 :   RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
     235      544985 : }
     236             : 
     237      152960 : void ScoreboardHazardRecognizer::RecedeCycle() {
     238      152960 :   IssueCount = 0;
     239      305920 :   ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
     240             :   ReservedScoreboard.recede();
     241      305920 :   RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
     242             :   RequiredScoreboard.recede();
     243      152960 : }

Generated by: LCOV version 1.13