LLVM  10.0.0svn
Scheduler.cpp
Go to the documentation of this file.
1 //===--------------------- Scheduler.cpp ------------------------*- C++ -*-===//
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 // A scheduler for processor resource units and processor resource groups.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/Support/Debug.h"
16 
17 namespace llvm {
18 namespace mca {
19 
20 #define DEBUG_TYPE "llvm-mca"
21 
22 void Scheduler::initializeStrategy(std::unique_ptr<SchedulerStrategy> S) {
23  // Ensure we have a valid (non-null) strategy object.
24  Strategy = S ? std::move(S) : llvm::make_unique<DefaultSchedulerStrategy>();
25 }
26 
27 // Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy.
30 
31 #ifndef NDEBUG
32 void Scheduler::dump() const {
33  dbgs() << "[SCHEDULER]: WaitSet size is: " << WaitSet.size() << '\n';
34  dbgs() << "[SCHEDULER]: ReadySet size is: " << ReadySet.size() << '\n';
35  dbgs() << "[SCHEDULER]: IssuedSet size is: " << IssuedSet.size() << '\n';
36  Resources->dump();
37 }
38 #endif
39 
41  const InstrDesc &Desc = IR.getInstruction()->getDesc();
42 
43  ResourceStateEvent RSE = Resources->canBeDispatched(Desc.Buffers);
44  HadTokenStall = RSE != RS_BUFFER_AVAILABLE;
45 
46  switch (RSE) {
52  break;
53  }
54 
55  // Give lower priority to LSUnit stall events.
56  LSUnit::Status LSS = LSU.isAvailable(IR);
57  HadTokenStall = LSS != LSUnit::LSU_AVAILABLE;
58 
59  switch (LSS) {
66  }
67 
68  llvm_unreachable("Don't know how to process this LSU state result!");
69 }
70 
71 void Scheduler::issueInstructionImpl(
72  InstRef &IR,
73  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
74  Instruction *IS = IR.getInstruction();
75  const InstrDesc &D = IS->getDesc();
76 
77  // Issue the instruction and collect all the consumed resources
78  // into a vector. That vector is then used to notify the listener.
79  Resources->issueInstruction(D, UsedResources);
80 
81  // Notify the instruction that it started executing.
82  // This updates the internal state of each write.
83  IS->execute(IR.getSourceIndex());
84 
86 
87  if (IS->isMemOp()) {
88  LSU.onInstructionIssued(IR);
89  const MemoryGroup &Group = LSU.getGroup(IS->getLSUTokenID());
91  }
92 
93  if (IS->isExecuting())
94  IssuedSet.emplace_back(IR);
95  else if (IS->isExecuted())
96  LSU.onInstructionExecuted(IR);
97 }
98 
99 // Release the buffered resources and issue the instruction.
101  InstRef &IR,
102  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
103  SmallVectorImpl<InstRef> &PendingInstructions,
104  SmallVectorImpl<InstRef> &ReadyInstructions) {
105  const Instruction &Inst = *IR.getInstruction();
106  bool HasDependentUsers = Inst.hasDependentUsers();
107  HasDependentUsers |= Inst.isMemOp() && LSU.hasDependentUsers(IR);
108 
109  Resources->releaseBuffers(Inst.getDesc().Buffers);
110  issueInstructionImpl(IR, UsedResources);
111  // Instructions that have been issued during this cycle might have unblocked
112  // other dependent instructions. Dependent instructions may be issued during
113  // this same cycle if operands have ReadAdvance entries. Promote those
114  // instructions to the ReadySet and notify the caller that those are ready.
115  if (HasDependentUsers)
116  if (promoteToPendingSet(PendingInstructions))
117  promoteToReadySet(ReadyInstructions);
118 }
119 
120 bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
121  // Scan the set of waiting instructions and promote them to the
122  // ready set if operands are all ready.
123  unsigned PromotedElements = 0;
124  for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
125  InstRef &IR = *I;
126  if (!IR)
127  break;
128 
129  // Check if there are unsolved register dependencies.
130  Instruction &IS = *IR.getInstruction();
131  if (!IS.isReady() && !IS.updatePending()) {
132  ++I;
133  continue;
134  }
135  // Check if there are unsolved memory dependencies.
136  if (IS.isMemOp() && !LSU.isReady(IR)) {
137  ++I;
138  continue;
139  }
140 
141  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
142  << " promoted to the READY set.\n");
143 
144  Ready.emplace_back(IR);
145  ReadySet.emplace_back(IR);
146 
147  IR.invalidate();
148  ++PromotedElements;
149  std::iter_swap(I, E - PromotedElements);
150  }
151 
152  PendingSet.resize(PendingSet.size() - PromotedElements);
153  return PromotedElements;
154 }
155 
156 bool Scheduler::promoteToPendingSet(SmallVectorImpl<InstRef> &Pending) {
157  // Scan the set of waiting instructions and promote them to the
158  // pending set if operands are all ready.
159  unsigned RemovedElements = 0;
160  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
161  InstRef &IR = *I;
162  if (!IR)
163  break;
164 
165  // Check if this instruction is now ready. In case, force
166  // a transition in state using method 'updateDispatched()'.
167  Instruction &IS = *IR.getInstruction();
168  if (IS.isDispatched() && !IS.updateDispatched()) {
169  ++I;
170  continue;
171  }
172 
173  if (IS.isMemOp() && LSU.isWaiting(IR)) {
174  ++I;
175  continue;
176  }
177 
178  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
179  << " promoted to the PENDING set.\n");
180 
181  Pending.emplace_back(IR);
182  PendingSet.emplace_back(IR);
183 
184  IR.invalidate();
185  ++RemovedElements;
186  std::iter_swap(I, E - RemovedElements);
187  }
188 
189  WaitSet.resize(WaitSet.size() - RemovedElements);
190  return RemovedElements;
191 }
192 
194  unsigned QueueIndex = ReadySet.size();
195  for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
196  InstRef &IR = ReadySet[I];
197  if (QueueIndex == ReadySet.size() ||
198  Strategy->compare(IR, ReadySet[QueueIndex])) {
199  Instruction &IS = *IR.getInstruction();
200  uint64_t BusyResourceMask = Resources->checkAvailability(IS.getDesc());
201  if (BusyResourceMask)
202  IS.setCriticalResourceMask(BusyResourceMask);
203  BusyResourceUnits |= BusyResourceMask;
204  if (!BusyResourceMask)
205  QueueIndex = I;
206  }
207  }
208 
209  if (QueueIndex == ReadySet.size())
210  return InstRef();
211 
212  // We found an instruction to issue.
213  InstRef IR = ReadySet[QueueIndex];
214  std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
215  ReadySet.pop_back();
216  return IR;
217 }
218 
219 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
220  unsigned RemovedElements = 0;
221  for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
222  InstRef &IR = *I;
223  if (!IR)
224  break;
225  Instruction &IS = *IR.getInstruction();
226  if (!IS.isExecuted()) {
227  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
228  << " is still executing.\n");
229  ++I;
230  continue;
231  }
232 
233  // Instruction IR has completed execution.
234  LSU.onInstructionExecuted(IR);
235  Executed.emplace_back(IR);
236  ++RemovedElements;
237  IR.invalidate();
238  std::iter_swap(I, E - RemovedElements);
239  }
240 
241  IssuedSet.resize(IssuedSet.size() - RemovedElements);
242 }
243 
245  Insts.insert(Insts.end(), ReadySet.begin(), ReadySet.end());
246  return BusyResourceUnits;
247 }
248 
250  SmallVectorImpl<InstRef> &MemDeps) {
251  const auto EndIt = PendingSet.end() - NumDispatchedToThePendingSet;
252  for (const InstRef &IR : make_range(PendingSet.begin(), EndIt)) {
253  const Instruction &IS = *IR.getInstruction();
254  if (Resources->checkAvailability(IS.getDesc()))
255  continue;
256 
257  if (IS.isMemOp() && LSU.isPending(IR))
258  MemDeps.emplace_back(IR);
259 
260  if (IS.isPending())
261  RegDeps.emplace_back(IR);
262  }
263 }
264 
266  SmallVectorImpl<InstRef> &Executed,
267  SmallVectorImpl<InstRef> &Pending,
268  SmallVectorImpl<InstRef> &Ready) {
269  LSU.cycleEvent();
270 
271  // Release consumed resources.
272  Resources->cycleEvent(Freed);
273 
274  for (InstRef &IR : IssuedSet)
275  IR.getInstruction()->cycleEvent();
276  updateIssuedSet(Executed);
277 
278  for (InstRef &IR : PendingSet)
279  IR.getInstruction()->cycleEvent();
280 
281  for (InstRef &IR : WaitSet)
282  IR.getInstruction()->cycleEvent();
283 
284  promoteToPendingSet(Pending);
285  promoteToReadySet(Ready);
286 
287  NumDispatchedToThePendingSet = 0;
288  BusyResourceUnits = 0;
289 }
290 
292  const InstrDesc &Desc = IR.getInstruction()->getDesc();
293  if (Desc.isZeroLatency())
294  return true;
295  // Instructions that use an in-order dispatch/issue processor resource must be
296  // issued immediately to the pipeline(s). Any other in-order buffered
297  // resources (i.e. BufferSize=1) is consumed.
298  return Desc.MustIssueImmediately;
299 }
300 
302  Instruction &IS = *IR.getInstruction();
303  const InstrDesc &Desc = IS.getDesc();
304  Resources->reserveBuffers(Desc.Buffers);
305 
306  // If necessary, reserve queue entries in the load-store unit (LSU).
307  if (IS.isMemOp())
308  IS.setLSUTokenID(LSU.dispatch(IR));
309 
310  if (IS.isDispatched() || (IS.isMemOp() && LSU.isWaiting(IR))) {
311  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
312  WaitSet.push_back(IR);
313  return false;
314  }
315 
316  if (IS.isPending() || (IS.isMemOp() && LSU.isPending(IR))) {
317  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
318  << " to the PendingSet\n");
319  PendingSet.push_back(IR);
320  ++NumDispatchedToThePendingSet;
321  return false;
322  }
323 
324  assert(IS.isReady() && (!IS.isMemOp() || LSU.isReady(IR)) &&
325  "Unexpected internal state found!");
326  // Don't add a zero-latency instruction to the Ready queue.
327  // A zero-latency instruction doesn't consume any scheduler resources. That is
328  // because it doesn't need to be executed, and it is often removed at register
329  // renaming stage. For example, register-register moves are often optimized at
330  // register renaming stage by simply updating register aliases. On some
331  // targets, zero-idiom instructions (for example: a xor that clears the value
332  // of a register) are treated specially, and are often eliminated at register
333  // renaming stage.
334  if (!mustIssueImmediately(IR)) {
335  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
336  ReadySet.push_back(IR);
337  }
338 
339  return true;
340 }
341 
342 } // namespace mca
343 } // namespace llvm
void setCriticalMemDep(const CriticalDependency &MemDep)
Definition: Instruction.h:530
void dump() const
Definition: Scheduler.cpp:32
Instruction * getInstruction()
Definition: Instruction.h:559
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
void execute(unsigned IID)
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:440
bool hasDependentUsers() const
Definition: Instruction.h:418
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Status isAvailable(const InstRef &IR)
Check if the instruction in &#39;IR&#39; can be dispatched during this cycle.
Definition: Scheduler.cpp:40
void issueInstruction(InstRef &IR, SmallVectorImpl< std::pair< ResourceRef, ResourceCycles >> &Used, SmallVectorImpl< InstRef > &Pending, SmallVectorImpl< InstRef > &Ready)
Issue an instruction and populates a vector of used pipeline resources, and a vector of instructions ...
Definition: Scheduler.cpp:100
SmallVector< uint64_t, 4 > Buffers
Definition: Instruction.h:356
bool isDispatched() const
Definition: Instruction.h:510
InstRef select()
Select the next instruction to issue from the ReadySet.
Definition: Scheduler.cpp:193
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:545
A node of a memory dependency graph.
Definition: LSUnit.h:37
virtual void cycleEvent()
Definition: LSUnit.cpp:44
unsigned getSourceIndex() const
Definition: Instruction.h:558
unsigned dispatch(const InstRef &IR) override
Allocates LS resources for instruction IR.
Definition: LSUnit.cpp:69
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
void cycleEvent(SmallVectorImpl< ResourceRef > &Freed, SmallVectorImpl< InstRef > &Executed, SmallVectorImpl< InstRef > &Pending, SmallVectorImpl< InstRef > &Ready)
This routine notifies the Scheduler that a new cycle just started.
Definition: Scheduler.cpp:265
unsigned getLSUTokenID() const
Definition: Instruction.h:487
uint64_t analyzeResourcePressure(SmallVectorImpl< InstRef > &Insts)
Returns a mask of busy resources, and populates vector Insts with instructions that could not be issu...
Definition: Scheduler.cpp:244
void onInstructionExecuted(const InstRef &IR) override
Definition: LSUnit.cpp:188
const InstrDesc & getDesc() const
Definition: Instruction.h:414
Status isAvailable(const InstRef &IR) const override
Returns LSU_AVAILABLE if there are enough load/store queue entries to accomodate instruction IR...
Definition: LSUnit.cpp:153
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void invalidate()
Invalidate this reference.
Definition: Instruction.h:566
void setLSUTokenID(unsigned LSUTok)
Definition: Instruction.h:488
bool hasDependentUsers(const InstRef &IR) const
Definition: LSUnit.h:270
const CriticalDependency & computeCriticalRegDep()
ResourceStateEvent
Used to notify the internal state of a processor resource.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setCriticalResourceMask(uint64_t ResourceMask)
Definition: Instruction.h:535
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
const CriticalDependency & getCriticalPredecessor() const
Definition: LSUnit.h:76
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:467
bool isReady() const
Definition: Instruction.h:512
bool isPending(const InstRef &IR) const
Check if instruction IR only depends on memory instructions that are currently executing.
Definition: LSUnit.h:256
An instruction descriptor.
Definition: Instruction.h:347
bool mustIssueImmediately(const InstRef &IR) const
Returns true if IR has to be issued immediately, or if IR is a zero latency instruction.
Definition: Scheduler.cpp:291
bool isWaiting(const InstRef &IR) const
Check if instruction IR is still waiting on memory operations, and the wait time is still unknown...
Definition: LSUnit.h:264
void analyzeDataDependencies(SmallVectorImpl< InstRef > &RegDeps, SmallVectorImpl< InstRef > &MemDeps)
This method is called by the ExecuteStage at the end of each cycle to identify bottlenecks caused by ...
Definition: Scheduler.cpp:249
bool isExecuting() const
Definition: Instruction.h:513
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZeroLatency() const
Definition: Instruction.h:380
bool isPending() const
Definition: Instruction.h:511
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isExecuted() const
Definition: Instruction.h:514
A scheduler for Processor Resource Units and Processor Resource Groups.
bool dispatch(InstRef &IR)
Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.
Definition: Scheduler.cpp:301
virtual void onInstructionIssued(const InstRef &IR)
Definition: LSUnit.h:295
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Statically lint checks LLVM IR
Definition: Lint.cpp:192
const MemoryGroup & getGroup(unsigned Index) const
Definition: LSUnit.h:276
bool isReady(const InstRef &IR) const
Check if a peviously dispatched instruction IR is now ready for execution.
Definition: LSUnit.h:248