The 8 Compiler Optimizations

こちらのスライドで、コンパイラは8つの最適化を実装すれば十分だと述べられています。(いろいろな最適化がまとまった論文としてこちらが紹介されています。)
ここでは、これら8つの最適化をまとめていきます。

8つと述べましたが、正確には8つくらいですね。

Inline, Unroll (& Vectorize), CSE, DCE, Code Motion, Constant Fold, Peephole.

WIP

Inline, インライン展開

Unroll, ループアンローリング, ループ展開

その名の通り、ループの中身を展開する最適化です。
例えば以下のような変形を行います。（以下ではループの回数が定数ですが、動的に変化しても大丈夫です）

# before
for (int i = 0; i < 4; i++)
  a[i] = i;
# after
a[0] = 0;
a[1] = 1;
a[2] = 2;
a[3] = 3;

この最適化の利点は例えば以下があります。

• 分岐が減る（ため速くなるかもしれない）
• 命令レベルの並列性がある場合、その効果を享受できる

しかしながら、ループを展開するとコード量が増えるため、それに起因する欠点も生まれます。キャッシュミスの増加や、ループ内に複雑な制御フローが含まれていると分岐予測が当たりづらくなることなどが具体例です。

Vectorize, ベクトル化

CSE (Common Subexpression Elimination), 共通部分式除去

DCE (Dead Code Elimination), デッドコード除去

Code Motion, コード移動

Constant Fold, 定数畳み込み

定数の計算をコンパイル時に実行する最適化です。
具体的には、以下のような変形を行います。

# before
a = 3 + 2
b = a + 1
# after
a = 5
b = a + 1

ここで、共によく用いられる Constant Propagation (定数伝播) を用いると、さらに以下のように変形できます。

# before
a = 5
b = a + 1
# after
a = 5
b = 6

Peephole, ピープホール最適化

参考文献

• 中田 育男(2009), コンパイラの構成と最適化, 朝倉書店