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

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

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

## Erlangのアセンブラを見る方法
```bash
$ 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}}`|関数を呼び出す.呼び出し後は次の命令が呼ばれる.<br />例は引数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)を実行する. <br />例は`{y,0} + {x,0}`の結果を`{x,0}`に代入する. <br />失敗した場合は`{label, 0}`に飛ぶ.|
|`{allocate, StackNeed, Live}`|`{allocate, 1, 3}`|stack上の領域を割り当てる.<br />例の場合は1wordを割り当てている.<br />(Continuation Pointerもstackに保存される為実際には+1される)|
|`{deallocate, N}`|`{deallocate, 1}`|allocateした領域数を指定し, 解放する.<br />(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`と同じ結果を得られる関数を用意した.

```erlang: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). %% 末尾再帰になっていない
```

```erlang: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`, それとパターンマッチで実装した関数を用意した.

```erlang: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.
```

```erlang: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アセンブラの見方についての記事ということでどうか一つ.
...これで少しは効率的なコードが作れるようになったら良いなぁ