オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現 大畑 文明 井上研究室 2000/02/22 修士論文発表会 1 エイリアス (引数の参照渡し・参照変数・ポインタを介した間接 参照などで生じる,)同じメモリ領域を指す可能性の ある式間の同値関係 参照変数 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 修士論文発表会 2 エイリアス計算手順 到達エイリアス集合(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)} Integer a, b, c; 4 {(1, a), (1, new Integer)}, 1: a = new Integer(1); 2: b = new Integer(2); {(3, c), (2, b), (3, b), (2, new Integer)} 3: c = b; 5 {(1, a), (1, new Integer)}, 4: System.out.println(c); {(4, c), (3, c), (2, b), (3, b), (2, new 5: c = a; Integer)} 6: System.out.println(c); 6 {(5, c), (4, a), (1, a), (1, new Integer)}, {(2, b), (3, b), (2, new Integer)} 2000/02/22 3 修士論文発表会 問題点 エイリアス解析共通の問題 1) 到達エイリアス(RA)集合に依存した解析 プログラムのフローに従って解析をすすめるため,通常プログラムの 一部を変更しても全体を再解析する必要がある. OOプログラムにおけるエイリアス解析特有の問題 2) 解析結果の再利用が考慮されていない 再利用性を持つOOプログラムでは,モジュール(クラス/メソッド)単 位でエイリアス情報を保持し再利用可能にすることで,解析コスト の削減が期待できる.また,要求に応じたエイリアス解析にも有効. 3) インスタンス属性の取り扱いコストが大きい インスタンス内部のエイリアス情報を同一クラスのインスタンスで共 有する場合,正確な解析結果が期待できない.すべてを区別す る場合,多くのコストが必要となる. 2000/02/22 修士論文発表会 4 研究の目的 本研究では,エイリアスフローグラフ(AFG)による,OO プログラムに対するエイリアス解析手法を提案する 問題点への対処 1) RA集合は,AFG構築のためのメソッド(クラス)内でのエイ リアス解析でのみ利用される.エイリアス計算はグラフの到 達問題に置き換えられる. 2) AFGはメソッド(クラス)単位で構築され,自身/依存する メソッド(クラス)が変更されない限り,再利用可能. 3) AFGはすべてのインスタンスに共通なエイリアス関係のみ 持ち,インスタンス独自のエイリアス関係は,エイリアス計 算時に導出. 2000/02/22 修士論文発表会 5 AFGによるエイリアス解析手法 Phase 1: AFGの構築 ⇔ RA集合による直接のエイリアス関係の導出 class Test { Calc a, b; Integer c; Test() { a = new Calc(); b = new Calc(); a.inc(); b.add(1); c = b.result(); } } Phase 2: AFGによるエイリアス計算 ⇔ グラフの到達問題 2000/02/22 修士論文発表会 6 Phase 1: AFG標準節点 ⇔ オブジェクトへの参照 AFG構築 インスタンス生成式 参照変数 ポインタ変数による間接参照式 AFG特殊節点 ⇔ メソッド引数/メソッド戻り値/属性 AFG辺 ⇔ 2節点間の(代入文/引数渡し/同一変 数の参照 などによる)直接のエイリアス関係 1: Integer a = new Integer(1); 2: Integer b, c; 3: b = a; 4: c = b; 2000/02/22 ((1, new Integer), (1, a)) ((1, a), (3, a)) ((3, a), (3, b)) ((3, b), (4, b)) ((4, b), (4, c)) 修士論文発表会 7 Phase 1: AFG構築(続き) AFG ⇔ AFG節点/AFG辺により構築 メソッド → メソッドAFG クラス → クラスAFG public class Calc { Integer i; public Calc() Integer(0); } {i = new public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); } public Integer {return(i); } result() } 2000/02/22 修士論文発表会 8 Phase 2: 単純式x … 例: a, b, c, new Calc() Step 1: AFGによるエイリアス計算 グラフ到達問題 限定式x.y … 例: b.result() Step 1: Step 2: Step 3: (インスタンス)xに関するエイリアス計算 X に関する情報の抽出 (エイリアス集合をX) yに関するエイリアス計算 2000/02/22 public class Calc { Integer i; class Test { public Calc() Calc a = new Calc(); Integer(0); } {i = new Calc b = new public void inc() { Calc(); i = new Integer(i.intValue() + 1); Integer c; } Test() { public void add(int c) { a.inc(); i = new Integer(i.intValue() + c); b.add(1); } c = b.result(); public Integer } {return(i); } result() 9 修士論文発表会 } Phase 2: AFGによるエイリア…(続き) 例: 限定式b.result() bに関するエイリアス計算(エイリアス集合をB ) Step 2: B に関する情報の抽出 型: Calcクラス メソッド: Calc::Calc(), Calc::add(), Calc::result() Step 3: result()に関するエイリアス計算 Step 1: class Test { Calc a = new Calc(); Calc b = new Calc(); Integer c; Test() { a.inc(); b.add(1); c = b.result(); } } 2000/02/22 public class Calc { Integer i; public Calc() Integer(0); } {i = new public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); } public Integer {return(i); } result() } 修士論文発表会 10 本手法の実現(Javaエイリアス解析ツール) Javaエイリアス解析ライブラリ C++で記述 libantlr …構文解析(17,000[自動生成] + 1,200行) libjavamm …意味解析(5,500行) libAFG …AFG構築(3,300行) Javaエイリアス表示ツール C++で記述 Gtk+(GTK--)を利用(4,200行) 2000/02/22 修士論文発表会 11 評価 評価対象プログラム 新規 プログラム 再利用可能(JDK) ファイル 行(コメント無) ファイル 行(コメント無) WeirdX 47 16,703 815 ANTLR 129 18,775 267 DynamicJava 242 32,037 825 概要 115,977 Xサーバ 33,847 構文解析生成器 119,564 Javaインタプリタ 評価1: 解析結果のモジュール化による効率化 2000/02/22 新規[ms] 新規 + 再利用可能[ms] WeirdX 14,220 114,760 ANTLR 12,830 36,310 DynamicJava 56,260 166,410 修士論文発表会 12 評価(続き) 評価2: AFGによるエイリアス計算のオーバーヘッド プログラム 計算対象クラス 平均計算 時間[ms] エイリアス 平均 最小 最大 WeirdX com.jcraft.weirdx.Client 0.29 15.37 1 46 ANTLR antlr.MakeGrammer 0.17 5.94 1 18 0.07 9.16 1 37 DynamicJava koala.dynamicjava.interpreter.TypeChecker 評価3: 同一クラスのインスタンス間でのエイリアス情 報共有による正確性低下 エイリアス プログラム 計算対象クラス 非共有 平均 WeirdX com.jcraft.weirdx.Client ANTLR antlr.MakeGrammer DynamicJava koala.dynamicjava.inter preter.TypeChecker 2000/02/22 共有 最小 最大 平均 最小 最大 15.37 1 46 24.54 1 47 5.94 1 18 18.77 1 76 9.16 1 37 17.19 1 105 Debian/GNU Linux on PentiumIII-667MHz 512MB 13 修士論文発表会 まとめ と 今後の課題 まとめ 本研究では,エイリアスフローグラフによる,正確性・再利 用を考慮したオブジェクト指向プログラムにおけるエイリアス 解析手法を提案した また,提案手法をJavaを対象とするエイリアス解析ツール として実装を行いその有効性を評価した 今後の課題 スレッド/例外処理への対応 AFGデータベースの構築 2000/02/22 修士論文発表会 14 後期課程における研究方針 プログラムスライス プログラム中のある文のある変数に着目し,その変数に直 接/間接的に依存関係のある部分を抽出したもの プログラム中に存在するさまざまな(依存)関係 データ依存関係 制御依存関係(条件節~述部,同期制御,例外,…) 手続き呼び出し関係 エイリアス関係 関係の抽出方法 動的/静的 プログラム実行順を考慮する/考慮しない 2000/02/22 修士論文発表会 15 後期課程における研究方針(続き) プログラムスライスの現状 抽出可能なあらゆる依存関係が1つにまとめられている プログラム中に多種多様な関係が存在 (依存)関係の管理機能の実現 情報の分散生成/管理 ユーザの要求に応じた,いくつかの依存関係の組み合わ せによるスライス計算 および そのガイダンス 依存関係の集約/フィルタリング 2000/02/22 修士論文発表会 16
© Copyright 2024 ExpyDoc