自前のVMを作って適当な文法の言語を動かしてみる

はじめに

　この記事は東京高専プロコンゼミ① Advent Calender 2019 4日目の記事です。
また、この記事はGigaCode 2019での発表とほぼ同じ内容となっています。 (発表資料)

概要

　最近はコンパイラを作るのが流行りらしいです。そこで今回は流行に乗っかり、簡単な文法の自作言語もどきを動かしてみようと思います。
私のような知識ゼロの初心者がアセンブリに触れるのはかなり厳しいので、VM経由で動かす形式で実装をしていきます。

　制作期間は1週間、バイトコード生成器の実装はGoを、VM本体の実装はC++を用いる事にします。
私は今までGoを触った事が(Hello Worldレベルの事を含めて)一度もないのですが、この機会に触ってお気持ちを掴んでいこうと思います。また、VM側は速度が求められるのでC++で実装していきます。

今回やる事

　今回の実装内容は

で構成されています。それぞれ順番に実装方法などを書いていきたいと思います。

実装

事前にやっておく事

　まずは言語仕様を決めます、とりあえず動けばなんでもいい、言語としての優れた機能を求めない(他言語の劣化でも問題ない)事にして、型は32bit int固定、宣言時やプロトライプ引数の記述時に型を記述しないC言語のような構文を採用する事にしました。関数は実装して、とりあえず構造体やポインタ等は(今は)実装しない事にします。

　また、字句解析や構文解析で必要になるので、EBNF記法のような適当な記法を用いて言語構文を記述しておきます。
バイトコード生成についても同様に、LuaやJavaで生成されるバイトコードを参考にしながらオペコードを決めていきます。今回はレジスタマシンベースで動かすので、オペランドがスタックマシンベースと比べて少し多くなります。

字句解析

　構文解析をする前に、まずはプログラムからそれぞれの単語をトークンとして分割していきます。main(x, val)が["main", "(", "x", ",", "val", ")"]に分割されるイメージです。
正直このパートはやるだけ(先頭からマッチングするだけ、面倒な処理も愚直に書くか正規表現に投げればいい)なので、省略します。

構文解析

　字句解析で得られたトークンの列から、事前に決めておいたEBNF記法に沿って抽象構文木を生成していきます。
今回の言語仕様で使ったEBNF記法には左再帰が存在しなかったため、オーソドックスな再帰下降構文解析で普通に実装する事ができます。競技プログラミングなどで構文解析をやった事がある人にとっては(かなり面倒ですが)実装するだけ、そうでない人でも構文解析関連の資料は大量にあるのであまり困らないと思います。

バイトコード生成

　生成された構文木を潜っていきながら、事前に決めておいたバイトコード規則にそってバイトコードを生成していきます。
バイトコードの決め方は色々考える事ができますが、今回はオペコードに6bit、オペランドのレジスタ参照部分が9bit、他は余った部分を使う形で1命令32bitとしました。また、もし即値代入等で1命令に33bit以上を使いたい場合は次の4バイトに前の命令の続きを記述できるような形にしました。

VM作成

　ここは本当にやるだけです。書き出されたバイナリファイルを1バイトずつ読んで行きながら、例えばjumpがあったら読む位置を変更したり、代入命令に合わせて(VM内の配列に)値を代入していったりするのを、オペコードの数だけswitch文で場合分けしながら実装していきます。

VM内での動的コンパイル

　VMまで作成できれば十分な速度でプログラムが動作してくれるのですが、ここからさらにプログラムを高速化していきます。
JITコンパイルを採用する事でプログラムの大幅な高速化を図ります。動的にバイナリを生成する手段としては、x86/x64向けのJITアセンブラのライブラリを導入したり、もしくはasm直書き生成などが考えられますが、時間もない状況で新しい事に手を出して消耗するのは得策ではないため、他の方法を探します。

　例えばRubyではVM内でメソッドの呼び出し回数を監視し、一定回数以上呼ばれたメソッドのバイトコードをC言語のコードに変換、別スレッドでgccを用いてコンパイルを行い、生成された.soファイルをVM側から動的ロードして仕様する事で高速化をしています。この方法を用いる事で(比較的)簡単に動的コンパイルによる高速化が行えます。
　作成したVMに手を加え、関数の呼び出し回数を保存するようにし、関数が一定回数以上呼ばれた場合にバイトコードをC++コードに変換、gccでコンパイルしてdlopenとdlsymで動的ロードを行います。 特に今回の実装はレジスタマシンベースのため、オペランド中に出てくる定数の数がかなり多くなります。そのためバイトコードだった部分の定数埋め込みによる恩恵が大きくなり、細かい最適化をかけなくてもかなりの高速化が行えました。

まとめ

　実装量は多かったけど、異常に辛いという訳ではなく、締切に追われながら適度に限界ペースで開発をしている感じがあって楽しかったです。私自身はコードを書くという事自体が好きな人間なので、こうやって短期間に実装量が多い開発をするのは楽しく、定期的に行っていきたいと感じました。

　今回実装した物は言語として見ると本当に機能不足もいい所で、個人レベルでちゃんとした言語の開発をしている方は本当にすごいと感じました。(特に今回はlexer/parser関連のライブラリやLLVMを全く使用していないため実装で詰まらなかったという節もあったので、それらのライブラリの機能をフルに活用して開発するのは本当に大変そうだと思いました)

　最後にリポジトリを置いておきます。まぁもう手を加える事はないと思いますが・・・ github.com