LLVM  14.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  : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II),
34  DAG(SchedDAG) {
35  (void)DebugType;
36  // Determine the maximum depth of any itinerary. This determines the depth of
37  // the scoreboard. We always make the scoreboard at least 1 cycle deep to
38  // avoid dealing with the boundary condition.
39  unsigned ScoreboardDepth = 1;
40  if (ItinData && !ItinData->isEmpty()) {
41  for (unsigned idx = 0; ; ++idx) {
42  if (ItinData->isEndMarker(idx))
43  break;
44 
45  const InstrStage *IS = ItinData->beginStage(idx);
46  const InstrStage *E = ItinData->endStage(idx);
47  unsigned CurCycle = 0;
48  unsigned ItinDepth = 0;
49  for (; IS != E; ++IS) {
50  unsigned StageDepth = CurCycle + IS->getCycles();
51  if (ItinDepth < StageDepth) ItinDepth = StageDepth;
52  CurCycle += IS->getNextCycles();
53  }
54 
55  // Find the next power-of-2 >= ItinDepth
56  while (ItinDepth > ScoreboardDepth) {
57  ScoreboardDepth *= 2;
58  // Don't set MaxLookAhead until we find at least one nonzero stage.
59  // This way, an itinerary with no stages has MaxLookAhead==0, which
60  // completely bypasses the scoreboard hazard logic.
61  MaxLookAhead = ScoreboardDepth;
62  }
63  }
64  }
65 
66  ReservedScoreboard.reset(ScoreboardDepth);
67  RequiredScoreboard.reset(ScoreboardDepth);
68 
69  // If MaxLookAhead is not set above, then we are not enabled.
70  if (!isEnabled())
71  LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
72  else {
73  // A nonempty itinerary must have a SchedModel.
74  IssueWidth = ItinData->SchedModel.IssueWidth;
75  LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
76  << ScoreboardDepth << '\n');
77  }
78 }
79 
81  IssueCount = 0;
82  RequiredScoreboard.reset();
83  ReservedScoreboard.reset();
84 }
85 
86 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
88  dbgs() << "Scoreboard:\n";
89 
90  unsigned last = Depth - 1;
91  while ((last > 0) && ((*this)[last] == 0))
92  last--;
93 
94  for (unsigned i = 0; i <= last; i++) {
95  InstrStage::FuncUnits FUs = (*this)[i];
96  dbgs() << "\t";
97  for (int j = std::numeric_limits<InstrStage::FuncUnits>::digits - 1;
98  j >= 0; j--)
99  dbgs() << ((FUs & (1ULL << j)) ? '1' : '0');
100  dbgs() << '\n';
101  }
102 }
103 #endif
104 
106  if (IssueWidth == 0)
107  return false;
108 
109  return IssueCount == IssueWidth;
110 }
111 
114  if (!ItinData || ItinData->isEmpty())
115  return NoHazard;
116 
117  // Note that stalls will be negative for bottom-up scheduling.
118  int cycle = Stalls;
119 
120  // Use the itinerary for the underlying instruction to check for
121  // free FU's in the scoreboard at the appropriate future cycles.
122 
123  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
124  if (!MCID) {
125  // Don't check hazards for non-machineinstr Nodes.
126  return NoHazard;
127  }
128  unsigned idx = MCID->getSchedClass();
129  for (const InstrStage *IS = ItinData->beginStage(idx),
130  *E = ItinData->endStage(idx); IS != E; ++IS) {
131  // We must find one of the stage's units free for every cycle the
132  // stage is occupied. FIXME it would be more accurate to find the
133  // same unit free in all the cycles.
134  for (unsigned int i = 0; i < IS->getCycles(); ++i) {
135  int StageCycle = cycle + (int)i;
136  if (StageCycle < 0)
137  continue;
138 
139  if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
140  assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
141  "Scoreboard depth exceeded!");
142  // This stage was stalled beyond pipeline depth, so cannot conflict.
143  break;
144  }
145 
146  InstrStage::FuncUnits freeUnits = IS->getUnits();
147  switch (IS->getReservationKind()) {
149  // Required FUs conflict with both reserved and required ones
150  freeUnits &= ~ReservedScoreboard[StageCycle];
153  // Reserved FUs can conflict only with required ones.
154  freeUnits &= ~RequiredScoreboard[StageCycle];
155  break;
156  }
157 
158  if (!freeUnits) {
159  LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
160  LLVM_DEBUG(DAG->dumpNode(*SU));
161  return Hazard;
162  }
163  }
164 
165  // Advance the cycle to the next stage.
166  cycle += IS->getNextCycles();
167  }
168 
169  return NoHazard;
170 }
171 
173  if (!ItinData || ItinData->isEmpty())
174  return;
175 
176  // Use the itinerary for the underlying instruction to reserve FU's
177  // in the scoreboard at the appropriate future cycles.
178  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
179  assert(MCID && "The scheduler must filter non-machineinstrs");
180  if (DAG->TII->isZeroCost(MCID->Opcode))
181  return;
182 
183  ++IssueCount;
184 
185  unsigned cycle = 0;
186 
187  unsigned idx = MCID->getSchedClass();
188  for (const InstrStage *IS = ItinData->beginStage(idx),
189  *E = ItinData->endStage(idx); IS != E; ++IS) {
190  // We must reserve one of the stage's units for every cycle the
191  // stage is occupied. FIXME it would be more accurate to reserve
192  // the same unit free in all the cycles.
193  for (unsigned int i = 0; i < IS->getCycles(); ++i) {
194  assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
195  "Scoreboard depth exceeded!");
196 
197  InstrStage::FuncUnits freeUnits = IS->getUnits();
198  switch (IS->getReservationKind()) {
200  // Required FUs conflict with both reserved and required ones
201  freeUnits &= ~ReservedScoreboard[cycle + i];
204  // Reserved FUs can conflict only with required ones.
205  freeUnits &= ~RequiredScoreboard[cycle + i];
206  break;
207  }
208 
209  // reduce to a single unit
210  InstrStage::FuncUnits freeUnit = 0;
211  do {
212  freeUnit = freeUnits;
213  freeUnits = freeUnit & (freeUnit - 1);
214  } while (freeUnits);
215 
216  if (IS->getReservationKind() == InstrStage::Required)
217  RequiredScoreboard[cycle + i] |= freeUnit;
218  else
219  ReservedScoreboard[cycle + i] |= freeUnit;
220  }
221 
222  // Advance the cycle to the next stage.
223  cycle += IS->getNextCycles();
224  }
225 
226  LLVM_DEBUG(ReservedScoreboard.dump());
227  LLVM_DEBUG(RequiredScoreboard.dump());
228 }
229 
231  IssueCount = 0;
232  ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
233  RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
234 }
235 
237  IssueCount = 0;
238  ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
239  ReservedScoreboard.recede();
240  RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
241  RequiredScoreboard.recede();
242 }
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
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:491
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:612
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:80
llvm::ScoreboardHazardRecognizer::getHazardType
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - Return the hazard type of emitting this node.
Definition: ScoreboardHazardRecognizer.cpp:113
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:876
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:1592
MCInstrItineraries.h
llvm::COFF::DebugType
DebugType
Definition: COFF.h:652
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:195
llvm::MCInstrDesc::Opcode
unsigned short Opcode
Definition: MCInstrDesc.h:197
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:230
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:257
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:273
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:105
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:236
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::ScheduleHazardRecognizer
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
Definition: ScheduleHazardRecognizer.h:25
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:172