Elixir プログラムの再帰呼出しが、末尾呼び出し最適化されてるか確認するために、beam ファイルに格納されたマシン語からアセンブリ言語へ逆アセンブルする方法を調べてみた。
おまけとして、beam から Erlang のソースコードへ逆コンパイルする方法も紹介する。
beam ファイル
Elixir や Erlang のプログラムをコンパイルすると、モジュールごとに beam ファイルができる。このファイルには、Erlang VM のマシン語に変換されたプログラムや、オプションでデバッグ情報が入っている。
今回調べてわかったのだが、Erlang の標準ライブラリーに用意された関数を使うと、このマシン語を逆アセンブルできる。また、デバッグ情報付きでコンパイルされている場合は、Erlang コードに逆コンパイルすることも可能だ。
末尾呼び出し最適化されているか確認したい
Elixir や Erlang では、繰り返しの処理は、再帰呼出しで実現する。ただ、これを普通の関数呼び出しと同じように呼び出してしまうと、その度にコールスタックを消費し、いずれはメモリーを使い果たしてしまう。そこで、再帰呼出しが計算の最後のステップになっている時、つまり「末尾再帰」になっている時は、関数呼び出しではなく、戻り先を保存しないジャンプ命令に最適化するようになっている。これを、「末尾呼び出し最適化」と呼ぶ。Erlang VM には、末尾再帰のための命令がいくつか用意されている。
先日、「ReconTrace で Erlang VM のトレース機能に親しむ」という記事を書いたのだが、トレース結果をみて、あれ！？っと思った。末尾再帰で書いたはずの Elixir プログラムのトレースを見ると、再帰呼び出しと同じ回数のリターンが記録されており、普通の再帰呼出しをしているように見えるのだ。
iex(14)> ReconTrace.calls({MyMath, :_, fn(_) -> :return end}, 50, [scope: :local])
9
iex(15)> MyMath.factorial_iter(5)
23:51:32.439220 <0.57.0> MyMath.__info__(:macros)
120
23:51:32.439409 <0.57.0> MyMath.__info__/1 --> []
23:51:32.439564 <0.57.0> MyMath.factorial_iter(5)
23:51:32.439644 <0.57.0> MyMath.factorial_iter1(5, 1)
23:51:32.439737 <0.57.0> MyMath.factorial_iter1(4, 5)
23:51:32.439825 <0.57.0> MyMath.factorial_iter1(3, 20)
23:51:32.439902 <0.57.0> MyMath.factorial_iter1(2, 60)
23:51:32.439987 <0.57.0> MyMath.factorial_iter1(1, 120)
23:51:32.440066 <0.57.0> MyMath.factorial_iter1(0, 120)
23:51:32.440148 <0.57.0> MyMath.factorial_iter1/2 --> 120 # return は１回だけだと思ってた
23:51:32.440221 <0.57.0> MyMath.factorial_iter1/2 --> 120
23:51:32.440297 <0.57.0> MyMath.factorial_iter1/2 --> 120
23:51:32.440374 <0.57.0> MyMath.factorial_iter1/2 --> 120
23:51:32.440446 <0.57.0> MyMath.factorial_iter1/2 --> 120
23:51:32.440517 <0.57.0> MyMath.factorial_iter1/2 --> 120
23:51:32.440590 <0.57.0> MyMath.factorial_iter/1 --> 120
こちらがそのソースコード。
def factorial_iter(n) when n >= 0, do: factorial_iter1(n, 1)
defp factorial_iter1(0, acc), do: acc
defp factorial_iter1(n, acc), do: factorial_iter1(n - 1, acc * n)
これがもし、Erlang プログラムだったら、末尾再帰になっているかをすぐに確認できる。Erlang のコンパイラー erlc に、-S オプションを与えると、beam ファイルの代わりに、アセンブラーファイルを出力してくれるので、それを眺めればいい。
これについては、以下の記事が詳しいのでお薦め。
ところが、Elixir 1.1.1 のコンパイラー elixirc には、そのようなオプションはない。試しに -S オプションにあたる ERL_COMPILER_OPTIONS=\'S'\ を与えてみたところ、コンパイラーがクラッシュしてしまった。そういう使い方は想定されていないらしい。
時間もなかったので、以下のような方法で末尾再帰になっていることを確認し、その記事では、この件には触れないことにした。
- プログラムを Erlang に移植して、アセンブラーファイルを出力。コードを確認した → OK
- Elixir プログラム中に、以下のコードを埋め込んで、再帰呼出しの時に、スタックサイズが大きくならないことを確認した → OK
word_size = :erlang.system_info({:wordsize, :internal})
stack_size_words = :erlang.process_info(self(), :stack_size) |> elem 1
stack_size_bytes = stack_size_words * word_size
末尾呼び出し最適化になっているっぽいことは確認できたので、トレースで呼び出しと同じ回数 return するのは、きっとトレース結果をわかりやすくするために、中の人（トレース対象になったプロセス）が頑張ってるんでしょう。という結論に至った。 実際、トレースをかけながら、スタックサイズを観察すると、末尾再帰の時でもスタックサイズが不規則に増減するので、トレースのためになにかの情報をトラッキングしているように思えた。
2015年12月29日訂正： OTP のマニュアルによると、戻り値を表示させるオプション付きでトレースをすると、その間、末尾呼び出し最適化が解除されてしまうそうです。詳しくはこちら。
でも、なんだかすっきりしないところに、@hykw さんが、以下の記事を書かれていた。
実際その通りなのか、またどれぐらいでスタックが溢れるのか（どれぐらいまでなら、スタックを気にせず再帰させられるのか）を知るため、実際に再帰処理をしてみて確認してみました。
...
約１時間動かしてみた後のメモリ使用量です。末尾再帰版は、最初から最後まで、ほとんど変動ありませんでした。
やはり、実験だけでなく、コードも見てみたい。これは、Elixir でもアセンブリーコードを見るしかないでしょう！ ということで、いろいろと試行錯誤しながら、Erlang/OTP のドキュメントやテストコードを読んだり、Elixir のコンパイラーのコードを読んだりしたところ、最終的に、beam ファイルから、簡単に逆アセンブルできることがわかった。
逆アセンブル
まずはそのコードを紹介。Elixir で書いたが、Erlang の標準ライブラリーしか使ってないので、Erlang への移植は簡単にできる。
defmodule BeamSpy do
@spec disassemble(module) ::
{:ok, asm_code :: [tuple], asm_file :: :file.path} | {:error, term}
def disassemble(module) do
case read_abstract_code(module) do
{:ok, path, ac} ->
case :compile.noenv_forms(ac, [:S]) do
{:ok, _, {_erl_module, _exports, _attribs, asm_codes, _labels}} ->
asm_dir = :file.get_cwd |> elem 1
asm_name = :filename.basename(path, '.beam') ++ '.S'
{:ok, asm_codes, :filename.join(asm_dir, asm_name)}
:error ->
{:error, :unkown_compile_error}
{:error, errors, warnings} ->
{:error, {:compile_error, errors, warnings}}
end
{:error, _}=err ->
err
end
end
@spec decompile_to_erl(module) :: :ok | {:error, term}
def decompile_to_erl(module) do
case read_abstract_code(module) do
{:ok, _path, ac} ->
:erl_syntax.form_list(ac) |> :erl_prettypr.format |> IO.puts
:ok
{:error, _}=err ->
err
end
end
@spec read_abstract_code(module) :: {:ok, :file.path, [tuple]} | {:error, term}
defp read_abstract_code(module) do
case :code.which(module) do
:non_existing ->
{:error, {:non_existing, module}}
path when is_list(path) ->
case :beam_lib.chunks(path, [:abstract_code]) do
{:ok, {_, [{:abstract_code, {_, ac}}]}} ->
{:ok, path, ac}
{:error, :bean_lib, reason} ->
{:error, reason}
end
end
end
end
disassemble/1 が逆アセンブル、decompile_to_erl/1 が Erlang コードへの逆コンパイルだ。
では、試してみよう。今回私は Elixir 1.1.1 と Erlang/OTP 18.2.1 を使用した。
iex(1)> c "beam_spy.ex"
[BeamSpy]
例としてこの Elixir プログラムを使用する。
defmodule MyMath do
@spec factorial(non_neg_integer) :: non_neg_integer
def factorial(0), do: 1
def factorial(n) when n > 0, do: n * factorial(n - 1)
@spec factorial_iter(non_neg_integer) :: non_neg_integer
def factorial_iter(n) when n >= 0, do: factorial_iter1(n, 1)
defp factorial_iter1(0, acc), do: acc
defp factorial_iter1(n, acc), do: factorial_iter1(n - 1, acc * n)
end
iex(2)> c "my_math.ex"
[MyMath]
MyMath モジュールを逆アセンブルする。
iex(3)> BeamSpy.disassemble MyMath
{:ok,
[{:function, :__info__, 1, 2,
...（中略）...
{:function, :factorial_iter1, 2, 7,
[{:label, 6}, {:line, [{:location, 'my_math.ex', 10}]},
{:func_info, {:atom, MyMath}, {:atom, :factorial_iter1}, 2}, {:label, 7},
{:test, :is_eq_exact, {:f, 8}, [x: 0, integer: 0]},
{:move, {:x, 1}, {:x, 0}}, :return, {:label, 8},
{:line, [{:location, 'my_math.ex', 11}]},
{:gc_bif, :-, {:f, 0}, 2, [x: 0, integer: 1], {:x, 2}},
{:line, [{:location, 'my_math.ex', 11}]},
{:gc_bif, :*, {:f, 0}, 3, [x: 1, x: 0], {:x, 1}}, {:move, {:x, 2}, {:x, 0}},
{:call_only, 2, {:f, 7}}]},
{:function, :factorial, 1, 10,
[{:label, 9}, {:line, [{:location, 'my_math.ex', 4}]},
{:func_info, {:atom, MyMath}, {:atom, :factorial}, 1}, {:label, 10},
{:test, :is_eq_exact, {:f, 11}, [x: 0, integer: 0]},
{:move, {:integer, 1}, {:x, 0}}, :return, {:label, 11},
{:test, :is_lt, {:f, 9}, [integer: 0, x: 0]}, {:allocate_zero, 1, 1},
{:line, [{:location, 'my_math.ex', 5}]},
{:gc_bif, :-, {:f, 0}, 1, [x: 0, integer: 1], {:x, 1}},
{:move, {:x, 0}, {:y, 0}}, {:move, {:x, 1}, {:x, 0}},
{:line, [{:location, 'my_math.ex', 5}]}, {:call, 1, {:f, 10}},
{:line, [{:location, 'my_math.ex', 5}]},
{:gc_bif, :*, {:f, 0}, 1, [y: 0, x: 0], {:x, 0}}, {:deallocate, 1},
:return]},
...（中略）...
],
'/usr/home/tatsuya/tmp/Elixir.MyMath.S'}
iex(4)>
:factorial_iter1 の方は、{:call_only, 2, {:f, 7}} となっていることから、末尾再帰していることがわかる。プログラムによっては :call_only の代わりに、:call_last、:call_ext_only、:call_ext_last となっていることもあるが、これらも末尾再帰の一種だ。
一方、:factorial は、{:call, 1, {:f, 10}} や :return があることから、末尾再帰になっていないことがわかる。{:gc_bif, :* ...} となっているように、{:call, ...} の戻り値を使って乗算（*）しなけれはならないので、末尾呼び出し最適化は不可能だ。
なお、もしプログラムが長いと、iex 上では途中から表示が省略されてしまう。その時は、最後にアセンブラーファイルのパスが出ているので（上の例では '/usr/home/tatsuya/tmp/Elixir.MyMath.S'）、そのファイルを開いてみればいい。
おまけ：Erlang コードへ逆コンパイル
おまけとして、Erlang コードへの逆コンパイルの方法も紹介する。残念ながら、Elixir コードまで戻すことはできない。また、逆コンパイルするためには beam ファイルがデバッグ情報(debug_info)オプション付きでコンパイルされている必要がある。なお、Elixir 1.2 RC のコンパイラーのコードを読んだところ、常にデバッグ情報付きでコンパイルされるようになっていた。
iex(5)> BeamSpy.decompile_to_erl MyMath
-compile(no_auto_import).
-file("my_math.ex", 1).
-module('Elixir.MyMath').
...（中略）...
factorial_iter1(0, acc@1) -> acc@1;
factorial_iter1(n@1, acc@1) ->
factorial_iter1(n@1 - 1, acc@1 * n@1).
factorial(0) -> 1;
factorial(n@1) when n@1 > 0 -> n@1 * factorial(n@1 - 1).
factorial_iter(n@1) when n@1 >= 0 ->
factorial_iter1(n@1, 1).
:ok
ちなみに、今回使った逆コンパイル方法は、OTP のマニュアルにもちゃんと書いてある。また、同マニュアルでは、デバッグ情報は付けたいが、逆コンパイルされては困る人のために、デバッグ情報を暗号化する方法も書かれている。
まとめ
- Erlang/OTP の標準ライブラリーを使うと、beam ファイル内の Erlang VM マシン語を逆アセンブルできる
- アセンブリーコードを眺めると、末尾呼び出し最適化が行われていることなどが確認できる