[llvm-dev] How to understand "tail" call?

[Tim Northover via llvm-dev]

On Wed, 6 Feb 2019 at 18:04, Peng Yu via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> in the langref. Could anybody help me understand what tail call means?

In its simplest form, when the last thing a function does is call
something else then the compiler can deallocate the caller's stack
frame early and just jump to the callee rather than actually calling
it.

For example:

    void foo() {
        [...]
        bar();
     }

Without the tail-call optimization this might produce:

     foo:
         sub $16, %rsp ; Allocate stack space for local variables
         [...]
         callq bar
         add $16, %rsp ; Free up local stack space
         retq

With tail call optimization it would become:

     foo:
         sub $16, %rsp ; Allocate stack space for local variables
         [...]
         add $16, %rsp ; Free up local stack space
         jmpq bar

Then when bar returns, it actually grabs the return address intended
for foo and returns to the correct place. The main benefit is that
while bar (and its nested functions) are running, foo isn't consuming
any stack space.

There are certain embellishments that basically allow "return bar();"
as well if the arguments are compatible, but that's the basic idea.

Many functional languages that handle loop-like constructs via
recursion idioms instead demand their compilers guarantee this
optimization will occur, otherwise they'd blow their stack for fairly
small iteration counts on loops.

In the example you gave, no tail call optimization can occur despite
the calls being marked as candidates because main has to materialize
the "return 0" code after both calls to printf have happened. If you
returned the result of the last printf instead it would probably
trigger.

Cheers.

Tim.