王翠霞,韓 林,劉浩浩

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

1 引言

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

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

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

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

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

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

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

2 RTL循環(huán)展開

2.1 GCC編譯流程

Figure 1 Compilation process of GCC

GCC是GNU項(xiàng)目中應(yīng)用最廣泛的軟件之一，它支持多種語言前端和目標(biāo)平臺(tái)[15]。GCC將源代碼編譯成目標(biāo)平臺(tái)匯編代碼時(shí)，通常被劃分為高級(jí)語言前端、中間代碼優(yōu)化和后端代碼生成3個(gè)階段，分別采用不同的中間表示形式：抽象語法樹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)的，目的是實(shí)現(xiàn)與前端語言和目標(biāo)機(jī)器無關(guān)的優(yōu)化；接著，Expand過程將GIMPLE表示轉(zhuǎn)化為RTL表示形式，進(jìn)行一些與目標(biāo)機(jī)器相關(guān)的優(yōu)化；最后根據(jù)機(jī)器描述文件生成匯編代碼。

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

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

RTL階段的循環(huán)展開是根據(jù)循環(huán)類型進(jìn)行展開的。循環(huán)展開將循環(huán)分為3種類型：編譯時(shí)可計(jì)數(shù)循環(huán)，迭代次數(shù)能在編譯時(shí)確定的循環(huán)；運(yùn)行時(shí)可計(jì)數(shù)循環(huán)，迭代次數(shù)能在運(yùn)行時(shí)確定的循環(huán)；不可計(jì)數(shù)循環(huán)，迭代次數(shù)不可以在編譯時(shí)和運(yù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中實(shí)現(xiàn)。要開啟循環(huán)展開優(yōu)化，需要使用編譯優(yōu)化選項(xiàng)-funroll-loops或-funroll-all-loops。

Table 1 Information of loop unrolling pass

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

Figure 2 Flow chart of loop unrolling

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

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

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

2.3 代價(jià)模型

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

(1)計(jì)算展開因子上界。展開因子的上界nunroll通過循環(huán)的指令數(shù)和編譯器中給定的指令數(shù)上限進(jìn)行估算，并且不能超過編譯器中給定的展開因子上限，首先由編譯器中給定的指令數(shù)上限(pmui，pmaui)除以循環(huán)本身的指令數(shù)(ninsns，av_ninsns)計(jì)算出結(jié)果，并從中選取最小值作為展開因子上界的初始值nun_pre。然后比較nun_pre和編譯器中給定的展開因子上限pmut，選取較小值為展開因子上界nunroll。計(jì)算公式如式(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，默認(rèn)值為200;pmaui代表GCC編譯器中給定的平均指令數(shù)上限PARAM_MAX_AVERAGE_UNROLLED_INSNS，默認(rèn)值為80;pmut代表GCC編譯器中給定的最大展開因子上限PARAM_MAX_UNROLL_TIMES，默認(rèn)值為8。

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

2.4 存在的問題

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

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

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

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

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

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

(5)

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

pmui=(L1_ICache*50%)/word_size

(6)

pmaui=(L1_ICache*50%)/word_size

(7)

其中,L1_ICache代表目標(biāo)實(shí)驗(yàn)平臺(tái)的一級(jí)指令Cache容量(32 KB，32*1024 B)，word_size代表目標(biāo)實(shí)驗(yàn)平臺(tái)的指令字長(定長32 b，4 B)。

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

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

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

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

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

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

輸入:函數(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ù)進(jìn)行寄存器活躍分析，計(jì)算函數(shù)中每個(gè)基本塊出口處和入口處的活躍寄存器集?；钴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中存在的寄存器集：寄存器中的變量在引用之前已明確地對(duì)該變量進(jìn)行了賦值；use[B]表示基本塊B存在的寄存器集：寄存器中的變量在定義之前可能會(huì)被引用；S是基本塊B的后繼基本塊。

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

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

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

輸入:函數(shù)function。

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

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)中的寄存器壓力，并用寄存器壓力計(jì)算展開因子估計(jì)值。遍歷循環(huán)中所有的基本塊，根據(jù)不同的寄存器類reg_classes，比較在同一基本塊中不同寄存器類下的最大寄存器壓力curr_regs_pressure[reg_classes]和可用的物理寄存器數(shù)量hard_regs_num[reg_classes]，以評(píng)估寄存器壓力是否過大，當(dāng)滿足寄存器壓力小于可用物理寄存器數(shù)量時(shí)，通過寄存器壓力和可用物理寄存器數(shù)量去計(jì)算展開因子估計(jì)值集合unroll_list，如式(10)所示:

(10)

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

算法3計(jì)算展開因子估計(jì)值

輸入:循環(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 確定最佳展開因子

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

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

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

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

n=n>lr?lr:n

(11)

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

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

best_nunroll×ninsns≤pmui

(12)

4 實(shí)驗(yàn)測(cè)試與分析

4.1 實(shí)驗(yàn)環(huán)境

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

測(cè)試集采用SPEC CPU 2006和NPB-3.3.1標(biāo)準(zhǔn)測(cè)試集，SPEC使用ref規(guī)模輸入，NPB使用B規(guī)模輸入。編譯選項(xiàng)：-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 實(shí)驗(yàn)方法

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

(13)

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

4.3 Sunway平臺(tái)測(cè)試

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

對(duì)SPEC中性能提升效果較好的課題459.GemsFDTD和436.cactusADM的熱點(diǎn)循環(huán)進(jìn)行分析。在進(jìn)行原始循環(huán)展開優(yōu)化時(shí)，由于編譯器給定的指令數(shù)的限制太小，2個(gè)循環(huán)的展開因子均為0，未進(jìn)行循環(huán)展開。通過指令Cache調(diào)整指令數(shù)限制，計(jì)算出展開因子均為8(達(dá)到編譯器給定的最大展開因子限制)。循環(huán)展開不但降低了循環(huán)開銷，同時(shí)也暴露了相鄰2次迭代間的冗余訪存，為后續(xù)的冗余消除提供了機(jī)會(huì)。版本A2優(yōu)化后的459.GemsFDTD和436.cactusADM程序性能與版本A1優(yōu)化后的相比，分別提升了25%和22%?？紤]展開次數(shù)過多，增加了額外的臨時(shí)變量，會(huì)導(dǎo)致寄存器壓力過大的情況，結(jié)合指令Cache和寄存器壓力完善展開因子計(jì)算(版本A3)，此時(shí)展開因子為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時(shí)其他課題如410.bwaves、435.gromacs、437.leslie3d、447.dealII、470.lbm、400.perlbench、464.h264ref、BT、CG、FT、MG和UA等，分別相比使用版本A1時(shí)有3%～8%的加速效果。

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

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

4.4 Hygon平臺(tái)測(cè)試

海光平臺(tái)上的SPEC和NPB測(cè)試結(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ù)限制，導(dǎo)致選取的展開因子較小或不能進(jìn)行循環(huán)展開。針對(duì)這種情況，通過指令Cache調(diào)整循環(huán)展開指令數(shù)限制(版本A2優(yōu)化)，增加循環(huán)的優(yōu)化機(jī)會(huì)，其中性能提升較好的課題有459.GemsFDTD、436.cactusADM和SP，其展開因子由原本的0，0和2，均增加到了8，較原始循環(huán)展開優(yōu)化分別提升了 25%,23%和18%?？紤]寄存器壓力對(duì)循環(huán)展開的影響，結(jié)合指令Cache和寄存器壓力對(duì)展開因子計(jì)算進(jìn)行完善(版本A3優(yōu)化)，展開因子分別為4，2和4，性能較版本A2的進(jìn)一步提升了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平臺(tái)和Hygon平臺(tái)上的測(cè)試結(jié)果來看，結(jié)合指令Cache和寄存器壓力的循環(huán)展開優(yōu)化方法能夠針對(duì)目標(biāo)架構(gòu)自動(dòng)計(jì)算出合適的展開因子，提升了程序性能，但仍有需要改進(jìn)之處。在當(dāng)前的實(shí)現(xiàn)中，代價(jià)模型對(duì)寄存器溢出是零容忍的，即只要存在寄存器溢出就拒絕展開。這種對(duì)寄存器壓力的評(píng)估和使用方式是過于簡(jiǎn)單和嚴(yán)苛的，可能使程序丟失潛在的優(yōu)化機(jī)會(huì)，導(dǎo)致性能下降，需要結(jié)合優(yōu)化之間的相互作用，做出改進(jìn)。

5 結(jié)束語

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

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