Unterstützt gfortran Tail Call Elimination?

Question

Ich habe dieses kleine Programm zu testen, wenn gfortran tut Beseitigung Endrekursion:

program tailrec 
implicit none 

print *, tailrecsum(5, 0) 

contains 

recursive function tailrecsum (x, running_total) result (ret_val) 
    integer, intent(in) :: x 
    integer, intent(in) :: running_total 
    integer    :: ret_val 

    if (x == 0) then 
     ret_val = running_total 
     return 
    end if 
    ret_val = tailrecsum (x-1, running_total + x) 
end function tailrecsum 

end program 

Um zu überprüfen, habe ich es mit der -S-Option kompiliert, einen Blick auf die Anweisungen zu nehmen. Hier werden die Leitungen für die tailrecsum Funktion:

tailrecsum.3429: 
.LFB1: 
    .cfi_startproc 
    movl (%rdi), %eax 
    testl %eax, %eax 
    jne .L2 
    movl (%rsi), %eax 
    ret 
    .p2align 4,,10 
    .p2align 3 
.L2: 
    subq $24, %rsp 
    .cfi_def_cfa_offset 32 
    leal -1(%rax), %edx 
    addl (%rsi), %eax 
    leaq 8(%rsp), %rdi 
    leaq 12(%rsp), %rsi 
    movl %edx, 8(%rsp) 
    movl %eax, 12(%rsp) 
    call tailrecsum.3429 
    addq $24, %rsp 
    .cfi_def_cfa_offset 8 
    ret 
    .cfi_endproc 

Am Ende sehe ich call tailrecsum.3429 und daher denken, dass es keine Endrekursion Beseitigung ist. Dies gilt auch, wenn ich -O2 oder -O3 und -foptimize-sibling-calls verwende. Also, unterstützt Gfortran dies nicht oder ist es ein Problem meines Codes?

Answer 1

Es unterstützt es. Es ist ziemlich schwierig, viele sehr feine Fallen zu vermeiden, die die Tail-Call-Optimierung beeinträchtigen.

Betrachten Sie diese Version:

program tailrec 
use iso_fortran_env 

implicit none 

integer(int64) :: acc, x 

acc = 0 

x = 500000000 

call tailrecsum(x, acc) 

print *, acc 

contains 

recursive subroutine tailrecsum (x, running_total) 
    integer(int64), intent(inout) :: x 
    integer(int64), intent(inout) :: running_total 
    integer(int64)    :: ret_val 

    if (x == 0) return 

    running_total = running_total + x 
    x = x - 1 
    call tailrecsum (x, running_total) 
end subroutine tailrecsum 



end program 

Mit 500.000.000 Iterationen deutlich den Stapel ohne TCO sprengen würde, aber es funktioniert nicht:

> gfortran -O2 -frecursive tailrec.f90 
> ./a.out 
    125000000250000000 

können Sie prüfen, was der Compiler mehr nicht leicht -fdump-tree-optimized mit . Ehrlich gesagt, habe ich nicht einmal versucht, Ihre Assemblyausgabe zu verstehen. X86 Assembly ist einfach zu esoterisch für mich, mein einfaches Gehirn kann nur bestimmte RISCs handhaben.

Sie können sehen, dass es noch eine Menge ist nach dem Aufruf der nächsten Iteration in der ursprünglichen Version los:

<bb 6>: 
    _25 = _5 + -3; 
    D.1931 = _25; 
    _27 = _18 + _20; 
    D.1930 = _27; 
    ret_val_28 = tailrecsum (&D.1931, &D.1930); 
    D.1930 ={v} {CLOBBER}; 
    D.1931 ={v} {CLOBBER}; 

    <bb 7>: 
    # _29 = PHI <_20(5), ret_val_28(6)> 

    <bb 8>: 
    # _22 = PHI <_11(4), _29(7)> 

    <bb 9>: 
    # _1 = PHI <ret_val_7(3), _22(8)> 
    return _1; 

} 

Ich bin kein Experte in GIMPLE, aber die D.193x Operationen auf jeden Fall verbunden sind, die temporären Ausdrücke, die für den Aufruf auf den Stapel gelegt werden.

Die Operationen PHI10 finden dann, welche Version des Rückgabewerts tatsächlich zurückgegeben wird, basierend darauf, welcher Zweig tatsächlich in der if-Anweisung verwendet wurde (https://gcc.gnu.org/onlinedocs/gccint/SSA.html).

Wie gesagt, es ist manchmal schwierig, Ihren Code in die richtige Form zu bringen, was für gfortran akzeptabel ist, um die Tail-Call-Optimierung durchzuführen.