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; 53 AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {} 54 bool optimizeCopy(MachineBasicBlock *MBB); 55 bool runOnMachineFunction(MachineFunction &MF) override; 56 MachineFunctionProperties getRequiredProperties() const override { 57 return MachineFunctionProperties().set( 58 MachineFunctionProperties::Property::AllVRegsAllocated); 59 } 60 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 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 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 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 180 FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() { 181 return new AArch64RedundantCopyElimination(); 182 } 183