GCC對尾遞歸的優(yōu)化

linyunxian

GCC對尾遞歸的優(yōu)化
http://www.alivepea.me/prog/gcc-tail-recursion/

當(dāng)函數(shù)返回的最后一個操作是遞歸調(diào)用時就被稱作尾遞歸. 一直聽說與普通 的遞歸比起來，尾遞歸效率很高，原因是尾遞歸沒有函數(shù)棧調(diào)用的開銷。下面驗(yàn)證一下。

long long fact_aux(int n, long long result)
{
printf("Local var in stack addr: 0x%x\n", &n);

if(n<2) return result;

return fact_aux(n-1, result*n);
}

long long fact(int n)
{
return fact_aux(n, 1)
}
上面是用遞歸計算階乘的C語言實(shí)現(xiàn)，輸出結(jié)果顯示參數(shù)n在棧里的地址發(fā)現(xiàn)在遞減，說 明函數(shù)棧在不斷生成。用objdump -d或(gdb) bt也可以驗(yàn)證有沒有函數(shù)棧調(diào)用的開 銷。

1. 00000000004007e0 <fact_tr_aux>:
   
2. 4007e0:        53 push %rbx
   
3. 4007e1:        31 c0 xor %eax,%eax
   
4. 4007e3:        48 89 f3 mov %rsi,%rbx
   
5. 4007e6:        be 04 09 40 00 mov $0x400904,%esi
   
6. 4007eb:        48 83 ec 10 sub $0x10,%rsp
   
7. 4007ef:        48 8d 54 24 08 lea 0x8(%rsp),%rdx
   
8. 4007f4:        48 89 7c 24 08 mov %rdi,0x8(%rsp)
   
9. 4007f9:        bf 01 00 00 00 mov $0x1,%edi
   
10. 4007fe:        e8 4d fd ff ff callq 400550 <__printf_chk@plt>
    
11. 400803:        48 8b 7c 24 08 mov 0x8(%rsp),%rdi
    
12. 400808:        48 89 d8 mov %rbx,%rax
    
13. 40080b:        48 83 ff 01 cmp $0x1,%rdi
    
14. 40080f:        7e 10 jle 400821 <fact_tr_aux+0x41>
    
15. 400811:        48 0f af c7 imul %rdi,%rax
    
16. 400815:        48 83 ef 01 sub $0x1,%rdi
    
17. 400819:        48 89 c6 mov %rax,%rsi
    
18. 40081c:        e8 bf ff ff ff callq 4007e0 <fact_tr_aux> /* recursion call */
    
19. 400821:        48 83 c4 10 add $0x10,%rsp
    
20. 400825:        5b pop %rbx
    
21. 400826:        c3 retq
    
22. 400827:        66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
    
23. 40082e:        00 00

復(fù)制代碼

從上面的匯編上也看出依然是遞歸調(diào)用。 注釋掉源代碼的第2行, 再驗(yàn)證如下：

1. 00000000004007f0 <fact_tr_aux>:
   
2. 4007f0:        48 83 ff 01 cmp $0x1,%rdi
   
3. 4007f4:        48 89 f0 mov %rsi,%rax
   
4. 4007f7:        7e 15 jle 40080e <fact_tr_aux+0x1e>
   
5. 4007f9:        0f 1f 80 00 00 00 00 nopl 0x0(%rax)
   
6. 400800:        48 0f af c7 imul %rdi,%rax
   
7. 400804:        48 83 ef 01 sub $0x1,%rdi
   
8. 400808:        48 83 ff 01 cmp $0x1,%rdi
   
9. 40080c:        75 f2 jne 400800 <fact_tr_aux+0x10> /* recursion discard */
   
10. 40080e:        f3 c3 repz retq

復(fù)制代碼

遞歸不見了，被優(yōu)化為循環(huán)了。從上面的試驗(yàn)結(jié)果，得到下面一些淺顯的看法。

• 打開優(yōu)化選項(xiàng)~-O1 -foptimize-sibling-calls~ 或 ~-O2~后，gcc會對尾遞歸優(yōu)化。
• 尾遞歸被優(yōu)化的前提是遞歸函數(shù)不使用棧來記錄變量，也不記錄狀態(tài)。第一例沒有被 優(yōu)化就是因?yàn)閚的地址依賴函數(shù)棧。
• 尾遞歸被優(yōu)化的本質(zhì)是它的上下文不是保存在棧上，與調(diào)用者無關(guān)，這樣就可以重用 當(dāng)前的棧幀。上面的例子就是使用函數(shù)參數(shù)來記錄上下文。
• 尾遞歸是函數(shù)式編程的特性，也容易轉(zhuǎn)換成循環(huán)，在C語言中似乎沒有什么理由用它。
  

如果發(fā)現(xiàn)任何謬誤，請告訴我☺

~EOF~

captivated

1. 
   
2. ret_type foo (type para1, type para2)
   
3. {
   
4.      if (cond)
   
5.         return (no_cal_expr);
   
6. 
   
7.     stat1;
   
8.     stat2;
   
9.     ...
   
10.     statn;
    
11. 
    
12.     foo(argu1, argu2);
    
13. }
    

復(fù)制代碼

打印地址這種迫使 gcc 不能隱藏遞歸(因?yàn)楸仨毜谜故緱Ｉ献兞康拇娣?的情況, 那當(dāng)然 gcc 只好放棄優(yōu)化了.
至于尾遞歸優(yōu)化的原理太簡單了:

1. ret_type foo(type para1, type para2)
   
2. {
   
3. start:
   
4.     if (cond)
   
5.         return (no_cal_expr);
   
6.     stat1;
   
7.     stat2;
   
8.     ...
   
9.     statn;
   
10. 
    
11.     para1 = argu1, para2 = argu2;
    
12.     goto start;
    
13. }

復(fù)制代碼

captivated

PS, 尾遞歸不是什么函數(shù)式編程的特性, 函數(shù)式編程由于形式上是遞歸的, 所以見到尾遞歸為提升效率起見就會優(yōu)化掉.

linyunxian

回復(fù) 3# captivated


    嗯，對的，謝謝指正～