C言語を用いたマシン非依存な JITコンパイラ作成フレームワーク 栗田洋輔　千葉滋 東京工業大学

従来のJITコンパイラの開発と問題点 本格的なJITコンパイラ プラットフォーム依存の中間表現を作成し、それを機械語に変換 移植性の問題 マシンごとにプラットフォーム依存の中間表現を作成 実装の容易性の問題 高い開発スキルが必要 バイトコードから中間表現への変換 中間表現から機械語への変換 バイトコード 機械語 プラットフォーム依存の中間表現

本研究の目的 JIT コンパイラ作成を容易にするフレームワーク 移植性が高い 短いコンパイル時間でそこそこの品質のコードを生成 実装の容易性 実行速度 コンパイル時間 ネイティブコンパイラ △ × ◎ インタープリタ 従来のJITコンパイラ ○ 本フレームワークを用いて開発するJITコンパイラ

そこそこの最適化 本質的なオーバーヘッドを除去することで高速化を行う 本質的なオーバーヘッド 広い範囲のインタープリターに適用できる 汎用的な手法 本質的なオーバーヘッド バイトコードインタープリター 次の命令をフェッチしてデコードするコスト バイトコードのオペランドをメモリからロードするコスト 抽象構文木のインタープリター 抽象構文木を巡回してノードをデコードするコスト

命令をフェッチ・デコードする オーバーヘッド (1/2) 命令ポインタ(ip)のインクリメントと メモリからのフェッチ インタープリター トレース char *ip = code – 1; for (;;) { char* bcode = *++ip; switch (bcode) case PUSH_CONST: *++sp = (int)*++ip; break; case ADD: --sp; *sp += sp[1]; /* other cases …*/ } フェッチ デコード 本体 bcode = *++ip; PUSH_CONST 2 3 ADD バイトコード switch (bcode) ip *++sp = (int)*++ip; ip ip フェッチ デコード 本体 bcode = *++ip; ip switch (bcode) ip *++sp = (int)*++ip; フェッチ デコード 本体 bcode = *++ip; switch (bcode) --sp; *sp += sp[1];

命令をフェッチ・デコードする オーバーヘッド (2/2) バイトコードのデコード switchによる条件分岐で実装 インタープリター トレース char *ip = code – 1; for (;;) { char* bcode = *++ip; switch (bcode) case PUSH_CONST: *++sp = (int)*++ip; break; case ADD: --sp; *sp += sp[1]; /* other cases …*/ } フェッチ デコード 本体 bcode = *++ip; PUSH_CONST 2 3 ADD バイトコード switch (bcode) *++sp = (int)*++ip; フェッチ デコード 本体 bcode = *++ip; switch (bcode) *++sp = (int)*++ip; フェッチ デコード 本体 bcode = *++ip; switch (bcode) --sp; *sp += sp[1];

命令をフェッチ・デコードする オーバーヘッドの除去 高速化を達成 フェッチ・デコード部分を削除 本体部分のみを並べる 命令ポインタの指すアドレスが不正 フェッチ デコード 本体 bcode = *++ip; *++sp = (int)*++ip; bcode = *++ip; *++sp = (int)*++ip; switch (bcode) *++sp = (int)*++ip; フェッチ デコード 本体 switch (bcode) *++sp = (int)*++ip; --sp; *sp += sp[1]; フェッチ デコード 本体 switch (bcode) --sp; *sp += sp[1];

バイトコードのオペランドをメモリからロードするコストの削減 オペランドの値が既知の場合には不必要 フェッチ デコード 本体 bcode = *++ip; *++sp = (int)*++ip; bcode = *++ip; *++sp = (int)*++ip; switch (bcode) *++sp = (int)*++ip; *++sp = 2； フェッチ デコード 本体 *++sp = 3； switch (bcode) *++sp = (int)*++ip; --sp; *sp += sp[1]; --sp; *sp += sp[1]; フェッチ デコード 本体 switch (bcode) --sp; *sp += sp[1];

JIT コンパイラ・フレームワーク の提案 プラットフォーム独立な中間表現 テンプレート 中間表現から機械語への変換はフレームワークが担当 高い移植性を実現（フレームワーク自体の移植は必要） テンプレート 中間表現の各ノードに対応する機械語のひな形 中間表現のセマンティクスを与える JITコンパイラの 作成者が実装 テンプレート バイトコード 機械語 プラットフォーム独立な中間表現

テンプレートの書き方 インタープリターの主ループそのもの 記述は容易 一部の命令は、テンプレート用に書き換えが必要 命令ポインタ (IP) を使っている場合 生成される機械語に IP は含められない IP でオペランド（即値）を取得する HOLEマクロを利用 gccインラインアセンブリに展開 機械語生成時に即値を挿入 IP で分岐先を決定する 分岐命令にはテンプレート不要 テンプレート char *ip = code – 1; for (;;) { char* bcode = *++ip; switch (bcode) case ADD: --sp; *sp += sp[1]; break; case PUSH_CONST: *++sp = (int)*++ip; case TMPL_PUSH_CONST: HOLE(hole1, int_val); *++sp = int_val; } case TMPL_PUSH_CONST: HOLE(hole1, int_val); *++sp = int_val; break;

プラットフォーム独立な中間表現 各ノード バイトコード命令（あるいは式）に対応 属性 中間表現への変換は容易 テンプレートのどの部分を使って機械語を生成するか HOLE に挿入する即値の値 中間表現 抽象構文木 バイトコード PLUS label: TMPL_PUSH holes: {hole1:=2} second third PUSH 2 NUMBER: 2 NUMBER: 3 PUSH 3 label: TMPL_PUSH holes: {hole1:=3} ADD 中間表現 label: PLUS label: TMPL_ADD holes: NULL label: NUMBER holes: {hole1:=2} label: NUMBER holes: {hole1:=3}

中間表現への変換は容易 インタープリタの制御構造を流用可能 appendCmpnt addHoleInfo を作るコード インタープリタの制御構造を流用可能 appendCmpnt BlockCmpntをリストの末尾に追加 addHoleInfo Holeに埋め込む値を設定 char *ip = code – 1; for (;;) { char* bcode = *++ip; switch (bcode) case ADD: cmpnt = appendCmpnt(cmpnt, ip v_ADD); break; case PUSH_CONST: appendCmpnt(cmpnt, ip, v_TMPL_PUSH_CONST); addHoleInfo(cmpnt, ip, v_push_const_hole, *((int *)(++ip)) ); } 中間表現 label: TMPL_PUSH_CONST holes: {push_const_hole := 2} holes: {push_const_hole := 3} label: ADD holes: NULL

フレームワークによるコード生成 入力：中間表現、出力：機械語 機械語生成の流れ コンパイル済みテンプレートの逆アセンブル情報を利用する １．中間表現で指定されたコンパイル済みテンプレートを、最後のjmp命令やret命令を除きコピー ２. 相対アドレスを用いた部分をコードが移動した分だけずらす ３. 中間表現で指定された即値命令に指定された即値を埋め込む ４. バイトコードの分岐命令は機械語の分岐命令に変換 中間表現 コンパイル済みテンプレート 機械語 label: TMPL_PUSH holes: {hole1 := 2} 参照 コピー TMPL_PUSH movl $1234, %eax … movl $2, %eax … hole1: movl $1234, %eax … label: TMPL_PUSH holes: {hole1 := 3} movl $1234, %eax … movl $3, %eax … … TMPL_ADD label: TMPL_ADD holes: NULL …

バイトコードの分岐命令の処理 分岐先バイトコードのアドレスが入った中間表現を作る 機械語の分岐命令に変換 バイトコードのアドレスを機械語のアドレスへフレームワークが変換 バイトコード unsigned char code[] = { …, GOTO, -0x100, …}; 中間表現 label: … バイトコード番地: 0x0200 機械語 … 0x10000000 label: … バイトコード番地: 0x0204 … 0x10000020 中略 中略 label: NULL バイトコード番地: 0x0300 type: jump ジャンプオフセット: -0x0100 jmp 0x10000000 0x10001000

中間表現での最適化 中間表現のノードの並べ替え 複数ノードを最適化された１ノードへ置換 例 定数の畳み込み 中間表現 (最適化前) 例　定数の畳み込み 中間表現 (最適化前) label: TMPL_PUSH_CONST holes: {push_const_hole => 2} holes: {push_const_hole => 3} label: ADD holes: NULL 中間表現 (最適化後) label: TMPL_PUSH_CONST holes: {push_const_hole => 5} ・中間表現の範囲内で任意の最適化アルゴリズムを組み込み可能 ・ユーザーが望むバイトコードの最適化機能をJITコンパイラに追加できる 　・中間表現のオープンな仕様 ・やり方 　・ 　。。。 ・例：定数の畳み込み

抽象構文木インタープリターの場合 抽象構文木を直接解釈するインタープリター switch文がオーバーヘッド eval 関数が再帰呼び出し バイトコードインタープリターと同様 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

入れ子の関数呼び出しの中間表現 中間表現を木構造に 入れ子で呼ばれる関数を表すノードを 木構造の子ノードに 抽象構文木 PLUS second third NUMBER: 2 NUMBER: 3 中間表現 label: PLUS label: NUMBER holes: {hole1 := 2} label: NUMBER holes: {hole1 := 3}

入れ子の関数呼び出しのテンプレート 引数なしのvoid関数がテンプレート LABEL マクロ 値の受け渡しはグローバル変数で テンプレートの内部に他のテンプレートを挿入可能 中間表現 テンプレート PLUS PLUS_label1 PLUS_label1 void code_PLUS() { LABEL(PLUS_section); sp--; *sp = sp[1]; } LABEL(PLUS_label1); NUMBER 2 NUMBER 3 機械語 void code_PLUS() { void code_NUMBER() { int ret_val; HOLE(hole1, ret_val); *++sp = ret_val; } *++sp = 2; *++sp = 3; sp--; *sp = sp[1]; }

フレームワークのマシン非依存性 JITコンパイラの作成者 フレームワーク自体 マシンアーキテクチャを意識しない 中間表現はプラットフォーム独立 フレームワーク自体 マシンアーキテクチャ固有の実装 コンパイル済みテンプレートの機械語の解析 インラインアセンブリに展開されるマクロ 即値命令に定数を埋め込む方法 機械語の分岐命令 相対アドレスの調整 gccが必要 gccインラインアセンブリを使用

予備的な実験 ディスパッチにswitchを用いた抽象構文木 インタープリター 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] 伝統的なMultiflow Compilerをベースにしている 移植性に焦点が当てられていない Tempo [Noel 98] ランタイムコンパイラをフロントエンドからバックエンドまで提供 ネイティブコードの生成が自動化されているため、バイトコード命令レベルの最適化を行えない

まとめ JITコンパイラを作成するフレームワーク テンプレートが中間表現にセマンティクスを与える 高い移植性 そこそこの品質のコードを生成 プラットフォーム独立なコードを書くだけ そこそこの品質のコードを生成 オーバーヘッドを除去 命令のフェッチ・デコード オペランドのロード 実装が容易 インタープリタの実装を流用可能 テンプレートが中間表現にセマンティクスを与える 置き換えで独自の最適化が可能

終わり ご清聴ありがとうございました