View mode: basic / threaded / horizontal-split · Log in · Help
March 18, 2012
Tail call optimization?
Does D to tail call optimization of any kind?

-- 
- Alex
March 18, 2012
Re: Tail call optimization?
Alex Rønne Petersen Wrote:

> Does D to tail call optimization of any kind?

The D standard doesn't require the D compiler to perform that optimization (unlike Scheme).
Currently both DMD and LDC are able to perform tail call optimization in some normal cases. And I presume GDC is able to do the same.

Bye,
bearophile
March 19, 2012
Re: Tail call optimization?
On 18/03/2012 21:28, bearophile wrote:
> Alex Rønne Petersen Wrote:
>
>> Does D to tail call optimization of any kind?
>
> The D standard doesn't require the D compiler to perform that optimization (unlike Scheme).
> Currently both DMD and LDC are able to perform tail call optimization in some normal
> cases. And I presume GDC is able to do the same.

What are "normal cases"?

- where the function directly tail-calls itself?
- where two functions mutually tail-call each other?
- where a function tail-calls another non-recursively?

And in the last case, I can see that it depends on being able to replace the caller's 
stack frame with the callee's.  But what does this depend on - just the relative sizes of 
the functions' stack frames, or is it more subtle than that?

Stewart.
March 19, 2012
Re: Tail call optimization?
Stewart Gordon:

> What are "normal cases"?

It means "very simple cases". Things like fibonacci / factorial functions that call themselves at the tail.

Generally it's a fragile optimization, it's easy for it to not work/stop working. LLVM used to perform this optimization, then it stopped working for months an no one noticed. I have written a bug report and they have made it work again. And then they have put it in their demo :-)
http://llvm.org/demo/

Bye,
bearophile
March 19, 2012
Re: Tail call optimization?
On 19-03-2012 13:07, bearophile wrote:
> Stewart Gordon:
>
>> What are "normal cases"?
>
> It means "very simple cases". Things like fibonacci / factorial functions that call themselves at the tail.
>
> Generally it's a fragile optimization, it's easy for it to not work/stop working. LLVM used to perform this optimization, then it stopped working for months an no one noticed. I have written a bug report and they have made it work again. And then they have put it in their demo :-)
> http://llvm.org/demo/
>
> Bye,
> bearophile

I still don't understand why compilers don't just provide *guaranteed, 
well-defined* tail calls when the emitted IR demands it... this whole 
"it may or may not be TCO'd" business is ridiculous.

-- 
- Alex
Top | Discussion index | About this forum | D home