[flagged]
Tail-call optimization in C is relatively recent (2025)
111–120 of 128 posts
Re: Tail-call optimization in C is relatively recent (2025)
#112> In 2001 Mark Probst implemented tail-call optimization in GCC
That's me.
The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee.
The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure how many arguments it passed, which means that only the caller can clean up the stack, unless the stack frame size is also communicated, which "normal" C calling conventions don't do. But when the callee does a proper tail call, the stack frame that returns to the callee is not the stack frame that the callee originally sent. This is explained in more detail in my thesis starting on page 16: https://hostr.flingit.run/s/proper-tail-calls.pdf
Re: Tail-call optimization in C is relatively recent (2025)
#113I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there! On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.
I think Anton is wrong. Since C89 and before C23 calling an `int f();` function with arguments not matching the definition's actuals is UB. In C23 `int f();` became the same as `int f(void);`, so calling that function with any arguments is a compile-time error.
For variadic functions, if you use `va_start()`/`va_arg()`/`va_end()` to consume all the arguments, and leave no `va_list` alive, then the compiler can correctly generate a tail call from such functions.
Re: Tail-call optimization in C is relatively recent (2025)
#114Earlier quoted context omitted.
h() can't have more arguments than g(): that's an important limitation.
Consider what was being discussed originally, though. If h() has fewer arguments than g() and is in a different module (e.g. a static library) from h() such that the calling convention was necessary, how would h() recurse back to g()?
The example you set up was about f() calling into g() calling into h(). Why do you mention h() calling into g() now?
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?
Re: Tail-call optimization in C is relatively recent (2025)
#115Earlier quoted context omitted.
Consider what was being discussed originally, though. If h() has fewer arguments than g() and is in a different module (e.g. a static library) from h() such that the calling convention was necessary, how would h() recurse back to g()?
The example you set up was about f() calling into g() calling into h(). Why do you mention h() calling into g() now? 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?
That was in response to a specific point that TCO needed callee-cleanup. But nobody cares about TCO in non-recursive call stacks, and nobody does cross-module recursion. Hence my question: if the only situation where anyone would care whether TCO is being performed is one in which the compiler can see both sides of the call, what does it matter what the calling convention is? The compiler is not bound to use any calling convention to generate the code for the call, it can just generate the caller and callee to be compatible with other and with no one else.
Re: Tail-call optimization in C is relatively recent (2025)
#116> In 2001 Mark Probst implemented tail-call optimization in GCC That's me. The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee. The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure…
[deleted]
Re: Tail-call optimization in C is relatively recent (2025)
#117Earlier quoted context omitted.
> My impression is that every tail call can written as a loop much more naturally. 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. IMHO, both of these need to be taught, neither is particularly more natural. In addition, as others have descri…
> TCO makes a lot of sense for interpreters and state machines. 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 a…
That's not entirely true, but it's a valid reason to prefer using musttail.
`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.
Re: Tail-call optimization in C is relatively recent (2025)
#118I recently played around with what I call "manual tail-call optimization": transform a tail call to a goto to the beginning of the function. Check it out: https://godbolt.org/z/3fY1v1oeW int factorial_loop_iterative(int n, int a){ while(n > 0){ a = a * n; n = n - 1; } return a; } int factorial_loop_recursive(int n, int a){ if(n > 0){ return factorial_loop_recursive(n - 1, a * n); }else{ return a; } } int factorial_lo…
Seems like a complex way to write a normal looped version. Apart from factorial_loop_manual() being one in design, its name even says as much.
Re: Tail-call optimization in C is relatively recent (2025)
#119Earlier quoted context omitted.
> I can only think of a few other optimizations that affect memory usage Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.
> requiring more instructions for string access Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer. Or do you refer to the extra rolling-hash pass needed when concat…
> Wait, why would interned immutable strings require more instructions when doing regular string access?
Java automatically interns static strings (e.g. from class files), but does not automatically intern dynamically-allocated strings, e.g. new String(charArray)
If you want it interned, you have to intentionally call e.g. new String(...).intern(). If you do this on every string you work with, you can then reliably use reference equality instead of value equality, e.g. given char[] abc = {'a','b','c'}; then new String(abc) != new String(abc) != "abc" but new String(abc).intern() == new String(abc).intern() == "abc"
But if you're interning every string, you're doing extra work to maintain that string pool, and adding extra pressure on the GC, and potentially you'll be re-interning strings a lot depending on how many times they end up no longer referenced by the time GC runs.
Re: Tail-call optimization in C is relatively recent (2025)
#120Unless the language can guarantee TCO, I don’t feel comfortable writing tail recursive code and being at the compiler’s/interpreter’s mercy. I think the framing of TCO as an optimization has been very unfortunate.
Indeed. I guess this is why [[gnu::musttail]] and [[clang::musttail]] exist.
https://gcc.gnu.org/onlinedocs/gcc-15.1.0/gcc/Statement-Attr...