論 文
スライス計算効率化のためのプログラム依存グラフの節点集約法
大畑 文明y横森 励士y顯y; yy西松

井上 克郎y; yyy

Node Merging Method of Program Dependence Graph for EÆcient Slice Computationyy

Fumiaki OHATA , Reishi YOKOMORI , Akira NISHIMATSU

y; yy , and Katsuro

y; yyyINOUE

PDG

あらまし プログラム依存グラフ（）とはプログラム文間の依存関係を表す有向グラフであり，プログラ
ムスライスに利用される．これまで提案されている多くの構築法は，スライスの精度向上を目標としてきた．しかし ，大規模ソフトウェアにスライスを適用する場合，その精度だけでなく抽出の効率を考慮する必要がある
本研究では，依存情報が文単位で保持される従来手法に対し ，より大きな粒度で保持させることで効率向上を行ない，精度にも留意した構築手法を提案する．また，実際に提案手法の評価を行い，空間コスト，時間コストの削減を得た．

PDG

.

40%

キーワード

1.

5 { 60%PDG

10 {プログラムスライス，プログラム依存グラフ，効率，精度

28,000

存解析は多くの時間，空間を消費する．例えば，

まえが きプログラムスライス（ Program Slice ）は行のWeiser [6]C プログ ラムに対し 2 時間を要したとされる報[8]．我々はスライスを用いた対話形式のプロ

告もあるにより提案され ，プ ログラム保守，プログ ラム理解，

グラム解析ツールを求めており，依存解析のコストのプログラム統合 などに利用される．プログラムスライ

増大はその実現の妨げとなる．

スは，大きく静的スライス（ Static Slice ） ，動的ス（

[6][4] に分けられる．前者は入2 ） 依存解析の精度

スライス抽出はプログラム文間の依存関係に基づいライス（ Dynamic Slice ）力データを与えない静的解析に基づき，入力データのて行なわれるが，依存関係の抽出精度を高めるにはそすべての可能性を考慮した文間の依存関係が抽出されの解析コストの増大は避けられない．加えて，現在主る．後者は特定の入力データが与えられる動的解析に流となっているポインタ，配列を含む言語で記述され基づき，その入力データによる実行系列間の依存関係

たプログラムの解析はさらに困難となる．

が抽出される．本論文では静的スライスに着目し ，以プログラムを解析する場合，一般にこの効率に関して，我々は以下の

1 ） 依存解析のコスト

2 点に着目している．

{ 精度）はトレード オフの関係にあり，このトレー[2], [7]．本
研究では，プログラム依存グラフ（ PDG ）を用いてコストと精度のトレード オフを考える．PDG の構築はト

降，静的スライスを単にスライスと呼ぶ．
（

2 者（コスド オフに関して多くの研究がなされている

一般に，スライス抽出に必要となるプログラムの依スライス抽出に必要不可欠なものであり，その中でも，

y 大阪大学大学院 基礎工学研究科，豊中市

プログラム文間の依存関係把握のためのデータフロー

Graduate School of Engineering Science, Osaka University,

計算に多くの時間，空間を要する．

Toyonaka-shi, 560-8531 Japanyy アールスリーインスティテュート，大阪市

解析効率を高めるには様々な手法が考えられる．そGraduate School of Information Science, Nara Institute of
Science and Technology, Ikoma-shi, 630-0101 Japan

電子情報通信学会論文誌

1 つとして，通常各文の依存情報は PDG の対応す
1 節点に保持させるが，複数文の依存情報を 1 つのPDG 節点に保持させる節点集約による手法が考えらのR3 institute, Osaka-shi, 541-0057 Japanyyy 奈良先端科学技術大学院大学 情報科学研究科, 生駒市

XVol. Jxx{Xる

No. xxpp. 1{10xxxx

年 xx 月1

電子情報通信学会論文誌れる．この節点集約を用いることにより，

PDG 節点

1:
2:
3:
4:
5:

数は減少し解析コストの削減が期待できる．
本論文では，節点集約によるコスト削減手法を目的別に2 つ提案する．一つは精度の低下を抑えた空間コ
1

スト，時間コスト削減手法（ 手法 ），もう一つは空'xx/xx Vol. Jxx{X No. xx
b = 5;ba = b + b;a
if(a > 0)b = 5;
a = b + b;
if (a > 0) f
c = a;
d = b;gac = a;b

d = b;

CDDD

図 1 サンプルプログラム および その PDG

間コストが若干増加するが精度の低下のない時間コス2Fig. 1 Sample program and PDG

ト削減手法（ 手法 ）である．また，実際に我々が開発したスライスシステムに追加実装を行ないその有効性を評価した．いくつかのサンプルプログラムに対す

10 { 40%，時間コスト 5 {60%の削減が得られた．
以降，2. ではプログラムスライスについて紹介する．
3. では節点集約について述べ，4. で手法 1 を，5. で手法 2 をそれぞれ提案する．6. で提案手法の評価を行ない，7. でまとめと今後の課題について述べる．
る検証の結果，空間コスト

2.

1 ） s は v を定義する かつ，
2 ） t は v を参照する かつ，（ 3 ） s から t への 1 つ以上の実行経路の中に，vの再定義が起こらない経路が少なくとも 1 つ存在する
（

（

(

算は

プログラムスライス)

この関係を DD s; v; t と表す．制御依存関係の計

Phase 1 の結果および CFG から容易に行なうこ3とができる．しかし ，データ依存関係の条件（ ）のスライス計算にはさまざ まな手法が存在するが，本判定には，手続き呼び出しやポインタ 等の解析が必要

研究ではプログラム依存グラフによるスライス抽出技

不可欠であり，繰り返し文，再帰呼び出しによる再帰法

的な依存関係も存在するため，スライス抽出過程の中[3] に着目する．以下，各フェーズを簡単に述べる．

ただし ，ソースプログラムの構文解析，意味解析によでも最も計算量を必要とする．

りコント ロールフローグラフ（ Control Flow Graph ，[1] が得られているものとする．なお，本論文

CFG ）で対象とする言語はポインタのない手続き型言語とす

Phase 3: プログラム依存グラフの構築

Phase 2 で抽出された依存関係を利用し ，プログラる．ポインタを含むプログラムに対しては，既に提案

ム依存グラフを構築する．プログラム依存グラフ

されているポ インタ解析手法（ Program Dependence Graph ，PDG ）[5] を併用することで適用可能である．
Phase 1:

グラムに存在する文を節点，文間の依存関係（データ依存関係，制御依存関係）を辺で表現した有向グラフ

定義，参照変数の抽出プログラムの各文で定義，参照される変数を抽出する．このフェーズはプ ログ ラム文の1 回の走査で終わる．
Phase 2:[3] は，プ ロ

依存関係解析

Phase 1 の結果を元に，プログラム文間の，次に示
す 2 つの依存関係を抽出する．
ソースプ ログ ラム 中の 2 文 s，t に 関し て ，以下の条件を満たすとき，s から t の間に 制御依存関係[3] が存在するという．

（ Control Dependence ，CD ）1 ） s は条件文（ 節） かつ，
2 ） t の実行は s の判定結果に依存する
この関係を CD(s; t) と表す．また，以下の条件を満1 にサンプルプログラムおよびその PDGを示す．PDG は Phase 2 で抽出された依存関係からである．図

容易に構築可能である．
Phase 4:

スライスの抽出

スライス基準に対するスライスを抽出する．スライ,ス基準（ Slicing Criterion ）は対 <s v> で示され．sは文，v は s で定義もし くは参照され る変数を表す．

,
PDG 中の節点 Vs から，逆方向に制御依存辺

スライス基準 <s v> に対するスライスとは，s に対応した（

およびデータ依存辺を経て推移的に到達可能な節点集（合に対応する文の集合をいう．図

たすとき，s から t の間に変数 v に関するデータ依存[3]

関係（ Data Dependence ，DD ） が存在するという．
22 に図 1 のスライス
基準 < 文 5, b> に対するスライス (太枠部，文 1，2，
3，5) を示す．スライスの抽出は PDG を辿るのみであるため，依存関係解析に比べそれに要する計算量はわずかである．

論文／スライス計算効率化のためのプログラム依存グラフの節点集約法

b = 5;ba = b + b;a
if(a > 0)ab

図2c = a;
d = b;

1:
2:
3:
4:
5:

b = 5;
a = b + b;
if (a > 0) f
c = a;
d = b;g

図 1 のスライス基準 < 文 5, b> のスライス

Fig. 2 Slice of slicing criterion (5, b) for Fig.1

3. 2

局所依存関係

以下の条件のいずれかを満たす場合，文 s は文 t に対に関する局所依存関係（ Local Dependence ，

し変数

LD(s; ; t) と表す．なお，前LD ）が成り立つといい，

述のとおり，局所依存関係はデータ依存関係および 制
御依存関係を組み合せたものであり，変数る文 s およびそれを参照する文 t 間には， の再定義

1 つ存在することが前提が起らない経路が少なくとも
3.

節点集約

3. 1

方

を定義す

となる．

1 ） 文 s で変数 が定義され ，文 t で変数 が参照される．
（ 図 3(a) ）（ 2 ） 変数 を参照し 変数 を定義する文 u が存
（

通常

針

Phase 2 に最も手間がかかる．我々は，この依存関係解析の手間を小さくするための手法として，節（ 以降，単に集約と呼ぶ）を点集約（ Node Merging ）提案する．本手法を用いることにより，情報の共有による情報量（ 空間コスト ）削減や，節点数の減少による計算量（ 時間コスト ）削減が期待できる．
集約の方針を次に示す．なお，非集約 PDG（ Nonmerged PDG ）とは 従来手法で用いられ る集約のな

在し，かつ文 s が3(b) ）（ 3 ） 変数を 参照する条件文（ 繰り返し 文 ）u( )（ CD u; t ），かつ文 s は変数4 ） 文 s と文 t は同じ 文であり，かつ文 t は変数
3(d) ）
局所依存関係の抽出は Phase 1 および CFG から得を定義する．
（図PDG を用いと呼ぶ．

3(c) ）

する変数という．
（（ Non-merged Slice ），集約スライス（ Merged Slice ）を定義する．
（図を，文 t を 支配（ Control ）なお，このような変数（ Merged PDG ）とは今回提案する集約が行われたプ
ログ ラム依存グ ラフである．また ，各を参照する．
（図が 存在し ，文 t はその 分岐節（ 繰り返し 節 ）であり

いプ ログ ラム依存グ ラフである．一方，集約 PDGて抽出されるスライスをそれぞれ ，非集約スライスを定義し文 t がられる情報を用いることで可能であり，一段の間接依存まで調べている．多段の間接依存を認めることも可能であるが ，計算コストの増大が 予想され るため行（1 ） 集約は Phase 1 および Phase 2 と独立したフェーズで行ない，Phase 1，Phase 2 の変更は最小

なっていない．また，局所依存関係は後述する集約可限に抑える．

はない．

2 ） Phase 1 および CFG から得られる情報のみ
Phase 2 に渡す．
（ 3 ） 方針 (1)，(2) に関連するが，集約は後述する（を用いて集約を行ない集約条件が成り立つ連続文に限定する．また，手続き
呼び出し文およびそれを内包する制御文は集約対象としない．

4 ） 同じ スライス基準に対し ，非集約 PDG を用
A には含まれなかった文が，集約 PDG を用いて抽出されたスライス B に含まれること（精度の低下）があるが，スライス A に含まれる文は必ずスライス B に含まれる．
（ 5 ） 局所依存関係という，データ依存関係，制御（

いて抽出されたスライス

依存関係を組み合わせた依存関係を新たに定義し 節
点集約に利用する．局所依存関係については次節で述べる．

PDG 辺として存在すること否判定にのみ用いられ，
3. 3

節点集約

2 つ以上の直結する文を対象と2 文の集約に関してのみ述べる．この手法を繰り返し適用することで 3 文以上の集約もできる．なお，離れた 2 文にも同様の方法は適用可能であるが，Phase 2 { 4 の実装への変更が必
集約はプログラムのしており，ここでは連続する要であり対象としていない．

集約条件となりあ う2 文 x，y に つ い て ，文 x は 変 数

X1 ; X2 ;    ; Xm を参照，文 y は 変数 Y1 ; Y2 ;    ; Yn

を 参 照 し て い る と す る ．い ま 変 数 集 合 Vf

X1 ; X2 ;    ; Xm ; Y1 ; Y2 ;    ; Yn g に 属する各変数 v

(

)

(

)

に関して，LD s; v; x ^ LD s; v; y を満たす文 s がそれぞれ存在する場合，あるいは文 s が存在しないよ
うな変数がある場合でもその個数が limit 個以下であ3電子情報通信学会論文誌sα = ... ;s

α = ... ;αa = 1; c = 1; d = 1;adif(a > 0)
c
c
d
a

α

... = ... α ... ;t... = ... α ... ;

t

1:
2:
3:
4:
5:
6:
7:
8:

(a)
s
α

u

α = ... ;s

α = ... ;αβ = ... α ... ;β t... = ... β ... ;t... = ... β ... ;(b)s

α = ... ;s

α = ... ;αif(... α ...)t... ... ;t... ... ;a = 1;
b = 1;
c = 1;
d = 1;
if (a > 0) f
e = b;
f = c * d;g = f + c + d + a;

f = c * d;s, tα = ... ;s, t

α = ... ;g = f + c + d + a;a = 1; c = 1; d = 1;adif(a > 0)
a
c
c
d
a

g

α

f

(b) DD，CD による依存グラフ（ PDG の一部）

9: h = g;
10: i = e;αu'xx/xx Vol. Jxx{X No. xx

f = c * d;g = f + c + d + a;
f s2
s1(a) プログラム(c) LD，CD による依存

グラフ

(c)

図4 節点集約
Fig. 4 Merging Nodes

(d)
CD
DD
LD

集約の程度は limit 値（ limit 

図 3 局所依存関係
Fig. 3 Local Dependence Relation

れば ，文 x，y を小さくすることで集約は抑えられる．コストと精度は

1 節点に集約する．

トレード オフの関係にあり，目的に応じた limit 値の選定が必要となる．本論文では，その中でも特徴的な

集約例

4(a) のプ ログラムの文 7，8 に対する limit = 0
で の 集 約を 例に 挙げ る ．図 4(b) は DD，CD に よる依存グ ラフ，図 4(c) は LD，CD による依存グ ラ
フであ る（ ただし いずれ のグ ラフも，文 7，8 に 関
図連す る 依 存辺および その 辺に 接す る 節 点か ら な る
部分グ ラフである ）．変数 c，d は 文

7 で ，変数 f ，c，d，a は 文 8 で 参 照 され て い る ．変 数 c に 関し
(3; c; 7) ^ LD(3; c; 8)，変 数 d に 関し て も 同様に LD(4; d; 7) ^ LD(4; d; 8) が 成り立つ．変数 f ，a それ ぞ れ に ついて も ，LD(7; f; 7) ^ LD(7; f; 8)，LD(1; a; 7) ^ LD(1; a; 8) が 成り立つ．それ ゆえ ，2て LD

7 8 1 節点に集約する．

文 ， を

ここでは説明のため依存グラフを用いたが，集約対(象を直結する文に限定していることで LD s;; t) の

文 s に該当する文を把握する必要はなく（ 集約対象文

で同一識別子の変数が参照されている場合，その変数を定義した文は同じである．ただし ，集約対象文内でその変数が再定義される可能性があるが，その把握は容易である），集約判定は変数の集合演算に置き換え[9]ることができる．

集約の制御40 ）により制御さ

れ ，limit を大きくすることで集約は進み，limit を

limit 値に着目し ，先に述べた節点集約手法を拡張した

2 つの集約方法を提案する．


精度の低下を抑えた時間コスト，空間コスト削減のための，依存関係の局所性を利用した節点集約法

1（ 手法 ，limit  1 ）


空間コストは若干増加するが精度の低下のない

時間コスト削減のための，節点分解をともなう節点集

2

約法（ 手法 ，limit

=

1

）

その他の limit 値に関しては，特性を見い出せなかったため今回は扱っていない．また limit  1 の具体

6. では 0, 1, 2 を評価対象としている．

的な値として，
3. 4

集約アルゴリズム

集約の判定には，集約対象文に関する以下のような情報が必要であるが，


定義，参照される変数名

分岐節（ 繰り返し節）内の文かど うか

となりあう文の情報

これらの情報は

Phase 1 および CFG から取得できる．

3. 3 では連続文の集約判定を例に挙げて説明したが，集約はプログラム構造に依存するため，連続文以外にも，ブロック，分岐文，繰り返し 文の集約アルゴ リズム（ 集約判定 および 集約手続き）を考えた[9]．これ論文／スライス計算効率化のためのプログラム依存グラフの節点集約法

らは我々が開発したシステムに2 間）として実装されている．
4.

Phase 1.5（ Phase 1 {a = 1; b = 1; c = 1; d = 1; h = g; i = e;
c d
d
a
a
if(a > 0)cebge = b;

依存関係の局所性を利用し た節点集約法（ 手法 1 ）f = c * d;a = 1; b = 1; c = 1; d = 1; h = g; i = e;cadaif(a > 0)ebge = b;
f = c * d;g = f + c + d + a;について述べる．本手法により，精度の低下を抑えた
時間コスト，空間コストの削減を得ることができる．

[9] で述べられており，ここでは主要部分のみ

紹介する．
4. 1

依存関係の局所性(b) 集約 PDG

依存関係の局所性（ Dependency Locality ）とは，直図5

観的には対象となる複数文が持つ依存関係の類似性を表したものであり，limit  1 で集約可能な文にその性質が現れる．複数文をスライス基準 < 文 9, g> のスライス

Fig. 5 Slice of <9, g>

1 節点に集約することを考

a = 1; b = 1; c = 1; d = 1;aif(a > 0) b c cd d

えたとき，集約対象文に関するすべての依存関係を集約節点に委譲させる必要があるが，単純に連続文を集

PDG をスライス抽出に利用するとスライスの精度は著し く低下してし まう．しかし ，limit = 0 のとき集約可能な 2 文 s，t は 共に同じ文集合 に局所約したU依存しているため，言いかえると，同一の文集合 U に依存する文 s，t を集約しているため，集約による精度の低下を抑えることができる．

if(b > 0)

1:
2:
3:
4:
5:
6:
7:
8:

依存関係の局所性による集約の例

4(a) の サンプ ルプ ログ ラムに 対する ，非集約
PDG，集約 PDG（文 7，8 を limit = 0 で集約）を図
5(a)，(b) にそれぞれ示す．スライス基準 < 文 9, g>
に対するスライスを非集約 PDG および 集約 PDG を用いて抽出したとき，文 7，8 が依存関係の局所性を有することから，非集約 PDG によるスライス（ 文 1，
3，4，5，7，8，9 ）と同じ スライスが集約 PDG でも

a = 1;
b = 1;
c = 1;
d = 1;
if (a > 0)
if (b > 0) f
e = c + d;
f = c * d;g

図抽出されていることが分かる．

limit = 0 の集約で精度の低下が起こる状況は 2 つ存在する．1 つは，文 s，t のいずれかのみ非集約スラ

g = f + c + d + a;(a) 非集約 PDG

本節では，依存関係の局所性を利用した節点集約法

詳細はf

f = c *d; e = c + d;(a) 非集約 PDG
a = 1; b = 1; c = 1; d = 1;ab cdif(a > 0)if(b > 0) {e = c + d;
f = c * d;}(b) 集約 PDG

図 6 集約節点からのスライス

Fig. 6 Slice of merged node

るスライスの精度が著しく低下する可能性がある（ 集約節点で定義される変数をスライス基準としたときや，

PDG 探索中に集約節点に到達したときには，このような問題は生じない）．集約により集約前節点間に存在した制御依存に関する情報は失われ，定義変数は当然であるが参照変数であっても，すべての参照変数に

6で2 から 8 に増加してイスに含まれるようなスライス基準に対し集約スライ

依存していると解釈せざ るを得ない．例えば ，図スを抽出するときである．このとき，集約スライスはは集約によりスライスサイズが

文 s，t いずれも含むことになる．もういる．

1 つは ，集約

節点で参照のみされる変数をスライス基準としたときである．こちら関しては
4. 2

支 配

4. 2 で述べる．

表

limit  1 の集約により，スライスの精度低下を抑この問題を解決するため，同一集約節点に存在する
参照変数間の支配関係を記憶する支配表を集約節点に持たせた．支配関係（ Control Relation ）とは，変数が条件節で参照され変数が対応する述部で参照さえた集約を行なうことができる．しかし集約節点で参れるとき 〜 間に存在する関係をいう．また， が照のみされる変数をスライス基準としたとき，得られを支配するともいう．前述のとおり，集約節点内の5電子情報通信学会論文誌

支配 n 被支配
a
b
c
d

a

b

c

d

p p
p p p
p
p

a = 1; b = 1; c = 1; d = 1;ab cdif(a > 0)if(b > 0) {e = c + d;
f = c * d;}

図 7 支配表と集約節点からのスライス'xx/xx Vol. Jxx{X No. xx

解析範囲が大きい（2 ） 局所的な依存関係 . . . 手続き内で閉じた依存関係や非再帰的な依存関係などを指し ，その抽出に要する解析範囲が小さい
前述のとおり，スライス抽出過程の中でも最も時間計

Fig. 7 Control table and slice of merged node

算量を要するのはデータ依存関係の抽出であるが，それは大域的な依存関係の存在によるものが多い．そこ

制御依存に関する情報は破棄されるため，この支配関で，limit=

1

での集約により大域的な依存関係の抽係でその役割を補う．また，支配表（ Control Table ）出対象となる節点を可能な限り減らし ，その抽出コスとはトを削減させる．一方，集約によりn 行 n 列（ n は各集約節点の参照変数の数）の表

であり，支配関係の存在する組にはpで，存在しない

組は空欄で表す．支配表は集約時に逐次更新され，集係に該当し ，分解時にそれら節点間の依存関係解析の

約節点の参照のみされる変数 a がスライス基準となっみ行うことで抽出可能である．

ている参照変数を把握できる．

節点分解をともなう節点集約の例

たとき，支配表を参照することで変数 a が真に依存しれ自身にのみ依存していることが分かり，スライスサ
イズは8 から 5 に減少している．

8(a) は Phase 1 終了後の手続き P，Q を表して
Phase 1.5 の limit = の節点集約により図8(b) となる．その後 Phase 2 { 3 により図 8(c) の集
約 PDG が構築される．手続き Q は手続き P から呼び出されており，かつその呼び出し文はwhile 文の繰

節点分解をともなう節点集約法（ 手法
2）を少なくとも図

7 に，図 6 の集約節点の支配表およびそれに基づ

1 つの集約節点にまとめられていた節点間の依存関係は局所的な依存関き抽出された集約節点（ 網掛部）の変数 a のスライス（ 太枠部）を示す．支配表から集約節点の変数 a はそ

図

おり，

1

集

Q 内の依存関係解析
2 回行わなければならない．しかし ，手続き Q 内を limit =で集約することでデータ依存
解析の対象節点が減り，手続き P から手続き Q にお約による，精度の低下を抑えた節点集約法を提案した．

よぶ大域的な依存関係解析のコスト削減が得られる．

依存関係の局所性を利用した集約では，空間コスト，時8(d) の非集約 PDG が再構成される．ここでは説明のため比較的単純な例を用いたが，手続き Q がより大規

5.

4. では，依存関係の局所性を有する limit

 1間コストの削減を行うことができる．一方 limit=1とすると，コスト削減は十分に期待できるが，精度の= の集
PDG を構築後，その集約節点を分解する手

大幅な低下は避けられない．そこで，limit
約による

1

り返し節に存在するため，手続き
1

最後に集約節点内の局所的な依存関係解析を行い，図模である場合や，再帰呼び出し経路に含まれている場
合，集約によるコスト削減の効果はより大きなものと法が考えられる．この手法は，節点の分解を考慮するなる．

必要があるため空間コストが若干増加するが，精度の5. 2低下のない時間コスト削減を行うことができる．また分解アルゴリズム

limit = 1 の節点集約により構築された集約 PDG

limit = 1 では局所依存関係を抽出する必要はなく，に対し ，各集約節点内部で分解アルゴ リズムを適用

集約可能な文（ 手続き呼び出し文およびそれを内包す

し 非集約る制御文以外）はすべて集約される．
5. 1

節点分解

Phase 1.5

節点分解（ Node Decomposition ）とは，を経て構築された集約

PDG の集約節点を分解し ，そPDG をの内部の依存関係のみ解析することで非集約再構成することをいう．
ここで，データ依存関係を以下の（2 つに分類する．

1 ） 大域的な依存関係 . . . 手続きをまたぐ 依存関係や再帰的な依存関係などを指し ，その抽出に要する
6

PDG を再構成する．分解アルゴ リズムは，

Phase 2 の依存関係解析アルゴ リズムとほぼ同じものとなっている．異なるのは，集約前節点に関する依存関係は対応する集約節点が 代わりに 保持し ているた
め，集約節点内部の依存関係解析後，集約節点に関する依存関係を分解後（ 集約前）の節点に分散（ 図8(c){ 図 8(d) ）させなければ ならない点である．依存関係の分散が終わると，これらの依存関係を元に非集約

PDG の再構成を行う．分解アルゴ リズムは Phase 3.5（ Phase 3 { 4 間）として実装されている．

論文／スライス計算効率化のためのプログラム依存グラフの節点集約法
PQP

a = 1;

while(a < 10)while(a < 10)c = a;

b = a;(a) Phase 1a(b) Phase 1.5

Q
a = 1;
aawhile(a < 10) a
b = a;
Q();

a += c;

Q();

P

a

Q

c = a;

b = a;
aa += c;Q();(c) Phase 2 { 3a c = a;ca += c;(d) Phase 3.5(節 点 分

Fig. 8 Node decomposition

6.

評

価

6. 1

実

験

[10] 上[11] による．

5 種類の PDG の比較を行った．

N 集約なしL 依存関係の局所性を利用した節点集約（ 手法 1，
limit = 0 ）L 依存関係の局所性を利用した節点集約（ 手法 1，
limit = 1 ）L 依存関係の局所性を利用した節点集約（ 手法 1，
limit = 2 ）C 節点分解をともなう節点集約（ 手法 2 ）今回使用したテストプログラムを表 1 に，PDG 節点
数を表 2 に（ 括弧内は集約節点数を表す），PDG 辺数を表 3 に，支配表のセル数を表 4 に，節点数，辺数，
支配表セル数の単純和を表 5 に，PDG 構築までの時
間 (Phase 1 { 3 の合計時間，集約，分解を行う場合はPhase 1.5，Phase 3.5 もそれぞれ含まれる) を表 6 に，
平均スライスサイズ (テストプログラムの各手続きで
0

1

2

最後に参照される変数をスライス基準として選び ，そ)れらのスライスに含まれる文数の平均 を表考166(22)153(27)136(28)231(20)199(19)187(24)177(28)270(27)

P4 503 459(124) 419(150) 409(165)

547(44)

P2 211( 29.59%) ( 32.54%) ( 39.05%) (+6.51%)( 21.33%) ( 27.49%) ( 35.55%) (+9.48%)( 18.11%) ( 23.05%) ( 27.16%) (+11.11%)

表 3 PDG 辺数
Table 3 Number of edgesに実現した．依存関係解析アルゴ リズムは

6. 2

内容
チケット予約酒屋問題
小計算問題の集合
ソーティング( 8.75%) ( 16.70%) ( 18.69%) (+8.75%)

提案手法を我々が開発したスライスシステム
実験は以下に示す

14
18
30
22

C
180(11)N
P1 169P3 243解)

図8 節点分解

手続き

333
429
449
831

表 2 PDG 節点数
Table 2 Number of nodes
L0
L1
L2
119(26) 114(27) 103(34)a = 1;
aawhile(a < 10)

a

行

P1
P2
P3
P4

c = a;

b = a;

a += c;Q();P

表 1 テストプログラム
Table 1 Sample programsQ
a = 1;P1N935

P2 1487
P3 1092
P4 3360

L1

817

L2

774

( 10.91%) ( 12.62%) ( 17.22%)

C
935

1387

1336

1290 1487

980

951

912 1092

3135

2791

2750 3360( 6.72%) ( 10.15%) ( 13.25%)( 10.26%) ( 12.91%) ( 16.48%)( 6.70%) ( 16.93%) ( 18.15%)

表 5 節点，辺数，支配表セル数の和
Table 5 Sum of nodes, edges and cells of control tables
N
L0
L1
L2
C
P1 1104 1011 1018 1053 915
P2 1698 1634 1614 1609 1704
P3 1335 1205 1183 1191 1081
P4 3863 3744 3442 3396 1811

セルは真偽の2 値のみ保持し ，辺，節点に必要な情報量に比較すると十分に小さい．節点分解をともなう節

空間コスト（ PDG サイズ ）PDG 節点数は 10 { 40%（ 表 2 ），PDG 辺数は 10 { 20%（ 表3 ）の削減が得られた．L { L には今回新たに定義した支配表が導入されているが（ 表 4 ），支配表の各
局所依存関係による節点集約に関して，
0833

表 4 支配表セル数
Table 4 Number of cells of control tables
N L0 L1 L2 C
P1 0 59 87 176 0
P2 0 81 125 183 0
P3 0 26 45 102 0
P4 0 150 212 237 07 に示す．

察L0

2

2 に示すように集約前節点の保存のた
N および L と比較すると，それぞれ約 10%，約 40%の増加となっている）．
点集約では，表め節点数が増加している（1

時間コスト（ PDG 構築時間）
7電子情報通信学会論文誌

L では P のスライスサイズの大幅な増加が確認され

表 6 PDG 構築時間 [ms]Table 6 PDG construction time[ms]L080.789N
102.53

P1
P2

191.01

P3

187.84

L2
74.48

C69.258161.792

157.557

150.603129.192

161.494

156.074

147.365

157.712708.597607.979585.679

281.638( 15.30%) ( 17.51%) ( 21.15%) ( 32:36%)( 14.03%) ( 16.91%) ( 21.55%) ( 16:04%)

4( 4.14%) ( 17.75%) ( 20.77%) ( 61:90%)5（ 表 ）を考えたとき，limit
たものが limit= 1 まで減少傾向であっ= 2 で増加傾向に変化している．これ
3 点を考慮すると，

ら精度，時間コスト，空間コストのlimit = 1 を妥当な値として導き出すことができる．

今回は実装の言語制約のため，比較的規模の小さいプ ログ ラムに 対する実験のみであった ．残念ながCeleron-450MHz-128MB(FreeBSD)

ら，現時点では存在するすべてのプログラムに対して

表 7 平均スライスサイズ [文]Table 7 Average slice size[# statements]

現在開発中のシステムに本手法を適用することで大規

N
94.21

P2 143.22
P3

2ている．一方，節点数，辺数，支配表セル数の単純和( 21.21%) ( 21.42%) ( 27.38%) ( 32:45%)

P4 739.172

P1

L1
80.573'xx/xx Vol. Jxx{X No. xx

46.80

P4 173.43

模プログラムに対する検証も行いたいと考えている．

L0
95.21

L1
95.21

L2
95.21

C
94.21

プログラムスライスに関してさまざ まな研究がなさ

145.00147.44148.28 143.22

れている．解析コストと スライス精度とのトレ ード

48.27

48.27

52.50

オフに関するものとしては

178.52178.57178.57 173.43(+1.06%) (+1.06%) (+1.06%)(+1.24%) (+2.95%) (+3.53%)

46.80(+3.13%) (+3.13%) (+12.18%)(+2.94%) (+2.97%) (+2.97%)

6. 3

関連研究

[2], [7] がある．これらは，ユーザが解析コストとスライスの精度を操作できるシステムを開発しているが，解析方法全体を変更することでトレード オフを考慮している．

依存関係の局所性を利用した節点集約に関して，解析時間はlimit = 1 が有効であると断定することはできないが，

5 { 30%の削減が 得られた（ 表 6 ）．また，集約に要する時間はいずれのプ ログ ラムに対し ても10[ms] 以下であった．

[8] では完全に相互依存する節点のみの集約を行なっている．我々の手法は，相互依存しなくとも同じ 依存関係を持つ節点であれば集約を行なう．また，limit 値を変更することで解析コストとスライス精度のトレード オフが制御可能である．

節点分解をともなう節点集約に関して，解析時間は15 { 60%の削減が得られた（ 表 6 ）．limit =1の集約により，解析時間の大半を占める大域的な依存関係の解析時間が削減されたためである．一方，局所的な依存関係の解析に要する計算コストは少なく，分解に要する時間はP で 70[ms] であった．
4

7.

まとめと今後の課題

節点集約による

PDG 構築コスト削減手法を 2 つ提案し，その有効性を実験により評価した．依存関係の局所性を利用した節点集約法は，スライスサイズが大きくなる副作用が存在するが，その増加はわずかであり，空間コスト，時間コストの削減が可能である．コ

精度（スライスサイズ ）非集約スライスと比べ集約スライスのサイズは多少

ストと精度のトレード オフは limit 値により制御可能= 1 が最も有効であると思わ大きくなる．しかし ，依存関係の局所性を有する文ので，実験結果から limit

み集約するため，スライスの精度が大きく低下するこれる．節点分解をともなう節点集約法は，空間コストとはない．表が増加するが精度の低下の無い時間コスト削減を行う

7 で示されているように，L ，L とも0

1

1 { 3%程度のスライスサイズ増加で抑えられている．

ことができる．これらの手法はそれぞれ特徴を持っており，ユーザの要求に応じ た使い分けが可能である．

これらの実験結果から，依存関係の局所性を利用した節点集約では limit= 1 が最も有効であると考えら

例えば ，限られた計算機資源で大規模プログラムを解析する場合，依存関係の局所性を利用した節点集約法

れる．

が有効であろう．

の短縮は期待できるが反対にスライスサイズは増加す

ライスシステムおよびプログラム理解ツールの開発をる． 0 と行っている．また，ソフトウェア開発工程でのスライ

limit 値が 0，1，2 と大きくなるにつれ ，解析時間

L

L 間では スライスサイズに影響をほとん
1

ど 及ぼすことなく解析時間の短縮が得られているが ，
8

本研究をふまえ，Java を対象言語とする新しいス

スシステムの有効性をこのシステムを用いて評価する

論文／スライス計算効率化のためのプログラム依存グラフの節点集約法

大畑

予定である．

平 10 阪大・基礎工・情報中退．平 12 同大大学院修士課程了．現在同大学院博士

謝辞 本研究は，一部文部省科学研究費補助金特定領域研究(A)(2)(課題番号:10139223) の補助を受けて課程在学中．プログラムスライスの研究に
従事．

いる．

文

文明

献

[1] Aho, A.V., Sethi, S. and Ullman, J.D., \Compilers :Principles, Techniques, and Tools", Addison-Wesley,
1986.
[2] D. C. Atkison, W. G. Griswold, \The design of wholeprogram analysis tools," in Proceedings of the 18th
International Conference on Software Engineering,pp.16{27, Berlin, Germany, 1996.
[3] Horwitz, S. and Reps, T., \The use of program dependence graphs in software engineering," in Proceedings of the 14th International Conference on
Software Engineering, pp.392{411, Melbourne, Australia, 1992.
[4] Korel, B. and Rilling, J., \Dynamic program slicing
methods". In Information and Software Technology
Special Issue on Program Slicing, vol.40, pages 647{
659, 1998.
[5] M. Shapiro, and S. Horwitz, \Fast and accurate owinsensitive point-to analysis," in 24th Annual ACM
SIGACT-SIGPLAN Symposium on the Principles ofProgramming Languages, 1997.
[6] M. Weiser, \Program slicing," in Proceedings of the
5th International Conference on Software Engineering, pp.439{449, San Diego, USA, 1981.
[7] P. Tonella, G. Antoniol, R. Fiutem and E. Merlo,\Variable precision reaching de nitions analysis forsoftware maintenance," in Proceedings of the Euromicro Working Conference on Software Maintenance and Reengineering, pp.60{67, Berlin, Germany, 1997.
[8] The Wisconsin Program-Slicing Tool 1.0, Reference
Manual. Computer Sciences Department, Universityof Wisconsin-Madison, 1997.
[9] 大畑, 西松, 井上, \依存関係の局所性を利用したプログラム依存グラフの効率的な構築法," 情処学研報, 99-SE-122,
pp.17{24, 1999.
[10] 佐藤, 飯田, 井上, \プログラムの依存解析に基づくデバッグ
支援ツールの試作," 情処学論, vol.37, no.4, pp.536{545,1996.
[11] 植田, 練, 井上, 鳥居, \再帰を含むプログラムのスライス計算法," 信学誌, vol.J78-D-I, no.1, pp.11{22, 1995.

横森

励士

平 11 阪大・基礎工・情報卒．平 13 同大
大学院修士課程了．現在同大学院博士課程在学中．プログラムスライスの研究に従事．

西松顯

平 9 阪大・基礎工・情報卒．平 11 同大
大学院修士課程了．現在アールスリーイン
スティテュート勤務．在学中，プログラム
スライスの研究に従事．

井上克郎 （ 正員）

昭 54 阪大・基礎工・情報卒．昭 59 同大大学院博士課程了．同年同大・基礎工・情報・助手．昭 59〜昭 61 ハワイ大マノア
校・情報工学科・助教授．平 1 阪大・基礎

工・情報・講師．平 3 同学科・助教授．平7 同学科・教授．工博．ソフトウェア工学の研究に従事．

（ 平成年月日受付，月日再受付）

9電子情報通信学会論文誌

Fig.1
サンプルプログラム および その

PDG

Sample program and PDG
Fig.2
図 1 のスライス基準 < 文 5, b> のスライス
Slice of slicing criterion (5, b) for Fig.1
Fig.3
局所依存関係

Local Dependence Relation
Fig.4
節点集約

Merging Nodes
Fig.5

スライス基準 < 文Slice of <9, g>
Fig.6

9, g> のスライス

集約節点からのスライス

Slice of merged node
Fig.7

支配表と集約節点からのスライス

Control table and slice of merged node
Fig.8
節点分解

Node decomposition
Table.1
テストプログラムSample programs
Table.2
PDG 節点数
Number of nodes
Table.3
PDG 辺数
Number of edges
Table.4
支配表セル数

Number of cells of control tables
Table.5
節点，辺数，支配表セル数の和

Sum of nodes, edges and cells of control tables
Table.6
PDG 構築時間 [ms]PDG construction time[ms]Table.7
平均スライスサイズ [文]10'xx/xx Vol. Jxx{X No. xx

Average slice size[# statements]