面向DSP的零開銷循環(huán)編譯優(yōu)化

項(xiàng)利萍　王向前

摘要：魂芯DSP是一款具有分簇結(jié)構(gòu)的、支持SIMD的VLIW高性能通用處理器。為了提高循環(huán)執(zhí)行的效率，魂芯DSP設(shè)計(jì)了硬件支持的零開銷循環(huán)機(jī)制。提出了一個(gè)通用的從編譯層面支持的零開銷循環(huán)的識(shí)別轉(zhuǎn)換算法。以典型的DSP測試用例進(jìn)行實(shí)驗(yàn)評測，零開銷循環(huán)的識(shí)別可以帶來6%～37%的性能提升。

關(guān)鍵詞：循環(huán)執(zhí)行；零開銷循環(huán)；識(shí)別轉(zhuǎn)換算法

中圖分類號：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1009-3044（2015）12-0100-03

Compiler Optimization on Zero-overhead Loop for DSP

XIANG Li-ping， WANG Xiang-qian

（No.38 Research Institude，China Electronics Technology Group Corporation，Hefei 230088， China）

Abstract： BWDSP is a VLIW DSP processor supporting cluster and SIMD. In order to improve the efficiency of loop execution， the DSP provides hardware support for zero-overhead loop mechanism. A general framework for zero-overhead loop recognization as well as transformation on level of compiler is presented. Through the classsic DSP test set， zero-overhead loop recognization optimization can bring performance improvement ranging from 6% to 37%.

Key words： loop execution； zero-overhead loop； recognization and transformation algorithm

提高循環(huán)執(zhí)行效率有多種軟硬件技術(shù)。硬件技術(shù)包括分支預(yù)測、超標(biāo)量。但這些技術(shù)提高了循環(huán)執(zhí)行效率的同時(shí)，也導(dǎo)致了硬件的復(fù)雜度。而軟件方法循環(huán)展開雖然可以提高性能，但是增加了生成代碼的大小。零開銷循環(huán)[1]是DSP處理器中常見的體系結(jié)構(gòu)特性。它可以加快循環(huán)執(zhí)行的效率而不會(huì)引起生成代碼的增大。零開銷循環(huán)不需要循環(huán)計(jì)數(shù)更新、測試和回跳指令，因此能夠加速處理能力。典型DSP算法很大部分的執(zhí)行時(shí)間[2，3]花費(fèi)在執(zhí)行循環(huán)上，從硬件上支持零開銷循環(huán)對于提高DSP處理器的性能非常必要。零開銷循環(huán)機(jī)制可以在TI、ADI等眾多DSP處理器中發(fā)現(xiàn)，這些廠商提供的編譯器生成循環(huán)代碼時(shí)，已經(jīng)使用零開銷循環(huán)來提高代碼生成質(zhì)量。本文分析BWDSP中編譯器針對循環(huán)代碼效率的瓶頸所在，給出了BWDSP上的零開銷循環(huán)編譯優(yōu)化框架，提出識(shí)別可轉(zhuǎn)化為零開銷循環(huán)的一般性算法；提出零開銷循環(huán)變換的方法。

1 魂芯編譯器循環(huán)生成主要問題

在可重定向編譯基礎(chǔ)設(shè)施IMPACT[4]的基礎(chǔ)上，我們開發(fā)了針對BWDSP體系結(jié)構(gòu)的 C編譯器。

BWDSP C編譯器針對DSP典型程序（如圖1所示） 的循環(huán)生成的代碼如圖2所示。

可見BWDSP100編譯器針對兩個(gè)程序生成的循環(huán)代碼的并行度不高，計(jì)算代碼和循環(huán)控制代碼之間有依賴關(guān)系[5]，循環(huán)控制過程復(fù)雜，需要隨著循環(huán)的迭代同時(shí)計(jì)算步長，如圖3、圖4所示。如果進(jìn)行零開銷循化的變換，可以減小關(guān)鍵路徑，提高循環(huán)執(zhí)行效率。

2 零開銷循環(huán)的識(shí)別和轉(zhuǎn)換

2.1 循環(huán)的正規(guī)表示

一般在循環(huán)的正規(guī)表示[6，7]上進(jìn)行零開銷循環(huán)的識(shí)別。如果一個(gè)循環(huán)不是正規(guī)表示，在進(jìn)行零開銷循環(huán)

換前，則先進(jìn)行一系列的預(yù)處理轉(zhuǎn)化階段：循環(huán)簡化、歸納變量正規(guī)化、尾函數(shù)調(diào)用刪除。

1）循環(huán)簡化

循環(huán)簡化階段轉(zhuǎn)換自然循環(huán)為控制流具有同樣結(jié)構(gòu)的循環(huán)表示。保證每一個(gè)循環(huán)有一個(gè)循環(huán)前置結(jié)點(diǎn)（loop preheader）。另外保證每一個(gè)循環(huán)只有一個(gè)唯一的回邊。循環(huán)前置結(jié)點(diǎn)是在循環(huán)首結(jié)點(diǎn)前面建立的一個(gè)新的基本塊，原來從循環(huán)外進(jìn)入循環(huán)首結(jié)點(diǎn)的所有邊改成指向前置結(jié)點(diǎn)，并且從循環(huán)前置結(jié)點(diǎn)有一個(gè)新的邊指向循環(huán)首結(jié)點(diǎn)。

2）歸納變量正規(guī)化

該預(yù)處理階段是改變具有可識(shí)別歸納變量的循環(huán)為從零開始以一定的步長計(jì)數(shù)的歸納變量形式。如果循環(huán)迭代的次數(shù)可以計(jì)算出來，循環(huán)的退出條件轉(zhuǎn)換為歸納變量和循環(huán)迭代次數(shù)的比較。

3）尾函數(shù)調(diào)用刪除

循環(huán)可以用遞歸函數(shù)實(shí)現(xiàn)，可以轉(zhuǎn)換遞歸函數(shù)為其循環(huán)表示。

2.2 零開銷循環(huán)轉(zhuǎn)換的限制條件

條件1： 循環(huán)體里不能含有函數(shù)調(diào)用。

循環(huán)體里含有函數(shù)調(diào)用的循環(huán)不能進(jìn)行零開銷循環(huán)轉(zhuǎn)換。因?yàn)檎{(diào)用的函數(shù)有可能也包括有零開銷循環(huán)。

條件2： 轉(zhuǎn)換為零開銷循環(huán)的循環(huán)個(gè)數(shù)不能超過硬件提供的零開銷循環(huán)個(gè)數(shù)。

BWDSP支持兩個(gè)硬件零開銷循環(huán)同時(shí)執(zhí)行。

條件3：循環(huán)規(guī)約變量必須是循環(huán)退出條件指令的操作數(shù)。

條件4：如果循環(huán)有多個(gè)出口，則該循環(huán)不能進(jìn)行零開銷循環(huán)轉(zhuǎn)換。

條件5：如果循環(huán)次數(shù)不可數(shù)，則該循換不能進(jìn)行零開銷循環(huán)轉(zhuǎn)換。

循環(huán)次數(shù)可數(shù)，是指循環(huán)次數(shù)可以用一個(gè)寄存器或者立即數(shù)表示。

2.3 零開銷循環(huán)的轉(zhuǎn)換

進(jìn)行零開銷循環(huán)的轉(zhuǎn)化是在以上所有判斷條件都滿足的情況下才能進(jìn)行。

零開銷循環(huán)轉(zhuǎn)換分為三步。第一步，在preheader插入循環(huán)次數(shù)到零開銷循環(huán)寄存器的拷貝指令；第二步是用零開銷循環(huán)指令替換循環(huán)跳轉(zhuǎn)條件；第三步驟把轉(zhuǎn)換之后不需要的循環(huán)歸納條件和比較指令刪除以及產(chǎn)生的其它冗余指令刪除。

第二步中，循環(huán)跳轉(zhuǎn)指令分為兩種情況討論。

1）循環(huán)跳轉(zhuǎn)指令由條件跳轉(zhuǎn)指令和跟著的無條件跳轉(zhuǎn)指令組成。這種情況下條件判斷跳轉(zhuǎn)指令的跳轉(zhuǎn)目標(biāo)是否落在循環(huán)體外。如果是，則保留該跳轉(zhuǎn)指令。如果不是，則予以刪除。

2）循環(huán)跳轉(zhuǎn)指令只有一個(gè)條件跳轉(zhuǎn)指令，直接跳到循環(huán)起始處。直接把該指令替換為零開銷循環(huán)指令。

2.4 實(shí)現(xiàn)算法

在循環(huán)的正規(guī)表示形式上實(shí)現(xiàn)零開銷循環(huán)識(shí)別轉(zhuǎn)換算法[8-10]，如圖5所示。

3 實(shí)例分析

圖2（a）中循環(huán)體執(zhí)行需要10個(gè)周期，而在進(jìn)行零開銷循環(huán)轉(zhuǎn)換后的代碼，如圖6（a）上所示，循環(huán)體執(zhí)行只需要7個(gè)周期，執(zhí)行效率提高約30%。圖2（b）中循環(huán)體執(zhí)行需要8個(gè)周期，而在進(jìn)行零開銷循環(huán)轉(zhuǎn)換后，如圖6（b）上所示，循環(huán)體執(zhí)行只需要5個(gè)周期，執(zhí)行效率提高約37%?？梢娏汩_銷循環(huán)的識(shí)別和轉(zhuǎn)換極大地提高了循環(huán)的執(zhí)行效率。在進(jìn)行零開銷循環(huán)轉(zhuǎn)換后，消除了循環(huán)體中計(jì)算部分和循環(huán)控制部分的不必要的依賴關(guān)系，使得計(jì)算部分和循環(huán)控制部分的關(guān)聯(lián)代碼降至最少。

4 測試結(jié)果

選取數(shù)字信號處理的典型應(yīng)用dspstone[11]作為性能測試集合，圖7為零開銷循環(huán)優(yōu)化在各個(gè)典型應(yīng)用上的性能提升百分比。

可見，零開銷循環(huán)識(shí)別技術(shù)使得測試集合獲得不同程度的性能，從6%～37%。程序在零開銷循環(huán)識(shí)別技術(shù)下性能提升的百分比取決于零開銷循環(huán)技術(shù)可以節(jié)省的周期在整個(gè)循環(huán)體執(zhí)行周期占的百分比。這是不同的測試用例獲得不同的性能提升的原因。

5 結(jié)束語

本文分析了魂芯DSP C編譯器生成循環(huán)代碼效率的主要問題所在，提出了一般性的零開銷循環(huán)的識(shí)別和轉(zhuǎn)換算法。最后通過dspstone測試集驗(yàn)證了零開銷循環(huán)優(yōu)化取得的效果，dspstone測試集合用例獲得了6%～37%的代碼執(zhí)行效率的提升。

參考文獻(xiàn)：

[1] Eyre J， Bier J. The evolution of DSP processors[J]. IEEE Signal Processing Magazine， 2000， 17（2）： 43-51.

[2] 吳強(qiáng)， 任琳， 張杰，等. 快速歸一化互相關(guān)算法及 DSP 優(yōu)化實(shí)現(xiàn)[J]. 電子測量與儀器學(xué)報(bào)， 2011， 25（6）： 495-499.

[3] 牛海軍， 樊瑜波， 楊松巖， 等. 基于 ARM 和 DSP 的超聲膀胱容積檢測與預(yù)警系統(tǒng)的設(shè)計(jì)[J]. 儀器儀表學(xué)報(bào)， 2011， 32（8）：1858-1863.

[3] HU W M.The IMPACT Research Group[EB/OL].http：//impact.crh

c.illinois.edu/.

[4] Allen R， Kennedy K. Optimizing compilers for modern architectures[M]. San Francisco： Morgan Kaufmann， 2002.

[5] Novillo D. Tree SSA A New Optimization Infrastructure for GCC[C]//Proceedings of the 2003 GCC Developers Summit. 2003： 181-193.

[6] Liu S M， Lo R， Chow F. Loop induction variable canonicalization in parallelizing compilers[C]//Parallel Architectures and Compilation Techniques， 1996：Proceedings of the 1996 Conference on. IEEE， 1996： 228-237.

[7] Uh G R， Wang Y， Whalley D， et al. Effective exploitation of a zero overhead loop buffer[C]//ACM SIGPLAN Notices. ACM， 1999， 34（7）： 10-19.

[8] Uh G R， Wang Y， Whalley D， et al. Techniques for effectively exploiting a zero overhead loop buffer[C]//Compiler Construction. Springer Berlin Heidelberg， 2000： 157-172.

[9] Cao V P， Fajardo L A， Jinturkar S， et al. Compiler optimization techniques for exploiting a zero overhead loop mechanism： U.S. Patent 6，367，071[P]. 2002-4-2.

[10] The Institute for Integrated Signal ProcessingSystems.

DSPstone[EB/OL].http：//www.ert.rwth-aachen.de/Projekte/Tools/DSPSTONE/dspstone.