Document

プログラム解析の効率化
に関する研究
大阪大学大学院基礎工学研究科
情報数理系専攻ソフトウェア科学分野
高田智規
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
略歴
平成9年3月大阪大学大学院基礎工学研究科物理系専攻情報
工学分野博士前期課程修了在学中はプログラムスライシングに関
する研究に従事
平成9年4月日本電信電話株式会社入社
平成9年8月ヒューマンインタフェース研究所に配属ビデオサーバの負
荷分散技術の研究・開発に従事
平成12年4月西日本電信電話株式会社大阪支店に異動中規
模ERPパッケージのSI業務
平成13年10月大阪大学大学院基礎工学研究科情報数理系専
攻博士後期課程入学プログラムスライシングに関する研究に従事
平成14年5月日本電信電話株式会社サイバーソリューション研究
所に異動ディジタルコンテンツの著作権管理に関する研究・開発に従
事
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
論文一覧
プログラム依存グラフの効率的な更新手法
電子情報通信学会論文誌 (1998)
⇒ 2章
制限された動的情報を用いたプログラムスライシング手法の提案
電子情報通信学会論文誌(2002)
⇒ 3章
制限された動的情報を用いたブロック単位スライシング手法の提案
電子情報通信学会論文誌(投稿中)
⇒ 4章
ソースコード解析ツール開発支援システムの試用
電子情報通信学会論文誌(1997)
Dependence-Cache Slicing: A Program Slicing Method Using
Lightweight Dynamic Information,
10th IEEE International Workshop on Program Comprehension (2002/6
発表予定)
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
発表内容
プログラム解析概要
プログラム依存グラフの効率的な更新手法
プログラムが変更された場合に、プログラム依存グラフを
再計算することなく、部分的に更新する手法
準動的解析を用いたスライシング手法
静的解析情報と動的解析情報を組み合わせた効率的
なスライシング手法
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
プログラム解析概要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
デバッグ作業におけるプログラム解析
ソフトウェア開発において、デバッグ・テスト・保守
フェーズにおける比重はソフトウェアの大規模化に伴
い増加している
デバッグ効率向上へのアプローチ
文間の依存関係解析によって特定の文に関連のあ
る文を抽出
依存関係解析はオーバヘッドが大きい
↓
解析の効率化が重要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
プログラムスライス
注目した文に影響を与える（受ける）文の集合
プログラム開発における様々なフェーズで利用可能
⇒ 特にデバッグフェーズ
開発作業の効率化を実現
1 program Square_Cube(input, output);
2 var a, b, c, d : integer;
3 function Square(x : integer) : integer;
4 begin
5 Square := x * x
6 end;
7 function Cube(x : integer) : integer;
8 begin
9 Cube := x * x * x
10 end;
11 begin
12 writeln(``Squared Value ?'');
13 readln(a);
14 writeln(``Cubed Value ?'');
15 readln(b);
16 writeln(``Select Feature! Square: 0 Cube: 1'');
17 readln(c);
18 if c = 0 then
19 d := Square(a)
20 else
21 d := Cube(b);
22 if d < 0 then
23 d := -1 * d;
24 writeln(d)
25 end.
1 program Square_Cube(input, output);
2 var a, b, c, d : integer;
3 function Square(x : integer) : integer;
4 begin
5 Square := x * x
6 end;
7 function Cube(x : integer) : integer;
8 begin
9 Cube := x * x * x
10 end;
11 begin
12 writeln(``Squared Value ?'');
13 readln(a);
14 writeln(``Cubed Value ?'');
15 readln(b);
16 writeln(``Select Feature! Square: 0 Cube: 1'');
17 readln(c);
18 if c = 0 then
19 d := Square(a)
20 else
21 d := Cube(b);
22 if d < 0 then
23 d := -1 * d;
24 writeln(d)
25 end.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
フォールト位置特定におけるプログラムスライス
実験１
スライス利用
スライスなし
被験者
A1
A2
A3
B1
B2
B3
デバッグ時
間（分）
119
128
120
154
175
120
149.7
122.3
実験２
スライスなし
スライス利用
被験者
A1
A2
A3
B1
B2
B3
デバッグ時
間（分）
118
126
155
131
92
120
133.0
114.3
西松顕, 西江圭介, 楠本真二, 井上克郎: ``フォールト位置特定における
プログラムスライスの実験的評価'', 電子情報通信学会論文誌, Vol.J82-D-I,
No.11, pp. 1336--1344 (1999).
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
スライスの応用
フォールト位置特定
プログラム再利用
プログラム理解
プログラム合成
プログラム編集
プログラム簡素化
など
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
スライスの分類
静的スライシング
プログラムを静的に（実行なしに）解析
動的スライシング
特定の入力に基づき解析
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
静的スライシング
プログラムを静的に（実行なしに）解析
全ての入力データを仮定
依存関係を基にプログラム依存グラフ(Program
Dependence Graph, PDG)を構築
PDG辺を辿ることによりスライスを計算
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
依存関係
制御依存関係
ある文の実行有無が他の条件式の判定結果に依存
s1: if a=0 then
s2: b :=1;
s1
s2
データ依存関係
変数の定義-参照関係
s3: a := 1;
s4: writeln(a);
s3
a
s4
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
プログラム依存グラフ
依存関係を表したグラフ
節点文を表す
文
条件式
特殊節点（関数境界解析等）
辺
文間の依存関係を表す
データ依存辺
制御依存辺
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
PDGの例
1 program Square_Cube(input, output);
2 var a, b, c, d : integer;
3 function Square(x : integer) : integer;
4 begin
5 Square := x * x
6 end;
7 function Cube(x : integer) : integer;
8 begin
9 Cube := x * x * x
10 end;
11 begin
12 writeln(``Squared Value ?'');
13 readln(a);
14 writeln(``Cubed Value ?'');
15 readln(b);
16 writeln(``Select Feature! Square: 0 Cube: 1'');
17 readln(c);
18 if c = 0 then
19
d := Square(a)
20 else
21
d := Cube(b);
22 if d < 0 then
23
d := -1 * d;
24 writeln(d)
25 end.
Main
Square
writeln(“Sq..
readln(a)
x-para
writeln(“Cu..
x
readln(b)
a
Square := x * x
a
Square
Square-exit
Cube
x-para
x
writeln(“Sel..
readln(c)
if c=0
Square
d
d := Cube(b)
b
Cube := x*x*x
Cube-exit
b
d := Square(a)
if d<0
Cube
c
d
d
d := -1 * d
d
Cube
writeln(d)
d
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
静的スライスの例
1 program Square_Cube(input, output);
2 var a, b, c, d : integer;
3 function Square(x : integer) : integer;
4 begin
5 Square := x * x
6 end;
7 function Cube(x : integer) : integer;
8 begin
9 Cube := x * x * x
10 end;
11 begin
12 writeln(``Squared Value ?'');
13 readln(a);
14 writeln(``Cubed Value ?'');
15 readln(b);
16 writeln(``Select Feature! Square: 0 Cube: 1'');
17 readln(c);
18 if c = 0 then
19
d := Square(a)
20 else
21
d := Cube(b);
22 if d < 0 then
23
d := -1 * d;
24 writeln(d)
25 end.
Main
Square
writeln(“Sq..
readln(a)
x-para
writeln(“Cu..
x
readln(b)
a
Square := x * x
a
Square
Square-exit
Cube
x-para
x
writeln(“Sel..
readln(c)
if c=0
Square
d
d := Cube(b)
b
Cube := x*x*x
Cube-exit
b
d := Square(a)
if d<0
Cube
c
d
d
d := -1 * d
d
Cube
writeln(d)
d
スライシング基準
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
動的スライシング
プログラムをある入力データで実行する
注目した文に実際に影響を与えた文の集合
プログラムの実行系列を基に動的依存グラフ
(Dynamic Dependence Graph, DDG)を作成し、
グラフの辺を辿ることにより抽出
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
動的スライスの例
1 program Square_Cube(input, output);
2 var a, b, c, d : integer;
3 function Square(x : integer) : integer;
4 begin
5 Square := x * x
6 end;
7 function Cube(x : integer) : integer;
8 begin
9 Cube := x * x * x
10 end;
11 begin
12 writeln(``Squared Value ?'');
13 readln(a);
14 writeln(``Cubed Value ?'');
15 readln(b);
16 writeln(``Select Feature! Square: 0 Cube: 1'');
17 readln(c);
18 if c = 0 then
19
d := Square(a)
20 else
21
d := Cube(b);
22 if d < 0 then
23
d := -1 * d;
24 writeln(d)
25 end.
Square
Main
writeln(“Sq..
readln(a)
x-para
writeln(“Cu..
x
readln(b)
a
Square := x * x
a
Square
Square-exit
Cube
writeln(“Sel..
readln(c)
if c=0
Square
c
d := Square(a)
d
if d<0
d
writeln(d)
入力 a=2, b=1, c=0 の場合
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
静的・動的スライシングの特徴
静的スライシング
動的スライシング
プログラムの実行を伴わない
長所
プログラムの実行が必須
長所
有効な入力データが無い場
合でも解析可能
短所
全ての入力データを仮定した
安全な近似が必要
配列変数・ポインタ等の正確
な解析ができない
配列・ポインタ等も正確に解
析可能
短所
実行時オーバヘッドが大きい
実行時間、メモリ空間etc.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
プログラム依存グラフの
効率的な更新手法
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
デバッグフェーズにおけるスライス利用
ソース変更
実行
デバッグ終了
解析(PDG計算)
大規模プログラムにおいては
解析のオーバーヘッドが大きい
スライス計算
フォールト位置特定
プログラムに変更が加えられ
た際に、プログラム全体を再
解析することなしにPDGを更新
する手法が必要。
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
提案手法
PDG中の依存辺を基に変数の定義情報を復元
し、変更後の依存関係を計算することで、変更の
影響を受ける部分のみを更新
1. 制御依存辺更新
2. 関数内データ依存辺更新
3. 関数間影響解析
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
諸定義
対象言語
スカラ型のみからなる手続き型言語（Pascalサブセット）
PDG
通常のPDGに加え、フロー辺（実行順序を示す辺）を持
つグラフを対象とする
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
基本方針
制御依存関係は構文解析から更新
PDGのDD辺は解析時に変数の定義情報を基にし
て引かれている．
⇒ 変更前のPDG中のDD辺から，変数の定義情
報の一部を復元することが可能．
r
v
s
到達定義<r,v>
これを利用し、変更後のデータ依存関係を求め依
存辺を更新
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
提案するアルゴリズム
関数内解析アルゴリズム
文の削除
文の追加
文の修正（基本的には削除＋追加）
関数間解析アルゴリズム
他関数に与える影響を解析
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
削除アルゴリズム
アルゴリズムDeleteVertex
入力: 削除する節点s
出力: 更新されたPDG
1. sで定義されている各変数vについて
DD ← DD ∪ {r v t | r ∈ PreDef(s,v), t ∈ target(s,v)}
2. DD ← DD – {r v s | r ∈ source(s,v)} – {s v t | t ∈
target(s,v)}
3. FLOW ← FLOW ∪ { p → n | p ∈ prev(s), n ∈
next(s) } – { r → s | r ∈ prev(s) } – { s → t | t ∈
target(s) }
4. 節点s自身を削除
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
共通アルゴリズム
アルゴリズムFindPreDef （前定義節点の発見）
入力: 節点s , 変数v
出力: 前定義節点集合PreDef(s,v)
1. PreDef(s,v) ← φ
2. c ∈ prev(s) なる各cに対して以下を順に実行
a. cにおいてvが定義されていれば
PreDef(s,v) ← PreDef(s,v) ∪ c
b. cにおいてvが参照されていれば
PreDef(s,v) ← PreDef(s,v) ∪ source(c,v)
c. cにおいてvが定義・参照ともにされていなければ、c←prev(c)とし
て2a.以下を実行
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
定義
文sから文tへの変数vに関するデータ依存辺
s v t
文sから文tへのフロー辺
s→t
文sからフロー辺を逆方向に辿った節点集合
prev(s)
文sからフロー辺を順方向に辿った節点集合
next(s)
文sから変数vに関してデータ依存辺を逆方向に辿った節点集合
source(s,v)
文sから変数vに関してデータ依存辺を順方向に辿った節点集合
target(s,v)
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
削除アルゴリズム
s1
s1: readln(x,y);
s2: max := x;
s3: if x>y then
s4: max := x
else
s5: max := y;
s6: writeln(max);
1.
2.
3.
4.
readln(x,y)
s2
x
r
x
x
y
y
max := x
s3
max
if x>y
s4
s5
直前にmaxを定義している文r、
max := x
max := y
s
sからDDを辿った文tを発見
rからtへDDを追加
s6
t
max
直前の文と直後の文間にフ
max
writeln(max)
ロー辺を追加
sおよび関連する文を削除
DD
CD
Flow
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
挿入アルゴリズム
アルゴリズムInsertVertex
1.
2.
入力: 挿入する節点s, prev(s), next(s)
出力: 更新されたPDG
FLOW ← FLOW ∪ { p → s | p ∈ prev(s) } ∪ { s → n | n ∈
next(s) } – { p → n | p ∈ prev(s), n ∈ next(s) }
sで定義している各変数vすべてについて以下を実行
a.
各r∈PreDef(s,v), t∈target(r,v)に対して、vを定義しないようなパス
s, … , t が存在すれば、以下を実行
i.
ii.
3.
DD ← DD ∪ { s v t }
任意のr ∈ PreDef(s,v)に対してvを定義しないようなパスr, …, tが存在しなけれ
ば、
DD ← DD – { r v t | r ∈ PreDef(s,v)}
sで参照している各変数uすべてについて、
DD ← DD ∪ { r u s | r ∈ PreDef(s,v) }
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
挿入アルゴリズム
s1
s1: readln(x,y);
s2: max := x;
s3: if x>y then
max := x
else
s5: max := y;
s6: writeln(max);
1.
2.
3.
4.
5.
readln(x,y)
s2
x
x
y
y
max := x
x
s3
max
if x>y
s5
挿入する節点およびCDを作成
max := x
max := y
フロー辺引きなおし
maxを参照する文を探索しDDを
s6
max
追加
max
writeln(max)
挿入により不要となるDD削除
参照する変数のDD追加
DD
CD
Flow
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
修正アルゴリズム
アルゴリズムModifyVertex
1.
2.
3.
入力: 節点s, 変更後の定義変数集合V’, 変更後の参照変数集合U’
出力: 更新されたPDG
FLOW ← FLOW
v ∈ V – V’ に対して、
DD ← DD ∪ { r v t | r ∈ PreDef(s,v), t ∈ target(s,v) } – { s v t | t ∈
target(s,v) }
v’ ∈ V’ – V に対して、
1.
各r∈PreDef(s,v’), t∈target(r,v’)に対して、vを定義しないようなパスr,…,tが存在す
れば以下を実行
1.
2.
4.
5.
DD ← DD ∪ { s v’ t }
任意のr∈PreDef(s,v’)に対して、v’を定義しないようなパスr,…,tが存在しなければ、
DD ← DD – { r v’ t | t ∈ PreDef(s,v) }
u ∈ U – U’ に対して、
DD ← DD – { r u s | r∈PreDef(s,u) }
u’ ∈ U’ – U に対して、
DD ← DD ∪ { r u’ s | r∈PreDef(s,u’)}
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
関数間解析
1. 関数内変更を実行
2. 変更した関数内で「必ず定義される」「定義される
可能性がある」「参照される可能性がある」変数の
集合を計算
3. 他の関数に与える影響を計算し、変化があれば
依存辺を追加・削除（各関数の値が収束するまで
繰り返す）
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
実験
Pascalスライシングシステムに実装
削除約1060行
挿入約570行
実行結果
単位:秒 SparcStation20上
50行
100行
250行
430行
PDG再計算
0.08
0.35
1.42
16.61
削除
<0.01
<0.01
0.01
0.07
挿入・変更
<0.01
<0.01
0.01
0.05
単一関数
複数関数
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
まとめ
プログラムが変更された際に、プログラム全体を再解
析することなく、PDGを更新する手法を提案
実験により、PDG更新に要する時間を大幅に短縮
できることを確認
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
準動的情報を用いたプログラ
ムスライシング手法
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
静的スライシングと動的スライシング
解析コスト
静的＜動的
実行系列の保存 : 高コスト（実行時）
実行系列の解析 : 高コスト（解析時）
スライスサイズ
静的＞動的
静的スライシングでは全ての入力値を仮定
動的スライシングでは１種類のトレースを対象
実際の実行データを収集できるため、配列添字やポイン
タ解析も可能
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
静的情報と動的情報の結合
静的解析情報
＋
準動的解析
動的解析情報
効率的かつ効果的な解析
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
準動的解析
準動的解析のアプローチ
動的に経路情報を収集
コールマークスライシング（既存手法）
動的にデータ依存関係を収集
依存キャッシュスライシング
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
コールマークスライシング
依存関係
制御依存関係
データ依存関係
実行依存関係 ED（Execution Dependence）
ある文が実行されなければ、別の文は決して実行されない
実行時、関数呼び出し文が実行されたかどうか
（コールマーク）をセット
コールマークとEDを基に、実行されなかった文を
PDGから除外
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
コールマークスライシングの特長
実行されない文がスライスから除外される
⇒ 静的スライスより小さな（正確な）スライス
簡単なフラグと容易に計算できるCEDで実現可能
⇒ 実装が容易
実行時に収集する情報は呼び出し文が実行された
かどうかのみ
⇒ 実行時オーバヘッドの増加が少ない
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
コールマークスライシングの限界
配列・ポインタ・構造体変数の正確性は静的スライ
シングと同等
?
?
1:
2:
3:
4:
5:
6:
a[0]:=0;
a[1]:=3;
readln(b);
a[b]:=2; ?
c:=a[0]+4;
writeln(c);
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
依存キャッシュスライシング
データ依存関係に着目した準動的スライシング手法
制御依存関係
構文解析で容易に解析可能
⇒ 静的に解析
データ依存関係
静的に正確な解析は困難
⇒ 簡単なキャッシュを用い、動的に解析
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
依存キャッシュスライスの計算
1. 実行前解析: 節点と制御依存辺のみからなる
PDGのサブセットPDGDSを構築。変数にキャッシュ
を用意
2. 実行時解析: 変数が定義されれば、キャッシュに
文を設定。変数が参照されれば、キャッシュに保持
されている文からデータ依存辺を追加
3. 実行後解析: なし
4. スライス計算: PDGDSの辺を辿りスライスを抽出
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
アルゴリズムの概要
1.
2.
3.
静的制御依存関係解析
PDGの部分グラフPDGDSを静的に生成する．
まず，静的スライシングで利用するPDGと同様，文または制御文に対応する節点
を用意する．そして，文間に制御依存関係が存在すれば，対応する節点間に制
御依存辺を引く．ただし，PDGDSにデータ依存辺は加えない．
動的データ依存関係解析
対象プログラムをある入力データで実行する．
実行の際，次節で示すデータ依存関係抽出アルゴリズムに基き，動的なデータ依
存関係を計算し，PDGDSにデータ依存辺を追加する．プログラム実行が終了した
時点で，PDGDSの完成となる．
PDGDSによるスライス計算
PDGDSを用いて，静的スライシングと同様の方法でスライス計算を行う．
例えば，スライシング基準(sc, v)に関する依存キャッシュを抽出する場合，まず，sc
に対応する節点から制御依存辺およびvに関するデータ依存辺を逆向きに辿るこ
とで到達可能な節点集合を導出する．そして，この節点集合に対応する文が求
めるスライスとなる．
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
動的データ依存関係抽出アルゴリズム
入力
PDGBL: 部分的に生成されブロック化されたPDG
P: 対象プログラム
I: Pへの入力
作業変数
P中の各変数vに対する依存キャッシュC(v)
出力
OUT: 入力Iに対するプログラムPの実行の出力
PDGBL: 完成したPDG
アルゴリズム本体
1. P中の各静的変数vに対し, C(v) := Φ
2. Pが停止するまで以下を繰り返し実行する
{ Pを入力Iで最初から停止するまで文ごとに実行 }
a) Iに関して，Pの次の一文sを実行
b) sで使用(参照)される各変数uについて，
C(u) ≠Φかつ，データ依存辺
C(u) u sが存在しなければPDGBL
にC(u) u sを追加する．
c) sで定義される各変数wについて，C(w) := s
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
データ依存関係収集
キャッシュ内容
Input: b=0
b
a[0]
c
1:
2:
3:
4:
5:
6:
a[0]:=0;
a[1]:=3;
readln(b);
a[b]:=2;
c:=a[0]+4;
writeln(c);
a[0] a[1]
s1
s4
s2
b
c
s3
s5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
データ依存関係収集(2)
キャッシュ内容
Input: b=1
a[0]
b
c
1:
2:
3:
4:
5:
6:
a[0]:=0;
a[1]:=3;
readln(b);
a[b]:=2;
c:=a[0]+4;
writeln(c);
a[0] a[1]
s1
s2
s4
b
c
s3
s5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
依存キャッシュスライスの特長
簡単なキャッシュを用いることで、動的なデータ依存
関係を収集
⇒ 効率的かつ効果的なスライス
既存環境にキャッシュおよびDD辺構築機能を追加
することで実装可能
⇒ 実装が容易
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
実験
３つのプログラム
P1: カレンダー
P2：酒屋問題
P3：酒屋問題（拡張版）
について、
静的スライス
コールマークスライス
依存キャッシュスライス
動的スライス
を計算
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
実験結果～スライスサイズ
行
187
166
182
162
200
static
180
call-mark
160
dependence-cache
140
dynamic
120
100
80
61
60
40
20
21 17 15
5
16
8
5
0
P1
P2
P3
静的＞ CM ＞＞ DC ＞動的
P2・P3では配列変数を使用しているため顕著
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
実験結果～実行時解析時間
時間 6000
(ms) 5000
4000
3000
206464
static
4540
call-mark
4731
4700 4834
dependence-cache
dynamic
2000
1000
0
47 47 51 174
P1
43 43 45
P2
P3
静的 ≒ CM ≒ DC ＜＜動的
DCは僅かな実行時オーバヘッド増加で解析可能
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
まとめ
準動的手法を用いたスライシング手法「依存キャッ
シュスライシング」を提案
スライスサイズは静的スライシングより小さく、動的ス
ライシングより大きい
僅かな実行時オーバヘッドで、配列・ポインタ等を正
確に解析可能
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
むすび
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
まとめ
プログラム中の文間の依存関係解析に関して，解析を効率
化するための手法を提案した．
プログラムに変更が加えられた際の再解析を効率化し，インタラク
ティブなデバッグ作業を実現するプログラム依存グラフの効率的な
更新手法
静的解析情報と動的解析情報を組み合わせた準動的解析手法
を用いることにより，現実的な実行時オーバヘッドで高精度のプロ
グラムスライスを抽出できる依存キャッシュスライシング手法
提案手法についてそれぞれの有効性を確認
↓
デバッグ作業の効率化、ソフトウェア開発の生産性向上
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
今後の研究方針
作業者によるデバッグ作業における実験を通した評
価
実プログラムへの適用
PDG更新 … エイリアス解析等への対応
依存キャッシュスライシング … 他言語への実装
オブジェクト指向プログラムへの適用
継承・動的束縛などオブジェクト指向独自の概念への
対応
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University

Download Report