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 
13 #include "llvm/MCA/HardwareUnits/Scheduler.h"
14 #include "llvm/Support/Debug.h"
15 #include "llvm/Support/raw_ostream.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.
28 SchedulerStrategy::~SchedulerStrategy() = default;
29 DefaultSchedulerStrategy::~DefaultSchedulerStrategy() = default;
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 
40 Scheduler::Status Scheduler::isAvailable(const InstRef &IR) const {
41   const InstrDesc &Desc = IR.getInstruction()->getDesc();
42 
43   switch (Resources->canBeDispatched(Desc.Buffers)) {
44   case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
45     return Scheduler::SC_BUFFERS_FULL;
46   case ResourceStateEvent::RS_RESERVED:
47     return Scheduler::SC_DISPATCH_GROUP_STALL;
48   case ResourceStateEvent::RS_BUFFER_AVAILABLE:
49     break;
50   }
51 
52   // Give lower priority to LSUnit stall events.
53   switch (LSU.isAvailable(IR)) {
54   case LSUnit::LSU_LQUEUE_FULL:
55     return Scheduler::SC_LOAD_QUEUE_FULL;
56   case LSUnit::LSU_SQUEUE_FULL:
57     return Scheduler::SC_STORE_QUEUE_FULL;
58   case LSUnit::LSU_AVAILABLE:
59     return Scheduler::SC_AVAILABLE;
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.
86 void Scheduler::issueInstruction(
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)
100     promoteToReadySet(ReadyInstructions);
101 }
102 
103 void Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
104   // Scan the set of waiting instructions and promote them to the
105   // ready queue if operands are all ready.
106   unsigned RemovedElements = 0;
107   for (auto I = WaitSet.begin(), E = WaitSet.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.update();
117 
118     // Check if there are still unsolved data dependencies.
119     if (!isReady(IR)) {
120       ++I;
121       continue;
122     }
123 
124     Ready.emplace_back(IR);
125     ReadySet.emplace_back(IR);
126 
127     IR.invalidate();
128     ++RemovedElements;
129     std::iter_swap(I, E - RemovedElements);
130   }
131 
132   WaitSet.resize(WaitSet.size() - RemovedElements);
133 }
134 
135 InstRef Scheduler::select() {
136   unsigned QueueIndex = ReadySet.size();
137   for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
138     const InstRef &IR = ReadySet[I];
139     if (QueueIndex == ReadySet.size() ||
140         Strategy->compare(IR, ReadySet[QueueIndex])) {
141       const InstrDesc &D = IR.getInstruction()->getDesc();
142       uint64_t BusyResourceMask = Resources->checkAvailability(D);
143       if (!BusyResourceMask)
144         QueueIndex = I;
145     }
146   }
147 
148   if (QueueIndex == ReadySet.size())
149     return InstRef();
150 
151   // We found an instruction to issue.
152   InstRef IR = ReadySet[QueueIndex];
153   std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
154   ReadySet.pop_back();
155   return IR;
156 }
157 
158 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
159   unsigned RemovedElements = 0;
160   for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
161     InstRef &IR = *I;
162     if (!IR)
163       break;
164     Instruction &IS = *IR.getInstruction();
165     if (!IS.isExecuted()) {
166       LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
167                         << " is still executing.\n");
168       ++I;
169       continue;
170     }
171 
172     // Instruction IR has completed execution.
173     LSU.onInstructionExecuted(IR);
174     Executed.emplace_back(IR);
175     ++RemovedElements;
176     IR.invalidate();
177     std::iter_swap(I, E - RemovedElements);
178   }
179 
180   IssuedSet.resize(IssuedSet.size() - RemovedElements);
181 }
182 
183 void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
184                            SmallVectorImpl<InstRef> &Executed,
185                            SmallVectorImpl<InstRef> &Ready) {
186   // Release consumed resources.
187   Resources->cycleEvent(Freed);
188 
189   // Propagate the cycle event to the 'Issued' and 'Wait' sets.
190   for (InstRef &IR : IssuedSet)
191     IR.getInstruction()->cycleEvent();
192 
193   updateIssuedSet(Executed);
194 
195   for (InstRef &IR : WaitSet)
196     IR.getInstruction()->cycleEvent();
197 
198   promoteToReadySet(Ready);
199 }
200 
201 bool Scheduler::mustIssueImmediately(const InstRef &IR) const {
202   const InstrDesc &Desc = IR.getInstruction()->getDesc();
203   if (Desc.isZeroLatency())
204     return true;
205   // Instructions that use an in-order dispatch/issue processor resource must be
206   // issued immediately to the pipeline(s). Any other in-order buffered
207   // resources (i.e. BufferSize=1) is consumed.
208   return Desc.MustIssueImmediately;
209 }
210 
211 void Scheduler::dispatch(const InstRef &IR) {
212   const InstrDesc &Desc = IR.getInstruction()->getDesc();
213   Resources->reserveBuffers(Desc.Buffers);
214 
215   // If necessary, reserve queue entries in the load-store unit (LSU).
216   bool IsMemOp = Desc.MayLoad || Desc.MayStore;
217   if (IsMemOp)
218     LSU.dispatch(IR);
219 
220   if (!isReady(IR)) {
221     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
222     WaitSet.push_back(IR);
223     return;
224   }
225 
226   // Don't add a zero-latency instruction to the Ready queue.
227   // A zero-latency instruction doesn't consume any scheduler resources. That is
228   // because it doesn't need to be executed, and it is often removed at register
229   // renaming stage. For example, register-register moves are often optimized at
230   // register renaming stage by simply updating register aliases. On some
231   // targets, zero-idiom instructions (for example: a xor that clears the value
232   // of a register) are treated specially, and are often eliminated at register
233   // renaming stage.
234   if (!mustIssueImmediately(IR)) {
235     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
236     ReadySet.push_back(IR);
237   }
238 }
239 
240 bool Scheduler::isReady(const InstRef &IR) const {
241   const InstrDesc &Desc = IR.getInstruction()->getDesc();
242   bool IsMemOp = Desc.MayLoad || Desc.MayStore;
243   return IR.getInstruction()->isReady() && (!IsMemOp || LSU.isReady(IR));
244 }
245 
246 } // namespace mca
247 } // namespace llvm
248