JAVAバイトコードにおける データ依存解析手法の提案と実装 ‡ 誉田 謙二† 大畑 文明† 井上 克郎†‡ † 大阪大学 大学院基礎工学研究科 奈良先端科学技術大学院大学 情報科学研究科 発表内容 背景 JAVAバイトコードにおけるデータ依存 データ依存解析手法の提案 提案手法の実現 まとめと今後の課題 2000/09/20 ソフトウェア科学会全国大会 背景(1/2) プログラム文間の依存関係 制御依存関係 データ依存関係 条件節～述部(述部の実行が条件節に依存) 同一変数の定義～参照(データフローによる依存) 依存関係解析の利用 プログラム理解 プログラムデバッグ プログラム保守 2000/09/20 ソフトウェア科学会全国大会 a:=5; b:=3; if b>0 then c:=a else d:=b; 背景(2/2) 既に提案されている依存関係解析手法 高級言語(C, C++, etc…)のソースコード 3番地コード を対象 JAVAバイトコードのような、スタックの存在が前提 となる言語に対するデータ依存解析手法は提案 されていない 2000/09/20 ソフトウェア科学会全国大会 JAVAバイトコードにおけるデータ依存 クラスファイル JAVAバイトコード JAVAバイトコードにおけるデータ依存関係 ローカル変数に関するデータ依存 フィールドに関するデータ依存 スタックに関するデータ依存 2000/09/20 ソフトウェア科学会全国大会 クラスファイル ソースプログラムはJAVAコンパイラにより、クラスファ イルに変換される クラスファイル クラス単位に生成 JAVAバイトコードによる命令列などにより構成 class A JAVAコンパイラ class A class B class B 2000/09/20 ソフトウェア科学会全国大会 JAVAバイトコード クラスファイルを構成する命令列 JAVAバーチャルマシン（JVM）への入力 約200種類の命令で構成される 命令 動作 iconst_n 定数ｎをスタックに積む iload_n ローカル変数ｎの値をスタックに積む istore_n スタックトップの値をローカル変数ｎに格納する getfield フィールドの値をスタックに積む putfield スタックトップの値をフィールドに格納する iadd スタックトップの2つの値の加算を行う if_icmplt スタックトップの2つの値の大小により分岐を行う 2000/09/20 ソフトウェア科学会全国大会 JAVAバイトコードの実行例 0 iconst_4 1 23 ローカル変数 0 iload_1 1 4 スタック 23 23 ローカル変数 4 スタック 0 iadd 1 23 ローカル変数 2000/09/20 ソフトウェア科学会全国大会 27 スタック JAVAバイトコードにおけるデータ依存関係 データの格納 ローカル変数 / フィールド スタック ある値に対応する記憶領域が命令により変化する(push / pop演算の存在) iconst_n iload_n iadd etc… 命令に応じてその位置を追跡する必要がある 2000/09/20 ソフトウェア科学会全国大会 スタックに関するデータ依存 スタック上のある値v が参照されるとき、v を定義 した命令s から参照する命令t にスタックに関する データ依存関係が存在する s : iconst_v , t : istore_1 iconst_v 0 v 1 istore_1 2000/09/20 ローカル変数 ソフトウェア科学会全国大会 スタック スタックに関するデータ依存 スタック上のある値v が参照されるとき、v を定義 した命令s から参照する命令t にスタックに関する データ依存関係が存在する s : iconst_v , t : istore_1 iconst_v 0 v 1 istore_1 2000/09/20 ローカル変数 ソフトウェア科学会全国大会 スタック スタックに関するデータ依存 スタック上のある値v が参照されるとき、v を定義 した命令s から参照する命令t にスタックに関する データ依存関係が存在する s : iconst_v , t : istore_1 iconst_v 0 1 istore_1 2000/09/20 v ローカル変数 ソフトウェア科学会全国大会 スタック ローカル変数に関するデータ依存 あるローカル変数x の値v が参照されるとき、v を 定義した命令s から参照する命令t にx に関す るデータ依存関係が存在する x : 1, s : istore_1, t : iload_1 istore_1 v 0 1 v ローカル変数 iload_1 2000/09/20 0 1 スタック v v ローカル変数 ソフトウェア科学会全国大会 スタック フィールドに関するデータ依存 あるフィールドx の値v が参照されるとき、v を定 義した命令s から参照する命令t にx に関する データ依存関係が存在する s : putfield Point/x I, t : getfield Point/x I putfield Point/x I x v フィールド getfield Point/x I x v フィールド 2000/09/20 ソフトウェア科学会全国大会 v スタック v スタック データ依存解析手法の提案 前提 解析アルゴリズム 制御フローグラフの構築 データ依存関係の抽出 解析フレームの準備 データ依存関係の抽出 2000/09/20 ソフトウェア科学会全国大会 前提 提案するアルゴリズム 静的解析(存在しうるすべての経路に対して解析) 単一スレッドを対象 入力: JAVAバイトコード 出力: データ依存関係を表すグラフ 節点: JAVAバイトコードの命令 辺: 命令間に起こりうる制御の移動、 命令間に存在するデータ依存関係 2000/09/20 ソフトウェア科学会全国大会 解析アルゴリズム iload_0 iconst_3 Step1:制御フローグラフの構築 制御フローグラフ (Control Flow Graph,CFG) 節点：JAVAバイトコードの命令 辺：命令間に起こりうる制御の移動 if_icmplt L3 iconst_3 L3 iconst_4 goto L5 L5 istore_0 iload_0 ireturn 2000/09/20 ソフトウェア科学会全国大会 解析アルゴリズム iload_0 iconst_3 Step1:制御フローグラフの構築 制御フローグラフ (Control Flow Graph,CFG) 節点：JAVAバイトコードの命令 辺：命令間に起こりうる制御の移動 if_icmplt L3 iconst_3 Step2：データ依存関係の抽出 CFGにデータ依存辺を追加 L3 iconst_4 goto L5 L5 istore_0 iload_0 ireturn 2000/09/20 ソフトウェア科学会全国大会 Step1: 制御フローグラフの構築 iload_0 Phase1: 命令を抽出し、CFG節点を作成 Phase2: 各命令sについて iconst_3 if_icmplt L3 L3 iconst_4 iconst_3 命令sの次に実行される可能性 のある命令ｔを求める s~t間にCFG辺を引く goto L5 L5 istore_0 iload_0 ireturn 2000/09/20 ソフトウェア科学会全国大会 Step2:データ依存関係の抽出 (1/3) Phase1：解析フレームの準備 解析フレーム メソッド内で各ローカル変数・フィー ルド・スタック上の値がどの命令で 定義されたかを保持 変数名とその値を最後に定義した 命令の番号の対の集合 2000/09/20 ソフトウェア科学会全国大会 stack_0 undef stack_1 undef stack_2 5 local_0 3 local_1 4 Step2:データ依存関係の抽出 (2/3) 各メソッドの処理に必要なスタックサイズ・ローカル変 数の個数はコンパイラにより計算される 解析フレームの例 1: 2: 3: 4: 5: 6: 2000/09/20 iload_0 iconst_9 iadd istore_0 iload_0 ireturn local_0 4 stack_0 undef stack_1 ソフトウェア科学会全国大会 5 Step2:データ依存関係の抽出 (3/3) Phase2: データ依存関係の抽出 CFG辺をたどりながら、各節点を解析 1. 各節点が表す命令に応じて、解析フレームを更新 2. 3. 逐次実行 分岐 データ依存関係が抽出された場合、CFGにデータ依存辺 を追加 更新された解析フレームを用い、この節点を始点とするす べてのCFG辺をたどり次の節点に移動し、解析を続ける 2000/09/20 ソフトウェア科学会全国大会 逐次実行 解析フレームの更新 / データ依存辺の追加 1: iconst_3 0 1 3 ローカル変数 スタック local_0 undef local_1 undef stack_0 undef 2: istore_1 2000/09/20 ソフトウェア科学会全国大会 逐次実行 解析フレームの更新 / データ依存辺の追加 1: iconst_3 local_0 undef 3 local_1 undef スタック stack_0 1 0 1 ローカル変数 2: istore_1 2000/09/20 ソフトウェア科学会全国大会 逐次実行 解析フレームの更新 / データ依存辺の追加 1: iconst_3 local_0 undef 3 local_1 undef スタック stack_0 1 0 1 ローカル変数 2: istore_1 2000/09/20 ソフトウェア科学会全国大会 逐次実行 解析フレームの更新 / データ依存辺の追加 1: iconst_3 0 1 3 ローカル変数 スタック local_0 undef local_1 undef stack_0 1 2: istore_1 2000/09/20 ソフトウェア科学会全国大会 逐次実行 解析フレームの更新 / データ依存辺の追加 1: iconst_3 0 1 3 ローカル変数 スタック local_0 undef local_1 2 stack_0 undef 2: istore_1 2000/09/20 ソフトウェア科学会全国大会 分岐 解析フレームの更新 / データ依存辺の追加 5: iconst_3 local_0 2 stack_0 6 stack_1 5 6: iload_0 1 0 1 ローカル変数 7: if_icmplt L4 2000/09/20 ソフトウェア科学会全国大会 3 スタック 分岐 解析フレームの更新 / データ依存辺の追加 5: iconst_3 local_0 2 stack_0 undef 6: iload_0 stack_1 undef 0 1 ローカル変数 7: if_icmplt L4 2000/09/20 ソフトウェア科学会全国大会 スタック 分岐 解析フレームの更新 / データ依存辺の追加 解析フレームの複製 5: iconst_3 6: iload_0 0 1 ローカル変数 7: if_icmplt L4 local_0 2 local_0 2 stack_0 undef stack_0 undef stack_1 undef stack_1 undef 2000/09/20 ソフトウェア科学会全国大会 スタック 繰り返し(1/2) 繰り返しの存在による解析のループ CFGにループが存在する場合、解析がループに陥る L1 iconst_2 等価な解析が無限に繰り返され、 iload_0 解析が終了しない if_icmplt L3 L3 iload_0 等価な解析 ⇔ 等価な解析フレームによる解析 2000/09/20 ソフトウェア科学会全国大会 iconst_3 iadd ireturn goto L1 istore_0 ineg iload_0 繰り返し(2/2) 等価な解析フレームによる解析を回避 CFGの合流節点に、処理開始時の解析フレームの 履歴を保持させる 等価な解析フレームが既に履歴に含まれている場合、 解析を停止する iload_0 2000/09/20 local_0 undef local_0 undef local_1 undef local_1 6 stack_0 undef stack_0 undef ソフトウェア科学会全国大会 ・・・ 提案手法の実現 (1/2) JAVAバイトコードをJasmin形式に変換し、解析 構文解析、CFG構築、データ依存関係解析 データ依存解析ツール JAVAバイトコード 構文解析、 Jasmin Translator CFG構築 JAVAバイトコード （Jasmin形式） 2000/09/20 データ依存辺を 追加したCFG CFG 1000 101101 0010111 1011110 1101001 データ依存 関係解析 ソフトウェア科学会全国大会 提案手法の実現 (2/2) L3 iconst_2 iload_0 if_icmple L5 iload_0 ineg istore_0 goto L3 L5 iload_0 ireturn L3 iconst_2 データ依存 解析ツール goto L3 iload_0 istore_0 if_icmplt L5 L5 iload_0 ineg iload_0 ireturn ローカル変数に関するデータ依存辺 スタックに関するデータ依存辺 制御依存辺 2000/09/20 ソフトウェア科学会全国大会 まとめと今後の課題 まとめ 本研究では、JAVAバイトコードに対するデータ依存 関係を定義し、その抽出手法を提案した また、提案手法を採用したツールの試作を行い、そ の動作を確認した 今後の課題 スレッドへの対応 解析の効率化 JAVAバイトコードに対するプログラムスライスの抽出 2000/09/20 ソフトウェア科学会全国大会
© Copyright 2024 ExpyDoc
