オブジェクト指向プログラムにおける エイリアス解析・視覚化ツールの試作 近藤 和弘 大畑 文明 井上 克郎 大阪大学大学院 基礎工学研究科 2000/07/14 ソフトウェアサイエンス研究会

発表内容 OOプログラムに対するエイリアス解析手法の提案 OOプログラムに対するエイリアス解析手法の提案 既存の手法の問題点と対処法 Alias Flow Graph (AFG) によるエイリアス解析手法 AFG構築アルゴリズム AFGによるエイリアス計算 Javaエイリアス解析・視覚化ツール ツール設計 テキストウインドウ エイリアスツリーウインドウ ウインドウ間の連係 ツール概要と使用例 2000/07/14 ソフトウェアサイエンス研究会

エイリアス (引数の参照渡し・参照変数・ポインタを介した間接参照などで生じる, )同じメモリ領域を指す可能性のある式間の同値関係 参照変数 インスタンス生成式 class Employee { … … } 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/07/14 ソフトウェアサイエンス研究会

エイリアス情報の利用 プログラム依存関係解析(プログラムスライス) コンパイラ最適化 デバッグ, プログラム理解 プログラムスライス ⇔ プログラム中のある文のある変数に着目し, その変数に 直接/間接的に依存関係のある部分を抽出したもの データ依存関係の抽出 readln(a); readln(b); max := a; min := b; if a < b then begin max := b; min := a; end; writeln(‘Max: ’, max, ‘\n’); writeln(‘Min: ’, min, ‘\n’); コンパイラ最適化 冗長な命令の削除 仮想関数呼び出し/関数へのポインタの排除 デバッグ, プログラム理解 エイリアス関係の表示による特定オブジェクトの情報抽出(型, メソッド, …) 2000/07/14 ソフトウェアサイエンス研究会

エイリアス情報の利用例 デバッグへの利用 特定のオブジェクトに対するエイリアスの表示 実行結果 % java Office Mr.A Salary : 700 Mr.B Salary : 900 % java Office % java Office Mr.A Salary : 750 Mr.B Salary : 850 class Employee { … … } 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(); } add_salary(50); 2000/07/14 ソフトウェアサイエンス研究会

エイリアス計算手順 到達エイリアス集合(Reaching Alias, RA)を利用 RA(s) ⇔ 文sに到達可能なエイリアス組の集合 プログラム実行経路をたどりながら, 順次計算 {(5, c), (5, a), (1, a), (1, new Integer)}, {(2, b), (3, b), (2, new Integer)} 6 5 {(1, a), (1, new Integer)}, {(3, c), (2, b), (3, b), (2, new Integer)} 4 {(2, b), (2, new Integer)} 3 {(1, a), (1, new Integer)} 2 Φ 1 到達エイリアス集合 RA(s) 文 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); {(1, a), (1, new Integer)}, {(4, c), (3, c), (2, b), (3, b), (2, new Integer)} 2000/07/14 ソフトウェアサイエンス研究会

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

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

AFGによるエイリアス解析手法 ⇔ RA集合による直接のエイリアス関係の導出 ⇔ グラフの到達問題 Phase 1: AFGの構築 class Test { Calc a, b; Integer c; Test() { a = new Calc(); b = new Calc(); a.inc(); b.add(1); c = b.result(); } 2000/07/14 ソフトウェアサイエンス研究会

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

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); } AFG特殊節点（インスタンス属性） AFG標準節点（参照変数） メソッドAFG AFG特殊節点（メソッド戻り値） 2000/07/14 ソフトウェアサイエンス研究会

Phase 2: AFGによるエイリアス計算 単純式x … 例: a, b, c, new Calc() Step 1: グラフ到達問題 限定式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(); } 2000/07/14 ソフトウェアサイエンス研究会

Phase 2: AFGによるエイリア…(続き) 例: 限定式b.result() Step 1: bに関するエイリアス計算(エイリアス集合をB ) Step 2: B に関する情報の抽出 型: Calcクラス メソッド: Calc::Calc(), Calc::add(), Calc::result() 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(); } 2000/07/14 ソフトウェアサイエンス研究会

Javaエイリアス解析ライブラリ ライブラリ構成 開発環境 libantlr …構文解析 libjavamm …意味解析 libAFG …AFG構築 サイズ：17,000[自動生成] + 10,000行 開発環境 OS : Debian GNU/Linux 言語 : C++(C) 2000/07/14 ソフトウェアサイエンス研究会

発表内容 OOプログラムに対するエイリアス解析手法の提案 Javaエイリアス解析・視覚化ツール 既存の手法の問題点と対処法 Alias Flow Graph (AFG) によるエイリアス解析手法 AFG構築アルゴリズム AFGによるエイリアス計算 Javaエイリアス解析・視覚化ツール ツール設計 テキストウインドウ エイリアスツリーウインドウ ウインドウ間の連係 ツール概要と使用例 2000/07/14 ソフトウェアサイエンス研究会

エイリアス集合全体像の把握と理解の簡易化 ツール設計 情報視覚化において必要な技法† 必要なもののみ表示する技法 全体と詳細を同時に見る方法 本研究においての着目点 エイリアス集合全体像の把握と理解の簡易化 エイリアス集合の視覚的な表示 テキストウインドウ ソースコードの強調表示 エイリアス部分 非エイリアス部分 エイリアスツリーウインドウ エイリアスツリーによる表示 エイリアスの存在する クラス・メソッドの把握 各エイリアスの詳細情報 ウインドウ間の連係 全体像とソースコードの対応 視点の移動と拡大表示 エイリアスツリーからの ファイルオープン †増井俊之, “情報視覚化の最近の研究動向, ” 電子情報通信学会第９回データ工学ワークショップ, 1998． 2000/07/14 ソフトウェアサイエンス研究会

テキストウインドウ ソースコード → エイリアス部分, 非エイリアス部分 エイリアス部分 非エイリアス部分 着目点：エイリアス集合の視覚的な表示 ソースコード → エイリアス部分, 非エイリアス部分 エイリアス部分 着目したい部分 強調表示：フォント, 背景色（エイリアス別） 非エイリアス部分 ソース中の割合大 目的に応じた表示方法を選択 「縮小（可変・線分化）, 継承」 の三種類の表示方法を実装 2000/07/14 ソフトウェアサイエンス研究会

非エイリアス部分の表示：縮小 縮小：可変 縮小：線分化 エイリアスからの距離でサイズを変更 制御構造を把握しつつエイリアス部分に注目可 行を線分化して表示（インデント, 長さは維持） エイリアスのみに着目したい場合に有用 可変 線分化 2000/07/14 ソフトウェアサイエンス研究会

非エイリアス部分の表示：継承 継承 エイリアス表示前のソースコードの状態を継承 通常時に使用 → ソース全体を表示 縮小後に使用 → 縮小との和集合を表示 継承 線分化 継承 2000/07/14 ソフトウェアサイエンス研究会

エイリアスツリーウインドウ エイリアスツリー 情報表示リスト 着目点：エイリアス集合全体像の把握と理解の簡易化 エイリアスの存在するクラス・メソッドを階層表示 情報表示リスト エイリアスなどの詳細情報を表示 エイリアス指定 クラス メソッド エイリアス エイリアスツリー 情報表示リスト 2000/07/14 ソフトウェアサイエンス研究会

ウインドウ間の連係 着目点：全体像とソースコードの対応 テキストウインドウ エイリアスツリーウインドウ エイリアス集合全体像の表示 ソースコード中のエイリアスの表示 テキストウインドウ エイリアスツリーウインドウ 場所情報(ファイル) 場所情報(行) エイリアス集合の区別 背景色の違い カーソル位置 表示ファイル エイリアス ノード ファイル名 行番号 サブツリーの違い 着目対象 ウインドウ間の対応 2000/07/14 ソフトウェアサイエンス研究会

ウインドウ連係の例 Animeter.java 中に存在する imageURL についてのエイリアスを表示させる エイリアスツリーを表示させる エイリアス部分を強調表示 非エイリアス部分を「線分化」で表示 2000/07/14 ソフトウェアサイエンス研究会

ウインドウ連係の例 エイリアスツリーのノードから クラス Hashtable, メソッド put 中の エイリアス一覧を表示させる エイリアス old を選択 old の存在するファイル Hashtable.javaをオープン old の詳細な情報を表示 2000/07/14 ソフトウェアサイエンス研究会

ウインドウ連係の例 Hashtable.java 中の エイリアス部分を強調表示 非エイリアス部分を「線分化」で表示 old が存在する行にカーソルを移動 ウインドウ間の対応完了 old を拡大表示 2000/07/14 ソフトウェアサイエンス研究会

Javaエイリアス解析・視覚化ツール ツール構成 開発環境 図参照 サイズ: 約4,200行 OS : Debian GNU/Linux 言語 : C++(C) GUIライブラリ : GTK--(Gtk+) 2000/07/14 ソフトウェアサイエンス研究会

ツール適用範囲 デバッグ プログラム理解 エイリアス関係の表示によるデバッグ範囲の絞込み (ファイル, クラス, メソッド, …) エイリアス関係の表示によるデバッグ範囲の絞込み (ファイル, クラス, メソッド, …) プログラム理解 エイリアス関係の表示による特定オブジェクトの情報抽出(型, メソッド, …) 現時点ではツールの有効性評価を行っていない デバッグフェーズでのフォールト位置特定を 例として取り上げ, 有効性を検証する 2000/07/14 ソフトウェアサイエンス研究会

ツール使用例 フォールト事例 表計算Javaアプレット SpreadSheet.java (JDK付属サンプルコード, サイズ:約1000行) プログラム実行時に下図のようなフォールトが発生 (表計算の結果が誤っている) 実際にツールを利用して フォールト位置を特定する 2000/07/14 ソフトウェアサイエンス研究会

ツール使用例 非エイリアス部分の線分化により ソースコードの表示領域は10%に縮小 式を格納している変数 formula に ついてのエイリアスを表示させる 表計算式の解析を行うメソッド parseFormula を調べる エイリアスツリーを表示させて エイリアスの全体像を把握 2000/07/14 ソフトウェアサイエンス研究会

ツール使用例 メソッド parseValue の戻り値が 仮引数 formula となっていることが フォールト原因であることがわかる メソッド parseFormula,parseValue に のみエイリアスが存在することがわかる 両メソッド中のエイリアスに注目し エイリアスを含む文(約30行)を調べる 2000/07/14 ソフトウェアサイエンス研究会

ツール使用例 正しくは restformula を返さなければ ならないことを類推し修正する 正しい実行結果が得られる 2000/07/14 ソフトウェアサイエンス研究会

まとめ と 今後の課題 まとめ 本研究では, 我々が提案したオブジェクト指向プログラムに対するエイリアス解析手法を実現した, Javaエイリアス解析・視覚化ツールの試作を行った 本ツールは解析部とＵＩ部で構成され、ＵＩ部ではデバッグ, プログラム理解のために解析結果の視覚化を行う 今後の課題 スライス解析ツールへの発展 ツールの有効性の評価 非エイリアス部分の表示方法の改良 2000/07/14 ソフトウェアサイエンス研究会