242 lines · cpp
1//===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the ScoreboardHazardRecognizer class, which10// encapsultes hazard-avoidance heuristics for scheduling, based on the11// scheduling itineraries specified for the target.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/CodeGen/ScoreboardHazardRecognizer.h"16#include "llvm/CodeGen/ScheduleDAG.h"17#include "llvm/CodeGen/TargetInstrInfo.h"18#include "llvm/Config/llvm-config.h"19#include "llvm/MC/MCInstrDesc.h"20#include "llvm/MC/MCInstrItineraries.h"21#include "llvm/Support/Compiler.h"22#include "llvm/Support/Debug.h"23#include "llvm/Support/raw_ostream.h"24#include <cassert>25 26using namespace llvm;27 28#define DEBUG_TYPE DebugType29 30ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(31 const InstrItineraryData *II, const ScheduleDAG *SchedDAG,32 const char *ParentDebugType)33 : DebugType(ParentDebugType), ItinData(II), DAG(SchedDAG) {34 (void)DebugType;35 // Determine the maximum depth of any itinerary. This determines the depth of36 // the scoreboard. We always make the scoreboard at least 1 cycle deep to37 // avoid dealing with the boundary condition.38 unsigned ScoreboardDepth = 1;39 if (ItinData && !ItinData->isEmpty()) {40 for (unsigned idx = 0; ; ++idx) {41 if (ItinData->isEndMarker(idx))42 break;43 44 const InstrStage *IS = ItinData->beginStage(idx);45 const InstrStage *E = ItinData->endStage(idx);46 unsigned CurCycle = 0;47 unsigned ItinDepth = 0;48 for (; IS != E; ++IS) {49 unsigned StageDepth = CurCycle + IS->getCycles();50 if (ItinDepth < StageDepth) ItinDepth = StageDepth;51 CurCycle += IS->getNextCycles();52 }53 54 // Find the next power-of-2 >= ItinDepth55 while (ItinDepth > ScoreboardDepth) {56 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, which59 // completely bypasses the scoreboard hazard logic.60 MaxLookAhead = ScoreboardDepth;61 }62 }63 }64 65 ReservedScoreboard.reset(ScoreboardDepth);66 RequiredScoreboard.reset(ScoreboardDepth);67 68 // If MaxLookAhead is not set above, then we are not enabled.69 if (!isEnabled())70 LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");71 else {72 // A nonempty itinerary must have a SchedModel.73 IssueWidth = ItinData->SchedModel.IssueWidth;74 LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "75 << ScoreboardDepth << '\n');76 }77}78 79void ScoreboardHazardRecognizer::Reset() {80 IssueCount = 0;81 RequiredScoreboard.reset();82 ReservedScoreboard.reset();83}84 85#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)86LLVM_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 InstrStage::FuncUnits FUs = (*this)[i];95 dbgs() << "\t";96 for (int j = std::numeric_limits<InstrStage::FuncUnits>::digits - 1;97 j >= 0; j--)98 dbgs() << ((FUs & (1ULL << j)) ? '1' : '0');99 dbgs() << '\n';100 }101}102#endif103 104bool ScoreboardHazardRecognizer::atIssueLimit() const {105 if (IssueWidth == 0)106 return false;107 108 return IssueCount == IssueWidth;109}110 111ScheduleHazardRecognizer::HazardType112ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {113 if (!ItinData || ItinData->isEmpty())114 return NoHazard;115 116 // Note that stalls will be negative for bottom-up scheduling.117 int cycle = Stalls;118 119 // Use the itinerary for the underlying instruction to check for120 // free FU's in the scoreboard at the appropriate future cycles.121 122 const MCInstrDesc *MCID = DAG->getInstrDesc(SU);123 if (!MCID) {124 // Don't check hazards for non-machineinstr Nodes.125 return NoHazard;126 }127 unsigned idx = MCID->getSchedClass();128 for (const InstrStage *IS = ItinData->beginStage(idx),129 *E = ItinData->endStage(idx); IS != E; ++IS) {130 // We must find one of the stage's units free for every cycle the131 // stage is occupied. FIXME it would be more accurate to find the132 // same unit free in all the cycles.133 for (unsigned int i = 0; i < IS->getCycles(); ++i) {134 int StageCycle = cycle + (int)i;135 if (StageCycle < 0)136 continue;137 138 if (StageCycle >= (int)RequiredScoreboard.getDepth()) {139 assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&140 "Scoreboard depth exceeded!");141 // This stage was stalled beyond pipeline depth, so cannot conflict.142 break;143 }144 145 InstrStage::FuncUnits freeUnits = IS->getUnits();146 switch (IS->getReservationKind()) {147 case InstrStage::Required:148 // Required FUs conflict with both reserved and required ones149 freeUnits &= ~ReservedScoreboard[StageCycle];150 [[fallthrough]];151 case InstrStage::Reserved:152 // Reserved FUs can conflict only with required ones.153 freeUnits &= ~RequiredScoreboard[StageCycle];154 break;155 }156 157 if (!freeUnits) {158 LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");159 LLVM_DEBUG(DAG->dumpNode(*SU));160 return Hazard;161 }162 }163 164 // Advance the cycle to the next stage.165 cycle += IS->getNextCycles();166 }167 168 return NoHazard;169}170 171void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {172 if (!ItinData || ItinData->isEmpty())173 return;174 175 // Use the itinerary for the underlying instruction to reserve FU's176 // in the scoreboard at the appropriate future cycles.177 const MCInstrDesc *MCID = DAG->getInstrDesc(SU);178 assert(MCID && "The scheduler must filter non-machineinstrs");179 if (DAG->TII->isZeroCost(MCID->Opcode))180 return;181 182 ++IssueCount;183 184 unsigned cycle = 0;185 186 unsigned idx = MCID->getSchedClass();187 for (const InstrStage *IS = ItinData->beginStage(idx),188 *E = ItinData->endStage(idx); IS != E; ++IS) {189 // We must reserve one of the stage's units for every cycle the190 // stage is occupied. FIXME it would be more accurate to reserve191 // the same unit free in all the cycles.192 for (unsigned int i = 0; i < IS->getCycles(); ++i) {193 assert(((cycle + i) < RequiredScoreboard.getDepth()) &&194 "Scoreboard depth exceeded!");195 196 InstrStage::FuncUnits freeUnits = IS->getUnits();197 switch (IS->getReservationKind()) {198 case InstrStage::Required:199 // Required FUs conflict with both reserved and required ones200 freeUnits &= ~ReservedScoreboard[cycle + i];201 [[fallthrough]];202 case InstrStage::Reserved:203 // Reserved FUs can conflict only with required ones.204 freeUnits &= ~RequiredScoreboard[cycle + i];205 break;206 }207 208 // reduce to a single unit209 InstrStage::FuncUnits freeUnit = 0;210 do {211 freeUnit = freeUnits;212 freeUnits = freeUnit & (freeUnit - 1);213 } while (freeUnits);214 215 if (IS->getReservationKind() == InstrStage::Required)216 RequiredScoreboard[cycle + i] |= freeUnit;217 else218 ReservedScoreboard[cycle + i] |= freeUnit;219 }220 221 // Advance the cycle to the next stage.222 cycle += IS->getNextCycles();223 }224 225 LLVM_DEBUG(ReservedScoreboard.dump());226 LLVM_DEBUG(RequiredScoreboard.dump());227}228 229void ScoreboardHazardRecognizer::AdvanceCycle() {230 IssueCount = 0;231 ReservedScoreboard[0] = 0; ReservedScoreboard.advance();232 RequiredScoreboard[0] = 0; RequiredScoreboard.advance();233}234 235void ScoreboardHazardRecognizer::RecedeCycle() {236 IssueCount = 0;237 ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;238 ReservedScoreboard.recede();239 RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;240 RequiredScoreboard.recede();241}242