公共子表達式消除

公共子表達式消除，又稱CSE（Common subexpression elimination），是一個編譯器優化技術。在執行這項優化的過程中，編譯器會視情況將多個相同的表達式替換成一個變量，這個變量存儲着計算該表達式後所得到的值。 該優化技術十分常見，在現代各大編譯器中（如LLVM、GCC）均有實現。

例子

考慮到下列代碼：

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

可以觀察到 b * c 是兩項表達式中的公共子表達式。如果計算這個子表達式並將其計算結果存儲起來的開銷，低於重複計算這個子表達式的開銷，則能夠將以上代碼轉換成以下代碼：

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

原理

執行這項優化的可能性基於表達式的定義可達性。當以下條件成立，則一個表達式 $b*c$ 在程序的某個點 $p$ 被定義為是可達的：

• 從初始節點到點 $p$ 的每條路徑在到達 $p$ 之前計算過 $b*c$；
• $b*c$ 被計算後，無論 $b$ 或 $c$ 到點 $p$ 以前都沒有被重新賦值過。

由編譯器計算的成本效益分析可以判斷出，重複計算該表達式的開銷是否大於存儲該表達式的計算結果，並且這個分析也要將寄存器等因素考慮在內。

編譯器開發者將公共子表達式消除分成兩種：

• 本地公共子表達式消除：這項優化技術工作於基本塊之內。
• 全局公共子表達式消除：這項優化技術工作於整個過程之中。