LLVM  10.0.0svn
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  unsigned FUs = (*this)[i];
96  dbgs() << "\t";
97  for (int j = 31; j >= 0; j--)
98  dbgs() << ((FUs & (1 << 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  unsigned 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  unsigned 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  unsigned 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 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
unsigned IssueWidth
Definition: MCSchedule.h:256
void RecedeCycle() override
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:178
virtual void dumpNode(const SUnit &SU) const =0
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:322
ScoreboardHazardRecognizer(const InstrItineraryData *II, const ScheduleDAG *DAG, const char *ParentDebugType="")
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:581
bool atIssueLimit() const override
atIssueLimit - Return true if no more instructions may be issued in this cycle.
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
Itinerary data supplied by a subtarget to be used by a target.
unsigned MaxLookAhead
MaxLookAhead - Indicate the number of cycles in the scoreboard state.
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:596
unsigned getNextCycles() const
Returns the number of cycles from the start of this stage to the start of the next stage in the itine...
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - Return the hazard type of emitting this node.
HazardRecognizer - This determines whether or not an instruction can be issued this cycle...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void Reset() override
Reset - This callback is invoked when a new block of instructions is about to be schedule.
void AdvanceCycle() override
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
bool isEndMarker(unsigned ItinClassIndx) const
Returns true if the index is for the end marker itinerary.
unsigned short Opcode
Definition: MCInstrDesc.h:180
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned getCycles() const
Returns the number of cycles the stage is occupied.
bool isEmpty() const
Returns true if there are no itineraries.
MCSchedModel SchedModel
Basic machine properties.
These values represent a non-pipelined step in the execution of an instruction.
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
bool isZeroCost(unsigned Opcode) const
Return true for pseudo instructions that don&#39;t consume any machine resources in their current form...
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:558
DebugType
Definition: COFF.h:645
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:258
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242