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.
261 if (IS.isExecuted()) {
262 PRF.onInstructionExecuted(&IS);
264 notifyEvent<HWInstructionEvent>(
265 HWInstructionEvent(HWInstructionEvent::Executed, IR));
266 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n");
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 PRF.onInstructionExecuted(&IS);
299 notifyInstructionExecuted(IR);
300 ++NumExecuted;
301
302 retireInstruction(*I);
303
304 std::iter_swap(I, E - NumExecuted);
305 }
306
307 if (NumExecuted)
308 IssuedInst.resize(IssuedInst.size() - NumExecuted);
309}
310
311void InOrderIssueStage::updateCarriedOver() {
312 if (!CarriedOver)
313 return;
314
315 assert(!SI.isValid() && "A stalled instruction cannot be carried over.");
316
317 if (CarryOver > Bandwidth) {
318 CarryOver -= Bandwidth;
319 Bandwidth = 0;
320 LLVM_DEBUG(dbgs() << "[N] Carry over (" << CarryOver << "uops left) #"
321 << CarriedOver << " \n");
322 return;
323 }
324
325 LLVM_DEBUG(dbgs() << "[N] Carry over (complete) #" << CarriedOver << " \n");
326
327 if (CarriedOver.getInstruction()->getEndGroup())
328 Bandwidth = 0;
329 else
330 Bandwidth -= CarryOver;
331
332 CarriedOver = InstRef();
333 CarryOver = 0;
334}
335
336void InOrderIssueStage::retireInstruction(InstRef &IR) {
337 Instruction &IS = *IR.getInstruction();
338 IS.retire();
339
341 for (const WriteState &WS : IS.getDefs())
342 PRF.removeRegisterWrite(WS, FreedRegs);
343
344 if (IS.isMemOp())
346
347 notifyInstructionRetired(IR, FreedRegs);
348}
349
350void InOrderIssueStage::notifyStallEvent() {
351 assert(SI.getCyclesLeft() && "A zero cycles stall?");
352 assert(SI.isValid() && "Invalid stall information found!");
353
354 const InstRef &IR = SI.getInstruction();
355
356 switch (SI.getStallKind()) {
357 default:
358 break;
360 notifyEvent<HWStallEvent>(
361 HWStallEvent(HWStallEvent::RegisterFileStall, IR));
362 notifyEvent<HWPressureEvent>(
363 HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR));
364 break;
365 }
367 notifyEvent<HWStallEvent>(
368 HWStallEvent(HWStallEvent::DispatchGroupStall, IR));
369 notifyEvent<HWPressureEvent>(
370 HWPressureEvent(HWPressureEvent::RESOURCES, IR));
371 break;
372 }
374 notifyEvent<HWStallEvent>(
376 break;
377 }
378 }
379}
380
382 NumIssued = 0;
383 Bandwidth = getIssueWidth();
384
385 PRF.cycleStart();
386 LSU.cycleEvent();
387
388 // Release consumed resources.
390 RM.cycleEvent(Freed);
391
392 updateIssuedInst();
393
394 // Continue to issue the instruction carried over from the previous cycle
395 updateCarriedOver();
396
397 // Issue instructions scheduled for this cycle
398 if (SI.isValid()) {
399 if (!SI.getCyclesLeft()) {
400 // Make a copy of the reference, and try issue it again.
401 // Do not take the instruction reference because SI.clear() will
402 // invalidate it.
404 SI.clear();
405
406 if (llvm::Error E = tryIssue(IR))
407 return E;
408 }
409
410 if (SI.getCyclesLeft()) {
411 // The instruction is still stalled, cannot issue any new instructions in
412 // this cycle.
413 notifyStallEvent();
414 Bandwidth = 0;
415 return llvm::ErrorSuccess();
416 }
417 }
418
419 assert((NumIssued <= getIssueWidth()) && "Overflow.");
420 return llvm::ErrorSuccess();
421}
422
424 PRF.cycleEnd();
425 SI.cycleEnd();
426
427 if (LastWriteBackCycle > 0)
428 --LastWriteBackCycle;
429
430 return llvm::ErrorSuccess();
431}
432
433} // namespace mca
434} // 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)