通过优化编译器递归程序

我从尾调用优化的问题，促使What Is Tail Call Optimization?通过优化编译器递归程序

所以，我决定，看我怎么能做到这一点在平原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。

来源

2012-03-22 0xhacker

你应该在你的问题中包含生成的程序集（相关部分），这将有助于回答者评论正在发生的事情。 – 2012-03-22 14:42:38

程序2确实是long long计算，progtlram 1没有。

来源

2012-03-22 18:05:19

你速度更快。 :) – 2012-03-22 18:11:25

为什么这种差异b/w的2个方案？ – 2012-03-22 18:16:39

@Pavan：第一个版本乘以cont，这是一个int。第二个版本将结果乘以长整型int。 – 2012-03-22 18:22:38

所不同的是所述第一版本使用进行计算，然后将其在端部延伸到一个unsigned long long可变int，而后者使用的unsigned long long一路。

来源

2012-03-22 18:10:45

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

如果您确实想看到尾部呼叫优化的动作，让它调用不同的功能。当然，这不是递归，但编译器对于像这样的小测试用例来说太聪明了。

来源

2012-03-22 20:20:25 ams

通过优化编译器递归程序

回答

相关问题