Почему gcc выполняет оптимизацию хвостового вызова для одной версии, а не для другой?

Экспериментируя с оптимизацией хвостового вызова (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

6

Решение

В 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
2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]