JIT電卓言語を作る

この記事はN高等学校 Advent Calendar 2018の10日目の記事です。
この記事はN高等学校をそろそろ卒業してしまう人が言語処理系を書きたいと言っている後輩に向けて書いたものです。内容は言語処理系を書きたい万人向けのものですが、想定するレベル感はそれぐらいだと思ってもらえれば幸いです。
作ると言っても実際には実装日記みたいな感じですが、ソースコードと合わせて見ればどのようなことを考えて言語処理系を実装しているかを感じ取れるんじゃないかと思っています。

この記事について

この記事では簡単な言語処理系を作りたいと思います。どのような言語かというと、

• 1 + 1のような簡単な四則演算ができる
• 関数の定義、呼び出しができる
• if式がある
• 値は64bit整数のみ

言ってしまえば簡易的な電卓言語みたいなものです。これを作るだけでも言語処理系作りの練習になりますが、これだけでは面白みに欠けるので、簡易的なJITコンパイル機能も実装することにします。

実装に際して

実装言語にはCを使いました。ビルドはmakeで行い、shell scriptでテストを行っています。
JITコンパイルを行う関係上インラインアセンブラなどを使用する必要性があるので、簡便さのためにCの処理系はGCC前提で、かつ環境はx86_64固定でやっています。JITに関しては特殊なOSのAPIを呼ぶ必要がありますが、差異は少ないのでマクロでWindowsとLinux両対応にしてあります。
最終成果物はGithubに置いてあります。main.cで実装は完結しており、この記事を書いた時点では最終的に423行になりました。 https://github.com/snowlt23/jitcalc

今回の記事では実装に際して考えたことや順序、基本方針を書くことにします。コードに関しては細かいコードの解説などは省いて、重要なAPIの説明などに留めます。実装は上記のGithubのプロジェクトを適宜参照してください。
JITコンパイラを作る関係上、アセンブラを書く必要性が出てきますが、アセンブラに関しての説明は省いて、ポイントだけ解説します。

言語処理系としてのとりあえずの目的はフィボナッチ数を計算する関数を書けるようにすることです。言語仕様もそれに必要な最小限のものになっています。
最終的にそれをJITコンパイルできるようにしてどの程度の速度差が出るかベンチマークしてみたいと思います。

言語仕様紹介

実装する言語がどのような文法でどのような意味を持っているかの紹介です。

値

555

四則演算 (実装の都合上、乗算・除算は後回しにしています)

1 + 2
4 - 5

比較

2 < 3

括弧による優先順位

(1 < 2) + 1
1 < (2  + 1)

関数定義

f = 555

関数呼び出し (1引数固定)

f = 555
f . 0

引数の参照 (.演算子)

f = .
f . 555

if式

if 1; 4; 5;
if 0; 4; 5;

また、 ; や \n(改行)、 EOF 、 ) などは終端記号として扱われます。

実装方針

実装の基本方針としては、目的(今回はfib)に最小限必要なものを楽に実装していくという方針でいきます。
最終的には以下を実行できるようにします。

fib = if .<2; .; (fib . .-1;) + (fib . .-2;)
fib . 38

実装

自分が実装していった順に並べています。実装順や方法は割と自由ですが、このような順番にステップアップしていくのが順序としてはいいかもしれません。
JITについては最初は考えない方が楽です。JITはあくまで最適化なので後で好きなタイミングで導入できます。最初は動くものを楽に作ることを考えます。

単純な値

123

のような1つの値を読み込み、表示するプログラムについて考えます。
入力は基本的に標準入力から読み込むことにし、出力についても標準出力で表示することにします。

#include <stdio.h>
#include <stdlib.h>
int main() {
  int x;
  scanf("%d", &x);
  printf("%d", x);
  return 0;
}

基本はこれだけです。 低レイヤを知りたい人のための
Cコンパイラ作成入門でも触れられていますが、簡単なものからステップアップして作っていくことは大事です。
極端な話、このプログラム自体の全体の流れは変わることはありません。変わることとしてはscanfで入力をパースしているところが自前の字句解析(lex)・構文解析(parse)に変わることと、その解析結果を評価(eval)して計算するぐらいで、全体の流れは変わりません。

四則演算

自分はここあたりから字句解析器と構文解析器を作りました。
必要なものは

• 123 のような数値リテラルを標準入力から読み込む (字句解析)
• + - のような演算子を標準入力から読み込む (字句解析)
• 上記の字句解析器を利用し、 1 + 2 や 4 - 5 のような式をトークンに分割し、トークンを読み込んで式を組み立てる (構文解析)
• 組み立てた式を評価(eval)して結果を計算する

です。これらを１つ１つ実装します。
構文解析については再帰下降構文解析という手法が手で実装する際には楽です。再帰下降構文解析について詳しくはググってください。

ここで重要なのは、これらが実装できた際に、 1 + 1 が 2 になっているかなどを確認するテストを書くことです。テストを細かに書くことにより、それらを実行できるという保証と、テストの自動化、バグが出た際にどこまでが正常かどうかという境界を引くことができるというメリットがあります。テストは絶対に書くべきです。

関数定義

f = 555

555という値を返すfという関数を定義しています。
関数名 = 式 という構文は最初に紹介しましたが、実際にはこの関数定義を実装する際に構文は適当に考えました。
実装は、グローバルな関数一覧を持っておき、関数定義が現れた際にそれに関数名で検索できるように追加する形です。

関数呼び出し

f . 123

123という値を引数にf関数を呼び出しています。簡便さのために引数は１つ固定で取れるような仕様にしています。
実装は、上記の関数一覧から関数名で関数の式を引き出し、それを実行するだけです。関数定義が実装できればここはある程度楽なはずです。

引数

f = .

. により与えられた引数を参照できます。 f = . + . を f . 5 のように呼び出せば結果は 10 です。
やることとしては関数呼び出しの際の引数をどこかに保存しておき、どこからでも参照できるようにするのが楽です。
注意点としては、関数から関数を呼び出すこともできるので、適当にやると保存しておいた引数を新たな引数で上書きしてしまうので、別の関数を呼び出す際に、保存している引数を一時的に退避させ関数呼び出し後に戻すということが必要になります。

if式

if式は一つの条件式を取り、その結果に応じて真であったときの式、もしくは偽であったときの式を実行します。
インタプリタとしての実行であれば四則演算のノリで実装できるはずです。

括弧による優先順位

再帰下降構文解析が実装できていれば楽に実装できると思います。

フィボナッチ数

ここまでが実装できると、この時点ですでにフィボナッチ数を計算する関数を書けるようになっています。その他のいくつかの再帰的な数値計算などもできるようになっています。簡単な電卓言語としてはとりあえずこれで十分でしょう。

fib.calc

fib = if .<2; .; (fib . .-1;) + (fib . .-2;)
fib . 38

JIT

ここからはJITを実装していきますが、まずJITがなにかについて考えます。
JITはJust in Time、日本語でいうと 間に合わせ という意味ですが、言語処理系においてはインタプリタ実行の際に発生するコストをその場でネイティブコードにコンパイルして高速化するという意味で使われることが多いかと思います。

JITもいろいろな実装方式、手法がありますが、基本的に必要なことは以下です。

• 実行可能なメモリを用意する
• 式をネイティブコード(今回は機械語)にその場でコンパイルし、上記のメモリに書き込む
• 書き込んだネイティブコードを実行し、結果を受け取る

これらを実装すれば立派なJITといえるかと思います。

実行可能なメモリを用意する

メモリというのは基本的に多くの場合に実行可能ではありません。例えば、Cでよく使われるmallocにより確保されたメモリは実行可能ではありません。これはOSが確保したメモリを保護(protect)しているからです。
実行可能にするには、保護を外す、もしくは確保時に実行可能なメモリとして確保するということが必要です。今回は後者を採用しています。
実行可能なメモリを確保するにはOS依存のメモリ割り当てAPIを呼び出す必要があります。WindowsではVirtualAlloc、Linuxではmmapが今回の目的に該当します。(ちなみにmallocなどの標準メモリ割り当て関数などもこれらのAPIを内部で使っているはずです)

式をネイティブコードにコンパイルし、メモリに書き込む

今回扱う式は非常に単純な式であるので、単純なアセンブリにそのまま変換できるかと思います。
例えば 1 + 2 は

push 1
push 2
pop rcx
pop rax
add rax, rcx
push rax

のようなアセンブリに変換できます。少し冗長に見えるかもしれませんが、これは値を単純なスタックで受け渡しているため、このようなものになっています。ここで吐くアセンブリはいろいろ工夫ができるところですが、今回は楽さを重視して単純なスタックマシンにコンパイルしています。

あとは引数などの扱いを楽にするために、特定のレジスタを引数専用にしています。今回はr8レジスタがそれにあたります。今回は1引数しか使わないのでこれで事足ります。

ここで問題になるのが、アセンブリ自体が一種の言語であることです。今回欲しいのはアセンブリの出力ではなく機械語の出力であるため、アセンブリをどうにかして機械語にしなければなりません。
今回はアセンブラを実装することが目的ではないので、単純な 機械語をソースコードに直書きする という方法を取りました。 add rax, rcx は 0x48 0x01 0xc8 になるという具合に書いていきます。
アセンブリがどのような機械語になるかを確認するのには Online x86 / x64 Assembler and Disassembler が非常に便利です。これでアセンブリがどのような機械語になるかを確認しながら実装しました。
ここに関しては方法としてはいろいろで、nasmのようなアセンブラの出力を書き込んだり、XbyakなどのJITライブラリを使う、簡易的なアセンブラを実装してしまうなどのいろいろ方法があります。(余談: RubyのJITはCソースコードを出力してGCCでコンパイル、DLLとして動的ロードするという大胆な方法を取っているとのことです)

書き込んだネイティブコードを実行し、結果を受け取る

書き込んだネイティブコードは実行して結果を受け取らなければなりません。しかし、JITコンパイルしたネイティブコードはCとは違う世界です。呼び出すのも結果を受け取るのもそのままではできません。そこで橋渡しをする必要があります。

橋渡しにはインラインアセンブラを使います。ソースコード的にはjit_call関数が該当箇所です。やってることは難しくはなく、r8という引数専用レジスタに値を入れてJITしたネイティブコードのアドレスをcallしているだけです。これによりJITコンパイルしたネイティブコードとの齟齬を埋めることができます。

ベンチマーク

最後にJITによってどのくらい高速化されているのかを比較するためにベンチマークを取ってみました。
実行内容はfib(38)で、計測にはtimeコマンドを使っています。

方式	実行時間
インタプリタ	5.55s
JIT	0.44s

10倍以上の高速化に成功しています。今回のような簡単なJITでも単純な数値計算に関してはかなり高速化できますね。

終わりに

今回は簡単なJIT電卓言語を実装してみました。今回は電卓としての四則演算とJITに焦点を当てて実装しましたが、これに変数や複数引数を取れる関数、外部関数の呼び出し、構造体などを実装していくと立派なプログラミング言語になっていきます。

また、JITに関しても改善が可能な点が多くあります。今回の実装では簡略化のために関数はすべてJITコンパイルするという方式ですが、実際に使われている処理系のJITではどの関数をJITコンパイルするかなどを動的に判断したりしています。また、生成するネイティブコードについてもレジスタを有効活用するためにレジスタ割当を行うなどの工夫を行って高速化することが可能です。JITにおいては linear scan register allocation が多く使われているようです。気になる方は調べてみるといいかもしれません。

言語処理系は少しずつ実装していくと、ある時点で急激にできることが増えていき、様々なプログラムを書けるようになるので成長感があってとても楽しいです。Cコンパイラだったり電卓言語だったり僕の考えた最強の言語だったりを楽しみのためにいろいろ書いてみるのもいいんじゃないでしょうか。

余談: N高等学校まじで居心地良すぎて卒業したくない😭