公共子表達式消除

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

例子

編輯

考慮到下列代碼:

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

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

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

原理

編輯

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

  • 從初始節點到點   的每條路徑在到達   之前計算過  
  •   被計算後,無論    到點   以前都沒有被重新賦值過。

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

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

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

參考資料

編輯
  1. ^ Steven Muchnick; Muchnick and Associates. Advanced Compiler Design Implementation. Morgan Kaufmann. 15 August 1997. ISBN 978-1-55860-320-2. Common subexpression elimination.