Экспериментируя с оптимизацией хвостового вызова (tco), я наткнулся на следующий любопытный пример:
unsigned long long int fac1(unsigned long long int n){
if (n==0)
return 1;
return n*fac1(n-1);
}
на самом деле, я был впечатлен, что GCC был в состоянии выполнить тко здесь (с -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
Сначала я отклонял это как пропущенную оптимизацию, но теперь я не уверен, потому что лязг не в состоянии выполнить эту оптимизацию, а также. Так что, возможно, есть тонкости языка, о котором я не знаю, которые мешают этой оптимизации.
Почему gcc не выполняет хвостовую оптимизацию для функции fac2
но только для fac1
?
Мне понятно, что во втором варианте результат должен быть понижен. Очевидно, это единственная разница. Но почему это должно быть проблемой и предотвратить это?
Например, если я помогу компилятору и перепишу свою функцию как классическую хвостовую рекурсию (которая должна давать результаты, идентичные версии 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
можно использовать после врезки):
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()
, после завершения рекурсии понадобится приведение 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
Других решений пока нет …