依存関係の局所性を利用した プログラム依存グラフの 効率的な構築法

Presentation on theme: "依存関係の局所性を利用した プログラム依存グラフの 効率的な構築法"— Presentation transcript:

1 依存関係の局所性を利用した プログラム依存グラフの 効率的な構築法
大畑　文明 西松　顯 井上　克郎 大阪大学大学院　基礎工学研究科

2 発表内容 プログラムスライス 既存の手法の問題点 提案する手法 評価実験 まとめ 今後の課題 99/03/18
第122回 ソフトウェア工学研究会

3 研究の背景 ソフトウェアの大規模化・複雑化に伴い、ソフトウェア開発コストの50～80%をテスト工程に費やすという報告がある(Robson, D.J et al., “Approaches to Program Comprehension”, J.System Software, Vol.14, No.1, 1991.) テスト工程の中で最も時間のかかる作業がフォールト位置特定である フォールト位置の特定を効率よく行う手法として、プログラムスライスが提案されている 99/03/18 第122回 ソフトウェア工学研究会

4 プログラムスライス プログラム中のある文sのある変数v (スライス基準)の値に影響を与えうる文の集合 スライス基準(5, b)のスライス
スライスの他の用途 プログラム再利用・プログラム理解 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } スライス基準(5, b)のスライス 99/03/18 第122回 ソフトウェア工学研究会

5 スライスの計算過程 スライス計算問題 グラフ到達問題 99/03/18 第122回 ソフトウェア工学研究会

6 Phase 1: 定義・参照変数抽出 各文の定義・参照変数を抽出 1: b = 5; 2: a = b + b;
3: if(a > 0) { 4: c = a: 5: d = b; } 99/03/18 第122回 ソフトウェア工学研究会

7 Phase 2-1: (データ)依存関係解析 文間に存在するデータ依存関係を抽出
ある変数wが存在して、文sにおける変数wの定義が、変数wを参照している文tに到達 データ依存関係DD(s, w, t)が存在 DD(1, b, 2), DD(2, a, 3) DD(1, b, 5), DD(2, a, 4) 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } 99/03/18 第122回 ソフトウェア工学研究会

8 Phase 2-2: (制御)依存関係解析 文間に存在する制御依存関係を抽出
文sが分岐(繰り返し)命令であり、その分岐(繰り返し)節が文tを直接含む 制御依存関係CD(s, t)が存在 CD(3, 4), CD(3, 5) 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } 99/03/18 第122回 ソフトウェア工学研究会

9 Phase 3: プログラム依存グラフ構築 プログラムに存在する文・依存関係を有向グラフで表現した(節点 Û 文, 辺 Û 依存関係)、プログラム依存グラフ(PDG)を作成 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } 99/03/18 第122回 ソフトウェア工学研究会

10 Phase 4: スライス抽出 スライス基準に対応した節点からPDG辺を逆にたどる 到達可能節点 Û スライス基準に対するスライス
1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a; 5: d = b; } 99/03/18 第122回 ソフトウェア工学研究会

11 既存の手法の問題点 「よりきめ細かい依存関係解析を行い、スライスの大きさを小さくする」ことを目標としてきた
ポインタ解析、構造体・配列の要素を区別 関数間の依存解析 大規模プログラムに対する同様の要求は困難 28,000行のプログラムに対し、620MBのメモリ空間・2時間の解析時間(The Wisconsin Program-Slicing Tool 1.0, Reference Manual. Computer Science Department, University of Winconsion-Madison, August 1997.) 99/03/18 第122回 ソフトウェア工学研究会

12 既存の手法の問題点 続き コスト軽減のため多くの依存関係解析アルゴリズムが提案され、スライスの正確性(スライスの大きさ)とのトレード・オフが考えられてきた(Atkison, D. C. and Griswold, W. G. “The Design of Whole-Program Analysis Tools”. In Proceedings of the 18th International Conference on Software Engineering, Berlin, Germany, pages , 1996.) 異なる依存関係解析アルゴリズムで構築されたPDGは相互利用が困難 99/03/18 第122回 ソフトウェア工学研究会

13 提案する手法 依存関係解析アルゴリズム(Phase 2:)と独立した、コスト削減
従来PDG節点と文は1対1対応であったものを、1節点で複数文を処理(節点集約) 情報共有による、情報量(空間コスト)削減 計算対象の削減による、計算量(時間コスト)削減 99/03/18 第122回 ソフトウェア工学研究会

14 節点集約 位置付け 対象 「Phase 2: 依存関係解析」と独立 依存関係解析前に集約を実行(Phase 1.5: 集約)
集約の時間コストを最小限に抑える 制限された依存関係情報 PDG構築後の、正確性の変更コストを抑える 文・プログラム構造のまとまりに限定 99/03/18 第122回 ソフトウェア工学研究会

15 集約の問題 単純に連続した文を集約すると、スライスが著しく不正確になる可能性がある 1: a = 1; 2: b = 1;
3: c = 1; 4: d = 1; 5: if(a > 0) { 6: e = b; 7: f = c * d; 8: g = f + c + d + a; } 9: h = g; 10: i = e; (7) (9) 99/03/18 第122回 ソフトウェア工学研究会

16 集約の方針 同じ文に依存する(依存関係の局所性を有する)文の集約では、正確性の低下を抑えることができる 1: a = 1;
2: b = 1; 3: c = 1; 4: d = 1; 5: if(a > 0) { 6: e = b; 7: f = c * d; 8: g = f + c + d + a; } 9: h = g; 10: i = e; (7) (7) 99/03/18 第122回 ソフトウェア工学研究会

17 依存関係の局所性 隣接する2文に関して、それらが依存している文が一致していること
依存関係の局所性を把握するため、局所データ依存関係LD(s, w, t)を定義 99/03/18 第122回 ソフトウェア工学研究会

18 局所データ依存関係 直接のデータ依存関係に加え、間接的なデータ依存関係を含んでいる
集約対象文s1・s2の全参照変数集合Aに対し、"a$t[aÎA ® LD(t, a, s1)&LD(t, a, s2)]を満たす場合、集約を行う 99/03/18 第122回 ソフトウェア工学研究会

19 依存関係の局所性(例1) (直接の)参照変数の一致 1: a = 1; 2: b = 1; 3: c = a + b;
4: d = a + b; 99/03/18 第122回 ソフトウェア工学研究会

20 依存関係の局所性(例2) (DD+DD間接を含む)参照変数の一致 1: a = 1; 2: b = 1; 3: c = a + b;
4: d = c; 99/03/18 第122回 ソフトウェア工学研究会

21 依存関係の局所性(例3) (DD+CD間接を含む)参照変数の一致 1: a = 1; 2: b = 1; 3: if(a > 0) {
4: c = b; 5: d = a + b; } 99/03/18 第122回 ソフトウェア工学研究会

22 集約の判定(例) 文7・文8の集約 1: a = 1; 2: b = 1; 3: c = 1; 4: d = 1;
5: if(a > 0) { 6: e = b; 7: f = c * d; 8: g = f + c + d + a; } 9: h = g; 10: i = e; 99/03/18 第122回 ソフトウェア工学研究会

23 集約アルゴリズム 判定に必要な局所データ依存関係LDは、 「Phase 1: 定義・参照変数抽出」で取得可能
DD集合 Í LD集合であるため、集約によりスライスに含まれるべき文が含まれなくなることはない プログラム構造ごとの判定および集約 99/03/18 第122回 ソフトウェア工学研究会

24 集約アルゴリズム 続き 依存している文が一致する場合のみの集約は厳密であるため、集約許容値limit(³0)を定義
99/03/18 第122回 ソフトウェア工学研究会

25 評価実験 我々が試作したスライスツールへの機能追加 テストプログラム テスト項目 サブセットPascalを対象(レコード型・ポインタ なし)
空間コスト(PDGの節点・辺数) 時間コスト(解析時間) 正確性(スライスサイズ) 99/03/18 第122回 ソフトウェア工学研究会

26 実験結果(空間コスト) その1 PDG節点数[個] 99/03/18 第122回 ソフトウェア工学研究会

27 実験結果(空間コスト) その２ PDG辺数[本] 99/03/18 第122回 ソフトウェア工学研究会

28 実験結果(時間コスト) 解析時間[ms] Phase 1: (Phase 1.5:) Phase 2: Phase 3:
PentiumII-300MHz-128MB(Linux) 99/03/18 第122回 ソフトウェア工学研究会

29 実験結果(スライスサイズ) 平均スライスサイズ[文] 99/03/18 第122回 ソフトウェア工学研究会

30 考察 約500行のプログラムに対し、PDGの空間コスト:6.7～45.1%・時間コスト:10.0～40.0%の削減を行うことができた
より大きなプログラムに対して集約によるスライス正確性低下が抑えられる傾向がある 99/03/18 第122回 ソフトウェア工学研究会

31 まとめ プログラムスライスの紹介を行った 節点集約によるPDG構築コストの削減手法を提案し、その有効性を実験により評価した 99/03/18
第122回 ソフトウェア工学研究会

32 今後の課題 ポインタ変数を持つ言語への本アルゴリズムの適応 PDG構築後の節点分解 大規模プログラムに対する有効性の評価
プログラム理解に対する有効性の評価 99/03/18 第122回 ソフトウェア工学研究会