1//===-- SIOptimizeExecMaskingPreRA.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/// This pass performs exec mask handling peephole optimizations which needs
11/// to be done before register allocation to reduce register pressure.
12///
13//===----------------------------------------------------------------------===//
14
15#include "SIOptimizeExecMaskingPreRA.h"
16#include "AMDGPU.h"
17#include "AMDGPULaneMaskUtils.h"
18#include "GCNSubtarget.h"
19#include "llvm/CodeGen/LiveIntervals.h"
20#include "llvm/CodeGen/MachineFunctionPass.h"
21#include "llvm/InitializePasses.h"
22
23using namespace llvm;
24
25#define DEBUG_TYPE "si-optimize-exec-masking-pre-ra"
26
27namespace {
28
29class SIOptimizeExecMaskingPreRA {
30private:
31 const GCNSubtarget &ST;
32 const SIRegisterInfo *TRI;
33 const SIInstrInfo *TII;
34 MachineRegisterInfo *MRI;
35 LiveIntervals *LIS;
36 const AMDGPU::LaneMaskConstants &LMC;
37
38 MCRegister CondReg;
39 MCRegister ExecReg;
40
41 bool optimizeVcndVcmpPair(MachineBasicBlock &MBB);
42 bool optimizeElseBranch(MachineBasicBlock &MBB);
43
44public:
45 SIOptimizeExecMaskingPreRA(MachineFunction &MF, LiveIntervals *LIS)
46 : ST(MF.getSubtarget<GCNSubtarget>()), TRI(ST.getRegisterInfo()),
47 TII(ST.getInstrInfo()), MRI(&MF.getRegInfo()), LIS(LIS),
48 LMC(AMDGPU::LaneMaskConstants::get(ST)) {}
49 bool run(MachineFunction &MF);
50};
51
52class SIOptimizeExecMaskingPreRALegacy : public MachineFunctionPass {
53public:
54 static char ID;
55
56 SIOptimizeExecMaskingPreRALegacy() : MachineFunctionPass(ID) {}
57
58 bool runOnMachineFunction(MachineFunction &MF) override;
59
60 StringRef getPassName() const override {
61 return "SI optimize exec mask operations pre-RA";
62 }
63
64 void getAnalysisUsage(AnalysisUsage &AU) const override {
65 AU.addRequired<LiveIntervalsWrapperPass>();
66 AU.setPreservesAll();
67 MachineFunctionPass::getAnalysisUsage(AU);
68 }
69};
70
71} // End anonymous namespace.
72
73INITIALIZE_PASS_BEGIN(SIOptimizeExecMaskingPreRALegacy, DEBUG_TYPE,
74 "SI optimize exec mask operations pre-RA", false, false)
75INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
76INITIALIZE_PASS_END(SIOptimizeExecMaskingPreRALegacy, DEBUG_TYPE,
77 "SI optimize exec mask operations pre-RA", false, false)
78
79char SIOptimizeExecMaskingPreRALegacy::ID = 0;
80
81char &llvm::SIOptimizeExecMaskingPreRAID = SIOptimizeExecMaskingPreRALegacy::ID;
82
83// See if there is a def between \p AndIdx and \p SelIdx that needs to live
84// beyond \p AndIdx.
85static bool isDefBetween(const LiveRange &LR, SlotIndex AndIdx,
86 SlotIndex SelIdx) {
87 LiveQueryResult AndLRQ = LR.Query(Idx: AndIdx);
88 return (!AndLRQ.isKill() && AndLRQ.valueIn() != LR.Query(Idx: SelIdx).valueOut());
89}
90
91// FIXME: Why do we bother trying to handle physical registers here?
92static bool isDefBetween(const SIRegisterInfo &TRI,
93 LiveIntervals *LIS, Register Reg,
94 const MachineInstr &Sel, const MachineInstr &And) {
95 SlotIndex AndIdx = LIS->getInstructionIndex(Instr: And).getRegSlot();
96 SlotIndex SelIdx = LIS->getInstructionIndex(Instr: Sel).getRegSlot();
97
98 if (Reg.isVirtual())
99 return isDefBetween(LR: LIS->getInterval(Reg), AndIdx, SelIdx);
100
101 for (MCRegUnit Unit : TRI.regunits(Reg: Reg.asMCReg())) {
102 if (isDefBetween(LR: LIS->getRegUnit(Unit), AndIdx, SelIdx))
103 return true;
104 }
105
106 return false;
107}
108
109// Optimize sequence
110// %sel = V_CNDMASK_B32_e64 0, 1, %cc
111// %cmp = V_CMP_NE_U32 1, %sel
112// $vcc = S_AND_B64 $exec, %cmp
113// S_CBRANCH_VCC[N]Z
114// =>
115// $vcc = S_ANDN2_B64 $exec, %cc
116// S_CBRANCH_VCC[N]Z
117//
118// It is the negation pattern inserted by DAGCombiner::visitBRCOND() in the
119// rebuildSetCC(). We start with S_CBRANCH to avoid exhaustive search, but
120// only 3 first instructions are really needed. S_AND_B64 with exec is a
121// required part of the pattern since V_CNDMASK_B32 writes zeroes for inactive
122// lanes.
123//
124// Returns true on success.
125bool SIOptimizeExecMaskingPreRA::optimizeVcndVcmpPair(MachineBasicBlock &MBB) {
126 auto I = llvm::find_if(Range: MBB.terminators(), P: [](const MachineInstr &MI) {
127 unsigned Opc = MI.getOpcode();
128 return Opc == AMDGPU::S_CBRANCH_VCCZ ||
129 Opc == AMDGPU::S_CBRANCH_VCCNZ; });
130 if (I == MBB.terminators().end())
131 return false;
132
133 auto *And =
134 TRI->findReachingDef(Reg: CondReg, SubReg: AMDGPU::NoSubRegister, Use&: *I, MRI&: *MRI, LIS);
135 if (!And || And->getOpcode() != LMC.AndOpc || !And->getOperand(i: 1).isReg() ||
136 !And->getOperand(i: 2).isReg())
137 return false;
138
139 MachineOperand *AndCC = &And->getOperand(i: 1);
140 Register CmpReg = AndCC->getReg();
141 unsigned CmpSubReg = AndCC->getSubReg();
142 if (CmpReg == Register(ExecReg)) {
143 AndCC = &And->getOperand(i: 2);
144 CmpReg = AndCC->getReg();
145 CmpSubReg = AndCC->getSubReg();
146 } else if (And->getOperand(i: 2).getReg() != Register(ExecReg)) {
147 return false;
148 }
149
150 auto *Cmp = TRI->findReachingDef(Reg: CmpReg, SubReg: CmpSubReg, Use&: *And, MRI&: *MRI, LIS);
151 if (!Cmp || !(Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e32 ||
152 Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e64) ||
153 Cmp->getParent() != And->getParent())
154 return false;
155
156 MachineOperand *Op1 = TII->getNamedOperand(MI&: *Cmp, OperandName: AMDGPU::OpName::src0);
157 MachineOperand *Op2 = TII->getNamedOperand(MI&: *Cmp, OperandName: AMDGPU::OpName::src1);
158 if (Op1->isImm() && Op2->isReg())
159 std::swap(a&: Op1, b&: Op2);
160 if (!Op1->isReg() || !Op2->isImm() || Op2->getImm() != 1)
161 return false;
162
163 Register SelReg = Op1->getReg();
164 if (SelReg.isPhysical())
165 return false;
166
167 auto *Sel = TRI->findReachingDef(Reg: SelReg, SubReg: Op1->getSubReg(), Use&: *Cmp, MRI&: *MRI, LIS);
168 if (!Sel || Sel->getOpcode() != AMDGPU::V_CNDMASK_B32_e64)
169 return false;
170
171 if (TII->hasModifiersSet(MI: *Sel, OpName: AMDGPU::OpName::src0_modifiers) ||
172 TII->hasModifiersSet(MI: *Sel, OpName: AMDGPU::OpName::src1_modifiers))
173 return false;
174
175 Op1 = TII->getNamedOperand(MI&: *Sel, OperandName: AMDGPU::OpName::src0);
176 Op2 = TII->getNamedOperand(MI&: *Sel, OperandName: AMDGPU::OpName::src1);
177 MachineOperand *CC = TII->getNamedOperand(MI&: *Sel, OperandName: AMDGPU::OpName::src2);
178 if (!Op1->isImm() || !Op2->isImm() || !CC->isReg() ||
179 Op1->getImm() != 0 || Op2->getImm() != 1)
180 return false;
181
182 Register CCReg = CC->getReg();
183
184 // If there was a def between the select and the and, we would need to move it
185 // to fold this.
186 if (isDefBetween(TRI: *TRI, LIS, Reg: CCReg, Sel: *Sel, And: *And))
187 return false;
188
189 // Cannot safely mirror live intervals with PHI nodes, so check for these
190 // before optimization.
191 SlotIndex SelIdx = LIS->getInstructionIndex(Instr: *Sel);
192 LiveInterval *SelLI = &LIS->getInterval(Reg: SelReg);
193 if (llvm::any_of(Range: SelLI->vnis(),
194 P: [](const VNInfo *VNI) {
195 return VNI->isPHIDef();
196 }))
197 return false;
198
199 // TODO: Guard against implicit def operands?
200 LLVM_DEBUG(dbgs() << "Folding sequence:\n\t" << *Sel << '\t' << *Cmp << '\t'
201 << *And);
202
203 MachineInstr *Andn2 =
204 BuildMI(BB&: MBB, I&: *And, MIMD: And->getDebugLoc(), MCID: TII->get(Opcode: LMC.AndN2Opc),
205 DestReg: And->getOperand(i: 0).getReg())
206 .addReg(RegNo: ExecReg)
207 .addReg(RegNo: CCReg, Flags: getUndefRegState(B: CC->isUndef()), SubReg: CC->getSubReg());
208 MachineOperand &AndSCC = And->getOperand(i: 3);
209 assert(AndSCC.getReg() == AMDGPU::SCC);
210 MachineOperand &Andn2SCC = Andn2->getOperand(i: 3);
211 assert(Andn2SCC.getReg() == AMDGPU::SCC);
212 Andn2SCC.setIsDead(AndSCC.isDead());
213
214 SlotIndex AndIdx = LIS->ReplaceMachineInstrInMaps(MI&: *And, NewMI&: *Andn2);
215 And->eraseFromParent();
216
217 LLVM_DEBUG(dbgs() << "=>\n\t" << *Andn2 << '\n');
218
219 // Update live intervals for CCReg before potentially removing CmpReg/SelReg,
220 // and their associated liveness information.
221 SlotIndex CmpIdx = LIS->getInstructionIndex(Instr: *Cmp);
222 if (CCReg.isVirtual()) {
223 LiveInterval &CCLI = LIS->getInterval(Reg: CCReg);
224 auto CCQ = CCLI.Query(Idx: SelIdx.getRegSlot());
225 if (CCQ.valueIn()) {
226 LIS->removeInterval(Reg: CCReg);
227 LIS->createAndComputeVirtRegInterval(Reg: CCReg);
228 }
229 } else
230 LIS->removeAllRegUnitsForPhysReg(Reg: CCReg);
231
232 // Try to remove compare. Cmp value should not used in between of cmp
233 // and s_and_b64 if VCC or just unused if any other register.
234 LiveInterval *CmpLI = CmpReg.isVirtual() ? &LIS->getInterval(Reg: CmpReg) : nullptr;
235 if ((CmpLI && CmpLI->Query(Idx: AndIdx.getRegSlot()).isKill()) ||
236 (CmpReg == Register(CondReg) &&
237 std::none_of(first: std::next(x: Cmp->getIterator()), last: Andn2->getIterator(),
238 pred: [&](const MachineInstr &MI) {
239 return MI.readsRegister(Reg: CondReg, TRI);
240 }))) {
241 LLVM_DEBUG(dbgs() << "Erasing: " << *Cmp << '\n');
242 if (CmpLI)
243 LIS->removeVRegDefAt(LI&: *CmpLI, Pos: CmpIdx.getRegSlot());
244 LIS->RemoveMachineInstrFromMaps(MI&: *Cmp);
245 Cmp->eraseFromParent();
246
247 // Try to remove v_cndmask_b32.
248 // Kill status must be checked before shrinking the live range.
249 bool IsKill = SelLI->Query(Idx: CmpIdx.getRegSlot()).isKill();
250 LIS->shrinkToUses(li: SelLI);
251 bool IsDead = SelLI->Query(Idx: SelIdx.getRegSlot()).isDeadDef();
252 if (MRI->use_nodbg_empty(RegNo: SelReg) && (IsKill || IsDead)) {
253 LLVM_DEBUG(dbgs() << "Erasing: " << *Sel << '\n');
254
255 LIS->removeVRegDefAt(LI&: *SelLI, Pos: SelIdx.getRegSlot());
256 LIS->RemoveMachineInstrFromMaps(MI&: *Sel);
257 bool ShrinkSel = Sel->getOperand(i: 0).readsReg();
258 Sel->eraseFromParent();
259 if (ShrinkSel) {
260 // The result of the V_CNDMASK was a subreg def which counted as a read
261 // from the other parts of the reg. Shrink their live ranges.
262 LIS->shrinkToUses(li: SelLI);
263 }
264 }
265 }
266
267 return true;
268}
269
270// Optimize sequence
271// %dst = S_OR_SAVEEXEC %src
272// ... instructions not modifying exec ...
273// %tmp = S_AND $exec, %dst
274// $exec = S_XOR_term $exec, %tmp
275// =>
276// %dst = S_OR_SAVEEXEC %src
277// ... instructions not modifying exec ...
278// $exec = S_XOR_term $exec, %dst
279//
280// Clean up potentially unnecessary code added for safety during
281// control flow lowering.
282//
283// Return whether any changes were made to MBB.
284bool SIOptimizeExecMaskingPreRA::optimizeElseBranch(MachineBasicBlock &MBB) {
285 if (MBB.empty())
286 return false;
287
288 // Check this is an else block.
289 auto First = MBB.begin();
290 MachineInstr &SaveExecMI = *First;
291 if (SaveExecMI.getOpcode() != LMC.OrSaveExecOpc)
292 return false;
293
294 auto I = llvm::find_if(Range: MBB.terminators(), P: [this](const MachineInstr &MI) {
295 return MI.getOpcode() == LMC.XorTermOpc;
296 });
297 if (I == MBB.terminators().end())
298 return false;
299
300 MachineInstr &XorTermMI = *I;
301 if (XorTermMI.getOperand(i: 1).getReg() != Register(ExecReg))
302 return false;
303
304 Register SavedExecReg = SaveExecMI.getOperand(i: 0).getReg();
305 Register DstReg = XorTermMI.getOperand(i: 2).getReg();
306
307 // Find potentially unnecessary S_AND
308 MachineInstr *AndExecMI = nullptr;
309 I--;
310 while (I != First && !AndExecMI) {
311 if (I->getOpcode() == LMC.AndOpc && I->getOperand(i: 0).getReg() == DstReg &&
312 I->getOperand(i: 1).getReg() == Register(ExecReg))
313 AndExecMI = &*I;
314 I--;
315 }
316 if (!AndExecMI)
317 return false;
318
319 // Check for exec modifying instructions.
320 // Note: exec defs do not create live ranges beyond the
321 // instruction so isDefBetween cannot be used.
322 // Instead just check that the def segments are adjacent.
323 SlotIndex StartIdx = LIS->getInstructionIndex(Instr: SaveExecMI);
324 SlotIndex EndIdx = LIS->getInstructionIndex(Instr: *AndExecMI);
325 for (MCRegUnit Unit : TRI->regunits(Reg: ExecReg)) {
326 LiveRange &RegUnit = LIS->getRegUnit(Unit);
327 if (RegUnit.find(Pos: StartIdx) != std::prev(x: RegUnit.find(Pos: EndIdx)))
328 return false;
329 }
330
331 // Remove unnecessary S_AND
332 LIS->removeInterval(Reg: SavedExecReg);
333 LIS->removeInterval(Reg: DstReg);
334
335 SaveExecMI.getOperand(i: 0).setReg(DstReg);
336
337 LIS->RemoveMachineInstrFromMaps(MI&: *AndExecMI);
338 AndExecMI->eraseFromParent();
339
340 LIS->createAndComputeVirtRegInterval(Reg: DstReg);
341
342 return true;
343}
344
345PreservedAnalyses
346SIOptimizeExecMaskingPreRAPass::run(MachineFunction &MF,
347 MachineFunctionAnalysisManager &MFAM) {
348 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
349 SIOptimizeExecMaskingPreRA(MF, &LIS).run(MF);
350 return PreservedAnalyses::all();
351}
352
353bool SIOptimizeExecMaskingPreRALegacy::runOnMachineFunction(
354 MachineFunction &MF) {
355 if (skipFunction(F: MF.getFunction()))
356 return false;
357
358 auto *LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
359 return SIOptimizeExecMaskingPreRA(MF, LIS).run(MF);
360}
361
362bool SIOptimizeExecMaskingPreRA::run(MachineFunction &MF) {
363 CondReg = MCRegister::from(Val: LMC.VccReg);
364 ExecReg = MCRegister::from(Val: LMC.ExecReg);
365
366 DenseSet<Register> RecalcRegs({AMDGPU::EXEC_LO, AMDGPU::EXEC_HI});
367 bool Changed = false;
368
369 for (MachineBasicBlock &MBB : MF) {
370
371 if (optimizeElseBranch(MBB)) {
372 RecalcRegs.insert(V: AMDGPU::SCC);
373 Changed = true;
374 }
375
376 if (optimizeVcndVcmpPair(MBB)) {
377 RecalcRegs.insert(V: AMDGPU::VCC_LO);
378 RecalcRegs.insert(V: AMDGPU::VCC_HI);
379 RecalcRegs.insert(V: AMDGPU::SCC);
380 Changed = true;
381 }
382
383 // Try to remove unneeded instructions before s_endpgm.
384 if (MBB.succ_empty()) {
385 if (MBB.empty())
386 continue;
387
388 // Skip this if the endpgm has any implicit uses, otherwise we would need
389 // to be careful to update / remove them.
390 // S_ENDPGM always has a single imm operand that is not used other than to
391 // end up in the encoding
392 MachineInstr &Term = MBB.back();
393 if (Term.getOpcode() != AMDGPU::S_ENDPGM || Term.getNumOperands() != 1)
394 continue;
395
396 SmallVector<MachineBasicBlock*, 4> Blocks({&MBB});
397
398 while (!Blocks.empty()) {
399 auto *CurBB = Blocks.pop_back_val();
400 auto I = CurBB->rbegin(), E = CurBB->rend();
401 if (I != E) {
402 if (I->isUnconditionalBranch() || I->getOpcode() == AMDGPU::S_ENDPGM)
403 ++I;
404 else if (I->isBranch())
405 continue;
406 }
407
408 while (I != E) {
409 if (I->isDebugInstr()) {
410 I = std::next(x: I);
411 continue;
412 }
413
414 if (I->mayStore() || I->isBarrier() || I->isCall() ||
415 I->hasUnmodeledSideEffects() || I->hasOrderedMemoryRef())
416 break;
417
418 LLVM_DEBUG(dbgs()
419 << "Removing no effect instruction: " << *I << '\n');
420
421 for (auto &Op : I->operands()) {
422 if (Op.isReg())
423 RecalcRegs.insert(V: Op.getReg());
424 }
425
426 auto Next = std::next(x: I);
427 LIS->RemoveMachineInstrFromMaps(MI&: *I);
428 I->eraseFromParent();
429 I = Next;
430
431 Changed = true;
432 }
433
434 if (I != E)
435 continue;
436
437 // Try to ascend predecessors.
438 for (auto *Pred : CurBB->predecessors()) {
439 if (Pred->succ_size() == 1)
440 Blocks.push_back(Elt: Pred);
441 }
442 }
443 continue;
444 }
445
446 // If the only user of a logical operation is move to exec, fold it now
447 // to prevent forming of saveexec. I.e.:
448 //
449 // %0:sreg_64 = COPY $exec
450 // %1:sreg_64 = S_AND_B64 %0:sreg_64, %2:sreg_64
451 // =>
452 // %1 = S_AND_B64 $exec, %2:sreg_64
453 unsigned ScanThreshold = 10;
454 for (auto I = MBB.rbegin(), E = MBB.rend(); I != E
455 && ScanThreshold--; ++I) {
456 // Continue scanning if this is not a full exec copy
457 if (!(I->isFullCopy() && I->getOperand(i: 1).getReg() == Register(ExecReg)))
458 continue;
459
460 Register SavedExec = I->getOperand(i: 0).getReg();
461 if (SavedExec.isVirtual() && MRI->hasOneNonDBGUse(RegNo: SavedExec)) {
462 MachineInstr *SingleExecUser = &*MRI->use_instr_nodbg_begin(RegNo: SavedExec);
463 int Idx = SingleExecUser->findRegisterUseOperandIdx(Reg: SavedExec,
464 /*TRI=*/nullptr);
465 assert(Idx != -1);
466 if (SingleExecUser->getParent() == I->getParent() &&
467 !SingleExecUser->getOperand(i: Idx).isImplicit() &&
468 static_cast<unsigned>(Idx) <
469 SingleExecUser->getDesc().getNumOperands() &&
470 TII->isOperandLegal(MI: *SingleExecUser, OpIdx: Idx, MO: &I->getOperand(i: 1))) {
471 LLVM_DEBUG(dbgs() << "Redundant EXEC COPY: " << *I << '\n');
472 LIS->RemoveMachineInstrFromMaps(MI&: *I);
473 I->eraseFromParent();
474 MRI->replaceRegWith(FromReg: SavedExec, ToReg: ExecReg);
475 LIS->removeInterval(Reg: SavedExec);
476 Changed = true;
477 }
478 }
479 break;
480 }
481 }
482
483 if (Changed) {
484 for (auto Reg : RecalcRegs) {
485 if (Reg.isVirtual()) {
486 LIS->removeInterval(Reg);
487 if (!MRI->reg_empty(RegNo: Reg))
488 LIS->createAndComputeVirtRegInterval(Reg);
489 } else {
490 LIS->removeAllRegUnitsForPhysReg(Reg);
491 }
492 }
493 }
494
495 return Changed;
496}
497