LLVM 19.0.0git
InOrderIssueStage.cpp
Go to the documentation of this file.
1//===---------------------- InOrderIssueStage.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/// InOrderIssueStage implements an in-order execution pipeline.
11///
12//===----------------------------------------------------------------------===//
13
19
20#define DEBUG_TYPE "llvm-mca"
21namespace llvm {
22namespace mca {
23
25 IR.invalidate();
26 CyclesLeft = 0;
28}
29
30void StallInfo::update(const InstRef &Inst, unsigned Cycles, StallKind SK) {
31 IR = Inst;
32 CyclesLeft = Cycles;
33 Kind = SK;
34}
35
37 if (!isValid())
38 return;
39
40 if (!CyclesLeft)
41 return;
42
43 --CyclesLeft;
44}
45
46InOrderIssueStage::InOrderIssueStage(const MCSubtargetInfo &STI,
48 LSUnit &LSU)
49 : STI(STI), PRF(PRF), RM(STI.getSchedModel()), CB(CB), LSU(LSU),
50 NumIssued(), CarryOver(), Bandwidth(), LastWriteBackCycle() {}
51
53 return STI.getSchedModel().IssueWidth;
54}
55
57 return !IssuedInst.empty() || SI.isValid() || CarriedOver;
58}
59
61 if (SI.isValid() || CarriedOver)
62 return false;
63
64 const Instruction &Inst = *IR.getInstruction();
65 unsigned NumMicroOps = Inst.getNumMicroOps();
66
67 bool ShouldCarryOver = NumMicroOps > getIssueWidth();
68 if (Bandwidth < NumMicroOps && !ShouldCarryOver)
69 return false;
70
71 // Instruction with BeginGroup must be the first instruction to be issued in a
72 // cycle.
73 if (Inst.getBeginGroup() && NumIssued != 0)
74 return false;
75
76 return true;
77}
78
79static bool hasResourceHazard(const ResourceManager &RM, const InstRef &IR) {
80 if (RM.checkAvailability(IR.getInstruction()->getDesc())) {
81 LLVM_DEBUG(dbgs() << "[E] Stall #" << IR << '\n');
82 return true;
83 }
84
85 return false;
86}
87
88static unsigned findFirstWriteBackCycle(const InstRef &IR) {
89 unsigned FirstWBCycle = IR.getInstruction()->getLatency();
90 for (const WriteState &WS : IR.getInstruction()->getDefs()) {
91 int CyclesLeft = WS.getCyclesLeft();
92 if (CyclesLeft == UNKNOWN_CYCLES)
93 CyclesLeft = WS.getLatency();
94 if (CyclesLeft < 0)
95 CyclesLeft = 0;
96 FirstWBCycle = std::min(FirstWBCycle, (unsigned)CyclesLeft);
97 }
98 return FirstWBCycle;
99}
100
101/// Return a number of cycles left until register requirements of the
102/// instructions are met.
103static unsigned checkRegisterHazard(const RegisterFile &PRF,
104 const MCSubtargetInfo &STI,
105 const InstRef &IR) {
106 for (const ReadState &RS : IR.getInstruction()->getUses()) {
107 RegisterFile::RAWHazard Hazard = PRF.checkRAWHazards(STI, RS);
108 if (Hazard.isValid())
109 return Hazard.hasUnknownCycles() ? 1U : Hazard.CyclesLeft;
110 }
111
112 return 0;
113}
114
115bool InOrderIssueStage::canExecute(const InstRef &IR) {
116 assert(!SI.getCyclesLeft() && "Should not have reached this code!");
117 assert(!SI.isValid() && "Should not have reached this code!");
118
119 if (unsigned Cycles = checkRegisterHazard(PRF, STI, IR)) {
121 return false;
122 }
123
124 if (hasResourceHazard(RM, IR)) {
125 SI.update(IR, /* delay */ 1, StallInfo::StallKind::DISPATCH);
126 return false;
127 }
128
129 if (IR.getInstruction()->isMemOp() && !LSU.isReady(IR)) {
130 // This load (store) aliases with a preceding store (load). Delay
131 // it until the depenency is cleared.
132 SI.update(IR, /* delay */ 1, StallInfo::StallKind::LOAD_STORE);
133 return false;
134 }
135
136 if (unsigned CustomStallCycles = CB.checkCustomHazard(IssuedInst, IR)) {
137 SI.update(IR, CustomStallCycles, StallInfo::StallKind::CUSTOM_STALL);
138 return false;
139 }
140
141 if (LastWriteBackCycle) {
142 if (!IR.getInstruction()->getRetireOOO()) {
143 unsigned NextWriteBackCycle = findFirstWriteBackCycle(IR);
144 // Delay the instruction to ensure that writes happen in program order.
145 if (NextWriteBackCycle < LastWriteBackCycle) {
146 SI.update(IR, LastWriteBackCycle - NextWriteBackCycle,
148 return false;
149 }
150 }
151 }
152
153 return true;
154}
155
157 unsigned SourceIndex,
158 const MCSubtargetInfo &STI,
159 SmallVectorImpl<unsigned> &UsedRegs) {
160 assert(!IS.isEliminated());
161
162 for (ReadState &RS : IS.getUses())
163 PRF.addRegisterRead(RS, STI);
164
165 for (WriteState &WS : IS.getDefs())
166 PRF.addRegisterWrite(WriteRef(SourceIndex, &WS), UsedRegs);
167}
168
169void InOrderIssueStage::notifyInstructionIssued(const InstRef &IR,
170 ArrayRef<ResourceUse> UsedRes) {
171 notifyEvent<HWInstructionEvent>(
172 HWInstructionEvent(HWInstructionEvent::Ready, IR));
173 notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, UsedRes));
174
175 LLVM_DEBUG(dbgs() << "[E] Issued #" << IR << "\n");
176}
177
178void InOrderIssueStage::notifyInstructionDispatched(
179 const InstRef &IR, unsigned Ops, ArrayRef<unsigned> UsedRegs) {
180 notifyEvent<HWInstructionEvent>(
181 HWInstructionDispatchedEvent(IR, UsedRegs, Ops));
182
183 LLVM_DEBUG(dbgs() << "[E] Dispatched #" << IR << "\n");
184}
185
186void InOrderIssueStage::notifyInstructionExecuted(const InstRef &IR) {
187 notifyEvent<HWInstructionEvent>(
188 HWInstructionEvent(HWInstructionEvent::Executed, IR));
189 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n");
190}
191
192void InOrderIssueStage::notifyInstructionRetired(const InstRef &IR,
193 ArrayRef<unsigned> FreedRegs) {
194 notifyEvent<HWInstructionEvent>(HWInstructionRetiredEvent(IR, FreedRegs));
195 LLVM_DEBUG(dbgs() << "[E] Retired #" << IR << " \n");
196}
197
199 Instruction &IS = *IR.getInstruction();
200 if (IS.isMemOp())
201 IS.setLSUTokenID(LSU.dispatch(IR));
202
203 if (llvm::Error E = tryIssue(IR))
204 return E;
205
206 if (SI.isValid())
207 notifyStallEvent();
208
209 return llvm::ErrorSuccess();
210}
211
212llvm::Error InOrderIssueStage::tryIssue(InstRef &IR) {
213 Instruction &IS = *IR.getInstruction();
214 unsigned SourceIndex = IR.getSourceIndex();
215 const InstrDesc &Desc = IS.getDesc();
216
217 if (!canExecute(IR)) {
218 LLVM_DEBUG(dbgs() << "[N] Stalled #" << SI.getInstruction() << " for "
219 << SI.getCyclesLeft() << " cycles\n");
220 Bandwidth = 0;
221 return llvm::ErrorSuccess();
222 }
223
224 unsigned RCUTokenID = RetireControlUnit::UnhandledTokenID;
225 IS.dispatch(RCUTokenID);
226
228 addRegisterReadWrite(PRF, IS, SourceIndex, STI, UsedRegs);
229
230 unsigned NumMicroOps = IS.getNumMicroOps();
231 notifyInstructionDispatched(IR, NumMicroOps, UsedRegs);
232
233 SmallVector<ResourceUse, 4> UsedResources;
234 RM.issueInstruction(Desc, UsedResources);
235 IS.execute(SourceIndex);
236
237 if (IS.isMemOp())
239
240 // Replace resource masks with valid resource processor IDs.
241 for (ResourceUse &Use : UsedResources) {
242 uint64_t Mask = Use.first.first;
243 Use.first.first = RM.resolveResourceMask(Mask);
244 }
245 notifyInstructionIssued(IR, UsedResources);
246
247 bool ShouldCarryOver = NumMicroOps > Bandwidth;
248 if (ShouldCarryOver) {
249 CarryOver = NumMicroOps - Bandwidth;
250 CarriedOver = IR;
251 Bandwidth = 0;
252 NumIssued += Bandwidth;
253 LLVM_DEBUG(dbgs() << "[N] Carry over #" << IR << " \n");
254 } else {
255 NumIssued += NumMicroOps;
256 Bandwidth = IS.getEndGroup() ? 0 : Bandwidth - NumMicroOps;
257 }
258
259 // If the instruction has a latency of 0, we need to handle
260 // the execution and retirement now. If the instruction is issued in multiple
261 // cycles, we cannot handle the instruction being executed here so we make
262 // updateCarriedOver responsible.
263 if (IS.isExecuted() && !ShouldCarryOver) {
264 PRF.onInstructionExecuted(&IS);
266 notifyInstructionExecuted(IR);
267
268 retireInstruction(IR);
269 return llvm::ErrorSuccess();
270 }
271
272 IssuedInst.push_back(IR);
273
274 if (!IR.getInstruction()->getRetireOOO())
275 LastWriteBackCycle = IS.getCyclesLeft();
276
277 return llvm::ErrorSuccess();
278}
279
280void InOrderIssueStage::updateIssuedInst() {
281 // Update other instructions. Executed instructions will be retired during the
282 // next cycle.
283 unsigned NumExecuted = 0;
284 for (auto I = IssuedInst.begin(), E = IssuedInst.end();
285 I != (E - NumExecuted);) {
286 InstRef &IR = *I;
287 Instruction &IS = *IR.getInstruction();
288
289 IS.cycleEvent();
290 if (!IS.isExecuted()) {
291 LLVM_DEBUG(dbgs() << "[N] Instruction #" << IR
292 << " is still executing\n");
293 ++I;
294 continue;
295 }
296
297 // If the instruction takes multiple cycles to issue, defer these calls
298 // to updateCarriedOver. We still remove from IssuedInst even if there is
299 // carry over to avoid an extra call to cycleEvent in the next cycle.
300 if (!CarriedOver) {
301 PRF.onInstructionExecuted(&IS);
303 notifyInstructionExecuted(IR);
304
305 retireInstruction(*I);
306 }
307
308 ++NumExecuted;
309
310 std::iter_swap(I, E - NumExecuted);
311 }
312
313 if (NumExecuted)
314 IssuedInst.resize(IssuedInst.size() - NumExecuted);
315}
316
317void InOrderIssueStage::updateCarriedOver() {
318 if (!CarriedOver)
319 return;
320
321 assert(!SI.isValid() && "A stalled instruction cannot be carried over.");
322
323 if (CarryOver > Bandwidth) {
324 CarryOver -= Bandwidth;
325 Bandwidth = 0;
326 LLVM_DEBUG(dbgs() << "[N] Carry over (" << CarryOver << "uops left) #"
327 << CarriedOver << " \n");
328 return;
329 }
330
331 LLVM_DEBUG(dbgs() << "[N] Carry over (complete) #" << CarriedOver << " \n");
332
333 if (CarriedOver.getInstruction()->getEndGroup())
334 Bandwidth = 0;
335 else
336 Bandwidth -= CarryOver;
337
338 // updateIssuedInst defered these calls to updateCarriedOver when there was
339 // a carry over.
340 if (CarriedOver.getInstruction()->isExecuted()) {
341 PRF.onInstructionExecuted(CarriedOver.getInstruction());
342 LSU.onInstructionExecuted(CarriedOver);
343 notifyInstructionExecuted(CarriedOver);
344
345 retireInstruction(CarriedOver);
346 }
347
348 CarriedOver = InstRef();
349 CarryOver = 0;
350}
351
352void InOrderIssueStage::retireInstruction(InstRef &IR) {
353 Instruction &IS = *IR.getInstruction();
354 IS.retire();
355
357 for (const WriteState &WS : IS.getDefs())
358 PRF.removeRegisterWrite(WS, FreedRegs);
359
360 if (IS.isMemOp())
362
363 notifyInstructionRetired(IR, FreedRegs);
364}
365
366void InOrderIssueStage::notifyStallEvent() {
367 assert(SI.getCyclesLeft() && "A zero cycles stall?");
368 assert(SI.isValid() && "Invalid stall information found!");
369
370 const InstRef &IR = SI.getInstruction();
371
372 switch (SI.getStallKind()) {
373 default:
374 break;
376 notifyEvent<HWStallEvent>(
377 HWStallEvent(HWStallEvent::RegisterFileStall, IR));
378 notifyEvent<HWPressureEvent>(
379 HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR));
380 break;
381 }
383 notifyEvent<HWStallEvent>(
384 HWStallEvent(HWStallEvent::DispatchGroupStall, IR));
385 notifyEvent<HWPressureEvent>(
386 HWPressureEvent(HWPressureEvent::RESOURCES, IR));
387 break;
388 }
390 notifyEvent<HWStallEvent>(
392 break;
393 }
394 }
395}
396
398 NumIssued = 0;
399 Bandwidth = getIssueWidth();
400
401 PRF.cycleStart();
402 LSU.cycleEvent();
403
404 // Release consumed resources.
406 RM.cycleEvent(Freed);
407
408 updateIssuedInst();
409
410 // Continue to issue the instruction carried over from the previous cycle
411 updateCarriedOver();
412
413 // Issue instructions scheduled for this cycle
414 if (SI.isValid()) {
415 if (!SI.getCyclesLeft()) {
416 // Make a copy of the reference, and try issue it again.
417 // Do not take the instruction reference because SI.clear() will
418 // invalidate it.
420 SI.clear();
421
422 if (llvm::Error E = tryIssue(IR))
423 return E;
424 }
425
426 if (SI.getCyclesLeft()) {
427 // The instruction is still stalled, cannot issue any new instructions in
428 // this cycle.
429 notifyStallEvent();
430 Bandwidth = 0;
431 return llvm::ErrorSuccess();
432 }
433 }
434
435 assert((NumIssued <= getIssueWidth()) && "Overflow.");
436 return llvm::ErrorSuccess();
437}
438
440 PRF.cycleEnd();
441 SI.cycleEnd();
442
443 if (LastWriteBackCycle > 0)
444 --LastWriteBackCycle;
445
446 return llvm::ErrorSuccess();
447}
448
449} // namespace mca
450} // namespace llvm
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
InOrderIssueStage implements an in-order execution pipeline.
A Load/Store unit class that models load/store queues and that implements a simple weak memory consis...
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:81
This file defines abstractions used by the Pipeline to model register reads, register writes and inst...
#define I(x, y, z)
Definition: MD5.cpp:58
This file defines a register mapping file class.
This file simulates the hardware responsible for retiring instructions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Subclass of Error for the sole purpose of identifying the success path in the type system.
Definition: Error.h:332
Lightweight error class with error context and mandatory checking.
Definition: Error.h:160
Generic base class for all target subtargets.
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget's CPU.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Class which can be overriden by targets to enforce instruction dependencies and behaviours that aren'...
virtual unsigned checkCustomHazard(ArrayRef< InstRef > IssuedInst, const InstRef &IR)
Before the llvm-mca pipeline dispatches an instruction, it first checks for any register or resource ...
bool hasWorkToComplete() const override
Returns true if some instructions are still executing this stage.
Error cycleEnd() override
Called once at the end of each cycle.
Error execute(InstRef &IR) override
The primary action that this stage performs on instruction IR.
bool isAvailable(const InstRef &) const override
Returns true if it can execute IR during this cycle.
Error cycleStart() override
Called once at the start of each cycle.
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:720
void invalidate()
Invalidate this reference.
Definition: Instruction.h:741
Instruction * getInstruction()
Definition: Instruction.h:734
unsigned getNumMicroOps() const
Definition: Instruction.h:542
const InstrDesc & getDesc() const
Definition: Instruction.h:539
SmallVectorImpl< WriteState > & getDefs()
Definition: Instruction.h:535
SmallVectorImpl< ReadState > & getUses()
Definition: Instruction.h:537
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:600
bool isEliminated() const
Definition: Instruction.h:691
bool isExecuted() const
Definition: Instruction.h:689
int getCyclesLeft() const
Definition: Instruction.h:663
void execute(unsigned IID)
void setLSUTokenID(unsigned LSUTok)
Definition: Instruction.h:657
void dispatch(unsigned RCUTokenID)
virtual void onInstructionIssued(const InstRef &IR)
Definition: LSUnit.h:325
virtual void cycleEvent()
Definition: LSUnit.cpp:44
virtual void onInstructionRetired(const InstRef &IR)
Definition: LSUnit.cpp:214
bool isReady(const InstRef &IR) const
Check if a peviously dispatched instruction IR is now ready for execution.
Definition: LSUnit.h:273
Default Load/Store Unit (LS Unit) for simulated processors.
Definition: LSUnit.h:398
void onInstructionExecuted(const InstRef &IR) override
Definition: LSUnit.cpp:233
unsigned dispatch(const InstRef &IR) override
Allocates LS resources for instruction IR.
Definition: LSUnit.cpp:69
Tracks register operand latency in cycles.
Definition: Instruction.h:326
Manages hardware register files, and tracks register definitions for register renaming purposes.
Definition: RegisterFile.h:83
void addRegisterWrite(WriteRef Write, MutableArrayRef< unsigned > UsedPhysRegs)
unsigned getNumRegisterFiles() const
Definition: RegisterFile.h:293
RAWHazard checkRAWHazards(const MCSubtargetInfo &STI, const ReadState &RS) const
void removeRegisterWrite(const WriteState &WS, MutableArrayRef< unsigned > FreedPhysRegs)
void addRegisterRead(ReadState &RS, const MCSubtargetInfo &STI) const
void onInstructionExecuted(Instruction *IS)
A resource manager for processor resource units and groups.
void issueInstruction(const InstrDesc &Desc, SmallVectorImpl< std::pair< ResourceRef, ReleaseAtCycles > > &Pipes)
unsigned resolveResourceMask(uint64_t Mask) const
void cycleEvent(SmallVectorImpl< ResourceRef > &ResourcesFreed)
A reference to a register write.
Definition: RegisterFile.h:38
Tracks uses of a register definition (e.g.
Definition: Instruction.h:197
std::pair< ResourceRef, ReleaseAtCycles > ResourceUse
static void addRegisterReadWrite(RegisterFile &PRF, Instruction &IS, unsigned SourceIndex, const MCSubtargetInfo &STI, SmallVectorImpl< unsigned > &UsedRegs)
static bool hasResourceHazard(const ResourceManager &RM, const InstRef &IR)
static unsigned findFirstWriteBackCycle(const InstRef &IR)
static unsigned checkRegisterHazard(const RegisterFile &PRF, const MCSubtargetInfo &STI, const InstRef &IR)
Return a number of cycles left until register requirements of the instructions are met.
constexpr int UNKNOWN_CYCLES
Definition: Instruction.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Description of the encoding of one expression Op.
unsigned IssueWidth
Definition: MCSchedule.h:265
An instruction descriptor.
Definition: Instruction.h:447
static const unsigned UnhandledTokenID
StallKind getStallKind() const
const InstRef & getInstruction() const
unsigned getCyclesLeft() const
void update(const InstRef &Inst, unsigned Cycles, StallKind SK)