定数畳み込み

定数畳み込み（ていすうたたみこみ、英: constant folding）および定数伝播（ていすうでんぱ、英: constant propagation）は、多くのコンパイラで使われている最適化技法である。定数伝播の進化したものを疎な条件分岐を考慮した定数伝播と呼び、定数伝播と同時にデッドコード削除も行って、より正確な伝播を行う。

定数畳み込み

定数畳み込みとは、定数式をコンパイル時に単純化する技法である。定数式の項は一般に単純なリテラル（例えば、整数 2）であるが、値が変更されない変数も定数式の項と見なせるし、明示的に定数とされる変数もある。次の文（C言語）を考えてみよう。

int i = 320 * 200 * 32;

最近^[いつ?]の多くのコンパイラは乗算命令を2つ生成することはしない。その代わりに、上記の右辺式を計算した結果を定数値（この場合、2,048,000）とし、コンパイル時に中間表現上でその値に置き換えてしまう。

一部のコンパイラでは初期に定数畳み込みを行うため、C言語の配列初期化などで簡単な数式を使うことが可能となっている。ただし、最適化の後の方の工程で再度、定数畳み込みを行うことが多い。

定数畳み込みはコンパイラのフロントエンドで中間表現データ構造を使って行われ、その後、3番地コードに変換される。あるいは、バックエンドで定数伝播に付随して行われる。

定数畳み込みとクロスコンパイル

クロスコンパイラの実装では、ホストシステムの算術的アーキテクチャがターゲットシステムのものと一致しているかどうかに注意する必要がある。一致していない場合、定数畳み込みによって数式の計算をホストシステム上で行ってしまうため、プログラムの振る舞いが変わってしまう可能性がある。特に浮動小数点演算について注意が必要である（精度などがアーキテクチャによって異なるため）。

定数伝播

定数伝播とは、コンパイル時に数式内の値を既知の定数値に置き換える技法である。定数としては、定数畳み込みで述べたようなものの他に、定数値を引数とした Intrinsic Function（コンパイラが関数呼び出しではなく、機械語に置き換えてしまうような関数）も定数となる。次のC言語コードを見てみよう。

int x = 14;
int y = 7 - x / 2;
return y * (28 / x + 2);

これに一回、定数伝播を適用すると、次のようになる。

int x = 14;
int y = 7 - 14 / 2;
return y * (28 / 14 + 2);

これに同時に定数畳み込みを施すことが多く、そうするとさらに単純化される。

定数伝播を行うと、条件分岐が無条件の文に単純化されることがある。これは、条件文の条件式がコンパイル時に評価されて、常に真または偽となることが確定した場合である。これをさらに一般化して、プログラム自体の変換と見たものが部分評価である。

実際の最適化

定数畳み込みと定数伝播は同時に行って、かつそれ以上変化が起きなくなるまで繰り返し実施することで、さらに効果が大きくなる。例として次のC言語コードを見てみよう。

int a = 30;
int b = 9 - a / 5;
int c;

c = b * 4;
if (c > 10) {
    c = c - 10;
}
return c * (60 / a);

定数伝播を一回行い、その後定数畳み込みを施すと、次のようになる。

int a = 30;
int b = 3;
int c;

c = 12;
if (c > 10) {
    c = c - 10;
}
return c * 2;

a と b は定数に単純化され、これらを参照していた箇所は全て定数に置換された。コンパイラはここでデッドコード削除を適用し、不要なコードを削除し、コードを次のようにする。

int c;

c = 12;
if (12 > 10) {
    c = 2;
}
return c * 2;

次に、if文の条件が常に真であることが判明し、かつ c も省くことが可能であることがわかる。従って、コードは次のように削減される。

return 4;

このコードが関数の定義そのものであった場合、コンパイラはさらにその知識を利用して、この関数を呼び出している箇所全てを定数 4 に置き換えて性能を向上させることが可能である。

参考文献

Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.

定数畳み込み

定数畳み込みとクロスコンパイル

定数伝播

実際の最適化

関連項目

参考文献