1//===- AMDGPUInsertDelayAlu.cpp - Insert s_delay_alu instructions ---------===//
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//
9/// \file
10/// Insert s_delay_alu instructions to avoid stalls on GFX11+.
11//
12//===----------------------------------------------------------------------===//
13
14#include "AMDGPU.h"
15#include "GCNSubtarget.h"
16#include "SIInstrInfo.h"
17#include "SIMachineFunctionInfo.h"
18
19using namespace llvm;
20
21#define DEBUG_TYPE "amdgpu-insert-delay-alu"
22
23namespace {
24
25class AMDGPUInsertDelayAlu {
26public:
27 const GCNSubtarget *ST;
28 const SIInstrInfo *SII;
29 const TargetRegisterInfo *TRI;
30
31 const TargetSchedModel *SchedModel;
32
33 // Return true if MI waits for all outstanding VALU instructions to complete.
34 static bool instructionWaitsForVALU(const MachineInstr &MI) {
35 // These instruction types wait for VA_VDST==0 before issuing.
36 if (SIInstrFlags::isDS(O: MI) || SIInstrFlags::isEXP(O: MI) ||
37 SIInstrFlags::isFLAT(O: MI) || SIInstrFlags::isMIMG(O: MI) ||
38 SIInstrFlags::isBuffer(O: MI))
39 return true;
40 if (MI.getOpcode() == AMDGPU::S_SENDMSG_RTN_B32 ||
41 MI.getOpcode() == AMDGPU::S_SENDMSG_RTN_B64)
42 return true;
43 if (MI.getOpcode() == AMDGPU::S_WAITCNT_DEPCTR &&
44 AMDGPU::DepCtr::decodeFieldVaVdst(Encoded: MI.getOperand(i: 0).getImm()) == 0)
45 return true;
46 return false;
47 }
48
49 static bool instructionWaitsForSGPRWrites(const MachineInstr &MI) {
50 // These instruction types wait for VA_SDST==0 before issuing.
51 if (SIInstrFlags::isSMRD(O: MI))
52 return true;
53
54 if (SIInstrFlags::isSALU(O: MI)) {
55 for (auto &Op : MI.operands()) {
56 if (Op.isReg())
57 return true;
58 }
59 }
60 return false;
61 }
62
63 // Types of delay that can be encoded in an s_delay_alu instruction.
64 enum DelayType { VALU, TRANS, SALU, OTHER };
65
66 // Get the delay type for a MachineInstr.
67 DelayType getDelayType(const MachineInstr &MI, bool AllowLDSDMA) {
68 // Non-F64 TRANS instructions use a separate delay type.
69 if (SIInstrInfo::isTRANS(MI) &&
70 !AMDGPU::isDPMACCInstruction(Opc: MI.getOpcode()))
71 return TRANS;
72 // WMMA XDL ops are treated the same as TRANS.
73 if (ST->hasGFX1250Insts() && SII->isXDLWMMA(MI))
74 return TRANS;
75 if (SIInstrInfo::isVALU(MI, AllowLDSDMA))
76 return VALU;
77 if (SIInstrInfo::isSALU(MI))
78 return SALU;
79 return OTHER;
80 }
81
82 // Information about the last instruction(s) that wrote to a particular
83 // regunit. In straight-line code there will only be one such instruction, but
84 // when control flow converges we merge the delay information from each path
85 // to represent the union of the worst-case delays of each type.
86 struct DelayInfo {
87 // One larger than the maximum number of (non-TRANS) VALU instructions we
88 // can encode in an s_delay_alu instruction.
89 static constexpr unsigned VALU_MAX = 5;
90
91 // One larger than the maximum number of TRANS instructions we can encode in
92 // an s_delay_alu instruction.
93 static constexpr unsigned TRANS_MAX = 4;
94
95 // One larger than the maximum number of SALU cycles we can encode in an
96 // s_delay_alu instruction.
97 static constexpr unsigned SALU_CYCLES_MAX = 4;
98
99 // If it was written by a (non-TRANS) VALU, remember how many clock cycles
100 // are left until it completes, and how many other (non-TRANS) VALU we have
101 // seen since it was issued.
102 uint8_t VALUCycles = 0;
103 uint8_t VALUNum = VALU_MAX;
104
105 // If it was written by a TRANS, remember how many clock cycles are left
106 // until it completes, and how many other TRANS we have seen since it was
107 // issued.
108 uint8_t TRANSCycles = 0;
109 uint8_t TRANSNum = TRANS_MAX;
110 // Also remember how many other (non-TRANS) VALU we have seen since it was
111 // issued. When an instruction depends on both a prior TRANS and a prior
112 // non-TRANS VALU, this is used to decide whether to encode a wait for just
113 // one or both of them.
114 uint8_t TRANSNumVALU = VALU_MAX;
115
116 // If it was written by an SALU, remember how many clock cycles are left
117 // until it completes.
118 uint8_t SALUCycles = 0;
119
120 DelayInfo() = default;
121
122 DelayInfo(DelayType Type, unsigned Cycles) {
123 switch (Type) {
124 default:
125 llvm_unreachable("unexpected type");
126 case VALU:
127 VALUCycles = Cycles;
128 VALUNum = 0;
129 break;
130 case TRANS:
131 TRANSCycles = Cycles;
132 TRANSNum = 0;
133 TRANSNumVALU = 0;
134 break;
135 case SALU:
136 // Guard against pseudo-instructions like SI_CALL which are marked as
137 // SALU but with a very high latency.
138 SALUCycles = std::min(a: Cycles, b: SALU_CYCLES_MAX);
139 break;
140 }
141 }
142
143 bool operator==(const DelayInfo &RHS) const {
144 return VALUCycles == RHS.VALUCycles && VALUNum == RHS.VALUNum &&
145 TRANSCycles == RHS.TRANSCycles && TRANSNum == RHS.TRANSNum &&
146 TRANSNumVALU == RHS.TRANSNumVALU && SALUCycles == RHS.SALUCycles;
147 }
148
149 bool operator!=(const DelayInfo &RHS) const { return !(*this == RHS); }
150
151 // Merge another DelayInfo into this one, to represent the union of the
152 // worst-case delays of each type.
153 void merge(const DelayInfo &RHS) {
154 VALUCycles = std::max(a: VALUCycles, b: RHS.VALUCycles);
155 VALUNum = std::min(a: VALUNum, b: RHS.VALUNum);
156 TRANSCycles = std::max(a: TRANSCycles, b: RHS.TRANSCycles);
157 TRANSNum = std::min(a: TRANSNum, b: RHS.TRANSNum);
158 TRANSNumVALU = std::min(a: TRANSNumVALU, b: RHS.TRANSNumVALU);
159 SALUCycles = std::max(a: SALUCycles, b: RHS.SALUCycles);
160 }
161
162 // Update this DelayInfo after issuing an instruction of the specified type.
163 // Cycles is the number of cycles it takes to issue the instruction. Return
164 // true if there is no longer any useful delay info.
165 bool advance(DelayType Type, unsigned Cycles) {
166 bool Erase = true;
167
168 VALUNum += (Type == VALU);
169 if (VALUNum >= VALU_MAX || VALUCycles <= Cycles) {
170 // Forget about the VALU instruction. It was too far back or has
171 // definitely completed by now.
172 VALUNum = VALU_MAX;
173 VALUCycles = 0;
174 } else {
175 VALUCycles -= Cycles;
176 Erase = false;
177 }
178
179 TRANSNum += (Type == TRANS);
180 TRANSNumVALU += (Type == VALU);
181 if (TRANSNum >= TRANS_MAX || TRANSCycles <= Cycles) {
182 // Forget about any TRANS instruction. It was too far back or has
183 // definitely completed by now.
184 TRANSNum = TRANS_MAX;
185 TRANSNumVALU = VALU_MAX;
186 TRANSCycles = 0;
187 } else {
188 TRANSCycles -= Cycles;
189 Erase = false;
190 }
191
192 if (SALUCycles <= Cycles) {
193 // Forget about any SALU instruction. It has definitely completed by
194 // now.
195 SALUCycles = 0;
196 } else {
197 SALUCycles -= Cycles;
198 Erase = false;
199 }
200
201 return Erase;
202 }
203
204#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
205 void dump() const {
206 if (VALUCycles)
207 dbgs() << " VALUCycles=" << (int)VALUCycles;
208 if (VALUNum < VALU_MAX)
209 dbgs() << " VALUNum=" << (int)VALUNum;
210 if (TRANSCycles)
211 dbgs() << " TRANSCycles=" << (int)TRANSCycles;
212 if (TRANSNum < TRANS_MAX)
213 dbgs() << " TRANSNum=" << (int)TRANSNum;
214 if (TRANSNumVALU < VALU_MAX)
215 dbgs() << " TRANSNumVALU=" << (int)TRANSNumVALU;
216 if (SALUCycles)
217 dbgs() << " SALUCycles=" << (int)SALUCycles;
218 }
219#endif
220 };
221
222 // A map from regunits to the delay info for that regunit.
223 struct DelayState : DenseMap<MCRegUnit, DelayInfo> {
224 // Merge another DelayState into this one by merging the delay info for each
225 // regunit.
226 void merge(const DelayState &RHS) {
227 for (const auto &KV : RHS) {
228 iterator It;
229 bool Inserted;
230 std::tie(args&: It, args&: Inserted) = insert(KV);
231 if (!Inserted)
232 It->second.merge(RHS: KV.second);
233 }
234 }
235
236 // Advance the delay info for each regunit, erasing any that are no longer
237 // useful.
238 void advance(DelayType Type, unsigned Cycles) {
239 remove_if(Pred: [&](auto &P) { return P.second.advance(Type, Cycles); });
240 }
241
242 void advanceByVALUNum(unsigned VALUNum) {
243 remove_if(Pred: [&](auto &P) {
244 return P.second.VALUNum >= VALUNum && P.second.VALUCycles > 0;
245 });
246 }
247
248#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
249 void dump(const TargetRegisterInfo *TRI) const {
250 if (empty()) {
251 dbgs() << " empty\n";
252 return;
253 }
254
255 // Dump DelayInfo for each RegUnit in numerical order.
256 SmallVector<const_iterator, 8> Order;
257 Order.reserve(size());
258 for (const_iterator I = begin(), E = end(); I != E; ++I)
259 Order.push_back(I);
260 llvm::sort(Order, [](const const_iterator &A, const const_iterator &B) {
261 return A->first < B->first;
262 });
263 for (const_iterator I : Order) {
264 dbgs() << " " << printRegUnit(I->first, TRI);
265 I->second.dump();
266 dbgs() << "\n";
267 }
268 }
269#endif
270 };
271
272 // The saved delay state at the end of each basic block.
273 DenseMap<MachineBasicBlock *, DelayState> BlockState;
274
275 // Emit an s_delay_alu instruction if necessary before MI.
276 MachineInstr *emitDelayAlu(MachineInstr &MI, DelayInfo Delay,
277 MachineInstr *LastDelayAlu) {
278 unsigned Imm = 0;
279
280 // Wait for a TRANS instruction.
281 if (Delay.TRANSNum < DelayInfo::TRANS_MAX)
282 Imm |= 4 + Delay.TRANSNum;
283
284 // Wait for a VALU instruction (if it's more recent than any TRANS
285 // instruction that we're also waiting for).
286 if (Delay.VALUNum < DelayInfo::VALU_MAX &&
287 Delay.VALUNum <= Delay.TRANSNumVALU) {
288 if (Imm & 0xf)
289 Imm |= Delay.VALUNum << 7;
290 else
291 Imm |= Delay.VALUNum;
292 }
293
294 // Wait for an SALU instruction.
295 if (Delay.SALUCycles) {
296 assert(Delay.SALUCycles < DelayInfo::SALU_CYCLES_MAX);
297 if (Imm & 0x780) {
298 // We have already encoded a VALU and a TRANS delay. There's no room in
299 // the encoding for an SALU delay as well, so just drop it.
300 } else if (Imm & 0xf) {
301 Imm |= (Delay.SALUCycles + 8) << 7;
302 } else {
303 Imm |= Delay.SALUCycles + 8;
304 }
305 }
306
307 // Don't emit the s_delay_alu instruction if there's nothing to wait for.
308 if (!Imm)
309 return LastDelayAlu;
310
311 // If we only need to wait for one instruction, try encoding it in the last
312 // s_delay_alu that we emitted.
313 if (!(Imm & 0x780) && LastDelayAlu) {
314 unsigned Skip = 0;
315 for (auto I = MachineBasicBlock::instr_iterator(LastDelayAlu),
316 E = MachineBasicBlock::instr_iterator(MI);
317 ++I != E;) {
318 if (I->getOpcode() == AMDGPU::S_SET_VGPR_MSB) {
319 // It is not deterministic whether the skip count counts
320 // S_SET_VGPR_MSB instructions or not, so do not include them in a
321 // skip region.
322 Skip = 6;
323 break;
324 }
325 if (!I->isBundle() && !I->isMetaInstruction())
326 ++Skip;
327 }
328 if (Skip < 6) {
329 MachineOperand &Op = LastDelayAlu->getOperand(i: 0);
330 unsigned LastImm = Op.getImm();
331 assert((LastImm & ~0xf) == 0 &&
332 "Remembered an s_delay_alu with no room for another delay!");
333 LastImm |= Imm << 7 | Skip << 4;
334 Op.setImm(LastImm);
335 return nullptr;
336 }
337 }
338
339 auto &MBB = *MI.getParent();
340 MachineInstr *DelayAlu =
341 BuildMI(BB&: MBB, I&: MI, MIMD: DebugLoc(), MCID: SII->get(Opcode: AMDGPU::S_DELAY_ALU)).addImm(Val: Imm);
342 // Remember the s_delay_alu for next time if there is still room in it to
343 // encode another delay.
344 return (Imm & 0x780) ? nullptr : DelayAlu;
345 }
346
347 bool runOnMachineBasicBlock(MachineBasicBlock &MBB, bool Emit) {
348 DelayState State;
349 for (auto *Pred : MBB.predecessors())
350 State.merge(RHS: BlockState[Pred]);
351
352 LLVM_DEBUG(dbgs() << " State at start of " << printMBBReference(MBB)
353 << "\n";
354 State.dump(TRI););
355
356 bool Changed = false;
357 MachineInstr *LastDelayAlu = nullptr;
358
359 // FIXME: 0 is a valid register unit.
360 MCRegUnit LastSGPRFromVALU = static_cast<MCRegUnit>(0);
361
362 // Destination of the preceding WMMA, for C-reuse detection.
363 Register PrevWMMAVDst;
364
365 // Iterate over the contents of bundles, but don't emit any instructions
366 // inside a bundle.
367 for (auto &MI : MBB.instrs()) {
368 if (MI.isBundle() || MI.isMetaInstruction())
369 continue;
370
371 // Ignore some more instructions that do not generate any code.
372 switch (MI.getOpcode()) {
373 case AMDGPU::SI_RETURN_TO_EPILOG:
374 continue;
375 }
376
377 // LDSDMA is VALU-tagged but only behaves like VALU for operand-use delay
378 // checks (e.g. v_readfirstlane -> tensor_load_to_lds). It must not
379 // publish or advance VALU delay state on its defs.
380 DelayType ProducerType = getDelayType(MI, /*AllowLDSDMA=*/false);
381 DelayType ConsumerType = getDelayType(MI, /*AllowLDSDMA=*/true);
382
383 if (instructionWaitsForSGPRWrites(MI)) {
384 auto It = State.find(Val: LastSGPRFromVALU);
385 if (It != State.end()) {
386 DelayInfo Info = It->getSecond();
387 State.advanceByVALUNum(VALUNum: Info.VALUNum);
388 // FIXME: 0 is a valid register unit.
389 LastSGPRFromVALU = static_cast<MCRegUnit>(0);
390 }
391 }
392
393 if (instructionWaitsForVALU(MI)) {
394 // Forget about all outstanding VALU delays.
395 // TODO: This is overkill since it also forgets about SALU delays.
396 State = DelayState();
397 } else if (ConsumerType != OTHER) {
398 DelayInfo Delay;
399 // C-reuse: back-to-back WMMAs into the same C register forward the
400 // accumulator in place, so the tied srcC read has no dependency. WMMA
401 // implies GFX11+, so no explicit subtarget check is needed.
402 bool IsWMMACReuse =
403 PrevWMMAVDst.isValid() && (SII->isWMMA(MI) || SII->isSWMMAC(MI));
404 // TODO: Scan implicit uses too?
405 for (const auto &Op : MI.explicit_uses()) {
406 if (Op.isReg()) {
407 // One of the operands of the writelane is also the output operand.
408 // This creates the insertion of redundant delays. Hence, we have to
409 // ignore this operand.
410 if (MI.getOpcode() == AMDGPU::V_WRITELANE_B32 && Op.isTied())
411 continue;
412 // Skip the tied srcC of a C-reuse edge.
413 if (IsWMMACReuse && Op.isTied() && Op.getReg() == PrevWMMAVDst)
414 continue;
415 for (MCRegUnit Unit : TRI->regunits(Reg: Op.getReg())) {
416 auto It = State.find(Val: Unit);
417 if (It != State.end()) {
418 Delay.merge(RHS: It->second);
419 State.erase(Val: Unit);
420 }
421 }
422 }
423 }
424
425 if (ProducerType == VALU) {
426 for (const auto &Op : MI.defs()) {
427 Register Reg = Op.getReg();
428 if (AMDGPU::isSGPR(Reg, TRI)) {
429 LastSGPRFromVALU = *TRI->regunits(Reg).begin();
430 break;
431 }
432 }
433 }
434
435 if (Emit && !MI.isBundledWithPred()) {
436 // TODO: For VALU->SALU delays should we use s_delay_alu or s_nop or
437 // just ignore them?
438 LastDelayAlu = emitDelayAlu(MI, Delay, LastDelayAlu);
439 }
440 }
441
442 if (ProducerType != OTHER) {
443 // TODO: Scan implicit defs too?
444 for (const auto &Op : MI.defs()) {
445 unsigned Latency = SchedModel->computeOperandLatency(
446 DefMI: &MI, DefOperIdx: Op.getOperandNo(), UseMI: nullptr, UseOperIdx: 0);
447 for (MCRegUnit Unit : TRI->regunits(Reg: Op.getReg()))
448 State[Unit] = DelayInfo(ProducerType, Latency);
449 }
450 }
451
452 // Advance by the number of cycles it takes to issue this instruction.
453 // TODO: Use a more advanced model that accounts for instructions that
454 // take multiple cycles to issue on a particular pipeline.
455 unsigned Cycles = SIInstrInfo::getNumWaitStates(MI);
456 // TODO: In wave64 mode, double the number of cycles for VALU and VMEM
457 // instructions on the assumption that they will usually have to be issued
458 // twice?
459 State.advance(Type: ProducerType, Cycles);
460
461 // Track the preceding WMMA's dst for C-reuse; reset on anything else.
462 if (SII->isWMMA(MI) || SII->isSWMMAC(MI)) {
463 const MachineOperand *VDst =
464 SII->getNamedOperand(MI, OperandName: AMDGPU::OpName::vdst);
465 PrevWMMAVDst = VDst ? VDst->getReg() : Register();
466 } else {
467 PrevWMMAVDst = Register();
468 }
469
470 LLVM_DEBUG(dbgs() << " State after " << MI; State.dump(TRI););
471 }
472
473 if (Emit) {
474 assert(State == BlockState[&MBB] &&
475 "Basic block state should not have changed on final pass!");
476 } else if (DelayState &BS = BlockState[&MBB]; State != BS) {
477 BS = std::move(State);
478 Changed = true;
479 }
480 return Changed;
481 }
482
483 bool run(MachineFunction &MF) {
484 LLVM_DEBUG(dbgs() << "AMDGPUInsertDelayAlu running on " << MF.getName()
485 << "\n");
486
487 ST = &MF.getSubtarget<GCNSubtarget>();
488 if (!ST->hasDelayAlu())
489 return false;
490
491 SIMachineFunctionInfo &MFI = *MF.getInfo<SIMachineFunctionInfo>();
492
493 if (MFI.getMaxWavesPerEU() == 1)
494 return false;
495
496 SII = ST->getInstrInfo();
497 TRI = ST->getRegisterInfo();
498 SchedModel = &SII->getSchedModel();
499
500 // Calculate the delay state for each basic block, iterating until we reach
501 // a fixed point.
502 SetVector<MachineBasicBlock *> WorkList;
503 for (auto &MBB : reverse(C&: MF))
504 WorkList.insert(X: &MBB);
505 while (!WorkList.empty()) {
506 auto &MBB = *WorkList.pop_back_val();
507 bool Changed = runOnMachineBasicBlock(MBB, Emit: false);
508 if (Changed)
509 WorkList.insert_range(R: MBB.successors());
510 }
511
512 LLVM_DEBUG(dbgs() << "Final pass over all BBs\n");
513
514 // Make one last pass over all basic blocks to emit s_delay_alu
515 // instructions.
516 bool Changed = false;
517 for (auto &MBB : MF)
518 Changed |= runOnMachineBasicBlock(MBB, Emit: true);
519 return Changed;
520 }
521};
522
523class AMDGPUInsertDelayAluLegacy : public MachineFunctionPass {
524public:
525 static char ID;
526
527 AMDGPUInsertDelayAluLegacy() : MachineFunctionPass(ID) {}
528
529 void getAnalysisUsage(AnalysisUsage &AU) const override {
530 AU.setPreservesCFG();
531 MachineFunctionPass::getAnalysisUsage(AU);
532 }
533
534 bool runOnMachineFunction(MachineFunction &MF) override {
535 if (skipFunction(F: MF.getFunction()))
536 return false;
537 AMDGPUInsertDelayAlu Impl;
538 return Impl.run(MF);
539 }
540};
541} // namespace
542
543PreservedAnalyses
544AMDGPUInsertDelayAluPass::run(MachineFunction &MF,
545 MachineFunctionAnalysisManager &MFAM) {
546 if (!AMDGPUInsertDelayAlu().run(MF))
547 return PreservedAnalyses::all();
548 auto PA = getMachineFunctionPassPreservedAnalyses();
549 PA.preserveSet<CFGAnalyses>();
550 return PA;
551} // end namespace llvm
552
553char AMDGPUInsertDelayAluLegacy::ID = 0;
554
555char &llvm::AMDGPUInsertDelayAluID = AMDGPUInsertDelayAluLegacy::ID;
556
557INITIALIZE_PASS(AMDGPUInsertDelayAluLegacy, DEBUG_TYPE,
558 "AMDGPU Insert Delay ALU", false, false)
559