在尝试尾调用优化(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
fact2(n-1)
后需要进行类型转换,才能在return n*fac2(n-1);
中使用。 - Gaurav Sehgal