1321369Sdim//===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===// 2218885Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218885Sdim// 7218885Sdim//===----------------------------------------------------------------------===// 8218885Sdim// 9218885Sdim// This file implements the ScoreboardHazardRecognizer class, which 10218885Sdim// encapsultes hazard-avoidance heuristics for scheduling, based on the 11218885Sdim// scheduling itineraries specified for the target. 12218885Sdim// 13218885Sdim//===----------------------------------------------------------------------===// 14218885Sdim 15218885Sdim#include "llvm/CodeGen/ScoreboardHazardRecognizer.h" 16218885Sdim#include "llvm/CodeGen/ScheduleDAG.h" 17327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 18341825Sdim#include "llvm/Config/llvm-config.h" 19321369Sdim#include "llvm/MC/MCInstrDesc.h" 20224145Sdim#include "llvm/MC/MCInstrItineraries.h" 21321369Sdim#include "llvm/Support/Compiler.h" 22218885Sdim#include "llvm/Support/Debug.h" 23218885Sdim#include "llvm/Support/raw_ostream.h" 24321369Sdim#include <cassert> 25218885Sdim 26218885Sdimusing namespace llvm; 27218885Sdim 28309124Sdim#define DEBUG_TYPE DebugType 29276479Sdim 30309124SdimScoreboardHazardRecognizer::ScoreboardHazardRecognizer( 31309124Sdim const InstrItineraryData *II, const ScheduleDAG *SchedDAG, 32309124Sdim const char *ParentDebugType) 33309124Sdim : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II), 34321369Sdim DAG(SchedDAG) { 35327952Sdim (void)DebugType; 36239462Sdim // Determine the maximum depth of any itinerary. This determines the depth of 37239462Sdim // the scoreboard. We always make the scoreboard at least 1 cycle deep to 38239462Sdim // avoid dealing with the boundary condition. 39218885Sdim unsigned ScoreboardDepth = 1; 40218885Sdim if (ItinData && !ItinData->isEmpty()) { 41218885Sdim for (unsigned idx = 0; ; ++idx) { 42218885Sdim if (ItinData->isEndMarker(idx)) 43218885Sdim break; 44218885Sdim 45218885Sdim const InstrStage *IS = ItinData->beginStage(idx); 46218885Sdim const InstrStage *E = ItinData->endStage(idx); 47218885Sdim unsigned CurCycle = 0; 48218885Sdim unsigned ItinDepth = 0; 49218885Sdim for (; IS != E; ++IS) { 50218885Sdim unsigned StageDepth = CurCycle + IS->getCycles(); 51218885Sdim if (ItinDepth < StageDepth) ItinDepth = StageDepth; 52218885Sdim CurCycle += IS->getNextCycles(); 53218885Sdim } 54218885Sdim 55218885Sdim // Find the next power-of-2 >= ItinDepth 56218885Sdim while (ItinDepth > ScoreboardDepth) { 57218885Sdim ScoreboardDepth *= 2; 58239462Sdim // Don't set MaxLookAhead until we find at least one nonzero stage. 59239462Sdim // This way, an itinerary with no stages has MaxLookAhead==0, which 60239462Sdim // completely bypasses the scoreboard hazard logic. 61239462Sdim MaxLookAhead = ScoreboardDepth; 62218885Sdim } 63218885Sdim } 64218885Sdim } 65218885Sdim 66218885Sdim ReservedScoreboard.reset(ScoreboardDepth); 67218885Sdim RequiredScoreboard.reset(ScoreboardDepth); 68218885Sdim 69239462Sdim // If MaxLookAhead is not set above, then we are not enabled. 70239462Sdim if (!isEnabled()) 71341825Sdim LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n"); 72239462Sdim else { 73239462Sdim // A nonempty itinerary must have a SchedModel. 74280031Sdim IssueWidth = ItinData->SchedModel.IssueWidth; 75341825Sdim LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = " 76341825Sdim << ScoreboardDepth << '\n'); 77239462Sdim } 78218885Sdim} 79218885Sdim 80218885Sdimvoid ScoreboardHazardRecognizer::Reset() { 81218885Sdim IssueCount = 0; 82218885Sdim RequiredScoreboard.reset(); 83218885Sdim ReservedScoreboard.reset(); 84218885Sdim} 85218885Sdim 86243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 87309124SdimLLVM_DUMP_METHOD void ScoreboardHazardRecognizer::Scoreboard::dump() const { 88218885Sdim dbgs() << "Scoreboard:\n"; 89218885Sdim 90218885Sdim unsigned last = Depth - 1; 91218885Sdim while ((last > 0) && ((*this)[last] == 0)) 92218885Sdim last--; 93218885Sdim 94218885Sdim for (unsigned i = 0; i <= last; i++) { 95218885Sdim unsigned FUs = (*this)[i]; 96218885Sdim dbgs() << "\t"; 97218885Sdim for (int j = 31; j >= 0; j--) 98218885Sdim dbgs() << ((FUs & (1 << j)) ? '1' : '0'); 99218885Sdim dbgs() << '\n'; 100218885Sdim } 101218885Sdim} 102243830Sdim#endif 103218885Sdim 104218885Sdimbool ScoreboardHazardRecognizer::atIssueLimit() const { 105218885Sdim if (IssueWidth == 0) 106218885Sdim return false; 107218885Sdim 108218885Sdim return IssueCount == IssueWidth; 109218885Sdim} 110218885Sdim 111218885SdimScheduleHazardRecognizer::HazardType 112218885SdimScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) { 113218885Sdim if (!ItinData || ItinData->isEmpty()) 114218885Sdim return NoHazard; 115218885Sdim 116218885Sdim // Note that stalls will be negative for bottom-up scheduling. 117218885Sdim int cycle = Stalls; 118218885Sdim 119218885Sdim // Use the itinerary for the underlying instruction to check for 120218885Sdim // free FU's in the scoreboard at the appropriate future cycles. 121218885Sdim 122224145Sdim const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 123276479Sdim if (!MCID) { 124218885Sdim // Don't check hazards for non-machineinstr Nodes. 125218885Sdim return NoHazard; 126218885Sdim } 127224145Sdim unsigned idx = MCID->getSchedClass(); 128218885Sdim for (const InstrStage *IS = ItinData->beginStage(idx), 129218885Sdim *E = ItinData->endStage(idx); IS != E; ++IS) { 130218885Sdim // We must find one of the stage's units free for every cycle the 131218885Sdim // stage is occupied. FIXME it would be more accurate to find the 132218885Sdim // same unit free in all the cycles. 133218885Sdim for (unsigned int i = 0; i < IS->getCycles(); ++i) { 134218885Sdim int StageCycle = cycle + (int)i; 135218885Sdim if (StageCycle < 0) 136218885Sdim continue; 137218885Sdim 138218885Sdim if (StageCycle >= (int)RequiredScoreboard.getDepth()) { 139218885Sdim assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() && 140218885Sdim "Scoreboard depth exceeded!"); 141218885Sdim // This stage was stalled beyond pipeline depth, so cannot conflict. 142218885Sdim break; 143218885Sdim } 144218885Sdim 145218885Sdim unsigned freeUnits = IS->getUnits(); 146218885Sdim switch (IS->getReservationKind()) { 147218885Sdim case InstrStage::Required: 148218885Sdim // Required FUs conflict with both reserved and required ones 149218885Sdim freeUnits &= ~ReservedScoreboard[StageCycle]; 150314564Sdim LLVM_FALLTHROUGH; 151218885Sdim case InstrStage::Reserved: 152218885Sdim // Reserved FUs can conflict only with required ones. 153218885Sdim freeUnits &= ~RequiredScoreboard[StageCycle]; 154218885Sdim break; 155218885Sdim } 156218885Sdim 157218885Sdim if (!freeUnits) { 158341825Sdim LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", "); 159344779Sdim LLVM_DEBUG(DAG->dumpNode(*SU)); 160218885Sdim return Hazard; 161218885Sdim } 162218885Sdim } 163218885Sdim 164218885Sdim // Advance the cycle to the next stage. 165218885Sdim cycle += IS->getNextCycles(); 166218885Sdim } 167218885Sdim 168218885Sdim return NoHazard; 169218885Sdim} 170218885Sdim 171218885Sdimvoid ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) { 172218885Sdim if (!ItinData || ItinData->isEmpty()) 173218885Sdim return; 174218885Sdim 175218885Sdim // Use the itinerary for the underlying instruction to reserve FU's 176218885Sdim // in the scoreboard at the appropriate future cycles. 177224145Sdim const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 178224145Sdim assert(MCID && "The scheduler must filter non-machineinstrs"); 179224145Sdim if (DAG->TII->isZeroCost(MCID->Opcode)) 180218885Sdim return; 181218885Sdim 182218885Sdim ++IssueCount; 183218885Sdim 184218885Sdim unsigned cycle = 0; 185218885Sdim 186224145Sdim unsigned idx = MCID->getSchedClass(); 187218885Sdim for (const InstrStage *IS = ItinData->beginStage(idx), 188218885Sdim *E = ItinData->endStage(idx); IS != E; ++IS) { 189218885Sdim // We must reserve one of the stage's units for every cycle the 190218885Sdim // stage is occupied. FIXME it would be more accurate to reserve 191218885Sdim // the same unit free in all the cycles. 192218885Sdim for (unsigned int i = 0; i < IS->getCycles(); ++i) { 193218885Sdim assert(((cycle + i) < RequiredScoreboard.getDepth()) && 194218885Sdim "Scoreboard depth exceeded!"); 195218885Sdim 196218885Sdim unsigned freeUnits = IS->getUnits(); 197218885Sdim switch (IS->getReservationKind()) { 198218885Sdim case InstrStage::Required: 199218885Sdim // Required FUs conflict with both reserved and required ones 200218885Sdim freeUnits &= ~ReservedScoreboard[cycle + i]; 201314564Sdim LLVM_FALLTHROUGH; 202218885Sdim case InstrStage::Reserved: 203218885Sdim // Reserved FUs can conflict only with required ones. 204218885Sdim freeUnits &= ~RequiredScoreboard[cycle + i]; 205218885Sdim break; 206218885Sdim } 207218885Sdim 208218885Sdim // reduce to a single unit 209218885Sdim unsigned freeUnit = 0; 210218885Sdim do { 211218885Sdim freeUnit = freeUnits; 212218885Sdim freeUnits = freeUnit & (freeUnit - 1); 213218885Sdim } while (freeUnits); 214218885Sdim 215218885Sdim if (IS->getReservationKind() == InstrStage::Required) 216218885Sdim RequiredScoreboard[cycle + i] |= freeUnit; 217218885Sdim else 218218885Sdim ReservedScoreboard[cycle + i] |= freeUnit; 219218885Sdim } 220218885Sdim 221218885Sdim // Advance the cycle to the next stage. 222218885Sdim cycle += IS->getNextCycles(); 223218885Sdim } 224218885Sdim 225341825Sdim LLVM_DEBUG(ReservedScoreboard.dump()); 226341825Sdim LLVM_DEBUG(RequiredScoreboard.dump()); 227218885Sdim} 228218885Sdim 229218885Sdimvoid ScoreboardHazardRecognizer::AdvanceCycle() { 230218885Sdim IssueCount = 0; 231218885Sdim ReservedScoreboard[0] = 0; ReservedScoreboard.advance(); 232218885Sdim RequiredScoreboard[0] = 0; RequiredScoreboard.advance(); 233218885Sdim} 234218885Sdim 235218885Sdimvoid ScoreboardHazardRecognizer::RecedeCycle() { 236218885Sdim IssueCount = 0; 237218885Sdim ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0; 238218885Sdim ReservedScoreboard.recede(); 239218885Sdim RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0; 240218885Sdim RequiredScoreboard.recede(); 241218885Sdim} 242