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) : std::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  ResourceStateEvent RSE =
42  Resources->canBeDispatched(IR.getInstruction()->getUsedBuffers());
43  HadTokenStall = RSE != RS_BUFFER_AVAILABLE;
44 
45  switch (RSE) {
51  break;
52  }
53 
54  // Give lower priority to LSUnit stall events.
55  LSUnit::Status LSS = LSU.isAvailable(IR);
56  HadTokenStall = LSS != LSUnit::LSU_AVAILABLE;
57 
58  switch (LSS) {
65  }
66 
67  llvm_unreachable("Don't know how to process this LSU state result!");
68 }
69 
70 void Scheduler::issueInstructionImpl(
71  InstRef &IR,
72  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
73  Instruction *IS = IR.getInstruction();
74  const InstrDesc &D = IS->getDesc();
75 
76  // Issue the instruction and collect all the consumed resources
77  // into a vector. That vector is then used to notify the listener.
78  Resources->issueInstruction(D, UsedResources);
79 
80  // Notify the instruction that it started executing.
81  // This updates the internal state of each write.
82  IS->execute(IR.getSourceIndex());
83 
85 
86  if (IS->isMemOp()) {
87  LSU.onInstructionIssued(IR);
88  const MemoryGroup &Group = LSU.getGroup(IS->getLSUTokenID());
90  }
91 
92  if (IS->isExecuting())
93  IssuedSet.emplace_back(IR);
94  else if (IS->isExecuted())
95  LSU.onInstructionExecuted(IR);
96 }
97 
98 // Release the buffered resources and issue the instruction.
100  InstRef &IR,
101  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
102  SmallVectorImpl<InstRef> &PendingInstructions,
103  SmallVectorImpl<InstRef> &ReadyInstructions) {
104  const Instruction &Inst = *IR.getInstruction();
105  bool HasDependentUsers = Inst.hasDependentUsers();
106  HasDependentUsers |= Inst.isMemOp() && LSU.hasDependentUsers(IR);
107 
108  Resources->releaseBuffers(Inst.getUsedBuffers());
109  issueInstructionImpl(IR, UsedResources);
110  // Instructions that have been issued during this cycle might have unblocked
111  // other dependent instructions. Dependent instructions may be issued during
112  // this same cycle if operands have ReadAdvance entries. Promote those
113  // instructions to the ReadySet and notify the caller that those are ready.
114  if (HasDependentUsers)
115  if (promoteToPendingSet(PendingInstructions))
116  promoteToReadySet(ReadyInstructions);
117 }
118 
119 bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
120  // Scan the set of waiting instructions and promote them to the
121  // ready set if operands are all ready.
122  unsigned PromotedElements = 0;
123  for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
124  InstRef &IR = *I;
125  if (!IR)
126  break;
127 
128  // Check if there are unsolved register dependencies.
129  Instruction &IS = *IR.getInstruction();
130  if (!IS.isReady() && !IS.updatePending()) {
131  ++I;
132  continue;
133  }
134  // Check if there are unsolved memory dependencies.
135  if (IS.isMemOp() && !LSU.isReady(IR)) {
136  ++I;
137  continue;
138  }
139 
140  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
141  << " promoted to the READY set.\n");
142 
143  Ready.emplace_back(IR);
144  ReadySet.emplace_back(IR);
145 
146  IR.invalidate();
147  ++PromotedElements;
148  std::iter_swap(I, E - PromotedElements);
149  }
150 
151  PendingSet.resize(PendingSet.size() - PromotedElements);
152  return PromotedElements;
153 }
154 
155 bool Scheduler::promoteToPendingSet(SmallVectorImpl<InstRef> &Pending) {
156  // Scan the set of waiting instructions and promote them to the
157  // pending set if operands are all ready.
158  unsigned RemovedElements = 0;
159  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
160  InstRef &IR = *I;
161  if (!IR)
162  break;
163 
164  // Check if this instruction is now ready. In case, force
165  // a transition in state using method 'updateDispatched()'.
166  Instruction &IS = *IR.getInstruction();
167  if (IS.isDispatched() && !IS.updateDispatched()) {
168  ++I;
169  continue;
170  }
171 
172  if (IS.isMemOp() && LSU.isWaiting(IR)) {
173  ++I;
174  continue;
175  }
176 
177  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
178  << " promoted to the PENDING set.\n");
179 
180  Pending.emplace_back(IR);
181  PendingSet.emplace_back(IR);
182 
183  IR.invalidate();
184  ++RemovedElements;
185  std::iter_swap(I, E - RemovedElements);
186  }
187 
188  WaitSet.resize(WaitSet.size() - RemovedElements);
189  return RemovedElements;
190 }
191 
193  unsigned QueueIndex = ReadySet.size();
194  for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
195  InstRef &IR = ReadySet[I];
196  if (QueueIndex == ReadySet.size() ||
197  Strategy->compare(IR, ReadySet[QueueIndex])) {
198  Instruction &IS = *IR.getInstruction();
199  uint64_t BusyResourceMask = Resources->checkAvailability(IS.getDesc());
200  if (BusyResourceMask)
201  IS.setCriticalResourceMask(BusyResourceMask);
202  BusyResourceUnits |= BusyResourceMask;
203  if (!BusyResourceMask)
204  QueueIndex = I;
205  }
206  }
207 
208  if (QueueIndex == ReadySet.size())
209  return InstRef();
210 
211  // We found an instruction to issue.
212  InstRef IR = ReadySet[QueueIndex];
213  std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
214  ReadySet.pop_back();
215  return IR;
216 }
217 
218 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
219  unsigned RemovedElements = 0;
220  for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
221  InstRef &IR = *I;
222  if (!IR)
223  break;
224  Instruction &IS = *IR.getInstruction();
225  if (!IS.isExecuted()) {
226  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
227  << " is still executing.\n");
228  ++I;
229  continue;
230  }
231 
232  // Instruction IR has completed execution.
233  LSU.onInstructionExecuted(IR);
234  Executed.emplace_back(IR);
235  ++RemovedElements;
236  IR.invalidate();
237  std::iter_swap(I, E - RemovedElements);
238  }
239 
240  IssuedSet.resize(IssuedSet.size() - RemovedElements);
241 }
242 
244  Insts.insert(Insts.end(), ReadySet.begin(), ReadySet.end());
245  return BusyResourceUnits;
246 }
247 
249  SmallVectorImpl<InstRef> &MemDeps) {
250  const auto EndIt = PendingSet.end() - NumDispatchedToThePendingSet;
251  for (const InstRef &IR : make_range(PendingSet.begin(), EndIt)) {
252  const Instruction &IS = *IR.getInstruction();
253  if (Resources->checkAvailability(IS.getDesc()))
254  continue;
255 
256  if (IS.isMemOp() && LSU.isPending(IR))
257  MemDeps.emplace_back(IR);
258 
259  if (IS.isPending())
260  RegDeps.emplace_back(IR);
261  }
262 }
263 
265  SmallVectorImpl<InstRef> &Executed,
266  SmallVectorImpl<InstRef> &Pending,
267  SmallVectorImpl<InstRef> &Ready) {
268  LSU.cycleEvent();
269 
270  // Release consumed resources.
271  Resources->cycleEvent(Freed);
272 
273  for (InstRef &IR : IssuedSet)
274  IR.getInstruction()->cycleEvent();
275  updateIssuedSet(Executed);
276 
277  for (InstRef &IR : PendingSet)
278  IR.getInstruction()->cycleEvent();
279 
280  for (InstRef &IR : WaitSet)
281  IR.getInstruction()->cycleEvent();
282 
283  promoteToPendingSet(Pending);
284  promoteToReadySet(Ready);
285 
286  NumDispatchedToThePendingSet = 0;
287  BusyResourceUnits = 0;
288 }
289 
291  const InstrDesc &Desc = IR.getInstruction()->getDesc();
292  if (Desc.isZeroLatency())
293  return true;
294  // Instructions that use an in-order dispatch/issue processor resource must be
295  // issued immediately to the pipeline(s). Any other in-order buffered
296  // resources (i.e. BufferSize=1) is consumed.
297  return Desc.MustIssueImmediately;
298 }
299 
301  Instruction &IS = *IR.getInstruction();
302  Resources->reserveBuffers(IS.getUsedBuffers());
303 
304  // If necessary, reserve queue entries in the load-store unit (LSU).
305  if (IS.isMemOp())
306  IS.setLSUTokenID(LSU.dispatch(IR));
307 
308  if (IS.isDispatched() || (IS.isMemOp() && LSU.isWaiting(IR))) {
309  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
310  WaitSet.push_back(IR);
311  return false;
312  }
313 
314  if (IS.isPending() || (IS.isMemOp() && LSU.isPending(IR))) {
315  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
316  << " to the PendingSet\n");
317  PendingSet.push_back(IR);
318  ++NumDispatchedToThePendingSet;
319  return false;
320  }
321 
322  assert(IS.isReady() && (!IS.isMemOp() || LSU.isReady(IR)) &&
323  "Unexpected internal state found!");
324  // Don't add a zero-latency instruction to the Ready queue.
325  // A zero-latency instruction doesn't consume any scheduler resources. That is
326  // because it doesn't need to be executed, and it is often removed at register
327  // renaming stage. For example, register-register moves are often optimized at
328  // register renaming stage by simply updating register aliases. On some
329  // targets, zero-idiom instructions (for example: a xor that clears the value
330  // of a register) are treated specially, and are often eliminated at register
331  // renaming stage.
332  if (!mustIssueImmediately(IR)) {
333  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
334  ReadySet.push_back(IR);
335  }
336 
337  return true;
338 }
339 
340 } // namespace mca
341 } // namespace llvm
void setCriticalMemDep(const CriticalDependency &MemDep)
Definition: Instruction.h:547
void dump() const
Definition: Scheduler.cpp:32
Instruction * getInstruction()
Definition: Instruction.h:576
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
void execute(unsigned IID)
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:445
bool hasDependentUsers() const
Definition: Instruction.h:423
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:99
bool isDispatched() const
Definition: Instruction.h:527
InstRef select()
Select the next instruction to issue from the ReadySet.
Definition: Scheduler.cpp:192
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:562
A node of a memory dependency graph.
Definition: LSUnit.h:37
virtual void cycleEvent()
Definition: LSUnit.cpp:44
unsigned getSourceIndex() const
Definition: Instruction.h:575
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:264
unsigned getLSUTokenID() const
Definition: Instruction.h:499
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:243
void onInstructionExecuted(const InstRef &IR) override
Definition: LSUnit.cpp:188
const InstrDesc & getDesc() const
Definition: Instruction.h:418
uint64_t getUsedBuffers() const
Definition: Instruction.h:502
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:583
void setLSUTokenID(unsigned LSUTok)
Definition: Instruction.h:500
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:552
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:529
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:348
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:290
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:248
bool isExecuting() const
Definition: Instruction.h:530
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZeroLatency() const
Definition: Instruction.h:384
bool isPending() const
Definition: Instruction.h:528
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isExecuted() const
Definition: Instruction.h:531
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:300
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