[SCEV] Make computeExitLimit more simple and more powerful

Current implementation of `computeExitLimit` has a big piece of code
the only purpose of which is to prove that after the execution of this
block the latch will be executed. What it currently checks is actually a
subset of situations where the exiting block dominates latch.

This patch replaces all these checks for simple particular cases with
domination check over loop's latch which is the only necessary condition
of taking the exiting block into consideration. This change allows to
calculate exact loop taken count for simple loops like

  for (int i = 0; i < 100; i++) {
    if (cond) {...} else {...}
    if (i > 50) break;
    . . .
  }

Differential Revision: https://reviews.llvm.org/D44677
Reviewed By: efriedma

llvm-svn: 329047

1 files changed, 34 insertions, 0 deletions

diff --git a/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll b/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll
index ba0bc1f4cf3..443da146e77 100644
--- a/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll
+++ b/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll
@@ -25,3 +25,37 @@ exit:
 side.exit:
   ret void
 }
+
+define void @test_02(i1 %c) {
+
+; CHECK-LABEL: Determining loop execution counts for: @test_02
+; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is 50
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %side.cond = icmp slt i32 %iv, 50
+  br i1 %side.cond, label %backedge, label %side.exit
+
+backedge:
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp slt i32 %iv, 100
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+
+side.exit:
+  ret void
+}