Global Code Motion?/ Global Value Numbering

Introduction

????????本文認(rèn)為編譯器中機(jī)器獨(dú)立的優(yōu)化應(yīng)當(dāng)與代碼移動(dòng)分離，可以令這些優(yōu)化使用更簡(jiǎn)單的算法并提供更好的效果，因?yàn)榫S護(hù)合法的指令調(diào)度是PRE等算法復(fù)雜度的主要來源。

????????文章中提出了接近線性時(shí)間全局代碼移動(dòng)（GCM）算法，需要兩次遍歷。GCM算法將指令移出循環(huán)外至控制依賴盡可能多的基本塊，可能增加程序的路徑長(zhǎng)度，但減少了循環(huán)執(zhí)行指令的次數(shù)，因此不能保證最優(yōu)。GCM算法只使用指令間的依賴關(guān)系，并且不改變控制流圖（CFG），因此可以在該算法前使用一個(gè)更加簡(jiǎn)單高效的全局值編號(hào)算法?(GVN)。

????????GVN算法試圖將程序中計(jì)算相同值的所有指令替換為單一一條指令，通過哈希表判斷指令間是否相同，只需要一次遍歷。GVN算法不能保證替換后的調(diào)度正確性，因此很適合后接GCM算法。

Global Code Motion

????????算法的基本流程：1）計(jì)算CFG的支配樹，并在基本塊上標(biāo)記其支配樹上的深度；2）尋找循環(huán)，并對(duì)每個(gè)基本塊計(jì)算嵌套深度；3）對(duì)所有指令進(jìn)行early調(diào)度，移動(dòng)至第一個(gè)被該指令的輸入所支配的基本塊，這會(huì)導(dǎo)致大量的投機(jī)代碼；4）對(duì)所有指令進(jìn)行l(wèi)ate調(diào)度，找到最后一個(gè)可以支配該指令所有use的基本塊；5）將指令移動(dòng)至early和late之間的基本塊中，使得循環(huán)嵌套盡可能淺、控制依賴盡可能多。

Schedule Early

????????early調(diào)度將所有指令盡可能移至前面的基本塊，除非指令由于控制依賴被固定在了特定的基本塊，例如PHI、BRANCH、JUMP、RETUREN，此外中斷指令也無法被提前。

????????early調(diào)度對(duì)每條指令，使用后序的DFS遞歸地遍歷一條指令的所有輸入。當(dāng)指令的所有輸入都完成調(diào)度后，再對(duì)該指令進(jìn)行調(diào)度，移動(dòng)至在支配樹最深的輸入的基本塊。

????????這會(huì)產(chǎn)生一個(gè)問題，即一個(gè)指令的輸入不一定支配該指令，因此算法可能會(huì)錯(cuò)誤地將指令移至一個(gè)不支配其原本所在基本塊的基本塊中。因此，需要在程序的SSA中保留一些額外的PHI指令，令GVN算法忽略類似的模式，防止被消除冗余。

Schedule Late

????????late調(diào)度對(duì)指令的所有use在支配樹中計(jì)算最低共同祖先（LCA），? 即為指令最后一個(gè)合法的位置。該指令在支配樹中第一個(gè)合法位置與最后一個(gè)合法位置之間的所有基本塊即為可移動(dòng)的范圍，算法選擇其中循環(huán)嵌套最淺、最靠后的基本塊進(jìn)行指令移動(dòng)。

????????大部分指令的use和指令本身處于同一個(gè)基本塊中，但當(dāng)use為PHI指令時(shí)，應(yīng)計(jì)算PHI的input，其出現(xiàn)在CFG相應(yīng)的前驅(qū)基本塊中，在算法中需要特殊處理。（此處文章原文與給出的偽代碼相互矛盾，筆記中采用偽代碼的邏輯）

????????計(jì)算LCA的算法使用了一種簡(jiǎn)單的線性搜索算法。（此處文章中給出的偽代碼似乎有錯(cuò)誤）

????????對(duì)于如何在合法區(qū)間內(nèi)移動(dòng)指令，文章使用的啟發(fā)式算法選擇其中循環(huán)嵌套最淺、最靠后的基本塊進(jìn)行指令移動(dòng)。由于移動(dòng)一條指令后，會(huì)對(duì)其他指令的合法區(qū)間產(chǎn)生影響，因此在對(duì)一條指令完成late調(diào)度后隨即確定最終的位置。

Global Value Numbering

????????GVN算法使用自底向上的、基于哈希表的算法，遍歷每一條指令并在哈希表中查找?；玖鞒虨椋?）按照依賴邊逆后序遍歷所有指令；2）對(duì)每條指令嘗試使用哈希表進(jìn)行常量折疊、識(shí)別代數(shù)恒等變換、尋找等價(jià)指令。由于循環(huán)的存在，一次逆后序遍歷不能達(dá)到不動(dòng)點(diǎn)，因此遍歷第二次可能帶來提升，但一次遍歷的效果已經(jīng)足夠好。

????????具體來說，算法首先對(duì)指令嘗試進(jìn)行常量折疊，若成功，則將指令存入哈希表并替換為常量。判斷指令是否僅僅對(duì)輸入的代數(shù)變量進(jìn)行復(fù)制，若是，則將該指令的所有use替換為原變量。對(duì)指令的輸入和運(yùn)算符進(jìn)行哈希，在哈希表中尋找是否有進(jìn)行相同計(jì)算的指令，若命中，將該指令的所有use替換為哈希表中找到的指令；若未命中，則將該指令加入哈希表。

Experiments

????????文章在最后比較了多種情況下GVN-GCM和GCF-PRE-CCP的聯(lián)合優(yōu)化效果，結(jié)果表明，在給定的測(cè)試程序上，GVN-GCM在大多數(shù)情況下均取得了更好的效果。

參考文獻(xiàn)

[1] CLICK C. Global code motion/global value numbering[J/OL]. ACM SIGPLAN Notices, 1995, 30(6): 246-257. https://doi.org/10.1145/223428.207154.