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