樊永朝, 鄭啟龍, 耿 銳, 王向前, 王 昊

1(中國科學技術大學 安徽省高性能計算重點實驗室, 合肥 230027)2(中國科學技術大學 計算機科學與技術學院, 合肥 230027)3(中國電子科技集團公司 第三十八研究所, 合肥 230088)

BWDSP10x上地址和數據謂詞執(zhí)行的編譯優(yōu)化①

樊永朝1,2, 鄭啟龍1,2, 耿 銳3, 王向前3, 王 昊3

1(中國科學技術大學 安徽省高性能計算重點實驗室, 合肥 230027)2(中國科學技術大學 計算機科學與技術學院, 合肥 230027)3(中國電子科技集團公司 第三十八研究所, 合肥 230088)

傳統(tǒng)的謂詞優(yōu)化技術是在馮·諾伊曼體系結構計算機上實施的, 僅對數據流進行優(yōu)化, 并沒有考慮哈佛體系結構下指令和數據分開的情況. BWDSP10x是指令和數據分開的哈佛體系結構, 它支持超長指令字, 不僅提供了對數據謂詞執(zhí)行的支持也提供了對地址謂詞執(zhí)行的支持. 特此提出了一種在區(qū)域上對兩種謂詞模式優(yōu)化支持的方法, 在進行兩種比較之前, 通過判斷比較操作的兩個操作數類型來分別實施兩種模式的謂詞優(yōu)化, 使得對地址的比較不用傳輸到通用寄存器中. 實驗結果表明該優(yōu)化方法能顯著地節(jié)省CPU的時間和帶寬, 大大減少了分支指令, 使程序性能提高了28.4%.

地址謂詞執(zhí)行; 數據謂詞執(zhí)行; 區(qū)域; 編譯優(yōu)化

指令在執(zhí)行中要經歷取指、譯碼、執(zhí)行、存取等階段. 現(xiàn)在的處理器中大多都有多個執(zhí)行單元, 從而能使上述過程實現(xiàn)指令流水, 達到指令級并行的效果.但由于程序中條件分支的存在, 使指令流水停頓, 減弱了指令流水的效果. 為了減弱條件分支對指令流水的影響, 傳統(tǒng)的優(yōu)化方法有軟件流水[1]、指令調度[2]、分支預測[3]等, 軟件流水和指令調度通過循環(huán)展開,調整指令之間的次序來減弱分支指令對指令流水的影響, 但沒有從根本上消除條件分支. 分支預測使用分支預測器來猜測哪條分支將會被執(zhí)行, 它的缺點是當發(fā)生分支誤預測時, 流水線的性能大大降低.

解決條件分支的另一種方法是謂詞執(zhí)行[4], 利用條件轉換[5]使所有可能的分支路徑都被編碼, 在實際執(zhí)行中使一些指令執(zhí)行, 另一些指令不執(zhí)行. 謂詞執(zhí)行的基本思想是每條指令和一個謂詞相關, 只有當謂詞為真時指令才被執(zhí)行, 這樣便消除了條件分支, 使被條件分支分割的多個基本塊合為一個基本塊, 雖然增加了基本塊的長度, 但和減少的分支停頓相比這點代價很小. 傳統(tǒng)的謂詞優(yōu)化[6]僅僅針對馮·諾伊曼體系結構, 對地址和數據的謂詞優(yōu)化都放在通用寄存器中比較, 而BWDSP10x的哈佛體系結構指令和數據是分開的, 地址和數據的比較操作都采用一種模式不能充分利用處理器的資源.

本文基于BWDSP10x體系結構提出了一種對地址和數據比較都進行謂詞優(yōu)化的方法, 對條件分支中地址和數據的比較分開進行, 減少了不必要的數據傳輸, 提高了帶寬利用率, 使流水線停頓的次數大大減少, 從而提高了程序性能.

1 編譯器框架

1.1 BWDSP10x體系結構

BWDSP10x處理器[7]是一款32位靜態(tài)超標量處理器, 采用16發(fā)射、SIMD(單指令流, 多數據流)架構. BWDSP10x處理器內核有4個運算宏, 每個運算宏由8個算術邏輯單元、4個乘法器、2個移位器、1個超算器、1個8位數據謂詞寄存器以及1個通用寄存組組成. 運算宏之間通過宏間傳輸總線通信. 內部運算單元和存儲器之間的數據交換所需的存儲器地址主要是通過內部若干個地址發(fā)生器來提供. BWDSP10x內部有三個地址發(fā)生器(U/V/W), 地址發(fā)生器由三部分構成: 瞬時地址運算器、地址更新運算器和16個寄存器組構成的地址寄存器組, 每個地址寄存器位寬為32位.

1.2 BWDSP10x編譯器謂詞優(yōu)化框架

BWDSP10x的編譯器基于開源編譯器OPEN64, OPEN64前端是GCC, 后端構建在WHIRL中間語言的基礎上, OPEN64是為Intel IA64提供編譯優(yōu)化支持的[5]. BWDSP10x的謂詞模塊在后端代碼生成(CG)階段, 在CG階段開始后, 以中間語言VL WHIRL作為輸入, 經過CG expansion、生成region tree信息后開始以區(qū)域[8]為單元執(zhí)行謂詞優(yōu)化. 圖1描述了BWDSP10x謂詞執(zhí)行優(yōu)化框架, 其中謂詞定義指令生成、謂詞執(zhí)行指令生成構成了本文謂詞優(yōu)化算法.

2 添加機器描述

現(xiàn)階段為了支持多種目標體系結構, 許多編譯器基礎設施都采用了機器描述[9]的方式來對目標機的資源進行描述, OPEN64也是如此. 為了提供對BWDSP10x謂詞的支持, 則需要添加BWDSP10x謂詞指令的描述. BWDSP10x謂詞部分的機器描述包括地址謂詞U/V/W描述和數據謂詞CPred描述兩部分, 它們主要由以下幾部分構成:

圖1 BWDSP10x謂詞執(zhí)行優(yōu)化框架

3 區(qū)域信息生成

區(qū)域是一個流圖中只有單個入口結點的部分, 用區(qū)域可以很方便地進行控制流優(yōu)化. 區(qū)域有5種, 分別是: 根區(qū)域、多入口多出口區(qū)域、單入口多出口區(qū)域、不可規(guī)約區(qū)域、循環(huán)區(qū)域, 其中根區(qū)域是區(qū)域樹最外層區(qū)域[10]. 一個自然循環(huán)就是一個區(qū)域, 但區(qū)域不一定包含一條回邊. 為了構造區(qū)域, 必須找到自然循環(huán), 然后分析它的區(qū)域結構. 任何兩個自然循環(huán)要么不相交, 要么一個循環(huán)嵌套在另一個循環(huán)里. 沒有循環(huán)的基本塊本身就是一個區(qū)域. 一個程序的流圖分為可規(guī)約流圖和不可規(guī)約流圖. 對于可規(guī)約流圖, 把每個基本塊當做一個區(qū)域, 把循環(huán)從內到外排序, 對每一個自然循環(huán)構造循環(huán)體區(qū)域和循環(huán)區(qū)域, 完成對循環(huán)的規(guī)約, 規(guī)約完成后所有的循環(huán)都被規(guī)約為單個結點. 規(guī)約過程: 首先處理自然循環(huán), 直到流圖中包含環(huán)沒有回邊, 剩下不可規(guī)約的部分. 不可規(guī)約的部分盡管可以用結點分割的技術成為可規(guī)約的, 但由于時間復雜度較高, 本文不對此進行處理, 但必須把用強連通分量算法[11]找出不可規(guī)約區(qū)域, 供謂詞優(yōu)化階段優(yōu)化使用. 對于重疊的循環(huán),考慮到時間復雜度, 不需要進一步優(yōu)化. 最后, 對所有的區(qū)域進行分解提高目標機資源利用效率. 構建區(qū)域樹算法偽代碼, 如圖2所示.

圖2 區(qū)域樹算法

算法輸入為函數中的第一個基本塊first_bb, 輸出為一個區(qū)域樹, 樹上每一個結點代表一個區(qū)域. 首先創(chuàng)建基本塊結點映射, 把每個基本塊映射到相對應的區(qū)域控制流結點上, 然后增加區(qū)域樹的根結點, 根據全局數據流圖構建局部區(qū)域控制流圖, 在構建區(qū)域控制流圖的同時計算相應的入口和出口信息, 最后處理循環(huán)和不可規(guī)約的部分以及重疊的非自然循環(huán).

在構建區(qū)域樹算法中處理循環(huán)和不可規(guī)約部分是在區(qū)域控制流圖中進行的, 先找出環(huán), 然后計算關鍵邊和回邊找到強連通分量, 構建循環(huán)區(qū)域和不可規(guī)約區(qū)域. 處理循環(huán)和不可規(guī)約部分算法偽代碼如圖3所示.

圖3 處理循環(huán)和不可規(guī)約算法

盡管區(qū)域越大越好, 但如果區(qū)域超出了目標機的資源約束, 則會導致程序執(zhí)行效率[6]降低. 因此, 區(qū)域樹算法最后一步是按照目標機的體系結構對所有的區(qū)域進行分解, 把所有區(qū)域分解為較小的區(qū)域, 以最大利用目標機資源. 區(qū)域最終被分解為單入口多出口區(qū)域供后面謂詞優(yōu)化階段使用. 區(qū)域分解算法偽代碼如圖4所示.

圖4 區(qū)域分解算法

4 謂詞優(yōu)化算法

BWDSP10x和IA64一樣也提供了謂詞指令, 但BWDSP10x和IA64有兩點區(qū)別: 一、BWDSP10x是指令和數據分開的哈佛體系結構, 而IA64是傳統(tǒng)的馮·諾伊曼體系結構, 因此BWDSP10x支持U/V/W地址謂詞和CPred數據謂詞兩種模式; 二、IA64支持全謂詞執(zhí)行技術, 在指令執(zhí)行前利用每條指令的限定謂詞來決定此指令是否執(zhí)行, 不需要單獨的謂詞執(zhí)行指令,而BWDSP10x只支持部分謂詞, 需要單獨的謂詞執(zhí)行指令.

BWDSP10x的地址謂詞寄存器有16個, 當做謂詞寄存器使用時, 可使用其中的8位. 數據謂詞寄存器即每一個執(zhí)行宏上的一個獨立的8位CPred寄存器. U/V/W地址模式中把兩個地址比較結果放在地址發(fā)生器U/V/W中的一個地址寄存器的一位中, 此時地址寄存器中存的是立即數. CPred數據模式是把兩個數據比較的結果放在一個8位謂詞寄存器CPred中的一位中,此時CPred中存的也是立即數.

BWDSP10x兩種謂詞指令分別支持兩種不同的謂詞模式. 每一種指令都定義了謂詞定義指令、謂詞執(zhí)行指令. 其中U/V/W模式還定義了謂詞傳輸指令, 其原因是謂詞定義指令的結果和源操作數都是地址, 而條件分支中的兩個操作數之一可能是立即數或數據,需要把其傳輸到地址寄存器中. CPred模式中的謂詞定義指令中的兩個源操作數都是數據, 比較操作可以在通用寄存器中進行, 因此不需要謂詞傳輸指令.

4.1 謂詞定義指令生成

謂詞定義指令生成是指把編譯器中間代碼生成的比較指令替換為謂詞指令的過程.

BWDSP10x的U/V/W地址謂詞定義指令中的U地址指令形式如表1所示, V/W地址形式類似, 這些指令均為單字指令. 其中, s、m、n為地址謂詞寄存器的編號. 指令含義為根據Um和Un的比較結果對Us的第K位置位. 若比較結果為真, Us第[k]位置為1, 否則置為0, 0＜=k＜8. 本指令由U地址發(fā)生器中的“加法/移位”部件執(zhí)行.

BWDSP10x的CPred數據謂詞定義指令中的指令形式如表2所示, 這些指令均為雙字指令. 其中, x、y、z、t為運算宏的編號, m, n為通用寄存器編號.指令含義為在四個運算宏之一內根據Rm和Rn的比較結果對CPred的第k位置位. 若比較結果為真, CPred第k位置為1, 否則置為0, 0＜=k＜8. 第k個ALU控制CPred寄存器的第k位, 本指令由第k個ALU執(zhí)行.

表1 U/V/W地址謂詞定義指令形式

表2 CPred數據謂詞定義指令形式

由上可知, 在生成謂詞定義指令時需要對謂詞寄存器每一位進行編號確定運算單元比較結果置位的位置. 兩種謂詞寄存器的謂詞定義指令比較結果安排方式一樣. 謂詞寄存器的每一位表示一個比較條件, 8位代表在一個函數中, 一個if語句中最多能有8個比較條件或者最多有8層的if-else嵌套, 在一個if-else中每個條件置位謂詞寄存器的一位. 置位的順序從第一個比較條件開始置位謂詞寄存器最低位, 根據BWDSP10x指令集謂詞執(zhí)行指令, 當k為0時指令必須執(zhí)行, 因此謂詞寄存器最低位從1開始標號, 而不是0. 謂詞定義比較結果安排示意如表3所示.

表3 謂詞定義中比較結果安排

謂詞定義指令生成的算法流程和算法偽代碼分別如圖5和圖6所示.

在生成謂詞定義指令時, 在找到分支指令后, 判斷分支指令里比較的兩個操作數之一是否為地址來決定采用哪一種謂詞模式. 如果兩個操作數均為數據則生成CPred謂詞定義指令, 若其中一個操作數為地址另一個操作數為數據, 則把為數據操作數傳輸到地址寄存器中, 生成U/V/W謂詞定義指令. 在生成U/V/W謂詞定義指令和CPred謂詞定義指令之前要分別初始化一個虛擬謂詞寄存器u0和對應執(zhí)行宏的CPred, 并分別對兩種模式條件分支進行計數, 計數變量為全局變量ak、ck, 初值設為0, ak、ck同時指明了要置位的謂詞寄存器位編號, 選擇哪個執(zhí)行宏上的cpred寄存器要根據操作數的執(zhí)行宏來決定,當ak、ck、以及要使用的謂詞寄存器確定后就可以插入如上的謂詞定義指令.

4.2 謂詞執(zhí)行指令生成

在謂詞定義指令生成后開始謂詞執(zhí)行指令的生成,謂詞執(zhí)行指令的生成過程也是把跳轉分支合并為單個基本塊的過程. 在IA64中這是通過在跳轉目標塊前加上限定謂詞實現(xiàn)的, 而在BWDSP10x采用的是生成謂詞執(zhí)行指令的方式實現(xiàn).

BWDSP10x的U/V/W地址謂詞執(zhí)行指令中的U地址指令形式如表4所示, V/W地址格式類似, 這些指令均為雙字指令. 指令判斷Um對應K1為1位置的數據是否等于常數C1對應K1為1的位置的數據, 若判斷結果為真, 則執(zhí)行當前指令行中該指令后的前n條指令, 包括所有指令類型.

BWDSP10x的CPred數據謂詞執(zhí)行指令中的指令形式如表5所示, 這些指令均為雙字指令. 指令判斷CPred對應K1為1位置的數據是否等于常數C1對應K1為1的位置的數據, 若判斷結果為真, 則執(zhí)行當前指令行中該指令后的前n條指令, 只控制這些指令中受CPred控制的指令. 本指令不能控制非運算指令、宏間傳輸指令、訪存指令(無論讀或寫)等執(zhí)行單元不在宏內的指令.

圖5 謂詞定義指令生成算法流程圖

表4 U/V/W地址謂詞執(zhí)行指令形式

圖6 謂詞定義指令生成算法偽代碼

表5 CPred數據謂詞執(zhí)行指令格式

一個常見的帶多個條件分支的區(qū)域通過謂詞執(zhí)行技術規(guī)約過程如圖7. 首先過程1中基本塊2, 3合并到基本塊1中, 7合并到6中, 完成一次規(guī)約后刪除條件分支, 轉變?yōu)檫^程2, 再進行規(guī)約刪除條件分支最終轉換為過程3. 算法流程如圖8, 具體算法偽代碼如圖9所示.

圖7 條件分支轉換規(guī)約過程

圖8 條件轉換規(guī)約算法流程圖

圖9 謂詞執(zhí)行指令生成算法偽代碼

算法首先查找前面生成的謂詞定義指令, 根據謂詞定義指令的操作碼決定是生成U/V/W地址謂詞執(zhí)行指令還是CPred數據謂詞執(zhí)行指令. 然后獲得當前謂詞定義指令中的謂詞寄存器被置位的k和常量2^(result_k-1)相比較得到條件比較結果對跳轉目標或落入分支設置限定謂詞, 即生成謂詞執(zhí)行指令. 在生成CPred數據謂詞執(zhí)行指令時, 需要把設置限定謂詞的基本塊中不受CPred控制的指令移動到謂詞執(zhí)行指令的前面; 而且, 由于在CPred數據謂詞定義指令生成時已經確定了執(zhí)行宏, 此時不再需要重新確定執(zhí)行宏.

5 實例分析

常見的地址比較條件分支程序優(yōu)化前和優(yōu)化后對比如圖10所示.

常見的數據比較條件分支程序優(yōu)化前和優(yōu)化后對比如圖11所示.

圖10 地址比較條件分支優(yōu)化前后對比

圖11 數據比較條件分支優(yōu)化前后對比

實驗選取了SPEC CPU 2006 測試項目中的五個程序來驗證在打開謂詞優(yōu)化選項后的優(yōu)化結果. 這五個程序分別是壓縮程序bzip2、組合優(yōu)化mcf、尋路算法astar、有限元分析dealII、影像光線追蹤povray, 這些程序在DSP領域應用很廣泛.

這五種程序單獨實施地址謂詞優(yōu)化結果如表6所示.

表6 實施地址謂詞優(yōu)化前后對比

這五種程序單獨實施數據謂詞優(yōu)化結果如表7所示.

表7 實施數據謂詞優(yōu)化前后對比

這五種程序同時實施兩種謂詞優(yōu)化結果如表8所示.

表8 同時實施兩種謂詞優(yōu)化前后對比

從以上實驗結果可以看出, 表6中單獨實施地址謂詞優(yōu)化程序性能平均提升了17%; 表7中單獨實施數據謂詞優(yōu)化程序性能平均提升了10%; 從表6和表7的結果可以看出, 由于增加了地址謂詞的優(yōu)化, 使對地址的比較不用傳輸到通用寄存器中再進行比較, 節(jié)省了時間和帶寬, 比傳統(tǒng)的單一謂詞優(yōu)化模式性能有很大提升; 從表8可以看出尋路算法和影像光線追蹤優(yōu)化效果要比壓縮程序好, 說明謂詞優(yōu)化技術特別適用于地址比較條件分支和數據比較條件分支較多的程序, 表8中同時實施兩種謂詞優(yōu)化程序性能平均提升了28.4%, 說明實施謂詞優(yōu)化后消除了一部分分支指令減少了流水線停頓使指令流水效率大大提高了.

6 結語

本文針對BWDSP10x體系結構提供的謂詞指令,提出了一種條件分支轉換的方法. 通過生成謂詞定義指令和謂詞生成指令, 使源程序的條件分支基本塊可以合并為一個基本塊, 充分提高了程序的并行性. 這種方法適合指令和數據分開的哈佛結構, 能對地址和數據的條件分支優(yōu)化分開進行, 進一步提高了程序的效率. 本文只對兩種謂詞模式的生成做了研究, 接下來還應在生成的謂詞指令的基礎上進行各種數據流優(yōu)化分析.

1 馮玉謙.基于多簇VLIW軟件流水及相關編譯優(yōu)化技術研究[碩士學位論文].合肥:中國科學技術大學,2013.

2 付和萍.基于超長指令字的全局無環(huán)指令調度和復數乘法優(yōu)化設計[碩士學位論文].合肥:中國科學技術大學,2013.

3 黃偉,王玉艷,章建雄.嵌入式處理器動態(tài)分支預測機制研究與設計.計算機工程,2008,34(21):163–165.

4 Gary ST. The effects of predicated execution on branchprediction. Proc. of the 27th Annual International Symposium on Microarchitecture. 1994. 196–206.

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

6 劉旸.基于區(qū)域的編譯技術和棧寄存器優(yōu)化[博士學位論文].北京:中國科學院研究生院計算技術研究所,2003.

7 CETC. BWDSP100軟件用戶手冊.合肥:中國電子科技集團公司第三十八研究所,2013:1–2.

8 Aho AV, Lam MS, Sethi R, et al. Compilers: Principles, Techniques, and Tools. 2nd ed., Beijing: China Machine Press, 2009: 428–436.

9 楊萍,王生原.用于多目標編譯系統(tǒng)構造的目標機體系結構描述.計算機科學,2005,32(9):239–242.

10 劉旸,張兆慶,喬如良.基于域的編譯框架.計算機學報, 2003,26(2):190.

11 Lengauer T, Tarjan R, Endre R. A fast algorithm for finding dominators in a flowgraph. ACM Trans. on Programming Languages and Systems, 1979, 1(1): 121–141.

Compilation Optimization of Address and Data Predicated Execution on BWDSP10x

FAN Yong-Chao1,2, ZHENG Qi-Long1,2, GENG Rui3, WANG Xiang-Qian3, WANG Hao312
(Anhui High Performance Computing Key Laboratory, University of Science and Technology of China, Hefei 230027, China)3(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China) (No. 38th Research Institute, China Electronics Technology Group Corporation, Hefei 230088, China)

The traditional predicate optimization technique is based on the Von Neumann architecture, which considers the data flow optimization only. However, BWDSP10x is based on the Harvard architecture, which data and instructions are physically separated. It provides VLIW and supports not only data predicated execution but also address predicated execution. Hence, we present an optimization method for the two predicated execution technology based on the region. In this method, types of the two operands of comparison operation will be identified before the two kinds of operations are executed, and when addresses are compared, the two operands don’t need to transfer to general registers. Experimental result shows that the optimization method can highly reduce the time and bandwidth of CPU, and reduce large numbers of branch instructions. The performance of programs tested is increased by 28.4 percent after the optimization.

address predicated execution; data predicated execution; region; compilation optimization

“核高基”重大專項(2012ZX01034-00-001)

2016-03-22;收到修改稿時間:2016-06-12

10.15888/j.cnki.csa.005573