プログラム解析の効率化に関する研究

プログラム解析の効率化

に関する研究

大阪大学 大学院基礎工学研究科

情報数理系専攻 ソフトウェア科学分野

略歴

平成 9 年 3 月

大阪大学大学院基礎工学研究科 物理系専攻 情

報工学分野 博士前期課程修了 在学中はプログラムスライシ

ングに関する研究に従事

平成 9 年 4 月

日本電信電話株式会社 入社

平成 9 年 8 月

ヒューマンインタフェース研究所に配属 ビデ

オサーバの負荷分散技術の研究・開発に従事

平成 12 年 4 月

西日本電信電話株式会社 大阪支店に異動 中

規模 ERP パッケージの SI 業務

平成 13 年 10 月

大阪大学大学院基礎工学研究科 情報数理系

専攻 博士後期課程入学 プログラムスライシングに関する研

究に従事

平成 14 年 5 月

日本電信電話株式会社 サイバーソリューショ

ン研究所に異動 ディジタルコンテンツの著作権管理に関する

研究・開発に従事

論文一覧

プログラム依存グラフの効率的な更新手法

電子情報通信学会論文誌 (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

_発表

予定 )

発表内容

プログラム解析概要

プログラム依存グラフの効率的な更新手法

プログラムが変更された場合に、プログラム依

存グラフを再計算することなく、部分的に更新す

る手法

準動的解析を用いたスライシング手法

静的解析情報と動的解析情報を組み合わせた効

率的なスライシング手法

デバッグ作業におけるプログラム解析

ソフトウェア開発において、デバッグ・テス

ト・保守フェーズにおける比重はソフトウェ

アの大規模化に伴い増加している

デバッグ効率向上へのアプローチ

文間の

依存関係解析

によって特定の文に関連

のある文を抽出

依存関係解析はオーバヘッドが大きい

↓

解析の効率化が重要

プログラムスライス

注目した文に影響を与える（受ける）文の集

合

プログラム開発における様々なフェーズで利

用可能 ⇒ 特にデバッグフェーズ

開発作業の効率化を実現

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.

フォールト位置特定におけるプログラムスライス

スライス利用

スライスなし

被験者

A1

A2

A3

B1

B2

B3

デバッグ

時間

（分）

119

128

120

154

175

120

スライスなし

スライス利用

被験者

A1

A2

A3

B1

B2

B3

デバッグ

時間

（分）

118

126

155

131

92

120

実験１

実験２

122.3

149.7

133.0

114.3

西松 顕 , 西江 圭介 , 楠本 真二 , 井上 克郎 : `` フォールト位置特定における

スライスの応用

フォールト位置特定

プログラム再利用

プログラム理解

プログラム合成

プログラム編集

プログラム簡素化

など

スライスの分類

静的スライシング

プログラムを静的に（実行なしに）解析

動的スライシング

静的スライシング

プログラムを静的に（実行なしに）解析

全ての入力データを仮定

依存関係を基に

プログラム依存グラフ

(Program Dependence Graph, PDG)

を構築

依存関係

制御依存関係

ある文の実行有無が他の条件式の判定結果に依

存

データ依存関係

変数の定義 - 参照関係

s1: if a=0 then

s2: b :=1;

s1

s2

s3: a := 1;

s4: writeln(a);

s3

s4

a

プログラム依存グラフ

依存関係を表したグラフ

節点

文

を表す

文

条件式

特殊節点 （関数境界解析等）

辺

文間の依存関係

を表す

データ依存辺

制御依存辺

PDG

の例

x-para

Square-exit

x-para

Cube-exit

d := Square(a)

d := Cube(b)

d := -1 * d

Square := x * x

Cube := x*x*x

readln(a)

readln(b)

readln(c)

writeln(“Sq..

writeln(“Cu..

writeln(“Sel..

writeln(d)

if d<0

if c=0

Square

Cube

Main

x

x

Square

Cube

a

a

b

b

Cube

Square

d

d

d

d

c

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.

d

静的スライスの例

x-para

Square-exit

x-para

Cube-exit

d := Square(a)

d := Cube(b)

d := -1 * d

Square := x * x

Cube := x*x*x

readln(a)

readln(b)

readln(c)

writeln(“Sq..

writeln(“Cu..

writeln(“Sel..

writeln(d)

if d<0

if c=0

Square

Cube

Main

x

x

Square

Cube

a

a

b

b

Cube

Square

d

d

d

d

c

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.

d

スライシング基準

動的スライシング

プログラムをある入力データで実行する

注目した文に実際に影響を与えた文の集合

プログラムの

実行系列

を基に

動的依存グラフ

(Dynamic Dependence Graph, DDG)

を作成

動的スライスの例

x-para

Square-exit

Square := x * x

readln(a)

readln(b)

readln(c)

writeln(“Sq..

writeln(“Cu..

writeln(“Sel..

writeln(d)

if c=0

Square

Cube

Main

x

Square

a

a

Square

d

c

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.

入力 a=2, b=1, c=0 の場合

d := Square(a)

if d<0

d

静的・動的スライシングの特徴

静的スライシング

プログラムの実行を伴わな

い

長所

有効な入力データが無い

場合でも解析可能

短所

全ての入力データを仮定

した安全な近似が必要

配列変数・ポインタ等の

正確な解析ができない

動的スライシング

プログラムの実行が必須

長所

配列・ポインタ等も正確

に解析可能

短所

実行時オーバヘッドが大

きい

実行時間、メモリ空間

etc.

プログラム依存グラフの

効率的な更新手法

デバッグフェーズにおけるスライス利用

実行

解析 (PDG 計算 )

スライス計算

フォールト位置特定

ソース変更

デバッグ終了

大規模プログラムにおいては

解析のオーバーヘッドが大き

い

プログラムに変更が加えら

れた際に、プログラム全体

を再解析することなしに

PDG

を更新する手法が必要

提案手法

PDG

中の依存辺を基に変数の定義情報を復

元し、変更後の依存関係を計算することで

、変更の影響を受ける部分のみを更新

1.

制御依存辺更新

2.

関数内データ依存辺更新

3.

関数間影響解析

諸定義

対象言語

スカラ型のみからなる手続き型言語（ Pascal

サブセット）

PDG

通常の PDG に加え、フロー辺（実行順序を示

す辺）を持つグラフを対象とする

基本方針

制御依存関係は構文解析から更新

PDG

の DD 辺は解析時に変数の定義情報を基

にして引かれている．

⇒ 変更前の PDG 中の DD 辺から，変数の定

義情報の一部を復元することが可能．

これを利用し、変更後のデータ依存関係を求

め依存辺を更新

r

v

s

到達定義 <r,v>

提案するアルゴリズム

関数内解析アルゴリズム

文の削除

文の追加

文の修正 （基本的には削除＋追加）

関数間解析アルゴリズム

他関数に与える影響を解析

削除アルゴリズム

アルゴリズム 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) }

共通アルゴリズム

アルゴリズム 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

定義

文 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)

削除アルゴリズム

max := x

max := x

max := y

writeln(max)

readln(x,y)

x

x

_x

_y

y

max

max

s1

s2

s3

s4

s5

s6

if x>y

s1: readln(x,y);

s2: max := x;

s3: if x>y then

s4: max := x

else

s5: max := y;

s6: writeln(max);

r

s

t

max

max

max := x

max := x

max := y

writeln(max)

readln(x,y)

x

x

_x

_y

y

max

max

s1

s2

s3

s4

s5

s6

if x>y

max

max

1.

直前に max を定義している

文 r 、 s から DD を辿った

文 t を発見

2. r

から t へ DD を追加

3.

直前の文と直後の文間にフ

ロー辺を追加

挿入アルゴリズム

アルゴリズム InsertVertex

入力 : 挿入する節点 s, prev(s), next(s)

出力 : 更新された PDG

1.

FLOW ← FLOW {

∪ p → s | p ∈ prev(s) } {

∪ s → n | n

∈

next(s) } – { p → n | p

∈ prev(s), n

∈ next(s) }

2.

s

で定義している各変数 v すべてについて以下を実行

a.

各 r∈ PreDef(s,v), t∈ target(r,v) に対して、 v を定義しないようなパ

ス

s, … , t

が存在すれば、以下を実行

i.

DD ← DD {

∪ s

t }

i i .

任意の r

∈ PreDef(s,v) に対して v を定義しないようなパス r, …, t が存在

しなければ、

DD ← DD – { r

t | r

∈ PreDef(s,v)}

3.

s

で参照している各変数 u すべてについて、

DD ← DD {

∪ r

u

s | r

∈ PreDef(s,v) }

max := x

max

挿入アルゴリズム

max := x

max := y

writeln(max)

readln(x,y)

x

_x

_y

y

max

max

s1

s2

s3

s5

s6

if x>y

max := x

max := y

writeln(max)

readln(x,y)

x

_x

_y

y

max

max

s1

s2

s3

s5

s6

max := x

if x>y

x

s1: readln(x,y);

s2: max := x;

s3: if x>y then

else

s5: max := y;

s6: writeln(max);

1.

挿入する節点および CD を作

成

2.

フロー辺引きなおし

3. max

を参照する文を探索し

DD

を追加

4.

挿入により不要となる DD 削

max := x

修正アルゴリズム

アルゴリズム ModifyVertex

入力 : 節点 s, 変更後の定義変数集合 V’, 変更後の参照変数集合 U’

出力 : 更新された PDG

1.

FLOW ← FLOW

2.

v

∈ V – V’ に対して、

DD ← DD {

∪ r

v

t | r

∈ PreDef(s,v), t

∈ target(s,v) } – { s

v

t | t

∈

target(s,v) }

3.

v’

∈ V’ – V に対して、

1.

各 r∈ PreDef(s,v’), t∈ target(r,v’) に対して、 v を定義しないようなパス r,…,t が存

在すれば以下を実行

1.

DD ← DD {

∪ s

t }

2.

任意の r∈ PreDef(s,v’) に対して、 v’ を定義しないようなパス r,…,t が存在しなければ、

DD ← DD – { r

t | t ∈ PreDef(s,v) }

4.

u

∈ U – U’ に対して、

DD ← DD – { r

u

s | r∈ PreDef(s,u) }

5.

u’

∈ U’ – U に対して、

DD ← DD {

∪ r

u’

s | r∈ PreDef(s,u’)}

関数間解析

1.

関数内変更を実行

2.

変更した関数内で「必ず定義される」「定

義される可能性がある」「参照される可能

性がある」変数の集合を計算

3.

他の関数に与える影響を計算し、変化があ

れば依存辺を追加・削除（各関数の値が収

束するまで繰り返す）

実験

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

単一関数

複数関数

まとめ

プログラムが変更された際に、プログラム全

体を再解析することなく、 PDG を更新する

手法を提案

実験により、 PDG 更新に要する時間を大幅

に短縮できることを確認

準動的情報を用いたプログラ

ムスライシング手法

静的スライシングと動的スライシング

解析コスト

静的

＜ 動的

実行系列の保存 : 高コスト（実行時）

実行系列の解析 : 高コスト（解析時）

スライスサイズ 静的 ＞

動的

静的スライシングでは全ての入力値を仮定

動的スライシングでは１種類のトレースを対象

実際の実行データを収集できるため、配列添字

やポインタ解析も可能

静的情報と動的情報の結合

静的解析情報

動的解析情報

＋

効率的かつ効果的な解析

効率的かつ効果的な解析

準動的解析

準動的解析

準動的解析のアプローチ

動的に

経路情報

を収集

コールマークスライシング （既存手法）

動的に

データ依存関係

を収集

依存キャッシュスライシング

コールマークスライシング

依存関係

制御依存関係

データ依存関係

実行依存関係 ED （ Execution Dependence ）

ある文が実行されなければ、別の文は決して実行されな

い

実行時、関数呼び出し文が実行されたかどう

か（

コールマーク

）をセット

コールマークと ED を基に、実行されなかっ

た文を PDG から除外

コールマークスライシングの特長

実行されない文がスライスから除外される

⇒

静的スライスより小さな（正確な）スラ

イス

簡単なフラグと容易に計算できる CED で実

現可能

⇒

実装が容易

実行時に収集する情報は呼び出し文が実行さ

れたかどうかのみ

⇒

実行時オーバヘッドの増加が少ない

コールマークスライシングの限界

配列・ポインタ・構造体変数の正確性は静的

スライシングと同等

1: a[0]:=0;

2: a[1]:=3;

3: readln(b);

4: a[b]:=2;

5: c:=a[0]+4;

6: writeln(c);

?

?

?

依存キャッシュスライシング

データ依存関係

に着目した準動的スライシン

グ手法

制御依存関係

構文解析で容易に解析可能

⇒

静的に解析

データ依存関係

静的に正確な解析は困難

⇒

簡単なキャッシュを用い、動的に解析

依存キャッシュスライスの計算

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

は僅かな実行時オーバヘッド増加で解析可能

まとめ

準動的手法を用いたスライシング手法 「

依

存キャッシュスライシング

」 を提案

スライスサイズは静的スライシングより小さ

く、動的スライシングより大きい

僅かな実行時オーバヘッドで、配列・ポイン

タ等を正確に解析可能

まとめ

プログラム中の文間の依存関係解析に関して，解析を効

率化するための手法を提案した．

プログラムに変更が加えられた際の再解析を効率化し，インタ

ラクティブなデバッグ作業を実現するプログラム依存グラフの

効率的な更新手法

静的解析情報と動的解析情報を組み合わせた準動的解析手法を

用いることにより，現実的な実行時オーバヘッドで高精度のプ

ログラムスライスを抽出できる依存キャッシュスライシング手

法

提案手法についてそれぞれの有効性を確認

↓

デバッグ作業の効率化、ソフトウェア開発の生産性向上

今後の研究方針

作業者によるデバッグ作業における実験を通

した評価

実プログラムへの適用

PDG

更新 … エイリアス解析等への対応

依存キャッシュスライシング … 他言語への実

装

オブジェクト指向プログラムへの適用

継承・動的束縛などオブジェクト指向独自の概

念への対応