Re: CALL_EXPR_MUST_TAIL_CALL and LLVM's musttail

[Segher Boessenkool <segher@kernel.crashing.org>]

On Thu, Dec 09, 2021 at 08:06:51PM -0500, Marc Feeley wrote:
> > On Dec 9, 2021, at 6:36 PM, Segher Boessenkool <segher@kernel.crashing.org> wrote:
> >> The code generated by the Gambit compiler is sufficiently complex that it would be impossible (in the halting problem sense) to check that the tail-calling constraints are not violated. However, I know the constraints are not violated because the code was designed that way. And if I’m mistaken in this belief, then I am the one that will bare the blame of the ensuing problems.
> > 
> > On most architectures you can simply check if there are any "return"
> > instructions generated, no?  Or do you generate any actual calls (to
> > user code) as well?
> 
> You mean a “return” at the assembly code level?  Seems very brittle… on x86 a “pop %eax; jmp *%eax” will do the same as a “ret” and gcc might generate that sequence (from my point of view).  In any case, as I said previously, I don’t want to check if gcc did not optimize the tail calls… it is too late to do anything other than essentially tell the programmer “sorry I couldn’t compile that program correctly”.

I know of no single compiler that does not have very predictable insns
as return sequence.  There could be more than one sequence you need to
check for, sure, but in reality compilers generate only one or a few
code sequences to do returns: by its very nature a return can not be
combined with some other operation and optimised that way.

 >> So having a way to check during or after the compilation that tail-calls were optimized is not sufficient. A Scheme compiler that sometimes fails to compile is not very useful.  What is needed is a guarantee that specific C calls are optimized.
> > 
> > Then you need to write code that works as you want on all configurations
> > you support, state what those configs are, and test that it compiles on
> > all such configs, before every release.
> 
> This does not solve my problem either. No testing will cover all possible situations because for a particular architecture the tail call optimization may work on all the tests I can come up with, but some programmer using Gambit may write a program for which the tail calls in the C code generated by the Gambit compiler are not optimized.

You need to know what a particular compiler (for a particular target, in
a particular configuration, invoked with particular flags) will do with
epilogues, yes.  This is *unavoidable* if the compiler will not tell you
itself if every tail position call is optimised to an actual tail call,
and no existing GCC version will tell you.

> I’m not looking for a guarantee that tail calls are supported transparently on all architectures.  Currently Gambit uses a trampoline to implement Scheme tail calls, and this can be used as a fallback for architectures where C TCO is not guaranteed.
> 
> So what I need is some way to test at compile time if for the target architecture and compile options there is a guarantee that tail calls will be optimized (if the C code obeys the usual set of constraints).  Something like
> 
>   #if __has_attribute(tail_call_supported_on_this_architecture)
>   /* use tail calls for jumping around... */
>   #else
>   /* use trampoline fallback... */
>   #endif

This is impossible to do.  Tail calls are supported on *all* GCC
architectures, but not every (tail position) function call will be
optimised to a tail call, and not every such function call *can* (except
on architectures with a separate return stack of course, but
unfortunately there are very few of those).


Segher