どのように 'スマート'はGCCのテールコール最適化ですか？ forループ</p> <p>：

Question

私はちょうどCコードは、次の2 peicesが議論されていた議論を行った

#include <stdio.h> 
#define n (196607) 

int main() { 
    long loop; 
    int count=0; 
    for (loop=0;loop<n;loop++) { 
    count++; 
    } 
    printf("Result = %d\n",count); 

    return 0; 
} 

再帰：

#include <stdio.h> 
#define n (196607) 

long recursive(long loop) { 
    return (loop>0) ? recursive(loop-1)+1: 0; 
} 

int main() { 
    long result; 
    result = recursive(n); 
    printf("Result = %d\n",result); 
    return 0; 
} 

をこのコードを見て、私は見ましたrecursive(loop-1)+1と呼ばれ、recursiveへの呼び出しが完了した後に行う作業があるため、「ああ、それは再帰的な呼び出しではありません。戻り値をインクリメントする必要があります。

もちろん、最適化を行わないと、再帰的コードは期待どおりスタックオーバーフローを引き起こします。

と-O2というフラグが付いていますが、スタックのオーバーフローは発生しません。これは、スタック上にスタックを再利用するのではなく、スタックを再利用するという意味です。

GCCは明らかにこの単純なケースを検出して（値を返すよう+1）、それを最適化することはできますが、それはどれくらいかかりますか？

再帰呼び出しが実行される最後の操作ではない場合、gccがtcoで最適化できる制限は何ですか？

補足： コードの完全な末尾再帰return function();バージョンを作成しました。確かに同じ順序であるように見えるん

$ for f in *.exe; do time ./$f > results; done 
+ for f in '*.exe' 
+ ./forLoop.c.exe 

real 0m3.650s 
user 0m3.588s 
sys  0m0.061s 
+ for f in '*.exe' 
+ ./recursive.c.exe 

real 0m3.682s 
user 0m3.588s 
sys  0m0.093s 
+ for f in '*.exe' 
+ ./tail_recursive.c.exe 

real 0m3.697s 
user 0m3.588s 
sys  0m0.077s 

ので、（確かに簡単で、非常に厳密ではない）ベンチマークは示しています9999999回の反復でループに上記のラッピング 、私は次のタイミングを思い付きました撮影時間。

Answer 1

コードを逆アセンブルして何が起こったかを確認してください。最適化がなければ、私はこれを取得：

0x0040150B cmpl $0x0,0x10(%rbp) 
0x0040150F jle 0x401523 <recursive+35> 
0x00401511 mov 0x10(%rbp),%eax 
0x00401514 sub $0x1,%eax 
0x00401517 mov %eax,%ecx 
0x00401519 callq 0x401500 <recursive> 

しかし、-O1、-O2または-O3で、私はこれを取得：

0x00402D09 mov $0x2ffff,%edx 

これは、テール最適化を行うには何が、はるかに多くを持っていません根本的な最適化。コンパイラは単に関数全体をインライン展開し、結果を事前に計算しました。

これは、さまざまなベンチマークのすべてのケースで同じ結果に終わる可能性が高いためです。