[AArch64] Add pass to remove redundant copy after RA

[junbuml]

Summary

This change will add a pass to remove unnecessary zero copies in target blocks
of cbz/cbnz instructions. E.g., the copy instruction in the code below can be
removed because the cbz jumps to BB1 when x0 is zero :

BB0:
  cbz x0, .BB1
BB1:
  mov x0, xzr

Jun

[mcrosier]

lib/CodeGen/MachineCopyPropagation.cpp

342 ↗

(On Diff #44925)

Range-based loop?

lib/Target/AArch64/AArch64InstrInfo.cpp

985 ↗

(On Diff #44925)

What about something like this:
This function removes unnecessary zero copies from BBs that are targets of
cbz/cbnz instructions. For instance, the copy instruction in below code can
// be removed because the cbz jumps to BB#2 when w0 is zero.

1031 ↗

(On Diff #44925)

Range-based loop?

lib/Target/AArch64/AArch64InstrInfo.h

167 ↗

(On Diff #44925)

Please use doxygen (i.e., ///) style comments. Also, you should remove the function name from the comment as Doxygen knows what to do (see r253029 as an example).

test/CodeGen/AArch64/machine-copy-remove.ll

57 ↗

(On Diff #44925)

I'd suggest adding a comment to this case mention that the transform isn't safe because we don't know if the upper bits of the X register are zero.

[junbuml]

lib/Target/AArch64/AArch64InstrInfo.cpp

985 ↗

(On Diff #44925)

Thanks! Looks better !

1031 ↗

(On Diff #44925)

I don't think it's possible because we remove MI in the loop? Please correct me if I'm wrong.

lib/Target/AArch64/AArch64InstrInfo.h

167 ↗

(On Diff #44925)

Oh.. Thanks. I will fix it.

test/CodeGen/AArch64/machine-copy-remove.ll

57 ↗

(On Diff #44925)

I will do it !

[junbuml]

Addressed Chad's comments.

[junbuml]

ping?

[MatzeB]

I don't like the integration into MachineCopyPropagation here, the algorithm is not using any other information or methods of that pass (except for the fact that the pass iterates over all basic blocks). This is not enough reason to introduce a new TII callback. You can just as well make this a standalone aarch64 specific pass.

The scope of the algorithm could be extended, I don't see why it should not work for cases like "cmp reg, #CC; b.(n)e XX ... mov reg, #CC" (i.e. any reg getting compared equal/unequal to a constant). In principle this could also be extended to check the whole dominance subtree below the comparison though I guess it is not worth the compiletime to compute a dominance tree here just for that.

lib/CodeGen/MachineCopyPropagation.cpp

342 ↗

(On Diff #45206)

Using "MachineInstr &MI" instead of "auto &I" would be friendlier to the reader.

lib/Target/AArch64/AArch64InstrInfo.cpp

995 ↗

(On Diff #45206)

I would move this downwards closer to the point where it is first assigned.

1052–1054 ↗

(On Diff #45206)

These things cannot simply change the value of registers if they do they need additional MachineOperands with defs, uses, regmasks which already be handled below.

1056–1057 ↗

(On Diff #45206)

This could be for (const MachineOperand &MO : MI->operands())

1066–1067 ↗

(On Diff #45206)

This check can be moved into the assert(), as TargetRegs.count(0) will always be false.

[junbuml]

Thanks Matthias for the review.

the algorithm is not using any other information or methods of that pass (except for the fact that the pass iterates over all basic blocks). This is not enough reason to introduce a new TII callback. You can just as well make this a standalone aarch64 specific pass.

I also agree with your comments , but I doubt introducing a new pass for this is reasonable. I may want to try to find any other good place for this. Please also let me know if you have any suggestion.

[mssimpso]

I doubt introducing a new pass for this is reasonable.

I don't think an AArch64-specific pass is all that unreasonable, especially if you have plans to extend the scope like Matthias suggests. AArch64 already has a few small passes (the AAarch64DeadRegisterDefinitions pass comes to mind as a similar example).

[junbuml]

AArch64 already has a few small passes (the AAarch64DeadRegisterDefinitions pass comes to mind as a similar example).

Thanks Matthew. I'm looking at this pass now.

[junbuml]

Based on the comments from Matthias and Matthew, added a new pass to remove redundant zero copies.

[mcrosier]

lib/Target/AArch64/AArch64RedundantCopyElimination.cpp

8 ↗

(On Diff #47816)

Were we planning on adding support for handling arbitrary const copies, per Matthias' suggestion?

[junbuml]

lib/Target/AArch64/AArch64RedundantCopyElimination.cpp

8 ↗

(On Diff #47816)

In this patch, I want to handle zero first which applied in most spec2000/2006 benchmakrs. And then I will remove below FIXME as I handle the arbitrary mov #imm cases as a separate patch. I believe this could lead review process easier.

[mcrosier]

Sounds reasonable to me, Jun.

[junbuml]

By placing this pass before the control flow opt, we could remove basic blocks which contain only MOV zero.
E.g., we convert :

  cbz     x8, BB1
  ldr     w8, [x8,#4]
  b       BB2 
BB1:  
  mov     w8, wzr
BB2:  
  cmp     w22, w8

into

  cbz     x8, BB1 
  ldr     w8, [x8,#4]
BB1:
  cmp     w22, w8

This transformation happens in almost all spec2006 benchmarks.

[MatzeB]

LGTM with nitpicks addressed.

lib/Target/AArch64/AArch64RedundantCopyElimination.cpp

39 ↗

(On Diff #47816)

I'd call this NumCopiesRemoved.

117–118 ↗

(On Diff #47816)

Could be expressed as for (MachineInstr &MMI : make_range(MBB->begin(), MI->getIterator()))

162 ↗

(On Diff #47816)

It's friendlier to people reading the sourcecode to write MachineBasicBlock &MBB : MF

[junbuml]

Thanks Matthias for your super fast review. I will land it after fixing your comment.

[junbuml]

Addressed Matthias' comment.

llvm/trunk/lib/Target/AArch64/AArch64.h

 
 namespace llvm {
 
 class AArch64TargetMachine;
 class FunctionPass;
 class MachineFunctionPass;
 
 FunctionPass *createAArch64DeadRegisterDefinitions();
+FunctionPass *createAArch64RedundantCopyEliminationPass();
 FunctionPass *createAArch64ConditionalCompares();
 FunctionPass *createAArch64AdvSIMDScalar();
 FunctionPass *createAArch64BranchRelaxation();
 FunctionPass *createAArch64ISelDag(AArch64TargetMachine &TM,
                                  CodeGenOpt::Level OptLevel);
 FunctionPass *createAArch64StorePairSuppressPass();
 FunctionPass *createAArch64ExpandPseudoPass();
 FunctionPass *createAArch64LoadStoreOptimizationPass();

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

+//=- AArch64RedundantCopyElimination.cpp - Remove useless copy for AArch64 -=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+// This pass removes unnecessary zero copies in BBs that are targets of
+// cbz/cbnz instructions. For instance, the copy instruction in the code below
+// can be removed because the CBZW jumps to BB#2 when W0 is zero.
+//  BB#1:
+//    CBZW %W0, <BB#2>
+//  BB#2:
+//    %W0 = COPY %WZR
+// This pass should be run after register allocation.
+//
+// FIXME: This should be extended to handle any constant other than zero. E.g.,
+//   cmp w0, #1
+//     b.eq .BB1
+//   BB1:
+//     mov w0, #1
+//
+// FIXME: This could also be extended to check the whole dominance subtree below
+// the comparison if the compile time regression is acceptable.
+//
+//===----------------------------------------------------------------------===//
+
+#include "AArch64.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "aarch64-copyelim"
+
+STATISTIC(NumCopiesRemoved, "Number of copies removed.");
+
+namespace llvm {
+void initializeAArch64RedundantCopyEliminationPass(PassRegistry &);
+}
+
+namespace {
+class AArch64RedundantCopyElimination : public MachineFunctionPass {
+  const MachineRegisterInfo *MRI;
+  const TargetRegisterInfo *TRI;
+
+public:
+  static char ID;
+  AArch64RedundantCopyElimination() : MachineFunctionPass(ID) {}
+  bool optimizeCopy(MachineBasicBlock *MBB);
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  const char *getPassName() const override {
+    return "AArch64 Redundant Copy Elimination";
+  }
+};
+char AArch64RedundantCopyElimination::ID = 0;
+}
+
+INITIALIZE_PASS(AArch64RedundantCopyElimination, "aarch64-copyelim",
+                "AArch64 redundant copy elimination pass", false, false)
+
+bool AArch64RedundantCopyElimination::optimizeCopy(MachineBasicBlock *MBB) {
+  // Check if the current basic block has a single predecessor.
+  if (MBB->pred_size() != 1)
+    return false;
+
+  MachineBasicBlock *PredMBB = *MBB->pred_begin();
+  MachineBasicBlock::iterator CompBr = PredMBB->getLastNonDebugInstr();
+  if (CompBr == PredMBB->end() || PredMBB->succ_size() != 2)
+    return false;
+
+  unsigned LastOpc = CompBr->getOpcode();
+  // Check if the current basic block is the target block to which the cbz/cbnz
+  // instruction jumps when its Wt/Xt is zero.
+  if (LastOpc == AArch64::CBZW || LastOpc == AArch64::CBZX) {
+    if (MBB != CompBr->getOperand(1).getMBB())
+      return false;
+  } else if (LastOpc == AArch64::CBNZW || LastOpc == AArch64::CBNZX) {
+    if (MBB == CompBr->getOperand(1).getMBB())
+      return false;
+  } else {
+    return false;
+  }
+
+  unsigned TargetReg = CompBr->getOperand(0).getReg();
+  if (!TargetReg)
+    return false;
+  assert(TargetRegisterInfo::isPhysicalRegister(TargetReg) &&
+         "Expect physical register");
+
+  // Remember all registers aliasing with TargetReg.
+  SmallSetVector<unsigned, 8> TargetRegs;
+  for (MCRegAliasIterator AI(TargetReg, TRI, true); AI.isValid(); ++AI)
+    TargetRegs.insert(*AI);
+
+  bool Changed = false;
+  // Remove redundant Copy instructions unless TargetReg is modified.
+  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
+    MachineInstr *MI = &*I;
+    ++I;
+    if (MI->isCopy() && MI->getOperand(0).isReg() &&
+        MI->getOperand(1).isReg()) {
+
+      unsigned DefReg = MI->getOperand(0).getReg();
+      unsigned SrcReg = MI->getOperand(1).getReg();
+
+      if ((SrcReg == AArch64::XZR || SrcReg == AArch64::WZR) &&
+          !MRI->isReserved(DefReg) &&
+          (TargetReg == DefReg || TRI->isSuperRegister(DefReg, TargetReg))) {
+
+        CompBr->clearRegisterKills(DefReg, TRI);
+        if (MBB->isLiveIn(DefReg))
+          // Clear any kills of TargetReg between CompBr and MI.
+          for (MachineInstr &MMI :
+               make_range(MBB->begin()->getIterator(), MI->getIterator()))
+            MMI.clearRegisterKills(DefReg, TRI);
+        else
+          MBB->addLiveIn(DefReg);
+
+        DEBUG(dbgs() << "Remove redundant Copy : ");
+        DEBUG((MI)->print(dbgs()));
+
+        MI->eraseFromParent();
+        Changed = true;
+        NumCopiesRemoved++;
+        continue;
+      }
+    }
+
+    for (const MachineOperand &MO : MI->operands()) {
+      // FIXME: It is possible to use the register mask to check if all
+      // registers in TargetRegs are not clobbered. For now, we treat it like
+      // a basic block boundary.
+      if (MO.isRegMask())
+        return Changed;
+      if (!MO.isReg())
+        continue;
+      unsigned Reg = MO.getReg();
+
+      if (!Reg)
+        continue;
+
+      assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
+             "Expect physical register");
+
+      // Stop if the TargetReg is modified.
+      if (MO.isDef() && TargetRegs.count(Reg))
+        return Changed;
+    }
+  }
+  return Changed;
+}
+
+bool AArch64RedundantCopyElimination::runOnMachineFunction(
+    MachineFunction &MF) {
+  TRI = MF.getSubtarget().getRegisterInfo();
+  MRI = &MF.getRegInfo();
+  bool Changed = false;
+  for (MachineBasicBlock &MBB : MF)
+    Changed |= optimizeCopy(&MBB);
+  return Changed;
+}
+
+FunctionPass *llvm::createAArch64RedundantCopyEliminationPass() {
+  return new AArch64RedundantCopyElimination();
+}

llvm/trunk/lib/Target/AArch64/AArch64TargetMachine.cpp

 EnableDeadRegisterElimination("aarch64-dead-def-elimination", cl::Hidden,
                               cl::desc("Enable the pass that removes dead"
                                        " definitons and replaces stores to"
                                        " them with stores to the zero"
                                        " register"),
                               cl::init(true));
 
 static cl::opt<bool>
+EnableRedundantCopyElimination("aarch64-redundant-copy-elim",
+              cl::desc("Enable the redundant copy elimination pass"),
+              cl::init(true), cl::Hidden);
+
+static cl::opt<bool>
 EnableLoadStoreOpt("aarch64-load-store-opt", cl::desc("Enable the load/store pair"
                    " optimization pass"), cl::init(true), cl::Hidden);
 
 static cl::opt<bool>
 EnableAtomicTidy("aarch64-atomic-cfg-tidy", cl::Hidden,
                  cl::desc("Run SimplifyCFG after expanding atomic operations"
                           " to make use of cmpxchg flow-based information"),
                  cl::init(true));
if (TM->getOptLevel() != CodeGenOpt::None && EnableAdvSIMDScalar) {
     addPass(createAArch64AdvSIMDScalar());
     // The AdvSIMD pass may produce copies that can be rewritten to
     // be register coaleascer friendly.
     addPass(&PeepholeOptimizerID);
   }
 }
 
 void AArch64PassConfig::addPostRegAlloc() {
+  // Remove redundant copy instructions.
+  if (TM->getOptLevel() != CodeGenOpt::None && EnableRedundantCopyElimination)
+    addPass(createAArch64RedundantCopyEliminationPass());
+
   // Change dead register definitions to refer to the zero register.
   if (TM->getOptLevel() != CodeGenOpt::None && EnableDeadRegisterElimination)
     addPass(createAArch64DeadRegisterDefinitions());
   if (TM->getOptLevel() != CodeGenOpt::None && usingDefaultRegAlloc())
     // Improve performance for some FP/SIMD code for A57.
     addPass(createAArch64A57FPLoadBalancing());
 }
 

llvm/trunk/lib/Target/AArch64/CMakeLists.txt

add_llvm_target(AArch64CodeGen
   AArch64CollectLOH.cpp
   AArch64ConditionalCompares.cpp
   AArch64DeadRegisterDefinitionsPass.cpp
   AArch64ExpandPseudoInsts.cpp
   AArch64FastISel.cpp
   AArch64A53Fix835769.cpp
   AArch64FrameLowering.cpp
   AArch64ConditionOptimizer.cpp
+  AArch64RedundantCopyElimination.cpp
   AArch64ISelDAGToDAG.cpp
   AArch64ISelLowering.cpp
   AArch64InstrInfo.cpp
   AArch64LoadStoreOptimizer.cpp
   AArch64MCInstLower.cpp
   AArch64PromoteConstant.cpp
   AArch64PBQPRegAlloc.cpp
   AArch64RegisterInfo.cpp

llvm/trunk/test/CodeGen/AArch64/machine-copy-remove.ll

+; RUN: llc -mtriple=aarch64-linux-gnu -mcpu=cortex-a57 -verify-machineinstrs < %s | FileCheck %s
+
+; CHECK-LABEL: f_XX
+; CHECK: cbz x[[REG:[0-9]+]], [[BB:.LBB.*]]
+; CHECK: [[BB]]:
+; CHECK-NOT: mov x[[REG]], xzr
+define i64 @f_XX(i64 %n, i64* nocapture readonly %P) {
+entry:
+  %tobool = icmp eq i64 %n, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i64, i64* %P
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i64 [ %0, %if.then ], [ 0, %entry ]
+  ret i64 %a.0
+}
+
+; CHECK-LABEL: f_WW
+; CHECK: cbz w[[REG:[0-9]+]], [[BB:.LBB.*]]
+; CHECK: [[BB]]:
+; CHECK-NOT: mov w[[REG]], wzr
+define i32 @f_WW(i32 %n, i32* nocapture readonly %P) {
+entry:
+  %tobool = icmp eq i32 %n, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i32, i32* %P
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i32 [ %0, %if.then ], [ 0, %entry ]
+  ret i32 %a.0
+}
+
+; CHECK-LABEL: f_XW
+; CHECK: cbz x[[REG:[0-9]+]], [[BB:.LBB.*]]
+; CHECK: [[BB]]:
+; CHECK-NOT: mov w[[REG]], wzr
+define i32 @f_XW(i64 %n, i32* nocapture readonly %P) {
+entry:
+  %tobool = icmp eq i64 %n, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i32, i32* %P
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i32 [ %0, %if.then ], [ 0, %entry ]
+  ret i32 %a.0
+}
+
+; CHECK-LABEL: f_WX
+; CHECK: cbz w[[REG:[0-9]+]], [[BB:.LBB.*]]
+; CHECK: [[BB]]:
+; CHECK: mov x[[REG]], xzr
+; Do not remove the mov in this case because we do not know if the upper bits
+; of the X register are zero.
+define i64 @f_WX(i32 %n, i64* nocapture readonly %P) {
+entry:
+  %tobool = icmp eq i32 %n, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i64, i64* %P
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i64 [ %0, %if.then ], [ 0, %entry ]
+  ret i64 %a.0
+}