Erlangのアセンブラと仲良くなる

速度を求めている人がErlangを使う事はないと思うが, 信頼性を求めてErlangを使っている人が性能向上を図ることは割とよくある話だと思う.
そして, アセンブラを眺めたくなることもよくある話だと思う.

ふと, アセンブラを眺めたくなり, AdventCalendarがまだ埋まっていなかったので, この機会に調べたことを纏めてみる.

Erlangのアセンブラを見る方法

$ erlc -S hoge.erl
$ ls
hoge.erl hoge.S
# hoge.Sがアセンブラ

アセンブラの読み方

アセンブラに登場するキーワードは下記に書かれている.
https://github.com/erlang/otp/blob/maint/lib/compiler/src/genop.tab

主要なものを纏めたのが以下の表だ.

書式	例	説明
{x, N}	{x, 0}	レジスタの場所を指す
{y, N}	{y, 0}	スタックの場所を指す
{f, N}	{f, 0}	{label, N}を指す
{label, Lbl}	{label, 1}	codeの場所を示す名前.
{func_info, M, F, A}	{func_info, lists, reverse, 1}	関数定義. 例はlists:reverse/1を意味する.
{call, Arity Label}	{call, 1, {f, 7}}	関数を呼び出す.呼び出し後は次の命令が呼ばれる. 例は引数1の{label, 7}を実行する.
{call_only, Arity, Label}	{call_only, 1, {f, 7}}	末尾再帰関数を実行する.
{gc_bif, Lbl, Live, Bif, Arg, Reg}	{gc_bif,'+',{f,0},2,[{y,0},{x,0}],{x,0}}	BIF (Built in Function)を実行する. 例は{y,0} + {x,0}の結果を{x,0}に代入する. 失敗した場合は{label, 0}に飛ぶ.
{allocate, StackNeed, Live}	{allocate, 1, 3}	stack上の領域を割り当てる. 例の場合は1wordを割り当てている. (Continuation Pointerもstackに保存される為実際には+1される)
{deallocate, N}	{deallocate, 1}	allocateした領域数を指定し, 解放する. (allocate同様にContinuation Pointer分の領域も解放される)
{move, Src, Dst}	{move, {x,1}, {x,0}}	コピーする
return	return	Continuation Pointerに戻る. (C言語のreturnと同じ)
{get_list, Src, Head, Tail}	{get_list, {x,0}, {x,1}, {x,2}}	Srcに保存されたリストのHeadとTailをそれぞれ保存する
{get_tuple_element, Src, Elem, Dst}	{get_tuple_element, {x,0}, 0, {x,1}}	Dst = element(Elem, Src)
send	send	{x,0} ! {x,1}を実行する.
remove_message	remove_message	message queueからメッセージを取り出し, messageのポインタを{x,0}に代入する.
{test, is_XXX, Lbl, Args}	{test, is_nil, {f,6}, [{x,0}]}	Argsがis_XXXであるかを確かめ, falseの場合はLblに飛ぶ.

※ Liveと書かれている要素はGarbage Collection用に, 現在使用されているレジスタの数を意味する. 読む分には特に必要がない為, 各説明では割愛した.

実際にアセンブラを眺めてみた

末尾再帰を確かめる

lists:sum/1と同じ結果を得られる関数を用意した.

loop.erl

-module(loop).
-compile(export_all).

sum(Inputs) ->
    sum_impl(Inputs, 0).

sum_impl([], Sum)      -> Sum;
sum_impl([H | T], Sum) -> sum_impl(T, Sum + H). %% 末尾再帰

sum2([])      -> 0;
sum2([H | T]) -> H + sum2(T). %% 末尾再帰になっていない

loop.S

%% 必要な部分だけを抜粋したもの
{function, sum, 1, 2}.
  {label,2}.
    {move,{integer,0},{x,1}}.
    {call_only,2,{f,4}}. %% 末尾再帰！

{function, sum_impl, 2, 4}.
  {label,4}.
    {test,is_nonempty_list,{f,5},[{x,0}]}.
    {get_list,{x,0},{x,2},{x,3}}.
    {gc_bif,'+',{f,0},4,[{x,1},{x,2}],{x,1}}.
    {move,{x,3},{x,0}}.
    {call_only,2,{f,4}}. %% 末尾再帰！
  {label,5}.
    {test,is_nil,{f,3},[{x,0}]}.
    {move,{x,1},{x,0}}.
    return.

{function, sum2, 1, 7}.
  {label,7}.
    {test,is_nonempty_list,{f,8},[{x,0}]}.
    {allocate,1,1}.
    {get_list,{x,0},{y,0},{x,0}}. %% Headだけstackに待避！
    {call,1,{f,7}}. %% 末尾再帰できてない！
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}.
    {deallocate,1}.
    return.
  {label,8}.
    {test,is_nil,{f,6},[{x,0}]}.
    {move,{integer,0},{x,0}}.
    return.

callもcall_onlyも{x,0}から指定した数の部分が引数として渡される為, 末尾再帰ではないcallの場合はstackに待避されている様子も分かる.

element/hdを積極的に使う

次は, BIFで実装されているelement/2とhd/1, それとパターンマッチで実装した関数を用意した.

bif.erl

-module(bif).
-compile(export_all).

-spec bif({integer(), integer(), integer()}, [integer()]) -> integer().
bif(Tuple, List) ->
    X = element(1, Tuple),
    Y = hd(List),
    X + Y.

-spec match({integer(), integer(), integer()}, [integer()]) -> integer().
match(Tuple, List) ->
    {X, _, _} = Tuple,
    [Y | _]   = List,
    X + Y.

bif.S

%% 必要な部分だけを抜粋したもの
{function, bif, 2, 2}.
  {label,2}.
    {bif,element,{f,0},[{integer,1},{x,0}],{x,0}}.
    {bif,hd,{f,0},[{x,1}],{x,1}}.
    {gc_bif,'+',{f,0},2,[{x,0},{x,1}],{x,0}}.
    return.

{function, match, 2, 4}.
  {label,4}.
    {test,is_tuple,{f,6},[{x,0}]}.
    {test,test_arity,{f,6},[{x,0},3]}.
    {get_tuple_element,{x,0},0,{x,2}}.
    {test,is_nonempty_list,{f,5},[{x,1}]}.
    {get_list,{x,1},{x,0},{x,3}}.
    {gc_bif,'+',{f,0},4,[{x,2},{x,0}],{x,0}}.
    return.
  {label,5}.
    {badmatch,{x,1}}.
  {label,6}.
    {badmatch,{x,0}}.

パターンマッチの場合だとtestが走るため無駄がある事が分かる.
(もちろん可読性の問題もあるので一概に良いとは言えないが)

---

あまり役に立つとは言えない記事になってしまったが, Erlangアセンブラの見方についての記事ということでどうか一つ.
...これで少しは効率的なコードが作れるようになったら良いなぁ