BEAMローダー

この記事は英語の原文を日本語に翻訳したものです。原文: https://blog.stenmans.org/theBeamBook/#CH-Beam_loader

翻訳元: happi/theBeamBook 7998e22e78417dbe20e5136b9aee862a1ecaa404（コミット 7998e22）

汎用命令から専用命令への変換

BEAMローダーは、外部のbeamフォーマットを単純にメモリへ書き込むだけではありません。コードに対していくつもの変換を行い、外部(汎用)フォーマットから内部(専用)フォーマットへと変換します。

ローダーのコードは erts/emulator/beam 内の beam_load.c にありますが、変換のロジックの大部分は同じディレクトリ内の ops.tab ファイルにあります。

ローダーの最初のステップはbeamファイルをパースすることです。これは基本的に、BeamファイルのパースでErlangで行ったのと同じ処理をCで書いたものです。

続いて、コードチャンク内の命令に対して ops.tab の規則が適用され、汎用命令が1つ以上の専用命令へと変換されます。

変換テーブルはパターンマッチングによって動作します。ファイル内の各行は、1つ以上の汎用命令と引数からなるパターンを定義し、任意で矢印に続けて変換先の1つ以上の命令を記述します。

ops.tab内の変換は、コンパイラが生成する命令のパターンを扱い、それをより少ない専用命令へとピープホール最適化しようとします。また、select系のパターンに対してはジャンプテーブルを生成しようとします。

ops.tab ファイルは実行時にはパースされません。その代わりに、ops.tab からパターンマッチングを行うプログラムが生成され、生成されたCファイル内の配列に格納されます。 Perlスクリプト beam_makeops(erts/emulator/utils 内)が、ターゲット固有のオペコード集合と変換プログラムを beam_opcodes.h と beam_opcodes.c に生成します(これらのファイルは指定したターゲットディレクトリ、たとえば erts/emulator/x86_64-unknown-linux-gnu/opt/smp/ に置かれます)。

同じプログラム(beam_makeops)は、コンパイラのバックエンド用Erlangコードである beam_opcodes.erl も生成します。

ops.tabを理解する

ops.tab内の変換は、ファイルに書かれている順序どおりに実行されます。 Erlangのパターンマッチングと同様に、各規則は上から下へと順に試されます。

ops.tab が命令の引数に使う型については、Beam命令の付録を参照してください。

変換

ops.tab の規則の大半は、異なる命令間の変換です。単純な変換は次のようになります。

move S x==0 | return => move_return S

これは、任意の場所から x(0) への move とそれに続く return を、move_return という1つの命令にまとめます。変換を分解して、それぞれの部分が何をしているか見てみましょう。

move：パターンが最初にマッチしなければならない命令。コンパイラが出力した汎用命令の場合もあれば、ops.tab が変換を助けるために出力した一時的な命令の場合もあります。
S：任意の型の値を束縛する変数。パターン(左辺、または ⇒ の左側)に現れる値のうち、生成規則(⇒ の右側)で使われるものはすべて変数に束縛しなければなりません。
x==0：変換先の場所が値 0 を持つ x レジスタである場合にのみ変換を適用する、というガード。複数の型を連鎖させたり、ここで変数を束縛したりもできます。たとえば D=xy==0 なら、x レジスタと y レジスタのどちらでも値が 0 であれば許容し、その引数を変数 D に束縛します。
|：この命令の終わりと、同じパターンの一部である次の命令の始まりを示します。
return：このパターンでマッチさせる2番目の命令。
⇒：パターンの終わりと、生成されるコードの始まりを示します。
move_return S：生成される命令の名前と、左辺の変数名の組み合わせ。| 記号を使うことで、1つの変換の一部として複数の命令を生成することもできます。

さらに複雑な例

ops.tab ではもっと複雑な変換もできます。たとえばselect_val命令を見てみましょう。これは入力値に応じて、ローダーによってジャンプテーブル、線形探索配列、二分探索配列のいずれかに変換されます。

is_integer Fail=f S | select_val S=s Fail=f Size=u Rest=* | \
  use_jump_tab(Size, Rest) => gen_jump_tab(S, Fail, Size, Rest)

上の変換は、可能であれば select_val のジャンプテーブルを生成します。この変換にはいくつか新しい手法が使われています。

S：is_integer と select_val の両方で使われています。これは両方の値が同じ型かつ同じ値でなければならないことを意味します。さらに S=s というガードにより、型はソースレジスタに限定されます。
Rest=*：命令内の可変長引数を許容し、それらを変数 Rest に束縛します。
use_jump_tab(Size, Rest)：beam_load.c 内のC関数use_jump_tabを呼び出し、select_val の引数をジャンプテーブルに変換できるかどうかを判定します。
\：変換規則が次の行へ続くことを示します。
gen_jump_tab(S, Fail, Size, Rest)：beam_load.c 内のC関数gen_jump_tabを呼び出し、適切な命令の生成を行います。

専用命令

すべての変換が終わったら、専用命令がどのような形になるかを決める必要があります。引き続き move_return を見てみましょう。

%macro: move_return MoveReturn -nonext
move_return x
move_return c
move_return n

これにより、beam_emu.c 内のMoveReturnマクロを使って処理を行う3種類の命令が生成されます。

%macro: move_return：ops.tab に対して move_return のコードを生成するよう指示します。%macro 行がない場合、その命令はbeam_emu.c内で手書きで実装しなければなりません。命令のコードは、%hot または %cold ディレクティブが有効かどうかに応じて beam_hot.h か beam_cold.h のいずれかに置かれます。
MoveReturn：beam_emu.c内で使うCマクロの名前がMoveReturnであることをコード生成器に伝えます。このマクロは手動で実装する必要があります。
-nonext：次の命令へのディスパッチをコード生成器に生成させません。その代わりを MoveReturn マクロ自身が担います。
move_return x：命令の引数がxレジスタの場合の専用命令を生成するようコード生成器に指示します。引数が定数の場合は c、NIL の場合は n です。引数がyレジスタになるケースはコンパイラが決して生成しないため、この場合の命令は生成されません。

beam_hot.h 内に生成されるコードは次のようになります。

OpCase(move_return_c):
    {
    MoveReturn(Arg(0));
    }

OpCase(move_return_n):
    {
    MoveReturn(NIL);
    }

OpCase(move_return_x):
    {
    MoveReturn(xb(Arg(0)));
    }

実装者がすべきことは、beam_emu.c 内で MoveReturn マクロを定義することだけで、これで命令は完成です。

マクロのフラグ

%macro 規則には、生成されるコードを変更するための様々なフラグを指定できます。

以下の例では、次のような専用命令があると仮定します。

%macro move_call MoveCall
move_call x f

%macro に何のフラグも付けない場合、次のようなコードが生成されます。

BeamInstr* next;
PreFetch(2, next);
MoveCall(Arg(0));
NextPF(2, next);

PreFetchとNextPFマクロは、命令が実行される前に次にジャンプすべきアドレスを読み込んでおくことを保証します。この工夫により、キャッシュのアーキテクチャやCPUのスーパースカラー特性に応じた度合いで、すべてのアーキテクチャにおいて性能が向上します。

-nonext：この命令に対するディスパッチを発行しません。return、call、jumpのように、次の命令へ続かないことがわかっている命令に使われます。
%macro move_call MoveCall -nonext
```
MoveCall(xb(Arg(0)));
```
-arg_*：型が*である引数をCマクロの引数として含めます。すべての型の引数がデフォルトでCマクロに含まれるわけではありません。たとえば、失敗ラベルやローカル関数呼び出しに使われる型 f はデフォルトでは含まれません。そのため、オプション -arg_f を指定するとそれをCマクロの引数として含められます。
%macro move_call MoveCall -arg_f
```
MoveCall(xb(Arg(0)), Arg(1));
```
-size：命令のサイズをCマクロの引数として含めます。
%macro move_call MoveCall -size
```
MoveCall(xb(Arg(0)), 2);
```
-pack：可能であれば引数をパックします。これは複数のレジスタ引数を可能な限り同じワードに詰め込みます。レジスタ引数は0から1024までしか取らないため、格納には10ビットとタグ付け用の2ビットがあれば足ります。そのため32ビットシステムでは1ワードに2つのレジスタを、64ビットシステムでは1ワードに4つのレジスタを詰め込めます。パッキングによって1つの命令に必要なメモリを大幅に減らせますが、命令を展開するための小さなコストもかかるため、すべての命令で有効化されているわけではありません。
callの例では、f はパックできずほかの引数も1つしかないためパッキングはできません。そこで代わりにput_list命令を例に見てみましょう。
```
%macro:put_list PutList -pack
put_list x x x
```
```
BeamInstr tmp_packed1;
BeamInstr* next;
PreFetch(1, next);
tmp_packed1 = Arg(0);
PutList(xb(tmp_packed1&BEAM_TIGHT_MASK),
        xb((tmp_packed1>>BEAM_TIGHT_SHIFT)&BEAM_TIGHT_MASK),
        xb((tmp_packed1>>(2*BEAM_TIGHT_SHIFT))));
NextPF(1, next);
```
これは3つの引数を1マシンワードに詰め込み、この命令に必要なメモリを半分に減らします。
-fail_action：失敗時のアクションをCマクロの引数として含めます。ClauseFail()マクロは失敗ラベルが命令の最初の引数にあることを前提としているため、上の例でこれを使うには move_call x f を move_call f x に変える必要があります。
%macro move_call MoveCall -fail_action
```
MoveCall(xb(Arg(0)), ClauseFail());
```
-gen_dest：格納用の関数をCマクロの引数として含めます。
%macro move_call MoveCall -gen_dest
```
MoveCall(xb(Arg(0)), StoreSimpleDest);
```
-goto：通常の次命令へのディスパッチを、beam_emu.c内のCラベルへのジャンプに置き換えます。
%macro move_call MoveCall -goto:do_call
```
MoveCall(xb(Arg(0)));
goto do_call;
```

最適化

ローダーはコードのロード時に数多くのピープホール最適化を行います。もっとも重要なのは命令結合と命令特殊化です。

命令結合とは、2つ以上の小さな命令を1つの大きな命令へと結合することです。これらの命令がほとんどの場合連続して現れることがわかっているなら、コードの大幅な高速化につながります。命令間でディスパッチを行う必要がなくなるうえ、その命令を最適化する際にCコンパイラがより多くの情報を得られるため、高速化が達成されます。命令結合を行うかどうかは、メインのエミュレータループのサイズが増えることの影響と、その命令が実行されたときの利得とを天秤にかけるトレードオフです。

命令特殊化は、命令内の引数をデコードする必要をなくします。つまり、1つの move_sd 命令を持つ代わりに、引数がすでにデコードされた状態の move_xx や move_xy などが生成されます。これにより命令のデコードコストは下がりますが、これもまたエミュレータのコードサイズとのトレードオフです。

select_valの最適化

select_val 命令は、多数の関数節やcase節の制御フローを扱うためにコンパイラが出力します。たとえば次のコードを見てみましょう。

select(1) -> 3;
select(2) -> 3;
select(_) -> error.

これは次のようにコンパイルされます。

{function, select, 1, 2}.
  {label,1}.
    {line,[{location,"select.erl",5}]}.
    {func_info,{atom,select},{atom,select},1}.
  {label,2}.
    {test,is_integer,{f,4},[{x,0}]}.
    {select_val,{x,0},{f,4},{list,[{integer,2},{f,3},{integer,1},{f,3}]}}.
  {label,3}.
    {move,{integer,3},{x,0}}.
    return.
  {label,4}.
    {move,{atom,error},{x,0}}.
    return.

条件内の値として許されるのは整数かアトムだけです。値がそれ以外の型であれば、コンパイラは select_val 命令を出力しません。ローダーはいくつかのヒューリスティックを使い、select_val を行う際にどのアルゴリズムを使うかを決めます。

jump_on_val：ジャンプテーブルを作り、値をインデックスとして使います。近い範囲に集まった整数の集合を対象に選択する場合に非常に効率的です。値がすべて揃っていない場合は、ジャンプテーブルに追加の失敗ラベルのスロットが詰められます。
select_val2：選択対象が2つの値だけで、ジャンプテーブルに収まらない場合に使われます。
select_val_lins：ソート済みのアトムまたは整数を線形探索します。少数のアトムまたは整数から選択する場合に使われます。
select_val_bins：ソート済みのアトムまたは整数を二分探索します。

リテラルの事前ハッシュ化

リテラルがロードされ、ハッシュ化された値を必要とするbifや命令の引数として使われる場合、そのリテラル値を毎回ハッシュ化する代わりに、ハッシュはローダーによって作られ、各命令から使われます。

この手法を使うコードの例としては、マップの命令やプロセス辞書のbifが挙げられます。