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