インライン展開

インライン展開とは呼出し先のメソッド 本体を呼出し元に展開する最適化である．静的 コンパイラが生成するコード を直接呼出しするメソッド 呼出しにはインライン展開を適用 できる．

Java2Cトランスレータは インライン展開の適用にあたり，メソッド_n()の内部に適用

対象のメソッド 呼出しm⁽⁾があるとするとき，メソッド n()の仮定クラスを表す集合Sn^，

配列Nn^{に次の操作を施す．}

配列Nn^{中のメソッド} m()^を1^{つ捨てる．}

SnSnSm

配列Nn^に配列Nm中の要素を全て追加する．

この操作を施す理由は，インライン展開を適用すると，メソッドn()の中から メソッド m()への直接呼出しが1つ減り，代りに メソッド_m()の本体が メソッド _n()の中に展開さ れるからである．メソッド m()の本体内には別のクラスを参照して最適化したコード や 別のメソッド の静的コンパイル済みコード への直接呼出しが入っている場合がある．した がってメソッド _m()の本体をメソッド _n()の中に展開するならば，メソッドm^()の仮定

クラスを表す集合Sm^と配列Nm^{を，それぞれ集合}Sn^と配列Nn^{に加える必要がある．}

3.3.5

スタックトレース管理コード のオーバヘッド 軽減

ここではJeanPaulにおけるスタックトレースの実現方法を示し，次にスタックトレー

スの実現にともなうオーバヘッド を軽減する次の3種類の最適化について述べる．

1.冗長なスタックトレース管理コード の除去

2.スタックトレース管理コード の補償コード 領域への移動

3.スタックトレース管理コード の高速化

JeanPaul

におけるスタックトレースの実現

JeanPaulでは，実行時にメソッドjava.lang.SecurityManager.getClassContext() を呼出した際にスタックトレースを計算可能にするために，各スレッドがスタックトレー

スを表すリスト形式のデータ構造を維持管理する．このリストの先頭には，メソッド の実 行開始時点で，ど のメソッド を実行しているかを示す情報を収めたセルをつなぎ ，メソッ ド から返戻する時点で先頭のセルを破棄する．スタックトレースを計算する際には，この

リストにつないであるセルを先頭から順次たど る．

スタックトレ ースを維持管理するためにセルをつなぎ ，破棄するコード をスタックト レース管理コードと呼ぶことにする．JeanPaul^のJava2Cトランスレータは メソッド の出 入口にスタックトレース管理コード を挿入する．スタックトレース管理コード を図3.8^に

示す．図3.8^の1^〜4^{行目で定義する型}singleFrameは実行中のメソッド を示すセルを表 す．5^〜9^{行目で定義するマクロ}PushSingleFrame()はsingleFrame型のセルをリスト につなぐ ．Java2CトランスレータはマクロPushSingleFrame()をメソッド の入口に挿入 する．マクロPushSingleFrame()の定義中に出てくる変数_eeはスレッド 固有の資源を収 める構造体を指示する．変数_eeが指示する構造体のメンバjp current frameはスタッ クトレースをあらわすリストの先頭にあるセルを指示する．図3.8^の10^〜12^{行目で定義}

するマクロPopSingleFrame()はリストの先頭にあるセルを破棄する．Java2C^トランス

レータはマクロPopSingleFrame()をメソッド の出口に挿入する．13^{行目以降のコード}

についてはスタックトレース管理コード の高速化のところで述べる．

スタックトレース管理コード をメソッド の出入口に挿入すると，実行速度的にもコード サイズ的にも大きなオーバヘッドが生じ る．このオーバヘッド を軽減する最適化について 順次述べる．

冗長なスタックトレース管理コード の除去

スタックトレース情報は，スタックトレースを計算するメソッド（getClassContext() など ）の直接あるいは間接的な呼出し 元にならないメソッド では管理する必要がない．そ こで冗長なスタックトレース管理コード の除去では，メソッドがスタックトレースを計算 するメソッド の呼出し元になるか メソッド 間に跨がって解析し，ならないならスタックト レース情報の管理コード を削除する．

スタックトレース管理コード の補償コード 領域への移動

補償コード とは，実行頻度は低いが万一に備えて挿入するコード を意味する．スタック トレース管理コード の補償コード 領域への移動では，スタックトレース管理コード を補償 コードが存在する領域に移動できるか調べ，可能ならば移動することによってスタックト レース管理コード の実行頻度を引き下げ，実行を高速化する．

補償コード の例として，図3.9(a)^のJava^{ソースコード の}5^〜7 ^{行目にあるメソッド}

val()をCソースコード にトランスレートした結果を図3.9(b)に示す．トランスレートに あたっては，図3.9(a)^の6行目にある仮想メソッド 呼出しthis.val0()にクラスチェック

1: struct singleFrame^f 2: void *previous frame 3: unsigned long method id 4: ^g

5: #define PushSingleFrame(ee, frame, mid) ⁿⁿ 6: (frame).previous frame = ⁿⁿ

7: (ee)->jp current frame ⁿⁿ 8: (frame).method id = (mid)ⁿⁿ 9: (ee)->jp current frame = &(frame) 10: #define PopSingleFrame(ee, frame) ⁿⁿ 11: (ee)->jp current frame = ⁿⁿ

12: (frame).previous frame

13: #define DeclareMultiFrame(frame, depth) ⁿⁿ 14: struct ^{f nn}

15: void *previous frame ⁿⁿ 16: unsigned long sp ⁿⁿ

17: unsigned long method ids(depth)] ⁿⁿ 18: ^g (frame)

19: #define LinkMultiFrame(ee, frame) ⁿⁿ 20: (frame).previous frame = ⁿⁿ

21: (ee)->jp current frame ⁿⁿ 22: (ee)->jp current frame = &(frame) 23: #define UnlinkMultiFrame(ee, frame) ⁿⁿ 24: (ee)->jp current frame = ⁿⁿ

25: (frame).previous frame

26: #define PushMultiFrame(frame, depth) ⁿⁿ 27: (frame).sp = ((((depth) + 1) << 1) | 1) 28: #define SwapMultiFrame(frame, mid, depth) ⁿⁿ 29: frame.method ids(depth)] = (mid)

30: #define PopMultiFrame(frame, depth) ⁿⁿ 31: (frame).sp = (((depth) << 1) | 1)

図3.8: スタックトレース管理コード

変換を適用した．図3.9(b) ^の7^〜12行目がクラスチェック変換後の仮想メソッド 呼出し だが，ここで11行目の間接呼出しは，静的コンパイル時に予測したメソッド _C::val0と は違うメソッド を呼ぶ際に使う．静的コンパイル時の予測が外れる可能性は低く，11^行目

の間接呼出しを使う機会は少ない．したがって11行目の間接呼出しは補償コード である．

さて，図3.9(b)^{のコード では}6^行目と13行目でスタックトレース情報の積下しを実施

しているが，これは11行目の間接呼出しの呼出し 先が不定で，その呼出し 先からスタッ クトレースを計算するメソッド を呼ぶ可能性があるためである．7^行目のif^文が8^行目に

分岐する確率が高く，その場合スタックトレース情報の積下しが無駄になることを考慮す ると，積下しのコード は11行目の間接呼出しの前後に移動した方がよい．

スタックトレース管理コード の補償コード 領域への移動を適用してPushSingleFrame() とPopSingleFrame()を補償コード の前後に移動した結果を図3.9(c)^{に示す．図}3.9(c)^の

コード は静的コンパイル時の予測が外れない限りスタックトレース管理コード を実行しな い．スタックトレース管理コード の補償コード 領域への移動では，PushSingleFrame()と PopSingleFrame()が囲う領域内に補償コードがあり，補償コード の内部からのみスタッ クトレースを計算するメソッド を呼出し うる場合に，スタックトレース管理コード を補償 コード 領域に移動する．

スタックトレース管理コード の高速化

スタックトレース管理コード の高速化では，インライン展開したメソッドに関するスタッ クトレースの記録に，図3.8^の1^〜12行目に示したコード より高速な図3.8^の13^行目以

降のコード を使う．

具体的には，インライン展開を適用したメソッド では図3.8^の13^〜18^{行目にあるマク}

ロDeclareMultiFrame()を使ってトレース情報を収めるセルを確保する．セルの内部に は メソッド 内部でのスタックトレース情報を保持する配列method idsと，メソッド 内で の呼出し 深さを表すメンバspがある．実行時には，メソッド の入口で19^〜22^行目にあ

るマクロLinkMultiFrame()を使ってセルをスタックトレース情報リストにリンクする．

そして，メソッド 内で インライン展開した部分への突入時にマクロPushMultiFrame()と SwapMultiFrame()（26^〜29行目）を使ってメソッド 内でのトレース情報を更新し ，脱 出時に30^〜31^{行目のマクロ}PopMultiFrame()で元に戻す．マクロPushMultiFrame()， SwapMultiFrame()，PopMultiFrame()は，リストへのリンクやアンリンクをおこなわな いため，PushSingleFrame()やPopSingleFrame()より実行コストが小さい．

また，マクロPushMultiFrame()，SwapMultiFrame()，PopMultiFrame()を対象とし た次に示す2種類の最適化を実現した．

1.

マクロのループ 外移動 ループ 不変な情報を記録するマクロをループ 外に移動する．

2.

^{冗長なマクロの除去 spを設定するマクロ}PushMultiFrame()，PopMultiFrame()が

1: class C^f 2: int val0()^f

3: return (this.value) 4: ^g

5: int val()^f

6: return (this.val0()) 7: ^g

8: ^g

(a) ^{Javaソースコード}

1: int C val(ExecEnv *ee, Object *this)^f 2: struct singleFrame frame

3: int result

4: int (*code)(ExecEnv *, Object *)

5: = this->class.dispatch tableC val0 oset^]

6: PushSingleFrame(ee, frame, C val id⁾

7: if (code == C val0)^f 8: result = this->value 9: ^gelse^f

10: /* 補償コード 領域 */

11: result = code(ee, this) 12: ^g

13: PopSingleFrame(ee, frame) 14: return (result)

15: ^g

(b) ^{Cソースコード(最適化なし)}

1: int C val(ExecEnv *ee, Object *this)^f 2: struct singleFrame frame

3: int result

4: int (*code)(ExecEnv *, Object *)

5: = this->class.dispatch tableC val0 oset] 6: if (code == C val0)^f

7: result = this->value 8: ^gelse^f

9: /* 補償コード 領域 */

10: PushSingleFrame(ee, frame, C val id) 11: result = code(ee, this)

12: PopSingleFrame(ee, frame) 13: ^g

14: return (result) 15: ^g

(c) ^{Cソースコード(最適化あり)}

図3.9: 補償コード 領域への移動

冗長か判定し ，冗長であれば除去する．マクロが 冗長と判断できる条件は，マクロ から制御フローを順方向にたど るとき，全てのパスにおいてスタックトレースを計 算し うるメソッド 呼出しに 遭遇するより前に，他のPushMultiFrame()あるいは PopMultiFrame()に遭遇するか，あるいは メソッド の出口に到達することである．

この条件を満たすマクロでは，spを設定しても，スタックトレース計算ルーチン が設定したspを参照するより前に，別のマクロが_spを上書きするか，あるいはメ ソッド の出口に到達して，マクロUnlinkMultiFrame()が_spを保持するセルを捨 ててし まう．したが って，この条件を満たすマクロを冗長と判断して除去できる．

なお，図3.8^{において，Pushの動作を}PushMultiFrame()とSwapMultiFrame() に分けた理由は，冗長なマクロの除去ではPushMultiFrame()のみ除去可能であり，

SwapMultiFrame()を除去できないからである．

これらの最適化について図3.10^{を使って詳述する．図}3.10 (a)^のJava^{ソースコード 中}

にあるメソッドm1()をCソースコード にトランスレートした結果を図3.10(b)^および(c)

に示す．トランスレートにあたっては図3.10(a)^の4行目にあるメソッド 呼出しに インラ イン展開を適用し ，スタックトレース管理コード の高速化を適用した．図3.10(c)^のコー

ド には，さらに，冗長なマクロの除去とマクロのループ 外移動を適用した．

図3.10(b)^{のコード と図}3.10(c)のコード を比較すると，最適化の結果とし て図3.10(b)

のコード の5^，15^，18^，22行目にあったマクロが 消失し ，10^，11^{行目にあったマクロが}

ループ 外に移動していることが判る．

図3.10(b)^の5^{行目にある}PushMultiFrame()が 消失するのは ，後続する10^行目の

PushMultiFrame()あるいは22^行目のPopMultiFrame()の内部で_spを更新するまでの 間にスタックトレースを計算しうるメソッド 呼出しが存在せず，5^行目でPushMultiFrame() を実行してspに値を与えることに意味がないからである．5^{行目に後続する}7^{行目にある}

関数呼出し AllocIntArray()では例外OutOfMemoryErrorを生成することがあり，例外 の生成にあたってはスタックトレースの取得がおきるが，JeanPaulでは例外発生時に取 得するスタックトレースに限っては正確な情報を与えなくてもよいという方針をとった．

これは例外発生時に取得するスタックトレースが，開発者にデバッグ用のメッセージを与 える用途にのみ使われることを考えると¹，組込み機器向けJava VM^であるJeanPaul^で

はデバッグ用のメッセージよりも，最適化の機会を増やし て，たとえば5^{行目のマクロを}

除去してコード サイズを削減する方が重要だと判断したためである．

図3.10(b)^の15^{行目にある}PopMultiFrame()が消失するのは，後続する22^行目でsp

を更新するまでの間にスタックトレースを計算し うる関数呼出しが存在しないためで，同 様の理由から18行目のマクロも消失する．22^行目のPopMultiFrame()が消失するのは 直後の23^{行目でframeを捨てるので，}22^行目でspを更新する意味がないからである．

1例外オブジェクトが出力するスタックトレースのメッセージはJava実行系に依存して変わるので，それ がプログラムの実行に影響を与えるとは考えにくい．

ドキュメント内 言語への変換による (ページ 55-62)