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