gfortran 是否支持尾调用消除？

Question

我做了这个小程序来测试，gfortran是否做尾调用消除：

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

为了检查，我用-S选项编译了它，看看说明。这里是 tailrecsum 函数的行：

tailrecsum.3429:
.LFB1:
    .cfi_startproc
    movl    (%rdi), %eax
    testl   %eax, %eax
    jne .L2
    movl    (%rsi), %eax
    ret
    .p2align 4,,10
    .p2align 3
.L2:
    subq    , %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    , %rsp
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc

最后，我看到call tailrecsum.3429，因此认为没有尾调用消除。当我使用 -O2 或 -O3 和 -foptimize-sibling-calls 时也是如此。那么，gfortran不支持这个还是我代码的问题？

Answer 1

确实支持。要避免许多非常微妙的陷阱会损害尾调用优化，这是非常棘手的。

如果按值传递参数，编译器优化尾调用会变得更简单。在那种情况下，接收过程不需要指针（地址）指向它。

其实这样修改就可以搞定尾调用消除和无限递归了：

recursive function tailrecsum (x, running_total) result (ret_val) bind(C)
    integer, value :: x
    integer, value :: 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

Gfortran 不需要 bind(C) 因为它将所有 value 实现为类似 C 的按值传递。英特尔确实需要它，因为它会创建一个临时文件并传递其地址。

不同架构的细节可能不同，这取决于谁负责清理什么。

考虑这个版本：

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

使用 500000000 次迭代显然会在没有 TCO 的情况下破坏堆栈，但它不会：

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

您可以使用 -fdump-tree-optimized 更轻松地检查编译器的功能。老实说，我什至懒得去理解你的汇编输出。 X86 汇编对我来说太深奥了，我简单的大脑只能处理某些 RISC。

你可以看到在你原来的版本调用下一次迭代后还有很多事情要做：

  <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;

}

我不是 GIMPLE 的专家，但 D.193x 操作肯定链接到为调用而放在堆栈上的临时表达式。

PHI 操作然后根据 if 语句中实际采用的分支找到 return 值的哪个版本将被实际 returned (https://gcc.gnu.org/onlinedocs/gccint/SSA.html ).

正如我所说，有时很难将代码简化为 gfortran 可以接受的正确形式来执行尾调用优化。

gfortran 是否支持尾调用消除？

Does gfortran support tail call elimination?

fortran

gfortran

tail-recursion