Fix the the ceiling-division used in computing the MaxBECount so that it doesn't

have trouble with an intermediate add overflowing. Also, be more conservative
about the case where the induction variable in an SLT loop exit can step past
the RHS of the SLT and overflow in a single step.

Make getSignedRange more aggressive, to recover for some common cases which
the above fixes pessimized.

This addresses rdar://7561161.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94512 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 411 insertions, 2 deletions

diff --git a/test/Analysis/ScalarEvolution/nsw-offset.ll b/test/Analysis/ScalarEvolution/nsw-offset.ll
index fd0dfe66ae..ed97de6a50 100644
--- a/test/Analysis/ScalarEvolution/nsw-offset.ll
+++ b/test/Analysis/ScalarEvolution/nsw-offset.ll
@@ -6,8 +6,9 @@
 
 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"
 
-define void @foo(i32 %n, double* nocapture %d, double* nocapture %q) nounwind {
+define void @foo(i32 %no, double* nocapture %d, double* nocapture %q) nounwind {
 entry:
+  %n = and i32 %no, 4294967294
   %0 = icmp sgt i32 %n, 0                         ; <i1> [#uses=1]
   br i1 %0, label %bb.nph, label %return
 
@@ -73,4 +74,4 @@ return:                                           ; preds = %bb1.return_crit_edg
 }
 
 ; CHECK: Loop %bb: backedge-taken count is ((-1 + %n) /u 2)
-; CHECK: Loop %bb: max backedge-taken count is 1073741823
+; CHECK: Loop %bb: max backedge-taken count is 1073741822
diff --git a/test/Analysis/ScalarEvolution/trip-count9.ll b/test/Analysis/ScalarEvolution/trip-count9.ll
new file mode 100644
index 0000000000..9180f2b8dd
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/trip-count9.ll
@@ -0,0 +1,408 @@
+; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s
+
+; Every combination of
+;  - starting at 0, 1, or %x
+;  - steping by 1 or 2
+;  - stopping at %n or %n*2
+;  - using nsw, or not
+
+; Some of these represent missed opportunities.
+
+; CHECK: Determining loop execution counts for: @foo
+; CHECK: Loop %loop: backedge-taken count is (-1 + %n)
+; CHECK: Loop %loop: max backedge-taken count is 6
+define void @foo(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 1
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: Unpredictable max backedge-taken count. 
+define void @step2(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 2
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @start1
+; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
+; CHECK: Loop %loop: max backedge-taken count is 5
+define void @start1(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 1
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @start1_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: Unpredictable max backedge-taken count. 
+define void @start1_step2(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 2
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @startx
+; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
+; CHECK: Loop %loop: max backedge-taken count is -1
+define void @startx(i4 %n, i4 %x) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 1
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @startx_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: Unpredictable max backedge-taken count. 
+define void @startx_step2(i4 %n, i4 %x) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 2
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @nsw
+; CHECK: Loop %loop: backedge-taken count is (-1 + %n)
+; CHECK: Loop %loop: max backedge-taken count is 6
+define void @nsw(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 1
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; Be careful with this one. If %n is INT4_MAX, %i.next will wrap. The nsw bit
+; says that the result is undefined, but ScalarEvolution must respect that
+; subsequent passes may result the undefined behavior in predictable ways.
+; CHECK: Determining loop execution counts for: @nsw_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: Unpredictable max backedge-taken count. 
+define void @nsw_step2(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 2
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @nsw_start1
+; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
+; CHECK: Loop %loop: max backedge-taken count is 5
+define void @nsw_start1(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 1
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @nsw_start1_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: Unpredictable max backedge-taken count. 
+define void @nsw_start1_step2(i4 %n) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 2
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @nsw_startx
+; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
+; CHECK: Loop %loop: max backedge-taken count is -1
+define void @nsw_startx(i4 %n, i4 %x) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 1
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @nsw_startx_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: Unpredictable max backedge-taken count. 
+define void @nsw_startx_step2(i4 %n, i4 %x) {
+entry:
+  %s = icmp sgt i4 %n, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 2
+  %t = icmp slt i4 %i.next, %n
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even
+; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
+; CHECK: Loop %loop: max backedge-taken count is 5
+define void @even(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 1
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: max backedge-taken count is 2
+define void @even_step2(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 2
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_start1
+; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
+; CHECK: Loop %loop: max backedge-taken count is 4
+define void @even_start1(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 1
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_start1_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: max backedge-taken count is 2
+define void @even_start1_step2(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 2
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_startx
+; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
+; CHECK: Loop %loop: max backedge-taken count is -1
+define void @even_startx(i4 %n, i4 %x) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 1
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_startx_step2
+; CHECK: Loop %loop: Unpredictable backedge-taken count. 
+; CHECK: Loop %loop: max backedge-taken count is 7
+define void @even_startx_step2(i4 %n, i4 %x) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add i4 %i, 2
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_nsw
+; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
+; CHECK: Loop %loop: max backedge-taken count is 5
+define void @even_nsw(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 1
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_nsw_step2
+; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)
+; CHECK: Loop %loop: max backedge-taken count is 2
+define void @even_nsw_step2(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 2
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_nsw_start1
+; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
+; CHECK: Loop %loop: max backedge-taken count is 4
+define void @even_nsw_start1(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 1
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_nsw_start1_step2
+; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2)
+; CHECK: Loop %loop: max backedge-taken count is 2
+define void @even_nsw_start1_step2(i4 %n) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 2
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_nsw_startx
+; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
+; CHECK: Loop %loop: max backedge-taken count is -1
+define void @even_nsw_startx(i4 %n, i4 %x) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 1
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}
+
+; CHECK: Determining loop execution counts for: @even_nsw_startx_step2
+; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
+; CHECK: Loop %loop: max backedge-taken count is 7
+define void @even_nsw_startx_step2(i4 %n, i4 %x) {
+entry:
+  %m = shl i4 %n, 1
+  %s = icmp sgt i4 %m, 0
+  br i1 %s, label %loop, label %exit
+loop:
+  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i4 %i, 2
+  %t = icmp slt i4 %i.next, %m
+  br i1 %t, label %loop, label %exit
+exit:
+  ret void
+}