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   bool 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).getRegSlot();
94   SlotIndex SelIdx = LIS->getInstructionIndex(Sel).getRegSlot();
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 true on success.
123 bool 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 false;
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 false;
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 false;
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 false;
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 false;
160 
161   Register SelReg = Op1->getReg();
162   if (SelReg.isPhysical())
163     return false;
164 
165   auto *Sel = TRI->findReachingDef(SelReg, Op1->getSubReg(), *Cmp, *MRI, LIS);
166   if (!Sel || Sel->getOpcode() != AMDGPU::V_CNDMASK_B32_e64)
167     return false;
168 
169   if (TII->hasModifiersSet(*Sel, AMDGPU::OpName::src0_modifiers) ||
170       TII->hasModifiersSet(*Sel, AMDGPU::OpName::src1_modifiers))
171     return false;
172 
173   Op1 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src0);
174   Op2 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src1);
175   MachineOperand *CC = TII->getNamedOperand(*Sel, 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, LIS, CCReg, *Sel, *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(*Sel);
190   LiveInterval *SelLI = &LIS->getInterval(SelReg);
191   if (llvm::any_of(SelLI->vnis(),
192                     [](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(MBB, *And, And->getDebugLoc(), TII->get(Andn2Opc),
203               And->getOperand(0).getReg())
204           .addReg(ExecReg)
205           .addReg(CCReg, getUndefRegState(CC->isUndef()), CC->getSubReg());
206   MachineOperand &AndSCC = And->getOperand(3);
207   assert(AndSCC.getReg() == AMDGPU::SCC);
208   MachineOperand &Andn2SCC = Andn2->getOperand(3);
209   assert(Andn2SCC.getReg() == AMDGPU::SCC);
210   Andn2SCC.setIsDead(AndSCC.isDead());
211 
212   SlotIndex AndIdx = LIS->ReplaceMachineInstrInMaps(*And, *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(*Cmp);
220   if (CCReg.isVirtual()) {
221     // Apply live ranges from SelLI to CCReg potentially matching splits
222     // and extending to loop boundaries.
223 
224     auto applyLiveRanges = [&](LiveRange &Dst, VNInfo *VNI) {
225       // Copy live ranges from SelLI, adjusting start and end as required
226       auto DefSegment = SelLI->FindSegmentContaining(SelIdx.getRegSlot());
227       assert(DefSegment != SelLI->end() &&
228              "No live interval segment covering definition?");
229       for (auto I = DefSegment; I != SelLI->end(); ++I) {
230         SlotIndex Start = I->start < SelIdx.getRegSlot() ?
231                           SelIdx.getRegSlot() : I->start;
232         SlotIndex End = I->end < AndIdx.getRegSlot() || I->end.isBlock() ?
233                         I->end : AndIdx.getRegSlot();
234         Dst.addSegment(LiveRange::Segment(Start, End, VNI));
235       }
236       // If SelLI does not cover AndIdx (because Cmp killed Sel) then extend.
237       if (!SelLI->getSegmentContaining(AndIdx.getRegSlot()))
238         Dst.addSegment(LiveRange::Segment(CmpIdx.getRegSlot(), AndIdx.getRegSlot(), VNI));
239     };
240 
241     LiveInterval &CCLI = LIS->getInterval(CCReg);
242     auto CCQ = CCLI.Query(SelIdx.getRegSlot());
243     if (CCQ.valueIn())
244       applyLiveRanges(CCLI, CCQ.valueIn());
245 
246     if (CC->getSubReg()) {
247       LaneBitmask Mask = TRI->getSubRegIndexLaneMask(CC->getSubReg());
248       BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
249       CCLI.refineSubRanges(
250           Allocator, Mask,
251           [=](LiveInterval::SubRange &SR) {
252             auto CCQS = SR.Query(SelIdx.getRegSlot());
253             if (CCQS.valueIn())
254               applyLiveRanges(SR, CCQS.valueIn());
255           },
256           *LIS->getSlotIndexes(), *TRI);
257       CCLI.removeEmptySubRanges();
258 
259       SmallVector<LiveInterval *> SplitLIs;
260       LIS->splitSeparateComponents(CCLI, SplitLIs);
261     }
262   } else
263     LIS->removeAllRegUnitsForPhysReg(CCReg);
264 
265   // Try to remove compare. Cmp value should not used in between of cmp
266   // and s_and_b64 if VCC or just unused if any other register.
267   LiveInterval *CmpLI = CmpReg.isVirtual() ? &LIS->getInterval(CmpReg) : nullptr;
268   if ((CmpLI && CmpLI->Query(AndIdx.getRegSlot()).isKill()) ||
269       (CmpReg == Register(CondReg) &&
270        std::none_of(std::next(Cmp->getIterator()), Andn2->getIterator(),
271                     [&](const MachineInstr &MI) {
272                       return MI.readsRegister(CondReg, TRI);
273                     }))) {
274     LLVM_DEBUG(dbgs() << "Erasing: " << *Cmp << '\n');
275     if (CmpLI)
276       LIS->removeVRegDefAt(*CmpLI, CmpIdx.getRegSlot());
277     LIS->RemoveMachineInstrFromMaps(*Cmp);
278     Cmp->eraseFromParent();
279 
280     // Try to remove v_cndmask_b32.
281     // Kill status must be checked before shrinking the live range.
282     bool IsKill = SelLI->Query(CmpIdx.getRegSlot()).isKill();
283     LIS->shrinkToUses(SelLI);
284     bool IsDead = SelLI->Query(SelIdx.getRegSlot()).isDeadDef();
285     if (MRI->use_nodbg_empty(SelReg) && (IsKill || IsDead)) {
286       LLVM_DEBUG(dbgs() << "Erasing: " << *Sel << '\n');
287 
288       LIS->removeVRegDefAt(*SelLI, SelIdx.getRegSlot());
289       LIS->RemoveMachineInstrFromMaps(*Sel);
290       Sel->eraseFromParent();
291     }
292   }
293 
294   return true;
295 }
296 
297 // Optimize sequence
298 //    %dst = S_OR_SAVEEXEC %src
299 //    ... instructions not modifying exec ...
300 //    %tmp = S_AND $exec, %dst
301 //    $exec = S_XOR_term $exec, %tmp
302 // =>
303 //    %dst = S_OR_SAVEEXEC %src
304 //    ... instructions not modifying exec ...
305 //    $exec = S_XOR_term $exec, %dst
306 //
307 // Clean up potentially unnecessary code added for safety during
308 // control flow lowering.
309 //
310 // Return whether any changes were made to MBB.
311 bool SIOptimizeExecMaskingPreRA::optimizeElseBranch(MachineBasicBlock &MBB) {
312   if (MBB.empty())
313     return false;
314 
315   // Check this is an else block.
316   auto First = MBB.begin();
317   MachineInstr &SaveExecMI = *First;
318   if (SaveExecMI.getOpcode() != OrSaveExecOpc)
319     return false;
320 
321   auto I = llvm::find_if(MBB.terminators(), [this](const MachineInstr &MI) {
322     return MI.getOpcode() == XorTermrOpc;
323   });
324   if (I == MBB.terminators().end())
325     return false;
326 
327   MachineInstr &XorTermMI = *I;
328   if (XorTermMI.getOperand(1).getReg() != Register(ExecReg))
329     return false;
330 
331   Register SavedExecReg = SaveExecMI.getOperand(0).getReg();
332   Register DstReg = XorTermMI.getOperand(2).getReg();
333 
334   // Find potentially unnecessary S_AND
335   MachineInstr *AndExecMI = nullptr;
336   I--;
337   while (I != First && !AndExecMI) {
338     if (I->getOpcode() == AndOpc && I->getOperand(0).getReg() == DstReg &&
339         I->getOperand(1).getReg() == Register(ExecReg))
340       AndExecMI = &*I;
341     I--;
342   }
343   if (!AndExecMI)
344     return false;
345 
346   // Check for exec modifying instructions.
347   // Note: exec defs do not create live ranges beyond the
348   // instruction so isDefBetween cannot be used.
349   // Instead just check that the def segments are adjacent.
350   SlotIndex StartIdx = LIS->getInstructionIndex(SaveExecMI);
351   SlotIndex EndIdx = LIS->getInstructionIndex(*AndExecMI);
352   for (MCRegUnitIterator UI(ExecReg, TRI); UI.isValid(); ++UI) {
353     LiveRange &RegUnit = LIS->getRegUnit(*UI);
354     if (RegUnit.find(StartIdx) != std::prev(RegUnit.find(EndIdx)))
355       return false;
356   }
357 
358   // Remove unnecessary S_AND
359   LIS->removeInterval(SavedExecReg);
360   LIS->removeInterval(DstReg);
361 
362   SaveExecMI.getOperand(0).setReg(DstReg);
363 
364   LIS->RemoveMachineInstrFromMaps(*AndExecMI);
365   AndExecMI->eraseFromParent();
366 
367   LIS->createAndComputeVirtRegInterval(DstReg);
368 
369   return true;
370 }
371 
372 bool SIOptimizeExecMaskingPreRA::runOnMachineFunction(MachineFunction &MF) {
373   if (skipFunction(MF.getFunction()))
374     return false;
375 
376   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
377   TRI = ST.getRegisterInfo();
378   TII = ST.getInstrInfo();
379   MRI = &MF.getRegInfo();
380   LIS = &getAnalysis<LiveIntervals>();
381 
382   const bool Wave32 = ST.isWave32();
383   AndOpc = Wave32 ? AMDGPU::S_AND_B32 : AMDGPU::S_AND_B64;
384   Andn2Opc = Wave32 ? AMDGPU::S_ANDN2_B32 : AMDGPU::S_ANDN2_B64;
385   OrSaveExecOpc =
386       Wave32 ? AMDGPU::S_OR_SAVEEXEC_B32 : AMDGPU::S_OR_SAVEEXEC_B64;
387   XorTermrOpc = Wave32 ? AMDGPU::S_XOR_B32_term : AMDGPU::S_XOR_B64_term;
388   CondReg = MCRegister::from(Wave32 ? AMDGPU::VCC_LO : AMDGPU::VCC);
389   ExecReg = MCRegister::from(Wave32 ? AMDGPU::EXEC_LO : AMDGPU::EXEC);
390 
391   DenseSet<Register> RecalcRegs({AMDGPU::EXEC_LO, AMDGPU::EXEC_HI});
392   bool Changed = false;
393 
394   for (MachineBasicBlock &MBB : MF) {
395 
396     if (optimizeElseBranch(MBB)) {
397       RecalcRegs.insert(AMDGPU::SCC);
398       Changed = true;
399     }
400 
401     if (optimizeVcndVcmpPair(MBB)) {
402       RecalcRegs.insert(AMDGPU::VCC_LO);
403       RecalcRegs.insert(AMDGPU::VCC_HI);
404       RecalcRegs.insert(AMDGPU::SCC);
405       Changed = true;
406     }
407 
408     // Try to remove unneeded instructions before s_endpgm.
409     if (MBB.succ_empty()) {
410       if (MBB.empty())
411         continue;
412 
413       // Skip this if the endpgm has any implicit uses, otherwise we would need
414       // to be careful to update / remove them.
415       // S_ENDPGM always has a single imm operand that is not used other than to
416       // end up in the encoding
417       MachineInstr &Term = MBB.back();
418       if (Term.getOpcode() != AMDGPU::S_ENDPGM || Term.getNumOperands() != 1)
419         continue;
420 
421       SmallVector<MachineBasicBlock*, 4> Blocks({&MBB});
422 
423       while (!Blocks.empty()) {
424         auto CurBB = Blocks.pop_back_val();
425         auto I = CurBB->rbegin(), E = CurBB->rend();
426         if (I != E) {
427           if (I->isUnconditionalBranch() || I->getOpcode() == AMDGPU::S_ENDPGM)
428             ++I;
429           else if (I->isBranch())
430             continue;
431         }
432 
433         while (I != E) {
434           if (I->isDebugInstr()) {
435             I = std::next(I);
436             continue;
437           }
438 
439           if (I->mayStore() || I->isBarrier() || I->isCall() ||
440               I->hasUnmodeledSideEffects() || I->hasOrderedMemoryRef())
441             break;
442 
443           LLVM_DEBUG(dbgs()
444                      << "Removing no effect instruction: " << *I << '\n');
445 
446           for (auto &Op : I->operands()) {
447             if (Op.isReg())
448               RecalcRegs.insert(Op.getReg());
449           }
450 
451           auto Next = std::next(I);
452           LIS->RemoveMachineInstrFromMaps(*I);
453           I->eraseFromParent();
454           I = Next;
455 
456           Changed = true;
457         }
458 
459         if (I != E)
460           continue;
461 
462         // Try to ascend predecessors.
463         for (auto *Pred : CurBB->predecessors()) {
464           if (Pred->succ_size() == 1)
465             Blocks.push_back(Pred);
466         }
467       }
468       continue;
469     }
470 
471     // If the only user of a logical operation is move to exec, fold it now
472     // to prevent forming of saveexec. I.e.:
473     //
474     //    %0:sreg_64 = COPY $exec
475     //    %1:sreg_64 = S_AND_B64 %0:sreg_64, %2:sreg_64
476     // =>
477     //    %1 = S_AND_B64 $exec, %2:sreg_64
478     unsigned ScanThreshold = 10;
479     for (auto I = MBB.rbegin(), E = MBB.rend(); I != E
480          && ScanThreshold--; ++I) {
481       // Continue scanning if this is not a full exec copy
482       if (!(I->isFullCopy() && I->getOperand(1).getReg() == Register(ExecReg)))
483         continue;
484 
485       Register SavedExec = I->getOperand(0).getReg();
486       if (SavedExec.isVirtual() && MRI->hasOneNonDBGUse(SavedExec)) {
487         MachineInstr *SingleExecUser = &*MRI->use_instr_nodbg_begin(SavedExec);
488         int Idx = SingleExecUser->findRegisterUseOperandIdx(SavedExec);
489         assert(Idx != -1);
490         if (SingleExecUser->getParent() == I->getParent() &&
491             !SingleExecUser->getOperand(Idx).isImplicit() &&
492             TII->isOperandLegal(*SingleExecUser, Idx, &I->getOperand(1))) {
493           LLVM_DEBUG(dbgs() << "Redundant EXEC COPY: " << *I << '\n');
494           LIS->RemoveMachineInstrFromMaps(*I);
495           I->eraseFromParent();
496           MRI->replaceRegWith(SavedExec, ExecReg);
497           LIS->removeInterval(SavedExec);
498           Changed = true;
499         }
500       }
501       break;
502     }
503   }
504 
505   if (Changed) {
506     for (auto Reg : RecalcRegs) {
507       if (Reg.isVirtual()) {
508         LIS->removeInterval(Reg);
509         if (!MRI->reg_empty(Reg))
510           LIS->createAndComputeVirtRegInterval(Reg);
511       } else {
512         LIS->removeAllRegUnitsForPhysReg(Reg);
513       }
514     }
515   }
516 
517   return Changed;
518 }
519