| //===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the ScoreboardHazardRecognizer class, which |
| // encapsultes hazard-avoidance heuristics for scheduling, based on the |
| // scheduling itineraries specified for the target. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/CodeGen/ScoreboardHazardRecognizer.h" |
| #include "llvm/CodeGen/ScheduleDAG.h" |
| #include "llvm/CodeGen/TargetInstrInfo.h" |
| #include "llvm/Config/llvm-config.h" |
| #include "llvm/MC/MCInstrDesc.h" |
| #include "llvm/MC/MCInstrItineraries.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <cassert> |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE DebugType |
| |
| ScoreboardHazardRecognizer::ScoreboardHazardRecognizer( |
| const InstrItineraryData *II, const ScheduleDAG *SchedDAG, |
| const char *ParentDebugType) |
| : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II), |
| DAG(SchedDAG) { |
| (void)DebugType; |
| // Determine the maximum depth of any itinerary. This determines the depth of |
| // the scoreboard. We always make the scoreboard at least 1 cycle deep to |
| // avoid dealing with the boundary condition. |
| unsigned ScoreboardDepth = 1; |
| if (ItinData && !ItinData->isEmpty()) { |
| for (unsigned idx = 0; ; ++idx) { |
| if (ItinData->isEndMarker(idx)) |
| break; |
| |
| const InstrStage *IS = ItinData->beginStage(idx); |
| const InstrStage *E = ItinData->endStage(idx); |
| unsigned CurCycle = 0; |
| unsigned ItinDepth = 0; |
| for (; IS != E; ++IS) { |
| unsigned StageDepth = CurCycle + IS->getCycles(); |
| if (ItinDepth < StageDepth) ItinDepth = StageDepth; |
| CurCycle += IS->getNextCycles(); |
| } |
| |
| // Find the next power-of-2 >= ItinDepth |
| while (ItinDepth > ScoreboardDepth) { |
| ScoreboardDepth *= 2; |
| // Don't set MaxLookAhead until we find at least one nonzero stage. |
| // This way, an itinerary with no stages has MaxLookAhead==0, which |
| // completely bypasses the scoreboard hazard logic. |
| MaxLookAhead = ScoreboardDepth; |
| } |
| } |
| } |
| |
| ReservedScoreboard.reset(ScoreboardDepth); |
| RequiredScoreboard.reset(ScoreboardDepth); |
| |
| // If MaxLookAhead is not set above, then we are not enabled. |
| if (!isEnabled()) |
| LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n"); |
| else { |
| // A nonempty itinerary must have a SchedModel. |
| IssueWidth = ItinData->SchedModel.IssueWidth; |
| LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = " |
| << ScoreboardDepth << '\n'); |
| } |
| } |
| |
| void ScoreboardHazardRecognizer::Reset() { |
| IssueCount = 0; |
| RequiredScoreboard.reset(); |
| ReservedScoreboard.reset(); |
| } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| LLVM_DUMP_METHOD void ScoreboardHazardRecognizer::Scoreboard::dump() const { |
| dbgs() << "Scoreboard:\n"; |
| |
| unsigned last = Depth - 1; |
| while ((last > 0) && ((*this)[last] == 0)) |
| last--; |
| |
| for (unsigned i = 0; i <= last; i++) { |
| InstrStage::FuncUnits FUs = (*this)[i]; |
| dbgs() << "\t"; |
| for (int j = std::numeric_limits<InstrStage::FuncUnits>::digits - 1; |
| j >= 0; j--) |
| dbgs() << ((FUs & (1ULL << j)) ? '1' : '0'); |
| dbgs() << '\n'; |
| } |
| } |
| #endif |
| |
| bool ScoreboardHazardRecognizer::atIssueLimit() const { |
| if (IssueWidth == 0) |
| return false; |
| |
| return IssueCount == IssueWidth; |
| } |
| |
| ScheduleHazardRecognizer::HazardType |
| ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) { |
| if (!ItinData || ItinData->isEmpty()) |
| return NoHazard; |
| |
| // Note that stalls will be negative for bottom-up scheduling. |
| int cycle = Stalls; |
| |
| // Use the itinerary for the underlying instruction to check for |
| // free FU's in the scoreboard at the appropriate future cycles. |
| |
| const MCInstrDesc *MCID = DAG->getInstrDesc(SU); |
| if (!MCID) { |
| // Don't check hazards for non-machineinstr Nodes. |
| return NoHazard; |
| } |
| unsigned idx = MCID->getSchedClass(); |
| for (const InstrStage *IS = ItinData->beginStage(idx), |
| *E = ItinData->endStage(idx); IS != E; ++IS) { |
| // We must find one of the stage's units free for every cycle the |
| // stage is occupied. FIXME it would be more accurate to find the |
| // same unit free in all the cycles. |
| for (unsigned int i = 0; i < IS->getCycles(); ++i) { |
| int StageCycle = cycle + (int)i; |
| if (StageCycle < 0) |
| continue; |
| |
| if (StageCycle >= (int)RequiredScoreboard.getDepth()) { |
| assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() && |
| "Scoreboard depth exceeded!"); |
| // This stage was stalled beyond pipeline depth, so cannot conflict. |
| break; |
| } |
| |
| InstrStage::FuncUnits freeUnits = IS->getUnits(); |
| switch (IS->getReservationKind()) { |
| case InstrStage::Required: |
| // Required FUs conflict with both reserved and required ones |
| freeUnits &= ~ReservedScoreboard[StageCycle]; |
| LLVM_FALLTHROUGH; |
| case InstrStage::Reserved: |
| // Reserved FUs can conflict only with required ones. |
| freeUnits &= ~RequiredScoreboard[StageCycle]; |
| break; |
| } |
| |
| if (!freeUnits) { |
| LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", "); |
| LLVM_DEBUG(DAG->dumpNode(*SU)); |
| return Hazard; |
| } |
| } |
| |
| // Advance the cycle to the next stage. |
| cycle += IS->getNextCycles(); |
| } |
| |
| return NoHazard; |
| } |
| |
| void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) { |
| if (!ItinData || ItinData->isEmpty()) |
| return; |
| |
| // Use the itinerary for the underlying instruction to reserve FU's |
| // in the scoreboard at the appropriate future cycles. |
| const MCInstrDesc *MCID = DAG->getInstrDesc(SU); |
| assert(MCID && "The scheduler must filter non-machineinstrs"); |
| if (DAG->TII->isZeroCost(MCID->Opcode)) |
| return; |
| |
| ++IssueCount; |
| |
| unsigned cycle = 0; |
| |
| unsigned idx = MCID->getSchedClass(); |
| for (const InstrStage *IS = ItinData->beginStage(idx), |
| *E = ItinData->endStage(idx); IS != E; ++IS) { |
| // We must reserve one of the stage's units for every cycle the |
| // stage is occupied. FIXME it would be more accurate to reserve |
| // the same unit free in all the cycles. |
| for (unsigned int i = 0; i < IS->getCycles(); ++i) { |
| assert(((cycle + i) < RequiredScoreboard.getDepth()) && |
| "Scoreboard depth exceeded!"); |
| |
| InstrStage::FuncUnits freeUnits = IS->getUnits(); |
| switch (IS->getReservationKind()) { |
| case InstrStage::Required: |
| // Required FUs conflict with both reserved and required ones |
| freeUnits &= ~ReservedScoreboard[cycle + i]; |
| LLVM_FALLTHROUGH; |
| case InstrStage::Reserved: |
| // Reserved FUs can conflict only with required ones. |
| freeUnits &= ~RequiredScoreboard[cycle + i]; |
| break; |
| } |
| |
| // reduce to a single unit |
| InstrStage::FuncUnits freeUnit = 0; |
| do { |
| freeUnit = freeUnits; |
| freeUnits = freeUnit & (freeUnit - 1); |
| } while (freeUnits); |
| |
| if (IS->getReservationKind() == InstrStage::Required) |
| RequiredScoreboard[cycle + i] |= freeUnit; |
| else |
| ReservedScoreboard[cycle + i] |= freeUnit; |
| } |
| |
| // Advance the cycle to the next stage. |
| cycle += IS->getNextCycles(); |
| } |
| |
| LLVM_DEBUG(ReservedScoreboard.dump()); |
| LLVM_DEBUG(RequiredScoreboard.dump()); |
| } |
| |
| void ScoreboardHazardRecognizer::AdvanceCycle() { |
| IssueCount = 0; |
| ReservedScoreboard[0] = 0; ReservedScoreboard.advance(); |
| RequiredScoreboard[0] = 0; RequiredScoreboard.advance(); |
| } |
| |
| void ScoreboardHazardRecognizer::RecedeCycle() { |
| IssueCount = 0; |
| ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0; |
| ReservedScoreboard.recede(); |
| RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0; |
| RequiredScoreboard.recede(); |
| } |