WebAssemblyとコンパイラとランタイム

2017-02-16

# WebAssemblyとコンパイラとランタイム
----------------------
[emscripten night !! #3 - connpass](https://emsn.connpass.com/event/48100/)

===
# About Me
---------
![κeenのアイコン](/images/kappa.png)

* κeen
 * [@blackenedgold](https://twitter.com/blackenedgold)
 * Github: [KeenS](https://github.com/KeenS)
 * [Idein Inc.](https://idein.jp/)のエンジニア
 * Lisp, ML, Rust, Shell Scriptあたりを書きます

===
# 何の話
---------

* WebAssemblyをバックエンドに使う言語を作りたい
* [KeenS/webml: An ML like toy language compiler](https://github.com/KeenS/webml)
* 既に発表したものの補足記事的な
  + [コンパイラの人からみたWebAssembly | κeenのHappy Hacκing Blog](https://keens.github.io/slide/konpairanoninkaramitaWebAssembly/)
  + ある程度再度説明します

===
# アジェンダ
------------

* なぜWebAssembly
* コンパイラ
* コード生成
* ランタイム

===

# なぜWebAssembly

===
# なぜWebAssembly
----------------

* なんかバイナリでテンション上がる
* ポータブルでコンパクトで速い
* 機能的にJSを越えるかもしれない…？
* コンパイラがブラウザで動くと言語導入のハードル下がる
  + 気軽に試せる
  + コンパイラだけでなく吐いたコードもブラウザで動かしたい

===
# WASM over LLVM
----------------

* 既存のJS環境と協調する
  + JSとの相互呼び出しとか
* **non-determinismが少ない**
* 細かいアラインメント考える必要がない
* **API安定しそう**

===

# WASM over asm.js
--------------------

* ブラウザ以外への組込みもサポート
  + Node.jsとか
  + **JITエンジンに使えそう**
* プラットフォーム
* 実行までのレイテンシが短かい
* asm.jsより速度を出しやすい設計
* テキストフォーマットで生成コードの文法エラーが怖い
* 将来機能が増えるかも

===
# WebAssemblyの現状
-------------------

* Minimum Viable Product(MVP)
* 機能を削ってとりあえず動くものを作ってる
* 今はC/C++からLLVMを通して吐けるのが目標
  + C/C++には不要でも自分の言語に欲しい機能は……
* 今後SIMDとかスレッドとかDOM APIとか増えていく

===

# コンパイラ

===
# WASM概要
----------

* WASMには以下がある
  + 関数
    - 関数内ローカル変数
  + リニアメモリ
  + グローバル変数
  + テーブル
  + importテーブル
  + exportテーブル

===
# WASM実行モデル
--------------

* i32,i64,f32,f64のみ
* **スタックマシン**
  + 命令のオペランドや関数の引数はスタック経由で渡す
  + 1 passのコード生成が楽そう
* 無限のローカル変数が使える
  + 型がある
* 関数の引数はローカル変数経由で渡される
* コントロールフローはgotoじゃなくてstructured
  + 静的検証がしやすいらしい
  + 安全だけどコンパイラ的には…

===

# コントロールフロー
-------------------

* `loop` + `br` (名前付き)
* `block` + `br` (名前付き)
* `br_if` or `br_table`
* `if` + `else` + `end`
* `return`
* 等

===

# コントロールフロー
-------------------

* gotoがない
  + `br` はブランチじゃなくてブレイク
* gotoからstructuredに[変換出来る](https://github.com/kripken/emscripten/blob/master/docs/paper.pdf)
    + loop, block, br, br_ifを使う
* 高級言語から変換するなら `if` を使う
  + ifが2系統あることになる

===
# サンプル
---------

``` javascript
function geometricMean(start, end) {
  start = start|0; // start has type int
  end = end|0;     // end has type int
  return +exp(+logSum(start, end) / +((end - start)|0));
}
...
```

===
# サンプル
---------

```wasm
(module
  (type (;0;) (func (param i64 i64) (result f64)))
  (type (;1;) (func (param i64 i64) (result f64)))
  (type (;2;) (func (param f64) (result f64)))
  (func (;0;) (type 0) (param i64 i64) (result f64)
    (get_local 0)
    (get_local 1)
    (call 1)
    (get_local 1)
    (get_local 0)
    (i64.sub)
    (f64.convert_s/i64)
    (f64.div)
    (call 2))
  ...)
```

===
# サンプル
---------

```wasm
(module
  (type (;0;) (func (param i64 i64) (result f64)))
  (type (;1;) (func (param i64 i64) (result f64)))
  (type (;2;) (func (param f64) (result f64)))
  (func (;0;) (type 0) (param i64 i64) (result f64)
    (call 2
      (f64.div
       (call 1 (get_local 0) (get_local 1))
       (f64.convert_s/i64
        (i64.sub
         (get_local 1)
         (get_local 0))))))
  ...)
```

===

# WebMLコンパイラ
------------

* パーサ、AST、HIR、MIR、LIR
* LIRがRTLなのでそれをWASMに変換したい
* gotoからstructured control flow…

===

===

# 変数
------

* LIRはレジスタで計算する
* LIRはCFG由来の大量の変数を使う
  + レジスタ割り当ては一旦置いとく
* WASMはスタックで計算する
* どうコード生成すると最適か？

===

```
fun main: () -> i64 = {
 entry@0:
 r0: i64 <- 1
 r1: i32 <- 0
 r2: i64 <- 1
 r3: i64 <- 2
 r4: i64 <- 3
 r5: i64 <- r3 * r4
 r6: i64 <- 4
 r7: i64 <- r5 + r6
 r8: i64 <- r2 + r7
 r9: i64 <- 1
 r10: i64 <- 2
 r11: i64 <- r9 + r10
 r12: i64 <- 3
 r13: i64 <- r11 * r12
 r14: i64 <- 4
 r15: i64 <- r13 + r14
 r16: i32 <- 1
 jump_if_zero r16 then@1
 jump else@2
 then@1:
 r17: i64 <- r8
 jump join@3
 else@2:
 r17: i64 <- r15
 jump join@3
 join@3:
 r18: i64 <- 1
 r19: i64 <- r18 + r15
 r20: i64 <- 1
 r21: i64 <- call d@9(r20, )
 r22: i64 <- 2
 r23: i64 <- call #g37(r22, )
 r24: i64 <- 1
 r25: i64 <- heapalloc(16)
 [r25+0] <- <anonfun>@11
 [r25+8] <- r24
 r26: i64 <- 0
 ret r26
}
```

===

# 変数割り当て
--------------

* SSAの1変数 = WASMの1ローカル変数
* スタックの効率利用を完全に無視
* 計算はLV→スタック→LVに書き戻し
* どうせスタックもLVもレジスタ扱いにしてレジスタ割り当てされるでしょ
* （測ってないけど）多分速度は変わらない

===

# CFG
-----

* コンパイラが一旦gotoを使うコントロールフローグラフを作る
* WASMにはgotoがない
* どうやったら生成出来るか？
* そもそも生成出来るの？

===

# blockと前方ジャンプ
------------

* `block` + `break` で前方ジャンプ
* 閉じ括弧の位置にジャンプ
* `block` の位置は自由

===

<pre>
<code>
(block
 ...
 (br 0)--+
 ... |
 )<------+
</code>
</pre>
===
<pre>
<code>
(block
 ...
 ...
 ...
 (br 0)--+
 ... |
 )<------+
</code>
</pre>
===
<h1 id="loopと前方ジャンプ">loopと前方ジャンプ</h1>
<hr>
<ul>
<li><code>loop</code> + <code>break</code>で後方ジャンプ
<ul>
<li><code>loop</code> からの <code>break</code> はいわゆる <code>continue</code></li>
</ul>
</li>
<li>開き括弧の位置にジャンプ</li>
<li>閉じ括弧の位置は自由</li>
</ul>
===
<pre>
<code>
(loop<----+
 ... |
 (br 0)--+
 ...
 )
</code>
</pre>
===
<pre>
<code>
(loop<----+
 ... |
 (br 0)--+
 ...
 ...
 ...
 )
</code>
</pre>
===
<h1 id="ジャンプのクロス">ジャンプのクロス</h1>
<hr>
<ul>
<li>単一gotoは割り当て出来る</li>
<li>複数のgotoが入り組んだら？</li>
</ul>
===
<h1 id="絶対出来る">絶対出来る</h1>
<hr>
<ul>
<li>チューリング完全なら必ず書ける
<ul>
<li>whileとswitchでステートマシン作ればいい</li>
</ul>
</li>
<li>効率的とは限らない</li>
<li>効率的なコードを吐きたい</li>
</ul>
===
<h1 id="ステートマシンはつらい">ステートマシンはつらい</h1>
<hr>
<ul>
<li>これをナイーブに変換すると…</li>
</ul>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c">#include <stdio.h>
int main() {
 int sum = 0;
 for (int i = 1; i <= 100; i++)
 sum += i;
 printf("1+...+100=%d\n", sum);
 return 0;
}
</code></pre></div>===
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-javascript" data-lang="javascript">function _main() {
 var __stackBase__ = STACKTOP;
 STACKTOP += 12;
 var __label__ = -1;
 while(1)
 switch(__label__) {
 case -1:
 ...
 __label__ = 0;
 break;
 case 0:
 ...
 if ($4) {
 __label__ = 1;
 break;
 } else {
 __label__ = 2;
 break;
 }
 case 1:
 ...
 __label__ = 3;
 break;
 case 3:
 ...
 __label__ = 0;
 break;
 case 2:
 ...
 return 0;
 }
}
</code></pre></div>===
<h1 id="ステートマシンはつらい-1">ステートマシンはつらい</h1>
<hr>
<ul>
<li>どうにかする必要がある
<ul>
<li>emscriptenは<a href="https://github.com/kripken/emscripten/blob/master/docs/paper.pdf">ReLoop</a>で最適化</li>
</ul>
</li>
<li>なんか気に食わなかった</li>
<li>そもそもステートマシンを使わずに生成したい</li>
<li>複数のgotoが入り組んだパターンを自分で考えたの紹介します。</li>
<li>CFGと基本ブロックは知ってるかな？</li>
</ul>
===
<h1 id="前前">前前</h1>
<hr>
<pre tabindex="0"><code>[ ]--+
 | |
[ ]--+-+
 | | |
[ ]<-+ |
 | |
[ ]<---+
</code></pre>===
<h1 id="前前-1">前前</h1>
<hr>
<pre tabindex="0"><code>(block
 (block
 ...
 (br 0)-+
 ... |
 (br 1)-+-+
 )<-------+ |
)<-----------+
</code></pre>===
<h1 id="後後">後後</h1>
<hr>
<pre tabindex="0"><code>[ ]<-+
 | |
[ ]<-+-+
 | | |
[ ]--+ |
 | |
[ ]----+
</code></pre>===
<h1 id="後後-1">後後</h1>
<hr>
<pre tabindex="0"><code>(loop<-----+
 (loop<---+-+
 ... | |
 (br 1)-+ |
 ... |
 (br 0)---+
 )
)
</code></pre>===
<h1 id="後前">後前</h1>
<hr>
<pre tabindex="0"><code>[ ]<-+
 | |
[ ]--+-+
 | | |
[ ]--+ |
 | |
[ ]<---+
</code></pre>===
<h1 id="後前-1">後前</h1>
<hr>
<pre tabindex="0"><code>(block
 (loop<---+
 ... |
 (br 1)-+-+
 ... | |
 (br 0)-+ |
 ) |
)<-----------+
</code></pre>===
<h1 id="前後">前後</h1>
<hr>
<pre tabindex="0"><code>[ ]--+
 | |
[ ]<-+-+
 | | |
[ ]<-+ |
 | |
[ ]----+
</code></pre>===
<h1 id="前後-1">前後</h1>
<hr>
<ul>
<li>素直には出来ない…？</li>
<li>部分的にステートマーシン作る？</li>
</ul>
===
<h1 id="部分的ステートマーシン">部分的ステートマーシン</h1>
<hr>
<pre tabindex="0"><code>[1]--+
 | |
[2]<-+-+
 | | |
[3]<-+ |
 | |
[4]----+
</code></pre>===
<h1 id="部分的ステートマーシン-1">部分的ステートマーシン</h1>
<hr>
<pre tabindex="0"><code> [1] label = 0
 |
+->[br]-+ if label == 0
| | | then goto 3
| | | else goto 2
| | |
| [2] |
| | |
| [3]<-+ label = 1
| |
+--[4]
</code></pre>===
<h1 id="コード生成">コード生成</h1>

===
<h1 id="フォーマット">フォーマット</h1>
<hr>
<ul>
<li>バイナリフォーマットとテキストフォーマットがある</li>
<li>バイナリ: wasm
<ul>
<li>コンパクト</li>
<li>intとかもパッキングする</li>
</ul>
</li>
<li>テキスト: wast
<ul>
<li>人間可読+機械可読=S式</li>
<li>低級にもちょっと高級にも書ける</li>
<li>一旦アセンブラ噛まさないと動かない</li>
</ul>
</li>
</ul>
===
<h1 id="アセンブラ">アセンブラ</h1>
<hr>
<ul>
<li>オンメモリで生成するためにアセンブラ自作
<ul>
<li><a href="https://github.com/KeenS/WebAssembler-rs">KeenS/WebAssembler-rs: An in memory wasm assembler for Rust</a></li>
<li>ブラウザで動かすのに必要</li>
<li>既存のツールは使えない</li>
</ul>
</li>
<li>アセンブラ自体ブラウザで動かすのでRust製</li>
<li>まだ動かしてない</li>
</ul>
===
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-rust" data-lang="rust">let mut mb = ModuleBuilder::new();
let f = mb.new_function(FunctionBuilder::new(funtype!((i32, i32) -> i32))
 .code(|cb, args| {
 cb.constant(2)
 .get_local(args[0])
 .i32_add()
 })
 .build());
mb.export("addTwo", f);
let module = mb.build();
</code></pre></div>===
<h1 id="スタック領域">スタック領域</h1>
<hr>
<ul>
<li>Cでいう<code>struct foo x;</code>みたいにエフェメラルな多ワード領域が欲しい</li>
<li>WebAssemblyのローカルストレージはLVだけ
<ul>
<li>最大1ワードしか保存出来ない</li>
</ul>
</li>
<li>可能性
<ol>
<li>諦めてメモリに確保（場合によっては最適化で消えるかも）</li>
<li>ワード毎に分割してLVに保存（大変だけど速そう）</li>
</ol>
</li>
</ul>
===
<h1 id="ランタイム">ランタイム</h1>

===
<h1 id="言語のランタイム">言語のランタイム</h1>
<hr>
<ul>
<li>主にはGC</li>
<li>その他データのメモリ表現
<ul>
<li>アラインメントも</li>
</ul>
</li>
<li>スタック領域</li>
<li>FFI</li>
<li>コンパイラなのでシンボルテーブルはなし</li>
</ul>
===
<h1 id="メモリ">メモリ</h1>
<hr>
<ul>
<li>mallocとかはない</li>
<li>ページ単位のアロケーションだけ</li>
<li>自前でGCを実装することになる</li>
</ul>
===
<h1 id="gc">GC</h1>
<hr>
<ul>
<li>コールスタックを遡れない
<ul>
<li>コールスタックをGCルートに出来ない</li>
</ul>
</li>
<li>メモリonlyな走査なら可能
<ul>
<li>ポインタを都度メモリ領域(arena)にコピーすれば良い。</li>
<li>arenaもルートになる</li>
<li>コールスタックと連動するのでスタックで管理出来る。</li>
<li>CF <a href="http://www.rubyist.net/~matz/20130731.html">Matzにっき(2013-07-31)</a></li>
<li>ただしコンパイラなので関数全部をsave/restoreで囲んだりはしない。</li>
</ul>
</li>
</ul>
===
<h1 id="アロケータ">アロケータ</h1>
<hr>
<ul>
<li>どうにか書いてブラウザでリンクする必要がある
<ul>
<li>ブラウザにもランタイムライブラリの時代…</li>
<li>WASMはライブラリ間でメモリ共有出来る</li>
</ul>
</li>
<li>とりあえずRustで書く方針
<ul>
<li>WASMのページアロケートとかどうすればいいんだろう</li>
<li>まだ色々未定</li>
</ul>
</li>
</ul>
===
<h1 id="メモリ表現">メモリ表現</h1>
<hr>
<ul>
<li>出来れば楽して64bit統一したかった
<ul>
<li>i32やf32を抹殺したかった</li>
</ul>
</li>
<li>WASM32しかないのでポインタが32bit…</li>
<li>仕方ないので64bitアラインメントでパディングする</li>
<li>空いた32bitの使い道は未定
<ul>
<li>静的型付だし型タグが要らない</li>
<li>代数的データ型のタグ？</li>
</ul>
</li>
</ul>
===
<h1 id="高階関数">高階関数</h1>
<hr>
<ul>
<li>WASMに関数ポインタがない</li>
<li>テーブルに関数を登録してインデックス参照
<ul>
<li>C++のvtableのための機能</li>
<li>型も動的チェック</li>
</ul>
</li>
<li>ちょっと遅そう</li>
<li>気合でインライン化を頑張ろう</li>
</ul>
===
<h1 id="ffi">FFI</h1>
<hr>
<ul>
<li>JSの関数を呼びたい</li>
<li>細かいところどうなってるんだろう
<ul>
<li>例外は？JSオブジェクトは？GCは？</li>
</ul>
</li>
<li>型付…</li>
<li>ノープラン</li>
</ul>
===
<h1 id="雑にまとめ">雑にまとめ</h1>
<hr>
<ul>
<li>WASMはちょっと高級なので最適化コンパイラは困るよ
<ul>
<li>雑なコンパイラにはむしろ嬉しい</li>
</ul>
</li>
<li>コード生成は努力で解決</li>
<li>GCは割とつらいよ
<ul>
<li>将来楽になるかも</li>
</ul>
</li>
<li>JS連携や将来のスレッドとかはみんなで考えよう</li>
</ul>