[JumpThreading] Fix exponential time algorithm computing known values.

ComputeValueKnownInPredecessors has a "visited" set to prevent infinite
loops, since a value can be visited more than once.  However, the
implementation didn't prevent the algorithm from taking exponential
time. Instead of removing elements from the RecursionSet one at a time,
we should keep around the whole set until
ComputeValueKnownInPredecessors finishes, then discard it.

The testcase is synthetic because I was having trouble effectively
reducing the original.  But it's basically the same idea.

Instead of failing, we could theoretically cache the result instead.
But I don't think it would help substantially in practice.

Differential Revision: https://reviews.llvm.org/D54239

llvm-svn: 346562

1 files changed, 61 insertions, 1 deletions

diff --git a/llvm/test/Transforms/JumpThreading/crash.ll b/llvm/test/Transforms/JumpThreading/crash.ll
index 900a7738d3b..01bec4b2c2d 100644
--- a/llvm/test/Transforms/JumpThreading/crash.ll
+++ b/llvm/test/Transforms/JumpThreading/crash.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -jump-threading -disable-output
+; RUN: opt < %s -jump-threading -S | FileCheck %s
 ; PR2285
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 target triple = "x86_64-unknown-linux-gnu"
@@ -564,3 +564,63 @@ ur:
 declare i8* @PR14233.f1()
 
 declare i8* @PR14233.f2()
+
+; Make sure the following compiles in a sane amount of time, as opposed
+; to taking exponential time.
+; (CHECK to make sure the condition doesn't get simplified somehow;
+; if it does, the testcase will need to be revised.)
+; CHECK-LABEL: define void @almost_infinite_loop
+; CHECK: %x39 = or i1 %x38, %x38
+; CHECK: br i1 %x39, label %dest1, label %dest2
+define void @almost_infinite_loop(i1 %x0) {
+entry:
+  br label %if.then57.i
+
+if.then57.i:
+  %x1 = or i1 %x0, %x0
+  %x2 = or i1 %x1, %x1
+  %x3 = or i1 %x2, %x2
+  %x4 = or i1 %x3, %x3
+  %x5 = or i1 %x4, %x4
+  %x6 = or i1 %x5, %x5
+  %x7 = or i1 %x6, %x6
+  %x8 = or i1 %x7, %x7
+  %x9 = or i1 %x8, %x8
+  %x10 = or i1 %x9, %x9
+  %x11 = or i1 %x10, %x10
+  %x12 = or i1 %x11, %x11
+  %x13 = or i1 %x12, %x12
+  %x14 = or i1 %x13, %x13
+  %x15 = or i1 %x14, %x14
+  %x16 = or i1 %x15, %x15
+  %x17 = or i1 %x16, %x16
+  %x18 = or i1 %x17, %x17
+  %x19 = or i1 %x18, %x18
+  %x20 = or i1 %x19, %x19
+  %x21 = or i1 %x20, %x20
+  %x22 = or i1 %x21, %x21
+  %x23 = or i1 %x22, %x22
+  %x24 = or i1 %x23, %x23
+  %x25 = or i1 %x24, %x24
+  %x26 = or i1 %x25, %x25
+  %x27 = or i1 %x26, %x26
+  %x28 = or i1 %x27, %x27
+  %x29 = or i1 %x28, %x28
+  %x30 = or i1 %x29, %x29
+  %x31 = or i1 %x30, %x30
+  %x32 = or i1 %x31, %x31
+  %x33 = or i1 %x32, %x32
+  %x34 = or i1 %x33, %x33
+  %x35 = or i1 %x34, %x34
+  %x36 = or i1 %x35, %x35
+  %x37 = or i1 %x36, %x36
+  %x38 = or i1 %x37, %x37
+  %x39 = or i1 %x38, %x38
+  br i1 %x39, label %dest1, label %dest2
+
+dest1:
+  unreachable
+
+dest2:
+  unreachable
+}