LLVM  9.0.0svn
ExecuteStage.cpp
Go to the documentation of this file.
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 
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 
27  switch (Status) {
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)) {
46  notifyEvent<HWStallEvent>(HWStallEvent(ET, IR));
47  return false;
48  }
49 
50  return true;
51 }
52 
53 Error ExecuteStage::issueInstruction(InstRef &IR) {
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()) {
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)
73 
74  for (const InstRef &I : Ready)
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 
94  SmallVector<InstRef, 4> Executed;
97 
98  HWS.cycleEvent(Freed, Executed, Pending, Ready);
99  NumDispatchedOpcodes = 0;
100  NumIssuedOpcodes = 0;
101 
102  for (const ResourceRef &RR : Freed)
104 
105  for (InstRef &IR : Executed) {
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)
114 
115  for (const InstRef &IR : Ready)
117 
118  return issueReadyInstructions();
119 }
120 
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 
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');
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");
147  notifyEvent(Ev);
148  }
149 
150  if (MemDeps.size()) {
151  LLVM_DEBUG(dbgs() << "[E] Backpressure increased by memory dependencies\n");
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
175 #endif
178  notifyInstructionIssued(IR, {});
181  return moveToTheNextStage(IR);
182 }
183 
184 // Schedule the instruction for execution on the hardware.
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())
208  return ErrorSuccess();
209  }
210 
212 
213  // If we did not return early, then the scheduler is ready for execution.
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 
226  LLVM_DEBUG(dbgs() << "[E] Instruction Executed: #" << IR << '\n');
227  notifyEvent<HWInstructionEvent>(
229 }
230 
232  LLVM_DEBUG(dbgs() << "[E] Instruction Pending: #" << IR << '\n');
233  notifyEvent<HWInstructionEvent>(
235 }
236 
238  LLVM_DEBUG(dbgs() << "[E] Instruction Ready: #" << IR << '\n');
239  notifyEvent<HWInstructionEvent>(
241 }
242 
244  LLVM_DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.'
245  << RR.second << "]\n");
246  for (HWEventListener *Listener : getListeners())
247  Listener->onResourceAvailable(RR);
248 }
249 
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 
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
Instruction * getInstruction()
Definition: Instruction.h:531
void notifyEvent(const EventT &Event) const
Notify listeners of a particular hardware event.
Definition: Stage.h:79
void notifyInstructionPending(const InstRef &IR) const
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:430
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void sanityCheck(const InstRef &IR) const
Definition: Scheduler.h:262
Status isAvailable(const InstRef &IR)
Check if the instruction in &#39;IR&#39; can be dispatched during this cycle.
Definition: Scheduler.cpp:40
FormattedNumber format_hex(uint64_t N, unsigned Width, bool Upper=false)
format_hex - Output N as a fixed width hexadecimal.
Definition: Format.h:185
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:92
SmallVector< uint64_t, 4 > Buffers
Definition: Instruction.h:346
const std::set< HWEventListener * > & getListeners() const
Definition: Stage.h:35
Subclass of Error for the sole purpose of identifying the success path in the type system...
Definition: Error.h:324
void notifyInstructionReady(const InstRef &IR) const
InstRef select()
Select the next instruction to issue from the ReadySet.
Definition: Scheduler.cpp:182
bool isAvailable(const InstRef &IR) const override
Returns true if it can execute IR during this cycle.
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:521
Error cycleStart() override
Called once at the start of each cycle.
HWStallEvent::GenericEventType toHWStallEventType(Scheduler::Status Status)
void notifyResourceAvailable(const ResourceRef &RR) const
This file defines the execution stage of a default instruction pipeline.
unsigned getResourceID(uint64_t Mask) const
Convert a resource mask into a valid llvm processor resource identifier.
Definition: Scheduler.h:227
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
static void verifyInstructionEliminated(const InstRef &IR)
bool isEliminated() const
Definition: Instruction.h:497
void notifyInstructionIssued(const InstRef &IR, MutableArrayRef< std::pair< ResourceRef, ResourceCycles >> Used) const
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:254
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:232
const InstrDesc & getDesc() const
Definition: Instruction.h:404
Error cycleEnd() override
Called once at the end of each cycle.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:290
void notifyReservedOrReleasedBuffers(const InstRef &IR, bool Reserved) const
bool dispatch(const InstRef &IR)
Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.
Definition: Scheduler.cpp:288
std::pair< uint64_t, uint64_t > ResourceRef
A resource unit identifier.
size_t size() const
Definition: SmallVector.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void notifyInstructionExecuted(const InstRef &IR) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isReady() const
Definition: Instruction.h:493
bool hadTokenStall() const
Definition: Scheduler.h:254
Error moveToTheNextStage(InstRef &IR)
Called when an instruction is ready to move the next pipeline stage.
Definition: Stage.h:70
An instruction descriptor.
Definition: Instruction.h:337
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:278
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:237
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
bool isPending() const
Definition: Instruction.h:492
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere...
Definition: STLExtras.h:1267
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
bool isExecuted() const
Definition: Instruction.h:495
Error execute(InstRef &IR) override
The primary action that this stage performs on instruction IR.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Statically lint checks LLVM IR
Definition: Lint.cpp:192