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 float ReservationStationScaleFactor)
50 : STI(STI), PRF(PRF),
51 RM(STI.getSchedModel(), ReservationStationScaleFactor), CB(CB), LSU(LSU),
52 NumIssued(), CarryOver(), Bandwidth(), LastWriteBackCycle() {}
53
54unsigned InOrderIssueStage::getIssueWidth() const {
55 return STI.getSchedModel().IssueWidth;
56}
57
58bool InOrderIssueStage::hasWorkToComplete() const {
59 return !IssuedInst.empty() || SI.isValid() || CarriedOver;
60}
61
62bool InOrderIssueStage::isAvailable(const InstRef &IR) const {
63 if (SI.isValid() || CarriedOver)
64 return false;
65
66 const Instruction &Inst = *IR.getInstruction();
67 unsigned NumMicroOps = Inst.getNumMicroOps();
68
69 bool ShouldCarryOver = NumMicroOps > getIssueWidth();
70 if (Bandwidth < NumMicroOps && !ShouldCarryOver)
71 return false;
72
73 // Instruction with BeginGroup must be the first instruction to be issued in a
74 // cycle.
75 if (Inst.getBeginGroup() && NumIssued != 0)
76 return false;
77
78 return true;
79}
80
81static bool hasResourceHazard(const ResourceManager &RM, const InstRef &IR) {
82 if (RM.checkAvailability(Desc: IR.getInstruction()->getDesc())) {
83 LLVM_DEBUG(dbgs() << "[E] Stall #" << IR << '\n');
84 return true;
85 }
86
87 return false;
88}
89
90static unsigned findFirstWriteBackCycle(const InstRef &IR) {
91 unsigned FirstWBCycle = IR.getInstruction()->getLatency();
92 for (const WriteState &WS : IR.getInstruction()->getDefs()) {
93 int CyclesLeft = WS.getCyclesLeft();
94 if (CyclesLeft == UNKNOWN_CYCLES)
95 CyclesLeft = WS.getLatency();
96 if (CyclesLeft < 0)
97 CyclesLeft = 0;
98 FirstWBCycle = std::min(a: FirstWBCycle, b: (unsigned)CyclesLeft);
99 }
100 return FirstWBCycle;
101}
102
103/// Return a number of cycles left until register requirements of the
104/// instructions are met.
105static unsigned checkRegisterHazard(const RegisterFile &PRF,
106 const MCSubtargetInfo &STI,
107 const InstRef &IR) {
108 for (const ReadState &RS : IR.getInstruction()->getUses()) {
109 RegisterFile::RAWHazard Hazard = PRF.checkRAWHazards(STI, RS);
110 if (Hazard.isValid())
111 return Hazard.hasUnknownCycles() ? 1U : Hazard.CyclesLeft;
112 }
113
114 return 0;
115}
116
117bool InOrderIssueStage::canExecute(const InstRef &IR) {
118 assert(!SI.getCyclesLeft() && "Should not have reached this code!");
119 assert(!SI.isValid() && "Should not have reached this code!");
120
121 if (unsigned Cycles = checkRegisterHazard(PRF, STI, IR)) {
122 SI.update(Inst: IR, Cycles, SK: StallInfo::StallKind::REGISTER_DEPS);
123 return false;
124 }
125
126 if (hasResourceHazard(RM, IR)) {
127 SI.update(Inst: IR, /* delay */ Cycles: 1, SK: StallInfo::StallKind::DISPATCH);
128 return false;
129 }
130
131 if (IR.getInstruction()->isMemOp() && !LSU.isReady(IR)) {
132 // This load (store) aliases with a preceding store (load). Delay
133 // it until the depenency is cleared.
134 SI.update(Inst: IR, /* delay */ Cycles: 1, SK: StallInfo::StallKind::LOAD_STORE);
135 return false;
136 }
137
138 if (unsigned CustomStallCycles = CB.checkCustomHazard(IssuedInst, IR)) {
139 SI.update(Inst: IR, Cycles: CustomStallCycles, SK: StallInfo::StallKind::CUSTOM_STALL);
140 return false;
141 }
142
143 if (LastWriteBackCycle) {
144 if (!IR.getInstruction()->getRetireOOO()) {
145 unsigned NextWriteBackCycle = findFirstWriteBackCycle(IR);
146 // Delay the instruction to ensure that writes happen in program order.
147 if (NextWriteBackCycle < LastWriteBackCycle) {
148 SI.update(Inst: IR, Cycles: LastWriteBackCycle - NextWriteBackCycle,
149 SK: StallInfo::StallKind::DELAY);
150 return false;
151 }
152 }
153 }
154
155 return true;
156}
157
158static void addRegisterReadWrite(RegisterFile &PRF, Instruction &IS,
159 unsigned SourceIndex,
160 const MCSubtargetInfo &STI,
161 SmallVectorImpl<unsigned> &UsedRegs) {
162 assert(!IS.isEliminated());
163
164 for (ReadState &RS : IS.getUses())
165 PRF.addRegisterRead(RS, STI);
166
167 for (WriteState &WS : IS.getDefs())
168 PRF.addRegisterWrite(Write: WriteRef(SourceIndex, &WS), UsedPhysRegs: UsedRegs);
169}
170
171void InOrderIssueStage::notifyInstructionIssued(const InstRef &IR,
172 ArrayRef<ResourceUse> UsedRes) {
173 notifyEvent<HWInstructionEvent>(
174 Event: HWInstructionEvent(HWInstructionEvent::Ready, IR));
175 notifyEvent<HWInstructionEvent>(Event: HWInstructionIssuedEvent(IR, UsedRes));
176
177 LLVM_DEBUG(dbgs() << "[E] Issued #" << IR << "\n");
178}
179
180void InOrderIssueStage::notifyInstructionDispatched(
181 const InstRef &IR, unsigned Ops, ArrayRef<unsigned> UsedRegs) {
182 notifyEvent<HWInstructionEvent>(
183 Event: HWInstructionDispatchedEvent(IR, UsedRegs, Ops));
184
185 LLVM_DEBUG(dbgs() << "[E] Dispatched #" << IR << "\n");
186}
187
188void InOrderIssueStage::notifyInstructionExecuted(const InstRef &IR) {
189 notifyEvent<HWInstructionEvent>(
190 Event: HWInstructionEvent(HWInstructionEvent::Executed, IR));
191 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n");
192}
193
194void InOrderIssueStage::notifyInstructionRetired(const InstRef &IR,
195 ArrayRef<unsigned> FreedRegs) {
196 notifyEvent<HWInstructionEvent>(Event: HWInstructionRetiredEvent(IR, FreedRegs));
197 LLVM_DEBUG(dbgs() << "[E] Retired #" << IR << " \n");
198}
199
200llvm::Error InOrderIssueStage::execute(InstRef &IR) {
201 Instruction &IS = *IR.getInstruction();
202 if (IS.isMemOp())
203 IS.setLSUTokenID(LSU.dispatch(IR));
204
205 if (llvm::Error E = tryIssue(IR))
206 return E;
207
208 if (SI.isValid())
209 notifyStallEvent();
210
211 return llvm::ErrorSuccess();
212}
213
214llvm::Error InOrderIssueStage::tryIssue(InstRef &IR) {
215 Instruction &IS = *IR.getInstruction();
216 unsigned SourceIndex = IR.getSourceIndex();
217 const InstrDesc &Desc = IS.getDesc();
218
219 if (!canExecute(IR)) {
220 LLVM_DEBUG(dbgs() << "[N] Stalled #" << SI.getInstruction() << " for "
221 << SI.getCyclesLeft() << " cycles\n");
222 Bandwidth = 0;
223 return llvm::ErrorSuccess();
224 }
225
226 unsigned RCUTokenID = RetireControlUnit::UnhandledTokenID;
227 IS.dispatch(RCUTokenID);
228
229 SmallVector<unsigned, 4> UsedRegs(PRF.getNumRegisterFiles());
230 addRegisterReadWrite(PRF, IS, SourceIndex, STI, UsedRegs);
231
232 unsigned NumMicroOps = IS.getNumMicroOps();
233 notifyInstructionDispatched(IR, Ops: NumMicroOps, UsedRegs);
234
235 SmallVector<ResourceUse, 4> UsedResources;
236 RM.issueInstruction(Desc, Pipes&: UsedResources);
237 IS.execute(IID: SourceIndex);
238
239 if (IS.isMemOp())
240 LSU.onInstructionIssued(IR);
241
242 // Replace resource masks with valid resource processor IDs.
243 for (ResourceUse &Use : UsedResources) {
244 uint64_t Mask = Use.first.first;
245 Use.first.first = RM.resolveResourceMask(Mask);
246 }
247 notifyInstructionIssued(IR, UsedRes: UsedResources);
248
249 bool ShouldCarryOver = NumMicroOps > Bandwidth;
250 if (ShouldCarryOver) {
251 CarryOver = NumMicroOps - Bandwidth;
252 CarriedOver = IR;
253 Bandwidth = 0;
254 NumIssued += Bandwidth;
255 LLVM_DEBUG(dbgs() << "[N] Carry over #" << IR << " \n");
256 } else {
257 NumIssued += NumMicroOps;
258 Bandwidth = IS.getEndGroup() ? 0 : Bandwidth - NumMicroOps;
259 }
260
261 // If the instruction has a latency of 0, we need to handle
262 // the execution and retirement now. If the instruction is issued in multiple
263 // cycles, we cannot handle the instruction being executed here so we make
264 // updateCarriedOver responsible.
265 if (IS.isExecuted() && !ShouldCarryOver) {
266 PRF.onInstructionExecuted(IS: &IS);
267 LSU.onInstructionExecuted(IR);
268 notifyInstructionExecuted(IR);
269
270 retireInstruction(IR);
271 return llvm::ErrorSuccess();
272 }
273
274 IssuedInst.push_back(Elt: IR);
275
276 if (!IR.getInstruction()->getRetireOOO())
277 LastWriteBackCycle = IS.getCyclesLeft();
278
279 return llvm::ErrorSuccess();
280}
281
282void InOrderIssueStage::updateIssuedInst() {
283 // Update other instructions. Executed instructions will be retired during the
284 // next cycle.
285 unsigned NumExecuted = 0;
286 for (auto I = IssuedInst.begin(), E = IssuedInst.end();
287 I != (E - NumExecuted);) {
288 InstRef &IR = *I;
289 Instruction &IS = *IR.getInstruction();
290
291 IS.cycleEvent();
292 if (!IS.isExecuted()) {
293 LLVM_DEBUG(dbgs() << "[N] Instruction #" << IR
294 << " is still executing\n");
295 ++I;
296 continue;
297 }
298
299 // If an instruction takes multiple cycles to issue, defer these calls
300 // to updateCarriedOver. We still remove from IssuedInst even if there is
301 // carry over to avoid an extra call to cycleEvent in the next cycle.
302 if (CarriedOver.getInstruction() != IR.getInstruction()) {
303 PRF.onInstructionExecuted(IS: &IS);
304 LSU.onInstructionExecuted(IR);
305 notifyInstructionExecuted(IR);
306
307 retireInstruction(IR&: *I);
308 }
309
310 ++NumExecuted;
311
312 std::iter_swap(a: I, b: E - NumExecuted);
313 }
314
315 if (NumExecuted)
316 IssuedInst.resize(N: IssuedInst.size() - NumExecuted);
317}
318
319void InOrderIssueStage::updateCarriedOver() {
320 if (!CarriedOver)
321 return;
322
323 assert(!SI.isValid() && "A stalled instruction cannot be carried over.");
324
325 if (CarryOver > Bandwidth) {
326 CarryOver -= Bandwidth;
327 Bandwidth = 0;
328 LLVM_DEBUG(dbgs() << "[N] Carry over (" << CarryOver << "uops left) #"
329 << CarriedOver << " \n");
330 return;
331 }
332
333 LLVM_DEBUG(dbgs() << "[N] Carry over (complete) #" << CarriedOver << " \n");
334
335 if (CarriedOver.getInstruction()->getEndGroup())
336 Bandwidth = 0;
337 else
338 Bandwidth -= CarryOver;
339
340 // updateIssuedInst defered these calls to updateCarriedOver when there was
341 // a carry over.
342 if (CarriedOver.getInstruction()->isExecuted()) {
343 PRF.onInstructionExecuted(IS: CarriedOver.getInstruction());
344 LSU.onInstructionExecuted(IR: CarriedOver);
345 notifyInstructionExecuted(IR: CarriedOver);
346
347 retireInstruction(IR&: CarriedOver);
348 }
349
350 CarriedOver = InstRef();
351 CarryOver = 0;
352}
353
354void InOrderIssueStage::retireInstruction(InstRef &IR) {
355 Instruction &IS = *IR.getInstruction();
356 IS.retire();
357
358 llvm::SmallVector<unsigned, 4> FreedRegs(PRF.getNumRegisterFiles());
359 for (const WriteState &WS : IS.getDefs())
360 PRF.removeRegisterWrite(WS, FreedPhysRegs: FreedRegs);
361
362 if (IS.isMemOp())
363 LSU.onInstructionRetired(IR);
364
365 notifyInstructionRetired(IR, FreedRegs);
366}
367
368void InOrderIssueStage::notifyStallEvent() {
369 assert(SI.getCyclesLeft() && "A zero cycles stall?");
370 assert(SI.isValid() && "Invalid stall information found!");
371
372 const InstRef &IR = SI.getInstruction();
373
374 switch (SI.getStallKind()) {
375 default:
376 break;
377 case StallInfo::StallKind::REGISTER_DEPS: {
378 notifyEvent<HWStallEvent>(
379 Event: HWStallEvent(HWStallEvent::RegisterFileStall, IR));
380 notifyEvent<HWPressureEvent>(
381 Event: HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR));
382 break;
383 }
384 case StallInfo::StallKind::DISPATCH: {
385 notifyEvent<HWStallEvent>(
386 Event: HWStallEvent(HWStallEvent::DispatchGroupStall, IR));
387 notifyEvent<HWPressureEvent>(
388 Event: HWPressureEvent(HWPressureEvent::RESOURCES, IR));
389 break;
390 }
391 case StallInfo::StallKind::CUSTOM_STALL: {
392 notifyEvent<HWStallEvent>(
393 Event: HWStallEvent(HWStallEvent::CustomBehaviourStall, IR));
394 break;
395 }
396 }
397}
398
399llvm::Error InOrderIssueStage::cycleStart() {
400 NumIssued = 0;
401 Bandwidth = getIssueWidth();
402
403 PRF.cycleStart();
404 LSU.cycleEvent();
405
406 // Release consumed resources.
407 SmallVector<ResourceRef, 4> Freed;
408 RM.cycleEvent(ResourcesFreed&: Freed);
409
410 updateIssuedInst();
411
412 // Continue to issue the instruction carried over from the previous cycle
413 updateCarriedOver();
414
415 // Issue instructions scheduled for this cycle
416 if (SI.isValid()) {
417 if (!SI.getCyclesLeft()) {
418 // Make a copy of the reference, and try issue it again.
419 // Do not take the instruction reference because SI.clear() will
420 // invalidate it.
421 InstRef IR = SI.getInstruction();
422 SI.clear();
423
424 if (llvm::Error E = tryIssue(IR))
425 return E;
426 }
427
428 if (SI.getCyclesLeft()) {
429 // The instruction is still stalled, cannot issue any new instructions in
430 // this cycle.
431 notifyStallEvent();
432 Bandwidth = 0;
433 return llvm::ErrorSuccess();
434 }
435 }
436
437 assert((NumIssued <= getIssueWidth()) && "Overflow.");
438 return llvm::ErrorSuccess();
439}
440
441llvm::Error InOrderIssueStage::cycleEnd() {
442 PRF.cycleEnd();
443 SI.cycleEnd();
444
445 if (LastWriteBackCycle > 0)
446 --LastWriteBackCycle;
447
448 return llvm::ErrorSuccess();
449}
450
451} // namespace mca
452} // namespace llvm
453