[SCEV] Re-land: Fix isKnownPredicate

This is re-land of https://reviews.llvm.org/rL327362 with a fix
and regression test.

The crash was due to it is possible that for found MDL loop,
LHS or RHS may contain an invariant unknown SCEV which
does not dominate the MDL. Please see regression
test for an example.

Reviewers: sanjoy, mkazantsev, reames
Reviewed By: mkazantsev
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D44553

llvm-svn: 327822

2 files changed, 74 insertions, 0 deletions

diff --git a/llvm/test/Analysis/ScalarEvolution/inner-loop-by-latch-cond-unknown.ll b/llvm/test/Analysis/ScalarEvolution/inner-loop-by-latch-cond-unknown.ll
new file mode 100644
index 00000000000..cf75d1fb8cf
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/inner-loop-by-latch-cond-unknown.ll
@@ -0,0 +1,39 @@
+; RUN: opt < %s -analyze -iv-users -S | FileCheck %s
+
+; This is a regression test for the commit rL327362.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test(i64 %a, i64* %p) {
+entry:
+  br label %first_loop
+
+first_loop:
+  %i = phi i64 [20, %entry], [%i.next, %first_loop]
+  %i.next = add nuw nsw i64 %i, 1
+  %cond1 = icmp ult i64 %i.next, %a
+  br i1 %cond1, label %first_loop, label %middle_block
+
+middle_block:
+  %b = load i64, i64* %p
+  %cmp = icmp ult i64 %i, %b
+; When SCEV will try to compute the initial value for %j
+; it will observe umax generated by this select.
+; When it will try to simplify this umax it will invoke
+; isKnownPredicate with AddRec for %i and unknown SCEV for %b.
+; As a result we find MDL == first_loop where %b is not available
+; at loop entry.
+; CHECK: IV Users for loop %second_loop with backedge-taken count{{.*}}umax
+  %s = select i1 %cmp, i64 %i, i64 %b
+  br label %second_loop
+
+second_loop:
+  %j = phi i64 [%s, %middle_block], [%j.next, %second_loop]
+  %j.next = add nuw nsw i64 %j, 1
+  %cond2 = icmp ult i64 %j.next, 100
+  br i1 %cond2, label %second_loop, label %return
+
+return:
+  ret void
+}
diff --git a/llvm/test/Transforms/IndVarSimplify/inner-loop-by-latch-cond.ll b/llvm/test/Transforms/IndVarSimplify/inner-loop-by-latch-cond.ll
new file mode 100644
index 00000000000..1e0c0ddef85
--- /dev/null
+++ b/llvm/test/Transforms/IndVarSimplify/inner-loop-by-latch-cond.ll
@@ -0,0 +1,35 @@
+; RUN: opt < %s -indvars -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @foo(i64)
+
+; CHECK-LABEL: @test
+define void @test(i64 %a) {
+entry:
+  br label %outer_header
+
+outer_header:
+  %i = phi i64 [20, %entry], [%i.next, %outer_latch]
+  %i.next = add nuw nsw i64 %i, 1
+  br label %inner_header
+
+inner_header:
+  %j = phi i64 [1, %outer_header], [%j.next, %inner_header]
+  %cmp = icmp ult i64 %j, %i.next
+; CHECK-NOT: select
+  %s = select i1 %cmp, i64 %j, i64 %i
+; CHECK: call void @foo(i64 %j)
+  call void @foo(i64 %s)
+  %j.next = add nuw nsw i64 %j, 1
+  %cond = icmp ult i64 %j, %i
+  br i1 %cond, label %inner_header, label %outer_latch
+
+outer_latch:
+  %cond2 = icmp ne i64 %i.next, 40
+  br i1 %cond2, label %outer_header, label %return
+
+return:
+  ret void
+}