Extend ScalarEvolution's getBackedgeTakenCount to be able to

compute an upper-bound value for the trip count, in addition to
the actual trip count. Use this to allow getZeroExtendExpr and
getSignExtendExpr to fold casts in more cases.

This may eventually morph into a more general value-range
analysis capability; there are certainly plenty of places where
more complete value-range information would allow more folding.


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

3 files changed, 106 insertions, 1 deletions

diff --git a/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll b/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll
index ac746e2..78cda0e 100644
--- a/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll
+++ b/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll
@@ -1,5 +1,4 @@
 ; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& grep {/u 3}
-; XFAIL: *
 
 define i32 @f(i32 %x) nounwind readnone {
 entry:
diff --git a/test/Analysis/ScalarEvolution/max-trip-count.ll b/test/Analysis/ScalarEvolution/max-trip-count.ll
new file mode 100644
index 0000000..ab88f13
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/max-trip-count.ll
@@ -0,0 +1,32 @@
+; RUN: llvm-as < %s | opt -analyze -scalar-evolution -disable-output \
+; RUN:   | grep {\{(ptrtoint i32\\* %d to iPTR),+,4\}<bb>}
+
+define void @foo(i32* nocapture %d, i32 %n) nounwind {
+entry:
+	%0 = icmp sgt i32 %n, 0		; <i1> [#uses=1]
+	br i1 %0, label %bb.nph, label %return
+
+bb.nph:		; preds = %entry
+	br label %bb
+
+bb:		; preds = %bb1, %bb.nph
+	%i.02 = phi i32 [ %5, %bb1 ], [ 0, %bb.nph ]		; <i32> [#uses=2]
+	%p.01 = phi i8 [ %4, %bb1 ], [ -1, %bb.nph ]		; <i8> [#uses=2]
+	%1 = sext i8 %p.01 to i32		; <i32> [#uses=1]
+	%2 = sext i32 %i.02 to i64		; <i64> [#uses=1]
+	%3 = getelementptr i32* %d, i64 %2		; <i32*> [#uses=1]
+	store i32 %1, i32* %3, align 4
+	%4 = add i8 %p.01, 1		; <i8> [#uses=1]
+	%5 = add i32 %i.02, 1		; <i32> [#uses=2]
+	br label %bb1
+
+bb1:		; preds = %bb
+	%6 = icmp slt i32 %5, %n		; <i1> [#uses=1]
+	br i1 %6, label %bb, label %bb1.return_crit_edge
+
+bb1.return_crit_edge:		; preds = %bb1
+	br label %return
+
+return:		; preds = %bb1.return_crit_edge, %entry
+	ret void
+}
diff --git a/test/Analysis/ScalarEvolution/trip-count3.ll b/test/Analysis/ScalarEvolution/trip-count3.ll
new file mode 100644
index 0000000..a95138f
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/trip-count3.ll
@@ -0,0 +1,74 @@
+; RUN: llvm-as < %s | opt -scalar-evolution -analyze -disable-output \
+; RUN:  | grep {backedge-taken count is ((64 + (-64 smax (-1 + (-1 \\* %0))) + %0) /u 64)}
+
+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"
+target triple = "x86_64-unknown-linux-gnu"
+	%struct.FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct.FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
+	%struct.SHA_INFO = type { [5 x i32], i32, i32, [16 x i32] }
+	%struct._IO_marker = type { %struct._IO_marker*, %struct.FILE*, i32 }
+@_2E_str = external constant [26 x i8]		; <[26 x i8]*> [#uses=0]
+@stdin = external global %struct.FILE*		; <%struct.FILE**> [#uses=0]
+@_2E_str1 = external constant [3 x i8]		; <[3 x i8]*> [#uses=0]
+@_2E_str12 = external constant [30 x i8]		; <[30 x i8]*> [#uses=0]
+
+declare void @sha_init(%struct.SHA_INFO* nocapture) nounwind
+
+declare fastcc void @sha_transform(%struct.SHA_INFO* nocapture) nounwind
+
+declare void @sha_print(%struct.SHA_INFO* nocapture) nounwind
+
+declare i32 @printf(i8* nocapture, ...) nounwind
+
+declare void @sha_final(%struct.SHA_INFO* nocapture) nounwind
+
+declare void @llvm.memset.i64(i8* nocapture, i8, i64, i32) nounwind
+
+declare void @sha_update(%struct.SHA_INFO* nocapture, i8* nocapture, i32) nounwind
+
+declare void @llvm.memcpy.i64(i8* nocapture, i8* nocapture, i64, i32) nounwind
+
+declare i64 @fread(i8* noalias nocapture, i64, i64, %struct.FILE* noalias nocapture) nounwind
+
+declare i32 @main(i32, i8** nocapture) nounwind
+
+declare noalias %struct.FILE* @fopen(i8* noalias nocapture, i8* noalias nocapture) nounwind
+
+declare i32 @fclose(%struct.FILE* nocapture) nounwind
+
+declare void @sha_stream(%struct.SHA_INFO* nocapture, %struct.FILE* nocapture) nounwind
+
+define void @sha_stream_bb3_2E_i(%struct.SHA_INFO* %sha_info, i8* %data1, i32, i8** %buffer_addr.0.i.out, i32* %count_addr.0.i.out) nounwind {
+newFuncRoot:
+	br label %bb3.i
+
+sha_update.exit.exitStub:		; preds = %bb3.i
+	store i8* %buffer_addr.0.i, i8** %buffer_addr.0.i.out
+	store i32 %count_addr.0.i, i32* %count_addr.0.i.out
+	ret void
+
+bb2.i:		; preds = %bb3.i
+	%1 = getelementptr %struct.SHA_INFO* %sha_info, i64 0, i32 3		; <[16 x i32]*> [#uses=1]
+	%2 = bitcast [16 x i32]* %1 to i8*		; <i8*> [#uses=1]
+	call void @llvm.memcpy.i64(i8* %2, i8* %buffer_addr.0.i, i64 64, i32 1) nounwind
+	%3 = getelementptr %struct.SHA_INFO* %sha_info, i64 0, i32 3, i64 0		; <i32*> [#uses=1]
+	%4 = bitcast i32* %3 to i8*		; <i8*> [#uses=1]
+	br label %codeRepl
+
+codeRepl:		; preds = %bb2.i
+	call void @sha_stream_bb3_2E_i_bb1_2E_i_2E_i(i8* %4)
+	br label %byte_reverse.exit.i
+
+byte_reverse.exit.i:		; preds = %codeRepl
+	call fastcc void @sha_transform(%struct.SHA_INFO* %sha_info) nounwind
+	%5 = getelementptr i8* %buffer_addr.0.i, i64 64		; <i8*> [#uses=1]
+	%6 = add i32 %count_addr.0.i, -64		; <i32> [#uses=1]
+	br label %bb3.i
+
+bb3.i:		; preds = %byte_reverse.exit.i, %newFuncRoot
+	%buffer_addr.0.i = phi i8* [ %data1, %newFuncRoot ], [ %5, %byte_reverse.exit.i ]		; <i8*> [#uses=3]
+	%count_addr.0.i = phi i32 [ %0, %newFuncRoot ], [ %6, %byte_reverse.exit.i ]		; <i32> [#uses=3]
+	%7 = icmp sgt i32 %count_addr.0.i, 63		; <i1> [#uses=1]
+	br i1 %7, label %bb2.i, label %sha_update.exit.exitStub
+}
+
+declare void @sha_stream_bb3_2E_i_bb1_2E_i_2E_i(i8*) nounwind