この記事は「言語実装 Advent Calendar 2020」 21日目の記事です。
本記事は、主に JIT コンパイルに関する話題ですが、一般的なものではなく私の身の回りでやってることを中心にご紹介したいと思います。
はじめに
今回は、言語実装 Advent Calendar ということで 自作言語である Kinx における、最新の native 実装状況、そして JIT ライブラリのお話、および JIT 関連の注目ライブラリ MIR に関してご紹介します。本記事は、以下で構成されています。
-
JIT コンパイラのプラットフォーム依存性について
- JIT コンパイラの概要と課題。一般的には実行時にどこをコンパイルするかとかトレーシングがどうとかなのかもしれませんが、プラットフォーム依存も一つの問題です。Ruby は独特の方法で回避しましたが...
-
Kinx Native - sljit による JIT コンパイル
-
nativeというキーワードに関して元々は ここ(JIT Compile) でいくつか紹介していたのですが、その後、割とアップデートさせたので再度まとめ直してみました。
-
-
JIT ライブラリ - 手軽に JIT コンパイルを体験
- 直接アセンブラを使わないまでも、抽象化されたアセンブリを直接扱うためのライブラリを用意しています。その紹介と今後したいことなど。
-
MIR 感想
- 注目の JIT コンパイラ基盤。Cコンパイラが付いている。Ruby の人たちはよく知ってるアレです。非常に楽しみなプロジェクトで、少し触ってみた感想などをご紹介。
しかし本業が忙しすぎて色々なことを進める時間が圧倒的に足りなくなっている今、いつできるのか...。ちょっと前まではもう少し時間が取れたのですが。まぁ個人的なサイドプロジェクトなので、焦らず気長に行きます。もちろん、もし少しでもご興味を持っていただけるのであれば、どなたでもどんな内容でも コントリビュート大歓迎 です！（Kinx の GitHub は こちら）
【ご参考】Kinx とは
Kinx の最初のコミットは 2019/11/28 のようです。約 1 年（本記事の公開は 2020/12/21 ですが、書き始めたのは 11/11）経ちました。さて、元々の動機は下記を参照していただくとして、キャッチフレーズがありますので例によってそこからスタートします。Here we go!
「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。ご存じない方は下記をご参照ください。
- 参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
- 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
- Pull Request 等お待ちしております。
- Pull Request 等お待ちしております。
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
つい昨日（12/20）、「令和時代の基礎文法最速マスター Advent Calendar 2020」 20日目の記事として「Kinx 基礎文法最速マスター」がアップされましたので、そちらも合わせてご覧ください。
1. JIT コンパイラのプラットフォーム依存性について
あらためて、Just In Time、つまり まさにその場で コンパイルして実行する方式。ネイティブコード（機械語、マシン語1）にコンパイルして実行するため実行速度を追い求める人たちの間では 欲しくて欲しくてたまらない機能 の一つです。
ただし、普通は プロセッサーごとに個別に実装しないといけない。x64 だけ、とかならまだいいんだけど、どっかで ARM くらいはサポートすっかなー、とか、PowerPC は、SPARC?、とかになると、そもそもテストするのが大変です。
そして、同じ x64 でも Windows と Linux は違います。Microsoft x64 Calling Convention と System V Calling Convention という、いわゆる 呼出規約 というものが違っています。
Microsoft x64 / System V Calling Convention
そもそも関数呼び出しで使うレジスタが違います。これは読み替えればよいのだけれど。
| 引数 1 | 引数 2 | 引数 3 | 引数 4 | 引数 5 | 引数 6 | ... and more | |
|---|---|---|---|---|---|---|---|
| Microsoft | rcx |
rdx |
r8 |
r9 |
(stack) | (stack) | (stack) |
| System V | rdi |
rsi |
rdx |
rcx |
r8 |
r9 |
(stack) |
double 型の受け渡しにはどちらも SSE レジスタを使いますが、Microsoft x64 の場合は xmm0 から xmm3 まで、System V の場合は xmm0 から xmm7 までとなっています。そして、以下のように Microsoft x64 の場合は位置によって使うレジスタが固定であるのに対し、System V では 位置がズレます。
引数 1int
|
引数 2double
|
引数 3int
|
引数 4double
|
|
|---|---|---|---|---|
| Microsoft | ecx |
xmm1 |
r8d |
xmm3 |
| System V | edi |
xmm0 |
esi |
xmm1 |
こういうのを考えてプラットフォームごとに JIT コンパイラを作るわけですが、こういうのを意識しても所詮 x64 の世界の内側だけの話であって ARM にすら対応できていない、という現状なのです。
Ruby 方式
そこで、Ruby は なんと C ソースを出力してコンパイルして実行するという大胆な方式 を採用しました。メリットは上記に書いた多くのプロセッサへの対応を 他人に丸投げ（いい意味で）できること、デメリットはファイル入出力やプロセス起動などのオーバーヘッドが大いに気になることと 別途コンパイラを要求する ところ。実行環境にコンパイラを要求するのは、まぁ Linux なら gcc があるし、とか思うけど Windows が問題 ですよね。普通の人にコンパイラをインストールして、とかなかなか言いづらい。しかも本体とコンパイラを合わせないとイケなかったり。
これをやるなら、私なら C コンパイラも含めてパッケージに入れて提供したい、と思う。LLVM とか使えるのあるしね。デカいけど。ちなみに、以前 Clang で JIT するやり方を以下に公開してみました。Clang/LLVM 8.0.0 の頃なので多少古いが、今でも役に立つかな？
x64 だけに絞っても、全部スタティックリンクすると約 35MB の実行ファイルが出来上がります。デカいぜ。
そして（多少）時は流れ...
...と、ここまでは以前も書いた内容とほぼ同じ。で、やはり誰かが計画するわけですね。C コンパイラの同梱。そのためのプロジェクトが MIR です。がっつり Ruby の JIT に組み込むことを計画してます。軽量な最適化機能付き（関数のインライン展開付き） JIT コンパイラです。さらに、十分抽象化された中間表現 を持ち、それによって 様々なプラットフォームへの対応を可能 にしています。そして、C コンパイラが付いているのが超絶に便利 です。Ruby JIT に使うので当然でしょう。ところが、実はそれは単純に C スクリプト環境としても最適ということを意味します。あぁ、これ欲しかったですよ。ただし、まだバグも色々ありますが。
ある意味、C 言語にトランスパイルする言語はこれで全て実行可能にすることもできる でしょう。新たに C 言語にトランスパイルする言語を実装しようとしたとき、その言語実装自体は 超簡単 になりそうです2。...いや、いろいろ難しいかもしれませんが。イメージで話しました。すみません。
元々 Kinx でも同様に一気にアセンブルするやり方を試したりできないかなー、と kcs という自作 C JIT コンパイラを使ってみようと思ってました。ただ、x64 だけなのと最適化はほぼ無いので、MIR のほうが断然良いですね。もちろん kcs は JIT 基盤にしようとした訳ではなく、単に C スクリプトを実現しようとしたものなので、そもそもの目的が違ってます。しかし MIR みたいなのが出てくるとなると彼ももうお払い箱ですね…。残念ですが。一応 kcs の紹介だけ（更新止まってます）。
MIR は Ruby JIT への組み込みが計画されていますが、それだけでは勿体ないですね。これほどフレキシブルでライトウェイトでありながら、かつ十分抽象化された IR レイヤを持つ MIT ライセンスの（C コンパイラを含む）JIT コンパイラは他に見つけられなかったので、Kinx でも活用できないか、他に何か良い使い方が無いか、夢が膨らみます。MIR については後述します。つーか、Clang/LLVM はとにかくデカいんです（くどいですが）。
2. Kinx Native - sljit による JIT コンパイル
さて、本題に戻りましょう。まずは Kinx の native からです。
Kinx では、native というキーワードを使うことでネイティブ・コードにコンパイルして実行するという機能を持っています。いわゆるトレーシングとかは無しに、いきなりネイティブ・コードにコンパイルして実行させます。これは数値計算を主とする各種ベンチマークではそれなりに結構いい感じの結果を出してます。例えば「この記事」参照。
...が、実用上、通常のプログラムの中ではイマイチ使いこなせていません（私自身が。アイタタタ）。まぁでも、他の言語にはあまりない Kinx の特長でもあるので、大切に育てていきたい機能ではあります。
さて、Kinx の native による JIT コンパイルでは、上記のプラットフォームに依存してしまうという問題に対し、sljit を採用することで回避しています。sljit はアセンブラを抽象化しており、その抽象化アセンブラで書くことでコード出力時に x64 や ARM などに合わせて出力ができるようになっています。その代わり、レジスタ数とかどのプロセッサーでも共通に使えるようにミニマムに合わせておかなければなりません。
ちなみに、sljit のサポートアーキは以下の通りとのこと。
- Intel-x86 32
- AMD-x86 64
- ARM 32 (ARM-v5, ARM-v7 and Thumb2 instruction sets)
- ARM 64
- PowerPC 32
- PowerPC 64
- MIPS 32 (III, R1)
- MIPS 64 (III, R1)
- SPARC 32
ただし、x64 以外ではテストしていない & 64ビットしか想定していないので悪しからず。
具体的なソースコードとして、ネイティブ・コード用 IR 出力ルーチンは src/ast_native.c にあり、sljit を使ったネイティブ・コード用コンパイラは src/nir_compile.c にあります。
また、sljit 自体の使い方（と事例）は、先日「Kinx 実現技術 - JIT: sljit の使い方」に書いてみましたので、興味ある方はこちらも参照してみてください。
Native - 個別の実装状況
では、本題となるアップデート状況です。ここ(JIT Compile) での紹介の後、ちょっとずつ進化してます。
IR (Intermediate Representation) 
native ではネイティブ・コードに変換する上で扱いやすいように、スクリプト VM 用の IR と全く異なるコードを出力します。なぜなら例外の扱いとかコンパイル時点における型チェックの厳密さとかが全く異なるためで、それに合わせて違う体系にしています。
今回、IR 出力時のレジスタ割り当て方式を変更したところ、必要なレジスタ数が減ってだいぶスッキリさせられました。また、余計なコードもだいぶ出さないようにすることもしました。
前回の例でいうと、
native nfib(n) {
if (n < 3) return n;
return nfib(n-2) + nfib(n-1);
}
これは以下のようになります。
nfib(1, 3):
.L0
.L1
0: load r1, $(0,0)
1: lt r2 = r1, 3
2: jz .L4
.L2
3: load r1, $(0,0)
4: ret r1
.L3
.L4
5: load r1, $(0,0)
6: sub r2 = r1, 2
7: arg r2
8: call r1 = [rec-call]()
9: excpt r2 = check
a: jz .L6
.L5
b: ret 0
.L6
c: load r2, $(0,0)
d: sub r3 = r2, 1
e: arg r3
f: call r2 = [rec-call]()
10: excpt r3 = check
11: jz .L8
.L7
12: ret 0
.L8
13: add r3 = r1, r2
14: ret r3
.L9
15: ret 0
以前に比べて使用するレジスタ数が 10 → 3 に削減。ライン数も 0x20 → 0x15 に削減。
例外処理
例外機能は以前の記事から変わっていません。なので、現時点でも以下の制限があります。
- スタックトレースは取得できない。
- オブジェクトがまだ十分使えないので、キャッチする例外オブジェクトは実質あまり使えない。例外のフローはきちんと動作する。
いやぁ、もう少し機が熟す必要がありますね。
型チェック
これも以前から変わっていません。関数の入口で引数の型をチェック。レキシカル変数をアクセスする場合もチェック。関数から返ってきたときにもチェック。型が期待するものと違ってたらすぐさま例外を上げます。
Switch-Case
Switch-Case は、以前の記事では未サポートでしたが、頑張ってサポートしました。最新版では以下の形で実装しています。
- Case の数に応じて 2 分探索と線形探索を切り替える。
- Case 条件は Integer のみ。
- ジャンプテーブル化は現在未サポート。
たぶんジャンプテーブルも実現可能な感じには sljit をハックしたのですが、まずは 2 分探索で十分だろうと判断して上記で実現。少なくともこれで実用的な Switch-Case を実現することはできるので。ジャンプテーブル化は時間があれば実施しますが、優先度は低いです。
VM 関数呼び出し
これは現時点でも未サポートです。子 VM を起動してジャンプすれば良いとは思いますが、入れ子になった VM 内で例外が発生した場合の処理が大変そうなので、まだ手がつけられていません。おそらく以下のような感じでできるのでは、と思っています。
- フレームに
nativeからのコールであるフラグを立てる。 -
return時、nativeからであれば復帰値をセットして VM からreturnする。 - 例外発生時、スタックを巻き戻している最中に
nativeコールされたフラグを見つけた場合、そこでスタックトレース情報の作成を中断し、native向けの例外情報を設定してnativeにリターン。native側に帰ってきたら、nativeでの例外伝搬の仕組みで伝搬させていく。
例外のスタックトレースを native 関数内でも保存するようにしないといけません。やってみる時間があれば挑戦してみる、という予定ですが、今は難しい。ただ、たぶん面倒くさいだけで実現可能だとは思います。
オブジェクトへのアクセス
これは一部実装しました。具体的には Integer と Double への配列をサポートしました。以下のように Quick Sort くらいはできます。
native quicksort_n(a:int[], first, last) {
var i = first;
var j = last;
var x = a[(first + last) / 2];
while (true) {
while (a[i] < x) i++;
while (x < a[j]) j--;
if (i >= j) break;
[a[i], a[j]] = [a[j], a[i]];
++i; --j;
}
if (first < i - 1)
quicksort_n(a, first, i - 1);
if (j + 1 < last)
quicksort_n(a, j + 1, last);
}
const N = 20;
var a = N.times { => Integer.parseInt(Math.random() * 100) };
System.print("Before:");
a.each { System.print(" %2d" % _1); };
System.print("\n");
quicksort_n(a, 0, N - 1);
System.print("After: ");
a.each { System.print(" %2d" % _1); };
System.print("\n");
結果。
Before: 97 6 27 1 21 25 96 52 6 0 11 98 97 66 76 66 69 99 68 80
After: 0 1 6 6 11 21 25 27 52 66 66 68 69 76 80 96 97 97 98 99
整数配列は a:int[] と記述し、実数の場合は a:dbl[] という記述をします。
レジスタ割り付け
実際には変数へのレジスタ割り付け自体はやっていません。
...が、IR 出力時のレジスタ割り当て方式を 大幅に 変更したので、それに伴って演算結果で保存可能なものをレジスタに割り当てることにした結果、劇的にメモリアクセスが減りました。例えば、上記 fib の例でいうと以下のようになります。
以前のコードでは fib(n-2) の部分は以下のように出力されていました（無駄なコードがいっぱいです）。
d7: 48 8b 14 24 mov rdx, [rsp]
db: 48 89 94 24 30 02 00 00 mov [rsp+0x230], rdx
e3: 48 8b 94 24 30 02 00 00 mov rdx, [rsp+0x230]
eb: 48 83 ea 02 sub rdx, 0x02
ef: 48 89 94 24 38 02 00 00 mov [rsp+0x238], rdx
f7: 48 8b 94 24 38 02 00 00 mov rdx, [rsp+0x238]
ff: 48 89 54 24 18 mov [rsp+0x18], rdx
104: 48 c7 84 24 18 01 00 00 01 00 00 00 mov [rsp+0x118], 0x01
112: 48 8b 4b 18 mov rcx, [rbx+0x18]
116: 48 89 d8 mov rax, rbx
119: 49 8b 57 08 mov rdx, [r15+0x8]
11d: 48 89 54 24 10 mov [rsp+0x10], rdx
122: 48 8d 74 24 08 lea rsi, [rsp+0x8]
127: 48 89 c7 mov rdi, rax
12a: ff d1 call rcx
12c: 48 89 84 24 40 02 00 00 mov [rsp+0x240], rax
これがこうなりました。
93: 48 8b 2c 24 mov rbp, [rsp]
97: 48 8d 45 fe lea rax, [rbp-0x2]
9b: 48 89 44 24 18 mov [rsp+0x18], rax
a0: 48 c7 84 24 18 01 00 00 01 00 00 00 mov qword [rsp+0x118], 0x1
ac: 48 8b 4b 18 mov rcx, [rbx+0x18]
b0: 48 89 d8 mov rax, rbx
b3: 49 8b 57 08 mov rdx, [r15+0x8]
b7: 48 89 54 24 10 mov [rsp+0x10], rdx
bc: 48 8d 74 24 08 lea rsi, [rsp+0x8]
c1: 48 89 c7 mov rdi, rax
c4: ff d1 call rcx
c6: 48 89 c5 mov rbp, rax
分かりづらいとは思いますが全部載せるとこんな感じで、メモリアクセスがかなり減りました。
nfib: (native-base:0x7fbd9c030010)
0: 53 push rbx
1: 41 57 push r15
3: 41 56 push r14
5: 41 55 push r13
7: 55 push rbp
8: 41 54 push r12
a: 48 8b df mov rbx, rdi
d: 4c 8b fe mov r15, rsi
10: 4c 8b f2 mov r14, rdx
13: 48 81 ec 38 02 00 00 sub rsp, 0x238
1a: 49 8b 47 08 mov rax, [r15+0x8]
1e: 48 83 c0 01 add rax, 0x1
22: 49 89 47 08 mov [r15+0x8], rax
26: 48 3d 00 04 00 00 cmp rax, 0x400
2c: 72 29 jb 0x57
2e: 48 c7 43 20 01 00 00 00 mov qword [rbx+0x20], 0x1
36: 48 c7 43 28 06 00 00 00 mov qword [rbx+0x28], 0x6
3e: 48 c7 c0 00 00 00 00 mov rax, 0x0
45: 48 81 c4 38 02 00 00 add rsp, 0x238
4c: 41 5c pop r12
4e: 5d pop rbp
4f: 41 5d pop r13
51: 41 5e pop r14
53: 41 5f pop r15
55: 5b pop rbx
56: c3 ret
57: 49 83 bf 10 01 00 00 01 cmp qword [r15+0x110], 0x1
5f: 0f 85 11 01 00 00 jnz 0x176
65: 49 8b 57 10 mov rdx, [r15+0x10]
69: 48 89 14 24 mov [rsp], rdx
6d: 48 8b 2c 24 mov rbp, [rsp]
71: 48 89 e8 mov rax, rbp
74: 48 83 f8 03 cmp rax, 0x3
78: 7d 19 jge 0x93
7a: 48 8b 2c 24 mov rbp, [rsp]
7e: 48 89 e8 mov rax, rbp
81: 48 81 c4 38 02 00 00 add rsp, 0x238
88: 41 5c pop r12
8a: 5d pop rbp
8b: 41 5d pop r13
8d: 41 5e pop r14
8f: 41 5f pop r15
91: 5b pop rbx
92: c3 ret
93: 48 8b 2c 24 mov rbp, [rsp]
97: 48 8d 45 fe lea rax, [rbp-0x2]
9b: 48 89 44 24 18 mov [rsp+0x18], rax
a0: 48 c7 84 24 18 01 00 00 01 00 00 00 mov qword [rsp+0x118], 0x1
ac: 48 8b 4b 18 mov rcx, [rbx+0x18]
b0: 48 89 d8 mov rax, rbx
b3: 49 8b 57 08 mov rdx, [r15+0x8]
b7: 48 89 54 24 10 mov [rsp+0x10], rdx
bc: 48 8d 74 24 08 lea rsi, [rsp+0x8]
c1: 48 89 c7 mov rdi, rax
c4: ff d1 call rcx
c6: 48 89 c5 mov rbp, rax
c9: 48 8b 43 20 mov rax, [rbx+0x20]
cd: 48 83 f8 00 cmp rax, 0x0
d1: 74 19 jz 0xec
d3: 48 c7 c0 00 00 00 00 mov rax, 0x0
da: 48 81 c4 38 02 00 00 add rsp, 0x238
e1: 41 5c pop r12
e3: 5d pop rbp
e4: 41 5d pop r13
e6: 41 5e pop r14
e8: 41 5f pop r15
ea: 5b pop rbx
eb: c3 ret
ec: 4c 8b 24 24 mov r12, [rsp]
f0: 49 8d 44 24 ff lea rax, [r12-0x1]
f5: 48 89 44 24 18 mov [rsp+0x18], rax
fa: 48 c7 84 24 18 01 00 00 01 00 00 00 mov qword [rsp+0x118], 0x1
106: 48 8b 4b 18 mov rcx, [rbx+0x18]
10a: 48 89 d8 mov rax, rbx
10d: 49 8b 57 08 mov rdx, [r15+0x8]
111: 48 89 54 24 10 mov [rsp+0x10], rdx
116: 48 8d 74 24 08 lea rsi, [rsp+0x8]
11b: 48 89 c7 mov rdi, rax
11e: ff d1 call rcx
120: 49 89 c4 mov r12, rax
123: 48 8b 43 20 mov rax, [rbx+0x20]
127: 48 83 f8 00 cmp rax, 0x0
12b: 74 19 jz 0x146
12d: 48 c7 c0 00 00 00 00 mov rax, 0x0
134: 48 81 c4 38 02 00 00 add rsp, 0x238
13b: 41 5c pop r12
13d: 5d pop rbp
13e: 41 5d pop r13
140: 41 5e pop r14
142: 41 5f pop r15
144: 5b pop rbx
145: c3 ret
146: 4a 8d 44 25 00 lea rax, [rbp+r12]
14b: 48 81 c4 38 02 00 00 add rsp, 0x238
152: 41 5c pop r12
154: 5d pop rbp
155: 41 5d pop r13
157: 41 5e pop r14
159: 41 5f pop r15
15b: 5b pop rbx
15c: c3 ret
15d: 48 c7 c0 00 00 00 00 mov rax, 0x0
164: 48 81 c4 38 02 00 00 add rsp, 0x238
16b: 41 5c pop r12
16d: 5d pop rbp
16e: 41 5d pop r13
170: 41 5e pop r14
172: 41 5f pop r15
174: 5b pop rbx
175: c3 ret
176: 48 c7 43 20 01 00 00 00 mov qword [rbx+0x20], 0x1
17e: 48 c7 43 28 07 00 00 00 mov qword [rbx+0x28], 0x7
186: 48 c7 c0 00 00 00 00 mov rax, 0x0
18d: 48 81 c4 38 02 00 00 add rsp, 0x238
194: 41 5c pop r12
196: 5d pop rbp
197: 41 5d pop r13
199: 41 5e pop r14
19b: 41 5f pop r15
19d: 5b pop rbx
19e: c3 ret
最適化
定数伝搬と定数の畳み込み を実装しました。他はやっていませんが、enum とか const とかしてシンボル化した値を伝搬させて畳み込むのは結構効果があります。
Kinx Native - 今後の予定
以下はやりたいですが、全然取り掛かれる気配がないのが問題ですね。やはり焦らず気長に。。。
- オブジェクトの配列
- スクリプト関数の呼び出し
- オブジェクト・プロパティアクセス
- BigInteger のオブジェクト利用効率化
- 例外オブジェクトの送出
3. JIT ライブラリ - 手軽に JIT コンパイルを体験
さて、次は JIT ライブラリです。
Kinx では、native 以外にも直接 JIT を楽しめる JIT ライブラリがあります。これはまさしく sljit をラップしたライブラリです（sljit の使い方の例等は「こちら」）。必要なレジスタ数などの自動計算などもあり、直接使うより便利にはしています。
JIT ライブラリに関しては以下に記事を載せています。私個人的にはこれを拡張して色々できると楽しいなー、と思っていますが、なかなか手が付けられませんね。うーん。
以前と同じことを書いても仕方がないので、サンプルを再掲して今後したいことなど。細かい使い方に関しては上記の「JIT ライブラリ」をご参照ください。
JIT ライブラリ・サンプル
こんな感じで、抽象化アセンブラを Kinx 上から手軽に使えます。
using Jit;
var c = new Jit.Compiler();
var entry1 = c.enter();
var jump0 = c.ge(Jit.S0, Jit.IMM(3));
c.ret(Jit.S0);
var l1 = c.label();
c.sub(Jit.R0, Jit.S0, Jit.IMM(2));
c.call(entry1);
c.mov(Jit.S1, Jit.R0);
c.sub(Jit.R0, Jit.S0, Jit.IMM(1));
c.call(entry1);
c.add(Jit.R0, Jit.R0, Jit.S1);
c.ret(Jit.R0);
jump0.setLabel(l1);
var code = c.generate();
for (var i = 1; i <= 42; ++i) {
var tmr = new SystemTimer();
var r = code.run(i);
System.println("[%8.3f] fib(%2d) = %d" % tmr.elapsed() % i % r);
}
Jit.Compiler オブジェクトを作って、enter で関数エントリを作り、色々レジスタをいじくりまわして ret するコードを書きます。で、実行するときは generate() して run()、となります。generate() して dump() とすると、アセンブル・リストを見ることもできます。
上記は、よく見ないと分からないかもしれませんが（ご想像の通り）フィボナッチ数列を求めるプログラムです。アセンブル・リストを出してみましょう。実行せずに code.dump() とすると以下が表示されます。
0: 53 push rbx
1: 41 57 push r15
3: 41 56 push r14
5: 48 8b df mov rbx, rdi
8: 4c 8b fe mov r15, rsi
b: 4c 8b f2 mov r14, rdx
e: 48 83 ec 10 sub rsp, 0x10
12: 48 83 fb 03 cmp rbx, 0x3
16: 73 0d jae 0x25
18: 48 89 d8 mov rax, rbx
1b: 48 83 c4 10 add rsp, 0x10
1f: 41 5e pop r14
21: 41 5f pop r15
23: 5b pop rbx
24: c3 ret
25: 48 8d 43 fe lea rax, [rbx-0x2]
29: 48 89 fa mov rdx, rdi
2c: 48 89 c7 mov rdi, rax
2f: e8 cc ff ff ff call 0x0
34: 49 89 c7 mov r15, rax
37: 48 8d 43 ff lea rax, [rbx-0x1]
3b: 48 89 fa mov rdx, rdi
3e: 48 89 c7 mov rdi, rax
41: e8 ba ff ff ff call 0x0
46: 49 03 c7 add rax, r15
49: 48 83 c4 10 add rsp, 0x10
4d: 41 5e pop r14
4f: 41 5f pop r15
51: 5b pop rbx
52: c3 ret
ここでは Linux ですが、Windows だと使われるレジスタが変わります。そう、例の呼出規約の話です。型チェックなどがバッサリ無い分、そして書いた通りのコードが出ているので（大体のところ）非常に綺麗ですね。スタックの操作とかレジスタの退避とかは必要な分だけ自動的に行われるので、その辺りもラクチンです。
JIT ライブラリ・ベンチマーク
では、ベンチマークを載せてみましょう。fib(42) を再帰で計算させた結果です。
| 言語 | 版数 | User 時間 |
|---|---|---|
| Kinx(Jit-Lib) | 0.10.0 | 0.828 |
| HHVM | 3.21.0 | 2.227 |
| Kinx(native) | 0.10.0 | 2.250 |
| PyPy | 5.10.0 | 3.313 |
| PHP | 7.2.24 | 11.422 |
| Ruby | 2.5.1p57 | 14.877 |
| Kinx | 0.10.0 | 27.478 |
| Python | 2.7.15+ | 41.125 |
JIT ライブラリは結構使い方次第で役に立ちそうだとは思ってはいるんですけどね。何気に native もいい結果なので、目下、自己満足中です。しかし Ruby 速いなー。どんどん速くなるなー。いいナー3。それ以上に PHP が速いけど。
JIT ライブラリ・今後の予定
そんな JIT ライブラリとしては、以下を計画したいと思っています。
- 文字列操作機能（Kinx オブジェクトも使用可能かつある程度抽象化した形で）。
- C 関数のお手軽呼び出し機能。
C 関数をお手軽に呼べるようにできれば、かなり拡張できるようになります。具体的には dll からエントリ・ポイントを取得してコールするようにすれば良さそうなので、やればできそうです。
あー、やりたいことは沢山あります。焦らず、気長に。
4. MIR 感想
そしてお待ちかねの MIR です。Windows でも Linux でもそれなりには行けました。ここでは Linux での内容をお伝えします。オリジナルのリポジトリは以下です。
Build してみよう
では早速 MIR にトライしてみましょう。clone します。
$ git clone https://github.com/vnmakarov/mir.git
Cloning into 'mir'...
remote: Enumerating objects: 435, done.
remote: Counting objects: 100% (435/435), done.
remote: Compressing objects: 100% (231/231), done.
remote: Total 10386 (delta 280), reused 336 (delta 204), pack-reused 9951
Receiving objects: 100% (10386/10386), 3.59 MiB | 3.08 MiB/s, done.
Resolving deltas: 100% (6372/6372), done.
Checking out files: 100% (1370/1370), done.
$ cd mir
$ ls
CMakeLists.txt c2mir mir-gen-ppc64.c mir-interp.c mir.h
HOW-TO-PORT-MIR.md check-threads.sh mir-gen-s390x.c mir-ppc64.c mir2c
LICENSE include mir-gen-stub.c mir-reduce.h mir3.svg
MIR.md llvm2mir mir-gen-x86_64.c mir-s390x.c mirall.svg
Makefile mir-aarch64.c mir-gen.c mir-tests real-time.h
README.md mir-bin-driver.c mir-gen.h mir-utils sieve.c
adt-tests mir-bitmap.h mir-gen.svg mir-varr.h
c-benchmarks mir-dlist.h mir-hash.h mir-x86_64.c
c-tests mir-gen-aarch64.c mir-htab.h mir.c
cmake がありますが、Makefile がありますので Linux（実際は WSL）では直接 make します。
$ make
cc -std=gnu11 -Wno-abi -fsigned-char -fno-tree-sra -fno-ipa-cp-clone -DMIR_PARALLEL_GEN -c -O3 -g -DNDEBUG -o mir.o mir.c
cc -std=gnu11 -Wno-abi -fsigned-char -fno-tree-sra -fno-ipa-cp-clone -DMIR_PARALLEL_GEN -c -O3 -g -DNDEBUG -o mir-gen.o mir-gen.c
cc -std=gnu11 -Wno-abi -fsigned-char -fno-tree-sra -fno-ipa-cp-clone -DMIR_PARALLEL_GEN -O3 -g -DNDEBUG -I. mir-gen.o c2mir/c2mir.c c2mir/c2mir-driver.c mir.o -lm -ldl -lpthread -o c2m
cc -std=gnu11 -Wno-abi -fsigned-char -fno-tree-sra -fno-ipa-cp-clone -DMIR_PARALLEL_GEN -I. -O3 -g -DNDEBUG -o m2b mir.o mir-utils/m2b.c
cc -std=gnu11 -Wno-abi -fsigned-char -fno-tree-sra -fno-ipa-cp-clone -DMIR_PARALLEL_GEN -I. -O3 -g -DNDEBUG -o b2m mir.o mir-utils/b2m.c
cc -std=gnu11 -Wno-abi -fsigned-char -fno-tree-sra -fno-ipa-cp-clone -DMIR_PARALLEL_GEN -I. -O3 -g -DNDEBUG -o b2ctab mir.o mir-utils/b2ctab.c
あっさりと、うまくいきました。
ベンチマークしてみよう
では恒例のフィボナッチ、行ってみましょう。JIT ライブラリのときと同じ条件で fib(42) で実行し、結果をマージしてみます。
int printf(const char *fmt, ...);
#define N 42
int fib(int n)
{
if (n < 3) return n;
return fib(n-2) + fib(n-1);
}
int main(void)
{
printf("fib %d = %d\n", N, fib(N));
return 0;
}
gcc と比較してみるため、gcc でもコンパイル。
$ gcc -O0 -o fib_gcc_o0 fib.c
$ gcc -O2 -o fib_gcc_o2 fib.c
さて、結果です。
| 言語 | 版数 | User 時間 | 備考 |
|---|---|---|---|
| GCC -O2 | 7.5.0 | 0.531 | コンパイル時間を除く |
| Kinx(Jit-Lib) | 0.10.0 | 0.828 | |
| GCC -O0 | 7.5.0 | 1.109 | コンパイル時間を除く |
| c2m -eg | - | 1.500 | 全ての関数を最初にコンパイルする方式 |
| c2m -el | - | 1.750 | 関数が呼び出される直前にコンパイル、必要な関数のみコンパイル |
| HHVM | 3.21.0 | 2.227 | |
| Kinx(native) | 0.10.0 | 2.250 | |
| PyPy | 5.10.0 | 3.313 | |
| PHP | 7.2.24 | 11.422 | |
| Ruby | 2.5.1p57 | 14.877 | |
| Kinx | 0.10.0 | 27.478 | |
| Python | 2.7.15+ | 41.125 | |
| c2m -ei | - | 71.453 | 全て MIR インタプリタで実行 |
さすがに GCC -O2 が速いです。といってもコンパイルが無視されていますがこの程度だと 15ms くらいだったのでまぁ良いでしょう。今のところ、GCC の最適化無しでも c2m より速いようですが、コンパイル時間を除くと若干差は縮まるとは思われます。尚、c2m は -O2 がデフォルトのようです。-O0 を付けると遅くなります。元々、gcc とか clang とかはスタートアップとコンパイルフェーズが長いのでそれを回避したい、ということなので、ランタイムは多少遅くても良いでしょう。そういう意味では gcc とは比較したい場所が違いますね。
この MIR、まだプロジェクトは初期のステージとのことなのでこれからと言ったところでしょう。現時点での結果としては、全然悪くないです。
IR 自体まだ仕様が安定してなさそうなのですが、非常に楽しみです。
（その他）MIR での標準ライブラリについて
printf を自分でプロトタイプ宣言してますが、MIR では標準ライブラリを 動的にロードして 実行していました。おお、画期的。こんなやり方できたんですね。目からうろこでした。実際本当にいいのかはよくわかりませんが、このやり方でうまく動いています。
具体的には以下のソースコードです（リンク先が変わってしまったらごめんなさい）。
-
https://github.com/vnmakarov/mir/blob/master/c2mir/c2mir-driver.c
-
std_libs配列に標準ライブラリの dll/so ファイルのパスを入れておき、dlopen等で動的にエントリ・ポイントを取得。
-
この技、今度使おう。
今後
いくつか妄想だけでも...
- Ruby 方式の簡易版 JIT コンパイルを Kinx で実現してみたり。
- C 拡張スクリプトとして色んな言語の拡張を C の動的コンパイルで実現できるようにしてみたり。
- 簡単なサンプル自作言語として C へのトランスパイラを作成してみたり。
時間がいくらあっても足りない。
と、いいつつ、MIR を使いたい一心で何か始めます。というか始めてます。ちゃんと記事ができるようになったら紹介できるかもしれません。
おわりに
ここまで読んでくださってありがとうございます。
今後、以下のようなことは考えています。
言語実装 Advent Calendar ということで、自作言語 Kinx を紹介させていただくと共に、それに関する JIT 関連と最近の興味を記事にしてみました。全部と言わずとも少しでも皆さんの興味にヒットして、何かしらのお役に立てれば幸いです。
また、もし宜しければ Kinx は GitHub にソースコードを公開していますので、Star とか貰えるとやる気出ます（やる気があっても時間がないのはいかんともしがたいが...）。泣き言言ってますが、焦らず、気長に見守っててください。もちろん、最初にも書きましたが、どなたでもどんな内容でも コントリビュート大歓迎 ですので、何かありましたらぜひぜひ宜しくお願い致します。
ではこの辺で、またどこかでお会いしましょう。
改めて、最後までお読みいただき、ありがとうございました。
-
全く関係ない話ですが、昔、何かの本で「マシン語は一部で『魔神語』と呼ばれ恐れられている」（←うろ覚え、適当）みたいなことが書いてあって、子供ながらに面白いと思った記憶が多少残ってます（なんだっけなー）。 ↩
-
当時（Kinx を作り始めたのは約 1 年前）、これの完成版があったら、もしかしたら最初から全て C 言語にトランスコンパイルする形で設計したかもしれません。というより、Kinx 以前に同じシンタックスで作っていた前身言語は、Kinx 同様 VM 実行させるように実装した後、Clang ベースで別バージョンを作った過去があります。当然のように起動がモッサリしました。MIR はこういうのを避けられそうで Good です。 ↩
-
ちなみに Kinx は Ruby 2.4.0 と大体同じくらいの実行速度なレベルです。VM 性能は、割とがっつりチューニングしているのでそんなに変わらん気がするのだが。GC の差かな。あまり頑張って調べる気はないのですけど。Kinx の GC は当初から変わらず Stop The World での Mark & Sweep を堅持しているので。しかし、Ruby は1.8.7 の頃とは全く比較になりませんね。 ↩
-
Kinx 自体はデバッガ作りたいとか、Language Server をサポートしたい（主に VSCode）とか、パッケージマネージャーを用意したいとか、マニュアルをコンプリートさせたいとか、GUI ライブラリ取り揃えたいとか、やりたいことはテンコ盛りなのですが…。 ↩