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  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 
85  if (IS->isExecuting())
86  IssuedSet.emplace_back(IR);
87  else if (IS->isExecuted())
88  LSU.onInstructionExecuted(IR);
89 }
90 
91 // Release the buffered resources and issue the instruction.
93  InstRef &IR,
94  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
95  SmallVectorImpl<InstRef> &PendingInstructions,
96  SmallVectorImpl<InstRef> &ReadyInstructions) {
97  const Instruction &Inst = *IR.getInstruction();
98  bool HasDependentUsers = Inst.hasDependentUsers();
99 
100  Resources->releaseBuffers(Inst.getDesc().Buffers);
101  issueInstructionImpl(IR, UsedResources);
102  // Instructions that have been issued during this cycle might have unblocked
103  // other dependent instructions. Dependent instructions may be issued during
104  // this same cycle if operands have ReadAdvance entries. Promote those
105  // instructions to the ReadySet and notify the caller that those are ready.
106  if (HasDependentUsers && promoteToPendingSet(PendingInstructions))
107  promoteToReadySet(ReadyInstructions);
108 }
109 
110 bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
111  // Scan the set of waiting instructions and promote them to the
112  // ready set if operands are all ready.
113  unsigned PromotedElements = 0;
114  for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
115  InstRef &IR = *I;
116  if (!IR)
117  break;
118 
119  // Check if there are still unsolved memory dependencies.
120  Instruction &IS = *IR.getInstruction();
121  if (IS.isMemOp()) {
122  unsigned CriticalMemDep = LSU.isReady(IR);
123  if (CriticalMemDep != IR.getSourceIndex()) {
124  IS.setCriticalMemDep(CriticalMemDep);
125  ++I;
126  continue;
127  }
128  }
129 
130  // Check if this instruction is now ready. In case, force
131  // a transition in state using method 'update()'.
132  if (!IS.isReady() && !IS.updatePending()) {
133  ++I;
134  continue;
135  }
136  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
137  << " promoted to the READY set.\n");
138 
139  Ready.emplace_back(IR);
140  ReadySet.emplace_back(IR);
141 
142  IR.invalidate();
143  ++PromotedElements;
144  std::iter_swap(I, E - PromotedElements);
145  }
146 
147  PendingSet.resize(PendingSet.size() - PromotedElements);
148  return PromotedElements;
149 }
150 
151 bool Scheduler::promoteToPendingSet(SmallVectorImpl<InstRef> &Pending) {
152  // Scan the set of waiting instructions and promote them to the
153  // pending set if operands are all ready.
154  unsigned RemovedElements = 0;
155  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
156  InstRef &IR = *I;
157  if (!IR)
158  break;
159 
160  // Check if this instruction is now ready. In case, force
161  // a transition in state using method 'update()'.
162  Instruction &IS = *IR.getInstruction();
163  if (IS.isDispatched() && !IS.updateDispatched()) {
164  ++I;
165  continue;
166  }
167  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
168  << " promoted to the PENDING set.\n");
169 
170  Pending.emplace_back(IR);
171  PendingSet.emplace_back(IR);
172 
173  IR.invalidate();
174  ++RemovedElements;
175  std::iter_swap(I, E - RemovedElements);
176  }
177 
178  WaitSet.resize(WaitSet.size() - RemovedElements);
179  return RemovedElements;
180 }
181 
183  unsigned QueueIndex = ReadySet.size();
184  for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
185  InstRef &IR = ReadySet[I];
186  if (QueueIndex == ReadySet.size() ||
187  Strategy->compare(IR, ReadySet[QueueIndex])) {
188  Instruction &IS = *IR.getInstruction();
189  uint64_t BusyResourceMask = Resources->checkAvailability(IS.getDesc());
190  IS.setCriticalResourceMask(BusyResourceMask);
191  BusyResourceUnits |= BusyResourceMask;
192  if (!BusyResourceMask)
193  QueueIndex = I;
194  }
195  }
196 
197  if (QueueIndex == ReadySet.size())
198  return InstRef();
199 
200  // We found an instruction to issue.
201  InstRef IR = ReadySet[QueueIndex];
202  std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
203  ReadySet.pop_back();
204  return IR;
205 }
206 
207 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
208  unsigned RemovedElements = 0;
209  for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
210  InstRef &IR = *I;
211  if (!IR)
212  break;
213  Instruction &IS = *IR.getInstruction();
214  if (!IS.isExecuted()) {
215  LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
216  << " is still executing.\n");
217  ++I;
218  continue;
219  }
220 
221  // Instruction IR has completed execution.
222  LSU.onInstructionExecuted(IR);
223  Executed.emplace_back(IR);
224  ++RemovedElements;
225  IR.invalidate();
226  std::iter_swap(I, E - RemovedElements);
227  }
228 
229  IssuedSet.resize(IssuedSet.size() - RemovedElements);
230 }
231 
233  Insts.insert(Insts.end(), ReadySet.begin(), ReadySet.end());
234  return BusyResourceUnits;
235 }
236 
238  SmallVectorImpl<InstRef> &MemDeps) {
239  const auto EndIt = PendingSet.end() - NumDispatchedToThePendingSet;
240  for (InstRef &IR : make_range(PendingSet.begin(), EndIt)) {
241  Instruction &IS = *IR.getInstruction();
242  if (Resources->checkAvailability(IS.getDesc()))
243  continue;
244 
245  if (IS.isReady() ||
246  (IS.isMemOp() && LSU.isReady(IR) != IR.getSourceIndex())) {
247  MemDeps.emplace_back(IR);
248  } else {
249  RegDeps.emplace_back(IR);
250  }
251  }
252 }
253 
255  SmallVectorImpl<InstRef> &Executed,
256  SmallVectorImpl<InstRef> &Pending,
257  SmallVectorImpl<InstRef> &Ready) {
258  // Release consumed resources.
259  Resources->cycleEvent(Freed);
260 
261  for (InstRef &IR : IssuedSet)
262  IR.getInstruction()->cycleEvent();
263  updateIssuedSet(Executed);
264 
265  for (InstRef &IR : PendingSet)
266  IR.getInstruction()->cycleEvent();
267 
268  for (InstRef &IR : WaitSet)
269  IR.getInstruction()->cycleEvent();
270 
271  promoteToPendingSet(Pending);
272  promoteToReadySet(Ready);
273 
274  NumDispatchedToThePendingSet = 0;
275  BusyResourceUnits = 0;
276 }
277 
279  const InstrDesc &Desc = IR.getInstruction()->getDesc();
280  if (Desc.isZeroLatency())
281  return true;
282  // Instructions that use an in-order dispatch/issue processor resource must be
283  // issued immediately to the pipeline(s). Any other in-order buffered
284  // resources (i.e. BufferSize=1) is consumed.
285  return Desc.MustIssueImmediately;
286 }
287 
288 bool Scheduler::dispatch(const InstRef &IR) {
289  const Instruction &IS = *IR.getInstruction();
290  const InstrDesc &Desc = IS.getDesc();
291  Resources->reserveBuffers(Desc.Buffers);
292 
293  // If necessary, reserve queue entries in the load-store unit (LSU).
294  if (IS.isMemOp())
295  LSU.dispatch(IR);
296 
297  if (IS.isPending()) {
298  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
299  << " to the PendingSet\n");
300  PendingSet.push_back(IR);
301  ++NumDispatchedToThePendingSet;
302  return false;
303  }
304 
305  // Memory operations that are not in a ready state are initially assigned to
306  // the WaitSet.
307  if (!IS.isReady() ||
308  (IS.isMemOp() && LSU.isReady(IR) != IR.getSourceIndex())) {
309  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
310  WaitSet.push_back(IR);
311  return false;
312  }
313 
314  // Don't add a zero-latency instruction to the Ready queue.
315  // A zero-latency instruction doesn't consume any scheduler resources. That is
316  // because it doesn't need to be executed, and it is often removed at register
317  // renaming stage. For example, register-register moves are often optimized at
318  // register renaming stage by simply updating register aliases. On some
319  // targets, zero-idiom instructions (for example: a xor that clears the value
320  // of a register) are treated specially, and are often eliminated at register
321  // renaming stage.
322  if (!mustIssueImmediately(IR)) {
323  LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
324  ReadySet.push_back(IR);
325  }
326 
327  return true;
328 }
329 
330 } // namespace mca
331 } // namespace llvm
void dump() const
Definition: Scheduler.cpp:32
Instruction * getInstruction()
Definition: Instruction.h:531
Status isAvailable(const InstRef &IR) const
Definition: LSUnit.cpp:87
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:645
void execute(unsigned IID)
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:430
bool hasDependentUsers() const
Definition: Instruction.h:408
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:92
SmallVector< uint64_t, 4 > Buffers
Definition: Instruction.h:346
bool isDispatched() const
Definition: Instruction.h:491
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:182
void onInstructionExecuted(const InstRef &IR)
Definition: LSUnit.cpp:157
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:521
unsigned getSourceIndex() const
Definition: Instruction.h:530
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:254
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:232
const InstrDesc & getDesc() const
Definition: Instruction.h:404
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void invalidate()
Invalidate this reference.
Definition: Instruction.h:538
bool dispatch(const InstRef &IR)
Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.
Definition: Scheduler.cpp:288
void setCriticalMemDep(unsigned IID)
Definition: Instruction.h:513
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:510
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")
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:471
bool isReady() const
Definition: Instruction.h:493
An instruction descriptor.
Definition: Instruction.h:337
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:278
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:237
bool isExecuting() const
Definition: Instruction.h:494
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZeroLatency() const
Definition: Instruction.h:370
void dispatch(const InstRef &IR)
Definition: LSUnit.cpp:68
bool isPending() const
Definition: Instruction.h:492
bool isExecuted() const
Definition: Instruction.h:495
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