c++ - 为什么 gcc 对一个版本执行尾调用优化而不对另一个版本执行尾调用优化？

Question

在试验尾调用优化 (tco) 时，我偶然发现了以下奇怪的示例:

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

事实上，我印象深刻的是，gcc was able在这里执行 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);
}

我们可以清楚地看到 resulting assembly 中的递归调用:

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 isn't able也执行此优化。因此，也许存在我不知道的语言的微妙之处阻止了这种优化。

为什么 gcc 不对函数 fac2 执行尾调用优化，而只对 fac1 执行尾调用优化？

---

我很清楚，在第二个版本中，结果必须是沮丧的。显然这是唯一的区别。但为什么这会成为一个问题并阻止 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 优化版本，它是 identical to fac1 (高32位是allowed to contain garbage，所以imulq可以内联后使用):

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

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