LLVM  15.0.0git
ScoreboardHazardRecognizer.cpp
Go to the documentation of this file.
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the ScoreboardHazardRecognizer class, which
10 // encapsultes hazard-avoidance heuristics for scheduling, based on the
11 // scheduling itineraries specified for the target.
12 //
13 //===----------------------------------------------------------------------===//
14 
18 #include "llvm/Config/llvm-config.h"
19 #include "llvm/MC/MCInstrDesc.h"
21 #include "llvm/Support/Compiler.h"
22 #include "llvm/Support/Debug.h"
24 #include <cassert>
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE DebugType
29 
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 of
36  // the scoreboard. We always make the scoreboard at least 1 cycle deep to
37  // 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 >= ItinDepth
55  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, which
59  // 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 
80  IssueCount = 0;
81  RequiredScoreboard.reset();
82  ReservedScoreboard.reset();
83 }
84 
85 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
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 #endif
103 
105  if (IssueWidth == 0)
106  return false;
107 
108  return IssueCount == IssueWidth;
109 }
110 
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 for
120  // 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 the
131  // stage is occupied. FIXME it would be more accurate to find the
132  // 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()) {
148  // Required FUs conflict with both reserved and required ones
149  freeUnits &= ~ReservedScoreboard[StageCycle];
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 
172  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  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 the
190  // stage is occupied. FIXME it would be more accurate to reserve
191  // 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()) {
199  // Required FUs conflict with both reserved and required ones
200  freeUnits &= ~ReservedScoreboard[cycle + i];
203  // Reserved FUs can conflict only with required ones.
204  freeUnits &= ~RequiredScoreboard[cycle + i];
205  break;
206  }
207 
208  // reduce to a single unit
209  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  else
218  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 
230  IssueCount = 0;
231  ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
232  RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
233 }
234 
236  IssueCount = 0;
237  ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
238  ReservedScoreboard.recede();
239  RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
240  RequiredScoreboard.recede();
241 }
i
i
Definition: README.txt:29
llvm::InstrStage::getCycles
unsigned getCycles() const
Returns the number of cycles the stage is occupied.
Definition: MCInstrItineraries.h:73
llvm::binaryformat::last
@ last
Definition: Swift.h:19
ScheduleDAG.h
ScoreboardHazardRecognizer.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
MCInstrDesc.h
llvm::ScheduleHazardRecognizer::MaxLookAhead
unsigned MaxLookAhead
MaxLookAhead - Indicate the number of cycles in the scoreboard state.
Definition: ScheduleHazardRecognizer.h:31
llvm::MCInstrDesc::getSchedClass
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:618
llvm::InstrStage::Reserved
@ Reserved
Definition: MCInstrItineraries.h:61
llvm::ScoreboardHazardRecognizer::Reset
void Reset() override
Reset - This callback is invoked when a new block of instructions is about to be schedule.
Definition: ScoreboardHazardRecognizer.cpp:79
llvm::ScoreboardHazardRecognizer::getHazardType
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - Return the hazard type of emitting this node.
Definition: ScoreboardHazardRecognizer.cpp:112
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
TargetInstrInfo.h
llvm::ScheduleHazardRecognizer::Hazard
@ Hazard
Definition: ScheduleHazardRecognizer.h:39
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::InstrItineraryData::endStage
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
Definition: MCInstrItineraries.h:141
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::InstrStage::Required
@ Required
Definition: MCInstrItineraries.h:60
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::TargetInstrInfo::isZeroCost
bool isZeroCost(unsigned Opcode) const
Return true for pseudo instructions that don't consume any machine resources in their current form.
Definition: TargetInstrInfo.h:1600
MCInstrItineraries.h
llvm::COFF::DebugType
DebugType
Definition: COFF.h:651
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
llvm::MCInstrDesc::Opcode
unsigned short Opcode
Definition: MCInstrDesc.h:199
llvm::ScheduleDAG::getInstrDesc
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:581
llvm::ScoreboardHazardRecognizer::AdvanceCycle
void AdvanceCycle() override
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
Definition: ScoreboardHazardRecognizer.cpp:229
llvm::InstrItineraryData::isEndMarker
bool isEndMarker(unsigned ItinClassIndx) const
Returns true if the index is for the end marker itinerary.
Definition: MCInstrItineraries.h:129
llvm::ScheduleHazardRecognizer::HazardType
HazardType
Definition: ScheduleHazardRecognizer.h:37
uint64_t
llvm::MCSchedModel::IssueWidth
unsigned IssueWidth
Definition: MCSchedule.h:256
llvm::ScoreboardHazardRecognizer::ScoreboardHazardRecognizer
ScoreboardHazardRecognizer(const InstrItineraryData *II, const ScheduleDAG *DAG, const char *ParentDebugType="")
Definition: ScoreboardHazardRecognizer.cpp:30
llvm::InstrStage::getNextCycles
unsigned getNextCycles() const
Returns the number of cycles from the start of this stage to the start of the next stage in the itine...
Definition: MCInstrItineraries.h:88
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ScheduleHazardRecognizer::isEnabled
bool isEnabled() const
Definition: ScheduleHazardRecognizer.h:45
llvm::ScheduleDAG
Definition: ScheduleDAG.h:555
llvm::ScheduleDAG::dumpNode
virtual void dumpNode(const SUnit &SU) const =0
Compiler.h
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:280
llvm::InstrStage
These values represent a non-pipelined step in the execution of an instruction.
Definition: MCInstrItineraries.h:58
j
return j(j<< 16)
llvm::ScoreboardHazardRecognizer::atIssueLimit
bool atIssueLimit() const override
atIssueLimit - Return true if no more instructions may be issued in this cycle.
Definition: ScoreboardHazardRecognizer.cpp:104
llvm::ScheduleHazardRecognizer::NoHazard
@ NoHazard
Definition: ScheduleHazardRecognizer.h:38
llvm::ScheduleDAG::TII
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:558
llvm::ScoreboardHazardRecognizer::RecedeCycle
void RecedeCycle() override
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
Definition: ScoreboardHazardRecognizer.cpp:235
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::InstrItineraryData::beginStage
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
Definition: MCInstrItineraries.h:135
raw_ostream.h
llvm::InstrItineraryData::isEmpty
bool isEmpty() const
Returns true if there are no itineraries.
Definition: MCInstrItineraries.h:126
Debug.h
llvm::InstrItineraryData
Itinerary data supplied by a subtarget to be used by a target.
Definition: MCInstrItineraries.h:109
llvm::InstrItineraryData::SchedModel
MCSchedModel SchedModel
Basic machine properties.
Definition: MCInstrItineraries.h:111
llvm::ScoreboardHazardRecognizer::EmitInstruction
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
Definition: ScoreboardHazardRecognizer.cpp:171