WASM3の末尾呼び出しVMがかしこい

(EDIT: 末尾呼び出しVMって何だ.. direct-threading VMを末尾呼び出しで実現しているのが面白いと思ったもんで...)

WebAssemblyの インタプリタ であるWASM3( https://github.com/wasm3/wasm3 )が良いデザインをしていると思うメモ。

(WASM3はM3と呼ばれていたインタプリタプロジェクトが移動してきたもの。というわけでWASMのバージョン番号ではない。)

かしこい所

基本的にはリポジトリの README.md に述べられている。

コンパイラの末尾呼び出し最適化を期待してシンプルに記述

WASM3のVM命令は以下のようなC言語関数で実装される:

d_m3OpDef  (GetGlobal) // ★ これはマクロで次節のようなプロトタイプに展開される
{
    // ★ 次の2行が実際の処理
    i64 * global = immediate (i64 *);
    slot (i64) = * global;                  //  printf ("get global: %p %" PRIi64 "\n", global, *global);

    return nextOp (); // ★ 次の命令を実行
}

このような書き方だと、VM命令列の分だけ関数の呼び出しを再帰させてしまいそうだが、gccのようなコンパイラは末尾呼び出しは call ではなく jump に置き換えてしまうのでスタックを消費しない。

実際のreturn値は NULL (trapなし) か、trapを表現するポインタとなっている。

更にかしこい事に、この nextOp もマクロになっていて、defineを変化させることで簡単に各命令にプロファイリングを挿入できるようになっている。

• https://github.com/wasm3/wasm3/blob/968b7fabecec6e55ff31bbd9426277a664a5e61e/source/m3_exec.h#L41

#define nextOpDirect()              ((IM3Operation)(* _pc))(_pc + 1, d_m3OpArgs)

# if d_m3EnableOpProfiling
d_m3RetSig  profileOp  (d_m3OpSig, cstr_t i_operationName);
#   define nextOp()                 profileOp (d_m3OpAllArgs, __FUNCTION__)
# elif d_m3TraceExec
#   define nextOp()                 debugOp (d_m3OpAllArgs, __FUNCTION__)
# else
#   define nextOp()                 nextOpDirect()
# endif

このような構造を取ることで、表面上はC言語のナチュラルな記述でありながら Direct-threading 実装と実質的に同じことができる。

もちろん、C言語は別に末尾呼び出しの最適化を言語規格としては要求していないので移植性という意味では難があるが、今時clang以外のコンパイラも無いし良いんじゃないだろうか。 ...デバッグで困るか。

他にdirect-threadingを実現する方法としては、GCCのlabel-as-value拡張を使った方法とか、大昔のqemuの"dyngen"のようにC言語で書いた関数のバイト列を直接切り貼りして実行可能領域に貼っていくといった方法がある。

TODO: デバッグビルドでは安全にlabel-as-valueにfallbackするように末尾呼び出しVMを記述する方法は存在する？

関数プロトタイプを工夫してVMレジスタと物理レジスタを一致させる

↑ の GetGlobal のようなVM命令は、全て IM3Operation 型の関数となっている。

• https://github.com/wasm3/wasm3/blob/f189e42c3e0eef77b6610b671ae642c566b8fe69/test/tailcall/ops.c#L29

#    define vectorcall

#    define d_m3OpSig                 pc_t _pc, u64 * _sp, u8 * _mem, m3reg_t _r0, f64 _fp0
#    define d_m3OpArgs                _sp, _mem, _r0, _fp0
#    define d_m3OpAllArgs             _pc, _sp, _mem, _r0, _fp0
#    define d_m3OpDefaultArgs         666, 666.0

typedef m3ret_t (vectorcall * IM3Operation) (d_m3OpSig);

... 要するに

__vectorcall void * Operation_Whatever (pc_t pc, u64 * sp, u8 * mem, reg_t r0, f64 fp0);

となる。こうすることで、通常のCPUの呼び出し規約はC言語APIの引数のうち、整数引数と実数引数はレジスタに載せるため、VMレジスタとハードウェアレジスタを一致させることができる。

• https://github.com/wasm3/wasm3/blob/b1c06f35f962a3221b188ec8fb60b82d1775dfd3/source/README.md#the-end-result

M3 Register	x86 Register
program counter (pc)	rdi
stack pointer (sp)	rsi
linear memory (mem)	rdx
integer register (r0)	rcx
floating-point register (fp0)	xmm0

ハードウェアFPUを持たないプロセッサでは fp0 が常に無駄になるが、そもそもWASM自体がFPUの存在を前提としているので大きな問題では無いだろう。

( __vectorcall はWin32の呼び出し規約でSSE2レジスタの使用を強制するために必要になる。)

Issue 33

↑ のREADME.mdは 今日のコミット b1c06f35f962a3221b188ec8fb60b82d1775dfd3 で原作者が疑問に思った点が削られているが、これの問答も興味深い。回答している @sunfishcode はMozilla所属、WASIや funclet 等。

回答は Issue 33 に纏まっている。

WASMモジュールが16MiBものメモリを取るのは何故か

→ これは単にtoolchainのデフォルト

ただWASMはページサイズ64KiBを仮定していて、これをどうにかしたいというIssue( https://github.com/WebAssembly/spec/issues/899 )もある。

この64KiB選択の理由はWASMのDesign rationaleに述べられている:

• https://github.com/WebAssembly/design/blob/541b81160e3aac49ff21d21b3a4c04bb62cdfa4c/Rationale.md#linear-memory-resizing

64KiB represents the least common multiple of many platforms and CPUs. In the future, WebAssembly may offer the ability to use larger page sizes on some platforms for increased TLB efficiency.

このRationaleでは上記のIssueとは逆方向 -- いわゆるlarge pages -- には含みを持たせている。

メモリを一発取って終わりにはできないの？

→ できない。WASMアプリケーションにメモリを渡す形式でインターフェースして、メモリ管理を(embedder側で)やるみたいな方法は有るけど。

トラップ: 符号付数のオーバーフローはtrapしろ？

それだと通常の人間が期待する整数のオーバーラップ挙動を表現できないんじゃないの？

→ わかりづらいけど: add 、 sub と mul はここにあるような符号セマンティクスを持たない。このためオーバーフロー時はwrapする & trapはしない。

この文言 "Signed and unsigned operators trap whenever the result cannot be represented in the result type." は 古いドキュメント には言及があるが、 公式のドキュメント では、はっきりとwrap around挙動で定義されている。

iaddN(i1,i2) -- Return the result of adding i1 and i2 modulo 2N
iaddN(i1,i2)=(i1+i2)mod2N

ちなみにC言語では符号付整数のオーバーフローは未定義挙動で、 fwrapvのような最適化抑制オプションの是非がよく話題になる 。

かんそう

WASMのインタプリタはどちらかというと安全性に振った実装が多くそうでないものは大体JITCなので、普通のインタプリタ言語VMのように、レジスタベースVMを実装したらどういうパフォーマンスになるかは誰もが興味を持っていたと思う。

それをやってみたWASM3はネイティブコードの4〜15倍しか遅くないと主張している。これはなかなか良い数字で、JIT禁止なプラットフォームがあることを考えるともうちょっと突き詰めても面白いかもしれない。

元々の実装であるM3を開発した動機として:

• https://github.com/wasm3/wasm3/blob/b1c06f35f962a3221b188ec8fb60b82d1775dfd3/source/README.md#m3-massey-meta-machine

Early on I decided I needed an efficient interpreter to achieve the instant-feedback, live-coding environment I desire. Deep traditional compilation is too slow and totally unnecessary during development. And, most importantly, compilation latency destroys creative flow.

レイテンシの少さを挙げている。確かに、適当に(低コストで)出力したバイトコードをreliableかつ高速に実行する環境というのは意義があるのかもしれない。

でも自分で書くならlabel-as-valueか巨大switchかなぁ。。物理レジスタの活用を良く表現する方法が思いつかないけど。