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