LLVM  8.0.0svn
ScoreboardHazardRecognizer.cpp
Go to the documentation of this file.
1 //===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the ScoreboardHazardRecognizer class, which
11 // encapsultes hazard-avoidance heuristics for scheduling, based on the
12 // scheduling itineraries specified for the target.
13 //
14 //===----------------------------------------------------------------------===//
15 
19 #include "llvm/Config/llvm-config.h"
20 #include "llvm/MC/MCInstrDesc.h"
22 #include "llvm/Support/Compiler.h"
23 #include "llvm/Support/Debug.h"
25 #include <cassert>
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE DebugType
30 
32  const InstrItineraryData *II, const ScheduleDAG *SchedDAG,
33  const char *ParentDebugType)
34  : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II),
35  DAG(SchedDAG) {
36  (void)DebugType;
37  // Determine the maximum depth of any itinerary. This determines the depth of
38  // the scoreboard. We always make the scoreboard at least 1 cycle deep to
39  // avoid dealing with the boundary condition.
40  unsigned ScoreboardDepth = 1;
41  if (ItinData && !ItinData->isEmpty()) {
42  for (unsigned idx = 0; ; ++idx) {
43  if (ItinData->isEndMarker(idx))
44  break;
45 
46  const InstrStage *IS = ItinData->beginStage(idx);
47  const InstrStage *E = ItinData->endStage(idx);
48  unsigned CurCycle = 0;
49  unsigned ItinDepth = 0;
50  for (; IS != E; ++IS) {
51  unsigned StageDepth = CurCycle + IS->getCycles();
52  if (ItinDepth < StageDepth) ItinDepth = StageDepth;
53  CurCycle += IS->getNextCycles();
54  }
55 
56  // Find the next power-of-2 >= ItinDepth
57  while (ItinDepth > ScoreboardDepth) {
58  ScoreboardDepth *= 2;
59  // Don't set MaxLookAhead until we find at least one nonzero stage.
60  // This way, an itinerary with no stages has MaxLookAhead==0, which
61  // completely bypasses the scoreboard hazard logic.
62  MaxLookAhead = ScoreboardDepth;
63  }
64  }
65  }
66 
67  ReservedScoreboard.reset(ScoreboardDepth);
68  RequiredScoreboard.reset(ScoreboardDepth);
69 
70  // If MaxLookAhead is not set above, then we are not enabled.
71  if (!isEnabled())
72  LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
73  else {
74  // A nonempty itinerary must have a SchedModel.
75  IssueWidth = ItinData->SchedModel.IssueWidth;
76  LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
77  << ScoreboardDepth << '\n');
78  }
79 }
80 
82  IssueCount = 0;
83  RequiredScoreboard.reset();
84  ReservedScoreboard.reset();
85 }
86 
87 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
89  dbgs() << "Scoreboard:\n";
90 
91  unsigned last = Depth - 1;
92  while ((last > 0) && ((*this)[last] == 0))
93  last--;
94 
95  for (unsigned i = 0; i <= last; i++) {
96  unsigned FUs = (*this)[i];
97  dbgs() << "\t";
98  for (int j = 31; j >= 0; j--)
99  dbgs() << ((FUs & (1 << 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  unsigned 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  unsigned 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  unsigned 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 }
This class represents lattice values for constants.
Definition: AllocatorList.h:24
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
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:164
virtual void dumpNode(const SUnit &SU) const =0
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:299
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:585
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
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:577
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:166
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
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:562
DebugType
Definition: COFF.h:643
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define LLVM_DEBUG(X)
Definition: Debug.h:123
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:246