Noah Lavine <noah.b.lav...@gmail.com> 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
