末尾呼出の最適化とは
末尾呼出の最適化とは、ある関数f()の最後が別の関数g()を呼び出しているだけの場合、g()の呼出をcallでなくjmpに変える最適化です。わずかですが速度とサイズの両方を改善する反面、デメリットが非常に少なく、定数畳み込みと並んで私の好きな最適化の一つです。
組み込み環境では、シリアルポートのような周辺デバイスへのアクセスに、直接レジスタにアクセスするのではなく、普通は何かしらのラッパーを用意します。その結果、シリアルポートを有効にする関数が、ラッパーを2つほど通ってoutp()相当の1命令に過ぎないというような状況は良く発生します。組み込み環境では、比較的よく遭遇する最適化だと思います。
MISPにおけるcall/retは、jal/j になります。関数呼び出しMIPS編に簡単にまとめてあります。
最適化する前のコード
f()がg()を呼んで、g()がh()を呼ぶだけのCソースです。h()の中でdummy()を呼んでいるのは、最適化により丸ごと関数呼び出しが削除されてしまうのを防いでいます。
int f(void); void g(void); void h(void); extern void dummy(void); int f(void) { g(); return 0; } void g(void) { h(); } void h(void) { dummy(); }
最適化オプション無しでコンパイルするとこうなります。
f: addiu $sp,$sp,-24 sw $31,20($sp) sw $fp,16($sp) move $fp,$sp jal g nop move $2,$0 move $sp,$fp lw $31,20($sp) lw $fp,16($sp) addiu $sp,$sp,24 j $31 nop g: addiu $sp,$sp,-24 sw $31,20($sp) # 戻り先の保存 sw $fp,16($sp) move $fp,$sp jal h # h()の呼出 nop move $sp,$fp lw $31,20($sp) # 戻り先の復元 lw $fp,16($sp) addiu $sp,$sp,24 # g()から戻る j $31 nop h: addiu $sp,$sp,-24 sw $31,20($sp) sw $fp,16($sp) move $fp,$sp jal dummy nop move $sp,$fp lw $31,20($sp) lw $fp,16($sp) addiu $sp,$sp,24 j $31 nop
g()に注目してください。h()を呼び出す前にレジスタ$31に入っている戻り先をスタックに保存し、h()から戻ってきた所でスタックから$31に戻り先を復元してます。最後に、j $31でf()に戻ります。
最適化されたコード
同じソースを最適化オプション -O2 を付けてコンパイルします。
YUKI.N>sde-gcc -S -O2 tailcall.c
f: addiu $sp,$sp,-24 sw $31,16($sp) jal g nop lw $31,16($sp) move $2,$0 j $31 addiu $sp,$sp,24 g: j h nop h: j dummy nop
綺麗に最適化されています。
g()はjal h がただのj h になっていますし、戻り先の保存と復元も無くなりました。コードサイズが小さくなっただけでなく、実行速度も速くなっています。
h()も最適化されています。dummy()はこのファイルの外（コンパイル単位の外）にある関数なのですが、h()が最後にdummy()を呼び出しているだけなので、同じように最適化されます。最初のシリアルポートの例でいくと、シリアルポートのアクセス関連だけ別のCソース、もしくはコンパイル済みバイナリの提供になっていても最適化の効果があります。
最適化の仕組みは、()の呼出時(jal命令)に$31に保存された戻り番地を、そのままh()、dummy()に渡し、最後に一回だけj $31を実行しています。これで、一気にf()に戻ってこれます。もし実行中のスタックを見て関数の呼出を調べるツールがあれば、h()やdummy()の中身は、g()として実行されているように見えます。
void g(void) { goto h; h: goto dummy; dummy: /* dummy の処理 */ return ; /* dummy ここまで。returnはdummy()の中のreturn */ }
Cで擬似的に書きなおすと、こんな感じになります。
末尾呼出の最適化その2
もう一つ末尾呼出の最適化として、関数の一番最後が他の関数を呼び出した結果を返すだけ、というパターンがあります。
このように、h()はdummy()の結果を返すだけ、g()はh()の結果を返すだけ、f()はg()の結果を返すだけのパターンです。結果的に、f()はdummy()の戻りを返すだけです。
int f(void); int g(void); int h(void); extern int dummy(void); int f(void) { return g(); } int g(void) { return h(); } int h(void) { return dummy(); }
同じく -O2を付けてコンパイルするとこうなります。
f: j g nop g: j h nop h: j dummy nop
こちらも綺麗に最適化されました。dummy()を呼び出した結果、dummy()によって戻り値が$2に入っています。f()からの戻り番地は$31に入っていますので、dummy()の中でj $31を実行することで、f()の呼出元へdummy()の戻り値を渡すことが出来ます。
末尾再帰/継続との関係
練習問題ex2.16-2.18で出てくる末尾再帰は、この最適化の特殊系になります。
「なんでも継続」のつかみの部分にも、この最適化が登場します。
http://practical-scheme.net/docs/cont-j.html
