RegisterCoalescer: Don't delete IMPLICIT_DEF if it's live into the same block

[arsenm]

Summary

Live out implicit_defs need to be kept, but the check for this only
checked if the block parent was the same. This doesn't work if the
parent blocks are the same but the value is live. Fixes verifier error
"Instruction ending live segment doesn't read the register", which
would appear at the coalesced non-implicit_def def.

Fixes #38788

[uabelho]

I've done quite some testing on our downstream target with this and
https://reviews.llvm.org/D158850
without problems so it's probably not totally wrong :)

I'll leave for someone who knows the code to accept it.

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

1

I don't know what file this is? It doesn't exist in the repo and it's not added in
https://reviews.llvm.org/D158850

Something you only have in your local repo?

[arsenm]

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

1

I just moved this to the main test file

[bjope]

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

1

The file doesn't exist on main. So when trying to apply this patch it fails since there is no file with this name to delete. So there is something weird with "Diff 1" in the differential.

llvm/test/CodeGen/X86/pr38795.ll

2–3 ↗

(On Diff #553583)

I guess we want to do this now. I.e. enable verify-machineinstrs.

(PR39440 == GH issue 38788)

[arsenm]

squash test

[bjope]

I'm confused. In "Diff 2" (that now is approved) the things you did in "Diff 1" was removed,
The "diff against base" now seem to show the diff compared to the base of D158850. Which is a not-yet-approved patch prio to this in the patch stack.

So something seems really weird to me. Should this patch perhaps be rebased on top of D158850? And what about the original code changes that were in here before the "squash test" update?

(I still expect that this patch would change the RUN line in llvm/test/CodeGen/X86/pr38795.ll to enable -verify-machineinstrs as part of solving PR39440 == GH issue 38788. Right?)

[arsenm]

Correct diff

[bjope]

llvm/test/CodeGen/X86/pr38795.ll

2–3 ↗

(On Diff #553583)

Still think you want to remove the FIXME and enabe the verifier, right?
(LGTM otherwise.)

[arsenm]

llvm/test/CodeGen/X86/pr38795.ll

2–3 ↗

(On Diff #553583)

Only in the next patch, the first one doesn't fix it

[arsenm]

cd4b906e183ffa6b78b2f2d062626ee5f54ceba3

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
+
+...