BWDSP104X多條件謂詞編譯優化①

韓東科,鄭啟龍,張仁高

1(中國科學技術大學 計算機科學與技術學院,合肥 230027)2(中國科學技術大學 安徽省高性能計算重點實驗室,合肥 230027)

程序中的條件分支是影響程序性能的一個重要因素.其一,降低調度性能[1].條件分支會分割基本塊規模,將一個基本塊變成多個基本塊,從而使可調度區域減小,不利于指令調度.其二,減弱甚至中斷指令流水.分支后的指令是否執行需要根據當前分支的執行結果進行判斷,因此當程序中含有大量的條件分支時,會中斷指令流水,變指令為串行執行.

為了減弱條件分支對程序性能的影響,傳統的方式是采用分支預測,即在指令調度之前預測哪條分支指令會被執行,然而當條件分支預測失敗時,將會導致流水線中斷,減弱指令流水的性能.分支預測并沒有對條件分支和多個條件分支之間的控制依賴關系進行處理,謂詞執行從根本上消除程序中的跳轉分支,完成從控制相關到數據相關的轉化,改變基本塊內部的控制依賴關系,從而有利于指令流水和指令級并行.但利用謂詞執行技術在處理多條件分支時只是局部的消除程序中的跳轉指令,從全局范圍來看多條件分支之間依然存在跳轉指令和控制依賴關系.

本文針對傳統謂詞優化在處理多條件謂詞時的局限性,提出一種基于BWDSP104X體系結構下多條件謂詞編譯優化方法,以此消除多條件謂詞的跳轉分支及多謂詞之間的控制依賴關系,從而實現指令流水,達到指令級并行效果,提高程序運行效率.

1 概述

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

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

在國內對謂詞編譯優化也作了大量的研究,中國科學院計算技術研究所蘆運照等[5]對IA-64體系結構下的謂詞優化進行了深入的研究,提出了謂詞敏感的數據流分析技術,使得謂詞間關系得到了更精確的描述.國防科學技術大學田祖偉等[6]對謂詞執行的IF轉換技術進行了詳細的研究,包括IF轉換分支的選擇、IF轉換時機的選擇對程序性能的影響.

1.1 BWDSP104X謂詞指令

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

1.2 BWDSP104X編譯器謂詞優化流程

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

圖1 謂詞執行流程

2 BWDSP104X多條件謂詞編譯優化實現

2.1 傳統謂詞優化針對多條件謂詞的局限性

傳統謂詞的優化形式為:

p1,p2=cond1

(p1)branch1

(p2)branch2

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

傳統的謂詞優化技術對多條件分支的優化提供了一種可借鑒的實現思路,但存在以下幾點不足之處:

(1)傳統的謂詞優化技術僅對單條件分支有很好的優化效果,對多條件分支的優化不能很好的支持.

(2)傳統的謂詞優化技術是在一個局部的基本塊內實現的,對多條件分支的全局謂詞關系不能很好的描述.

(3)傳統謂詞優化技術并不能很好的處理多條件分支間的跳轉和控制依賴關系.

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

2.2 多條件謂詞編譯優化實現

傳統的謂詞編譯框架主要包三個步驟:將區域初始化生成條件轉換候選結構的必備信息,尋找合適的候選區域,對候選區域進行轉換生成謂詞化代碼.具體流程如圖6所示.

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

圖2 多條件謂詞示例1

圖3 示例1傳統謂詞優化生成匯編

圖4 多條件謂詞示例2

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

圖5 示例2傳統謂詞優化生成匯編

圖6 傳統謂詞編譯優化框架

圖7 改進謂詞編譯優化框架

圖8 全局謂詞控制路徑圖

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

圖9 謂詞化指令

對比圖3可以看出,改進后的謂詞優化消除了跳轉分支,將多個基本塊合并為一個基本塊.同樣,對于圖5進行全局謂詞關系分析后,可以消除多謂詞之間的控制依賴,從而解決傳統謂詞在優化多條件謂詞的不足,提高程序性能.

2.3 BWDSP104X體系下匯編指令生成

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

圖10 BWDSP104X體系匯編代碼

3 實驗結果和分析

本文在BWDSP104X上實現了多條件謂詞編譯優化算法,為了驗證編譯優化的的效果,我們選取DSPstone以及DSP廣泛應用的圖形圖像處理領域的實例進行測試.為了更好的說明實驗結果,表1給出了測試用例中的核心代碼.

表1 測試用例及核心代碼

在進行測試時,選取向量的規模大小為N=2048,并在BWDSP調試器ECS(Effective Coding Studio)中來測試謂詞編譯優化生成匯編指令的時鐘周期,具體結果如表2所示.

表2 優化前后時鐘周期數

從表2可以看出當程序中不含有跳轉語句(vector_dot)或者僅含有單條件跳轉分支(vector_max)時,優化前后的兩種謂詞模式持平,實際上在此種情形下,兩種謂詞模式產生相同的謂詞控制指令.但對于程序中含有多條件分支(sign,vector_sum)時,相對于傳統謂詞優化模式,新的謂詞優化算法在匯編指令周期上有很大的性能提升,這是因為改進的謂詞優化算法消除了程序中多條件分支間的控制依賴和分支跳轉指令.

4 結語

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

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 蘆運照.謂詞相關編譯技術和深層代碼優化[博士學位論文].北京:中國科學院研究生院(計算技術研究所),2004.

6 田祖偉.基于IA-64謂詞執行的IF轉換技術研究[碩士學位論文].哈爾濱:國防科學技術大學,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.