ホワット・ア・ワンダフル・ワールド GCC の末尾再帰最適化まとめ
参照 : gcc/tree-tailcall.c 要するに，GCC がジャンプに最適化できる再帰呼び出しは，以下のようなパターンの組み合わせにプログラム変換可能な場合 (あと static 変数とか extern 変数とか大域変数とか，sjlj (GCC 内部での例外というか unwind の実装というか setjmp/longjmp) 呼び出しとか，とにかく副作用が入ってたら全て駄目)． ※ 追記 : 副作用という言い方は曖昧でした．入出力とかはたぶん大丈夫．ローカルじゃない変数に対する読みだしとか書き込みとか，途中で大域ジャンプとかの可能性が混じると，GCC は最適化を諦めます．suitable_for_tail_opt_p () という関数で最適化するか否かを決めているみたい． (1) return x x は定数．これは加算と乗算それぞれの累積変数 a_acc/m_acc と組み合
末尾再帰最適化判定 - やねうらおブログ(移転しました)
C++でコンパイラが末尾最適化を行なっているのかを判定するコードを考えてみた。 私は最初、id:higepon:20070804:1186241590のコードを思いついたのだけど、このプログラムは誤りだった。関数のなかでアドレス演算子&でアドレスをとると、そのアドレスを外部から参照されて変更とかされたときに、N回目の再帰とM回目(N!=M)の再帰とで異なるアドレス指していないと元のプログラムと等価にならない。 だから途中でアドレスをとると末尾再帰の最適化は行なわれないのだろう。 修正案は、こうだ。 #include <stdio.h> #include <stdlib.h> int* tail_rec_opt_internal(int level) { if (level == 0) return &level; return tail_rec_opt_internal(--level);
末尾再帰最適化をC/C++上で検知してみたい - higepon blog
某所で「処理系が末尾再帰最適化をしているかを、処理系で動くコードから判定できるか」的な話をふったところ 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(102
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
