LLVM  9.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  switch (Resources->canBeDispatched(Desc.Buffers)) {
49  break;
50  }
51 
52  // Give lower priority to LSUnit stall events.
53  switch (LSU.isAvailable(IR)) {
60  }
61 
62  llvm_unreachable("Don't know how to process this LSU state result!");
63 }
64 
65 void Scheduler::issueInstructionImpl(
66  InstRef &IR,
67  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
68  Instruction *IS = IR.getInstruction();
69  const InstrDesc &D = IS->getDesc();
70 
71  // Issue the instruction and collect all the consumed resources
72  // into a vector. That vector is then used to notify the listener.
73  Resources->issueInstruction(D, UsedResources);
74 
75  // Notify the instruction that it started executing.
76  // This updates the internal state of each write.
77  IS->execute();
78 
79  if (IS->isExecuting())
80  IssuedSet.emplace_back(IR);
81  else if (IS->isExecuted())
82  LSU.onInstructionExecuted(IR);
83 }
84 
85 // Release the buffered resources and issue the instruction.
87  InstRef &IR,
88  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
89  SmallVectorImpl<InstRef> &ReadyInstructions) {
90  const Instruction &Inst = *IR.getInstruction();
91  bool HasDependentUsers = Inst.hasDependentUsers();
92 
93  Resources->releaseBuffers(Inst.getDesc().Buffers);
94  issueInstructionImpl(IR, UsedResources);
95  // Instructions that have been issued during this cycle might have unblocked
96  // other dependent instructions. Dependent instructions may be issued during
97  // this same cycle if operands have ReadAdvance entries. Promote those
98  // instructions to the ReadySet and notify the caller that those are ready.
99  if (HasDependentUsers && promoteToPendingSet())
100  promoteToReadySet(ReadyInstructions);
101 }
102 
103 bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
104  // Scan the set of waiting instructions and promote them to the
105  // ready set if operands are all ready.
106  unsigned PromotedElements = 0;
107  for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
108  InstRef &IR = *I;
109  if (!IR)
110  break;
111 
112  // Check if this instruction is now ready. In case, force
113  // a transition in state using method 'update()'.
114  Instruction &IS = *IR.getInstruction();
115  if (!IS.isReady())
116  IS.updatePending();
117 
118  // Check if there are still unsolved data dependencies.
119  if (!isReady(IR)) {
120  ++I;
121  continue;
122  }
123 
124  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
125  << " promoted to the READY set.\n");
126 
127  Ready.emplace_back(IR);
128  ReadySet.emplace_back(IR);
129 
130  IR.invalidate();
131  ++PromotedElements;
132  std::iter_swap(I, E - PromotedElements);
133  }
134 
135  PendingSet.resize(PendingSet.size() - PromotedElements);
136  return PromotedElements;
137 }
138 
139 bool Scheduler::promoteToPendingSet() {
140  // Scan the set of waiting instructions and promote them to the
141  // pending set if operands are all ready.
142  unsigned RemovedElements = 0;
143  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
144  InstRef &IR = *I;
145  if (!IR)
146  break;
147 
148  // Check if this instruction is now ready. In case, force
149  // a transition in state using method 'update()'.
150  Instruction &IS = *IR.getInstruction();
151  if (IS.isDispatched() && !IS.updateDispatched()) {
152  ++I;
153  continue;
154  }
155  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
156  << " promoted to the PENDING set.\n");
157 
158  PendingSet.emplace_back(IR);
159 
160  IR.invalidate();
161  ++RemovedElements;
162  std::iter_swap(I, E - RemovedElements);
163  }
164 
165  WaitSet.resize(WaitSet.size() - RemovedElements);
166  return RemovedElements;
167 }
168 
170  unsigned QueueIndex = ReadySet.size();
171  for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
172  const InstRef &IR = ReadySet[I];
173  if (QueueIndex == ReadySet.size() ||
174  Strategy->compare(IR, ReadySet[QueueIndex])) {
175  const InstrDesc &D = IR.getInstruction()->getDesc();
176  uint64_t BusyResourceMask = Resources->checkAvailability(D);
177  BusyResourceUnits |= BusyResourceMask;
178  if (!BusyResourceMask)
179  QueueIndex = I;
180  }
181  }
182 
183  if (QueueIndex == ReadySet.size())
184  return InstRef();
185 
186  // We found an instruction to issue.
187  InstRef IR = ReadySet[QueueIndex];
188  std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
189  ReadySet.pop_back();
190  return IR;
191 }
192 
193 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
194  unsigned RemovedElements = 0;
195  for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
196  InstRef &IR = *I;
197  if (!IR)
198  break;
199  Instruction &IS = *IR.getInstruction();
200  if (!IS.isExecuted()) {
201  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
202  << " is still executing.\n");
203  ++I;
204  continue;
205  }
206 
207  // Instruction IR has completed execution.
208  LSU.onInstructionExecuted(IR);
209  Executed.emplace_back(IR);
210  ++RemovedElements;
211  IR.invalidate();
212  std::iter_swap(I, E - RemovedElements);
213  }
214 
215  IssuedSet.resize(IssuedSet.size() - RemovedElements);
216 }
217 
219  SmallVectorImpl<InstRef> &Executed,
220  SmallVectorImpl<InstRef> &Ready) {
221  // Release consumed resources.
222  Resources->cycleEvent(Freed);
223 
224  // Propagate the cycle event to the 'Issued' and 'Wait' sets.
225  for (InstRef &IR : IssuedSet)
226  IR.getInstruction()->cycleEvent();
227 
228  updateIssuedSet(Executed);
229 
230  for (InstRef &IR : PendingSet)
231  IR.getInstruction()->cycleEvent();
232 
233  for (InstRef &IR : WaitSet)
234  IR.getInstruction()->cycleEvent();
235 
236  promoteToPendingSet();
237  promoteToReadySet(Ready);
238 
239  BusyResourceUnits = 0;
240 }
241 
243  const InstrDesc &Desc = IR.getInstruction()->getDesc();
244  if (Desc.isZeroLatency())
245  return true;
246  // Instructions that use an in-order dispatch/issue processor resource must be
247  // issued immediately to the pipeline(s). Any other in-order buffered
248  // resources (i.e. BufferSize=1) is consumed.
249  return Desc.MustIssueImmediately;
250 }
251 
252 void Scheduler::dispatch(const InstRef &IR) {
253  const InstrDesc &Desc = IR.getInstruction()->getDesc();
254  Resources->reserveBuffers(Desc.Buffers);
255 
256  // If necessary, reserve queue entries in the load-store unit (LSU).
257  bool IsMemOp = Desc.MayLoad || Desc.MayStore;
258  if (IsMemOp)
259  LSU.dispatch(IR);
260 
261  if (IR.getInstruction()->isPending()) {
262  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
263  << " to the PendingSet\n");
264  PendingSet.push_back(IR);
265  return;
266  }
267 
268  if (!isReady(IR)) {
269  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
270  WaitSet.push_back(IR);
271  return;
272  }
273 
274  // Don't add a zero-latency instruction to the Ready queue.
275  // A zero-latency instruction doesn't consume any scheduler resources. That is
276  // because it doesn't need to be executed, and it is often removed at register
277  // renaming stage. For example, register-register moves are often optimized at
278  // register renaming stage by simply updating register aliases. On some
279  // targets, zero-idiom instructions (for example: a xor that clears the value
280  // of a register) are treated specially, and are often eliminated at register
281  // renaming stage.
282  if (!mustIssueImmediately(IR)) {
283  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
284  ReadySet.push_back(IR);
285  }
286 }
287 
288 bool Scheduler::isReady(const InstRef &IR) const {
289  const InstrDesc &Desc = IR.getInstruction()->getDesc();
290  bool IsMemOp = Desc.MayLoad || Desc.MayStore;
291  return IR.getInstruction()->isReady() &&
292  (!IsMemOp || LSU.isReady(IR) == IR.getSourceIndex());
293 }
294 
295 } // namespace mca
296 } // namespace llvm
void dump() const
Definition: Scheduler.cpp:32
bool isReady(const InstRef &IR) const
Returns true if IR is ready to be executed by the underlying pipelines.
Definition: Scheduler.cpp:288
Instruction * getInstruction()
Definition: Instruction.h:507
Status isAvailable(const InstRef &IR) const
Definition: LSUnit.cpp:87
Status isAvailable(const InstRef &IR) const
Check if the instruction in &#39;IR&#39; can be dispatched and returns an answer in the form of a Status valu...
Definition: Scheduler.cpp:40
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:422
bool hasDependentUsers() const
Definition: Instruction.h:401
void cycleEvent(SmallVectorImpl< ResourceRef > &Freed, SmallVectorImpl< InstRef > &Ready, SmallVectorImpl< InstRef > &Executed)
This routine notifies the Scheduler that a new cycle just started.
Definition: Scheduler.cpp:218
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SmallVector< uint64_t, 4 > Buffers
Definition: Instruction.h:339
bool isDispatched() const
Definition: Instruction.h:470
virtual unsigned isReady(const InstRef &IR) const
Definition: LSUnit.cpp:96
InstRef select()
Select the next instruction to issue from the ReadySet.
Definition: Scheduler.cpp:169
void onInstructionExecuted(const InstRef &IR)
Definition: LSUnit.cpp:157
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:497
unsigned getSourceIndex() const
Definition: Instruction.h:506
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
const InstrDesc & getDesc() const
Definition: Instruction.h:397
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void invalidate()
Invalidate this reference.
Definition: Instruction.h:514
void issueInstruction(InstRef &IR, SmallVectorImpl< std::pair< ResourceRef, ResourceCycles >> &Used, SmallVectorImpl< InstRef > &Ready)
Issue an instruction and populates a vector of used pipeline resources, and a vector of instructions ...
Definition: Scheduler.cpp:86
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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
bool isReady() const
Definition: Instruction.h:472
An instruction descriptor.
Definition: Instruction.h:330
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:242
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:644
bool isExecuting() const
Definition: Instruction.h:473
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZeroLatency() const
Definition: Instruction.h:363
void dispatch(const InstRef &IR)
Definition: LSUnit.cpp:68
bool isPending() const
Definition: Instruction.h:471
bool isExecuted() const
Definition: Instruction.h:474
A scheduler for Processor Resource Units and Processor Resource Groups.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Statically lint checks LLVM IR
Definition: Lint.cpp:192
void dispatch(const InstRef &IR)
Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.
Definition: Scheduler.cpp:252