[MachineCopyPropagation] Remove redundant copies after TailDup via machine-cp

[lkail]

Summary

After tailduplication, we have redundant copies. For example

bb.6.land.lhs.true.1:                                                                                                                                                                          
; predecessors: %bb.4                                                                                                                                                                          
  successors: %bb.2(0x80000000); %bb.2(100.00%)                                                                                                                                                
                                                                                                                                                                                               
  renamable $x5 = LI8 0                                                                                                                                                                        
  B %bb.2


bb.2.cleanup16:                                                                                                                                                                                
; predecessors: %bb.3, %bb.1, %bb.6                                                                                                                                                            
  liveins: $x5                                                                                                                                                                                 
  $x3 = COPY killed renamable $x5                                                                                                                                                              
  BLR8 implicit $lr8, implicit $rm, implicit $x3

TailDuplication will duplicate the copy of $x5 and blr in bb.2 to the end of bb.6.

We can remove these copies in machine-cp if it's safe to, i.e.

$reg0 = OP ...
... <<< No uses of $reg0 and $reg1
$reg1 = COPY $reg0 <<< $reg0 is killed
...
<RET>

will be transformed to

$reg1 = OP ...
...
<RET>

[lkail]

Ping

[hfinkel]

Is this something that could be fixed in TailDuplication?

[lkail]

In D65267#1610661, @hfinkel wrote:

Is this something that could be fixed in TailDuplication?

TailDuplication doesn't take specific instructions, such as generating a immediate number, into account. We are able to add code to do such folding in tailduplication, however I think it's beyond taildup's duty.

For the test case, we have such MIR before taildup

bb.6.land.lhs.true.1:                                                                                                                                                                          
; predecessors: %bb.4                                                                                                                                                                          
  successors: %bb.2(0x80000000); %bb.2(100.00%)                                                                                                                                                
                                                                                                                                                                                               
  renamable $x5 = LI8 0                                                                                                                                                                        
  B %bb.2


bb.2.cleanup16:                                                                                                                                                                                
; predecessors: %bb.3, %bb.1, %bb.6                                                                                                                                                            
  liveins: $x5                                                                                                                                                                                 
  $x3 = COPY killed renamable $x5                                                                                                                                                              
  BLR8 implicit $lr8, implicit $rm, implicit $x3

So taildup copys bb.2s code at the end of bb.6.

[lkail]

ping

[jsji]

Have you considered extend MachineCopyPropagation to cover this? Looks like to me that this is a 'backward' COPY propagation.

[lkail]

This comment was removed by lkail.

[lkail]

This comment was removed by lkail.

[lkail]

In D65267#1625969, @jsji wrote:

Have you considered extend MachineCopyPropagation to cover this? Looks like to me that this is a 'backward' COPY propagation.

Yes, it's indeed a backward COPY problem. But I suggest not to implement it in machine-cp. I've inspected MIR of arm64 and x86-64, no such pattern is generated after taildup. If I implement it in machine-cp, I might write some like isMoveImmediate and invoke target hook like TII->FoldImmediate. However currently only PowerPC implements specific TII->FoldImmediate. Taking above into account, this issues seems not general enough to implement in machine-cp.

[jsji]

If I implement it in machine-cp, I might write some like isMoveImmediate and invoke target hook like TII->FoldImmediate. However currently only PowerPC implements specific TII->FoldImmediate. Taking above into account, this issues seems not general enough to implement in machine-cp.

I don't see this is specific to 'isMoveImmediate`.

//   $reg0 = OP ....
// ...
//   $reg1 = COPY $reg0

If we can be sure that $reg0 is renamable, and no use of $reg0 or $reg1 in between (and of course there might be other restrictions, like ReservedReg etc),
we should be able to remove the COPY here.

// `$reg1` = OP ..
// ...

LI $r,0 in your testcase is just a typical example here.

[lkail]

//   $reg0 = OP ....
// ...
//   $reg1 = COPY $reg0

If we can be sure that $reg0 is renamable, and no use of $reg0 or $reg1 in between (and of course there might be other restrictions, like ReservedReg etc),
we should be able to remove the COPY here.

// `$reg1` = OP ..
// ...

One concern here, there might be uses of $reg0 in succ BBs. To overcome it, we might constraint this opt in terminal BBs considering current machine-cp working on single BB. To summarize, without complex uses and defs(thus we don't need to do complex replace-uses-with after RA), in a terminal BB we should have

$reg0 = OP ...
... <<< No uses of $reg0 and $reg1
$reg1 = COPY $reg0 <<< $reg0 is killed
...
<RET>

For complex scenes,

$reg0 = OP ...
... <<< No uses of $reg1, might have uses of $reg0
$reg1 = COPY $reg0
...
$reg1 = OP ...
... <<< If there are uses of $reg0, seems not profitable to conduct this opt.
$reg0 = OP ...
...
<RET>

[jsji]

To summarize, without complex uses and defs(thus we don't need to do complex replace-uses-with after RA). in a terminal BB

Yes, only do simple and valid backward propagate.

[lkail]

Updated patch to remove redundant copies by implementing backward copy propagation in machine-cp.

[jsji]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

315

Can we check !Copy.getOperand(1).isKill() earlier? before the backward SrcMI search? Maybe together with isRenamable()?

[jsji]

@lkail Can you please update the summary to describe more details about why we might have such redundant copies after TailDup.
I know we have those in comments, it would be great if we can summarize those into summary, so that reviewers don't have to look into every single comments. Thanks.

[lkail]

Updated the patch and summary.

[lkail]

ping.

[lkail]

Gentle ping.

[jsji]

LGTM. Please hold for a few days, in case someone has more comments. Thanks.

The testcase needs rebasing, umulo-128-legalisation-lowering.ll needs update too.

[lkail]

Rebased and updated tests.

[jsji]

LGTM.

[lkail]

Added comment for bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy).

[lkail]

Hi @craig.topper , would you mind having a look at changes of X86 test cases?

[lkail]

Added reserved register check on SrcOp.getReg().

[craig.topper]

X86 changes look good.

[lkail]

Check if SrcOp is tied or an implicit-def.

[gribozavr]

Hi,

Unfortunately, with this patch the following program (that I believe to be valid C++) fails under MSan:

#include <set>
#include <string>
#include <vector>

struct Inner {
  __attribute__((noinline)) int Opaque1(int, char) const { return -1; }
  __attribute__((noinline)) void Opaque2(int, char, int) {}
  std::vector<std::set<const std::string*> > output;
  int next = 1;
};

struct Outer {
  __attribute__((noinline)) void Enter(const std::string&);
  Inner* inner;
};

void Outer::Enter(const std::string& str) {
  int state = 0;
  int j = 0;
  for (; j < str.size(); j++) {
    int next_state = inner->Opaque1(state, str[j]);
    if (next_state == -1)
      break;
    else
      state = next_state;
  }
  for (; j < str.size(); j++) {
    inner->Opaque2(state, str[j], inner->next);
    state = inner->next;
    inner->next++;
  }
  inner->output[state].insert(&str);
}

__attribute__((noinline))
void fault(const std::set<const std::string*>& x) {
  for (const std::string *xx : x) {
    std::string copy = *xx;
  }
}

int main() {
  std::string TheString = "a";
  Outer outer;
  outer.inner = new Inner;
  outer.inner->output.resize(2);
  outer.Enter(TheString);
  const std::set<const std::string*>& x = outer.inner->output[1];
  fault(x);
}

==8166==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x7f20d47060e0 in std::__msan::basic_string<char, std::__msan::char_traits<char>, std::__msan::allocator<char> >::__is_long() const include/string:1420:39
    #1 0x7f20d47060e0 in std::__msan::basic_string<char, std::__msan::char_traits<char>, std::__msan::allocator<char> >::basic_string(std::__msan::basic_string<char, std::__msan::char_traits<char>, std::__msan::allocator<char> > const&) include/string:1835:16
    #2 0x7f20d58209ad in fault(std::__msan::set<std::__msan::basic_string<char, std::__msan::char_traits<char>, std::__msan::allocator<char> > const*, std::__msan::less<std::__msan::basic_string<char, std::__msan::char_traits<char>, std::__msan::allocator<char> > const*>, std::__msan::allocator<std::__msan::basic_string<char, std::__msan::char_traits<char>, std::__msan::allocator<char> > const*> > const&) test.cc:38:24
    #3 0x7f20d5820b21 in main test.cc:49:3
    #4 0x7f20d3e6dbbc in __libc_start_main
    #5 0x563387ed2d08 in _start

I'm suspecting a miscompile in Outer::Enter. I have verified that the program works without this patch, and fails with this patch. Please let me know if I could help more you to reproduce the problem.

I'm reverting this patch for now, sorry (r371421).

[lkail]

Hi @gribozavr , thanks for the affirmative action. Could you provide me your command to generate the executable and the target platform you compile to?

[lkail]

When replacing copy's src with copy's def, I missed a point that copy's def is clobbered by selected SrcMI and Tracker should have been informed.

[lkail]

@gribozavr Please let me know if the latest patch resolves the issue.

[lkail]

bugpoint-reduced-simplified.ll21 KBDownload

The failing case is rather large even reduced by bugpoint.

[gribozavr]

Thank you for the fix! I can confirm that the new patch does not break this test in my environment.

I'm not an expert in this part of the backend, however, I wanted to ask to add more tests to the patch, both positive and negative. The logic in the code is quite complex, it has lots of branches (so there are many possibilities for things to go wrong), but testing is extremely light. The patch is only updating existing tests in three places -- which to me looks more like a happy coincidence (that LLVM already includes tests that happen to trigger the new behavior) than intentional testing. Thanks!

[jsji]

Please add more tests as required by @gribozavr . Thanks.

[jsji]

The patch is only updating existing tests in three places -- which to me looks more like a happy coincidence (that LLVM already includes tests that happen to trigger the new behavior) than intentional testing. Thanks!

redundant-copy-after-tail-dup.ll was newly added test (pre-committed) dedicated for this patch.
But yes, it was mostly focus on positive testing, we should try to add more tests ,
especially due to the nature of MachineCopyPropagation.

[lkail]

Pre-committed machine-backward-cp.mir, including edge cases as far as I can imagine. Some test cases remain unchanged, reviewers might have to read whole diff of machine-backward-cp.mir to see unchanged cases.

[lkail]

llvm/test/CodeGen/MIR/PowerPC/machine-backward-cp.mir

151

This case is reduced from @gribozavr 's case.

[lkail]

llvm/test/CodeGen/MIR/PowerPC/machine-backward-cp.mir

165

Prior to the fix, $x7 will be considered not clobbered and use of $x5 in the next instruction will be replaced by $x7 which MCP still considers renamable $x5 = COPY killed renamable $x7 a valid copy.

[jsji]

llvm/test/CodeGen/MIR/PowerPC/machine-backward-cp.mir

1

This file shouldn't be in MIR/PowerPC, I have moved it to PowerPC in https://reviews.llvm.org/rL371857.
Please rebase.

[lkail]

Rebased.

[jsji]

LGTM.

[lkail]

Updated the patch. Currently we don't handle non-trivial copy which has more than 2 operands(Cuz I notice current copy forward propagation algorithm considers copy's implicit operands https://reviews.llvm.org/D29522).

[lkail]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

300

Added check of non-trivial copy.

[lkail]

Added test case that copy has side effect.

[jsji]

Hmm... OK, too many details that I did not even think of. I would leave this to be reviewed by other experts.

[lkail]

Seems we don't need the terminal BB constraint. I'll prepare another patch to address this issue.

llvm/lib/CodeGen/MachineCopyPropagation.cpp

 #include <iterator>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-cp"
 
 STATISTIC(NumDeletes, "Number of dead copies deleted");
 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
+STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
               "Controls which register COPYs are forwarded");
 
 namespace {
 
 class CopyTracker {
   struct CopyInfo {
     MachineInstr *MI;

 
 private:
   typedef enum { DebugUse = false, RegularUse = true } DebugType;
 
   void ClobberRegister(unsigned Reg);
   void ReadRegister(unsigned Reg, MachineInstr &Reader,
                     DebugType DT);
   void CopyPropagateBlock(MachineBasicBlock &MBB);
+  bool eraseIfRedundant(MachineInstr &Copy);
   bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
   void forwardUses(MachineInstr &MI);
   bool isForwardableRegClassCopy(const MachineInstr &Copy,
                                  const MachineInstr &UseI, unsigned UseIdx);
   bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
+  bool isSafeBackwardCopyPropagation(MachineInstr &Copy, MachineInstr &SrcMI);
 
   /// Candidates for deletion.
   SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
 
   /// Multimap tracking debug users in current BB
   DenseMap<MachineInstr*, SmallVector<MachineInstr*, 2>> CopyDbgUsers;
 
   CopyTracker Tracker;
if (Src == PreviousSrc) {
     return true;
   }
   if (!TRI->isSubRegister(PreviousSrc, Src))
     return false;
   unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
   return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
 }
 
+bool MachineCopyPropagation::isSafeBackwardCopyPropagation(
+    MachineInstr &Copy, MachineInstr &SrcMI) {
+  MachineOperand &SrcOp = SrcMI.getOperand(0);
+  if (!(SrcOp.isReg() && SrcOp.isDef() &&
+        SrcOp.getReg() == Copy.getOperand(1).getReg() && SrcOp.isRenamable() &&
+        !SrcOp.isTied() && !SrcOp.isImplicit() &&
+        !MRI->isReserved(SrcOp.getReg())))
+    return false;
+  if (const TargetRegisterClass *URC = SrcMI.getRegClassConstraint(0, TII, TRI))
+    return URC->contains(Copy.getOperand(0).getReg());
+  return false;
+}
+
+/// In a terminal BB, remove instruction \p Copy if \p Copy's src and dst are
+/// not used or defined between \p Copy and definition point of \p Copy's src.
+/// \p Copy's dst will be backward propagated to where \p Copy's src is defined.
+bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy) {
+  // Only take terminal BBs into account.
+  if (!Copy.getParent()->succ_empty())
+    return false;
+  if (!Copy.getOperand(1).isRenamable() || !Copy.getOperand(1).isKill())
+    return false;
+  unsigned Def = Copy.getOperand(0).getReg();
+  unsigned Src = Copy.getOperand(1).getReg();
+  if (MRI->isReserved(Src) || MRI->isReserved(Def))
+    return false;
+  MachineBasicBlock::reverse_iterator E = Copy.getParent()->rend(), It = Copy;
+  It++;
+  MachineInstr *SrcMI = nullptr;
+  for (; It != E; ++It) {
+    if (It->readsRegister(Src, TRI) || It->readsRegister(Def, TRI))
+      return false;
+    if (It->modifiesRegister(Def, TRI))
+      return false;
+    if (It->modifiesRegister(Src, TRI)) {
+      SrcMI = &*It;
+      break;
+    }
+  }
+  if (!SrcMI)
+    return false;
+  if (!isSafeBackwardCopyPropagation(Copy, *SrcMI))
+    return false;
+  SrcMI->getOperand(0).setReg(Def);
+  SrcMI->getOperand(0).setIsRenamable(Copy.getOperand(0).isRenamable());
+  // FIXME: Since SrcMI no longer clobbers Src reg, Tracker still considers Src
+  // reg is clobbered. Therefore we might miss opportunities to delete more
+  // copies.
+  Tracker.clobberRegister(Def, *TRI);
+  Copy.eraseFromParent();
+  ++NumCopyBackwardPropagated;
+  ++NumDeletes;
+  return true;
+}
+
 /// Remove instruction \p Copy if there exists a previous copy that copies the
 /// register \p Src to the register \p Def; This may happen indirectly by
 /// copying the super registers.
 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
                                               unsigned Def) {
   // Avoid eliminating a copy from/to a reserved registers as we cannot predict
   // the value (Example: The sparc zero register is writable but stays zero).
   if (MRI->isReserved(Src) || MRI->isReserved(Def))
if (MI->isCopy() && !TRI->regsOverlap(MI->getOperand(0).getReg(),
                                           MI->getOperand(1).getReg())) {
       Register Def = MI->getOperand(0).getReg();
       Register Src = MI->getOperand(1).getReg();
 
       assert(!Register::isVirtualRegister(Def) &&
              !Register::isVirtualRegister(Src) &&
              "MachineCopyPropagation should be run after register allocation!");
 
+      // In a terminal BB,
+      //  $reg0 = OP ...
+      //  ... <<< No uses of $reg0 and $reg1, no defs of $reg0 and $reg1
+      //  $reg1 = COPY $reg0 <<< $reg0 is killed
+      // =>
+      //  $reg1 = OP ...
+      //  ...
+      //  <RET>
+      if (eraseIfRedundant(*MI))
+        continue;
+
       // The two copies cancel out and the source of the first copy
       // hasn't been overridden, eliminate the second one. e.g.
       //  %ecx = COPY %eax
       //  ... nothing clobbered eax.
       //  %eax = COPY %ecx
       // =>
       //  %ecx = COPY %eax
       //

llvm/test/CodeGen/MIR/PowerPC/machine-backward-cp.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 # RUN: llc -O3 -verify-machineinstrs -mtriple=powerpc64le-unknown-unknown \
 # RUN: -mcpu=pwr9 -simplify-mir -run-pass=machine-cp %s -o - | FileCheck %s
 
 # Normal case
 ---
 name: test0
 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     ; CHECK-LABEL: name: test0
-    ; CHECK: renamable $x4 = LI8 1024
-    ; CHECK: $x3 = COPY killed renamable $x4
+    ; CHECK: $x3 = LI8 1024
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x4 = LI8 1024
     $x3 = COPY renamable killed $x4
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...
 
 # Not in terminal BBs

 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     liveins: $x5
 
     ; CHECK-LABEL: name: iterative_deletion
     ; CHECK: liveins: $x5
-    ; CHECK: renamable $x6 = ADDI8 killed renamable $x5, 1
-    ; CHECK: $x3 = COPY $x6
+    ; CHECK: $x3 = ADDI8 killed renamable $x5, 1
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x6 = ADDI8 renamable killed $x5, 1
     renamable $x4 = COPY renamable killed $x6
     renamable $x7 = COPY renamable killed $x4
     $x3 = COPY renamable killed $x7
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...
 
 ---
 name: Enter
 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     liveins: $x4, $x7
     ; CHECK-LABEL: name: Enter
     ; CHECK: liveins: $x4, $x7
     ; CHECK: renamable $x5 = COPY killed renamable $x7
-    ; CHECK: renamable $x6 = ADDI8 killed renamable $x4, 1
-    ; CHECK: $x3 = ADD8 killed renamable $x5, $x6
+    ; CHECK: renamable $x7 = ADDI8 killed renamable $x4, 1
+    ; CHECK: $x3 = ADD8 killed renamable $x5, killed renamable $x7
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x5 = COPY killed renamable $x7
     renamable $x6 = ADDI8 killed renamable $x4, 1
     renamable $x7 = COPY killed renamable $x6
     $x3 = ADD8 renamable killed $x5, renamable killed $x7
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...
 
 ---
 name: foo
 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     liveins: $x4, $x7
     ; CHECK-LABEL: name: foo
     ; CHECK: liveins: $x4, $x7
     ; CHECK: renamable $x5 = COPY killed renamable $x7
-    ; CHECK: renamable $x6 = ADDI8 renamable $x4, 1
-    ; CHECK: renamable $x7 = COPY killed renamable $x6
-    ; CHECK: renamable $x8 = ADDI8 killed $x4, 2
-    ; CHECK: $x3 = ADD8 killed renamable $x5, $x8
+    ; CHECK: renamable $x7 = ADDI8 renamable $x4, 1
+    ; CHECK: renamable $x6 = ADDI8 killed $x4, 2
+    ; CHECK: $x3 = ADD8 killed renamable $x5, killed renamable $x6
     ; CHECK: $x3 = ADD8 $x3, killed renamable $x7
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x5 = COPY killed renamable $x7
     renamable $x6 = ADDI8 renamable $x4, 1
     renamable $x7 = COPY killed renamable $x6
     renamable $x8 = ADDI8 killed $x4, 2
     renamable $x6 = COPY killed renamable $x8
     $x3 = ADD8 renamable killed $x5, renamable killed $x6
     $x3 = ADD8 $x3, renamable killed $x7
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...
 
 ---
 name: bar
 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     liveins: $x4, $x7
     ; CHECK-LABEL: name: bar
     ; CHECK: liveins: $x4, $x7
     ; CHECK: renamable $x5 = COPY killed renamable $x7
-    ; CHECK: renamable $x6 = ADDI8 renamable $x4, 1
-    ; CHECK: renamable $x8 = COPY $x6
-    ; CHECK: renamable $x6 = ADDI8 renamable $x5, 2
-    ; CHECK: $x3 = ADD8 killed renamable $x5, $x6
+    ; CHECK: renamable $x8 = ADDI8 renamable $x4, 1
+    ; CHECK: renamable $x7 = ADDI8 renamable $x5, 2
+    ; CHECK: $x3 = ADD8 killed renamable $x5, killed renamable $x7
     ; CHECK: $x3 = ADD8 $x3, killed renamable $x8
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x5 = COPY killed renamable $x7
     renamable $x6 = ADDI8 renamable $x4, 1
     renamable $x7 = COPY killed renamable $x6
     renamable $x8 = COPY killed renamable $x7
     renamable $x6 = ADDI8 renamable $x5, 2
     renamable $x7 = COPY killed renamable $x6
     $x3 = ADD8 renamable killed $x5, renamable killed $x7
     $x3 = ADD8 $x3, renamable killed $x8
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...
 
 ---
 name: bogus
 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     liveins: $x7
     ; CHECK-LABEL: name: bogus
     ; CHECK: liveins: $x7
     ; CHECK: renamable $x5 = COPY renamable $x7
-    ; CHECK: renamable $x6 = ADDI8 $x7, 1
-    ; CHECK: renamable $x7 = COPY $x6
+    ; CHECK: renamable $x4 = ADDI8 $x7, 1
     ; CHECK: renamable $x6 = ADDI8 renamable $x5, 2
-    ; CHECK: $x3 = ADD8 $x7, killed renamable $x5
+    ; CHECK: $x3 = ADD8 killed renamable $x4, killed renamable $x5
     ; CHECK: $x3 = ADD8 $x3, killed renamable $x6
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x5 = COPY killed renamable $x7
     renamable $x6 = ADDI8 renamable $x5, 1
     renamable $x4 = COPY killed renamable $x6
     renamable $x7 = COPY killed renamable $x4
     renamable $x6 = ADDI8 renamable $x5, 2
     renamable $x4 = COPY killed renamable $x7
     $x3 = ADD8 renamable killed $x4, renamable killed $x5
     $x3 = ADD8 $x3, renamable killed $x6
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...
 
 ---
 name: foobar
 alignment: 4
 tracksRegLiveness: true
 body: |
   bb.0.entry:
     liveins: $x7
     ; CHECK-LABEL: name: foobar
     ; CHECK: liveins: $x7
-    ; CHECK: renamable $x6 = ADDI8 $x7, 1
-    ; CHECK: renamable $x8 = COPY $x6
-    ; CHECK: renamable $x6 = ADDI8 $x7, 2
-    ; CHECK: $x3 = ADD8 $x6, $x7
+    ; CHECK: renamable $x8 = ADDI8 $x7, 1
+    ; CHECK: renamable $x4 = ADDI8 $x7, 2
+    ; CHECK: $x3 = ADD8 killed renamable $x4, $x7
     ; CHECK: $x3 = ADD8 $x3, killed renamable $x8
     ; CHECK: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
     renamable $x5 = COPY killed renamable $x7
     renamable $x6 = ADDI8 renamable $x5, 1
     renamable $x4 = COPY killed renamable $x6
     renamable $x8 = COPY killed renamable $x4
     renamable $x6 = ADDI8 renamable $x5, 2
     renamable $x4 = COPY killed renamable $x6
     $x3 = ADD8 renamable killed $x4, renamable killed $x5
     $x3 = ADD8 $x3, renamable killed $x8
     BLR8 implicit $lr8, implicit undef $rm, implicit $x3
 
 ...

llvm/test/CodeGen/PowerPC/redundant-copy-after-tail-dup.ll

 ; CHECK-P9-NEXT:    bc 12, 4*cr5+lt, .LBB0_4
 ; CHECK-P9-NEXT:  # %bb.1: # %land.lhs.true
 ; CHECK-P9-NEXT:    bc 12, 4*cr5+lt, .LBB0_5
 ; CHECK-P9-NEXT:  .LBB0_2: # %for.inc
 ; CHECK-P9-NEXT:    lhz r3, 5308(r3)
 ; CHECK-P9-NEXT:    cmplwi r3, 2
 ; CHECK-P9-NEXT:    bge- cr0, .LBB0_6
 ; CHECK-P9-NEXT:  # %bb.3: # %land.lhs.true.1
-; CHECK-P9-NEXT:    li r5, 0
-; CHECK-P9-NEXT:    mr r3, r5
+; CHECK-P9-NEXT:    li r3, 0
 ; CHECK-P9-NEXT:    blr
 ; CHECK-P9-NEXT:  .LBB0_4: # %lor.lhs.false
 ; CHECK-P9-NEXT:    cmplwi cr0, r4, 0
 ; CHECK-P9-NEXT:    bne cr0, .LBB0_2
 ; CHECK-P9-NEXT:  .LBB0_5: # %cleanup16
 ; CHECK-P9-NEXT:    mr r3, r5
 ; CHECK-P9-NEXT:    blr
 ; CHECK-P9-NEXT:  .LBB0_6: # %lor.lhs.false.1

llvm/test/CodeGen/X86/mul-i512.ll

 ; X32-NEXT:    addl %ecx, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Folded Spill
 ; X32-NEXT:    adcl {{[-0-9]+}}(%e{{[sb]}}p), %ebx # 4-byte Folded Reload
 ; X32-NEXT:    movl %ebx, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
 ; X32-NEXT:    movzbl {{[-0-9]+}}(%e{{[sb]}}p), %ecx # 1-byte Folded Reload
 ; X32-NEXT:    adcl %ecx, %eax
 ; X32-NEXT:    movl %eax, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
 ; X32-NEXT:    adcl $0, %edx
 ; X32-NEXT:    movl %edx, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X32-NEXT:    movl %esi, %ecx
-; X32-NEXT:    movl 8(%esi), %ebx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl 8(%ecx), %ebx
 ; X32-NEXT:    movl %ebx, %eax
 ; X32-NEXT:    movl %ebx, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
 ; X32-NEXT:    movl {{[-0-9]+}}(%e{{[sb]}}p), %esi # 4-byte Reload
 ; X32-NEXT:    mull %esi
 ; X32-NEXT:    movl %eax, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
 ; X32-NEXT:    movl %edx, %ebp
 ; X32-NEXT:    movl 12(%ecx), %ecx
 ; X32-NEXT:    movl %ecx, %eax

llvm/test/CodeGen/X86/umulo-128-legalisation-lowering.ll

 ; X86-NEXT:    movl %eax, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    mull %ecx
 ; X86-NEXT:    movl %edx, %ebp
 ; X86-NEXT:    movl %eax, %ecx
 ; X86-NEXT:    addl %esi, %ecx
 ; X86-NEXT:    adcl $0, %ebp
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    mull %esi
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    mull %edx
 ; X86-NEXT:    movl %edx, %esi
 ; X86-NEXT:    addl %ecx, %eax
 ; X86-NEXT:    movl %eax, {{[-0-9]+}}(%e{{[sb]}}p) # 4-byte Spill
 ; X86-NEXT:    adcl %ebp, %esi
 ; X86-NEXT:    setb %cl
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebp
 ; X86-NEXT:    movl %ebp, %eax
 ; X86-NEXT:    mull {{[0-9]+}}(%esp)