基于ARM9體系架構的編譯優(yōu)化研究

葛吳超，周亦敏

(上海理工大學 光電信息與計算機工程學院，上海 200093)

?

基于ARM9體系架構的編譯優(yōu)化研究

葛吳超，周亦敏

(上海理工大學 光電信息與計算機工程學院，上海 200093)

在嵌入式系統(tǒng)軟件開發(fā)過程中, GCC編譯循環(huán)程序時的窺孔優(yōu)化比較欠缺，編譯代碼在性能上較ARM商業(yè)編譯器低。文中提出針對于ARM9處理器的循環(huán)計數(shù)值組合、循環(huán)處理數(shù)據(jù)合并和循環(huán)最優(yōu)展開等3種窺孔優(yōu)化方法優(yōu)化匯編代碼。選取矩陣乘法，圖像合并和內(nèi)存設置等經(jīng)典程序運行在ARM9平臺上，分別驗證3種窺孔優(yōu)化方法。實驗數(shù)據(jù)表明，與GCC編譯代碼相比，經(jīng)文中提出的方法優(yōu)化后的代碼在寄存器使用數(shù)量上，平均節(jié)省了50%,性能提升近2倍。

窺孔優(yōu)化；循環(huán)計數(shù)值組合；循環(huán)處理數(shù)據(jù)合并；循環(huán)最優(yōu)展開

嵌入式系統(tǒng)中，包含一些決定系統(tǒng)性能的關鍵程序。通過程序優(yōu)化可大幅提升系統(tǒng)的性能，降低系統(tǒng)的整體功耗。優(yōu)化可將一個不可行的系統(tǒng)變得可行，亦可將一個無競爭力的系統(tǒng)變得極具競爭力。對于程序的優(yōu)化，使用傳統(tǒng)的編譯器優(yōu)化可得到性能較好的目標代碼。但要獲得最佳性能，就要通過手寫匯編來優(yōu)化對軟件性能起到?jīng)Q定作用的關鍵程序。手工編寫匯編代碼，可直接控制高級語言編程時不能有效使用的3個優(yōu)化手段：條件執(zhí)行、指令調整和寄存器分配[1]。本文基于ARM9指令架構的特點，應用上述優(yōu)化手段，對決定系統(tǒng)性能的關鍵程序的匯編代碼做二次優(yōu)化。

1　ARM處理器結構

ARM采用RISC(Reduced Instruction Set Computer)指令結構，使用簡單高效的指令，并通過簡單指令組合來完成不常用的復雜功能。因此在ARM上實現(xiàn)特殊功能時，效率可能較低，但可利用流水線技術和超標量技術加以改進和彌補。ARM架構對存儲器操作有限制，使得控制簡單化[2-3]。

2　ARM9架構相關優(yōu)化

ARM處理器指令具備條件執(zhí)行的特征，利于取代比較指令優(yōu)化分支結構和循環(huán)結構。ARM寄存器數(shù)量眾多，結合多寄存器裝載或存儲的LDM和STM指令，易于實現(xiàn)循環(huán)展開優(yōu)化。

近年來，嵌入式微處理器的代碼優(yōu)化得到廣泛研究。Simunic等人[4]將代碼優(yōu)化分成算法優(yōu)化、數(shù)據(jù)優(yōu)化和指令流優(yōu)化3類。kis Kaspersky[5]使用VC++6.0、BorlandC++5.0和WatcomC10.0的3種流行編譯器分析優(yōu)化內(nèi)容，對比代碼質量。Rainer Leupers[6]分析了大量嵌入式微處理器相關的優(yōu)化方法、優(yōu)化算法和優(yōu)化工具。研究了寄存器分配、指令調度、代碼選擇、條件執(zhí)行、函數(shù)內(nèi)聯(lián)等各種優(yōu)化手段的優(yōu)缺點。David A Ortiz和Nayda G等人[7]研究了編譯器優(yōu)化，指令級優(yōu)化和源代碼級優(yōu)化對嵌入式系統(tǒng)的性能影響。劉露、李小進等人[8]通過研究處理器功耗與代碼優(yōu)化的關系，驗證代碼優(yōu)化能影響cache命中率從而改善硬件功耗。王榮勝等[9]研究了基于ARM編譯器的優(yōu)化策略，并通過軟硬件的綜合測試來驗證包括循環(huán)優(yōu)化，指令歸并優(yōu)化，延遲分支等各項優(yōu)化策略的效果。江毛進、陸鑫達等人[10]討論了循環(huán)優(yōu)化的目標和循環(huán)優(yōu)化的各種程序變換方法。本文提出多層嵌套循環(huán)計數(shù)值組合、循環(huán)處理數(shù)據(jù)合并和循環(huán)最優(yōu)展開等優(yōu)化方法。

2.1循環(huán)計數(shù)值組合

多層嵌套循環(huán)需要多個循環(huán)計數(shù)器。對于ARM架構，一個計數(shù)器可滿足循環(huán)計數(shù)低于32位的循環(huán)體。實際應用中，循環(huán)計數(shù)一般<32位，則可將多個循環(huán)計數(shù)值組合放在一個寄存器中，最內(nèi)層的循環(huán)計數(shù)值放在寄存器的最高位，依次類推。組合方式可依據(jù)總的循環(huán)次數(shù)和循環(huán)嵌套層數(shù)來決定。以矩陣乘法程序為例，程序流程圖如圖1所示。

圖1　矩陣乘法程序主流程

以上代碼經(jīng)ARM-Linux-gcc3.4.5編譯后的代碼的主要部分如下

.L6:ldrr3, [fp, #-28] //取i

bhi.L5

.L9: ldrr3, [fp, #-32]//取j

bhi.L8

.L12: ldrr3, [fp, #-36]//取k

bhi.L13

上述程序中3層循環(huán)的3個計數(shù)變量全都存儲在內(nèi)存中，這樣嚴重影響了程序的性能。但若將3個變量全部存儲在寄存器中這樣又增加了寄存器使用數(shù)量。因此，對程序進行循環(huán)計數(shù)值合并到寄存器的優(yōu)化。取1個寄存器r3，最低8位放最外層循環(huán)計數(shù)變量，第2個8位放中間層循環(huán)計數(shù)值，第3個8位放最內(nèi)層循環(huán)計數(shù)值。同時利用條件執(zhí)行來取代比較指令。優(yōu)化后的程序如下

.LPI:add r3, r3, #39<<8；移位使用變量

.LPJ:add r3, r3, #39<<16;循環(huán)計數(shù)值合并

.LPK:ldr r5, [r1], #4

Ldr r6, [r2], #4*40

subsr3, r3, #(1<<16) ; 移位使用變量

mlar4,r5,r6,r4

bpl.LPK

…

subplr1,r1,#4*40;j

bpl.LPJ

bpl.LPI

上述程序首先對r3的16～23位進行減1運算，直到結果為負便完成最內(nèi)層循環(huán)計數(shù)。接著用加 來清除位16-31。然后對r3的位8～15減28來完成中間層循環(huán)計數(shù)。最外層循環(huán)也采用相同的處理方法。由此既節(jié)省了寄存器資源，又發(fā)揮了ARM加減指令處理寬范圍常數(shù)的能力，ARM桶形寄存器的移位處理能力和ARM指令條件執(zhí)行的優(yōu)勢。

理論上，當循環(huán)程序循環(huán)次數(shù)不超過32位，則不論循環(huán)嵌套多少層，均可將循環(huán)的計數(shù)值移位組合到一個寄存器中。單個寄存器組合一般情形：設循環(huán)嵌套層數(shù)為n，循環(huán)由外向內(nèi)每層循環(huán)次數(shù)分別為 (i=1,2,3,…,n)。則有

(1)

設每個Xi(i=1,2,3,…,n)的二進制位數(shù)分別為Bi(i=1,2,3,…,n)。則有

(2)

再結合循環(huán)結束條件控制循環(huán)跳轉與計數(shù)值重裝即可完成循環(huán)控制。

2.2循環(huán)處理數(shù)據(jù)合并

ARM在處理<32位長度的變量(字節(jié)數(shù)據(jù)，雙字節(jié)數(shù)據(jù)等)時，可將多個數(shù)據(jù)存放在單個32位寄存器中，即可減少代碼尺寸，又能改善性能。以圖像合并程序為例，程序流程如圖2所示。

圖2　圖像合并程序主流程圖

以上程序經(jīng)ARM-Linux-gcc3.4.5編譯后的代碼的主要部分如下

ldrr2, [fp, #-16]

ldrr3, [fp, #-32]

ldrbr1, [fp, #-33]

ldrr2, [fp, #-20]

ldrr3, [fp, #-32]

ldrbr3, [r3, #0]

ldrbr3, [fp, #-33]

ldrr2, [fp, #-24]

ldrr3, [fp, #-32]

ldrbr3, [r3, #0]

mulr3, r1, r3

…

上述程序中，處理1 Byte的數(shù)據(jù)全部采用32位寄存器。且每個字節(jié)的處理均有多次內(nèi)存操作。不僅浪費寄存器資源，同時頻繁訪問內(nèi)存影響程序性能。因此可將4 Byte數(shù)據(jù)一次合并到一個寄存器中，通過移位的方式來進行單字節(jié)的處理。經(jīng)二次優(yōu)化后的主要代碼如下

.merge_loop:

ldrr4,[r1],#4；一次取4 Byte

ldrr5,[r2],#4

addr6,r6,r7,LSL#8;移位處理單個字節(jié)

andr8,r14,r6,LSR#8;

andr6,r14,r4,LSR#8;

andr7,r14,r5,LSR#8;

addr6,r6,r7,LSL#8

andr6,r14,r6,LSR#8

bgt.merge_loop

ARM處理器中采用SIMD向量擴展作為計算加速部件，利用128或256位的SIMD寄存器對多個字符型、整型、浮點型數(shù)據(jù)同時進行相同操作，實現(xiàn)一種細粒度的數(shù)據(jù)級并行[11]。將4 Byte存放在一個寄存器中，使一次循環(huán)能處理多個數(shù)據(jù)。充分利用寄存器資源以及ARM桶形寄存器對移位所提供的硬件支持，使程序運行在性能最優(yōu)化狀態(tài)。

2.3循環(huán)最優(yōu)展開

通過多次執(zhí)行循環(huán)內(nèi)部語句來展開循環(huán)，可減小循環(huán)開銷。但當循環(huán)計數(shù)值不是展開次數(shù)的倍數(shù)或循環(huán)計數(shù)值比展開次數(shù)小時，需要對循環(huán)展開做一些特殊處理。實際情況中，循環(huán)展開次數(shù)與剩余循環(huán)的處理，循環(huán)體變量個數(shù)以及處理器能提供寄存器數(shù)量均有關[12]。當上述情況不存在時，循環(huán)展開多少次對性能提升最優(yōu)也需要有一定理論依據(jù)。本文基于ARM指令的周期數(shù)及其所處理的數(shù)據(jù)格式特點為依據(jù)，以最佳次數(shù)展開循環(huán)，使得關鍵程序性能提升最大化。以內(nèi)存設置程序為例，程序流程圖如圖3所示。

圖3　內(nèi)存設置程序主流程圖

該代碼經(jīng)過ARM-Linux-gcc3.4.5編譯后的代碼的主要部分如下

.L16: ldrr3, [fp, #-24]

cmpr3, #0;n>0

beq.L17

…

str r2, [r0, #0]; *p++ =(unsigned char) c;

…

b.L16

.L17:;end

為提高效率，需使用STR或STM指令一次寫入多個字節(jié)。因此，首先需對齊數(shù)組指針s邊界。但只有當循環(huán)次數(shù)n足夠大時，對齊才有意義。因此，設足夠大的循環(huán)次數(shù)為N1，在n≥N1時，對齊數(shù)組指針s邊界。且N1必須≥3，否則數(shù)據(jù)不足4 Byte，也就無所謂字邊界對齊問題。 對齊處理后，一次循環(huán)使用4條批量存儲指令，每條指令寫8個字，這樣每次可操作128 Byte存儲單元。但只有在n≥N2≥128的前提下才值得這樣做，此處N2為上限值。最后，還剩下n≤N2個字節(jié)要設置。但STR指令一次存儲4 Byte，當n<4時，再使用STRB指令單字節(jié)操作剩余的字節(jié)單元。上述過程優(yōu)化后的代碼如下

.ALIGNED:;內(nèi)存對齊

.LOOP128:;循環(huán)展開

STMIA R0!,{R1,R3-R8,R12}

STMIA R0!,{R1,R3-R8,R12}

STMIA R0!,{R1,R3-R8,R12}

STMIA R0!,{R1,R3-R8,R12}

…

LDMFD sp!,{R4-R8}

.MEMSET_4BT: SUBSR2,R2,#4

.LOOP4: STRGER1,[R0],#4

BGE.LOOP4

ADDR2,R2,#4

.MEMSET_1BT: SUBSR2,R2,#1

.LOOP1:STRGEB R1,[R0],#1

SUBGES R2,R2,#1

BGE.LOOP1

上述算法中以128Byte，4Byte和1Byte的形式進行，則按塊分解循環(huán)次數(shù)n可表示為n=128n128+4n4+n1,0≤n4<32,0≤n1<4。則有以下3種情形，如表1所示。

(1) 0≤n

(2)N1≤n

(3)N2≤n時，與(2)中類似，總周期數(shù)為5(n4+z4+n1+z1)+32，列表如表1所示。

表1　n值與周期數(shù)的關系表

比較上表可知：當n4≥1時，第2行值小于第一行，除非n4=1或n4=0。設置N1為5，從第1行和第2行來選擇最佳的周期。只要當n128≥1時，第2行的值就小于第2行的值。因此取N2為128。綜上所述，在循環(huán)展開的過程中，可根據(jù)處理器指令周期特點以及程序處理數(shù)據(jù)的特征，列出與展開相關的指令周期多項式。根據(jù)多項式系數(shù)特征確定最優(yōu)展開次數(shù)。

3　實驗

3.1實驗環(huán)境

本文通過硬件實驗驗證優(yōu)化方法的有效性。實驗環(huán)境如下：硬件平臺：精致2440開發(fā)板；處理器： S3C2440；內(nèi)核：ARM920T；操作系統(tǒng)內(nèi)核版本：Linux 2.6.22.6；編譯工具：ARM-Linux-gcc-3.4.5。

3.2實驗過程

取3組經(jīng)典程序，矩陣乘法程序，圖像合并程序和內(nèi)存設置程序。將其編譯成兩種匯編程序，即原始程序和編譯器最優(yōu)程序。將原始程序進行二次優(yōu)化得到二次優(yōu)化程序。將其分別運行在目標平臺上。統(tǒng)計1 000次實驗數(shù)據(jù)，利用Matlab7.0獲得性能直方圖，通過對比分析驗證優(yōu)化手段的有效性。

3.3實驗結果分析

3個程序運行平均時間如圖4所示，寄存器使用數(shù)量、代碼行數(shù)以及性能對比如表2～表4所示。

圖4　程序運行平均時間圖

程序原始程序編譯器最優(yōu)程序二次優(yōu)化程序寄存器數(shù)497代碼行數(shù)853330性能提升0120%490%

表3　圖像合并程序性能指標統(tǒng)計表

表4　內(nèi)存設置程序性能指標統(tǒng)計表

上述實驗數(shù)據(jù)表明，3個經(jīng)典程序經(jīng)二次優(yōu)化后，性能均優(yōu)于原始程序和編譯器最優(yōu)程序。矩陣乘法程序和圖像合并程序的代碼也得到了精簡，利于節(jié)省內(nèi)存空間；寄存器使用方面，矩陣乘法程序利用循環(huán)計數(shù)值合并優(yōu)化，利于節(jié)省寄存器資源；而圖像合并程序和內(nèi)存設置程序以犧牲寄存器資源換取程序性能的大幅提升。

4　結束語

本文提到的3種優(yōu)化方法中，循環(huán)計數(shù)值的組合應用靈活，各種架構均可參考應用。但對于循環(huán)計數(shù)值超過32位時，如何應用多個寄存器進行組合并改善性能還有待研究。而循環(huán)的最優(yōu)展開次數(shù)需根據(jù)處理器架構和程序的特點來確定，且需要列出指令周期多項式,過程較為繁瑣，實際應用中可根據(jù)性能要求取舍。循環(huán)處理數(shù)據(jù)合并適用于圖像和字符處理，內(nèi)存對齊雖增加一定開銷，但數(shù)據(jù)量較大時實用性較強。

[1]Andrew N Sloss,Dominic Symes,Chris Wright.ARM system developer’s guide designing and optimizing system software[M].沈建華，譯.北京:北京航空航天大學出版社,2005.

[2]三恒星科技.ARM9原理與應用設計[M].北京:電子工業(yè)出版社,2008.

[3]Advanced RISC Machines Co.,Ltd. ARM920T system-on-chip platform OS processor[M].UK:Advanced RISC Machines Co.,Ltd,2001.

[4]Simunic T,Benini L,G de Micheli. Energy-efficient design of battery-powered embedded systems[J].IEEE Transactions on Very Large Scale Integration Systems,2001，9(1)：15-28.

[5]Kris Kaspersky.Code optimization effective memory usage[M].譚金明,譯.北京:電子工業(yè)出版社,2004.

[6]Leupers R.Code optimization techniques for embedded processors[M].America:Kluwer Academic Publishers,2000.

[7]David A Ortiz,Nayda G.Santiago impact of source code optimizations on power consumption of embedded systems[C].Mantreal: Joint 6th International IEEE Northeast Workshop on Circuits and Systems and TAISA Conference,2008.

[8]劉露,李小進,張宏,等.基于訪存特性的嵌入式移動設備軟件低功耗優(yōu)化方法[J].計算機應用研究,2014,31(11):3392-3396.

[9]王榮勝.基于ARM的編譯器選優(yōu)技術研究與實現(xiàn)[D].長沙:國防科學技術大學,2007.

[10]江毛進,陸鑫達,陳杰.編譯中的循環(huán)優(yōu)化[J].上海交通大學學報,1996,30(6):20-27.

[11]侯永生,趙榮彩,黃磊,等.面向SIMD擴展部件的循環(huán)優(yōu)化研究[J].計算機科學,2014,41(5):27-32.

[12]周海亮,高軍,張民選.一種基于流處理器的多重循環(huán)優(yōu)化技術[C].北京:全國高性能計算學術會議,2006.

Compiler Optimizations Based on ARM9 Architecture

GE Wuchao, ZHOU Yimin

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

Software developing in Embedded systems lacks the process of peephole optimization when using the GCC compiler, thus a poorer performance of the compiled code than that by the ARM compiler. This paper proposes a combination of cycle counter, consolidating data of cyclic process and cycle expansion optimally to optimize assembly code on the ARM9 processor, which are verified by running matrix multiplication, image merging and memory settings programs, respectively, on the ARM9 platform. Experimental data show that above mentioned methods reduce the number of register counts by 50% on average while nearly doubling the performance compared with the GCC compiled code.

peephole optimization; combination of cycle counter; consolidating data of cyclic process; cycle expansion optimally

2015- 12- 10

葛吳超(1989-)，男，碩士研究生。研究方向：嵌入式系統(tǒng)。周亦敏(1962-)，男，副教授。研究方向：嵌入式系統(tǒng)。

10.16180/j.cnki.issn1007-7820.2016.09.029

TP316.2

A

1007-7820(2016)09-106-05