共同子運算式消除(common-subexpression elimination)
/ CSE /
如果食譜說「加入(麵粉乘 2)杯,稍後再加(麵粉乘 2)杯」,你會把麵粉乘 2 算一次並重用,而不是乘兩次。共同子運算式消除(CSE)就是編譯器正在做這件事:找出它已經算過、且輸入未改變的運算式,重用稍早的結果,而不是再算一次。
編譯器掃描 IR,尋找同一個運算式出現兩次以上——相同操作、相同運算元——且運算元保證在兩處持有相同的值(其間沒有任何一個被重新指派)。當它找到這樣一對,它把運算式算一次存進臨時變數,並用那個臨時變數取代後面的出現。所以 a = (x + y) * z; b = (x + y) * w; 變成 t = x + y; a = t * z; b = t * w;,省下一次加法。現代編譯器通常透過全域值編號(global value numbering)來實作,它為整個函式中可證明相等的運算式指派相同的內部「編號」,連跨分支的冗餘都能抓到,而不只是同一條直線內。
它重要在於:一旦巨集、內聯與陣列索引算術展開,冗餘計算到處都是——同一個位址計算或子運算式反覆出現,CSE 把它合併。一個提醒:CSE 只有在兩次計算確實給出相同結果時才有效,所以編譯器必須尊重可能的副作用與別名。如果兩者之間有東西可能改變一個運算元(透過可能別名 x 的指標的儲存、或可能修改它的函式呼叫),這些子運算式就不「共同」,CSE 不可觸發。而重用一個值有時會延長它的生存期,可能增加暫存器壓力——消除一次便宜的重算並非無條件是勝利。
a = (x + y) * z; b = (x + y) * w; // CSE 把 x + y 算一次: t = x + y; a = t * z; b = t * w; // 第二次的 x + y 消失了
x + y 被算一次存進 t 並重用,前提是 x 與 y 在兩次使用之間都沒有改變。
CSE 只在運算元於兩次計算間可證明未改變時才觸發:中間透過可能別名的指標的儲存、或有副作用的呼叫都會擋住它,所以弱的別名分析可能讓明顯的冗餘留在原地。