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
23namespace llvm {
24namespace mca {
25
26HWStallEvent::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
43bool 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
53Error 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
80Error 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
93Error 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
122Error 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
161static 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
173Error 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.
186Error 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
227void 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
233void 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
239void 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
245void 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
252void 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
271void 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