編譯器優化–5--消除備援

關于消除備援，我們着這裡隻讨論在局部範圍内（單個程式塊）上的消除備援。做這種優化一般常用兩種方法：

值編号（value numbering）

，

樹高平衡（tree-height balancing）

。我這這裡詳細讨論關于

值編号（value numbering）

的技術細節。

局部值編号（Local Value Numbering，LVN）

定義：對于基本程式塊B中的一個表達式，當且僅當它在B中此前已經計算過，且在此之間并無其他運算重新定義組成表達式的各個參數值時，則稱該表達式是備援的。

例子1

基本程式塊如下：

a ← b + c b ← a − d c ← b + c d ← a − d \begin{aligned}a &\leftarrow b + c\\b &\leftarrow a - d\\c &\leftarrow b + c\\d &\leftarrow a - d\\\end{aligned} abcd​←b+c←a−d←b+c←a−d​

在上面例子中第3個運算中出現 b + c b + c b+c不是備援的，因為第2個運算重新定義了b。第4個運算中出現的 a − d a-d a−d是備援的，因為在第2個和第4個運算之間沒有重新定義表達式中的參數a或d。

編譯器在優化時會重寫該基本程式塊，使得隻對 a − d a-d a−d僅運算一次。如下圖所示

a ← b + c b ← a − d c ← b + c d ← b \begin{aligned}a &\leftarrow b + c\\b &\leftarrow a - d\\c &\leftarrow b + c\\d &\leftarrow b\\\end{aligned} abcd​←b+c←a−d←b+c←b​

例子2

前一個例子中，備援表達式的文本與先前計算過的表達式是相同的。另外還有其他情況，比如：假設已經分析出 d d d右側的表達式是備援的，可以使用 b b b的值直接替換它，使得 d ← b d \leftarrow b d←b。整個基本程式塊如下所示：

a ← b + c b ← a − d c ← b + c d ← b e ← d + c \begin{aligned}a &\leftarrow b + c\\b &\leftarrow a - d\\c &\leftarrow b + c\\d &\leftarrow b\\e &\leftarrow d + c\\\end{aligned} abcde​←b+c←a−d←b+c←b←d+c​

對于上面程式塊B中的第3條語句和第5條語句中 b + c b + c b+c和 d + c d + c d+c表達式的值是相同的。為了識别這種情形，編譯器必須跟蹤值通過名字發生的流動。這種情況，如果僅依賴基于比較文本是否相同的技術是無法檢測出來的。

算法

程式員可能會說，如上面兩個例子，他們是不會編寫出包含這種備援表達式的代碼。實際上，從源碼到IR的轉換會細化許多細節（如位址計算）并引入備援表達式，

備援消除

是可以找到許多優化時機的。

人們已經開發出了許多用于發現并消除備援的技術。

局部值編号（Local Value Numbering）

是這些變換中最古老也最強大的技術之一。它可以發現基本程式塊内部的備援，并重寫該程式塊避免備援。它為其他局部優化（如常量合并和使用代數恒等式進行簡化）提供了一套簡單且高效的架構。

值編号背後的思想很簡單。算法周遊基本程式塊，并為程式塊計算的每個值配置設定一個不同的編号。該算法會為值選擇編号，使得給定兩個表達式 e i e_i ei​和 e j e_j ej​，當且僅當對表達式的所有可能的運算對象，都可以驗證 e i e_i ei​和 e j e_j ej​具有相等的值時，兩者具有相同的值編号。

下面給出了基本的LVN算法的僞代碼。

for i in range(0, n-1), where the block has n operations "Ti = li Opi Ri"
    1. get the value numbers for Li and Ri
    2. construct a hash key from Opi and the value numbers for Li and Ri
    3. if the hash key is already present in the table then
           replace operation i with a copy of the value into Ti and associate the value number with Ti
       else
           insert a new value number into the table at the hash key location record that new value number for Ti

           

LVN的輸入是一個具有n個二進制運算的基本程式塊，每個運算符形如 T i = L i   O p i   R i T_i = L_i\ Op_i\ R_i Ti​=Li​ Opi​ Ri​。LVN算法會按照順序考擦每個運算。它使用一個散清單來将名字、常數和表達式映射到不同的值編号。該散清單最初是空的。

為處理第 i i i個運算，LVN在散清單中查找 L i L_i Li​和 R i R_i Ri​，擷取與二者對應的值編号。如果算法找到對應的項，LVN将使用該項包含的值編号；否則，算法将建立一個表項并配置設定一個新的值編号。

給出 L i L_i Li​和 R i R_i Ri​的值編号，分别記作 V N ( L i ) VN(L_i) VN(Li​)和 V N ( R i ) VN(R_i) VN(Ri​)，LVN算法會基于 ( V N ( L i ) , O p i , V N ( R i ) ) (VN(L_i), Op_i, VN(R_i)) (VN(Li​),Opi​,VN(Ri​))構造一個散清單的鍵，并在表中查找該鍵。如果存在對應的表項，那麼該表達式是備援的，可以将其替換為對此前計算值的引用；否則，運算 i i i是該程式塊中對此表達式的第一次計算，随後LVN會對應的散列鍵建立一個散清單項，并為該表項配置設定一個新的值編号。算法還将散列鍵的值編号（新的或現存的）配置設定給對應的 T i T_i Ti​的表項。因為LVN使用值編号而非名字來構造表達式的散列鍵，它實際上可以通過複制和指派操作來跟蹤值的流動，它可以解決如前面第2個例子的情形。将LVN擴充到任意元表達式是很簡單的。

對于之前給出的LVN算法僞代碼還有很多需要完善可考慮的地方如：

1. 将LVN算法擴充到任意元表達式；

2. 交換運算

   的問題，如（ a ∗ b a * b a∗b和 b ∗ a b * a b∗a），兩者應該配置設定同樣的值編号；
3. 常量的求值及合并；
4. 代數恒等式，如（$ x + 0 \equiv x$）等；
5. 命名的影響；
6. 間接指派的影響；

想要完整的實作LVN的算法，需要考慮以上6點甚至更多。在此我就不在深入闡述關于LVN的更多細節

有興趣對LVN深挖的讀者可以參考《Engineering a Compiler》的第8.4章節。

參考

《編譯原理》

《Engineering a Compiler》