LLVM 17.0.0git
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
17namespace llvm {
18namespace mca {
19
20#define DEBUG_TYPE "llvm-mca"
21
22void Scheduler::initializeStrategy(std::unique_ptr<SchedulerStrategy> S) {
23 // Ensure we have a valid (non-null) strategy object.
24 Strategy = S ? std::move(S) : std::make_unique<DefaultSchedulerStrategy>();
25}
26
27// Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy.
30
31#ifndef NDEBUG
32void 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
42 Resources->canBeDispatched(IR.getInstruction()->getUsedBuffers());
43 HadTokenStall = RSE != RS_BUFFER_AVAILABLE;
44
45 switch (RSE) {
51 break;
52 }
53
54 // Give lower priority to LSUnit stall events.
55 LSUnit::Status LSS = LSU.isAvailable(IR);
56 HadTokenStall = LSS != LSUnit::LSU_AVAILABLE;
57
58 switch (LSS) {
65 }
66
67 llvm_unreachable("Don't know how to process this LSU state result!");
68}
69
70void Scheduler::issueInstructionImpl(
71 InstRef &IR,
72 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
73 Instruction *IS = IR.getInstruction();
74 const InstrDesc &D = IS->getDesc();
75
76 // Issue the instruction and collect all the consumed resources
77 // into a vector. That vector is then used to notify the listener.
78 Resources->issueInstruction(D, UsedResources);
79
80 // Notify the instruction that it started executing.
81 // This updates the internal state of each write.
82 IS->execute(IR.getSourceIndex());
83
85
86 if (IS->isMemOp()) {
88 const MemoryGroup &Group = LSU.getGroup(IS->getLSUTokenID());
90 }
91
92 if (IS->isExecuting())
93 IssuedSet.emplace_back(IR);
94 else if (IS->isExecuted())
96}
97
98// Release the buffered resources and issue the instruction.
100 InstRef &IR,
101 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
102 SmallVectorImpl<InstRef> &PendingInstructions,
103 SmallVectorImpl<InstRef> &ReadyInstructions) {
104 const Instruction &Inst = *IR.getInstruction();
105 bool HasDependentUsers = Inst.hasDependentUsers();
106 HasDependentUsers |= Inst.isMemOp() && LSU.hasDependentUsers(IR);
107
108 Resources->releaseBuffers(Inst.getUsedBuffers());
109 issueInstructionImpl(IR, UsedResources);
110 // Instructions that have been issued during this cycle might have unblocked
111 // other dependent instructions. Dependent instructions may be issued during
112 // this same cycle if operands have ReadAdvance entries. Promote those
113 // instructions to the ReadySet and notify the caller that those are ready.
114 if (HasDependentUsers)
115 if (promoteToPendingSet(PendingInstructions))
116 promoteToReadySet(ReadyInstructions);
117}
118
119bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
120 // Scan the set of waiting instructions and promote them to the
121 // ready set if operands are all ready.
122 unsigned PromotedElements = 0;
123 for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
124 InstRef &IR = *I;
125 if (!IR)
126 break;
127
128 // Check if there are unsolved register dependencies.
129 Instruction &IS = *IR.getInstruction();
130 if (!IS.isReady() && !IS.updatePending()) {
131 ++I;
132 continue;
133 }
134 // Check if there are unsolved memory dependencies.
135 if (IS.isMemOp() && !LSU.isReady(IR)) {
136 ++I;
137 continue;
138 }
139
140 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
141 << " promoted to the READY set.\n");
142
143 Ready.emplace_back(IR);
144 ReadySet.emplace_back(IR);
145
146 IR.invalidate();
147 ++PromotedElements;
148 std::iter_swap(I, E - PromotedElements);
149 }
150
151 PendingSet.resize(PendingSet.size() - PromotedElements);
152 return PromotedElements;
153}
154
155bool Scheduler::promoteToPendingSet(SmallVectorImpl<InstRef> &Pending) {
156 // Scan the set of waiting instructions and promote them to the
157 // pending set if operands are all ready.
158 unsigned RemovedElements = 0;
159 for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
160 InstRef &IR = *I;
161 if (!IR)
162 break;
163
164 // Check if this instruction is now ready. In case, force
165 // a transition in state using method 'updateDispatched()'.
166 Instruction &IS = *IR.getInstruction();
167 if (IS.isDispatched() && !IS.updateDispatched()) {
168 ++I;
169 continue;
170 }
171
172 if (IS.isMemOp() && LSU.isWaiting(IR)) {
173 ++I;
174 continue;
175 }
176
177 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
178 << " promoted to the PENDING set.\n");
179
180 Pending.emplace_back(IR);
181 PendingSet.emplace_back(IR);
182
183 IR.invalidate();
184 ++RemovedElements;
185 std::iter_swap(I, E - RemovedElements);
186 }
187
188 WaitSet.resize(WaitSet.size() - RemovedElements);
189 return RemovedElements;
190}
191
193 unsigned QueueIndex = ReadySet.size();
194 for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
195 InstRef &IR = ReadySet[I];
196 if (QueueIndex == ReadySet.size() ||
197 Strategy->compare(IR, ReadySet[QueueIndex])) {
198 Instruction &IS = *IR.getInstruction();
199 uint64_t BusyResourceMask = Resources->checkAvailability(IS.getDesc());
200 if (BusyResourceMask)
201 IS.setCriticalResourceMask(BusyResourceMask);
202 BusyResourceUnits |= BusyResourceMask;
203 if (!BusyResourceMask)
204 QueueIndex = I;
205 }
206 }
207
208 if (QueueIndex == ReadySet.size())
209 return InstRef();
210
211 // We found an instruction to issue.
212 InstRef IR = ReadySet[QueueIndex];
213 std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
214 ReadySet.pop_back();
215 return IR;
216}
217
218void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
219 unsigned RemovedElements = 0;
220 for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
221 InstRef &IR = *I;
222 if (!IR)
223 break;
224 Instruction &IS = *IR.getInstruction();
225 if (!IS.isExecuted()) {
226 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
227 << " is still executing.\n");
228 ++I;
229 continue;
230 }
231
232 // Instruction IR has completed execution.
234 Executed.emplace_back(IR);
235 ++RemovedElements;
236 IR.invalidate();
237 std::iter_swap(I, E - RemovedElements);
238 }
239
240 IssuedSet.resize(IssuedSet.size() - RemovedElements);
241}
242
244 llvm::append_range(Insts, ReadySet);
245 return BusyResourceUnits;
246}
247
249 SmallVectorImpl<InstRef> &MemDeps) {
250 const auto EndIt = PendingSet.end() - NumDispatchedToThePendingSet;
251 for (const InstRef &IR : make_range(PendingSet.begin(), EndIt)) {
252 const Instruction &IS = *IR.getInstruction();
253 if (Resources->checkAvailability(IS.getDesc()))
254 continue;
255
256 if (IS.isMemOp() && LSU.isPending(IR))
257 MemDeps.emplace_back(IR);
258
259 if (IS.isPending())
260 RegDeps.emplace_back(IR);
261 }
262}
263
265 SmallVectorImpl<InstRef> &Executed,
268 LSU.cycleEvent();
269
270 // Release consumed resources.
271 Resources->cycleEvent(Freed);
272
273 for (InstRef &IR : IssuedSet)
274 IR.getInstruction()->cycleEvent();
275 updateIssuedSet(Executed);
276
277 for (InstRef &IR : PendingSet)
278 IR.getInstruction()->cycleEvent();
279
280 for (InstRef &IR : WaitSet)
281 IR.getInstruction()->cycleEvent();
282
283 promoteToPendingSet(Pending);
284 promoteToReadySet(Ready);
285
286 NumDispatchedToThePendingSet = 0;
287 BusyResourceUnits = 0;
288}
289
291 const InstrDesc &Desc = IR.getInstruction()->getDesc();
292 if (Desc.isZeroLatency())
293 return true;
294 // Instructions that use an in-order dispatch/issue processor resource must be
295 // issued immediately to the pipeline(s). Any other in-order buffered
296 // resources (i.e. BufferSize=1) is consumed.
297 return Desc.MustIssueImmediately;
298}
299
301 Instruction &IS = *IR.getInstruction();
302 Resources->reserveBuffers(IS.getUsedBuffers());
303
304 // If necessary, reserve queue entries in the load-store unit (LSU).
305 if (IS.isMemOp())
306 IS.setLSUTokenID(LSU.dispatch(IR));
307
308 if (IS.isDispatched() || (IS.isMemOp() && LSU.isWaiting(IR))) {
309 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
310 WaitSet.push_back(IR);
311 return false;
312 }
313
314 if (IS.isPending() || (IS.isMemOp() && LSU.isPending(IR))) {
315 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
316 << " to the PendingSet\n");
317 PendingSet.push_back(IR);
318 ++NumDispatchedToThePendingSet;
319 return false;
320 }
321
322 assert(IS.isReady() && (!IS.isMemOp() || LSU.isReady(IR)) &&
323 "Unexpected internal state found!");
324 // Don't add a zero-latency instruction to the Ready queue.
325 // A zero-latency instruction doesn't consume any scheduler resources. That is
326 // because it doesn't need to be executed, and it is often removed at register
327 // renaming stage. For example, register-register moves are often optimized at
328 // register renaming stage by simply updating register aliases. On some
329 // targets, zero-idiom instructions (for example: a xor that clears the value
330 // of a register) are treated specially, and are often eliminated at register
331 // renaming stage.
332 if (!mustIssueImmediately(IR)) {
333 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
334 ReadySet.push_back(IR);
335 }
336
337 return true;
338}
339
340} // namespace mca
341} // namespace llvm
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Statically lint checks LLVM IR
Definition: Lint.cpp:746
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A scheduler for Processor Resource Units and Processor Resource Groups.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:720
const InstrDesc & getDesc() const
Definition: Instruction.h:539
bool hasDependentUsers() const
Definition: Instruction.h:562
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:600
bool isDispatched() const
Definition: Instruction.h:685
bool isExecuted() const
Definition: Instruction.h:689
bool isExecuting() const
Definition: Instruction.h:688
void setCriticalResourceMask(uint64_t ResourceMask)
Definition: Instruction.h:710
bool isReady() const
Definition: Instruction.h:687
const CriticalDependency & computeCriticalRegDep()
void execute(unsigned IID)
void setLSUTokenID(unsigned LSUTok)
Definition: Instruction.h:657
void setCriticalMemDep(const CriticalDependency &MemDep)
Definition: Instruction.h:705
uint64_t getUsedBuffers() const
Definition: Instruction.h:659
bool isPending() const
Definition: Instruction.h:686
unsigned getLSUTokenID() const
Definition: Instruction.h:656
virtual unsigned dispatch(const InstRef &IR)=0
Allocates LS resources for instruction IR.
virtual void onInstructionExecuted(const InstRef &IR)
Definition: LSUnit.cpp:205
bool isWaiting(const InstRef &IR) const
Check if instruction IR is still waiting on memory operations, and the wait time is still unknown.
Definition: LSUnit.h:292
virtual void onInstructionIssued(const InstRef &IR)
Definition: LSUnit.h:328
const MemoryGroup & getGroup(unsigned Index) const
Definition: LSUnit.h:304
bool isPending(const InstRef &IR) const
Check if instruction IR only depends on memory instructions that are currently executing.
Definition: LSUnit.h:284
virtual Status isAvailable(const InstRef &IR) const =0
This method checks the availability of the load/store buffers.
virtual void cycleEvent()
Definition: LSUnit.cpp:44
bool hasDependentUsers(const InstRef &IR) const
Definition: LSUnit.h:298
bool isReady(const InstRef &IR) const
Check if a peviously dispatched instruction IR is now ready for execution.
Definition: LSUnit.h:276
A node of a memory dependency graph.
Definition: LSUnit.h:35
const CriticalDependency & getCriticalPredecessor() const
Definition: LSUnit.h:78
InstRef select()
Select the next instruction to issue from the ReadySet.
Definition: Scheduler.cpp:192
Status isAvailable(const InstRef &IR)
Check if the instruction in 'IR' can be dispatched during this cycle.
Definition: Scheduler.cpp:40
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:248
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:99
bool dispatch(InstRef &IR)
Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.
Definition: Scheduler.cpp:300
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:264
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:290
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:243
void dump() const
Definition: Scheduler.cpp:32
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ResourceStateEvent
Used to notify the internal state of a processor resource.
@ RS_BUFFER_UNAVAILABLE
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
An instruction descriptor.
Definition: Instruction.h:447
bool isZeroLatency() const
Definition: Instruction.h:485
unsigned MustIssueImmediately
Definition: Instruction.h:474