オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現 大畑 文明 井上研究室 2000/02/22 修士論文発表会

エイリアス (引数の参照渡し・参照変数・ポインタを介した間接参照などで生じる，)同じメモリ領域を指す可能性のある式間の同値関係 エイリアス解析結果の利用分野 プログラム依存関係解析/コンパイラ最適化 プログラム理解 インスタンス生成式 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/02/22 修士論文発表会

エイリアス計算手順 到達エイリアス集合(Reaching Alias, RA)を利用 RA(s) ⇔ 文sに到達可能なエイリアス組の集合 プログラム実行経路をたどりながら，順次計算 文 到達エイリアス集合 RA(s) 1 Φ 2 {(1, a), (1, new Integer)} 3 {(1, a), (1, new Integer)}, {(2, b), (2, new Integer)} 4 {(3, c), (2, b), (3, b), (2, new Integer)} 5 {(4, c), (3, c), (2, b), (3, b), (2, new Integer)} 6 {(5, c), (4, a), (1, a), (1, new Integer)}, {(2, b), (3, b), (2, 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/02/22 修士論文発表会

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

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

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/02/22 修士論文発表会

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/02/22 修士論文発表会

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/02/22 修士論文発表会

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/02/22 修士論文発表会

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/02/22 修士論文発表会

本手法の実現(Javaエイリアス解析ツール) C++で記述 libantlr …構文解析(17,000[自動生成] + 1,200行) libjavamm …意味解析(5,500行) libAFG …AFG構築(3,300行) Javaエイリアス表示ツール Gtk+(GTK--)を利用(4,200行) 2000/02/22 修士論文発表会

評価 評価対象プログラム 評価1: 解析結果のモジュール化による効率化 2000/02/22 修士論文発表会 新規 再利用可能(JDK) ファイル 行(コメント無) 概要 WeirdX 47 16,703 815 115,977 Xサーバ ANTLR 129 18,775 267 33,847 構文解析生成器 DynamicJava 242 32,037 825 119,564 Javaインタプリタ 新規[ms] 新規 + 再利用可能[ms] WeirdX 14,220 114,760 ANTLR 12,830 36,310 DynamicJava 56,260 166,410 2000/02/22 修士論文発表会

評価(続き) 評価2: AFGによるエイリアス計算のオーバーヘッド 評価3: 同一クラスのインスタンス間でのエイリアス情報共有による正確性低下 プログラム 計算対象クラス 平均計算時間[ms] エイリアス 平均 最小 最大 WeirdX com.jcraft.weirdx.Client 0.29 15.37 1 46 ANTLR antlr.MakeGrammer 0.17 5.94 18 DynamicJava koala.dynamicjava.interpreter.TypeChecker 0.07 9.16 37 エイリアス プログラム 計算対象クラス 非共有 共有 平均 最小 最大 WeirdX com.jcraft.weirdx.Client 15.37 1 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/02/22 修士論文発表会

まとめ と 今後の課題 まとめ 本研究では，エイリアスフローグラフによる，正確性・再利用を考慮したオブジェクト指向プログラムにおけるエイリアス解析手法を提案した また，提案手法をJavaを対象とするエイリアス解析ツールとして実装を行いその有効性を評価した 今後の課題 スレッド/例外処理への対応 AFGデータベースの構築 2000/02/22 修士論文発表会

後期課程における研究方針 プログラムスライス プログラム中に存在するさまざまな(依存)関係 関係の抽出方法 プログラム中のある文のある変数に着目し，その変数に直接/間接的に依存関係のある部分を抽出したもの プログラム中に存在するさまざまな(依存)関係 データ依存関係 制御依存関係(条件節～述部，同期制御，例外，…) 手続き呼び出し関係 エイリアス関係 関係の抽出方法 動的/静的 プログラム実行順を考慮する/考慮しない 2000/02/22 修士論文発表会

後期課程における研究方針(続き) プログラムスライスの現状 プログラム中に多種多様な関係が存在 (依存)関係の管理機能の実現 抽出可能なあらゆる依存関係が1つにまとめられている プログラム中に多種多様な関係が存在 (依存)関係の管理機能の実現 情報の分散生成/管理 ユーザの要求に応じた，いくつかの依存関係の組み合わせによるスライス計算 および そのガイダンス 依存関係の集約/フィルタリング 2000/02/22 修士論文発表会