Which D compilers will perform tail-call optimization on this function?

Question

string reverse(string str) pure nothrow
{
    string reverse_impl(string temp, string str) pure nothrow
    {
        if (str.length == 0)
        {
            return temp;
        }
        else
        {
            return reverse_impl(str[0] ~ temp, str[1..$]);
        }
    }

    return reverse_impl("", str);
}

As far as I know, this code should be subject to tail-call optimization, but I can't tell if DMD is doing it or not. Which of the D compilers support tail-call optimization, and will they perform it on this function?

Vizard

GDC certainly does do tail-call optimisation in some circumstances, but in this particular case the version of GDC I used still does generate straight recursive calls though. – Karakalpak

I used GDC 5.2.0. – Karakalpak

LDC 1.1.0 did the right thing with this example though. – Karakalpak

Answer 1

From looking at the disassembly, DMD performs TCO on your code:

_D4test7reverseFNaNbAyaZAya12reverse_implMFNaNbAyaAyaZAya   comdat
    assume  CS:_D4test7reverseFNaNbAyaZAya12reverse_implMFNaNbAyaAyaZAya
L0:     sub ESP,0Ch
        push    EBX
        push    ESI
        cmp dword ptr 018h[ESP],0
        jne L1C

LC:     mov EDX,024h[ESP]
        mov EAX,020h[ESP]
        pop ESI
        pop EBX
        add ESP,0Ch
        ret 010h

L1C:    push    dword ptr 024h[ESP]
        mov EAX,1
        mov EDX,offset FLAT:_D12TypeInfo_Aya6__initZ
        push    dword ptr 024h[ESP]
        mov ECX,024h[ESP]
        push    ECX
        push    EAX
        push    EDX
        call    near ptr __d_arraycatT
        mov EBX,02Ch[ESP]
        mov ESI,030h[ESP]
        mov 034h[ESP],EAX
        dec EBX
        lea ECX,1[ESI]
        mov 01Ch[ESP],EBX
        mov 020h[ESP],ECX
        mov 02Ch[ESP],EBX
        mov 030h[ESP],ECX
        mov 038h[ESP],EDX
        add ESP,014h
        cmp dword ptr 8[ESP],0
        jne L1C
        jmp short   LC
_D4test7reverseFNaNbAyaZAya12reverse_implMFNaNbAyaAyaZAya   ends
    end

Flanch

Will all 3 "main" D compilers perform the optimization in this case? – Vizard

Unfortunately, TCO is not present in language specification and this can't be guaranteed. But for your example probability is pretty high. – Soria

Answer 2

A very good resource for quickly looking at the code generated by gdc is http://d.godbolt.org/. We currently don't have a dmd equivalent.

Houghton