Line data Source code
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;
83 1122 : AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {
84 1122 : initializeAArch64RedundantCopyEliminationPass(
85 1122 : *PassRegistry::getPassRegistry());
86 1122 : }
87 :
88 : struct RegImm {
89 : MCPhysReg Reg;
90 : int32_t Imm;
91 387 : 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;
99 1107 : MachineFunctionProperties getRequiredProperties() const override {
100 1107 : return MachineFunctionProperties().set(
101 1107 : MachineFunctionProperties::Property::NoVRegs);
102 : }
103 1114 : StringRef getPassName() const override {
104 1114 : return "AArch64 Redundant Copy Elimination";
105 : }
106 : };
107 : char AArch64RedundantCopyElimination::ID = 0;
108 : }
109 :
110 200154 : 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.
125 3340 : bool AArch64RedundantCopyElimination::knownRegValInBlock(
126 : MachineInstr &CondBr, MachineBasicBlock *MBB,
127 : SmallVectorImpl<RegImm> &KnownRegs, MachineBasicBlock::iterator &FirstUse) {
128 3340 : 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 3453 : if (((Opc == AArch64::CBZW || Opc == AArch64::CBZX) &&
133 3340 : MBB == CondBr.getOperand(1).getMBB()) ||
134 3294 : ((Opc == AArch64::CBNZW || Opc == AArch64::CBNZX) &&
135 241 : MBB != CondBr.getOperand(1).getMBB())) {
136 232 : FirstUse = CondBr;
137 232 : KnownRegs.push_back(RegImm(CondBr.getOperand(0).getReg(), 0));
138 232 : return true;
139 : }
140 :
141 : // Otherwise, must be a conditional branch.
142 3108 : if (Opc != AArch64::Bcc)
143 : return false;
144 :
145 : // Must be an equality check (i.e., == or !=).
146 803 : AArch64CC::CondCode CC = (AArch64CC::CondCode)CondBr.getOperand(0).getImm();
147 803 : if (CC != AArch64CC::EQ && CC != AArch64CC::NE)
148 : return false;
149 :
150 392 : MachineBasicBlock *BrTarget = CondBr.getOperand(1).getMBB();
151 392 : if ((CC == AArch64CC::EQ && BrTarget != MBB) ||
152 298 : (CC == AArch64CC::NE && BrTarget == MBB))
153 : return false;
154 :
155 : // Stop if we get to the beginning of PredMBB.
156 245 : MachineBasicBlock *PredMBB = *MBB->pred_begin();
157 : assert(PredMBB == CondBr.getParent() &&
158 : "Conditional branch not in predecessor block!");
159 245 : 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 245 : MachineBasicBlock::reverse_iterator RIt = CondBr.getReverseIterator();
169 388 : for (MachineInstr &PredI : make_range(std::next(RIt), PredMBB->rend())) {
170 :
171 : bool IsCMN = false;
172 776 : 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 110 : case AArch64::SUBSWri:
183 : case AArch64::SUBSXri: {
184 : // Sometimes the first operand is a FrameIndex. Bail if tht happens.
185 220 : if (!PredI.getOperand(1).isReg())
186 : return false;
187 109 : MCPhysReg DstReg = PredI.getOperand(0).getReg();
188 109 : 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 109 : if (PredI.getOperand(2).isImm() && DomBBClobberedRegs.available(SrcReg) &&
196 : SrcReg != DstReg) {
197 : // We've found the instruction that sets NZCV.
198 62 : int32_t KnownImm = PredI.getOperand(2).getImm();
199 62 : int32_t Shift = PredI.getOperand(3).getImm();
200 62 : KnownImm <<= Shift;
201 62 : if (IsCMN)
202 5 : KnownImm = -KnownImm;
203 62 : FirstUse = PredI;
204 62 : 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 109 : 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 48 : if (!DomBBClobberedRegs.available(DstReg))
216 : return Res;
217 :
218 48 : FirstUse = PredI;
219 48 : KnownRegs.push_back(RegImm(DstReg, 0));
220 48 : return true;
221 : }
222 :
223 : // Look for NZCV setting instructions that define something other than
224 : // WZR/XZR.
225 113 : 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 113 : MCPhysReg DstReg = PredI.getOperand(0).getReg();
254 113 : 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 18 : if (!DomBBClobberedRegs.available(DstReg))
260 : return false;
261 :
262 : // We've found the instruction that sets NZCV whose DstReg == 0.
263 16 : FirstUse = PredI;
264 16 : KnownRegs.push_back(RegImm(DstReg, 0));
265 16 : return true;
266 : }
267 : }
268 :
269 : // Bail if we see an instruction that defines NZCV that we don't handle.
270 165 : if (PredI.definesRegister(AArch64::NZCV))
271 : return false;
272 :
273 : // Track clobbered and used registers.
274 143 : LiveRegUnits::accumulateUsedDefed(PredI, DomBBClobberedRegs, DomBBUsedRegs,
275 : TRI);
276 : }
277 : return false;
278 : }
279 :
280 16511 : bool AArch64RedundantCopyElimination::optimizeBlock(MachineBasicBlock *MBB) {
281 : // Check if the current basic block has a single predecessor.
282 16511 : 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 1688 : MachineBasicBlock *PredMBB = *MBB->pred_begin();
288 1688 : if (PredMBB->succ_size() != 2)
289 : return false;
290 :
291 1442 : MachineBasicBlock::iterator CondBr = PredMBB->getLastNonDebugInstr();
292 1442 : 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 1442 : SmallVector<RegImm, 4> KnownRegs;
306 :
307 1442 : MachineBasicBlock::iterator Itr = std::next(CondBr);
308 : do {
309 : --Itr;
310 :
311 3340 : 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 356 : for (auto PredI = Itr;; --PredI) {
321 856 : if (FirstUse == PredI)
322 : SeenFirstUse = true;
323 :
324 856 : if (PredI->isCopy()) {
325 36 : MCPhysReg CopyDstReg = PredI->getOperand(0).getReg();
326 36 : MCPhysReg CopySrcReg = PredI->getOperand(1).getReg();
327 45 : for (auto &KnownReg : KnownRegs) {
328 38 : 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 45 : if (CopySrcReg == KnownReg.Reg &&
333 9 : OptBBClobberedRegs.available(CopyDstReg)) {
334 8 : KnownRegs.push_back(RegImm(CopyDstReg, KnownReg.Imm));
335 8 : if (SeenFirstUse)
336 7 : 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 51 : if (CopyDstReg == KnownReg.Reg &&
342 23 : OptBBClobberedRegs.available(CopySrcReg)) {
343 21 : KnownRegs.push_back(RegImm(CopySrcReg, KnownReg.Imm));
344 21 : if (SeenFirstUse)
345 21 : FirstUse = PredI;
346 : break;
347 : }
348 : }
349 : }
350 :
351 : // Stop if we get to the beginning of PredMBB.
352 856 : if (PredI == PredMBB->begin())
353 : break;
354 :
355 1336 : LiveRegUnits::accumulateUsedDefed(*PredI, OptBBClobberedRegs,
356 668 : OptBBUsedRegs, TRI);
357 : // Stop if all of the known-zero regs have been clobbered.
358 668 : if (all_of(KnownRegs, [&](RegImm KnownReg) {
359 0 : return !OptBBClobberedRegs.available(KnownReg.Reg);
360 : }))
361 : break;
362 : }
363 356 : break;
364 :
365 5335 : } while (Itr != PredMBB->begin() && Itr->isTerminator());
366 :
367 : // We've not found a registers with a known value, time to bail out.
368 1442 : 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 973 : 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 698 : if (IsCopy || IsMoveImm) {
383 219 : MCPhysReg DefReg = MI->getOperand(0).getReg();
384 219 : MCPhysReg SrcReg = IsCopy ? MI->getOperand(1).getReg() : 0;
385 219 : int64_t SrcImm = IsMoveImm ? MI->getOperand(1).getImm() : 0;
386 438 : if (!MRI->isReserved(DefReg) &&
387 215 : ((IsCopy && (SrcReg == AArch64::XZR || SrcReg == AArch64::WZR)) ||
388 : IsMoveImm)) {
389 200 : for (RegImm &KnownReg : KnownRegs) {
390 205 : if (KnownReg.Reg != DefReg &&
391 74 : !TRI->isSuperRegister(DefReg, KnownReg.Reg))
392 : continue;
393 :
394 : // For a copy, the known value must be a zero.
395 66 : if (IsCopy && KnownReg.Imm != 0)
396 : continue;
397 :
398 60 : if (IsMoveImm) {
399 : // For a move immediate, the known immediate must match the source
400 : // immediate.
401 29 : 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 13 : MCPhysReg CmpReg = KnownReg.Reg;
407 13 : if (any_of(MI->implicit_operands(), [CmpReg](MachineOperand &O) {
408 0 : return !O.isDead() && O.isReg() && O.isDef() &&
409 0 : 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 43 : MI->eraseFromParent();
420 : Changed = true;
421 : LastChange = I;
422 : NumCopiesRemoved++;
423 43 : 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 43 : continue;
433 :
434 : // Remove any regs the MI clobbers from the KnownConstRegs set.
435 1360 : for (unsigned RI = 0; RI < KnownRegs.size();)
436 1410 : if (MI->modifiesRegister(KnownRegs[RI].Reg, TRI)) {
437 178 : 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 616 : ++RI;
443 : }
444 :
445 : // Continue until the KnownRegs set is empty.
446 655 : if (KnownRegs.empty())
447 : break;
448 : }
449 :
450 356 : 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 85 : for (MCPhysReg KnownReg : UsedKnownRegs)
456 43 : 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 173 : for (MachineInstr &MMI : make_range(FirstUse, PredMBB->end()))
464 131 : MMI.clearKillInfo();
465 46 : for (MachineInstr &MMI : make_range(MBB->begin(), LastChange))
466 4 : MMI.clearKillInfo();
467 :
468 : return true;
469 : }
470 :
471 14132 : bool AArch64RedundantCopyElimination::runOnMachineFunction(
472 : MachineFunction &MF) {
473 14132 : if (skipFunction(MF.getFunction()))
474 : return false;
475 14126 : TRI = MF.getSubtarget().getRegisterInfo();
476 14126 : MRI = &MF.getRegInfo();
477 :
478 : // Resize the clobbered and used register unit trackers. We do this once per
479 : // function.
480 14126 : DomBBClobberedRegs.init(*TRI);
481 14126 : DomBBUsedRegs.init(*TRI);
482 14126 : OptBBClobberedRegs.init(*TRI);
483 14126 : OptBBUsedRegs.init(*TRI);
484 :
485 : bool Changed = false;
486 30637 : for (MachineBasicBlock &MBB : MF)
487 16511 : Changed |= optimizeBlock(&MBB);
488 : return Changed;
489 : }
490 :
491 1120 : FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() {
492 1120 : return new AArch64RedundantCopyElimination();
493 : }
|
