1 //===--------------------- Scheduler.cpp ------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // A scheduler for processor resource units and processor resource groups.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/MCA/HardwareUnits/Scheduler.h"
14 #include "llvm/Support/Debug.h"
15 #include "llvm/Support/raw_ostream.h"
20 #define DEBUG_TYPE "llvm-mca"
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>();
27 // Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy.
28 SchedulerStrategy::~SchedulerStrategy() = default;
29 DefaultSchedulerStrategy::~DefaultSchedulerStrategy() = default;
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';
40 Scheduler::Status Scheduler::isAvailable(const InstRef &IR) {
41 const InstrDesc &Desc = IR.getInstruction()->getDesc();
43 ResourceStateEvent RSE = Resources->canBeDispatched(Desc.Buffers);
44 HadTokenStall = RSE != RS_BUFFER_AVAILABLE;
47 case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
48 return Scheduler::SC_BUFFERS_FULL;
49 case ResourceStateEvent::RS_RESERVED:
50 return Scheduler::SC_DISPATCH_GROUP_STALL;
51 case ResourceStateEvent::RS_BUFFER_AVAILABLE:
55 // Give lower priority to LSUnit stall events.
56 LSUnit::Status LSS = LSU.isAvailable(IR);
57 HadTokenStall = LSS != LSUnit::LSU_AVAILABLE;
60 case LSUnit::LSU_LQUEUE_FULL:
61 return Scheduler::SC_LOAD_QUEUE_FULL;
62 case LSUnit::LSU_SQUEUE_FULL:
63 return Scheduler::SC_STORE_QUEUE_FULL;
64 case LSUnit::LSU_AVAILABLE:
65 return Scheduler::SC_AVAILABLE;
68 llvm_unreachable("Don't know how to process this LSU state result!");
71 void Scheduler::issueInstructionImpl(
73 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
74 Instruction *IS = IR.getInstruction();
75 const InstrDesc &D = IS->getDesc();
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);
81 // Notify the instruction that it started executing.
82 // This updates the internal state of each write.
83 IS->execute(IR.getSourceIndex());
85 IS->computeCriticalRegDep();
88 LSU.onInstructionIssued(IR);
89 const MemoryGroup &Group = LSU.getGroup(IS->getLSUTokenID());
90 IS->setCriticalMemDep(Group.getCriticalPredecessor());
93 if (IS->isExecuting())
94 IssuedSet.emplace_back(IR);
95 else if (IS->isExecuted())
96 LSU.onInstructionExecuted(IR);
99 // Release the buffered resources and issue the instruction.
100 void Scheduler::issueInstruction(
102 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
103 SmallVectorImpl<InstRef> &PendingInstructions,
104 SmallVectorImpl<InstRef> &ReadyInstructions) {
105 const Instruction &Inst = *IR.getInstruction();
106 bool HasDependentUsers = Inst.hasDependentUsers();
107 HasDependentUsers |= Inst.isMemOp() && LSU.hasDependentUsers(IR);
109 Resources->releaseBuffers(Inst.getDesc().Buffers);
110 issueInstructionImpl(IR, UsedResources);
111 // Instructions that have been issued during this cycle might have unblocked
112 // other dependent instructions. Dependent instructions may be issued during
113 // this same cycle if operands have ReadAdvance entries. Promote those
114 // instructions to the ReadySet and notify the caller that those are ready.
115 if (HasDependentUsers)
116 if (promoteToPendingSet(PendingInstructions))
117 promoteToReadySet(ReadyInstructions);
120 bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
121 // Scan the set of waiting instructions and promote them to the
122 // ready set if operands are all ready.
123 unsigned PromotedElements = 0;
124 for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
129 // Check if there are unsolved register dependencies.
130 Instruction &IS = *IR.getInstruction();
131 if (!IS.isReady() && !IS.updatePending()) {
135 // Check if there are unsolved memory dependencies.
136 if (IS.isMemOp() && !LSU.isReady(IR)) {
141 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
142 << " promoted to the READY set.\n");
144 Ready.emplace_back(IR);
145 ReadySet.emplace_back(IR);
149 std::iter_swap(I, E - PromotedElements);
152 PendingSet.resize(PendingSet.size() - PromotedElements);
153 return PromotedElements;
156 bool Scheduler::promoteToPendingSet(SmallVectorImpl<InstRef> &Pending) {
157 // Scan the set of waiting instructions and promote them to the
158 // pending set if operands are all ready.
159 unsigned RemovedElements = 0;
160 for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
165 // Check if this instruction is now ready. In case, force
166 // a transition in state using method 'updateDispatched()'.
167 Instruction &IS = *IR.getInstruction();
168 if (IS.isDispatched() && !IS.updateDispatched()) {
173 if (IS.isMemOp() && LSU.isWaiting(IR)) {
178 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
179 << " promoted to the PENDING set.\n");
181 Pending.emplace_back(IR);
182 PendingSet.emplace_back(IR);
186 std::iter_swap(I, E - RemovedElements);
189 WaitSet.resize(WaitSet.size() - RemovedElements);
190 return RemovedElements;
193 InstRef Scheduler::select() {
194 unsigned QueueIndex = ReadySet.size();
195 for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
196 InstRef &IR = ReadySet[I];
197 if (QueueIndex == ReadySet.size() ||
198 Strategy->compare(IR, ReadySet[QueueIndex])) {
199 Instruction &IS = *IR.getInstruction();
200 uint64_t BusyResourceMask = Resources->checkAvailability(IS.getDesc());
201 if (BusyResourceMask)
202 IS.setCriticalResourceMask(BusyResourceMask);
203 BusyResourceUnits |= BusyResourceMask;
204 if (!BusyResourceMask)
209 if (QueueIndex == ReadySet.size())
212 // We found an instruction to issue.
213 InstRef IR = ReadySet[QueueIndex];
214 std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
219 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
220 unsigned RemovedElements = 0;
221 for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
225 Instruction &IS = *IR.getInstruction();
226 if (!IS.isExecuted()) {
227 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
228 << " is still executing.\n");
233 // Instruction IR has completed execution.
234 LSU.onInstructionExecuted(IR);
235 Executed.emplace_back(IR);
238 std::iter_swap(I, E - RemovedElements);
241 IssuedSet.resize(IssuedSet.size() - RemovedElements);
244 uint64_t Scheduler::analyzeResourcePressure(SmallVectorImpl<InstRef> &Insts) {
245 Insts.insert(Insts.end(), ReadySet.begin(), ReadySet.end());
246 return BusyResourceUnits;
249 void Scheduler::analyzeDataDependencies(SmallVectorImpl<InstRef> &RegDeps,
250 SmallVectorImpl<InstRef> &MemDeps) {
251 const auto EndIt = PendingSet.end() - NumDispatchedToThePendingSet;
252 for (const InstRef &IR : make_range(PendingSet.begin(), EndIt)) {
253 const Instruction &IS = *IR.getInstruction();
254 if (Resources->checkAvailability(IS.getDesc()))
257 if (IS.isMemOp() && LSU.isPending(IR))
258 MemDeps.emplace_back(IR);
261 RegDeps.emplace_back(IR);
265 void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
266 SmallVectorImpl<InstRef> &Executed,
267 SmallVectorImpl<InstRef> &Pending,
268 SmallVectorImpl<InstRef> &Ready) {
271 // Release consumed resources.
272 Resources->cycleEvent(Freed);
274 for (InstRef &IR : IssuedSet)
275 IR.getInstruction()->cycleEvent();
276 updateIssuedSet(Executed);
278 for (InstRef &IR : PendingSet)
279 IR.getInstruction()->cycleEvent();
281 for (InstRef &IR : WaitSet)
282 IR.getInstruction()->cycleEvent();
284 promoteToPendingSet(Pending);
285 promoteToReadySet(Ready);
287 NumDispatchedToThePendingSet = 0;
288 BusyResourceUnits = 0;
291 bool Scheduler::mustIssueImmediately(const InstRef &IR) const {
292 const InstrDesc &Desc = IR.getInstruction()->getDesc();
293 if (Desc.isZeroLatency())
295 // Instructions that use an in-order dispatch/issue processor resource must be
296 // issued immediately to the pipeline(s). Any other in-order buffered
297 // resources (i.e. BufferSize=1) is consumed.
298 return Desc.MustIssueImmediately;
301 bool Scheduler::dispatch(InstRef &IR) {
302 Instruction &IS = *IR.getInstruction();
303 const InstrDesc &Desc = IS.getDesc();
304 Resources->reserveBuffers(Desc.Buffers);
306 // If necessary, reserve queue entries in the load-store unit (LSU).
308 IS.setLSUTokenID(LSU.dispatch(IR));
310 if (IS.isDispatched() || (IS.isMemOp() && LSU.isWaiting(IR))) {
311 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
312 WaitSet.push_back(IR);
316 if (IS.isPending() || (IS.isMemOp() && LSU.isPending(IR))) {
317 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
318 << " to the PendingSet\n");
319 PendingSet.push_back(IR);
320 ++NumDispatchedToThePendingSet;
324 assert(IS.isReady() && (!IS.isMemOp() || LSU.isReady(IR)) &&
325 "Unexpected internal state found!");
326 // Don't add a zero-latency instruction to the Ready queue.
327 // A zero-latency instruction doesn't consume any scheduler resources. That is
328 // because it doesn't need to be executed, and it is often removed at register
329 // renaming stage. For example, register-register moves are often optimized at
330 // register renaming stage by simply updating register aliases. On some
331 // targets, zero-idiom instructions (for example: a xor that clears the value
332 // of a register) are treated specially, and are often eliminated at register
334 if (!mustIssueImmediately(IR)) {
335 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
336 ReadySet.push_back(IR);