View mode: basic / threaded / horizontal-split · Log in · Help
October 12, 2012
Re: Explicit TCE
> Hey, that's dmd (compiler) using a ton of memory,  not 
> std.regex :(
> It actually flies with only a modest set of ram after CTFE (or 
> rather 'if') succeeds that is :)

My bad. Even then, TCE wouldn't hurt.

>> The main problem I see is working with other compilers like 
>> GCC/LLVM. If
>> this can be done on those compilers, I don't see any major 
>> hurdle to
>> getting this implemented.
>
> Perhaps the biggest one would be convincing GCC/LLVM devs to 
> accept patches :)

I think getting Walter Bright on board is the best starting 
point. If he likes the idea, I'm sure we can work out way with 
the GCC/LLVM devs. I saw some basic signs (noted earlier) that 
this may be a non-issue, as the functionality may already be 
there.

I'll keep looking and see if I can find a definitive answer for 
those compilers. Would support of one of the compilers be enough, 
or would both be required to get this in the formal language spec?
October 12, 2012
Re: Explicit TCE
Dmitry Olshansky:

> Perhaps the biggest one would be convincing GCC/LLVM devs to 
> accept patches :)

From what I've seen LLVM devs seem open enough to good patches. 
They have accepted several changes to allow LLVM to become the 
back-end of GHC (Haskell compiler), and generally my enhancement 
requests to improve LDC1 life were well accepted. They have even 
kept open a large request enhancement of mine to optimize D 
vector ops in the back-end.

Bye,
bearophile
October 12, 2012
Re: Explicit TCE
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
October 13, 2012
Re: Explicit TCE
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.
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home