JAVAバイトコードにおける データ依存解析手法の提案と実装

Presentation on theme: "JAVAバイトコードにおける データ依存解析手法の提案と実装"— Presentation transcript:

1 JAVAバイトコードにおける データ依存解析手法の提案と実装
誉田 謙二† 大畑 文明† 井上 克郎†‡ †　大阪大学 大学院基礎工学研究科 ‡　奈良先端科学技術大学院大学 情報科学研究科

2 発表内容 背景 JAVAバイトコードにおけるデータ依存 データ依存解析手法の提案 提案手法の実現 まとめと今後の課題 2000/09/20
ソフトウェア科学会全国大会

3 背景(1/2) プログラム文間の依存関係 依存関係解析の利用 制御依存関係 データ依存関係 プログラム理解 プログラムデバッグ
条件節～述部(述部の実行が条件節に依存)　 データ依存関係 同一変数の定義～参照(データフローによる依存) 依存関係解析の利用 プログラム理解 プログラムデバッグ プログラム保守 a:=5; b:=3; if b>0 then c:=a else d:=b; 2000/09/20 ソフトウェア科学会全国大会

4 背景(2/2) 既に提案されている依存関係解析手法 を対象
高級言語(C, C++, etc…)のソースコード 3番地コード を対象 JAVAバイトコードのような、スタックの存在が前提となる言語に対するデータ依存解析手法は提案されていない 2000/09/20 ソフトウェア科学会全国大会

5 JAVAバイトコードにおけるデータ依存 クラスファイル JAVAバイトコード JAVAバイトコードにおけるデータ依存関係
ローカル変数に関するデータ依存 フィールドに関するデータ依存 スタックに関するデータ依存 2000/09/20 ソフトウェア科学会全国大会

6 クラスファイル ソースプログラムはJAVAコンパイラにより、クラスファイルに変換される クラスファイル クラス単位に生成
class A class B 2000/09/20 ソフトウェア科学会全国大会

7 JAVAバイトコード クラスファイルを構成する命令列 JAVAバーチャルマシン（JVM）への入力 約200種類の命令で構成される 命令 動作
iconst_n 定数ｎをスタックに積む iload_n ローカル変数ｎの値をスタックに積む istore_n スタックトップの値をローカル変数ｎに格納する getfield フィールドの値をスタックに積む putfield スタックトップの値をフィールドに格納する iadd スタックトップの2つの値の加算を行う if_icmplt スタックトップの2つの値の大小により分岐を行う 2000/09/20 ソフトウェア科学会全国大会

8 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 ソフトウェア科学会全国大会

9 JAVAバイトコードにおけるデータ依存関係
データの格納 ローカル変数 / フィールド スタック ある値に対応する記憶領域が命令により変化する(push / pop演算の存在) iconst_n iload_n iadd etc… 命令に応じてその位置を追跡する必要がある 2000/09/20 ソフトウェア科学会全国大会

10 スタックに関するデータ依存 スタック上のある値v が参照されるとき、v を定義した命令s から参照する命令t にスタックに関するデータ依存関係が存在する s : iconst_v , t : istore_1 iconst_v 1 v ローカル変数 スタック istore_1 2000/09/20 ソフトウェア科学会全国大会

11 スタックに関するデータ依存 スタック上のある値v が参照されるとき、v を定義した命令s から参照する命令t にスタックに関するデータ依存関係が存在する s : iconst_v , t : istore_1 iconst_v 1 v ローカル変数 スタック istore_1 2000/09/20 ソフトウェア科学会全国大会

12 スタックに関するデータ依存 スタック上のある値v が参照されるとき、v を定義した命令s から参照する命令t にスタックに関するデータ依存関係が存在する s : iconst_v , t : istore_1 iconst_v 1 v ローカル変数 スタック istore_1 2000/09/20 ソフトウェア科学会全国大会

13 ローカル変数に関するデータ依存 あるローカル変数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 ソフトウェア科学会全国大会

14 フィールドに関するデータ依存 あるフィールド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 ソフトウェア科学会全国大会

15 データ依存解析手法の提案 前提 解析アルゴリズム 制御フローグラフの構築 データ依存関係の抽出 解析フレームの準備 2000/09/20
ソフトウェア科学会全国大会

16 前提 提案するアルゴリズム 入力: JAVAバイトコード 出力: データ依存関係を表すグラフ 静的解析(存在しうるすべての経路に対して解析)
単一スレッドを対象 入力: JAVAバイトコード 出力: データ依存関係を表すグラフ 節点: JAVAバイトコードの命令 辺: 命令間に起こりうる制御の移動、 命令間に存在するデータ依存関係 2000/09/20 ソフトウェア科学会全国大会

17 解析アルゴリズム 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 ソフトウェア科学会全国大会

18 解析アルゴリズム 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 ソフトウェア科学会全国大会

19 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 ソフトウェア科学会全国大会

20 Step2:データ依存関係の抽出 (1/3) Phase1：解析フレームの準備 解析フレーム メソッド内で各ローカル変数・フィー
ルド・スタック上の値がどの命令で 定義されたかを保持 変数名とその値を最後に定義した 命令の番号の対の集合 stack_0 undef stack_1 stack_2 5 local_0 3 local_1 4 2000/09/20 ソフトウェア科学会全国大会

21 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 ソフトウェア科学会全国大会

22 Step2:データ依存関係の抽出 (3/3) Phase2: データ依存関係の抽出 CFG辺をたどりながら、各節点を解析
各節点が表す命令に応じて、解析フレームを更新 逐次実行 分岐 データ依存関係が抽出された場合、CFGにデータ依存辺を追加 更新された解析フレームを用い、この節点を始点とするすべてのCFG辺をたどり次の節点に移動し、解析を続ける 2000/09/20 ソフトウェア科学会全国大会

23 逐次実行 解析フレームの更新 / データ依存辺の追加 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 ソフトウェア科学会全国大会

24 逐次実行 解析フレームの更新 / データ依存辺の追加 local_0 undef local_1 stack_0 1 1: iconst_3
1 3 ローカル変数 スタック stack_0 1 2: istore_1 2000/09/20 ソフトウェア科学会全国大会

25 逐次実行 解析フレームの更新 / データ依存辺の追加 local_0 undef local_1 stack_0 1 1: iconst_3
1 3 ローカル変数 スタック stack_0 1 2: istore_1 2000/09/20 ソフトウェア科学会全国大会

26 逐次実行 解析フレームの更新 / データ依存辺の追加 local_0 undef local_1 stack_0 1 1: iconst_3
1 3 ローカル変数 スタック stack_0 1 2: istore_1 2000/09/20 ソフトウェア科学会全国大会

27 逐次実行 解析フレームの更新 / データ依存辺の追加 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 ソフトウェア科学会全国大会

28 分岐 解析フレームの更新 / データ依存辺の追加 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 ソフトウェア科学会全国大会

29 分岐 解析フレームの更新 / データ依存辺の追加 local_0 2 stack_0 undef stack_1 5: iconst_3
6: iload_0 1 ローカル変数 スタック 7: if_icmplt L4 2000/09/20 ソフトウェア科学会全国大会

30 分岐 解析フレームの更新 / データ依存辺の追加 解析フレームの複製 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 ソフトウェア科学会全国大会

31 繰り返し(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

32 繰り返し(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 ソフトウェア科学会全国大会

33 提案手法の実現 (1/2) JAVAバイトコードをJasmin形式に変換し、解析 構文解析、CFG構築、データ依存関係解析
データ依存解析ツール JAVAバイトコード データ依存辺を 追加したCFG 1000 101101 CFG Jasmin Translator 構文解析、 CFG構築 データ依存 関係解析 JAVAバイトコード （Jasmin形式） 2000/09/20 ソフトウェア科学会全国大会

34 提案手法の実現 (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 ソフトウェア科学会全国大会

35 まとめと今後の課題 まとめ 今後の課題 本研究では、JAVAバイトコードに対するデータ依存関係を定義し、その抽出手法を提案した
また、提案手法を採用したツールの試作を行い、その動作を確認した 今後の課題 スレッドへの対応 解析の効率化 JAVAバイトコードに対するプログラムスライスの抽出 2000/09/20 ソフトウェア科学会全国大会