erlangのアセンブリを読んでみる.
Erlangが末尾再帰最適化をしてるか調べようとした - みずぴー日記
に興味が湧いたので,erlangのアセンブリコードを見てみた.beamのバイトコードにほぼ一対一対応していると考えていいと思う.
まず単純な定義の場合
fact(0) -> 1; fact(N) -> N * fact(N-1).
以下のようになる.アセンブリコードの各行はそのままerlangのタプルとなっている.ここで,
- {x, N}: はx registerという.Nはレジスタ番号.
- {y, N}: はy registerという.レジスタという名前だが,スタック上に置かれる.
- {f, N}: は{label, N}に対応している.{f, 0}はプログラム終了コードのラベル.
{function, fact, 1, 2}. % 引数1個, {label,2}がエントリーポイントという意味. {label,1}. {func_info,{atom,fact},{atom,fact},1}. {label,2}. % 引数は{x, 0}に入っている. {test,is_eq_exact,{f,3},[{x,0},{integer,0}]}. % N!=0なら{label, 3}に飛ぶ {move,{integer,1},{x,0}}. % 戻り値は{x, 0}に入れる return. {label,3}. {allocate_zero,1,1}. % スタックフレームを1ワード分確保. {gc_bif,'-',{f,0},1,[{x,0},{integer,1}],{x,1}}. {move,{x,0},{y,0}}. % もとのNをスタックに退避 {move,{x,1},{x,0}}. {call,1,{f,2}}. % 再帰呼び出し.1は引数の数を表す. {gc_bif,'*',{f,0},1,[{y,0},{x,0}],{x,0}}. {'%live',1}. {deallocate,1}. return.
見ての通りerlangだからといって何も特殊な点はなく,いたって普通のコードだった.
スタックも通常どおり消費されているので,Erlangが末尾再帰最適化をしてるか調べようとした - みずぴー日記でスタックオーバーフローしないというのは単にスタックを大きく取れているからなのだと思う.
続いて末尾再帰バージョンを見てみる。
fact(N) -> fact_iter(N, 1). fact_iter(0, R) -> R; fact_iter(N, R) -> fact_iter(N-1, N*R).
{function, fact, 1, 2}. {label,1}. {func_info,{atom,fact},{atom,fact},1}. {label,2}. {move,{integer,1},{x,1}}. {'%live',2}. {call_only,2,{f,4}}. {function, fact_iter, 2, 4}. {label,3}. {func_info,{atom,fact},{atom,fact_iter},2}. {label,4}. {test,is_eq_exact,{f,5},[{x,0},{integer,0}]}. {move,{x,1},{x,0}}. return. {label,5}. {gc_bif,'-',{f,0},2,[{x,0},{integer,1}],{x,2}}. {gc_bif,'*',{f,0},3,[{x,0},{x,1}],{x,1}}. {move,{x,2},{x,0}}. {call_only,2,{f,4}}.
末尾呼び出しの部分がcall_onlyとなっているので,確かに末尾再帰の最適化が行われている事が分かる.y registerが使われていない事からもスタックが消費されていないことが見て取れる.
ところでこれらのコードをみる限り,スケジューラとレジスタ割り当てがあまり賢くないようだ.
コンパイル時間を優先して簡略化しているのかな.[追記]コンパイラを見てみたら、そもそも命令スケジューリングを行っていないように見えた.もしかしたらアセンブリ -> バイトコードのフェーズか,beam側で何かやっているかも知れない.