?
?
?
依存キャッシュスライシング
データ依存関係に着目した準動的スライシン グ手法
制御依存関係
構文解析で容易に解析可能
⇒ 静的に解析
データ依存関係
静的に正確な解析は困難
⇒ 簡単なキャッシュを用い、動的に解析
依存キャッシュスライスの計算
1.
実行前解析:
節点と制御依存辺のみからなるPDG
のサブセットPDG DS
を構築。変数にキャッシュを用意
2.
実行時解析:
変数が定義されれば、キャッ シュに文を設定。変数が参照されれば、キャッシュに保持されている文からデータ依 存辺を追加
3.
実行後解析:
なし4.
スライス計算: PDG DS
の辺を辿りスライスを抽 出アルゴリズムの概要
1.
静的制御依存関係解析PDG
の部分グラフPDG DS
を静的に生成する．まず，静的スライシングで利用する
PDG
と同様，文または制御文に対応 する節点を用意する．そして，文間に制御依存関係が存在すれば，対応す る節点間に制御依存辺を引く．ただし，PDG DS
にデータ依存辺は加えな い．2.
動的データ依存関係解析対象プログラムをある入力データで実行する．
実行の際，次節で示すデータ依存関係抽出アルゴリズムに基き，動的な データ依存関係を計算し，
PDG DS
にデータ依存辺を追加する．プログラ ム実行が終了した時点で，PDG DS
の完成となる．3. PDG DS
によるスライス計算PDG DS
を用いて，静的スライシングと同様の方法でスライス計算を行う．例えば，スライシング基準
(s c , v)
に関する依存キャッシュを抽出する場合，まず，
s c
に対応する節点から制御依存辺およびv
に関するデータ依存辺 を逆向きに辿ることで到達可能な節点集合を導出する．そして，この節点 集合に対応する文が求めるスライスとなる．動的データ依存関係抽出アルゴリズム
入力
PDG BL :
部分的に生成されブロック化されたPDG P:
対象プログラムI: P
への入力作業変数
P
中の各変数v
に対する依存キャッシュC(v)
出力
OUT:
入力I
に対するプログラムP
の実行の出力PDG BL :
完成したPDG
アルゴリズム本体1. P
中の各静的変数v
に対し, C(v) := Φ 2. P
が停止するまで以下を繰り返し実行する{ P
を入力I
で最初から停止するまで文ごとに実行}
a) I
に関して，P
の次の一文s
を実行b) s
で使用(
参照)
される各変数u
について，C(u) ≠Φ
かつ，データ依存辺C(u) u s
が存在しなければPDG BL
に
C(u) u s
を追加する．c) s
で定義される各変数w
について，C(w) := s
a[0] a[1] b c s1
s1 s2
s1 s2 s3
データ依存関係収集
1: a[0]:=0;
2: a[1]:=3;
3: readln(b);
4: a[b]:=2;
5: c:=a[0]+4;
6: writeln(c);
2: a[1]:=3;
3: readln(b);
4: a[b]:=2;
5: c:=a[0]+4;
6: writeln(c);
1: a[0]:=0;
Input: b=0
b a[0]
c
キャッシュ内容
s4 s2 s3
s4 s2 s3 s5
s4 s2 s3 s5
a[0] a[1] b c s1
s1 s2
s1 s2 s3
データ依存関係収集 (2)
1: a[0]:=0;
2: a[1]:=3;
3: readln(b);
4: a[b]:=2;
5: c:=a[0]+4;
6: writeln(c);
2: a[1]:=3;
3: readln(b);
4: a[b]:=2;
5: c:=a[0]+4;
6: writeln(c);
1: a[0]:=0;
Input: b=1
b a[0]
c
キャッシュ内容
s1 s4 s3
s1 s4 s3 s5
依存キャッシュスライスの特長
簡単なキャッシュを用いることで、動的な データ依存関係を収集
⇒ 効率的かつ効果的なスライス
既存環境にキャッシュおよび
DD
辺構築機能 を追加することで実装可能⇒ 実装が容易
実験
３つのプログラム
P1:
カレンダーP2
：酒屋問題P3
：酒屋問題（拡張版）について、
静的スライス
コールマークスライス 依存キャッシュスライス 動的スライス
を計算
実験結果～スライスサイズ
21
182 187
17
162 166
15 16
61
5 5 8
0 20 40 60 80 100 120 140 160 180 200
P1 P2 P3
static call-mark
dependence-cache dynamic
行
静的 ＞
CM ＞＞ DC ＞
動的P2 ・ P3
では配列変数を使用しているため顕著47 43
4700
47 43
4731
51 174 45
4540
206464 4834
0 1000 2000 3000 4000 5000 6000
P1 P2 P3
static call-mark
dependence-cache dynamic
実験結果～実行時解析時間
時間
(ms)
静的 ≒
CM DC ≒ ＜＜
動的DC
は僅かな実行時オーバヘッド増加で解析可能まとめ
準動的手法を用いたスライシング手法 「依 存キャッシュスライシング」 を提案
スライスサイズは静的スライシングより小さ く、動的スライシングより大きい
僅かな実行時オーバヘッドで、配列・ポイン タ等を正確に解析可能
むすび
まとめ
プログラム中の文間の依存関係解析に関して，解析を効 率化するための手法を提案した．
プログラムに変更が加えられた際の再解析を効率化し，インタ ラクティブなデバッグ作業を実現するプログラム依存グラフの 効率的な更新手法
静的解析情報と動的解析情報を組み合わせた準動的解析手法を 用いることにより，現実的な実行時オーバヘッドで高精度のプ ログラムスライスを抽出できる依存キャッシュスライシング手 法
提案手法についてそれぞれの有効性を確認
↓
デバッグ作業の効率化、ソフトウェア開発の生産性向上