[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

2 files changed, 181 insertions, 0 deletions

diff --git a/llvm/test/Transforms/IRCE/decrementing-loop.ll b/llvm/test/Transforms/IRCE/decrementing-loop.ll
index d72813844fd..4c82cd3e341 100644
--- a/llvm/test/Transforms/IRCE/decrementing-loop.ll
+++ b/llvm/test/Transforms/IRCE/decrementing-loop.ll
@@ -119,5 +119,148 @@ define void @test_02(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
   ret void
 }
 
+; Check that we can figure out that IV is non-negative via implication through
+; Phi node.
+define void @test_03(i32* %a, i32* %a_len_ptr, i1 %cond) {
+
+; CHECK-LABEL: test_03
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.minus.one = sub nsw i32 %len.a, 1
+  %len.minus.two = sub nsw i32 %len.a, 2
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
+  %first.itr.check = icmp sgt i32 %len.a, 3
+  br i1 %first.itr.check, label %loop, label %exit
+
+loop:
+  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rc = icmp ult i32 %idx.next, %len.a
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %v = load i32, i32* %el.a
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; Check that we can figure out that IV is non-negative via implication through
+; two Phi nodes.
+define void @test_04(i32* %a, i32* %a_len_ptr, i1 %cond) {
+
+; CHECK-LABEL: test_04
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.minus.one = sub nsw i32 %len.a, 1
+  %len.plus.one = add nsw i32 %len.a, 1
+  %len.minus.two = sub nsw i32 %len.a, 2
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
+  %len.phi = phi i32 [ %len.a, %if.true ], [ %len.plus.one, %if.false ]
+  %first.itr.check = icmp sgt i32 %len.a, 3
+  br i1 %first.itr.check, label %loop, label %exit
+
+loop:
+  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rc = icmp ult i32 %idx.next, %len.phi
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %v = load i32, i32* %el.a
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; Check that we can figure out that IV is non-negative via implication through
+; two Phi nodes, one being AddRec.
+define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {
+
+; CHECK-LABEL: test_05
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.minus.one = sub nsw i32 %len.a, 1
+  %len.plus.one = add nsw i32 %len.a, 1
+  %len.minus.two = sub nsw i32 %len.a, 2
+  br label %merge
+
+merge:
+  %starting.value = phi i32 [ %len.minus.two, %entry ], [ %len.minus.one, %merge ]
+  %len.phi = phi i32 [ %len.a, %entry ], [ %len.phi.next, %merge ]
+  %len.phi.next = add nsw i32 %len.phi, 1
+  br i1 true, label %first.iter.check, label %merge
+
+first.iter.check:
+  %first.itr.check = icmp sgt i32 %len.a, 3
+  br i1 %first.itr.check, label %loop, label %exit
+
+loop:
+  %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rc = icmp ult i32 %idx.next, %len.phi
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %v = load i32, i32* %el.a
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
 !0 = !{i32 0, i32 2147483647}
 !1 = !{!"branch_weights", i32 64, i32 4}
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}