末尾再帰最適化をC/C++上で検知してみたい
某所で「処理系が末尾再帰最適化をしているかを、処理系で動くコードから判定できるか」的な話をふったところ
C/C++ なら出来そうだよねと id:yaneurao さんからツッコミが。
やってみよう。
最適化されているなら is_tail_rec_opt_internal の引数である level は再帰しないのだから常に同じアドレスにいるはずだという予想の元に判定をしている。
int is_tail_rec_opt_internal(int level, int* p) { if (0 == level) { return &level == p; } else { return is_tail_rec_opt_internal(--level, &level); } } int is_tail_rec_opt() { return is_tail_rec_opt_internal(1024, NULL); } int main(int argc, char *argv[]) { printf("tail recursion call optimized? : %s\n", is_tail_rec_opt() ? "true" : "false"); return 0; }
このコードを gcc / icc で -O3 でコンパイルしてみて実行。
どちらの場合も false が返る。
じゃあ実際のところ最適化されているのか -S したところ、
# -- Begin _Z24is_tail_rec_opt_internaliPi # mark_begin; .align 2,0x90 .globl _Z24is_tail_rec_opt_internaliPi _Z24is_tail_rec_opt_internaliPi: # parameter 1: 4 + %esp # parameter 2: 8 + %esp # 略 call _Z24is_tail_rec_opt_internaliPi #27.16 # 略 ret #27.16
あれれ。末尾再帰呼出し最適化されてないな。
少なくとも gcc 4.0 では
-foptimize-sibling-calls Optimize sibling and tail recursive calls. Enabled at levels -O2, -O3, -Os.
こんなオプションが有効になっているはずなのに。
結局判定結果は正しいのだけど、末尾再帰最適化を有効にできていないので片手落ちな感じ。
他のコンパイラだと違う結果になったりするのかな。もし良かったら誰か試してみてください_(__)_
ちなみに再帰しまくるコードを書いてみて、スタックオーバーフローするかどうか判定するってのはありそうだけど美しくない。
