コンパイラ 2011年11月24日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html.

Presentation on theme: "コンパイラ 2011年11月24日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html."— Presentation transcript:

1 コンパイラ 2011年11月24日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)

2 動的コンパイラ コンパイル処理という負荷が実行時に発生 実行プロファイルに基づく最適化コンパイルができる
コンパイラがメモリを消費する（空間的負荷） 一時記憶・二次記憶が貴重な環境では大問題 動的コンパイルに費やす時間（時間的負荷） 起動時に集中して動的コンパイル コンパイルが終わるまで、アプリケーションが応答しない インタプリタ実行の結果により、動的コンパイル 初期化ルーチンは、たいてい１回しか実行されないので、コンパイル無用 実行プロファイルに基づく最適化コンパイルができる インタプリタ実行中にプロファイルを集める 条件分岐の頻度を反映したコードを出力する

3 on stack replacement 実行頻度が高い、とは？ 途中で Native実行に切り替えるには？ メソッドの… ブロックの…
呼んで処理して帰ってくるメソッドならば対応しやすい メソッドを呼んだ回数を数えて動的コンパイルするかどうか決める メソッド呼び出し時にインタプリタ実行か Native実行かを選択可能 ブロックの… たとえば、無限ループを含むメソッドは呼んだらそれっきり 呼んだっきりでは、実行の途中で切り替えるしか方法がない 途中で Native実行に切り替えるには？ 動的コンパイラでコンパイルする on stack replacement により動作を引き継ぐ

4 public class Example10 { public volatile Executable _job; synchronized void wait_and_go() throws InterruptedException { while(true){ this.wait(); this._job.execute(); } … public class Executable{ public static Executable escape_path; public void execute(){ if(unluckey()){ try{ Class klass = System.loadClass("Executable2"); escape_path = (Executable)(klass.newInstance()); }catch(Throwable t){} public class Executable2 extends Executable{

5 on stack replacement の手順
インタプリタは実行頻度が高いメソッドを見つけコンパイル ループ回数が多いループを含むメソッドも実行頻度が高いとする 実行を引き継ぐ 変数などの格納位置を修正する レジスタ割り当ての変化 変数のスタック-レジスタ間の移動 レジスタの退避・復帰 実行中のバイトコードに対応するNativeコードに分岐 コンパイル時に対応表を用意する 制御フロー解析と最適化の結果から生成すればよいだけ

6 wait_and_go()のバイトコード表現
Method void wait_and_go() 0 aload_0 1 invokevirtual #2 <Method void wait()> 4 aload_0 5 getfield #3 <Field Executable _job> 8 invokevirtual (args 1) #4 <VirtualMethod void execute()> 13 goto 0

7 wait_and_go()のNativeコード例
addil L'0x2000, %sp, %r1 ; %r1 <- %sp(スタックポインタ) + 0x2000 stw %r0, 0(%r1) ; %sp + 0x2000 が参照可能か検査(stack banging) copy %sp, %fp ; %fp(フレームポインタ) <- %sp ldo 0xC0(%sp), %sp ; %sp += スタックフレームサイズ stw %fp, -0x4(%sp) ; フレームの開放に備え%fp (=旧%sp)を退避 stw %rp, -0x8(%sp) ; %rp(戻り番地)をフレームに退避 stw r3, 0(%fp) ; 呼び出し先保存レジスタ(%r3)の退避 copy %r26, %r3 ; %r3 <- this (%r26には0番引数thisが入っている) ENTER_SYNC(%r3, 0x4(%fp)) ; [マクロ]%r3(this)の排他制御権を確保 Loop: call WAIT ; wait()の呼び出し copy %r3, %r26 ; [遅延スロット] %r26(0番引数) <- this ldw,o 8(%r3), %r26 ; %r26(0番引数) <- this._job call EXECUTE ; execute()の呼出し ldw 0(%r26), %r1 ; [遅延スロット] 暗黙のnull検査, _job==null? b Loop ; ラベルLoopにジャンプ nop ; [遅延スロット] 何もしない（することがない） …

8 on stack replacement と脱最適化
インタプリタ実行時 実行時スタック wait_and_go() のインタプリタ用 スタックフレーム レジスタ群 %sp→ %fp→ thisの排他制御権 %r6退避値 %r5退避値 %r4退避値 %r3退避値 旧々%sp 戻り番地 this 旧%sp … オペランドスタックポインタ 確保済み排他制御権スタックポインタ … %r32 %r6 %r5 %r4 %r3 %r0 局所変数領域への参照 バイトコードプログラムカウンタ 確保済み排他制御権スタック 呼び出し先保存レジスタ退避領域 局所変数格納領域 on stack replacement 脱最適化 wait_and_go()の コンパイル済みコード 用スタックフレーム %sp→ %fp→ thisの排他制御権 %r3退避値 旧々%sp 戻り番地 this 旧%sp … %r6退避値 %r5退避値 … %r32 %r6 %r5 %r4 %r3 %r0 this %r4退避値 確保済み排他制御権格納領域 呼び出し先保存レジスタ退避領域 on stack replacement と脱最適化 局所変数格納領域 コンパイル済みコード実行時

9 動的文脈を利用した最適化 「call EXECUTE」のところは直接呼出し 本来は（メモリを介した）間接呼び出しである
「getfield #3 <Field Executable _job>」に対応 実行中に矛盾が生じた場合、脱最適化を行う _job フィールドが別のインスタンスを指す場合に矛盾を生じる 動的文脈を利用して、脱仮想化という最適化をしている ループ内では_job フィールドが不変であると仮定している この仮定が崩れる場合は、本来のバイトコード実行に戻す、としている 本来では、オブジェクト変数からインスタンスの参照、 インスタンスから該当メソッドのエントリーポイントの獲得および分岐、 という一連の処理を、直接分岐命令に置き換えている

10 Javaの仮想呼出しの実装 実行時の型、つまりクラスを表すデータ構造を取り出す 該当のメソッドのエントリーポイントをレジスタに代入
レジスタを介した間接ジャンプ（遅延分岐） ldw 4(%r26), %r2 ; %r2 <- インスタンス (%r26) のクラスを表すデータ構造 ldw METHOD_ID(%r2), %r2 ; %r2 <- 呼出し対象のメソッドの番地 bve,l %r2 ; %r2 が指示する番地にジャンプ(間接ジャンプ) nop ; [遅延スロット] 何もしない(することがない) PC: X+0 X+1 Y+0 Y+１ Y+２ IF ID EX WB 遅延分岐命令 IF ID EX WB 遅延スロットの命令 IF ID EX WB 分岐先の命令 分岐命令がEXステージに入る前は 分岐前PCを基準にInstruction Fetch

11 ヘッダ クラス ヘッダ クラス フィールド_job Executableクラスが 定義するexecute() のオブジェクトコード …
のインスタンス ヘッダ クラス Executableクラス を表すデータ構造 フィールド_job Executableクラスが 定義するexecute() のオブジェクトコード … java.lang.Object Executable 固定長 部分 execute() のメソッド番号 ディスパッチ表 親クラス クラス名 Executable２クラス のインスタンス ヘッダ クラス Executable２クラス を表すデータ構造 フィールド_job Executable２クラスが 定義するexecute() のオブジェクトコード … Executable Executable2 固定長 部分 execute() のメソッド番号 ディスパッチ表 親クラス クラス名

12 動的文脈と静的文脈 静的文脈 プログラムに書いてあるとおりに解釈した文脈 動的文脈 静的文脈の他、実行時の情報も加味して解釈した文脈
静的文脈 プログラムに書いてあるとおりに解釈した文脈 脱仮想化のために、変数の到達定義連鎖を利用する 動的文脈 静的文脈の他、実行時の情報も加味して解釈した文脈 ユーザーからの入力 コマンドライン引数 実行環境(OS・CPU) たとえば、シングルトンパターン if(!initialized){初期化; initialized = true;}

13 静的文脈を利用して脱仮想化できる 仮想呼出し
2行目のe.execute()を参照するとき、そこに到達する 定義は1行目にあり、それが唯一である。 本来はインスタンスから実行時クラスの情報を取り出し、 そこから該当のメソッドを選択し間接的に呼ぶ。 しかし、到達する定義から明らかなように、実行時クラス はExecutableと静的に読み取れることから、２行目を 直接Executableのexecute()を呼ぶようにする。 Executable e = new Executable(); e.execute();

14 脱最適化 一方で、152ページのリスト10.1の_jobでは、静的な 脱仮想化はできない。
静的コンパイルの結果、_jobを参照する行へ到達する 定義が唯一ではないときには、静的に脱仮想化できない。 特に、volatileで広いスコープを持つ場合は、参照するごと に値が変わっている、と推定するしかない。 ただし、実行時に値が変わらないようであれば脱仮想化 してもいい、という意味でもある。そこで、 動的文脈を監視し、仮定が成立しているか調べる機能 仮定が不成立のときに、最適化を解除する機能（脱最適化） 　 を持たせれば、_jobに関するような文脈でも、動的な 最適化ができる。

15 最適化の解除 動的文脈の監視 最適化の解除 Nativeコードが使えなくなる条件を動的コンパイラが付与し、 実行時にその条件を監視させる。
条件が不成立となった場合 Nativeコードを上書きして再利用する 新しくコンパイルしなおすか、バイトコードのインタプリタ実行に戻る 脱最適化するスレッド以外のスレッドを停止 全てのスレッドのスタックフレームを検査 矛盾のある破棄対象コードへ戻ることがないように戻り番地を書き換える 書き換え先は脱最適化ハンドラ スレッドの実行を再開 （たとえば）脱最適化ハンドラが呼ばれるたび、インタプリタ実行に戻る

16 脱最適化前 脱最適化準備段階 戻り番地 呼出し元の%sp Class::newInstance() のスタックフレーム
wait_and_go: addil L'0x2000, %sp, %sp, %ri Loop: call WAIT copy %r3, %r26 ldw,o 8(%r3), %r26 call EXECUTE ldw 0(%r26), %r1 b Loop nop Class::newInstance() のスタックフレーム Executable::execute() のスタックフレーム Executable10::wait_and_go() のスタックフレーム 脱最適化前 wait_and_go: addil L'0x2000, %sp, %sp, %ri Loop: call WAIT copy %r3, %r26 ldw,o 8(%r3), %r26 call EXECUTE ldw 0(%r26), %r1 b Loop nop 戻り番地 呼出し元の%sp Class::newInstance() のスタックフレーム Executable::execute() のスタックフレーム Executable10::wait_and_go() のスタックフレーム 戻り番地退避先 脱最適化ハンドラ： … 脱最適化準備段階

17 Q末試験 日時 ２０１１年１１月２８日２時限目 場所 A１０６（いつもの講義室）
日時 ２０１１年１１月２８日２時限目 場所 A１０６（いつもの講義室） 時間 10時40分から12時10分までの１時間30分 開始後30分過ぎたら退室可 開始後30分までは入室可（遅刻限度） 持ち込んでいいもの 紙の資料、紙の書籍　（紙媒体であればいい）