2001年度中間発表会

バイトコード間の動的依存情報を
抽出するJavaバーチャルマシン
井上研究室
誉田謙二
プログラムスライス
プログラム中のある文sのある変数v （スライス
基準）の値に影響を与えうる文の集合
1:
2:
3:
4:
5:
6:
a = 5;
b = a + a;
if (b > 0) {
c = a;
}
d = b;
スライス基準（6, b）に
対するスライス
1:
2:
3:
4:
5:
6:
a = 5;
b = a + a;
if (b > 0) {
c = a;
}
d = b;
デバッグ対象が限定され、フォールト位置特定
を効率よく行うことができる
2002/02/19
2001年度修士論文発表会
1
スライスの計算過程
1.依存関係解析


データ依存関係
制御依存関係
2.プログラム依存グラフ（PDG）構築


節点：各プログラム文
有向辺：文間の依存関係
3.グラフ探索

データ依存関係
10: a = 1;
11: c = 4;
12: b = a;
a
制御依存関係
20: if (a < 1) {
21:
b = a;
22: }
プログラム依存グラフ
（PDG）
スライス基準に対応する節点から
有向辺を逆向きに探索
2002/02/19
2001年度修士論文発表会
2
静的・動的・DCスライス
静的スライス

ソースコードに存在する全経路に対し、依存関係解析を行う
計算されるスライスの精度低下
動的スライス

特定の実行系列に対し、依存関係解析を行う
実行系列の保存に伴う解析コストの増大
DCスライス


特定の経路に対し、動的にデータ依存関係解析を行う
静的に制御依存関係解析を行い、実行系列は保存しない
低コストでかつ精度の高いスライス計算が可能
2002/02/19
2001年度修士論文発表会
3
動的データ依存関係解析
一時記憶：キャッシュ


各変数と1対1対応するように用意する
各データを最後に定義した命令を保持する
アルゴリズム

変数が定義されたとき
 定義した文をキャッシュに保存

10: a = 1;
11: c = 4;
12: b = a;
変数が参照されたとき
 最後に定義した文をキャッシュから取得
 取得した文と実行中の文との間に
発生するデータ依存関係を抽出
2002/02/19
2001年度修士論文発表会
a
キャッシュ
a
b
c
10
-
11
（文12実行時）
4
スライス手法の比較
制御依存関係
データ依存関係
PDG節点
静的スライス
静的
DCスライス
静的
動的スライス
動的
静的
プログラム文
動的
プログラム文
動的
実行時点
スライスサイズ（精度）: 静的  DC  動的
依存関係解析コスト: 動的 ≫ DC > 静的†
Y.Ashida, F.Ohata and K.Inoue: “Slicing Methods Using Static and Dynamic Information”,
Proceedings of the 6th Asia Pacific Software Engineering Conference , pp.344-350,
Takamatsu, Japan, December (1999).
†
2002/02/19
2001年度修士論文発表会
5
研究目的
オブジェクト指向言語 Java


近年のソフトウェア開発環境で多く利用される
多くの実行時決定要素の存在
配列の添字・オブジェクトへの参照・動的束縛・
例外処理・並列処理
「Javaプログラムに対するDCスライスの適用」
2002/02/19
2001年度修士論文発表会
6
既存の手法とその問題点
ソースコード埋め込みによるDCスライス計算†

解析命令を埋め込んだソースコードを
コンパイル・実行し、動的情報を持つ
PDGを構築
問題点


構文制約による解析精度の低下
クラスファイルしか存在しないクラスを
介した依存関係解析の実現が困難
1 : a = 10;
2 : b = a + 1;
1’: def(a, 1);
1 : a = 10;
2’: ref(a, 2);
2’: def(b, 2);
2 : b = a + 1;
F.Ohata, K.Hirose, M.Fujii and K.Inoue:“A Slicing Method for Object-Oriented Programs Using
Lightweight Dynamic Information”, Proceedings of 8th Asia Pacific Software Engineering
Conference , pp.273-280, Macau, China, December (2001).
†
2002/02/19
2001年度修士論文発表会
7
提案手法
「JVMに基づくDCスライスのJavaへの適用」


コンパイル時に、バイトコードの各命令とソースコー
ドのトークン集合との対応表を生成
バイトコードに対し、依存関係解析を行う
 JVMを用いた動的データ依存関係解析
 静的制御依存関係解析（JVMとは独立）


バイトコードに対するPDG構築、スライス計算
生成した対応表をもとにバイトコードでのスライス
をソースコードに対応付ける
2002/02/19
2001年度修士論文発表会
8
計算手順
ソースコード
class A
Javaコンパイラ
スライス結果
対応表
class A
iconst_2
2
iload_1
j
iadd
+
istore_1
j=
バイトコードでのPDG
クラスファイル
class A
iconst_2
iload_1
iadd
istore_1
Java Virtual Machine
通常の実行結果
2002/02/19
2001年度修士論文発表会
9
提案手法による利点
解析精度の向上


コードの埋め込みを行わないため、構文制約の影
響を受けず、それに伴う解析精度の低下を防止
JDKライブラリ等、クラスファイルしか存在しないクラ
スを介した依存関係の抽出が可能
細粒度の解析の実現

バイトコードの各命令をPDG節点とすることで、
ソースコードの各文を節点とした場合と比べ細粒
度の解析が可能
2002/02/19
2001年度修士論文発表会
10
JVMでの動的データ依存関係解析
Java Virtual Machine
1:
2:
3:
4:
iconst_1
iconst_2
iadd
istore_0
ローカル変数
0
2
3
1
対応するキャッシュ
データ依存関係
0
2002/02/19
3
スタック
s4
2001年度修士論文発表会
s2
s1
s3
11
提案手法の実現
提案した手法を実現するシステムを構築





対応表出力（コンパイラ）†
動的データ依存関係解析（JVM）†
静的制御依存関係解析
PDG構築・スライス計算
ユーザインターフェイス
総行数：約580,000行（うち追加コード16,000行）
†
2002/02/19
JDK付属の javac , java に対する機能追加により実現
2001年度修士論文発表会
12
評価（1/2）
簡易データベースシステム（4クラス・262行）
（Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2）
スライスサイズ [行（全体に対する割合）]
静的スライス
提案手法
動的スライス
スライス基準1 60（22.9%） 30（11.4%） 24（10.3%）
スライス基準2
19（7.3%）
15（5.7%）
14（5.4%）
静的スライスに比べ約50%から80%のスライスサイズ
静的スライスに比べ精度の高いスライス計算
2002/02/19
2001年度修士論文発表会
13
評価（2/2）
JVM実行時間 [ms]
通常実行解析付実行
325
2,058
JVM消費メモリ [Kbytes]
通常実行解析付実行
3,780
15,980
構築されるPDGの節点数
提案手法動的スライス
34,966
1,198,596
動的スライスの計算には30倍以上の解析コストが必要
動的スライスに比べ十分に小さいコストでのスライス計算
2002/02/19
2001年度修士論文発表会
14
まとめ・今後の課題
JVMを用いたDCスライス計算手法の提案


JVMによる動的データ依存関係解析
バイトコードでのスライスをソースコードに対応付け
小さい解析コストで、精度の高いスライス計算を実現
今後の課題


動的に発生する制御フローへの対応
ネイティブメソッドへの対応
2002/02/19
2001年度修士論文発表会
15

Download Report