WebAssembly 向けのコンパイラを作ってみる

はじめに

結構前から wasm さわってみたいと思いつつ手を出せずにいたんですが 去年 C コンパイラを学んだりしてハードルが下がった感じがあって簡単なコンパイラ実装をやりはじめました。

まずは難しい機能は入れず C 言語から大分機能を落としたサブセットのコンパイラを作ることにしました。

リポジトリはこれです。

https://github.com/tkaaad97/wasm-experiment1

例として下のコードをコンパイルすると

void printf_i(string s, int a);

int add(int a, int b) {
    return a + b;
}

int main(int n, int b) {
    int a = 0;
    for (int i = 0; i < n; ++i) {
        a = add(a, b);
    }
    printf_i("a=%d\n", a);
    return a;
}

出力の wasm (テキスト形式) は下のようになります。

(module
  (import (;0;) "" "printf_i" (func (param i64 i32)))
  (type (;0;) (func (param i32 i32) (result i32)))
  (type (;1;) (func (param i32 i32) (result i32)))
  (func (;1;) (type 0) (param i32 i32) (result i32)
    local.get 0
    local.get 1
    i32.add
    return
    unreachable
  )
  (func (;2;) (type 1) (param i32 i32) (result i32)
    (local i32 i32)
    i32.const 0
    local.tee 2
    drop
    block
      i32.const 0
      local.tee 3
      drop
      loop
        local.get 3
        local.get 0
        i32.lt_s
        i32.eqz
        br_if 1
        local.get 2
        local.get 1
        call 1
        local.tee 2
        drop
        local.get 3
        i32.const 1
        i32.add
        local.tee 3
        drop
        br 0
      end
    end
    i64.const 12884901888
    local.get 2
    call 0
    local.get 2
    return
    unreachable
  )
  (export "memory" (memory 0))
  (export "add" (func 1))
  (export "main" (func 2))
  (memory (;0;) 1 10)
  (data (;0;) (i32.const 0) "a=%d\n\00")
)

WebAssembly 関連情報

wasm の仕様はここのようです。大体ここに必要なことは書かれているはずです。

webassembly.github.io

wasm の入門的な記事です。最初はこのあたりを読んだりしていました。

developer.mozilla.org

developer.mozilla.org

実行するときに wasmtime の C API を使いました。その他にもコマンドラインで色々試したりできます。

github.com

コンパイラ実装について

スタックマシン

前に C コンパイラ作成したときは x86-64 でやっていてこれはレジスタマシンでした。

wasm はスタックマシンなので色々と実装が変わってきます。

x86-64 向けの実装でもメモリ上のスタックは使っていたので、 スタックマシンではレジスタに動かす必要がなくなって実装が楽になるのかなと思ってましたが、 実装を進めるとちょっと勘違いしていたことがわかりました。

wasm のスタックはメモリ上のスタックとは違って操作がかなり制限されています。

例えば関数の引数とローカル変数には local.get という命令でアクセスできるんですが この引数には定数のインデックスしか渡せず何らかの計算をしたインデックスを使ったりできません。 配列をローカル変数としてスタック上配置したとしてもループで回してインデックスアクセスしたりできないわけです。

なので wasm 側のスタックとは別にメモリ上にアプリケーションがスタックとして使う領域を別に用意して使うことになるんじゃないかと思います。 C 言語と違ってポインタが無い言語ではまた実装違うかなという気もします。

今回実装した言語は機能を大幅にカットしていてポインタも配列も無いので 全部 wasm 側のスタックで済ませるということにしています。

四則演算

四則演算はそのままスタックに積んでいって計算すればいいので簡単です。

四則演算の例

1 + 2 * 3 - 4 / 5 + 6

wasm

    i32.const 1
    i32.const 2
    i32.const 3
    i32.mul
    i32.add
    i32.const 4
    i32.const 5
    i32.div_s
    i32.sub
    i32.const 6
    i32.add

関数

wasm にも関数の機能があって、これを C 言語の関数実装にも使えますが 先に触れたように引数とローカル変数におけるものが限られているのでちゃんと実装するには自前でメモリ上にスタックを作るなどする必要がありそうです。

関数には型が付きます。スタックから入力として使うデータの型とスタックに結果として残すデータの型です。 スタックに渡すデータの型や個数は実行前にチェックされて少し静的言語っぽい感じもしました。

関数の例

int add(int a, int b) {
    return a + b;
}

wasm の例

  (func (param i32 i32) (result i32)
    local.get 0
    local.get 1
    i32.add
  )

テキストフォーマットでは S 式のようにも書くことができます。

  (func (param i32 i32) (result i32)
    (i32.add (local.get 0) (local.get 1))
  )

if

wasm はジャンプ命令がなくてブロックがいくつかあります。

アセンブリだと普通ネストした構造はないですが wasm はこのあたり変わってて ブロックはプログラミング言語のようにネストした構造を作れます。

C 言語の if 文を実装するには wasm の if ブロックがそのまま使えます。

if 文の例

int min(int a, int b) {
    int c = 0;
    if (a < b) {
        c = a;
    } else {
        c = b;
    }
    return c;
}

wasm

  (func (param i32 i32) (result i32)
    (local i32)
    i32.const 0
    local.tee 2
    drop
    local.get 0
    local.get 1
    i32.lt_s
    if
      local.get 0
      local.tee 2
      drop
    else
      local.get 1
      local.tee 2
      drop
    end
    local.get 2
  )

この例だとパラメーターも結果も無いので省略されていますがブロックにも関数と同じように型が付きます。

関数内で if ブロックを使って return しようとすると警告出てしまうことがありました。

警告がでるコード

  (func (param i32 i32) (result i32)
    local.get 0
    local.get 1
    i32.lt_s
    if
      local.get 0
      return
    else
      local.get 1
      return
    end
  )

wat2wasm の警告

error: type mismatch in implicit return, expected [i32] but got []

こういう場合は unreachable を入れるといいようです。

  (func (param i32 i32) (result i32)
    local.get 0
    local.get 1
    i32.lt_s
    if
      local.get 0
      return
    else
      local.get 1
      return
    end
    unreachable
  )

for

for 文 は loop ブロックと br, br_if を使って作れます。

br と br_if は break と似てますが loop ブロックに使う場合は continue のような挙動になるようです。

loop ブロックの参考

qiita.com

for 文の例

    int a = 0;
    for (int i = 0; i < 10; ++i) {
        a = a + i;
    }

生成された wasm

    i32.const 0
    local.tee 0
    drop
    block
      i32.const 0
      local.tee 1
      drop
      loop
        local.get 1
        i32.const 10
        i32.lt_s
        i32.eqz
        br_if 1
        local.get 0
        local.get 1
        i32.add
        local.tee 0
        drop
        local.get 1
        i32.const 1
        i32.add
        local.tee 1
        drop
        br 0
      end
    end

break 実装するときに wasm 側でどのブロックを抜けるのか知る必要があります。

例えば for の中に if があってそこで break 使う場合は二つ上のブロックを抜けるように br 2 とします。

この部分は wasm 生成する関数で今 break 使ったらどのブロック抜けるかというのを引数で渡す感じで実装しました。

文字列リテラル

data segment という機能でメモリ上に文字列データを配置することができます。

コードに持つ文字列リテラルの情報としてはメモリ上のオフセットとサイズを持っておけばいいので

i64.const にオフセットとサイズを 32bit づつにして定数として埋め込んでいます。

グローバル変数

グローバル変数も wasm 側で機能が用意されていてある程度はこれを使えるんですが C 言語の機能とはちょっと違っています。

配列や構造体、ポインタとして扱うデータなどはメモリ側に置くことになると思います。

wasm グローバル変数の初期化式には定数式しか使えないので

C 言語の機能を実装していくにはグローバル変数初期化用の関数を作ったりする必要がありそうです。

ホスト側の関数を呼ぶには

wasm の範囲では標準入出力やファイルを扱ったりできません。

かわりにホスト側の処理を呼び出すことができるような仕組みがあります。

wasmtime では C API が実装されていてホスト側の関数ポインタをモジュールの import として呼び出せるようになっています。

JavaScript 向けの処理系では wasm から JavaScript の関数を呼び出すような仕組みを持っています。

また WebAssembly System Interface (WASI) というのが提案されていて入出力やファイルシステムなどを扱うための インターフェースが定義されて色々なランタイムが実装されているようです。

WASI を使って実装された wasi-libc というのもあって C 言語で実装されたものを wasm にするときには必要になりそうです。

github.com

printf を呼ぶ

ホスト側の関数を呼べるので printf なども使えますが可変長引数の仕組みはないので 引数を変えてたくさん関数を import したりする必要があります。

それか引数もメモリ上に配置してホスト側で復元して呼び出すような感じにもできるかもしれません。

今回使ってないですが wasi-libc に printf もあるらしいです。

感想

関数があったりネストした構文があったりしてアセンブラよりかなりプログラミング言語に近く感じました。

wasm にコンパイルできる言語は色々あるので別に自分でコンパイラ書く必要はそんなにない気もしますが色々勉強になりました。

私が使いたいところとしては Web でなにか動かしたいというよりは、 例えばゲームやアプリで一部スクリプトやプラグインのようなものを動かすのに使えるかもと考えてました。

今回は大分実装を省略しましたが配列、構造体、メモリ上のスタック、コルーチン (難しそう) などそのうち実装してみたいと思いました。