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