RegisterCoalescer: Correctly set valid lanes when keeping live out implicit defs

[arsenm]

Summary

This fixes some verifier errors when live out implicit defs are
coalesced with identity copies. Fixes some reduced testcases from
issue #38788 but doesn't solve the original failure.

I was surprised this seems to obviate the special casing in
analyzeValue that's been there since the subregister liveness support
went in.

[bjope]

llvm/lib/CodeGen/RegisterCoalescer.cpp

2455

If I understand correctly (well I'm trying to understand things), this is needed since we now want to treat the IMPLICIT_DEF as an ordinary value. And some previously computed ValidLanes values would be incorrect as it has treated the IMPLICIT_DEF as producing undefined values so we originally did not care about those lanes?

[arsenm]

llvm/lib/CodeGen/RegisterCoalescer.cpp

2455

Yes. We would try to restore the valid lanes later, but that was less precise

[arsenm]

ping, my Phabricator deadline is this week

[foad]

This looks identical to D158882.

[bjope]

In D158850#4643076, @foad wrote:

This looks identical to D158882.

This is a parent to D158882. So I think it really is the other way around, that something happened with D158882, and that the real fix in that patch got lost somehow?

[arsenm]

Rebase

[bjope]

LGTM

[arsenm]

de5585078e910d8b31369d027a0bea97e31664a2

llvm/lib/CodeGen/RegisterCoalescer.cpp

struct Val {
     /// copy is redundant, i.e. the source value is already the same as
     /// the destination. In such cases the subranges need to be updated
     /// properly. See comment at pruneSubRegValues for more info.
     bool Identical = false;
 
     Val() = default;
 
     bool isAnalyzed() const { return WriteLanes.any(); }
+
+    /// Mark this value as an IMPLICIT_DEF which must be kept as if it were an
+    /// ordinary value.
+    void mustKeepImplicitDef(const TargetRegisterInfo &TRI,
+                             const MachineInstr &ImpDef) {
+      assert(ImpDef.isImplicitDef());
+      ErasableImplicitDef = false;
+      ValidLanes = TRI.getSubRegIndexLaneMask(ImpDef.getOperand(0).getSubReg());
+    }
   };
 
   /// One entry per value number in LI.
   SmallVector<Val, 8> Vals;
 
   /// Compute the bitmask of lanes actually written by DefMI.
   /// Set Redef if there are any partial register definitions that depend on the
   /// previous value of the register.
JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
   if (OtherV.ErasableImplicitDef) {
     // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.
     // This shouldn't normally happen, but ProcessImplicitDefs can leave such
     // IMPLICIT_DEF instructions behind, and there is nothing wrong with it
     // technically.
     //
     // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try
     // to erase the IMPLICIT_DEF instruction.
-    MachineBasicBlock *OtherMBB = Indexes->getMBBFromIndex(V.OtherVNI->def);
+    MachineInstr *OtherImpDef =
+        Indexes->getInstructionFromIndex(V.OtherVNI->def);
+    MachineBasicBlock *OtherMBB = OtherImpDef->getParent();
     if (DefMI && DefMI->getParent() != OtherMBB) {
       LLVM_DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
                  << " extends into "
                  << printMBBReference(*DefMI->getParent())
                  << ", keeping it.\n");
-      OtherV.ErasableImplicitDef = false;
+      OtherV.mustKeepImplicitDef(*TRI, *OtherImpDef);
     } else if (OtherMBB->hasEHPadSuccessor()) {
       // If OtherV is defined in a basic block that has EH pad successors then
       // we get the same problem not just if OtherV is live beyond its basic
       // block, but beyond the last call instruction in its basic block. Handle
       // this case conservatively.
       LLVM_DEBUG(
           dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
                  << " may be live into EH pad successors, keeping it.\n");
-      OtherV.ErasableImplicitDef = false;
+      OtherV.mustKeepImplicitDef(*TRI, *OtherImpDef);
     } else {
       // We deferred clearing these lanes in case we needed to save them
       OtherV.ValidLanes &= ~OtherV.WriteLanes;
     }
   }
 
   // Allow overlapping PHI values. Any real interference would show up in a
   // predecessor, the PHI itself can't introduce any conflicts.
LLVM_DEBUG(dbgs() << "\t\tmerge " << printReg(Reg) << ':' << ValNo << '@'
                       << V.OtherVNI->def << " --> @"
                       << NewVNInfo[Assignments[ValNo]]->def << '\n');
     break;
   case CR_Replace:
   case CR_Unresolved: {
     // The other value is going to be pruned if this join is successful.
     assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
     Val &OtherV = Other.Vals[V.OtherVNI->id];
-    // We cannot erase an IMPLICIT_DEF if we don't have valid values for all
-    // its lanes.
-    if (OtherV.ErasableImplicitDef &&
-        TrackSubRegLiveness &&
-        (OtherV.ValidLanes & ~V.ValidLanes).any()) {
-      LLVM_DEBUG(dbgs() << "Cannot erase implicit_def with missing values\n");
-
-      OtherV.ErasableImplicitDef = false;
-      // The valid lanes written by the implicit_def were speculatively cleared
-      // before, so make this more conservative. It may be better to track this,
-      // I haven't found a testcase where it matters.
-      OtherV.ValidLanes = LaneBitmask::getAll();
-    }
-
     OtherV.Pruned = true;
     [[fallthrough]];
   }
   default:
     // This value number needs to go in the final joined live range.
     Assignments[ValNo] = NewVNInfo.size();
     NewVNInfo.push_back(LR.getValNumInfo(ValNo));
     break;

llvm/test/CodeGen/X86/pr38795-verifier-error-pr38788.ll

+; RUN: llc -mtriple=i386-unknown-linux-gnu -o - -verify-machineinstrs %s | FileCheck %s
+
+define void @fn(i1 %cmp11) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %p.0 = phi i8 [ 0, %entry ], [ %p.2, %for.inc ]
+  %k.0 = phi i8 [ 0, %entry ], [ %k.2, %for.inc ]
+  br i1 %cmp11, label %for.cond35, label %if.end
+
+if.end:                                           ; preds = %for.cond
+  br i1 %cmp11, label %if.then13, label %if.end26
+
+if.then13:                                        ; preds = %if.end
+  br i1 %cmp11, label %for.inc, label %for.cond35
+
+if.end26:                                         ; preds = %for.cond35, %if.end
+  %p.1 = phi i8 [ %p.4, %for.cond35 ], [ %k.0, %if.end ]
+  %k.1 = phi i8 [ %k.4, %for.cond35 ], [ 0, %if.end ]
+  %tobool30 = icmp ne i8 %p.0, 0
+  %spec.select1 = select i1 %tobool30, i8 %k.1, i8 0
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end26, %if.then13
+  %p.2 = phi i8 [ poison, %if.then13 ], [ %p.1, %if.end26 ]
+  %k.2 = phi i8 [ 0, %if.then13 ], [ %spec.select1, %if.end26 ]
+  %0 = load i32, ptr null, align 4
+  br label %for.cond
+
+for.cond35:                                       ; preds = %if.then13, %for.cond
+  %p.4 = phi i8 [ %k.0, %if.then13 ], [ 0, %for.cond ]
+  %k.4 = phi i8 [ 0, %if.then13 ], [ %k.0, %for.cond ]
+  %tobool36 = icmp eq i32 0, 0
+  br label %if.end26
+}

llvm/test/CodeGen/X86/pr38795-verifier-error-pr38788.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py UTC_ARGS: --version 2
+# RUN: llc -mtriple=i386-unknown-linux-gnu -verify-coalescing -run-pass=register-coalescer -o - %s | FileCheck %s
+
+# Make sure no verifier error is produced from coalescing the identity
+# copy in bb.3 with live out implicit_defs. The value is live out of
+# the block, and the incoming value is a phi def.
+
+---
+name:            pr38795_verifier_error_reduced_1
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: pr38795_verifier_error_reduced_1
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT:   liveins: $eax
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr32 = COPY $eax
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.3(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF:%[0-9]+]]:gr32 = IMPLICIT_DEF
+  ; CHECK-NEXT:   JCC_1 %bb.3, 4, implicit undef $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def dead $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.5(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JCC_1 %bb.5, 4, implicit undef $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   successors: %bb.5(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr32 = COPY [[MOV32r0_]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gr32 = COPY [[COPY]]
+  ; CHECK-NEXT:   JMP_1 %bb.1
+  bb.0:
+    liveins: $eax
+    %0:gr32 = COPY $eax
+
+  bb.1:
+    %1:gr32 = IMPLICIT_DEF
+    JCC_1 %bb.3, 4, implicit undef $eflags
+
+  bb.2:
+    %0:gr32 = MOV32r0 implicit-def dead $eflags
+
+  bb.3:
+    %0:gr32 = COPY %0
+    JCC_1 %bb.5, 4, implicit undef $eflags
+
+  bb.4:
+    %1:gr32 = COPY %0
+
+  bb.5:
+    %0:gr32 = COPY killed %1
+    JMP_1 %bb.1
+
+...
+
+# Check for "Instruction ending live segment doesn't read the
+# register" verifier error after coalescing
+# This still failed with a similar error after a preliminary fix was
+# attempted for pr38795_verifier_error_reduced_1
+
+---
+name:            pr38795_verifier_error_reduced_2
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: pr38795_verifier_error_reduced_2
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF:%[0-9]+]]:gr32 = IMPLICIT_DEF
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.3(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF1:%[0-9]+]]:gr32 = IMPLICIT_DEF
+  ; CHECK-NEXT:   JCC_1 %bb.3, 4, implicit killed undef $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.9(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JMP_1 %bb.9
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.5(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JCC_1 %bb.5, 5, implicit killed undef $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   successors: %bb.6(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def dead $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.6
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   successors: %bb.9(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF1:%[0-9]+]]:gr32 = IMPLICIT_DEF
+  ; CHECK-NEXT:   JMP_1 %bb.9
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.6:
+  ; CHECK-NEXT:   successors: %bb.8(0x40000000), %bb.7(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JCC_1 %bb.8, 4, implicit killed undef $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.7:
+  ; CHECK-NEXT:   successors: %bb.8(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr32 = COPY [[DEF1]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.8:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gr32 = COPY [[COPY]]
+  ; CHECK-NEXT:   JMP_1 %bb.1
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.9:
+  ; CHECK-NEXT:   successors: %bb.6(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JMP_1 %bb.6
+  bb.0:
+    %0:gr32 = IMPLICIT_DEF
+
+  bb.1:
+    %1:gr32 = IMPLICIT_DEF
+    JCC_1 %bb.3, 4, implicit killed undef $eflags
+
+  bb.2:
+    %2:gr32 = COPY killed %0
+    JMP_1 %bb.9
+
+  bb.3:
+    JCC_1 %bb.5, 5, implicit killed undef $eflags
+
+  bb.4:
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    JMP_1 %bb.6
+
+  bb.5:
+    %2:gr32 = IMPLICIT_DEF
+    JMP_1 %bb.9
+
+  bb.6:
+    JCC_1 %bb.8, 4, implicit killed undef $eflags
+
+  bb.7:
+    %1:gr32 = COPY killed %3
+
+  bb.8:
+    %4:gr32 = COPY killed %1
+    %0:gr32 = COPY killed %4
+    JMP_1 %bb.1
+
+  bb.9:
+    %3:gr32 = COPY killed %2
+    JMP_1 %bb.6
+
+...