[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Problem with GCC as a Scheme compiler: tail calls

From: Mark H Weaver
Subject: Problem with GCC as a Scheme compiler: tail calls
Date: Thu, 07 Apr 2011 10:25:45 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)

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:

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

* 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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]