LLVM  10.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  Instruction &IS = *IR.getInstruction();
60  NumIssuedOpcodes += IS.getNumMicroOps();
61 
62  notifyReservedOrReleasedBuffers(IR, /* Reserved */ false);
63 
64  notifyInstructionIssued(IR, Used);
65  if (IS.isExecuted()) {
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)
74 
75  for (const InstRef &I : Ready)
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 
95  SmallVector<InstRef, 4> Executed;
98 
99  HWS.cycleEvent(Freed, Executed, Pending, Ready);
100  NumDispatchedOpcodes = 0;
101  NumIssuedOpcodes = 0;
102 
103  for (const ResourceRef &RR : Freed)
105 
106  for (InstRef &IR : Executed) {
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)
115 
116  for (const InstRef &IR : Ready)
118 
119  return issueReadyInstructions();
120 }
121 
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 
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');
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");
148  notifyEvent(Ev);
149  }
150 
151  if (MemDeps.size()) {
152  LLVM_DEBUG(dbgs() << "[E] Backpressure increased by memory dependencies\n");
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  const InstrDesc &Desc = Inst.getDesc();
169  assert(!Desc.MayLoad && !Desc.MayStore && "Cannot eliminate a memory op!");
170 }
171 #endif
172 
173 Error ExecuteStage::handleInstructionEliminated(InstRef &IR) {
174 #ifndef NDEBUG
176 #endif
179  notifyInstructionIssued(IR, {});
182  return moveToTheNextStage(IR);
183 }
184 
185 // Schedule the instruction for execution on the hardware.
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.sanityCheck(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())
210  return ErrorSuccess();
211  }
212 
214 
215  // If we did not return early, then the scheduler is ready for execution.
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 
228  LLVM_DEBUG(dbgs() << "[E] Instruction Executed: #" << IR << '\n');
229  notifyEvent<HWInstructionEvent>(
231 }
232 
234  LLVM_DEBUG(dbgs() << "[E] Instruction Pending: #" << IR << '\n');
235  notifyEvent<HWInstructionEvent>(
237 }
238 
240  LLVM_DEBUG(dbgs() << "[E] Instruction Ready: #" << IR << '\n');
241  notifyEvent<HWInstructionEvent>(
243 }
244 
246  LLVM_DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.'
247  << RR.second << "]\n");
248  for (HWEventListener *Listener : getListeners())
249  Listener->onResourceAvailable(RR);
250 }
251 
253  const InstRef &IR,
254  MutableArrayRef<std::pair<ResourceRef, ResourceCycles>> Used) const {
255  LLVM_DEBUG({
256  dbgs() << "[E] Instruction Issued: #" << IR << '\n';
257  for (const std::pair<ResourceRef, ResourceCycles> &Resource : Used) {
258  assert(Resource.second.getDenominator() == 1 && "Invalid cycles!");
259  dbgs() << "[E] Resource Used: [" << Resource.first.first << '.'
260  << Resource.first.second << "], ";
261  dbgs() << "cycles: " << Resource.second.getNumerator() << '\n';
262  }
263  });
264 
265  // Replace resource masks with valid resource processor IDs.
266  for (std::pair<ResourceRef, ResourceCycles> &Use : Used)
267  Use.first.first = HWS.getResourceID(Use.first.first);
268 
269  notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, Used));
270 }
271 
273  bool Reserved) const {
274  uint64_t UsedBuffers = IR.getInstruction()->getDesc().UsedBuffers;
275  if (!UsedBuffers)
276  return;
277 
278  SmallVector<unsigned, 4> BufferIDs(countPopulation(UsedBuffers), 0);
279  for (unsigned I = 0, E = BufferIDs.size(); I < E; ++I) {
280  uint64_t CurrentBufferMask = UsedBuffers & (-UsedBuffers);
281  BufferIDs[I] = HWS.getResourceID(CurrentBufferMask);
282  UsedBuffers ^= CurrentBufferMask;
283  }
284 
285  if (Reserved) {
286  for (HWEventListener *Listener : getListeners())
287  Listener->onReservedBuffers(IR, BufferIDs);
288  return;
289  }
290 
291  for (HWEventListener *Listener : getListeners())
292  Listener->onReleasedBuffers(IR, BufferIDs);
293 }
294 
295 } // namespace mca
296 } // namespace llvm
Instruction * getInstruction()
Definition: Instruction.h:576
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:445
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void sanityCheck(const InstRef &IR) const
Definition: Scheduler.h:269
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:186
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
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:192
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:562
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:234
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:533
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:264
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
unsigned getNumMicroOps() const
Definition: Instruction.h:421
const InstrDesc & getDesc() const
Definition: Instruction.h:418
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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void notifyReservedOrReleasedBuffers(const InstRef &IR, bool Reserved) const
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
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:519
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
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:529
bool hadTokenStall() const
Definition: Scheduler.h:261
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:348
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
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
#define I(x, y, z)
Definition: MD5.cpp:58
bool isPending() const
Definition: Instruction.h:528
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:531
bool dispatch(InstRef &IR)
Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.
Definition: Scheduler.cpp:300
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