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