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
14#include "llvm/MCA/Stages/InOrderIssueStage.h"
15#include "llvm/MCA/HardwareUnits/LSUnit.h"
16#include "llvm/MCA/HardwareUnits/RegisterFile.h"
17#include "llvm/MCA/HardwareUnits/RetireControlUnit.h"
18#include "llvm/MCA/Instruction.h"
19
20#define DEBUG_TYPE "llvm-mca"
21namespace llvm {
22namespace mca {
23
24void StallInfo::clear() {
25 IR.invalidate();
26 CyclesLeft = 0;
27 Kind = StallKind::DEFAULT;
28}
29
30void StallInfo::update(const InstRef &Inst, unsigned Cycles, StallKind SK) {
31 IR = Inst;
32 CyclesLeft = Cycles;
33 Kind = SK;
34}
35
36void StallInfo::cycleEnd() {
37 if (!isValid())
38 return;
39
40 if (!CyclesLeft)
41 return;
42
43 --CyclesLeft;
44}
45
46InOrderIssueStage::InOrderIssueStage(const MCSubtargetInfo &STI,
47 RegisterFile &PRF, CustomBehaviour &CB,
48 LSUnitBase &LSU)
49 : STI(STI), PRF(PRF), RM(STI.getSchedModel()), CB(CB), LSU(LSU),
50 NumIssued(), CarryOver(), Bandwidth(), LastWriteBackCycle() {}
51
52unsigned InOrderIssueStage::getIssueWidth() const {
53 return STI.getSchedModel().IssueWidth;
54}
55
56bool InOrderIssueStage::hasWorkToComplete() const {
57 return !IssuedInst.empty() || SI.isValid() || CarriedOver;
58}
59
60bool InOrderIssueStage::isAvailable(const InstRef &IR) const {
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(Desc: 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(a: FirstWBCycle, b: (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)) {
120 SI.update(Inst: IR, Cycles, SK: StallInfo::StallKind::REGISTER_DEPS);
121 return false;
122 }
123
124 if (hasResourceHazard(RM, IR)) {
125 SI.update(Inst: IR, /* delay */ Cycles: 1, SK: 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(Inst: IR, /* delay */ Cycles: 1, SK: StallInfo::StallKind::LOAD_STORE);
133 return false;
134 }
135
136 if (unsigned CustomStallCycles = CB.checkCustomHazard(IssuedInst, IR)) {
137 SI.update(Inst: IR, Cycles: CustomStallCycles, SK: 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(Inst: IR, Cycles: LastWriteBackCycle - NextWriteBackCycle,
147 SK: StallInfo::StallKind::DELAY);
148 return false;
149 }
150 }
151 }
152
153 return true;
154}
155
156static void addRegisterReadWrite(RegisterFile &PRF, Instruction &IS,
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(Write: WriteRef(SourceIndex, &WS), UsedPhysRegs: UsedRegs);
167}
168
169void InOrderIssueStage::notifyInstructionIssued(const InstRef &IR,
170 ArrayRef<ResourceUse> UsedRes) {
171 notifyEvent<HWInstructionEvent>(
172 Event: HWInstructionEvent(HWInstructionEvent::Ready, IR));
173 notifyEvent<HWInstructionEvent>(Event: 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 Event: 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 Event: 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>(Event: HWInstructionRetiredEvent(IR, FreedRegs));
195 LLVM_DEBUG(dbgs() << "[E] Retired #" << IR << " \n");
196}
197
198llvm::Error InOrderIssueStage::execute(InstRef &IR) {
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
227 SmallVector<unsigned, 4> UsedRegs(PRF.getNumRegisterFiles());
228 addRegisterReadWrite(PRF, IS, SourceIndex, STI, UsedRegs);
229
230 unsigned NumMicroOps = IS.getNumMicroOps();
231 notifyInstructionDispatched(IR, Ops: NumMicroOps, UsedRegs);
232
233 SmallVector<ResourceUse, 4> UsedResources;
234 RM.issueInstruction(Desc, Pipes&: UsedResources);
235 IS.execute(IID: SourceIndex);
236
237 if (IS.isMemOp())
238 LSU.onInstructionIssued(IR);
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, UsedRes: 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: &IS);
265 LSU.onInstructionExecuted(IR);
266 notifyInstructionExecuted(IR);
267
268 retireInstruction(IR);
269 return llvm::ErrorSuccess();
270 }
271
272 IssuedInst.push_back(Elt: 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: &IS);
302 LSU.onInstructionExecuted(IR);
303 notifyInstructionExecuted(IR);
304
305 retireInstruction(IR&: *I);
306 }
307
308 ++NumExecuted;
309
310 std::iter_swap(a: I, b: E - NumExecuted);
311 }
312
313 if (NumExecuted)
314 IssuedInst.resize(N: 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(IS: CarriedOver.getInstruction());
342 LSU.onInstructionExecuted(IR: CarriedOver);
343 notifyInstructionExecuted(IR: CarriedOver);
344
345 retireInstruction(IR&: 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
356 llvm::SmallVector<unsigned, 4> FreedRegs(PRF.getNumRegisterFiles());
357 for (const WriteState &WS : IS.getDefs())
358 PRF.removeRegisterWrite(WS, FreedPhysRegs: FreedRegs);
359
360 if (IS.isMemOp())
361 LSU.onInstructionRetired(IR);
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;
375 case StallInfo::StallKind::REGISTER_DEPS: {
376 notifyEvent<HWStallEvent>(
377 Event: HWStallEvent(HWStallEvent::RegisterFileStall, IR));
378 notifyEvent<HWPressureEvent>(
379 Event: HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR));
380 break;
381 }
382 case StallInfo::StallKind::DISPATCH: {
383 notifyEvent<HWStallEvent>(
384 Event: HWStallEvent(HWStallEvent::DispatchGroupStall, IR));
385 notifyEvent<HWPressureEvent>(
386 Event: HWPressureEvent(HWPressureEvent::RESOURCES, IR));
387 break;
388 }
389 case StallInfo::StallKind::CUSTOM_STALL: {
390 notifyEvent<HWStallEvent>(
391 Event: HWStallEvent(HWStallEvent::CustomBehaviourStall, IR));
392 break;
393 }
394 }
395}
396
397llvm::Error InOrderIssueStage::cycleStart() {
398 NumIssued = 0;
399 Bandwidth = getIssueWidth();
400
401 PRF.cycleStart();
402 LSU.cycleEvent();
403
404 // Release consumed resources.
405 SmallVector<ResourceRef, 4> Freed;
406 RM.cycleEvent(ResourcesFreed&: 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.
419 InstRef IR = SI.getInstruction();
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
439llvm::Error InOrderIssueStage::cycleEnd() {
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
451