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 removes redundant S_OR_B64 instructions enabling lanes in
11 /// the exec. If two SI_END_CF (lowered as S_OR_B64) come together without any
12 /// vector instructions between them we can only keep outer SI_END_CF, given
13 /// that CFG is structured and exec bits of the outer end statement are always
14 /// not less than exec bit of the inner one.
15 ///
16 /// This needs to be done before the RA to eliminate saved exec bits registers
17 /// but after register coalescer to have no vector registers copies in between
18 /// of different end cf statements.
19 ///
20 //===----------------------------------------------------------------------===//
21 
22 #include "AMDGPU.h"
23 #include "AMDGPUSubtarget.h"
24 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
25 #include "SIInstrInfo.h"
26 #include "llvm/CodeGen/LiveIntervals.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/InitializePasses.h"
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "si-optimize-exec-masking-pre-ra"
33 
34 static cl::opt<bool>
35 RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",
36     cl::init(false), cl::ReallyHidden);
37 
38 namespace {
39 
40 class SIOptimizeExecMaskingPreRA : public MachineFunctionPass {
41 private:
42   const SIRegisterInfo *TRI;
43   const SIInstrInfo *TII;
44   MachineRegisterInfo *MRI;
45 
46 public:
47   MachineBasicBlock::iterator skipIgnoreExecInsts(
48     MachineBasicBlock::iterator I, MachineBasicBlock::iterator E) const;
49 
50     MachineBasicBlock::iterator skipIgnoreExecInstsTrivialSucc(
51       MachineBasicBlock *&MBB,
52       MachineBasicBlock::iterator It) const;
53 
54 public:
55   static char ID;
56 
57   SIOptimizeExecMaskingPreRA() : MachineFunctionPass(ID) {
58     initializeSIOptimizeExecMaskingPreRAPass(*PassRegistry::getPassRegistry());
59   }
60 
61   bool runOnMachineFunction(MachineFunction &MF) override;
62 
63   StringRef getPassName() const override {
64     return "SI optimize exec mask operations pre-RA";
65   }
66 
67   void getAnalysisUsage(AnalysisUsage &AU) const override {
68     AU.addRequired<LiveIntervals>();
69     AU.setPreservesAll();
70     MachineFunctionPass::getAnalysisUsage(AU);
71   }
72 };
73 
74 } // End anonymous namespace.
75 
76 INITIALIZE_PASS_BEGIN(SIOptimizeExecMaskingPreRA, DEBUG_TYPE,
77                       "SI optimize exec mask operations pre-RA", false, false)
78 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
79 INITIALIZE_PASS_END(SIOptimizeExecMaskingPreRA, DEBUG_TYPE,
80                     "SI optimize exec mask operations pre-RA", false, false)
81 
82 char SIOptimizeExecMaskingPreRA::ID = 0;
83 
84 char &llvm::SIOptimizeExecMaskingPreRAID = SIOptimizeExecMaskingPreRA::ID;
85 
86 FunctionPass *llvm::createSIOptimizeExecMaskingPreRAPass() {
87   return new SIOptimizeExecMaskingPreRA();
88 }
89 
90 static bool isEndCF(const MachineInstr &MI, const SIRegisterInfo *TRI,
91                     const GCNSubtarget &ST) {
92   if (ST.isWave32()) {
93     return MI.getOpcode() == AMDGPU::S_OR_B32 &&
94            MI.modifiesRegister(AMDGPU::EXEC_LO, TRI);
95   }
96 
97   return MI.getOpcode() == AMDGPU::S_OR_B64 &&
98          MI.modifiesRegister(AMDGPU::EXEC, TRI);
99 }
100 
101 static bool isFullExecCopy(const MachineInstr& MI, const GCNSubtarget& ST) {
102   unsigned Exec = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
103 
104   if (MI.isCopy() && MI.getOperand(1).getReg() == Exec) {
105     assert(MI.isFullCopy());
106     return true;
107   }
108 
109   return false;
110 }
111 
112 static unsigned getOrNonExecReg(const MachineInstr &MI,
113                                 const SIInstrInfo &TII,
114                                 const GCNSubtarget& ST) {
115   unsigned Exec = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
116   auto Op = TII.getNamedOperand(MI, AMDGPU::OpName::src1);
117   if (Op->isReg() && Op->getReg() != Exec)
118      return Op->getReg();
119   Op = TII.getNamedOperand(MI, AMDGPU::OpName::src0);
120   if (Op->isReg() && Op->getReg() != Exec)
121      return Op->getReg();
122   return AMDGPU::NoRegister;
123 }
124 
125 static MachineInstr* getOrExecSource(const MachineInstr &MI,
126                                      const SIInstrInfo &TII,
127                                      const MachineRegisterInfo &MRI,
128                                      const GCNSubtarget& ST) {
129   auto SavedExec = getOrNonExecReg(MI, TII, ST);
130   if (SavedExec == AMDGPU::NoRegister)
131     return nullptr;
132   auto SaveExecInst = MRI.getUniqueVRegDef(SavedExec);
133   if (!SaveExecInst || !isFullExecCopy(*SaveExecInst, ST))
134     return nullptr;
135   return SaveExecInst;
136 }
137 
138 /// Skip over instructions that don't care about the exec mask.
139 MachineBasicBlock::iterator SIOptimizeExecMaskingPreRA::skipIgnoreExecInsts(
140   MachineBasicBlock::iterator I, MachineBasicBlock::iterator E) const {
141   for ( ; I != E; ++I) {
142     if (TII->mayReadEXEC(*MRI, *I))
143       break;
144   }
145 
146   return I;
147 }
148 
149 // Skip to the next instruction, ignoring debug instructions, and trivial block
150 // boundaries (blocks that have one (typically fallthrough) successor, and the
151 // successor has one predecessor.
152 MachineBasicBlock::iterator
153 SIOptimizeExecMaskingPreRA::skipIgnoreExecInstsTrivialSucc(
154   MachineBasicBlock *&MBB,
155   MachineBasicBlock::iterator It) const {
156 
157   do {
158     It = skipIgnoreExecInsts(It, MBB->end());
159     if (It != MBB->end() || MBB->succ_size() != 1)
160       break;
161 
162     // If there is one trivial successor, advance to the next block.
163     MachineBasicBlock *Succ = *MBB->succ_begin();
164 
165     // TODO: Is this really necessary?
166     if (!MBB->isLayoutSuccessor(Succ))
167       break;
168 
169     It = Succ->begin();
170     MBB = Succ;
171   } while (true);
172 
173   return It;
174 }
175 
176 
177 // Optimize sequence
178 //    %sel = V_CNDMASK_B32_e64 0, 1, %cc
179 //    %cmp = V_CMP_NE_U32 1, %1
180 //    $vcc = S_AND_B64 $exec, %cmp
181 //    S_CBRANCH_VCC[N]Z
182 // =>
183 //    $vcc = S_ANDN2_B64 $exec, %cc
184 //    S_CBRANCH_VCC[N]Z
185 //
186 // It is the negation pattern inserted by DAGCombiner::visitBRCOND() in the
187 // rebuildSetCC(). We start with S_CBRANCH to avoid exhaustive search, but
188 // only 3 first instructions are really needed. S_AND_B64 with exec is a
189 // required part of the pattern since V_CNDMASK_B32 writes zeroes for inactive
190 // lanes.
191 //
192 // Returns %cc register on success.
193 static unsigned optimizeVcndVcmpPair(MachineBasicBlock &MBB,
194                                      const GCNSubtarget &ST,
195                                      MachineRegisterInfo &MRI,
196                                      LiveIntervals *LIS) {
197   const SIRegisterInfo *TRI = ST.getRegisterInfo();
198   const SIInstrInfo *TII = ST.getInstrInfo();
199   bool Wave32 = ST.isWave32();
200   const unsigned AndOpc = Wave32 ? AMDGPU::S_AND_B32 : AMDGPU::S_AND_B64;
201   const unsigned Andn2Opc = Wave32 ? AMDGPU::S_ANDN2_B32 : AMDGPU::S_ANDN2_B64;
202   const unsigned CondReg = Wave32 ? AMDGPU::VCC_LO : AMDGPU::VCC;
203   const unsigned ExecReg = Wave32 ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
204 
205   auto I = llvm::find_if(MBB.terminators(), [](const MachineInstr &MI) {
206                            unsigned Opc = MI.getOpcode();
207                            return Opc == AMDGPU::S_CBRANCH_VCCZ ||
208                                   Opc == AMDGPU::S_CBRANCH_VCCNZ; });
209   if (I == MBB.terminators().end())
210     return AMDGPU::NoRegister;
211 
212   auto *And = TRI->findReachingDef(CondReg, AMDGPU::NoSubRegister,
213                                    *I, MRI, LIS);
214   if (!And || And->getOpcode() != AndOpc ||
215       !And->getOperand(1).isReg() || !And->getOperand(2).isReg())
216     return AMDGPU::NoRegister;
217 
218   MachineOperand *AndCC = &And->getOperand(1);
219   Register CmpReg = AndCC->getReg();
220   unsigned CmpSubReg = AndCC->getSubReg();
221   if (CmpReg == ExecReg) {
222     AndCC = &And->getOperand(2);
223     CmpReg = AndCC->getReg();
224     CmpSubReg = AndCC->getSubReg();
225   } else if (And->getOperand(2).getReg() != ExecReg) {
226     return AMDGPU::NoRegister;
227   }
228 
229   auto *Cmp = TRI->findReachingDef(CmpReg, CmpSubReg, *And, MRI, LIS);
230   if (!Cmp || !(Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e32 ||
231                 Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e64) ||
232       Cmp->getParent() != And->getParent())
233     return AMDGPU::NoRegister;
234 
235   MachineOperand *Op1 = TII->getNamedOperand(*Cmp, AMDGPU::OpName::src0);
236   MachineOperand *Op2 = TII->getNamedOperand(*Cmp, AMDGPU::OpName::src1);
237   if (Op1->isImm() && Op2->isReg())
238     std::swap(Op1, Op2);
239   if (!Op1->isReg() || !Op2->isImm() || Op2->getImm() != 1)
240     return AMDGPU::NoRegister;
241 
242   Register SelReg = Op1->getReg();
243   auto *Sel = TRI->findReachingDef(SelReg, Op1->getSubReg(), *Cmp, MRI, LIS);
244   if (!Sel || Sel->getOpcode() != AMDGPU::V_CNDMASK_B32_e64)
245     return AMDGPU::NoRegister;
246 
247   if (TII->hasModifiersSet(*Sel, AMDGPU::OpName::src0_modifiers) ||
248       TII->hasModifiersSet(*Sel, AMDGPU::OpName::src1_modifiers))
249     return AMDGPU::NoRegister;
250 
251   Op1 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src0);
252   Op2 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src1);
253   MachineOperand *CC = TII->getNamedOperand(*Sel, AMDGPU::OpName::src2);
254   if (!Op1->isImm() || !Op2->isImm() || !CC->isReg() ||
255       Op1->getImm() != 0 || Op2->getImm() != 1)
256     return AMDGPU::NoRegister;
257 
258   LLVM_DEBUG(dbgs() << "Folding sequence:\n\t" << *Sel << '\t' << *Cmp << '\t'
259                     << *And);
260 
261   Register CCReg = CC->getReg();
262   LIS->RemoveMachineInstrFromMaps(*And);
263   MachineInstr *Andn2 =
264       BuildMI(MBB, *And, And->getDebugLoc(), TII->get(Andn2Opc),
265               And->getOperand(0).getReg())
266           .addReg(ExecReg)
267           .addReg(CCReg, getUndefRegState(CC->isUndef()), CC->getSubReg());
268   And->eraseFromParent();
269   LIS->InsertMachineInstrInMaps(*Andn2);
270 
271   LLVM_DEBUG(dbgs() << "=>\n\t" << *Andn2 << '\n');
272 
273   // Try to remove compare. Cmp value should not used in between of cmp
274   // and s_and_b64 if VCC or just unused if any other register.
275   if ((Register::isVirtualRegister(CmpReg) && MRI.use_nodbg_empty(CmpReg)) ||
276       (CmpReg == CondReg &&
277        std::none_of(std::next(Cmp->getIterator()), Andn2->getIterator(),
278                     [&](const MachineInstr &MI) {
279                       return MI.readsRegister(CondReg, TRI);
280                     }))) {
281     LLVM_DEBUG(dbgs() << "Erasing: " << *Cmp << '\n');
282 
283     LIS->RemoveMachineInstrFromMaps(*Cmp);
284     Cmp->eraseFromParent();
285 
286     // Try to remove v_cndmask_b32.
287     if (Register::isVirtualRegister(SelReg) && MRI.use_nodbg_empty(SelReg)) {
288       LLVM_DEBUG(dbgs() << "Erasing: " << *Sel << '\n');
289 
290       LIS->RemoveMachineInstrFromMaps(*Sel);
291       Sel->eraseFromParent();
292     }
293   }
294 
295   return CCReg;
296 }
297 
298 bool SIOptimizeExecMaskingPreRA::runOnMachineFunction(MachineFunction &MF) {
299   if (skipFunction(MF.getFunction()))
300     return false;
301 
302   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
303   TRI = ST.getRegisterInfo();
304   TII = ST.getInstrInfo();
305   MRI = &MF.getRegInfo();
306 
307   MachineRegisterInfo &MRI = MF.getRegInfo();
308   LiveIntervals *LIS = &getAnalysis<LiveIntervals>();
309   DenseSet<unsigned> RecalcRegs({AMDGPU::EXEC_LO, AMDGPU::EXEC_HI});
310   unsigned Exec = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
311   bool Changed = false;
312 
313   for (MachineBasicBlock &MBB : MF) {
314 
315     if (unsigned Reg = optimizeVcndVcmpPair(MBB, ST, MRI, LIS)) {
316       RecalcRegs.insert(Reg);
317       RecalcRegs.insert(AMDGPU::VCC_LO);
318       RecalcRegs.insert(AMDGPU::VCC_HI);
319       RecalcRegs.insert(AMDGPU::SCC);
320       Changed = true;
321     }
322 
323     // Try to remove unneeded instructions before s_endpgm.
324     if (MBB.succ_empty()) {
325       if (MBB.empty())
326         continue;
327 
328       // Skip this if the endpgm has any implicit uses, otherwise we would need
329       // to be careful to update / remove them.
330       // S_ENDPGM always has a single imm operand that is not used other than to
331       // end up in the encoding
332       MachineInstr &Term = MBB.back();
333       if (Term.getOpcode() != AMDGPU::S_ENDPGM || Term.getNumOperands() != 1)
334         continue;
335 
336       SmallVector<MachineBasicBlock*, 4> Blocks({&MBB});
337 
338       while (!Blocks.empty()) {
339         auto CurBB = Blocks.pop_back_val();
340         auto I = CurBB->rbegin(), E = CurBB->rend();
341         if (I != E) {
342           if (I->isUnconditionalBranch() || I->getOpcode() == AMDGPU::S_ENDPGM)
343             ++I;
344           else if (I->isBranch())
345             continue;
346         }
347 
348         while (I != E) {
349           if (I->isDebugInstr()) {
350             I = std::next(I);
351             continue;
352           }
353 
354           if (I->mayStore() || I->isBarrier() || I->isCall() ||
355               I->hasUnmodeledSideEffects() || I->hasOrderedMemoryRef())
356             break;
357 
358           LLVM_DEBUG(dbgs()
359                      << "Removing no effect instruction: " << *I << '\n');
360 
361           for (auto &Op : I->operands()) {
362             if (Op.isReg())
363               RecalcRegs.insert(Op.getReg());
364           }
365 
366           auto Next = std::next(I);
367           LIS->RemoveMachineInstrFromMaps(*I);
368           I->eraseFromParent();
369           I = Next;
370 
371           Changed = true;
372         }
373 
374         if (I != E)
375           continue;
376 
377         // Try to ascend predecessors.
378         for (auto *Pred : CurBB->predecessors()) {
379           if (Pred->succ_size() == 1)
380             Blocks.push_back(Pred);
381         }
382       }
383       continue;
384     }
385 
386     if (!RemoveRedundantEndcf)
387       continue;
388 
389     // Try to collapse adjacent endifs.
390     // The assumption is that conditional regions are perfectly nested and
391     // a mask restored at the exit from the inner block will be completely
392     // covered by a mask restored in the outer.
393     auto E = MBB.end();
394     auto Lead = skipDebugInstructionsForward(MBB.begin(), E);
395     if (MBB.succ_size() != 1 || Lead == E || !isEndCF(*Lead, TRI, ST))
396       continue;
397 
398     MachineBasicBlock *TmpMBB = &MBB;
399     auto NextLead = skipIgnoreExecInstsTrivialSucc(TmpMBB, std::next(Lead));
400     if (NextLead == TmpMBB->end() || !isEndCF(*NextLead, TRI, ST) ||
401         !getOrExecSource(*NextLead, *TII, MRI, ST))
402       continue;
403 
404     LLVM_DEBUG(dbgs() << "Redundant EXEC = S_OR_B64 found: " << *Lead << '\n');
405 
406     auto SaveExec = getOrExecSource(*Lead, *TII, MRI, ST);
407     unsigned SaveExecReg = getOrNonExecReg(*Lead, *TII, ST);
408     for (auto &Op : Lead->operands()) {
409       if (Op.isReg())
410         RecalcRegs.insert(Op.getReg());
411     }
412 
413     LIS->RemoveMachineInstrFromMaps(*Lead);
414     Lead->eraseFromParent();
415     if (SaveExecReg) {
416       LIS->removeInterval(SaveExecReg);
417       LIS->createAndComputeVirtRegInterval(SaveExecReg);
418     }
419 
420     Changed = true;
421 
422     // If the only use of saved exec in the removed instruction is S_AND_B64
423     // fold the copy now.
424     if (!SaveExec || !SaveExec->isFullCopy())
425       continue;
426 
427     Register SavedExec = SaveExec->getOperand(0).getReg();
428     bool SafeToReplace = true;
429     for (auto& U : MRI.use_nodbg_instructions(SavedExec)) {
430       if (U.getParent() != SaveExec->getParent()) {
431         SafeToReplace = false;
432         break;
433       }
434 
435       LLVM_DEBUG(dbgs() << "Redundant EXEC COPY: " << *SaveExec << '\n');
436     }
437 
438     if (SafeToReplace) {
439       LIS->RemoveMachineInstrFromMaps(*SaveExec);
440       SaveExec->eraseFromParent();
441       MRI.replaceRegWith(SavedExec, Exec);
442       LIS->removeInterval(SavedExec);
443     }
444   }
445 
446   if (Changed) {
447     for (auto Reg : RecalcRegs) {
448       if (Register::isVirtualRegister(Reg)) {
449         LIS->removeInterval(Reg);
450         if (!MRI.reg_empty(Reg))
451           LIS->createAndComputeVirtRegInterval(Reg);
452       } else {
453         LIS->removeAllRegUnitsForPhysReg(Reg);
454       }
455     }
456   }
457 
458   return Changed;
459 }
460