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
16 #include "llvm/MC/MCSchedule.h"
17 #include "llvm/MCA/HWEventListener.h"
18 #include "llvm/MCA/HardwareUnits/RegisterFile.h"
19 #include "llvm/MCA/HardwareUnits/ResourceManager.h"
20 #include "llvm/MCA/HardwareUnits/RetireControlUnit.h"
21 #include "llvm/MCA/Instruction.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/Error.h"
24
25 #include <algorithm>
26
27 #define DEBUG_TYPE "llvm-mca"
28 namespace llvm {
29 namespace mca {
30
hasWorkToComplete() const31 bool InOrderIssueStage::hasWorkToComplete() const {
32 return !IssuedInst.empty() || StalledInst || CarriedOver;
33 }
34
isAvailable(const InstRef & IR) const35 bool InOrderIssueStage::isAvailable(const InstRef &IR) const {
36 if (StalledInst || CarriedOver)
37 return false;
38
39 const Instruction &Inst = *IR.getInstruction();
40 unsigned NumMicroOps = Inst.getNumMicroOps();
41 const InstrDesc &Desc = Inst.getDesc();
42
43 bool ShouldCarryOver = NumMicroOps > SM.IssueWidth;
44 if (Bandwidth < NumMicroOps && !ShouldCarryOver)
45 return false;
46
47 // Instruction with BeginGroup must be the first instruction to be issued in a
48 // cycle.
49 if (Desc.BeginGroup && NumIssued != 0)
50 return false;
51
52 return true;
53 }
54
hasResourceHazard(const ResourceManager & RM,const InstRef & IR)55 static bool hasResourceHazard(const ResourceManager &RM, const InstRef &IR) {
56 if (RM.checkAvailability(IR.getInstruction()->getDesc())) {
57 LLVM_DEBUG(dbgs() << "[E] Stall #" << IR << '\n');
58 return true;
59 }
60
61 return false;
62 }
63
findLastWriteBackCycle(const InstRef & IR)64 static unsigned findLastWriteBackCycle(const InstRef &IR) {
65 unsigned LastWBCycle = 0;
66 for (const WriteState &WS : IR.getInstruction()->getDefs()) {
67 int CyclesLeft = WS.getCyclesLeft();
68 if (CyclesLeft == UNKNOWN_CYCLES)
69 CyclesLeft = WS.getLatency();
70 if (CyclesLeft < 0)
71 CyclesLeft = 0;
72 LastWBCycle = std::max(LastWBCycle, (unsigned)CyclesLeft);
73 }
74 return LastWBCycle;
75 }
76
findFirstWriteBackCycle(const InstRef & IR)77 static unsigned findFirstWriteBackCycle(const InstRef &IR) {
78 unsigned FirstWBCycle = ~0U;
79 for (const WriteState &WS : IR.getInstruction()->getDefs()) {
80 int CyclesLeft = WS.getCyclesLeft();
81 if (CyclesLeft == UNKNOWN_CYCLES)
82 CyclesLeft = WS.getLatency();
83 if (CyclesLeft < 0)
84 CyclesLeft = 0;
85 FirstWBCycle = std::min(FirstWBCycle, (unsigned)CyclesLeft);
86 }
87 return FirstWBCycle;
88 }
89
90 /// Return a number of cycles left until register requirements of the
91 /// instructions are met.
checkRegisterHazard(const RegisterFile & PRF,const MCSchedModel & SM,const MCSubtargetInfo & STI,const InstRef & IR)92 static unsigned checkRegisterHazard(const RegisterFile &PRF,
93 const MCSchedModel &SM,
94 const MCSubtargetInfo &STI,
95 const InstRef &IR) {
96 unsigned StallCycles = 0;
97 SmallVector<WriteRef, 4> Writes;
98 SmallVector<WriteRef, 4> CommittedWrites;
99
100 for (const ReadState &RS : IR.getInstruction()->getUses()) {
101 const ReadDescriptor &RD = RS.getDescriptor();
102 const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
103
104 PRF.collectWrites(STI, RS, Writes, CommittedWrites);
105 for (const WriteRef &WR : Writes) {
106 const WriteState *WS = WR.getWriteState();
107 unsigned WriteResID = WS->getWriteResourceID();
108 int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
109 LLVM_DEBUG(dbgs() << "[E] ReadAdvance for #" << IR << ": " << ReadAdvance
110 << '\n');
111
112 if (WS->getCyclesLeft() == UNKNOWN_CYCLES) {
113 // Try again in the next cycle until the value is known
114 StallCycles = std::max(StallCycles, 1U);
115 continue;
116 }
117
118 int CyclesLeft = WS->getCyclesLeft() - ReadAdvance;
119 if (CyclesLeft > 0) {
120 LLVM_DEBUG(dbgs() << "[E] Register hazard: " << WS->getRegisterID()
121 << '\n');
122 StallCycles = std::max(StallCycles, (unsigned)CyclesLeft);
123 }
124 }
125 Writes.clear();
126
127 for (const WriteRef &WR : CommittedWrites) {
128 unsigned WriteResID = WR.getWriteResourceID();
129 assert(!WR.getWriteState() && "Should be already committed!");
130 assert(WR.hasKnownWriteBackCycle() && "Invalid write!");
131 assert(STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID) < 0);
132 unsigned ReadAdvance = static_cast<unsigned>(
133 -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID));
134 unsigned Elapsed = PRF.getElapsedCyclesFromWriteBack(WR);
135 assert(Elapsed < ReadAdvance && "Should not have been added to the set!");
136 unsigned CyclesLeft = (ReadAdvance - Elapsed);
137 StallCycles = std::max(StallCycles, CyclesLeft);
138 }
139 }
140
141 return StallCycles;
142 }
143
canExecute(const InstRef & IR,unsigned * StallCycles) const144 bool InOrderIssueStage::canExecute(const InstRef &IR,
145 unsigned *StallCycles) const {
146 *StallCycles = 0;
147
148 if (unsigned RegStall = checkRegisterHazard(PRF, SM, STI, IR)) {
149 *StallCycles = RegStall;
150 // FIXME: add a parameter to HWStallEvent to indicate a number of cycles.
151 for (unsigned I = 0; I < RegStall; ++I) {
152 notifyEvent<HWStallEvent>(
153 HWStallEvent(HWStallEvent::RegisterFileStall, IR));
154 notifyEvent<HWPressureEvent>(
155 HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR));
156 }
157 } else if (hasResourceHazard(*RM, IR)) {
158 *StallCycles = 1;
159 notifyEvent<HWStallEvent>(
160 HWStallEvent(HWStallEvent::DispatchGroupStall, IR));
161 notifyEvent<HWPressureEvent>(
162 HWPressureEvent(HWPressureEvent::RESOURCES, IR));
163 } else if (LastWriteBackCycle) {
164 if (!IR.getInstruction()->getDesc().RetireOOO) {
165 unsigned NextWriteBackCycle = findFirstWriteBackCycle(IR);
166 // Delay the instruction to ensure that writes occur in program order
167 if (NextWriteBackCycle < LastWriteBackCycle) {
168 *StallCycles = LastWriteBackCycle - NextWriteBackCycle;
169 }
170 }
171 }
172
173 return *StallCycles == 0;
174 }
175
addRegisterReadWrite(RegisterFile & PRF,Instruction & IS,unsigned SourceIndex,const MCSubtargetInfo & STI,SmallVectorImpl<unsigned> & UsedRegs)176 static void addRegisterReadWrite(RegisterFile &PRF, Instruction &IS,
177 unsigned SourceIndex,
178 const MCSubtargetInfo &STI,
179 SmallVectorImpl<unsigned> &UsedRegs) {
180 assert(!IS.isEliminated());
181
182 for (ReadState &RS : IS.getUses())
183 PRF.addRegisterRead(RS, STI);
184
185 for (WriteState &WS : IS.getDefs())
186 PRF.addRegisterWrite(WriteRef(SourceIndex, &WS), UsedRegs);
187 }
188
notifyInstructionIssue(const InstRef & IR,const SmallVectorImpl<std::pair<ResourceRef,ResourceCycles>> & UsedRes,const Stage & S)189 static void notifyInstructionIssue(
190 const InstRef &IR,
191 const SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedRes,
192 const Stage &S) {
193
194 S.notifyEvent<HWInstructionEvent>(
195 HWInstructionEvent(HWInstructionEvent::Ready, IR));
196 S.notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, UsedRes));
197
198 LLVM_DEBUG(dbgs() << "[E] Issued #" << IR << "\n");
199 }
200
notifyInstructionDispatch(const InstRef & IR,unsigned Ops,const SmallVectorImpl<unsigned> & UsedRegs,const Stage & S)201 static void notifyInstructionDispatch(const InstRef &IR, unsigned Ops,
202 const SmallVectorImpl<unsigned> &UsedRegs,
203 const Stage &S) {
204
205 S.notifyEvent<HWInstructionEvent>(
206 HWInstructionDispatchedEvent(IR, UsedRegs, Ops));
207
208 LLVM_DEBUG(dbgs() << "[E] Dispatched #" << IR << "\n");
209 }
210
execute(InstRef & IR)211 llvm::Error InOrderIssueStage::execute(InstRef &IR) {
212 if (llvm::Error E = tryIssue(IR, &StallCyclesLeft))
213 return E;
214
215 if (StallCyclesLeft) {
216 StalledInst = IR;
217 }
218
219 return llvm::ErrorSuccess();
220 }
221
tryIssue(InstRef & IR,unsigned * StallCycles)222 llvm::Error InOrderIssueStage::tryIssue(InstRef &IR, unsigned *StallCycles) {
223 Instruction &IS = *IR.getInstruction();
224 unsigned SourceIndex = IR.getSourceIndex();
225 const InstrDesc &Desc = IS.getDesc();
226
227 if (!canExecute(IR, StallCycles)) {
228 LLVM_DEBUG(dbgs() << "[E] Stalled #" << IR << " for " << *StallCycles
229 << " cycles\n");
230 Bandwidth = 0;
231 return llvm::ErrorSuccess();
232 }
233
234 unsigned RCUTokenID = RetireControlUnit::UnhandledTokenID;
235 IS.dispatch(RCUTokenID);
236
237 SmallVector<unsigned, 4> UsedRegs(PRF.getNumRegisterFiles());
238 addRegisterReadWrite(PRF, IS, SourceIndex, STI, UsedRegs);
239
240 unsigned NumMicroOps = IS.getNumMicroOps();
241 notifyInstructionDispatch(IR, NumMicroOps, UsedRegs, *this);
242
243 SmallVector<std::pair<ResourceRef, ResourceCycles>, 4> UsedResources;
244 RM->issueInstruction(Desc, UsedResources);
245 IS.execute(SourceIndex);
246
247 // Replace resource masks with valid resource processor IDs.
248 for (std::pair<ResourceRef, ResourceCycles> &Use : UsedResources) {
249 uint64_t Mask = Use.first.first;
250 Use.first.first = RM->resolveResourceMask(Mask);
251 }
252 notifyInstructionIssue(IR, UsedResources, *this);
253
254 bool ShouldCarryOver = NumMicroOps > Bandwidth;
255 if (ShouldCarryOver) {
256 CarryOver = NumMicroOps - Bandwidth;
257 CarriedOver = IR;
258 Bandwidth = 0;
259 NumIssued += Bandwidth;
260 LLVM_DEBUG(dbgs() << "[N] Carry over #" << IR << " \n");
261 } else {
262 NumIssued += NumMicroOps;
263 Bandwidth = Desc.EndGroup ? 0 : Bandwidth - NumMicroOps;
264 }
265
266 IssuedInst.push_back(IR);
267
268 if (!IR.getInstruction()->getDesc().RetireOOO)
269 LastWriteBackCycle = findLastWriteBackCycle(IR);
270
271 return llvm::ErrorSuccess();
272 }
273
updateIssuedInst()274 void InOrderIssueStage::updateIssuedInst() {
275 // Update other instructions. Executed instructions will be retired during the
276 // next cycle.
277 unsigned NumExecuted = 0;
278 for (auto I = IssuedInst.begin(), E = IssuedInst.end();
279 I != (E - NumExecuted);) {
280 InstRef &IR = *I;
281 Instruction &IS = *IR.getInstruction();
282
283 IS.cycleEvent();
284 if (!IS.isExecuted()) {
285 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR
286 << " is still executing\n");
287 ++I;
288 continue;
289 }
290
291 PRF.onInstructionExecuted(&IS);
292 notifyEvent<HWInstructionEvent>(
293 HWInstructionEvent(HWInstructionEvent::Executed, IR));
294 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n");
295 ++NumExecuted;
296
297 retireInstruction(*I);
298
299 std::iter_swap(I, E - NumExecuted);
300 }
301
302 if (NumExecuted)
303 IssuedInst.resize(IssuedInst.size() - NumExecuted);
304 }
305
updateCarriedOver()306 void InOrderIssueStage::updateCarriedOver() {
307 if (!CarriedOver)
308 return;
309
310 assert(!StalledInst && "A stalled instruction cannot be carried over.");
311
312 if (CarryOver > Bandwidth) {
313 CarryOver -= Bandwidth;
314 Bandwidth = 0;
315 LLVM_DEBUG(dbgs() << "[N] Carry over (" << CarryOver << "uops left) #"
316 << CarriedOver << " \n");
317 return;
318 }
319
320 LLVM_DEBUG(dbgs() << "[N] Carry over (complete) #" << CarriedOver
321 << " \n");
322
323 if (CarriedOver.getInstruction()->getDesc().EndGroup)
324 Bandwidth = 0;
325 else
326 Bandwidth -= CarryOver;
327
328 CarriedOver = InstRef();
329 CarryOver = 0;
330 }
331
retireInstruction(InstRef & IR)332 void InOrderIssueStage::retireInstruction(InstRef &IR) {
333 Instruction &IS = *IR.getInstruction();
334 IS.retire();
335
336 llvm::SmallVector<unsigned, 4> FreedRegs(PRF.getNumRegisterFiles());
337 for (const WriteState &WS : IS.getDefs())
338 PRF.removeRegisterWrite(WS, FreedRegs);
339
340 notifyEvent<HWInstructionEvent>(HWInstructionRetiredEvent(IR, FreedRegs));
341 LLVM_DEBUG(dbgs() << "[E] Retired #" << IR << " \n");
342 }
343
cycleStart()344 llvm::Error InOrderIssueStage::cycleStart() {
345 NumIssued = 0;
346 Bandwidth = SM.IssueWidth;
347
348 PRF.cycleStart();
349
350 // Release consumed resources.
351 SmallVector<ResourceRef, 4> Freed;
352 RM->cycleEvent(Freed);
353
354 updateIssuedInst();
355
356 // Continue to issue the instruction carried over from the previous cycle
357 updateCarriedOver();
358
359 // Issue instructions scheduled for this cycle
360 if (!StallCyclesLeft && StalledInst) {
361 if (llvm::Error E = tryIssue(StalledInst, &StallCyclesLeft))
362 return E;
363 }
364
365 if (!StallCyclesLeft) {
366 StalledInst.invalidate();
367 assert(NumIssued <= SM.IssueWidth && "Overflow.");
368 } else {
369 // The instruction is still stalled, cannot issue any new instructions in
370 // this cycle.
371 Bandwidth = 0;
372 }
373
374 return llvm::ErrorSuccess();
375 }
376
cycleEnd()377 llvm::Error InOrderIssueStage::cycleEnd() {
378 PRF.cycleEnd();
379
380 if (StallCyclesLeft > 0)
381 --StallCyclesLeft;
382
383 if (LastWriteBackCycle > 0)
384 --LastWriteBackCycle;
385
386 return llvm::ErrorSuccess();
387 }
388
389 } // namespace mca
390 } // namespace llvm
391