0
$\begingroup$

I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, where each function had let's say a dozen temporary variables throughout. What happens to register usage? It seems like everything would have to be stored in memory and the register usage would almost be negligible. What is it like in reality? Where am I going wrong?

$\endgroup$
2
$\begingroup$

Ignore recursion for the moment, and pretend that a recursive call is just like any other call.

Then the solution is easy: all local variables are spilled to the stack across calls, including the recursive call. So yes, if there is deep recursion going on, most of the local variables will reside on the stack most of the time.

Every platform (operating system + CPU family) defines a protocol called the application binary interface, or ABI for short. This specifies how parameters are passed to a function, how values are returned, how the stack is to be managed, and so on. If you want to see what a real-world ABI looks like, see the SysV ABI for Intel x86-64/AMD64. Almost all operating systems follow this ABI on that family of CPUs, with Windows being the most notable exception.

The ABI will specify that some registers are not preserved across function calls (i.e. they are caller-save) and some are preserved (i.e. they are callee-save). A callee-save register must be preserved by a function if it wants to use that register, and a caller-save register must be explicitly spilled across a call if the caller needs the value.

It's also possible to optimise recursion, as long as the function ultimately presents itself to the rest of the system as if it obeys the ABI. This is where things get interesting.

Tail call optimisation is the most common scenario. If the last thing that a function does in some code path is to call another function, it's sometimes possible to transform the last call into a jump. And if it's a recursive call, then it can be transformed into a loop.

So this:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
}

can be transformed into this:

foo(args)
{
    while (the base case doesn't apply) {
        before_the_recursive_call();
        args = recursive_args;
    }
    return something();
}

But in that case, no local variables have to be saved across that final call. So nothing, in theory at least, needs to be spilled to the stack there.

As an aside, in C++, the semantics of RAII and exception handling often makes tail call optimisation impossible, so you won't often see this in compilers for the C family of languages.

There is a related optimisation called "middle recursion optimisation", which is used for the more familiar recursive scenario, where there is a single recursive call in the middle of a function:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
    return after_the_recursive_call();
}

This can be transformed into something like this:

foo(args)
{
    while (the base case does not apply) {
        before_the_recursive_call();
        push_anything_to_the_stack_that_the_last_part_needs();
        args = recursive_args;
    }

    return_value = something();  // base case

    while (pop_the_stack()) {
        return_value = after_the_recursive_call();
    }
    return return_value;
}

Again, this is rare in C-like languages. You would more typically find it in functional or logic languages which don't have loop constructs, and only have recursion. In a language like that, it's often worth going to a lot of trouble to optimise recursion into loops.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.