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

Generated by: LCOV version 1.13