実行履歴 利用した

スプログラムの部分解析に基づく

スライス抽出技法の提案
芦田 佳行 大畑 文明 井上 克郎
大阪大学大学院基礎工学研究科情報数理系専攻〒 560-8531 大阪府豊中市待兼山町 1-3

Phone: 06-6850-6571 Fax: 06-6850-6574
E-mail: fasida, oohata, inoueg@ics.es.osaka-u.ac.jp
らまし
本研究では，静的解析と動的解析を組み合わせたプログラムスライス計算法を つ提案する．
スライス 文の実行履歴を用いて，実行されなかった文 スライスに不要な文 を取り除く． プログラムの部分解析 関数の実行履歴を用いて，実行された文だけを静的
動的なデータ依存解析 制御依存解析を静に解析することで依存解析のコストを削減する．
的に，データ依存解析を動的に行うことで，より正確なデータ依存関係を抽出する． 配列，ポインタ解析 ポインタ，配列のデータ依存解析のみを動的に，その他の依存解析を静的に行うこと比較して実行時間の削減をめざす．
とで，(1)Statement-Mark
)
(2)
(3)

:

:

(

(3)

:

:

4

(4)

ワ ド プログラムスライス，静的解析，動的解析，実行履歴

Proposal of Slicing Algorithms Using Static andDynamic Analysis Information
Yoshiyuki Ashida, Fumiaki Ohata and Katsuro Inoue
Graduate School of Engineering Science, Osaka University
1-3 Machikaneyama-cho, Toyonaka, Osaka 560-8531, Japan
Phone: +81-6-6850-6571 Fax: +81-6-6850-6574
E-mail: fasida, oohata, inoueg@ics.es.osaka-u.ac.jp

Abstract
In this paper, we propose four slicing algorithms using static and dynamic analysis information. (1) Statement-Mark Slice : removes the unnecessary statements using a execution historyof the statements. (2) Partial Program Analysis : reduces the static analysis cost using invocation history of procedures. (3) Dynamic Data Dependence Analysis : extracts precise data
dependence relations using dynamic data dependence analysis. (4) Array and Pointer Analysis: improves the eciency of analysis(3) by dynamically analyzing pointer and array variables
only.
Key words program slice，static analysis，dynamic analysis，execution history

まえがき

1

[12]

プログラムスライスとは，直観的には，ある文 のある変数 の値に影響を与え得る文の集合である．プログラムスライスを計算するには，プ
ログラム文間の依存関係を把握する必要がある．

sv

プ ログ ラムスライスは，デバッグ，テスト，プ
ログラム解析，プログラム理解，プログラム統合等に有効であると考えられている．また我々もデバッグ，保守にプログラムスライスが有効であることを確認した．

[3, 4, 12][2, 6, 7]

プログラムスライスは，静的スライスと動的ス
ライスの 種類に大別される．前者は，ソースプ
ログラムの解析し ，全ての入力データを考慮した依存関係を抽出する．後者は，実際に入力データを与えて実行することによって，特定の入力において生じる依存関係をのみを抽出する．静的スライスは，全ての入力を考慮するため，不必要な情報を含むことがあり，その結果，スライスサイズ
が大きくなってし まう．動的スライスは，実行系
列 実際に実行された文の並び を扱うため，スライスサイズを減らすことができるが，全ての実行系列を保存しそこから依存関係を抽出するために，多大な時間，空間コストを必要とする．

2

(

)

スライスの計算に必要なコストとスライスサイ
ズはトレード オフの関係にあり，さまざ まな研究がなされている．
本研究では，動的情報と静的解析を組み合わせることで，スライス計算に必要なコストを削減する手法を提案する．また，ポインタや配列といった，静的解析が困難であるものについても，動的情報を利用した解析方法を提案する．以降， では，
静的スライス，動的スライスについて述べる． では，スライスについて述べる．
では，実行履歴を使ったプログラムの部分解析法
について述べる． では，動的にデータ依存関係解析を行う方法について述べる． では，動的にポインタ，配列の解析を行う方法について述べる．
最後に で，まとめと今後の課題について述べる．

2

Statement-Mark
5

3

4

6

7

2
2.1

プログラムスライス
静的スライス

今，ソースプログラム p 中の文 s1 ，s2 について考える．次の条件をすべて満たすとき，文 s1 から
文 s2 への制御依存 ControlDependence，CD があるという．

(

 文 s1 が条件文である．

)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*xend;function Cube(x : integer):integer;
begin
Cube := x*x*x
end;
begin
writeln("Squared Value ?");
readln(a);writeln("Cubed Value ?");
readln(b);writeln("Select Feature! Square:0
Cube: 1");
readln(c);if(c = 0) thend := Square(a)else
d := Cube(b);if (d < 0) thend := -1 * d;writeln(d)end.

図1: ソースプログラム

 文 s2 が実行されるかど うかは，文 s1 の結果に依存する．
この関係を s1 s2 ，もし くは CD s1 ; s2 と表す．
また，以下の つの条件をすべて満たすとき，
文 s1 から 文 s2 へ 変数 v に 関し てデ ータ依存
DataDependence，DD があるという．
文 s1 で変数 v を定義している．
文 s2 で変数 v を参照している．
文 s1 から文 s2 への実行可能なパスが少なくとも一つは存在し，さらに，そのパスにおいて文s1 から文 s2 間に変数 v を定義している文が存在しない．
この関係を s1 v s2 ，もしくは DD s1 ; v; s2 と表す．
ソー スプ ログ ラムに 含まれ るこれ らつの依 存 関 係を 表 すた め ，プ ログ ラ ム 依 存グ ラフ
P rogramDependenceGraph，P DG が用いられ
る．
の各節点は，プ ログ ラムに含まれる代入文，入出力文，条件判定文，手続き呼出し文などの各文を表し ，辺は つの文間の依存関係を表す．図 ののソースプログラムに対応する
は図 のようになる．
プログラム中の文 s の変数 v に関する静的スラ
イス 組 s; v をスライシング基準と呼び，どの文に関してスライスを計算するのかを表す． は，スライシング基準に対応する節点から 制御依存辺，
データ依存辺を逆向きに辿って到達できる節点に

-

(

3

(

)





-

(

)

(

)

PDG

1 Pascal
PDG 2
( ( )

)

2

)

2

SquareMainwriteln("Sq ...

readln(a)x-paraax

writeln("Cu ...

readln(b)Square:=x*x
writeln("Sel...

readln(c)SquareSquare-exit

Squarecab

if c = 0

Cube
d:=Square(a)x-paraxdb
Cube:=x*x*x

d:=Cube(b)dCube
if d < 0

Cube

Cube-exit

d:= -1 * ddwriteln(d)DataDependence

図Control
Dependence

2: プログラム依存グラフ

対応する文の集合となる{1 ．
例えば，図 のプログラムの文 の変数 d をス
ライシング基準として静的スライスを計算すると，
図のように
文， ， 行 を除いたすべての文が含まれる．

1

2.1

2.2

24

write (12 14 16 )動的スライス

静的スライスの計算は，ソースコード を対象として依存関係を計算し ，スライスを抽出していたが，動的スライスの計算では，依存関係を計算す
る対象は実行系列である．実行系列とは，ある入力を与えプログラムを実行したときの，実際に実行された文の列をいう．また，実行系列中の p 番
目の文の実行のことを実行時点 p と呼ぶ．
実 行 系 列 e 中 の 実 行 時 点 r1 ，r2 に つ い て
考え る ．次の 条 件を す べ て 満 た すと き ，実 行
時 点 r1 か ら 実 行 時 点 r2 へ の 動 的 制 御 依 存
DynamicControlDependence，DCD があるという．
実行時点 r1 が条件文である．
実行時点 r2 が実行され るかど うかは，実行時
点 r1 の結果に依存する．
次の条件をすべて満たすとき，実行時点 r1 から 実行時点 r2 へ変数 v に 関し て動的デ ータ依
存 DynamicDataDependence，DDD があるという．
実行時点 r1 で変数 v を定義している．
実行時点 r2 で変数 v を参照している．
実行時点 r1 から r2 の間に変数 v を定義している実行時点が存在しない．
{1データ依存辺を辿るには，まず v に関する辺を辿り，以

(

)




(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

)





降，影響を与える変数の辺のみを推移的に辿る．

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*xend;function Cube(x : integer):integer;
begin
Cube := x*x*x
end;
begin
readln(a);readln(b);readln(c);if(c = 0) thend := Square(a)else
d := Cube(b);if (d < 0) thend := -1 * d;writeln(d)end.

3: 24 行目変数 d に関する静的スライス

図

(

)

動的スライスのスライシング基準 x，r ，v は，
入力 x，実行時点 r ，変数 v の つからなる．スライシング基準 x，r ，v に対応する節点から動的制御依存辺，動的データ依存辺を逆向きに辿って到達できる節点に対応する文の集合となる．
図 のプログラムにおいて，スライシング基準
が入力 a
，b
，c
，実行時点
行
目の文を実行した時点 ，変数 d である動的スライスの計算結果を図 に示す．

(

1

2.3

3

)

( = 2 = 3 = 0)
)
4

13(24

静的スライスと動的スライスの特徴

静的スライスの計算は，プログラムを実行せず
ソースプ ログ ラムの依存解析を行い，得られた上で行う．
を構築する際，制御依存関係はプログラム構造を調べることで容易に求まる．
また，データ依存関係はデータフロー方程式 を解くことで求まる．静的スライス計算の複雑さは，その評価の基準によって変わるが，現実には比較的短い時間で計算できる．しかし ，すべての実行可能なパスについて考えているため，静的スライスに元のプ ログラムの大部分が含まれてしまい，デバッグやプログラム理解等の効率向上は期待できない場合がある．

PDG

PDG

[1]

[11, 9]

一方，動的スライスは特定の入力でプログラムを実行して得られる実行系列から計算するため，その実行に関係のない部分はスライスに含まれない．
つまり，一般的に抽出されるサイズは静的スライ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

図

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*x
end;

begin
readln(a);Call-Mark
Call-Mark[5, 8]

関数の実行履歴という簡単な動的情報を用いる
ことで，動的スライスの欠点であった実行時のオー
バーヘッド を大幅に減らしている．

writeln(d)
end.

3.2

4: 入力データ (a = 2; b = 3; c = 0)，24 行目変

スよりも小さくなる．
特定のテストデータに対して不具合が発生し，その欠陥の原因をプログラム中で捜すことを考える．
静的スライスでは，そのテストデータでは実行されていないパスに関する依存関係まで計算してしまうため，不具合の原因とは全く関係のない部分
までスライスに含まれてしまうが，動的スライス
はテストデータの実行に関連する部分の中から計算するため，不具合に関係のない部分がスライスに含まれるようなことはない．
このように特定のテストデータで存在するフォー
ルト位置特定を行う場合には，動的スライスは非常に有効となる．
動的スライスの計算には，プログラム実行前の解析は必要ではないが，実行中に動的データ依存
関係と動的制御依存関係の情報を主記憶等に記憶しなければならない．このため，動的スライスの計算には多くの記憶領域と計算時間を要する．また，動的スライスを抽出する対象となる実行系列
はプログラムが実行した文の数に比例することか
ら，入力データによっては非常に大きくなるために，抽出する時間も非常に要することがある．
Statement-Mark スライス

本節では ，文の実行履歴を用いた

我々は，静的スライスと動的スライスの中間に位置付けされるものとして，スライスを提案している．
スライスの計算
手順は，次のようになる．

かった文の一部を特定し，それらの文をスライスから取り除く．

readln(c);if(c = 0) thend := Square(a)Mark スライスを提案する．

Call-Mark スライス

(1) 静的スライスと同じ方法で PDG を作成する．
(2) プログラムに入力データを与えて実行させる．
その際，関数の実行履歴 (各関数が呼び出されたか否か ) を取得する．
(3) 取得した関数の実行履歴を用いて実行されな

数 d に関する動的スライス

3

3.1

Statement-

Statement-Mark スライス

Call-Mark スライスでは，動的情報として関数の実行履歴を用いているが，これを文の実行履歴にすれば，取得すべき情報は多くなるが，より正確なスライスを抽出することができると考えられる．
そこで，文の実行履歴を用いたスライスを提案する．

Statement-Mark

3.2.1 アルゴ リズム

Call-Mark スライスと同じ手順で計

基本的には算を行うことになる．

(1) 静的な依存関係解析を行い，PDG を構築する．
(2) 入力データを与えて実行する．ある文が実行されるごとに，対応する PDG の節点に対してフラグを立てる．

(3) PDG において，スライシング基準に対応する
節点から依存辺を逆向きに探索する．実行されていない節点に着いた時は， その節点も含めてその節点以降の探索を止め，他の分岐を探す．

()

3.2.2 例

1

図 のプログラムについてのスライシング基準
が入力 a
，b
，c
，文
の変数 d である
スライスの計算結果を図 に示す．

( = 2 = 3 = 0)
Statement-Mark

24

5

動的スライスと全く同じ結果が得られているが，一般に，動的スライスは
スライ
スの部分集合である．

Statement-Mark

3.2.3 考察Statement-Mark スライスを，実際にスライシン[9] に実装し，スライスサイズと実行時間

グツール

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*x
end;

表program

P1
P2
P3

begin

4.1

62
87
62
903
5,318 31,635(Pentium-II 300MHz with 256MB Memory)

部分解析法

[11]

2

1: スライスサイズ (行)Call-Mark

27
176
324

22
155
166

Statement-Mark

dynamic

15
141
148

(Pentium-II 300MHz with 256MB Memory)( 1を計測した． 表 ，表

14
139
50

2)

Call-Mark スライスと比較して，スライスサイズ
が 1030%の減少が見られ，実行時間は 1530%増加している．
静的スラ イスと比較すると ，スライスサイズがの減少が見られ ，実行時間は増加している．

2055%

3060%

ソースプログラムの部分解析

静的スライスにおいては，入力データを考慮せずに全ての可能な実行パスを想定して依存関係解析を行っている．しかし 度入力データを与えて実行すれば ，その実行において使用されていない文が特定できる．使用されなかった部分を解析しないことによって，

1(1) スライスのサイズの減少(2) PDG 構築のコストの削減が期待できる．

dynamic-Mark(1) 関数内の依存関係解析(2) プログラム全体の依存関係解析

5: 入力データ (a = 2; b = 3; c = 0)，24 行目変
数 d に関する Statement-Mark スライス

4

47
53
4,104

( )

図

P1
P2
P3

38
48
4,064

Statement

ある実行 E において使用された関数の集合を
UsedF E とする． のアルゴ リズムは，

writeln(d)end.

staticCall-Mark

スライス計算法を改良した，部分解析法を提案する．

readln(c);if(c = 0) thend := Square(a)program

2: 実行時間 (ms)Call-Mark

readln(a);表static( )となっている．そこで，f = UsedF E である関
数 f の依存解析は行わなければよい．また，プロ
グラム全体の解析の際には，関数呼び出し文の出現によるの接続等の作業を行わない．

PDG

この部分解析法は，関数の実行履歴を利用している．このため，結果としてスライスと等しいスライスが得られる．また，文の実行履
歴を利用することで，さらに効率良い依存関係解
析が期待できる．その際に得られるスライスは，
スライスと等しい．

Call-MarkStatement-Mark
4.2

適用例

部分解析法は，何らかの形で実行されていない文を調べ，その部分を解析しないことによって，そのコストを削減するというものである．
そこで，関数の実行履歴を用いることで，ソースプログラムの何 が不要になるかを調べた．

%

ftp対象となるプログラムとして， を選んだ．このプログラムは，ソースプログラムが行で，定義された関数が個である． を実際に実行
し ，使われなかった関数をソースプログラムから削除し，解析が必要な部分がどれだけかを調べた．

130

ftp

6294

2 回の実行を行い，データを取得した．
1 回目は簡単な実行で，ls でファイルを確かめ，get でファイルを獲得し，bye で終了するというものであった．この実行では，30 個の関数が使用され，必要な部分は 3227 行 (51.3%) であることが分かった．

2 回目は 73 個のコマンドを実行するものであった．この実行では，87 個の関数が使用され，必要な部分は 4838 行 (76.9%) であると分かった．

1
2
3
4
5
6

a[0]:=0;a[1]:=1;
a[2]:=2;
readln(c);b:=a[c]+5;
writeln(b);

図
1
2
3
4
5
6
7
8

5.2

配列，ポインタの静的な解析は，コストがかかる上に完全な解析は期待できない．そこで，実行中にデータ依存関係を抽出する方法が考えられる．
実行中は，配列の添字，ポインタの値を把握するのは簡単である．動的スライスとの差異として，次の つが挙げられる．

6: 配列を含むプログラム

2

a=2;
b=1;
c=&a;
d=&c;
*c=5;
**d=b;
printf("%d",a);printf("%d",**d);

図4.3

 制御依存関係は静的に解析する．
 実行系列を保存することはしない．

これによって，動的スライス抽出に比べて実行時間の短縮を図る．

7: ポインタを利用するプログラム

Call-Mark スライス，Statement-Mark

スライス，部分解析法の特徴

Call-Mark関数の実行履歴を用いた部分解析法とスライス，文の実行履歴を用いた部分解析法とスライスは，共にスライスのサイズとしては同じになる．

Statement-Mark2

部分解析法を用いれば ，他の つのスライス技
法と比べて，依存関係解析のコストを減らすことができる．しかし，入力データに依存したを構築するため，別の実行を行った際には，新たにを再構築する必要がある．

PDG

PDG
5

動的なデータ依存関係解析

5.1

配列，ポインタの解析

6

図 は，配列を含んだ簡単なプログラムである．
文 の変数 c の値が分からないため，文 の配列 aが文全てにデータ依存していると解析される．

6

13

alias

ポインタ解析では，ポインタによるによって，陽には表れないデータ依存関係が発生する．その依存関係を知るために，各ポインタが何を指しているかを把握しておく必要がある．
グ
ラフを使った手法などが提案されているが ，多大なコストを必要とするものが多く，静的に解析する方法には限界がある．

point-to[10]7

図 は，ポインタを利用する簡単なプログラムである．文 の変数 a は文 によって定義されているが，こういった依存関係は簡単には解析でき
ない．

7

6

5.3

概要

実行中に，ある文 s である変数 v が 参照された時，v がどの文 t で定義されたかが分かれば ，DD t; v; s ど いうデータ依存関係があることが分かる．逆に言えば ，v を定義してる文さえ分かればデータ依存関係を知ることができる．

(

()

)

そこで，全ての変数に対して，その値を定義したのはどの文か，という情報を持たせておき，その変数の参照があった場合には，その情報からデー
タ依存関係を把握する．
また，得られたデータ依存関係は各文に持たせる．各文 s は集合 DDS s を持つとする．このDDS s の要素は， つの要素からなる組であり，依存関係の原因となる変数 v ， s がデータ依存している文 となっている．

()

(\

2

")

5.4

配列変数を静的に解析する際に，配列の添字の値を把握するのは困難であり，それゆえ不要に多くの依存関係を抽出してしまうことがある．

6

方針

()

" \

アルゴリズム

ある実行時点において，変数 v を最後に定義した文を DefS v とする．ここで v は，動的に生成される変数も含めた全ての変数を考える．配列では，各要素にも DefS を考える．

()( ) =  とする．

(1)ある文 s を実行する前に，DDS s(2)入力データを与えてプログラムの実行を行う．

今，文 s が実行されたとする．

 文 s で 変 数 v が 参 照{2 さ れ た 場 合 ，
DDS (s)DDS (s) [ (v; DefS (v ))．とする．

 文 s で変数 v が定義された場合，DefS (v) =s とする．

{2ポインタ変数が出現した場合，何が参照されたかを判断する際に注意が必要となる．例えば，代入文の右辺や出力文などに   v という 2 階のポインタが現れた場合，v ，v ，  v が参照されたと考える．また，代入文の左辺に現れた変数は普通参照されたとは考えないが，例えば v という一階のポインタが現れた場合は，v を参照したと考える．

表3: 図 6 のプログラムにおける，各実行時点での DefS の推移
実行文
1
2
3
4
5
6

a[0]
1

a[1]

a[2]

b

c

3

1
2
3
4
5
6

4

5

()



5.5

)

( ) 6=
()






(

PDG

() =

g

( ) f( )g

-

-

適用例

5.5.1 図 6 のプログラム

1, 2, 33[0] [1] [2]3
DefS (a[0]) = 1; DefS (a[1]) = 2; DefS ([2]) = 3

では ，それぞれ 変数 a ; a ; a
文が 定義されているので ，文 を実行し た時点で
となる．

4

( )=4

文 では，c を定義しているので，DefS cとなる．

5 で は ，a[0]; c を 参 照 し て い る の で ，DDS (5)
DDS (5) [ (a[0]; DefS (a[0])) [(c; DefS (c))．つ ま り，DDS (5) = f(a[0]; 1),(c; 4)g となる．
文

5.5.2 図 7 のプログラム

4

各実行時点における DefS の推移を表 に表す．

では，それぞれ変数 a; b; c; d が定義さ文れているので，文 を実行した時点で DefS a; DefS b; DefS c; DefS d
と
なる．

1

()=2

4

()=3

( )=
()=4

5 では，c を参照しているので，DDS (5) !
 [ (c; DefS (c))．つまり，DDS (5) = (c; 3) となる．また，c を定義しているので，DefS (c) =5(DefS (a) = 5) となる．
文 6 で は ，b，d，d を 参 照し て い る の で ，DDS (6) = f(b; 2); (d; 4); (d; 3)g となる．
さらに ，文 6 では   d を 定義し ているので ，Def (  d) = 6(DefS (a) = 6) となる．
文 7 では，a を参照しているので，DDS (7) =
文

a
1

b

c

2

3

5
6

d
4

f(a; 6)g となる．
文 8 では ，d; d;   d を 参照し て いるので ，DDS (8) = f(d; 4); (d; 3); (  d; 6)g となる．
5.6

考察

本アルゴリズムでは，全ての変数に対して DefS
を考える必要がある．このため，大きなメモリ空間を必要とする可能性がある．また，動的スライスほどではないとしても，実行時間が大きくなってしまう．
そこで，配列やポインタの解析のみを動的に行
い，その他の解析は静的に行う方法が考えられる．

各実行時点における DefS の推移を表 に表す．

1, 2, 3, 4

4: 図 7 のプ ログラムにおける，各実行時点で
実行文

2

この作業によって得られた DDS s は，全てのデ ータ依存関係を表し ており，DDS sv; t DD t; v; s が成り立つ となっている．
(3)集合 DDS を使ってを構築する．文 s の解析において，DDS s  の間，次の操作を繰り返す．
DDS s
DDS s
v; t ．
vs を引く．
データ依存辺 ts が制御文であれば，その制御文内の全ての
文 t に対して，制御依存辺 st を引く．

f( )j

表の DefS の推移

6

配列，ポインタ解析

6.1

概要

ここで提案する手法は，配列，ポインタのデー
タ依存解析のみを動的に行うものである． 節の手法よりも実行時間の短縮，空間コストの削減が期待できる．

5

本アルゴ リズムで仮定している言語は，ポイン
タで指すことができる変数は new などによって動的に生成された変数と限る 例．

( : Pascal)

上記の仮定により，動的に生成された変数，配列の各要素についてのみ DefS を考えればよい．
6.2

アルゴリズム本アルゴ リズムとみを述べる．

5 節のアルゴ リズムの差異の 配列の個々の要素と動的に生成された変数に対( [ ])

してのみ，DefS a i を考える．

 PDG 構築の際は，ポインタ，配列に関する依存関係解析が必要な場合のみ DDS を使った解析(5 節) を行い，その他は静的な依存関係解析を
行う．
7

まとめ

本研究では，動的情報と静的情報を組み合わせた手法を提案した．

(1) Statement-Mark スライス (3 節)(2) プログラムの部分解析法 (4 節)(3) 動的なデータ依存関係解析法 (5 節)(4) 動的なポインタ，配列解析法 (6 節)(1),(2) に関しては，コンパイラ (インタプ リタ)のわずかな変更で動的情報を取得することが可能である．しかし ，に関しては，実行中に依存関係解析を行うため，特別なコンパイラ インタ
プ リタ が必要となる．

(3),(4))((2)(4) を実装し，評価する

今後の課題として，ことが挙げられる．

参考文献[1] Aho, A.V., Sethi, R., and Ullman, J.D.
: \Compilers: Principles, Techniques, andTools", Addison Wesley, Massachusetts,
1986.
[2] 芦田, 西松, 楠本, 井上 : \プログラムスライスに基づいたデバッグ支援システムの評価のための追証実験 第 58 回 (平成 11 年前期) 全
国大会, 講演論文集 (1)",, pp. 259{260, 1999.
[3] Gallagher, K.B. and Lyle, J.R. : \Using
program slicing in software maintenance",
IEEE Transactions on Software Engineer-, pp. 751{761, 1991.
[4] Horwitz, S. and Reps, T. : \The Use of Program Dependence Graphs in Software Engineering", Proceedings of the 14th International Conference on Software Engineering,pp. 392{411, 1992.
[5] 地平, 西松, 楠本, 井上 : \関数呼び出し履歴を利用したプログラムスライスの提案と実現",
信学技報, SS98-7, pp. 9{15, 1998.
[6] 西江, 神谷, 楠本, 井上 : \プ ログ ラムスラ
ing, 17(8)イスに基づくデバッグ支援ツールの実験的評
価 ソフトウェアシンポジウム 97 予稿集

",
, pp.
142{147, 1997.
[7] 西松, 楠本, 井上 : \フォールト位置特定におけるプログラムスライスの実験的評価", 電子情報通信学会技術研究報告, SS98-3, pp. 17{24,1998.
[8] Nishimatsu, A., Jihira, M., Kusumoto, S.
and Inoue, K. : \Call-Mark Slicing: AnEÆcient and Economical Way of Reducing Slice", Proceedings of The 21st International Conference on Software Engineering,Los Angeles, CA, USA, 1999.
[9] 佐藤, 飯田, 井上 : \プログラムの依存関係解析に基づくデバッグ支援システムの試作", 情処学論, Vol. 37, No. 4, pp. 536{545, 1996.
[10] Steensgaard, B. : \Points-to analysis in almost linear time", Technical Report MSRTR-95-08, Microsoft Research, 1995
[11] 植田, 練, 井上, 鳥居 : \再帰を含むプログラ
ムのスライス計算法", 信学論, Vol. J78-D-I,
No. 1, pp. 11{22, 1995.
[12] Weiser, M. : \Program Slicing", Proceedings of the Fifth International Conference on, pp. 439{449, 1981.

Software Engineering