gfortran 支持尾调用消除吗？

我编写了这个小程序来测试 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 or -O3 and -foptimize-sibling-calls。 那么，gfortran不支持这个还是我的代码有问题？

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

如果按值传递参数，编译器优化尾部调用就会变得更简单。在这种情况下，接收过程不需要有一个临时指针（地址）。

事实上，这个修改足以消除尾调用并启用无限递归：

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操作肯定链接到放置在堆栈上以供调用的临时表达式。

The PHI然后，操作会根据 if 语句中实际采用的分支来查找实际返回哪个版本的返回值（https://gcc.gnu.org/onlinedocs/gccint/SSA.html https://gcc.gnu.org/onlinedocs/gccint/SSA.html).

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