[LLVMdev] Query on optimization and tail call.

[Mahadevan R]

Hi,

While playing around on the LLVM, I tried this code:

int sum(int n)
{
    if (n == 0)
      return 0;
    else
      return n + sum(n-1);
}

and this is what "llvm-gcc -O2" gave me:

define i32 @sum(i32 %n) nounwind  {
entry:
	%tmp215 = icmp eq i32 %n, 0		; <i1> [#uses=1]
	br i1 %tmp215, label %bb10, label %tailrecurse.bb10_crit_edge

tailrecurse.bb10_crit_edge:		; preds = %entry
	%tmp = add i32 %n, -1		; <i32> [#uses=3]
	%tmp17 = mul i32 %tmp, %tmp		; <i32> [#uses=1]
	%tmp18 = add i32 %tmp17, %n		; <i32> [#uses=1]
	%tmp. = zext i32 %tmp to i64		; <i64> [#uses=2]
	%tmp19 = add i64 %tmp., -1		; <i64> [#uses=1]
	%tmp20 = mul i64 %tmp19, %tmp.		; <i64> [#uses=1]
	%tmp21 = lshr i64 %tmp20, 1		; <i64> [#uses=1]
	%tmp.22 = trunc i64 %tmp21 to i32		; <i32> [#uses=1]
	%tmp24 = sub i32 %tmp18, %tmp.22		; <i32> [#uses=1]
	ret i32 %tmp24

bb10:		; preds = %entry
	ret i32 0
}

which is great! It computes the sum as n*(n+1)/2. However, when I try just this:

int sum(int n)
{
    return n + sum(n-1);
}

it generates this:

define i32 @sum(i32 %n) nounwind  {
entry:
	%tmp2 = add i32 %n, -1		; <i32> [#uses=1]
	%tmp3 = tail call i32 @sum( i32 %tmp2 ) nounwind 		; <i32> [#uses=1]
	%tmp5 = add i32 %tmp3, %n		; <i32> [#uses=1]
	ret i32 %tmp5
}

Why isn't llvm able to eliminate the tail call in this (simpler) case?

Regards,
-Mahadevan.