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

[arsenm]

Summary

This reverts commit 6c062b7641623b1cfd2f359edb3118a4810c965e.

The testcase was invalid and failed the verifier after LiveIntervals
construction. I am unable to see the original error when I correct the
value numbering.

[bjope]

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

27–29

Something weird here. But since it talks about hoisting I figure this used to refer to the COPY in bb.2. So then it should be %3 instead of %1.
But then the "%3 is used in the BEQ" becomes weird. But now when it says %1 it is weird as well, because I don't see that %1 is used in any BEQ.

[bjope]

One thing I don't fully understand is that the description says that the test case was wrong and did not pass verification. But you've also reverted the code and not only changed the test case.

But I figure the modified test case would pass both with and without the code changes.

So do you want to revert the code changes as well since there is no motivating test case? If so it would be nice to say something in the commit message about that (that the code is reverted even if there is no proof that it was incorrect?).

Btw. I'll try to dig a bit to see if I can track this patch back to some other test case (I suspect that uabelho has used mips64 just to find an upstream target showing the original bug).

[arsenm]

In D158324#4600553, @bjope wrote:

One thing I don't fully understand is that the description says that the test case was wrong and did not pass verification. But you've also reverted the code and not only changed the test case.

But I figure the modified test case would pass both with and without the code changes.

It does

So do you want to revert the code changes as well since there is no motivating test case?

That is what this does

If so it would be nice to say something in the commit message about that (that the code is reverted even if there is no proof that it was incorrect?).

Not sure what you mean, if you add -verify-coalescing to the test it fails.

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

27–29

Yes, the comments also didn't make sense (and made less sense with the value numbering fixed)

[bjope]

In D158324#4600616, @arsenm wrote:

In D158324#4600553, @bjope wrote:

If so it would be nice to say something in the commit message about that (that the code is reverted even if there is no proof that it was incorrect?).

Not sure what you mean, if you add -verify-coalescing to the test it fails.

The test case failed verification even before (or without) running the register-coalescer. So as the commit message says, the test case seems broken.

But I thought it was a bit unclear in the commit message that it also removes a defensive check in removePartialRedundancy. I doubt that we will trigger the optimization in more cases (and if it does, then that would be faulty). So something saying that we no longer think that the problematic situation can occur for valid input. And if that assumption is wrong, then we hopefully will catch it in regression tests with verifiers activates since the defensive check in removePartialRedundancy is removed.

I've however found our downstream test case now. And that one is not failing verification on the input.

I came up with these adjustments, that without the patch by uabelho would end up with "Assertion `SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def"' failed.":

# RUN: llc -march=mips64 -o - %s -run-pass=register-coalescer -verify-coalescing | FileCheck %s

---
name:            f
tracksRegLiveness: true
body:             |
  bb.0:
    %0:gpr32 = ADDiu $zero, 0
    %1:gpr32 = COPY %0
    %1:gpr32 = ADDiu %1, 1
    BEQ %0, $zero, %bb.3, implicit-def $at
    J %bb.1, implicit-def dead $at

  bb.1:
    J %bb.2, implicit %1, implicit-def dead $at

  bb.2:
    %1:gpr32 = COPY %0
    %0:gpr32 = COPY %1
    BEQ %0:gpr32, $zero, %bb.2, implicit-def $at

  bb.3:
    %4:gpr32 = ADDiu %1, 1

...

Afaict that test case passes verification on the test input.

[uabelho]

In D158324#4601014, @bjope wrote:

In D158324#4600616, @arsenm wrote:

In D158324#4600553, @bjope wrote:

If so it would be nice to say something in the commit message about that (that the code is reverted even if there is no proof that it was incorrect?).

Not sure what you mean, if you add -verify-coalescing to the test it fails.

The test case failed verification even before (or without) running the register-coalescer. So as the commit message says, the test case seems broken.

But I thought it was a bit unclear in the commit message that it also removes a defensive check in removePartialRedundancy. I doubt that we will trigger the optimization in more cases (and if it does, then that would be faulty). So something saying that we no longer think that the problematic situation can occur for valid input. And if that assumption is wrong, then we hopefully will catch it in regression tests with verifiers activates since the defensive check in removePartialRedundancy is removed.

I've however found our downstream test case now. And that one is not failing verification on the input.

I came up with these adjustments, that without the patch by uabelho would end up with "Assertion `SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def"' failed.":

# RUN: llc -march=mips64 -o - %s -run-pass=register-coalescer -verify-coalescing | FileCheck %s

---
name:            f
tracksRegLiveness: true
body:             |
  bb.0:
    %0:gpr32 = ADDiu $zero, 0
    %1:gpr32 = COPY %0
    %1:gpr32 = ADDiu %1, 1
    BEQ %0, $zero, %bb.3, implicit-def $at
    J %bb.1, implicit-def dead $at

  bb.1:
    J %bb.2, implicit %1, implicit-def dead $at

  bb.2:
    %1:gpr32 = COPY %0
    %0:gpr32 = COPY %1
    BEQ %0:gpr32, $zero, %bb.2, implicit-def $at

  bb.3:
    %4:gpr32 = ADDiu %1, 1

...

Afaict that test case passes verification on the test input.

I put up a patch to fix the testcase rather than reverting the whole patch (which I think is still needed):
https://reviews.llvm.org/D158397

Thanks @arsenm for pointing the problem out and @bjope for the testcase update suggestion.

[arsenm]

Fixed test fails with the revert

llvm/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 (almost sure it's) ok to move copy.
+  // Now 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;
-    }
-
     LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "
                       << printMBBReference(*CopyLeftBB) << '\t' << CopyMI);
 
-    // Insert new copy to CopyLeftBB.
     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/test/CodeGen/Mips/coalesce-partial-redundant-reguse-terminator.mir

-# RUN: llc -march=mips64 -o - %s -run-pass=register-coalescer | FileCheck %s
+# RUN: llc -march=mips64 -o - %s -run-pass=register-coalescer -verify-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
+    %0:gpr32 = ADDiu $zero, 0
+    %1:gpr32 = COPY %0
+    %2:gpr32 = ADDiu %1, 1
     J %bb.1, implicit-def dead $at
 
   bb.1:
-    successors: %bb.2
-
-    BEQ %22, $zero, %bb.2, implicit-def $at
+    BEQ %2, $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
+    %3:gpr32 = COPY %0
+    %0:gpr32 = COPY %3
+    BEQ undef %4:gpr32, $zero, %bb.2, implicit-def $at
 
   bb.3:
 
 ...
 
 # We should not hoist the
 #
-#  %22:gpr32 = COPY %21
+#  %1:gpr32 = COPY %0
 #
-# into bb.1 since %22 is used in the BEQ.
+# into bb.1 since %1 is used in the BEQ.
 
 # CHECK-LABEL: bb.1:
 # CHECK-NOT:      COPY
 # CHECK:          BEQ
 
 # CHECK-LABEL: bb.2: