スライシングツールの実現

現在、制限を加えたANSI C言語を対象に、Weiserのプログラムスライシングを行う CASEツールを実現した。ここでは、本研究で用いた静的スライシングについて概要を示 し、それに基づいて、実現したスライシングツールについて述べる。

静的スライシング

定義 ある変数に関しては、元のプログラムと同じ値を計算する実行可能な部分プログラ ムを静的スライスという。静的スライスは、プログラムのフローグラフをデータ依存関係 と制御依存関係に従い、それを辿ることで得ることができる。プログラムの制御の流れる 方向を示した有効グラフがフローグラフである。一般に、フローグラフは以下のように定 義される。

1. ノード

ノードはプログラム内の命令を表す 2. アーク

ノードsとtの間のアークは、命令sを実行したあと、制御が直接ノードtに移る可 能性があることを示している。

例えば、階乗を計算するプログラムのフローグラフを図5.1の示す。

1 sum=0;

2 fact=1;

3 i=1;

4 while(i<=10){

5 sum=sum+i;

6 fact=fact*i 7 i++;

}

8 printf("%d, %d\n", sum, fact);

1 2 3 4 5 6 7

8

図 5.1: フローグラフの例

また、静的スライシングにおけるデータ依存関係と制御依存関係の定義を次に示す。

• データ依存関係，DD(s, t)

変数wが存在するとする。命令sにおいて定義された変数wが、wを参照している

別の命令tに到達するとき、「sからtに対してデータ依存関係DD(s, t)がある」と いう。ここで言う「到達する」とは、命令sが変数wを定義し、かつ、フローグラ フ上でsからtに至るパスが存在し、そのパス上では変数wが再定義されないこと を言う。つまり、データ依存関係があることは、sで定義した変数をtで参照する可 能性があることを意味している。

• 制御依存関係，CD(s, t)

命令sが分岐命令またはループ命令で、命令tがその文の内部に直接含まれている とき、「sからtに対して制御依存関係CD(s, t)がある」という。ここで言う「直接 含まれている」とは、ネストした分岐文やループ文に中にtが含まれていないこと を意味する。つまり、制御依存関係があることは、命令tが実行されるかどうかが 命令sの実行結果に依存していることを意味する。

方法 静的スライシングではスライシング基準はプログラム中の命令uとプログラム中 の変数の部分集合Vによって与えられる。これをC = (u, V)とする。スライシング基準 C = (u, V)に関する静的スライスSSの求め方は、次のように定式化できる。

1. A⁰ ={命令t|ある変数v ∈Vに対して命令tにおける変数vの定義が命令uに到達 する、あるいはCD(t, u)}

2. i ≥ 1 に対して、A¹ = {命令 s|ある命令t ∈ Aⁱ⁻¹が存在してDD(s, t)もしく はCD(s, t)}

3. SS =

∞

i=0Aⁱ{u}

実現したスライシングツール

XMLを用いたCASEツールプラットフォームを使用することで、プログラム中の条件 を満たす変数の抽出と必要な文の抽出は比較的容易だった。DOM[10]を用いたことも開 発を容易にした。このツールは約2,000行のJavaプログラムで、作成期間は、開発者1人 で約2週間を費やした。その仕様を以下に示す。

• スライシングの基準として、任意の文の任意の1変数が指定できる。

• if-else文、およびwhile文を持つプログラムから実行可能な必要部分を抽出する。

switch-case文、goto文、for文は扱わない。

• ポインタ、配列の解析、および関数間を跨る変数の解析は行わない。

例えば、次のファイルの行数と語数、文字数を計算する関数を対象にスライシングを 行ったところ、行数部、語数部、文字数部のみを取り出せた。

1 iw = 0; /*in a word*/

2 nl = 0;

3 nw = 0;

4 nc = 0;

5 c = fgetc(stdin);

6 while (c != EOF) {

7 nc = nc + 1;

8 if (c == ’\n’)

9 nl = nl + 1;

10 if (isspace(c))

11 inword = 0;

12 else if (iw == 0) {

13 inword = 1;

14 nw = nw + 1;

15 }

16 c = fgetc(stdin);

17 }

18 printf("%d\n", nl);

19 printf("%d\n", nw);

20 printf("%d\n", nc);

元のプログラム

2 nl = 0;

5 c = fgetc(stdin);

6 while (c != EOF) {

8 if (c == ’\n’)

9 nl = nl + 1;

16 c = fgetc(stdin);

17 }

18 printf("%d\n", nl);

スライス結果(18, nl)

結果として、粗い比較にはなるが、XCIの構文解析、静的意味解析に費した労力(2人 月)に比べると、大幅に少ない労力(0.5人月)で済んだので、この種の小さなCASEツー ルの作成においては、開発コストが削減できXMLを用いる有用性を確認した。