ループ展開

ループ展開（ループてんかい、英語: Loop Unwinding）は、プログラムのサイズを犠牲に実行速度を最適化する（時間と空間のトレードオフ）、ループ変換と呼ばれる手法の1つである。ループアンローリング（英語: Loop Unrolling）とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。
ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる（もしくはなくす）事によって、実行速度を向上させることである。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる。

静的/手動ループ展開

人手による（または静的な）ループ展開は、プログラマがループを分析し展開することでループのオーバーヘッドを低減させるものである。一方コンパイラが行うループ展開を動的ループ展開と呼ぶ。

動的ループ展開

ループ展開の有効性は対象となる配列の大きさに依存するが、実行時にならないとその大きさが判明しないことも多い。実行時コンパイラ (JIT) などは、通常のループにすべきか、展開すべきかを判断できる。ループ展開の観点では、この柔軟性が静的または手動の最適化に比べてJIT方式の強みとなっている。
アセンブリ言語では、効率的なジャンプテーブルを使うような技法で動的ループ展開を行うことができる。ここで重要となるのは、配列の最大オフセットが機械語命令で表せる範囲かどうかである。その範囲外の場合、最適化の効果が薄れる。次の例はSystem/360またはZ/Architectureのアセンブリ言語で書かれている。FROM配列とTO配列はそれぞれ1要素256バイトで50要素あり、各要素の先頭から100バイトをFROMからTOにコピーするものである。

アセンブリ言語（System/360）の例

* 配列などを指すよう全レジスタを初期化しておく（R14はリターンアドレス）
         LM    R15,R2,INIT                       load R15= '16'、R0= 配列要素数、R1--> FROM配列、R2--> TO配列
LOOP     EQU   *
         SR    R15,R0                            配列要素数を16から引く         BNP   ALL                               n > 16 なら全命令列を実行し、繰り返す
* MVC命令列の先頭からのオフセットを計算し、展開されたMVCループの所定の位置に無条件ジャンプする         MH    R15,=AL2(ILEN)                    MVC命令の長さ（この例では6）をかける         B     ALL(R15)                          インデックス付き分岐命令（その位置からMVC命令を実行）
* 転送テーブル - 1つめが最大オフセットであり、この例では  X'F00'
ALL      MVC   15*256(100,R2),15*256(R1)         * 16番目のエントリの100バイトをFROMからTOに転送ILEN     EQU   *-ALL                                         MVC命令の長さ。この例では6
         MVC   14*256(100,R2),14*256(R1)         *
         MVC   13*256(100,R2),13*256(R1)         *
         MVC   12*256(100,R2),12*256(R1)         * これら16個の文字転送命令 (MVC) はベース+オフセットのアドレッシングであり         MVC   11*256(100,R2),11*256(R1)         * オフセットは配列の要素長 (256) ずつ減っている。
         MVC   10*256(100,R2),10*256(R1)         * System/360では命令で指定できるオフセットの最大値は X'FFF' であり         MVC   09*256(100,R2),09*256(R1)         * それを越えない範囲で展開可能な最大が16要素ということになる。
         MVC   08*256(100,R2),08*256(R1)         * オフセットの大きい方から転送するので、先頭の要素が最後に転送される。
         MVC   07*256(100,R2),07*256(R1)         *
         MVC   06*256(100,R2),06*256(R1)         *
         MVC   05*256(100,R2),05*256(R1)         *
         MVC   04*256(100,R2),04*256(R1)         *
         MVC   03*256(100,R2),03*256(R1)         *
         MVC   02*256(100,R2),02*256(R1)         *
         MVC   01*256(100,R2),01*256(R1)         2番目の要素の100バイトを転送         MVC   00*256(100,R2),00*256(R1)         1番目の要素の100バイトを転送*
         S     R0,MAXM1                          残り要素数を引く         BNPR  R14                               全部転送し終えたので、R14のリターンアドレスで呼び出し元に復帰         AH    R1,=AL2(16*256)                   FROMへのポインタを1反復ぶんだけずらす         AH    R2,=AL2(16*256)                   TOへのポインタを1反復ぶんだけずらす         L     R15,MAXM1                         R15をMVC命令数 (16) に再設定する（計算で壊れているため）
         B     LOOP                              ループの先頭に戻る*
* ----- 定数と変数の定義（引数として渡すこともできる） ---------------------------------  *
INIT     DS    0A                                LM命令で事前ロードされる4つのアドレス（ポインタ）
MAXM1    DC    A(16)                             MVC命令数N        DC    A(50)                             配列の要素数（変数であり、変更可能）
         DC    A(FROM)                           配列1の先頭アドレス（ポインタ）
         DC    A(TO)                             配列2の先頭アドレス（ポインタ）
* ----- 配列の定義（動的に確保することも可能） --------------------------------------------------  *
FROM     DS    50CL256                          256バイト×50エントリの配列TO       DS    50CL256                          256バイト×50エントリの配列

この例を通常の50回反復するループで記述すると202命令を必要とするが、このように動的コードにすると約89命令で済む（約56%のコード削減）。配列が2要素しかない場合でも、単純なループ展開と同程度の命令数となる。バイナリサイズの増大は約108バイトほどであり、配列の要素数が数千であっても対応可能である。この場合はMVC命令の反復を展開しただけだが、複数命令の場合も同様の技法が適用可能である。例えば、この例で各要素の先頭100バイトをコピーした後、残りの部分をヌル文字でクリアしたい場合、'XC xx*256+100(156,R1),xx*256+100(R2)' という命令を各MVC命令の後に追加すればよい（'xx' は直前のMVC命令と同じ値にする。ILENの位置に注意）。
4つまたは5つの引数を持つマクロで上記コードをインライン展開することも可能だし、サブルーチン化することも可能である。

C言語の例

次の例はC言語で書かれた簡単なプログラムを動的ループ展開したものである。アセンブリ言語の上掲の例とは異なり、変数 (i) が配列の要素を指すのに使われているため、コンパイラはポインタ/インデックスの計算コードを生成することになる。最大限最適化するには、全てのインデックス指定を定数に置き換えなければならない。
#include<stdio.h>#define TOGETHER (8)int main(void){
 int i = 0; 
 int entries = 50;                                 /* 総処理回数 */
 int repeat;                                       /* ループ回数 */
 int left = 0;                                     /* 余り（後で処理する） */
 
 /* 要素数がBLOCKSIZEで割り切れないとしても、 */
 /* 処理の大部分をwhileループで行うように、反復回数を得る。 */

 repeat = (entries / TOGETHER);                    /* 反復回数 */
 left  =  (entries % TOGETHER);                    /* 余りを計算 */

 /* 8回ぶんの処理を展開 */
 while( repeat-- > 0 )
  {
    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 += TOGETHER; 
  }

 /* 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 :                               ;      /* 割り切れた場合 */
  }}