Javaプログラム用スライスシステムの制御依存関係解析

バイトコードを単位とする
Javaスライスシステムの試作
井上研究室
梅森文彰
1
プログラムスライス
• ある文のある変数(スライス基準)の値に影響を
与え得る文の集合
1:
2:
3:
4:
5:
6:
7:
8:
a = 0;
b = 1;
if (a > b) {
c = a;
} else {
c = b;
}
return c;
スライス基準
＜6，c＞
1:
2:
3:
4:
5:
6:
7:
8:
a = 0;
b = 1;
if (a > b) {
c = a;
} else {
c = b;
}
return c;
• デバッグ対象が限定され、フォールト位置の特定
を効率よく行うことができる
2
スライス - 計算手順 1. 依存関係解析
– 制御依存関係解析
– データ依存関係解析
2. プログラム依存グラフ(PDG)構築
– 節点: 各プログラム文
– 辺: 文間の依存関係
3. スライス計算
制御依存関係
if (i < 5) {
i++;
}
データ依存関係
a = 1;
b = a;
a
プログラム依存グラフ
– スライス基準に対応するPDG節点か
ら有向辺を逆向きにたどる
– 到達可能な節点集合に対応する文
が求めるスライス
3
スライス - 分類 • 静的スライス
– (プログラム実行を伴わない)静的依存関係解析に基づく
解析コストは小さいが、すべての実行経路を
考慮するため、解析精度は低い
• 動的スライス
– (プログラム実行を伴う)動的依存関係解析に基づく
解析精度は高いが、プログラムの実行系列を
保存しなければならず、解析コストは大きい
• DCスライス
– 動的データ依存関係解析、静的制御依存関係解析に基づく
動的スライスより低コストで、かつ静的スライス
より高精度のスライス計算が可能
4
研究の目的
• オブジェクト指向言語 Java
– 近年のソフトウェア開発環境で多く利用される
– 多くの実行時決定要素の存在
• 配列の添字、オブジェクトへの参照、動的束縛
• 例外処理、並列処理
• Javaを対象とするスライスシステムの構築
– DCスライスを適用
– バイトコードを解析単位とし、解析結果をソースコード
に反映
5
Javaスライスシステム - 解析手順 Phase 1: ソースコード・バイトコード対応表の出力
Phase 2: バイトコードに対する依存関係解析
(a)：静的制御依存関係解析
(b)：動的データ依存関係解析†
Phase 3: PDGによるスライス計算
以降、スライス、スライス基準、PDGに対し、バイトコード、
ソースコードそれぞれに関するものを、(S)、(B)を用いて表す。
(例: スライス基準(S) 、スライス(B) )
†誉田謙二：“バイトコード間の動的依存情報を抽出するＪａｖａバーチャルマシン”，
大阪大学大学院基礎工学研究科修士学位論文，2002
6
Phase 1: ソースコード・バイトコード対応表の出力
• ソースコードのトークン列とバイトコードとの対応を
抽出
int i = 0;
if (i < 5) {
i++;
}
iconst_0
0
istore_1
i=
iconst_5
5
iload_1
i
if_cmpge L8
<
iinc 1 1
L8:
nop
return
i++
<
main
7
Phase 2(a): 静的制御依存関係解析†
• バイトコード間の制御依存関係を静的に解析
• 手順
– 基本ブロックの分割
– 制御フローグラフの構築
– 制御依存関係の抽出
iconst_0
istore_1
iconst_5
iload_1
if_cmpge L8
iconst_0
istore_1
iconst_5
iload_1
iconst_0
istore_1
iconst_5
iload_1
if_cmpge L8
iinc 1 1
L8:
if_cmpge L8
iinc 1 1
iinc 1 1
nop
L8:nop
return
return
†Andrew.W:
Modern Compiler Implementation in C, 1998
L8:
nop
return
8
Phase 3:
PDGによるスライス計算
• スライス基準に対応するPDG節点から有向辺を
逆向きにたどることで、スライスを抽出
• 手順
– 対応表による、スライス基準(S)からスライス基準(B)へ
の変換
– PDG(B)の構築およびその探索
– 対応表による、スライス(B)からスライス(S)への変換
9
Javaスライスシステム - 適用例スライス結果
ソースコード
int i = 0;
if (i < 5) {
i++;
}
スライス基準
Javaコンパイラ
1:
iconst_0
1:
0
2:
isotre_1
2:
i=
3:
iconst_5
3:
5
4:
iload_1
4:
i
5:
if_cmpge L8
5:
<
6:
iinc 1 1
6:
i++
nop
7:
<
return
8:
main
7:
8:
L8:
Java
バーチャルマシン
int i = 0;
if (i < 5) {
i++;
}
iconst_0
スライサ
istore_1
iconst_5
iload_1
if_cmpge
L8
制御依存関係
解析ツール
iinc 1 1
L8: nop
静的制御依存関係
通常の実行結果
動的データ依存関係
return
10
Javaスライスシステム - 実装 Phase 1:
ソースコード・バイトコード対応表の出力
– Javaコンパイラの機能拡張
– 言語:Java、行数:約3,000行(約42,000行)
Phase 2(a):
バイトコードに対する静的制御依存関
係解析
– バイトコードダンプツールの機能拡張
– 言語:C、行数:約1,600行(約4,000行)
Phase 3:
PDGによるスライス計算
– 言語:C、行数:約1,200行
()内は機能拡張後のツールにおけるコード総行数を表す
11
Javaスライスシステム - 評価 • 解析精度(スライスサイズ)
– 対象: 簡易データベースシステム（4クラス・262行）
– 評価: 提案手法と動的スライス、静的スライスとの比較
スライスサイズ[行](全体に対するスライスの割合)
静的スライス
提案手法
動的スライス
スライス基準1
60(22.9%)
30(11.4%)
24(10.3%)
スライス基準2
19(7.3%)
15(5.7%)
14(5.4%)
静的スライスに比べ、十分に高い解析精度を満たすことを
確認
実験環境： Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2
12
まとめ
• バイトコードを単位とする細粒度Javaスライスシ
ステムの試作
– ソースコード・バイトコードの対応表の出力
– バイトコードに対する制御依存関係解析
– PDGによるスライス計算
高精度のスライスを低コストで抽出可能
• 今後の課題
– バイトコードの最適化に対応したバイトコード・ソース
コード対応表の作成
– 実際のプログラム開発におけるシステムの適用
13
評価 - 解析コスト Phase 1:
ソースコード・バイトコード対応表の出力
簡易データベースシステム（4クラス・262行）のコンパイル
Phase 2(a):
係解析
Phase 3:
通常出力時[ms]
対応表出力時[ms]
1,114
2,405
バイトコードに対する静的制御依存関
JDK付属クラスライブラリの制御依存関係解析
総クラス数
解析時間(全体)[ms]
平均解析時間(一クラス)[ms]
4,807
48,060
9.99
PDGによるスライス計算
簡易データベースシステム（4クラス・262行）のスライス計算
PDG節点数
34,996
PDG構築時間[ms] スライス計算時間[ms]
346
179
実験環境： Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2
14

Download Report