Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラム静的解析手法の効率化と
解析フレームワークの構築に関する
研究
大阪大学 大学院基礎工学研究科
情報数理系専攻 ソフトウェア科学
分野
大畑 文明
背景
ソフトウェアの大規模化による、開発作業の複雑化
高品質ソフトウェアを効率よく開発する要求の高ま
り
ソフトウェアの品質改善、開発作業の生産性向上の必
要性
プログラム解析 : プログラムからその性質やふるま
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University3
プログラム静的解析
プログラム静的解析 : 対象プログラムの実行を必
要としないプログラム解析技法で、一般に対象プ
ログラムのソースコードに対して行われる
プログラム静的解析により得られる解析情報 ( 例 )
データフロー
制御フロー
抽象構文木
クラス階層
…
問題点
既存のプログラム解析手法は、
解析精度の向上
ある解析対象に特化した手法の提案及び実装
を重視してきた
(a) 解析の効率
(b) 解析コストと解析精度のトレードオフ制御
(c) 解析情報の二次利用
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University5
(a) 効率
プログラミング言語の高級化、プログラムの
大規模化
解析コストの増大
目標
解析アルゴリズムの効率化
解析手順の効率化
(b) トレードオフ制御
解析コストと解析精度はトレードオフ関係
解析コストを抑えると、解析精度が低下する
解析精度を向上させると、解析コストは増大する
求められるコストと精度のバランスは、目的に
よって様々
目標
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University7
(c) 二次利用
二次利用を想定していない実装
解析により得られた情報はメモリ上にのみ記憶
される
別の解析での利用を考慮していたとしても、特
定のプログラミング言語による API を要求する
目標
二次利用を考慮し、その利用者への制約の少な
い、解析情報データベース
目的
(a) 効率、 (b) トレードオフ制御、 (c) 二次利用
を考慮したプログラム静的解析手法及び、プログ
ラム解析フレームワークの構築に関する研究を
行った
(a) に重点を置き、プログラムスライス計算、エイリア
ス解析、意味解析木構築の効率化手法をそれぞれ提案
(b) 、 (c) については、各効率化手法の中で議論
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University9
第 1 章
. まえがき
第 2 章 . プログラム依存グラフの節点集約による
スライス計算の効率化 [1-1,1-3]
→ プログラムスライス計算の効率化 … (a),(b) に
配慮
第 3 章 . エイリアス情報のモジュール化による
エイリアス解析の効率化 [1-2]
→ エイリアス解析の効率化 … (a),(b) に配慮
第 4 章 . XML データベースを利用した
プログラム解析の効率化 [1-6]
→ 意味解析木構築の効率化 … (a),(c) に配慮
第 5 章 . むすび
論文の構成
節点集約によるスライス計算の効率
化
[ 論文の 2 章 ]
プログラムスライス
節点集約
依存関係の局所性を利用した節点集約法
節点分解を伴う節点集約法
Pascal スライスシステム
Osaka Slicing System (OSS)
-評価
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University11
プログラムスライス
プログラムスライス : ある文のある変数 ( スライ
ス基準 ) の値に影響を与える可能性のある文の集
合
適用分野
プログラムデバッグ
プログラム理解
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d = b;
}
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d =
b
;
}
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d = b;
}
1:
b = 5;
2:
a = b + b;
3:
if(a > 0) {
4: c = a;
5:
d = b;
}
スライス基準 <5, b> に対する
スライス
PDG によるスライス計算
計算過程
… スライス計算のグラフ到達問題への置き換え
による
Phase 1: 定義、参照変数の抽出
Phase 2: 依存関係解析
Phase 3: プログラム依存グラフ (
PDG
) の構築
節点 : プログラム文
辺 : プログラム文間の依存関係
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University13
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
b = 5
d = b
c = a
if (a > 0)
a = b + b
PDG によるスライス計算 ( 例 )
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d = b;
}
1:
b = 5;
2:
a = b + b;
3:
if(a > 0) {
4: c = a;
5:
d = b;
}
b = 5
d = b
c = a
if (a > 0)
a = b + b
b
a
b
a
b = 5
d = b
c = a
if (a > 0)
a = b + b
b
a
b
a
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d = b;
}
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d =
b
;
}
b = 5
d = b
c = a
if (a > 0)
a = b + b
b
a
b
a
節点集約
Phase 2: 依存関係解析 が最も解析コストを要する
節点集約 : 通常各文の依存情報は対応する PDG
節点に保持させるが、複数文の依存情報を 1 つの
PDG 節点に保持させる
PDG の節点数及び辺数の減少
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University15
集約の制御
節点集約アルゴリズムは、集約の程度を制御
するためのパラメータ
limit
(
limit
0) を持
つ
limit
を拡大 : コストは減少、精度は低下
limit
を縮小 : コストは増加、精度は向上
b = 5
d = b
c = a
if (a > 0)
a = b + b
b
a
b
a
集約なし
b = 5
a = b + b
d = b
c = a
if (a > 0)
b
a
a
集約あり (
limit
= 0)
b = 5
a = b + b
c = a
d = b
if (a > 0)
a,b
a
集約あり (
limit
= 1)
集約
b = 5;
a = b+b;
if (a > 0) {
c = a;
d = b;
}
集約あり (
limit
= )
集約の応用 (2 つの節点集約法 )
依存関係の局所性を利用した節点集約法 (
limit
« )
精度低下の少ない、時間コスト及び空間コスト削減
節点分解を伴う節点集約法 (
limit
= )
精度低下のない、時間コスト削減
節点分解が必要であるため、空間コストは増加
(b) トレードオフ制御 への配慮
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University17
依存関係の局所性を利用した節点集約
法
依存関係の局所性 : 集約対象となる文集合
が持つ、依存関係の類似性
局所性が強い文同士の集約では、精度低下が少
ない
b = 5
a = b + b
d = b
c = a
if (a > 0)
b
a
a
集約あり (
limit
= 0)
b = 5
a = b + b
c = a
d = b
if (a > 0)
a,b
a
集約あり (
limit
= 1)
b = 5
d = b
c = a
if (a > 0)
a = b + b
b
a
b
a
集約なし
集約
節点分解を伴う節点集約法
依存関係の分類とその抽出方針
手続き間 ( 繰り返し解析が必要 ): 集約後に抽
出
手続き内 ( 繰り返し解析が不要 ): 分解後に抽
出
b = 5;
a = b+b;
if (a > 0) {
c = a;
d = b;
…
… = a;
…
…
b = 5
if (a > 0)
a = b + b
b
a
b
a
c
a
分解
b = 5;
a = b+b;
if (a > 0) {
c = a;
d = b;
…
… = a;
…
…
a
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University19
Pascal スライスシステム
Osaka Slicing System (OSS)
-対象言語 : Pascal
開発
言語 : C
ツールキット : Tcl/Tk
コード : 12,000 行
評価
OSS に対して Pascal プログラムを適用し、
既存手法との比較を行った
既存手法 : 節点集約を行わない
提案手法 : 節点集約 ( 及び節点分解 ) を行う
プログラム
[ 概要 ]
行
手続
き
P
1[ チケット予約 ]
333
14
P
2[ 酒屋問題 ]
429
18
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University21
考察
依存関係の局所性を利用した節点集約
解析コスト ( 時間 ): 5 ～ 30% の削減
解析コスト ( 空間 ): 5 ～ 40% の削減
解析精度 : 1 ～ 3% の低下
節点分解を伴う節点集約
解析コスト ( 時間 ): 15 ～ 60% の削減
解析コスト ( 空間 ): 約 10% の増加
解析精度 : 低下はなし
まとめ
節点集約によるスライス計算効率化手法の提案
依存関係の局所性を利用した節点集約法
節点分解を伴う節点集約法
OSS による提案手法の実装、及びその評価
(a) 効率、 (b) トレードオフ制御 への配慮
今後の課題
ポインタ変数の存在するプログラムへの適用
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University23
モジュール化によるエイリアス解析
の効率化
[ 論文の 3 章 ]
エイリアス
AFG によるエイリアス解析
Java エイリアス解析ツール
Java Alias Analysis Tool (JAAT)
-評価
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(c);
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(
c
);
エイリアス
エイリアス : ある文のある式 ( エイリアス基準 ) と
同一メモリ領域を指す可能性のある式の集合
適用分野
コンパイラ最適化
エイリアス基準 <6, c> に対するエ
イリアス
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(c);
1: Integer a, b, c;
2:
a
=
new Integer(1)
;
3: b = new Integer(2);
4: System.out.println
(b);
5:
c
=
a
;
6: System.out.println
(
c
);
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University25
エイリアス解析手法における問題点
(1/2)
エイリアス解析全般における問題点
スケーラビリティ : 実行順に従ってプログラム全体を解析
しなければならないため、大規模プログラムへの適用にお
けるコストは膨大なものになる
利用分野に適した解析手法 : プログラムデバッグ、プログ
ラム理解に利用する場合、求めるエイリアスのみを即座に
抽出できることが望まれる
スケーラビリティに配慮するための、モジュール解析
エイリアスを効率よく抽出するための、オンデマンド解析
の重要性
エイリアス解析手法における問題点
(2/2)
OO プログラムに対するエイリアス解析における問題
点
インスタンスを区別した解析 : 同一クラスのインスタンス
が属性に関するエイリアス情報を共有する方式では、解析
精度が低くなる
しかし、単純にインスタンスの数だけエイリアス情報を生
成してしまうと多大な空間コストが必要になるため、イン
スタンスを区別した解析は実現されてない
エイリアスを効率よく抽出するための、オンデマンド解析
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University27
AFG によるエイリアス解析 ( 方針 )
方針 : 2 フェーズ方式
Phase 1: メソッド内エイリアス解析 ( モジュール解析 )
メソッド単位に解析結果が保持される
インスタンス共通のエイリアス情報 の抽出
Phase 2: メソッド間エイリアス解析 ( オンデマンド解
析 )
メソッド単位の解析結果を結びつける
インスタンス独自のエイリアス情報 の抽出
(a) 効率 への配慮
解析アルゴリズムの効率化
AFG によるエイリアス解析 ( 計算
過程 )
計算過程
… エイリアス解析のグラフ到達問題への置き換
えによる
Phase 1: エイリアスフローグラフ (
AFG
) の構
築
… メソッド内エイリアス解析
節点 : 参照型の式
辺 : 式間のエイリアス関係
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University29
AFG によるエイリアス解析 ( 例 :
単純式 )
[Phase 1 ～ Phase 2]
a
new Integer(1)
new Integer(2)
b
b
a
c
c
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(c);
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(c);
a
new Integer(1)
new Integer(2)
b
b
a
c
c
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(c);
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(
c
);
a
new Integer(1)
new Integer(2)
b
b
a
c
c
1: Integer a, b, c;
2: a = new Integer(1);
3: b = new Integer(2);
4: System.out.println
(b);
5: c = a;
6: System.out.println
(c);
1: Integer a, b, c;
2:
a
=
new Integer(1)
;
3: b = new Integer(2);
4: System.out.println
(b);
5:
c
=
a
;
6: System.out.println
(
c
);
AFG によるエイリアス解析 ( 例 :
限定式 )
[Phase 2: “b.result()”]
Step 1: b に関するエイリアス計算 エ
イリアス :
A
(b)
Step 2:
A
(b) に関する情報の抽出 型 : Cal
c クラス
メソッド : Calc::Calc(), Calc::add(), Calc::result
()
Step 3: result() に関するエイリアス計算
class Test {
Calc a = new
Calc();
Calc b = new
Calc();
Integer c;
Test() {
class Test {
Calc a = new
Calc();
Calc b = new
Calc();
Integer c;
Test() {
a.inc();
public class Calc {
Integer i;
public Calc() {i = new
Integer(0); }
public void inc() {
i = new Integer(i.intValue() +
1);
}
public class Calc {
Integer i;
public Calc() {i = new
Integer(0); }
public void inc() {
i = new Integer(i.intValue() +
1);
}
public class Calc {
Integer i;
public Calc() {i = new
Integer(0); }
public void inc() {
i = new Integer(i.intValue() +
1);
}
public class Calc {
Integer i;
public Calc() {i = new
Integer(0); }
public void inc() {
i = new Integer(i.intValue() +
1);
}
public class Calc {
Integer i;
public Calc() {i = new
Integer(0); }
public void inc() {
i = new Integer(i.intValue() +
1);
}
public class Calc {
Integer i;
public Calc() {
i
=
new
Integer
(0); }
public void inc() {
i = new Integer(i.intValue() +
1);
}
class Test {
Calc a = new
Calc();
Calc b = new
Calc();
Integer c;
Test() {
class Test {
Calc a = new
Calc();
Calc b = new
Calc();
Integer c;
Test() {
a.inc();
class Test {
Calc a = new
Calc();
Calc b = new
Calc();
Integer c;
Test() {
class Test {
Calc a = new
Calc();
Calc
b
=
new
Calc
();
Integer c;
Test() {
a.inc();
class Test {
Calc a = new
Calc();
Calc b = new
Calc();
Integer c;
Test() {
class Test {
Calc a = new
Calc();
Calc
b
=
new
Calc
();
Integer c;
Test() {
a.inc();
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University31
AFG によるエイリアス解析 ( アル
ゴリズム )
アルゴリズム : フェーズごとに定義可能
Phase 1: メソッド内エイリアス解析
→ AFG 構築アルゴリズム
Phase 2: メソッド間エイリアス解析
→ AFG 探索アルゴリズム ( 変更が容易 )
(b) トレードオフ制御 への配慮
トレードオフ制御を考慮した解析アルゴリズム
Java エイリアス解析ツール
Java Alias Analysis Tool (JAAT)
-対象言語 : Java
開発
言語 : C++
ツールキット :
GTK--コード : 32,000 行
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University33
評価
JAAT に対し Java プログラムを適用し、提案
手法の有効性を検証
プログラム
サンプルプログ
ラム
関連するクラスライ
ブラリ
[ 概要 ]
ファイ
ル
行
ファイル
行
TextEditor
1
915
802
114,887
[ テキストエディタ ]
(0.1%)
(0.8%)
(99.9%)
(99.2%)
WeirdX
47 16,703
815
115,977
[X サーバ ]
(5.5%)
(12.6%)
(94.5%)
(87.4%)
ANTLR
129 18,775
267
33,847
[ 構文解析生成 ]
(32.6%)
(35.7%)
(67.4%)
(64.3%)
DynamicJava
242 32,037
825
119,564
[Java インタプリタ ]
(22.7%)
(21.1%)
(77.3%)
(78.9%)
考察
(1/3)
解析コスト ( 時間 )
Phase 1: AFG 構築 : モジュール化により、前
もってクラスライブラリを解析しておくことが
できる
サンプルプログラムに対するエイリアス解析に
おいて、クラスライブラリ全体を再解析する必
要はない
プログラム サンプルプログラム
[sec]
関連するクラスライブラ
リ [sec]
TextEditor
0.001
100
WeirdX
14
101
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University35
考察
(2/3)
Phase 2: AFG によるエイリアス計算 : オンデマ
ンド解析を採用しているため、メソッド間のエ
イリアス解析はその都度行う必要があるが、そ
のコストは十分に小さい
プログラム [ms]
TextEditor
0.65
WeirdX
0.29
ANTLR
0.17
DynamicJava 0.07
考察
(3/3)
解析精度 ( エイリアス集合の平均要素数 )
既存手法 : インスタンスを区別しない解析
提案手法 : インスタンスを区別した解析
提案手法による解析精度の向上を確認
プログラム
区別する
[ 個 ]
区別しない
[ 個 ]
TextEditor
4.42
8.31
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University37
