Оптимизация компилятором в рекурсивном программа

Я получил мотивацию от вопроса оптимизации хвостового вызова Что такое оптимизация хвостового вызова ?

Итак, я решил посмотреть, как я могу сделать это на чистом C.

Итак, я написал 2 факториальные программы, 1-я, где можно применить оптимизацию хвостовых вызовов. Я называю эту функцию факта фактом (n, 1).

unsigned long long int fact(int n, int cont)
{
      if(n == 0)
            return cont;

      else return fact(n-1, n * cont);
}

2nd — это обычная рекурсия, когда требуется несколько кадров стека.

unsigned long long int fact(int n)
{
    if(n == 0)
        return 1;

    else return n * fact(n-1);
}

Это сборка, сгенерированная 32-битным компилятором для первого с -O2.

0x8048470 :   push   %ebp
0x8048471 : mov    %esp,%ebp
0x8048473 : mov    0x8(%ebp),%edx
0x8048476 : mov    0xc(%ebp),%eax
0x8048479 : test   %edx,%edx
0x804847b :    je     0x8048488 
0x804847d :    lea    0x0(%esi),%esi
0x8048480 :    imul   %edx,%eax
0x8048483 :    sub    $0x1,%edx
0x8048486 :    jne    0x8048480 
0x8048488 :    mov    %eax,%edx
0x804848a :    sar    $0x1f,%edx
0x804848d :    pop    %ebp
0x804848e :    ret    

Это сборка, сгенерированная 32-битным компилятором для последнего с -O2.

0x8048470 :   push   %ebp
0x8048471 : mov    %esp,%ebp
0x8048473 : push   %edi
0x8048474 : push   %esi
0x8048475 : push   %ebx
0x8048476 : sub    $0x14,%esp
0x8048479 : mov    0x8(%ebp),%eax
0x804847c :    movl   $0x1,-0x18(%ebp)
0x8048483 :    movl   $0x0,-0x14(%ebp)
0x804848a :    test   %eax,%eax
0x804848c :    je     0x80484fc 
0x804848e :    mov    %eax,%ecx
0x8048490 :    mov    %eax,%esi
0x8048492 :    sar    $0x1f,%ecx
0x8048495 :    add    $0xffffffff,%esi
0x8048498 :    mov    %ecx,%edi
0x804849a :    mov    %eax,%edx
0x804849c :    adc    $0xffffffff,%edi
0x804849f :    sub    $0x1,%eax
0x80484a2 :    mov    %eax,-0x18(%ebp)
0x80484a5 :    movl   $0x0,-0x14(%ebp)
0x80484ac :    sub    -0x18(%ebp),%esi
0x80484af :    mov    %edx,-0x20(%ebp)
0x80484b2 :    sbb    -0x14(%ebp),%edi
0x80484b5 :    movl   $0x1,-0x18(%ebp)
0x80484bc :    movl   $0x0,-0x14(%ebp)
0x80484c3 :    mov    %ecx,-0x1c(%ebp)
0x80484c6 :    xchg   %ax,%ax
0x80484c8 :    mov    -0x14(%ebp),%ecx
0x80484cb :    mov    -0x18(%ebp),%ebx
0x80484ce :    imul   -0x1c(%ebp),%ebx
0x80484d2 :    imul   -0x20(%ebp),%ecx
0x80484d6 :   mov    -0x18(%ebp),%eax
0x80484d9 :   mull   -0x20(%ebp)
0x80484dc :   add    %ebx,%ecx
0x80484de :   add    %ecx,%edx
0x80484e0 :   addl   $0xffffffff,-0x20(%ebp)
0x80484e4 :   adcl   $0xffffffff,-0x1c(%ebp)
0x80484e8 :   mov    -0x1c(%ebp),%ebx
0x80484eb :   mov    %eax,-0x18(%ebp)
0x80484ee :   mov    -0x20(%ebp),%eax
0x80484f1 :   mov    %edx,-0x14(%ebp)
0x80484f4 :   xor    %edi,%ebx
0x80484f6 :   xor    %esi,%eax
0x80484f8 :   or     %eax,%ebx
0x80484fa :   jne    0x80484c8 
0x80484fc :   mov    -0x18(%ebp),%eax
0x80484ff :   mov    -0x14(%ebp),%edx
0x8048502 :   add    $0x14,%esp
0x8048505 :   pop    %ebx
0x8048506 :   pop    %esi
0x8048507 :   pop    %edi
0x8048508 :   pop    %ebp
0x8048509 :   ret    

При компиляции обеих программ и просмотре сгенерированной сборки обе программы по-прежнему имеют рекурсивные вызовы. Но когда я компилирую с опцией -O2 (сборка, опубликованная выше) в первом, я вообще не вижу рекурсивных вызовов, и поэтому я думаю, что gcc выполняет оптимизацию хвостовых вызовов.

Но когда я компилирую последний с опцией -O2, он также удаляет рекурсивные вызовы и вместо этого помещает довольно большое количество ассемблерных инструкций по сравнению с тем, что происходит с первым на -O2.

Я хотел понять, что именно компилятор делает в последнем, и почему он не может преобразовать сборку, сгенерированную первым, даже с O4.

8
задан Community 23 May 2017 в 12:04
поделиться