[MachineCopyPropagation] Do more backward copy propagations

[yshui]

Summary

Previously we only do backward copy propagations if there is no read or write to both the Def and Src of the copy between the definition site and the copy site.

However, this restriction can be relaxed. Reads of the Src can be allowed as long as those Reads are rewritten to use Def instead during the propagation.

This commit implements that, potentially improve the generated code. In particular, this resolve an inconsistency between optimized build and optimized build with debuginfo, where DBG_VALUE instructions could prevent backward copy propagation from happening (See: https://bugs.llvm.org/show_bug.cgi?id=49446)

[yshui]

Things still need to be done:

1. Review the failed tests and see which ones are actual bad CodeGen, and which ones need to be updated.
2. Add a test case for this propagation case.

I need some help with (2) as I can't come up with a simple test case that generates the kind of machine IR pattern I need.

[yshui]

Fix typos in comments.

[yshui]

Adjust how DBG_VALUE is rewritten.

[yshui]

Remove a TODO which is no longer relevant

[yshui]

Adjust a debug message.

[condy]

Please do move https://reviews.llvm.org/D98401 regression test to this patch set

[foad]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

331

Hi, I tried testing this on AMDGPU but quite a lot of tests crash here because Copy is nullptr.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

331

Thanks, I will have a look.

[yshui]

Strengthen the invariant maintained by the CopyTracker.

trackUse assumed that when a copy instruction exists in Copies, it can be found via both its Def and its Src, and vice-versa. This wasn't true previously, causing segfaults because findCopyDefViaUnit returned nullptr.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

331

Looks like I made an assumption that was stronger than what CopyTracker actually guaranteed.

This should be fixed now.

[foad]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

331

Yes that fixes the crashes thanks. There are no affected tests for AMDGPU -- of course I was hoping for some massive codegen improvents!

[yshui]

I reviewed the changes in CodeGen tests to the best of my ability, and they look fine to me. If someone else could review and confirm, that would be appreciated.

Also fix some clang-tidy complaints.

[lebedev.ri]

Please upload all patches with full context (-U9999)

[yshui]

Include full context in the patch

[yshui]

Update Mips tests.

My knowledge of Mips is much more limited. I am especially not sure about the $gp motion. Someone more knowledgeable should definitely double check.

[jrtc27]

I don't know why it only affects microMIPS (presumably it does its lowering subtly differently from normal MIPS) but those changes look sensible to me

[atanasyan]

In D98659#2631768, @jrtc27 wrote:

I don't know why it only affects microMIPS (presumably it does its lowering subtly differently from normal MIPS) but those changes look sensible to me

MIIPS changes look good to me. Using $gp register in instructions like lw $25, %call16(__divti3)($gp) is a common way. I do not know why initially another register were involved.

[yshui]

Since this patch already changed output of many test cases, do we still need a test case specifically for this patch?

[lkail]

I haven't looked into implementation details. There are some coding style issues need to be fixed.

llvm/lib/CodeGen/MachineCopyPropagation.cpp

88

Any reason of moving these two functions?

366

This comment should be ended with a period.

370

Comment should be a complete sentence.

910

Please follow https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

929

Missing period.

[lkail]

In D98659#2632859, @yshui wrote:

Since this patch already changed output of many test cases, do we still need a test case specifically for this patch?

You'd better add some mir tests to demonstrate the idea, w/o -g.

[condy]

In D98659#2633657, @lkail wrote:

In D98659#2632859, @yshui wrote:

Since this patch already changed output of many test cases, do we still need a test case specifically for this patch?

You'd better add some mir tests to demonstrate the idea, w/o -g.

A piece of tests can be copied from https://reviews.llvm.org/D98401 @yshui

[yshui]

In D98659#2633657, @lkail wrote:

In D98659#2632859, @yshui wrote:

Since this patch already changed output of many test cases, do we still need a test case specifically for this patch?

You'd better add some mir tests to demonstrate the idea, w/o -g.

Thanks for your review. There is a test case in https://reviews.llvm.org/D98401, which is quite big. I wasn't able to reduce it further, is it OK to just include that as test case?

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

88

I realized these two functions don't have to be part of CopyTracker. If this is not fine I can put them back.

[lkail]

Thanks for your review. There is a test case in https://reviews.llvm.org/D98401, which is quite big. I wasn't able to reduce it further, is it OK to just include that as test case?

Have you tried using bugpoint to reduce it further, or writing MIR test manually?

llvm/lib/CodeGen/MachineCopyPropagation.cpp

88

I would prefer leave them as they are to make code diff less noisy. If you have strong desire to move, please post another NFC patch.

[yshui]

In D98659#2634206, @lkail wrote:

Thanks for your review. There is a test case in https://reviews.llvm.org/D98401, which is quite big. I wasn't able to reduce it further, is it OK to just include that as test case?

Have you tried using bugpoint to reduce it further, or writing MIR test manually?

I am not sure how to use bugpoint for this, as this is not a miscompilation, bad codegen, or crash. But I did try using llvm-reduce, which did help, but the resulting IR is still pretty big.

I find it difficult to manually create the kind of MIR pattern I want.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

88

Ah, sorry, my mistake. These functions were originally in class MachineCopyPropagation, but I needed them in class CopyTracker, so I moved them out.

[yshui]

Style fixes.

[jmorse]

There isn't a lot of difference to how debug-info is updated, as far as I can see, but the summary says a fault is resolved. Is this patch just masking the debug-info issue by doing more propagation? (I might have missed something in the implementation).

For the codegen change -- I would suggest this additional feature deserves a dedicated MIR test. All the tests modified are IR-to-assembly, where unrelated changes to other parts of the compiler might obscure this feature being accidentally disabled or otherwise modified. A MIR test for this specific behaviour in this specific pass will guarantee it isn't broken in the future. Plus, it'll make it easier for reviewers and post-review-readers to understand the patch.

llvm/lib/CodeGen/MachineCopyPropagation.cpp

283–284

Performance nit -- is it safe to return a SmallVector * in the pair? That avoids needless copying and potential allocations.

[yshui]

In D98659#2648161, @jmorse wrote:

There isn't a lot of difference to how debug-info is updated, as far as I can see, but the summary says a fault is resolved. Is this patch just masking the debug-info issue by doing more propagation? (I might have missed something in the implementation).

I am not exactly sure what you mean here. The fault is caused by debug-info preventing propagation from happening, this patch fixes that problem.

For the codegen change -- I would suggest this additional feature deserves a dedicated MIR test. All the tests modified are IR-to-assembly, where unrelated changes to other parts of the compiler might obscure this feature being accidentally disabled or otherwise modified. A MIR test for this specific behaviour in this specific pass will guarantee it isn't broken in the future. Plus, it'll make it easier for reviewers and post-review-readers to understand the patch.

I agree, but I mentioned above I have problem creating an small IR input that would generate the kind of MIR pattern I need. There is a test case attached to the issue but it's quite big.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

283–284

I don't see a problem with this. Will update.

[yshui]

Thanks @jmorse for the review.

Update findAvailBackwardCopy to return a pointer to the SmallVector instead.

[yshui]

Rebasing

[yshui]

Uh, I just figured out how mir tests work. Guess nobody wanted to point out how dumb I am. 😅

Adapted the MIR test from D98401, thanks @condy

[jmorse]

Uh, I just figured out how mir tests work.

No worries, there's a first time for everything :),

I am not exactly sure what you mean here. The fault is caused by debug-info preventing propagation from happening, this patch fixes that problem.

This is true, but I think the patch fixes it by masking the underlying debug-info problem. I've taken a closer look at MCP, I reckon there's a fault in MachineCopyPropagation::BackwardCopyPropagateBlock where it treats all register operands the same, i.e. a "use" by a DBG_VALUE is treated the same as a "use" by any ordinary instruction, causing the debug instruction to prevent an optimisation. The simplest and easiest fix for that, is to have the function ignore debug-info instructions by adding a "if (MI.isDebugInstr()) continue;" statement in the loop before interpreting its register-reads.

That fits with why the extra optimisation gets rid of the different-code-with-debug problem, optimising through register uses would also optimise through debug uses.

If I'm right about that -- could you add that guard, with a debug specific test (ideally in the llvm/tests/DebugInfo/X86 directory), in a separate patch so that we can consider the debug-info matter separate from the optimisation.

That being said: the extra optimisation in this patch is good, as shown by the changes to ll-to-assembly tests, some completely un-necessary copies get eliminated. It's well worth pursuing -- I think more MIR test coverage is needed though (as suggested in D98659#2633657), for example:

• A full example without debug-info being involved,
• Testing that no optimisation happens if the "renamable" flag is absent,
• Checking that propagation doesn't occur (or occurs correctly modified) when sub-registers are read

Plus the scenarios you list in the comment in the trackUse function. The best way to guarantee that those situations are not incorrectly optimised by mistake in the future is by having a test that detects such a scenario. (It's often the case that the tests are a lot more important than the code in the patch itself).

[yshui]

In D98659#2661440, @jmorse wrote:

The simplest and easiest fix for that, is to have the function ignore debug-info instructions by adding a "if (MI.isDebugInstr()) continue;" statement in the loop before interpreting its register-reads.

This is what @condy did in D98401, but this is incorrect. A debug-info use is still a use, you still need to update them when doing propagation, otherwise the debug-info would be incorrect. And that is what this patch is trying to do.

That being said: the extra optimisation in this patch is good, as shown by the changes to ll-to-assembly tests, some completely un-necessary copies get eliminated. It's well worth pursuing -- I think more MIR test coverage is needed though (as suggested in D98659#2633657), for example:

• A full example without debug-info being involved,
• Testing that no optimisation happens if the "renamable" flag is absent,
• Checking that propagation doesn't occur (or occurs correctly modified) when sub-registers are read

Plus the scenarios you list in the comment in the trackUse function. The best way to guarantee that those situations are not incorrectly optimised by mistake in the future is by having a test that detects such a scenario. (It's often the case that the tests are a lot more important than the code in the patch itself).

Makes sense, I'll get on with those.

Thanks!

[yshui]

Add tests suggested by @jmorse

[jmorse]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

160–162

The key is only MCRegisters, but invalidateRegister and similar functions only work with register units. How are Uses found so that they can be invalidated too?

198–199

Could you explain how this is different from the original code -- after all, the original implementation invalidated copes for the reguints for source and destinations of copies found. I don't quite understand "entire register" -- is it the set of regunits, the aliases, or something else?

306–308

This would be a lot easier to understand if it had a motivating example of what it's doing -- see the top of MachineCopyPropagation.cpp for a few samples of what I mean.

315

clang-format? (And other single-statement-continues)

388–392

Shouldn't this be left to the rest of the machine-copy-propagate implementation -- after all, this method is called "trackUse", and it seems to be doing more than that.

935

I ran a stage2 RelWithDebInfo build of clang to test this (I was curious), and got an assertion failure in this function:

llvm::MachineRegisterInfo::updateDbgUsersToReg(llvm::Register, ArrayRef<llvm::MachineInstr *>) const: Assertion `MI->getOperand(0).isReg()' failed.

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

139–149 ↗

(On Diff #335397)

The rbp-to-rbx copy is deleted without this patch too, the only difference is that some of the registers change. I think this is fragile, and doesn't demonstrate the intention of the optimisation. Could you use a test body that

a) deletes a COPY that wasn't already dead, and
b) rewrites a non-COPY operand, another NOOP for example.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

160–162

Uses is always accessed with registers as key (instead of register units), whether it's to find entries or to invalidate entries.

Unless I misunderstood your question?

198–199

So entries of Copies form pairs. Say we have a Def = COPY Src, then Copies will contain {RegUnits of Def} and {RegUnits of Src} as a pair. trackUse relies on the invariant that when Def = COPY Src is no longer a candidate, all related entries in Copies are removed.

The original code doesn't guarantee this. When a RegUnit of a Src register is passed to the original invalidateRegister, only that RegUnit, as well as the related Def RegUnits will be removed, leaving all other RegUnits of that Src register around.

This change makes sure all the related RegUnits are removed.

388–392

trackUse tracks the uses that are rewrite candidates, so if a use is no longer a candidate for rewrite, trackUse removes it.

I think this makes sense.

935

Interesting. I assume this is on X86? Do you happen to have the offending MIR around?

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

935

I can successfully build a RelWithDebInfo stage 2 clang with this patch applied to ab158d35b5a09b2541071ec8351a6ad57dfd7b6e.

Maybe a recent change broke this patch. I will test again after updating.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

935

Hmm, still cannot reproduce with this patch applied to d4528cbb0e703ee17ee6fb4abe72b7246ccb38f1

[yshui]

Update:

• Rebase
• Add an example of the new copy propagation in the top comments
• One more updated test cases: CodeGen/X86/vector-interleaved-load-i16-stride-4.ll
• Style fixes

[yshui]

Rebasing

[yshui]

Update:

• Rebasing
• More affected tests:
  • CodeGen/RISCV/rvv/vselect-fp-rv64.ll
  • CodeGen/RISCV/rvv/vselect-fp-rv32.ll

[yshui]

Rebasing, no new affected tests.

[yshui]

@jmorse Ping.

[yshui]

One more affected test: CodeGen/ARM/umulo-128-legalisation-lowering.ll

[lkail]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

54

Is it possible forward copy propagation can also eliminate this COPY if $R1 defined by this COPY is killed at the BB later? If so, I think we should extend forward copy propagation and should be less complex than what current patch does.

283

Missing perid.

[yshui]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

54

One case I can think of where this can't done is if $R0 got clobbered between $R1 = $R0 and the use of $R1 later.

[yshui]

Fix a missing period

[jmorse]

Looks like the verifier error I experienced must have been transient / my fault, I can't reproduce it now,

I think I understand what's going on here now, however it involves re-purposing the "Avail" flag attached to copies in an unexpected way. At the very least, it needs re-naming. As far as I understand it before this patch, avail means:

• False: candidate for def being rewritten in backward copy propagation
• False: is a clobbered register, in forward copy propagation
• True: candidate for forward copy propagation

With this patch the "false" value takes on even more meaning: "uses can be rewritten along the way". Realistically, I think if this is to all be understood, the "Avail" flag needs to become an enum or something to communicate more information to the reader about what it means.

How does this new form of backwards copy propagation interact with the existing backwards copy propagation? The reason being, modifying one your tests a little:

---

name: copyprop3
body: |
  bb.0:
    renamable $rbp = LEA64r $rax, 1, $noreg, 8, $noreg
    NOOP implicit renamable $rbp
    renamable $rax = COPY renamable $rbp
    renamable $rbx = COPY killed renamable $rbp
    NOOP implicit $rax
...

I was expecting $rbp to be rewritten to $rax and the copies dropped -- instead the dead COPY is dropped, and the uses left un-rewritten:

bb.0:
  renamable $rbp = LEA64r $rax, 1, $noreg, 8, $noreg
  NOOP implicit renamable $rbp
  renamable $rax = COPY renamable $rbp
  NOOP implicit $rax

I suspect (90% confidence) that this is because CopyTracker::invalidateRegister is deleting the copy because it's not eligible for the "plain" backwards copy propagation. The design of these two things needs to be unified.

[yshui]

In D98659#2830241, @jmorse wrote:

Looks like the verifier error I experienced must have been transient / my fault, I can't reproduce it now,

I think I understand what's going on here now, however it involves re-purposing the "Avail" flag attached to copies in an unexpected way. At the very least, it needs re-naming. As far as I understand it before this patch, avail means:

• False: candidate for def being rewritten in backward copy propagation
• False: is a clobbered register, in forward copy propagation
• True: candidate for forward copy propagation

With this patch the "false" value takes on even more meaning: "uses can be rewritten along the way". Realistically, I think if this is to all be understood, the "Avail" flag needs to become an enum or something to communicate more information to the reader about what it means.

I think it's just "Avail" has different meanings in forward/backward propagation. In backward propagation, it means "def is a candidate for rewriting", this patch doesn't add a new meaning.

How does this new form of backwards copy propagation interact with the existing backwards copy propagation? The reason being, modifying one your tests a little:

---

name: copyprop3
body: |
  bb.0:
    renamable $rbp = LEA64r $rax, 1, $noreg, 8, $noreg
    NOOP implicit renamable $rbp
    renamable $rax = COPY renamable $rbp
    renamable $rbx = COPY killed renamable $rbp
    NOOP implicit $rax
...

I was expecting $rbp to be rewritten to $rax and the copies dropped -- instead the dead COPY is dropped, and the uses left un-rewritten:

bb.0:
  renamable $rbp = LEA64r $rax, 1, $noreg, 8, $noreg
  NOOP implicit renamable $rbp
  renamable $rax = COPY renamable $rbp
  NOOP implicit $rax

I suspect (90% confidence) that this is because CopyTracker::invalidateRegister is deleting the copy because it's not eligible for the "plain" backwards copy propagation. The design of these two things needs to be unified.

renamable $rax = COPY renamable $rbp isn't a candidate for propagation because $rbp isn't killed in that instruction. The later copy is probably eliminated because it's dead code.

[yshui]

Rebasing, new affected test:

• CodeGen/Thumb2/mve-vqdmulh.ll

llvm/lib/CodeGen/MachineCopyPropagation.cpp

 
 namespace {
 
+/// Check that \p MI does not have implicit uses that overlap with it's \p Use
+/// operand (the register being replaced), since these can sometimes be
+/// implicitly tied to other operands.  For example, on AMDGPU:
+///
+/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>,
+/// %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
+///
+/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
+/// way of knowing we need to update the latter when updating the former.
+bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use,
+                        const TargetRegisterInfo &TRI) {
+  for (const MachineOperand &MIUse : MI.uses())
+    if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
+        MIUse.isUse() && TRI.regsOverlap(Use.getReg(), MIUse.getReg()))
+      return true;
+
+  return false;
+}
+
+/// 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 isForwardableRegClassCopy(const Register &NewReg, const MachineInstr &UseI,
+                               unsigned UseIdx, const TargetInstrInfo &TII,
+                               const TargetRegisterInfo &TRI) {
+
+  // If the new register meets the opcode register constraints, then allow
+  // forwarding.
+  if (const TargetRegisterClass *URC =
+          UseI.getRegClassConstraint(UseIdx, &TII, &TRI))
+    return URC->contains(NewReg);
+
+  if (!UseI.isCopy())
+    return false;
+
+  /// COPYs don't have register class constraints, so if the user instruction
+  /// is a COPY, we just try to avoid introducing additional cross-class
+  /// COPYs.  For example:
+  ///
+  ///   RegClassA = COPY RegClassB  // Copy parameter
+  ///   ...
+  ///   RegClassB = COPY RegClassA  // UseI parameter
+  ///
+  /// which after forwarding becomes
+  ///
+  ///   RegClassA = COPY RegClassB
+  ///   ...
+  ///   RegClassB = COPY RegClassB
+  ///
+  /// so we have reduced the number of cross-class COPYs and potentially
+  /// introduced a nop COPY that can be removed.
+  const TargetRegisterClass *UseDstRC =
+      TRI.getMinimalPhysRegClass(UseI.getOperand(0).getReg());
+
+  const TargetRegisterClass *SuperRC = UseDstRC;
+  for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
+       SuperRC; SuperRC = *SuperRCI++)
+    if (SuperRC->contains(NewReg))
+      return true;
+
+  return false;
+}
+
 class CopyTracker {
   struct CopyInfo {
     MachineInstr *MI;

 
   DenseMap<MCRegister, CopyInfo> Copies;
 
+  /// Mapping registers to where they are used later. Key is actual registers
+  /// (not register units) Only used for Backward Propagation
+  DenseMap<MCRegister, SmallVector<MachineInstr *>> Uses;
+
 public:
   /// Mark all of the given registers and their subregisters as unavailable for
   /// copying.

                                 I->second.DefRegs.end());
       }
     }
-    for (MCRegister InvalidReg : RegsToInvalidate)
+    for (MCRegister InvalidReg : RegsToInvalidate) {
       for (MCRegUnitIterator RUI(InvalidReg, &TRI); RUI.isValid(); ++RUI)
         Copies.erase(*RUI);
+      Uses.erase(InvalidReg);
+    }
   }
 
   /// Clobber a single register, removing it from the tracker's copy maps.

     }
   }
 
-  bool hasAnyCopies() {
-    return !Copies.empty();
-  }
+  bool hasAnyCopies() { return !Copies.empty(); }
 
   MachineInstr *findCopyForUnit(MCRegister RegUnit,
                                 const TargetRegisterInfo &TRI,

     return CI->second.MI;
   }
 
+  /// Find the corresponding copy instruction where \p RegUnit appeared as the
+  /// Src
   MachineInstr *findCopyDefViaUnit(MCRegister RegUnit,
                                    const TargetRegisterInfo &TRI) {
     auto CI = Copies.find(RegUnit);

     return findCopyForUnit(*RUI, TRI, true);
   }
 
-  MachineInstr *findAvailBackwardCopy(MachineInstr &I, MCRegister Reg,
-                                      const TargetRegisterInfo &TRI) {
+  std::pair<MachineInstr *, SmallVector<MachineInstr *>>
+  findAvailBackwardCopy(MachineInstr &I, MCRegister Reg,
+                        const TargetRegisterInfo &TRI) {
     MCRegUnitIterator RUI(Reg, &TRI);
     MachineInstr *AvailCopy = findCopyDefViaUnit(*RUI, TRI);
     if (!AvailCopy ||
         !TRI.isSubRegisterEq(AvailCopy->getOperand(1).getReg(), Reg))
-      return nullptr;
+      return {nullptr, {}};
 
     Register AvailSrc = AvailCopy->getOperand(1).getReg();
     Register AvailDef = AvailCopy->getOperand(0).getReg();

         if (MO.isRegMask())
           // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef?
           if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
-            return nullptr;
+            return {nullptr, {}};
 
-    return AvailCopy;
+    auto UseI = Uses.find(AvailSrc);
+    return {AvailCopy,
+            UseI == Uses.end() ? SmallVector<MachineInstr *>{} : UseI->second};
+  }
+
+  /// Track uses of registers that are candidates for backward copy propagation
+  void trackUse(MachineInstr *MI, const TargetRegisterInfo &TRI,
+                const TargetInstrInfo &TII) {
+    SmallSet<MCRegister, 8> RegsToInvalidate;
+    for (unsigned OpIdx = 0, OpEnd = MI->getNumOperands(); OpIdx != OpEnd;
+         ++OpIdx) {
+      MachineOperand &MOUse = MI->getOperand(OpIdx);
+      if (!MOUse.isReg() || !MOUse.isUse() || MOUse.isUndef()) {
+        continue;
+      }
+      if (!MOUse.getReg()) {
+        continue;
+      }
+
+      MCRegister Use = MOUse.getReg().asMCReg();
+
+      // Three cases where we should give up propagating copies:
+      //
+      //   1) If a read register overlaps, but is not equal to, some of the
+      //   candidate src registers, we need to give up on propagating those
+      //   overlapping registers.
+      //
+      //   2) If a copy candidate's Def is read or partially read.
+      //
+      //   3) This instruction has uses, but we don't know how to
+      //   rewrite those uses because of overlaps/ties/unrenamble registers, so
+      //   give up on propagating copies related to these uses
+      bool isOverlappingUse = false;
+      Register candidateSrc = {0}, candidateDef = {0};
+      for (MCRegUnitIterator RUI(Use, &TRI); RUI.isValid(); ++RUI) {
+        auto CopyInfoI = Copies.find(*RUI);
+        if (CopyInfoI == Copies.end()) {
+          continue;
+        }
+        if (!CopyInfoI->second.Avail) {
+          // Use matches or overlaps with an Src
+          // Find the actual Src in the copy instruction
+          MachineInstr *Copy = findCopyDefViaUnit(*RUI, TRI);
+          MCRegister Src = Copy->getOperand(1).getReg().asMCReg();
+          MCRegister Def = Copy->getOperand(0).getReg().asMCReg();
+          if (Src != Use) {
+            // Case (1)
+            isOverlappingUse = true;
+            RegsToInvalidate.insert(Src);
+            RegsToInvalidate.insert(Def);
+          } else {
+            candidateSrc = Src;
+            candidateDef = Def;
+            break;
+          }
+        } else {
+          // Case (2)
+          RegsToInvalidate.insert(
+              CopyInfoI->second.MI->getOperand(0).getReg().asMCReg());
+          RegsToInvalidate.insert(
+              CopyInfoI->second.MI->getOperand(1).getReg().asMCReg());
+        }
+      }
+
+      // Can't have matching and overlapping Srcs at the same time
+      assert(!candidateSrc || !isOverlappingUse);
+
+      if (candidateSrc) {
+        // implies: !isOverlappingUse
+        if (!MI->isDebugValue() &&
+            (hasImplicitOverlap(*MI, MOUse, TRI) || !MOUse.isRenamable() ||
+             MOUse.isTied() ||
+             !isForwardableRegClassCopy(candidateSrc, *MI, OpIdx, TII, TRI))) {
+          // Case (3)
+          RegsToInvalidate.insert(candidateSrc.asMCReg());
+          RegsToInvalidate.insert(candidateDef.asMCReg());
+          continue;
+        }
+
+        // Add to Uses for future rewrite
+        auto I = Uses.insert({Use, {MI}});
+        if (!I.second) {
+          I.first->second.push_back(MI);
+        }
+      }
+    }
+
+    for (MCRegister InvalidReg : RegsToInvalidate) {
+      for (MCRegUnitIterator RUI(InvalidReg, &TRI); RUI.isValid(); ++RUI)
+        Copies.erase(*RUI);
+      Uses.erase(InvalidReg);
+    }
   }
 
   MachineInstr *findAvailCopy(MachineInstr &DestCopy, MCRegister Reg,

 
   void clear() {
     Copies.clear();
+    Uses.clear();
   }
 };
 

   bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
   void forwardUses(MachineInstr &MI);
   void propagateDefs(MachineInstr &MI);
-  bool isForwardableRegClassCopy(const MachineInstr &Copy,
-                                 const MachineInstr &UseI, unsigned UseIdx);
   bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
                                           const MachineInstr &UseI,
                                           unsigned UseIdx);
-  bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
   bool hasOverlappingMultipleDef(const MachineInstr &MI,
                                  const MachineOperand &MODef, Register Def);
 

   SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
 
   /// Multimap tracking debug users in current BB
-  DenseMap<MachineInstr*, SmallVector<MachineInstr*, 2>> CopyDbgUsers;
+  DenseMap<MachineInstr *, SmallVector<MachineInstr *, 2>> CopyDbgUsers;
 
   CopyTracker Tracker;
 

   return false;
 }
 
-/// 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,
-                                                       unsigned UseIdx) {
-
-  Register CopySrcReg = Copy.getOperand(1).getReg();
-
-  // If the new register meets the opcode register constraints, then allow
-  // forwarding.
-  if (const TargetRegisterClass *URC =
-          UseI.getRegClassConstraint(UseIdx, TII, TRI))
-    return URC->contains(CopySrcReg);
-
-  if (!UseI.isCopy())
-    return false;
-
-  /// COPYs don't have register class constraints, so if the user instruction
-  /// is a COPY, we just try to avoid introducing additional cross-class
-  /// COPYs.  For example:
-  ///
-  ///   RegClassA = COPY RegClassB  // Copy parameter
-  ///   ...
-  ///   RegClassB = COPY RegClassA  // UseI parameter
-  ///
-  /// which after forwarding becomes
-  ///
-  ///   RegClassA = COPY RegClassB
-  ///   ...
-  ///   RegClassB = COPY RegClassB
-  ///
-  /// so we have reduced the number of cross-class COPYs and potentially
-  /// introduced a nop COPY that can be removed.
-  const TargetRegisterClass *UseDstRC =
-      TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg());
-
-  const TargetRegisterClass *SuperRC = UseDstRC;
-  for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
-       SuperRC; SuperRC = *SuperRCI++)
-    if (SuperRC->contains(CopySrcReg))
-      return true;
-
-  return false;
-}
-
-/// Check that \p MI does not have implicit uses that overlap with it's \p Use
-/// operand (the register being replaced), since these can sometimes be
-/// implicitly tied to other operands.  For example, on AMDGPU:
-///
-/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
-///
-/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
-/// way of knowing we need to update the latter when updating the former.
-bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
-                                                const MachineOperand &Use) {
-  for (const MachineOperand &MIUse : MI.uses())
-    if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
-        MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
-      return true;
-
-  return false;
-}
-
 /// For an MI that has multiple definitions, check whether \p MI has
 /// a definition that overlaps with another of its definitions.
 /// For example, on ARM: umull   r9, r9, lr, r0

     if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
       continue;
 
-    if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
+    if (!isForwardableRegClassCopy(CopySrcReg, MI, OpIdx, *TII, *TRI))
       continue;
 
-    if (hasImplicitOverlap(MI, MOUse))
+    if (hasImplicitOverlap(MI, MOUse, *TRI))
       continue;
 
     // Check that the instruction is not a copy that partially overwrites the

   LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
                     << "\n");
 
-  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
+  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
     MachineInstr *MI = &*I;
     ++I;
 

     if (!MODef.isRenamable())
       continue;
 
-    MachineInstr *Copy =
+    auto Copy =
         Tracker.findAvailBackwardCopy(MI, MODef.getReg().asMCReg(), *TRI);
-    if (!Copy)
+    if (!Copy.first)
       continue;
 
-    Register Def = Copy->getOperand(0).getReg();
-    Register Src = Copy->getOperand(1).getReg();
+    Register Def = Copy.first->getOperand(0).getReg();
+    Register Src = Copy.first->getOperand(1).getReg();
 
     if (MODef.getReg() != Src)
       continue;
 
-    if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))
+    if (!isBackwardPropagatableRegClassCopy(*Copy.first, MI, OpIdx))
       continue;
 
-    if (hasImplicitOverlap(MI, MODef))
+    if (hasImplicitOverlap(MI, MODef, *TRI)) {
       continue;
+    }
 
     if (hasOverlappingMultipleDef(MI, MODef, Def))
       continue;
 
     LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI)
                       << "\n     with " << printReg(Def, TRI) << "\n     in "
-                      << MI << "     from " << *Copy);
+                      << MI << "     from " << *Copy.first);
 
+    bool isRenamable = Copy.first->getOperand(0).isRenamable();
     MODef.setReg(Def);
-    MODef.setIsRenamable(Copy->getOperand(0).isRenamable());
+    MODef.setIsRenamable(isRenamable);
 
     LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
-    MaybeDeadCopies.insert(Copy);
+
+    // Update uses of the original Def.
+    // We don't need to perform checks here, Uses only contains rewrittable
+    // uses
+    for (MachineInstr *User : Copy.second) {
+      if (User->isDebugValue()) {
+        MRI->updateDbgUsersToReg(Def, User);
+        continue;
+      }
+      for (unsigned UseIdx = 0, UseEnd = User->getNumOperands();
+           UseIdx != UseEnd; ++UseIdx) {
+        MachineOperand &MOUse = User->getOperand(UseIdx);
+        if (!MOUse.isReg() || MOUse.getReg() != Src) {
+          continue;
+        }
+        // TODO: update dbg instructions, see CopyDbgUsers
+        LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
+                          << "\n     with " << printReg(Def, TRI)
+                          << "\n     in " << *User << "     from "
+                          << *Copy.first);
+        MOUse.setReg(Def);
+        MOUse.setIsRenamable(isRenamable);
+      }
+      LLVM_DEBUG(dbgs() << "MCP: After replacement: " << *User << "\n");
+    }
+
+    MaybeDeadCopies.insert(Copy.first);
     Changed = true;
     ++NumCopyBackwardPropagated;
   }

       // Unlike forward cp, we don't invoke propagateDefs here,
       // just let forward cp do COPY-to-COPY propagation.
       if (isBackwardPropagatableCopy(*MI, *MRI)) {
+        // Remove copies related to Src. Src can only possibly appear
+        // in copy candidates as define, because otherwise the current copy
+        // won't kill Src.
         Tracker.invalidateRegister(Src, *TRI);
+        // Remove copies related to Def.
         Tracker.invalidateRegister(Def, *TRI);
         Tracker.trackCopy(MI, *TRI);
         continue;

       }
 
     propagateDefs(*MI);
+
+    // Track uses after propagation, because we need the correct Def register.
+    Tracker.trackUse(MI, *TRI, *TII);
     for (const MachineOperand &MO : MI->operands()) {
       if (!MO.isReg())
         continue;

       if (!MO.getReg())
         continue;
 
-      if (MO.isDef())
-        Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI);
-
-      if (MO.readsReg())
+      if (MO.isDef()) {
+        // Even if we did apply propagation, the relevant copy instruction
+        // would still get invalidated here. The original instruction would
+        // trigger invalidation because its Def matches the Src of the relevant
+        // copy, the updated instruction would still do because its Def now
+        // matches the Def of the relevant copy.
         Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI);
+      }
     }
   }