C言語を用いたマシン非依存な

C言語を用いたマシン非依存な
JITコンパイラ作成フレームワーク
栗田洋輔千葉滋
東京工業大学
1
従来のJITコンパイラの開発と問題点



本格的なJITコンパイラ
 プラットフォーム依存の中間表現を作成し、それを機械語に変換
移植性の問題
 マシンごとにプラットフォーム依存の中間表現を作成
実装の容易性の問題
 高い開発スキルが必要
 バイトコードから中間表現への変換
 中間表現から機械語への変換
バイトコード
機械語
プラットフォーム依存の中間表現
2
本研究の目的

JIT コンパイラ作成を容易にするフレームワーク


移植性が高い
短いコンパイル時間でそこそこの品質のコードを生成
実装の容易性
移植性
実行速度
コンパイル時間
ネイティブコンパイラ
△
×
◎
×
インタープリタ
◎
◎
×
◎
従来のJITコンパイラ
×
×
○
△
本フレームワークを用いて ○
開発するJITコンパイラ
○
△
○
3
そこそこの最適化

本質的なオーバーヘッドを除去することで高速
化を行う


広い範囲のインタープリターに適用できる
汎用的な手法
本質的なオーバーヘッド


バイトコードインタープリター
 次の命令をフェッチしてデコードするコスト
 バイトコードのオペランドをメモリからロードするコスト
抽象構文木のインタープリター
 抽象構文木を巡回してノードをデコードするコスト
4
命令をフェッチ・デコードする
オーバーヘッド (1/2)

命令ポインタ(ip)のインクリメントと
メモリからのフェッチ
インタープリター
バイトコード
ip
ip
ip
ip
ip
PUSH_CONST
2
PUSH_CONST
3
ADD
char *ip = code – 1;
for (;;) {
char* bcode = *++ip;
switch (bcode)
case PUSH_CONST:
*++sp = (int)*++ip;
break;
case ADD:
--sp;
*sp += sp[1];
break;
/* other cases …*/
}
}
トレース
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
--sp;
5
*sp += sp[1];
命令をフェッチ・デコードする
オーバーヘッド (2/2)

バイトコードのデコード

switchによる条件分岐で実装
インタープリター
バイトコード
PUSH_CONST
2
PUSH_CONST
3
ADD
char *ip = code – 1;
for (;;) {
char* bcode = *++ip;
switch (bcode)
case PUSH_CONST:
*++sp = (int)*++ip;
break;
case ADD:
--sp;
*sp += sp[1];
break;
/* other cases …*/
}
}
トレース
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
--sp;
6
*sp += sp[1];
命令をフェッチ・デコードする
オーバーヘッドの除去

高速化を達成


フェッチ・デコード部分を削除
本体部分のみを並べる
命令ポインタの指す
アドレスが不正
フェッチ bcode = *++ip;
*++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
*++ip;
フェッチ bcode = *++ip;
*++sp = (int)*++ip;
(int)*++ip;
*++sp = (int)*++ip;
(int)*++ip;
--sp;
*sp += sp[1];
デコード switch (bcode)
本体
--sp;
*sp += sp[1];
7
バイトコードのオペランドをメモリから
ロードするコストの削減

バイトコードのオペランドをメモリからロード

オペランドの値が既知の場合には不必要
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
デコード switch (bcode)
本体
*++sp = (int)*++ip;
フェッチ bcode = *++ip;
*++sp = (int)*++ip;
(int)*++ip;
*++sp = 2；
*++sp = (int)*++ip;
(int)*++ip;
*++sp = 3；
--sp;
*sp += sp[1];
--sp;
*sp += sp[1];
デコード switch (bcode)
本体
--sp;
*sp += sp[1];
8
JIT コンパイラ・フレームワーク
の提案

プラットフォーム独立な中間表現


中間表現から機械語への変換はフレームワークが担当
 高い移植性を実現（フレームワーク自体の移植は必要）
テンプレート


中間表現の各ノードに対応する機械語のひな形
中間表現のセマンティクスを与える
JITコンパイラの
作成者が実装
テンプレート
バイトコード
機械語
9
プラットフォーム独立な中間表現
テンプレートの書き方

インタープリターの主ループそのもの
テンプレート
char *ip = code – 1;
 記述は容易
for (;;) {
char* bcode = *++ip;
 一部の命令は、テンプレート用に書き
switch (bcode)
換えが必要
case ADD:
--sp;
 命令ポインタ (IP) を使っている場合
*sp += sp[1];
 生成される機械語に IP は含められない
break;
 IP でオペランド（即値）を取得する
case PUSH_CONST:
*++sp = (int)*++ip;
 HOLEマクロを利用
break;
 gccインラインアセンブリに展開
case TMPL_PUSH_CONST:
 機械語生成時に即値を挿入
HOLE(hole1, int_val);
*++sp = int_val;
 IP で分岐先を決定する
break;
 分岐命令にはテンプレート不要
}
}
10
プラットフォーム独立な中間表現

各ノード


バイトコード命令（あるいは式）に対応
 中間表現への変換は容易
属性
 テンプレートのどの部分を使って機械語を生成するか
 HOLE に挿入する即値の値
中間表現
抽象構文木
second
バイトコード
PLUS
third
NUMBER: 2
NUMBER: 3
PUSH 2
PUSH 3
中間表現
label: PLUS
label: NUMBER
holes: {hole1:=2}
label: NUMBER
holes: {hole1:=3}
label: TMPL_PUSH
holes: {hole1:=2}
label: TMPL_PUSH
holes: {hole1:=3}
ADD
label: TMPL_ADD
holes: NULL
11
中間表現への変換は容易

インタープリタの制御構造を流
用可能

appendCmpnt


BlockCmpntをリストの末尾に追加
addHoleInfo

Holeに埋め込む値を設定
中間表現
label: TMPL_PUSH_CONST
holes: {push_const_hole := 2}
label: TMPL_PUSH_CONST
holes: {push_const_hole := 3}
label: ADD
holes: NULL
中間表現
を作るコード
char *ip = code – 1;
for (;;) {
char* bcode = *++ip;
switch (bcode)
case ADD:
cmpnt =
appendCmpnt(cmpnt, ip
v_ADD);
break;
case PUSH_CONST:
cmpnt =
appendCmpnt(cmpnt, ip,
v_TMPL_PUSH_CONST);
addHoleInfo(cmpnt, ip,
v_push_const_hole,
*((int *)(++ip)) );
break;
}
12
}
フレームワークによるコード生成

入力：中間表現、出力：機械語


コンパイル済みテンプレートの逆アセンブル情報を利用する
機械語生成の流れ
１．中間表現で指定されたコンパイル済みテンプレートを、最後のjmp命令
やret命令を除きコピー
２. 相対アドレスを用いた部分をコードが移動した分だけずらす
３. 中間表現で指定された即値命令に指定された即値を埋め込む
４. バイトコードの分岐命令は機械語の分岐命令に変換
中間表現
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
…
…
13
バイトコードの分岐命令の処理


分岐先バイトコードのアドレスが入った中間表現を作る
機械語の分岐命令に変換

バイトコードのアドレスを機械語のアドレスへフレームワークが変換
バイトコード
unsigned char code[] = {
…, GOTO, -0x100, …};
中間表現
label: …
バイトコード番地: 0x0200
label: …
バイトコード番地: 0x0204
機械語
0x10000000
…
0x10000020
…
中略
label: NULL
バイトコード番地: 0x0300
type: jump
ジャンプオフセット: -0x0100
中略
0x10001000
jmp 0x10000000
14
中間表現での最適化


中間表現のノードの並べ替え
複数ノードを最適化された１ノードへ置換
 例定数の畳み込み
中間表現 (最適化前)
label: TMPL_PUSH_CONST
holes: {push_const_hole => 2}
中間表現 (最適化後)
label: TMPL_PUSH_CONST
holes: {push_const_hole => 3}
label: TMPL_PUSH_CONST
holes: {push_const_hole => 5}
label: ADD
holes: NULL
15
抽象構文木インタープリターの場合

抽象構文木を直接解釈するインタープリター

switch文がオーバーヘッド


バイトコードインタープリターと同様
eval 関数が再帰呼び出し
インタープリター
int eval(List* expr) {
switch (testElementType(expr)) {
/* ... */
case PLUS :
return eval(getSecond(expr))
+ eval(getThird(expr));
case NUMBER :
return getIntegerElement(expr);
/* ... */
}}
抽象構文木
PLUS
second
third
NUMBER: 2 NUMBER: 3
16
入れ子の関数呼び出しの中間表現

中間表現を木構造に

入れ子で呼ばれる関数を表すノードを
木構造の子ノードに
抽象構文木
PLUS
second
third
NUMBER: 2
中間表現
NUMBER: 3
label: PLUS
label: NUMBER
holes: {hole1 := 2}
label: NUMBER
holes: {hole1 := 3}
17
入れ子の関数呼び出しのテンプレート

引数なしのvoid関数がテンプレート


値の受け渡しはグローバル変数で
LABEL マクロ

テンプレートの内部に他のテンプレートを挿入可能
テンプレート
void code_PLUS() {
LABEL(PLUS_section);
LABEL(PLUS_label1);
sp--;
*sp = sp[1];
}
void code_NUMBER() {
int ret_val;
HOLE(hole1, ret_val);
*++sp = ret_val;
}
中間表現
PLUS
PLUS_label1
NUMBER 2
PLUS_label1
NUMBER 3
機械語
void code_PLUS() {
*++sp = 2;
*++sp = 3;
sp--;
*sp = sp[1];
}
18
フレームワークのマシン非依存性

JITコンパイラの作成者



マシンアーキテクチャを意識しない
中間表現はプラットフォーム独立
フレームワーク自体


マシンアーキテクチャ固有の実装
 コンパイル済みテンプレートの機械語の解析
 インラインアセンブリに展開されるマクロ
 即値命令に定数を埋め込む方法
 機械語の分岐命令
 相対アドレスの調整
gccが必要
 gccインラインアセンブリを使用
19
予備的な実験

ディスパッチにswitchを用いた抽象構文木
インタープリター
(+ x y)の実行結果
120
160
140
100
実行時間(JITなし) [nｓ]
120
80
100
60
80
60
40
40
20
20
0
0
O0
O1
O2
gcc最適化オプション
O3
実行時間(JITあり) [nｓ]
JITコンパイル時間 [μs]
Intel Xeon CPU 3.06GHz x 2
memory 2GB
linux 2.6.17
gcc 4.1.1
glibc 2.4
20
関連研究

Cコンパイラが生成した機械語を利用する研究

ErtlらのJITコンパイラの移植に関する研究 [Ertl 04]




命令ポインタを除去して高速化するところが本研究に類似
インタープリタを書き換えないため、バイトコードの即値命令を機
械語の即値命令に書き換えられない場合がある
本研究はフレームワークおよびそれが解釈する中間表現を提供
している
DyC [Grant 00]

伝統的なMultiflow Compilerをベースにしている


移植性に焦点が当てられていない
Tempo [Noel 98]


ランタイムコンパイラをフロントエンドからバックエンドまで提供
ネイティブコードの生成が自動化されているため、バイトコード命
令レベルの最適化を行えない
21
まとめ

JITコンパイラを作成するフレームワーク


高い移植性
 プラットフォーム独立なコードを書くだけ
そこそこの品質のコードを生成
 オーバーヘッドを除去




命令のフェッチ・デコード
オペランドのロード
実装が容易
 インタープリタの実装を流用可能
テンプレートが中間表現にセマンティクスを与える

置き換えで独自の最適化が可能
22
終わり

ご清聴ありがとうございました
23

Download Report