You can have a set of mutually recursive functions, which tail call each other.
In C you can write state machines using "goto" (the implementations with "switch" are typically much more inefficient), but in languages with guaranteed tail call optimizations you can write a state machine where each state is a function.
In general, it is frequent enough to call another function as the last step of a function, even when there is no recursion involved. It is quite stupid for a compiler to use a CALL in such instances, instead of using a JMP. The only problem is that the function calling convention must be compatible with this optimization, while traditionally the C language used an inefficient calling convention that is not compatible with optimizations. That convention is a residue of the time when functions could be used without being declared and it should never be used by modern compilers.
Of course, a language implementation can arrange for all that; but clearly, calling conventions are relevant here.
Why? In functional languages, it's common for an exported function from one compilation context to tail call into an exported function from another.
This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)
A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work.
In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
You can still do that with a caller-cleanup convention. Suppose you have a convention like
* Set up stack
* Call
* Clean up stack
and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be
* f: Set up stack for g()
* f: Call g()
* g: Do work
* g: Set up stack for h()
* g: Call h()
* h: Do work
* h: Return
* g: Clean up stack
* g: Return
* f: Clean up stack
And with TCO:
* f: Set up stack for g()
* f: Call g()
* g: Do work
* g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step.
* g: Jump to h()
(At this point it looks as if f() called h() directly.)
* h: Do work
* h: Return
* f: Clean up stack
This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.
The whole thread is about how the traditional calling convention makes it difficult to implement TCO in C. Functions with different arity having different stack layout is indeed one of the roadblocks, so I think we agree here, no?
> I can't see why the calling convention could matter.
The "could matter" was understood as "would influence TCO" and so the rest of the thread was devoted to explain how the two are connected, while you meant "should be fixed and not be changed at the compiler's whims".
And you are right, of course: if a function is static and its address is never taken, the compiler can choose whatever calling strategy it wants, possibly one that facilitates TCO.
Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.
The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.
[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...
Which is more natural? (please just assume my wonky pseudo code syntax makes sense)
printall(List) ->
foreach item in List {
print_item(item)
}.
printall([Head | Tail]) ->
print_item(Head),
printall(Tail);
printall([]) -> ok.
The reason that performant implementations prefer TCO is because the only reliable knob that clang and gcc provide to control which locals are spilled to stack vs. kept in registers is via calling convention constraints. One could accomplish the same performance without TCO'd recursion if there existed an annotation for local variables designating them as spill/no-spill. But that doesn't exist in clang or gcc - the "register" keyword in the C standard was supposed to be for exactly that, but it's ignored in both compilers.
`register` is a hint if you don't specify which register you want to use - however, if you specify the register it will clobber it.
noinline void bar()
{
register void *parent __asm__("r10");
...
}
noinline void bar()
{
void *volatile parent;
// set parent = %r10 before anything else.
asm volatile ("mov{q}\t{%%r10, %0|%0, r10}" : "=r"(parent) : : "r10");
...
}
In both cases you would set the register immediately before making the call, again using `volatile`. Since `r10` is not used by a typical call in SYSV - it's the static chain pointer in the SYSV convention, but otherwise usable as a GP register, a call will not overwrite it.
void foo()
{
struct foo_frame {
int x;
} locals = {
.x = 999
};
// Set `r10` to our function's local frame
asm volatile("mov{q}\t{%0, %%r10|r10, %0}" : : "r"(&locals) : "r10")
bar();
}
Demo: https://godbolt.org/z/cM9d8e1r5
For other registers which are part of the regular calling convention, we might be able to clobber them if they wouldn't normally be used for the call. Eg, if our function takes regular 2 arguments, they would be in `rdi` and `rsi` - so we could use `rdx`, `rcx`, `r8`, `r9` like the above, but if our function took 6 or more regular arguments we wouldn't be able to use any of these in this way. If we wanted a custom calling convention we could just make all functions have zero-arguments and perform all of the setting and capturing ourself - which gives us more control than using [[musttail]] - though less portable, and may prevent optimizations the compiler could otherwise make.
It's important in interpreters. Here's an example: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
local factorial do
local function impl(n, acc)
if n == 1 then
return acc
else
return impl(n - 1, acc * n)
end
end
factorial = function(n)
if n < 0 then
error("factorial input is negative")
elseif n <= 1 then
return 1
else
return impl(n - 1, n)
end
end
end
local acc = 1
repeat
acc = acc * n
n = n - 1
until n == 1
return acc