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

я получил мотивировал от оптимизации вопроса хвоста вызова What Is Tail Call Optimization?Оптимизация компилятора в рекурсивной программе

Итак, я решил посмотреть, как я могу сделать это в простом 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); 
}

2-я нормальная рекурсия, в которой требуется несколько стековых фреймов.

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

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

Это сборка генерируется с помощью 32-битового компилятора для первого с -O2

0x8048470 <fact>: push %ebp 
0x8048471 <fact+1>: mov %esp,%ebp 
0x8048473 <fact+3>: mov 0x8(%ebp),%edx 
0x8048476 <fact+6>: mov 0xc(%ebp),%eax 
0x8048479 <fact+9>: test %edx,%edx 
0x804847b <fact+11>: je  0x8048488 <fact+24> 
0x804847d <fact+13>: lea 0x0(%esi),%esi 
0x8048480 <fact+16>: imul %edx,%eax 
0x8048483 <fact+19>: sub $0x1,%edx 
0x8048486 <fact+22>: jne 0x8048480 <fact+16> 
0x8048488 <fact+24>: mov %eax,%edx 
0x804848a <fact+26>: sar $0x1f,%edx 
0x804848d <fact+29>: pop %ebp 
0x804848e <fact+30>: ret

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

0x8048470 <fact>: push %ebp 
0x8048471 <fact+1>: mov %esp,%ebp 
0x8048473 <fact+3>: push %edi 
0x8048474 <fact+4>: push %esi 
0x8048475 <fact+5>: push %ebx 
0x8048476 <fact+6>: sub $0x14,%esp 
0x8048479 <fact+9>: mov 0x8(%ebp),%eax 
0x804847c <fact+12>: movl $0x1,-0x18(%ebp) 
0x8048483 <fact+19>: movl $0x0,-0x14(%ebp) 
0x804848a <fact+26>: test %eax,%eax 
0x804848c <fact+28>: je  0x80484fc <fact+140> 
0x804848e <fact+30>: mov %eax,%ecx 
0x8048490 <fact+32>: mov %eax,%esi 
0x8048492 <fact+34>: sar $0x1f,%ecx 
0x8048495 <fact+37>: add $0xffffffff,%esi 
0x8048498 <fact+40>: mov %ecx,%edi 
0x804849a <fact+42>: mov %eax,%edx 
0x804849c <fact+44>: adc $0xffffffff,%edi 
0x804849f <fact+47>: sub $0x1,%eax 
0x80484a2 <fact+50>: mov %eax,-0x18(%ebp) 
0x80484a5 <fact+53>: movl $0x0,-0x14(%ebp) 
0x80484ac <fact+60>: sub -0x18(%ebp),%esi 
0x80484af <fact+63>: mov %edx,-0x20(%ebp) 
0x80484b2 <fact+66>: sbb -0x14(%ebp),%edi 
0x80484b5 <fact+69>: movl $0x1,-0x18(%ebp) 
0x80484bc <fact+76>: movl $0x0,-0x14(%ebp) 
0x80484c3 <fact+83>: mov %ecx,-0x1c(%ebp) 
0x80484c6 <fact+86>: xchg %ax,%ax 
0x80484c8 <fact+88>: mov -0x14(%ebp),%ecx 
0x80484cb <fact+91>: mov -0x18(%ebp),%ebx 
0x80484ce <fact+94>: imul -0x1c(%ebp),%ebx 
0x80484d2 <fact+98>: imul -0x20(%ebp),%ecx 
0x80484d6 <fact+102>: mov -0x18(%ebp),%eax 
0x80484d9 <fact+105>: mull -0x20(%ebp) 
0x80484dc <fact+108>: add %ebx,%ecx 
0x80484de <fact+110>: add %ecx,%edx 
0x80484e0 <fact+112>: addl $0xffffffff,-0x20(%ebp) 
0x80484e4 <fact+116>: adcl $0xffffffff,-0x1c(%ebp) 
0x80484e8 <fact+120>: mov -0x1c(%ebp),%ebx 
0x80484eb <fact+123>: mov %eax,-0x18(%ebp) 
0x80484ee <fact+126>: mov -0x20(%ebp),%eax 
0x80484f1 <fact+129>: mov %edx,-0x14(%ebp) 
0x80484f4 <fact+132>: xor %edi,%ebx 
0x80484f6 <fact+134>: xor %esi,%eax 
0x80484f8 <fact+136>: or  %eax,%ebx 
0x80484fa <fact+138>: jne 0x80484c8 <fact+88> 
0x80484fc <fact+140>: mov -0x18(%ebp),%eax 
0x80484ff <fact+143>: mov -0x14(%ebp),%edx 
0x8048502 <fact+146>: add $0x14,%esp 
0x8048505 <fact+149>: pop %ebx 
0x8048506 <fact+150>: pop %esi 
0x8048507 <fact+151>: pop %edi 
0x8048508 <fact+152>: pop %ebp 
0x8048509 <fact+153>: ret

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

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

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

источник

2012-03-22 0xhacker

Вы должны включить сгенерированную сборку в свой вопрос (соответствующие части), что поможет ответчикам прокомментировать происходящее. –

Программа 2 делает long long расчетов, прогтрам 1 не имеет.

источник

2012-03-22 18:05:19

Вы были быстрее. :) –

Почему это дифференцирование ч/б двух программ? –

@Pavan: Первая версия умножает cont, которая является int. Вторая версия умножает результат, который является длинным длинным int. –

Разница заключается в том, что в первой версии используется переменная int для расчета, которая затем заканчивается на unsigned long long, в то время как последняя использует полностью unsigned long long.

источник

2012-03-22 18:10:45

Компилятор, похоже, оптимизировал рекурсивные вызовы в циклы. Обратите внимание, что ваш C-код имеет только ветви вперед (if-then-else), но у ассемблера есть обратные ветви (петли).

Если вы действительно хотите увидеть оптимизацию хвостового вызова в действии, вызовите ли вы другую функцию. Конечно, это не рекурсия, но компилятор слишком умен для небольших тестовых случаев, подобных этому.

источник

2012-03-22 20:20:25 ams

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

ответ

Смежные вопросы