基于指令Cache和寄存器壓力的循環(huán)展開優(yōu)化*

王翠霞,韓 林,劉浩浩

(中原工學院前沿信息技術(shù)研究院，河南 鄭州 450007)

1 引言

循環(huán)是影響程序性能的核心，通常也是編譯器優(yōu)化的理想目標[1]。循環(huán)展開是關(guān)鍵的循環(huán)優(yōu)化技術(shù)之一，主流編譯器如GCC(GNU Compiler Collection)、LLVM和ICC等都實現(xiàn)了該優(yōu)化技術(shù)。循環(huán)展開通過多次復制原始循環(huán)體，并調(diào)整循環(huán)退出代碼來減少計算循環(huán)索引和測試循環(huán)分支條件帶來的開銷[2]。循環(huán)展開能為其他優(yōu)化增加機會，如公共子表達式消除、歸納變量優(yōu)化和軟件流水等[3]，它也是向量化、數(shù)據(jù)預取[4,5]等優(yōu)化的重要組成部分。

但是，循環(huán)展開并不總是有收益的，過度的循環(huán)展開會導致循環(huán)的指令數(shù)量激增，如果目標平臺的指令Cache過小，將會造成指令Cache溢出，從而降低指令Cache的命中率。同時，循環(huán)展開會增加額外的中間變量，展開之后的循環(huán)體對寄存器的需求增大，容易導致寄存器溢出，從而降低程序的運行性能[6]。然而，循環(huán)展開次數(shù)過少，則浪費了潛在的優(yōu)化機會，不能充分改善程序運行時的性能。因此，決定循環(huán)展開性能的關(guān)鍵因素是確定合適的展開因子。

針對這一問題的研究可以分為2個方向：一個是使用機器學習預測展開因子；另一個是編譯器普遍采用啟發(fā)式方法自動計算展開因子。文獻[7]使用有監(jiān)督的機器學習來優(yōu)化循環(huán)展開，通過使用2種不同的機器學習算法NN(Near Neighbor)和SVM(Support Vector Machine)來預測循環(huán)展開因子。文獻[8]基于優(yōu)化遍之間的交互關(guān)系對循環(huán)展開的影響，提出了一種介于傳統(tǒng)編譯器和迭代編譯器的輕量型編譯器。文獻[9]將傳統(tǒng)的隨機森林模型進行加權(quán)和非平衡數(shù)據(jù)集處理，使用改進后的模型來預測展開因子。文獻[10]在TIRAMISU多面體編譯器上利用深度神經(jīng)網(wǎng)絡(luò)DNN(Deep Neural Network)學習循環(huán)展開因子模型，用來自動計算循環(huán)展開因子。但是，使用機器學習預測展開因子的開銷大于啟發(fā)式方法的，因為模型的準確性不僅依賴于提取特征的完備性，而且還需要大量樣本用于訓練，所以編譯器普遍采用啟發(fā)式方法計算展開因子。

文獻[11]基于軟件流水中的資源限制提出了基于程序特性的展開因子算法，并考慮循環(huán)展開對數(shù)據(jù)預取的影響，同時提出了基于展開的數(shù)據(jù)預取優(yōu)化技術(shù)，并在ORC(Open Research Compiler)編譯器上實現(xiàn)了該算法。文獻[12]基于開源編譯器Open64-5.0，針對向量程序的向量寄存器壓力和代碼膨脹等因素，提出了一種自動計算展開因子的算法CUFVL(Compute Unroll Factor for Vectorized Loop)，通過結(jié)合CUFVL算法和完全展開策略，選取合適的展開因子進行展開優(yōu)化。文獻[13]基于GCC-5.3.0編譯器，提出了一種將循環(huán)展開優(yōu)化技術(shù)與寄存器壓力相結(jié)合的方法，用于估算合適的展開因子。文獻[14]針對編譯時和運行時都無法確定迭代計數(shù)的循環(huán)(不可計數(shù)循環(huán))，提出了一種通過快速路徑展開不可計數(shù)循環(huán)的方法，并在Java虛擬機GraalVM上實現(xiàn)了該方法。

影響展開因子的因素眾多，有控制流、指令數(shù)量、寄存器數(shù)量和指令Cache大小等，其中最為重要的2個因素是指令Cache和寄存器資源[6,12]?；贕CC-7.1.0開源編譯器，以循環(huán)展開問題開展深入的分析與研究，針對指令Cache和寄存器資源對循環(huán)展開的影響，本文提出了一種基于指令Cache和寄存器壓力的循環(huán)展開因子計算方法，旨在計算出更加適合目標架構(gòu)的循環(huán)展開因子。在申威和海光平臺上的實驗結(jié)果表明了該方法的有效性。本文的主要貢獻如下：

(1)深入分析了GCC-7.1.0編譯器中寄存器傳輸語言RTL(Register Transfer Language)階段的循環(huán)展開優(yōu)化技術(shù)，著重剖析了計算循環(huán)展開因子的代價模型，指出了其不足之處。

(2)針對指令Cache容量和寄存器資源對循環(huán)展開的影響，提出了一種更加完善的循環(huán)展開因子計算方法，并在GCC-7.1.0編譯器中實現(xiàn)了該方法。

2 RTL循環(huán)展開

2.1 GCC編譯流程

Figure 1 Compilation process of GCC

GCC是GNU項目中應用最廣泛的軟件之一，它支持多種語言前端和目標平臺[15]。GCC將源代碼編譯成目標平臺匯編代碼時，通常被劃分為高級語言前端、中間代碼優(yōu)化和后端代碼生成3個階段，分別采用不同的中間表示形式：抽象語法樹AST(Abstract Syntax Tree)、GIMPLE中間表示和寄存器傳輸語言RTL。轉(zhuǎn)換流程如圖1所示，首先，源程序代碼通過詞法/語法分析轉(zhuǎn)化為與前端語言相關(guān)的抽象語法樹AST；然后，通過Gimplify轉(zhuǎn)化為GIMPLE三地址中間表示形式，GIMPLE層的優(yōu)化是基于SSA(Static Single Assignment)的，目的是實現(xiàn)與前端語言和目標機器無關(guān)的優(yōu)化；接著，Expand過程將GIMPLE表示轉(zhuǎn)化為RTL表示形式，進行一些與目標機器相關(guān)的優(yōu)化；最后根據(jù)機器描述文件生成匯編代碼。

GCC中的編譯過程是由多個優(yōu)化遍(Pass)組成的，各個遍之間相對獨立，完成各自的功能。循環(huán)展開優(yōu)化在GCC-7.1.0編譯優(yōu)化中有2種實現(xiàn)方式：GIMPLE階段的循環(huán)完全展開優(yōu)化；RTL階段的循環(huán)展開優(yōu)化。本文主要對RTL階段的循環(huán)展開進行分析與優(yōu)化。

2.2 循環(huán)展開流程

RTL階段的循環(huán)展開是根據(jù)循環(huán)類型進行展開的。循環(huán)展開將循環(huán)分為3種類型：編譯時可計數(shù)循環(huán)，迭代次數(shù)能在編譯時確定的循環(huán)；運行時可計數(shù)循環(huán)，迭代次數(shù)能在運行時確定的循環(huán)；不可計數(shù)循環(huán)，迭代次數(shù)不可以在編譯時和運行時確定的循環(huán)[14]。循環(huán)展開優(yōu)化遍的信息如表1所示。優(yōu)化遍pass_rtl_unroll_loops在loop-init.c中定義，入口函數(shù)為unroll_loops(intflags)，在loop-unroll.c中實現(xiàn)。要開啟循環(huán)展開優(yōu)化，需要使用編譯優(yōu)化選項-funroll-loops或-funroll-all-loops。

Table 1 Information of loop unrolling pass

循環(huán)展開優(yōu)化從內(nèi)到外遍歷循環(huán)嵌套，選擇滿足條件的循環(huán)進行展開,其流程如圖2所示,主要分為3個階段：合法性分析、計算循環(huán)展開因子和生成循環(huán)展開代碼。

Figure 2 Flow chart of loop unrolling

合法性分析主要是對循環(huán)進行檢查，判斷循環(huán)是否滿足循環(huán)展開的條件，不滿足條件則不會進行循環(huán)展開。其包括3種類型的檢查：(1)檢查是否優(yōu)化了目標代碼體積，因為循環(huán)展開優(yōu)化增大了目標代碼體積，如果用戶要求優(yōu)化目標代碼體積，則不會考慮循環(huán)展開；(2)檢查循環(huán)體是否能進行復制，不能復制的循環(huán)體無法進行展開；(3)檢查循環(huán)是否為最內(nèi)層循環(huán)，非最內(nèi)層循環(huán)不予展開。

在進行展開因子計算之前，首先計算出當前循環(huán)的指令數(shù)用于估算循環(huán)展開因子的上界，然后再根據(jù)循環(huán)類型分別計算出最佳展開因子。循環(huán)的指令數(shù)ninsns由函數(shù)num_loop_insns()計算得出，此時不考慮循環(huán)中的分支情況。對于存在分支的循環(huán)，由函數(shù)average_num_loop_insns()計算出循環(huán)的平均指令數(shù)av_ninsns。不同的循環(huán)類型需要與之相應的展開因子計算方式。利用decide_unroll_constant_iterations()計算編譯時可計數(shù)循環(huán)的展開因子時，需要開啟編譯選項-funroll-loops。利用decide_unroll_runtime_iterations()計算運行時可計數(shù)循環(huán)的展開因子時，需要開啟編譯選項-funroll-loops。當循環(huán)的迭代次數(shù)不能在編譯時和運行時確定，且循環(huán)中的分支數(shù)小于或等于1時，調(diào)用decide_unroll_stupid()計算不可計數(shù)循環(huán)的展開因子，需要開啟編譯選項-funroll-all-loops。當不滿足計算展開因子條件(如未開啟循環(huán)展開編譯選項或展開因子上界小于或等于1)時，無法計算出展開因子，則不進行循環(huán)展開。

在代碼生成階段，從內(nèi)到外遍歷循環(huán)嵌套，根據(jù)展開類型和最佳展開因子生成循環(huán)展開代碼。若循環(huán)類型為LPT_UNROLL_CONSTANT，由函數(shù)unroll_loop_constant_iterations()生成編譯時可計數(shù)循環(huán)的展開代碼。在進行展開代碼生成時，如果展開因子能被循環(huán)迭代次數(shù)整除，就根據(jù)展開因子去復制循環(huán)體。如果展開因子不能被循環(huán)迭代次數(shù)整除，就會產(chǎn)生剩余循環(huán)，需要將剩余循環(huán)完全展開。若展開類型為LPT_UNROLL_RUNTIME，由函數(shù)unroll_loop_runtime_iterations()生成運行時可計數(shù)循環(huán)的展開代碼。在生成展開代碼時，需要將剩余循環(huán)進行剝離，剝離完之后調(diào)整循環(huán)信息，然后根據(jù)展開因子去復制循環(huán)體。若展開類型為LPT_UNROLL_STUPID，由函數(shù)unroll_loop_stupid()生成不可計數(shù)循環(huán)的展開代碼。代碼變換完成后，更新循環(huán)信息，調(diào)整循環(huán)結(jié)構(gòu)和基本塊的支配信息。

2.3 代價模型

展開因子的計算是循環(huán)展開優(yōu)化的核心問題，結(jié)合循環(huán)展開流程對計算展開因子的代價模型進行分析。循環(huán)展開的代價模型主要分為2部分：(1)計算展開因子上界nunroll；(2)計算最佳展開因子best_nunroll。

(1)計算展開因子上界。展開因子的上界nunroll通過循環(huán)的指令數(shù)和編譯器中給定的指令數(shù)上限進行估算，并且不能超過編譯器中給定的展開因子上限，首先由編譯器中給定的指令數(shù)上限(pmui，pmaui)除以循環(huán)本身的指令數(shù)(ninsns，av_ninsns)計算出結(jié)果，并從中選取最小值作為展開因子上界的初始值nun_pre。然后比較nun_pre和編譯器中給定的展開因子上限pmut，選取較小值為展開因子上界nunroll。計算公式如式(1)～式(4)所示：

nun=pmui/ninsns

(1)

nun_av=pmaui/av_ninsns

(2)

nun_pre=nun>nun_av?nun_av:nun

(3)

nunroll=nun_pre>pmut?pmut:nun_pre

(4)

其中,pmui代表GCC編譯器中給定的指令數(shù)上限PARAM_MAX_UNROLLED_INSNS，默認值為200;pmaui代表GCC編譯器中給定的平均指令數(shù)上限PARAM_MAX_AVERAGE_UNROLLED_INSNS，默認值為80;pmut代表GCC編譯器中給定的最大展開因子上限PARAM_MAX_UNROLL_TIMES，默認值為8。

(2)計算最佳展開因子。編譯時可計數(shù)循環(huán)計算最佳展開因子時，需要對剩余循環(huán)完全展開，則循環(huán)展開因子是循環(huán)體的復制次數(shù)加剩余循環(huán)迭代次數(shù)。從第1步計算的展開因子上界所在的[nunroll-1,2*nunroll+2]內(nèi)選取最小值做為最佳展開因子best_nunroll。運行時可計數(shù)循環(huán)和不可計數(shù)循環(huán)計算最佳展開因子時，調(diào)整上一步計算出的展開因子上界nunroll為2的整數(shù)次冪，并將其做為最佳展開因子best_nunroll，使展開后的循環(huán)滿足指令 Cache對齊[8]。

2.4 存在的問題

通過上述分析可以發(fā)現(xiàn)，代價模型中展開因子上界nunroll的計算只考慮到了循環(huán)指令數(shù)的影響，而忽略了寄存器資源等其他限制因素，模型的準確性仍有較大的改進空間。模型參數(shù)pmui和pmaui為編譯器給定的經(jīng)驗值，參數(shù)的調(diào)整依賴于編譯器開發(fā)人員的經(jīng)驗知識，缺乏理論依據(jù)，需要結(jié)合目標架構(gòu)進行定制。

3 循環(huán)展開優(yōu)化方法

為了解決2.4節(jié)中提到的問題，本節(jié)介紹基于指令Cache和寄存器壓力的循環(huán)展開因子計算方法。針對循環(huán)展開代價模型的不足之處，首先根據(jù)指令Cache容量對編譯器中的指令數(shù)上限進行調(diào)整；然后考慮寄存器壓力對循環(huán)展開的限制，對展開因子的上界進行預估；最后確定展開因子上界和最佳的展開因子。

3.1 基于指令Cache容量的架構(gòu)參數(shù)調(diào)優(yōu)

循環(huán)展開的有效性取決于可調(diào)參數(shù)：循環(huán)展開最大指令數(shù)pmui和平均指令數(shù)pmaui，它們是編譯器給定的經(jīng)驗值，與循環(huán)自身的指令數(shù)一起用于估算展開因子上界(式(1)～式(3))。根據(jù)機器描述中的指令Cache容量，實現(xiàn)pmui和pmaui的自動調(diào)整,以適應目標平臺。

現(xiàn)在處理器架構(gòu)的指令Cache容量一般為32 KB，假定指令字長為4 B，由式(5):

(5)

可知其最多能容納8 192條指令。而編譯器中給定的循環(huán)展開指令數(shù)pmui和平均指令數(shù)pmaui上限值太小，默認為200和80，不適用于現(xiàn)在的處理器架構(gòu)[8]。由于循環(huán)展開次數(shù)過少浪費了潛在的優(yōu)化機會，因此針對目標平臺的指令Cache容量和指令字長對循環(huán)展開指令數(shù)上限進行調(diào)整，需要滿足以下條件：

pmui=(L1_ICache*50%)/word_size

(6)

pmaui=(L1_ICache*50%)/word_size

(7)

其中,L1_ICache代表目標實驗平臺的一級指令Cache容量(32 KB，32*1024 B)，word_size代表目標實驗平臺的指令字長(定長32 b，4 B)。

單純考慮指令Cache對循環(huán)展開的影響，可能會導致過度的循環(huán)展開，展開之后的循環(huán)體對寄存器的需求增大，容易導致寄存器溢出，從而降低程序性能。為避免這一情況，通過考慮寄存器壓力對展開因子上界進行預估。

3.2 基于寄存器壓力的展開因子上界預估

程序某一點的寄存器壓力是指在這一點處活躍的虛擬寄存器數(shù)量，這些活躍的虛擬寄存器會被分配到不同的物理寄存器中[16]。虛擬寄存器用于存儲程序中的變量或編譯器產(chǎn)生的臨時變量。

編譯器在對程序進行循環(huán)展開優(yōu)化時，會增加額外的臨時變量，增大寄存器壓力，寄存器壓力大于可用的物理寄存器會導致寄存器溢出，就需要將溢出寄存器中的變量值寫回到內(nèi)存中，在需要的時候通過內(nèi)存加載指令加載到寄存器中，這些額外的訪存開銷會降低程序性能[17]。因此，針對上述問題，在進行循環(huán)展開優(yōu)化時對循環(huán)中的寄存器壓力進行評估，并計算出展開因子估計值。

在RTL階段的循環(huán)展開優(yōu)化中，代碼中的寄存器為虛擬寄存器和物理寄存器(處理器要求某些操作數(shù)存儲在特定的CPU寄存器中)，每個寄存器都有特定的數(shù)據(jù)類型[16]。首先對函數(shù)中的寄存器進行活躍分析，計算出每個基本塊出口處和入口處的活躍寄存器集(即算法1第1行)，根據(jù)基本塊中指令的def集和use集計算不同類型的最大寄存器壓力(即算法1第2行)，與該類型可用的物理寄存器數(shù)量進行對比，如果寄存器壓力大于可用物理寄存器數(shù)量，則認為寄存器壓力過大。否則，通過寄存器壓力和可用物理寄存器數(shù)量去計算展開因子估計值(即算法1第3～5行)。評估循環(huán)寄存器壓力和展開因子估計值的算法偽代碼如算法1所示。

算法1計算寄存器壓力和展開因子估計值

輸入:函數(shù)function。

輸出:展開因子loop->reg_nunroll。

1.init_anaylise()；

2.calculate_bb_reg_pressure(function)；

3.foreachloopstarting at innermostdo

4.loop->reg_nunroll←check_register_pressure(loop)；

5.endfor

6.returnloop->reg_nunroll

首先由算法1中的init_anaylise()函數(shù)進行寄存器活躍分析，計算函數(shù)中每個基本塊出口處和入口處的活躍寄存器集?；钴S分析由式(8)和式(9)所示的后向數(shù)據(jù)流公式描述[18]：

in[B]=(out[B]-def[B])∪use[B]

(8)

(9)

其中,in[B]表示基本塊B入口處的活躍寄存器集；out[B]表示基本塊B出口處的活躍寄存器集；def[B]表示基本塊B中存在的寄存器集：寄存器中的變量在引用之前已明確地對該變量進行了賦值；use[B]表示基本塊B存在的寄存器集：寄存器中的變量在定義之前可能會被引用；S是基本塊B的后繼基本塊。

遍歷函數(shù)中的基本塊，計算出每個基本塊的def[B]和use[B]集合；然后再后向遍歷函數(shù)中的基本塊，根據(jù)式(8)和式(9)計算出每個in[B]和out[B]集合，其中初始值in[EXIT]=?，EXIT為函數(shù)的退出塊。

計算函數(shù)中每個基本塊的最大寄存器壓力，由算法1中的calculate_bb_reg_pressure(function)函數(shù)完成。寄存器壓力是根據(jù)指令def集和use集計算的，指令的def集是指令定義(產(chǎn)生)的寄存器集，而use集是指令使用(消耗)的寄存器集[16]。由curr_live保存在基本塊bb出口處的活躍寄存器集out[bb](即算法2第3行)，根據(jù)不同的寄存器類reg_classes對基本塊bb中的最大寄存器壓力值curr_regs_pressure[reg_classes]進行初始化(即算法2第4～6行)，獲取分配curr_live時所需的不同類別的物理寄存器數(shù)量，作為當前基本塊的最大寄存器壓力(即算法2第7～9行)。然后通過對基本塊bb中的指令insn進行反向遍歷，根據(jù)指令的def和use信息計算在各指令處的活躍寄存器集，并更改相應的寄存器壓力(即算法2第10～22行)。計算函數(shù)基本塊最大寄存器壓力的偽代碼如算法2所示。

算法2計算函數(shù)中基本塊的最大寄存器壓力

輸入:函數(shù)function。

輸出:每個基本塊的最大寄存器壓力。

1.curr_live←?；

2.foreachbboffunctiondo

3.curr_live←df_get_live_out(bb)；

4.foreachreg_classesdo

5.curr_regs_pressure[reg_classes]← 0；

6.endfor

7.foreachiofcurr_livedo

8.change_pressure(i,true)；

9.endfor

10.foreachinsnofbbin backward orderdo

11.foreachdefofinsndo

12.ifcleari(register number ofdef)fromcurr_liveis truethen

13.change_pressure(i,false)；

14.endif

15.endfor//def

16.foreachuseofinsndo

17.ifaddi(register number ofuse)intocurr_liveis truethen

18.change_pressure(i,false)；

19.endif

20.endfor//use

21.endfor//insn

22.endfor//bb

最后從內(nèi)到外遍歷循環(huán)，通過算法1中的check_register_pressure(loop)函數(shù)估算循環(huán)中的寄存器壓力，并用寄存器壓力計算展開因子估計值。遍歷循環(huán)中所有的基本塊，根據(jù)不同的寄存器類reg_classes，比較在同一基本塊中不同寄存器類下的最大寄存器壓力curr_regs_pressure[reg_classes]和可用的物理寄存器數(shù)量hard_regs_num[reg_classes]，以評估寄存器壓力是否過大，當滿足寄存器壓力小于可用物理寄存器數(shù)量時，通過寄存器壓力和可用物理寄存器數(shù)量去計算展開因子估計值集合unroll_list，如式(10)所示:

(10)

從中選取最小值賦給loop->reg_nunroll作為寄存器壓力相關(guān)的展開因子估計值。計算展開因子估計值的偽代碼如算法3所示。

算法3計算展開因子估計值

輸入:循環(huán)loop。

輸出:展開因子reg_nunroll。

1.body←get_loop_body(loop)；

2. auto_vec(int,10)unroll_list；

3.fori← 0 toloop->num_nodesdo

4.curr_bb←body[i]；

5.ifcurr_bbis NULLthen

6. continue；

7.endif

8.foreachreg_classesdo

9.unroll← 0；

10.ifcurr_regs_pressure[reg_classes]ofcurr_bbis 0then

11. continue；

12.endif

13.ifcurr_regs_pressure[reg_classes]ofcurr_bb

15.unroll_list.safe_push(unroll)；

16.endif

17.endfor

18.endfor

19. Select the minimum ofunroll_listand assign it toloop->reg_nunroll;

20.returnloop->reg_nunroll

3.3 確定最佳展開因子

因為循環(huán)展開最大指令數(shù)pmui和平均指令數(shù)pmaui的限制，導致循環(huán)不能展開或展開因子過小，浪費了潛在的優(yōu)化機會，根據(jù)指令Cache容量對循環(huán)展開指令數(shù)進行調(diào)整，會增大展開因子，增加額外的中間變量，導致寄存器壓力增大，所以結(jié)合指令Cache和寄存器壓力這2個因素來共同確定最佳的展開因子，具體要求步驟如下所示：

(1)根據(jù)指令Cache容量(式(6)和式(7))調(diào)整pmui和pmaui，由代價模型中的式(1)～式(4)計算出展開因子上界nunroll。

(2)利用算法1計算當前循環(huán)中與寄存器壓力有關(guān)的展開因子估計值loop->reg_nunroll。

(3)在根據(jù)循環(huán)類型計算展開因子時，如果loop->reg_nunroll為空，則說明寄存器壓力過大，就不進行循環(huán)展開;否則比較loop->reg_nunroll與展開因子上界nunroll，選取較小值作為展開因子上界,如式(11)所示：

n=n>lr?lr:n

(11)

其中,n代表nunroll，lr代表loop->reg_nunroll。

(4)根據(jù)展開因子上界nunroll計算最佳展開因子best_nunroll。最佳展開因子best_nunroll需滿足式(12)：

best_nunroll×ninsns≤pmui

(12)

4 實驗測試與分析

4.1 實驗環(huán)境

在GCC-7.1.0編譯器中實現(xiàn)了本文所提出的方法，并分別在申威(Sunway)1621多核處理器和海光(Hygon)C86 7165處理器上對優(yōu)化前后的編譯器進行了實驗，表2為實驗平臺信息。

測試集采用SPEC CPU 2006和NPB-3.3.1標準測試集，SPEC使用ref規(guī)模輸入，NPB使用B規(guī)模輸入。編譯選項：-O3-static-funroll-loops-funroll-all-loops-fprefetch-loop-arrays。

Table 2 Information of experimental platforms

Figure 3 Results of SPEC CPU 2006 FP test sets on Sunway platform

Figure 4 Results of SPEC CPU 2006 INT test sets on Sunway platform

4.2 實驗方法

為了驗證本文優(yōu)化方法的有效性，使用SPEC和NPB測試集，分別在2種實驗平臺上進行3組不同版本的測試：基礎(chǔ)的循環(huán)展開版本A1；基于指令Cache優(yōu)化的循環(huán)展開版本A2；結(jié)合指令Cache和寄存器壓力的循環(huán)展開版本A3。若經(jīng)過優(yōu)化后的循環(huán)展開未對測試集的運行結(jié)果帶來不良影響，則表明了該優(yōu)化方法的正確性。以版本A1下的程序運行時間為基準，計算不同優(yōu)化版本下的程序加速比，評估優(yōu)化后的程序性能。某優(yōu)化版本v下的課題加速比計算公式如式(13)所示：

(13)

其中，timev為優(yōu)化版本v下課題的運行時間，timeA1為基礎(chǔ)循環(huán)展開版本A1下課題的運行時間。測試集上的平均性能加速比(average)為測試集上所有課題加速比的算術(shù)平均值。

4.3 Sunway平臺測試

SPEC測試結(jié)果如圖3和圖4所示，NPB測試結(jié)果如圖5所示。實驗結(jié)果顯示，通過綜合寄存器壓力和指令Cache對循環(huán)展開的影響，優(yōu)化版本A3在所有測試用例上都可以獲得不次于版本A2的加速效果;對于絕大多數(shù)課題，版本A3可以獲得不次于基礎(chǔ)優(yōu)化版本A1的加速效果;部分課題取得了顯著的性能提升，個別課題出現(xiàn)了少許性能下降。整體上看，版本A3優(yōu)化在SPEC和NPB上的平均性能分別提升了2.7%和5.4%。接下來對有性能提升和出現(xiàn)性能下降的課題進行分析。

對SPEC中性能提升效果較好的課題459.GemsFDTD和436.cactusADM的熱點循環(huán)進行分析。在進行原始循環(huán)展開優(yōu)化時，由于編譯器給定的指令數(shù)的限制太小，2個循環(huán)的展開因子均為0，未進行循環(huán)展開。通過指令Cache調(diào)整指令數(shù)限制，計算出展開因子均為8(達到編譯器給定的最大展開因子限制)。循環(huán)展開不但降低了循環(huán)開銷，同時也暴露了相鄰2次迭代間的冗余訪存，為后續(xù)的冗余消除提供了機會。版本A2優(yōu)化后的459.GemsFDTD和436.cactusADM程序性能與版本A1優(yōu)化后的相比，分別提升了25%和22%?？紤]展開次數(shù)過多，增加了額外的臨時變量，會導致寄存器壓力過大的情況，結(jié)合指令Cache和寄存器壓力完善展開因子計算(版本A3)，此時展開因子為4和2，性能較版本A1的提升了26%和25%。優(yōu)化版本A2和A3在SP上也分別有17%和25%的性能提升。

Figure 5 Results of NPB-3.3.1 test sets on Sunway platform

使用版本A3時其他課題如410.bwaves、435.gromacs、437.leslie3d、447.dealII、470.lbm、400.perlbench、464.h264ref、BT、CG、FT、MG和UA等，分別相比使用版本A1時有3%～8%的加速效果。

Figure 6 Results of SPEC CPU 2006 test sets on Hygon platform

但是，本文方法并非對所有程序都有正面效果，如482.sphinx3的熱點循環(huán)為2層嵌套for循環(huán)，耗時比重占整個課題的36%，使用版本A1優(yōu)化時的展開因子為4，使用版本A2優(yōu)化時的展開因子為8。由于循環(huán)體含有較多的中間變量，展開因子增大后，出現(xiàn)了較多的寄存器溢出，程序性能下降了5%?？紤]寄存器壓力因素(版本A3)進行優(yōu)化，代價模型認為寄存器壓力過大而拒絕展開，丟失了程序潛在的優(yōu)化機會，程序性能下降了2%，但性能下降幅度較小。從SPEC和NPB測試集上的測試結(jié)果來看，結(jié)合指令Cache和寄存器壓力的循環(huán)展開方法能夠有效提升程序性能。

4.4 Hygon平臺測試

海光平臺上的SPEC和NPB測試結(jié)果分別如圖6和圖7所示。版本A3優(yōu)化下的平均性能分別比版本A1優(yōu)化的提升3.1%和6.1%。

Figure 7 Results of NPB-3.3.1 test sets on Hygon platform

由于編譯器給定了指令數(shù)限制，導致選取的展開因子較小或不能進行循環(huán)展開。針對這種情況，通過指令Cache調(diào)整循環(huán)展開指令數(shù)限制(版本A2優(yōu)化)，增加循環(huán)的優(yōu)化機會，其中性能提升較好的課題有459.GemsFDTD、436.cactusADM和SP，其展開因子由原本的0，0和2，均增加到了8，較原始循環(huán)展開優(yōu)化分別提升了 25%,23%和18%?？紤]寄存器壓力對循環(huán)展開的影響，結(jié)合指令Cache和寄存器壓力對展開因子計算進行完善(版本A3優(yōu)化)，展開因子分別為4，2和4，性能較版本A2的進一步提升了2%,3%和8%。

在版本A3優(yōu)化下的其他課題如410.bwaves、435.gromacs、437.leslie3d、447.dealII、470.lbm、400.perlbench、464.h264ref、BT、CG、FT、MG和UA等，較原始循環(huán)展開優(yōu)化有3%～9%的性能提升。

4.5 總結(jié)

綜合Sunway平臺和Hygon平臺上的測試結(jié)果來看，結(jié)合指令Cache和寄存器壓力的循環(huán)展開優(yōu)化方法能夠針對目標架構(gòu)自動計算出合適的展開因子，提升了程序性能，但仍有需要改進之處。在當前的實現(xiàn)中，代價模型對寄存器溢出是零容忍的，即只要存在寄存器溢出就拒絕展開。這種對寄存器壓力的評估和使用方式是過于簡單和嚴苛的，可能使程序丟失潛在的優(yōu)化機會，導致性能下降，需要結(jié)合優(yōu)化之間的相互作用，做出改進。

5 結(jié)束語

本文在對GCC中RTL階段的循環(huán)展開優(yōu)化技術(shù)進行深入分析后，指出了現(xiàn)有代價模型的不足之處。結(jié)合處理器架構(gòu)的指令Cache容量和寄存器資源對循環(huán)展開的影響，提出了一種基于指令Cache和寄存器壓力的循環(huán)展開因子計算方法，并在GCC-7.1.0編譯器中實現(xiàn)了該方法。申威和海光平臺上的實驗結(jié)果顯示，相較于目前GCC中存在的其它展開因子計算方法，該方法能夠自動計算出適合目標架構(gòu)的循環(huán)展開因子，提升程序性能。2種平臺上在SPEC CPU 2006測試集上平均性能分別提升了2.7%和3.1%，在NPB-3.3.1測試集上的平均性能分別提升了5.4%和6.1%。

由于各個優(yōu)化遍之間的交互也會對程序性能造成影響，因此下一步的工作是考慮其他優(yōu)化遍對循環(huán)展開的影響，完善循環(huán)展開優(yōu)化。