論 文プログラム依存グラフの効率的な更新手法
高田 智規y佐藤 慎一yy

井上 克郎yIncremental Update Method of Program Dependence GraphyyyTomonori TAKADA , Shinichi SATO

, and Katsuro INOUEy

あらましプログラム依存グラフ（ Program Dependence Graph，PDG ）は， プログラム中の文間の依存関係を表す有向グラフである．PDG の辺をたどることにより，ある文に関連する文の集合（プログラムスライス，スライス）を抽出することができる．PDG やスライスはデバッグ・保守などさまざ まな用途に用いられる．
一般に，PDG の計算には時間がかかる．しかし ，頻繁にプログラムを変更しそのスライスを求めるような場合
でも，これまではプログラムが変更されるたびに PDG 全体を再計算していた．
そこで本論文では，プログラムが変更されたときに，PDG のプログラムの変更箇所に対応する部分だけを更新するアルゴ リズムを提案する．これにより，再計算の時間が軽減され，デバッグ等を効率的に行うことが期待される．
また，既存のデバッグ支援システムに本手法の実装を行い，実際に本手法の有効性を確認する．
キーワード
プログラム依存グラフ，更新，プログラムスライス，デバッグ支援

1.

（ これをここでは PDG 再計算とよぶ ），PDG 再計算

まえが きは複雑であり，それに多くの時間を費していた．これ

プ ロ グ ラ ム 依 存 グ ラ フ（ Program Dependence

はインタラクティブにプログラムの修正や実行を行い，Graph，PDG ）は，プログラムの各文における変数間

デバッグを効率良く行う際の大きな障害となっていた．

の各節点はプログラム中の各文・条件式を表し，有向辺

PDG のうちプ ログ ラムの変更箇所に関する部分だけを更新することができれば ，PDG 再計算に要しては依存関係（データ依存・制御依存）を表す．PDG のいた時間が短縮され，作業効率の大幅な向上が期待で有効辺をたど ることにより，プログラムスライス [2] 〜

きる．

の依存関係を表す有向グラフである [1], [6], [7]．PDG[7], [9], [13] 〜 [16] とよばれる，プログラム中のある文

プ ログ ラム内の部分的な変更が ，その 他の文に与に影響を受ける，または影響を与える文の集合を抽出える影響を調べるアルゴ リズムは既に提案され ていすることができる．プログラムスライスはデバッグやる [8], [10], [11]．文献 [8] のアルゴ リズムでは ，PDG

テスト，保守，プログラム合成などに利用されている．

の修正を容易にするためだけに，各頂点で多くの情報

これまでに，プログラムスライスを抽出しデバッグを保持しておく必要があった (例えば ，到達定義集合

を効率良く進めるためのシステム [12] を開発した．こなど )．また，関数間解析を行っていない文献 [10], [11]のシステムは抽出したプログラムスライスを対象としは，データフローグラフの効率的な更新法を提案しててデバッグを行う機能を持っている．このシステムでいるが，いずれも関数間にまたがる解析に必須な引数はプログラムに変更を加えるたびに PDG 全体を変更

や戻り値，大域変数による依存関係解析の伝播方法

されたソースプログラムの全体から再計算していたがが明示されておらず，実際のシステムで実現が困難である．

y大阪大学 大学院基礎工学研究科，豊中市
Graduate School of Engineering Science, Osaka University,yy

PDG を再計算する手法を提案する．また，前述のデ

NTT データ通信株式会社
NTT Data Corporation

電子情報通信学会論文誌

そこで，プログラムの部分的変更が行われた時に関数境界を越える依存関係を正し く計算し ，効率良くToyonaka-shi, 560 Japan

D{IVol. J80{D{INo. 10

pp. 1{81997 年 10 月

1

電子情報通信学会論文誌 '97/10 Vol. J80{D{I No. 10

バッグ 支援システムに提案する手法を実装し ，PDGの再計算と本手法との実行時間を比較し ，その有効性を確認する．
2.

諸 定 義

2. 1

入力言語

本論文では 以下のよ うな言語を入力言語とし て考える．この言語には文として条件文（ if 文），代入文，対象とする．
節点として，プログラム内の文または条件式（ 条件
文・繰り返し文の条件判定部分）に対応した節点（ 文節点）および ，手続き境界をこえる依存関係の解析などに用いる特殊節点がある．
辺として，データ依存関係を表すものをデータ依存
辺といい，制御依存関係を表すものを制御依存辺という．以下，節点（ 文）s から節点 t への変数 v に関する

繰返し 文（ while 文 ），入力文（ readln 文 ），出力文

データ依存辺を s（ writeln 文），手続き呼出し文，複合文（ begin{end ）

制御依存辺を s- ，節点 s から節点 t への- と表す．
vttがある．変数の型としてはスカラ型のみを考える．プ

これらの依存関係を表す辺のほかに ，フロー辺とログラムは，大域変数宣言，手続き（ 関数）定義，メ呼ばれる実行順序を表す辺がある（ 注 1 ）．文 s から文 t に

インプログラムからなり，ブロック構造はない．手続（ 他の文の実行無しに ）直接制御が移る可能性がある

き内では内部で宣言された局所変数と仮引数変数およ時，節点 s から節点 t へのフロー辺が存在し， s → t

び大域変数のみが参照可能で，他の手続き内の局所変と表す．

数は参照できない．手続きは，自己再帰的および 相互

パス s; ．
．
．
．
t が存在するとは，節点 s からフロー辺を再帰的に定義可能であり，その引数は，値渡しで扱わ

順方向にたど り節点 t へ到達するような経路が存在すれる．

ることをいう．

2. 2

到達定義

文 s における変数 x（の値）の定義が文 t に到達するとは，文 s が変数 x を定義し，かつ，s から t に至る実
行パス s，
u1 ，u2 ，．．．．，uk ，t 中に変数 x を再定義しないよ

図 1に PDG の例を示す，図中の DD はデ ータ依存辺，CD は制御依存辺， ow はフロー辺をそれぞれ表
す．また，PDG に対して，表 1で示す集合を定義する．

うな実行パス u1 ，
u2 ，．．．．，uk が存在する場合を言う．

文 n における変数 v の定義が文 s に到達する場合，文s には到達定義 hn; v i が存在するという．到達定義集
合とは，文 s に到達するすべての到達定義からなる集
合である．
2. 3

表1

(

)

(

)

source c; vtarget c; v

依存関係

プログラム中の文間の依存関係として以下の二種類()

prev cを考える．
（ 1 ） データ依存関係（ Data Dependence ）変数 v を参照している文 t において到達定義集合中に到達定義

hs; vi が存在するとき，文 s から文 t に対して変数 v に関するデータ依存関係があるという．

()

next c

DD
CD
F LOW

PDG に対する集合
Table 1 Set for PDG

節点 c から変数 v に関するデータ依存辺を遡って到達できる（ 有向辺を逆方向にたど った）
節点の集合を表す（ c 自身を含めない．以下同様）．
節点 c から変数 v に関するデータ依存辺を辿って到達できる（ 有向辺を順方向にたど った）
節点の集合を表す．
節点 c からフロー辺を遡って到達できる節点の集合を表す．
節点 c からフロー辺を辿って到達できる節点の集合を表す．
データ依存辺の集合．
制御依存辺の集合．
フロー辺の集合．

（ 2 ） 制御依存関係（ Control Dependence ）文 s が条件文または繰り返し 文の条件式であり，文 sの条件判定の結果によって文 t を実行するか否かが直

2. 5

前定義節点

節点 r における変数 v の定義が節点 s の入口に到達

接決まる時，文 s から文 t への制御依存関係があるとしている場合，節点 r を，節点 s の変数 v に関する前いう．

定義節点とよぶ．また，前定義節点の集合を前定義節

2. 4

プログラム依存グラフ

プ ロ グ ラ ム 依 存 グ ラ フ（ Program Dependence
Graph，PDG ）は，プログラム内の各文間に存在する依存関係を有向グラフで表したものである．本論文では，文献 [16] のアルゴ リズムを用いて求めた PDG を2

点集合とよぶ．例えば ，図 1において節点 s5 の変数 bに関する前定義節点集合は

fs3; s4g となる．

（ 注 1）：フロー辺を PDG に含めない場合が多いが ，ここではこのグラ
フを PDG とよぶ論文／プログラム依存グラフの効率的な更新手法ていた．しかし ，この方法では各節点ごとに計算した

s1

到達定義集合を保存しておかなければならず，実装すa:=0

る際に非常に多くのメモリを必要としていた（ 注 2 ）．
そこで，ここでは次のような工夫をした．PDG のas2

データ依存辺は解析時に到達定義集合を基にして引かれている．よって，変更前の PDG 中のデ ータ依存辺

if a=0- があったとき，から，到達定義集合の一部を知ることができる．例え

s4

s3
b:=1

b:=0

v

ば ，ある節点 s において rs

変更前の s における到達定義集合の中に

hr; vi が存在していたことになる．本手法ではプログラムが変更さ

b

s5

b

れたときに，到達定義集合を保存しておかなくても，
このようなデータ依存辺の情報を利用し ，依存関係のwriteln(b)変化を求め，PDG の更新を行うことができる．
しかし，これだけでは関数境界を越える依存関係を正しく解析することはできない．そこで，関数内解析

flow

DD

CD

と関数間解析の二種類のアルゴ リズムを考える．関数
内解析アルゴ リズムでは上記の手法により変更された

図 1 PDG の例
Fig. 1 Example of PDG

文が含まれる関数内部のデータ依存辺を引き直す．関数間解析アルゴ リズムでは変更による他の関数への影
響を調べ，関数境界を越える依存関係を解析する．

2. 6

プログラムの変更

プログラムの変更として PDG の文節点一つに対し ，以下の 3 種類の操作を考える．

 文の削除PDG 上に存在する節点を削除する

4.

単一関数内解析アルゴリズム

まず，文の削除・挿入・修正それぞれに共通な前定義
節点の発見のためのアルゴ リズムを示し ，次に削除・挿入・修正のアルゴ リズムを示す．
4. 1

前定義節点の発見

 文の挿入このアルゴ リズムではフロー辺を遡り，節点での定 文の修正このアルゴ リズムは 4. 2節〜 4. 4節において用いる．

新たに節点を作り PDG に挿入する
節点はそのまま保存するが，その内容を修正する
3.

アルゴリズムの概要

ここでは，ユーザーがプログラムの部分的変更を行う際，その作業の種類 (文の削除/挿入/修正) を陽に指定し，それに従って制御依存辺を修正するものとする．
例えば ，条件文の節中に文を挿入した場合，条件文から挿入文に対して制御依存辺 を追加する．逆に，条件文の節中の文を削除した場合，制御依存辺を削除す
る．このように制御依存辺の変化は，変更前の制御依
存辺から容易に求めることができる．以降はデータ依
存辺，フロー辺の変化についてのみ述べる．
文献 [8] では，プ ログラムの変更に伴う到達定義集
合の変化をフロー辺を辿り，後の節点に伝えていくことにより，変更によって変化した依存関係を再計算し義・参照変数を調べることにより前定義節点を求める．
アルゴリズム FindPreDef

input: 節点 s，変数 v
output: 前定義節点集合 P reDef (s; v )（ 1 ） P reDef (s; v )（ 2 ） c 2 prev (s) なる各 c に対して以下を順に実行．
（ a ） c において v が定義されていれば ，

P reDef (s; v )P reDef (s; v ) [ fcg（ b ） c において v が参照されていれば ，

P reDef (s; v )source(c; v )P reDef (s; v )[（ c ） c において v が定義も参照もされていなけれ（ 注 2）：通常，到達定義集合はデータ依存辺を引いた後は必要無く，保存する必要は無い．
3

電子情報通信学会論文誌 '97/10 Vol. J80{D{I No. 10

ば ，c
4. 2

削

除

節点を削除することにより，その文における変数の定義が無効となる．そのような変数に関するデータ依
存辺を引き直し ，その後節点を削除する．

input: 削除する節点 s
output: 更新された PDG（ 1 ） s で定義されている各変数 v すべてについて，v
DD DD [ frt j r 2 P reDef (s; v ); t 2target(s; v )g
（ 2 ） DDDD
fr v s j r 2v
t j t 2 target(s; v )gsource(s; v )g fs（ 3 ） F LOW
F LOW [ fp → n j
p 2 prev (s) ; n 2 next(s)g fr → s j r 2
prev (s)g fs → t j t 2 next(s)g（ 4 ） 節点 s 自身を削除

-

4. 3

挿

-

入

このアルゴ リズムではまず，フロー辺をつけかえる．
次に，挿入する節点で定義する変数を参照する節点へ
データ依存辺を引く．また，挿入によって依存関係の無くなるデータ依存辺を削除する．最後に，挿入する

input: 挿入する節点 s，prev (s)，next(s)output: 更新された PDGての変数を定義してものとみなす．

（ 1 ） F LOW
F LOW [ fp → s j p 2
prev (s)g [ fs → n j n 2 next(s)g fp → n j p 2
prev (s) ; n 2 next(s)g（ 2 ） s で定義している各変数 v すべてについて，以2 P reDef (s; v); t 2 target(r; v) に対して ，v を定義し ないようなパス s; :::; t が 存在すれば ，-i. DD DD [ fstgii. 任意の r 2 P reDef (s; v ) に対して v を定義
v

しないようなパス r; :::; t が存在しなければ ，DD
DD
P reDef (s; v )g

f

r

v

-

t

j

r

（ 3 ） s で参照している各変数 u について，
4

r

2

正

このアルゴ リズムは，削除アルゴ リズムと挿入アル
変数集合 V を定義し変数集合 U を参照する節点 s を，

変数集合 V 0 を定義し変数集合 U 0 を参照するように修正したとする．
アルゴリズム ModifyVertex
節点 s，変更後の定義変数集合 V 0 ，変更後

input:の参照変数集合 U 0

output: 更新された PDG（ 1 ） F LOW

2V

（2） v

F LOW

V に対して，0-DD
DD [ frt
j r
P reDef (s; v ); t
2 target(s; v)g
fs v t j t 2 target(s; v)gv

2-2 V V に対して，（ a ） 各 r 2 P reDef (s; v ); t 2 target(r; v ) に対
（ 3 ） v0000

して，v を定義しないようなパス s; :::; t が存在すれば-以下を実行．

義しないようなパス r; ::; t が存在しなければ ，

但し ，手続き・関数・プログラムの入口において全以下を実行．

jv'

アルゴリズム InsertVertex（ a ） 各r

修si. DD DD [ fstgii. 任意の r 2 P reDef (s; v 0 ) に対して，v 0 を定

節点で参照する変数のデータ依存辺を引く．

下を実行．

4. 4

u

ゴ リズムを組み合わせることによって実現している．

アルゴリズム DeleteVertex

-

-

DD
DD [ fr
P reDef (s; u)gprev (c) として 2a. 以下を実行．

2

DD
DD
P reDef (s; v )g
（4） u

2U

2U

r

-

t

j

t

2

-

s

j

r

2

s

j

r

2

v'

U に対して，0DD
DD
P reDef (s; u)g（ 5 ） u0

f

f

r

u

U に対して，0DD
DD [ fr
P reDef (s; u )g

-

u'

0

5.

複数関数間解析アルゴリズム

5. 1

PDG

図 2のプログラム proc は手続き inc の中で大域変数a を参照・定義している．このプログラムの PDG は図3のようになる．関数（ 手続き ）内部で関数外での大域変数を参照している場合は global-in とよばれる特論文／プログラム依存グラフの効率的な更新手法
表2 特 殊 節 点
Table 2 Special Vertex

殊節点を関数の入口に作り，関数内部で大域変数を定義している場合は global-out とよばれる特殊節点を関数の出口に作る．関数境界を越える依存関係がある場
合はこれらの特殊節点を介してデータ依存辺を引く．



このような特殊節点を表 2に示す．

program proc(input,output);var a: integer;procedure inc;begin
a:=a+1end;
beginreadln(a);inc;writeln(a)end.



図 2 プログラム proc
Fig. 2 Sample Program proc

特殊節点
プ ログ ラムおよび 手続き (関数) にひとつずつあり，そのプログラム (関数・手続き) の中のすべての文は entry 節点
からの CD 関係がある
exit 節点関数の戻り値を通して伝わる影響を検出するための節点で ,各関数にひとつずつある
global-in 節点
手続き外からの大域変数の影
響を内部へ伝えるための節点
で , 手続きに , 個々の大域変数に対して , ひとつずつある
手続き内で定義された大域変
global-out 節点数の影響をその外へ伝えるための節点で , 手続きに , 個々の大域変数に対して, ひとつずつある
paramter-in 節点
手続きの引数を通して伝わる影響を検出するための節点で ,その引数それぞれにひとつず
つあるparameter-out 節点 手続きの変数引数を通して伝
わる影響を検出するための節
点で , 変数引数それぞれにひとつずつある

entry 節点表記例

f{Entry

f

{exit

fg

{in

{

fg out{fp par{fp parout

プログラムのある領域 S について，S を実行したときに 必ずその値が 定義され る変数とその定義節点との組の集合を確実定義集合と呼び ，SuDEF (S ) と表
す．また，定義される可能性のある変数とその定義節
点との組の集合を潜在定義集合と呼び ，P oDEF (S )と表す．
また，次に示す条件をすべて満たす変数 v を「手続きp で暗使用される変数」と呼び，その集合を ImUSE (p)と表す．

 v は大域変数である
 p 内での v の参照地点に p 外の v の定義が 到達

する
図 3 プログラム proc の PDG
Fig. 3 PDG for sample program proc

5. 2

関数間解析

関数（ 手続き ）f 中の文 s に対して変更を行うことを考える．

関数（ 手続き ）中の文に対して変更を行った場合，その関数内で参照・定義している変数が変更前と異なる場合がある．このような場合は既存の特殊節点の削除や新たな特殊節点の挿入が必要になる．
このような変更に対応するため，文献 [16] で PDGを計算する際に用いている確実定義集合，潜在定義集
合，暗使用される変数集合を考える．

（ 1 ） s に関数内変更アルゴ リズムを行う．

（ 2 ） f を直接，または間接に呼び 出す関数およびf 自身の集合を F とする．
（ 3 ） 8g 2 F に対して，
SuDEF (g )P oDEF (g )ImUSE (g )




5

電子情報通信学会論文誌 '97/10 Vol. J80{D{I No. 10（ 4 ） F 中各関数の SuDEF , P oDEF , ImUSEを求める．
（ 5 ） 4. を F 中 の す べ て の 関 数 の SuDEF ,P oDEF , ImUSE が変化しなくなるまで繰り返す．
（ 6 ） 関数ご とに 変更前後の SuDEF , P oDEF ,ImUSE を比較し，異なっていれば以下を実行する．

表 4 PDG 再計算・更新にかかわる要素
Table 4 Component for recompute and incremental
update of PDG
P
G
L
Si
St

（ a ） 新たに定義・参照するようになった変数に関すVE

る global-out, global-in 節点を作り，関数内部のデー
タ依存辺を引く．
（ b ） 関数呼出し 文に対して アルゴ リズム ModifyVertex を用いてデ ータ依存辺を引き直す．その際，関数内で参照・定義する変数を呼び出し文で参照・定義する変数として用いる．
（ c ） 呼び 出し 文におけるデ ータ依存辺を globalin,global-out でのデータ依存辺とする．
6.

実行効率

6. 1

実

装

本アルゴ リズムのうち，削除アルゴ リズムおよび 挿入アルゴ リズムを文献 [12] のシ ステムに組み込んだ．
ソースコード は C で記述し，ユーザインタフェースには Tcl/Tk を用いた．本アルゴ リズムを組み込むにあたり，フロー辺の追加や仕様変更，機能拡張などを行った．削除アルゴ リズムは約 1060 行，挿入アルゴ リズム

手続きの総数
大域変数の総数
手続きの局所変数の最大値
手続き呼び出しの総数
文の総数
PDG の節点の総数
PDG の有向辺の総数

表5 計 算 量
Table 5 Computational complexity
PDG 再計算O (P  St  (G + L))
単一関数内削除O ((V + E )  (G + L))
単一関数内挿入O ((V + E )  (G + L))
単一関数内修正O ((V + E )  (G + L))
関数間削除・挿入・修正
O (P  St  (G + L)+
Si  G  (V + E )(G + L))

6. 3

考

察

PDG の再計算および 更新アルゴ リズムの時間計算量を示した．
本アルゴ リズムの時間計算量が最悪となるのは PDG
が完全グラフであり，かつ特殊節点に関する操作をすべての関数で行う時である．しかし ，通常のプログラ
ムでこのようになることは無い．
また，一つの関数の大きさはプログラム全体の大きは約 570 行である．また，システム全体では約 13500

さとは独立で，ある定数以下であると仮定すると前定行である．

義節点の発見手続きは O(1) で計算できる．

削除，挿入・変更アルゴ リズムの実行時間を表 3に示す（ SPARCstation 20, Memory 64MB 上での実行時間）．但し ，表 3中の左側二つ（ 50 行・100 行 ）は単一関数，右側二つは複数関数のプログラムである．
表 3 実行時間（ 単位は秒）
Table 3 execution time(sec)
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以上の仮定のもとでは，本アルゴ リズムでは関数間の削除・挿入・修正は O(V + E + St (G + L)) で計算で

きる．一方，PDG 全体を再計算すると O(St (G + L))になる．

PDG 再計算と本アルゴ リズムでは解析の対象がそれぞれソースプログラム，PDG と異なるため，計算量の表現に用いられる変数が異なっている．本アルゴ
リズムでは関数境界を越える依存関係を PDG 再計算と同様に解析しており，表記上の計算量が大きくなる．
本アルゴ リズムでは関数間の依存関係の変化を解析

これにより，本アルゴ リズムによる PDG の変更がするために，関数で定義・参照する変数を収束するまプログラムを変更した後に全体を再計算することに比で調べる．この部分の計算量は PDG 再計算と同じだ

べ，解析時間が大幅に削減されることがわかる．

け必要である．しかし ，PDG 再計算ではこの繰り返

6. 2

計

算

量

PDG の再計算・更新にかかわる要素を表 4に示す．
集合演算にその要素数に比例する計算量が必要だとしたときの，PDG 再計算・本アルゴ リズムの計算量は
表 5のようになる．
6

しにおいてすべての節点でデータ依存辺の挿入を行っているが，本アルゴ リズムでは節点の内容を調べるだ
けで，辺の挿入は行わない．

PDG 再計算のためにはプログラム全体の構文解析などが必要であるが，本アルゴ リズムでは部分的な構

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

文解析（ 必要ない場合もある）だけで済み，大部分の節点や辺の作成も必要ないため，現実的には PDG 再計算に比べて短い時間で解析できる．
また，本アルゴ リズムのために PDG 中に保持しておく必要のある情報は関数ごとの定義・参照変数情報だけである．しかし ，変更前に PDG を調べることによりこの情報も復元できるため，PDG のみあれば 変更を行うことができる．これは，すべての節点で到達定義集合を保存しておくという文献 [8] のアルゴ リズ
ムに比べ使用する作業領域面で効率が良い．
7.

あとがき

プ ログ ラムの部分的変更が行われた際に，PDG を部分的に変更する手法を提案した．また，既存のシステムに組み込みその高速実行性を確認した．我々のデバッグ支援システムはこの機能を組み込んだため，頻繁にソースプログラムの変更をしてもスライスを効率良く抽出できるようになり，よりインタラクティブに
デバッグ作業を行えるようになった．
本手法は，今回実際に組み入れたシステムに限らず，

PDG を利用し その一部が頻繁に変更され る可能性のあるシステム使用時の作業効率を向上させることが期待される．
本論文では Pascal 風言語を入力言語とし て扱ったが，2. 4節で示した PDG を用いて解析を行っていれば，他の手続き型言語にも適用可能である．
文

献[1] Aho, A., Sethi, R. and Ullman, J., \Compilers:Principles,Techniques, and Tools",Addison Wesley,1986.
[2] Fritzson, P., Gyimothy, T., Kamkar, M. and Shahmehri, N., \Generalized algorithmic debugging andtesting", Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Vol. 26, No. 6, pp. 317{326 ,1991.
[3] Fritzson, P., shahmehri, N. and Kamkar, M., \Generalized algorithmic debugging and testing", ACM Letters on Programming Languages and Systems, Vol. 1,
No. 4, pp. 303{322 ,1992.
[4] 二村, 他, \プ ログ ラム変換", 共立出版, chapter 4, pp.
63{79 ,1987.
[5] Gallagher, B. and Lyle, R., \Using program slicing
in software maintenance", IEEE Trans. on software
engineering, Vol. 17, No. 8, pp. 751{761 ,1991.
[6] Horwitz, S. and Reps, T., \The use of program dependence graphs in software engineering", Proceedings of the 14th International Conference on Software
Engineering, Dallas, Texas, Association for Comput-

ing Machinery, pp. 392{411 ,1992.
[7] Horwitz, S., Reps, T. and Binkley, D., \Interprocedural slicing using dependence graphs", ACM Trans. on
Programming Languages and Systems, Vol. 12, No. 1,
pp. 26{60 ,1990.
[8] 鍛冶 武志, \プログラムの部分的変更にともなう依存解析
グラフの更新手法", 大阪大学基礎工学部情報工学科 特別
研究報告 ,1996.
[9] Lyle, R. and Weiser, M., \Automatic program bug
location by program slicing", Proceedings 2nd International Conference on Computers and Applications,pp. 877{883 ,1987.
[10] Pollock, L. and So a, L., \An Incremental Version of
Iterative Data Flow Analysis ", IEEE Transactions
on Software Engineering, Vol. 15, No. 12, pp. 1537{
1549,1989.
[11] Ryder, G. and Pall, C., \Incremental data- ow analysis algorithm", ACM Trans. on Programming Languages and Systems, Vol. 10, No. 1, pp. 1{50 ,1988.
[12] 佐藤, 飯田, 井上, \プログラムの依存関係解析に基づくデバッグ支援システムの試作", 情処学論, Vol. 37, No. 4,
pp. 536{545 ,1996.
[13] Shimomura, T., \Bug localization based on error{
cause{chasing methods", Transactions of Information
Processing Society of Japan, Vol. 34, No. 3, pp. 489{
500 ,1993.
[14] 下村 隆夫, \プログラムスライシング技術と応用", 共立出
版 ,1995.
[15] 高谷 暢之, 出力の制限情報を利用し たプログ ラム簡素化手法の提案, 修士論文, 大阪大学基礎工学部情報工学科,1994.
[16] 植田, 練, 井上, 鳥居, \再帰を含むプログラムのスライス計
算法", 信学論, Vol. J78-D-I, No. 1, pp. 11{22 ,1995.
[17] Weiser, M., \Program slicing", Proceedings of theFifth International Conference on Software Engineering , San Diego, CA, pp. 439{449 ,1981.

付
1.

録

アルゴリズムの正当性

本アルゴ リズムによってデータ依存辺が PDG 計算のアルゴ リズムと同様に引かれることを示す．以下，ある文 s の入口における到達定義集合を RDin (s)，出口における到達定義集合を RDout (s) で表す．
削

1. 1

除

削除する節点 s で変数を定義していない場合，削除によって s 以降の文に与える影響はない．この場合，

データ依存辺を新たに追加する必要は無く，s と関連する辺を削除すればよい．

削除する節点 s で変数 v を定義し ，RDin (s) 中に到

hr; vi が 存在し たとする．この場合，削除前の RD (s) 中には hr; v i は存在せず， hs; v i が存在
達定義

out

7

電子情報通信学会論文誌 '97/10 Vol. J80{D{I No. 10

する可能性があり，これらが変化すればこの関数の呼する．

s が無ければ，s 以降，v が再び定義されるまで到達
定義集合中には hs; v i は存在せず， hr; v i が存在する．
そのため ，v を参照する節点 t でのデ ータ依存辺は sv- の代わりにtアル- が存在する．

v

r

ゴ

リ

t

ム DeleteV-ズ

r 2 P reDef (s; v ); t 2 target(s; v ) にv
対し rt は上記の節
t を追加する．ここで r ，
点 r，t に相当する，また，s に関するデータ依存辺を削-

ertex では

- の代わりにv

除するため， st

び出し文で参照・定義する変数が異なってくる．そこ
で，変更を受けた関数を直接または間接に呼び出す可能性のある関数の集合に対して，SuDEF , P oDEF ,ImUSE を求め，これらの値が収束するまで計算を行う．この方法は PDG 計算アルゴ リズムの関数間解析と同じ 方法であるため，これによって PDG 全体を再計算するのと同じ PDG が計算できる．

（ 平成 97 年 7 月 25 日受付）

- が

v

r

t

新たに引き直されている．
1. 2

挿

入

挿入する節点 s で変数 v を定義し ，変数 u を参照し高田 智規ていたとする．
変数 v に関して，挿入アルゴ リズムは削除アルゴ リ- をv

ズムの逆を行う，つまり r

t

s

-

v

平 7 阪大・基礎工・情報卒．平 9 同大学

院修士課程了．現在 NTT ヒューマン イン
ターフェース研究所勤務．在学中、プログtにすることで PDG の更新が行える．但し ，挿入を行

ラムスライスの研究に従事．

う段階で s に関するデ ータ依存辺が存在しないため ，

到達定義集合に関する情報を復元するのにいくつかの問題がある．

佐藤 慎一

一つめの問題は，変数 v に関する前定義節点 r ，参平 6 阪大・基礎工・情報卒．平 8 同大学

照する節点 t としたときに r::t::s という実行順序とな

院修士課程了．同年 NTT データ通信株式
会社技術開発本部入社．ソフトウェア工学がある．

の研究に従事．

る時である．この時，s が t 以前に実行されない可能性
二つめの問題は，s の挿入によって r での v の定義がt に到達するかど うかがわからないことである．

井上 克郎 （ 正員）

これらを解決するため， アルゴ リズム InsertVer-

昭 54 阪大・基礎工・情報卒．昭 59 同大s; :::; t が存在する場合だけ処理を行う．
また，すべてのパス r; :::; t に対して，パス中に v を定義する文が 存在しているならば r での v の定義は t に
tex ではパス到達しないとして， r- を削除している．こv

るのと同じ PDG が計算できる．
修

正文の修正アルゴ リズムは削除・挿入アルゴ リズムを組合せたものである． アルゴ リズム ModifyVertex
は変更によって定義・参照されなくなった変数に対して
削除アルゴ リズムを，新たに定義・参照されるようになった変数に対して挿入アルゴ リズムを適用している．
1. 4

関数境界を越える場合

まず，4. 2節〜 4. 4節のアルゴ リズムによって関数内部の解析を行う．次に，変更による他の関数への影響を調べる．
変更によって関数内部で定義・参照する変数が変化
8

情報工学科・助教授．平 1 阪大・基礎工・情報・講師．平 3 同学科・助教授．平 7 同学

tれにより，全ての場合において PDG 全体を再計算す
1. 3

大学院博士課程了．同年同大・基礎工・情報・助手．昭 59 〜昭 61 ハワイ大マノア校・科・教授．工博．ソフトウェア工学の研究に従事．