Re: Problem with GCC as a Scheme compiler: tail calls

[Noah Lavine]

Ah, I see. The problem is quite significant.

I found this page in the GCC internals documentation:
http://gcc.gnu.org/onlinedocs/gccint/Tail-Calls.html. It seems to
suggest that we would need to make our own calling convention.

So I guess the question is, is it worthwhile for us to fix GCC so it
can handle tail calls, or should we use another code generation
library that already deals with them? I must admit I still really like
the idea of using GCC, because it has a lot of good optimizations, and
I also like the idea of working with other groups rather than making
yet another compiler. However, I guess the next thing to do is to ask
on the GCC mailing list if they're interested in tail call patches,
and how hard those would be to make.

I realize however that the GSoC deadline is tomorrow, and that Paul is
probably wondering whether he should submit a proposal for an AOT
compiler or not. So I suggest that an AOT compiler is a good project,
and the first step should be to figure out if it's possible for us to
use GCC. What do people think of this? (Also note: I know Paul outside
of this mailing list, so my opinion is not objective.)

Noah

On Thu, Apr 7, 2011 at 10:25 AM, Mark H Weaver <address@hidden> wrote:
> Noah Lavine <address@hidden> writes:
>>> There is one _very_ serious problem with using GCC to compile Scheme, or
>>> at least there was the last time I researched this issue: tail calls.
>>
>> I might be wrong about this, but I thought that GCC supported multiple
>> calling conventions, with the user telling GCC which one to use
>> (cdecl, fastcall, possibly others). If so, it must have some way to
>> represent that in its intermediate representations. We might be able
>> to add our own calling convention.
>>
>> I also know that GCC has an --optimize-sibling-calls argument, which
>> will make it do something similar to at least some regular C calls.
>> I'm not sure if it's possible, but maybe we could arrange for whatever
>> code transformation implements this to be run on every Scheme call.
>
> Please read section 3.3 of the thesis I referenced:
>
>  http://users.cecs.anu.edu.au/~baueran/thesis/
>
> There you will find the list of conditions required for tail calls to be
> optimized by GCC circa 2003.  Among other things, it includes:
>
> * The caller's stack frame must be empty (i.e. no stack-allocated local
>  variables or temporaries).
>
> * No overlapping arguments (i.e. if it's too difficult to rearrange the
>  input arguments on the stack to match what the next function expects,
>  gcc will bail on the tail call)
>
> * No position-independent code on several platforms, including x86
>  (i.e. no tail calls in shared libraries)
>
> * No indirect calls (i.e. no tail calls to function pointers)
>
> * No setjmp or longjmp
>
> * Sibling call epilogue must be defined (i.e. many targets aren't
>  supported)
>
> * Additional machine-independent constraints (i.e. many targets impose
>  additional restrictions)
>
> The end result of all of these restrictions is that tail calls can only
> be optimized by GCC in extremely simple cases like fibonacci.  Some of
> these restrictions may have been lifted since 2003, but I'm reasonably
> sure the problem has not been solved satisfactorily.  If it had been, it
> would've been very big news in the functional programming language
> implementors community, since this has been a long-standing problem.
>
> However, what I find more persuasive than any paper is that fact that
> I've never found an implementation of a high-level programming language
> based on GCC that manages to support tail calls without doing some nasty
> hacks.  Lots of smart people have worked on this, but to my knowledge,
> no one has found a good solution.  The solutions I'm aware of are:
>
> * Cheney on the MTA, as is done by Chicken
>
> * Trampoline: instead of calling functions directly, return the address
>  of the next function back to the trampoline loop.
>
> * Don't do function calls at all.  Instead use inline asm to jump to the
>  inside of the next function, passing arguments via register globals.
>  GHC did this at one point.
>
> GCC's problems in this area are almost certainly the main reason so many
> functional programming language implementors have resorted to writing
> their own native code generators from scratch.
>
> If anyone knows of a recent breakthrough in this area, please speak up.
>
>    Best,
>     Mark
>