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