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