8

我从尾调用优化问题中得到了激励，什么是尾调用优化？

所以，我决定看看我怎么能用普通的 C 来做。

所以，我写了 2 个阶乘程序，第一个可以应用尾调用优化。我将此事实函数称为事实（n，1）。

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

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

第二个是需要多个堆栈帧的正常递归。

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 也不能转换为前者生成的程序集。

4

3 回答 3

5

程序 2long long进行计算，程序 1 没有。

于 2012-03-22T18:05:19.930 回答
4

不同的是，第一个版本使用一个int变量进行计算，然后将其扩展到unsigned long long最后，而后者unsigned long long一直使用一个。

于 2012-03-22T18:10:45.623 回答
0

编译器似乎已将递归调用优化为循环。请注意，您的 C 代码只有前向分支（if-then-else），但汇编程序有后向分支（循环）。

如果你真的想看到一个尾调用优化的实际效果，让它调用一个不同的函数。当然，这不是递归，但是编译器对于像这样的小型测试用例来说太聪明了。

于 2012-03-22T20:20:25.310 回答