[JumpThreading] Fix PR44611

[junparser]

Summary

As title, this patch fixes hang (https://bugs.llvm.org/show_bug.cgi?id=44611) which caused by unreachable cycles inside cfg when build with jump-threading-across-loop-headers.

TestPlan: check-llvm

[kazu]

Hi junparser, your main change in JumpThreading.cpp looks good. Now, could you explain your change in removed-use.ll? To be honest, I haven't understood the original intent of the testcase. Thanks!

[efriedma]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

455

We've been trying to avoid calling getDomTree() in JumpThreading where possible because there's a performance cost: it actually flushes all the pending DomTree updates. Calling it for every basic block will likely cause performance issues. (You should be able to find some discussion of this in the review threads for the related JumpThreading patches.)

[junparser]

In D75977#1922477, @kazu wrote:

Hi junparser, your main change in JumpThreading.cpp looks good. Now, could you explain your change in removed-use.ll? To be honest, I haven't understood the original intent of the testcase. Thanks!

It's just that the testcase need to be updated after this patch, I just make some simplification since bb3 -> bb4 -> bb5 is an unreachable cycle and we do not need to handle them.

[junparser]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

455

Yes, I have already know about that. That's why i add this check at the end of for statement after other checks. However, for unreachable cycles, I afraid maybe this is the only way to check (maybe I am wrong).

Btw, the condition can be update to:

if (Changed && !DTU->getDomTree().isReachableFromEntry(&BB))

which can reduce the performance cost.

[efriedma]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

455

I'd like to see some actual numbers for the performance impact, similar to what was done in the past.

Where exactly is the infinite loop coming from? We already have some code which should guard the use of LazyValueInfo.

[kazu]

Sorry, the infinite recursion seems to come from EvaluateOnPredecessorEdge, a function that I recently added to support jump threading across two basic blocks. EvaluateOnPredecessorEdge does not have a guard against infinite recursion while its close cousin ComputeValueKnownInPredecessors does.

The best thing to do is to get rid of the code duplication I introduced, namely EvaluateOnPredecessorEdge, but for now we can detect infinite recursion by maintaining RecursionSet much like ComputeValueKnownInPredecessors. Alternatively, we could pass a recursion depth and stop recursion when we reach a certain limit. We have a limit on the number of LLVM IR statements we duplicate, so we could use that as a starting point.

Anyway, let me try to come up with something.

[junparser]

In D75977#1925178, @kazu wrote:

Sorry, the infinite recursion seems to come from EvaluateOnPredecessorEdge, a function that I recently added to support jump threading across two basic blocks. EvaluateOnPredecessorEdge does not have a guard against infinite recursion while its close cousin ComputeValueKnownInPredecessors does.

The best thing to do is to get rid of the code duplication I introduced, namely EvaluateOnPredecessorEdge, but for now we can detect infinite recursion by maintaining RecursionSet much like ComputeValueKnownInPredecessors. Alternatively, we could pass a recursion depth and stop recursion when we reach a certain limit. We have a limit on the number of LLVM IR statements we duplicate, so we could use that as a starting point.

Anyway, let me try to come up with something.

Thanks for the clarification, I'll let you handle this:)

[junparser]

see https://reviews.llvm.org/D76390

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (auto &BB : F) {
             // detect and transform nested loops later.
             !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
             TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU)) {
           RemoveRedundantDbgInstrs(Succ);
           // BB is valid for cleanup here because we passed in DTU. F remains
           // BB's parent until a DTU->getDomTree() event.
           LVI->eraseBlock(&BB);
           Changed = true;
-        }
+          continue;
+        }
+
+      // We may hit cycles, just add it to Unreachable.
+      if (!DTU->getDomTree().isReachableFromEntry(&BB)) {
+        Unreachable.insert(&BB);
+        Changed = true;
       }
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   // Flush only the Dominator Tree.
   DTU->getDomTree();

llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll

 ; RUN: opt -S -jump-threading -verify -o - %s | FileCheck %s
 @a = external global i16, align 1
 
 ; CHECK-LABEL: f
 ; CHECK: bb6:
 ; CHECK: bb2:
 ; CHECK: bb3:
+; CHECK: bb4:
 ; CHECK-NOT: bb0:
 ; CHECK-NOT: bb1:
-; CHECK-NOT: bb4:
 ; CHECK-NOT: bb5:
 define void @f(i32 %p1) {
 bb0:
   %0 = icmp eq i32 %p1, 0
   br i1 undef, label %bb6, label %bb1
 
 bb1:
   br label %bb2

llvm/test/Transforms/JumpThreading/PR44611-across-header-hang.ll

+; RUN: opt -S < %s -jump-threading -jump-threading-across-loop-headers | FileCheck %s
+
+; CHECK-LABEL: @func
+; Just check that we don't hang on this test.
+
+define void @func() {
+bb:
+  %tmp3 = alloca [2 x [3 x [2 x i32]]], align 4
+  br label %bb6
+
+bb6:                                              ; preds = %bb7, %bb
+  %tmp1.0 = phi i32 [ undef, %bb ], [ %tmp1.1, %bb7 ]
+  %tmp2.0 = phi i32 [ undef, %bb ], [ %tmp2.1, %bb7 ]
+  br label %bb7
+
+bb7:                                              ; preds = %bb56, %bb6
+  %tmp1.1 = phi i32 [ %tmp1.0, %bb6 ], [ 1, %bb56 ]
+  %tmp2.1 = phi i32 [ %tmp2.0, %bb6 ], [ %tmp25, %bb56 ]
+  %tmp9 = icmp slt i32 %tmp1.1, 2
+  br i1 %tmp9, label %bb10, label %bb6
+
+bb10:                                             ; preds = %bb7
+  %tmp12 = sext i32 %tmp1.1 to i64
+  %tmp19 = getelementptr inbounds [2 x [3 x [2 x i32]]], [2 x [3 x [2 x i32]]]* %tmp3, i64 0, i64 %tmp12, i64 %tmp12, i64 %tmp12
+  %tmp20 = load i32, i32* %tmp19, align 4
+  %0 = and i32 %tmp20, 1
+  %tmp25 = or i32 %tmp2.1, %0
+  br label %bb27
+
+bb27:                                             ; preds = %bb53, %bb10
+  %tmp.0 = phi i64 [ -3, %bb10 ], [ %tmp55, %bb53 ]
+  %tmp29 = icmp eq i64 %tmp.0, 17
+  br i1 %tmp29, label %bb56, label %bb31
+
+bb31:                                             ; preds = %bb27, %bb34
+  %tmp5.0 = phi i32 [ %tmp36, %bb34 ], [ 0, %bb27 ]
+  %tmp33 = icmp ult i32 %tmp5.0, 6
+  br i1 %tmp33, label %bb34, label %bb37
+
+bb34:                                             ; preds = %bb31
+  %tmp36 = add nuw nsw i32 %tmp5.0, 1
+  br label %bb31
+
+bb37:                                             ; preds = %bb31
+  %tmp48 = icmp eq i32 %tmp20, 0
+  br i1 %tmp48, label %bb53, label %bb56
+
+bb53:                                             ; preds = %bb37
+  %tmp55 = add nsw i64 %tmp.0, 1
+  br label %bb27
+
+bb56:                                             ; preds = %bb27, %bb37
+  br label %bb7
+}
+

llvm/test/Transforms/JumpThreading/removed-use.ll

 ; RUN: opt -S < %s -jump-threading | FileCheck %s
 ; CHECK-LABEL: @foo
 ; CHECK: bb6:
 ; CHECK-NEXT: ret void
 ; CHECK: bb3:
+; CHECK: br i1 %p, label %bb4, label %bb3
+; CHECK: bb4:
 ; CHECK: br label %bb3
+
 define void @foo() {
 entry:
   br i1 true, label %bb6, label %bb3
 
 bb3:
   %x0 = phi i32 [ undef, %entry ], [ %x1, %bb5 ]
   %y  = and i64 undef, 1
   %p  = icmp ne i64 %y, 0
   br i1 %p, label %bb4, label %bb5
 
 bb4:
   br label %bb5
 
 bb5:
   %x1 = phi i32 [ %x0, %bb3 ], [ %x0, %bb4 ]
   %z  = phi i32 [ 0, %bb3 ], [ 1, %bb4 ]
   %q  = icmp eq i32 %z, 0
-  br i1 %q, label %bb3, label %bb6
+  br label %bb3
 
 bb6:
   ret void
 }
 
 ; CHECK-LABEL: @bar
 ; Just check that we don't crash on this test.
 define void @bar(i1 %p) {