contrib/llvm/lib/Target/AArch64/AArch64RedundantCopyElimination.cpp

   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 }