1 //=- AArch64RedundantCopyElimination.cpp - Remove useless copy for AArch64 -=//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 // This pass removes unnecessary zero copies in BBs that are targets of
9 // cbz/cbnz instructions. For instance, the copy instruction in the code below
10 // can be removed because the CBZW jumps to BB#2 when W0 is zero.
11 //  BB#1:
12 //    CBZW %W0, <BB#2>
13 //  BB#2:
14 //    %W0 = COPY %WZR
15 // This pass should be run after register allocation.
16 //
17 // FIXME: This should be extended to handle any constant other than zero. E.g.,
18 //   cmp w0, #1
19 //     b.eq .BB1
20 //   BB1:
21 //     mov w0, #1
22 //
23 // FIXME: This could also be extended to check the whole dominance subtree below
24 // the comparison if the compile time regression is acceptable.
25 //
26 //===----------------------------------------------------------------------===//
27 
28 #include "AArch64.h"
29 #include "llvm/ADT/SetVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/iterator_range.h"
32 #include "llvm/CodeGen/MachineFunctionPass.h"
33 #include "llvm/CodeGen/MachineRegisterInfo.h"
34 #include "llvm/Support/Debug.h"
35 
36 using namespace llvm;
37 
38 #define DEBUG_TYPE "aarch64-copyelim"
39 
40 STATISTIC(NumCopiesRemoved, "Number of copies removed.");
41 
42 namespace llvm {
43 void initializeAArch64RedundantCopyEliminationPass(PassRegistry &);
44 }
45 
46 namespace {
47 class AArch64RedundantCopyElimination : public MachineFunctionPass {
48   const MachineRegisterInfo *MRI;
49   const TargetRegisterInfo *TRI;
50 
51 public:
52   static char ID;
53   AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {}
54   bool optimizeCopy(MachineBasicBlock *MBB);
55   bool runOnMachineFunction(MachineFunction &MF) override;
56   const char *getPassName() const override {
57     return "AArch64 Redundant Copy Elimination";
58   }
59 };
60 char AArch64RedundantCopyElimination::ID = 0;
61 }
62 
63 INITIALIZE_PASS(AArch64RedundantCopyElimination, "aarch64-copyelim",
64                 "AArch64 redundant copy elimination pass", false, false)
65 
66 static bool guaranteesZeroRegInBlock(MachineInstr &MI, MachineBasicBlock *MBB) {
67   unsigned Opc = MI.getOpcode();
68   // Check if the current basic block is the target block to which the
69   // CBZ/CBNZ instruction jumps when its Wt/Xt is zero.
70   if ((Opc == AArch64::CBZW || Opc == AArch64::CBZX) &&
71       MBB == MI.getOperand(1).getMBB())
72     return true;
73   else if ((Opc == AArch64::CBNZW || Opc == AArch64::CBNZX) &&
74            MBB != MI.getOperand(1).getMBB())
75     return true;
76 
77   return false;
78 }
79 
80 bool AArch64RedundantCopyElimination::optimizeCopy(MachineBasicBlock *MBB) {
81   // Check if the current basic block has a single predecessor.
82   if (MBB->pred_size() != 1)
83     return false;
84 
85   MachineBasicBlock *PredMBB = *MBB->pred_begin();
86   MachineBasicBlock::iterator CompBr = PredMBB->getLastNonDebugInstr();
87   if (CompBr == PredMBB->end() || PredMBB->succ_size() != 2)
88     return false;
89 
90   ++CompBr;
91   do {
92     --CompBr;
93     if (guaranteesZeroRegInBlock(*CompBr, MBB))
94       break;
95   } while (CompBr != PredMBB->begin() && CompBr->isTerminator());
96 
97   // We've not found a CBZ/CBNZ, time to bail out.
98   if (!guaranteesZeroRegInBlock(*CompBr, MBB))
99     return false;
100 
101   unsigned TargetReg = CompBr->getOperand(0).getReg();
102   if (!TargetReg)
103     return false;
104   assert(TargetRegisterInfo::isPhysicalRegister(TargetReg) &&
105          "Expect physical register");
106 
107   // Remember all registers aliasing with TargetReg.
108   SmallSetVector<unsigned, 8> TargetRegs;
109   for (MCRegAliasIterator AI(TargetReg, TRI, true); AI.isValid(); ++AI)
110     TargetRegs.insert(*AI);
111 
112   bool Changed = false;
113   MachineBasicBlock::iterator LastChange = MBB->begin();
114   unsigned SmallestDef = TargetReg;
115   // Remove redundant Copy instructions unless TargetReg is modified.
116   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
117     MachineInstr *MI = &*I;
118     ++I;
119     if (MI->isCopy() && MI->getOperand(0).isReg() &&
120         MI->getOperand(1).isReg()) {
121 
122       unsigned DefReg = MI->getOperand(0).getReg();
123       unsigned SrcReg = MI->getOperand(1).getReg();
124 
125       if ((SrcReg == AArch64::XZR || SrcReg == AArch64::WZR) &&
126           !MRI->isReserved(DefReg) &&
127           (TargetReg == DefReg || TRI->isSuperRegister(DefReg, TargetReg))) {
128         DEBUG(dbgs() << "Remove redundant Copy : ");
129         DEBUG((MI)->print(dbgs()));
130 
131         MI->eraseFromParent();
132         Changed = true;
133         LastChange = I;
134         NumCopiesRemoved++;
135         SmallestDef =
136             TRI->isSubRegister(SmallestDef, DefReg) ? DefReg : SmallestDef;
137         continue;
138       }
139     }
140 
141     if (MI->modifiesRegister(TargetReg, TRI))
142       break;
143   }
144 
145   if (!Changed)
146     return false;
147 
148   // Otherwise, we have to fixup the use-def chain, starting with the
149   // CBZ/CBNZ. Conservatively mark as much as we can live.
150   CompBr->clearRegisterKills(SmallestDef, TRI);
151 
152   if (std::none_of(TargetRegs.begin(), TargetRegs.end(),
153                    [&](unsigned Reg) { return MBB->isLiveIn(Reg); }))
154     MBB->addLiveIn(TargetReg);
155 
156   // Clear any kills of TargetReg between CompBr and the last removed COPY.
157   for (MachineInstr &MMI :
158        make_range(MBB->begin()->getIterator(), LastChange->getIterator()))
159     MMI.clearRegisterKills(SmallestDef, TRI);
160 
161   return true;
162 }
163 
164 bool AArch64RedundantCopyElimination::runOnMachineFunction(
165     MachineFunction &MF) {
166   TRI = MF.getSubtarget().getRegisterInfo();
167   MRI = &MF.getRegInfo();
168   bool Changed = false;
169   for (MachineBasicBlock &MBB : MF)
170     Changed |= optimizeCopy(&MBB);
171   return Changed;
172 }
173 
174 FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() {
175   return new AArch64RedundantCopyElimination();
176 }
177