アルゴリズムとデータ構造1

コンパイラ
2011年11月24日
酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html
1
動的コンパイラ
コンパイル処理という負荷が実行時に発生


コンパイラがメモリを消費する（空間的負荷）


一時記憶・二次記憶が貴重な環境では大問題
動的コンパイルに費やす時間（時間的負荷）

起動時に集中して動的コンパイル


コンパイルが終わるまで、アプリケーションが応答しない
インタプリタ実行の結果により、動的コンパイル

初期化ルーチンは、たいてい１回しか実行されないので、コンパイル無用
実行プロファイルに基づく最適化コンパイルができる



2
インタプリタ実行中にプロファイルを集める
条件分岐の頻度を反映したコードを出力する
on stack replacement
実行頻度が高い、とは？


メソッドの…




呼んで処理して帰ってくるメソッドならば対応しやすい
メソッドを呼んだ回数を数えて動的コンパイルするかどうか決める
メソッド呼び出し時にインタプリタ実行か Native実行かを選択可能
ブロックの…


たとえば、無限ループを含むメソッドは呼んだらそれっきり
呼んだっきりでは、実行の途中で切り替えるしか方法がない
途中で Native実行に切り替えるには？



3
動的コンパイラでコンパイルする
on stack replacement により動作を引き継ぐ
4
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
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{
public void execute(){
…
}
}
on stack replacement の手順
インタプリタは実行頻度が高いメソッドを見つけコンパイル


ループ回数が多いループを含むメソッドも実行頻度が高いとする
実行を引き継ぐ


変数などの格納位置を修正する




レジスタ割り当ての変化
変数のスタック-レジスタ間の移動
レジスタの退避・復帰
実行中のバイトコードに対応するNativeコードに分岐

コンパイル時に対応表を用意する

5
制御フロー解析と最適化の結果から生成すればよいだけ
wait_and_go()のバイトコード表現
1. Method void wait_and_go()
2.
0 aload_0
3.
1 invokevirtual
#2 <Method void wait()>
4.
4 aload_0
5.
5 getfield #3 <Field Executable _job>
6.
8 invokevirtual (args 1) #4 <VirtualMethod void execute()>
7.
13 goto 0
6
wait_and_go()のNativeコード例
1.
addil
L'0x2000, %sp, %r1
2.
stw
%r0, 0(%r1)
3.
copy
%sp, %fp
4.
ldo
0xC0(%sp), %sp
5.
stw
%fp, -0x4(%sp)
6.
stw
%rp, -0x8(%sp)
7.
stw
r3, 0(%fp)
8.
copy
%r26, %r3
9.
ENTER_SYNC(%r3, 0x4(%fp))
10. Loop:
11.
call
WAIT
12.
copy
%r3, %r26
13.
ldw,o
8(%r3), %r26
14.
call
EXECUTE
15.
ldw
0(%r26), %r1
16.
b
Loop
17.
nop
18.
…
7
;
;
;
;
;
;
;
;
;
%r1 <- %sp(スタックポインタ) + 0x2000
%sp + 0x2000 が参照可能か検査(stack banging)
%fp(フレームポインタ) <- %sp
%sp += スタックフレームサイズ
フレームの開放に備え%fp (=旧%sp)を退避
%rp(戻り番地)をフレームに退避
呼び出し先保存レジスタ(%r3)の退避
%r3 <- this (%r26には0番引数thisが入っている)
[マクロ]%r3(this)の排他制御権を確保
;
;
;
;
;
;
;
wait()の呼び出し
[遅延スロット] %r26(0番引数) <- this
%r26(0番引数) <- this._job
execute()の呼出し
[遅延スロット] 暗黙のnull検査, _job==null?
ラベルLoopにジャンプ
[遅延スロット] 何もしない（することがない）
インタプリタ実行時
レジスタ群
実行時スタック
%sp→
%r32
…
%r6
オペランドスタックポインタ
%r5 確保済み排他制御権スタックポインタ
%r4
バイトコードプログラムカウンタ
%r3
局所変数領域への参照
…
%fp→
%r0
旧%sp
戻り番地
thisの排他制御権
%r6退避値
%r5退避値
%r4退避値
%r3退避値
旧々%sp
戻り番地
this
wait_and_go()
のインタプリタ用
スタックフレーム
確保済み排他制御権スタック
呼び出し先保存レジスタ退避領域
局所変数格納領域
…
on stack replacement
脱最適化
%sp→
%r32
…
%r6
%r5
%r4
%r3
%r6退避値
%r5退避値
%r4退避値
this
…
8
確保済み排他制御権格納領域
呼び出し先保存レジスタ退避領域
局所変数格納領域
…
%r0
%fp→
旧%sp
戻り番地
thisの排他制御権
%r3退避値
旧々%sp
戻り番地
this
wait_and_go()の
コンパイル済みコード
用スタックフレーム
コンパイル済みコード実行時
on stack replacement と脱最適化
動的文脈を利用した最適化
「call EXECUTE」のところは直接呼出し


本来は（メモリを介した）間接呼び出しである


実行中に矛盾が生じた場合、脱最適化を行う


「getfield #3 <Field Executable _job>」に対応
_job フィールドが別のインスタンスを指す場合に矛盾を生じる
動的文脈を利用して、脱仮想化という最適化をしている

ループ内では_job フィールドが不変であると仮定している


9
この仮定が崩れる場合は、本来のバイトコード実行に戻す、としている
本来では、オブジェクト変数からインスタンスの参照、
インスタンスから該当メソッドのエントリーポイントの獲得および分岐、
という一連の処理を、直接分岐命令に置き換えている
Javaの仮想呼出しの実装
1.
2.
3.
1.
2.
3.
4.
実行時の型、つまりクラスを表すデータ構造を取り出す
該当のメソッドのエントリーポイントをレジスタに代入
レジスタを介した間接ジャンプ（遅延分岐）
ldw 4(%r26), %r2
ldw METHOD_ID(%r2), %r2
bve,l %r2
nop
PC:
;
;
;
;
X+0
X+1
Y+0
Y+１
IF
ID
EX
WB
IF
ID
EX
WB
IF
ID
EX
分岐命令がEXステージに入る前は
分岐前PCを基準にInstruction Fetch
10
%r2 <- インスタンス (%r26) のクラスを表すデータ構造
%r2 <- 呼出し対象のメソッドの番地
%r2 が指示する番地にジャンプ(間接ジャンプ)
[遅延スロット] 何もしない(することがない)
Y+２
遅延分岐命令
遅延スロットの命令
WB
分岐先の命令
Executableクラス
のインスタンス
ヘッダ
クラス
フィールド_job
Executableクラス
を表すデータ構造
クラス名
親クラス
Executable
java.lang.Object
…
ディスパッチ表
execute()
のメソッド番号
…
Executableクラスが
定義するexecute()
のオブジェクトコード
Executable２クラス
のインスタンス
ヘッダ
クラス
フィールド_job
固定長
部分
Executable２クラス
を表すデータ構造
クラス名
親クラス
Executable2
Executable
…
ディスパッチ表
固定長
部分
execute()
のメソッド番号
…
Executable２クラスが
定義するexecute()
のオブジェクトコード
11
動的文脈と静的文脈

静的文脈
プログラムに書いてあるとおりに解釈した文脈


脱仮想化のために、変数の到達定義連鎖を利用する
動的文脈
静的文脈の他、実行時の情報も加味して解釈した文脈




12
ユーザーからの入力
コマンドライン引数
実行環境(OS・CPU)
たとえば、シングルトンパターン
if(!initialized){初期化; initialized = true;}
静的文脈を利用して脱仮想化できる
仮想呼出し

2行目のe.execute()を参照するとき、そこに到達する
定義は1行目にあり、それが唯一である。
1. Executable e = new Executable();
2. e.execute();

本来はインスタンスから実行時クラスの情報を取り出し、
そこから該当のメソッドを選択し間接的に呼ぶ。
しかし、到達する定義から明らかなように、実行時クラス
はExecutableと静的に読み取れることから、２行目を
直接Executableのexecute()を呼ぶようにする。
13
脱最適化

一方で、152ページのリスト10.1の_jobでは、静的な
脱仮想化はできない。


静的コンパイルの結果、_jobを参照する行へ到達する
定義が唯一ではないときには、静的に脱仮想化できない。
特に、volatileで広いスコープを持つ場合は、参照するごと
に値が変わっている、と推定するしかない。
ただし、実行時に値が変わらないようであれば脱仮想化
してもいい、という意味でもある。そこで、


動的文脈を監視し、仮定が成立しているか調べる機能
仮定が不成立のときに、最適化を解除する機能（脱最適化）
を持たせれば、_jobに関するような文脈でも、動的な
最適化ができる。
14
最適化の解除

動的文脈の監視


Nativeコードが使えなくなる条件を動的コンパイラが付与し、
実行時にその条件を監視させる。
最適化の解除

条件が不成立となった場合


Nativeコードを上書きして再利用する
新しくコンパイルしなおすか、バイトコードのインタプリタ実行に戻る



脱最適化するスレッド以外のスレッドを停止
全てのスレッドのスタックフレームを検査
矛盾のある破棄対象コードへ戻ることがないように戻り番地を書き換える



15
書き換え先は脱最適化ハンドラ
スレッドの実行を再開
（たとえば）脱最適化ハンドラが呼ばれるたび、インタプリタ実行に戻る
Class::newInstance()
のスタックフレーム
Executable::execute()
のスタックフレーム
Executable10::wait_and_go()
のスタックフレーム
呼出し元の%sp
戻り番地
呼出し元の%sp
戻り番地
呼出し元の%sp
戻り番地
wait_and_go:
addil
Loop:
call
copy
ldw,o
call
ldw
b
nop
L'0x2000, %sp, %sp, %ri
WAIT
%r3, %r26
8(%r3), %r26
EXECUTE
0(%r26), %r1
Loop
脱最適化前
Class::newInstance()
のスタックフレーム
Executable::execute()
のスタックフレーム
Executable10::wait_and_go()
のスタックフレーム
16
呼出し元の%sp
戻り番地
呼出し元の%sp
戻り番地
呼出し元の%sp
戻り番地
wait_and_go:
addil
Loop:
call
copy
ldw,o
call
ldw
b
nop
L'0x2000, %sp, %sp, %ri
WAIT
%r3, %r26
8(%r3), %r26
EXECUTE
0(%r26), %r1
Loop
戻り番地退避先
脱最適化ハンドラ：
…
脱最適化準備段階
Q末試験




日時
２０１１年１１月２８日２時限目
場所
A１０６（いつもの講義室）
時間
10時40分から12時10分までの１時間30分
開始後30分過ぎたら退室可
開始後30分までは入室可（遅刻限度）
持ち込んでいいもの
紙の資料、紙の書籍（紙媒体であればいい）
17

Download Report