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