[RegisterCoalescing] Don't move COPY if it would interfere with another value

[uabelho]

Summary

RegisterCoalescer::removePartialRedundancy tries to hoist B = A from
BB0/BB2 to BB1:

BB1:
     ...
BB0/BB2:  ----
     B = A;   |
     ...      |
     A = B;   |
       |-------
       |

It does so if a number of conditions are fulfilled. However, it failed
to check if B was used by any of the terminators in BB1. Since we must
insert B = A before the terminators (since it's not a terminator itself),
this means that we could erroneously insert a new definition of B before a
use of it.

[wmi]

LGTM. Thanks for the fix.

[uabelho]

In D44918#1050096, @wmi wrote:

LGTM. Thanks for the fix.

Thank you for the review!

[arsenm]

llvm/trunk/test/CodeGen/Mips/coalesce-partial-redundant-reguse-terminator.mir

1

This testcase is invalid and fails the verifier with -verify-coalescing. I'm not sure how to reproduce the original problem while preserving correct value numbering

llvm/trunk/lib/CodeGen/RegisterCoalescer.cpp

bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,
   // If CopyLeftBB is not nullptr, move CopyMI from MBB to CopyLeftBB and
   // update IntA/IntB.
   //
   // If CopyLeftBB is not nullptr, ensure CopyLeftBB has a single succ so
   // MBB is hotter than CopyLeftBB.
   if (CopyLeftBB && CopyLeftBB->succ_size() > 1)
     return false;
 
-  // Now ok to move copy.
+  // Now (almost sure it's) ok to move copy.
   if (CopyLeftBB) {
+    // Position in CopyLeftBB where we should insert new copy.
+    auto InsPos = CopyLeftBB->getFirstTerminator();
+
+    // Make sure that B isn't referenced in the terminators (if any) at the end
+    // of the predecessor since we're about to insert a new definition of B
+    // before them.
+    if (InsPos != CopyLeftBB->end()) {
+      SlotIndex InsPosIdx = LIS->getInstructionIndex(*InsPos).getRegSlot(true);
+      if (IntB.overlaps(InsPosIdx, LIS->getMBBEndIdx(CopyLeftBB)))
+        return false;
+    }
+
     DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "
                  << printMBBReference(*CopyLeftBB) << '\t' << CopyMI);
 
     // Insert new copy to CopyLeftBB.
-    auto InsPos = CopyLeftBB->getFirstTerminator();
     MachineInstr *NewCopyMI = BuildMI(*CopyLeftBB, InsPos, CopyMI.getDebugLoc(),
                                       TII->get(TargetOpcode::COPY), IntB.reg)
                                   .addReg(IntA.reg);
     SlotIndex NewCopyIdx =
         LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();
     IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
     for (LiveInterval::SubRange &SR : IntB.subranges())
       SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());

llvm/trunk/test/CodeGen/Mips/coalesce-partial-redundant-reguse-terminator.mir

+# RUN: llc -march=mips64 -o - %s -run-pass=simple-register-coalescing | FileCheck %s
+
+---
+name:            f
+tracksRegLiveness: true
+body:             |
+ bb.0:
+    successors: %bb.1
+
+    %21:gpr32 = ADDiu $zero, 0
+    %22:gpr32 = COPY %21
+    %22:gpr32 = ADDiu %22, 1
+    J %bb.1, implicit-def dead $at
+
+ bb.1:
+    successors: %bb.2
+
+    BEQ %22, $zero, %bb.2, implicit-def $at
+
+ bb.2:
+    successors: %bb.2, %bb.3
+
+    %22:gpr32 = COPY %21
+    %21:gpr32 = COPY %22
+    BEQ undef %0:gpr32, $zero, %bb.2, implicit-def $at
+
+ bb.3:
+
+...
+
+# We should not hoist the
+#
+#  %22:gpr32 = COPY %21
+#
+# into bb.1 since %22 is used in the BEQ.
+
+# CHECK-LABEL: bb.1:
+# CHECK-NOT:      COPY
+# CHECK:          BEQ
+
+# CHECK-LABEL: bb.2: