[MachineCopyPropagation] Improve redundant copy elimination

[aivchenk]

Summary

We can go a little further and delete the first copy here as well:
   %R1 = COPY %R0         << Redundant
   ... // No clobber of %R1 and no uses of %R1 defined by the first copy.
   %R0 = COPY killed %R1  << Redundant
In other words, The first copy is only used for defining a reg
that is used only in the second copy.

Previously, we deleted only the second copy as redundant.

[aivchenk]

kind ping?

[efriedma]

Please don't wait months to ping on a patch; if you haven't gotten any response in a week, please ping, and if you haven't gotten any response in a couple weeks, please email llvmdev. We want to review patches in a timely fashion, but sometimes reviewers miss an email, or incorrectly expect someone else will review the patch.

I just tried your testcase, and it looks like it passes without your patch. What new cases does this patch handle?

lib/CodeGen/MachineCopyPropagation.cpp

 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <iterator>
+#include <algorithm>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-cp"
 
 STATISTIC(NumDeletes, "Number of dead copies deleted");
 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
   MachineInstr &PrevCopy = *CI->second;
   if (PrevCopy.getOperand(0).isDead())
     return false;
   if (!isNopCopy(PrevCopy, Src, Def, TRI))
     return false;
 
   LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
 
+  // Here we can go a little further and delete the first copy as well:
+  //    %R1 = COPY %R0         << Redundant
+  //    ... // No clobber of %R1 and no uses of %R1 defined by the first copy.
+  //    %R0 = COPY killed %R1  << Redundant
+  // In other words, The first copy (PrevCopy) is only used for defining a reg
+  // that is used only in the second copy (Copy). Note, that "killed" flag is
+  // important here.
+  bool IsPrevCopyRedundant = false;
+  if (Copy.getOperand(1).isKill() &&
+      PrevCopy.getOperand(1).getReg() != Copy.getOperand(1).getReg()) {
+    auto DI =
+        std::find(MaybeDeadCopies.begin(), MaybeDeadCopies.end(), &PrevCopy);
+    if (DI != MaybeDeadCopies.end()) {
+      MachineInstr *MaybeDead = *DI;
+      assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
+
+      IsPrevCopyRedundant = true;
+      MaybeDeadCopies.erase(DI);
+    }
+  }
+
   // Copy was redundantly redefining either Src or Def. Remove earlier kill
   // flags between Copy and PrevCopy because the value will be reused now.
   assert(Copy.isCopy());
   unsigned CopyDef = Copy.getOperand(0).getReg();
   assert(CopyDef == Src || CopyDef == Def);
   for (MachineInstr &MI :
        make_range(PrevCopy.getIterator(), Copy.getIterator()))
     MI.clearRegisterKills(CopyDef, TRI);
 
   Copy.eraseFromParent();
   Changed = true;
   ++NumDeletes;
+
+  if (IsPrevCopyRedundant) {
+    LLVM_DEBUG(dbgs() << "MCP: copy is a redundant as it's def use was "
+                         "redundant, removing: ";
+               PrevCopy.dump());
+
+    ClobberRegister(PrevCopy.getOperand(1).getReg());
+
+    PrevCopy.eraseFromParent();
+    ++NumDeletes;
+  }
+
   return true;
 }
 
 /// Decide whether we should forward the source of \param Copy to its use in
 /// \param UseI based on the physical register class constraints of the opcode
 /// and avoiding introducing more cross-class COPYs.
 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
                                                        const MachineInstr &UseI,

test/CodeGen/X86/machine-copy-prop.mir

 # RUN: llc -mtriple=i686-- -run-pass machine-cp -verify-machineinstrs -o - %s | FileCheck %s
 
 --- |
   declare void @foo()
   define void @copyprop_remove_kill0() { ret void }
   define void @copyprop_remove_kill1() { ret void }
   define void @copyprop_remove_kill2() { ret void }
   define void @copyprop0() { ret void }
   define void @copyprop1() { ret void }
   define void @copyprop2() { ret void }
+  define void @copyprop3() { ret void }
+  define void @copyprop4() { ret void }
   define void @nocopyprop0() { ret void }
   define void @nocopyprop1() { ret void }
   define void @nocopyprop2() { ret void }
   define void @nocopyprop3() { ret void }
   define void @nocopyprop4() { ret void }
   define void @nocopyprop5() { ret void }
+  define void @nocopyprop6() { ret void }
 ...
 ---
 # The second copy is redundant and will be removed, check that we also remove
 # the kill flag of intermediate instructions.
 # CHECK-LABEL: name: copyprop_remove_kill0
 # CHECK: bb.0:
 # CHECK-NEXT: $rax = COPY $rdi
 # CHECK-NEXT: NOOP implicit $rdi
body: |
   bb.0:
     $rax = COPY $rdi
     NOOP implicit killed $ax
     CALL64pcrel32 @foo, csr_64_rt_mostregs
     $rax = COPY $rdi
     NOOP implicit $rax, implicit $rdi
 ...
 ---
+# Those two pairs of copies are redundant and can be removed.
+# CHECK-LABEL: name: copyprop3
+# CHECK: bb.0:
+# CHECK:   NOOP implicit $rax
+name: copyprop3
+body: |
+  bb.0:
+    liveins: $rax
+
+    $rbx = COPY killed $rax
+    $rax = COPY killed $rbx
+    $rbx = COPY killed $rax
+    $rax = COPY killed $rbx
+    NOOP implicit $rax
+
+...
+---
+# This whole chain of copies is redundant.
+# CHECK-LABEL: name: copyprop4
+# CHECK: bb.0:
+# CHECK:   NOOP implicit $rax
+name: copyprop4
+body: |
+  bb.0:
+    liveins: $rax
+
+    renamable $rbx = COPY renamable killed $rax
+    renamable $rcx = COPY renamable killed $rbx
+    renamable $rax = COPY renamable killed $rcx
+    NOOP implicit $rax
+
+...
+---
 # The second copy is not redundant if the source register ($rax) is clobbered
 # even if the dest ($rbp) is not.
 # CHECK-LABEL: name: nocopyprop0
 # CHECK: bb.0:
 # CHECK-NEXT: $rax = COPY $rbp
 # CHECK-NEXT: CALL64pcrel32 @foo, csr_64, implicit $rax, implicit $rbp
 # CHECK-NEXT: $rbp = COPY $rax
 # CHECK-NEXT: NOOP implicit $rax, implicit $rbp

 # CHECK-NEXT: $rip = COPY $rax
 # CHECK-NEXT: $rip = COPY $rax
 name: nocopyprop5
 body: |
   bb.0:
     $rip = COPY $rax
     $rip = COPY $rax
 ...
+# Make sure that we don't delete the first copy
+# CHECK-LABEL: name: nocopyprop6
+# CHECK: bb.0:
+# CHECK-NEXT: $rbx = COPY $rax
+# CHECK-NEXT: NOOP implicit killed $rbx
+# CHECK-NEXT: NOOP implicit $rax
+name: nocopyprop6
+body: |
+  bb.0:
+    $rbx = COPY $rax
+    NOOP implicit killed $rbx
+    $rax = COPY killed $rbx
+    NOOP implicit $rax
+...