From a1af757e0af9c2fb5ade4b06408e1adfa0425c6c Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Thu, 30 Apr 2009 20:47:05 +0000 Subject: 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 --- .../Analysis/ScalarEvolution/2008-11-18-Stride1.ll | 1 - test/Analysis/ScalarEvolution/max-trip-count.ll | 32 ++++++++++ test/Analysis/ScalarEvolution/trip-count3.ll | 74 ++++++++++++++++++++++ 3 files changed, 106 insertions(+), 1 deletion(-) create mode 100644 test/Analysis/ScalarEvolution/max-trip-count.ll create mode 100644 test/Analysis/ScalarEvolution/trip-count3.ll (limited to 'test') 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\}} + +define void @foo(i32* nocapture %d, i32 %n) nounwind { +entry: + %0 = icmp sgt i32 %n, 0 ; [#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 ] ; [#uses=2] + %p.01 = phi i8 [ %4, %bb1 ], [ -1, %bb.nph ] ; [#uses=2] + %1 = sext i8 %p.01 to i32 ; [#uses=1] + %2 = sext i32 %i.02 to i64 ; [#uses=1] + %3 = getelementptr i32* %d, i64 %2 ; [#uses=1] + store i32 %1, i32* %3, align 4 + %4 = add i8 %p.01, 1 ; [#uses=1] + %5 = add i32 %i.02, 1 ; [#uses=2] + br label %bb1 + +bb1: ; preds = %bb + %6 = icmp slt i32 %5, %n ; [#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* ; [#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 ; [#uses=1] + %4 = bitcast i32* %3 to 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 ; [#uses=1] + %6 = add i32 %count_addr.0.i, -64 ; [#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 ] ; [#uses=3] + %count_addr.0.i = phi i32 [ %0, %newFuncRoot ], [ %6, %byte_reverse.exit.i ] ; [#uses=3] + %7 = icmp sgt i32 %count_addr.0.i, 63 ; [#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 -- cgit v1.1