ソフトウェアエンジニアリングシンポジウム 2011

1. は じ め に

制御フローを考慮しない
データ依存関係解析の実験的評価
石

尾

隆†1

井 上 克 郎†1

データ依存関係解析は，様々なプログラム解析手法の基盤として用いられている．
通常のデータ依存関係解析では，変数に代入された値がどこで参照されるかを制御フ
ローグラフ上で計算するが，本研究では，制御フローを考慮せず，すべての代入結果
がすべての参照に到達すると仮定してデータ依存関係を計算し，通常のデータ依存関
係解析の結果と比較した．その結果，10 個の Java プログラムに含まれた約 58 万個のメソッドのうち，90.9%のメソッドについては，2 つの計算方法で同一の結果が得られることを確認した．また，正しい解析結果を得るために制御フローの考慮が必要なメソッドは，代入文が 2 つ以上ある変数を持つメソッドに限られており，その条件に該当するメソッドが 15.8%だけであることを示した．

システム依存グラフ (SDG)5) の辺の 1 つであるデータ依存関係は，プログラムスライシ
ング18) や，ある特定の機能を実装したソースコード位置の特定2) ，手続き抽出リファクタリング8) ，類似ソースコードの検索17) など，様々なプログラム解析手法の基盤として用いられている．しかし，システム依存グラフを構築する計算には時間がかかることも知られている．Jász ら7) によると，CPU に AMD Opteron 2.2GHz，メモリを 4GB 搭載した計算機で，C 言語に対するプログラムスライシングツールである CodeSurfer を実行した場合，

14KLOC の valgrind に対する SDG の構築には 21 分が必要であり，30KLOC の gdb に対する SDG の構築には 132 分必要であった．一方で，開発者が 1 日に行うプログラミングなどの作業は，30 分の短いタスクが数回，2 時間の長いタスクが 1 回程度であると報告されており14) ，開発者の日常的な作業にデータ依存関係解析を活用することは困難な状況にある．
著者らの研究グループでは，データ依存関係を高速に抽出するために，制御フロー解析を行わず，変数のすべての代入からすべての参照に，直接，データ依存関係を接続する解析手法を提案した4),15) ．この近似計算は，10 万行程度のプログラムに対して約 5 分で解析がAn Empirical Evaluation ofa Flow-Insensitive Data Dependence Analysis

完了する15) 一方で，従来のデータ依存関係の解析では出現しない不適切なパス（infeasible

Takashi Ishio†1 and Katsuro Inoue†1

近似計算したデータ依存関係あっても，開発者が行うプログラムの調査を支援可能であるこ

Data dependence analysis is employed for various program analysis techniques. Traditional data dependence analysis computes reaching deﬁnitions on
a control-ﬂow graph. In this research, we have compared the traditional analysis and our ﬂow-insensitive analysis that assumes all assignments to a variable
have control-ﬂow paths to all statements that refer to the variable. As a result,
we have found that ﬂow-insensitive analysis could compute the correct resultfor 90.9% of 580 thousand methods in 10 Java programs. We have also shown
only 15.8% of methods required ﬂow-sensitive analysis since the methods haveat least two assignment statements to a single variable.

paths）を抽出することになる．これに対して，悦田の実験4) では，制御フロー解析なしでとを示した．しかし，この実験は，JEdit という 1 つのソフトウェアを対象としたプログラ
ム理解の実施を行ったものであり，他のソフトウェアにも同様の手法が効果的であるかどうかは示していない．
本研究では，この観測結果が一般化できるかどうかを評価するために，従来から使用されているデータ依存関係と，近似計算したデータ依存関係を，10 個の Java プログラムに対して比較する実験を行った．その結果，全プログラムの 90.9%のメソッドについては，制御フローを考慮せず，すべての代入からすべての参照にデータ依存関係があると考えても，正しいデータ依存関係が得られることを示した．正しい結果が得られるメソッドの割合はプ
ログラムごとに大きな違いはなく，制御フローを考慮しないデータ依存関係が，一般的な多くの Java プログラムに適用可能であることが期待できる．また，データ依存関係を正しく†1 大阪大学 大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka University1

得られないメソッドの集合は，1 つの変数に対する 2 回以上の代入を持つメソッドの一部であり，そのようなメソッドは平均で 1 プログラムの 15.8%，最大でも 20.9%であった．

© 2011 Information Processing Society of Japan2

制御フローを考慮しないデータ依存関係解析の実験的評価

1:
2:
3:
4:
5:
6:

public File getFile() {String filename = getFileName();if (filename == null) {filename = getDefaultFileName();}
File f = new File(filename);
return f;}

ある文 s1 が変数 v に値を代入しており，別の文 s2 が変数 v の値を参照している場合を，
1

3

2

5

近似計算したデータ依存関係であるとみなす．これは，データ依存関係の条件 3 を取り除いたものに相当し，解析速度を向上するかわりに不適切なパス (infeasible path) を抽出しう
る．たとえば図 1 左のコード片では，1 行目で変数 filename に代入された値が 2 行目と 5行目で参照され，3 行目で代入された値が 5 行目で参照される．また，5 行目で代入された

6

図 1 データ依存関係の解析例．左のコード片におけるデータ依存関係が右のグラフの実線に対応する．
Fig. 1 An example of data dependence. The solid edges in the right graph shows data dependenceof the left code.

変数 f は 6 行目で参照される．これらのデータ依存関係を図で表現すると，図 1 右のグラフにおける実線で示された辺となる．制御フローを考慮しない場合は，すべての代入と参照の組を取るので，変数 filename については，3 行目の代入から 2 行目の参照へと，不適切なパスを抽出する．図 1 ではこの辺を点線で示している．変数 f については，代入と参照がそれぞれただ 1 つしか存在しないので，制御フローを考慮しなくとも，結果に変化はない．

本研究の貢献は，開発者が日常的な開発作業に使用できるプログラム解析技法の１つとし過去の実験4) では，JEdit の複数のメソッドに渡るデータフローを調査する 2 つのタスて，制御フローを考慮しない，変数の代入および参照関係を用いた簡便なデータ依存関係がクで，不適切なパスが発見されたのは 1 度だけであった．そして，不適切なパスの出現は活用できる可能性を示したことである．

開発者の作業に影響を与えず，データ依存関係解析の有効性を損なわなかった．不適切なパ

以降，2 節では，研究の背景であるデータ依存関係の定義について述べる．3 節ではデー

スが少なかった要因として，ローカル変数は使用する直前に宣言すべきであること，1 つのタ依存関係の調査方法とその結果について述べる．4 節は結果の妥当性および影響に関する

ローカル変数は 1 つの目的に使用すべきであること（他の値を格納するために再利用しな議論を行う．5 節では関連研究を紹介し，6 節でまとめを述べる．

い）1) が知られているためと考えられる．変数が再利用されず，ただ 1 度しか値を代入され

2. 背

景

なければ，その 1 つの代入からすべての参照へデータ依存辺を接続することで，制御フロー解析を用いずとも，正確なデータ依存関係を抽出することが可能である．このような状況

2.1 データ依存関係

が，JEdit や他の Java プログラムにおいて一般に成り立つことが確認できれば，悦田の手システム依存グラフ5) を用いたプログラムスライシングでは，次のようにデータ依存関法4) が一般の Java プログラムで有効に働く可能性が高いと予測できるとともに，データ依係を定義している．
プログラム文 s1 と s2 の間に，以下の条件が成り立ったとき，s2 は s1 にデータ依存するといい，s1 から s2 にデータ依存辺を引く．

存関係解析に基づく様々な手法2),8),17) の計算の高速化にもつながる．
なお，解析の簡略化によって短縮できる時間の見積もりであるが，著者らが過去に実装したスライシングツール6) で制御フロー解析，データ依存解析，ポインタ解析を完全に実行(1)

s1 が変数 v に値を代入する．

したところ，10 万行程度のプログラムに対するシステム依存グラフの構築に約 30 分を要し

(2)

s2 が変数 v の値を参照する．

ていた．制御フローを考慮しなければ，同じ規模のプログラムでも約 5 分で処理を完了する(3)

s1 から s2 に，v の値を書き換えない実行経路が少なくとも 1 つ存在する．

ことが可能であった15) ．これらのツールは内部で使用しているデータ構造が違うので，厳条件 3 に示されている通り，データ依存関係を求めるには，制御フロー情報が必要であ

密な比較ではないが，大幅な時間短縮を見込める可能性がある．

る．しかし，Java のようなプログラミング言語では，例外処理や finally ブロックのよう

2.3 用に複雑な制御フローをもたらすプログラム要素が存在しており，計算に時間がかかる．

本論文において，不適切なパスとは，制御フローを考慮したデータ依存関係解析では抽出

語

2.2 制御フローを考慮しないデータ依存関係

されないが，制御フローを考慮しないデータ依存関係解析では抽出されるデータ依存関係の我々の研究グループが提案したデータフローの可視化手法4) では，文の順序に関わらず，みを示すものとする．制御フローを考慮したデータ依存関係解析であっても，たとえば条件

ソフトウェアエンジニアリングシンポジウム 2011

© 2011 Information Processing Society of Japan3

制御フローを考慮しないデータ依存関係解析の実験的評価

式が必ず偽になる if 文に含まれた代入文などが原因で，プログラムの実行時に発生しえななるのは，STORE 命令群と IINC 命令である．代入命令の数と参照命令の数の積が，制御フ

いデータ依存関係を持つことはある12) が，それらは不適切なパスとはみなさない．

ローを考慮しない場合のデータ依存辺の数となり，制御フローグラフから計算されたデータ
依存辺の数との差が，不適切なパスの数となる．

3. データ依存関係の調査

取り扱うローカル変数．本研究で扱うローカル変数とは，メソッドの中で宣言されたすべ制御フローの考慮がデータ依存関係の正確さに与えている影響を明らかにするために，制てのローカル変数であり，メソッドの仮引数や，catch 節で宣言された変数を含む．メソッ

御フローを考慮せず近似したデータ依存関係を，従来のデータ依存関係解析の結果と比較

ドを実行しているオブジェクトを表現する予約語 this については，仮引数の一種と考えるした．プログラムに含まれるデータ依存関係は，ローカル変数，メソッド呼び出しの引数，こともできるが，メソッドの実行中には書き換えが不可能な値であり，データ依存関係を必

戻り値あるいは例外，フィールドによって生じるが，本研究では，このうち，ローカル変数

ず正しく抽出できるため，今回の解析対象からは除外している．

によって生じる手続き内データ依存関係の調査を行っている．メソッド呼び出しの引数や戻り値によって生じるデータの流れは動的束縛の解決の正確さによって定まるが，広く使用さ仮引数に関するデータ依存関係．メソッドの最初の命令の直前に，すべての仮引数に値を代入する仮想的な命令があるとみなすことで，データ依存関係解析を行う．

れている Class Hierarchy Analysis3) はクラス階層情報のみを使用して動的束縛の解決を

例外の発生に関する制御フローの扱い． Java では，命令の実行中に例外が発生すると，行うため，制御フロー解析の有無は，メソッド呼び出しによって生じるデータ依存関係に影対応する catch ブロックに制御が移動する．本研究では，try ブロックのすべての命令に響を与えない．

ついて，その実行後に catch に遷移する可能性があると仮定した．なお，このような仮定

フィールドや配列によって生じる手続き内・手続き間データ依存関係については，同一のを置かないと，catch ブロック内の命令が制御フローグラフ上で到達不能になってしまい，

オブジェクトを読み書きする可能性のある文間で，データ依存関係を接続することになる．

制御フローを考慮した場合にデータ依存関係の見逃しが生じる可能性がある．本研究では，

このデータ依存関係の解析は，同一のオブジェクトを参照する可能性の有無をポインタ解析

制御フローを考慮した場合に正しい結果が出ることが望ましいと考え，例外に関する実行経の結果に基づいて判定することになる．本研究のように制御フローグラフの作成を行わない路はすべて接続するものとした．

のであれば，制御フローを考慮しないポインタ解析アルゴリズム

11)が適用可能である一方

バイトコード上でのローカル変数の区別方法．ローカル変数は，バイトコード上では名前

で，制御フローを考慮したポインタ解析手法は適用不可能である．制御フロー解析の有無にではなく，変数に割り当てられた記憶域を示すインデクスで区別されており，スコープが互よる，フィールドや配列によって生じるデータ依存関係の変化の比較は，ポインタ解析のア

いに重ならない変数に関しては，異なる変数であっても同一のインデクスを割り当てられルゴリズムの違いにも影響を受けるため，本論文ではメソッド間データフローに関しては，る可能性がある．本研究では，変数が同一のインデクスを持ち，同名であり，かつスコープ

議論の対象から外している．

の有効範囲が制御フローグラフ上で連結成分となっている場合にのみ同じ変数とみなすこ

3.1 データ依存関係の抽出方法とで，異なるスコープに出現するローカル変数を区別する．デバッグ情報が付与されていな

本研究では，Java プログラムの各ローカル変数について，制御フローを考慮したデータ

いメソッドについては，ローカル変数の区別はインデクスのみで行った．これによって複数依存関係解析を実行する．データ依存関係の解析には，以下のような方式，条件を採用した．

の変数を同一視してしまった場合は，不適切なパスの出現を多く見積もる可能性はあるが，バイトコード解析．データ依存関係の解析は，Java のバイトコード解析を用いて実装し見逃しは生じない．

た．バイトコード上では，finally ブロックや break，continue などの実行制御文が，い3.2 調 査 対 象

わゆる GOTO 命令の形式に変換されており，容易に制御フローグラフを取得することがで調査対象とした 10 個のプログラムを表 1 に示す．このうち，和歌山大学教務システムは，きる．バイトコード上では，ローカル変数の値を計算用のスタックに読み出す LOAD 命令群

教育プロジェクト IT Spiral19) で提供されているソフトウェア開発データである．JDK と（int 型変数に対する ILOAD など変数型ごとの命令10) ）と，ローカル変数の値をインクリメ

和歌山大学教務システムを除き，バイナリ配布のパッケージ（ZIP ファイル）に含まれるすントする IINC 命令が，ローカル変数に対する参照となる．また，ローカル変数への代入とべてのクラスファイルを解析対象とした．バイナリ配布パッケージには，サンプルコードな

ソフトウェアエンジニアリングシンポジウム 2011

© 2011 Information Processing Society of Japan4

制御フローを考慮しないデータ依存関係解析の実験的評価
表 1 解析対象の Java プログラム
Table 1 Target Java Programs

Program

析を行わなくとも，従来のデータ依存関係解析と同一の結果を得ることができる変数．

#Classes#Methods#Variables

1063
1177
2368
5877
33270
15951
1045

10930
11033
25632
46326
258073134497
7521

26129
20282
60422
10048561009930823918417

Torque 3.3
Vuze 4.6.0.2

3788
2106
6739

36484
21468
41822

70842
40340
101912

Total

72575

5843531339110ANTLR 3.3
Apache Ant 1.8.2
Apache Tomcat 7.0.8
Batik 1.7
Eclipse SDK 3.6.2
JDK 1.6.0
JEdit 4.3.2
和歌山大学教務システム19)

Split: 変数の名前を付け替えることで，複数の Correct 変数に分割することができる変数．具体例を示すと，図 2 に示されている 2 つのコード片のうち，左側のコードに登場する変数 x が該当する．このコードでは，1 行目で x に代入された値は 2 行目のみで使われており，3 行目で x に代入された値は 4 行目で使われている．そのため，1 行
目から 2 行目までと，3 行目から 4 行目までのデータ依存関係が完全に独立したものとなっており，図 2 右側のコードのように変数の名前を付け替えると，不適切なパスを除去することができる．このような変数は，本来は Correct 変数のみで記述できる処理であることから，次の Infeasible とは区別して扱う．

Infeasible: 不適切なパスを 1 つ以上持ち，かつ，Split の条件を満たさない変数．
次に，これら 3 つの分類の形式的な定義を示す．まず，ローカル変数 v について，代入
命令集合を Dv ，参照命令集合を Uv とすると，データ依存辺の集合 Ev は，次のように表現できる．

1: int x = a_value;
2: use(x);3: x = another;
4: anotherUse(x);1: int x1 = a_value;
2: use(x1);
3: int x2 = another;
4: anotherUse(x2);

図 2 変数の名前変更によって不適切なパスを除去できるコードの例．
Fig. 2 A variable renaming that prevents infeasible data-ﬂow paths

Ev = {(d, u)|d ∈ Dv から u ∈ Uv へと，代入命令 k ∈ Dv (k = d) を通過せずに到達可能な制御フローグラフ上の経路が存在する．}
また，制御フローを考慮しないデータ依存辺 Iv は，次のように定義できる．

Iv = {(d, u)|d ∈ Dv , u ∈ Uv }これらを用いて，各変数 v の分類 Correct, Split, Infeasible を，次のように定義する．

ども含まれていることがあるが，コンパイルされているファイルはすべて解析対象とした．

Correct: Ev = Iv が成立する変数．

JDK に関しては，jre/lib サブディレクトリ下にある rt.jar をはじめとするファイルをSplit: Ev = ∪ki=1 Ivi となるように，Dv と Uv をそれぞれ Dv1 , · · · , Dvk および

解析対象とした．和歌山大学教務システムは，著者の環境で Eclipse 3.4 を用いてコンパイ

Uv1 , · · · , Uvk と分割1 することが可能な変数．

ルしたもので，ある企業によって書かれた 170 個のクラスと，これらのクラスが使用して

図 2 の左側のコードにおける変数 x の場合，1 行目で代入された値は 2 行目のみで使われいるオープンソースのフレームワークやライブラリをすべて含んだ数値である．

ており，3 行目で代入された値は 4 行目で使われているから，Dx = {1, 3}, Ux = {2, 4}

Total 行には，10 個のシステムの合計を示しているが，2 つ以上のシステムに共通したクであり，Ex = {(1, 2), (3, 4)} となる．これは明らかに Iv = {(1, 2), (1, 4), (3, 2), (3, 4)}

ラス 809 個を取り除いているため，各システムの個別の値の合計とは一致しない値になっとは異なるため，x は Correct の条件を満たさない．Dx , Ux を Dx1 = {1}, Dx2 =ている．クラスの重複は，同一パッケージ名，同一クラス名によって判定している．

{3}, Ux1 = {2}, Ux2 = {4} へと分割すると，Ix1 = {(1, 2)}, Ix2 = {(3, 4)} となり，

3.3 データ依存関係に基づく変数の分類

Ex = Ix1 ∪ Ix2 が成り立つことから，x は Split の条件を満たす．

変数ごとに計算されたデータ依存関係の情報から，制御フローを考慮せずともデータ依存関係を抽出できるかどうかで，変数を次の 3 種類に分類する．

Correct: すべての代入からすべての参照にデータ依存関係を持っており，制御フロー解

ソフトウェアエンジニアリングシンポジウム 2011

1 集合 S の分割とは，S = ∪ki=1 Si を満たし，1 ≤ i, j ≤ k, i = j であるようなすべての i, j についてSi ∩ Sj = φ を満たすような S の部分集合 S1 , · · · , Sk を求めることである．

© 2011 Information Processing Society of Japan5

制御フローを考慮しないデータ依存関係解析の実験的評価
表 2 データ依存関係に基づく変数の分類結果
Table 2 Variables categorized by data dependence

ProgramVariables

CorrectSplit

表 3 データ依存関係に基づくメソッドの分類結果
Table 3 Methods categorized by data dependence

Infeasible

Program

Methods

Correct

Split

Infeasible

ANTLR 3.3
Apache Ant 1.8.2
Apache Tomcat 7.0.8
Batik 1.7
Eclipse SDK 3.6.2
JDK 1.6.0
JEdit 4.3.2
和歌山大学教務システム
Torque 3.3
Vuze 4.6.0.2

26129
20282
60422
100485610099308239
18417
70842
40340
101912

22754
18976
56136
90415
577535273458
17383
66048
37238
97566

(87.1%)(93.6%)(92.9%)(90.0%)(94.7%)(88.7%)(94.4%)(93.2%)(92.3%)(95.7%)

2275
529
1760
5298
13667
22971
379
2474
1782
1817

(8.7%)(2.6%)(2.9%)(5.3%)(2.2%)(7.5%)(2.1%)(3.5%)(4.4%)(1.8%)

1100
777
2526
4772
18897
11810
655
2320
1320
2529

(4.2%)(3.8%)(4.2%)(4.7%)(3.1%)(3.8%)(3.6%)(3.3%)(3.3%)(2.5%)ANTLR 3.3
Apache Ant 1.8.2
Apache Tomcat 7.0.8
Batik 1.7
Eclipse SDK 3.6.2
JDK 1.6.0
JEdit 4.3.2
和歌山大学教務システム
Torque 3.3
Vuze 4.6.0.2

10930
11033
25632
46326
258073147962
7521
36484
21468
41822

9480
10218
23163
41641
237420130518
6817
33620
19690
39260

(86.7%)(92.6%)(90.4%)(89.9%)(92.0%)(88.2%)(90.6%)(92.1%)(91.7%)(93.9%)

482
262
722
1752
7064
9373
219
1018
819
876

(4.4%)(2.4%)(2.8%)(3.8%)(2.7%)(6.3%)(2.9%)(2.8%)(3.8%)(2.1%)

968
553
1747
2933
13589
8071
485
1846
959
1686

(8.9%)(5.0%)(6.8%)(6.3%)(5.3%)(5.5%)(6.4%)(5.1%)(4.5%)(4.0%)

Total

13391101240879(92.7%)

52279(3.9%)

45952(3.4%)

Total

597818543260(90.9%)

22324(3.7%)

32234(5.4%)

なお，変数 v が Split の条件を満たすとき，Dv および Uv の分割方法 v1 , · · · , vk は一

3.4 データ依存関係に基づくメソッドの分類

意に定まる．なぜなら，他に分割の候補 v1 , · · · , vl を作るには，少なくとも 1 つの vi に変数に対する分類の結果は，各変数が不適切なパスの原因になっているかどうかを示すもついて，d ∈ Dvi , u ∈ Uvi であるが，ある m, n(m = n) について d ∈ Dv m , u ∈ Uv nのである．各メソッドについて考えると，1 つでも，不適切なパスを生じる変数が存在すれとなるような組 (d, u) を作らなければならない．ここで，(d, u) ∈ Ev であるが，ば，そのメソッドについては不適切なパスを生じることになる．そこで，変数の分類結果を(d, u) ∈/ Iv m かつ (d, u) ∈/ Iv n となり，Ev = ∪li=1 Iv i を満たすことができない．よっ用いて，メソッドに対しても同様の分類を行う．

て，条件を満たす分割は v1 , · · · , vk の他には存在しない．

Correct: メソッドに出現するすべてのローカル変数が Correct に分類されているメソッ

Infeasible: Ev = Iv であり，Split の条件を満たさない変数．
この形式化に基づいて，調査対象のすべてのローカル変数を分類した結果を表 2 に示す．

ド．つまり，制御フロー解析を行わなくとも，従来のデータ依存関係解析と同一の結果を得ることができるメソッド．

この表から，変数の 90%に関しては，制御フロー解析なしでも，従来のデータ依存関係とSplit: メソッドに出現する 1 つ以上のローカル変数が Split に分類されており，残るすべ同一の計算結果を得ることができ，変数名の簡単な変更を行うだけで，95%の変数についてのローカル変数が Correct に分類されているメソッド．つまり，開発者が変数の名ては正しい結果を得ることができると読み取れる．プログラムごとに大きな差は見られず，

前を付け替えさえすれば，プログラムの意味を変えることなく従来のデータ依存関係解Java プログラムにおいて一般的な傾向であると考えることができる．

析と同一の結果を得ることができるようになるメソッド．

このような結果が出た理由の 1 つとして，1 つの変数を 1 つの目的にのみ使うというコー

Infeasible: メソッドに出現する 1 つ以上のローカル変数が Infeasible に分類されている

ディング方法が考えられる．各変数について，その代入命令の個数を数えたところ，代入

メソッド．制御フローの考慮なしには不適切なパスを生じるメソッドがここに分類さ命令がただ 1 つであるような変数，すなわち不適切なパスが抽出されることのない変数はれる．

85.3%を占めていた．代入命令が 2 つであるような変数が 10.7%であり，代入命令が 3 つ以

表 3 に，メソッド単位での分類結果を示す．メソッド単位で考えた場合でも，90.9%のメ

上あるような変数は約 4%となっている．これら 14.7%の変数のうち，3 分の 1 だけが，制ソッドについては制御フロー解析なしに，従来のデータ依存関係解析と同一の結果を得るこ御フローの考慮が必要な変数に該当している．

とが可能である．また，変数の場合と同様に，プログラムごとの差異は大きくない．
正確な結果を必要とする解析では，メソッドが不適切なパスを持ちうる場合にのみ制御

ソフトウェアエンジニアリングシンポジウム 2011

© 2011 Information Processing Society of Japan6

制御フローを考慮しないデータ依存関係解析の実験的評価
表 4 制御フロー解析が必要な変数，メソッドの割合
Table 4 Variables and Methods that requires ﬂow-sensitive analysis

ProgramVariables
Incorrect
代入 2 回以上

ル変数のデータ依存関係を知ることの価値が低いことになってしまう．そこで，オブジェク

Methods
Incorrect
代入 2 回以上

ANTLR 3.3
Apache Ant 1.8.2
Apache Tomcat 7.0.8
Batik 1.7
Eclipse SDK 3.6.2
JDK 1.6.0
JEdit 4.3.2
和歌山大学教務システム
Torque 3.3
Vuze 4.6.0.2

3375
1306
4286
10070
32564
34781
1034
4794
3102
4346

5482
2626
9938
17752
80494
53015
2482
9271
5659
11984

(21.0%)(12.9%)(16.4%)(17.7%)(13.2%)(17.2%)(13.5%)(13.1%)(14.0%)(11.8%)

1450
815
2469
4685
20653
17444
704
2864
1778
2562

2279
1340
4291
7232
41481
24840
1347
4849
2976
5297

(20.9%)(12.1%)(16.7%)(15.6%)(16.1%)(16.8%)(17.9%)(13.3%)(13.9%)(12.7%)

Total

98231

195935(14.6%)

54558

94440

(15.8%)

トを考慮しない解析（object-insensitive analysis）によって，フィールドや配列によって生じている手続き内データ依存関係の個数を調べた．
フィールドや配列の値は，オブジェクト参照や添え字の値によって，読み書きする記憶領域が変化する．ローカル変数であれば，値の書き込みによってそれまで格納されていた値を必ず上書きすると考えるが，フィールドの場合は別オブジェクトへの書き込み，配列の場合は異なる添字を用いての書き込みの可能性を考慮して，各書き込み命令で書かれた値は，それまでに書き込まれた値を上書きするとは限らないと考える．つまり，一度書き込まれた値
は，制御フローによって到達しうるすべての読み込み命令によって参照される可能性があるとみなす．フィールドに関しては，フィールドの名前，型，所有クラス名によって区別し，あるフィールドに値を代入する命令から，同一フィールドの値を参照する命令に到達可能であれば，そのフィールドが手続き内でのデータ依存関係に関係していると考える．配列に関しては，解析の簡略化のため，プリミティブ型の配列は型名によって区別し，オブジェクト

フローを考慮した解析を実施し，そうでない場合には制御フローを考慮しない解析を行うを格納する配列に関しては型を無視してすべて同一種の配列とみなす．ある配列への書き込という方式が可能である．この判定を軽量に，かつ安全行うことができると考えられる基み命令から，同じ要素型の配列の読み込み命令へと制御フローによって到達可能であれば，準は，「変数への代入が 2 つ以上存在すること」である．変数への代入が 1 つしかなければ，その配列が手続き内のデータ依存関係に関係していると考える．

参照がどれだけあっても，必ずその代入が到達するはずなので，安全に解析を行うことがで解析の結果，10 個のプログラムに定義されたフィールドは全部で 245,684 個であり，1きる．表 4 に，代入が 2 つ以上ある変数の割合と，そのような変数を少なくとも 1 つ持つつのフィールドは，平均で 1.47 個のメソッドによって値を書き込まれ，2.69 個のメソッド

ようなメソッドの割合を示す．この表において，Incorrect 列は，分類が Correct ではない

によって値を参照される．1 つの手続き内で，フィールドへの代入命令から，同一フィール（Split または Infeasible である）変数およびメソッドの数を示しており，代入が 2 回以上

ドの参照命令に到達可能であったメソッドは，36,732 個であった．これは，全メソッドのある変数は，これらの変数を包含し，その数はおよそ 2 倍から 3 倍程度となっている．ま

6.1%である．また，配列に対する書き込み命令から配列の読み込み命令に到達可能なメソッ

た，代入が 2 回以上ある変数を少なくとも 1 つ持つようなメソッドの数は，Correct に分類

ドは 9,290 個であった．これは全メソッドの 1.6%である．これらの結果から，メソッドのされたメソッドの 2 倍程度であった．この表から，すべてのメソッドのうち 15.8%だけに多くはローカル変数を手続き内でのデータの受け渡しに用いており，制御フローを無視した

制御フロー解析を行えば，正確なデータ依存関係を計算することができることが分かる．プ

解析によって手続き内のデータ依存関係を正しく計算できることを示している．

ログラムによって値は異なり，今回の調査対象では最大で 20.9%となっているが，それでも全体に対して解析する場合に比べて，時間コストを大幅に削減できる可能性を示している．

4. 議

論

3.5 フィールド，配列の手続き内データ依存関係への関与

4.1 妥当性への脅威

ここまで，ローカル変数によって生じる手続き内データ依存関係について制御フロー解析

本研究の結果は，10 個の Java プログラムに対して求められたものである．対象となったなしでも，制御フロー解析ありの場合と同じ計算結果が得られるメソッドの割合を示した．

プログラムは，開発環境，サーバ，テキストエディタなど様々な目的のために作られたソフ

しかし，手続き内でのデータ依存関係に，フィールドや配列が大きく貢献しているのであれ

トウェアであり，アプリケーションソフトウェアやライブラリを含んでいることから，多様ば（開発者が配列やフィールドを手続き内でのデータ受け渡しに使用していれば），ローカ

な Java プログラムの書き方が反映されていると考えられる．一方で，企業の開発者が記述

ソフトウェアエンジニアリングシンポジウム 2011

© 2011 Information Processing Society of Japan7

制御フローを考慮しないデータ依存関係解析の実験的評価

したコードは和歌山大学教務システムの一部に限られており，企業の開発者が従うコーディて行ったものである．制御フローを考慮しないことによる正確さの変化が，悦田の実験4) でング規約による影響はあまり反映されていない．そのため，企業のソフトウェアを収集しては開発者の作業に悪影響を与えなかったが，プログラムスライシングなどデータ依存関係実験を行うと，異なる結果となる可能性がある．

を使用した手法に与える影響は，まだ評価していない．この評価にあたっては，データ依存

本研究での調査は，プログラミング言語を Java に限定したものとなっている．近年では

辺の有無だけでなく，グラフ上での到達関係の変化に与える影響（Ripple Eﬀect）が問題

企業のソフトウェア開発でも Java が多く採用されていることから，この結果自体は有益でとなる．たとえば，図 1 のコード片に対して，6 行目の変数 f に対するプログラムスライ

あるが，たとえば C 言語や COBOL など，他の言語に適用した場合には，言語特有のコースを計算すると，制御フローを考慮した場合でも，しなかった場合でも，1 行目から 5 行目

ディング方法による違いが出る可能性がある．

までがスライスに含まれるので，データ依存関係の差異はスライス結果に影響を与えない．

本研究では，データ依存関係解析をバイトコード上で定義し，例外処理に関しては保守的

一方，2 行目の変数 filename に対するプログラムスライスは，制御フローを考慮すると 1

な制御フロー解析を採用した．例外処理を含む制御フローグラフをより正確に構築すること

行目だけであるが，制御フローを考慮しないと 1 行目と 3 行目がスライスに含まれることができれば，制御フローを考慮したデータ依存関係解析がより正確になり，制御フローを考になり，結果に違いが生じる．このような解析結果への影響の評価は，今後の課題である．

慮しない解析の正確さが相対的に低下する可能性がある．
バイトコード上でデバッグ情報から変数の識別を行ったため，デバッグ情報の不足や，コ

5. 関 連 研 究

ンパイラによって自動生成された変数が結果に反映されている．デバッグ情報が不足した変本研究では，データ依存関係の定義そのものは変更せず，制御フローを考慮せずに計算し数については，スコープの異なる 2 つ以上の変数を同一視している．このとき，1 変数あた

たデータ依存関係の結果を，従来の計算方法と比較した．この方法と対照的なアプローチ

りの代入命令の数を多く算定するので，本来なら Correct であった 2 つの変数が，1 つのとして，Jász ら7) による，データ依存関係を制御フローで近似する手法が提案されている．

Split に変わっている可能性がある．また，自動生成された変数，たとえば拡張 for 文にJász らの方式は，ある命令が，別の命令よりも後に実行されるのなら，前の命令に何らかよって作られる Iterator 型の変数によって，正しく解析可能な変数の数を増加させている．

の影響を受けていると考える．単純に制御フローグラフ上での順序関係を用いるので，逐次

ただし，自動生成された変数に関しては，メソッド単位での計算には影響を与えていない．

的に実行される処理であれば，高速に正確な結果を得られるが，メッセージループからすべ

4.2 プログラムスライシングへの影響ての処理を呼び出す種類のプログラムに対しては正確な結果を得られない．一方で，本研究

本研究では，データ依存関係の近似計算のみを議論している．システム依存グラフの定のようにデータ依存関係のみを用いる手法では，処理の順序を考慮しないため，逐次的に行義

5)には制御依存関係も含まれており，本研究の成果が，ただちにプログラムスライシングを置き換えるわけではない．

われる変数の更新に対して不適切なパスを抽出することがある．そのため，2 つの手法は互
いに相補的な関係にあると考えられる．

プログラムスライシングにおいて，正確な計算を要求する場合は，データ依存関係を求め

この他の関連研究として，特定の目的に適用できるように，簡略化した依存関係解析を定る計算のみを省略する形で，計算時間の短縮に貢献する．Thin Slicing16) のように，デー義した手法が存在する．Groum13) は，Java の 1 つのメソッド内部で生じるメソッド呼び

タ依存関係のみを用いるスライシング技法には，本研究の成果をただちに適用可能である．

出しとフィールドへのアクセスの順序関係を，循環を持たない有向グラフとして表現したもプログラムスライシングの簡略化を行い，制御フローグラフの構築を完全に省略することのである．Groum は，メソッド呼び出しなどの順序に対するパターンマイニングを目的と4)を目指す場合は，制御依存関係を近似計算する手法が必要である．悦田の手法の場合はしているため，2 つの文が少なくとも 1 つの変数を共有していればそれら 2 つの文に依存関

構文情報のみを用いた近似計算を導入しているが，この方法に基づく近似計算の性能に関し係があるという単純な定義を用いている．そのかわり，ループ構造によるデータ依存関係なては，実験による評価が今後の課題となっている．

どは抽出しない．

4.3 Ripple Eﬀect
本研究におけるデータ依存関係の正確性の評価は，すべて手続き内の個別の依存辺に対しソフトウェアエンジニアリングシンポジウム 2011

Lawall ら9) は，C 言語における整数型の定数に関するデータ依存関係を抽出する手法を提案している．実装上は制御フローを考慮している解析であるが，定数が代入されうる変数© 2011 Information Processing Society of Japan8

制御フローを考慮しないデータ依存関係解析の実験的評価に関するビット演算，比較演算のみに限定して解析を行い，不適切な定数比較を検出する手法となっている．

6. ま と め
本研究では，制御フローを考慮せず，すべての代入文から参照文へと辺を接続して得られるデータ依存関係であっても，90.9%のメソッドについては，制御フロー解析を用いた従来の解析手法と同一の結果を得ることができ，また，正確な結果を得たい場合に解析が必要なメソッドは 15.8%だけであることを示した．
今後の課題として，制御フローグラフを考慮しない場合に生じるデータ依存関係が，推移的な到達関係に与える影響と，エイリアス解析やプログラムスライシングなどの高度な解析手法に与える影響を評価することが挙げられる．プログラムスライシングのような手続き間のデータ依存関係解析は，計算に時間がかかることから，大規模プログラムに対してはほとんど適用されていない．制御フローグラフの構築を省略した高速なデータ依存関係に基づいて，プログラムスライシングなどの解析を実用上問題ない正確さで計算できるのであれば，大規模プログラムに対する高度な解析手法の適用が容易になると考えられる．
謝辞 本研究は，日本学術振興会科学研究費補助金基盤研究（A）（課題番号:21240002）の助成を得た．

参 考 文 献1) Ambler, S.W.: Writing Robust Java Code. The AmbySoft Inc. Coding Standards
for Java, v17.01d, Chapter 4 (2000).
2) Chen, K. and Rajlich, V.: Case Study of Feature Location Using Dependence
Graph, Proceedings of the 8th International Workshop on Program Comprehension,
pp.241–247 (2000).
3) Dean, J., Grove, D. and Chambers, C.: Optimization of Object-Oriented Programs
Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference
on Object-Oriented Programming, pp.77–101 (1995).
4) 悦田翔悟，石尾 隆，井上克郎：変数間データフローグラフを用いたソースコード間の移動支援，情報処理学会研究報告（SE）， Vol.2011-SE-171, No.12, pp.1–8 (2011).
5) Horwitz, S., Reps, T. and Binkley, D.: Interprocedural Slicing Using Dependence
Graphs, ACM Transactions on Programming Languages and Systems, Vol.12, No.1,
pp.26–60 (1990).
6) 石尾 隆，仁井谷竜介，井上克郎：プログラムスライシングを用いた機能的関心事の抽出，コンピュータソフトウェア，Vol.26, No.2, pp.127–146 (2009).

ソフトウェアエンジニアリングシンポジウム 20117) Jász, J., Árpád Beszédes, Gyimóthy, T. and Rajilich, V.: Static Execute After/Before as a Replacement of Traditional Software Dependencies, Proceedingsof the 24th IEEE International Conference on Software Maintenance, pp.137–146(2008).
8) Komondoor, R. and Horwitz, S.: Eﬀective, Automatic Procedure Extraction, Proceedings of the 11th International Workshop on Program Comprehension, pp.33–42(2003).
9) Lawall, J. and Lo, D.: An Automated Approach for Finding Variable-ConstantPairing Bugs, Proceedings of the 26th IEEE/ACM International Conference on Automated Software Engineering, pp.103–112 (2010).
10) Lindholm, T. and Yellin, F.: Java Virtual Machine Speciﬁcation, the 2nd Edition,
Prentice Hall (1999).
11) Milanova, A.: Light Context-Sensitive Points-to Analysis for Java, Proceedings ofthe 7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software
Tools and Engineering, pp.25–30 (2007).
12) Ngo, M.N. and Tan, H. B.K.: Detecting Large Number of Infeasible Paths throughRecognizing their Pattenrs, Proceedings of the 15th Symposium on Foundations ofSoftware Engineering, pp.215–224 (2007).
13) Nguyen, T.T., Nguyen, H.A., Pham, N.H., Al-Kofahi, J.M. and Nguyen, T.N.:
Graph-based mining of multiple object usage patterns, Proceedings of the the 7th
joint meeting of the European Software Engineering Conference and the ACM SIGSOFT symposium on the Foundations of Software Engineering, pp.383–392 (2009).
14) Parnin, C. and Rugaber, S.: Resumption strategies for interrupted programming
tasks, Software Quality Journal, Vol.19, No.1, pp.5–34 (2011).
15) 柳 慶吾，石尾 隆，井上克郎：ソフトウェア部品利用例抽出のためのデータフロー
解析手法の提案と評価，情報処理学会研究報告（SE）， Vol.2010-SE-167, No.29, pp.
1–8 (2010).
16) Sridharan, M., Fink, S.J. and Bodik, R.: Thin Slicing, Proceedings of the ACM
SIGPLAN 2007 Conference on Programming Language Design and Implementation, pp.112–122 (2007).
17) Wang, X., Lo, D., Cheng, J., Zhang, L., Mei, H. and Yu, J. X.: Matching
Dependence-Related Queries in the System Dependence Graph, Proceedings of the
26th IEEE/ACM International Conference on Automated Software Engineering,
pp.457–466 (2010).
18) Weiser, M.: Program Slicing, IEEE Transactions on Software Engineering, Vol.10,
No.4, pp.352–357 (1984).
19) 先導的 IT スペシャリスト育成推進プログラム：http://it-spiral.ist.osaka-u.ac.jp/.

© 2011 Information Processing Society of Japan