論 文
制限された動的情報を用いたプログラムスライシング手法の提案
高田 智規Ý

井上 克郎ÝÝ

大畑 文明ÝÝ

芦田 佳行ÝÝÝ

A Program Slicing Method Using Lightweight Dynamic Information
Tomonori TAKADA  , Katsuro INOUE , Fumiaki OHATA , and Yoshiyuki ASHIDA 

あらまし
大規模なプログラムのデバッグを行なう際，デバッグの対象となるソースプログラム全体からバグがあると思われる部分を小さな範囲に限定することができれば作業効率が向上する．プログラムから注目した一部分を抽出する技術としてプログラムスライシング技術があるが，静的スライシングはプログラムから抽出したスライスが大きくなり，動的スライシングは実行オーバヘッドが大きくなるという問題がある．本稿では，静的手法と動的手法との中間に位置する，依存キャッシュスライシング手法の提案を行なう．また，このアルゴリズムを実装し，サンプルプログラムを用いて実行データの収集を行なった．この結果，配列やポインタを使用したプログラムに対し，依存キャッシュスライシングは既存手法と比較して約 30–90%のスライスサイズ削減を得ることができ，要したオーバヘッドも現実的な値であった．この手法は，効果的にデバッグを行なう上で有効と考えられる．
キーワード

静的スライス，動的スライス，実行時オーバヘッド，依存キャッシュスライシング

スライシング技術は大きく静的スライシング（Static

1. は じ め に

Slicing）と動的スライシング（Dynamic Slicing）の 2

ソフトウェアのテストや保守工程において，ソースつに分類される．

に時間を要する作業である．このとき，ソースプログ

Weiser [12] によって提案された静的スライス（Static
Slice）は，特定のプログラム文中のある変数の値に影ラム全体を見るのではなくフォールトに関連する部

響を与える可能性のある文の集合である．静的スライ分のみ着目することができれば，作業効率を改善す

スは一般にサイズが大きく，極端な場合，ソースプロ

ることができる．このようなフォールト位置特定を行

グラム全体がスライスとして抽出される．これは静的う手法の一つに，プログラムスライシング（Program

スライシングが，すべての入力データ，つまりすべて

Slicing，以降，スライシングと略す）[12] がある．プ
ログラムスライス （Program Slice，以降，スライスとの実行経路パターンを想定しているためである．また，略す）とは，直観的には，関心のある文に含まれる変の判定，配列および構造体要素の区別，ポインタ変数

数に影響を与える文の集合を指す．作業者はスライスの参照先の追跡 などの解析は容易ではない．さらにオに含まれる文のみに着目すればよく，デバッグを効率

ブジェクト指向プログラムでは，識別子に対応するメ的に行うことができる [9]．

ソッドがプログラム実行時に決定される点も無視できプログラム中に存在するフォールト位置の特定は非常

Weiser による研究 [12] をきっかけに，スライシング

静的スライシングにおいて，変数名の別名（Aliasing）

ない．

Agrawal ら [1], [6] によって提案された動的スライス（Dynamic Slice）は，注目した文中の変数の値に実際に関する多くの研究と応用がなされている．
Ý 西日本電信電話株式会社, 大阪市に影響を与えた実行文の集合である．動的スライスは

Nippon Telegraph and Telephone West Corporation, Osaka-shi, 550-0001, Japan

特定の入力データに基づいて導出されるため，ソース

Graduate School of Engineering Science, Osaka University, Toyonaka-shi, 560-

プログラムのうち実行されなかった部分は自動的に除8531 Japan

かれる．このため，スライスサイズは静的スライスとNTT Software Corporation, Yokohama-shi, 231-8554, Japan

比べ一般的に小さくなり，フォールト位置特定には好ÝÝ 大阪大学 大学院基礎工学研究科，豊中市

ÝÝÝ NTT ソフトウェア株式会社, 横浜市

電子情報通信学会論文誌

X

Vol. Jxx–X

No. xxpp. 1–8xxxx 年 xx 月

1

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25



図 1 サンプルプログラム
Fig. 1 Sample program

図2

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.





静的スライシング基準 (24, ) に対する静的スライス
Fig. 2 Static slice for slicing critetia (24, )ましい．しかし，動的スライシングでは動的にプログ

 が制御文であり， の結果によって  が実行さラム文間の依存関係を追跡する必要があるため，多くれるかどうかが決定されるとき，文  から  に対のメモリや時間を必要とする．

し制御依存（Control Dependence, CD）があるといい，

本稿では，静的スライシングと動的スライシングの中間に位置する，準動的（Semi-Dynamic）手法の一つを提案する．以降，2. 節では，静的・動的スライシン
グについての簡単な説明および既存の準動的手法の分類を行う．3. 節では，新たな準動的手法である依存
キャッシュスライシングの提案を行う．Osaka Slicing

System を用いた提案手法の実現および評価実験を 4.
節で示し，5. 節で検証結果の考察と関連研究について述べる．最後に，6. 節でまとめと今後の課題について述べる．

2. スライシング手法の分類

 と記述する．
 から  へ変数  を再定義しない実行経路が少な
くとも 1 つ存在し， において  が定義され， において  が参照されるとき，文  から  に対し変数
 に関するデータ依存（Data Dependence, DD）があるといい，
 と記述する．
プログラム依存グラフ（Program Dependence Graph,
PDG）は辺が文間の依存関係を表し，節点が制御文・代入文などの文を表す有向グラフである．
文  における変数  に関する静的スライスとは，文 に対応する PDG 節点から PDG 辺を逆向きに（制御依存辺は無条件に，データ依存辺は最初は着目してい本節では，静的スライシングと動的スライシングにる変数名に対応するもののみで以降無条件に）辿る

関し，その抽出過程を中心に述べ，その具体例として，

ことで到達可能な節点集合に対応する文の集合であ

図 1 のプログラムに対する静的スライスおよび動的ス

る．なお，組 (,  ) を静的スライシング基準 （Static
Slicing Criteria）と呼ぶ．

ライスを，図 2，図 3 にそれぞれ示す．また，これらの中間に位置する準動的手法がいくつか提案されており，それらの紹介および分類を行う．

2. 1 静的スライシング および その分類
ソースプログラム  中の文  と  について考える．
2

静的スライシングの解析手法は，以下のように分類できる．

 制御フロー解析の有無（Flow Sensitiveness / Insensitiveness）

論文／制限された動的情報を用いたプログラムスライシング手法の提案

 関数・手続き解析時に実際の引数・大域変数情報

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

を用いるかどうか（Context Sensitiveness / Insensitive-ness）
本稿では，特に明示しなければ，制御フロー解析を行ない かつ 関数・手続き解析時に実際の引数・大域変数情報を用いない（呼び出し文と呼び出し先とを独立して解析する）手法を採用する．

2. 2 動的スライシング
静的スライシングではソースプログラムコードを対象に依存関係を解析し，スライスを抽出していたが，動的スライシングでは，依存関係の抽出対象は実行系

列 （Execution Trace）になる．実行系列とは，ある入力を与えプログラムを実行したときの，実際に実行された文の列をいう．また，実行系列中の  番目の文の実行のことを実行時点  と呼ぶ．
実行系列  中の実行時点  ， について考える．

 が制御文であり， の結果によって  が実行されるかどうかが決定されるとき，実行時点  から

 に対し動的制御依存（Dynamic Control Dependence,
DCD）があるという．
 から  へ変数  を再定義する実行時点がなく，
 において  が定義され， において  が参照されるとき，実行時点  から  に対し変数  に関する動的データ依存（Dynamic Data Dependence, DDD）があるという．
そして，これらの動的依存関係を元に動的依存グラフ（Dynamic Dependence Graph, DDG）を構築する．
入力値の組  が与えられたときの実行時点  におprogram Square Cube(input, output);var a, b, c, d : integer;function Square(x : integer) : integer;
begin
Square := x * x
end;

begin
readln(a);readln(c);if c = 0 thend := Square(a)writeln(d)end.



図 3 動的スライシング基準 (a = 2, b = 3, c = 0, 24, ) に対する動的スライス
Fig. 3 Dynamic slice for slicing critetia (a = 2, b = 3, c = 0,
24, )



など）プログラム実行に関する全履歴を必要とするため，プログラム実行時のオーバヘッドが非常に大きい．
そこで，実行時オーバヘッドの削減を目的として，
静的解析と動的解析を組み合わせてスライスを抽出す
る，準動的手法が提案されている．

2. 3. 1 実行経路の収集に着目した手法

ける変数  に関する動的スライスとは，実行時点  にプログラムの実行経路に関する情報を収集・利用す対応する DDG 節点から DDG 辺を逆向きに辿ることることでスライスサイズの削減を行う．軽量な実行時で到達可能な節点集合に対応する文の集合である．な

オーバヘッドで経路情報を収集することに重点が置か

お，組 ( , ,  ) を 動的スライシング基準（Dynamic

れる．

Slicing Criteria）と呼ぶ．
2. 3 準動的手法 および その分類

 Profiling Method [1]動的スライシングを単純化したものとして提案さテスト・保守工程でのデバッグ作業において，プロれた．各文の実行の有無を記録し，静的に生成された

グラムスライシング技術はフォールト位置特定に有効

PDG から実行されなかった文を削除する．この手法でである [9]．このとき，テストケースは一般に有限個

は，実行系列の保存は不要である．

であり，入力データも特定のものに限定される．本来，デバッグ作業では対象プログラムの実行は必要不可欠

 コ ー ル マ ー ク ス ラ イ シ ン グ (Call-Mark Slicing) [10]であり，そこから得られる情報を利用することで，静実行時，関数・手続き呼び出し文の実行の有無のみ的スライスよりも小さい（正確な）スライスを抽出す記録する．しかし，静的解析により導出される実行経ることができる．

路情報と組み合わせることで，呼び出し文以外で かつ

動的スライシングはそのようなアプローチの一つで確実に実行されることのない文もスライス計算対象かあるが，（実行経路 および 各実行時点での変数の状態ら排除できる．この手法は，Profiling Method と比べ，3

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

1:
2:
3:
4:

a[0] := 0;a[1] := 1;
readln(i);c := a[i];図 4 配列変数に関するデータ依存
Fig. 4 Data dependence for array variables

一方，ある入力データを与えプログラムを実行し，その際にポインタ変数の参照先や配列の添字値を把握する機構を実現することは容易である．しかし，プログ
ラム実行のために非常に大きなオーバヘッドを必要とする．
そこで我々は，依存関係抽出の正確性と実行時オー

実行時に記録する文が少なくなる．

バヘッドとのトレードオフを考慮したスライシング手

 ハイブリッドスライシング (Hybrid Slicing) [3]法である，依存キャッシュスライシング（Dependence

ユーザの設定したブレークポイントの実行履歴またCache Slicing）手法を提案する．以下は依存キャッシュは各関数・手続きの呼び出し履歴を記録することで，スライスの計算手順の概略である．

実行経路の予測を行う．有効な実行経路情報を得るた

Step 1 静的制御依存関係解析
PDG の部分グラフ   を静的に生成する．
まず，静的スライシングで利用する PDG と同様，文め，ユーザはブレークポイントの設定位置に注意を払う必要がある．

2. 3. 2 データ依存関係の収集に着目した手法

または制御文に対応する節点を用意する．そして，文プログラムの実行経路を静的解析により予測できれ間に制御依存関係が存在すれば，対応する節点間に制ば，整数やブールなどの単純型の変数に関するデータ

御依存辺を引く．ただし，  にデータ依存辺は

依存関係は容易に抽出できる．しかし，配列やポイン加えない．

タ変数に関するデータ依存関係の抽出には限界がある．

Step 2 動的データ依存関係解析

例として，図 4 に示すプログラム断片を考える．この場合，実行経路は唯一に定まるが，それだけでは文対象プログラムをある入力データで実行する．
実行の際，次節で示すデータ依存関係抽出アルゴリ

4 が文 1 および文 2 にデータ依存するかを決定するこズムに基き，動的なデータ依存関係を計算し， とはできない．

にデータ依存辺を追加する．プログラム実行が終了し通常，この問題の解決には，完全実行履歴 (Full Execution History) を用いて DDG 構築を行なう．DDG でた時点で，  の完成となる．

はすべての配列要素が展開されており，完全なデータ

Step 3   によるスライス計算
  を用いて，静的スライシングと同様の方法

依存関係を保持することができるが，完全実行履歴のでスライス計算を行う．

蓄積に要するオーバヘッドは極めて大きい．そこで，
データ依存関係の正確性と実行時オーバヘッドとのト
レードオフを考慮した手法が提案されている．

 Reduced DDG Method [1]
DDG 中に存在する同一構造を持つ部分グラフを一つに集約し，DDG 全体の大きさを削減する．これにより DDG のサイズは小さくなるが，実行時オーバヘッ

例えば，スライシング基準 ( ,  ) に関する依存キャッシュスライスを抽出する場合，まず， に対応する節

点から制御依存辺および  に関するデータ依存辺を逆向きに辿ることで到達可能な節点集合を導出する．そして，この節点集合に対応する文が求めるスライスとなる．

3. 2 データ依存関係収集アルゴリズム

ドは類似性チェックのため増加する．

図 5 に 3. 1 節の Step 2 で使われるデータ依存関係

 依存キャッシュスライシング

抽出アルゴリズムを示す．まず，プログラム中で用い本稿でこの手法を提案する．単純なキャッシュを利られる全ての変数  に対して，キャッシュ（   と記用して動的に抽出したデータ依存関係と，静的に解析す）を用意する．大域変数など静的な変数はプログラ

した制御依存関係を組み合わせてスライスの計算を行

ム実行開始時に，スタック上の Automatic 変数やヒー

なう．この詳細は 3. 節で示す．

プ中の変数など動的な変数はその変数の割付け時に3. 依存キャッシュスライシング
3. 1 概要キャッシュを用意する．プログラムの各実行時点において，   は最も新しく  を定義した文に対応する
節点を保持し，文  において  が使用（参照）された

通常，ポインタ変数や配列要素のデータ依存関係時，   が保持する節点から  に対応する節点に対を静的解析により得ることは非常に難しい [4], [5], [7]．

してデータ依存辺を (すでに存在しなければ) 追加す

4





論文／制限された動的情報を用いたプログラムスライシング手法の提案

入力 : 部分的に生成された PDG : 対象プログラム :  への入力

作業変数
中の各変数



出力





ス回数に応じた実行時間のオーバヘッドが必要である．

4. 実

 に対する依存キャッシュ: 入力 に対するプログラム: 完成した PDG

様々なスライシングアルゴリズムを評価するため，
我々は Osaka Slicing System [11] と呼ぶソフトウェア開 に対し,   
 各キャッシュの未代入マークによる初期化．
(注) 動的に割当てられる変数は割当てられた時点でキャッシュを用意し， を代入する． （ 2 ）  が停止するまで以下を繰り返し実行する  を入力  で最初から停止するまで文ごとに実行 （ a ）  に関して， の次の一文 を実行（ b ） で使用 (参照) される各変数 について，   が存在しなければ か つ ，デ ー タ 依 存 辺    に  を追加する．
（ c ） で定義される各変数  について，  
Fig. 5験

4. 1 Osaka Slicing System の概要

 の実行の出力

アルゴリズム本体（1）
中の各静的変数

このアルゴリズムでは，プログラム実行中の変数の使用状況に比例したキャッシュ空間と，変数へのアクセ

図 5 データ依存関係収集アルゴリズム
Algorithm for computing data dependence relations

発・デバッグ環境を構築している．対象言語は Pascal
である．
このシステムはプログラムの実行とデバッグを行なうことができる．また，静的スライシング，動的スラ
イシングの機能を持つ．今回，コールマークスライシ

ング，そして 3. 2 節で提案した依存キャッシュスライ
シング の機能を追加した．

4. 2 サンプルプログラムの実行
このシステムを用い，様々なプログラムを実行し幾つかの評価尺度を得た．プログラム   はカレンダー
プログラム，  は在庫管理プログラム， はプログ

る．一方， で  が定義された時，   は  に対応すラム   の在庫管理プログラムの拡張版である．

る節点に更新する．これらを全ての変数に対して行う．

表 1 は 3 つのサンプルプログラムのスライスサイズ

配列変数や構造体に対しては，全ての要素に対してである（表中，CM はコールマークスライス，DC はキャッシュを用意する．例えば， ,

依存キャッシュスライスを示す）．これらの値はスラ

は，キャッシュイシング基準や入力値によって変動する．ここでは典  を持つ．ポインタ変型的なデバッグ状況に対していくつかの基準と入力をという 10 個の要素を持つ配列変数 , , . . . ,, . . . ,数  が文  において使用された場合，使用された 

用いた平均値を示している．

自身だけでなく， を介して間接参照された変数  

表 2 は実行前解析に要した時間を示している．静的をも考慮しなければならない．つまり，直接と間接のスライシングの場合，この値は PDG 構築に要した時参照（ 

 の両者）をデータ間である．コールマークスライシングでは PDG の構依存辺に含めなければならない．また，文 における

築と実行経路情報の静的解析の両方に要した時間であ





と

 

p

のようなポインタ変数を介した間接的なる．依存キャッシュスライシングでは初期の  代入については，キャッシュ   が において更新構築に要した時間である．また，動的スライシングでされ，また において

は実行前解析は不要である．

が使用されたと考える．

動的変数に対しては，個々のインスタンスごとに

表 3 に実行時間を示す．静的スライシングの場合，キャッシュを用意する．また，配列や構造体では，参対象プログラムは実行時オーバヘッド無しで実行され照されうる要素ごとにキャッシュが必要である．例えるため，この値は対象プログラム自身の実行時間であば，要素  と  から構成される構造体  に対してる．動的スライシングの実行は DDG の生成時間が含は，キャッシュ  ,   を用意する．各  ,  への定義及び参照時の操作は図 5 のアルゴリズムと同じまれている．依存キャッシュスライシング の実行時間である．文  で構造体  全体への定義が行なわれる時，る時間が含まれている．また，コールマークスライシ  ,   

 を行なう．また， で  全体

 


及び   を   に追加する．(注: 辺上のラベル  , は静的に決まりうる要素名)の参照が行なわれる時は，データ依存辺は依存関係をキャッシュする時間と   を生成す
ングでは呼び出し文を記録する時間が含まれている．
表 4 は依存グラフを用いてスライスを計算する時間を示している．静的スライシングの場合，これは実行前に完了している．動的スライシングでは，動的依存5電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

シュスライスのサイズの削減度合はプログラム   と表 1 スライスサイズ (行)Table 1 Size of slice (lines)
プログラム

静的

CM

DC

動的

P1(85 行)
P2(387 行)
P3(871 行)

21
182
187

17
162
166

15
16
61

5
5
8

表 2 実行前解析時間 (ms)Table 2 Pre-execution analysis time (ms)

 では，  に比べ大きい．これは   が整数やブールなどの単純型の変数しか使用していないのに対し，  と  が依存キャッシュスライシングもしくは動的
スライシングのみが詳細に解析できる配列変数を使用しているためである．

 実行前解析

プログラム

静的

CM

DC

動的

表 2 で示したように，依存キャッシュスライシング

P1
P2
P3

11
213
710

14
215
698

5
19
48

N/A
N/A
N/A

では，静的スライシングに比べ短い実行時間で実行前(Celeron-450MHz CPU with 128MB Memory)

依存関係とデータ依存関係の解析を行なっているのに対し，依存キャッシュスライシングでは制御依存関係

表 3 実行時間 (ms)Table 3 Execution time (ms)
プログラム

静的

P1
P2
P3

47
47
43
43
4,700 4,731

CMDC

のみの解析を行なえばよいためである．
動的

51
174
45
4,540
4,834 206,464(Celeron-450MHz CPU with 128MB Memory)

表4
Table 4

解析が可能である．これは，静的スライシングが制御

スライス計算時間 (ms)Slice computation time (ms)

プログラム

静的

CM

DC

動的

P1
P2
P3

0.4
1.9
3.0

0.6
1.8
3.0

0.3
0.7
1.2

76.0
101.0
24,969.3(Celeron-450MHz CPU with 128MB Memory)

 実行時間表 3 で示した実行時間は動的スライシングのオーバ
ヘッドが極端に大きいことを示している．ループを繰り返し実行するなどしてプログラムの実行が長くなると，深刻な性能低下を引き起こす．依存キャッシュス
ライシングは静的スライシングよりも実行時間が長く，動的スライシングよりも短くなっている．
ここで示した実行時間はインタープリタ型のシステ
ムに基づいているため，これらはインタープリタのオーバヘッドによって隠蔽されている可能性がある．
この問題については 5. 2 節で議論する．

関係を探索する時間が計測されている．また，コール
マークスライシングと依存キャッシュスライシングでは，それぞれの Step 3 に要した時間である．
次節でこれらの結果について議論を行なう．

5. 考

察

5. 1 実験データの解釈

 スライスサイズ
表 1 はスライスのサイズを示している．依存キャッシュスライスのサイズは静的スライスの 9–71%となっ スライス計算時間
表 4 で示すように，動的スライシングはスライス
結果を収集するのに長時間を必要とする．依存キャッシュスライシングでは，静的スライシングよりも短くなっている．これは，依存キャッシュスライシングが  よりも小さい   を用いているためである．動的スライシングについては，巨大な DDG を探索するのに非常に時間がかかる．

5. 2 依存キャッシュスライスの適用領域と限界ている．
依存キャッシュスライスのサイズは静的スライスと4. 節で示した実験はインタープリタ型の実行システ

動的スライスの中間となっている．これは常に静的ス

ムの下で行なわれた．ここでは，スライシングに対すライスより小さく (良く)，動的スライスより大きい (悪る解析・実行時間の特徴がコンパイラ環境でも同様かい)．また，依存キャッシュスライスはコールマークス

どうかを考察する．

ライス よりも良い (小さい) といえる．これは，コールC でマージソートのプログラムを書き，実行中に依マークスライシングが静的に解析したデータ依存関係

存キャッシュの更新とデータ依存関係を収集するようから実行されない部分を削除するだけなのに対し，依にソースプログラムを変更した．このプログラムの実

存キャッシュスライシングが特定の実行パスに依存す

行時間は変更前の 8.6 倍であった．これは依存キャッるデータ依存関係を反映するためである．依存キャッシュスライシング のオーバヘッドがコンパイラ環境で

6

論文／制限された動的情報を用いたプログラムスライシング手法の提案

は大きくなることを示している（注 1）．しかし，単純型

動的スライシング手法を提案した．

変数のデータ依存情報は静的解析で容易に決定できる

スライス結果は同一スライシング基準での動的スラ

ため，データ依存情報を配列とポインタ変数について

イスより大きくなるが，静的スライスより小さくなる．

のみ動的に収集することで高速化が可能である．この我々はこれらのスライシングアルゴリズムを実験イン

考えに基づき，プログラムを再び変更した．この部分

タープリタシステムに実装した．また，様々なサンプ

的依存キャッシュスライシングプログラムの実行時間

ルプログラムを実行し，我々のアプローチを検証した．

は変更前の 3.4 倍となり，これは実用的に許容できると考える．

我々は現在のインタープリタシステムではなくコン
パイラシステムに基づくデバッグ環境の構築を予定し

表 1 からわかるように，依存キャッシュスライスはている．そのシステムでは様々なデバッグ機能を結合

常に動的スライスよりも大きくなっている．これは依させ，依存キャッシュスライスが計算可能となる．こ存キャッシュスライシングは同じ文の複数回の出現をのコンパイラは依存キャッシュ機能を持ったオブジェ

区別せず，キャッシュの中に直近の Def-Use 関係を保クトコードを生成し，そのコードは自動的に動的デー持しているからである．

タ依存関係を収集する．この情報はスライスまたは他

5. 3 他手法との関連のデバッグ補助情報としてユーザから要求された際にデータフロー情報の収集に注目した動的手法につ表示され，フォールト位置特定のための有用なデバッ

いてはほとんど研究されていない．2. 3 節で紹介した

Reduced DDG Method はこれらのうちの一つであり，動的スライシングの正確さと，解析に必要なメモリ空グ情報を提供する．

謝辞 本研究は，一部文部省科学研究費補助金特定領域研究 (A)(2) (課題番号:10139223) の補助を受けた．

間の削減を実現している．しかし，DDG の重複チェックのために実行オーバヘッドは削減されず，増加する文[1]

可能性もある．
文献 [4], [5] では，ポインタや配列変数の静的解析に

PLAN Notices, Vol.25, No.6, pp. 246–256, 1990.
[2]

Field, J., and Ramalingam, G.: “Parametric Program Slicing”,
Proc. of 22nd ACM Symposium on Principles of Programming

ついて述べられている．これらは不確実性を残している [13] のに対し，依存キャッシュスライシングは動的

献

Agrawal, H. and Horgan, J. : “Dynamic Program Slicing”, SIG-

Languages, pp. 379–392, San Francisco, USA, January (1995).
[3]

Gupta, R., Soffa, M.L., and Howard, J. : “Hybrid Slicing: Inte-

情報を利用しており，軽量なオーバヘッドでどんな種

grating Dynamic Information with Static Analysis”, ACM Trans-

類の変数に対しても，実用的なスライスの正確さを実

action on Software Engineering and Methodology, Vol. 6, No. 4,

現している．

pp. 370–397, 1997.
[4]

文献 [2] では，静的と動的スライスを一般化させた，

制約スライス（Constrained Slice）が提案されている．
これはプログラムの入力の部分集合をプログラムの実

and Systems, Vol.21, No. 4, pp. 848–894 (1999).
[5]

Horwitz, S. Pfeiffer, P., and Reps, T.:“Dependence Analysis for
Pointer variables”, Proceedings of SIGPLAN ’89 Conference on

行と捉え，この入力制限を用い，依存関係の再計算を

Programming Language Design and Implementation, pp.28–40,

行なう．しかし，このアプローチの実行効率やその実用性については不明である．

Hind, M., Burke, M., Carini, P., and Choi, J.:“Interprocedural
Pointer Alias Analysis”, ACM Trans. on Programming Languages

SIGPLAN Notices Vol. 24, No. 6 (1989).
[6]

Korel, B., and Laski, J. : “Dynamic Program Slicing”, Information Processing Letters, Vol.29, No,10, pp. 155–163 (1988).

6. ま と め[7]

Liang, D., and Harrold, M. J., : “Efficient Points-To Analysis for
Whole-Program Analysis”, Proc. of 7th European Software Engi-

プログラマの注意をソフトウェアの小さな一部分にneering Conference and 7th ACM SIGSOFT Symposium on Foun-

特化させることは，プログラムのデバッグや保守の効

dations of Software Engineering, pp.199–215, Toulouse, France

率を改善するために非常に重要である．伝統的なプロ(1999).
[8]

グラムスライシングは精度と効率の十分なトレードオ

ACM, Vol. 37, No. 5, pp.50–57, May (1994).

フを提供していない．
我々は依存キャッシュスライシングという軽量な準（注 1）：これは，実行中に DDG の探索が必要な動的スライシングでは
オーバヘッドが許容できないほど大きくなることも示唆している．

Ning, J. Q., Engberts, A., Kozaczynski, W. V. : “Automated Support for Legacy Code Understanding”, Communications of the[9]

西松 顕, 楠本 真二, 井上 克郎: “フォールト位置特定におけるプログラムスライスの実験的評価”, 信学技報 SS98-3,
pp.17-24, Mar 1998

[10]

Nishimatsu, A., Jihira, M., Kusumoto, S. and Inoue, K. : “CallMark Slicing: An Efficient and Economical Way of Reducing

7電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx
Slice”, Proceedings of The 21st International Conference on Software Engineering, pp.422-431, Los Angeles, CA, USA, 1999.
[11]

佐藤 慎一, 飯田 元, 井上 克郎: “プログラムの依存関係解析に基づくデバッグ支援ツ−ルの試作”, 情処論 Vol.37, No.4,
pp.536-545, Apr 1996

[12]

Weiser, M.: “Program Slicing”, Proceedings of the Fifth International Conference on Software Engineering, pp. 439–449 (1981).

[13]

Ramalingam, G.: The Undecidability of Aliasing, ACM Transactions on Programming Languages and Systems, Vol. 16, No. 5, pp.
1467–1471 (1994).

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

高田 智規
平 7 阪大・基礎工・情報卒．平 9 同大大学院修士課程了．現在西日本電信電話株式会社勤務．在学中，プログラムスライスの研究に従事．

井上 克郎 （正員）昭 54 阪大・基礎工・情報卒．昭 59 同大
大学院博士課程了．同年同大・基礎工・情報・助手．昭 59〜昭 61 ハワイ大マノア校・情報工学科・助教授．平 1 阪大・基礎工・情報・講師．平 3 同学科・助教授．平 7 同学科・教授．工博．ソフトウェア工学の研
究に従事．

大畑 文明
平 10 阪大・基礎工・情報中退．平 12 同大
大学院修士課程了．現在同大学院博士課程在学中．プログラム構造解析の研究に従事．

芦田 佳行
平 10 阪大・基礎工・情報中退．平 12 同大大学院修士課程了．現在 NTT ソフトウェ
ア株式会社勤務．在学中，プログラムスライスの研究に従事．

8