Explicit TCE

[Tyler Jameson Little]

On Friday, 12 October 2012 at 20:23:00 UTC, David Nadlinger wrote:
> On Friday, 12 October 2012 at 17:39:53 UTC, Alex Rønne 
> Petersen wrote:
>> However, the primary problem with this approach is a really 
>> mundane one: The major compiler back ends (GCC and LLVM) don't 
>> have any means of guaranteeing TCE...
>
> LLVM shouldn't be as big a problem – there is some support 
> for guaranteed TCO in order to make implementations of some of 
> the functional languages possible.
>
> I know that you can force LLVM to tail-call everything it 
> possibly can (which in consequence horribly breaks the ABI), 
> but I am not sure right now how fine-grained you can control 
> that mechanism.
>
> Also don't forget that some calling conventions don't lend 
> themselves particularly well for doing efficient tail calls.
>
> David

I found this:

http://llvm.org/docs/CodeGenerator.html#tail-call-optimization
http://llvm.org/docs/CodeGenerator.html#target-feature-matrix

It seems that llvm won't be a problem. I've never worked with 
LLVM (or any compiler for that matter) at this low of a level, 
but I assume that the front-end produces code that looks like the 
provided code snippet in the first link. If that's the case, then 
we can basically guarantee that LLVM will do what we expect, as 
long as we can guarantee that all callers and callees use 
"fastcc". I'm not 100% on the implications of this, but it should 
work.


As for GCC, the situation seems less hopeful. I found this thread 
about GUILE, but it did mention GCC's lack of support for tail 
calls. This was april of last year, so maybe things have 
improved. The thread does mention that the GCC devs would be open 
to suggestions, but it seems like this might be a harder fought 
battle than for LLVM.

http://lists.gnu.org/archive/html/guile-devel/2011-04/msg00055.html


LLVM should be sufficient though, right? GDC can just outright 
reject explicit TCO for now until it supports proper TCO. Maybe 
the GUILE mailing list would be a good place to start, since 
there may be efforts already there.


What steps would need to happen for this to become a reality?  
Here's my list:

1. Get Walter Bright/Andrei Alexandrescu on board
2. Verify that it will work with LLVM
3. Get it working in DMD
4. Get it working in LDC
5. Work with GCC devs

Is there enough interest in this to implement it? I really don't 
know DMD or LLVM at all, so I don't know how big of a project 
this is.