Vol. 37 No. 4

Apr. 1996

情報処理学会論文誌

プログラムの依存関係解析に基づくデバッグ支援ツールの試作
佐 藤 慎 一y

元 yy

飯 田

井 上

克 郎y

ソースプログラムの依存関係解析に基づき，スライスの抽出や部分評価を行い，デバッグの対象となる部分を小さくすることができるデバッグ支援ツールを試作した．本ツールでは，ステップ実行やトレースなどを元のプログラムだけでなく限定されたプログラム部分に対しても行なうことができる．
本ツールを用いれば，プログラム中でバグに関係のある部分のみを作業の対象とすることができるた
め，効率の良いデバッグを行なうことができる．

Software Debug Supporting Tool
Based on Program Dependence Analysis
Shinichi Sato,y Hajimu Iida yy and Katsuro Inouey

Debugging large and complex software is not easy task since localizing and identifying faults
are very di cult. We have depeloped a debug tool which extracts program slices and which
partially evaluates program texts based on program dependence analysis. Using this tool，we
can extract parts of the program which would relates to bugs，and also we can execute andtrace the extracted parts. Using this tool，we would expect that the debugging process will
be more eÆcient.

1.

する方法が必要である．

まえがき

本研究では，プログラムスライス（以降，単にスラ

年々プログラムは多機能化し，大規模になっている．

イスと呼ぶ）及び部分評価手法を用いて，プログラム

そのような大規模なプログラムをデバッグするのは容全体から注目する文や変数に関係のある部分のみを易ではない．

抽出し，それに対して処理を行うようなデバッグ支援

通常，プログラムをデバッグする際には，対象となツールを提案し，実際にツールの試作を行った．

るプログラム全体を読んで理解する必要がある．したスライスとは，直観的には，プログラム中のある文がって，プログラムが大きくなるとプログラム全体のs での変数の値に影響を与える文の集合，もしくは s で把握やエラーに関する部分の特定に多くの時間がかの変数の定義が影響を与える文の集合である．スライ

かってしまう．

スを用いることにより，ある出力変数に関係のある文のみをプログラムから抽出することができる．

もし，エラーに関係があると思われる部分だけをプ
ログラムから抽出するような機能があれば，開発者はまた，部分評価とは，プログラムに対する入力変数

プログラムの一部分だけに注目してエラー位置の特定の値をある定数に固定し，プログラム中の文や式の書ができ，開発効率の向上が期待される．ただし，その換えを行い，目的とする部分の抽出を行うことをいう．

際に開発者がエラーに関連のあるプログラムの部分の本研究では，動的スライス（プログラムの実行系列抽出を手動で行うのは手間がかかるうえ，ときとしてを解析して得られるスライス）ではなく，静的スライ

関連のある部分を見過ごす危険がある．したがって，ス（プログラムの依存関係を解析し，それに基づいてそのようなプログラムの部分を機械的に効率良く抽出求められるスライス）を利用することにより，抽出したスライスを１つのプログラムとして扱ってデバッグ

y 大阪大学 基礎工学部 情報工学科

を行うことができる．

Department of Information and Computer Sciences，さらに，スライスによって有効な抽出が行いにくい

Faculty of Engineering Science，
Osaka University

場合でも本ツールでは，部分評価の機能を持つため，

yy 奈良先端科学技術大学院大学 情報科学研究科

対象を小さくできる場合がある．たとえば入力のパラ

Graduate School of Information Science，

メータでサブシステムの 1 つの機能の実行が指定/除Nara Institute of Science and Technology

12

Apr. 1996

情報処理学会論文誌

外されるようなプログラムに対しては，入力パラメー

きるため，必要ならば，それらの手法を抽出部分に適タを特定の値として部分評価することによって，容易用することもできる．

にそのサブシステムを抽出したり除いたりすることが本稿では，これ以降，2 章でプログラムの依存関係

解析の概要を，3 章で作成したツールの概要を，4 章

できる．
本ツールにおいて背景となるスライスや部分評価の手法は，それぞれ独立して詳しく研究されている 6),14) ．
しかし，このような静的スライスと部分評価を組み合でツールの実行例およびその評価について述べる．

プログラムの依存関係解析

2.

わせたデバッグ支援ツールは今までに存在しない．

本稿で述べるデバッグ支援ツールは，プログラムの

ここでは，比較的実現が容易でかつ実行効率が現実

依存関係解析の結果得られるプログラム依存グラフ

的なスライスや部分評価の方法を用いて試作ツールを（Program Dependence Graph，略して PDG）から，作成し，この種のツールの有効性を調べる．スライス

スライシングや部分評価を行うことによってプログラについては，（再帰/非再帰）関数間の変数依存解析 16)

ムの参照範囲を小さくすることによりデバッグの支援を実現している．ここで実現されている方法に加え，を行う．

ポインタ変数の解析 2),10) や，それに伴う変数のエイ

2.1

プログラム依存グラフ（PDG）

ツールでは実現しなかった．部分評価は，値の代入に

PDG はプログラム内の文の依存関係を表すグラフである．PDG の節点はプログラム中の各文および if 文や while 文の条件判定部分を表し，辺は変数の影響を伝えるデータ依存（Data Dependence，略して DD）

よる式の評価と不要式の削除という方法に基づいてい関係および条件文や繰り返し文の制御の影響を伝えるる 15) ．プログラムの記号実行やループの展開 3) ，ブ

制御依存（Control Dependence，略して CD）関係を

リアス解析 11) ，なども考えられるが，それらを正確に扱えるアルゴリズムがまだ存在しないことから，その実行効率やその実用性が不明であるため，本試作

レスブルガ式の評価

9)などの技法も採用できると考え表す．

存する必要性があることなどから本ツールではより簡DD は，各頂点の到達定義集合（Reaching De nitions，略して RD）を求めることによって得られる．
PDG 上でのある頂点 の RD とは，変数 と頂点 と単な方法を用いた．

の組 h ，i の集合である．これは，られるが，実現の困難さや非効率さ，さらに，デバッ
ガとして用いるには元のプログラムとの対応関係を保

t

vs

s

v

v

s

に関係のある部分のみをスライスもしくは部分評価で

 プログラム中の文 で変数 を定義している．
 プログラム中の 2 つの文 から へのすべての実抽出して，その部分のみを実行させることが可能とな

行パスの中で， を定義しないパスが少なくとも本ツールを用いることにより，デバッグ時に，バグり，その結果，デバッグの対象となるプログラムの参照部分を減少させることができた．
これまでにも，スライスを利用したデバッグ支援
ツールはいくつか発表されている 1),13) ．しかし，こ1 つ存在する．

v

s

t

t
vs
t が v を参照するとき，s から t への DD 関係があるとことを示している． の RD に h ，i が含まれ，かつ
いう．

s
s t

t

れらはいずれも動的スライスに基づくもので，実行さまた，ある条件判定部分 の結果により文 の実行

せるたびにスライスを計算しなければならないうえ，の有無が決定されるとき， と との間に CD が存在す

実行系列を保存しておく必要があるために解析結果がるものとする．すなわち CD は if 文や while 文の条件

膨大な量になる．

判定部分からそれらの内部ブロックに属する文への影

また，静的スライスを用いたデバッグ手法としては，
ダイシング 8) やアルゴリズミック・デバッギング 4),5)があるが，本研究では，スライスや部分評価を行うことにより，プログラムのうち，一部の機能のみを実行

響であり，これはプログラムを解析すれば容易に求められる．
一般にプログラムには複数の手続きが定義されており，各手続き間には引数や大域変数を通じて DD 関係する部分を抽出し，その抽出部分をデバッグの対象とが生じる．これらの DD 関係を表すために， PDG にすることによりデバッグ時の参照範囲を縮小させるこプログラム中の文とは直接対応しない節点（中継節点とを目的としている．一方，ダイシングやアルゴリズと呼ぶ）を用意する．

ミック・デバッギングは，いきなりバグ位置を特定しようとしている点が，本研究とは異なる．本ツールは，抽出した部分を１つのプログラムとして扱うことがで

PDG の作成は，プログラムを解析し，プログラムの各文を PDG の節点に切りわけ，プログラム中の各文における RD を求め，それをもとにして PDG の各辺

Vol. 37 No. 4プログラムの依存関係解析に基づくデバッグ支援ツールの試作を生成することによって行われる．詳細は，文献 17）を参照されたい．
例として図 1 のプログラムに対応する PDG を図 2に示す．図の PDG の中で角の丸い四角がプログラム
中の各文に対応する節点で，楕円が中継節点である．
また，有向辺のうち，実線で名前がついているものがDD 関係の辺で，破線のものが CD 関係の辺である．実線についている名前は，その DD 関係の辺が影響を伝える変数の名前である．また，破線で囲まれている部
分はプログラム上の１つの手続きを表す．
2.2

スライス

１章で述べたように，本ツールで扱うスライスは，
静的スライスである．文 s における変数 v に関するスライスとは，PDG 上において，CD 関係の辺またはDD 関係の辺を辿って文 s の変数 v に到達できる節点集合に対応する文の集合である 16) ．

PDG を与えられた頂点から辺の順方向に探索していくものを forward slice と呼び，逆方向に探索していくものを backward slice と呼ぶ．
スライスの例を図 1 に述べる．このプログラムの 36
行目で参照されている変数 g に関する backward slice
が，図中の下線部分に示されている．この場合，変数g に影響を及ぼさない部分，すなわち関数 lcm はスライスに含まれていない．
2.3

部分評価

本稿でいう部分評価とは，プログラムに対する入力
変数のとる値を固定し，それを参照する式や変数の値を順次書き換えたり，実行されない不要な文や手続きの削除を行うことをいう．部分評価を適用すれば，入力変数，もしくはそれに相当する大域変数の値によってどの機能を使うか，もしくは使わないかを決定しているようなプログラムに対しては，使用しない機能に関する部分をプログラムから削除することができる．
部分評価手法の詳細は文献 16）に述べられているので，本稿では，あるプログラム

P の部分評価手法の概略を示す．

P の大域変数の中から固定の対象とする入力変x （複数個でもよい）を選ぶ．
( 2 ) 目的とする機能を選び出すのに応じて x の値
（特定の値 a）を定め，変数とその値の組 hx，aiを作る．その他の大域変数と局所変数 y につい（各変数のては不定値 ? との組 hy，?i を作る．
(1)

数

(3)

3

1 program euclid(input,output);2
var x,y,g,l:integer;3function gcd(m,n:integer):integer;forward;
4
procedure swap(var a,b:integer);5
var
temp:integer;
6
begin
7
temp:=a;8a:=b;9b:=temp;10
end;
11
function lcm(a,b:integer):integer;12varc:integer;
13
begin
14
c:=gcd(a,b);
15
lcm:=(a div c)*(b div c)*c
16
end;
17
function gcd;
18
var
w:integer;
19
begin
20
if m ＜ n then begin
21
swap(m,n);
22
end;
23
while n ＜＞ 0 do begin24
w:=m mod n;
25
m:=n;
26
n:=w;
27
end;
28
gcd:=m;
29
end;
30
begin
31
writeln('Input x and y');32
readln(x,y);33
writeln('x=',x,' y=',y);34
g:=gcd(x,y);35
l:=lcm(x,y);36
writeln('gcd=',g);37
writeln('lcm=',l);
38
end.
図1

Fig. 1

PDG の元のプログラム
Original program of PDG.

の返り値を部分評価の結果として出力する．

simple は与えられた状態の下で，入力文を

ここで，組の集合を状態と呼び，特にこのような値の割

部分評価した結果の文を返す．simple は文の種類ごと）当てを初期状態 S という．

に定義されており，（右辺の値が決まる場合の）代入文

主プログラムの本体の実行，（条件式の値が決まる場合の）条件分岐文の書M および初期状態状態 Sを引数として関数 simple（M ，S ）を呼び，そき換え，（同じく条件式の値が決まる場合の）繰り返し

4

Apr. 1996

情報処理学会論文誌

文の書き換えを行う．また，いくつかの文の系列であ1program wordcount(in,out);

る複合文は，前の文から順に再帰的に simple を実行す2

ることにより部分評価される．詳細は文献 12），16）

3

in:array[0..1000] of char;

4

i:integer;5

letter,word,line:integer;

6

isinword:boolean;を参照されたい．
上記の手順でプログラムが部分評価されると，元のプログラムにあった手続きの呼び出しや，変数の定義，参照がなくなることが起こりうる．手続きが一度も呼ばれなかったり変数が一度も参照されない場合，それvar a,b,c:char;

7
8
9

begin

10

writeln('Count the letter?(y/n)');11

readln(a);12writeln('Count the word?(y/n)');や宣言文を削除できる．これらはプログラムを解析し13

readln(b);た結果生成される PDG からその依存関係を調べるこ

14

writeln('Count the line?(y/n)');15

readln(c);16i := 0;

部分評価の例として，図 3 のプログラムの入力変数

17

letter := 0;のうち，変数 b の値を'n' に，変数 c の値を'y' に固定

18

word := 0;19line := 0;20

isinword := false;21

while in[i]らの手続きの定義や変数宣言が不要となり，その定義とによって容易に調べることができる．

して部分評価を行った結果のプログラムを図 4 に示す．
入力変数 b の値を'n' に固定した結果，入力文が削除され，また，その値が'y' のときに実行されるはずであった 27 行目から 37 行目の部分が削除されている．
また，入力変数 c の値を'y' に固定した結果，24 行目の if 節が削除されている．
3.

ツールの概要22＜＞ EOF do begin

if a = 'y' then23

letter := letter + 1;

24

if c = 'y' then25

if in[i] = EOL then26

line := line + 1;

27

if b = 'y' thenif (in[i] ＜＞' ')and(in[i] ＜＞ EOL) then

28
29

begin

30

if isinword = false then

31

begin

概要について述べる．本ツールの実装には，解析や実32

isinword := true;

行部には C 言語を，インタフェースには Tcl/Tk を用

33

本章では，本研究で試作したデバッグ支援ツールの

いた．
3.1

言語仕様

本ツールが対象とする言語は，以下のような仕様を持つ Pascal のサブセットである．

word := word +1

34

end

35

end

36

else

37

isinword := false;38i := i +1

39

end;

 文として，代入文，条件文，繰り返し文，手続き

40

if a = 'y' then

呼出文，begin{end で囲まれる複合文を扱う．

41

 手続きは再帰呼び出しも扱う．ただし，部分評価
ではこれは扱えない．手続きの引数の渡し方については，値渡しと変数渡しの２種類がある．

 変数のデータ型はスカラー型のみでポインタ型は扱わない．具体的には整数型，文字型，論理型お42

writeln('letter =',letter);
if b = 'y' then43

writeln('word44

if c = 'y' then45
46

writeln('line=',word);=',line)end.

図3Fig. 3

部分解釈前のプログラム

Original program before partial evaluation.

よびそれらを要素に持つ配列型とした．
このように，簡単化されてはいるものの，プログラミ

ward slice のどちらでも抽出でき，また，そのとング言語の基本的な文の構造はすべて含んでいるので，

きに，PDG のうち制御依存とデータ依存の片方

拡張は容易に行うことができる．

だけを探索したり，希望の段階までを探索するこ

3.2

機

能

本ツールは以下のような特長を持つ．

ともできる．

 入力変数もしくは入力に相当する変数の値を定数 通常のデバッガと同様にプログラムのステップ実に固定することにより，部分解釈を行って，プロ

行，変数の参照，ブレークポイントの設定などがグラムの一部の機能のみを実現する部分のみを抽行える．

出することができる．

 プログラムスライスとして backward slice，for- 抽出したプログラム部分に対してもデバッグ作業

Vol. 37 No. 45

プログラムの依存関係解析に基づくデバッグ支援ツールの試作

program wordcount(in,out);
var a,b,c:char;in:array[0..1000] of char;i:integer;

パーザ部

プログラム

アナラ

letter,word,line:integer;
isinword:boolean;

begin
writeln('Count the letter?(y/n)');readln(a);PDGwriteln('Count the word?(y/n)');writeln('Count the line?(y/n)');i:=0;letter:=0;
line:=0;
while in[i]＜＞ EOF do begin

if a='y' then

スライサ部

部分評価部

letter:=letter+1;
if in[i]=EOLN thenline:=line+1;
i:=i+1end;

スライス起点情報

if a='y' then

入力制限情報writeln('letter =',letter);writeln('line =',line)end.

図4Fig. 4

部分解釈後のプログラム
Result of partial evaluation.

スライス結果を行える．

図5

 プログラムの抽出部分を一つのプログラムとして

Fig. 5

ツールの構成図Components of this tool.

構文的に正しくなるように修正し，保存できる．
3.3

ツール構成およびその動作

本ツールの構成図を図 5 に示す．本ツールは，ソー値の参照などのデバッグに必要な作業も行うことができる．

スコードの構文解析を行いつつプログラム中の各文を部分評価を行なう場合，ユーザは，まず，どの入力

PDG の各節点と対応付けるパーザ部，その結果に基づいて PDG を作成するアナライザ部，PDG を探索してスライスを得るスライサ部，PDG を利用してプロ変数をどの値に固定するのかといった情報を入力する．
よび構文木などの情報が部分評価部に渡される．また，グラムの部分評価を行う部分評価部，プログラムの実

それらをもとにして部分評価部で部分評価が行われ，行を行うインタープリタ部に分けられる．

結果として，プログラムの一部の機能のみを実現する

ユーザがデバッグの対象となるプログラムを入力す

その後，ツール内では，その入力制限情報と PDG おプログラムが生成される．

ると，ツールは，パーザ部で構文解析を行った後，ア

スライスを抽出する場合には，ユーザは，まず，ス

ナライザ部で依存関係の解析を行う．それらの解析がライサ部に，どの変数に関するスライスを抽出するの終了すると，PDG および実行に必要な構文木や変数

かといった情報を入力する．その後，ツール内では，の情報などが生成される．

そのスライス起点情報と PDG がスライサ部に渡され，ユーザはこの段階でツールにどの動作をさせるかをそこでスライスが計算される．そのスライス結果は，指定する．ユーザがプログラムを実行させた場合には，元のプログラムの部分プログラムとして出力される．

ツール内では，インタープリタ部にアナライザ部が生

また，部分評価部やスライサ部から出力された部分

成した構文木や変数の情報などが渡され，プログラム

プログラムもインタープリタ部で実行することができが実行される．その際，ユーザは，通常の実行だけでる．この場合にも上述のようなデバッグ作業を行うこ

なく，ステップ実行やブレークポイントの設定，変数とができる．このようにして，デバッグの対象を限定

部分評価結果6

Apr. 1996

情報処理学会論文誌
1

ward slice を求めることにする．こうして得ら

program coverage(input,output);2

var

A: array[1..5] of integer;4n: integer;5

れるスライス結果は図 9 中の網掛け部分としてSum, Max, Min, Mean: integer;3

参照される．ここで，スライスの起点となった
変数 Max には直接関係のない文（24,26,27 行目

procedure calc(var sum, max, min, mean: integer);

6

var

7

begin

28 行目の手続き呼出し文で参照している変数の8

i := 1 + 1;

9while i ＜= n do

10の文）がスライスに含まれているが，これらは，

i: integer;

値に影響を与える文であり，この手続き呼出文

begin

11

sum := sum + A[i];12

if A[i] ＞ max then13else if A[i] ＜ min then14
15

min := A[i];

16

(3)

mean := sum div n;

19

end;

に，レベルの設定を 1 などの適当な値に設定することにより得られる．

(4)

begin

21

n := 5;22

writeln('Please Input ',n,' values');23

readln(A[1],A[2],A[3],A[4],A[5]);24

Sum := A[1];25

Max := A[1];26

Min := A[1];27

Mean := A[1];28calc(Sum, Max, Min, Mean);29

writeln('SUM: ', Sum);30

writeln('MAX: ', Max);31

writeln('MIN: ', Min);32

writeln('MEAN

図6

この文にブレークポイントを設定し，スライス部分のみを実行させる．すると，この文自体は何度も実行されているにもかかわらず，Max の値が変化していないことがわかる．これは，こ: ', Mean)

end.

Fig. 630 行目の Max に直接定義を行っている文は，13行目の文である．これはスライスを計算する際

end;

18

33

イスに含まれる．

i := i + 1

17

20がスライスに含まれるため，これらの文もスラ

max := A[1]バグを含んだプログラム

Example of program including a bug.

の文で参照される変数が A[1] となっているた
めで，それを A[i] に修正することにより正し
い結果が得られる．
4.2

実行時間

本ツールを用いてプログラムを解析したときの解析
時間を表 1 に示す．この表には，実行したプログラム，
その中に含まれるコードの行数および手続き数，およすることにより，効率良くデバッグ作業を進めること

び，そのプログラムを Sun Sparc Station ELC 上でができる．

実行させた場合の解析時間（秒）が示されている．こ4.
4.1

実行および評価
簡単な例の解析時間とは，ツールのパーザ部およびアナライザ
部における実行時間であり，スライスの抽出，部分評
価の実行時間は含まれていない．

本ツールの実行例として，図 6 に示されるバグを含

表1

むプログラムをデバッグする例を考える．このプログ
ラムは，入力された 5 つの数の合計，最大，最小，平均を計算し，出力するプログラムである．

(1)

プログラムを解析し，インタープリタ部で実行させる．この実行結果が図 7 である．これを見ると，明らかに，最大値を示す MAX の値が誤っ(2)

Table 1

実行速度
Analysis speed.

行数

手続き数

解析時間 (秒)

wc

48

0

0.09

calendar

84

4

0.22

201

89

4

0.63

arraysum

93

13

0.07

230

13

3.95

program

pai

ている．

hanoi

28

2

0.1

この値を出力した変数（図 6 における 30 行目のmutual

95

4

0.91

変数 Max）に関するスライス（backward slice）
を抽出する．このとき，図 8 のようなウィンドウが現れる．この画面で，スライスを抽出した

スライスの抽出は， 2.2 節で述べたように，依存関係解析の結果生成された PDG を探索することによっい変数名や，CD および DD のどちらの依存関て行われるが，その時間は比較的短い．たとえば，表 1

するパスの長さなどの情報を入力する．ここでもかかわらず，スライスの抽出にかかった時間は 0.02

係について PDG を探索するか，PDG を探索

は，変数 Max に関して，CD，DD の両方の依存関係について PDG をできる限り探索して back-中のプログラム pai は，解析に 3.95 秒かかっているに秒であった. したがって，スライス計算の時間については，ここでは述べない．また，入力されたプログラ

Vol. 37 No. 4

7

プログラムの依存関係解析に基づくデバッグ支援ツールの試作

ムを実行する時間は，入力データに依存するため，これについてもここでは述べない．

5.

ま

と

め

また，表中のプログラム wc から語数のみを計算すプログラムから依存関係に基づいてスライシングやる部分を取り出すような部分評価にかかった時間は，部分評価を行い，バグに関係のある部分のみを抽出す

4.69 秒であった．これは部分評価の手続きではプログるデバッグ支援ツールを作成した．本ツールを用いる

ラムを 2 度解析したり，各文の解釈ごとに全大域変数

ことにより，プログラム全体を対象としていた従来のの組からなる状態をチェックしたりするオーバーヘッ

デバッガを用いるよりも効率の良いデバッグを行うこドによるものである．

とができると期待される．また，本ツールでは，プロ

4.3

実行結果

グラムの依存関係解析だけでなく，部分評価に必要なスライシングおよび部分評価を行なうと，プログラ

その他の情報を得るための解析も行い，保存している．

ムの参照部分を小さくできる．その割合は，入力プロ

それらは必要に応じて自由に利用できるので，デバッ

グラムおよび変数の指定方法などに依存するが，たとグ以外にも，それらの情報を利用するような作業（たえば，図 1 のプログラムは，スライシングの結果，38

とえば，保守 7) など）にも役立つと考えられる．

図 4 のプログラムは，部分評価の結果，46 行のプログるような依存解析アルゴリズム 2),10),12) を適用し，対行のプログラムが 28 行になった．また，図 3 およびラムが，26 行になった．
4.4

考

察

デバッグ時に，プログラムのうちバグに関係のある部分のみを抽出してその部分のみをデバッグの対象と今後の課題としては，ポインタ変数や構造体も扱え
象言語を拡張することなどがあげられる．
謝辞 本研究を行うにあたり，多大なご指導をいた
だいた，奈良先端科学技術大学院大学情報科学研究科の鳥居宏次教授に深謝いたします．

することにより，開発者のプログラムの参照範囲を小さくするという当初の目的は，本ツールを用いることにより実現できる．また，その依存関係情報は，１度解析すれば内部に保存できるため，同じプログラムに対しては，解析しなおすことなく別のスライス計算などの作業を行うことができる．
ただし，一般に元のプログラムが大きいときには，スライスも大きくなる 1) ．本ツールでは，スライス全体を参照するだけでなく， PDG を探索するレベルを任意に設定することができるので，注目している文に直接影響する文のみを抽出したり，データ依存もしく
は制御依存の一方だけを用いた PDG の探索もできる
ため，参照部分をさらに小さくすることができる．今後，プログラム全体ではなく，手続き単位でスライスを計算したり，実行したりできる機構があればさらに便利になると考えられる．
また，部分評価を行うと，式中の変数が定数に置き換えられる場合が起こるが，その場合でも式の意味は変わらない．ただし，部分評価により削除される部分にバグが含まれていた場合，当然そのバグは部分評価
結果には含まれない．しかし，本来，部分評価は入力
変数もしくはそれに相当する変数の値を固定すること
により，プログラムの機能を限定することなので，部
分評価によって削除される部分にバグが存在していたとしても，それはその時点で注目している部分ではな
い．したがって，その時点でのバグの原因究明には影響を与えない．

参 考 文 献1) Agrawal, H., Demillo, R. A. and Spa ord,
E. H.: Debugging with Dynamic Sllicing and
Backtracking, Software{Practice and Experience , Vol. 23, No. 6, pp. 589{616 (1993).
2) Choi, J.-D., Burke, M. and Carini, P.: EÆcient Flow{Sensitive Interprocedural Computation of Pointer{Induced Aliases and Side Effects, Conference Record of 20th ACM Symposium on

Principles ofProgramming

Lan-, Charleston, South Carolina, pp. 232{
245 (1993).
3) Coen-Porisini, A., Paoli, F. D., Ghezzi, C.
and Mandrioli, D.: Software Specialization Via Symbolic Execution, IEEE Transactions on
Software Engineering , Vol. 17, No. 9, pp. 884{
899 (1991).
4) Fritzson, P., Gyimothy, T., Kamkar, M. andShahmehri, N.: Generalized Algorithmic Debugging and Testing, Proceedings of the ACM
guagesSIGPLAN'91

Conferenceon

Programming, Vol. 26,
No. 6, pp. 317{326 (1991).
5) 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).
6) 二村良彦ほか: プログラム変換, 共立出版, chapter 4, pp. 63{79 (1987).
7) Gallagher, K. B. and Lyle, J. R.: Using ProLanguage Design and Implementation

8

Apr. 1996

情報処理学会論文誌

gram Slicing in Software Maintenance, IEEE
Transactions on Software Engineering , Vol. 17,
No. 8, pp. 751{761 (1991).
8) Lyle, J. R. and Weiser, M.: Automatic
Program Bug Location by Program Slicing, Proceedings 2nd International Conference
on Computers and Applications , pp. 877{883(1987).
9) Naoi, K. and Takahashi, N.: Detection of Infeasible Paths with a Path Dependence Flow
Graph, Transactions of the Institute of Elec-(平成 7 年 8 月 2 日受付)
(平成 8 年 2 月 7 日採録)
佐藤 慎一（学生会員）
昭和 46 年生．平成 6 年大阪大学基礎工学部情報工学科卒業．現在同大学大学院基礎工学研究科物理系専攻
情報工学分野博士前期課程在学中．
プログラムの依存解析の研究に従事．

tronics, Information and Communication En-

gineers , Vol. J76D-I, No. 8, pp. 429{439 (1993).
10) Pande, H. D., Landi, W. A. and Ryder,
B. G.: Interprocedural Def{Use Associations for C Systems with Single Level Pointers,IEEE Transanctions on Software Engineering ,Vol. 20, No. 5, pp. 385{402 (1994).
11) Ramalingam, G.: The Undecidability of Aliasing, ACM Transactions on Programming Languages and Systems , Vol. 16, No. 5, pp. 1467{
1471 (1994).
12) 佐藤 慎一, 植田 良一, 井上 克郎: 再帰やポインタを含むプログラムの効率的な依存関係解析法の提案, 信学技報, Vol. 95, No. 475, pp. 9{16 (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).

飯田

元（正会員）

昭和 63 年大阪大学基礎工学部情報工学科卒業．平成２年同大学大学
院博士前期課程修了．同年同後期課
程入学．平成３年大阪大学基礎工学
部情報工学科助手．平成７年奈良先端科学技術大学院大学情報科学センター助教授，現在に至る．平成６年大阪大学，工学博士．ソフトウェア
開発プロセスおよび開発支援環境，協調作業支援技術などの研究に従事． IEEE，日本ソフトウェア科学会
各会員．
井上 克郎（正会員）
昭和 54 年大阪大学基礎工学部情報工学科卒業．昭和 59 年同大大学院博士課程修了．同年同大基礎工学部情報工学科助手．同年 8 月ハワイ大学
マノア校芸術・科学学部助教授．昭和 61 年大阪大学基礎工学部情報工学科助手．平成元年同学科講師．平成 3 年 11 月同学科助教授．平成 7 年

12 月同学科教授，現在に至る．工学博士．ソフトウェ
ア工学の研究に従事．ACM，IEEE，電子情報通信学会各会員．

Vol. 37 No. 4

9プログラムの依存関係解析に基づくデバッグ支援ツールの試作nm−para−in

n−para−inmnb−para−in

if m<n thenma−para−in

n

n
m

a

temp:=abswap(m,n)nwhile n<>0 do
m

y

n
a:=b

x

temp

w:=m mod n
n

a

m
n
m:=n

b:=temp

w

b

n

n
n:=w

b−para−outma−para−outmgcd:=mgcd

mgcd−exit
writeln(’Input x and y’)a−para−in

gcd

b−para−inreadln(x,y)
bac:=gcd(a,b)

writeln(’x=’,x,’ y=’,y)

x

y
a

y

y

x

gcd

x

b
g:=gcd(x,y)

cxylcm:=(a div c)*(b div c)*cg

l:=lcm(x,y)
lcm

lcm

l
writeln(’lcm=’,l)lcm−exit
図2
Fig. 2

PDG の例The PDG.

writeln(’gcd=’,g)10

情報処理学会論文誌

図7
Fig. 7

プログラムの実行結果
Output of the program.

図8
Fig. 8

スライス選択画面
Select window.

図9

スライス結果（網掛けの部分がスライス）

Fig. 9Result of slicing(slices are shaded).

Apr. 1996