Check in LLVM r95781.

14 files changed, 370 insertions, 0 deletions

diff --git a/test/Transforms/TailCallElim/accum_recursion.ll b/test/Transforms/TailCallElim/accum_recursion.ll
new file mode 100644
index 0000000..b2a9ed2
--- /dev/null
+++ b/test/Transforms/TailCallElim/accum_recursion.ll
@@ -0,0 +1,15 @@
+; RUN: opt < %s -tailcallelim -S | not grep call
+
+define i32 @factorial(i32 %x) {
+entry:
+	%tmp.1 = icmp sgt i32 %x, 0		; <i1> [#uses=1]
+	br i1 %tmp.1, label %then, label %else
+then:		; preds = %entry
+	%tmp.6 = add i32 %x, -1		; <i32> [#uses=1]
+	%tmp.4 = call i32 @factorial( i32 %tmp.6 )		; <i32> [#uses=1]
+	%tmp.7 = mul i32 %tmp.4, %x		; <i32> [#uses=1]
+	ret i32 %tmp.7
+else:		; preds = %entry
+	ret i32 1
+}
+
diff --git a/test/Transforms/TailCallElim/accum_recursion_constant_arg.ll b/test/Transforms/TailCallElim/accum_recursion_constant_arg.ll
new file mode 100644
index 0000000..2a90cf3
--- /dev/null
+++ b/test/Transforms/TailCallElim/accum_recursion_constant_arg.ll
@@ -0,0 +1,20 @@
+; This is a more aggressive form of accumulator recursion insertion, which 
+; requires noticing that X doesn't change as we perform the tailcall.  Thanks
+; go out to the anonymous users of the demo script for "suggesting" 
+; optimizations that should be done.  :)
+
+; RUN: opt < %s -tailcallelim -S | not grep call
+
+define i32 @mul(i32 %x, i32 %y) {
+entry:
+	%tmp.1 = icmp eq i32 %y, 0		; <i1> [#uses=1]
+	br i1 %tmp.1, label %return, label %endif
+endif:		; preds = %entry
+	%tmp.8 = add i32 %y, -1		; <i32> [#uses=1]
+	%tmp.5 = call i32 @mul( i32 %x, i32 %tmp.8 )		; <i32> [#uses=1]
+	%tmp.9 = add i32 %tmp.5, %x		; <i32> [#uses=1]
+	ret i32 %tmp.9
+return:		; preds = %entry
+	ret i32 %x
+}
+
diff --git a/test/Transforms/TailCallElim/ackermann.ll b/test/Transforms/TailCallElim/ackermann.ll
new file mode 100644
index 0000000..0c140ad
--- /dev/null
+++ b/test/Transforms/TailCallElim/ackermann.ll
@@ -0,0 +1,25 @@
+; This function contains two tail calls, which should be eliminated
+; RUN: opt < %s -tailcallelim -stats -disable-output |& grep {2 tailcallelim}
+
+define i32 @Ack(i32 %M.1, i32 %N.1) {
+entry:
+	%tmp.1 = icmp eq i32 %M.1, 0		; <i1> [#uses=1]
+	br i1 %tmp.1, label %then.0, label %endif.0
+then.0:		; preds = %entry
+	%tmp.4 = add i32 %N.1, 1		; <i32> [#uses=1]
+	ret i32 %tmp.4
+endif.0:		; preds = %entry
+	%tmp.6 = icmp eq i32 %N.1, 0		; <i1> [#uses=1]
+	br i1 %tmp.6, label %then.1, label %endif.1
+then.1:		; preds = %endif.0
+	%tmp.10 = add i32 %M.1, -1		; <i32> [#uses=1]
+	%tmp.8 = call i32 @Ack( i32 %tmp.10, i32 1 )		; <i32> [#uses=1]
+	ret i32 %tmp.8
+endif.1:		; preds = %endif.0
+	%tmp.13 = add i32 %M.1, -1		; <i32> [#uses=1]
+	%tmp.17 = add i32 %N.1, -1		; <i32> [#uses=1]
+	%tmp.14 = call i32 @Ack( i32 %M.1, i32 %tmp.17 )		; <i32> [#uses=1]
+	%tmp.11 = call i32 @Ack( i32 %tmp.13, i32 %tmp.14 )		; <i32> [#uses=1]
+	ret i32 %tmp.11
+}
+
diff --git a/test/Transforms/TailCallElim/dg.exp b/test/Transforms/TailCallElim/dg.exp
new file mode 100644
index 0000000..f200589
--- /dev/null
+++ b/test/Transforms/TailCallElim/dg.exp
@@ -0,0 +1,3 @@
+load_lib llvm.exp
+
+RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]]
diff --git a/test/Transforms/TailCallElim/dont-tce-tail-marked-call.ll b/test/Transforms/TailCallElim/dont-tce-tail-marked-call.ll
new file mode 100644
index 0000000..5cc92e1
--- /dev/null
+++ b/test/Transforms/TailCallElim/dont-tce-tail-marked-call.ll
@@ -0,0 +1,13 @@
+; RUN: opt < %s -tailcallelim -S | \
+; RUN:    grep {call i32 @foo}
+
+declare void @bar(i32*)
+
+define i32 @foo(i32 %N) {
+	%A = alloca i32, i32 %N		; <i32*> [#uses=2]
+	store i32 17, i32* %A
+	call void @bar( i32* %A )
+	%X = tail call i32 @foo( i32 %N )		; <i32> [#uses=1]
+	ret i32 %X
+}
+
diff --git a/test/Transforms/TailCallElim/dont_reorder_load.ll b/test/Transforms/TailCallElim/dont_reorder_load.ll
new file mode 100644
index 0000000..cc273c3
--- /dev/null
+++ b/test/Transforms/TailCallElim/dont_reorder_load.ll
@@ -0,0 +1,64 @@
+; RUN: opt < %s -tailcallelim -S | 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/inf-recursion.ll b/test/Transforms/TailCallElim/inf-recursion.ll
new file mode 100644
index 0000000..a5f246d
--- /dev/null
+++ b/test/Transforms/TailCallElim/inf-recursion.ll
@@ -0,0 +1,10 @@
+; RUN: opt < %s -tailcallelim -S | grep call
+; Don't turn this into an infinite loop, this is probably the implementation
+; of fabs and we expect the codegen to lower fabs.
+
+define double @fabs(double %f) {
+entry:
+        %tmp2 = call double @fabs( double %f )          ; <double> [#uses=1]
+        ret double %tmp2
+}
+
diff --git a/test/Transforms/TailCallElim/intervening-inst.ll b/test/Transforms/TailCallElim/intervening-inst.ll
new file mode 100644
index 0000000..0c40bd5
--- /dev/null
+++ b/test/Transforms/TailCallElim/intervening-inst.ll
@@ -0,0 +1,17 @@
+; This function contains intervening instructions which should be moved out of the way
+; RUN: opt < %s -tailcallelim -S | not grep call
+
+define i32 @Test(i32 %X) {
+entry:
+	%tmp.1 = icmp eq i32 %X, 0		; <i1> [#uses=1]
+	br i1 %tmp.1, label %then.0, label %endif.0
+then.0:		; preds = %entry
+	%tmp.4 = add i32 %X, 1		; <i32> [#uses=1]
+	ret i32 %tmp.4
+endif.0:		; preds = %entry
+	%tmp.10 = add i32 %X, -1		; <i32> [#uses=1]
+	%tmp.8 = call i32 @Test( i32 %tmp.10 )		; <i32> [#uses=1]
+	%DUMMY = add i32 %X, 1		; <i32> [#uses=0]
+	ret i32 %tmp.8
+}
+
diff --git a/test/Transforms/TailCallElim/move_alloca_for_tail_call.ll b/test/Transforms/TailCallElim/move_alloca_for_tail_call.ll
new file mode 100644
index 0000000..a556ddb
--- /dev/null
+++ b/test/Transforms/TailCallElim/move_alloca_for_tail_call.ll
@@ -0,0 +1,15 @@
+; RUN: opt -tailcallelim %s -S | FileCheck %s
+; PR615
+
+declare void @bar(i32*)
+
+define i32 @foo() {
+; CHECK: i32 @foo()
+; CHECK-NEXT: alloca
+	%A = alloca i32		; <i32*> [#uses=2]
+	store i32 17, i32* %A
+	call void @bar( i32* %A )
+	%X = tail call i32 @foo( )		; <i32> [#uses=1]
+	ret i32 %X
+}
+
diff --git a/test/Transforms/TailCallElim/nocapture.ll b/test/Transforms/TailCallElim/nocapture.ll
new file mode 100644
index 0000000..87cb9dd
--- /dev/null
+++ b/test/Transforms/TailCallElim/nocapture.ll
@@ -0,0 +1,25 @@
+; RUN: opt %s -tailcallelim -S | FileCheck %s
+; XFAIL: *
+
+declare void @use(i8* nocapture, i8* nocapture)
+
+define i8* @foo(i8* nocapture %A, i1 %cond) {
+; CHECK: tailrecurse:
+; CHECK: %A.tr = phi i8* [ %A, %0 ], [ %B, %cond_true ]
+; CHECK: %cond.tr = phi i1 [ %cond, %0 ], [ false, %cond_true ]
+  %B = alloca i8
+; CHECK: %B = alloca i8
+  br i1 %cond, label %cond_true, label %cond_false
+; CHECK: br i1 %cond.tr, label %cond_true, label %cond_false
+cond_true:
+; CHECK: cond_true:
+; CHECK: br label %tailrecurse
+  call i8* @foo(i8* %B, i1 false)
+  ret i8* null
+cond_false:
+; CHECK: cond_false
+  call void @use(i8* %A, i8* %B)
+; CHECK: tail call void @use(i8* %A.tr, i8* %B)
+  ret i8* null
+; CHECK: ret i8* null
+}
diff --git a/test/Transforms/TailCallElim/reorder_load.ll b/test/Transforms/TailCallElim/reorder_load.ll
new file mode 100644
index 0000000..7f8af7e
--- /dev/null
+++ b/test/Transforms/TailCallElim/reorder_load.ll
@@ -0,0 +1,101 @@
+; RUN: opt < %s -tailcallelim -S | 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
+}
diff --git a/test/Transforms/TailCallElim/return_constant.ll b/test/Transforms/TailCallElim/return_constant.ll
new file mode 100644
index 0000000..48e5641
--- /dev/null
+++ b/test/Transforms/TailCallElim/return_constant.ll
@@ -0,0 +1,17 @@
+; Though this case seems to be fairly unlikely to occur in the wild, someone
+; plunked it into the demo script, so maybe they care about it.
+;
+; RUN: opt < %s -tailcallelim -S | not grep call
+
+define i32 @aaa(i32 %c) {
+entry:
+	%tmp.1 = icmp eq i32 %c, 0		; <i1> [#uses=1]
+	br i1 %tmp.1, label %return, label %else
+else:		; preds = %entry
+	%tmp.5 = add i32 %c, -1		; <i32> [#uses=1]
+	%tmp.3 = call i32 @aaa( i32 %tmp.5 )		; <i32> [#uses=0]
+	ret i32 0
+return:		; preds = %entry
+	ret i32 0
+}
+
diff --git a/test/Transforms/TailCallElim/switch.ll b/test/Transforms/TailCallElim/switch.ll
new file mode 100644
index 0000000..3388431
--- /dev/null
+++ b/test/Transforms/TailCallElim/switch.ll
@@ -0,0 +1,34 @@
+; RUN: opt %s -tailcallelim -S | FileCheck %s
+
+define i64 @fib(i64 %n) nounwind readnone {
+; CHECK: @fib
+entry:
+; CHECK: tailrecurse:
+; CHECK: %accumulator.tr = phi i64 [ %n, %entry ], [ %3, %bb1 ]
+; CHECK: %n.tr = phi i64 [ %n, %entry ], [ %2, %bb1 ]
+  switch i64 %n, label %bb1 [
+; CHECK: switch i64 %n.tr, label %bb1 [
+    i64 0, label %bb2
+    i64 1, label %bb2
+  ]
+
+bb1:
+; CHECK: bb1:
+  %0 = add i64 %n, -1
+; CHECK: %0 = add i64 %n.tr, -1
+  %1 = tail call i64 @fib(i64 %0) nounwind
+; CHECK: %1 = tail call i64 @fib(i64 %0)
+  %2 = add i64 %n, -2
+; CHECK: %2 = add i64 %n.tr, -2
+  %3 = tail call i64 @fib(i64 %2) nounwind
+; CHECK-NOT: tail call i64 @fib
+  %4 = add nsw i64 %3, %1
+; CHECK: add nsw i64 %accumulator.tr, %1
+  ret i64 %4
+; CHECK: br label %tailrecurse
+
+bb2:
+; CHECK: bb2:
+  ret i64 %n
+; CHECK: ret i64 %accumulator.tr
+}
diff --git a/test/Transforms/TailCallElim/trivial_codegen_tailcall.ll b/test/Transforms/TailCallElim/trivial_codegen_tailcall.ll
new file mode 100644
index 0000000..3dddb01
--- /dev/null
+++ b/test/Transforms/TailCallElim/trivial_codegen_tailcall.ll
@@ -0,0 +1,11 @@
+; RUN: opt < %s -tailcallelim -S | \
+; RUN:    grep {tail call void @foo}
+
+
+declare void @foo()
+
+define void @bar() {
+	call void @foo( )
+	ret void
+}
+