1 //===-- SIPreEmitPeephole.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 the peephole optimizations before code emission.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #include "AMDGPU.h"
15 #include "GCNSubtarget.h"
16 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "si-pre-emit-peephole"
22 
23 static unsigned SkipThreshold;
24 
25 static cl::opt<unsigned, true> SkipThresholdFlag(
26     "amdgpu-skip-threshold", cl::Hidden,
27     cl::desc(
28         "Number of instructions before jumping over divergent control flow"),
29     cl::location(SkipThreshold), cl::init(12));
30 
31 namespace {
32 
33 class SIPreEmitPeephole : public MachineFunctionPass {
34 private:
35   const SIInstrInfo *TII = nullptr;
36   const SIRegisterInfo *TRI = nullptr;
37 
38   bool optimizeVccBranch(MachineInstr &MI) const;
39   bool optimizeSetGPR(MachineInstr &First, MachineInstr &MI) const;
40   bool getBlockDestinations(MachineBasicBlock &SrcMBB,
41                             MachineBasicBlock *&TrueMBB,
42                             MachineBasicBlock *&FalseMBB,
43                             SmallVectorImpl<MachineOperand> &Cond);
44   bool mustRetainExeczBranch(const MachineBasicBlock &From,
45                              const MachineBasicBlock &To) const;
46   bool removeExeczBranch(MachineInstr &MI, MachineBasicBlock &SrcMBB);
47 
48 public:
49   static char ID;
50 
51   SIPreEmitPeephole() : MachineFunctionPass(ID) {
52     initializeSIPreEmitPeepholePass(*PassRegistry::getPassRegistry());
53   }
54 
55   bool runOnMachineFunction(MachineFunction &MF) override;
56 };
57 
58 } // End anonymous namespace.
59 
60 INITIALIZE_PASS(SIPreEmitPeephole, DEBUG_TYPE,
61                 "SI peephole optimizations", false, false)
62 
63 char SIPreEmitPeephole::ID = 0;
64 
65 char &llvm::SIPreEmitPeepholeID = SIPreEmitPeephole::ID;
66 
67 bool SIPreEmitPeephole::optimizeVccBranch(MachineInstr &MI) const {
68   // Match:
69   // sreg = -1 or 0
70   // vcc = S_AND_B64 exec, sreg or S_ANDN2_B64 exec, sreg
71   // S_CBRANCH_VCC[N]Z
72   // =>
73   // S_CBRANCH_EXEC[N]Z
74   // We end up with this pattern sometimes after basic block placement.
75   // It happens while combining a block which assigns -1 or 0 to a saved mask
76   // and another block which consumes that saved mask and then a branch.
77   bool Changed = false;
78   MachineBasicBlock &MBB = *MI.getParent();
79   const GCNSubtarget &ST = MBB.getParent()->getSubtarget<GCNSubtarget>();
80   const bool IsWave32 = ST.isWave32();
81   const unsigned CondReg = TRI->getVCC();
82   const unsigned ExecReg = IsWave32 ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
83   const unsigned And = IsWave32 ? AMDGPU::S_AND_B32 : AMDGPU::S_AND_B64;
84   const unsigned AndN2 = IsWave32 ? AMDGPU::S_ANDN2_B32 : AMDGPU::S_ANDN2_B64;
85   const unsigned Mov = IsWave32 ? AMDGPU::S_MOV_B32 : AMDGPU::S_MOV_B64;
86 
87   MachineBasicBlock::reverse_iterator A = MI.getReverseIterator(),
88                                       E = MBB.rend();
89   bool ReadsCond = false;
90   unsigned Threshold = 5;
91   for (++A; A != E; ++A) {
92     if (!--Threshold)
93       return false;
94     if (A->modifiesRegister(ExecReg, TRI))
95       return false;
96     if (A->modifiesRegister(CondReg, TRI)) {
97       if (!A->definesRegister(CondReg, TRI) ||
98           (A->getOpcode() != And && A->getOpcode() != AndN2))
99         return false;
100       break;
101     }
102     ReadsCond |= A->readsRegister(CondReg, TRI);
103   }
104   if (A == E)
105     return false;
106 
107   MachineOperand &Op1 = A->getOperand(1);
108   MachineOperand &Op2 = A->getOperand(2);
109   if (Op1.getReg() != ExecReg && Op2.isReg() && Op2.getReg() == ExecReg) {
110     TII->commuteInstruction(*A);
111     Changed = true;
112   }
113   if (Op1.getReg() != ExecReg)
114     return Changed;
115   if (Op2.isImm() && !(Op2.getImm() == -1 || Op2.getImm() == 0))
116     return Changed;
117 
118   int64_t MaskValue = 0;
119   Register SReg;
120   if (Op2.isReg()) {
121     SReg = Op2.getReg();
122     auto M = std::next(A);
123     bool ReadsSreg = false;
124     for (; M != E; ++M) {
125       if (M->definesRegister(SReg, TRI))
126         break;
127       if (M->modifiesRegister(SReg, TRI))
128         return Changed;
129       ReadsSreg |= M->readsRegister(SReg, TRI);
130     }
131     if (M == E || !M->isMoveImmediate() || !M->getOperand(1).isImm() ||
132         (M->getOperand(1).getImm() != -1 && M->getOperand(1).getImm() != 0))
133       return Changed;
134     MaskValue = M->getOperand(1).getImm();
135     // First if sreg is only used in the AND instruction fold the immediate
136     // into into the AND.
137     if (!ReadsSreg && Op2.isKill()) {
138       A->getOperand(2).ChangeToImmediate(MaskValue);
139       M->eraseFromParent();
140     }
141   } else if (Op2.isImm()) {
142     MaskValue = Op2.getImm();
143   } else {
144     llvm_unreachable("Op2 must be register or immediate");
145   }
146 
147   // Invert mask for s_andn2
148   assert(MaskValue == 0 || MaskValue == -1);
149   if (A->getOpcode() == AndN2)
150     MaskValue = ~MaskValue;
151 
152   if (!ReadsCond && A->registerDefIsDead(AMDGPU::SCC)) {
153     if (!MI.killsRegister(CondReg, TRI)) {
154       // Replace AND with MOV
155       if (MaskValue == 0) {
156         BuildMI(*A->getParent(), *A, A->getDebugLoc(), TII->get(Mov), CondReg)
157             .addImm(0);
158       } else {
159         BuildMI(*A->getParent(), *A, A->getDebugLoc(), TII->get(Mov), CondReg)
160             .addReg(ExecReg);
161       }
162     }
163     // Remove AND instruction
164     A->eraseFromParent();
165   }
166 
167   bool IsVCCZ = MI.getOpcode() == AMDGPU::S_CBRANCH_VCCZ;
168   if (SReg == ExecReg) {
169     // EXEC is updated directly
170     if (IsVCCZ) {
171       MI.eraseFromParent();
172       return true;
173     }
174     MI.setDesc(TII->get(AMDGPU::S_BRANCH));
175   } else if (IsVCCZ && MaskValue == 0) {
176     // Will always branch
177     // Remove all succesors shadowed by new unconditional branch
178     MachineBasicBlock *Parent = MI.getParent();
179     SmallVector<MachineInstr *, 4> ToRemove;
180     bool Found = false;
181     for (MachineInstr &Term : Parent->terminators()) {
182       if (Found) {
183         if (Term.isBranch())
184           ToRemove.push_back(&Term);
185       } else {
186         Found = Term.isIdenticalTo(MI);
187       }
188     }
189     assert(Found && "conditional branch is not terminator");
190     for (auto BranchMI : ToRemove) {
191       MachineOperand &Dst = BranchMI->getOperand(0);
192       assert(Dst.isMBB() && "destination is not basic block");
193       Parent->removeSuccessor(Dst.getMBB());
194       BranchMI->eraseFromParent();
195     }
196 
197     if (MachineBasicBlock *Succ = Parent->getFallThrough()) {
198       Parent->removeSuccessor(Succ);
199     }
200 
201     // Rewrite to unconditional branch
202     MI.setDesc(TII->get(AMDGPU::S_BRANCH));
203   } else if (!IsVCCZ && MaskValue == 0) {
204     // Will never branch
205     MachineOperand &Dst = MI.getOperand(0);
206     assert(Dst.isMBB() && "destination is not basic block");
207     MI.getParent()->removeSuccessor(Dst.getMBB());
208     MI.eraseFromParent();
209     return true;
210   } else if (MaskValue == -1) {
211     // Depends only on EXEC
212     MI.setDesc(
213         TII->get(IsVCCZ ? AMDGPU::S_CBRANCH_EXECZ : AMDGPU::S_CBRANCH_EXECNZ));
214   }
215 
216   MI.RemoveOperand(MI.findRegisterUseOperandIdx(CondReg, false /*Kill*/, TRI));
217   MI.addImplicitDefUseOperands(*MBB.getParent());
218 
219   return true;
220 }
221 
222 bool SIPreEmitPeephole::optimizeSetGPR(MachineInstr &First,
223                                        MachineInstr &MI) const {
224   MachineBasicBlock &MBB = *MI.getParent();
225   const MachineFunction &MF = *MBB.getParent();
226   const MachineRegisterInfo &MRI = MF.getRegInfo();
227   MachineOperand *Idx = TII->getNamedOperand(MI, AMDGPU::OpName::src0);
228   Register IdxReg = Idx->isReg() ? Idx->getReg() : Register();
229   SmallVector<MachineInstr *, 4> ToRemove;
230   bool IdxOn = true;
231 
232   if (!MI.isIdenticalTo(First))
233     return false;
234 
235   // Scan back to find an identical S_SET_GPR_IDX_ON
236   for (MachineBasicBlock::instr_iterator I = std::next(First.getIterator()),
237                                          E = MI.getIterator();
238        I != E; ++I) {
239     if (I->isBundle())
240       continue;
241     switch (I->getOpcode()) {
242     case AMDGPU::S_SET_GPR_IDX_MODE:
243       return false;
244     case AMDGPU::S_SET_GPR_IDX_OFF:
245       IdxOn = false;
246       ToRemove.push_back(&*I);
247       break;
248     default:
249       if (I->modifiesRegister(AMDGPU::M0, TRI))
250         return false;
251       if (IdxReg && I->modifiesRegister(IdxReg, TRI))
252         return false;
253       if (llvm::any_of(I->operands(),
254                        [&MRI, this](const MachineOperand &MO) {
255                          return MO.isReg() &&
256                                 TRI->isVectorRegister(MRI, MO.getReg());
257                        })) {
258         // The only exception allowed here is another indirect vector move
259         // with the same mode.
260         if (!IdxOn ||
261             !((I->getOpcode() == AMDGPU::V_MOV_B32_e32 &&
262                I->hasRegisterImplicitUseOperand(AMDGPU::M0)) ||
263               I->getOpcode() == AMDGPU::V_MOV_B32_indirect))
264           return false;
265       }
266     }
267   }
268 
269   MI.eraseFromBundle();
270   for (MachineInstr *RI : ToRemove)
271     RI->eraseFromBundle();
272   return true;
273 }
274 
275 bool SIPreEmitPeephole::getBlockDestinations(
276     MachineBasicBlock &SrcMBB, MachineBasicBlock *&TrueMBB,
277     MachineBasicBlock *&FalseMBB, SmallVectorImpl<MachineOperand> &Cond) {
278   if (TII->analyzeBranch(SrcMBB, TrueMBB, FalseMBB, Cond))
279     return false;
280 
281   if (!FalseMBB)
282     FalseMBB = SrcMBB.getNextNode();
283 
284   return true;
285 }
286 
287 bool SIPreEmitPeephole::mustRetainExeczBranch(
288     const MachineBasicBlock &From, const MachineBasicBlock &To) const {
289   unsigned NumInstr = 0;
290   const MachineFunction *MF = From.getParent();
291 
292   for (MachineFunction::const_iterator MBBI(&From), ToI(&To), End = MF->end();
293        MBBI != End && MBBI != ToI; ++MBBI) {
294     const MachineBasicBlock &MBB = *MBBI;
295 
296     for (MachineBasicBlock::const_iterator I = MBB.begin(), E = MBB.end();
297          I != E; ++I) {
298       // When a uniform loop is inside non-uniform control flow, the branch
299       // leaving the loop might never be taken when EXEC = 0.
300       // Hence we should retain cbranch out of the loop lest it become infinite.
301       if (I->isConditionalBranch())
302         return true;
303 
304       if (TII->hasUnwantedEffectsWhenEXECEmpty(*I))
305         return true;
306 
307       // These instructions are potentially expensive even if EXEC = 0.
308       if (TII->isSMRD(*I) || TII->isVMEM(*I) || TII->isFLAT(*I) ||
309           TII->isDS(*I) || I->getOpcode() == AMDGPU::S_WAITCNT)
310         return true;
311 
312       ++NumInstr;
313       if (NumInstr >= SkipThreshold)
314         return true;
315     }
316   }
317 
318   return false;
319 }
320 
321 // Returns true if the skip branch instruction is removed.
322 bool SIPreEmitPeephole::removeExeczBranch(MachineInstr &MI,
323                                           MachineBasicBlock &SrcMBB) {
324   MachineBasicBlock *TrueMBB = nullptr;
325   MachineBasicBlock *FalseMBB = nullptr;
326   SmallVector<MachineOperand, 1> Cond;
327 
328   if (!getBlockDestinations(SrcMBB, TrueMBB, FalseMBB, Cond))
329     return false;
330 
331   // Consider only the forward branches.
332   if ((SrcMBB.getNumber() >= TrueMBB->getNumber()) ||
333       mustRetainExeczBranch(*FalseMBB, *TrueMBB))
334     return false;
335 
336   LLVM_DEBUG(dbgs() << "Removing the execz branch: " << MI);
337   MI.eraseFromParent();
338   SrcMBB.removeSuccessor(TrueMBB);
339 
340   return true;
341 }
342 
343 bool SIPreEmitPeephole::runOnMachineFunction(MachineFunction &MF) {
344   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
345   TII = ST.getInstrInfo();
346   TRI = &TII->getRegisterInfo();
347   bool Changed = false;
348 
349   MF.RenumberBlocks();
350 
351   for (MachineBasicBlock &MBB : MF) {
352     MachineBasicBlock::iterator TermI = MBB.getFirstTerminator();
353     // Check first terminator for branches to optimize
354     if (TermI != MBB.end()) {
355       MachineInstr &MI = *TermI;
356       switch (MI.getOpcode()) {
357       case AMDGPU::S_CBRANCH_VCCZ:
358       case AMDGPU::S_CBRANCH_VCCNZ:
359         Changed |= optimizeVccBranch(MI);
360         break;
361       case AMDGPU::S_CBRANCH_EXECZ:
362         Changed |= removeExeczBranch(MI, MBB);
363         break;
364       }
365     }
366 
367     if (!ST.hasVGPRIndexMode())
368       continue;
369 
370     MachineInstr *SetGPRMI = nullptr;
371     const unsigned Threshold = 20;
372     unsigned Count = 0;
373     // Scan the block for two S_SET_GPR_IDX_ON instructions to see if a
374     // second is not needed. Do expensive checks in the optimizeSetGPR()
375     // and limit the distance to 20 instructions for compile time purposes.
376     // Note: this needs to work on bundles as S_SET_GPR_IDX* instructions
377     // may be bundled with the instructions they modify.
378     for (auto &MI :
379          make_early_inc_range(make_range(MBB.instr_begin(), MBB.instr_end()))) {
380       if (Count == Threshold)
381         SetGPRMI = nullptr;
382       else
383         ++Count;
384 
385       if (MI.getOpcode() != AMDGPU::S_SET_GPR_IDX_ON)
386         continue;
387 
388       Count = 0;
389       if (!SetGPRMI) {
390         SetGPRMI = &MI;
391         continue;
392       }
393 
394       if (optimizeSetGPR(*SetGPRMI, MI))
395         Changed = true;
396       else
397         SetGPRMI = &MI;
398     }
399   }
400 
401   return Changed;
402 }
403