mark-probst
3 days ago
> 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
anitil
3 days ago
That is a very cool contribution, I actually didn't know that it required a new calling convention! I look forward to reading your thesis
kazinator
2 days ago
Let's assume that parameter are all the same size and put on a stack.
If you know that you are an M-parameter function being called, and you want to tail cal an N-parameter function, where N <= M, then you can just place the new N parameters in the same space on the stack where you received your M parameters, and jump to that function. That function will return to your original caller, which will remove the M parameters, not caring that some of them are not the originals that it passed.
Suppose N > M. Things start to get tricky. There isn't space in our original argument space for N. If we increase the space, the original caller won't clean it up properly. If we just allocate a new space of N, we are not making a tail call.
Because we want to make a tail call, it means we don't expect to execute any code in this function any more, and are free to trash the local variables. We can move the stack down a bit to make room for N arguments above where previously we were given M by our caller. To solve the problem that our caller wants to clean up M, but we need it to clean up N could be solved by a trampoline. We prime the stack such that when the tail-called function we are targeting returns, it will not go to our caller directly but to a stub function. That stub function will clean up the N-M words of the stack, leaving M, and then return to the original caller, which cleans up M.
In this situation, we are benefiting from knowing that the caller passed M to us. In the case of a variadic function, we don't know at all. It could just be the fixed arguments (parameters before the ellipsis) like printf("hello\n'), or any number. There is a run-time protocol to discover what parameters there are; the application logic figures it out from the arbitrary conventions. That's too late and too ad hoc for compile time.
I think yuo can reason about it similarly to above. If we are a variadic with M fixed parameters, we know we are called with at least M arguments, so we can place N <= M tail-callee arguments into the variadic space and proceed accordingly. For N > M, we can extend to make up the difference and use the trampoline to clean up and return to the original caller.
sThese trampolines are not closures; they are behind-the-scenes that can be generated as static code; no executable heaps or stacks required.
mark-probst
2 days ago
- The vararg function doesn't even know exactly how many args it's been passed, it only knows a lower bound (the non-variable declared args). - The trampoline is another stack frame, so putting that in would make the tail call not "proper" anymore. You could still consume an unbounded amount of stack with tail-call-only recursion.
Maybe I misunderstand your idea?
user
2 days ago
cryptonector
2 days ago
The trampoline must indeed be a closure, but let's say you have a chain of main() calling f() tail-calling g() tail-calling... in all cases needing a trampoline, and some being [mutually, even] recursive, and even variadic: there is only ever one live closure: the return to the main() call site to f(), so there is no unbounded stack growth due to tail-call recursion.
The trampoline would replace the {main retaddr, main fp} closure with {trampoline addr, [stack byte count to pop], main retaddr, main fp} and would pop some number of bytes, either hard-coded into the the trampoline function (so you get a bunch of them) or is part of the closure.
kazinator
2 days ago
We have to avoid the situation whereby we have a tail calling loop, in the course of which a growing chain of these fixup thunks is accumulating, such that when we return to the original caller, a cascade of these goes off. That will clearly cause accumulation of something on the stack. Maybe we just need one global thunk. When a function sees that its return address points to the tail fixup thunk, it avoids installing another one, but instead updates some word at a well-known frame offset location to inform that thunk that more words need to be cleaned up. All of this obviously does relate to trampoline-based tail calling.
cryptonector
2 days ago
Yes, of course, the tail-calling function must recognize that its continuation is a trampoline closure, pop it, then push either a new trampoline or the original closure (if no trampoline would be needed for the particular tail-call being performed).
Do it right and there should only ever be one trampoline closure on the stack for any chain of tail calls, making the scheme O(1) in space.
So the whole protocol is that when the compiler recognizes that a call is a tail call, and one that can be turned into a jump instead of call, then the compiler must emit code to
a) pop the current continuation (which will either be the original or a trampoline that embeds the original, and from which the original can be recovered),
b) pop all the previous arguments and push all the new ones (possibly some are the same, so there is room for optimization here),
and
c) push a new continuation that is either the same as the previous current continuation or else a new continuation closure that is the correct trampoline corresponding to -and embedding- the original continuation, where the original is recovered from (a).
The trampoline recovers the original continuation, fixes the stack depth to what the caller expects, and executes a return to the original continuation.
For variadic functions it has to be the case that they have used `va_start()`, consumed all variadic arguments with `va_arg()`, then called `va_end()`, leaving no active copy of the `va_list`, then the compiler can arrange to keep a hidden local variable count of stack words used by the variadic arguments that it can use to implement the above protocol correctly.
user
3 days ago