WASM となかよくなりたいから Brainfuck をコンパイルしよう

tl;dr

• WASM ともっとなかよくなりたかったからバイナリ表現を読み書きしたかった
• Brainfuck をブラウザ上でコンパイルしてそのまま実行できる状態にした
• バイナリを並べて君だけのコンパイラを作ろう！！！

はじめに

WASM ともっとなかよくなりたい。そう思いますよね。

でも、WASM はバイナリ形式の実行ファイルということはわかっていても、実際何が入っているのかは謎。
何が入っているのかを理解するには WASM をターゲットとするコンパイラを実装するのが圧倒的に近道です。それに、誰でも人生に 1 度や 2 度は書いてみたいと思っているはずですから。

コンパイラを書くには最終的にバイナリを出力しないといけないわけですが、幸運なことに WASM には WAT というテキスト表現が定義されています。このテキスト表現はいわゆるアセンブリ言語と同じで、命令が 1 対 1 に対応しています。この WAT を経由することで比較的簡単に WASM を出力することができます。実際に WAT を経由して WASM を出力するコンパイラのような試みはいろいろなところで見ることができます。

といっても、WAT なんていう軟弱なフォーマットを経由していては WASM をバックエンドに持つコンパイラとは言えないですよね。そしてさらに WASM となかよくなるには WAT ではなく WASM を理解したい。なんならバイトコードを目で見て実行コードが理解できるようになりたい。というわけで、バイナリを直接出力してみようと思います。

しかし、コンパイラって結構難しいというかめんどくさいです。やりたいのは WASM バイトコードの生成なのにそこにたどり着くまでにテキストをパースしないといけないんです。特に高級言語は構造がそれはもうめんどくさい。できるだけ単純で、制御構造があってバイトコードを Emit しがいのある言語…ということで難解言語界の古典とも言える Brainfuck を採用することにしました¹。

今回は、Brainfuck のコンパイラを TypeScript で実装して、WASM のバイナリを生成しながら WASM となかよくなっていこうと思います。

前提条件

• このエントリでは、1 バイトの値について、LSB を 0bit 目、MSB を 7bit 目と呼びます。

Brainfuck について詳しくなる

Brainfuck は 1993 年に Urban Müller によって設計されたプログラミング言語で、可読性がとても低く実用には向いていないがチューリング完全となっています。
難解言語界ではあまりにも有名すぎて今更紹介するまでもないのですが、簡単に紹介しておきます。

Brainfuck には 8 命令しかありません。これらの命令は 1 命令が 1 文字に割り当てられていて、それ以外の文字はすべて無視されます。
使用可能な命令は次の通りです。

命令	意味
>	ポインタをインクリメントする
<	ポインタをデクリメントする
+	ポインタが指す値をインクリメントする
-	ポインタが指す値をデクリメントする
.	ポインタが指す値を書き出す
,	1 バイト入力しポインタが指す位置に値を書き込む
[	ポインタが指す値が 0 なら対応する]にジャンプする
]	ポインタが指す値が 0 でないなら対応する[の直後にジャンプする

これら 8 命令をそれぞれ対応したマシン語に置き換えるだけで簡単に実行できますし、世間にはたくさんインタプリタの実装もあります。

例えば TypeScript で Brainfuck のインタプリタを実装するとこんな感じです。

const program =
  "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";
const loopStack = [];
const tape = [];
let ptr = 0;

for (let i = 0; i < program.length; ++i) {
  switch (program[i]) {
    case ">":
      ptr++;
      break;
    case "<":
      ptr--;
      break;
    case "+":
      tape[ptr] = (tape[ptr] ?? 0) + 1;
      break;
    case "-":
      tape[ptr] = (tape[ptr] ?? 0) - 1;
      break;
    case ".":
      console.log(String.fromCharCode(tape[ptr]));
      break;
    case ",":
      // 本当はstdin読むんですがいったんここではスキップ
      break;
    case "[":
      // これだとジャンプの処理バグってるんですがとりあえずみなかったことにしてください
      if ((tape[ptr] ?? 0) == 0) {
        i = program.indexOf("]", i);
      } else {
        loopStack.push(i);
      }
      break;
    case "]":
      if ((tape[ptr] ?? 0) != 0) {
        i = loopStack[loopStack.length - 1];
      } else {
        loopStack.pop();
      }
      break;
  }
}

この出力は Hello World! となります。これが Brainfuck です。今回は TypeScript でインタプリタを作るのではなく、TypeScript で Brainfuck の制御構造を WASM に出力しブラウザで実行結果を得られるようにしてみましょう。

WASM となかよくなる

WASM(WebAssembly)は CPU 非依存のポータブルな軽量バイナリ表現で、主に JavaScript 実行環境上で動作するコードフォーマットです。
WebAssembly は JavaScript からすると比較的 CPU のネイティブ表現に近い命令語表現で、スタックマシンとして実装されています。
最近では、CPU 非依存でポータブルな軽量バイナリであるということに着目して、コンテナをはじめとしたブラウザの外でも活用していこうという動きが盛んです。
WASI という汎用インターフェース WASI 0.2 が安定版としてリリースされ、今後さらに活用が進むと楽しそうだなと思っているところです。

さて、そんな WASM ですがよくある VM っぽくスタックベースの VM で、JVM や CLR よりも仕様がコンパクトで、バイナリさえ並べれば簡単にしかもサンドボックスで実行できます。
となると WASM をターゲットとしたフロントエンドを作ってみたくなります。WASM をターゲットとしたフロントエンドの実装では、テキスト表現である WAT を生成し、それ以降を wat2wasm などの既存ツールチェインに頼ることもできます。ですがせっかく WASM となかよくなる！と掲げているのでここでは WASM の仕様に沿って自力でバイナリを Emit していくことにしましょう。
ここで、WASM の仕様に沿ったバイナリというのは次のようなものです。

00 61 73 6d          ;; magic "\0asm"
01 00 00 00          ;; version 1
01 ...               ;; Type Section
03 ...               ;; Function Section
0a ...               ;; Code Section

要するに、マジックがあって、バージョンがあって、実際の中身はいくつかのセクションに分かれている。というよくあるファイル構造です。そしてセクションとして、関数の型定義があって、関数宣言があって、さらに実行コードが収められています。
ここまでわかればあとは Emit するだけなので楽勝に思えてきました。

LEB128

WASM のバイナリを作るうえで避けられないのがセクションサイズなどでも必要になる LEB128 エンコーディングという存在です。
これは整数を可変長でエンコードすることで、小さい値を短いバイトで表現できるようにする工夫です。
イメージ的には UTF-8 の整数版みたいな感じで、UTF-8 は 1 バイト目の上位ビット側に何文字続くかを示すビットが入っていたりしますが、LEB128 はもう少しシンプルに先頭ビットが立っていれば次のバイトも続くよ、という感じで実装されています。

LEB128 には Signed と Unsigned の 2 種類がありますが、特に Unsigned の方は実装も単純です。
LEB128 でも特に Unsigned の方である ULEB128 は、任意精度の整数 N について次のようなアルゴリズムで変形した値です。

function encodeLEB128(n: number): Uint8Array {
  const ret = [];
  while (n >= 0x80) {
    ret.push((n & 0x7f) | 0x80);
    n >>= 7;
  }
  ret.push(n);
  return Uint8Array.from(ret);
}

実際のアプリケーションでは符号付き整数が必要になるケースも多いのですが、Brainfuck を素朴に実装した場合はほとんど 0 または 1 という小さな整数しか現れないため LEB128 エンコーディングの出番はほとんどありません。
あるとすればセクションサイズを求める時くらいでしょうか。この場合は Unsigned なため、ULEB128 で十分です。

実際に ULEB128 で整数をエンコードしてみるとこんな感じになります。
たとえば 42 という値はとても短い表現なので 1 バイトで2Aです。128 は継続ビットである 7bit 目まで値を詰めることになってしまうので 2 バイトになり、80 01 という結果になります。もっと大きい 12345678 だとCE C2 F1 05になります。通常の int32 だと 24bit の範囲に収まる値が 4 バイトに伸びてしまっていますが、3 バイト整数が存在しない以上 2 バイトと 1 バイトで表現できる値が増える方が全体のファイルサイズとしてはお得なんでしょうね。
特に実アプリケーションの場合だと、128 未満の小さい定数を扱うことが多いので最終的なファイルサイズにも結構効いてくる小技といった感じがします。

WASM を Emit する

Emit するにしてもスタート地点としてなんらかのコードを解釈できた方が絶対楽しいです。そこで今回は Brainfuck 言語をターゲットにしたコンパイラを実装していきます。

コンパイラといってもいろいろあります。ソースコードを解釈して中間表現を作るところまで（フロントエンド）を担当し、実際のコード生成は既存のツールチェインに任せるパターンもありますが、今回はコード生成（バックエンド）まで含めて全部実装していきましょう。

といっても Brainfuck の規模です。コンパイラといってもそんなに難しいことはないです。なんなら Brainfuck の 1 命令を WASM の命令語に置換するだけでも割と簡単に作ることができます。とても簡単に実装してみるとこんな感じになります。

export function compile(program: string): Uint8Array {
  const code: number[] = [];

  for (const char of program) {
    switch (char) {
      case ">":
        code.push(0x20, 0);
        code.push(0x41, 1);
        code.push(0x6a);
        code.push(0x21, 0);
        break;
      case "<":
        code.push(0x20, 0);
        code.push(0x41, 1);
        code.push(0x6b);
        code.push(0x21, 0);
        break;
      case "+":
        code.push(0x20, 0);
        code.push(0x20, 0);
        code.push(0x2d, 0x00, 0x00);
        code.push(0x41, 1);
        code.push(0x6a);
        code.push(0x3a, 0x00, 0x00);
        break;
      case "-":
        code.push(0x20, 0);
        code.push(0x20, 0);
        code.push(0x2d, 0x00, 0x00);
        code.push(0x41, 1);
        code.push(0x6b);
        code.push(0x3a, 0x00, 0x00);
        break;
      case ".":
        code.push(0x20, 0);
        code.push(0x2d, 0x00, 0x00);
        code.push(0x10, 0);
        break;
      case ",":
        code.push(0x10, 1);
        code.push(0x20, 0);
        code.push(0x3a, 0x00, 0x00);
        break;
      case "[":
        code.push(0x02, 0x40);
        code.push(0x03, 0x40);
        code.push(0x20, 0);
        code.push(0x2d, 0x00, 0x00);
        code.push(0x45);
        code.push(0x0d, 0x01);
        break;
      case "]":
        code.push(0x0c, 0x00);
        code.push(0x0b, 0x0b);
        break;
    }
  }

  code.push(0x0b);

  return Uint8Array.from(code);
}

正直これはコンパイラと呼ぶにはちょっと怪しく、Brainfuck の命令を逐語的に WASM の命令語に置き換えているだけの"変換機"に近いです。あとはこの出力にマジックやバージョン、その他セクションなどをくっつけてあげれば WASM モジュールの完成です。

今回の出力結果が正しく動作する WASM モジュールを完全に構成するには最低限次の要素が必要です²。

• Magic (00 61 73 6d)
• Version (01 00 00 00)
• Type Section (01 ...)
• Imports Section (02 ...)
• Functions Section (03 ...)
• Memory Section (05 ...)
• Exports Section (07 ...)
• Code Section (0A ...)

これらのセクションは ID の昇順で並んでいる必要があります。必要なセクションをすべて定義し、先ほどのコードが生成するバイナリを Code Section に埋めてあげれば実行可能な WASM バイナリの完成です。
これらのセクションは WASM の仕様書に沿ってバイナリを並べていくだけです。Code Section には各関数のバイトコードが入ります。ここを少しだけ眺めてみます。

0A          ;; Section ID: Code
xx          ;; Section size (LEB128)
01          ;; Function count
xx          ;; Function body size
01          ;; Local declaration count
01 7F       ;; 1 local of type i32 (本当はローカル変数をいくつ使うかでちゃんと書く)
...         ;; 実際のバイトコード

この構造を TypeScript っぽく書くとこんな感じになります。

type CodeSection = {
  sectionID: 0x0a;
  sectionSize: number;
  functionCount: number;
  functionBody: {
    functionBodySize: number;
    localDeclarationCount: number;
    localDeclarations: {
      count: number;
      type: i32 | i64 | f32 | f64 | v128;
    }[];
    body: Uint8Array;
  }[];
};

この、個数の後ろにリストが続く構造は WASM の構造では頻出するパターンです³。他の構造もたいていこうなっています。こんな感じにしてバイナリを埋めていくことで WASM のモジュールを生成することができました。

もっと最適化したい

WASM となかよくなりたかったはずなのに、出力されたバイナリを見ていると似たようなバイトコードが並んでてなんだか無駄だなぁと思いますよね。例えば20 00 20 00 2D 00 00 41 01 6A 3A 00 00 パターンが無限に並んでいるのがとても気になります。よくよく考えたらこれは一般的な最適化の話な気がしてきました。
ちょっとずつ最適化していると楽しくなってきちゃって普通に最適化を実装してしまいました。ここからは普通のコンパイラみたいに Brainfuck をパースし、普通のコンパイラみたいに最適化し、WASM バイトコードを出力してみたので軽くだけ紹介します。

今回のコンパイラは最終的にこんなパイプラインで実装されています。

1. Parser: ソースコードを AST に変換
2. Optimizer (AST): 連続する命令の畳み込み、イディオム認識、定数伝播
3. IR Generator: AST をスタックマシン命令列に変換
4. Optimizer (IR): Peephole 最適化
5. Code Generator: IR を WASM バイトコードに変換
6. Emitter: WASM モジュールを合成

あまり詳しく書くと延々最適化手法の話になってしまうのでかいつまんで紹介します。
Brainfuck はその言語仕様上、+++ のような連続した加算命令が続くことが大多数のケースになります。これはバイトコードで表現するとこんな感じになります。

20 00    ;; local.get 0
20 00    ;; local.get 0
2D 00 00 ;; i32.load8_u
41 01    ;; i32.const 1
6A       ;; i32.add
3A 00 00 ;; i32.store8
20 00    ;; local.get 0
20 00    ;; local.get 0
2D 00 00 ;; i32.load8_u
41 01    ;; i32.const 1
6A       ;; i32.add
3A 00 00 ;; i32.store8
20 00    ;; local.get 0
20 00    ;; local.get 0
2D 00 00 ;; i32.load8_u
41 01    ;; i32.const 1
6A       ;; i32.add
3A 00 00 ;; i32.store8

すごくもったいない気がします。全く同じことが 3 回しかも 1 回あたり 6 命令もあります。さすがになんとかならないのでしょうか……
なります。今回の例でいえば、あるメモリ X に対して定数の1を 3 回加算しています。これは TypeScript だとmem[X] += 1 + 1 + 1 みたいなものです。これはmem[X] += 3 と同じ意味です⁴。つまりこれはこのようなバイトコードに最適化できるはずです。

20 00    ;; local.get 0
20 00    ;; local.get 0
2D 00 00 ;; i32.load8_u
41 03    ;; i32.const 3
6A       ;; i32.add
3A 00 00 ;; i32.store8

このような最適化を定数畳み込みといって、コンパイル時に計算を済ませてしまいバイナリには計算後の値しか残っていない。みたいなのは現実世界のコンパイラでもよくある話です。
また、Brainfuck は基本的に 1 バイトの代入で構成されています。しかしよくみてみると隣り合ったバイトに対して連続で代入していることもあります。これらを 2 バイトや 4 バイトの整数として代入すれば命令数が減ってお得！これをさらに突き詰めて SIMD 命令を使うことで最大で 16 バイトを一気にメモリに書き込むことができます。Brainfuck に SIMD はやりすぎな気がしますが、バイトコードからすればソース言語がなんだろうが関係ありません。大切な最適化です。

Brainfuck のコンパイラでは出てくる整数がせいぜい 0 か 1 なので符号付き整数を気にする必要はなかったんですが、定数畳み込み・定数伝播することでもっと大きい整数に遭遇してしまいます。そうなると ULEB128 で誤魔化すことができなくなってくるので SLEB128 を正しく実装する必要があります。SLEB128 を使うか ULEB128 を使うかは命令によってさまざまです。Brainfuck でよく使う整数演算系の命令はだいたい SLEB128 を要求することが多いので、最適化を進めれば進めるほど SLEB128 エンコーディングを正しく計算できるようにする必要に迫られてきます。

ここまでの AST レベルでの最適化に加えて、IR というほとんど WASM のバイトコードみたいな中間表現を使って 2 回目の最適化を実施しています。Brainfuck ではその言語仕様上どうしてもlocal.setの直後にlocal.getが出現するパターンが頻出します。たとえば、>.>.はバイトコードだとこんな感じになります。

20 00    ;; local.get 0
41 01    ;; i32.const 1
6A       ;; i32.add
21 00    ;; local.set 0
20 00    ;; local.get 0
2D 00 00 ;; i32.load8_u
10 00    ;; call 0
20 00    ;; local.get 0
41 01    ;; i32.const 1
6A       ;; i32.add
21 00    ;; local.set 0
20 00    ;; local.get 0
2D 00 00 ;; i32.load8_u
10 00    ;; call 0

local.setした直後にlocal.getでスタックに読み直すのなんだかすごい無駄な感じがする、なんとかならないのか…？
なります。WASM にはlocal.setとlocal.getを 1 命令で実行するlocal.teeという命令があります。隣接する 2 命令を見つけた時に 1 命令に置き換えれば実行効率はよくなり、ファイルサイズも小さくなり一石二鳥です。2 命令しか削減されていないので地味な最適化ですが、Brainfuck の頻出コードだと 10 命令近く削れたりするので塵も積もれば…というタイプの最適化です。

20 00    ;; local.get 0
41 01    ;; i32.const 1
6A       ;; i32.add
22 00    ;; local.tee 0
2D 00 00 ;; i32.load8_u
10 00    ;; call 0
20 00    ;; local.get 0
41 01    ;; i32.const 1
6A       ;; i32.add
22 00    ;; local.tee 0
2D 00 00 ;; i32.load8_u
10 00    ;; call 0

このような最適化を Peephole 最適化といって、局所的なパターンを認識して命令を削減したりしています。今回では 2 命令を 1 命令にするだけでしたが、現実世界のコンパイラは変数のゼロクリアを短い命令に置き換えたり、2 の冪乗の除算をシフト命令に置き換えたりといった局所的なパターンマッチで最適化を実現しています。

なんとなく WASM のバイナリを作ってみたかっただけなのに気がついたら意外とちゃんとしたコンパイラらしい設計に辿り着いてしまっていて、やっちまったなって感じですね。
こんなふうな最適化をたくさん入れた結果、小さく、高速なバイトコードが出力されるようになってうれしいですね！
…と思っていたのですが、実はこのコンパイラは,が出現した時の定数伝播の扱いをすっかり忘れていました。たとえば+++,--のようなコードで、本来は,以降のセルの値は不定になるため、先行の+++による計算を破棄する必要がありますが、それができていません。
この結果コンパイル結果がread, sub 2ではなくread, store1のようになって壊れてしまいます。いわゆる、最適化によるバグというやつ⁵なんですが、せっかくなので"最適化で壊れる例"としてここに残しておきました。
最近のコンパイラは本当に壊れなくなったものの、Brainfuck みたいな小さいコンパイラでも最適化は普通に壊れるので、やっぱり最適化って難しいんだな……と思いつつ、マイコン向けの GCC は最適化がよく壊れていたよなぁ⁶ということを思い出しました。

おわりに

今回はずっとまえから思っていた WASM のバイトコードを手書きするという遊びに取り組みました。いつの間にかちゃんと AST があって、Optimizer があって、IR があって、Optimizer があって、コードジェネレータにつながっているという普通のマルチステージコンパイラとほぼ同じ構造になっていておもしろかったです。特にメモリに定数を書き込むところの SIMD 畳み込みなんてのはなかなか見どころがあったと思います。

WASM のバイナリを直接生成するというのはやりたいと思いつつもあまりやる機会もなく、そもそも普通は既存のツールチェインを使うし任意の言語から WASM にしたい場合でも WAT 経由すればいいのでバイナリ作ろう！というのはそういう趣味の人しかいないのかもしれません。
今回一番めんどくさかったのは、セクションのバイナリ表現がまったくわからんことです。一応、WASM はオープンな仕様なので正式な仕様書が公開されています。ところがこの仕様書、めちゃくちゃ読みづらい。結局そのセクションがバイナリに落ちた時どういう値を取りうるのかがさっぱりわからん。仕様書を読みながら、wat2wasm で変換した WASM をヘキサダンプしたものを眺めながらようやく出来上がったのが途中に掲載したセクション情報でした。
WASM ターゲットのリンカを作ってる人だってたくさんいるはずなのでもっと読みやすいドキュメントにしてほしいですね。

この記事を作るにあたって実装した Brainfuck コンパイラは https://bfwc.utatane.dev/ で公開しています。入力した Brainfuck のコードがブラウザ上で WASM にコンパイルされ、そのまま WebAssembly.instantiate()され実行結果が得られます⁷。WASM のランタイムは JIT を駆使してめちゃくちゃに高速にコードを実行するので Brainfuck という難解言語がネイティブに近い速度で実行されるというのは少し面白いです。
なのですが、Brainfuck の実行時間なんてたかが知れてるのでむしろコンパイルにかかってるオーバヘッドを含めると普通に実行する方が速いまであるかもしれません。

関連資料

• bfwc Playground
• bfwc GitHub
• WebAssembly Specification
• WebAssembly Opcodes

---

1. Brainfuck って単純なのにバイトコードよりはちゃんと抽象化されてて、意外と”高級”なんだなってなりました。 ↩

2. 本当は他にも Table Section, Global Section, Data Section などがありますが今回は不要なので省略しています。 ↩

3. WASM に限らず可変長のデータ構造をバイナリに落とし込むと大体こういう感じ。 ↩

4. あまりにも自明すぎて説明することすら申し訳なくなるレベル。 ↩

5. 現実世界のコンパイラも昔はよく壊れていました。特に -O3 とかすると最適化しすぎて無限ループするとか結構いろいろありました。 ↩

6. GCC をベースにしてバックエンドを自社のマイコンに向けたコンパイラとかを各社が作っていたので Optimizer が壊れてたりしたみたいですね。 ↩

7. このサイトでは WAT を表示していますが wasm2wat を通して生成したいわゆる逆アセンブルリストです。さすがにバイナリだけだと読めない人がいるかもしれないので出力しておきました。 ↩