Loading article…
コンパイラ理論において、共通部分式除去（CSE）は、同一の式（つまり、すべて同じ値に評価される式）のインスタンスを探し、計算された値を保持する単一の変数でそれらを置き換える価値があるかどうかを分析するコンパイラ最適化です。[ 1 ]
以下のコードでは：
a = b * c + g; d = b * c * e;
コードを以下のように変更する価値があるかもしれません。
tmp = b * c; a = tmp + g; d = tmp * e;
保管および検索にかかる費用が、追加時間tmpを計算する費用よりも少ない場合。b * c
CSEを実行できるかどうかは、利用可能な式解析（データフロー解析）に基づいています。プログラム内のb*cポイントpで式が利用可能であるのは、以下の条件を満たす場合です。
b*cに到達する前に評価されます。b割り当てはありません。c最適化ツールによって実行される費用対効果分析では、格納のコストがtmp乗算のコストよりも低いかどうかを計算します。実際には、どのレジスタにどの値が保持されているかなど、他の要因も重要になります。
コンパイラ開発者は、CSEを2種類に分類します。
どちらの方法も、プログラムのどの時点でどの式が使用可能かというデータフロー分析に依存している。
CSEを実行することのメリットは非常に大きいため、これは一般的に用いられる最適化手法となっている。
上記の例のような単純なケースでは、プログラマーはコードを書く際に重複する式を手動で削除することができます。しかし、CSE（共通部分式）の最大の原因は、コンパイラによって生成される中間コードシーケンスです。配列のインデックス計算などでは、開発者が手動で介入することはできません。また、言語機能によって多くの重複式が生成される場合もあります。例えば、C言語のマクロでは、マクロ展開によって元のソースコードには現れない共通部分式が生成されることがあります。
コンパイラは、値を保持するために作成される一時変数の数を慎重に判断する必要があります。一時変数が多すぎるとレジスタに負荷がかかり、レジスタからメモリへのスピルが発生する可能性があり、必要なときに算術演算結果を再計算するよりも時間がかかる場合があります。