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 B.buildInstr(Opc: LMC->AndOpc, DstOps: {CurMaskedReg}, SrcOps: {LMC->ExecReg, CurRegCopy});
185 B.buildInstr(Opc: LMC->OrOpc, DstOps: {DstReg}, SrcOps: {PrevMaskedReg, CurMaskedReg});
186}
187
188// GlobalISel has to constrain S1 incoming taken as-is with lane mask register
189// class. Insert a copy of Incoming.Reg to new lane mask inside Incoming.Block,
190// Incoming.Reg becomes that new lane mask.
191void DivergenceLoweringHelper::constrainAsLaneMask(AMDGPU::Incoming &In) {
192 B.setInsertPt(MBB&: *In.Block, II: In.Block->getFirstTerminator());
193
194 auto Copy = B.buildCopy(Res: LLT::scalar(SizeInBits: 1), Op: In.Reg);
195 MRI->setRegClass(Reg: Copy.getReg(Idx: 0), RC: ST->getBoolRC());
196 In.Reg = Copy.getReg(Idx: 0);
197}
198
199void replaceUsesOfRegInInstWith(Register Reg, MachineInstr *Inst,
200 Register NewReg) {
201 for (MachineOperand &Op : Inst->operands()) {
202 if (Op.isReg() && Op.getReg() == Reg)
203 Op.setReg(NewReg);
204 }
205}
206
207bool DivergenceLoweringHelper::lowerTemporalDivergence() {
208 AMDGPU::IntrinsicLaneMaskAnalyzer ILMA(MF);
209 DenseMap<Register, Register> TDCache;
210
211 for (auto [Reg, UseInst, _] : MUI->getTemporalDivergenceList()) {
212 if (MRI->getType(Reg) == LLT::scalar(SizeInBits: 1) || MUI->isDivergentAtDef(V: Reg) ||
213 ILMA.isS32S64LaneMask(Reg))
214 continue;
215
216 Register CachedTDCopy = TDCache.lookup(Val: Reg);
217 if (CachedTDCopy) {
218 replaceUsesOfRegInInstWith(Reg, Inst: UseInst, NewReg: CachedTDCopy);
219 continue;
220 }
221
222 MachineInstr *Inst = MRI->getVRegDef(Reg);
223 MachineBasicBlock *MBB = Inst->getParent();
224 B.setInsertPt(MBB&: *MBB, II: MBB->SkipPHIsAndLabels(I: std::next(x: Inst->getIterator())));
225
226 Register VgprReg = MRI->createGenericVirtualRegister(Ty: MRI->getType(Reg));
227 B.buildInstr(Opc: AMDGPU::COPY, DstOps: {VgprReg}, SrcOps: {Reg})
228 .addUse(RegNo: LMC->ExecReg, Flags: RegState::Implicit);
229
230 replaceUsesOfRegInInstWith(Reg, Inst: UseInst, NewReg: VgprReg);
231 TDCache[Reg] = VgprReg;
232 }
233 return false;
234}
235
236bool DivergenceLoweringHelper::lowerTemporalDivergenceI1() {
237 MachineRegisterInfo::VRegAttrs BoolS1 = {.RCOrRB: ST->getBoolRC(), .Ty: LLT::scalar(SizeInBits: 1)};
238 initializeLaneMaskRegisterAttributes(Attrs: BoolS1);
239 MachineSSAUpdater SSAUpdater(MF);
240
241 const auto &CInfo = MUI->getCycleInfo();
242
243 // In case of use outside muliple nested cycles or muliple uses we only need
244 // to merge lane mask across largest relevant cycle.
245 SmallDenseMap<Register, std::pair<CycleRef, Register>> LRCCache;
246 for (auto [Reg, UseInst, LRC] : MUI->getTemporalDivergenceList()) {
247 if (MRI->getType(Reg) != LLT::scalar(SizeInBits: 1))
248 continue;
249
250 auto [LRCCacheIter, RegNotCached] = LRCCache.try_emplace(Key: Reg);
251 auto &CycleMergedMask = LRCCacheIter->getSecond();
252 CycleRef &CachedLRC = CycleMergedMask.first;
253 if (RegNotCached || CInfo.contains(Outer: LRC, Inner: CachedLRC)) {
254 CachedLRC = LRC;
255 }
256 }
257
258 for (auto &LRCCacheEntry : LRCCache) {
259 Register Reg = LRCCacheEntry.first;
260 auto &CycleMergedMask = LRCCacheEntry.getSecond();
261 CycleRef Cycle = CycleMergedMask.first;
262
263 Register MergedMask = MRI->createVirtualRegister(RegAttr: BoolS1);
264 SSAUpdater.Initialize(V: MergedMask);
265
266 MachineBasicBlock *MBB = MRI->getDefBlock(Reg);
267 SSAUpdater.AddAvailableValue(BB: MBB, V: MergedMask);
268
269 for (auto Entry : CInfo.getEntries(C: Cycle)) {
270 for (MachineBasicBlock *Pred : Entry->predecessors()) {
271 if (!CInfo.contains(C: Cycle, Block: Pred)) {
272 B.setInsertPt(MBB&: *Pred, II: Pred->getFirstTerminator());
273 auto ImplDef = B.buildInstr(Opc: AMDGPU::IMPLICIT_DEF, DstOps: {BoolS1}, SrcOps: {});
274 SSAUpdater.AddAvailableValue(BB: Pred, V: ImplDef.getReg(Idx: 0));
275 }
276 }
277 }
278
279 buildMergeLaneMasks(MBB&: *MBB, I: MBB->getFirstTerminator(), DL: {}, DstReg: MergedMask,
280 PrevReg: SSAUpdater.GetValueInMiddleOfBlock(BB: MBB), CurReg: Reg);
281
282 CycleMergedMask.second = MergedMask;
283 }
284
285 for (auto [Reg, UseInst, Cycle] : MUI->getTemporalDivergenceList()) {
286 if (MRI->getType(Reg) != LLT::scalar(SizeInBits: 1))
287 continue;
288
289 replaceUsesOfRegInInstWith(Reg, Inst: UseInst, NewReg: LRCCache.lookup(Val: Reg).second);
290 }
291
292 return false;
293}
294
295static bool runDivergenceLowering(MachineFunction &MF, MachineDominatorTree &DT,
296 MachinePostDominatorTree &PDT,
297 MachineUniformityInfo &MUI) {
298 DivergenceLoweringHelper Helper(MF, DT, PDT, &MUI);
299
300 bool Changed = false;
301 // Temporal divergence lowering needs to inspect list of instructions used
302 // outside cycle with divergent exit provided by uniformity analysis. Uniform
303 // instructions from the list require lowering, no instruction is deleted.
304 // Thus it needs to be run before lowerPhis that deletes phis that require
305 // lowering and replaces them with new instructions.
306
307 // Non-i1 temporal divergence lowering.
308 Changed |= Helper.lowerTemporalDivergence();
309 // This covers both uniform and divergent i1s. Lane masks are in sgpr and need
310 // to be updated in each iteration.
311 Changed |= Helper.lowerTemporalDivergenceI1();
312 // Temporal divergence lowering of divergent i1 phi used outside of the cycle
313 // could also be handled by lowerPhis but we do it in lowerTempDivergenceI1
314 // since in some case lowerPhis does unnecessary lane mask merging.
315 Changed |= Helper.lowerPhis();
316 return Changed;
317}
318
319} // End anonymous namespace.
320
321INITIALIZE_PASS_BEGIN(AMDGPUGlobalISelDivergenceLoweringLegacy, DEBUG_TYPE,
322 "AMDGPU GlobalISel divergence lowering", false, false)
323INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
324INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
325INITIALIZE_PASS_DEPENDENCY(MachineUniformityAnalysisPass)
326INITIALIZE_PASS_END(AMDGPUGlobalISelDivergenceLoweringLegacy, DEBUG_TYPE,
327 "AMDGPU GlobalISel divergence lowering", false, false)
328
329char AMDGPUGlobalISelDivergenceLoweringLegacy::ID = 0;
330
331char &llvm::AMDGPUGlobalISelDivergenceLoweringLegacyID =
332 AMDGPUGlobalISelDivergenceLoweringLegacy::ID;
333
334FunctionPass *llvm::createAMDGPUGlobalISelDivergenceLoweringPass() {
335 return new AMDGPUGlobalISelDivergenceLoweringLegacy();
336}
337
338bool AMDGPUGlobalISelDivergenceLoweringLegacy::runOnMachineFunction(
339 MachineFunction &MF) {
340 MachineDominatorTree &DT =
341 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
342 MachinePostDominatorTree &PDT =
343 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
344 MachineUniformityInfo &MUI =
345 getAnalysis<MachineUniformityAnalysisPass>().getUniformityInfo();
346
347 return runDivergenceLowering(MF, DT, PDT, MUI);
348}
349
350PreservedAnalyses AMDGPUGlobalISelDivergenceLoweringPass::run(
351 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {
352 MachineDominatorTree &DT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
353 MachinePostDominatorTree &PDT =
354 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
355 MachineUniformityInfo &MUI = MFAM.getResult<MachineUniformityAnalysis>(IR&: MF);
356
357 if (!runDivergenceLowering(MF, DT, PDT, MUI))
358 return PreservedAnalyses::all();
359
360 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
361}
362