[LLVMdev] [cfe-dev] Does LLVM optimize recursive call?

[David Chisnall]

On 3 Oct 2012, at 09:48, John McCall wrote:

> If your teachers are really making this sort of superficial generalization,
> they're doing you a disservice.

I completely agree with John here - we had a case a few years ago where someone spent ages refactoring their algorithm to be iterative and was surprised that it became slower (with the MS compiler).  Looking at the assembly, it was using push and pop instructions for the temporaries on the recursive version, but had to do more complex addressing to find the right place for them in the iterative version, which made everything slower (and prevented the CPU from doing some register-stack aliasing tricks).

One thing John didn't mention is that LLVM will try to do tail call optimisation.  This means that if your function ends with something like:

return a(b);

It will attempt to turn this into a jump, rather than a call.  This doesn't happen in all cases, because it is dependent on the calling convention.  For static functions in C, the compiler is free to chose whatever calling convention it wants (because it's not part of the public API), but for others it may need to use a non-standard calling convention.

This has the advantage that it doesn't consume extra stack space (especially if it's self-recursive, it only consumes one stack frame no matter how deep the recursion goes) and the return will return to the outer caller.  It is slightly more complex, because most C calling conventions require the caller to clean up the call frame (the callee can't clean it up in the general case, because C allows variadic functions), and so a tail call optimisation must ensure that the inner callee has the same layout of call frame as its caller.

David