diff options
author | Chris Lattner <sabre@nondot.org> | 2009-06-19 04:22:16 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2009-06-19 04:22:16 +0000 |
commit | 6a35b40250735a50efe66c88414cdd3b79185019 (patch) | |
tree | 85715b813e7c1a087961d5f6fc115641ef431279 /test/Transforms/TailCallElim | |
parent | 849832c0fb47f4e111840e0031b9129d41ffb389 (diff) | |
download | llvm-6a35b40250735a50efe66c88414cdd3b79185019.tar.gz llvm-6a35b40250735a50efe66c88414cdd3b79185019.tar.bz2 llvm-6a35b40250735a50efe66c88414cdd3b79185019.tar.xz |
Improve tail call elim to move loads above readonly calls
when it allows forming a tail call. Patch by Frits van
Bommel. This implements PR4323.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73752 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'test/Transforms/TailCallElim')
-rw-r--r-- | test/Transforms/TailCallElim/dont_reorder_load.ll | 64 | ||||
-rw-r--r-- | test/Transforms/TailCallElim/reorder_load.ll | 101 |
2 files changed, 165 insertions, 0 deletions
diff --git a/test/Transforms/TailCallElim/dont_reorder_load.ll b/test/Transforms/TailCallElim/dont_reorder_load.ll new file mode 100644 index 0000000000..8fbe008387 --- /dev/null +++ b/test/Transforms/TailCallElim/dont_reorder_load.ll @@ -0,0 +1,64 @@ +; RUN: llvm-as <%s | opt -tailcallelim | llvm-dis | grep call | count 3 +; PR4323 + +; Several cases where tail call elimination should not move the load above the +; call, and thus can't eliminate the tail recursion. + + +@extern_weak_global = extern_weak global i32 ; <i32*> [#uses=1] + + +; This load can't be safely moved above the call because the load is from an +; extern_weak global and may trap, but the call may unwind before that happens. +define fastcc i32 @no_tailrecelim_1(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) readonly { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + unwind + +else: ; preds = %entry + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @no_tailrecelim_1(i32* %a_arg, i32 %a_len_arg, i32 %tmp7) ; <i32> [#uses=1] + %tmp9 = load i32* @extern_weak_global ; <i32> [#uses=1] + %tmp10 = add i32 %tmp9, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} + + +; This load can't be safely moved above the call because function may write to the pointer. +define fastcc i32 @no_tailrecelim_2(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) nounwind { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + store i32 1, i32* %a_arg; + ret i32 0; + +else: ; preds = %entry + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @no_tailrecelim_2(i32* %a_arg, i32 %a_len_arg, i32 %tmp7) ; <i32> [#uses=1] + %tmp9 = load i32* %a_arg ; <i32> [#uses=1] + %tmp10 = add i32 %tmp9, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} + +; This load can't be safely moved above the call because that would change the +; order in which the volatile loads are performed. +define fastcc i32 @no_tailrecelim_3(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) nounwind { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + ret i32 0; + +else: ; preds = %entry + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @no_tailrecelim_3(i32* %a_arg, i32 %a_len_arg, i32 %tmp7) ; <i32> [#uses=1] + %tmp9 = volatile load i32* %a_arg ; <i32> [#uses=1] + %tmp10 = add i32 %tmp9, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} diff --git a/test/Transforms/TailCallElim/reorder_load.ll b/test/Transforms/TailCallElim/reorder_load.ll new file mode 100644 index 0000000000..aeb9042bc7 --- /dev/null +++ b/test/Transforms/TailCallElim/reorder_load.ll @@ -0,0 +1,101 @@ +; RUN: llvm-as <%s | opt -tailcallelim | llvm-dis | not grep call +; PR4323 + +; Several cases where tail call elimination should move the load above the call, +; then eliminate the tail recursion. + + +@global = external global i32 ; <i32*> [#uses=1] +@extern_weak_global = extern_weak global i32 ; <i32*> [#uses=1] + + +; This load can be moved above the call because the function won't write to it +; and the call has no side effects. +define fastcc i32 @raise_load_1(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) nounwind readonly { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + ret i32 0 + +else: ; preds = %entry + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @raise_load_1(i32* %a_arg, i32 %a_len_arg, i32 %tmp7) ; <i32> [#uses=1] + %tmp9 = load i32* %a_arg ; <i32> [#uses=1] + %tmp10 = add i32 %tmp9, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} + + +; This load can be moved above the call because the function won't write to it +; and the load provably can't trap. +define fastcc i32 @raise_load_2(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) readonly { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + ret i32 0 + +else: ; preds = %entry + %nullcheck = icmp eq i32* %a_arg, null ; <i1> [#uses=1] + br i1 %nullcheck, label %unwind, label %recurse + +unwind: ; preds = %else + unwind + +recurse: ; preds = %else + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @raise_load_2(i32* %a_arg, i32 %a_len_arg, i32 %tmp7) ; <i32> [#uses=1] + %tmp9 = load i32* @global ; <i32> [#uses=1] + %tmp10 = add i32 %tmp9, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} + + +; This load can be safely moved above the call (even though it's from an +; extern_weak global) because the call has no side effects. +define fastcc i32 @raise_load_3(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) nounwind readonly { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + ret i32 0 + +else: ; preds = %entry + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @raise_load_3(i32* %a_arg, i32 %a_len_arg, i32 %tmp7) ; <i32> [#uses=1] + %tmp9 = load i32* @extern_weak_global ; <i32> [#uses=1] + %tmp10 = add i32 %tmp9, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} + + +; The second load can be safely moved above the call even though it's from an +; unknown pointer (which normally means it might trap) because the first load +; proves it doesn't trap. +define fastcc i32 @raise_load_4(i32* %a_arg, i32 %a_len_arg, i32 %start_arg) readonly { +entry: + %tmp2 = icmp sge i32 %start_arg, %a_len_arg ; <i1> [#uses=1] + br i1 %tmp2, label %if, label %else + +if: ; preds = %entry + ret i32 0 + +else: ; preds = %entry + %nullcheck = icmp eq i32* %a_arg, null ; <i1> [#uses=1] + br i1 %nullcheck, label %unwind, label %recurse + +unwind: ; preds = %else + unwind + +recurse: ; preds = %else + %tmp7 = add i32 %start_arg, 1 ; <i32> [#uses=1] + %first = load i32* %a_arg ; <i32> [#uses=1] + %tmp8 = call fastcc i32 @raise_load_4(i32* %a_arg, i32 %first, i32 %tmp7) ; <i32> [#uses=1] + %second = load i32* %a_arg ; <i32> [#uses=1] + %tmp10 = add i32 %second, %tmp8 ; <i32> [#uses=1] + ret i32 %tmp10 +} |