冗長な null 検査の除去

冗長なnull^{検査の除去では，}null検査が例外を投げ うるか検査し，例外を投げえないな らば，null検査を冗長とみなし て除去する．2^{章で述べたように，}Java2C^{トランスレータ}

では暗黙のnull検査を利用できない．そこでJeanPaul^のJava2C^{トランレータは}null^検

査を明示的な分岐によって実現するが，明示的な分岐は実行速度的な意味からも，コード サイズ的な意味からもオーバヘッド の元となる．そこでJeanPaul^のJava2C^{トランスレー}

タではメソッド 間に跨がるフロー解析を使って冗長なnull検査を検出して除去する．

フロー解析を使った冗長なnull検査の除去について，図3.11(a)^に示したJava^ソース

コード を使って述べる．図3.11(a)^{のコードは配列array}に収めてある数値の合計を求める プログラムだが，最適化を適用しない場合，1行目で配列の長さを参照するところと，2^行

目で配列要素を参照するところでnull検査を実施する．最適化を適用せずに図3.11(a)^に示

したJava^{ソースコード を}Cソースコード に変換した結果を図3.11(b)^{に示す．図}3.11(b)

の3^{行目にある}null検査は配列の長さを参照するところから生じたものであり，7^行目の null検査は配列要素の参照から生じたものである．ところで7^行目のnull^{検査はフロー解}

析をおこなうと冗長であることを証明できる．なぜなら7^行目のnull^{検査に到達するには} 3^行目のnull検査を経由せねばならず，3^行目のnull^{検査でarrayが}null^{ではない場合に}

限って7 行目方面に制御が移るからである．したが って7^行目のnull^{検査は除去できる．}

3.3.7

ループのピーリングはループ 本体を1回分展開する．ループのピーリング自体にプログ ラムの実行を高速化する効果はないが，冗長なnull検査の除去や共通式除去など 別の最適 化を適用する機会を増やす効果がある．

たとえば 図3.11(b)のプ ログラムでは，フロー解析による冗長なnull^{検査の除去によっ}

て7^行目のnull検査を除去しても，まだ3^行目にnull^{検査が残っている．}3^{行目はループ}

の内部にあたり，null検査を残すと実行速度に大きな悪影響を与える．このような場合に はループをピーリングしてnull検査をループ 外に追い出すことができる．

図3.11(a)のプログラムにループのピーリングを適用した上で冗長なnull^{検査の除去を}

適用した結果を図3.11(c)^{に示す．図}3.11(c)^の2^〜8行目がピーリングの結果生じたコー ド であり，ループの1回目の実行をおこなう．2^{回目以降の実行は}9^〜14^{行目がをおこな}

う．2^〜8^{行目のコード と，}9^〜14^{行目を比較すると，}3^{行目にある}null^{検査が，ループ}

本体にあたる9^〜14行目ではなくなっていることが判る．これはループの1^{回目の実行}

でnull^{検査を実施した結果，}2^{回目以降の実行では}null検査が不要なった結果であり，こ のことからループのピーリングがnull検査をループ 外に追い出したことが判る．

3.3.8

冗長な配列添字検査の除去では，配列参照時の添字検査が冗長か，添字の値域を調査して 判定し，冗長ならば添字検査を除去する．添字検査とは，配列参照時に添字を検査して，添 字が配列の長さの範囲内にあるか調べ，範囲外ならば実行時例外ArrayIndexOutOfBounds を投げる動作を意味する．Javaの言語仕様は不正なメモリ参照の防止を目的として，配列 の範囲外を参照したときに実行時例外を投げ るよう規定している．

図3.11(a)^のJava^{ソースコード の}2行目に配列参照がある．この配列参照に相当するC

ソースコードが，図3.11(b)^の7^〜12行目にあるが，そのうち9^〜11^{行目が添字検査を}

おこなう．ただしこの添字検査は冗長である．なぜなら図3.11(a)のコード を見ると添字

1: for(int i=0 i<array.length i++) 2: sum += arrayi]

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

1: int i=0 2: LOOP:

3: if (array == NULL)

4: goto THROW NullPointerException 5: if (!(i<array->length))

6: goto EXIT

7: if (array == NULL)

8: goto THROW NullPointerException 9: unsigned int len = array->length 10: if ((unsigned int)i >= len)

11: goto THROW ArrayIndexOutOfBounds 12: sum += arrayi]

13: i = i + 1 14: goto LOOP 15: EXIT:

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

1: int i=0 2: PEEL:

3: if (array == NULL)

4: goto THROW NullPointerException 5: if (!(i<array->length))

6: goto EXIT 7: sum += arrayi]

8: i = i + 1 9: LOOP:

10: if (!(i<array->length)) 11: goto EXIT

12: sum += arrayi]

13: i = i + 1 14: goto LOOP 15: EXIT:

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

図3.11: ループピーリングと冗長なnull検査および 配列添字検査除去

iの値域が0ⁱ<^array:^{lengthであり，}2行目の配列参照において例外が発生しえない ことが 判るからである．冗長な配列添字検査の除去ではプログラムを解析して配列参照に おいて例外が発生し うるか調べ，2行目の配列参照については例外が発生しえないので配 列添字検査が冗長であると判断して除去する．この結果，図3.11(b)^{の最適化なし のコー}

ド では9^〜11行目にあった配列添字検査が，図3.11(c)の最適化済みコード ではなくなっ ていることが判る．

第

章 クラス初期化検査の除去が実行速度に