What's the modern view here? I think it's bimodal: either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on.
I think a third option is that tail calls are only guaranteed if you add a special attribute (eg. [[musttail]]) and that attribute fails to compile if your code is written in such a way that a true tail call cannot be guaranteed.
The LLVM backend supports a "musttail" marker on function calls (https://llvm.org/docs/LangRef.html#call-instruction), but it specifies a set of constraints that must be met for "musttail" to be valid. I have been experimenting with a Clang change that would plumb a C++ [[musttail]] attribute through the C++ frontend to LLVM, but it requires some care to make sure we satisfy LLVM's constraints.
goto function(parameter1, parameter2);
Edit: Hmm there is an issue in handling the stack space I suppose, because there are live old parameter objects already in the place you want to put your new parameters. An ugly but possibly workable way of handling it is to have two areas for parameters. One used for odd recursion depths and another used for even ones.
Message 1
Message 2
Message 3
Message 3
Message 2
Message 1
A call to a destructor is a normal call. If you need to call destructors, then it means your tail call is a call to a destructor and not what you're seeing in the code. It's a fundamental semantical problem. You can't have "make the last call in this function be an implicit call to some function" and "make the last call be the explicit call to this other function" at the same time.
Either you push a copy of the object to the list, in which case it is fine. Or you push a pointer/reference to the object, in which case it becomes dangling.
void foo(const char* str) {
if (*str == '\0') return;
printf("%c", str[0]);
std::string x = str + 1;
return foo(x.c_str());
}> fails to compile if your code is written in such a way that a true tail call cannot be guaranteed
[[clang:musttail]] f(a, b);
[[clang:musttail]] return f(a, b);
I don't think that is feasible, it would change the semantics of the language. You can always put your destructors in an inner scope if you want them to run first:
int Func() { { TypeWithDestructor a; int ret = a.get(); } [[clang:musttail]] return ret; }
This means that TCO can't be done across calls where the amount of stack space used for arguments in the callee is larger than that of the caller. (In cases where the stack space used by the callee is less than the caller, the caller just needs to leave "wasted" stack space as if amount of stack space used by arguments were the same.) It wouldn't be much of a point on architectures where the cdecl calling convention passes enough arguments in registers to cover the majority of functions, except that some of these ABIs (notably Windows x64 calling convetion, but not Linux x64_64 SysV ABI) require the caller to allocate shadow space on the stack for all register-passed arguments. (Edit: I was wrong, the Windows shadow space on the stack is a fixed 32 bytes, regardless of the number of register-passed arguments.)
This motivates a couple of ABI questions:
1. Why does the Windows x64 ABI require the caller to pre-allocate "shadow space" to potentially spill register-passed arguments? It's wasteful if it's not needed (especially in ABIs with a redzone), and it reduces opportunities for TCO. (Edit: ahh, unlike Linux, the Windows x64 calling convention has no redzone. I guess this then becomes "Why doesn't Windows x64 provide a redzone?")
2. Why not define a calling convention that is callee-cleanup where the post-cleanup stack pointer is passed in a designated register (or at the top of the stack) to the callee? I understand that it might not make sense to pay the cost (fewer arguments passed in registers, and often an extra stack spill) for the majority of functions, but it seems an oversight that there's not a calling convention that (in the absence of destructors) always allows tail calls to be optimized.
I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right?
[0] https://en.wikipedia.org/wiki/X86_calling_conventions plus their variants on other architectures
LLVM mostly follows this path: it allows full TCO only when using the “fastcc” (i.e. “whatever LLVM feels like generating”) and some calling conventions from functional languages (like GHC) that have a specific carve out for it.
Shouldn't TCE be trivial with callee cleanup?
When I (the function) get called, I get X bytes of stack in arguments, then start pushing variables and whatnot. When I return, I simply put my return value at the start of my stack space, pop everything else, then jump back.
In a tail call, all I need to do is put the next functions arguments at the start of my stack space, pop everything else, then jump to its address.
Obviously in IRL CPUs some of this data would be kept in registers instead of the stack, but the mechanism should be the same.
In the article's printf example, the compiler is able to perform TCO only because it uses at most 5 pointer/integer arguments (with number of fp arguments passed in al) and at most 6 fp arguments, so it's caller-cleanup, but with no cleanup to perform.
Under SvsV (Linux, etc.) x86_64 ABI, varargs calls, the number of fp arguments passed in XMMx registers is passed in al, but nothing to directly indicate how much stack space is used by arguments (and it's also obviously caller-cleanup). The printf example from the article works because all of the arguments fit in registers.
If a variable is captured by the tail-called function (i.e. the function receives the unique or borrowed pointer) then you can do TCO with an extra argument (said variable, owned/unique) and clean up at the end of the "loop".
If the variable isn't captured by the tail-called function, then it's unobservable (except through side effects) if it's deallocated before the tail call.
But IMO that does not seem like it's worth it considering how less predictable it would make drop.