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 // Similarly, this pass also handles non-zero copies.
  16 //  BB#0:
  17 //    cmp x0, #1
  18 //    b.eq .LBB0_1
  19 //  .LBB0_1:
  20 //    orr x0, xzr, #0x1
  21 //
  22 // This pass should be run after register allocation.
  23 //
  24 // FIXME: This could also be extended to check the whole dominance subtree below
  25 // the comparison if the compile time regression is acceptable.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "AArch64.h"
  30 #include "llvm/ADT/Optional.h"
  31 #include "llvm/ADT/SetVector.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/ADT/iterator_range.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/Support/Debug.h"
  37
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "aarch64-copyelim"
  41
  42 STATISTIC(NumCopiesRemoved, "Number of copies removed.");
  43
  44 namespace {
  45 class AArch64RedundantCopyElimination : public MachineFunctionPass {
  46   const MachineRegisterInfo *MRI;
  47   const TargetRegisterInfo *TRI;
  48   BitVector ClobberedRegs;
  49
  50 public:
  51   static char ID;
  52   AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {
  53     initializeAArch64RedundantCopyEliminationPass(
  54         *PassRegistry::getPassRegistry());
  55   }
  56
  57   struct RegImm {
  58     MCPhysReg Reg;
  59     int32_t Imm;
  60     RegImm(MCPhysReg Reg, int32_t Imm) : Reg(Reg), Imm(Imm) {}
  61   };
  62
  63   Optional<RegImm> knownRegValInBlock(MachineInstr &CondBr,
  64                                       MachineBasicBlock *MBB,
  65                                       MachineBasicBlock::iterator &FirstUse);
  66   bool optimizeCopy(MachineBasicBlock *MBB);
  67   bool runOnMachineFunction(MachineFunction &MF) override;
  68   MachineFunctionProperties getRequiredProperties() const override {
  69     return MachineFunctionProperties().set(
  70         MachineFunctionProperties::Property::NoVRegs);
  71   }
  72   StringRef getPassName() const override {
  73     return "AArch64 Redundant Copy Elimination";
  74   }
  75 };
  76 char AArch64RedundantCopyElimination::ID = 0;
  77 }
  78
  79 INITIALIZE_PASS(AArch64RedundantCopyElimination, "aarch64-copyelim",
  80                 "AArch64 redundant copy elimination pass", false, false)
  81
  82 /// Remember what registers the specified instruction modifies.
  83 static void trackRegDefs(const MachineInstr &MI, BitVector &ClobberedRegs,
  84                          const TargetRegisterInfo *TRI) {
  85   for (const MachineOperand &MO : MI.operands()) {
  86     if (MO.isRegMask()) {
  87       ClobberedRegs.setBitsNotInMask(MO.getRegMask());
  88       continue;
  89     }
  90
  91     if (!MO.isReg())
  92       continue;
  93     unsigned Reg = MO.getReg();
  94     if (!Reg)
  95       continue;
  96     if (!MO.isDef())
  97       continue;
  98
  99     for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 100       ClobberedRegs.set(*AI);
 101   }
 102 }
 103
 104 /// It's possible to determine the value of a register based on a dominating
 105 /// condition.  To do so, this function checks to see if the basic block \p MBB
 106 /// is the target to which a conditional branch \p CondBr jumps and whose
 107 /// equality comparison is against a constant.  If so, return a known physical
 108 /// register and constant value pair.  Otherwise, return None.
 109 Optional<AArch64RedundantCopyElimination::RegImm>
 110 AArch64RedundantCopyElimination::knownRegValInBlock(
 111     MachineInstr &CondBr, MachineBasicBlock *MBB,
 112     MachineBasicBlock::iterator &FirstUse) {
 113   unsigned Opc = CondBr.getOpcode();
 114
 115   // Check if the current basic block is the target block to which the
 116   // CBZ/CBNZ instruction jumps when its Wt/Xt is zero.
 117   if (((Opc == AArch64::CBZW || Opc == AArch64::CBZX) &&
 118        MBB == CondBr.getOperand(1).getMBB()) ||
 119       ((Opc == AArch64::CBNZW || Opc == AArch64::CBNZX) &&
 120        MBB != CondBr.getOperand(1).getMBB())) {
 121     FirstUse = CondBr;
 122     return RegImm(CondBr.getOperand(0).getReg(), 0);
 123   }
 124
 125   // Otherwise, must be a conditional branch.
 126   if (Opc != AArch64::Bcc)
 127     return None;
 128
 129   // Must be an equality check (i.e., == or !=).
 130   AArch64CC::CondCode CC = (AArch64CC::CondCode)CondBr.getOperand(0).getImm();
 131   if (CC != AArch64CC::EQ && CC != AArch64CC::NE)
 132     return None;
 133
 134   MachineBasicBlock *BrTarget = CondBr.getOperand(1).getMBB();
 135   if ((CC == AArch64CC::EQ && BrTarget != MBB) ||
 136       (CC == AArch64CC::NE && BrTarget == MBB))
 137     return None;
 138
 139   // Stop if we get to the beginning of PredMBB.
 140   MachineBasicBlock *PredMBB = *MBB->pred_begin();
 141   assert(PredMBB == CondBr.getParent() &&
 142          "Conditional branch not in predecessor block!");
 143   if (CondBr == PredMBB->begin())
 144     return None;
 145
 146   // Registers clobbered in PredMBB between CondBr instruction and current
 147   // instruction being checked in loop.
 148   ClobberedRegs.reset();
 149
 150   // Find compare instruction that sets NZCV used by CondBr.
 151   MachineBasicBlock::reverse_iterator RIt = CondBr.getReverseIterator();
 152   for (MachineInstr &PredI : make_range(std::next(RIt), PredMBB->rend())) {
 153
 154     // Track clobbered registers.
 155     trackRegDefs(PredI, ClobberedRegs, TRI);
 156
 157     bool IsCMN = false;
 158     switch (PredI.getOpcode()) {
 159     default:
 160       break;
 161
 162     // CMN is an alias for ADDS with a dead destination register.
 163     case AArch64::ADDSWri:
 164     case AArch64::ADDSXri:
 165       IsCMN = true;
 166       LLVM_FALLTHROUGH;
 167     // CMP is an alias for SUBS with a dead destination register.
 168     case AArch64::SUBSWri:
 169     case AArch64::SUBSXri: {
 170       // Sometimes the first operand is a FrameIndex. Bail if tht happens.
 171       if (!PredI.getOperand(1).isReg())
 172         return None;
 173       MCPhysReg SrcReg = PredI.getOperand(1).getReg();
 174
 175       // Must not be a symbolic immediate.
 176       if (!PredI.getOperand(2).isImm())
 177         return None;
 178
 179       // The src register must not be modified between the cmp and conditional
 180       // branch.  This includes a self-clobbering compare.
 181       if (ClobberedRegs[SrcReg])
 182         return None;
 183
 184       // We've found the Cmp that sets NZCV.
 185       int32_t KnownImm = PredI.getOperand(2).getImm();
 186       int32_t Shift = PredI.getOperand(3).getImm();
 187       KnownImm <<= Shift;
 188       if (IsCMN)
 189         KnownImm = -KnownImm;
 190       FirstUse = PredI;
 191       return RegImm(SrcReg, KnownImm);
 192     }
 193     }
 194
 195     // Bail if we see an instruction that defines NZCV that we don't handle.
 196     if (PredI.definesRegister(AArch64::NZCV))
 197       return None;
 198   }
 199   return None;
 200 }
 201
 202 bool AArch64RedundantCopyElimination::optimizeCopy(MachineBasicBlock *MBB) {
 203   // Check if the current basic block has a single predecessor.
 204   if (MBB->pred_size() != 1)
 205     return false;
 206
 207   // Check if the predecessor has two successors, implying the block ends in a
 208   // conditional branch.
 209   MachineBasicBlock *PredMBB = *MBB->pred_begin();
 210   if (PredMBB->succ_size() != 2)
 211     return false;
 212
 213   MachineBasicBlock::iterator CondBr = PredMBB->getLastNonDebugInstr();
 214   if (CondBr == PredMBB->end())
 215     return false;
 216
 217   // Keep track of the earliest point in the PredMBB block where kill markers
 218   // need to be removed if a COPY is removed.
 219   MachineBasicBlock::iterator FirstUse;
 220   // After calling knownRegValInBlock, FirstUse will either point to a CBZ/CBNZ
 221   // or a compare (i.e., SUBS).  In the latter case, we must take care when
 222   // updating FirstUse when scanning for COPY instructions.  In particular, if
 223   // there's a COPY in between the compare and branch the COPY should not
 224   // update FirstUse.
 225   bool SeenFirstUse = false;
 226   // Registers that contain a known value at the start of MBB.
 227   SmallVector<RegImm, 4> KnownRegs;
 228
 229   MachineBasicBlock::iterator Itr = std::next(CondBr);
 230   do {
 231     --Itr;
 232
 233     Optional<RegImm> KnownRegImm = knownRegValInBlock(*Itr, MBB, FirstUse);
 234     if (KnownRegImm == None)
 235       continue;
 236
 237     KnownRegs.push_back(*KnownRegImm);
 238
 239     // Reset the clobber list, which is used by knownRegValInBlock.
 240     ClobberedRegs.reset();
 241
 242     // Look backward in PredMBB for COPYs from the known reg to find other
 243     // registers that are known to be a constant value.
 244     for (auto PredI = Itr;; --PredI) {
 245       if (FirstUse == PredI)
 246         SeenFirstUse = true;
 247
 248       if (PredI->isCopy()) {
 249         MCPhysReg CopyDstReg = PredI->getOperand(0).getReg();
 250         MCPhysReg CopySrcReg = PredI->getOperand(1).getReg();
 251         for (auto &KnownReg : KnownRegs) {
 252           if (ClobberedRegs[KnownReg.Reg])
 253             continue;
 254           // If we have X = COPY Y, and Y is known to be zero, then now X is
 255           // known to be zero.
 256           if (CopySrcReg == KnownReg.Reg && !ClobberedRegs[CopyDstReg]) {
 257             KnownRegs.push_back(RegImm(CopyDstReg, KnownReg.Imm));
 258             if (SeenFirstUse)
 259               FirstUse = PredI;
 260             break;
 261           }
 262           // If we have X = COPY Y, and X is known to be zero, then now Y is
 263           // known to be zero.
 264           if (CopyDstReg == KnownReg.Reg && !ClobberedRegs[CopySrcReg]) {
 265             KnownRegs.push_back(RegImm(CopySrcReg, KnownReg.Imm));
 266             if (SeenFirstUse)
 267               FirstUse = PredI;
 268             break;
 269           }
 270         }
 271       }
 272
 273       // Stop if we get to the beginning of PredMBB.
 274       if (PredI == PredMBB->begin())
 275         break;
 276
 277       trackRegDefs(*PredI, ClobberedRegs, TRI);
 278       // Stop if all of the known-zero regs have been clobbered.
 279       if (all_of(KnownRegs, [&](RegImm KnownReg) {
 280             return ClobberedRegs[KnownReg.Reg];
 281           }))
 282         break;
 283     }
 284     break;
 285
 286   } while (Itr != PredMBB->begin() && Itr->isTerminator());
 287
 288   // We've not found a registers with a known value, time to bail out.
 289   if (KnownRegs.empty())
 290     return false;
 291
 292   bool Changed = false;
 293   // UsedKnownRegs is the set of KnownRegs that have had uses added to MBB.
 294   SmallSetVector<unsigned, 4> UsedKnownRegs;
 295   MachineBasicBlock::iterator LastChange = MBB->begin();
 296   // Remove redundant Copy instructions unless KnownReg is modified.
 297   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
 298     MachineInstr *MI = &*I;
 299     ++I;
 300     bool RemovedMI = false;
 301     bool IsCopy = MI->isCopy();
 302     bool IsMoveImm = MI->isMoveImmediate();
 303     if (IsCopy || IsMoveImm) {
 304       MCPhysReg DefReg = MI->getOperand(0).getReg();
 305       MCPhysReg SrcReg = IsCopy ? MI->getOperand(1).getReg() : 0;
 306       int64_t SrcImm = IsMoveImm ? MI->getOperand(1).getImm() : 0;
 307       if (!MRI->isReserved(DefReg) &&
 308           ((IsCopy && (SrcReg == AArch64::XZR || SrcReg == AArch64::WZR)) ||
 309            IsMoveImm)) {
 310         for (RegImm &KnownReg : KnownRegs) {
 311           if (KnownReg.Reg != DefReg &&
 312               !TRI->isSuperRegister(DefReg, KnownReg.Reg))
 313             continue;
 314
 315           // For a copy, the known value must be a zero.
 316           if (IsCopy && KnownReg.Imm != 0)
 317             continue;
 318
 319           if (IsMoveImm) {
 320             // For a move immediate, the known immediate must match the source
 321             // immediate.
 322             if (KnownReg.Imm != SrcImm)
 323               continue;
 324
 325             // Don't remove a move immediate that implicitly defines the upper
 326             // bits when only the lower 32 bits are known.
 327             MCPhysReg CmpReg = KnownReg.Reg;
 328             if (any_of(MI->implicit_operands(), [CmpReg](MachineOperand &O) {
 329                   return !O.isDead() && O.isReg() && O.isDef() &&
 330                          O.getReg() != CmpReg;
 331                 }))
 332               continue;
 333           }
 334
 335           if (IsCopy)
 336             DEBUG(dbgs() << "Remove redundant Copy : " << *MI);
 337           else
 338             DEBUG(dbgs() << "Remove redundant Move : " << *MI);
 339
 340           MI->eraseFromParent();
 341           Changed = true;
 342           LastChange = I;
 343           NumCopiesRemoved++;
 344           UsedKnownRegs.insert(KnownReg.Reg);
 345           RemovedMI = true;
 346           break;
 347         }
 348       }
 349     }
 350
 351     // Skip to the next instruction if we removed the COPY/MovImm.
 352     if (RemovedMI)
 353       continue;
 354
 355     // Remove any regs the MI clobbers from the KnownConstRegs set.
 356     for (unsigned RI = 0; RI < KnownRegs.size();)
 357       if (MI->modifiesRegister(KnownRegs[RI].Reg, TRI)) {
 358         std::swap(KnownRegs[RI], KnownRegs[KnownRegs.size() - 1]);
 359         KnownRegs.pop_back();
 360         // Don't increment RI since we need to now check the swapped-in
 361         // KnownRegs[RI].
 362       } else {
 363         ++RI;
 364       }
 365
 366     // Continue until the KnownRegs set is empty.
 367     if (KnownRegs.empty())
 368       break;
 369   }
 370
 371   if (!Changed)
 372     return false;
 373
 374   // Add newly used regs to the block's live-in list if they aren't there
 375   // already.
 376   for (MCPhysReg KnownReg : UsedKnownRegs)
 377     if (!MBB->isLiveIn(KnownReg))
 378       MBB->addLiveIn(KnownReg);
 379
 380   // Clear kills in the range where changes were made.  This is conservative,
 381   // but should be okay since kill markers are being phased out.
 382   DEBUG(dbgs() << "Clearing kill flags.\n\tFirstUse: " << *FirstUse
 383                << "\tLastChange: " << *LastChange);
 384   for (MachineInstr &MMI : make_range(FirstUse, PredMBB->end()))
 385     MMI.clearKillInfo();
 386   for (MachineInstr &MMI : make_range(MBB->begin(), LastChange))
 387     MMI.clearKillInfo();
 388
 389   return true;
 390 }
 391
 392 bool AArch64RedundantCopyElimination::runOnMachineFunction(
 393     MachineFunction &MF) {
 394   if (skipFunction(*MF.getFunction()))
 395     return false;
 396   TRI = MF.getSubtarget().getRegisterInfo();
 397   MRI = &MF.getRegInfo();
 398
 399   // Resize the clobber register bitfield tracker.  We do this once per
 400   // function and then clear the bitfield each time we optimize a copy.
 401   ClobberedRegs.resize(TRI->getNumRegs());
 402
 403   bool Changed = false;
 404   for (MachineBasicBlock &MBB : MF)
 405     Changed |= optimizeCopy(&MBB);
 406   return Changed;
 407 }
 408
 409 FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() {
 410   return new AArch64RedundantCopyElimination();
 411 }