1//===-- AMDGPUGlobalISelDivergenceLowering.cpp ----------------------------===//
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/// GlobalISel pass that selects divergent i1 phis as lane mask phis.
11/// Lane mask merging uses same algorithm as SDAG in SILowerI1Copies.
12/// Handles all cases of temporal divergence.
13/// For divergent non-phi i1 and uniform i1 uses outside of the cycle this pass
14/// currently depends on LCSSA to insert phis with one incoming.
15//
16//===----------------------------------------------------------------------===//
17
18#include "AMDGPU.h"
19#include "AMDGPUGlobalISelUtils.h"
20#include "SILowerI1Copies.h"
21#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
22#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
23#include "llvm/CodeGen/MachineFunctionPass.h"
24#include "llvm/CodeGen/MachinePassManager.h"
25#include "llvm/CodeGen/MachineUniformityAnalysis.h"
26#include "llvm/InitializePasses.h"
27
28#define DEBUG_TYPE "amdgpu-global-isel-divergence-lowering"
29
30using namespace llvm;
31
32namespace {
33
34class AMDGPUGlobalISelDivergenceLoweringLegacy : public MachineFunctionPass {
35public:
36 static char ID;
37
38public:
39 AMDGPUGlobalISelDivergenceLoweringLegacy() : MachineFunctionPass(ID) {}
40
41 bool runOnMachineFunction(MachineFunction &MF) override;
42
43 StringRef getPassName() const override {
44 return "AMDGPU GlobalISel divergence lowering";
45 }
46
47 void getAnalysisUsage(AnalysisUsage &AU) const override {
48 AU.setPreservesCFG();
49 AU.addRequired<MachineDominatorTreeWrapperPass>();
50 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
51 AU.addRequired<MachineUniformityAnalysisPass>();
52 MachineFunctionPass::getAnalysisUsage(AU);
53 }
54};
55
56class DivergenceLoweringHelper : public AMDGPU::PhiLoweringHelper {
57public:
58 DivergenceLoweringHelper(MachineFunction &MF, MachineDominatorTree &DT,
59 MachinePostDominatorTree &PDT,
60 MachineUniformityInfo *MUI);
61
62private:
63 MachineUniformityInfo *MUI = nullptr;
64 MachineIRBuilder B;
65 Register buildRegCopyToLaneMask(Register Reg);
66
67public:
68 void markAsLaneMask(Register DstReg) const override;
69 void getCandidatesForLowering(
70 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const override;
71 void collectIncomingValuesFromPhi(
72 const MachineInstr *MI,
73 SmallVectorImpl<AMDGPU::Incoming> &Incomings) const override;
74 void replaceDstReg(Register NewReg, Register OldReg,
75 MachineBasicBlock *MBB) override;
76 void buildMergeLaneMasks(MachineBasicBlock &MBB,
77 MachineBasicBlock::iterator I, const DebugLoc &DL,
78 Register DstReg, Register PrevReg,
79 Register CurReg) override;
80 void constrainAsLaneMask(AMDGPU::Incoming &In) override;
81
82 bool lowerTemporalDivergence();
83 bool lowerTemporalDivergenceI1();
84};
85
86DivergenceLoweringHelper::DivergenceLoweringHelper(
87 MachineFunction &MF, MachineDominatorTree &DT,
88 MachinePostDominatorTree &PDT, MachineUniformityInfo *MUI)
89 : PhiLoweringHelper(MF, DT, PDT), MUI(MUI), B(MF) {}
90
91// _(s1) -> SReg_32/64(s1)
92void DivergenceLoweringHelper::markAsLaneMask(Register DstReg) const {
93 assert(MRI->getType(DstReg) == LLT::scalar(1));
94
95 if (MRI->getRegClassOrNull(Reg: DstReg)) {
96 if (MRI->constrainRegClass(Reg: DstReg, RC: ST->getBoolRC()))
97 return;
98 llvm_unreachable("Failed to constrain register class");
99 }
100
101 MRI->setRegClass(Reg: DstReg, RC: ST->getBoolRC());
102}
103
104void DivergenceLoweringHelper::getCandidatesForLowering(
105 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const {
106 LLT S1 = LLT::scalar(SizeInBits: 1);
107
108 // Add divergent i1 G_PHIs to the list. Only consider G_PHI instructions,
109 // not PHI instructions that may have been created by earlier lowering stages
110 // (e.g., lowerTemporalDivergenceI1).
111 for (MachineBasicBlock &MBB : MF) {
112 for (MachineInstr &MI : MBB.phis()) {
113 if (MI.getOpcode() != TargetOpcode::G_PHI)
114 continue;
115 Register Dst = MI.getOperand(i: 0).getReg();
116 if (MRI->getType(Reg: Dst) == S1 && MUI->isDivergentAtDef(V: Dst))
117 Vreg1Phis.push_back(Elt: &MI);
118 }
119 }
120}
121
122void DivergenceLoweringHelper::collectIncomingValuesFromPhi(
123 const MachineInstr *MI,
124 SmallVectorImpl<AMDGPU::Incoming> &Incomings) const {
125 for (unsigned i = 1; i < MI->getNumOperands(); i += 2) {
126 Incomings.emplace_back(Args: MI->getOperand(i).getReg(),
127 Args: MI->getOperand(i: i + 1).getMBB(), Args: Register());
128 }
129}
130
131void DivergenceLoweringHelper::replaceDstReg(Register NewReg, Register OldReg,
132 MachineBasicBlock *MBB) {
133 BuildMI(BB&: *MBB, I: MBB->getFirstNonPHI(), MIMD: {}, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: OldReg)
134 .addReg(RegNo: NewReg);
135}
136
137// Copy Reg to new lane mask register, insert a copy after instruction that
138// defines Reg while skipping phis if needed.
139Register DivergenceLoweringHelper::buildRegCopyToLaneMask(Register Reg) {
140 Register LaneMask = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
141 MachineInstr *Instr = MRI->getVRegDef(Reg);
142 MachineBasicBlock *MBB = Instr->getParent();
143 B.setInsertPt(MBB&: *MBB, II: MBB->SkipPHIsAndLabels(I: std::next(x: Instr->getIterator())));
144 B.buildCopy(Res: LaneMask, Op: Reg);
145 return LaneMask;
146}
147
148// bb.previous
149// %PrevReg = ...
150//
151// bb.current
152// %CurReg = ...
153//
154// %DstReg - not defined
155//
156// -> (wave32 example, new registers have sreg_32 reg class and S1 LLT)
157//
158// bb.previous
159// %PrevReg = ...
160// %PrevRegCopy:sreg_32(s1) = COPY %PrevReg
161//
162// bb.current
163// %CurReg = ...
164// %CurRegCopy:sreg_32(s1) = COPY %CurReg
165// ...
166// %PrevMaskedReg:sreg_32(s1) = ANDN2 %PrevRegCopy, ExecReg - active lanes 0
167// %CurMaskedReg:sreg_32(s1) = AND %ExecReg, CurRegCopy - inactive lanes to 0
168// %DstReg:sreg_32(s1) = OR %PrevMaskedReg, CurMaskedReg
169//
170// DstReg = for active lanes rewrite bit in PrevReg with bit from CurReg
171void DivergenceLoweringHelper::buildMergeLaneMasks(
172 MachineBasicBlock &MBB, MachineBasicBlock::iterator I, const DebugLoc &DL,
173 Register DstReg, Register PrevReg, Register CurReg) {
174 // DstReg = (PrevReg & !EXEC) | (CurReg & EXEC)
175 // TODO: check if inputs are constants or results of a compare.
176
177 Register PrevRegCopy = buildRegCopyToLaneMask(Reg: PrevReg);
178 Register CurRegCopy = buildRegCopyToLaneMask(Reg: CurReg);
179 Register PrevMaskedReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
180 Register CurMaskedReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
181
182 B.setInsertPt(MBB, II: I);
183 B.buildInstr(Opc: LMC->AndN2Opc, DstOps: {PrevMaskedReg}, SrcOps: {PrevRegCopy, LMC->ExecReg})
184 .setOperandDead(3);
185 B.buildInstr(Opc: LMC->AndOpc, DstOps: {CurMaskedReg}, SrcOps: {LMC->ExecReg, CurRegCopy})
186 .setOperandDead(3);
187 B.buildInstr(Opc: LMC->OrOpc, DstOps: {DstReg}, SrcOps: {PrevMaskedReg, CurMaskedReg})
188 .setOperandDead(3);
189}
190
191// GlobalISel has to constrain S1 incoming taken as-is with lane mask register
192// class. Insert a copy of Incoming.Reg to new lane mask inside Incoming.Block,
193// Incoming.Reg becomes that new lane mask.
194void DivergenceLoweringHelper::constrainAsLaneMask(AMDGPU::Incoming &In) {
195 B.setInsertPt(MBB&: *In.Block, II: In.Block->getFirstTerminator());
196
197 auto Copy = B.buildCopy(Res: LLT::scalar(SizeInBits: 1), Op: In.Reg);
198 MRI->setRegClass(Reg: Copy.getReg(Idx: 0), RC: ST->getBoolRC());
199 In.Reg = Copy.getReg(Idx: 0);
200}
201
202void replaceUsesOfRegInInstWith(Register Reg, MachineInstr *Inst,
203 Register NewReg) {
204 for (MachineOperand &Op : Inst->operands()) {
205 if (Op.isReg() && Op.getReg() == Reg)
206 Op.setReg(NewReg);
207 }
208}
209
210bool DivergenceLoweringHelper::lowerTemporalDivergence() {
211 AMDGPU::IntrinsicLaneMaskAnalyzer ILMA(MF);
212 DenseMap<Register, Register> TDCache;
213
214 for (auto [Reg, UseInst, _] : MUI->getTemporalDivergenceList()) {
215 if (MRI->getType(Reg) == LLT::scalar(SizeInBits: 1) || MUI->isDivergentAtDef(V: Reg) ||
216 ILMA.isS32S64LaneMask(Reg))
217 continue;
218
219 Register CachedTDCopy = TDCache.lookup(Val: Reg);
220 if (CachedTDCopy) {
221 replaceUsesOfRegInInstWith(Reg, Inst: UseInst, NewReg: CachedTDCopy);
222 continue;
223 }
224
225 MachineInstr *Inst = MRI->getVRegDef(Reg);
226 MachineBasicBlock *MBB = Inst->getParent();
227 B.setInsertPt(MBB&: *MBB, II: MBB->SkipPHIsAndLabels(I: std::next(x: Inst->getIterator())));
228
229 Register VgprReg = MRI->createGenericVirtualRegister(Ty: MRI->getType(Reg));
230 B.buildInstr(Opc: AMDGPU::COPY, DstOps: {VgprReg}, SrcOps: {Reg})
231 .addUse(RegNo: LMC->ExecReg, Flags: RegState::Implicit);
232
233 replaceUsesOfRegInInstWith(Reg, Inst: UseInst, NewReg: VgprReg);
234 TDCache[Reg] = VgprReg;
235 }
236 return false;
237}
238
239bool DivergenceLoweringHelper::lowerTemporalDivergenceI1() {
240 MachineRegisterInfo::VRegAttrs BoolS1 = {.RCOrRB: ST->getBoolRC(), .Ty: LLT::scalar(SizeInBits: 1)};
241 initializeLaneMaskRegisterAttributes(Attrs: BoolS1);
242 MachineSSAUpdater SSAUpdater(MF);
243
244 const auto &CInfo = MUI->getCycleInfo();
245
246 // In case of use outside muliple nested cycles or muliple uses we only need
247 // to merge lane mask across largest relevant cycle.
248 SmallDenseMap<Register, std::pair<CycleRef, Register>> LRCCache;
249 for (auto [Reg, UseInst, LRC] : MUI->getTemporalDivergenceList()) {
250 if (MRI->getType(Reg) != LLT::scalar(SizeInBits: 1))
251 continue;
252
253 auto [LRCCacheIter, RegNotCached] = LRCCache.try_emplace(Key: Reg);
254 auto &CycleMergedMask = LRCCacheIter->getSecond();
255 CycleRef &CachedLRC = CycleMergedMask.first;
256 if (RegNotCached || CInfo.contains(Outer: LRC, Inner: CachedLRC)) {
257 CachedLRC = LRC;
258 }
259 }
260
261 for (auto &LRCCacheEntry : LRCCache) {
262 Register Reg = LRCCacheEntry.first;
263 auto &CycleMergedMask = LRCCacheEntry.getSecond();
264 CycleRef Cycle = CycleMergedMask.first;
265
266 Register MergedMask = MRI->createVirtualRegister(RegAttr: BoolS1);
267 SSAUpdater.Initialize(V: MergedMask);
268
269 MachineBasicBlock *MBB = MRI->getDefBlock(Reg);
270 SSAUpdater.AddAvailableValue(BB: MBB, V: MergedMask);
271
272 for (auto Entry : CInfo.getEntries(C: Cycle)) {
273 for (MachineBasicBlock *Pred : Entry->predecessors()) {
274 if (!CInfo.contains(C: Cycle, Block: Pred)) {
275 B.setInsertPt(MBB&: *Pred, II: Pred->getFirstTerminator());
276 auto ImplDef = B.buildInstr(Opc: AMDGPU::IMPLICIT_DEF, DstOps: {BoolS1}, SrcOps: {});
277 SSAUpdater.AddAvailableValue(BB: Pred, V: ImplDef.getReg(Idx: 0));
278 }
279 }
280 }
281
282 buildMergeLaneMasks(MBB&: *MBB, I: MBB->getFirstTerminator(), DL: {}, DstReg: MergedMask,
283 PrevReg: SSAUpdater.GetValueInMiddleOfBlock(BB: MBB), CurReg: Reg);
284
285 CycleMergedMask.second = MergedMask;
286 }
287
288 for (auto [Reg, UseInst, Cycle] : MUI->getTemporalDivergenceList()) {
289 if (MRI->getType(Reg) != LLT::scalar(SizeInBits: 1))
290 continue;
291
292 replaceUsesOfRegInInstWith(Reg, Inst: UseInst, NewReg: LRCCache.lookup(Val: Reg).second);
293 }
294
295 return false;
296}
297
298static bool runDivergenceLowering(MachineFunction &MF, MachineDominatorTree &DT,
299 MachinePostDominatorTree &PDT,
300 MachineUniformityInfo &MUI) {
301 DivergenceLoweringHelper Helper(MF, DT, PDT, &MUI);
302
303 bool Changed = false;
304 // Temporal divergence lowering needs to inspect list of instructions used
305 // outside cycle with divergent exit provided by uniformity analysis. Uniform
306 // instructions from the list require lowering, no instruction is deleted.
307 // Thus it needs to be run before lowerPhis that deletes phis that require
308 // lowering and replaces them with new instructions.
309
310 // Non-i1 temporal divergence lowering.
311 Changed |= Helper.lowerTemporalDivergence();
312 // This covers both uniform and divergent i1s. Lane masks are in sgpr and need
313 // to be updated in each iteration.
314 Changed |= Helper.lowerTemporalDivergenceI1();
315 // Temporal divergence lowering of divergent i1 phi used outside of the cycle
316 // could also be handled by lowerPhis but we do it in lowerTempDivergenceI1
317 // since in some case lowerPhis does unnecessary lane mask merging.
318 Changed |= Helper.lowerPhis();
319 return Changed;
320}
321
322} // End anonymous namespace.
323
324INITIALIZE_PASS_BEGIN(AMDGPUGlobalISelDivergenceLoweringLegacy, DEBUG_TYPE,
325 "AMDGPU GlobalISel divergence lowering", false, false)
326INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
327INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
328INITIALIZE_PASS_DEPENDENCY(MachineUniformityAnalysisPass)
329INITIALIZE_PASS_END(AMDGPUGlobalISelDivergenceLoweringLegacy, DEBUG_TYPE,
330 "AMDGPU GlobalISel divergence lowering", false, false)
331
332char AMDGPUGlobalISelDivergenceLoweringLegacy::ID = 0;
333
334char &llvm::AMDGPUGlobalISelDivergenceLoweringLegacyID =
335 AMDGPUGlobalISelDivergenceLoweringLegacy::ID;
336
337FunctionPass *llvm::createAMDGPUGlobalISelDivergenceLoweringPass() {
338 return new AMDGPUGlobalISelDivergenceLoweringLegacy();
339}
340
341bool AMDGPUGlobalISelDivergenceLoweringLegacy::runOnMachineFunction(
342 MachineFunction &MF) {
343 MachineDominatorTree &DT =
344 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
345 MachinePostDominatorTree &PDT =
346 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
347 MachineUniformityInfo &MUI =
348 getAnalysis<MachineUniformityAnalysisPass>().getUniformityInfo();
349
350 return runDivergenceLowering(MF, DT, PDT, MUI);
351}
352
353PreservedAnalyses AMDGPUGlobalISelDivergenceLoweringPass::run(
354 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {
355 MachineDominatorTree &DT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
356 MachinePostDominatorTree &PDT =
357 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
358 MachineUniformityInfo &MUI = MFAM.getResult<MachineUniformityAnalysis>(IR&: MF);
359
360 if (!runDivergenceLowering(MF, DT, PDT, MUI))
361 return PreservedAnalyses::all();
362
363 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
364}
365