1//===- GCNVOPDUtils.cpp - GCN VOPD Utils ------------------------===//
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 This file contains the AMDGPU DAG scheduling
10/// mutation to pair VOPD instructions back to back. It also contains
11// subroutines useful in the creation of VOPD instructions
12//
13//===----------------------------------------------------------------------===//
14
15#include "GCNVOPDUtils.h"
16#include "AMDGPUSubtarget.h"
17#include "GCNSubtarget.h"
18#include "SIInstrInfo.h"
19#include "Utils/AMDGPUBaseInfo.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineInstr.h"
24#include "llvm/CodeGen/MachineOperand.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/MacroFusion.h"
27#include "llvm/CodeGen/ScheduleDAG.h"
28#include "llvm/CodeGen/ScheduleDAGMutation.h"
29#include "llvm/CodeGen/TargetInstrInfo.h"
30#include "llvm/MC/MCInst.h"
31#include "llvm/TargetParser/AMDGPUTargetParser.h"
32
33using namespace llvm;
34
35#define DEBUG_TYPE "gcn-vopd-utils"
36
37// Return the register class of the VOPDOpc operand named
38// src/vsrc<SrcIdx><CompIdx>, which is the slot src<SrcIdx> of MI<CompIdx> maps
39// to.
40static const TargetRegisterClass *getVOPDSrcRegClass(const SIInstrInfo &TII,
41 int VOPDOpc,
42 unsigned CompIdx,
43 unsigned SrcIdx) {
44 using namespace AMDGPU;
45 int OpIdx = -1;
46 const bool IsX = CompIdx == VOPD::X;
47 switch (SrcIdx) {
48 case 0:
49 OpIdx = getNamedOperandIdx(Opcode: VOPDOpc, Name: IsX ? OpName::src0X : OpName::src0Y);
50 break;
51 case 1:
52 OpIdx = getNamedOperandIdx(Opcode: VOPDOpc, Name: IsX ? OpName::vsrc1X : OpName::vsrc1Y);
53 break;
54 case 2:
55 OpIdx = getNamedOperandIdx(Opcode: VOPDOpc, Name: IsX ? OpName::vsrc2X : OpName::vsrc2Y);
56 if (OpIdx == -1)
57 OpIdx = getNamedOperandIdx(Opcode: VOPDOpc, Name: IsX ? OpName::src2X : OpName::src2Y);
58 break;
59 default:
60 llvm_unreachable("unexpected VOPD source index");
61 }
62
63 assert(OpIdx != -1);
64 return TII.getRegClass(MCID: TII.get(Opcode: VOPDOpc), OpNum: OpIdx);
65}
66
67// Check if physical register from src<SrcIdx> operand of MI<CompIdx> matches
68// register class constraints in corresponding VOPDOpc operand with name
69// src/vsrc<SrcIdx><CompIdx>.
70static bool isValidVOPDSrc(const SIInstrInfo &TII, int VOPDOpc,
71 unsigned CompIdx, unsigned SrcIdx,
72 Register PhysSrcReg) {
73 return getVOPDSrcRegClass(TII, VOPDOpc, CompIdx, SrcIdx)
74 ->contains(Reg: PhysSrcReg);
75}
76
77static const MachineOperand &getNamedOp(const MachineInstr &MI,
78 AMDGPU::OpName Name) {
79 return MI.getOperand(i: getNamedOperandIdx(Opcode: MI.getOpcode(), Name));
80}
81
82// Check if MI is a VOP3P instruction with operands that satisfy the constraints
83// for mapping it to a VOP2/VOPD opcode: no modifiers, no clamp, src1 and src2
84// are registers (src0 can be register or literal), and src2 is same as dst.
85static bool canMapVOP3PToVOPD(const MachineInstr &MI) {
86 unsigned Opc = MI.getOpcode();
87 if (Opc != AMDGPU::V_DOT2_F32_F16 && Opc != AMDGPU::V_DOT2_F32_BF16)
88 return false;
89 // src0 can be register or literal
90 if (getNamedOp(MI, Name: AMDGPU::OpName::src0_modifiers).getImm() !=
91 SISrcMods::OP_SEL_1)
92 return false;
93 if (getNamedOp(MI, Name: AMDGPU::OpName::src1_modifiers).getImm() !=
94 SISrcMods::OP_SEL_1)
95 return false;
96 if (!getNamedOp(MI, Name: AMDGPU::OpName::src1).isReg())
97 return false;
98 if (getNamedOp(MI, Name: AMDGPU::OpName::src2_modifiers).getImm() !=
99 SISrcMods::OP_SEL_1)
100 return false;
101 if (!getNamedOp(MI, Name: AMDGPU::OpName::src2).isReg())
102 return false;
103 if (getNamedOp(MI, Name: AMDGPU::OpName::clamp).getImm() != 0)
104 return false;
105 return getNamedOp(MI, Name: AMDGPU::OpName::vdst).getReg() ==
106 getNamedOp(MI, Name: AMDGPU::OpName::src2).getReg();
107}
108
109// In a VOPD3 whose OPX is a 64-bit operation, an OPY VGPR source operand reads
110// back the wrong value if it is the last VGPR the wave owns.
111// A wave always owns a whole number of VGPR allocation granules, so only a
112// register just below a granule boundary can be the last one. The wave also
113// owns at least as many VGPRs as this function uses, so a source which has a
114// register above it in use here cannot be the last one either.
115// The number of VGPRs the wave is actually given is not available until the
116// assembler has seen the whole module, but that can only come out above this
117// function's own usage, so this is conservatively correct.
118static bool isVOPD3F64OPYSrcHazard(const SIInstrInfo &TII,
119 const MachineInstr &MIX,
120 const MachineInstr &MIY) {
121 const MachineFunction &MF = *MIX.getMF();
122 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
123 if (!ST.hasVOPD3F64OPYSrcHazard())
124 return false;
125
126 // Every 64-bit VOPD3 OPX opcode has a 64-bit vdst, and no 32-bit one has.
127 int VDstIdx =
128 AMDGPU::getNamedOperandIdx(Opcode: MIX.getOpcode(), Name: AMDGPU::OpName::vdst);
129 assert(VDstIdx != -1 && "VOPD3 OPX component must have a vdst");
130 if (TII.getOpSize(MI: MIX, OpNo: VDstIdx) != 8)
131 return false;
132
133 unsigned Granule =
134 AMDGPU::getVGPRAllocGranule(AK: ST.getTargetID().getGPUKind(), IsWave32: ST.isWave32());
135 const SIRegisterInfo *TRI = ST.getRegisterInfo();
136 unsigned NumVGPRs = TRI->getNumUsedPhysRegs(
137 MRI: MF.getRegInfo(), RC: AMDGPU::VGPR_32RegClass, /*IncludeCalls=*/false);
138 for (AMDGPU::OpName Name :
139 {AMDGPU::OpName::src0, AMDGPU::OpName::src1, AMDGPU::OpName::src2}) {
140 const MachineOperand *Src = TII.getNamedOperand(MI: MIY, OperandName: Name);
141 // Every OPY source which can be a VGPR is 32 bits wide.
142 if (!Src || !Src->isReg() ||
143 !AMDGPU::VGPR_32RegClass.contains(Reg: Src->getReg()))
144 continue;
145 unsigned Idx = TRI->getHWRegIndex(Reg: Src->getReg());
146 if ((Idx + 1) % Granule == 0 && Idx + 1 >= NumVGPRs)
147 return true;
148 }
149 return false;
150}
151
152static bool canMaterializeVOPDLiterals(const MachineFunction &MF) {
153 // A free register cannot be found without liveness. A move also makes the
154 // code longer, so a function which asked for small code keeps its literals.
155 return MF.getProperties().hasTracksLiveness() &&
156 !MF.getFunction().hasOptSize();
157}
158
159static bool
160checkVOPDRegConstraints(const SIInstrInfo &TII, const MachineInstr &MIX,
161 const MachineInstr &MIY, bool IsVOPD3,
162 bool AllowSameVGPR,
163 SmallVectorImpl<VOPDLiteralFixup> &LiteralFixups) {
164 namespace VOPD = AMDGPU::VOPD;
165
166 const MachineFunction *MF = MIX.getMF();
167 const GCNSubtarget &ST = MF->getSubtarget<GCNSubtarget>();
168
169 if (IsVOPD3 && !ST.hasVOPD3())
170 return false;
171 if (IsVOPD3 && isVOPD3F64OPYSrcHazard(TII, MIX, MIY))
172 return false;
173 if (!IsVOPD3 && ((TII.isVOP3(MI: MIX) && !canMapVOP3PToVOPD(MI: MIX)) ||
174 (TII.isVOP3(MI: MIY) && !canMapVOP3PToVOPD(MI: MIY))))
175 return false;
176 if (TII.isDPP(MI: MIX) || TII.isDPP(MI: MIY))
177 return false;
178
179 // Collected here and handed over only on success, so a failed check cannot
180 // leave anything behind.
181 SmallVector<VOPDLiteralFixup, 2> Fixups;
182
183 const SIRegisterInfo *TRI = ST.getRegisterInfo();
184 const MachineRegisterInfo &MRI = MF->getRegInfo();
185 // Literals also count against scalar bus limit
186 SmallVector<const MachineOperand *> UniqueLiterals;
187 auto AddLiteral = [&](const MachineOperand &Op) {
188 for (auto &Literal : UniqueLiterals) {
189 if (Literal->isIdenticalTo(Other: Op))
190 return;
191 }
192 UniqueLiterals.push_back(Elt: &Op);
193 };
194 // Immediates which the caller will move into a scalar register. Identical
195 // values share one register, so they count like one scalar operand each.
196 SmallSet<int32_t, 2> MaterializedLiterals;
197 SmallSet<Register, 4> UniqueScalarRegs;
198
199 unsigned EncodingFamily = AMDGPU::getVOPDEncodingFamily(ST);
200 unsigned XOpc = AMDGPU::getVOPDOpcode(Opc: MIX.getOpcode(), VOPD3: IsVOPD3);
201 unsigned YOpc = AMDGPU::getVOPDOpcode(Opc: MIY.getOpcode(), VOPD3: IsVOPD3);
202 int VOPDOpc = AMDGPU::getVOPDFull(OpX: XOpc, OpY: YOpc, EncodingFamily, VOPD3: IsVOPD3);
203 assert(VOPDOpc != -1);
204
205 auto InstInfo = AMDGPU::getVOPDInstInfo(OpX: MIX.getDesc(), OpY: MIY.getDesc());
206
207 for (auto CompIdx : VOPD::COMPONENTS) {
208 const MachineInstr &MI = (CompIdx == VOPD::X) ? MIX : MIY;
209
210 const MachineOperand &Src0 = *TII.getNamedOperand(MI, OperandName: AMDGPU::OpName::src0);
211 if (Src0.isReg()) {
212 if (!isValidVOPDSrc(TII, VOPDOpc, CompIdx, SrcIdx: 0, PhysSrcReg: Src0.getReg()))
213 return false;
214 if (TII.regUsesConstantBus(Reg: Src0, MRI))
215 UniqueScalarRegs.insert(V: Src0.getReg());
216 } else if (!TII.isInlineConstant(MO: Src0)) {
217 if (!IsVOPD3) {
218 AddLiteral(Src0);
219 } else {
220 // A VOPD3 component cannot encode a literal, but src0 can read a
221 // scalar register. The pair is therefore still possible if the caller
222 // moves the value into one.
223 if (!canMaterializeVOPDLiterals(MF: *MF) || !Src0.isImm())
224 return false;
225 // Only a 32-bit slot is handled, because the caller produces the value
226 // with a single S_MOV_B32.
227 int OpIdx = getNamedOperandIdx(Opcode: MI.getOpcode(), Name: AMDGPU::OpName::src0);
228 if (TII.getOpSize(MI, OpNo: OpIdx) != 4)
229 return false;
230 const TargetRegisterClass *SlotRC =
231 TRI->getCommonSubClass(A: getVOPDSrcRegClass(TII, VOPDOpc, CompIdx, SrcIdx: 0),
232 B: &AMDGPU::SGPR_32RegClass);
233 if (!SlotRC)
234 return false;
235 // Only the low bits reach the register, so two operands which name
236 // the same value share one move whichever way they were written.
237 int32_t Imm = static_cast<int32_t>(Src0.getImm());
238 MaterializedLiterals.insert(V: Imm);
239 Fixups.push_back(Elt: {.CompIdx: CompIdx, .OpIdx: static_cast<unsigned>(OpIdx), .Imm: Imm, .SlotRC: SlotRC});
240 }
241 }
242
243 // V_FMAMK_F32 (src1) and V_FMAAK_F32 (src2) have a mandatory literal.
244 // VOPD3 instructions don't set MandatoryLiteralIdx.
245 if (InstInfo[CompIdx].hasMandatoryLiteral()) {
246 auto CompOprIdx = InstInfo[CompIdx].getMandatoryLiteralCompOperandIndex();
247 AddLiteral(MI.getOperand(i: CompOprIdx));
248 }
249
250 // VOPD only. Affects V_CNDMASK_B32_e32.
251 if (MI.getDesc().hasImplicitUseOfPhysReg(Reg: AMDGPU::VCC))
252 UniqueScalarRegs.insert(V: AMDGPU::VCC_LO);
253
254 if (const MachineOperand *Src1 =
255 TII.getNamedOperand(MI, OperandName: AMDGPU::OpName::src1)) {
256 if (Src1->isReg()) {
257 if (!isValidVOPDSrc(TII, VOPDOpc, CompIdx, SrcIdx: 1, PhysSrcReg: Src1->getReg()))
258 return false;
259 assert(TRI->isVectorRegister(MRI, Src1->getReg()));
260 } else if (IsVOPD3) {
261 return false;
262 }
263 }
264
265 if (IsVOPD3) {
266 if (const MachineOperand *Src2 =
267 TII.getNamedOperand(MI, OperandName: AMDGPU::OpName::src2)) {
268 if (AMDGPU::hasNamedOperand(Opcode: MI.getOpcode(), NamedIdx: AMDGPU::OpName::bitop3)) {
269 // BITOP3 can be converted to DUAL_BITOP2 when src2 is zero.
270 if (!Src2->isImm() || Src2->getImm())
271 return false;
272 } else {
273 if (!Src2->isReg())
274 return false;
275 if (!isValidVOPDSrc(TII, VOPDOpc, CompIdx, SrcIdx: 2, PhysSrcReg: Src2->getReg()))
276 return false;
277 if (TII.regUsesConstantBus(Reg: *Src2, MRI)) {
278 assert(MI.getOpcode() == AMDGPU::V_CNDMASK_B32_e64);
279 UniqueScalarRegs.insert(V: Src2->getReg());
280 }
281 }
282 }
283 for (auto OpName : {AMDGPU::OpName::clamp, AMDGPU::OpName::omod,
284 AMDGPU::OpName::op_sel}) {
285 if (TII.hasModifiersSet(MI, OpName))
286 return false;
287 }
288
289 // Neg is allowed, other modifiers are not. NB: even though sext has the
290 // same value as neg, there are no combinable instructions with sext.
291 for (auto OpName :
292 {AMDGPU::OpName::src0_modifiers, AMDGPU::OpName::src1_modifiers,
293 AMDGPU::OpName::src2_modifiers}) {
294 const MachineOperand *Mods = TII.getNamedOperand(MI, OperandName: OpName);
295 if (Mods && (Mods->getImm() & ~SISrcMods::NEG))
296 return false;
297 }
298 }
299 }
300
301 if (UniqueLiterals.size() > 1)
302 return false;
303 // Keep materialization pair-local and do not increase instruction count or
304 // register pressure by producing two different values for one pair.
305 if (MaterializedLiterals.size() > 1)
306 return false;
307 if ((UniqueLiterals.size() + MaterializedLiterals.size() +
308 UniqueScalarRegs.size()) > 2)
309 return false;
310
311 auto GetVRegIdx = [&](unsigned OpcodeIdx, unsigned OperandIdx) {
312 const MachineInstr &MI = (OpcodeIdx == VOPD::X) ? MIX : MIY;
313 const MachineOperand &Operand = MI.getOperand(i: OperandIdx);
314 if (Operand.isReg() && TRI->isVectorRegister(MRI, Reg: Operand.getReg()))
315 return Operand.getReg();
316 return Register();
317 };
318
319 // On GFX1170+ if both OpX and OpY are V_MOV_B32 then OPY uses SRC2
320 // source-cache.
321 bool SkipSrc = (ST.hasGFX11_7Insts() || ST.hasGFX12Insts()) &&
322 MIX.getOpcode() == AMDGPU::V_MOV_B32_e32 &&
323 MIY.getOpcode() == AMDGPU::V_MOV_B32_e32;
324
325 // Check VGPR bank constraints for operand registers across both instructions.
326 if (InstInfo.hasInvalidOperand(GetRegIdx: GetVRegIdx, MRI: *TRI, SkipSrc, AllowSameVGPR,
327 VOPD3: IsVOPD3, HasGFX11InterlockHazard: ST.hasVOPDInterlockHazard()))
328 return false;
329
330 LLVM_DEBUG(dbgs() << "VOPD Reg Constraints Passed\n\tX: " << MIX
331 << "\n\tY: " << MIY << "\n");
332 LiteralFixups.assign(RHS: Fixups);
333 return true;
334}
335
336/// Core pair-eligibility check for a single VOPD encoding variant (VOPD or
337/// VOPD3). Returns the X/Y assignment on success, or std::nullopt otherwise.
338static std::optional<VOPDMatchInfo>
339tryMatchVOPDPairVariant(const SIInstrInfo &TII, unsigned EncodingFamily,
340 MachineInstr &FirstMI, MachineInstr &SecondMI,
341 bool IsVOPD3) {
342 unsigned Opc = FirstMI.getOpcode();
343 unsigned Opc2 = SecondMI.getOpcode();
344 AMDGPU::CanBeVOPD FirstCanBeVOPD =
345 AMDGPU::getCanBeVOPD(Opc, EncodingFamily, VOPD3: IsVOPD3);
346 AMDGPU::CanBeVOPD SecondCanBeVOPD =
347 AMDGPU::getCanBeVOPD(Opc: Opc2, EncodingFamily, VOPD3: IsVOPD3);
348
349 if (!(FirstCanBeVOPD.X && SecondCanBeVOPD.Y) &&
350 !(FirstCanBeVOPD.Y && SecondCanBeVOPD.X))
351 return std::nullopt;
352
353 // If SecondMI depends on FirstMI they cannot execute at the same time.
354 if (TII.hasRAWDependency(FirstMI, SecondMI))
355 return std::nullopt;
356
357 const GCNSubtarget &ST = TII.getSubtarget();
358 bool AllowSameVGPR = ST.hasGFX12Insts();
359
360 // Only a VOPD3 component can need a fixup; a plain one may hold a literal.
361 // checkVOPDRegConstraints() only writes this when it succeeds.
362 SmallVector<VOPDLiteralFixup, 2> Fixups;
363
364 if (FirstCanBeVOPD.X && SecondCanBeVOPD.Y) {
365 if (checkVOPDRegConstraints(TII, MIX: FirstMI, MIY: SecondMI, IsVOPD3, AllowSameVGPR,
366 LiteralFixups&: Fixups))
367 return VOPDMatchInfo{
368 .InOrder: {&FirstMI, &SecondMI}, .XIdx: 0, .IsVOPD3: IsVOPD3, .LiteralFixups: std::move(Fixups)};
369 }
370
371 if (FirstCanBeVOPD.Y && SecondCanBeVOPD.X) {
372 // AllowSameVGPR relaxes the VGPR bank overlap check for source operands.
373 // Only enable it when there is no antidependency.
374 bool IsAntiDep = TII.hasRAWDependency(FirstMI: SecondMI, SecondMI: FirstMI);
375 AllowSameVGPR &= !IsAntiDep;
376 if (IsAntiDep && !TII.isVOPDAntidependencyAllowed(MI: SecondMI))
377 return std::nullopt;
378 if (checkVOPDRegConstraints(TII, MIX: SecondMI, MIY: FirstMI, IsVOPD3, AllowSameVGPR,
379 LiteralFixups&: Fixups))
380 return VOPDMatchInfo{
381 .InOrder: {&FirstMI, &SecondMI}, .XIdx: 1, .IsVOPD3: IsVOPD3, .LiteralFixups: std::move(Fixups)};
382 }
383
384 return std::nullopt;
385}
386
387std::optional<VOPDMatchInfo> llvm::tryMatchVOPDPair(const SIInstrInfo &TII,
388 MachineInstr &FirstMI,
389 MachineInstr &SecondMI) {
390 const GCNSubtarget &ST = TII.getSubtarget();
391 unsigned EncodingFamily = AMDGPU::getVOPDEncodingFamily(ST);
392 if (auto Match = tryMatchVOPDPairVariant(TII, EncodingFamily, FirstMI,
393 SecondMI, /*IsVOPD3=*/false))
394 return Match;
395 if (ST.hasVOPD3())
396 return tryMatchVOPDPairVariant(TII, EncodingFamily, FirstMI, SecondMI,
397 /*IsVOPD3=*/true);
398 return std::nullopt;
399}
400
401/// Check if the instr pair, FirstMI and SecondMI, should be scheduled
402/// together. Given SecondMI, when FirstMI is unspecified, then check if
403/// SecondMI may be part of a fused pair at all.
404static bool shouldScheduleVOPDAdjacent(const TargetInstrInfo &TII,
405 const TargetSubtargetInfo &TSI,
406 const MachineInstr *FirstMI,
407 const MachineInstr &SecondMI,
408 const SDep *) {
409 const SIInstrInfo &STII = static_cast<const SIInstrInfo &>(TII);
410 const GCNSubtarget &ST = STII.getSubtarget();
411
412 // One instruction case: just check whether SecondMI is eligible at all.
413 if (!FirstMI) {
414 unsigned EncodingFamily = AMDGPU::getVOPDEncodingFamily(ST);
415 unsigned Opc2 = SecondMI.getOpcode();
416 auto CheckCanBeVOPD = [&](bool VOPD3) {
417 AMDGPU::CanBeVOPD CanBeVOPD =
418 AMDGPU::getCanBeVOPD(Opc: Opc2, EncodingFamily, VOPD3);
419 return CanBeVOPD.Y || CanBeVOPD.X;
420 };
421 return CheckCanBeVOPD(false) || (ST.hasVOPD3() && CheckCanBeVOPD(true));
422 }
423
424#ifdef EXPENSIVE_CHECKS
425 assert([&]() -> bool {
426 for (auto MII = MachineBasicBlock::const_iterator(FirstMI);
427 MII != FirstMI->getParent()->instr_end(); ++MII) {
428 if (&*MII == &SecondMI)
429 return true;
430 }
431 return false;
432 }() && "Expected FirstMI to precede SecondMI");
433#endif
434
435 return tryMatchVOPDPair(TII: STII, FirstMI&: *const_cast<MachineInstr *>(FirstMI),
436 SecondMI&: const_cast<MachineInstr &>(SecondMI))
437 .has_value();
438}
439
440/// Collect all load (dependents if \p Forward else dependencies) that connect
441/// to the \p Head SU.
442/// \p Visited should allocate enough bits for the number of SUnits, but its
443/// value can otherwise be uninitialized.
444static void collectLoads(SmallPtrSet<SUnit *, 8> &Loads, BitVector &Visited,
445 SUnit &Head, bool Forward, bool StopAtLoads) {
446 if (Head.isBoundaryNode())
447 return;
448
449 Visited.reset();
450
451 SmallVector<SUnit *> Stack;
452 Stack.push_back(Elt: &Head);
453 while (!Stack.empty()) {
454 SUnit *SU = Stack.pop_back_val();
455 const SmallVector<SDep, 4> &Deps = Forward ? SU->Succs : SU->Preds;
456 for (const SDep &Edge : Deps) {
457 if (StopAtLoads && Edge.getKind() != SDep::Data)
458 continue;
459 SUnit *Dep = Edge.getSUnit();
460 if (Dep->isBoundaryNode() || Visited.test(Idx: Dep->NodeNum))
461 continue;
462 Visited.set(Dep->NodeNum);
463
464 if (Dep->isInstr() && Dep->getInstr()->mayLoad()) {
465 Loads.insert(Ptr: Dep);
466 if (StopAtLoads)
467 continue;
468 }
469 Stack.push_back(Elt: Dep);
470 }
471 }
472}
473
474/// Checks whether fusing SU \p I with SU \p J would force the loads preceding
475/// \p J to complete before loads depending on \p I.
476///
477/// \p ILoadSuccs should hold all first load successors of \p I (via
478/// collectLoads with StopAtLoads=true). For set bits in \p LoadPredsComputed,
479/// the corresponding set in \p LoadPredsCache should hold all transitive load
480/// dependencies (via collectLoads with StopAtLoads=false). The \p Scratch
481/// bitvector should allocate enough bits for the number of SUnits.
482static bool loadsMayOverlap(
483 [[maybe_unused]] SUnit &I, const SmallPtrSet<SUnit *, 8> &ILoadSuccs,
484 SUnit &J, BitVector &LoadPredsComputed,
485 SmallVector<SmallPtrSet<SUnit *, 8>> &LoadPredsCache, BitVector &Scratch) {
486
487 if (ILoadSuccs.empty())
488 return false;
489
490 SmallPtrSet<SUnit *, 8> &JLoadPreds = LoadPredsCache[J.NodeNum];
491 if (!LoadPredsComputed.test(Idx: J.NodeNum)) {
492 collectLoads(Loads&: JLoadPreds, Visited&: Scratch, Head&: J, /*Forward=*/false,
493 /*StopAtLoads=*/true);
494 LoadPredsComputed.set(J.NodeNum);
495 }
496 if (JLoadPreds.empty())
497 return false;
498
499 for (SUnit *ILoad : ILoadSuccs) {
500 SmallPtrSet<SUnit *, 8> &ILoadDeps = LoadPredsCache[ILoad->NodeNum];
501 if (!LoadPredsComputed.test(Idx: ILoad->NodeNum)) {
502 collectLoads(Loads&: ILoadDeps, Visited&: Scratch, Head&: *ILoad, /*Forward=*/false,
503 /*StopAtLoads=*/false);
504 LoadPredsComputed.set(ILoad->NodeNum);
505 }
506
507 for (SUnit *JLoad : JLoadPreds) {
508 if (ILoad == JLoad) {
509 LLVM_DEBUG(
510 dbgs() << "Will not pair " << I << " with " << J << "\n"
511 << " Fusion would introduce a cyclic dependency with "
512 << *ILoad << "\n");
513 return true;
514 }
515
516 if (!ILoadDeps.contains(Ptr: JLoad)) {
517 LLVM_DEBUG(dbgs() << "Will not pair " << I << " with " << J << "\n"
518 << " Fusion may force " << *JLoad
519 << " to complete its load before dispatching "
520 << *ILoad << "\n");
521 return true;
522 }
523 }
524 }
525 return false;
526}
527
528namespace {
529/// Adapts design from MacroFusion
530/// Puts valid candidate instructions back-to-back so they can easily
531/// be turned into VOPD instructions
532/// Greedily pairs instruction candidates. O(n^2) algorithm.
533struct VOPDPairingMutation : ScheduleDAGMutation {
534 MacroFusionPredTy shouldScheduleAdjacent; // NOLINT: function pointer
535
536 VOPDPairingMutation(
537 MacroFusionPredTy shouldScheduleAdjacent) // NOLINT: function pointer
538 : shouldScheduleAdjacent(shouldScheduleAdjacent) {}
539
540 void apply(ScheduleDAGInstrs *DAG) override {
541 const TargetInstrInfo &TII = *DAG->TII;
542 const GCNSubtarget &ST = DAG->MF.getSubtarget<GCNSubtarget>();
543 if (!AMDGPU::hasVOPD(STI: ST) || !ST.isWave32()) {
544 LLVM_DEBUG(dbgs() << "Target does not support VOPDPairingMutation\n");
545 return;
546 }
547
548 BitVector VOPDCapable(DAG->SUnits.size());
549 unsigned IIdx = 0;
550 // Pre-compute whether each individual instruction can be VOPD
551 for (auto ISUI = DAG->SUnits.begin(), E = DAG->SUnits.end(); ISUI != E;
552 ++ISUI, ++IIdx) {
553 const MachineInstr *IMI = ISUI->getInstr();
554 if (shouldScheduleAdjacent(TII, ST, nullptr, *IMI, nullptr) &&
555 hasLessThanNumFused(SU: *ISUI, FuseLimit: 2))
556 VOPDCapable[IIdx] = true;
557 }
558
559 IIdx = 0;
560 SmallPtrSet<SUnit *, 8> ILoadSuccs;
561
562 // Cache collected load predecessors.
563 // For VOPDCapable nodes, this caches collectLoads with StopAtLoads=true
564 // For loads, this caches collectLoads with StopAtLoads=false
565 BitVector LoadPredsComputed(DAG->SUnits.size());
566 SmallVector<SmallPtrSet<SUnit *, 8>> LoadPredsCache(DAG->SUnits.size());
567
568 BitVector Scratch(DAG->SUnits.size());
569 for (auto ISUI = DAG->SUnits.begin(), E = DAG->SUnits.end(); ISUI != E;
570 ++ISUI, ++IIdx) {
571 if (!VOPDCapable[IIdx])
572 continue;
573 const MachineInstr *IMI = ISUI->getInstr();
574
575 ILoadSuccs.clear();
576 collectLoads(Loads&: ILoadSuccs, Visited&: Scratch, Head&: *ISUI, /*Forward=*/true,
577 /*StopAtLoads=*/true);
578
579 unsigned JIdx = IIdx + 1;
580 for (auto JSUI = ISUI + 1; JSUI != E; ++JSUI, ++JIdx) {
581 if (!VOPDCapable[JIdx] || JSUI->isBoundaryNode())
582 continue;
583 const MachineInstr *JMI = JSUI->getInstr();
584 if (!hasLessThanNumFused(SU: *JSUI, FuseLimit: 2) ||
585 !shouldScheduleAdjacent(TII, ST, IMI, *JMI, nullptr))
586 continue;
587
588 if (loadsMayOverlap(I&: *ISUI, ILoadSuccs, J&: *JSUI, LoadPredsComputed,
589 LoadPredsCache, Scratch))
590 continue;
591
592 if (fuseInstructionPair(DAG&: *DAG, FirstSU&: *ISUI, SecondSU&: *JSUI)) {
593 // Clear to prevent future checks/fusing
594 VOPDCapable[JIdx] = false;
595 break;
596 }
597 }
598 }
599 LLVM_DEBUG(dbgs() << "Completed VOPDPairingMutation\n");
600 }
601};
602} // namespace
603
604std::unique_ptr<ScheduleDAGMutation> llvm::createVOPDPairingMutation() {
605 return std::make_unique<VOPDPairingMutation>(args&: shouldScheduleVOPDAdjacent);
606}
607