ループ展開

ループアンローリング（ループアンワインドとも呼ばれる）は、バイナリサイズを犠牲にしてプログラムの実行速度を最適化しようとするループ変換技術であり、空間と時間のトレードオフとして知られるアプローチです 。変換はプログラマが手動で行うことも、最適化コンパイラによって行うこともできます。現代のプロセッサでは、ループアンローリングは逆効果になることが多く、コードサイズが大きくなるとキャッシュミスが増える可能性があります。ダフのデバイスを参照してください。^[1]

ループアンワインドの目的は、ポインタ演算や各反復での「ループ終了」テストなど、ループを制御する命令を削減または削除することでプログラムの速度を向上させることです。^[2]分岐ペナルティを軽減し、メモリからデータを読み取る際の遅延などのレイテンシを隠蔽します。^[3]この計算オーバーヘッドを排除するために、ループは同様の独立したステートメントの繰り返しシーケンスとして書き直すことができます。^[4]

ループアンローリングは、特定の形式検証技術、特に境界モデル検査の一部でもあります。^[5]

「タイトな」ループのオーバーヘッドは、多くの場合、配列内の次の要素へのポインタまたはインデックスを増分する命令 (ポインタ演算) と、「ループの終了」テストで構成されます。最適化コンパイラまたはアセンブラが、個別に参照される配列変数へのオフセットを事前に計算できる場合は、これらをマシン コード命令に直接組み込むことができるため、実行時に追加の算術演算は必要ありません。

• 実行される命令の削減によって、プログラムのサイズの増加によって生じるパフォーマンスの低下を補うことができれば、大きな利益を実現できます。
• 分岐ペナルティは最小限に抑えられます。^[6]
• ループ内のステートメントが互いに独立している場合 (つまり、ループ内で先に発生したステートメントが後続のステートメントに影響を与えない場合)、ステートメントは潜在的に並列に実行される可能性があります。
• コンパイル時に配列要素の数が不明な場合は、動的に実装できます ( Duff のデバイスの場合など)。

最適化コンパイラは、アンローリングを自動的に、または要求に応じて実行することがあります。

• プログラム コード サイズが大きくなると、特に組み込みアプリケーションでは望ましくないだけでなく、命令キャッシュ ミスも増加し、パフォーマンスに悪影響を与える可能性があります。
• 最適化コンパイラによって透過的に実行されない限り、コードの可読性が低下する可能性があります。
• ループ本体のコードに関数呼び出しが含まれている場合、コード サイズの増加が過度になる可能性があるため、アンローリングとインライン展開を組み合わせることができない場合があります。したがって、2 つの最適化の間にはトレードオフが存在する可能性があります。
• ループ展開と並行してパフォーマンスを向上させるためにソフトウェアパイプラインが必要なハードウェア（レジスタ名の変更が欠如しているか、順序付きスーパースカラー実行を実装しているハードウェア）では、同じレジスタを再利用できる複数の反復からの一時変数を格納するために追加のレジスタを使用する必要がある場合があります。^[7]
• 非常に小さく単純なコードを除けば、分岐を含む展開ループは再帰よりもさらに遅くなります。^[8]

手動 (または静的) ループ アンローリングでは、プログラマーがループを分析し、反復を一連の命令に解釈してループのオーバーヘッドを削減します。これは、コンパイラーによって実行される動的アンローリングとは対照的です。

コンピュータ プログラム内の手順では、コレクションから 100 個のアイテムを削除します。これは通常、for関数delete(item_number)を呼び出す -loop によって実行されます。プログラムのこの部分を最適化する必要があり、ループのオーバーヘッドがdelete(x)関数に比べてかなりのリソースを必要とする場合は、アンワインドを使用して速度を上げることができます。

この変更の結果、新しいプログラムでは 100 回ではなく 20 回の反復のみを実行する必要があります。その後、ジャンプと条件分岐の 20% のみを実行する必要があり、多くの反復でループ管理オーバーヘッドが大幅に減少する可能性があります。最適な利点を得るには、ポインター演算を必要とするアンロール コードで変数を指定しないでください。これには通常、インデックス参照ではなく、「ベース+ オフセット」アドレス指定 が必要です。

一方、この手動のループ展開により、ソース コードのサイズが 3 行から 7 行に拡大し、生成、チェック、デバッグする必要があり、コンパイラーは、拡張されたループ反復内の変数を格納するために、より多くのレジスタを割り当てる必要がある場合があります^{[疑わしい–議論]}。さらに、ループ制御変数と展開されたループ構造内の操作数は、結果が元のコードと同じになるように慎重に選択する必要があります (これが、すでに動作しているコードに対する後からの最適化であると仮定)。たとえば、反復回数が 5 で割り切れなかった場合の影響を考えてみましょう。テスト条件が変数の場合、必要な手動の修正もやや複雑になります。Duffのデバイスも参照してください。

単純なケースでは、ループ制御は生産的なステートメントを整理するための管理上のオーバーヘッドにすぎません。ループ自体は、望ましい結果には何の貢献もせず、単に、複製を生成するプリプロセッサやテキスト エディタで実行できたコードを 100 回複製するというプログラマの退屈な作業を省くだけです。同様に、if- ステートメントやその他のフロー制御ステートメントは、コードの複製で置き換えることができますが、その結果、コードが肥大化する可能性があります。コンピュータ プログラムは組み合わせを簡単に追跡できますが、プログラマはこの繰り返しを退屈だと感じ、ミスを犯します。次の点を考慮してください。

しかし、もちろん、実行されるコードはプロシージャの呼び出しである必要はなく、次の例では計算にインデックス変数が含まれます。

これをコンパイルすると、大量のコードが生成される可能性がある ( printステートメントは悪名高い) が、さらに最適化することは可能である。この例では、ループ内でx(i)とx(i - 1)のみを参照する(後者は新しい値x(i) を開発するためだけに参照する) ため、ここで開発された配列xへの参照が後でないことを考えると、その使用は単純な変数に置き換えることができる。ただし、このような変更は、値が変更される単純な変数を意味するが、配列のままであれば、コンパイラの分析により、配列の値は定数であり、それぞれが前の定数から派生していることがわかり、定数値が引き継がれるため、コードは次のようになる。

2, 2 を印刷します。
印刷 3, 6;
印刷4、24;
...等。

一般的に、ループの内容は大きく、複雑な配列インデックスが関係することがあります。このようなケースでは、最適化コンパイラに展開を任せるのが最善でしょう。最も内側のループを複製すると、多くの最適化が可能になりますが、n が大きくない限り、わずかな利点しか得られません。

次のような疑似コード WHILE ループを考えてみましょう。

この場合、ENDWHILE (ループの先頭へのジャンプ) の実行頻度が 66% 減少するため、アンローリングが高速になります。

さらに良いのは、「調整された」疑似コードの例です。これは、一部の最適化コンパイラによって自動的に実行され、無条件ジャンプを完全に排除する可能性があります。

ループ アンローリングの利点は配列のサイズに依存することが多く、配列のサイズは実行時までわからない場合が多いため、JITコンパイラ (例) は、「標準」ループ シーケンスを呼び出すか、代わりに各要素に対して (比較的短い) 個別の命令シーケンスを生成するかを決定できます。この柔軟性は、ループ アンローリングのコンテキストで、静的または手動の最適化と比較したジャストインタイム手法の利点の 1 つです。この状況では、nの値が比較的小さい場合でも、節約が依然として有効であることが多く、プログラム サイズ全体の増加は (あったとしても) 非常に小さくなります (標準ライブラリの一部として 1 回だけ含まれる場合があります)。

アセンブリ言語プログラマー (最適化コンパイラーの作成者を含む) も、効率的な分岐テーブルに使用される方法と同様の方法を使用して、動的ループ展開の手法の恩恵を受けることができます。この場合、特定の配列内の参照フィールドの最大オフセットが、マシン命令で指定できる最大オフセット (超過するとアセンブラーによってフラグが立てられます) よりも小さい場合に、メリットが最大になります。

この例はIBM/360またはZ/Architectureアセンブラー用であり、100 バイトのフィールド (オフセット 0) が配列FROMから配列TOにコピーされることを想定しています。どちらの配列にも、要素の長さがそれぞれ 256 バイトのエントリが 50 個あります。

* 返送先住所はR14です。
* レジスタR15、R0、R1、R2を、 
* ラベル INIT/MAXM1 で始まるプログラム。
         LM R15、R2、INIT R15 = MVCの最大数を設定します
* 命令（MAXM1 = 16）、 
* R0 = 配列のエントリ数、
* R1 = 'FROM'配列のアドレス、
* R2 = 'TO'配列のアドレス。
*
* ループはここから始まります。
LOOP EQU * LOOP ラベルを定義します。
* この時点で、R15 には常に数字 16 (MAXM1) が含まれます。
         SR R15,R0 残りの数を引く 
* 配列 (R0) から R15 までのエントリ。
         BNP ALL R15が正でない場合、つまり
* 残りエントリー数が16件以上ある
* 配列内の、全体を実行するためにジャンプします
* MVC シーケンスを実行して繰り返します。
*
* 無条件分岐のオフセット（MVCシーケンスの開始から）を計算します 
* 以下の「展開された」MVC ループ。
* 配列の残りのエントリ数が0の場合、R15は16になります。 
* すべての MVC 命令はバイパスされます。
         MH R15,=AL2(ILEN) R15に1の長さを掛ける
* MVC命令。
         B ALL(R15) ALL+R15にジャンプ、
* 計算された特定のMVC命令 
* 残りの部分にドロップスルーします。
*
* MVC 命令の「テーブル」。 
* 最初のエントリは、単一レジスタで最大許容オフセットを持ちます = 16進数 F00
* この例では (15*256) です。
* 以下の16個のMVC（「文字移動」）命令はすべて、ベースプラスオフセットを使用します。 
* アドレス指定と各オフセットは配列要素の長さだけ減少します
* (256)。これにより、各要素に対してポインタ演算が必要になるのを回避できます。 
* 16進数FFFの命令内での最大許容オフセット 
* (15*256+255)。命令はオフセットの降順で記述されるため、最後の 
* セット内の要素が最初に移動されます。
ALL MVC 15*256(100,R2),15*256(R1) 16番目のエントリの100バイトを移動 
* 配列1から配列2へ（ 
* ドロップスルー)。
ILEN EQU *-ALL ILENを前の長さに設定する
* MVC命令。
         MVC 14*256(100,R2),14*256(R1) 15番目のエントリの100バイトを移動します。
         MVC 13*256(100,R2),13*256(R1) 14番目のエントリの100バイトを移動します。
         MVC 12*256(100,R2),12*256(R1) 13番目のエントリの100バイトを移動します。
         MVC 11*256(100,R2),11*256(R1) 12番目のエントリの100バイトを移動します。
         MVC 10*256(100,R2),10*256(R1) 11番目のエントリの100バイトを移動します。
         MVC 09*256(100,R2),09*256(R1) 10番目のエントリの100バイトを移動します。
         MVC 08*256(100,R2),08*256(R1) 9番目のエントリの100バイトを移動します。
         MVC 07*256(100,R2),07*256(R1) 8番目のエントリの100バイトを移動します。
         MVC 06*256(100,R2),06*256(R1) 7番目のエントリの100バイトを移動します。
         MVC 05*256(100,R2),05*256(R1) 6番目のエントリの100バイトを移動します。
         MVC 04*256(100,R2),04*256(R1) 5番目のエントリの100バイトを移動します。
         MVC 03*256(100,R2),03*256(R1) 4番目のエントリの100バイトを移動します。
         MVC 02*256(100,R2),02*256(R1) 3番目のエントリの100バイトを移動します。
         MVC 01*256(100,R2),01*256(R1) 2番目のエントリの100バイトを移動します。
         MVC 00*256(100,R2),00*256(R1) 最初のエントリの100バイトを移動します。
*
         S R0,MAXM1 残りのエントリの数を減らす
* 処理します。
         BNPR R14 処理するエントリがなくなったら、
* R14 でアドレス指定します。
         AH R1,=AL2(16*256) 'FROM'配列ポインタを増分する
* 最初のセット。
         AH R2,=AL2(16*256) 'TO'配列ポインタを増分する
* 最初のセット。
         L R15,MAXM1 最大数のMVCを再ロードする 
* バッチごとの指示をR15に
* （計算によって破壊される） 
* ループの最初の命令)。
         B LOOP ループを再度実行します。
*
* 静的定数と変数（これらはパラメータとして渡すことができますが、 
* MAXM1)。
INIT DS 0A 4つのアドレス（ポインタ） 
* 'LM'命令がプリロードされています
* プログラムの冒頭で。
MAXM1 DC A(16) MVC命令の最大数
* バッチごとに実行されます。
N DC A(50) 配列内の実際のエントリ数（a 
* 変数、別の場所で設定します。
         DC A(FROM) 配列1の開始アドレス 
* （「ポインタ」）。
         DC A(TO) 配列2の先頭アドレス 
* （「ポインタ」）。
*
* 静的配列（動的に取得できます）。
FROM DS 50CL256 それぞれ 256 バイトの 50 個のエントリの配列。
TO DS 50CL256 それぞれ 256 バイトの 50 個のエントリの配列。

この例では、「従来の」ループ (50 回の反復) では約 202 個の命令が必要になりますが、上記の動的コードでは約 89 個の命令しか必要ありません (つまり、約 56% の節約になります)。配列が 2 つのエントリのみで構成されていた場合、元の展開されたループとほぼ同じ時間で実行されます。配列に何千ものエントリがある場合でも、コードサイズの増加は約 108 バイトだけです。

もちろん、複数の命令が関係する場合にも、結合された命令の長さがそれに応じて調整される限り、同様の手法を使用できます。たとえば、この同じ例で、100 バイトのフィールドがコピーされた直後に各配列エントリの残りを null にクリアする必要がある場合は、XC xx*256+100(156,R1),xx*256+100(R2)シーケンス内のすべての MVC の直後に、追加のクリア命令 を追加できます (ここで、 はxxその上の MVC の値と一致します)。

もちろん、4 つまたは 5 つのオペランドのみを指定して、単一のアセンブラマクロステートメントを使用して上記のコードを「インライン」で生成することも完全に可能です (または、代わりに、それをライブラリ サブルーチンにして、パラメータのリストを渡す単純な呼び出しでアクセスすることもできます)。これにより、最適化を簡単に利用できるようになります。

次の例は、 Cで記述された単純なプログラムの動的ループ展開を示しています。上記のアセンブラの例とは異なり、この例では変数 (i) が配列要素のアドレス指定に使用されているため、ポインタ/インデックス演算がコンパイラによって生成されます。完全な最適化は、置換ステートメントで絶対インデックスが使用されている場合にのみ可能です。

#include <stdio.h> 

/* ループの繰り返しごとに処理されるエントリの数。 */ 
/* この数値は、以下のコードを反映した「定数」であることに注意してください。 */ 
#define BUNCHSIZE (8)

int main ( void ) { int i = 0 ; /* カウンター */ int entrys = 50 ; /* 処理する合計数 */ int repeat ; /* while の繰り返し回数 */ int left = 0 ; /* 残り (後で処理) */ /* 要素数が BUNCHSIZE で割り切れない場合は、 */ /* while ループでほとんどの処理を実行するために必要な繰り返し回数を取得します */ 
 
                                         
                                  
                                      
                                       
 
   
  

  repeat = ( entries / BUNCHSIZE ); /* 繰り返す回数 */ left = ( entries % BUNCHSIZE ); /* 余りを計算 */                    
                        

  /* ループを 8 個ずつ展開します */ while ( repeat -- ) { printf ( "process(%d) \n " , i ); printf ( "process(%d) \n " , i + 1 ); printf ( "process(%d) \n " , i + 2 ); printf ( "process(%d) \n " , i + 3 ); printf ( "process(%d) \n " , i + 4 ); printf ( "process(%d) \n " , i + 5 ); printf ( "process(%d) \n " , i + 6 ); printf ( "process(%d) \n " , i + 7 ); 
    
   
         
        
        
        
        
        
        
       

    /* 一度に処理された量でインデックスを更新します */ i += BUNCHSIZE ; } 
      
  

  /* switch 文を使用して case ラベルにジャンプし、残りを処理します */ /* このラベルでドロップスルーしてセットを完了します */ switch ( left ) { case 7 : printf ( "process(%d) \n " , i + 6 ); /* 処理してドロップスルーに依存                                                   */ case 6 : printf ( "process(%d) \n " , i + 5 ); case 5 : printf ( "process(%d) \n " , i + 4 ); case 4 : printf ( "process(%d) \n " , i + 3 ); case 3 : printf ( "process(%d) \n " , i + 2 ); case 2 : printf ( "process(%d) \n " , i + 1 ); /* 残り 2 つ */ case 1 : printf ( "process(%d) \n " , i ); /* 処理があと 1 つ残っています */ case 0 : ; /* 残りはありません */ } } 
   
    
  
              

            
             
             
            
              
                 
                                         
   

Duff のデバイスのように 2 つの部分を一緒に記述することで、コードの重複を回避できます。

次の例では、 型の 2 つの 100 エントリ ベクトル A と B のドット積 を計算しますdouble。 C のコードは次のとおりです。

ダブルドットプロダクト= 0 ;   
( int i = 0 ; i < 100 ; i ++ ) {​         
  ドット積+= A [ i ] * B [ i ];  
}

以下は、ループ展開を実装する前に、2 つの 100 エントリ ベクトル A と B のドット積を計算する MIPS アセンブリ コードです。以下のコードでは、ループの初期化が省略されています。

• ループカウント（$7）を100に初期化します。
• ドット積 ($f8) を 0 に初期化します。
• A[i]ポインタ ($5) を のベースアドレスに初期化しますA。
• B[i]ポインタ ($6) を のベースアドレスに初期化しますB。

配列(a)の1つの要素のサイズはdouble8バイトであることに注意してください。

    ループ3:
            ld $f10 , 0 ( $5 ) ; $f10 ← A[i]             
            ld $f12 , 0 ( $6 ) ; $f12 ← B[i]             
            mul.d $f10 , $f10 , $f12 ; $f10 ← A[i]*B[i]       
            d $f8 、$f8 、$f10 ; $f8 ← $f8 + A[i]*B[i]         
            addi $5 , $5 , 8 ; A[i]のポインタをサイズ分増加               
                                      ; ダブルの。
            addi $6 , $6 , 8 ; B[i]のポインタをサイズ分増加               
                                      ; ダブルの。
            addi $7 , $7 , -1 ; ループカウントを減算する              
    テスト：
            bgtz $7 , loop3 ; ループ回数が0より大きい場合は継続              

以下は上記と同じですが、ループの展開が係数 4 で実装されています。配列 (a double) の 1 つの要素のサイズは 8 バイトであることに注意してください。したがって、各ループには 0、8、16、24 の変位と 32 の変位があります。

    ループ3:
            ld $f10 , 0 ( $5 ) ; 変位0での反復               
            ld $f12 , 0 ( $6 )      
            mul.d $f10 、$f10 、$f12     
            追加.d $f8 、$f8 、$f10     

            ld $f10 , 8 ( $5 ) ; 変位8での反復               
            ld $f12 , 8 ( $6 )      
            mul.d $f10 、$f10 、$f12     
            追加.d $f8 、$f8 、$f10     

            ld $f10 , 16 ( $5 ) ; 変位16での反復              
            ld $f12 , 16 ( $6 )      
            mul.d $f10 、$f10 、$f12     
            追加.d $f8 、$f8 、$f10     

            ld $f10 , 24 ( $5 ) ; 変位24での反復              
            ld $f12 , 24 ( $6 )      
            mul.d $f10 、$f10 、$f12     
            追加.d $f8 、$f8 、$f10     

            追加$5 、$5 、32      
            追加$6 、$6 、32      
            追加$7 、$7 、-4      
    テスト：
            bgtz $7 , loop3 ; $7 > 0 の場合はループを続行                

• Kennedy, Ken; Allen, Randy (2001)。『現代アーキテクチャのためのコンパイラの最適化: 依存性ベースのアプローチ』。Morgan Kaufmann。ISBN 1-55860-286-0。

• Michael Abrashの『Graphics Programming Black Book』の第 7 章、8 ～ 10 ページでは、x86 アセンブリの例を使用してループの展開について説明しています。
• 一般化ループアンローリングでは簡潔な紹介が行われます。
• ループ アンローリングテクニックを使用したアセンブリ言語のサブルーチンの最適化、Agner Fog の最適化ハンドブック(2012)。