ポータブルなJITコンパイラバックエンド

ポータブルで使いやすい
JITコンパイラ・バックエンド
数理・計算科学専攻千葉研究室
栗田洋輔
指導教員: 千葉滋
JITコンパイラの開発の難しさ


移植性の高いポータブルな JIT コンパイラ・フレーム
ワークがほしい
現状の技術


新しいJITコンパイラを開発
 実装が難しい
他言語のJIT コンパイラつきVMを利用
 Java VM、CLI など
 対象言語のソース・プログラムを
他言語（or 独自中間言語）のVMのバイトコードへ変換して実行

２つの言語の仕様のミスマッチが実装を面倒にする
ポータブルな
JITコンパイラ・バックエンドの提案
既に存在して
いることを仮定
インタプリタ
開発者が作成
バイトコード or AST
JITコンパイラ
開発者が作成
フロントエンド
コード生成
テンプレート
gccでコンパイル
中間表現
本システム
バックエンド
機械語
機械語
コンパイル済み
テンプレート
本システムの特徴

移植性が高い

JITコンパイラ作成者はマシン依存のコードを書かない


C言語とマシン非依存のマクロを使用
開発が容易

フロントエンド


ソース言語に合わせて中間表現を定義可能
コード生成テンプレート

元のインタープリタのコードを流用できる
最適化の手法

命令ポインタ(IP)に関わるオーバーヘッドを除去



バイトコードのフェッチ
バイトコードのデコード
オペランドのロード
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
バイトコード
ip
PUSH_CONST
2
PUSH_CONST
3
ADD
*++sp = (int)*++ip;
オペランドのロード
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
--sp;
*sp += sp[1];
*++sp = (int)*++ip;
*++sp = 2；
*++sp = (int)*++ip;
*++sp = 3；
--sp;
*sp += sp[1];
--sp;
*sp += sp[1];
開発者が自由に定義できる中間表現

中間表現の各ノード


各々のバイトコード命令に対応
コード生成テンプレートで開発者が定義
テンプレート
TMPL_PUSH
中間表現
バイトコード
PUSH 2
PUSH 3
label: TMPL_PUSH
holes: {hole1:=2}
機械語
2をPUSHする
label: TMPL_PUSH
holes: {hole1:=3}
ADD
label: TMPL_ADD
holes: NULL
3をPUSHする
スタックのトップにある
2つの値を加算
テンプレート
TMPL_ADD
テンプレートの定義
char *ip = code – 1;
for (;;) {
char* bcode = *++ip;
switch (bcode)
case ADD:
LABEL(ADD_b);
--sp;
*sp += sp[1];
LABEL(ADD_e);
break;
case PUSH_CONST:
*++sp = (int)*++ip;
break;
case TMPL_PUSH_CONST:
LABEL(TMPL_PUSH_CONST_b)
LABEL(TMPL_PUSH_CONST_b);
HOLE(hole1, int_val);
*++sp = int_val;
LABEL(TMPL_PUSH_CONST_e)
break;
}
}
インタープリター
のソースコード
を流用できる
機械語
--sp;
*sp += sp[1];
命令ポインタを含む
実装はテンプレート
として利用しない
機械語
HOLE(hole1, int_val);
*++sp = int_val;
定数値のコード中への埋め込み

HOLEマクロ


ラベルと即値命令に変換
即値命令の即値部分には中間表現で指定された定
数値が埋め込まれる
HOLEマクロ
HOLE(hole1, int_val);
中間表現
label: TMPL_PUSH
holes: {hole1 := 2}
label: TMPL_PUSH
holes: {hole1 := 3}
コンパイル済みテンプレート
参照 TMPL_PUSH
hole1:
movl $1234, %eax
…
TMPL_ADD
label: TMPL_ADD
holes: NULL
…
機械語
コピー
movl $2,
$1234,
%eax
%eax
…
movl $3,
$1234,
%eax
%eax
…
…
分岐命令の変換


全ての中間表現はバイトコードの番地を属性に持つ
分岐命令用中間表現


システムが機械語の分岐命令に変換する
テンプレートを用いない特殊な中間表現
中間表現
機械語
label: …
バイトコード番地: 0x0200
label: …
バイトコード番地: 0x0204
0x10000000
…
0x10000020
…
中略
中略
label: NULL
バイトコード番地: 0x0300
type: jump
ジャンプオフセット: -0x0100
0x10001000
分岐命令用
中間表現
jmp 0x10000000
フロントエンドによる最適化

融合命令の利用


融合命令を開発者がテンプレートで定義しておく
定数の畳み込み
中間表現 (最適化前)
label: SUB
中間表現 (最適化後)
融合命令
に変換
label: TMPL_SUB_MUL
label: MUL
label: TMPL_PUSH_CONST
holes: {hole1 => 2}
定数の畳み込み
label: TMPL_PUSH_CONST
holes: {hole1 => 3}
label: ADD
label: TMPL_PUSH_CONST
holes: {hole1 => 5}
抽象構文木インタープリタの場合

中間表現を木構造にする

抽象構文木では式が入れ子になる

各式の実行中にオペランド式の実行を行う
抽象構文木
PLUS
second
third
NUMBER: 2
中間表現
PLUS_label1
NUMBER 2
NUMBER: 3
PLUS
PLUS_label1
NUMBER 3
PLUSの実行中に
NUMBERの実行を行う
抽象構文木の巡回順
PLUS
NUMBER 2
PLUS
NUMBER 3
PLUS
抽象構文木インタープリタのテンプレート


テンプレートはvoid関数内に記述
変数はグローバル変数を利用
テンプレート
中間表現
PLUS
void code_PLUS() {
LABEL(PLUS_section);
LABEL(PLUS_label1);
sp--;
*sp = sp[1];
}
PLUS_label1
void code_NUMBER() {
int ret_val;
HOLE(hole1, ret_val);
*++sp = ret_val;
}
void code_PLUS() {
*++sp = 2;
*++sp = 3;
sp--;
*sp = sp[1];
}
NUMBER 2
機械語
PLUS_label1
NUMBER 3
予備的な実験
ディスパッチにswitchを用いた抽象構文木インタープリタ
(defun factorial (x)
(if x
(* x (factorial (- x 1)))
1))
(factorial 16) の実行結果
30
54
25
実行時間 [μs]
実行時間(JITなし)
53
52
20
51
50
15
49
10
48
47
5
46
0
45
O0
O1
O2
gcc最適化オプション
O3
JITコンパイル時間
[μs]

実行時間(JITあり)
JITコンパイル時間
Intel Xeon CPU 3.06GHz x 2
memory 2GB
linux 2.6.17
gcc 4.1.1
glibc 2.4
Gforthへの適用




バイトコードインタープリタ
コア部分はDirect threaded
code
ルーチン(Word)はDictionary
に保存される
JITコンパイルの開発


Dictionaryに最適化コードを
保存する
Direct threaded codeの延
長にテンプレートを記述
void *code[] = { ...,
&&opcode_push3,
&&opcode_push4,
&&opcode_add, ... };
/* 次の命令をディスパッチ */
#define NEXT() goto **++instructionPointer；
void **instructionPointer = code - 1;
/* 最初のオペコードをディスパッチ */
NEXT();
/* オペコードの実装 */
opcode_push3:
*++stackPointer = 3;
NEXT();
opcode_push4:
*++stackPointer = 4;
NEXT();
opcode_add:
--stackPointer;
*stackPointer += stackPointer[1];
NEXT();
/* ... */
Gforth用JITコンパイラ開発のコスト








プリミティブ命令の数431
インタープリタのプリミティブ命令の行数17019
テンプレートのためにプリミティブ命令の実装からコピーした
行数4201
テンプレートのために新たに書き加えた行数629
フロントエンドのためにインタープリタからコピーした行数
2355
フロントエンドのために新たに書き加えた行数1348
インタープリタ本体に新たに書き加えた行数306
JITコンパイラ開発のために新たに書き加えた総行数
629+1348+306=2283
Gforthでの実験
Gforthベンチマークの実行結果
900
25
実行時間(JITなし)
20
700
600
15
500
400
10
300
200
5
100
0
0
sieve
bubble
matrix
Gforthベンチマーク
fib
JITコンパイル時間
[ms]
実行時間 [ms]
800
実行時間(JITあり)
JITコンパイル時間
Intel Xeon CPU 3.06GHz x 2
memory 2GB
linux 2.6.17
gcc 4.1.1
glibc 2.4
関連研究

Cコンパイラが生成した機械語を利用する研究

ErtlらのJITコンパイラの移植に関する研究 [Ertl 04]




命令ポインタを除去して高速化するところが本研究に類似
インタープリタを書き換えないため、バイトコードの即値命令を機械語の
即値命令に書き換えられない場合がある
本研究はフレームワークおよびそれが解釈する中間表現を提供してい
る
DyC [Grant 00]

C言語用のRuntime Specializer


Tempo [Noel 98]



独自にコンパイラを拡張しているので移植性が低い
ランタイムコンパイラをフロントエンドからバックエンドまで提供
ネイティブコードの生成が半自動化されているため、フロントエンドでの
最適化を柔軟に行えない
VMの仕様記述からバイトコードインタプリタを自動生成する研究
 Virtual Machine Builder [内山 03]


実装の命令合成よりも強力な仕様記述上の命令合成が可能
静的コンパイルにしか対応していない
まとめ

ポータブルなJITコンパイラバックエンドの提案



移植性が高いアーキテクチャ
 フロントエンドの開発者はマシン依存のコードを書かない
開発が容易
 ソース言語に合わせて中間表現を定義可能
 元のインタープリタのコードを流用できる
実装・実験




抽象構文木インタープリタ(簡易Lisp)用JITコンパイラを作成
バイトコードインタープリタ(Gforth)用JITコンパイラを作成
それぞれにおいて最適化の効果を確認
JITコンパイラの開発にかかるコストが小さいことを確認

Download Report