Re: Tail call optimization in dmd

[Andrei Alexandrescu]

On 10/6/10 14:26 CDT, Denis Koroskin wrote:
Hi guys!
Does anyone have an experience with tail recursion (in dmd in particular)?

I have (at least) 3 functions that are invoked recursively like this:

A -> B -> C -> A -> B -> ...

Problem is that even though I turned all three of them into tail
recursive functions, each cycle still consumes about 80 bytes of stack.

After hours of debugging I've noticed that dmd does terrible work on
TCO. For example, the following produces stack overflow:

void foo()
{
{
}

bar();
}

void bar()
{
{
}

foo();
}

void main()
{
foo();
}

I compile code with -O -release -inline if that matters.

Any tips would be highly appreciated.

dmd currently optimizes tail recursion but not tail calls. Tail 
recursion == function calls itself as the last expression. Tail call == 
function issues a call to another function as the last expression. 
Without tail call optimization, mutual recursion will consume stack as 
you noted.

Andrei