韓東科,鄭啟龍,張仁高

1(中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230027)2(中國(guó)科學(xué)技術(shù)大學(xué) 安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室,合肥 230027)

程序中的條件分支是影響程序性能的一個(gè)重要因素.其一,降低調(diào)度性能[1].條件分支會(huì)分割基本塊規(guī)模,將一個(gè)基本塊變成多個(gè)基本塊,從而使可調(diào)度區(qū)域減小,不利于指令調(diào)度.其二,減弱甚至中斷指令流水.分支后的指令是否執(zhí)行需要根據(jù)當(dāng)前分支的執(zhí)行結(jié)果進(jìn)行判斷,因此當(dāng)程序中含有大量的條件分支時(shí),會(huì)中斷指令流水,變指令為串行執(zhí)行.

為了減弱條件分支對(duì)程序性能的影響,傳統(tǒng)的方式是采用分支預(yù)測(cè),即在指令調(diào)度之前預(yù)測(cè)哪條分支指令會(huì)被執(zhí)行,然而當(dāng)條件分支預(yù)測(cè)失敗時(shí),將會(huì)導(dǎo)致流水線中斷,減弱指令流水的性能.分支預(yù)測(cè)并沒有對(duì)條件分支和多個(gè)條件分支之間的控制依賴關(guān)系進(jìn)行處理,謂詞執(zhí)行從根本上消除程序中的跳轉(zhuǎn)分支,完成從控制相關(guān)到數(shù)據(jù)相關(guān)的轉(zhuǎn)化,改變基本塊內(nèi)部的控制依賴關(guān)系,從而有利于指令流水和指令級(jí)并行.但利用謂詞執(zhí)行技術(shù)在處理多條件分支時(shí)只是局部的消除程序中的跳轉(zhuǎn)指令,從全局范圍來看多條件分支之間依然存在跳轉(zhuǎn)指令和控制依賴關(guān)系.

本文針對(duì)傳統(tǒng)謂詞優(yōu)化在處理多條件謂詞時(shí)的局限性,提出一種基于BWDSP104X體系結(jié)構(gòu)下多條件謂詞編譯優(yōu)化方法,以此消除多條件謂詞的跳轉(zhuǎn)分支及多謂詞之間的控制依賴關(guān)系,從而實(shí)現(xiàn)指令流水,達(dá)到指令級(jí)并行效果,提高程序運(yùn)行效率.

1 概述

有關(guān)謂詞執(zhí)行的研究最早是由Allen等人提出的If-conversion的概念[2],這一概念在最初的向量機(jī)上得到了廣泛的應(yīng)用.通過邏輯表達(dá)式的真假來限定程序中的條件分支是否執(zhí)行,這樣便刪除了程序中相應(yīng)的分支跳轉(zhuǎn)指令,有利于代碼的向量化.緊接著,HP實(shí)驗(yàn)室的Park和Schlansker等人改進(jìn)了if-conversion算法并提出了一個(gè)經(jīng)典的RK算法[3],該算法首先對(duì)每個(gè)基本塊之間的控制依賴關(guān)系進(jìn)行分析并建立謂詞控制流圖,然后由謂詞控制流圖來計(jì)算函數(shù)R和K,以此來完成條件分支的謂詞化.

Mahlke等率先提出了Hyperblock編譯優(yōu)化技術(shù)來支持謂詞執(zhí)行[4],Hyperblock是通過采用IF轉(zhuǎn)換多個(gè)條件分支而形成的一個(gè)單入口多出口的謂詞化基本塊的集合,但卻并不是對(duì)程序中所有的條件分支都進(jìn)行條件轉(zhuǎn)換,而是僅僅對(duì)那些有利于程序性能提升的條件分支進(jìn)行轉(zhuǎn)化.

在國(guó)內(nèi)對(duì)謂詞編譯優(yōu)化也作了大量的研究,中國(guó)科學(xué)院計(jì)算技術(shù)研究所蘆運(yùn)照等[5]對(duì)IA-64體系結(jié)構(gòu)下的謂詞優(yōu)化進(jìn)行了深入的研究,提出了謂詞敏感的數(shù)據(jù)流分析技術(shù),使得謂詞間關(guān)系得到了更精確的描述.國(guó)防科學(xué)技術(shù)大學(xué)田祖?zhèn)サ萚6]對(duì)謂詞執(zhí)行的IF轉(zhuǎn)換技術(shù)進(jìn)行了詳細(xì)的研究,包括IF轉(zhuǎn)換分支的選擇、IF轉(zhuǎn)換時(shí)機(jī)的選擇對(duì)程序性能的影響.

1.1 BWDSP104X謂詞指令

BWDSP104X體系下謂詞指令主要包含謂詞定義指令和謂詞執(zhí)行指令生成.謂詞定義指令生成是把中間代碼的比較指令轉(zhuǎn)化為謂詞指令,其指令形式為{x,y,z,t}CPred[k]=Rm＞Rn,其中,x、y、z、t為BWDSP104X多簇運(yùn)算宏編號(hào),Rm,Rn為通用寄存器.指令含義為根據(jù)Rm、Rn寄存器中的比較結(jié)果設(shè)置CPred寄存器中的相應(yīng)位,即若判斷結(jié)果為真,CPred謂詞寄存器第k位為1,否則為0[7].謂詞執(zhí)行指令的生成是消除中間代碼中的分支跳轉(zhuǎn)指令,將條件分支分割的多個(gè)基本塊合并為一個(gè)基本塊,其指令形式為if CPred[K1]==C1 don,即通過判斷CPred對(duì)應(yīng)K1為1位置的數(shù)據(jù)是否等于常數(shù)C1對(duì)應(yīng)K1為1的位置的數(shù)據(jù),若判斷結(jié)果為真,則執(zhí)行當(dāng)前指令行中該指令后的前n條指令[8].

1.2 BWDSP104X編譯器謂詞優(yōu)化流程

BWDSP104X編譯器是基于開源Open64[9]編譯器作為基本框架,其中BWDSP104X的謂詞模塊在后端代碼生成(CG)階段,在CG階段開始后,以中間語言WHIRL[10]作為輸入,經(jīng)過CG expansion、生成region tree信息后開始以區(qū)域[11]為單元執(zhí)行謂詞優(yōu)化.具體優(yōu)化階段如圖1所示,從圖可以看出謂詞執(zhí)行技術(shù)優(yōu)化if-conversion/parallel cmp在生成region formation之后,在軟流水(swp)階段之前,謂詞分析技術(shù)(predicate analysis)在軟流水之后.

圖1 謂詞執(zhí)行流程

2 BWDSP104X多條件謂詞編譯優(yōu)化實(shí)現(xiàn)

2.1 傳統(tǒng)謂詞優(yōu)化針對(duì)多條件謂詞的局限性

傳統(tǒng)謂詞的優(yōu)化形式為:

p1,p2=cond1

(p1)branch1

(p2)branch2

條件分支指令被轉(zhuǎn)換為定義的謂詞p1和p2指令,當(dāng)比較條件cond1結(jié)果為真時(shí),p1為1,p2為0,反之,p1為0,p2為1.然后根據(jù)條件謂詞的值來決定其分支是否執(zhí)行,若p1為1,p2為0,則執(zhí)行branch1,否則執(zhí)行branch2,如此程序中的分支跳轉(zhuǎn)被消除,控制關(guān)系轉(zhuǎn)換為數(shù)據(jù)關(guān)系,達(dá)到謂詞優(yōu)化的目的.但這種形式的優(yōu)化并不能消除多條件謂詞的跳轉(zhuǎn)語句和謂詞之間的控制依賴關(guān)系.

傳統(tǒng)的謂詞優(yōu)化技術(shù)對(duì)多條件分支的優(yōu)化提供了一種可借鑒的實(shí)現(xiàn)思路,但存在以下幾點(diǎn)不足之處:

(1)傳統(tǒng)的謂詞優(yōu)化技術(shù)僅對(duì)單條件分支有很好的優(yōu)化效果,對(duì)多條件分支的優(yōu)化不能很好的支持.

(2)傳統(tǒng)的謂詞優(yōu)化技術(shù)是在一個(gè)局部的基本塊內(nèi)實(shí)現(xiàn)的,對(duì)多條件分支的全局謂詞關(guān)系不能很好的描述.

(3)傳統(tǒng)謂詞優(yōu)化技術(shù)并不能很好的處理多條件分支間的跳轉(zhuǎn)和控制依賴關(guān)系.

圖2實(shí)例中,多條件優(yōu)化后生成的匯編格式圖3,可以看出基本塊之間仍然含有跳轉(zhuǎn)語句分支,圖4實(shí)例經(jīng)過多條件優(yōu)化后生成的匯編格式圖5,其中多個(gè)謂詞之間含有控制依賴關(guān)系,如p3和p4依賴謂詞p2.這兩種多條件謂詞采用傳統(tǒng)謂詞優(yōu)化后都不利于指令流水和指令并行,為此提出一種基于BWDSP104X體系下多條件優(yōu)化編譯框架.

2.2 多條件謂詞編譯優(yōu)化實(shí)現(xiàn)

傳統(tǒng)的謂詞編譯框架主要包三個(gè)步驟:將區(qū)域初始化生成條件轉(zhuǎn)換候選結(jié)構(gòu)的必備信息,尋找合適的候選區(qū)域,對(duì)候選區(qū)域進(jìn)行轉(zhuǎn)換生成謂詞化代碼.具體流程如圖6所示.

上述謂詞優(yōu)化方法對(duì)單條件謂詞優(yōu)化有很好的支持,但對(duì)于多條件謂詞并不能達(dá)到很好的優(yōu)化效果.其主要原因是,多條件謂詞之間往往含有控制依賴關(guān)系,而上述優(yōu)化方法在謂詞轉(zhuǎn)換時(shí)只是局部的進(jìn)行代碼謂詞化,并沒有全局化分析多條件謂詞之間的控制關(guān)系.因此在轉(zhuǎn)換生成謂詞代碼之前進(jìn)行全局的謂詞關(guān)系分析是很有必要的.為此通過改進(jìn)傳統(tǒng)的謂詞編譯框架,提出一種新的謂詞編譯框架,其不僅適用單條件謂詞優(yōu)化,對(duì)多條件謂詞也有很好的支持,具有更廣的適用范圍.改進(jìn)后的謂詞編譯優(yōu)化框架如圖7所示.

圖2 多條件謂詞示例1

圖3 示例1傳統(tǒng)謂詞優(yōu)化生成匯編

圖4 多條件謂詞示例2

下面具體闡述算法改進(jìn)部分Cal_Predicate_Path的實(shí)現(xiàn)過程,首先由起始基本塊出發(fā),沿著控制流方向,不斷迭代,直至找到每個(gè)控制塊的全部控制謂詞路徑.算法實(shí)現(xiàn)的流程如圖8所示.

圖5 示例2傳統(tǒng)謂詞優(yōu)化生成匯編

圖6 傳統(tǒng)謂詞編譯優(yōu)化框架

圖7 改進(jìn)謂詞編譯優(yōu)化框架

圖8 全局謂詞控制路徑圖

由上述的謂詞控制流分析,由于多個(gè)謂詞之間含有控制依賴關(guān)系,一個(gè)基本塊可能含有多個(gè)控制謂詞路徑,如基本塊BB3的控制謂詞路徑為p2或p1p4,其意思為控制謂詞路徑p2或p1p4有一個(gè)成立是,基本塊BB3便執(zhí)行.在計(jì)算出多條件謂詞全局控制路徑后,其執(zhí)行語句所對(duì)應(yīng)的區(qū)塊的每條控制路徑都要插入一條謂詞執(zhí)行指令,如基本塊BB4含有p1p3,p2p5,p1p4p5三條控制路徑,故要插入三條謂詞執(zhí)行指令與其對(duì)應(yīng),(p1p3)re=1,(p2p5)re=1,(p1p4p5)re=1.在基本塊合并過程中主要完成:刪除無用分支指令,即候選區(qū)域中的跳轉(zhuǎn)指令,將代碼按拓?fù)渑判蚺帕?并將其合并到一個(gè)基本塊中.最終生成的謂詞化指令如圖9所示.

圖9 謂詞化指令

對(duì)比圖3可以看出,改進(jìn)后的謂詞優(yōu)化消除了跳轉(zhuǎn)分支,將多個(gè)基本塊合并為一個(gè)基本塊.同樣,對(duì)于圖5進(jìn)行全局謂詞關(guān)系分析后,可以消除多謂詞之間的控制依賴,從而解決傳統(tǒng)謂詞在優(yōu)化多條件謂詞的不足,提高程序性能.

2.3 BWDSP104X體系下匯編指令生成

對(duì)于上述謂詞化指令按照BWDSP104X指令格式進(jìn)行謂詞定義指令和謂詞執(zhí)行指令匯編輸出.由于BWDSP體系下是使用謂詞寄存器中的一位來保存條件判斷的比較結(jié)果,比如第一個(gè)條件分支p1,p2=a＞b,對(duì)應(yīng)的謂詞定義指令為CPred[0]=a＞b.BWDSP謂詞執(zhí)行指令匯編格式為if CPred[K]==C don.其中K值取決于條件分支個(gè)數(shù)m,K=2^m–1,然后由謂詞化指令中控制路徑的加權(quán)值計(jì)算C,比如控制路徑為p1p4p5,C=p1*2^0+p4*2^1+p5*2^(m–1).生成的謂詞執(zhí)行指令為if CPred[7]==5 do 1 || re=1.綜上,上述謂詞化指令轉(zhuǎn)化為BWDSP下匯編形式如圖10所示.

圖10 BWDSP104X體系匯編代碼

3 實(shí)驗(yàn)結(jié)果和分析

本文在BWDSP104X上實(shí)現(xiàn)了多條件謂詞編譯優(yōu)化算法,為了驗(yàn)證編譯優(yōu)化的的效果,我們選取DSPstone以及DSP廣泛應(yīng)用的圖形圖像處理領(lǐng)域的實(shí)例進(jìn)行測(cè)試.為了更好的說明實(shí)驗(yàn)結(jié)果,表1給出了測(cè)試用例中的核心代碼.

表1 測(cè)試用例及核心代碼

在進(jìn)行測(cè)試時(shí),選取向量的規(guī)模大小為N=2048,并在BWDSP調(diào)試器ECS(Effective Coding Studio)中來測(cè)試謂詞編譯優(yōu)化生成匯編指令的時(shí)鐘周期,具體結(jié)果如表2所示.

表2 優(yōu)化前后時(shí)鐘周期數(shù)

從表2可以看出當(dāng)程序中不含有跳轉(zhuǎn)語句(vector_dot)或者僅含有單條件跳轉(zhuǎn)分支(vector_max)時(shí),優(yōu)化前后的兩種謂詞模式持平,實(shí)際上在此種情形下,兩種謂詞模式產(chǎn)生相同的謂詞控制指令.但對(duì)于程序中含有多條件分支(sign,vector_sum)時(shí),相對(duì)于傳統(tǒng)謂詞優(yōu)化模式,新的謂詞優(yōu)化算法在匯編指令周期上有很大的性能提升,這是因?yàn)楦倪M(jìn)的謂詞優(yōu)化算法消除了程序中多條件分支間的控制依賴和分支跳轉(zhuǎn)指令.

4 結(jié)語

本文針對(duì)BWDSP104X體系結(jié)構(gòu),提出一種多條件謂詞編譯優(yōu)化方案.通過全局的謂詞關(guān)系分析,得到每個(gè)控制塊的謂詞控制路徑,進(jìn)而消除多條件謂詞之間的控制依賴關(guān)系和每個(gè)基本塊中的跳轉(zhuǎn)分支,將多個(gè)基本塊合并為一個(gè)基本塊,從而實(shí)現(xiàn)指令流水,達(dá)到指令級(jí)并行效果.實(shí)驗(yàn)結(jié)果表明,該方案在多條件謂詞編譯優(yōu)化方面能夠取得平均5.62倍的加速比.今后,還要對(duì)多謂詞之間的等價(jià)、互斥、互補(bǔ)等關(guān)系進(jìn)行分析,通過建立謂詞關(guān)系數(shù)據(jù)庫(kù)(PRDB),對(duì)編譯器下一優(yōu)化階段的謂詞指令調(diào)度,謂詞寄存器分配以及謂詞數(shù)據(jù)流分析提供更好的謂詞模式支持.

1 Ferrante J,Ottenstein KJ,Warren JD.The program dependence graph and its use in optimization.ACM Transactions on Programming Languages and Systems,1987,9(3):319–349.[doi:10.1145/24039.24041]

2 Allen JR,Kennedy K,Porterfield C,et al.Conversion of control dependence to data dependence.Proceedings of the 10th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages.Austin,TX,USA.1983.177–189.

3 Park JCH,Schlansker MS.On predicated execution.Technical Report HPL-91-58,Palo Alto,CA:Hewlett-Packard Laboratories,1991.

4 Mahlke SA,Lin DC,Chen WY,et al.Effective compiler support for predicated execution using the hyperblock.ACM SIGMICRO Newsletter,1992,23(1-2):45–54.[doi:10.1145/144965]

5 蘆運(yùn)照.謂詞相關(guān)編譯技術(shù)和深層代碼優(yōu)化[博士學(xué)位論文].北京:中國(guó)科學(xué)院研究生院(計(jì)算技術(shù)研究所),2004.

6 田祖?zhèn)?基于IA-64謂詞執(zhí)行的IF轉(zhuǎn)換技術(shù)研究[碩士學(xué)位論文].哈爾濱:國(guó)防科學(xué)技術(shù)大學(xué),2005.

7 China Electronics Technology Group Corporation.CETC38.BWDSP100 hardware user manual.Heifei:China Electronics Technology Group Corporation Research Institute,2011:178–179.

8 China Electronics Technology Group Corporation.CETC38.BWDSP100 hardware user manual.Heifei:China Electronics Technology Group Corporation Research Institute,2011:180–181.

9 Sui YL.Open64 introduction.http://www.cse.unsw.edu.au/～ysui/saber/open64.pdf.[2015-03-17].

10 Open64.Open64 compiler whirl intermediate representation.http://www.mcs.anl.gov/OpenAD/open64A.pdf. [2015-03-17].

11 Aho AV,Lam MS,Sethi R,et al.Compilers:Principles,Techniques,and Tools.2nd ed.Wilmington,DE,USA:Addison Wesley,2006:428–436.