Kinx での JIT、そして MIR の話 ... Ruby だけでは勿体ないネ

この記事は「[言語実装 Advent Calendar 2020](https://qiita.com/advent-calendar/2020/lang_dev)」 21日目の記事です。

本記事は、主に JIT コンパイルに関する話題ですが、一般的なものではなく私の身の回りでやってることを中心にご紹介したいと思います。

# はじめに

今回は、言語実装 Advent Calendar ということで **自作言語である [Kinx](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76)** における、最新の `native` 実装状況、そして JIT ライブラリのお話、および JIT 関連の注目ライブラリ MIR に関してご紹介します。本記事は、以下で構成されています。

1. **JIT コンパイラのプラットフォーム依存性について**
    * JIT コンパイラの概要と課題。一般的には実行時にどこをコンパイルするかとかトレーシングがどうとかなのかもしれませんが、プラットフォーム依存も一つの問題です。Ruby は独特の方法で回避しましたが...
2. **Kinx Native - [sljit](https://github.com/zherczeg/sljit) による JIT コンパイル**
    * `native` というキーワードに関して元々は [ここ(JIT Compile)](https://qiita.com/Kray-G/items/66257e4cca0ad6dd7636) でいくつか紹介していたのですが、その後、割とアップデートさせたので再度まとめ直してみました。
3. **JIT ライブラリ - 手軽に JIT コンパイルを体験**
    * 直接アセンブラを使わないまでも、抽象化されたアセンブリを直接扱うためのライブラリを用意しています。その紹介と今後したいことなど。
4. **[MIR](https://github.com/vnmakarov/mir) 感想**
    * 注目の JIT コンパイラ基盤。**Cコンパイラが付いている**。Ruby の人たちはよく知ってるアレです。非常に楽しみなプロジェクトで、少し触ってみた感想などをご紹介。

しかし本業が忙しすぎて色々なことを進める時間が圧倒的に足りなくなっている今、いつできるのか...。ちょっと前まではもう少し時間が取れたのですが。まぁ個人的なサイドプロジェクトなので、焦らず気長に行きます。もちろん、もし少しでもご興味を持っていただけるのであれば、どなたでもどんな内容でも **コントリビュート大歓迎** です！（Kinx の GitHub は [こちら](https://github.com/Kray-G/kinx)）

## 【ご参考】Kinx とは

> Kinx の最初のコミットは 2019/11/28 のようです。約 1 年（本記事の公開は 2020/12/21 ですが、書き始めたのは 11/11）経ちました。さて、元々の動機は下記を参照していただくとして、キャッチフレーズがありますので例によってそこからスタートします。Here we go!

**「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」** でお届けしているスクリプト言語 [Kinx](https://github.com/Kray-G/kinx)。ご存じない方は下記をご参照ください。

* 参考
    * 最初の動機 ... [スクリプト言語 KINX（ご紹介）](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76)
        * 個別記事へのリンクは全てここに集約してあります。
    * リポジトリ ... [https://github.com/Kray-G/kinx](https://github.com/Kray-G/kinx)
        * Pull Request 等お待ちしております。  

つい昨日（12/20）、「[令和時代の基礎文法最速マスター Advent Calendar 2020](https://qiita.com/advent-calendar/2020/reiwa_saisoku)」 20日目の記事として「[Kinx 基礎文法最速マスター](https://qiita.com/Kray-G/items/e6d8087aba2ce84fc43c)」がアップされましたので、そちらも合わせてご覧ください。

# 1. JIT コンパイラのプラットフォーム依存性について

あらためて、Just In Time、つまり **まさにその場で** コンパイルして実行する方式。ネイティブコード（機械語、マシン語[^machine]）にコンパイルして実行するため実行速度を追い求める人たちの間では **欲しくて欲しくてたまらない機能** の一つです。

[^machine]: 全く関係ない話ですが、昔、何かの本で「マシン語は一部で『魔神語』と呼ばれ恐れられている」（←うろ覚え、適当）みたいなことが書いてあって、子供ながらに面白いと思った記憶が多少残ってます（なんだっけなー）。

ただし、**普通は** プロセッサーごとに個別に実装しないといけない。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 では **位置がズレます**。

|           | 引数 1<br />`int` | 引数 2<br />`double` | 引数 3<br />`int` | 引数 4<br />`double` |
| --------- | :---------------: | :------------------: | :---------------: | :------------------: |
| 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 の頃なので多少古いが、今でも役に立つかな？

* https://github.com/Kray-G/clang-jit

x64 だけに絞っても、全部スタティックリンクすると約 35MB の実行ファイルが出来上がります。デカいぜ。

### そして（多少）時は流れ...

...と、ここまでは以前も書いた内容とほぼ同じ。で、やはり誰かが計画するわけですね。**C コンパイラの同梱**。そのためのプロジェクトが [**MIR**](https://github.com/vnmakarov/mir) です。がっつり Ruby の JIT に組み込むことを計画してます。軽量な最適化機能付き（関数のインライン展開付き） JIT コンパイラです。さらに、**十分抽象化された中間表現** を持ち、それによって **様々なプラットフォームへの対応を可能** にしています。そして、**C コンパイラが付いているのが超絶に便利** です。Ruby JIT に使うので当然でしょう。ところが、実はそれは単純に C スクリプト環境としても最適ということを意味します。あぁ、これ欲しかったですよ。ただし、まだバグも色々ありますが。

ある意味、**C 言語にトランスパイルする言語はこれで全て実行可能にすることもできる** でしょう。新たに C 言語にトランスパイルする言語を実装しようとしたとき、その言語実装自体は **超簡単** になりそうです[^kinxx]。...いや、いろいろ難しいかもしれませんが。イメージで話しました。すみません。

[^kinxx]: 当時（Kinx を作り始めたのは約 1 年前）、これの完成版があったら、もしかしたら最初から全て C 言語にトランスコンパイルする形で設計したかもしれません。というより、Kinx 以前に同じシンタックスで作っていた前身言語は、Kinx 同様 VM 実行させるように実装した後、Clang ベースで別バージョンを作った過去があります。当然のように起動がモッサリしました。MIR はこういうのを避けられそうで Good です。

元々 Kinx でも同様に一気にアセンブルするやり方を試したりできないかなー、と [kcs](https://github.com/Kray-G/kcs) という自作 C JIT コンパイラを使ってみようと思ってました。ただ、x64 だけなのと最適化はほぼ無いので、MIR のほうが断然良いですね。もちろん kcs は JIT 基盤にしようとした訳ではなく、単に C スクリプトを実現しようとしたものなので、そもそもの目的が違ってます。しかし MIR みたいなのが出てくるとなると彼ももうお払い箱ですね…。残念ですが。一応 kcs の紹介だけ（更新止まってます）。

* kcs - https://github.com/Kray-G/kcs

MIR は Ruby JIT への組み込みが計画されていますが、それだけでは勿体ないですね。これほどフレキシブルでライトウェイトでありながら、かつ十分抽象化された IR レイヤを持つ MIT ライセンスの（C コンパイラを含む）JIT コンパイラは他に見つけられなかったので、Kinx でも活用できないか、他に何か良い使い方が無いか、夢が膨らみます。MIR については後述します。つーか、Clang/LLVM はとにかくデカいんです（くどいですが）。

# 2. Kinx Native - [sljit](https://github.com/zherczeg/sljit) による JIT コンパイル

さて、本題に戻りましょう。まずは Kinx の `native` からです。

Kinx では、`native` というキーワードを使うことでネイティブ・コードにコンパイルして実行するという機能を持っています。いわゆるトレーシングとかは無しに、いきなりネイティブ・コードにコンパイルして実行させます。これは数値計算を主とする各種ベンチマークではそれなりに結構いい感じの結果を出してます。例えば「[この記事](https://qiita.com/Kray-G/items/222e6936daf612673999)」参照。

...が、実用上、通常のプログラムの中ではイマイチ使いこなせていません（私自身が。アイタタタ）。まぁでも、他の言語にはあまりない Kinx の特長でもあるので、大切に育てていきたい機能ではあります。

さて、Kinx の `native` による JIT コンパイルでは、上記のプラットフォームに依存してしまうという問題に対し、[sljit](https://github.com/zherczeg/sljit) を採用することで回避しています。[sljit](https://github.com/zherczeg/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](https://github.com/Kray-G/kinx/blob/master/src/ast_native.c) にあり、[sljit](https://github.com/zherczeg/sljit) を使ったネイティブ・コード用コンパイラは [src/nir_compile.c](https://github.com/Kray-G/kinx/blob/master/src/nir_compile.c) にあります。

また、[sljit](https://github.com/zherczeg/sljit) 自体の使い方（と事例）は、先日「[Kinx 実現技術 - JIT: sljit の使い方](https://qiita.com/Kray-G/items/c0636ede884ef6094daa)」に書いてみましたので、興味ある方はこちらも参照してみてください。

## Native - 個別の実装状況

では、本題となるアップデート状況です。[ここ(JIT Compile)](https://qiita.com/Kray-G/items/66257e4cca0ad6dd7636) での紹介の後、ちょっとずつ進化してます。

### IR (Intermediate Representation) :tada:

`native` ではネイティブ・コードに変換する上で扱いやすいように、スクリプト VM 用の IR と全く異なるコードを出力します。なぜなら例外の扱いとかコンパイル時点における型チェックの厳密さとかが全く異なるためで、それに合わせて違う体系にしています。

今回、IR 出力時のレジスタ割り当て方式を変更したところ、必要なレジスタ数が減ってだいぶスッキリさせられました。また、余計なコードもだいぶ出さないようにすることもしました。

前回の例でいうと、

```javascript
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 に削減。

### 例外処理

例外機能は[以前の記事](https://qiita.com/Kray-G/items/66257e4cca0ad6dd7636)から変わっていません。なので、現時点でも以下の制限があります。

* スタックトレースは取得できない。
* オブジェクトがまだ十分使えないので、キャッチする例外オブジェクトは実質あまり使えない。例外のフローはきちんと動作する。

いやぁ、もう少し機が熟す必要がありますね。

### 型チェック

これも[以前](https://qiita.com/Kray-G/items/66257e4cca0ad6dd7636)から変わっていません。関数の入口で引数の型をチェック。レキシカル変数をアクセスする場合もチェック。関数から返ってきたときにもチェック。型が期待するものと違ってたらすぐさま例外を上げます。

### Switch-Case :tada:

Switch-Case は、[以前の記事](https://qiita.com/Kray-G/items/66257e4cca0ad6dd7636)では未サポートでしたが、頑張ってサポートしました。最新版では以下の形で実装しています。

* Case の数に応じて 2 分探索と線形探索を切り替える。
* Case 条件は Integer のみ。
* ジャンプテーブル化は現在未サポート。

たぶんジャンプテーブルも実現可能な感じには [sljit](https://github.com/zherczeg/sljit) をハックしたのですが、まずは 2 分探索で十分だろうと判断して上記で実現。少なくともこれで実用的な Switch-Case を実現することはできるので。ジャンプテーブル化は時間があれば実施しますが、優先度は低いです。

### VM 関数呼び出し

これは現時点でも未サポートです。子 VM を起動してジャンプすれば良いとは思いますが、入れ子になった VM 内で例外が発生した場合の処理が大変そうなので、まだ手がつけられていません。おそらく以下のような感じでできるのでは、と思っています。

* フレームに `native` からのコールであるフラグを立てる。
* `return` 時、`native` からであれば復帰値をセットして　VM から `return` する。
* 例外発生時、スタックを巻き戻している最中に `native` コールされたフラグを見つけた場合、そこでスタックトレース情報の作成を中断し、`native` 向けの例外情報を設定して `native` にリターン。`native` 側に帰ってきたら、`native` での例外伝搬の仕組みで伝搬させていく。

例外のスタックトレースを `native` 関数内でも保存するようにしないといけません。やってみる時間があれば挑戦してみる、という予定ですが、今は難しい。ただ、たぶん面倒くさいだけで実現可能だとは思います。

### オブジェクトへのアクセス :tada:

これは一部実装しました。具体的には `Integer` と `Double` への配列をサポートしました。以下のように Quick Sort くらいはできます。

```javascript
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[]` という記述をします。

### レジスタ割り付け :tada:

実際には変数へのレジスタ割り付け自体はやっていません。

...が、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
```

### 最適化 :tada:

**定数伝搬と定数の畳み込み** を実装しました。他はやっていませんが、`enum` とか `const` とかしてシンボル化した値を伝搬させて畳み込むのは結構効果があります。

## Kinx Native - 今後の予定

以下はやりたいですが、全然取り掛かれる気配がないのが問題ですね。やはり焦らず気長に。。。

* オブジェクトの配列
* スクリプト関数の呼び出し
* オブジェクト・プロパティアクセス
* BigInteger のオブジェクト利用効率化
* 例外オブジェクトの送出

# 3. JIT ライブラリ - 手軽に JIT コンパイルを体験

さて、次は JIT ライブラリです。

Kinx では、`native` 以外にも直接 JIT を楽しめる JIT ライブラリがあります。これはまさしく [sljit](https://github.com/zherczeg/sljit) をラップしたライブラリです（[sljit](https://github.com/zherczeg/sljit) の使い方の例等は「[こちら](https://qiita.com/Kray-G/items/c0636ede884ef6094daa)」）。必要なレジスタ数などの自動計算などもあり、直接使うより便利にはしています。

JIT ライブラリに関しては以下に記事を載せています。私個人的にはこれを拡張して色々できると楽しいなー、と思っていますが、なかなか手が付けられませんね。うーん。

* [JIT ライブラリ](https://qiita.com/Kray-G/items/a237f195630f3f0a91df)
* [JIT ライブラリ（番外編）](https://qiita.com/Kray-G/items/6d85d97b93d11c956b54)

以前と同じことを書いても仕方がないので、サンプルを再掲して今後したいことなど。細かい使い方に関しては上記の「[JIT ライブラリ](https://qiita.com/Kray-G/items/a237f195630f3f0a91df)」をご参照ください。

## JIT ライブラリ・サンプル

こんな感じで、抽象化アセンブラを Kinx 上から手軽に使えます。

```javascript
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 速いなー。どんどん速くなるなー。いいナー[^ruby]。それ以上に PHP が速いけど。

[^ruby]: ちなみに Kinx は Ruby 2.4.0 と大体同じくらいの実行速度なレベルです。VM 性能は、割とがっつりチューニングしているのでそんなに変わらん気がするのだが。GC の差かな。あまり頑張って調べる気はないのですけど。Kinx の GC は当初から変わらず Stop The World での Mark & Sweep を堅持しているので。しかし、Ruby は1.8.7 の頃とは全く比較になりませんね。

## JIT ライブラリ・今後の予定

そんな JIT ライブラリとしては、以下を計画したいと思っています。

* 文字列操作機能（Kinx オブジェクトも使用可能かつある程度抽象化した形で）。
* C 関数のお手軽呼び出し機能。

C 関数をお手軽に呼べるようにできれば、かなり拡張できるようになります。具体的には dll からエントリ・ポイントを取得してコールするようにすれば良さそうなので、やればできそうです。

あー、やりたいことは沢山あります。焦らず、気長に。

# 4. MIR 感想

そしてお待ちかねの [MIR](https://github.com/vnmakarov/mir) です。Windows でも Linux でもそれなりには行けました。ここでは Linux での内容をお伝えします。オリジナルのリポジトリは以下です。

* https://github.com/vnmakarov/mir

## 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) で実行し、結果をマージしてみます。

```c
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 を使いたい一心で何か始めます。というか始めてます。ちゃんと記事ができるようになったら紹介できるかもしれません。

# おわりに

ここまで読んでくださってありがとうございます。

今後、以下のようなことは考えています。

* [Kinx](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76) の `native` 機能をゆっくりでも育てていく[^kinxfuture]。
* [Kinx](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76) の JIT ライブラリを機能拡張する。
* [MIR](https://github.com/vnmakarov/mir) でチャレンジ精神を発揮する。

[^kinxfuture]: Kinx 自体はデバッガ作りたいとか、Language Server をサポートしたい（主に VSCode）とか、パッケージマネージャーを用意したいとか、マニュアルをコンプリートさせたいとか、GUI ライブラリ取り揃えたいとか、やりたいことはテンコ盛りなのですが…。

言語実装 Advent Calendar ということで、自作言語 [Kinx](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76) を紹介させていただくと共に、それに関する JIT 関連と最近の興味を記事にしてみました。全部と言わずとも少しでも皆さんの興味にヒットして、何かしらのお役に立てれば幸いです。

また、もし宜しければ Kinx は GitHub にソースコードを公開していますので、Star とか貰えるとやる気出ます（やる気があっても時間がないのはいかんともしがたいが...）。泣き言言ってますが、焦らず、気長に見守っててください。もちろん、最初にも書きましたが、どなたでもどんな内容でも **コントリビュート大歓迎** ですので、何かありましたらぜひぜひ宜しくお願い致します。

* https://github.com/Kray-G/kinx

ではこの辺で、またどこかでお会いしましょう。

改めて、最後までお読みいただき、ありがとうございました。