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 {
43 class AArch64RedundantCopyElimination : public MachineFunctionPass {
44   const MachineRegisterInfo *MRI;
45   const TargetRegisterInfo *TRI;
46 
47 public:
48   static char ID;
49   AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {
50     initializeAArch64RedundantCopyEliminationPass(
51         *PassRegistry::getPassRegistry());
52   }
53   bool optimizeCopy(MachineBasicBlock *MBB);
54   bool runOnMachineFunction(MachineFunction &MF) override;
55   MachineFunctionProperties getRequiredProperties() const override {
56     return MachineFunctionProperties().set(
57         MachineFunctionProperties::Property::NoVRegs);
58   }
59   StringRef getPassName() const override {
60     return "AArch64 Redundant Copy Elimination";
61   }
62 };
63 char AArch64RedundantCopyElimination::ID = 0;
64 }
65 
66 INITIALIZE_PASS(AArch64RedundantCopyElimination, "aarch64-copyelim",
67                 "AArch64 redundant copy elimination pass", false, false)
68 
69 static bool guaranteesZeroRegInBlock(MachineInstr &MI, MachineBasicBlock *MBB) {
70   unsigned Opc = MI.getOpcode();
71   // Check if the current basic block is the target block to which the
72   // CBZ/CBNZ instruction jumps when its Wt/Xt is zero.
73   if ((Opc == AArch64::CBZW || Opc == AArch64::CBZX) &&
74       MBB == MI.getOperand(1).getMBB())
75     return true;
76   else if ((Opc == AArch64::CBNZW || Opc == AArch64::CBNZX) &&
77            MBB != MI.getOperand(1).getMBB())
78     return true;
79 
80   return false;
81 }
82 
83 bool AArch64RedundantCopyElimination::optimizeCopy(MachineBasicBlock *MBB) {
84   // Check if the current basic block has a single predecessor.
85   if (MBB->pred_size() != 1)
86     return false;
87 
88   MachineBasicBlock *PredMBB = *MBB->pred_begin();
89   MachineBasicBlock::iterator CompBr = PredMBB->getLastNonDebugInstr();
90   if (CompBr == PredMBB->end() || PredMBB->succ_size() != 2)
91     return false;
92 
93   ++CompBr;
94   do {
95     --CompBr;
96     if (guaranteesZeroRegInBlock(*CompBr, MBB))
97       break;
98   } while (CompBr != PredMBB->begin() && CompBr->isTerminator());
99 
100   // We've not found a CBZ/CBNZ, time to bail out.
101   if (!guaranteesZeroRegInBlock(*CompBr, MBB))
102     return false;
103 
104   unsigned TargetReg = CompBr->getOperand(0).getReg();
105   if (!TargetReg)
106     return false;
107   assert(TargetRegisterInfo::isPhysicalRegister(TargetReg) &&
108          "Expect physical register");
109 
110   // Remember all registers aliasing with TargetReg.
111   SmallSetVector<unsigned, 8> TargetRegs;
112   for (MCRegAliasIterator AI(TargetReg, TRI, true); AI.isValid(); ++AI)
113     TargetRegs.insert(*AI);
114 
115   bool Changed = false;
116   MachineBasicBlock::iterator LastChange = MBB->begin();
117   unsigned SmallestDef = TargetReg;
118   // Remove redundant Copy instructions unless TargetReg is modified.
119   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
120     MachineInstr *MI = &*I;
121     ++I;
122     if (MI->isCopy() && MI->getOperand(0).isReg() &&
123         MI->getOperand(1).isReg()) {
124 
125       unsigned DefReg = MI->getOperand(0).getReg();
126       unsigned SrcReg = MI->getOperand(1).getReg();
127 
128       if ((SrcReg == AArch64::XZR || SrcReg == AArch64::WZR) &&
129           !MRI->isReserved(DefReg) &&
130           (TargetReg == DefReg || TRI->isSuperRegister(DefReg, TargetReg))) {
131         DEBUG(dbgs() << "Remove redundant Copy : ");
132         DEBUG((MI)->print(dbgs()));
133 
134         MI->eraseFromParent();
135         Changed = true;
136         LastChange = I;
137         NumCopiesRemoved++;
138         SmallestDef =
139             TRI->isSubRegister(SmallestDef, DefReg) ? DefReg : SmallestDef;
140         continue;
141       }
142     }
143 
144     if (MI->modifiesRegister(TargetReg, TRI))
145       break;
146   }
147 
148   if (!Changed)
149     return false;
150 
151   // Otherwise, we have to fixup the use-def chain, starting with the
152   // CBZ/CBNZ. Conservatively mark as much as we can live.
153   CompBr->clearRegisterKills(SmallestDef, TRI);
154 
155   if (none_of(TargetRegs, [&](unsigned Reg) { return MBB->isLiveIn(Reg); }))
156     MBB->addLiveIn(TargetReg);
157 
158   // Clear any kills of TargetReg between CompBr and the last removed COPY.
159   for (MachineInstr &MMI : make_range(MBB->begin(), LastChange))
160     MMI.clearRegisterKills(SmallestDef, TRI);
161 
162   return true;
163 }
164 
165 bool AArch64RedundantCopyElimination::runOnMachineFunction(
166     MachineFunction &MF) {
167   if (skipFunction(*MF.getFunction()))
168     return false;
169   TRI = MF.getSubtarget().getRegisterInfo();
170   MRI = &MF.getRegInfo();
171   bool Changed = false;
172   for (MachineBasicBlock &MBB : MF)
173     Changed |= optimizeCopy(&MBB);
174   return Changed;
175 }
176 
177 FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() {
178   return new AArch64RedundantCopyElimination();
179 }
180