ループ反転
コンピュータサイエンスにおいて、ループ反転とは、whileループをdo..whileループを含むifブロックに置き換えるコンパイラ最適化およびループ変換のことである。[1]正しく使用すると、[説明が必要] 、命令パイプライン化[引用が必要]またはジャンプ命令を回避することで分岐予測ミスを減らすことでパフォーマンスが向上する可能性がある。[1]
Javaの例
void pre_inversion () { while ( /* 条件 */ ) { /* ループ本体 */ } } は次と同等です:
void post_inversion () { if ( /* 条件 */ ) { do { /* ループ本体 */ } while ( /* 条件 */ ); } } ループの最初と最後以外の反復では、条件が偽のためループに入らない場合も含め、パフォーマンスに変化はありません。ただし、最後の反復では、ループに入る際にジャンプ命令が2つ少なくなります。これは、do-whileループがループ条件を評価するためにwhileループの先頭にジャンプする必要がないためです。[1]
C言語の例
int i , a [ 100 ]; i = 0 ; while ( i < 100 ) { a [ i ] = 0 ; i ++ ; } は次と同等です:
int i , a [ 100 ]; i = 0 ; if ( i < 100 ) { do { a [ i ] = 0 ; i ++ ; } while ( i < 100 ); } 2番目の例は一見複雑に見えるかもしれませんが、命令パイプラインを使用しているため、最近のCPUでは実際にはより高速に実行される可能性があります。コード内のジャンプはパイプラインストールを引き起こし、パフォーマンスに悪影響を及ぼします。[要出典]
さらに、ループ反転により、ループ不変のコードを安全に移動できるようになります。[要引用] [要説明]
3アドレスコードの例
[説明が必要]
私 := 0 L1: i >= 100 の場合は L2 へ a[i] := 0 i := i + 1 L1へ移動 L2:
i が100 で初期化されていた場合、実行時に実行される命令は次のようになります。
i >= 100の場合 L2へ移動i が100 未満の値に初期化されていると仮定します。次に、ループ内でiが 99 に増分された後に実行される命令を見てみましょう。
L1へ移動 i < 100の場合 a[i] := 0 i := i + 1 L1へ移動 i >= 100の場合 L2へ移動 <<L2にて>>それでは、最適化されたバージョンを見てみましょう。
私 := 0 i >= 100 の場合は L2 へ L1: a[i] := 0 i := i + 1 i < 100 の場合は L1 へ L2:
ここでも、 iが 100 に初期化された場合に実行される命令を見てみましょう。
i >= 100の場合 L2へ移動元のバージョンと比べて、サイクルを無駄にすることはありませんでした。次に、 iがインクリメントされて、より詳細な情報が得られるケースを考えてみましょう。これは、あらゆるものを作成するために最も一般的に使用されます。
i < 100の場合 L1へ移動 a[i] := 0 i := i + 1 i < 100の場合 <<L2にて>>ご覧のとおり、実行時に 2 つのgoto (および 2 つのパイプライン ストール) が排除されました。
参考文献
- ^ abcd Jubb、Chae、「現代のCコンパイラにおけるループ最適化」（PDF）
