1 //===---------------------- ExecuteStage.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 /// \file
9 ///
10 /// This file defines the execution stage of an instruction pipeline.
11 ///
12 /// The ExecuteStage is responsible for managing the hardware scheduler
13 /// and issuing notifications that an instruction has been executed.
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/MCA/Stages/ExecuteStage.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Support/Debug.h"
20 
21 #define DEBUG_TYPE "llvm-mca"
22 
23 namespace llvm {
24 namespace mca {
25 
26 HWStallEvent::GenericEventType toHWStallEventType(Scheduler::Status Status) {
27   switch (Status) {
28   case Scheduler::SC_LOAD_QUEUE_FULL:
29     return HWStallEvent::LoadQueueFull;
30   case Scheduler::SC_STORE_QUEUE_FULL:
31     return HWStallEvent::StoreQueueFull;
32   case Scheduler::SC_BUFFERS_FULL:
33     return HWStallEvent::SchedulerQueueFull;
34   case Scheduler::SC_DISPATCH_GROUP_STALL:
35     return HWStallEvent::DispatchGroupStall;
36   case Scheduler::SC_AVAILABLE:
37     return HWStallEvent::Invalid;
38   }
39 
40   llvm_unreachable("Don't know how to process this StallKind!");
41 }
42 
43 bool ExecuteStage::isAvailable(const InstRef &IR) const {
44   if (Scheduler::Status S = HWS.isAvailable(IR)) {
45     HWStallEvent::GenericEventType ET = toHWStallEventType(S);
46     notifyEvent<HWStallEvent>(HWStallEvent(ET, IR));
47     return false;
48   }
49 
50   return true;
51 }
52 
53 Error ExecuteStage::issueInstruction(InstRef &IR) {
54   SmallVector<ResourceUse, 4> Used;
55   SmallVector<InstRef, 4> Pending;
56   SmallVector<InstRef, 4> Ready;
57 
58   HWS.issueInstruction(IR, Used, Pending, Ready);
59   Instruction &IS = *IR.getInstruction();
60   NumIssuedOpcodes += IS.getNumMicroOps();
61 
62   notifyReservedOrReleasedBuffers(IR, /* Reserved */ false);
63 
64   notifyInstructionIssued(IR, Used);
65   if (IS.isExecuted()) {
66     notifyInstructionExecuted(IR);
67     // FIXME: add a buffer of executed instructions.
68     if (Error S = moveToTheNextStage(IR))
69       return S;
70   }
71 
72   for (const InstRef &I : Pending)
73     notifyInstructionPending(I);
74 
75   for (const InstRef &I : Ready)
76     notifyInstructionReady(I);
77   return ErrorSuccess();
78 }
79 
80 Error ExecuteStage::issueReadyInstructions() {
81   InstRef IR = HWS.select();
82   while (IR) {
83     if (Error Err = issueInstruction(IR))
84       return Err;
85 
86     // Select the next instruction to issue.
87     IR = HWS.select();
88   }
89 
90   return ErrorSuccess();
91 }
92 
93 Error ExecuteStage::cycleStart() {
94   SmallVector<ResourceRef, 8> Freed;
95   SmallVector<InstRef, 4> Executed;
96   SmallVector<InstRef, 4> Pending;
97   SmallVector<InstRef, 4> Ready;
98 
99   HWS.cycleEvent(Freed, Executed, Pending, Ready);
100   NumDispatchedOpcodes = 0;
101   NumIssuedOpcodes = 0;
102 
103   for (const ResourceRef &RR : Freed)
104     notifyResourceAvailable(RR);
105 
106   for (InstRef &IR : Executed) {
107     notifyInstructionExecuted(IR);
108     // FIXME: add a buffer of executed instructions.
109     if (Error S = moveToTheNextStage(IR))
110       return S;
111   }
112 
113   for (const InstRef &IR : Pending)
114     notifyInstructionPending(IR);
115 
116   for (const InstRef &IR : Ready)
117     notifyInstructionReady(IR);
118 
119   return issueReadyInstructions();
120 }
121 
122 Error ExecuteStage::cycleEnd() {
123   if (!EnablePressureEvents)
124     return ErrorSuccess();
125 
126   // Always conservatively report any backpressure events if the dispatch logic
127   // was stalled due to unavailable scheduler resources.
128   if (!HWS.hadTokenStall() && NumDispatchedOpcodes <= NumIssuedOpcodes)
129     return ErrorSuccess();
130 
131   SmallVector<InstRef, 8> Insts;
132   uint64_t Mask = HWS.analyzeResourcePressure(Insts);
133   if (Mask) {
134     LLVM_DEBUG(dbgs() << "[E] Backpressure increased because of unavailable "
135                          "pipeline resources: "
136                       << format_hex(Mask, 16) << '\n');
137     HWPressureEvent Ev(HWPressureEvent::RESOURCES, Insts, Mask);
138     notifyEvent(Ev);
139   }
140 
141   SmallVector<InstRef, 8> RegDeps;
142   SmallVector<InstRef, 8> MemDeps;
143   HWS.analyzeDataDependencies(RegDeps, MemDeps);
144   if (RegDeps.size()) {
145     LLVM_DEBUG(
146         dbgs() << "[E] Backpressure increased by register dependencies\n");
147     HWPressureEvent Ev(HWPressureEvent::REGISTER_DEPS, RegDeps);
148     notifyEvent(Ev);
149   }
150 
151   if (MemDeps.size()) {
152     LLVM_DEBUG(dbgs() << "[E] Backpressure increased by memory dependencies\n");
153     HWPressureEvent Ev(HWPressureEvent::MEMORY_DEPS, MemDeps);
154     notifyEvent(Ev);
155   }
156 
157   return ErrorSuccess();
158 }
159 
160 #ifndef NDEBUG
161 static void verifyInstructionEliminated(const InstRef &IR) {
162   const Instruction &Inst = *IR.getInstruction();
163   assert(Inst.isEliminated() && "Instruction was not eliminated!");
164   assert(Inst.isReady() && "Instruction in an inconsistent state!");
165 
166   // Ensure that instructions eliminated at register renaming stage are in a
167   // consistent state.
168   assert(!Inst.getMayLoad() && !Inst.getMayStore() &&
169          "Cannot eliminate a memory op!");
170 }
171 #endif
172 
173 Error ExecuteStage::handleInstructionEliminated(InstRef &IR) {
174 #ifndef NDEBUG
175   verifyInstructionEliminated(IR);
176 #endif
177   notifyInstructionPending(IR);
178   notifyInstructionReady(IR);
179   notifyInstructionIssued(IR, {});
180   IR.getInstruction()->forceExecuted();
181   notifyInstructionExecuted(IR);
182   return moveToTheNextStage(IR);
183 }
184 
185 // Schedule the instruction for execution on the hardware.
186 Error ExecuteStage::execute(InstRef &IR) {
187   assert(isAvailable(IR) && "Scheduler is not available!");
188 
189 #ifndef NDEBUG
190   // Ensure that the HWS has not stored this instruction in its queues.
191   HWS.instructionCheck(IR);
192 #endif
193 
194   if (IR.getInstruction()->isEliminated())
195     return handleInstructionEliminated(IR);
196 
197   // Reserve a slot in each buffered resource. Also, mark units with
198   // BufferSize=0 as reserved. Resources with a buffer size of zero will only
199   // be released after MCIS is issued, and all the ResourceCycles for those
200   // units have been consumed.
201   bool IsReadyInstruction = HWS.dispatch(IR);
202   const Instruction &Inst = *IR.getInstruction();
203   unsigned NumMicroOps = Inst.getNumMicroOps();
204   NumDispatchedOpcodes += NumMicroOps;
205   notifyReservedOrReleasedBuffers(IR, /* Reserved */ true);
206 
207   if (!IsReadyInstruction) {
208     if (Inst.isPending())
209       notifyInstructionPending(IR);
210     return ErrorSuccess();
211   }
212 
213   notifyInstructionPending(IR);
214 
215   // If we did not return early, then the scheduler is ready for execution.
216   notifyInstructionReady(IR);
217 
218   // If we cannot issue immediately, the HWS will add IR to its ready queue for
219   // execution later, so we must return early here.
220   if (!HWS.mustIssueImmediately(IR))
221     return ErrorSuccess();
222 
223   // Issue IR to the underlying pipelines.
224   return issueInstruction(IR);
225 }
226 
227 void ExecuteStage::notifyInstructionExecuted(const InstRef &IR) const {
228   LLVM_DEBUG(dbgs() << "[E] Instruction Executed: #" << IR << '\n');
229   notifyEvent<HWInstructionEvent>(
230       HWInstructionEvent(HWInstructionEvent::Executed, IR));
231 }
232 
233 void ExecuteStage::notifyInstructionPending(const InstRef &IR) const {
234   LLVM_DEBUG(dbgs() << "[E] Instruction Pending: #" << IR << '\n');
235   notifyEvent<HWInstructionEvent>(
236       HWInstructionEvent(HWInstructionEvent::Pending, IR));
237 }
238 
239 void ExecuteStage::notifyInstructionReady(const InstRef &IR) const {
240   LLVM_DEBUG(dbgs() << "[E] Instruction Ready: #" << IR << '\n');
241   notifyEvent<HWInstructionEvent>(
242       HWInstructionEvent(HWInstructionEvent::Ready, IR));
243 }
244 
245 void ExecuteStage::notifyResourceAvailable(const ResourceRef &RR) const {
246   LLVM_DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.'
247                     << RR.second << "]\n");
248   for (HWEventListener *Listener : getListeners())
249     Listener->onResourceAvailable(RR);
250 }
251 
252 void ExecuteStage::notifyInstructionIssued(
253     const InstRef &IR, MutableArrayRef<ResourceUse> Used) const {
254   LLVM_DEBUG({
255     dbgs() << "[E] Instruction Issued: #" << IR << '\n';
256     for (const ResourceUse &Use : Used) {
257       assert(Use.second.getDenominator() == 1 && "Invalid cycles!");
258       dbgs() << "[E] Resource Used: [" << Use.first.first << '.'
259              << Use.first.second << "], ";
260       dbgs() << "cycles: " << Use.second.getNumerator() << '\n';
261     }
262   });
263 
264   // Replace resource masks with valid resource processor IDs.
265   for (ResourceUse &Use : Used)
266     Use.first.first = HWS.getResourceID(Use.first.first);
267 
268   notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, Used));
269 }
270 
271 void ExecuteStage::notifyReservedOrReleasedBuffers(const InstRef &IR,
272                                                    bool Reserved) const {
273   uint64_t UsedBuffers = IR.getInstruction()->getDesc().UsedBuffers;
274   if (!UsedBuffers)
275     return;
276 
277   SmallVector<unsigned, 4> BufferIDs(llvm::popcount(UsedBuffers), 0);
278   for (unsigned I = 0, E = BufferIDs.size(); I < E; ++I) {
279     uint64_t CurrentBufferMask = UsedBuffers & (-UsedBuffers);
280     BufferIDs[I] = HWS.getResourceID(CurrentBufferMask);
281     UsedBuffers ^= CurrentBufferMask;
282   }
283 
284   if (Reserved) {
285     for (HWEventListener *Listener : getListeners())
286       Listener->onReservedBuffers(IR, BufferIDs);
287     return;
288   }
289 
290   for (HWEventListener *Listener : getListeners())
291     Listener->onReleasedBuffers(IR, BufferIDs);
292 }
293 
294 } // namespace mca
295 } // namespace llvm
296