Home | History | Annotate | Download | only in AArch64 
      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