1//===- GCNCreateVOPD.cpp - Create VOPD 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/// Form VOPD instructions from adjacent VALU operations on wave32. The post-RA
11/// scheduler puts likely component pairs next to each other. This pass checks
12/// their final physical-register constraints and selects a non-overlapping set.
13///
14/// VOPD3 components cannot encode literal operands. When all non-inline
15/// immediates in a pair have the same 32-bit value, the pass can materialize
16/// that value in an SGPR which is free over the pair. The move and its register
17/// stay pair-local, so fusion adds at most one move and does not extend
18/// register pressure across pairs.
19///
20/// The pass considers every adjacent candidate. It first maximizes the number
21/// of pairs, then minimizes scalar moves among equal-size matchings. The
22/// earlier candidate wins an exact tie.
23///
24//
25//===----------------------------------------------------------------------===//
26
27#include "AMDGPU.h"
28#include "GCNSubtarget.h"
29#include "GCNVOPDUtils.h"
30#include "SIInstrInfo.h"
31#include "Utils/AMDGPUBaseInfo.h"
32#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/SmallBitVector.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/CodeGen/LiveRegUnits.h"
36#include "llvm/CodeGen/MachineBasicBlock.h"
37#include "llvm/CodeGen/MachineInstr.h"
38#include "llvm/CodeGen/MachineOperand.h"
39#include "llvm/CodeGen/MachinePassManager.h"
40#include "llvm/CodeGen/MachineRegisterInfo.h"
41#include "llvm/Support/Debug.h"
42
43#define DEBUG_TYPE "gcn-create-vopd"
44STATISTIC(NumVOPDCreated, "Number of VOPD Insts Created.");
45STATISTIC(NumLiteralsMaterialized,
46 "Number of immediates moved into a scalar register to allow VOPD3 "
47 "pairing.");
48STATISTIC(NumCandidateEdgesWithoutFreeSGPR,
49 "Number of VOPD3 candidate edges skipped because no scalar register "
50 "was free for their immediate.");
51
52using namespace llvm;
53
54namespace {
55
56struct VOPDCandidate {
57 VOPDMatchInfo Match;
58 /// The register for Match.LiteralFixups, or a null register if none is free.
59 Register MaterializationReg;
60
61 bool needsMaterialization() const { return !Match.LiteralFixups.empty(); }
62
63 bool isFeasible() const {
64 return !needsMaterialization() || MaterializationReg;
65 }
66};
67
68} // namespace
69
70/// Add everything the instructions in [\p Begin, \p RangeEnd] touch to
71/// \p Live, which already holds what is live after \p RangeEnd.
72static void addRangeUses(LiveRegUnits &Live, MachineBasicBlock::iterator Begin,
73 MachineInstr &RangeEnd) {
74 MachineBasicBlock::iterator After =
75 std::next(x: MachineBasicBlock::iterator(&RangeEnd));
76 for (MachineInstr &MI : make_range(x: Begin, y: After)) {
77 if (!MI.isDebugInstr())
78 Live.accumulate(MI);
79 }
80}
81
82/// Return a scalar register which every fixup can read and which no value in
83/// \p Live occupies, or a null register. Low registers are preferred, because
84/// those are most likely in use already, so the function's register count does
85/// not grow.
86static Register takeFreeSGPR(const GCNSubtarget &ST,
87 const MachineRegisterInfo &MRI,
88 const LiveRegUnits &Live,
89 ArrayRef<VOPDLiteralFixup> Fixups) {
90 assert(!Fixups.empty());
91 const SIRegisterInfo *TRI = ST.getRegisterInfo();
92 for (MCPhysReg Reg : AMDGPU::SGPR_32RegClass) {
93 // SGPR_32 also holds the halves of VCC. Writing those changes VCCZ,
94 // which is not modelled by \p Live, so a free half is not safe to use.
95 if (MRI.isReserved(PhysReg: Reg) || TRI->isSubRegisterEq(RegA: AMDGPU::VCC, RegB: Reg) ||
96 !Live.available(Reg))
97 continue;
98 if (!all_of(Range&: Fixups, P: [Reg](const VOPDLiteralFixup &Fixup) {
99 return Fixup.SlotRC->contains(Reg);
100 }))
101 continue;
102 return Reg;
103 }
104 return Register();
105}
106
107namespace {
108
109class GCNCreateVOPD {
110public:
111 const GCNSubtarget *ST = nullptr;
112
113 void
114 assignMaterializationRegisters(MachineBasicBlock &MBB,
115 MutableArrayRef<VOPDCandidate> Candidates) {
116 auto Candidate = Candidates.rbegin();
117 auto SkipPlainCandidates = [&] {
118 while (Candidate != Candidates.rend() &&
119 !Candidate->needsMaterialization())
120 ++Candidate;
121 };
122 SkipPlainCandidates();
123 if (Candidate == Candidates.rend())
124 return;
125
126 const MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
127 LiveRegUnits Walk(*ST->getRegisterInfo());
128 Walk.addLiveOuts(MBB);
129
130 // Before stepping over an instruction, Walk holds what is live immediately
131 // after it. This answers every pair-local range in one backward walk.
132 for (MachineInstr &MI : reverse(C&: MBB)) {
133 if (Candidate != Candidates.rend() &&
134 Candidate->Match.InOrder[1] == &MI) {
135 LiveRegUnits RangeLive = Walk;
136 addRangeUses(Live&: RangeLive, Begin: Candidate->Match.InOrder[0]->getIterator(),
137 RangeEnd&: *Candidate->Match.InOrder[1]);
138 Candidate->MaterializationReg =
139 takeFreeSGPR(ST: *ST, MRI, Live: RangeLive, Fixups: Candidate->Match.LiteralFixups);
140 ++Candidate;
141 SkipPlainCandidates();
142 }
143 if (!MI.isDebugInstr())
144 Walk.stepBackward(MI);
145 }
146 assert(Candidate == Candidates.rend() &&
147 "every candidate range must end in this block");
148 }
149
150 static SmallVector<VOPDCandidate *, 8>
151 selectCandidates(MutableArrayRef<VOPDCandidate> Candidates) {
152 struct Score {
153 unsigned NumPairs = 0;
154 unsigned NumMoves = 0;
155 };
156
157 const size_t NumCandidates = Candidates.size();
158 SmallVector<Score, 8> Best(NumCandidates + 1);
159 SmallBitVector Take(NumCandidates);
160 auto NextNonOverlapping = [&](size_t I) {
161 size_t Next = I + 1;
162 if (Next != NumCandidates &&
163 Candidates[Next].Match.InOrder[0] == Candidates[I].Match.InOrder[1])
164 ++Next;
165 return Next;
166 };
167
168 // Maximize the number of pairs, then minimize the moves they need. Taking
169 // the current edge on an exact tie preserves the old left-to-right choice.
170 for (size_t I = NumCandidates; I-- != 0;) {
171 Best[I] = Best[I + 1];
172 if (!Candidates[I].isFeasible()) {
173 ++NumCandidateEdgesWithoutFreeSGPR;
174 continue;
175 }
176
177 Score With = Best[NextNonOverlapping(I)];
178 ++With.NumPairs;
179 With.NumMoves += Candidates[I].needsMaterialization();
180 if (With.NumPairs > Best[I].NumPairs ||
181 (With.NumPairs == Best[I].NumPairs &&
182 With.NumMoves <= Best[I].NumMoves)) {
183 Best[I] = With;
184 Take.set(I);
185 }
186 }
187
188 SmallVector<VOPDCandidate *, 8> Selected;
189 for (size_t I = 0; I != NumCandidates;) {
190 if (!Take[I]) {
191 ++I;
192 continue;
193 }
194 Selected.push_back(Elt: &Candidates[I]);
195 I = NextNonOverlapping(I);
196 }
197 return Selected;
198 }
199
200 void materializeLiteral(const SIInstrInfo &TII, VOPDCandidate &Candidate) {
201 if (!Candidate.needsMaterialization())
202 return;
203
204 ArrayRef<VOPDLiteralFixup> Fixups = Candidate.Match.LiteralFixups;
205 assert(Candidate.MaterializationReg);
206 assert(all_of(Fixups,
207 [Imm = Fixups.front().Imm](const VOPDLiteralFixup &Fixup) {
208 return Fixup.Imm == Imm;
209 }));
210
211 MachineInstr *InsertPt = Candidate.Match.InOrder[0];
212 BuildMI(BB&: *InsertPt->getParent(), I: InsertPt, MIMD: DebugLoc(),
213 MCID: TII.get(Opcode: AMDGPU::S_MOV_B32), DestReg: Candidate.MaterializationReg)
214 .addImm(Val: Fixups.front().Imm);
215 ++NumLiteralsMaterialized;
216
217 for (const VOPDLiteralFixup &Fixup : Fixups) {
218 MachineInstr *MI = Fixup.CompIdx == AMDGPU::VOPD::X
219 ? Candidate.Match.getMIX()
220 : Candidate.Match.getMIY();
221 MI->getOperand(i: Fixup.OpIdx)
222 .ChangeToRegister(Reg: Candidate.MaterializationReg, /*isDef=*/false);
223 }
224 }
225
226 bool doReplace(const SIInstrInfo *SII, VOPDMatchInfo &Match) {
227 MachineInstr *MIX = Match.getMIX();
228 MachineInstr *MIY = Match.getMIY();
229 unsigned Opc1 = MIX->getOpcode();
230 unsigned Opc2 = MIY->getOpcode();
231 unsigned EncodingFamily =
232 AMDGPU::getVOPDEncodingFamily(ST: SII->getSubtarget());
233 int NewOpcode =
234 AMDGPU::getVOPDFull(OpX: AMDGPU::getVOPDOpcode(Opc: Opc1, VOPD3: Match.IsVOPD3),
235 OpY: AMDGPU::getVOPDOpcode(Opc: Opc2, VOPD3: Match.IsVOPD3),
236 EncodingFamily, VOPD3: Match.IsVOPD3);
237 assert(NewOpcode != -1 &&
238 "Should have previously determined this as a possible VOPD\n");
239
240 auto VOPDInst =
241 BuildMI(BB&: *MIX->getParent(), I: MIX, MIMD: MIX->getDebugLoc(), MCID: SII->get(Opcode: NewOpcode))
242 .setMIFlags(MIX->getFlags() | MIY->getFlags());
243
244 namespace VOPD = AMDGPU::VOPD;
245 MachineInstr *MI[] = {MIX, MIY};
246 auto InstInfo = AMDGPU::getVOPDInstInfo(OpX: MIX->getDesc(), OpY: MIY->getDesc());
247
248 for (auto CompIdx : VOPD::COMPONENTS) {
249 auto MCOprIdx = InstInfo[CompIdx].getIndexOfDstInMCOperands();
250 VOPDInst.add(MO: MI[CompIdx]->getOperand(i: MCOprIdx));
251 }
252
253 const AMDGPU::OpName Mods[2][3] = {
254 {AMDGPU::OpName::src0X_modifiers, AMDGPU::OpName::vsrc1X_modifiers,
255 AMDGPU::OpName::vsrc2X_modifiers},
256 {AMDGPU::OpName::src0Y_modifiers, AMDGPU::OpName::vsrc1Y_modifiers,
257 AMDGPU::OpName::vsrc2Y_modifiers}};
258 const AMDGPU::OpName SrcMods[3] = {AMDGPU::OpName::src0_modifiers,
259 AMDGPU::OpName::src1_modifiers,
260 AMDGPU::OpName::src2_modifiers};
261 const unsigned VOPDOpc = VOPDInst->getOpcode();
262
263 for (auto CompIdx : VOPD::COMPONENTS) {
264 auto CompSrcOprNum = InstInfo[CompIdx].getCompSrcOperandsNum();
265 bool IsVOP3 = SII->isVOP3(MI: *MI[CompIdx]);
266 for (unsigned CompSrcIdx = 0; CompSrcIdx < CompSrcOprNum; ++CompSrcIdx) {
267 if (AMDGPU::hasNamedOperand(Opcode: VOPDOpc, NamedIdx: Mods[CompIdx][CompSrcIdx])) {
268 const MachineOperand *Mod =
269 SII->getNamedOperand(MI&: *MI[CompIdx], OperandName: SrcMods[CompSrcIdx]);
270 VOPDInst.addImm(Val: Mod ? Mod->getImm() : 0);
271 }
272 auto MCOprIdx =
273 InstInfo[CompIdx].getIndexOfSrcInMCOperands(CompSrcIdx, VOPD3: IsVOP3);
274 VOPDInst.add(MO: MI[CompIdx]->getOperand(i: MCOprIdx));
275 }
276 if (MI[CompIdx]->getOpcode() == AMDGPU::V_CNDMASK_B32_e32 &&
277 Match.IsVOPD3)
278 VOPDInst.addReg(RegNo: AMDGPU::VCC_LO);
279 }
280
281 if (Match.IsVOPD3) {
282 if (unsigned BitOp2 = AMDGPU::getBitOp2(Opc: Opc2))
283 VOPDInst.addImm(Val: BitOp2);
284 }
285
286 SII->fixImplicitOperands(MI&: *VOPDInst);
287 for (auto CompIdx : VOPD::COMPONENTS)
288 VOPDInst.copyImplicitOps(OtherMI: *MI[CompIdx]);
289
290 LLVM_DEBUG(dbgs() << "VOPD Fused: " << *VOPDInst << " from\tX: " << *MIX
291 << "\tY: " << *MIY << "\n");
292
293 for (auto CompIdx : VOPD::COMPONENTS)
294 MI[CompIdx]->eraseFromParent();
295
296 ++NumVOPDCreated;
297 return true;
298 }
299
300 bool run(MachineFunction &MF) {
301 ST = &MF.getSubtarget<GCNSubtarget>();
302 if (!AMDGPU::hasVOPD(STI: *ST) || !ST->isWave32())
303 return false;
304 LLVM_DEBUG(dbgs() << "CreateVOPD Pass:\n");
305
306 const SIInstrInfo *SII = ST->getInstrInfo();
307 bool Changed = false;
308
309 for (MachineBasicBlock &MBB : MF) {
310 SmallVector<VOPDCandidate, 8> Candidates;
311 auto MII = MBB.begin(), E = MBB.end();
312 while (MII != E) {
313 MachineInstr *FirstMI = &*MII;
314 MII = next_nodbg(It: MII, End: MBB.end());
315 if (MII == MBB.end())
316 break;
317 if (FirstMI->isDebugInstr())
318 continue;
319 MachineInstr *SecondMI = &*MII;
320
321 if (std::optional<VOPDMatchInfo> Match =
322 tryMatchVOPDPair(TII: *SII, FirstMI&: *FirstMI, SecondMI&: *SecondMI))
323 Candidates.push_back(Elt: {.Match: std::move(*Match), .MaterializationReg: Register()});
324 }
325
326 assignMaterializationRegisters(MBB, Candidates);
327 SmallVector<VOPDCandidate *, 8> Selected = selectCandidates(Candidates);
328 for (VOPDCandidate *Candidate : Selected) {
329 materializeLiteral(TII: *SII, Candidate&: *Candidate);
330 Changed |= doReplace(SII, Match&: Candidate->Match);
331 }
332 }
333
334 return Changed;
335 }
336};
337
338class GCNCreateVOPDLegacy : public MachineFunctionPass {
339public:
340 static char ID;
341 GCNCreateVOPDLegacy() : MachineFunctionPass(ID) {}
342
343 StringRef getPassName() const override {
344 return "GCN Create VOPD Instructions";
345 }
346
347protected:
348 void getAnalysisUsage(AnalysisUsage &AU) const override {
349 AU.setPreservesCFG();
350 MachineFunctionPass::getAnalysisUsage(AU);
351 }
352
353 bool runOnMachineFunction(MachineFunction &MF) override {
354 if (skipFunction(F: MF.getFunction()))
355 return false;
356
357 return GCNCreateVOPD().run(MF);
358 }
359};
360
361} // namespace
362
363PreservedAnalyses
364llvm::GCNCreateVOPDPass::run(MachineFunction &MF,
365 MachineFunctionAnalysisManager &AM) {
366 if (!GCNCreateVOPD().run(MF))
367 return PreservedAnalyses::all();
368 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
369}
370
371char GCNCreateVOPDLegacy::ID = 0;
372
373char &llvm::GCNCreateVOPDID = GCNCreateVOPDLegacy::ID;
374
375INITIALIZE_PASS(GCNCreateVOPDLegacy, DEBUG_TYPE, "GCN Create VOPD Instructions",
376 false, false)
377