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