[SCEV] Prove implications for SCEVUnknown Phis

This patch teaches SCEV how to prove implications for SCEVUnknown nodes that are Phis.
If we need to prove `Pred` for `LHS, RHS`, and `LHS` is a Phi with possible incoming values
`L1, L2, ..., LN`, then if we prove `Pred` for `(L1, RHS), (L2, RHS), ..., (LN, RHS)` then we can also
prove it for `(LHS, RHS)`. If both `LHS` and `RHS` are Phis from the same block, it is sufficient
to prove the predicate for values that come from the same predecessor block.

The typical case that it handles is that we sometimes need to prove that `Phi(Len, Len - 1) >= 0`
given that `Len > 0`. The new logic was added to `isImpliedViaOperations` and only uses it and
non-recursive reasoning to prove the facts we need, so it should not hurt compile time a lot.

Differential Revision: https://reviews.llvm.org/D44001
Reviewed By: anna

llvm-svn: 329150

1 files changed, 38 insertions, 0 deletions

diff --git a/llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll b/llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll
index 5872e4e03a8..d1712da3a6b 100644
--- a/llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll
+++ b/llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll
@@ -188,5 +188,43 @@ loop:
   br i1 %loopcond, label %loopexit, label %loop
 }
 
+define void @promote_latch_condition_decrementing_loop_04(i32* %p, i32* %a, i1 %cond) {
+
+; CHECK-LABEL: @promote_latch_condition_decrementing_loop_04(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %len.minus.1 = add nsw i32 %len, -1
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %iv_start = phi i32 [ %len, %if.true ], [%len.minus.1, %if.false ]
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %iv_start, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
+  %loopcond = icmp slt i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
 
 !0 = !{i32 0, i32 2147483647}