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