オブジェクト指向プログラムにおける エイリアス解析について 大畑 文明 井上 克郎 大阪大学大学院 基礎工学研究科 2000/03/09 第126回 ソフトウェア工学研究会

発表内容 研究の背景 既存の手法の問題点 提案「Alias Flow Graph(AFG)によるエイリアス解析」 オブジェクト指向言語 既存の手法の問題点 提案「Alias Flow Graph(AFG)によるエイリアス解析」 AFGの構築 / AFGによるエイリアス計算 ポインタ変数によるエイリアス 実現「Javaエイリアス解析ツール」 評価 まとめ と 今後の課題 2000/03/09 第126回 ソフトウェア工学研究会

エイリアス (引数の参照渡し・参照変数・ポインタを介した間接参照などで生じる，)同じメモリ領域を指す可能性のある式間の同値関係 参照変数 インスタンス生成式 class Manager extends Employee { Manager(String n, int s) { super(n, s); } void manage(Employee e) { e.set_boss(this); e.add_salary(50); class Office { public static void main(String args[]) { Employee A = new Employee("Mr.A", 700); Manager B = new Manager("Mr.B", 850); B.manage(A); A.print(); B.print(); } 「エイリアス指定」 2000/03/09 第126回 ソフトウェア工学研究会

エイリアス情報の利用 プログラム依存関係解析(プログラムスライス) コンパイラ最適化 プログラム理解 プログラムスライス ⇔ プログラム中のある文のある変数に着目し，その変数に直接/間接的に依存関係のある部分を抽出したもの データ依存関係の抽出 コンパイラ最適化 冗長な命令の削除 仮想関数呼び出し/関数へのポインタの排除 プログラム理解 エイリアス関係の表示による特定オブジェクトの情報抽出(型, メソッド, …) 2000/03/09 第126回 ソフトウェア工学研究会

エイリアス計算手順 到達エイリアス集合(Reaching Alias, RA)を利用 RA(s) ⇔ 文sに到達可能なエイリアス組の集合 プログラム実行経路をたどりながら，順次計算 文 到達エイリアス集合 RA(s) 1 Φ 2 {a, (1, new Integer)} 3 {a, (1, new Integer)}, {b, (2, new Integer)} 4 {c, b, (2, new Integer)} 5 6 {c, a, (1, new Integer)}, Integer a, b, c; 1: a = new Integer(1); 2: b = new Integer(2); 3: c = b; 4: System.out.println(c); 5: c = a; 6: System.out.println(c); 2000/03/09 第126回 ソフトウェア工学研究会

オブジェクト指向(OO)言語 オブジェクト指向(Object-Oriented, OO)言語 オブジェクト指向特有の概念 Java C++ … オブジェクト指向特有の概念 クラス(Class) / オブジェクト(Object) 属性(Attribute) / メソッド(Method) 継承(Inheritance) 動的束縛(Dynamic Binding) 2000/03/09 第126回 ソフトウェア工学研究会

問題点 エイリアス解析共通の問題 OOプログラムにおけるエイリアス解析特有の問題 1) 到達エイリアス(RA)集合に依存した解析 プログラムのフローに従って解析をすすめるため，通常プログラムの一部を変更しても全体を再解析する必要がある． OOプログラムにおけるエイリアス解析特有の問題 2) 解析結果の再利用が考慮されていない 再利用性を持つOOプログラムでは，モジュール(クラス/メソッド)単位でエイリアス情報を保持し再利用可能にすることで，解析コストの削減が期待できる．また，要求に応じたエイリアス解析にも有効． 3) インスタンス属性の取り扱いコストが大きい インスタンス内部のエイリアス情報を同一クラスのインスタンスで共有する場合，正確な解析結果が期待できない．すべてを区別する場合，多くのコストが必要となる． 2000/03/09 第126回 ソフトウェア工学研究会

研究の目的 本研究では，エイリアスフローグラフ(AFG)による，OOプログラムに対するエイリアス解析手法を提案する 問題点への対処 1) RA集合は，AFG構築のためのクラス/メソッド内でのエイリアス解析でのみ利用される．エイリアス計算はグラフの到達問題に置き換えられる． 2) AFGはクラス/メソッド単位で構築され，自身/依存するクラス/メソッドが変更されない限り，再利用可能． 3) AFGはすべてのインスタンスに共通なエイリアス関係のみ持ち，インスタンス独自のエイリアス関係は，エイリアス計算時に導出． 2000/03/09 第126回 ソフトウェア工学研究会

AFGによるエイリアス解析手法 Phase 1: AFGの構築 ⇔ RA集合による直接のエイリアス関係の導出 Phase 2: メソッド呼び出しグラフ(MFG)の構築 Phase 3: AFG + MFGによるエイリアス計算 ⇔ グラフの到達問題 class Test { Calc a, b; Integer c; Test() { a = new Calc(); b = new Calc(); a.inc(); b.add(1); c = b.result(); } 2000/03/09 第126回 ソフトウェア工学研究会

AFG特殊節点 ⇔ メソッド引数/メソッド戻り値/属性 Phase 1: AFG構築 AFG標準節点 ⇔ オブジェクトへの参照 インスタンス生成式 参照変数 ポインタ変数による間接参照式 AFG特殊節点 ⇔ メソッド引数/メソッド戻り値/属性 AFG辺 ⇔ 2節点間の(代入文/引数渡し/同一変数の参照 などによる)直接のエイリアス関係 ((1, new Integer), (1, a)) ((1, a), (3, a)) ((3, a), (3, b)) ((3, b), (4, b)) ((4, b), (4, c)) 1: Integer a = new Integer(1); 2: Integer b, c; 3: b = a; 4: c = b; 2000/03/09 第126回 ソフトウェア工学研究会

Phase 1: AFG構築(続き) AFG ⇔ AFG節点/AFG辺により構築 メソッド → メソッドAFG クラス → クラスAFG public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i); } 2000/03/09 第126回 ソフトウェア工学研究会

メソッド呼び出しグラフ(Method Flow Graph, MFG) Phase 2: MFG構築 メソッド呼び出しグラフ(Method Flow Graph, MFG) 各クラスのメソッド呼び出し関係を有向グラフで表現 エイリアス計算時に利用 継承メソッドに留意し構築 A::p A::r A::q Aクラス class A { public void p() { q();} public void q() { r();} public void r() {} } class B extends A { public void q() { s();} public void s() {} B::s B::q B::p(A::p) Bクラス A::q 2000/03/09 第126回 ソフトウェア工学研究会

Phase 3: AFGによるエイリアス計算 単純式x … 例: a, b, c, new Calc() Step 1: グラフ到達問題(AFG + MFG) 限定式x.y … 例: b.result() Step 1: (インスタンス)xに関するエイリアス計算 Step 2: X に関する情報の抽出 (エイリアス集合をX) Step 3: yに関するエイリアス計算 public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i); } class Test { Calc a = new Calc(); Calc b = new Calc(); Integer c; Test() { a.inc(); b.add(1); c = b.result(); }

Phase 3: AFGによるエイリア…(続き) 例: 限定式b.result() Step 1: bに関するエイリアス計算(エイリアス集合をB) Step 2: B に関する情報の抽出 型: Calcクラス メソッド: Calc::Calc(), Calc::add(), Calc::result() …Object-Context(B) Step 3: result()に関するエイリアス計算 public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i); } class Test { Calc a = new Calc(); Calc b = new Calc(); Integer c; Test() { a.inc(); b.add(1); c = b.result(); }

オブジェクトコンテキスト Object-Context(A) ⇔ エイリアス集合A に属するオブジェクトの，呼び出されうるメソッド Flow-Insensitive …メソッド呼び出し順を考慮しない 例: {Calc::Calc(), Calc::add(), Calc::result()} Flow-Sensitive …メソッド呼び出し順を考慮する 例: Calc::Calc()→Calc::add()→Calc::result() public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i); } public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i); } Flow-Insensitive Flow-Sensitive

ポインタ変数によるエイリアス(1/3) ポインタ変数を持つOO言語(C++など) 間接(*)演算子 …被演算子が指すオブジェクト/関数 アドレス(&)演算子 …被演算子のアドレス Phase 1: AFGの構築 AFG節点 ⇔ アドレス AFG辺 ⇔ 2節点間 のポインタ間接による 直接のエイリアス関 係 ((1, &a), (1, b)) ((1, b), (2, b)) ((2, &b), (2, c)) ((1, b), (3, b)) ((3, &b), (3, d)) ((2, c), (4, c)) ((4, &a), (4, *c)) ((3, d), (5, d)) ((5, &e), (5, *d)) ((1, b), (6, b)) int a = 0; int e = 0; int *b; int **c, **d; 1: b = &a; 2: c = &b; 3: d = &b; 4: *c = &a; 5: *d = &e; 6: printf(“%d \n”, **d); 2000/03/09 第126回 ソフトウェア工学研究会

ポインタ変数によるエイリアス(2/3) Phase 3: AFGによるエイリアス計算 演算子なし x 間接演算子あり *x Step 1: グラフ到達問題 間接演算子あり *x Step 1: xに関するエイリアス計算(エイリアス集合をX) Step 2: {y|&y∈X }∪{*y|y∈X }に関するエイリアス計算 アドレス演算子あり &x Step 2: {y|*y∈X }∪{&y|y∈X }に関するエイリアス計算 2000/03/09 第126回 ソフトウェア工学研究会

ポインタ変数によるエイリアス(3/3) 例: 2階の間接演算子あり **d Phase 1: 「d」 int a = 0; int e = 0; int *b; int **c; int **d; 1: b = &a; 2: c = &b; 3: d = &b; 4: *c = &a; 5: *d = &e; 6: printf(“%d \n”, **d); Phase 1: 「d」 Phase 2: 「*d」 Phase 3: 「**d」 int a = 0; int e = 0; int *b; int **c; int **d; 1: b = &a; 2: c = &b; 3: d = &b; 4: *c = &a; 5: *d = &e; 6: printf(“%d \n”, **d); int a = 0; int e = 0; int *b; int **c; int **d; 1: b = &a; 2: c = &b; 3: d = &b; 4: *c = &a; 5: *d = &e; 6: printf(“%d \n”, **d); int a = 0; int e = 0; int *b; int **c; int **d; 1: b = &a; 2: c = &b; 3: d = &b; 4: *c = &a; 5: *d = &e; 6: printf(“%d \n”, **d); 2000/03/09 第126回 ソフトウェア工学研究会

実現(Javaエイリアス解析ライブラリ) C++で記述 libantlr …構文解析 libjavamm …意味解析 libAFG …AFG構築 アルゴリズム: Flow-Insensitive Object-Context 2000/03/09 第126回 ソフトウェア工学研究会

実現(Javaエイリアス表示ツール) C++で記述 GTK--(Gtk+)を利用 テキストウインドウ ツリーウインドウ 2000/03/09 第126回 ソフトウェア工学研究会

評価(1/4) 対象プログラム インターネット上で公開されている，Javaで記述されたソフトウェアを使用 ソフトウェア自身 …新規モジュール ソフトウェアが利用する，JDK付属クラスライブラリ …再利用可能モジュール 新規 再利用可能(JDK) プログラム ファイル 行(コメント無) 概要 TextEditor 1 915 803 115,802 テキストエディタ WeirdX 47 16,703 815 115,977 Xサーバ ANTLR 129 18,775 267 33,847 構文解析生成器 DynamicJava 242 32,037 825 119,564 Javaインタプリタ 2000/03/09 第126回 ソフトウェア工学研究会

評価(2/4) 解析結果のモジュール化による効率化 再利用可能モジュール(JDK付属クラスライブラリ)を解析後，新規モジュール(ソフトウェア自身)を解析する時間 再利用可能・新規すべてのモジュールの解析時間 新規[ms] 新規 + 再利用可能[ms] TextEditor - 99.980 WeirdX 14,220 114,760 ANTLR 12,830 36,310 DynamicJava 56,260 166,410 2000/03/09 第126回 ソフトウェア工学研究会

評価(3/4) AFGによるエイリアス計算のオーバーヘッド 既存手法 AFGによるエイリアス解析手法 到達エイリアス集合によるエイリアス解析のため，すべてのエイリアス関係が抽出されている AFGによるエイリアス解析手法 到達エイリアス集合によるAFGの構築(部分的なエイリアス関係のみ抽出されている) AFGによるエイリアス計算 プログラム 計算対象クラス 平均計算時間[ms] エイリアス 平均 最小 最大 TextEditor test.MyTextArea 0.65 4.42 1 24 WeirdX com.jcraft.weirdx.Client 0.29 15.37 46 ANTLR antlr.MakeGrammer 0.17 5.94 18 DynamicJava koala.dynamicjava.interpreter.TypeChecker 0.07 9.16 37 2000/03/09 第126回 ソフトウェア工学研究会

評価(4/4) 同一クラスのインスタンス間でのエイリアス情報共有による正確性低下 エイリアスをインスタンス独立に解析(非共有) エイリアスを非独立に解析(共有) エイリアス プログラム 計算対象クラス 非共有 共有 平均 最小 最大 TextEditor test.MyTextArea 4.42 1 24 8.31 30 WeirdX com.jcraft.weirdx.Client 15.37 46 24.54 47 ANTLR antlr.MakeGrammer 5.94 18 18.77 76 DynamicJava koala.dynamicjava.interpreter.TypeChecker 9.16 37 17.19 105 Debian/GNU Linux on PentiumIII-667MHz 512MB 2000/03/09 第126回 ソフトウェア工学研究会

まとめ と 今後の課題 まとめ エイリアスフローグラフによる，正確性・再利用を考慮したオブジェクト指向プログラムにおけるエイリアス解析手法を提案した 提案手法をJavaを対象とするエイリアス解析ツールとして実装を行いその有効性を評価した 今後の課題 Flow-Sensitive Object-Contextの実現 スレッド/例外処理への対応 既存手法との比較 2000/03/09 第126回 ソフトウェア工学研究会