効率と精度を考慮したプログラムスライスの抽出法の提案
西松 顯

井上 克郎

大阪大学大学院基礎工学研究科情報数理系専攻〒 560-8531 大阪府豊中市待兼山町 1-3 基礎工学研究科 井上研究室

Phone: 06-850-6571 Fax: 06-850-6574
E-mail: fa-nisimt, inoueg@ics.es.osaka-u.ac.jp

あらまし
本研究では，複数の効率の異なるプログラムスライス抽出技法の生成する依存関係情報を共有，再利用し ，効率と精度を考慮したプログラムスライス抽出技法を提案する．従来の手法では複数の依存関係解析アルゴ リズムを持つような場合，アルゴ リズム間で依存関係情報を共有，再利用することができなかった．あるアルゴ リズムが生成した依存関係情報が存在している場合でも，他のアルゴ リズムにより，その依存関係情報は利用できないために，新たに依存解析を最初から行う必要があった．本手法ではアルゴ リズム間で依存関係情報を共有，再利用可能にすることで，複数の依存関係解析アルゴ リズムにおいてスライス計算が効率良く行うことが可能である．本手法は効率及び精度の異なる 3 種類の依存関係解析アルゴ リズムを対象としている．
キーワード プログラムスライス，効率，精度

Proposal of a Slicing Algorithm and Its EÆciency and Accuracy
Trade-oAkira Nishimatsu and Katsuro Inoue
Graduate School of Engineering Science, Osaka University
1-3 Machikaneyama-cho, Toyonaka-shi, Osaka 560-8531, Japan
Phone: +81-6-850-6571 Fax: +81-6-850-6574
E-mail: fa-nisimt, inoueg@ics.es.osaka-u.ac.jp

Abstract

In this paper, we propose a new slicing algorithm considering eÆciency and accuracy tradeo . This algorithm consists of three kinds of the dependency analysis algorithm with thestatements in the source program. The dependency information is shared and reused between
these dependency analysis algorithms. By using our technique, a program slice is eÆciently
computed with the di errent dependency analysis.
Key words program slice，eÆciency，accuracy

1 まえがきプログラム P のスライスとは，直感的には P 中のある地点 n およびある変数 v に対して，n における v の値に影響を与える P 中の各文や式の集合を言う．すべての可能な入力データに対して解析したものを静的ス
ライス，特定の入力データに対して解析したものを動的スライスという (本論文では静的スライスのみを扱う
ので，以下単にスライスと言えば，静的スライスを意味するものとする)．スライスの技法は Mark Weiser [11]によって提案され , 当初はプログラムのデバッグを支援するために使われていたが，現在では，デバッグだけ
でなくテストや保守，プログラム合成などにも利用されている [3, 9]．
当初，スライス計算の対象となるプログラム言語は，非常に単純な言語であったが，実用的な言語 (例えば，C言語) にスライスを適用すると，さまざ まな問題点が指摘されるようになった．その問題点とは，『 スライスに含まれるべきでない文がスライスに含まれる．
』『スライスに含まれるべき文がスライスに含まれない．
』の 2 点である．例えば，構造化されたプログラム言語では，Weiser
が提案している手法により依存解析が可能であるが，非構造化な文 (break，continue 等) を含むようなプログラ
ムに対しては，Weiser が提案している手法では，正確な依存解析が行えない．正確な依存解析が行えない場
合には，スライスを用いてフォールト位置特定を行う際に，スライス内にフォールトを含まないような事も生じて来る．そこで，これまでに依存関係の正確性を向上させるような研究が多数されている (Calling Context[3]，関数間制御依存関係 [7]，statement side-e ect[2, 5] 等)．
依存関係の正確性を向上させるにつれ，スライス計
算アルゴ リズムも複雑になり，大規模なソフトウェア
でスライス計算には多くの時間を要するようになった．
例えば，約 28000 行のプログラムに対してスライスを計算するために，約 2 時間を要するという報告もされている [12]．そこで，スライスの正確性とスライス計算に要する時間とのトレード オフを考慮する事が必要になってきた [1]．この問題に対して，Atkison らは，ユーザがスライスの正確性を制御できるようなシステムを提供する事で，解決できる事を示した．さらに，Tonella
らは，3 種類の正確性の異なるアルゴ リズムを有するシ
ステムを開発し 、ユーザにスライス計算アルゴ リズムを指定できるようにした [4]．しかし ，これらの研究においては，各依存解析方法により得られた依存解析情報を共有していないために，依存解析情報の再利用ができず，それぞれの依存解析方法に対して同様の解析を何度も行う必要がある．
本研究では，複数の効率の異なるプログラムスライ
ス抽出アルゴ リズムの生成する依存関係情報を，各アルゴ リズム間で共有，再利用し ，効率と精度を考慮したプログラムスライス抽出法を提案する．各スライス
抽出アルゴ リズム間で共有な可能なデータ構造を定義
し ，その構築方法を述べる．また，あるスライスアルゴ リズムによって生成された依存関係情報を別のスラ
イスアルゴ リズムで利用する方法についても述べる．
以降，2．ではスライスの計算手順と計算効率について述べる．3．では共有可能な依存関係情報のデータ構
造および構築法について述べる．4．では共有可能な依存関係情報を利用したスライス計算方法について述べる．最後に，5．でまとめと今後の課題について述べる．

2 プログラムスライス
2.1

スライス計算手順

図 1に通常多く用いられるスライスの計算手順を示
す．スライス計算手順は，2 つのフェーズに分けられる．
以降，2 つのフェーズについて述べる．
2.1.1

Phase 1

フェーズ 1 では，ソースコード を入力とし ，依存関
係解析を行い，プログラム依存グラフを出力する．プ
ログラム依存グラフ (Program Dependence Graph．以降，PDG と呼ぶ) とは，プログ ラム中の文間の依存関係をグラフに表現したもので，各節点は文を，各辺は依存関係を表す．依存関係には制御依存関係とデータ依存関係の以下の 2 種類がある．

 制御依存関係
今，ソースプログラム p 中の文 s1 ，s2 について考える．以下の条件を全て満たしているとき，文 s1 から文 s2 への制御依存 (Control Dependence，CD)があるという．
{{

文 s1 が条件文である．
文 s2 が実行されるかど うかは，文 s1 の結果に依存する．

 データ依存関係
今，ソースプログラム p 中の文 s1 ，s2 について考える．以下の 3 つの条件を全て満たすとき，文 s1
から文 s2 へ変数 v に関してデータ依存 (Data Dependence，DD) があるという．
{

文 s1 で変数 v を定義している．

{

文 s2 で変数 v を参照している．

{

2.1.2

文 s1 から文 s2 への実行可能なパスで，そのパスにおいて文 s1 から文 s2 間に変数 v を再定義している文が存在しない，というものが存在する．

Phase 2

フェーズ 2 では，フェーズ 1 で生成された PDG を用いてスライスを計算する．スライスを計算するには，まず，『どの文のどの変数に対してスライスを計算するか』を指定する．これをスライシング基準と呼ぶ．スライシ
ング基準は，文と変数の組から成る．指定された文に対応する PDG 上の節点から，推移的に依存辺を辿って到達できる節点に対応する文の集合がスライスとなる．

Phase 1

Phase 2

ソースコードPDG

図 2及び図 3を用いて，それぞれ，制御フローを考慮するかど うか，Calling-Context を考慮するかど うかに
よって得られるデータ依存関係ついて考える．
図 2の文 3 の変数 a とデータ依存関係である文を調べる．制御フローを考慮にいれる場合には，依存関係解析

 文 1 の a の定義が文 2 の定義により消去される．
 文 3 は文 2 の定義を参照している．

プログラム依存グラフ
・節点-文・辺-依存関係

制御依存辺
データ依存辺

図 1: スライス計算手順
2.2

効率

スライス計算において，ソースコードを PDG に変換
した後は，単に，グラフの到達性を判定する問題として処理できる [6]．従って，スライス計算における効率とは，
主にフェーズ 1 の依存関係解析の効率の事を言い，スライスの安全性を保ちつつ正確性を犠牲にしてい向上をはかるものとして，(1) 制御フロー，(2)Calling-Context
等がある．
制御フロー
プログラム中の制御の流れ，つまり，文の実行順序のことである．

Calling-Context
各関数/手続き呼出し文と各関数/手続き本体との
対応．

1 a=1
…
…

2 a=2
…
…

3 print(a)
…
…

4 a=3
図 2: 制御フローという情報を得ることができ，結果として，文 3 の変数
a とデータ依存関係がある文は，文 2 であることが分かる．一方，制御フローを考慮にいれない場合には，

 変数 a が定義されている文の情報を得る．
f1，2，4g
 文 3 の a は f1，2，4g の定義を参照している．
という情報を得ることができ，結果として，文 3 の変数
a とデータ依存関係がある文は，文 1，2，9 であることが分かる．このように，制御フローを考慮する場合には，正確な情報を得ることができるが，情報を得るた
めの計算量は多い，また，制御フローを考慮しない場
合には，情報は正確ではないが ，情報を得るための計算量は少なくてすむ．
図 3の文 3 の変数 a とデータ依存関係がある文を調べ
る．Calling-Context を考慮にいれる場合には，

 文 2 の関数に到達した時点で，関数 f 内を解析する．
 関数 f 内の解析後，main に戻るときに文 2 に戻る．という情報を得ることができ，結果として，文 3 とデー
タ依存関係がある文は，文 1，9 であることが分かる．一方，Calling-Context を考慮にいれない場合には，

int a;
main()
{
1
a=1;
2
f(2);
3
print(a);4
a=3;
5
print(a);6f(4);
7print(a);}f(int x)
{
8
if(x)
9
a+=x;
10 return;} 関数 f は，文 2，6 で呼ばれているという情報を持つ．
 関数 f 内の解析後，文 2，6 の両方に戻る．
という情報を得ることができ，結果として，文 3 とデー
タ依存関係がある文は，文 1，4，9 であることが分かる．
Calling-Context に関しても，制御フローの場合と同様に，情報の正確性と計算量の関係が言える．
制御フロー，Calling-Context の 2 つを考慮している
かど うかで，以下の 3 種類1の依存関係解析アルゴ リズ
ムが存在する [4]．

(1) CSFS(Context Sensitive Flow Sensitive)(2) CIFS(Context Insensitive Flow Sensitive)(3) CIFI(Context Insensitive Flow Insensitive)

図 3: Calling-Context

1

Calling Context を考慮にいれる場合には制御フローも考慮にいれる必要があるため CSFI は存在しない．

これら 3 種類のアルゴ リズムの計算量，情報の正確性を比較すると，表 1のようになる [4]．

表 1: アルゴ リズム比較

CSFS

CIFS

CIFI

多
高

中
中

少
低

計算量
正確性

3 提案する手法
3.1

しかし，このうち (2)(3) に関しては，それぞれ単独に実装している図 4と同様の手法を利用できるために，本研究では述べない．さらに，(5) に関しても，(2) と (6) を連続して行う事と同等であるため述べない．また，(6) に関しては，既に文献 [3] で，実現する手法が提案されているため述べない．よって，ここでは (4) に関して，また，(4) で再利用可能な PDG を生成するための (1) の手法についても述べる (図 5)．以降，4節で図 5の (1) について述べ，5節で (4) について述べる．以降，(1) を『 CIFI グ
ラフ構築』，(4) を『 CIFS グラフ構築』と呼ぶことにする．
(1)

従来の手法の問題点

文献 [4] では，2.2節の 3 種類のアルゴ リズム (CIFI，
CIFS，CSFS) を持つシステムを開発している．しかし，
このシステムは図 4に示すように，各アルゴ リズムにより得られた依存関係情報を共有していないために，ア
ルゴ リズム間での依存関係情報の再利用がされていな
い．例えば ，ある文のある変数に関するデータ依存関係を CIFI で計算した後に，さらに CIFS で計算しようとすると，CIFI で得られた依存関係情報を全く用いずに，最初から CIFS で計算を行う．
計算時間
プログラム

CIFI

プログラム

CIFS

プログラム

PDG
小

PDG
中

CSFS

スライスサイズ
CIFI

CIFS

スライス抽出スライス
大スライス抽出

スライス
中

PDG

CSFS

スライス抽出大

スライス
小図 4: 従来手法
3.2

研究の目的

本研究では，CIFI，CIFS，CSFS により得られた依存関係情報を共有，再利用することが可能な手法を提案する．本手法により，例えば CIFI により得られた依存関係情報を用いて CIFS を行うことができ，結果として単純に CIFS を行うよりも高速に行え，また，それぞれの解析手法により得られた依存関係情報を別々に管理するのではなく，単一のプ ログラム表現として扱えるため空間的コストが少なく済む．上記のようなシス
テムでは，以下の 6 種類の変換が必要となる．2 ．

ソースコード

(4)

CIFI

PDG

CIFI

CIFS

PDG

CIFS

CSFS

PDG

4

2

PDGCIFI とは，CIFI 依存解析アルゴ リズムにより生成される PDG を表す．他も同様である．

スライス

スライス抽出スライス

ここでは，『 CIFI グラフ構築アルゴ リズム』の出力となる PDG の構造について述べ，CIFI グラフ構築アルゴ リズムについて述べる．このアルゴ リズムは，関数内アルゴ リズムと関数間アルゴ リズムの 2 種類に分類できる．
4.1

プログラム表現

本節で述べる CIFI グラフ構築アルゴ リズムの生成する PDG は，次節で説明する CIFS グラフ構築アルゴ
リズムの入力となる構造を持つ．この PDG を一般的な PDG と区別するために，CIFI-PDG と呼ぶ．CIFIPDG は PDG と同様に，プログラム中の文を表す節点と依存関係 (表 2) を表す辺から構成される．また，関数間の依存関係を表現するために，表 3に示す特殊節点を用意する．図 6に示すソースコードに対する CIFI-PDG
を図 7に示す．

表 2: 依存辺(3) ソースコード ) CSFS ) P DGCSFS(6) P DGCIFS ) CSFS ) P DGCSFS

スライス抽出CIFI グラフ構築アルゴリズム(2) ソースコード ) CIFS ) P DGCIFS(5) P DGCIFI ) CSFS ) P DGCSFS

スライス

図 5: 提案する手法(1) ソースコード ) CIFI ) P DGCIFI(4) P DGCIFI ) CIFS ) P DGCIFS

CSFS

スライス抽出関数内の依存関係を表す辺
def-def

変数の定義-定義関係

def-ref

変数の定義-参照関係

control dependence

制御依存関係func-dependence

関数呼出し文と特殊節点間の関係

関数間の依存関係を表す辺
parameter

実引数と仮引数の関係

func-return

関数の返値と関数呼出し文の関係

表 3: 特殊節点
手続き外からの大域変数の影響を内部へ伝えるための節点で，その手続き内で定義/参照している

global-def-in

大域変数に対して，ひとつずつある
global-def-out

手続き内で定義された大域変数の影響をその外へ伝えるための節点で，定義/参照しているの大域変数に対して，ひとつずつある

global-out

関数/手続き呼出しによって関数が実行された後に，その関数から制御が戻って来るときに，その関数内の大域変数に与えた影響を呼出した関数 (手続き) に与えるための節点である．

parameter-in

関数/手続き呼出しの引数を表現するための節点である．各引数ごとに用意される．

parameter-out

関数/手続き呼出しの引数が，呼ばれた関数により，影響を受けている場合 (例えば，参照渡しで値が変更されたような場合)，呼んだ関数に制御が戻ってきたときに，その影響を伝えるための節点である．

actual-in

手続き/関数の実引数の手続き/関数内部への影響を伝えるための節点である．

actual-out

手続き/関数の実引数の手続き/関数外部への影響を与えるための節点である．

func-return

関数の戻り値を通して伝わる影響を検出するための節点で，各関数呼出しにひとつずつある．

func-exit

関数の戻り値を通して伝わる影響を検出するための節点で，各関数にひとつずつある．

…

a=4
b=f(a)
print(b)集合 DefV ariable は，ある文に到達する変数定義からなる集合である．

f(x){
f=x+2
}

(1) 〜 (4) を実行

Step 2．関数内の全ての文に対して，する．全ての文を実行すれば ，その関数の解析は終了する．さらに関数を解析終了後に，その関数内で定義した大域変数の global-out 節点を作る．

…
図 6: サンプルプログラム(1) 変数を定義している文なら，まず DefV ariable を検索する．同じ 変数の定義が 存在する場合には ，その 節点に def-def 辺を 引く．
存 在し な い場 合には ，その 関 数に 属す る

global-def-in 節点を作成し，def-def 辺を追加

actual-inxする．その後，その変数と節点番号の組をDefV ariable 集合に追加する．

a = 4
para-inab = f(a)f(2) 参 照 変 数 が 存 在 す る 文 の 場 合 には，DefV ariable 集合からその変数に対応

f=x+2

a

func-exit para-out

print(b)fxactual-out

func-exit

def-usedef-def

func-dependence

parameter

func-return

図 7: CIFI-PDG の例

4.2

関数内アルゴリズム

関数ご との CIFI-PDG の構築方法について述べる．
制御フローを考慮した解析では，文を複数回解析する可能性があるが，本手法のように制御フローを考慮しない解析では，各文を一回だけ解析するだけで良い．CIFIPDG を構築する際のアルゴ リズムは以下のようになる．
アルゴリズムInput:

AnalyzeFunction

関数 F

Output:F の CIFI-PDG

Step 1．以下の集合の初期設定を行なう．

DefV ariable = する組を検索する．もし 存在する場合には，その節点に def-ref 辺を追加する．ない場合には，その関数に属する global-in 節点を作
成し ，def-ref 辺を追加する．

(3) 解析対象の文が，if 文，while 文により入れ子構造を有する場合には，if 文/while 文から，その文に対して制御依存辺を引く．また，入れ子の深さが 2 以上の場合には，直接，入れ子になっている if 文/while 文にのみ制御依存
辺を引く．

(4) 解析対象の文が call 文であるとき，関数を越えて依存関係が存在する可能性があるために，4.1節で示した特殊節点及特殊辺が必要になる．パラメータが参照渡しである場合には，関数から出るときに値が変更されているかもしれない，また，大域変数等も関数内で変更されている可能性がある．大域変数に関
しては，関数呼び出し文に遭遇した時点では無視する．その関数呼び出し文以降に，その関数呼び出し文により大域変数を参照，定義する場合には，その関数呼び出し文に globalin 節点及び global-out 節点を用意する．これ

らの節点は，4.3節のプ ログラム内アルゴ リ
ズムにおいて処理される．
4.3

関数間アルゴリズム

本節では関数ごとの CIFI-PDG を連結し，プログラ
ムの CIFI-PDG を構築する方法について述べる．本手法では関数間の呼び出し関係を表す Call Graph 3を用
いて，関数ごとの CIFI-PDG を連結する．このとき，関数呼び出し文の特殊節点 (実引数，大域変数) と関数本体の特殊節点 (仮引数，大域変数) を辺でつなぐ．これにより関数間のデータ依存関係を表現できる．
関数内アルゴ リズムにおいて関数呼び出し文以降の文の解析では，大域変数を定義/参照すると，関数呼び出し 文の特殊節点 (大域変数) を用意した．しかし ，この時点で実際に関数内で値が再定義されているか，値の変更はないかど うかが判定できるため，もし 関数内で値が変更されていない場合には，その大域変数に関する特殊節点は削除する．このとき，削除された節点に引かれている辺は，ソースリスト中で前に存在する文に対応する節点へと引き直される．本アルゴ リズム
は，『 制御フローを考慮しない』となっているが，関数間のフローの制御に関しては Call Graph で判定できる範囲で制御フローを考慮している．しかし ，『 全ての制御フローを考慮する』場合と比較すると，再帰等を考慮しなくて良いため，関数間にまたがる依存関係の解析は 1 回だけで良い．
Call Graph を利用して，関数ごとの CIFI-PDG に連結するときのアルゴ リズムを以下に示す．
アルゴリズムInput:

A

優先探索して，ポストオーダーで順序付けする．

Step 1 で 決 定し た 順 序で 強 連 結 成 分を ひ
とつず つ選び ，関数単位の CIFI-PDG を 連結する．global-def-out 節点がある場合には ，対応する global-out 節点と paramter 辺でつなぐ．しかし，対応する global-out 節点が存在しない場合もある．
このときは対応する呼び出し 文に global-out 節点
を 生成し ，連結する．さらに ，対応する呼び 出
し 文においてもその変数の global-def-out 節点を生成し ，その global-def-out 節点と呼び 出し 文のglobal-out 節点を def-ref 辺でつなぐ．

Step 3．

各節点は手続き名で，手続き間の『呼ぶ-呼ばれる』関係

を，呼ぶ側から呼ばれる側への有向辺で表したもの．

aaaprint(a)a=3global-out

global-out

aglobal-def-out

global-def-out

図 8: 関数間連結 (その 1)

global-def-in

A

a

a:= 4

global-def-in

B

a

c

global-inaacall C

call B
global-out

global-inprint(a)aprint(a)P の Call Graph 上で強連結成分

Step 2．各強連結成分内の要素を任意の要素から深さ

call C

call B

プログラム P の CIFI-PDG

を抽出して，その集約グラフを作り，その根から深さ優先探索して，ポストオーダーで順序付けする (ただし，一回の探索ですべての節点に到達できないときは，未到達の節点がなくなるまで繰り返
し ，すべての節点を順序付けする)．

c

global-ina

PdgMerge

Step 1．プ ログ ラム

B

a:= 4

プログラム P 中の全ての関数 F の CIFI-PDG

Output:3

例えば，図 8の場合には，関数 B は global-def-out 節
点を持たないが，関数 C において変数 a が定義されていることを，関数 A に伝える必要がある．このとき上記のアルゴ リズムを用いると連結する順序は，C)B)A となる．関数 C の global-def-out 節点の存在により，関数B にも global-out，global-def-out 節点が作成され，最終的に関数 A にある関数 B の呼び出し文の global-def-in，
global-def-out 節点にも parameter 辺が引かれる．このようにして，変数 a に関するデータ依存は表現できる．
global-def-in 節点がある場合には，対応する global-in 節
点と paramter 辺でつなぐ ，しかし，対応する global-in
節点が存在しない場合もある．例えば，図 9の場合には，対応する呼び出し文に global-in 節点を生成し ，連結する．さらに，対応する呼び出し 文においてもその変数の global-def-in 節点を生成し ，その節点と呼び 出し 文の global-in 節点を def-ref 辺でつなぐ．

図 9: 関数間連結 (その 2)

5

CIFS グラフ構築アルゴリズム

本節では，4節により生成された CIFI-PDG を用いた
CIFS 解析の方法について述べる．
5.1

方針

4節で述べたように，プログラムを CIFI 解析によって CIFI-PDG に変換する際には，プログラム全体を対象として解析及び変換を行う．しかし，本アルゴ リズム
では，CIFI-PDG 全体を CIFS-PDG に変換するのではなく，必要な部分のみを変換する．必要な部分とは，あるスライシング基準に対するスライスに含まれる部分である．このようにする事で，抽出されるスライスに比例した時間で，スライス計算が可能となる．図 10の部
分的な変換について示す．図 10の左は，CIFI 解析により得られた CIFI-PDG を示している．次に，スライシ
ング基準として文 print(b) の変数 b を指定したときに，
CIFI-PDG を用いてスライスを計算する．図 10の右に，抽出されたスライスに含まれる文を灰色にて示しているが，スライスに含まれる文に関する依存関係のみがSlice = f(s; v )g
Sliced = 

再計算されている (太い実線は，CIFS 解析により計算されたデータ依存関係を表す)．

a=2

集合 Slice は 文と 変 数の 組から な る集合 ，集合
Sliced は文からなる集合である．

a=2

b=3
if b==aif b==ab=1

b=1

print(a)Slice 内の各要素について以下を繰り返し 実
行する．このとき注目する要素を (S; V ) とする．
Slice =  ならば終了する．

Step 2．

b=3

print(a)(1) 文 S の変数 V に関してデータ依存関係のある
文を CIFI-PDG を用いて計算する．このときデータ依存関係のある文を S ，また，文 S
で使用している変数を V とすると，全ての(S ; V ) を集合 Slice に追加する．ただし，集合 Sliced に文 S が存在する場合には追加し
0

0

0

print(b)CIFI 解析

print(b)

部分的 CIFS 解析

図 10: スライス計算手順

5.2

アルゴリズム

部分的な変換の実現方法，つまり，必要な部分 CIFS
解析方法について述べる．制御依存関係は CIFI 解析時に計算されているため，ここではデータ依存関係の計算が対象となる．CIFI-PDG を用いて，文 s の変数 v とデータ依存関係のある文 s0 を計算する場合を考える．まず，変数 v を定義している文を特定する作業が必要であるが，CIFI-PDG の def-ref 辺を逆方向に辿ることで特定できる．ただし ，図 10の様に文 print(b) から def-ref
辺を辿ることによって到達可能な文 b = 1 は，if 文内にあるために，それ以前の変数 b の定義を消去することができない．そのために文 b = 1 以前で変数 b を定義している文を特定する必要がある．これは CIFI-PDG 上の
def-def 辺を辿れば 特定できる．図 10では，文 b = 3 に到達できる．文 b = 3 は，それ以前の変数 b の定義を消去するので，文 print(b) は，文 b = 3，文 b = 1 で定義されている変数 b を参照して，つまり，この 2 文との間にデータ依存関係があることがわかる．
スライス計算時には，スライシング基準からデータ依存関係を再計算し ，スライシング基準とデータ依存関係のある文との間にデータ依存関係のある文を再計算するというように，再帰的にデータ依存関係を計算することで，スライスが計算できる．これまでをまとめると以下のようになる．
アルゴリズムGet DataDepepndence And Slice

Input:
プログラム P の CIFI-PDG
スライシング基準 (s; v )Output:スライス
部分的に CIFS 解析された CIFS-PDG
Step 1．以下の集合を初期化する．

0

0

0

ない．

(2) 文 S と制御依存関係のある文に関しても上記と同様に集合 Slice に追加する．ただし，集合 Sliced に文 S が存在する場合には追加し
0

ない．

(3) 要 素 (S; V ) を 集 合 Slice か ら 除 き ，集 合
Sliced に文 S を追加する．
Step 3．スライスは集合

Sliced に含まれる文となる．

6 考察
本節では，本手法の効率および精度について述べる．
図 4に示す従来手法によるスライス計算と，図 5に示す
本手法によるスライス計算とを比較する．

 CIFI 解析
従来の CIFI 依存解析アルゴ リズムと 4節で述べた，
アルゴ リズムとを比較する．本手法では，生成された PDG が別の依存関係解析アルゴ リズムにより再利用されるために，PDG の構造は従来のものと異なるが，各手法により生成される PDG が含む依存情報は同じものであるため，PDG 構築に要する時間および抽出されるスライスの精度は同じである．

AnalyzeFunction PdgMerge

 CIFS 解析
従来の CIFS 依 存解析アルゴ リズ ムと 本手法のアルゴ リ
ズムとを比較する．従来手法では，ソースコード
を入力とするためにプログラム全体の依存解析を
CIFS を用いて行う．しかし ，本手法では，CIFIで生成された PDG を入力とするため，CIFS を行
う部分はプログラムの一部となる．PDG の構築を行った後にスライス抽出を行うという手順を考えると，必要な部分に比例した時間を要する本手法の方が，従来手法よりもスライスシステムの構築には適していると思われる．ただし従来手法ではPDG を一度構築した後は，スライス抽出時に，あまり時間を要さない．しかし ，本手法においては必要な部分のみを正確に解析し ，解析時に得られ

Get DataDepepndence And Sliceた正確な依存関係情報は PDG に付加されるため，スライスを計算する度に，新たに CIFS 解析を行う．しかし ，解析が必要な部分はスライスをとるごとに減少し，あまり時間を要さなくなる．現在，本手法をシステムに実装している段階であるため，効率に関しては比較できないが，実際にスライスシステムでの利用を考えると，ユーザに使用しやすものになると考えている．

7 まとめと今後の課題
本研究では，複数の効率の異なるプログラムスライ
ス抽出アルゴ リズムの生成する依存関係情報を共有，再利用し ，効率と精度を考慮したプログラムスライス抽出法を提案した．本手法を用いることにより，ユーザが効率の異なるスライス計算アルゴ リズムを利用する場
合に，依存関係の再計算の必要がなくなる．さらに，従来の PDG を利用したスライス計算アルゴ リズムでは，最初にソース全体に対して正確な依存解析を行う必要があったが，本手法では，最初は不正確な (時間をあまり要さない) 依存解析を行い，必要な部分のみを正確な依存解析を行うことが可能である．
現在，本手法をこれまでに開発したシステム [8] に実装している段階であり，実装後はこれまでの手法 [10] との比較を行う予定である．

参考文献[1] Atkison, D. C. and Griswold, W. G. \The Design of Whole-Program Analysis Tools". In Proceedings of the 18th International Conference
on Software Engineering, pages 16{27, 1996.

[2] Michael, D. E. \Practical ne-grained static
slicing of optimized code ". Technical Report
MSR-TR-94-14, Microsoft Research, Redmond,
WA, July 1994.

[3] 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).
[4] Fiutem, R. , Tonella, P. , Antoniol, G. and Merlo, E. \Variable Precision Reaching De nitions
Analysis for Software Maintenance". In Proc. of
the Euromicro Working Conf. on Soft. Mainte-

nance and Reengineering, pages 60{67, Berlin,

Germany, March 1997.

[5] Livadas, P. E. and Croll, S. \Program slicing".
Technical Report SERC-TR-61-F, Software Engineering Research Center, October 1992.

[6] Ottenstein, K.J. and Ottenstein, L.M.:\The
Program Dependence Graph in a Software Development Environment", Proceedings of the

ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, ACM SIGPLAN Notices
19(5) pp. 177{184(1984).
[7] Harrold, M. J. and Ci, N. \Reuse-Driven Interprocedural Slicing". In Proceedings of the20th International Conference on Software Engineering, pages 74{83, Kyoto, April 1998.

[8] 佐藤，飯田，井上:\プログラムの依存解析に基づくデバッグ支援ツールの試作", 情報処理学会論文誌, Vol. 37, No.4, pp.536-545(1996).
[9] 下村 隆夫:\Program Slicing 技術とテスト , デ
バッグ , 保守への応用", 情報処理, Vol. 33, No.
9, pp. 1078{1086(1992).
[10] 植田，練，井上，鳥居:\再帰を含むプログラムのスライス計算法", 電子情報通信学会論文誌,Vol.
J78-D-I, No.1, pp.11-22(1995).
[11] Weiser, M.: \Program Slicing", Proceedings ofthe Fifth International Conference on Software
Engineering, pp. 439{449(1981).
[12] \The Wisconsin Program-Slicing Tool 1.0, Reference Manual", Computer Sciences Department, University of Wisconsin-Madison, August,1997．