編譯器中激進(jìn)蝴蝶優(yōu)化方法的研究與實(shí)現(xiàn)*

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

(1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190;2.西華師范大學(xué)計(jì)算機(jī)學(xué)院，四川 南充 637009;3.中國(guó)民用航空飛行學(xué)院，四川 廣漢 618307)

1 引言

冗余代碼是程序中較為常見(jiàn)的問(wèn)題，通過(guò)動(dòng)態(tài)、靜態(tài)分析以及插樁方法都能定位到一些冗余代碼，可以輔助編譯器進(jìn)行冗余代碼刪除操作。但是，受限于保守的分析手段，編譯器中仍有一部分冗余代碼無(wú)法被發(fā)現(xiàn)，以至于無(wú)法對(duì)其優(yōu)化。而程序中的冗余代碼會(huì)致使布局優(yōu)化難以實(shí)施，甚至?xí)?dǎo)致嚴(yán)重的寄存器溢出等問(wèn)題。

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

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

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

2 相關(guān)工作

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

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

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

3 激進(jìn)蝴蝶優(yōu)化方法的設(shè)計(jì)與實(shí)現(xiàn)

3.1 總體設(shè)計(jì)

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

Figure 1 Schematic diagram of the overall design of the program

3.2 SSA中間表示介紹

靜態(tài)單賦值(SSA)表示是和前端語(yǔ)言與目標(biāo)機(jī)器無(wú)關(guān)的一種中間表示，它在程序的編譯過(guò)程中對(duì)每條語(yǔ)句的變量定義一個(gè)唯一的名稱[15]。通過(guò)使用靜態(tài)單賦值中間表示能簡(jiǎn)化程序的全局過(guò)程間優(yōu)化，它消除了復(fù)雜的尋址方式和指令語(yǔ)義的副作用[16]，是一種不可或缺的全局過(guò)程間數(shù)據(jù)流分析形式，不管是GCC、LLVM這些開源編譯器或是ICC、AOCC等商業(yè)編譯器都在使用SSA形式的中間表示[17]。

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

3.3 構(gòu)建butterfly分支

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

構(gòu)建butterfly分支是該方法的核心部分，通過(guò)對(duì)程序的指定區(qū)域創(chuàng)建條件判斷語(yǔ)句，構(gòu)建出butterfly分支，調(diào)整修復(fù)控制流圖，并更新SSA的PHI節(jié)點(diǎn)信息，得到的代碼中包含了幾個(gè)流程分支條件及其對(duì)應(yīng)分支代碼，再經(jīng)過(guò)常量傳播、無(wú)效數(shù)據(jù)刪除等全局優(yōu)化之后簡(jiǎn)化控制流。這一系列操作在編譯器的編譯階段進(jìn)行，在程序的運(yùn)行階段會(huì)根據(jù)輸入的參數(shù)值，找到正確的流程分支，從而簡(jiǎn)化程序中不必要的邏輯運(yùn)算，減少運(yùn)行時(shí)間，以此達(dá)到對(duì)程序優(yōu)化的目的。

如圖2所示是具有2個(gè)butterfly分支的控制流圖抽象模型。圖2中包含了原始代碼的控制流圖和進(jìn)行butterfly優(yōu)化之后的控制流圖。

Figure 2 Abstract model of butterfly control flow graph

圖2a是一個(gè)簡(jiǎn)化的程序控制流圖，其包含1個(gè)entry_bb、1個(gè)exit_bb和程序的主體代碼基本塊，它們分別通過(guò)ENTRY_EDGE、EXIT_EDGE和ORIG_BBS進(jìn)行關(guān)聯(lián)。圖2b所示是將源碼控制流圖抽象成butterfly的設(shè)計(jì)模式，corig_bbs是根據(jù)orig_bbs復(fù)制而來(lái)的代碼主要邏輯部分，作為條件語(yǔ)句塊cond_bb2的then分支，false_bb是由orig_bbs中EXIT基本塊的前置基本塊復(fù)制而來(lái)，作為條件語(yǔ)句塊cond_bb2的else分支，條件語(yǔ)句塊cond_bb1和cond_bb2是根據(jù)參數(shù)的2個(gè)可能值創(chuàng)建出的基本塊，cond_bb2作為cond_bb1的else分支，orig_bbs基本塊作為條件語(yǔ)句塊cond_bb1的then分支。

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

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

3.4 與其它優(yōu)化組合

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

對(duì)于一些邏輯相對(duì)較復(fù)雜的程序代碼，采用激進(jìn)蝴蝶優(yōu)化方法對(duì)局部代碼構(gòu)建butterfly分支后，代碼中包含參數(shù)取值的流程分支。在程序運(yùn)行時(shí)這些流程分支中只有一個(gè)會(huì)被執(zhí)行，這便會(huì)促進(jìn)SSA上眾多優(yōu)化操作的進(jìn)行。對(duì)于邏輯相對(duì)較簡(jiǎn)單的程序，通過(guò)控制流分析或相關(guān)支配關(guān)系優(yōu)化，可以找出程序中的部分常量和不可訪問(wèn)的代碼段，直接刪除無(wú)效代碼段，從而達(dá)到優(yōu)化效果。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)平臺(tái)

為了對(duì)本文提出的激進(jìn)蝴蝶優(yōu)化方法的可行性和有效性進(jìn)行評(píng)估，本文主要采用GCC編譯器進(jìn)行實(shí)驗(yàn)，將優(yōu)化方法應(yīng)用到GCC 8.2.0編譯器，在Intel的Ubuntu Linux和AMD的Red Hat Linux 2種平臺(tái)上，對(duì)優(yōu)化前后的GCC 8.2.0編譯器進(jìn)行實(shí)驗(yàn)。表1給出了實(shí)驗(yàn)中所使用平臺(tái)的主要信息。

Table 1 Main information of the experimental platform

在Intel和AMD 2種平臺(tái)上，對(duì)GCC 8.2.0編譯器進(jìn)行SPEC CPU 2017基準(zhǔn)測(cè)試。SPEC CPU 2017包含43個(gè)基準(zhǔn)測(cè)試套件，涵蓋區(qū)域海洋模擬、天氣預(yù)報(bào)等眾多領(lǐng)域，是一套被國(guó)際上廣泛用于評(píng)估編譯器性能的標(biāo)準(zhǔn)測(cè)試套件[19,20]。選定優(yōu)化前GCC 8.2.0編譯器為參考編譯器(base compiler)，優(yōu)化后的GCC 8.2.0編譯器為目標(biāo)編譯器(target compiler)，使用ref輸入數(shù)據(jù)集進(jìn)行基準(zhǔn)測(cè)試。

采用測(cè)試結(jié)果的ratio值來(lái)進(jìn)行編譯器優(yōu)化前后的性能對(duì)比，根據(jù)式(1)，以參考編譯器運(yùn)行benchmark得出的ratio值為基準(zhǔn)，根據(jù)目標(biāo)編譯器運(yùn)行benchmark得出的ratio值計(jì)算出目標(biāo)編譯器的性能提升比ratiospeedup。

(1)

4.2 方法的可行性分析

在可行性方面，采用優(yōu)化前的編譯器編譯經(jīng)手工修改的代碼，若得到的關(guān)鍵中間表示與優(yōu)化后的編譯器編譯原始代碼得到的關(guān)鍵中間表示一致，說(shuō)明該方法可行。

下面列舉了一個(gè)示例程序以及該示例程序的源碼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;

}

示例代碼描述了一個(gè)循環(huán)計(jì)算的熱區(qū)域，for循環(huán)在某種常數(shù)參數(shù)下為冗余代碼，其計(jì)算結(jié)果result在其后的條件判斷中使用。條件語(yǔ)句中參數(shù)type的取值與運(yùn)行時(shí)輸入的參數(shù)值相關(guān)，該參數(shù)的可能值為type1和type2。源碼butterfly變換是根據(jù)type1和type2這2個(gè)取值來(lái)創(chuàng)建2個(gè)代碼分支，一個(gè)進(jìn)行激進(jìn)冗余刪除優(yōu)化，另一個(gè)維持原有保守設(shè)計(jì)，確保非常數(shù)參數(shù)條件下的正確性。

以上述代碼為實(shí)驗(yàn)代碼，進(jìn)行2組對(duì)照實(shí)驗(yàn)，以對(duì)比編譯器優(yōu)化前后的控制流程圖。圖4a所示為采用優(yōu)化后的編譯器編譯示例代碼所得到的控制流程圖。圖4b所示是對(duì)上述源碼butterfly變換后的代碼采用優(yōu)化前的編譯器進(jìn)行編譯所得到的控制流程圖。

圖4a示例代碼的控制流圖中return語(yǔ)句所在的基本塊和得到結(jié)果值的基本塊被合并為bb17，所以比圖4b少一個(gè)基本塊bb18。從實(shí)驗(yàn)結(jié)果可以看出，編譯器優(yōu)化前后的控制流圖一致，通過(guò)對(duì)比分析其匯編碼也有相似的結(jié)構(gòu)，由此說(shuō)明該優(yōu)化方法可行。

Figure 4 Control flow graph before and after compiler optimization

4.3 方法的有效性分析

在方法的有效性方面，主要通過(guò)在Intel和AMD的2個(gè)平臺(tái)上分別進(jìn)行基準(zhǔn)測(cè)試，觀察其性能表現(xiàn)。第1組實(shí)驗(yàn)在Intel平臺(tái)上進(jìn)行，分別使用優(yōu)化前GCC和優(yōu)化后的GCC對(duì)SPEC CPU 2017進(jìn)行ref數(shù)據(jù)集的浮點(diǎn)測(cè)試；第2組實(shí)驗(yàn)在AMD平臺(tái)上進(jìn)行，同樣采用優(yōu)化前后的GCC進(jìn)行ref數(shù)據(jù)集的浮點(diǎn)測(cè)試，分別得出在638.imagick_s測(cè)試用例上的ratio值。

根據(jù)式(1)對(duì)實(shí)驗(yàn)的ratio值進(jìn)行計(jì)算得到性能提升比，如圖5所示。實(shí)驗(yàn)數(shù)據(jù)表明，對(duì)于638.imagick_s測(cè)試用例，在Intel平臺(tái)上，優(yōu)化改進(jìn)后的GCC 8.2.0性能提升比達(dá)到了26%，在AMD平臺(tái)上的性能提升比達(dá)到了25%，該優(yōu)化方法的有效性得到了驗(yàn)證。

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

綜合以上實(shí)驗(yàn)論述，驗(yàn)證了本文提出的激進(jìn)蝴蝶優(yōu)化方法的可行性和有效性。通過(guò)對(duì)程序代碼塊構(gòu)建butterfly分支可以有效進(jìn)行無(wú)效代碼的刪除，達(dá)到提升程序性能的目的。

5 結(jié)束語(yǔ)

本文提出一種依賴數(shù)據(jù)流分析的激進(jìn)蝴蝶優(yōu)化方法，作為無(wú)效代碼刪除優(yōu)化的一個(gè)動(dòng)態(tài)擴(kuò)展方案，最后通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法在GCC編譯器上的可行性和有效性。該方法利用SSA中間表示，根據(jù)動(dòng)態(tài)運(yùn)行時(shí)輸入?yún)?shù)的傳遞過(guò)程，分析出特定區(qū)域中關(guān)鍵變量的可能值，結(jié)合變量值，自動(dòng)為程序生成多個(gè)代碼形狀類似butterfly的分支代碼，使編譯器在程序編譯階段為無(wú)效代碼刪除等相關(guān)組合優(yōu)化提供可行的優(yōu)化依據(jù)。該方法通過(guò)構(gòu)建butterfly分支能調(diào)整程序的控制流程圖，以促進(jìn)其它優(yōu)化的進(jìn)行。接下來(lái)的工作是優(yōu)化改進(jìn)該方法，使其能在更多的程序中發(fā)揮優(yōu)化作用，并且能做出更激進(jìn)的優(yōu)化，更自動(dòng)化的判斷。