共通部分式除去

共通部分式除去（きょうつうぶぶんしきじょきょ、英: Common subexpression elimination, CSE）は、計算機科学におけるコンパイラ最適化方法の一つで、同じ式 (すべて同じ値に評価される) の出現を探し出し、計算結果を格納する一つの変数に置き換える価値があるかどうかの解析を行うものである。

下記の例では、

a = b * c + g;
d = b * c * d;

コードが下記のように記述されたとして解釈できるよう変更すると、 (プログラムの実行が速くなるため)利点がある。

tmp = b * c;
a = tmp + g;
d = tmp * d;

最適化プログラムはコストと利点の解析を行い、tmpを格納するコストが複数回計算を行うコストより低いかどうかを計算する。実際には、どの値がどのレジスタに格納されるかといった要素も重要である。

上記のような単純な場合には、プログラマはコードを記述する際に重複した式を手動で除去してしまうことが多い。CSE の入力としてもっとも重要なものはコンパイラが出力する中間コードである。例えば配列のインデックス計算などで生成されるもので、開発者が介在して手動で除去することができない。また、言語の特徴によって重複した式が多数作られる場合もある。たとえばC言語のマクロでは、マクロの展開により元のコードに現れない共通部分式が生成される。

CSE を実行する利点は大きく、広く用いられる最適化手法である。

CSE ではコンパイラが値を一時的に格納する変数の数に関して十分賢いものである必要がある。膨大な一時変数を作成するとレジスタが枯渇し、メモリを使用する必要を生じる。単純な演算結果を必要に応じて再計算するより時間がかかってしまう場合もある。

コンパイラ開発者は二種類の CSE を区別している:

局所共通部分式除去 は一つのブロック内で動作するため実装が簡単な最適化方法である。
大域共通部分式除去 は手続きの全体で動作し、式が手続きのどこで利用可能になるかを解析するデータフロー解析の結果に依存する。

参考文献

Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, 1997) pp. 378-396
John Cocke. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.

関連項目

参考文献