 バイトコードにおけるデータ依存解析手法の提案と実現    

誉田 謙二 Ý    

大畑 文明 Ý 

井上 克郎 ÝÞ     

Ý 大阪大学 大学院基礎工学研究科

         !"Þ 奈良先端科学技術大学院大学 情報科学研究科

               "
概要
プログラムの依存関係解析は，プログラム理解，テスト，デバッグなど，ソフトウェアの開発から保守に至るまでその利用範囲は広く，様々な言語に対する解析手法が提案されてきた．しかし，その多くは通常の手続型言語を対象としたものであり，バイトコードのようなスタックマシンを前提としたプログラムの解析法の提案は少ない．本稿では  バイトコードにおけるデータ依存関係を定義し，その解析手法の提案および手法の実現を行った．

まえがき

ラス単位に生成され，対応するクラスに関連したデータおよびバイトコードの命令列を含む．そして，  バーチャ   ，以下， ）がクルマシン（ ラスファイルを読み込み，バイトコードを解釈，実行する．

+,

プログラム依存関係解析は，コンパイラ最適化のバックエンドとしてだけでなく，プログラム理解，プログラムデバッグ（保守）など，その利用範囲は大きい．これまで提案されている依存関係解析手法は，高級言語のソースコードや 番地コードを対象としてきた ．しかし，  バ
イトコード（    ，以下，バイトコード） は，スタックマシン上での実行が前提となっており，従来手法を適用しただけではスタックを介したデータ依存関係を考慮することはできない．また，バイトコードにおける依存があるが，依存関係の定関係に関する研究としては義が述べられているだけで，実際の抽出手法については知られていない．

#

$%&

$#&

int sample(int a,int b){if(a == b) a = 3;
else a = 4;
return(a);}ソースコード$' (&

図%)..

'*

データ依存関係命令 × で定義されたローカル変数 Ú の値が命令 Ø で参照されるとき，× から Ø に Ú に関するデータ依存関係（     ）が存在するという．図 では，   によりスタックトップの値 Ü がローカル変数 に代入（定義）され， によりローカル変数の値がスタックトップにプッシュ（参照）されている．この間にローカル変数 に関のとき，   と  バイトコードとデータ依存関係%#以降， でバイトコードおよびそこに存在するデータ依存関係について説明する． でデータ依存解析手法の提案およびその実現について述べる．最後に でまとめと今後の課題について述べる．

#*%- バイトコードへの変換例

例えば図 のように，メソッド  はコンパイラによりソースコードからバイトコードに変換される．バイト種類の命令から構成されており，表コードはおよそに代表的な命令とその動作を挙げる．またバイトコードにはデータを格納可能な変数として，フィールド，ローカル変数，スタックの 種類がある．

本研究では，バイトコードにおける単一スレッド内のデー
タ依存関係を定義し，その抽出手法を提案する．また，提案手法に基づき，バイトコードを入力とするデータ依存解析ツールを試作し，アルゴリズムを実際に動作させてみた．

)*

iload_1
iload_2
if_icmpne L10
iconst_3
istore_1
goto L12
JavaCompiler L10: iconst_4
istore_1
L12: iload_1
ireturn
バイトコード)バイトコード% で書かれたソースプログラムは，  コンパイラによりクラスファイルに変換される．クラスファイルはク%%%

%- バイトコードの代表的な命令....

表動作      

スタックトップからデータを取り除く
定数  をスタックに積む
ローカル変数  の値をスタックに積む
スタックトップからデータを取り除き，それをローカル変数  に格納するフィールドの値をスタックに積む
スタックトップからデータを取り除き，それをフィールドに格納する
スタックトップからデータを  つ取り除き，それらの加算結果をスタックに積む
スタックトップからデータを  つ取り除き，それらの除算結果をスタックに積む
スタックトップからデータを  つ取り除き，それらが等しくなければラベル  に制御移動する

図....
................
....

iload_1

図 制御フローグラフの構築
制御フローグラフ（       ，以下， ）とは，バイトコードに対して制御フロー解析を行い，各命令を節点，命令間の制御の移動を有向辺で表現したもので構築は，従来の手続きある．バイトコードに対するを適用することが可能であ型プログラムに対する手法
り，図 にアルゴリズムの概略を示す．また，このアルゴリズムを図 のバイトコードに適用した結果を図 に示す．

(x%1

アルゴリズム入力 バイトコード
出力 
処理 バイトコードに対し  を構築する

 各命令を抽出し， 節点を作成   全節点の集合     の次に実行され得る  節点の集合  ¼ を導出 ¼   ¼から ¼ に  辺を引く 

命令 × で定義されたフィールド Ú の値が命令 Ø で参照されるとき，× から Ø に Ú に関するデータ依存関係が存在するという．図 では，     によりスタックトップの値 Ý がフィールド に代入（定義）され，   によりフィールド の値がスタックトップにプッシュ（参照）されている．このとき，    と    の間にフィールド に関するデータ依存関係が存在する．

/0 $%&stack)- ローカル変数に関するデータ依存関係#'- スタックに関するデータ依存関係)

stack

0
1
xmemorystack

本稿で提案するバイトコードに対するデータ依存解析手法は，以下の つのステップで構成される．

x0
1xmemory3

 データ依存解析手法

するデータ依存関係が存在する．

istore_1

stack

0
1
3
memoryistore_1....

   301
memoryiconst_3................

命令/

図/(- アルゴリズム



iload_1
起こりうる制御移動

iload_2yputfield Point/x Iyfield_x
memoryif_icmpne L10stackygetfield Point/x I

field_x

memory図iconst_3y

L10 iconst_4

stack#- フィールドに関するデータ依存関係

istore_1
istore_1
goto L12

また，命令 × でスタック上に積まれた値が命令 Ø で参照されるとき，× から Ø にスタックに関するデータ依存関係が存在するという．図 では，    によりスタックにプッシュ（定義）された値が   によって参照される
ため，    と   の間にスタックに関するデータ依存関係が存在する．

L12'iload_1

ireturn図)

1- 図 % の 0  データ依存関係の抽出 アルゴリズム
入力 節点 ，解析フレーム 
出力 データ依存辺が追加された制御フローグラフ
処理 解析フレームを用いてデータ依存辺を追加する

はじめに，データ依存解析に用いる解析フレームを準備す
る．次に，解析フレームを更新しながらでの辺をたどることにより，データ依存関係の構築したへのデータ依存辺の追加を行う．
抽出および解析は実行可能性のある全ての経路に対して行い，新たなデータ依存関係が抽出されなくなるまで続ける．以下，各フェーズを詳細に述べる．

5%

  が  の合流点      が の解析フレーム履歴に含まれている   の解析フレーム履歴に  を追加     !  を更新し、データ依存辺を  に追加
" の次に実行され得る  節点の集合  ¼ を導出#  ¼   ¼    の複製  ¼ を作成  ¼ $  ¼  23 )4 解析フレームの準備
データ依存関係の抽出を行うにあたり，各メソッド内のフィールドやローカル変数，スタック上の各値がどの命令で定義されたかを保持する表（解析フレーム（    ）と呼ぶ）を用意する．解析フレームは，変数名およびその値を最後に定義した命令の行番号の対の集合である．図は，バイトコードおよびその 〜 行目の命令を解析し終えた状態での解析フレームを示している．フィールド は未定義，ローカル変数 は 行目の    で，は 行目の   で，は 行目の  によってに関しては， 行目定義されたことを表している．の   により値が定義されるが， 行目の  により値が取り除かれるため，未定義となる．

図

解析フレームの Ü に対応するエントリが命令 Ø であるとき，命令 Ø から命令 × にデータ依存関係が存在す
節点間に Ü に関するることが分かり，対応するデータ依存辺を追加する．

0 

6

field_0

undef

local_0

4

stack_0
stack_1
stack_2

undef8524 命令 × で変数 Ü が定義されるとき

解析フレームの Ü に対応するエントリを命令 × の行番号に変更する．

24     や   など，スタックへのプッシュを伴う命令のときスタックトップを記憶するポインタ ×Ô の値をげる

2!4 や  など，スタックからのポップを伴う命令のとき
解析フレームのスタックトップの変数のエントリを未定義にするとともに ×Ô の値を つ上げる．

6- 解析フレーム%+, の仕様により，特定の分岐から派生した分岐経

8

図 において，    は    で定義されたデー
タをスタックからポップし，ローカル変数 を定義している．そのため，これらの命令間はデータ依存関係が存在し，節点間に辺が追加される．加えて，解析フ対応するレームのローカル変数 に対応するエントリが    の行番号である に，スタックトップに対応するエントリが未定義として更新される．

路が合流する地点でのスタックサイズは経路に依存せず等
しい ．また，各メソッドの処理に必要なローカル変数の個数や最大スタックサイズはコンパイラによりあらかじめ計算されているため，解析フレームの大きさは静的に決定することができる．

$#&.

0 

#

データ依存関係の抽出

2: iconst_6

3 %

データ依存関係の抽出は，で用意した解析フレー
ムおよび，プログラムの開始節点を入力として，図 に示すアルゴリズム に従って行われる．このアルゴリズムは再帰的に適用される．

274

3: istore_0

24

データ依存辺の追加

2: iconst_6
3: istore_0

....

7

アルゴリズム のでは，命令の種類に応およびは，じて以下の つの処理を行う．ただし'.

....

% つ下2!4local_0

undef

stack_0
stack_1undef2

図#....

1: iload_0
2: iconst_9
3: iadd
4: istore_0
5: iload_0
6: iconst_2
7: iload_0
8: idiv
9: imul
10: istore_0

24 命令 × で変数 Ü が参照されるとき.
  ). '  % 7
  .
7

7- アルゴリズム

24 や 24 の処理とともに行われる．

6% 7(図....

23 %40 0 

解析フレームの更新

local_03

stack_0
stack_1

undef
undef

8- 解析フレームの更新，データ依存辺の追加 の 2%4〜264 は，0  にループがある際にバイトコード解析が無限に続いてしまうのを回避する働きをしている．

0  の合流節点は， が適用される毎にその節点での解析フレームを履歴として保持する．このとき履歴に同一のフレームが存在しないかを調べ，存在すればその解析フレームによる解析を停止する．先にも述べたが解析フレームはコンパイル時にその大きさが決定可能であり，またそのエントリの値は行番号の最大値で抑えられるため， は必ず停止する．

Jasmintranslator%. に，図 % のバイトコードに対する解析結果を示す．
図 1 の 0  に対して，ローカル変数，スタックに関する図+,

スタックに関するデータ依存

if_icmpne L10

L10 iconst_4$1&

istore_1
istore_1
goto L12

L12

iload_1

参考文献$%& *+*  :* 9** ;0 5 35 <    =>?" 2%8714*$)& ;9     3  =ireturn

図%.- データ依存解析結果（データ依存辺を追加した 0 ）    提案手法の実現$#& 9*," *@- ;  +  ,  =A:" B   2%8864*$'& 9*C - ;5  "  9 ! D" = 日
本ソフトウェア科学会第 ! 回大会 55*#%6>#).2%8884*$(& 9*C - ;  "E 0 @  9 ! D"> = 日本ソフトウェア科学会第 ! 回大会 55*#%#>#%12%8884*$1& ,*?- ;3  =     @   %.2'4 55*#()F#(62%87'4*#*

本節では， で提案したデータ依存解析手法の実現について述べる．

%%)
9  
9  にツールの構成を示す．バイトコードは通常 進図形式のデータ列であるため，あらかじめ読みやすい形式に変換しておく．本ツールは，はじめに形を構築する．その式のバイトコードを構文解析し，後，ローカル変数，スタックに関するデータ依存関係を抽にデータ依存辺を追加する．これによりデー出し，が得られる．
タ依存辺が追加された$)&

0 %%- ツール構成

本研究では，バイトコードに対して， の特徴であるスタックを考慮したデータ依存関係を定義し，その抽出手法を提案した．さらに，提案手法のプロトタイプ実装を行いアルゴリズムの動作を確認した．
今後の課題としては，提案した解析手法の効率化や，複数スレッド間におけるデータ依存関係の抽出が挙げられる．
また，メソッド間のデータ依存関係の抽出を行うことでプ
ログラム依存グラフ（      ， ）を構築し，プログラムスライス（     ） 抽出などへの発展を考えている．

起こりうる制御移動
ローカル変数に関するデータ依存

iconst_3

データ依存関係解析

 まとめと今後の課題

データ依存関係を表すデータ依存辺が追加されている．

iload_2

構文解析,
CFG構築

バイトコード(Jasmin形式)

図iload_1

データ依存解析ツール
データ依存辺をCFG追加したCFG

01010
000000101001111111110 

0 

実際に本ツールを用いてバイトコードのデータ依存解析を行い，提案手法が正しく動作することを確認した．本ツー
ルでは，メソッド呼び出し命令がある場合，単にメソッド呼び出し引数を参照される変数，戻り値を定義される変数として扱うため，解析結果の正確性はメソッド間の解析を行った場合より低下する．ただし，抽出すべきデータ依存関係が排除されることはない．また，複数スレッド間にまたがる変数参照や変数定義は解析の対象としていない．

'