束縛時解析 - 米澤研究室

実行時バイトコード特化の
オブジェクト指向言語への拡張
中間発表
アフェルトレナルド – 米澤研究室
オブジェクト特化

オブジェクト指向プログラミングの特質:
– 小さいメソッド
– 入れ子オブジェクト

– オブジェクト生成
プログラム特化による最適化（部分評価）:
– 定数伝播
– メソッドインライニング
– 定数式評価
– ループアンローリング
 オブジェクト指向プログラムの特化は効果的
本研究の目的

出発点：
実行時バイトコード特化 [増原０１]
– プログラムの実行中に特化する
– JAVAバイトコードの小さい部分集合がターゲット
– 配列とオブジェクトのサポートはない

目的：
– Imperativeな操作と
– オブジェクト指向
のサポートを加える
本発表の概要
1) 特化エンジンの概要
2) 本研究における:
–
–
–
–
部分的に静的な構造
エイリアシング
副作用と剰余コードの再利用
オブジェクトの動的な割り当て
3) 結論
特化エンジンの基本概念：
１．束縛時解析

プログラムの言語構成要素を
– 静的な構成要素と
– 動的な構成要素
に分類する
元のプログラム
int
0
1
2
3
add (x, y)
iload_1
iload_2
iadd
ireturn
束縛時分割
x = S
y = D
束縛時解析
注釈したプログラム
int
0
1
2
3
add (x, y)
iload_1
iload_2
iadd
ireturn
特化エンジンの基本概念：
２．特化

注釈したプログラムに沿って
– 静的な構成要素を評価して、
– 動的な構成要素をそのまま剰余コードに入れる
静的な引数の値
注釈したプログラム
int
0
1
2
3
add (x, y)
iload_1
iload_2
iadd
ireturn
x = 3
y = ?
特化
剰余コード
int
0
1
2
3
add (y)
const_3
iload_1
iadd
ireturn
特化エンジンの基本概念：
まとめ
束縛時分割
元の
プログラム
型システムを用
いた束縛時解析
静的な引数の値
注釈した
プログラム
特化
剰余コード
BCS [増原０１]
部分的に静的な構造と
別名

部分的に静的な構造:
this
operands = D

Stack = S
items = D
別名：エイリアス情報が無いと
– 不安全,又は
– 保守的な
特化しか出来ない
sp = S
副作用と剰余コード再生利用
(1/2)

実行時に二つのデータスペースがある：
– ヒープと静的なメモリ
– 特化の記憶

安全性の問題:
一部の静的な副作用は剰余コードに書き込むべき

性能の問題:
全部の静的な副作用を書き込めば、性能が悪化
最適な剰余コードを生成したい
副作用を出来る限り遅らせ、まとめて行う
副作用と剰余コード再生利用
(2/2)
this
operands = S
Stack = S
items = D
sp = 4
BCS
void add (Stack st) {
st.push (operands[0]);
st.push (operands[1]);
int t0 = st.pop ();
int t1 = st.pop ();
st.push (t0 + t1);
}
void add (Stack st) {
st.items[4] = operands[0];
st.items[5] = operands[1];
int t0 = st.items[5];
int t1 = st.items[4];
st.items[4] = t0 + t1;
st.sp = 5;
}
オブジェクトの動的な割り当て
(1/2)

JAVAの特質:
– 動的割り当て
– 内部変数エスケープ

剰余コード中のオブジェクトの割り当てを避ける:
– 特化記憶の再利用
– スタック割り当て

束縛時解析で伝統的な
– useと
– エスケープ
解析を利用
オブジェクトの動的な割り当て
(2/2)
stat = S
dyn = D
BCS
int[] function
(int stat, int dyn) {
int[] array = new int[3];
Integer cst = new Integer (11);
for (int i = 0; i < 3; i++) {
array[i] = cst.add (stat);
cst.value = dyn;
}
return array;
}
int[] function’ (int dyn) {
Integer cst = getRef (0);
int[] array = getRef (1);
cst.value = dyn;
array[1] = cst.value + stat;
cst.value = dyn;
array[2] = cst.value + stat;
cst.value = dyn;
return array;
}
関連研究

Imperativeな言語:
– “The taming of C pointers” [Andersen93]
– “Use, flow, context, and return” sensitivity
[Hornof97]

メソッドの動的結合を削除:
– “C++ customization” [Lea91]
– バーチャルメソッドの特化 [Dean94]

オブジェクト特化:
– 抽象解釈 [Steensgaard92]
– 宣言的な特化 [Volanschi97]
結論

実行時オブジェクトバイトコード特化:
– パフォーマンスとモジュラープログラミングを保存する
– ソース言語とマシンに依存しない
– 普通の翻訳とJITコンパイラーの間に適する

現状：
– 束縛時解析の拡張（オブジェクトの命令）

今後の課題:
– コンテキストsensitivity
– エイリアスと副作用と動的な割り当て

応用:
– 自分で特化出来るモバイルコード

Download Report