バイトコードを単位とするJavaスライスシステムの試作

Presentation on theme: "バイトコードを単位とするJavaスライスシステムの試作"— Presentation transcript:

1 バイトコードを単位とするJavaスライスシステムの試作
井上研究室 梅森　文彰

2 プログラムスライス ある文のある変数(スライス基準)の値に影響を与え得る文の集合
デバッグ対象が限定され、フォールト位置の特定を効率よく行うことができる 1: a = 0; 2: b = 1; 3: if (a > b) { 4: c = a; 5: } else { 6: c = b; 7: } 8: return c; スライス基準 ＜6，c＞ 1: a = 0; 2: b = 1; 3: if (a > b) { 4: c = a; 5: } else { 6: c = b; 7: } 8: return c; プログラムスライス。以降単にスライスと呼びます。 ある文のある変数、これをスライス基準と呼びますが、この値に影響を与えうる文の集合をスライスと呼びます。 例えば、左のようなソースコードが与えられたときにスライス基準、６行目のｄを与えると右の図の赤字のようなスライスが得られます。 このようにデバッグ対象が限定されるので、フォールト位置の特定を効率よく行うことができます。

3 スライス - 計算手順 - 1. 依存関係解析 2. プログラム依存グラフ(PDG)構築 3. スライス計算 制御依存関係解析
データ依存関係解析 2. プログラム依存グラフ(PDG)構築 節点: 各プログラム文 辺: 文間の依存関係 3. スライス計算 スライス基準に対応するPDG節点から有向辺を逆向きにたどる 到達可能な節点集合に対応する文が求めるスライス 制御依存関係 if (i < 5) { i++; } データ依存関係 a = 1; b = a; a プログラム依存グラフ スライス計算手順 1．依存関係解析 依存関係解析には、制御依存関係解析とデータ依存関係解析があり、 制御依存関係とは、 ある条件文とその条件文によって実行されるかどうかが決定する文との関係のことです。 例えば、i<5という条件文によりi++という文が実行されるかどうか決定するのでここに制御依存関係が存在します。 データ依存関係とは、 ある変数を定義する文と参照する文の関係のことです。 例えば、変数aについて、a=1で定義され、b=aで参照されているのでここにデータ依存関係が存在します。 ２．プログラム依存グラフ(PDG)構築 プログラム依存グラフとは各プログラム文を節点で表し、文間の依存関係を有向辺で表したグラフです。 ３． スライス計算 まず、スライス基準に対応するPDGの節点を設定します。 そして、ここから有向辺を逆方向にたどることで到達可能な節点の集合を求めます。

4 スライス - 分類 - 静的スライス 動的スライス DCスライス (プログラム実行を伴わない)静的依存関係解析に基づく
解析コストは小さいが、すべての実行経路を考慮するため、解析精度は低い 動的スライス (プログラム実行を伴う)動的依存関係解析に基づく 解析精度は高いが、プログラムの実行系列を保存しなければならず、解析コストは大きい DCスライス 動的データ依存関係解析、静的制御依存関係解析に基づく 動的スライスより低コストで、かつ静的スライスより高精度のスライス計算が可能

5 研究の目的 オブジェクト指向言語 Java Javaを対象とするスライスシステムの構築 近年のソフトウェア開発環境で多く利用される
多くの実行時決定要素の存在 配列の添字、オブジェクトへの参照、動的束縛 例外処理、並列処理 Javaを対象とするスライスシステムの構築 DCスライスを適用 バイトコードを解析単位とし、解析結果をソースコードに反映 研究の目的 オブジェクト指向言語Javaは近年のソフトウェア開発環境で多く利用されていますが、Javaには多くの実行時決定要素が存在します。 そのため、静的スライスでは十分な解析制度が得られず、動的スライスでは解析コストが膨大な量になってしまいます。 そこで、Javaを対象とするスライスシステムの構築としてDCスライスを適用し、またバイトコードを解析単位とすることで、 細粒度のスライスを計算し、その結果をソースコードに反映させます。

6 Javaスライスシステム - 解析手順 - Phase 1: ソースコード・バイトコード対応表の出力
(b)： 動的データ依存関係解析† Phase 3: PDGによるスライス計算 Javaスライスシステムの解析手順 Phase 1: ソースコード・バイトコード対応表の出力 Phase 2: バイトコードに対する依存関係解析 (a)： 静的制御依存関係解析 (b)： 動的データ依存関係解析† Phase 3: PDGによるスライス計算 今回私が研究したのはPhase1、Phase2の(a)、Phase3で、以降この３つについて説明します。 以降、スライス、スライス基準、PDGに対し、バイトコード、ソースコードそれぞれに関するものを、(S)、(B)を用いて表します。 例えば、ソースコード上のスライス基準はスライス基準(S) 、バイトコード単位のスライスはスライス(B) と表されます。 以降、スライス、スライス基準、PDGに対し、バイトコード、ソースコードそれぞれに関するものを、(S)、(B)を用いて表す。 (例: スライス基準(S) 、スライス(B) ) †誉田謙二：“バイトコード間の動的依存情報を抽出するＪａｖａバーチャルマシン”， 大阪大学大学院基礎工学研究科修士学位論文，2002

7 Phase 1: ソースコード・バイトコード対応表の出力
ソースコードのトークン列とバイトコードとの対応を抽出 iconst_0 istore_1 i = iconst_5 5 iload_1 i if_cmpge L8 < iinc 1 1 i++ L8: nop return main int i = 0; if (i < 5) { i++; } Phase 1: ソースコード・バイトコード対応表の出力 ここでは、ソースコードのトークン列とバイトコードとの対応を抽出します。 手順、まずトークン列と構文木要素との対応を抽出します。 次に構文木要素とバイトコードとの対応を抽出します。 対応表の例として、図のようなソースコードに対して次のようなバイトコードと対応関係が得られます。 例えば、1行目のiconst_０はソースコードのこの０に対応するのでこちらで０が出力されています。 以下同様になっています。

8 Phase 2(a): 静的制御依存関係解析†
バイトコード間の制御依存関係を静的に解析 手順 基本ブロックの分割 制御フローグラフの構築 制御依存関係の抽出 iconst_0 istore_1 iconst_5 iload_1 if_cmpge L8 iinc 1 1 L8: nop return iconst_0 istore_1 iconst_5 iload_1 if_cmpge L8 iconst_0 istore_1 iconst_5 iload_1 if_cmpge L8 iinc 1 1 L8: nop return Phase 2(a): 静的制御依存関係解析 ここではバイトコード間の制御依存関係を静的に解析します。 手順、まずバイトコードを分岐も合流もない基本ブロックに分割します。 次にプログラムの流れを有向辺で表し、制御フローグラフを構築します。 そして、それから制御依存関係を抽出します。 例えば、図のようなバイトコードをまず基本ブロックに分け、制御フローグラフを構築します。 これにより、この図の赤字のような制御依存関係が得られます。 if_cmpge L8 iinc 1 1 iinc 1 1 L8:nop return †Andrew.W: Modern Compiler Implementation in C, 1998

9 スライス基準に対応するPDG節点から有向辺を逆向きにたどることで、スライスを抽出 手順
Phase 3: PDGによるスライス計算 スライス基準に対応するPDG節点から有向辺を逆向きにたどることで、スライスを抽出 手順 対応表による、スライス基準(S)からスライス基準(B)への変換 PDG(B)の構築およびその探索 対応表による、スライス(B)からスライス(S)への変換 Phase 3: PDGによるスライス計算 ここでは、スライス基準に対応するPDG節点から有向辺を逆向きにたどります。 手順として、 まずソースコード上のスライス基準から、バイトコード上のスライス基準に変換します。 次にバイトコードのPDGを構築し、探索を行いスライスを得ます。 最後にバイトコード単位のスライスから、ソースコード単位のスライスに変換します。

10 Javaスライスシステム - 適用例 - スライサ iconst_0 istore_1 iconst_5 iload_1 iinc 1 1
int i = 0; if (i < 5) { i++; } スライス結果 int i = 0; if (i < 5) { i++; } ソースコード スライス基準 Javaコンパイラ iconst_0 1: iconst_0 2: isotre_1 3: iconst_5 4: iload_1 5: if_cmpge L8 6: iinc 1 1 7: L8: nop 8: return 1: 2: i = 3: 5 4: i 5: < 6: i++ 7: 8: main istore_1 スライサ iconst_5 iload_1 Javaスライスシステムの適用例 まずソースコードをJavaコンパイラに通すと、バイトコードと対応関係が得られます。 次にバイトコードをバイトコードダンプツールに通し、静的制御依存関係を求めます。 またバイトコードをJavaバーチャルマシン上で実行することで、通常の実行結果と動的データ依存関係が得られます。 そしてこれらの依存関係と先程の対応表、スライス基準を基にスライサによってPDGを構築し、スライス基準に対応する節点から スライスを求めます。 そしてその結果をソースコードに反映させます。 if_cmpge L8 制御依存関係 解析ツール iinc 1 1 Java バーチャルマシン L8: nop 静的制御依存関係 return 動的データ依存関係 通常の実行結果

11 Javaスライスシステム - 実装 - Javaコンパイラの機能拡張 言語:Java、行数:約3,000行(約42,000行)
Phase 1: ソースコード・バイトコード対応表の出力 Javaコンパイラの機能拡張 言語:Java、行数:約3,000行(約42,000行) Phase 2(a): バイトコードに対する静的制御依存関係解析 バイトコードダンプツールの機能拡張 言語:C、行数:約1,600行(約4,000行) Phase 3: PDGによるスライス計算 言語:C、行数:約1,200行 Javaスライスシステムの実装 Phase1ではJavaコンパイラの機能拡張を行いました。 Phase2の(a)ではバイトコードダンプツールの機能拡張を行いました。 Phase3では約1200行のプログラムを作成しました。 ()内は機能拡張後のツールにおけるコード総行数を表す

12 Javaスライスシステム - 評価 - 解析精度(スライスサイズ) 対象: 簡易データベースシステム（4クラス・262行）
評価: 提案手法と動的スライス、静的スライスとの比較 スライスサイズ[行](全体に対するスライスの割合) 静的スライス 提案手法 動的スライス スライス基準1 60(22.9%) 30(11.4%) 24(10.3%) スライス基準2 19(7.3%) 15(5.7%) 14(5.4%) Javaスライスシステムの評価 ここでは解析精度としてスライスサイズの評価をしました。 対象プログラムとして簡易データベースシステム、4クラス262行のプログラムを使いました。 評価方法として提案手法と動的スライス、静的スライスとの比較を行いました。 なお、得られたスライスのサイズ小さいほど解析精度が高いということになります。 ここでスライスの結果をUIを用いて表示するとこのようになります。 青い部分がスライスです。 この結果から静的スライスに比べ、十分に高い解析精度を満たすことを確認しました。 静的スライスに比べ、十分に高い解析精度を満たすことを 確認 実験環境： Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2

13 まとめ バイトコードを単位とする細粒度Javaスライスシステムの試作 今後の課題 ソースコード・バイトコードの対応表の出力
バイトコードに対する制御依存関係解析 PDGによるスライス計算 高精度のスライスを低コストで抽出可能 今後の課題 バイトコードの最適化に対応したバイトコード・ソースコード対応表の作成 実際のプログラム開発におけるシステムの適用 まとめ 今回、バイトコードを単位とする細粒度Javaスライスシステムの試作として ソースコード・バイトコードの対応表の出力、バイトコードに対する依存関係解析、PDGによるスライス計算を行いました。 今後の課題として バイトコードの最適化に対応したバイトコード・ソースコード対応表の作成、実際のプログラム開発におけるシステムの適用が 挙げられます。

14 実験環境： Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2
評価 - 解析コスト - Phase 1: ソースコード・バイトコード対応表の出力 Phase 2(a): バイトコードに対する静的制御依存関係解析 Phase 3: PDGによるスライス計算 簡易データベースシステム（4クラス・262行）のコンパイル 通常出力時[ms] 対応表出力時[ms] 1,114 2,405 JDK付属クラスライブラリの制御依存関係解析 総クラス数 解析時間(全体)[ms] 平均解析時間(一クラス)[ms] 4,807 48,060 9.99 Phase1では、通常の実行時に比べて、対応表出力時は2倍以上のコストがかかっております。 これはバイトコードに対して最適化を一切行わなかったことが原因だと考えられます。 Phase2(a)、Phase3では、比較することができないので結果だけをのせています。 これらの解析コストは動的データ依存関係の解析コストに比べるとはるかに小さいものなのでこれらの解析コストが 特に問題ありません。 簡易データベースシステム（4クラス・262行）のスライス計算 PDG節点数 PDG構築時間[ms] スライス計算時間[ms] 34,996 346 179 実験環境： Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2