ループ展開(ループてんかい、英語: Loop Unwinding)は、プログラムのサイズを犠牲に実行速度を最適化する(時間と空間のトレードオフ)、ループ変換と呼ばれる手法の1つである。ループアンローリング(英語: Loop Unrolling)とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。

ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる事によって、実行速度を向上させることである。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる。

## 利点

ループのオーバーヘッドは、ポインタまたはインデックスをインクリメントして配列の次の要素を指すための命令群(ポインタ演算)と「ループ終了条件」のテストに由来する。最適化コンパイラなどで配列の個々の要素への参照のためのオフセットを事前に計算でき、それを直接機械語命令列にできるなら、実行時の余分な演算を省くことができる。

- ループ展開によってプログラムが長くなったとしても、それ以上に実質的な実行命令数が削減されれば、全体としては性能が強化される。
- 分岐ペナルティが最小化される。
- ループ内の各文が相互に依存していない場合(すなわち、ループのある周回の結果がその後の周回で必要とされない場合)、それらの文は並列計算できる可能性がある。
- コンパイル時にループ回数(配列要素数)が不明な場合でも、動的ループ展開を実装可能である(Duff's device)。

最適化コンパイラには自動的または要求に応じてループ展開できるものもある。

## 欠点

- プログラムのコードサイズが増大するため、組み込みシステムなどメモリ容量が小さい場合は適切でない。
  - 命令キャッシュミス回数が増え、性能を低下させることがある。
- 最適化コンパイラは透過的にループ展開するが、展開後のコードは可読性が低下する。
- ループ内の処理が関数呼び出しだった場合、インライン展開を伴ったループ展開はコードが膨大になりすぎて現実的でないことがある。従ってそれら2つの最適化の間にはトレードオフの関係があるともいえる。
- 展開後にどのような最適化が可能かにも依存するが、一時変数用にレジスタを多く必要とする場合は性能が低下する可能性もある。
- 小さく単純なループは別として、ループ本体内に分岐がある場合は再帰呼び出しより遅くなることがある。

## 静的/手動ループ展開

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

### C言語での簡単な例

あるプログラムの手続きで、データの集合体から100個の要素を削除(delete)する必要があるとする。このため、`for` ループ内で関数 delete(要素の番号) を呼び出す。この部分を最適化する場合、ループに必要なオーバヘッドがリソースを多大に消費しているなら、ループ展開で性能が向上する。

| 通常のループ | ループ展開後 |
| --- | --- |
| ```  int x;  for (x = 0; x < 100; x++)  {      delete(x);  } ``` | ```  int x;   for (x = 0; x < 100; x+=5)  {      delete(x);      delete(x+1);      delete(x+2);      delete(x+3);      delete(x+4);  } ``` |

この修正の結果、新たなプログラムのループ回数は 100 回から 20 回に削減される。ジャンプ命令と条件付分岐命令の実行回数は5分の1となり、ループそのものの処理にかかる時間は大幅に削減される可能性がある。その効果を最大にするため、展開されたコードではポインタ計算をしないようにすることが重要である。そのため通常はインデックスによる参照からベースとオフセットによる参照に転換する必要がある。

一方、ループ展開によってコードサイズは 3 行から 7 行に増え、コンパイラは展開された部分で必要となる変数を格納するレジスタをさらに必要とすることになる可能性がある。加えて、展開前と展開後で処理結果が同じになるように、ループ変数のループ内での操作は注意深く行わなければならない。例えば、上の例で 6 回ぶんのループを展開した場合、100 は 6 で割り切れないため、展開前と同じ結果を得るには細工が必要となる。また、ループの終了条件が変数だった場合にはさらに問題は複雑化する。Duff's device を参照されたい。

### 複雑性

単純なループでは、ループ制御は単なる管理オーバヘッドである。ループ自体は必要な結果に直接貢献することはなく、単にプログラマが同じコードをいくつもコーディングする手間を省くだけである。それだけであれば、コードの複製はプリプロセッサやエディタの機能を使っても実現できる。同様に `if` 文などの他の制御構造もコードの複製で置き換えることもできるが、結果として滅茶苦茶なコードが出来上がってしまう。プログラムは組み合わせに絶えず注意することができるが、人間は退屈な作業に我慢できず、間違いを犯す。

| 通常のループ | ループ展開後 |
| --- | --- |
| ```   for i:=1:8 do    if i mod 2 = 0 then do_evenstuff(i)                    else do_oddstuff(i);    next i; ``` | ```  do_oddstuff(1); do_evenstuff(2);  do_oddstuff(3); do_evenstuff(4);  do_oddstuff(5); do_evenstuff(6);  do_oddstuff(7); do_evenstuff(8); ``` |

しかし、もちろん展開される中身は手続き呼び出しである必要はない。次の例ではインデックス変数の計算が関わっている。

| 通常のループ | ループ展開後 |
| --- | --- |
| ```  x(1) = 1;  For i:=2:9 do            x(i):=x(i - 1)*i;            print i,x(i);            next i; ``` | ```  x(1):=1;  x(2):=x(1)*2; print 2,x(2);  x(3):=x(2)*3; print 3,x(3);  ...etc.  . ``` |

コンパイラのループ展開によって大量のコード(特に print 文)が生成されるとしても、更なる最適化が可能である。この例ではループ内で x(i) と x(i - 1) しか参照しておらず(後者は x(i) の値を作るためにのみ参照)、配列 x に他から参照することがないなら、配列の各要素を単純な変数に置き換えることもできる。しかもこのコードでは各変数の値を定数から求めていて、全て定数とみなすこともできる。すると次のように最適化できる。

コンパイラが x を階乗のテーブルだと認識したとしたら驚きである。

一般にループの中身は大きく、複雑な配列のインデックス付けに関連している。その場合は最適化コンパイラに展開を任せるのが最善であろう。最も内側のループを展開することで様々な最適化が可能となるかもしれないが、ループ回数が多くない限り効果は限定的である。

### WHILEループの展開

WHILEループの擬似コードの例を示す。

| 通常のループ | ループ展開後 | 展開し「調整」したループ |
| --- | --- | --- |
| ```   WHILE (condition) DO          action   ENDWHILE . . . . . . ``` | ```   WHILE (condition) DO          action          IF NOT(condition) THEN GOTO break          action          IF NOT(condition) THEN GOTO break          action  ENDWHILE  LABEL break: . ``` | ```  IF (condition) THEN   REPEAT {          action          IF NOT(condition) THEN GOTO break          action          IF NOT(condition) THEN GOTO break           action          } WHILE (condition)  LABEL break: ``` |

展開した例ではENDWHILE(コンパイルされるとループ先頭へのジャンプになる)の実行回数が66%少なくなり、高速化される。

さらに「調整」を加えた擬似コードの例では、最適化コンパイラを使えば無条件ジャンプを全く使わない形に最適化されるだろう。

## 動的ループ展開

ループ展開の有効性は対象となる配列の大きさに依存するが、実行時にならないとその大きさが判明しないことも多い。実行時コンパイラ (JIT) などは、通常のループにすべきか、展開すべきかを判断できる。ループ展開の観点では、この柔軟性が静的または手動の最適化に比べてJIT方式の強みとなっている。

アセンブリ言語では、効率的なジャンプテーブルを使うような技法で動的ループ展開を行うことができる。ここで重要となるのは、配列の最大オフセットが機械語命令で表せる範囲かどうかである。その範囲外の場合、最適化の効果が薄れる。次の例はSystem/360またはZ/Architectureのアセンブリ言語で書かれている。FROM配列とTO配列はそれぞれ1要素256バイトで50要素あり、各要素の先頭から100バイトをFROMからTOにコピーするものである。

### アセンブリ言語(System/360)の例

この例を通常の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) が配列の要素を指すのに使われているため、コンパイラはポインタ/インデックスの計算コードを生成することになる。最大限最適化するには、全てのインデックス指定を定数に置き換えなければならない。