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 copies/moves in BBs based on a dominating
9 // condition.
10 //
11 // We handle three cases:
12 // 1. For BBs that are targets of CBZ/CBNZ instructions, we know the value of
13 // the CBZ/CBNZ source register is zero on the taken/not-taken path. For
14 // instance, the copy instruction in the code below can be removed because
15 // the CBZW jumps to %bb.2 when w0 is zero.
16 //
17 // %bb.1:
18 // cbz w0, .LBB0_2
19 // .LBB0_2:
20 // mov w0, wzr ; <-- redundant
21 //
22 // 2. If the flag setting instruction defines a register other than WZR/XZR, we
23 // can remove a zero copy in some cases.
24 //
25 // %bb.0:
26 // subs w0, w1, w2
27 // str w0, [x1]
28 // b.ne .LBB0_2
29 // %bb.1:
30 // mov w0, wzr ; <-- redundant
31 // str w0, [x2]
32 // .LBB0_2
33 //
34 // 3. Finally, if the flag setting instruction is a comparison against a
35 // constant (i.e., ADDS[W|X]ri, SUBS[W|X]ri), we can remove a mov immediate
36 // in some cases.
37 //
38 // %bb.0:
39 // subs xzr, x0, #1
40 // b.eq .LBB0_1
41 // .LBB0_1:
42 // orr x0, xzr, #0x1 ; <-- redundant
43 //
44 // This pass should be run after register allocation.
45 //
46 // FIXME: This could also be extended to check the whole dominance subtree below
47 // the comparison if the compile time regression is acceptable.
48 //
49 // FIXME: Add support for handling CCMP instructions.
50 // FIXME: If the known register value is zero, we should be able to rewrite uses
51 // to use WZR/XZR directly in some cases.
52 //===----------------------------------------------------------------------===//
53 #include "AArch64.h"
54 #include "llvm/ADT/Optional.h"
55 #include "llvm/ADT/SetVector.h"
56 #include "llvm/ADT/Statistic.h"
57 #include "llvm/ADT/iterator_range.h"
58 #include "llvm/CodeGen/LiveRegUnits.h"
59 #include "llvm/CodeGen/MachineFunctionPass.h"
60 #include "llvm/CodeGen/MachineRegisterInfo.h"
61 #include "llvm/Support/Debug.h"
62
63 using namespace llvm;
64
65 #define DEBUG_TYPE "aarch64-copyelim"
66
67 STATISTIC(NumCopiesRemoved, "Number of copies removed.");
68
69 namespace {
70 class AArch64RedundantCopyElimination : public MachineFunctionPass {
71 const MachineRegisterInfo *MRI;
72 const TargetRegisterInfo *TRI;
73
74 // DomBBClobberedRegs is used when computing known values in the dominating
75 // BB.
76 LiveRegUnits DomBBClobberedRegs, DomBBUsedRegs;
77
78 // OptBBClobberedRegs is used when optimizing away redundant copies/moves.
79 LiveRegUnits OptBBClobberedRegs, OptBBUsedRegs;
80
81 public:
82 static char ID;
AArch64RedundantCopyElimination()83 AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {
84 initializeAArch64RedundantCopyEliminationPass(
85 *PassRegistry::getPassRegistry());
86 }
87
88 struct RegImm {
89 MCPhysReg Reg;
90 int32_t Imm;
RegImm__anon1dc97ae40111::AArch64RedundantCopyElimination::RegImm91 RegImm(MCPhysReg Reg, int32_t Imm) : Reg(Reg), Imm(Imm) {}
92 };
93
94 bool knownRegValInBlock(MachineInstr &CondBr, MachineBasicBlock *MBB,
95 SmallVectorImpl<RegImm> &KnownRegs,
96 MachineBasicBlock::iterator &FirstUse);
97 bool optimizeBlock(MachineBasicBlock *MBB);
98 bool runOnMachineFunction(MachineFunction &MF) override;
getRequiredProperties() const99 MachineFunctionProperties getRequiredProperties() const override {
100 return MachineFunctionProperties().set(
101 MachineFunctionProperties::Property::NoVRegs);
102 }
getPassName() const103 StringRef getPassName() const override {
104 return "AArch64 Redundant Copy Elimination";
105 }
106 };
107 char AArch64RedundantCopyElimination::ID = 0;
108 }
109
110 INITIALIZE_PASS(AArch64RedundantCopyElimination, "aarch64-copyelim",
111 "AArch64 redundant copy elimination pass", false, false)
112
113 /// It's possible to determine the value of a register based on a dominating
114 /// condition. To do so, this function checks to see if the basic block \p MBB
115 /// is the target of a conditional branch \p CondBr with an equality comparison.
116 /// If the branch is a CBZ/CBNZ, we know the value of its source operand is zero
117 /// in \p MBB for some cases. Otherwise, we find and inspect the NZCV setting
118 /// instruction (e.g., SUBS, ADDS). If this instruction defines a register
119 /// other than WZR/XZR, we know the value of the destination register is zero in
120 /// \p MMB for some cases. In addition, if the NZCV setting instruction is
121 /// comparing against a constant we know the other source register is equal to
122 /// the constant in \p MBB for some cases. If we find any constant values, push
123 /// a physical register and constant value pair onto the KnownRegs vector and
124 /// return true. Otherwise, return false if no known values were found.
knownRegValInBlock(MachineInstr & CondBr,MachineBasicBlock * MBB,SmallVectorImpl<RegImm> & KnownRegs,MachineBasicBlock::iterator & FirstUse)125 bool AArch64RedundantCopyElimination::knownRegValInBlock(
126 MachineInstr &CondBr, MachineBasicBlock *MBB,
127 SmallVectorImpl<RegImm> &KnownRegs, MachineBasicBlock::iterator &FirstUse) {
128 unsigned Opc = CondBr.getOpcode();
129
130 // Check if the current basic block is the target block to which the
131 // CBZ/CBNZ instruction jumps when its Wt/Xt is zero.
132 if (((Opc == AArch64::CBZW || Opc == AArch64::CBZX) &&
133 MBB == CondBr.getOperand(1).getMBB()) ||
134 ((Opc == AArch64::CBNZW || Opc == AArch64::CBNZX) &&
135 MBB != CondBr.getOperand(1).getMBB())) {
136 FirstUse = CondBr;
137 KnownRegs.push_back(RegImm(CondBr.getOperand(0).getReg(), 0));
138 return true;
139 }
140
141 // Otherwise, must be a conditional branch.
142 if (Opc != AArch64::Bcc)
143 return false;
144
145 // Must be an equality check (i.e., == or !=).
146 AArch64CC::CondCode CC = (AArch64CC::CondCode)CondBr.getOperand(0).getImm();
147 if (CC != AArch64CC::EQ && CC != AArch64CC::NE)
148 return false;
149
150 MachineBasicBlock *BrTarget = CondBr.getOperand(1).getMBB();
151 if ((CC == AArch64CC::EQ && BrTarget != MBB) ||
152 (CC == AArch64CC::NE && BrTarget == MBB))
153 return false;
154
155 // Stop if we get to the beginning of PredMBB.
156 MachineBasicBlock *PredMBB = *MBB->pred_begin();
157 assert(PredMBB == CondBr.getParent() &&
158 "Conditional branch not in predecessor block!");
159 if (CondBr == PredMBB->begin())
160 return false;
161
162 // Registers clobbered in PredMBB between CondBr instruction and current
163 // instruction being checked in loop.
164 DomBBClobberedRegs.clear();
165 DomBBUsedRegs.clear();
166
167 // Find compare instruction that sets NZCV used by CondBr.
168 MachineBasicBlock::reverse_iterator RIt = CondBr.getReverseIterator();
169 for (MachineInstr &PredI : make_range(std::next(RIt), PredMBB->rend())) {
170
171 bool IsCMN = false;
172 switch (PredI.getOpcode()) {
173 default:
174 break;
175
176 // CMN is an alias for ADDS with a dead destination register.
177 case AArch64::ADDSWri:
178 case AArch64::ADDSXri:
179 IsCMN = true;
180 LLVM_FALLTHROUGH;
181 // CMP is an alias for SUBS with a dead destination register.
182 case AArch64::SUBSWri:
183 case AArch64::SUBSXri: {
184 // Sometimes the first operand is a FrameIndex. Bail if tht happens.
185 if (!PredI.getOperand(1).isReg())
186 return false;
187 MCPhysReg DstReg = PredI.getOperand(0).getReg();
188 MCPhysReg SrcReg = PredI.getOperand(1).getReg();
189
190 bool Res = false;
191 // If we're comparing against a non-symbolic immediate and the source
192 // register of the compare is not modified (including a self-clobbering
193 // compare) between the compare and conditional branch we known the value
194 // of the 1st source operand.
195 if (PredI.getOperand(2).isImm() && DomBBClobberedRegs.available(SrcReg) &&
196 SrcReg != DstReg) {
197 // We've found the instruction that sets NZCV.
198 int32_t KnownImm = PredI.getOperand(2).getImm();
199 int32_t Shift = PredI.getOperand(3).getImm();
200 KnownImm <<= Shift;
201 if (IsCMN)
202 KnownImm = -KnownImm;
203 FirstUse = PredI;
204 KnownRegs.push_back(RegImm(SrcReg, KnownImm));
205 Res = true;
206 }
207
208 // If this instructions defines something other than WZR/XZR, we know it's
209 // result is zero in some cases.
210 if (DstReg == AArch64::WZR || DstReg == AArch64::XZR)
211 return Res;
212
213 // The destination register must not be modified between the NZCV setting
214 // instruction and the conditional branch.
215 if (!DomBBClobberedRegs.available(DstReg))
216 return Res;
217
218 FirstUse = PredI;
219 KnownRegs.push_back(RegImm(DstReg, 0));
220 return true;
221 }
222
223 // Look for NZCV setting instructions that define something other than
224 // WZR/XZR.
225 case AArch64::ADCSWr:
226 case AArch64::ADCSXr:
227 case AArch64::ADDSWrr:
228 case AArch64::ADDSWrs:
229 case AArch64::ADDSWrx:
230 case AArch64::ADDSXrr:
231 case AArch64::ADDSXrs:
232 case AArch64::ADDSXrx:
233 case AArch64::ADDSXrx64:
234 case AArch64::ANDSWri:
235 case AArch64::ANDSWrr:
236 case AArch64::ANDSWrs:
237 case AArch64::ANDSXri:
238 case AArch64::ANDSXrr:
239 case AArch64::ANDSXrs:
240 case AArch64::BICSWrr:
241 case AArch64::BICSWrs:
242 case AArch64::BICSXrs:
243 case AArch64::BICSXrr:
244 case AArch64::SBCSWr:
245 case AArch64::SBCSXr:
246 case AArch64::SUBSWrr:
247 case AArch64::SUBSWrs:
248 case AArch64::SUBSWrx:
249 case AArch64::SUBSXrr:
250 case AArch64::SUBSXrs:
251 case AArch64::SUBSXrx:
252 case AArch64::SUBSXrx64: {
253 MCPhysReg DstReg = PredI.getOperand(0).getReg();
254 if (DstReg == AArch64::WZR || DstReg == AArch64::XZR)
255 return false;
256
257 // The destination register of the NZCV setting instruction must not be
258 // modified before the conditional branch.
259 if (!DomBBClobberedRegs.available(DstReg))
260 return false;
261
262 // We've found the instruction that sets NZCV whose DstReg == 0.
263 FirstUse = PredI;
264 KnownRegs.push_back(RegImm(DstReg, 0));
265 return true;
266 }
267 }
268
269 // Bail if we see an instruction that defines NZCV that we don't handle.
270 if (PredI.definesRegister(AArch64::NZCV))
271 return false;
272
273 // Track clobbered and used registers.
274 LiveRegUnits::accumulateUsedDefed(PredI, DomBBClobberedRegs, DomBBUsedRegs,
275 TRI);
276 }
277 return false;
278 }
279
optimizeBlock(MachineBasicBlock * MBB)280 bool AArch64RedundantCopyElimination::optimizeBlock(MachineBasicBlock *MBB) {
281 // Check if the current basic block has a single predecessor.
282 if (MBB->pred_size() != 1)
283 return false;
284
285 // Check if the predecessor has two successors, implying the block ends in a
286 // conditional branch.
287 MachineBasicBlock *PredMBB = *MBB->pred_begin();
288 if (PredMBB->succ_size() != 2)
289 return false;
290
291 MachineBasicBlock::iterator CondBr = PredMBB->getLastNonDebugInstr();
292 if (CondBr == PredMBB->end())
293 return false;
294
295 // Keep track of the earliest point in the PredMBB block where kill markers
296 // need to be removed if a COPY is removed.
297 MachineBasicBlock::iterator FirstUse;
298 // After calling knownRegValInBlock, FirstUse will either point to a CBZ/CBNZ
299 // or a compare (i.e., SUBS). In the latter case, we must take care when
300 // updating FirstUse when scanning for COPY instructions. In particular, if
301 // there's a COPY in between the compare and branch the COPY should not
302 // update FirstUse.
303 bool SeenFirstUse = false;
304 // Registers that contain a known value at the start of MBB.
305 SmallVector<RegImm, 4> KnownRegs;
306
307 MachineBasicBlock::iterator Itr = std::next(CondBr);
308 do {
309 --Itr;
310
311 if (!knownRegValInBlock(*Itr, MBB, KnownRegs, FirstUse))
312 continue;
313
314 // Reset the clobbered and used register units.
315 OptBBClobberedRegs.clear();
316 OptBBUsedRegs.clear();
317
318 // Look backward in PredMBB for COPYs from the known reg to find other
319 // registers that are known to be a constant value.
320 for (auto PredI = Itr;; --PredI) {
321 if (FirstUse == PredI)
322 SeenFirstUse = true;
323
324 if (PredI->isCopy()) {
325 MCPhysReg CopyDstReg = PredI->getOperand(0).getReg();
326 MCPhysReg CopySrcReg = PredI->getOperand(1).getReg();
327 for (auto &KnownReg : KnownRegs) {
328 if (!OptBBClobberedRegs.available(KnownReg.Reg))
329 continue;
330 // If we have X = COPY Y, and Y is known to be zero, then now X is
331 // known to be zero.
332 if (CopySrcReg == KnownReg.Reg &&
333 OptBBClobberedRegs.available(CopyDstReg)) {
334 KnownRegs.push_back(RegImm(CopyDstReg, KnownReg.Imm));
335 if (SeenFirstUse)
336 FirstUse = PredI;
337 break;
338 }
339 // If we have X = COPY Y, and X is known to be zero, then now Y is
340 // known to be zero.
341 if (CopyDstReg == KnownReg.Reg &&
342 OptBBClobberedRegs.available(CopySrcReg)) {
343 KnownRegs.push_back(RegImm(CopySrcReg, KnownReg.Imm));
344 if (SeenFirstUse)
345 FirstUse = PredI;
346 break;
347 }
348 }
349 }
350
351 // Stop if we get to the beginning of PredMBB.
352 if (PredI == PredMBB->begin())
353 break;
354
355 LiveRegUnits::accumulateUsedDefed(*PredI, OptBBClobberedRegs,
356 OptBBUsedRegs, TRI);
357 // Stop if all of the known-zero regs have been clobbered.
358 if (all_of(KnownRegs, [&](RegImm KnownReg) {
359 return !OptBBClobberedRegs.available(KnownReg.Reg);
360 }))
361 break;
362 }
363 break;
364
365 } while (Itr != PredMBB->begin() && Itr->isTerminator());
366
367 // We've not found a registers with a known value, time to bail out.
368 if (KnownRegs.empty())
369 return false;
370
371 bool Changed = false;
372 // UsedKnownRegs is the set of KnownRegs that have had uses added to MBB.
373 SmallSetVector<unsigned, 4> UsedKnownRegs;
374 MachineBasicBlock::iterator LastChange = MBB->begin();
375 // Remove redundant copy/move instructions unless KnownReg is modified.
376 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
377 MachineInstr *MI = &*I;
378 ++I;
379 bool RemovedMI = false;
380 bool IsCopy = MI->isCopy();
381 bool IsMoveImm = MI->isMoveImmediate();
382 if (IsCopy || IsMoveImm) {
383 MCPhysReg DefReg = MI->getOperand(0).getReg();
384 MCPhysReg SrcReg = IsCopy ? MI->getOperand(1).getReg() : 0;
385 int64_t SrcImm = IsMoveImm ? MI->getOperand(1).getImm() : 0;
386 if (!MRI->isReserved(DefReg) &&
387 ((IsCopy && (SrcReg == AArch64::XZR || SrcReg == AArch64::WZR)) ||
388 IsMoveImm)) {
389 for (RegImm &KnownReg : KnownRegs) {
390 if (KnownReg.Reg != DefReg &&
391 !TRI->isSuperRegister(DefReg, KnownReg.Reg))
392 continue;
393
394 // For a copy, the known value must be a zero.
395 if (IsCopy && KnownReg.Imm != 0)
396 continue;
397
398 if (IsMoveImm) {
399 // For a move immediate, the known immediate must match the source
400 // immediate.
401 if (KnownReg.Imm != SrcImm)
402 continue;
403
404 // Don't remove a move immediate that implicitly defines the upper
405 // bits when only the lower 32 bits are known.
406 MCPhysReg CmpReg = KnownReg.Reg;
407 if (any_of(MI->implicit_operands(), [CmpReg](MachineOperand &O) {
408 return !O.isDead() && O.isReg() && O.isDef() &&
409 O.getReg() != CmpReg;
410 }))
411 continue;
412 }
413
414 if (IsCopy)
415 LLVM_DEBUG(dbgs() << "Remove redundant Copy : " << *MI);
416 else
417 LLVM_DEBUG(dbgs() << "Remove redundant Move : " << *MI);
418
419 MI->eraseFromParent();
420 Changed = true;
421 LastChange = I;
422 NumCopiesRemoved++;
423 UsedKnownRegs.insert(KnownReg.Reg);
424 RemovedMI = true;
425 break;
426 }
427 }
428 }
429
430 // Skip to the next instruction if we removed the COPY/MovImm.
431 if (RemovedMI)
432 continue;
433
434 // Remove any regs the MI clobbers from the KnownConstRegs set.
435 for (unsigned RI = 0; RI < KnownRegs.size();)
436 if (MI->modifiesRegister(KnownRegs[RI].Reg, TRI)) {
437 std::swap(KnownRegs[RI], KnownRegs[KnownRegs.size() - 1]);
438 KnownRegs.pop_back();
439 // Don't increment RI since we need to now check the swapped-in
440 // KnownRegs[RI].
441 } else {
442 ++RI;
443 }
444
445 // Continue until the KnownRegs set is empty.
446 if (KnownRegs.empty())
447 break;
448 }
449
450 if (!Changed)
451 return false;
452
453 // Add newly used regs to the block's live-in list if they aren't there
454 // already.
455 for (MCPhysReg KnownReg : UsedKnownRegs)
456 if (!MBB->isLiveIn(KnownReg))
457 MBB->addLiveIn(KnownReg);
458
459 // Clear kills in the range where changes were made. This is conservative,
460 // but should be okay since kill markers are being phased out.
461 LLVM_DEBUG(dbgs() << "Clearing kill flags.\n\tFirstUse: " << *FirstUse
462 << "\tLastChange: " << *LastChange);
463 for (MachineInstr &MMI : make_range(FirstUse, PredMBB->end()))
464 MMI.clearKillInfo();
465 for (MachineInstr &MMI : make_range(MBB->begin(), LastChange))
466 MMI.clearKillInfo();
467
468 return true;
469 }
470
runOnMachineFunction(MachineFunction & MF)471 bool AArch64RedundantCopyElimination::runOnMachineFunction(
472 MachineFunction &MF) {
473 if (skipFunction(MF.getFunction()))
474 return false;
475 TRI = MF.getSubtarget().getRegisterInfo();
476 MRI = &MF.getRegInfo();
477
478 // Resize the clobbered and used register unit trackers. We do this once per
479 // function.
480 DomBBClobberedRegs.init(*TRI);
481 DomBBUsedRegs.init(*TRI);
482 OptBBClobberedRegs.init(*TRI);
483 OptBBUsedRegs.init(*TRI);
484
485 bool Changed = false;
486 for (MachineBasicBlock &MBB : MF)
487 Changed |= optimizeBlock(&MBB);
488 return Changed;
489 }
490
createAArch64RedundantCopyEliminationPass()491 FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() {
492 return new AArch64RedundantCopyElimination();
493 }
494