为什么gcc对一个版本进行了尾递归优化，而对另一个版本没有进行优化？

Question

在尝试尾调用优化（tco）时，我偶然发现了以下有趣的例子：

unsigned long long int fac1(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac1(n-1);
}

实际上，我对gcc能够在这里执行tco（使用-O2标志）印象深刻，因为这并不是那么直接的：

fac1(unsigned long long):
        testq   %rdi, %rdi
        movl    $1, %eax
        je      .L4
.L3:
        imulq   %rdi, %rax
        subq    $1, %rdi
        jne     .L3
        rep ret
.L4:
        rep ret

然而，将返回类型从unsigned long long int更改为unsigned int后，gcc无法执行tlo：

unsigned int fac2(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac2(n-1);
}

我们可以清楚地看到递归调用在生成的汇编代码中：

fac2(unsigned long long):
        testq   %rdi, %rdi
        jne     .L16
        movl    $1, %eax
        ret
.L16:
        pushq   %rbx
        movq    %rdi, %rbx
        leaq    -1(%rdi), %rdi
        call    fac2(unsigned long long)
        imull   %ebx, %eax
        popq    %rbx
        ret

起初，我认为这是一个被忽略的优化问题，但现在我不太确定了，因为clang无法执行此优化。也许有些微妙的语言细节我没有意识到，阻止了这种优化。

为什么gcc只对fac1函数进行尾递归优化而不对fac2进行优化？

---

我明白，在第二个版本中，结果必须被降级。显然这是唯一的区别。但为什么这会成为一个问题并阻止tlo呢？

例如，如果我帮助编译器并将我的函数重写为经典尾递归（应该产生与版本fac2相同的结果）：

unsigned int tlo_fac(unsigned long long int n, unsigned long long int cur){
  if (n==0)
    return cur;
  return tlo_fac(n-1, n*cur);
}

unsigned int fac(unsigned long long int n){
  return tlo_fac(n,1);
}

我得到了一个经过 tlo 优化的版本，它与 fac1 完全相同（高32位允许包含垃圾数据），因此可以在内联后使用 imulq。identical to fac1 的链接，allowed to contain garbage 的链接。

fac(unsigned long long):
        testq   %rdi, %rdi
        movl    $1, %eax
        je      .L10
.L11:
        imulq   %rdi, %rax
        subq    $1, %rdi
        jne     .L11
.L10:
        rep ret

- ead

---

可能是因为在调用fact2(n-1)后需要进行类型转换，才能在return n*fac2(n-1);中使用。 - Gaurav Sehgal

@GauravSehgal 但是这个转换为什么会阻止TLO呢？ - ead

{btsdaf} - Gaurav Sehgal

Answer 1

在 fact2() 中，递归完成后需要将 unsigned long long int 转换为 unsigned int。 unsigned int fac2(unsigned int n) 生成以下汇编代码：

fac2(unsigned int):
        testl   %edi, %edi
        movl    $1, %eax
        je      .L10
.L9:
        imull   %edi, %eax
        subl    $1, %edi
        jne     .L9
        rep ret
.L10:
        rep ret

- Gaurav Sehgal

---

{btsdaf} - harold

我知道，需要进行类型转换，并且将输入参数类型更改为输出类型会导致一个tlo'ed版本。但是对我来说，不清楚这样做为什么会阻止TLO。 - ead

为了执行尾递归优化，递归调用应该是函数中最后要完成的事情，return n*fac1(n-1);，最后一步不是函数调用fact(n-1)，而是结果的转换。 - Gaurav Sehgal

{btsdaf} - ead