編譯器中激進蝴蝶優化方法的研究與實現*

朱廣林,呂 方,賴慶寬,陳華英,何先波

(1.中國科學院計算技術研究所計算機體系結構國家重點實驗室，北京 100190;2.西華師范大學計算機學院，四川 南充 637009;3.中國民用航空飛行學院，四川 廣漢 618307)

1 引言

冗余代碼是程序中較為常見的問題，通過動態、靜態分析以及插樁方法都能定位到一些冗余代碼，可以輔助編譯器進行冗余代碼刪除操作。但是，受限于保守的分析手段，編譯器中仍有一部分冗余代碼無法被發現，以至于無法對其優化。而程序中的冗余代碼會致使布局優化難以實施，甚至會導致嚴重的寄存器溢出等問題。

編譯優化是非常成熟的領域，國內清華大學、中國科學院計算技術研究所以及國防科技大學和江南計算所等都有相關的研究和積累。例如，清華大學Zhou等人[1]將最小割法應用于控制流圖形成的流網絡中，提出了最小割法的靜態單賦值部分冗余消除MC-SSAPRE(Min-Cut Static Single Assignment Partial Redundancy Elimination)算法，以獲得部分冗余消除的最大收益；周虎成[2]研究總結了現有的冗余消除優化研究中存在的局限性，提出了有效的優化方法，降低了數據流分析的復雜度。計算技術研究所Lü等人[3]提出一種空閑寄存器利用的代碼優化方法，能夠有效減少寄存器溢出。但是，針對冗余代碼的優化研究仍然有繼續深挖的必要性。

編譯器的優化性能受諸多因素影響，如何使編譯器結合處理器架構，將應用程序的性能最大化地發揮出來，是一個值得探索的方向。程序代碼在編譯器中的表示形式對編譯器的優化性能有較大的影響，程序中的某些代碼重用或是優化處理，可能會導致無效代碼的出現[4]。無效代碼是程序中不會被訪問到的變量或不會被執行到的代碼塊，消除無效代碼可以通過刪除程序中那些不影響運行結果的部分，以節省代碼占用的內存空間，提高程序執行效率。編譯器中的無效代碼刪除算法依賴數據流分析技術，該算法利用收集的全局信息，通過刪除無效變量或代碼塊，調整程序的控制流程圖，從而為優化公共子表達式刪除、循環等創造條件[5]。GCC編譯器中保守的無效代碼刪除和常量傳播優化，在函數調用層數或結構體層數太多、復雜度太高時，優化效果存在一定的局限性。

本文提出一種依賴數據流分析的激進蝴蝶優化方法，作為無效代碼刪除優化的一個動態擴展方案，側重解決分支路徑與運行時輸入參數值相關的這類應用程序的優化問題。該方法利用靜態單賦值SSA(Static Single Assignment)中間表示，根據動態運行時輸入參數的傳遞過程，分析出特定區域中關鍵變量的可能值，結合變量值，自動為程序生成多個代碼形狀類似蝴蝶(butterfly)的分支代碼，稱為butterfly分支，使編譯器在程序編譯階段，構建出所有可能的流程分支。最后通過分析驗證了該方法的可行性，并在SPEC CPU 2017上進行實驗測試取得了一定的性能提升。

2 相關工作

隨著機器學習技術的日趨成熟和在各領域的廣泛應用，AI編譯器也呈現出蓬勃發展的態勢，AI編譯器優化技術的研究也愈加被重視。寒武紀針對智能處理器架構而設計的BANG語言及其編譯工具鏈，提升了智能計算編譯器的開發效率。華為為解決安卓系統碎片化問題研發了方舟編譯器。阿里巴巴和騰訊等眾多企業都為智能芯片搭載了相應的編譯器。編譯優化技術也越來越趨向自動化和智能化。例如，為在眾多優化方法中預測出程序最佳的編譯優化參數組合，Ballal等人[6]提出一種迭代編譯的遺傳算法;劉慧等人[7]通過使用監督學習的方法對函數特征進行提取，并建立了學習模型以對程序最佳優化參數組合進行預測。而文獻[8]則是直接基于GCC開發更高效的機器學習編譯器Milepost GCC，并經過系列優化后能更好地減小代碼大小和縮短編譯時間，提高程序執行效率。

在傳統的編譯器優化技術中，數據流分析方法被應用于常量傳播、無效代碼刪除、向量化優化、并行化和冗余刪除等諸多程序優化技術中。數據流描述的是操作和數據之間的關系，由控制流圖CFG(Control Flow Graph)、基本塊(basic_block)等要素組成。在關于數據流分析問題的研究中，連瑞琦等人[9]提出一種增量式數據流分析方法，該方法解決了數據流信息的失效和重算等問題，能更好地處理、維護數據流信息。Li等人[10]采用運行時數據流信息消除并行編譯器中無效代碼引起的不準確問題。汪小飛等人[11]介紹了數據流方程的幾種求解方法，給出了最常用的迭代求解算法的具體實現，并簡要分析了GCC編譯器中的數據流分析實現方法。楊小川等人[12]根據分析關鍵變量的數據流信息，提出了一種程序切片技術，通過該技術能更好地利用編譯時信息，減小程序的規模。

基于數據流分析方法的靜態單賦值SSA表示在現代編譯器甚至是虛擬機中都有著極其重要的作用，它的出現使數據流分析和優化算法實現更容易。文獻[1]提出了MC-SSAPRE算法，以獲得部分冗余消除的最大收益。文獻[2]研究總結了現有的冗余消除優化中存在的局限性，提出了更為有效的優化方法。文獻[13]根據數據流分析結果，針對部分冗余消除優化進行了論述和變換證明。文獻[14]提出基于代碼動作擴展的部分無效代碼刪除，有效提高了優化效率。

3 激進蝴蝶優化方法的設計與實現

3.1 總體設計

程序的總體設計示意圖如圖1所示，假設指定代碼區域在函數functionA中，該區域程序的流程分支與type參數的取值相關，且依賴于運行時參數，可能值為a、b或c，只有當type值為b時才是有效的流程分支；而當type值為a或者c時，該區域代碼為無效代碼，此時不再需要進行邏輯運算，可以直接刪除。因此，通過設計butterfly優化，對該區域代碼創建條件分別為type等于a，b和c的3個流程分支，使程序在編譯期為代碼可能的參數值生成條件分支，在程序運行時根據輸入參數值可以直接運行正確的流程分支，從而避免代碼中不必要的邏輯運算。

Figure 1 Schematic diagram of the overall design of the program

3.2 SSA中間表示介紹

靜態單賦值(SSA)表示是和前端語言與目標機器無關的一種中間表示，它在程序的編譯過程中對每條語句的變量定義一個唯一的名稱[15]。通過使用靜態單賦值中間表示能簡化程序的全局過程間優化，它消除了復雜的尋址方式和指令語義的副作用[16]，是一種不可或缺的全局過程間數據流分析形式，不管是GCC、LLVM這些開源編譯器或是ICC、AOCC等商業編譯器都在使用SSA形式的中間表示[17]。

GCC中的Tree-SSA包含原始程序的完整控制、數據和類型信息，是一種基于SSA表示的擴展型框架，它對GCC的樹表示進行操作[18]。GIMPLE中間表示轉換為SSA中間表示之后經過了多個SSA pass優化才轉換為寄存器傳輸語言RTL(Register Transform Language)中間表示，然后在RTL上根據機器模型進行指令選擇并輸出最終的目標文件。

3.3 構建butterfly分支

butterfly分支由控制流圖的基本塊(basic_block)復制而來。程序控制流圖中一個流程分支的基本塊從另一部分復制而來，再通過獲取變量最終所有可能的值、切分原始基本塊之間的連接邊、創建條件基本塊并構建then分支和else分支以形成具有2個或多個流程分支的控制流程圖，它的每一個分支即稱為butterfly分支。

構建butterfly分支是該方法的核心部分，通過對程序的指定區域創建條件判斷語句，構建出butterfly分支，調整修復控制流圖，并更新SSA的PHI節點信息，得到的代碼中包含了幾個流程分支條件及其對應分支代碼，再經過常量傳播、無效數據刪除等全局優化之后簡化控制流。這一系列操作在編譯器的編譯階段進行，在程序的運行階段會根據輸入的參數值，找到正確的流程分支，從而簡化程序中不必要的邏輯運算，減少運行時間，以此達到對程序優化的目的。

如圖2所示是具有2個butterfly分支的控制流圖抽象模型。圖2中包含了原始代碼的控制流圖和進行butterfly優化之后的控制流圖。

Figure 2 Abstract model of butterfly control flow graph

圖2a是一個簡化的程序控制流圖，其包含1個entry_bb、1個exit_bb和程序的主體代碼基本塊，它們分別通過ENTRY_EDGE、EXIT_EDGE和ORIG_BBS進行關聯。圖2b所示是將源碼控制流圖抽象成butterfly的設計模式，corig_bbs是根據orig_bbs復制而來的代碼主要邏輯部分，作為條件語句塊cond_bb2的then分支，false_bb是由orig_bbs中EXIT基本塊的前置基本塊復制而來，作為條件語句塊cond_bb2的else分支，條件語句塊cond_bb1和cond_bb2是根據參數的2個可能值創建出的基本塊，cond_bb2作為cond_bb1的else分支，orig_bbs基本塊作為條件語句塊cond_bb1的then分支。

若判斷出參數有多個可能的值，需要對程序代碼創建多個分支結構，則可按照該butterfly的控制流圖模型繼續創建條件基本塊cond_bb3，并添加其then分支和else分支代碼。如圖3所示，條件基本塊cond_bb2的else分支指向一個新創建的基本塊，以此形成一個新的語句分支，表明該方法在復雜的控制流結構中的適用性。

Figure 3 Abstract model of control flow graph with multiple of possible values of parameters

3.4 與其它優化組合

在GCC編譯器中Tree-SSA上進行的優化包括：無效數據刪除、無效指令和存儲刪除、公共子表達式消除、部分循環優化以及常量傳播等。本文提出的激進蝴蝶優化方法處于SSA優化pass的前期部分，能有效結合SSA中間表示上的其余優化，最大化地發揮出組合優化的性能。LLVM編譯器中的SSA中間表示是各階段使用的通用代碼，貫穿于整個中間過程，眾多優化pass都在SSA上進行，該方法能有效結合其它優化方法，發揮出優化效果。

對于一些邏輯相對較復雜的程序代碼，采用激進蝴蝶優化方法對局部代碼構建butterfly分支后，代碼中包含參數取值的流程分支。在程序運行時這些流程分支中只有一個會被執行，這便會促進SSA上眾多優化操作的進行。對于邏輯相對較簡單的程序，通過控制流分析或相關支配關系優化，可以找出程序中的部分常量和不可訪問的代碼段，直接刪除無效代碼段，從而達到優化效果。

4 實驗與結果分析

4.1 實驗平臺

為了對本文提出的激進蝴蝶優化方法的可行性和有效性進行評估，本文主要采用GCC編譯器進行實驗，將優化方法應用到GCC 8.2.0編譯器，在Intel的Ubuntu Linux和AMD的Red Hat Linux 2種平臺上，對優化前后的GCC 8.2.0編譯器進行實驗。表1給出了實驗中所使用平臺的主要信息。

Table 1 Main information of the experimental platform

在Intel和AMD 2種平臺上，對GCC 8.2.0編譯器進行SPEC CPU 2017基準測試。SPEC CPU 2017包含43個基準測試套件，涵蓋區域海洋模擬、天氣預報等眾多領域，是一套被國際上廣泛用于評估編譯器性能的標準測試套件[19,20]。選定優化前GCC 8.2.0編譯器為參考編譯器(base compiler)，優化后的GCC 8.2.0編譯器為目標編譯器(target compiler)，使用ref輸入數據集進行基準測試。

采用測試結果的ratio值來進行編譯器優化前后的性能對比，根據式(1)，以參考編譯器運行benchmark得出的ratio值為基準，根據目標編譯器運行benchmark得出的ratio值計算出目標編譯器的性能提升比ratiospeedup。

(1)

4.2 方法的可行性分析

在可行性方面，采用優化前的編譯器編譯經手工修改的代碼，若得到的關鍵中間表示與優化后的編譯器編譯原始代碼得到的關鍵中間表示一致，說明該方法可行。

下面列舉了一個示例程序以及該示例程序的源碼butterfly變換：

示例代碼：

long functionA(const Typetype){

longi;

longresult=0;

longresult1=0;

unsignedj=0;

for(j=0;j<100000;++j){

for(i=0;i

inttemp;

get_value(i,&temp);

result+=temp;

}

}

if(type&type1){

result1=getResult(result);

}

returnresult1;

}

源碼butterfly變換：

long functionA(const Typetype){

longi;

longresult=0;

longresult1=0;

unsignedj=0;

if(type==type1){

for(j=0;j<100000;++j){

for(i=0;i

inttemp;

get_value(i,&temp);

result+=temp;

}

}

if(type&type1){

result1=getResult(result);

}

}

if(type==type2){

……

}

returnresult1;

}

示例代碼描述了一個循環計算的熱區域，for循環在某種常數參數下為冗余代碼，其計算結果result在其后的條件判斷中使用。條件語句中參數type的取值與運行時輸入的參數值相關，該參數的可能值為type1和type2。源碼butterfly變換是根據type1和type2這2個取值來創建2個代碼分支，一個進行激進冗余刪除優化，另一個維持原有保守設計，確保非常數參數條件下的正確性。

以上述代碼為實驗代碼，進行2組對照實驗，以對比編譯器優化前后的控制流程圖。圖4a所示為采用優化后的編譯器編譯示例代碼所得到的控制流程圖。圖4b所示是對上述源碼butterfly變換后的代碼采用優化前的編譯器進行編譯所得到的控制流程圖。

圖4a示例代碼的控制流圖中return語句所在的基本塊和得到結果值的基本塊被合并為bb17，所以比圖4b少一個基本塊bb18。從實驗結果可以看出，編譯器優化前后的控制流圖一致，通過對比分析其匯編碼也有相似的結構，由此說明該優化方法可行。

Figure 4 Control flow graph before and after compiler optimization

4.3 方法的有效性分析

在方法的有效性方面，主要通過在Intel和AMD的2個平臺上分別進行基準測試，觀察其性能表現。第1組實驗在Intel平臺上進行，分別使用優化前GCC和優化后的GCC對SPEC CPU 2017進行ref數據集的浮點測試；第2組實驗在AMD平臺上進行，同樣采用優化前后的GCC進行ref數據集的浮點測試，分別得出在638.imagick_s測試用例上的ratio值。

根據式(1)對實驗的ratio值進行計算得到性能提升比，如圖5所示。實驗數據表明，對于638.imagick_s測試用例，在Intel平臺上，優化改進后的GCC 8.2.0性能提升比達到了26%，在AMD平臺上的性能提升比達到了25%，該優化方法的有效性得到了驗證。

Figure 5 Performance comparison of dead code elimination optimization dynamic extension technology of 638 imagick_s benchmark on Intel and AMD platforms

綜合以上實驗論述，驗證了本文提出的激進蝴蝶優化方法的可行性和有效性。通過對程序代碼塊構建butterfly分支可以有效進行無效代碼的刪除，達到提升程序性能的目的。

5 結束語

本文提出一種依賴數據流分析的激進蝴蝶優化方法，作為無效代碼刪除優化的一個動態擴展方案，最后通過實驗驗證了該方法在GCC編譯器上的可行性和有效性。該方法利用SSA中間表示，根據動態運行時輸入參數的傳遞過程，分析出特定區域中關鍵變量的可能值，結合變量值，自動為程序生成多個代碼形狀類似butterfly的分支代碼，使編譯器在程序編譯階段為無效代碼刪除等相關組合優化提供可行的優化依據。該方法通過構建butterfly分支能調整程序的控制流程圖，以促進其它優化的進行。接下來的工作是優化改進該方法，使其能在更多的程序中發揮優化作用，并且能做出更激進的優化，更自動化的判斷。