gcc (より具体的には g++) が特定の関数で末尾再帰を最適化しているかどうかを確認するにはどうすればよいですか? (何度か出てきたので: gcc が一般に末尾再帰を最適化できるかどうかをテストしたくありません。末尾再帰関数が最適化されるかどうかを知りたいです。 )
あなたの答えが「生成されたアセンブラを見てください」である場合、探しているものを正確に知りたいのですが、アセンブラを調べて最適化があるかどうかを確認する簡単なプログラムを作成できるかどうかを知りたいです。
PS。これは、末尾再帰の最適化を行う C++ コンパイラがあるとすれば、それはどれですか? 5ヶ月前から。しかし、その質問のこの部分は十分に答えられたとは思いません。（答えは、「コンパイラが最適化を行ったかどうかを確認する最も簡単な方法（私が知っている）は、そうでなければスタックオーバーフローを引き起こす呼び出しを実行するか、アセンブリ出力を調べることです。」）
他の質問のコード例を使用しましょう。コンパイルしますが、gcc にアセンブルしないように指示します。
gcc -std=c99 -S -O2 test.c
次に、結果のtest.sファイル (Mac OS 10.5 上の gcc 4.0.1)の_atoi関数を見てみましょう。
.text
.align 4,0x90
_atoi:
pushl %ebp
testl %eax, %eax
movl %esp, %ebp
movl %eax, %ecx
je L3
.align 4,0x90
L5:
movzbl (%ecx), %eax
testb %al, %al
je L3
leal (%edx,%edx,4), %edx
movsbl %al,%eax
incl %ecx
leal -48(%eax,%edx,2), %edx
jne L5
.align 4,0x90
L3:
leave
movl %edx, %eax
ret
コンパイラは、この関数に対して末尾呼び出しの最適化を実行しました。call元の C コードには明らかに関数呼び出しがあったのに対し、そのコードには命令がないため、それがわかります。さらに、jne L5関数内で逆方向にジャンプする命令を確認できます。これは、C コードに明らかにループがなかったときにループを示しています。最適化をオフにして再コンパイルすると、 という行が表示されcall _atoi、後方へのジャンプも表示されません。
これを自動化できるかどうかは別の問題です。アセンブラ コードの詳細は、コンパイルするコードによって異なります。
プログラムで発見できると思います。関数がスタック ポインターの現在の値を出力するようにします (x86 で ESP を登録します)。関数が最初の呼び出しで再帰呼び出しと同じ値を出力する場合、コンパイラは末尾呼び出しの最適化を実行しています。ただし、この考えでは、観察したい関数を変更する必要があり、コンパイラが関数を最適化する方法に影響を与える可能性があります。テストが成功した場合 (同じ ESP 値が両方とも出力された場合)、計測器を使用せずに最適化も実行されると想定するのが妥当だと思いますが、テストが失敗した場合、失敗が原因であったかどうかはわかりません。インストルメンテーション コードの追加。
EDIT私の元の投稿では、GCC が実際にテール コールを削除することもできませんでした。とにかく GCC をだましてテール コールの除去を行わせる、いくつかのトリッキーな機能を以下に追加しました。
Steven の回答を拡張すると、同じスタック フレームがあるかどうかをプログラムで確認できます。
#include <stdio.h>
// We need to get a reference to the stack without spooking GCC into turning
// off tail-call elimination
int oracle2(void) {
char oracle; int oracle2 = (int)&oracle; return oracle2;
}
void myCoolFunction(params, ..., int tailRecursionCheck) {
int oracle = oracle2();
if( tailRecursionCheck && tailRecursionCheck != oracle ) {
printf("GCC did not optimize this call.\n");
}
// ... more code ...
// The return is significant... GCC won't eliminate the call otherwise
return myCoolFunction( ..., oracle);
}
int main(int argc, char *argv[]) {
myCoolFunction(..., 0);
return 0;
}
関数を非再帰的に呼び出す場合は、check パラメータに 0 を渡します。それ以外の場合は、oracle を渡します。削除されるべき末尾再帰呼び出しが削除されなかった場合は、実行時に通知されます。
これをテストすると、私のバージョンの GCC は最初のテール コールを最適化していないように見えますが、残りのテール コールは最適化されています。面白い。
生成されたアセンブリ コードを見て、x86 での再帰呼び出しにcallor命令が使用されているかどうかを確認します (他のアーキテクチャの場合は、対応する命令を調べてください)。jmpとを使用nmしobjdumpて、関数に対応するアセンブリだけを取得できます。次の関数を検討してください。
int fact(int n)
{
return n <= 1 ? 1 : n * fact(n-1);
}
次のようにコンパイル
gcc fact.c -c -o fact.o -O2
次に、末尾再帰を使用しているかどうかをテストします。
# get starting address and size of function fact from nm
ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2)
# strip leading 0's to avoid being interpreted by objdump as octal addresses
STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/')
SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//')
STOPADDR=$(( $STARTADDR + $SIZE ))
# now disassemble the function and look for an instruction of the form
# call addr <fact+offset>
if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \
grep -qE 'call +[0-9a-f]+ <fact\+'
then
echo "fact is NOT tail recursive"
else
echo "fact is tail recursive"
fi
上記の関数で実行すると、このスクリプトは「fact is tail recursive」と出力します。-O3代わりに を使用してコンパイルすると-O2、不思議なことに「ファクトは末尾再帰ではありません」と出力されます。
ehemient がコメントで指摘したように、これは偽陰性をもたらす可能性があることに注意してください。このスクリプトは、関数にそれ自体への再帰呼び出しがまったく含まれておらず、兄弟再帰も検出されない場合にのみ正しい答えを生成します (例: whereがwhich を呼び出すA()) 。現時点では、生成されたアセンブリを人間の目で見る必要のない、より堅牢な方法は考えられませんが、少なくともこのスクリプトを使用して、オブジェクト ファイル内の特定の関数に対応するアセンブリを簡単に取得できます。B()A()
PolyThinker の回答を拡張して、具体的な例を示します。
int foo(int a, int b) {
if (a && b)
return foo(a - 1, b - 1);
return a + b;
}
i686-pc-linux-gnu-gcc-4.3.2 -Os -fno-optimize-sibling-calls出力：
00000000 <フー>: 0: 55 プッシュ %ebp 1: 89 e5 mov %esp,%ebp 3: 8b 55 08 mov 0x8(%ebp),%edx 6: 8b 45 0c mov 0xc(%ebp),%eax 9: 85 d2 テスト %edx,%edx b: 74 16 je 23 <foo+0x23> d: 85 c0 テスト %eax,%eax f: 74 12 je 23 <foo+0x23> 11: 51 プッシュ %ecx 12: 12 月 48 日 %eax 13: 51 プッシュ %ecx 14: 50 プッシュ %eax 15: 8d 42 ffリー -0x1(%edx),%eax 18: 50 プッシュ %eax 19: e8 fc ff ff ff コール 1a <foo+0x1a> 1e: 83 c4 10 追加 $0x10,%esp 21: eb 02 jmp 25 <foo+0x25> 23:01 d0 %edx、%eax を追加 25: c9 立ち去る 26: c3 ret
i686-pc-linux-gnu-gcc-4.3.2 -Os出力：
00000000 <フー>: 0: 55 プッシュ %ebp 1: 89 e5 mov %esp,%ebp 3: 8b 55 08 mov 0x8(%ebp),%edx 6: 8b 45 0c mov 0xc(%ebp),%eax 9: 85 d2 テスト %edx,%edx b: 74 08 je 15 <foo+0x15> d: 85 c0 テスト %eax,%eax f: 74 04 je 15 <foo+0x15> 11: 12 月 48 日 %eax 12: 4a dec %edx 13: eb f4 jmp 9 <foo+0x9> 15: 5d ポップ %ebp 16:01 d0 %edx,%eax を追加 18: c3 ret
最初のケースで<foo+0x11>-<foo+0x1d>は、関数呼び出しの引数をプッシュし、2 番目のケースでは、プリアンブルの後のどこかで<foo+0x11>-<foo+0x14>変数と s を同じ関数に変更します。jmpそれがあなたが探したいものです。
プログラムでこれを行うことはできないと思います。可能性のあるバリエーションが多すぎます。関数の「肉」は、開始点に近いか離れている可能性があり、jmpそれを見ずにループまたは条件付きと区別することはできません。の代わりに条件付きジャンプである可能性がありますjmp。 gcc場合によっては をそのままにしておくかもしれませんが、call他の場合には兄弟呼び出しの最適化を適用します。
参考までに、gcc の「兄弟呼び出し」は、末尾再帰呼び出しよりも少し一般的です。事実上、同じスタック フレームを再利用しても問題ない関数呼び出しは、潜在的に兄弟呼び出しです。
[編集]
自己再帰を探すだけでcall誤解を招く例として、
int bar(int n) {
if (n == 0)
return bar(bar(1));
if (n % 2)
return n;
return bar(n / 2);
}
GCC は、兄弟呼び出しの最適化を 3 つのbar呼び出しのうち 2 つに適用します。call <bar+..>生成されたアセンブリにa があっても、その単一の最適化されていない呼び出しが単一のレベルより先に進むことはないため、私はこれを末尾呼び出し最適化と呼んでいます。
私は分解を見るのが面倒です。これを試して：
void so(long l)
{
++l;
so(l);
}
int main(int argc, char ** argv)
{
so(0);
return 0;
}
このプログラムをコンパイルして実行します。永久に実行される場合、末尾再帰は最適化されていません。スタックを吹き飛ばした場合、そうではありませんでした。
編集:申し訳ありませんが、読むのが速すぎます.OPは、特定の関数の末尾再帰が最適化されているかどうかを知りたがっています。わかった...
...原則は同じです-末尾再帰が最適化されている場合、スタックフレームは同じままです。バックトレース関数を使用して、関数内からスタック フレームをキャプチャし、それらが成長しているかどうかを判断できる必要があります。末尾再帰が最適化されていない場合、 buffer にはリターン ポインターが 1 つしかありません。
これを確認した別の方法は次のとおりです。
簡単な方法: 簡単な末尾再帰プログラムを作成し、コンパイルし、逆アセンブルして、最適化されているかどうかを確認します。
質問にすでにそれがあることに気づきました。アセンブリの読み方を知っていれば、見分けるのは非常に簡単です。再帰関数は関数本体内から (「呼び出しラベル」を使用して) 自分自身を呼び出し、ループは単に「jmp ラベル」になります。
最適化がない場合、その関数呼び出しの再帰が深すぎるためにスタック オーバーフローにつながる入力データを作成し、それが発生するかどうかを確認できます。もちろん、これは些細なことではなく、入力が十分に大きいと、関数が耐えられないほど長時間実行されることがあります。