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.