[InstCombine] Fix infinite loop due to bitcast <-> phi transforms

[nikic]

Summary

Fix for https://bugs.llvm.org/show_bug.cgi?id=44245.

The optimizeBitCastFromPhi() and FoldPHIArgOpIntoPHI() end up fighting against each other, because optimizeBitCastFromPhi() assumes that bitcasts of loads will get folded. This doesn't happen here, because a dangling phi node prevents the one-use fold in https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp#L620-L628 from triggering.

This patch fixes the issue by adding the old phis to the IC worklist, so they actually get removed (instead of this happening on the next InstCombine iteration). I'm not very familiar with the overall InstCombine design, so not sure if this is a proper fix or just a workaround.

[spatel]

I don't know if this is enough to solve the bug completely, but since it's a 1-liner and works on this case, LGTM.

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2375

Can we assert that OldPN has no users at this point?

llvm/test/Transforms/InstCombine/pr44245.ll

5

Add a comment line here that this used to infinite loop.

I know that reducers like to put 'undef' into instructions, but we tend to make those tests meaningless as we improve/change our understanding of undef. So I'd change this test to take an 'i1' argument and replace all of the 'br i1 undef' to use that argument instead.

[cwabbott]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2375

This isn't true until D71209 lands, and therefore the problem could still happen because OldPN won't actually get cleaned up. Even afterwards, there could be a PHI web hanging around. In my patch I assumed that some other dead-code pass would come along and delete it eventually, but I don't know if InstCombine is smart enough to do that before folding the load. Maybe you can just remove all the old phi nodes manually once my patch lands?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2375

Yes, we can't assert that that there are no users here, as there may still be phi users.

I generally agree that it may be safer to explicitly remove the old phi nodes -- InstCombine can clean up dead phi cycles, but I'm not sure whether there are any limitations to that. Doing a final replaceInstUsesWith UndefValue on all the old phis would be the safest option.

I'll hold off on this until your patch lands, as doing an undef replacement wouldn't be safe without it.

[nikic]

Directly remove the instruction, to make sure potential phi cycles also get immediately removed.

[nikic]

I've now switched this to directly remove the instruction rather than only adding it to the worklist, please take another look.

[spatel]

LGTM - see inline for test nit.

llvm/test/Transforms/InstCombine/pr44245.ll

3

The standard RUN line uses:

; RUN: opt -S -instcombine < %s | FileCheck %s

I don't know if the extra "-o -" makes any difference, but we prefer the redirect of the input file because it can prevent unintended matching of strings from a file path that managed to escape into the checked output.

[nikic]

Seems to have broken test-suite and bootstrap, the latter possibly with an infinite loop, based on timeout messages. Not immediately clear to me why...

[lebedev.ri]

In D71164#1800062, @nikic wrote:

Seems to have broken test-suite and bootstrap, the latter possibly with an infinite loop, based on timeout messages. Not immediately clear to me why...

[nikic]

Mostly reduced testcase triggering an infinite loop with this patch:

%type_1 = type {}
%type_2 = type {}
%type_3 = type {}

define dso_local void @SearchGalley() local_unnamed_addr {
entry:
  br label %while.cond

while.cond:                                       ; preds = %cond.end144, %entry
  %link.0 = phi %type_2* [ undef, %entry ], [ %cond145, %cond.end144 ]
  %os115 = bitcast %type_2* %link.0 to %type_3*
  %ou116 = getelementptr inbounds %type_3, %type_3* %os115, i32 0
  %os1117 = bitcast %type_3* %ou116 to %type_1*
  br label %for.cond

for.cond:                                         ; preds = %while.cond
  switch i32 undef, label %sw.epilog [
    i32 120, label %sw.bb
    i32 122, label %sw.bb
    i32 121, label %sw.bb101
  ]

sw.bb:                                            ; preds = %for.cond, %for.cond
  unreachable

sw.bb101:                                         ; preds = %for.cond
  unreachable

sw.epilog:                                        ; preds = %for.cond
  br i1 undef, label %cond.true133, label %cond.false138

cond.true133:                                     ; preds = %sw.epilog
  %0 = load %type_2*, %type_2** undef, align 8
  br label %cond.end144

cond.false138:                                    ; preds = %sw.epilog
  %1 = load %type_2*, %type_2** undef, align 8
  br label %cond.end144

cond.end144:                                      ; preds = %cond.false138, %cond.true133
  %cond145 = phi %type_2* [ %0, %cond.true133 ], [ %1, %cond.false138 ]
  br label %while.cond
}

[nikic]

As far as I can see this is basically the same issue as what this patch tries to solve. Just this time it's not the extra use in the old phi causing the loop, but a change in worklist order caused by this change.

I think to really fix this issue, the transformation of the load and store need to be included as part of this transform, otherwise we cannot reliably guarantee that things will be processed in an order that does not result in loops.

[nikic]

Explicitly perform load combine.

[nikic]

I've updated the patch to directly perform the load combine now. I believe the store case shouldn't exhibit the same issue, as the bitcast is cannot be a phi operand there. I've also added the new looping testcase and -instcombine-infinite-loop-threshold=2 to make sure that the combine runs through in one iteration.

[lebedev.ri]

Did you verify that test-suite now passes?

(marking as reviewed, thanks)

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2327–2329

I'm confused. Why are we replacing old LI with undef instead of NewV?
This should be explained in the comment.

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

452 ↗

(On Diff #237493)

Can you please precommit this?

llvm/test/Transforms/InstCombine/pr44245.ll

2

Precommit

[nikic]

Add comment, split out NFC change.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2327–2329

Added a comment. Keep in mind that the new load is going to have a different type, so it can't be replaced. The whole transform replaces one phi web with another, so we're free to stick undefs in the original one.

llvm/test/Transforms/InstCombine/pr44245.ll

2

This is an infinite loop test. It's theoretically possible to precommit this because infinite loops are no longer infinite nowdays, but that means we have to mess with the exit code etc. I don't think there is any value in that, as we're not testing output anyway.

[nikic]

In D71164#1816462, @lebedev.ri wrote:

Did you verify that test-suite now passes?

Gah. No infinite loops now, but MultiSource/Benchmarks/Olden/power/power.test may have a miscompile.

[nikic]

I'm a bit stumped here. From the trace I see that previously instcombine produced

; Function Attrs: nounwind uwtable
define dso_local { double, double } @Compute_Leaf(%struct.leaf* nocapture %l, double %pi_R, double %pi_I) local_unnamed_addr #0 {
entry:
  %0 = bitcast %struct.leaf* %l to i64*
  %1 = load i64, i64* %0, align 8, !tbaa !32
  store i64 %1, i64* bitcast (double* @P to i64*), align 8, !tbaa !23
  %Q = getelementptr inbounds %struct.leaf, %struct.leaf* %l, i64 0, i32 0, i32 1
  %2 = bitcast double* %Q to i64*
  %3 = load i64, i64* %2, align 8, !tbaa !34
  store i64 %3, i64* bitcast (double* @Q to i64*), align 8, !tbaa !23
  tail call void @optimize_node(double %pi_R, double %pi_I)
  %4 = load double, double* @P, align 8, !tbaa !23
  %cmp = fcmp olt double %4, 0.000000e+00
  br i1 %cmp, label %if.then, label %entry.if.end_crit_edge

entry.if.end_crit_edge:                           ; preds = %entry
  %.pre = load i64, i64* bitcast (double* @Q to i64*), align 8, !tbaa !23
  %5 = bitcast i64 %.pre to double
  %phitmp = bitcast i64 %.pre to double
  br label %if.end

if.then:                                          ; preds = %entry
  store double 0.000000e+00, double* @P, align 8, !tbaa !23
  store double 0.000000e+00, double* @Q, align 8, !tbaa !23
  br label %if.end

if.end:                                           ; preds = %entry.if.end_crit_edge, %if.then
  %6 = phi double [ 0.000000e+00, %if.then ], [ %5, %entry.if.end_crit_edge ]
  %7 = phi double [ 0.000000e+00, %if.then ], [ %phitmp, %entry.if.end_crit_edge ]
  %8 = phi double [ 0.000000e+00, %if.then ], [ %4, %entry.if.end_crit_edge ]
  %9 = phi double [ 0.000000e+00, %if.then ], [ %4, %entry.if.end_crit_edge ]
  %10 = getelementptr %struct.leaf, %struct.leaf* %l, i64 0, i32 0, i32 0
  store double %8, double* %10, align 8, !tbaa !32
  store double %6, double* %Q, align 8, !tbaa !34
  %.fca.0.insert = insertvalue { double, double } undef, double %9, 0
  %.fca.1.insert = insertvalue { double, double } %.fca.0.insert, double %7, 1
  ret { double, double } %.fca.1.insert
}

while with this patch:

; Function Attrs: nounwind uwtable
define dso_local { double, double } @Compute_Leaf(%struct.leaf* nocapture %l, double %pi_R, double %pi_I) local_unnamed_addr #0 {
entry:
  %0 = bitcast %struct.leaf* %l to i64*
  %1 = load i64, i64* %0, align 8, !tbaa !32
  store i64 %1, i64* bitcast (double* @P to i64*), align 8, !tbaa !23
  %Q = getelementptr inbounds %struct.leaf, %struct.leaf* %l, i64 0, i32 0, i32 1
  %2 = bitcast double* %Q to i64*
  %3 = load i64, i64* %2, align 8, !tbaa !34
  store i64 %3, i64* bitcast (double* @Q to i64*), align 8, !tbaa !23
  tail call void @optimize_node(double %pi_R, double %pi_I)
  %4 = load double, double* @P, align 8, !tbaa !23
  %cmp = fcmp olt double %4, 0.000000e+00
  br i1 %cmp, label %if.then, label %entry.if.end_crit_edge

entry.if.end_crit_edge:                           ; preds = %entry
  %.pre12 = load double, double* @Q, align 8, !tbaa !23
  br label %if.end

if.then:                                          ; preds = %entry
  store double 0.000000e+00, double* @P, align 8, !tbaa !23
  store double 0.000000e+00, double* @Q, align 8, !tbaa !23
  br label %if.end

if.end:                                           ; preds = %entry.if.end_crit_edge, %if.then
  %5 = phi double [ 0.000000e+00, %if.then ], [ %.pre12, %entry.if.end_crit_edge ]
  %6 = phi double [ 0.000000e+00, %if.then ], [ %4, %entry.if.end_crit_edge ]
  %7 = phi double [ 0.000000e+00, %if.then ], [ %4, %entry.if.end_crit_edge ]
  %8 = getelementptr %struct.leaf, %struct.leaf* %l, i64 0, i32 0, i32 0
  store double %6, double* %8, align 8, !tbaa !32
  store double %5, double* %Q, align 8, !tbaa !34
  %.fca.0.insert = insertvalue { double, double } undef, double %7, 0
  %.fca.1.insert = insertvalue { double, double } %.fca.0.insert, double 0.000000e+00, 1
  ret { double, double } %.fca.1.insert
}

Note the double 0.0 argument on the second insertvalue.

Unfortunately I've not been able to reproduce this when running -instcombine standalone. I've also tried adding -tbaa -loops -expensive-combines but that didn't work either.

Am I missing some option that makes opt different from clang O3 instcombine?

[nikic]

Okay, I think I got it. I don't have a standalone reproducer for this, but what seems to be happening is that we're iterating over OldPN->users() in https://github.com/llvm/llvm-project/blob/a506f7f9105eec4baac296d21c922457d6f4b52a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp#L2347, but https://github.com/llvm/llvm-project/blob/a506f7f9105eec4baac296d21c922457d6f4b52a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp#L2353 is going to modify the users. That makes us skip over a user (specifically, the original bitcast), which then refers to the old phi node.

That's already rather bad in itself (because it defeats the purpose of the transform and smells of memory unsafety), but with this change the undef replacement makes uses of the old phi actively incorrect.

[nikic]

I was able to create a reproducer with uselistorder:

@Q = internal unnamed_addr global double 1.000000e+00, align 8
 
define double @test(i1 %c, i64* %p) {
entry:
  br i1 %c, label %if, label %end 

if:                           
  %load = load i64, i64* bitcast (double* @Q to i64*), align 8
  br label %end 

end:                                           
  %phi = phi i64 [ 0, %entry ], [ %load, %if ]
  store i64 %phi, i64* %p, align 8
  %cast = bitcast i64 %phi to double
  ret double %cast 

  uselistorder i64 %phi, { 1, 0 }
}

This also demonstrates the currently suboptimal (but not incorrect) transform without this patch: https://llvm.godbolt.org/z/KVqP2P

As such, we can fix this issue independently first :)

[nikic]

I've now verified that this passes test-suite when applied together with D72657.

[lebedev.ri]

Okay, LG if there are no further comments from @spatel.

[spatel]

I wish we didn't have such complicated transforms in instcombine, but that's out-of-bounds for this patch. :)
LGTM

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) {
       if (auto *C = dyn_cast<Constant>(V)) {
         NewV = ConstantExpr::getBitCast(C, DestTy);
       } else if (auto *LI = dyn_cast<LoadInst>(V)) {
         Builder.SetInsertPoint(LI->getNextNode());
         NewV = Builder.CreateBitCast(LI, DestTy);
         Worklist.Add(LI);
       } else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
         NewV = BCI->getOperand(0);
       } else if (auto *PrevPN = dyn_cast<PHINode>(V)) {
         NewV = NewPNodes[PrevPN];
       }
       assert(NewV);
       NewPN->addIncoming(NewV, OldPN->getIncomingBlock(j));
     }
   }
 
   // Traverse all accumulated PHI nodes and process its users,
   // which are Stores and BitcCasts. Without this processing
   // NewPHI nodes could be replicated and could lead to extra
for (User *V : OldPN->users()) {
           RetVal = I;
       } else if (auto *PHI = dyn_cast<PHINode>(V)) {
         assert(OldPhiNodes.count(PHI) > 0);
         (void) PHI;
       } else {
         llvm_unreachable("all uses should be handled");
       }
     }
+
+    // At this point the old phi has either no users, or is only used
+    // in other old phis. Replace with undef to break circles and remove
+    // the instruction.
+    replaceInstUsesWith(*OldPN, UndefValue::get(OldPN->getType()));
+    eraseInstFromFunction(*OldPN);
   }
 
   return RetVal;
 }
 
 Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {
   // If the operands are integer typed then apply the integer transforms,
   // otherwise just apply the common ones.

llvm/test/Transforms/InstCombine/pr44245.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; This used to cause on infinite instcombine loop.
+
+define void @test(i1 %c) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb16:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB17:%.*]], label [[BB24:%.*]]
+; CHECK:       bb17:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i8* [ [[TMP1:%.*]], [[BB47:%.*]] ], [ undef, [[BB16:%.*]] ]
+; CHECK-NEXT:    store i8* [[TMP0]], i8** undef, align 8
+; CHECK-NEXT:    ret void
+; CHECK:       bb24:
+; CHECK-NEXT:    br i1 [[C]], label [[BB44:%.*]], label [[BB49:%.*]]
+; CHECK:       bb44:
+; CHECK-NEXT:    [[TMP469:%.*]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb47:
+; CHECK-NEXT:    [[TMP1]] = phi i8* [ [[TMP2:%.*]], [[BB150:%.*]] ], [ [[TMP1223:%.*]], [[BB119:%.*]] ], [ [[TMP1034:%.*]], [[BB101:%.*]] ], [ [[TMP935:%.*]], [[BB91:%.*]] ], [ [[TMP836:%.*]], [[BB81:%.*]] ], [ [[TMP707:%.*]], [[BB67:%.*]] ], [ [[TMP588:%.*]], [[BB56:%.*]] ], [ [[TMP469]], [[BB44]] ]
+; CHECK-NEXT:    br label [[BB17]]
+; CHECK:       bb49:
+; CHECK-NEXT:    br i1 [[C]], label [[BB56]], label [[BB59:%.*]]
+; CHECK:       bb56:
+; CHECK-NEXT:    [[TMP588]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb59:
+; CHECK-NEXT:    br i1 [[C]], label [[BB67]], label [[BB71:%.*]]
+; CHECK:       bb67:
+; CHECK-NEXT:    [[TMP707]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb71:
+; CHECK-NEXT:    br i1 [[C]], label [[BB81]], label [[BB84:%.*]]
+; CHECK:       bb81:
+; CHECK-NEXT:    [[TMP836]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb84:
+; CHECK-NEXT:    br i1 [[C]], label [[BB91]], label [[BB94:%.*]]
+; CHECK:       bb91:
+; CHECK-NEXT:    [[TMP935]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb94:
+; CHECK-NEXT:    br i1 [[C]], label [[BB101]], label [[BB104:%.*]]
+; CHECK:       bb101:
+; CHECK-NEXT:    [[TMP1034]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb104:
+; CHECK-NEXT:    br i1 [[C]], label [[BB119]], label [[BB123:%.*]]
+; CHECK:       bb119:
+; CHECK-NEXT:    [[TMP1223]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb123:
+; CHECK-NEXT:    br i1 [[C]], label [[BB147:%.*]], label [[BB152:%.*]]
+; CHECK:       bb147:
+; CHECK-NEXT:    [[TMP1492:%.*]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    br label [[BB150]]
+; CHECK:       bb150:
+; CHECK-NEXT:    [[TMP2]] = phi i8* [ [[TMP1841:%.*]], [[BB152]] ], [ [[TMP1492]], [[BB147]] ]
+; CHECK-NEXT:    br label [[BB47]]
+; CHECK:       bb152:
+; CHECK-NEXT:    [[TMP1841]] = load i8*, i8** inttoptr (i64 16 to i8**), align 16
+; CHECK-NEXT:    call void undef()
+; CHECK-NEXT:    br label [[BB150]]
+;
+bb16:                                             ; preds = %bb
+  br i1 %c, label %bb17, label %bb24
+
+bb17:                                             ; preds = %bb47, %bb17
+  %0 = phi i8* [ %1, %bb47 ], [ undef, %bb16 ]
+  store i8* %0, i8** undef, align 8
+  ret void
+
+bb24:                                             ; preds = %bb24
+  br i1 %c, label %bb44, label %bb49
+
+bb44:                                             ; preds = %bb43
+  %tmp46 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb47:                                             ; preds = %bb150, %bb119, %bb101, %bb91, %bb81, %bb67, %bb56, %bb44
+  %.in1 = phi i64* [ %.in, %bb150 ], [ %tmp122, %bb119 ], [ %tmp103, %bb101 ], [ %tmp93, %bb91 ], [ %tmp83, %bb81 ], [ %tmp70, %bb67 ], [ %tmp58, %bb56 ], [ %tmp46, %bb44 ]
+  %1 = bitcast i64* %.in1 to i8*
+  br label %bb17
+
+bb49:                                             ; preds = %bb49
+  br i1 %c, label %bb56, label %bb59
+
+bb56:                                             ; preds = %bb55
+  %tmp58 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb59:                                             ; preds = %bb59
+  br i1 %c, label %bb67, label %bb71
+
+bb67:                                             ; preds = %bb66
+  %tmp70 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb71:                                             ; preds = %bb71
+  br i1 %c, label %bb81, label %bb84
+
+bb81:                                             ; preds = %bb80
+  %tmp83 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb84:                                             ; preds = %bb84
+  br i1 %c, label %bb91, label %bb94
+
+bb91:                                             ; preds = %bb90
+  %tmp93 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb94:                                            ; preds = %bb94
+  br i1 %c, label %bb101, label %bb104
+
+bb101:                                            ; preds = %bb100
+  %tmp103 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb104:                                            ; preds = %bb104
+  br i1 %c, label %bb119, label %bb123
+
+bb119:                                            ; preds = %bb118
+  %tmp122 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb47
+
+bb123:                                            ; preds = %bb123
+  br i1 %c, label %bb147, label %bb152
+
+bb147:                                            ; preds = %bb146
+  %tmp149 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  br label %bb150
+
+bb150:                                            ; preds = %bb152, %bb147
+  %.in = phi i64* [ %tmp184, %bb152 ], [ %tmp149, %bb147 ]
+  br label %bb47
+
+bb152:                                            ; preds = %bb146
+  %tmp184 = load i64*, i64** inttoptr (i64 16 to i64**), align 16
+  call void undef()
+  br label %bb150
+}