fortran - 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    $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

最后，我看到 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 语句 (https://gcc.gnu.org/onlinedocs/gccint/SSA.html) 中实际采用的分支查找实际返回的返回值版本。

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