葛吳超，周亦敏

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

?

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

葛吳超，周亦敏

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

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

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

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

1　ARM處理器結(jié)構(gòu)

ARM采用RISC(Reduced Instruction Set Computer)指令結(jié)構(gòu)，使用簡(jiǎn)單高效的指令，并通過(guò)簡(jiǎn)單指令組合來(lái)完成不常用的復(fù)雜功能。因此在ARM上實(shí)現(xiàn)特殊功能時(shí)，效率可能較低，但可利用流水線技術(shù)和超標(biāo)量技術(shù)加以改進(jìn)和彌補(bǔ)。ARM架構(gòu)對(duì)存儲(chǔ)器操作有限制，使得控制簡(jiǎn)單化[2-3]。

2　ARM9架構(gòu)相關(guān)優(yōu)化

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

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

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

多層嵌套循環(huán)需要多個(gè)循環(huán)計(jì)數(shù)器。對(duì)于ARM架構(gòu)，一個(gè)計(jì)數(shù)器可滿足循環(huán)計(jì)數(shù)低于32位的循環(huán)體。實(shí)際應(yīng)用中，循環(huán)計(jì)數(shù)一般<32位，則可將多個(gè)循環(huán)計(jì)數(shù)值組合放在一個(gè)寄存器中，最內(nèi)層的循環(huán)計(jì)數(shù)值放在寄存器的最高位，依次類(lèi)推。組合方式可依據(jù)總的循環(huán)次數(shù)和循環(huán)嵌套層數(shù)來(lái)決定。以矩陣乘法程序?yàn)槔?，程序流程圖如圖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個(gè)計(jì)數(shù)變量全都存儲(chǔ)在內(nèi)存中，這樣嚴(yán)重影響了程序的性能。但若將3個(gè)變量全部存儲(chǔ)在寄存器中這樣又增加了寄存器使用數(shù)量。因此，對(duì)程序進(jìn)行循環(huán)計(jì)數(shù)值合并到寄存器的優(yōu)化。取1個(gè)寄存器r3，最低8位放最外層循環(huán)計(jì)數(shù)變量，第2個(gè)8位放中間層循環(huán)計(jì)數(shù)值，第3個(gè)8位放最內(nèi)層循環(huán)計(jì)數(shù)值。同時(shí)利用條件執(zhí)行來(lái)取代比較指令。優(yōu)化后的程序如下

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

.LPJ:add r3, r3, #39<<16;循環(huán)計(jì)數(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

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

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

(1)

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

(2)

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

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

ARM在處理<32位長(zhǎng)度的變量(字節(jié)數(shù)據(jù)，雙字節(jié)數(shù)據(jù)等)時(shí)，可將多個(gè)數(shù)據(jù)存放在單個(gè)32位寄存器中，即可減少代碼尺寸，又能改善性能。以圖像合并程序?yàn)槔?，程序流程如圖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位寄存器。且每個(gè)字節(jié)的處理均有多次內(nèi)存操作。不僅浪費(fèi)寄存器資源，同時(shí)頻繁訪問(wèn)內(nèi)存影響程序性能。因此可將4 Byte數(shù)據(jù)一次合并到一個(gè)寄存器中，通過(guò)移位的方式來(lái)進(jìn)行單字節(jié)的處理。經(jīng)二次優(yōu)化后的主要代碼如下

.merge_loop:

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

ldrr5,[r2],#4

addr6,r6,r7,LSL#8;移位處理單個(gè)字節(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向量擴(kuò)展作為計(jì)算加速部件，利用128或256位的SIMD寄存器對(duì)多個(gè)字符型、整型、浮點(diǎn)型數(shù)據(jù)同時(shí)進(jìn)行相同操作，實(shí)現(xiàn)一種細(xì)粒度的數(shù)據(jù)級(jí)并行[11]。將4 Byte存放在一個(gè)寄存器中，使一次循環(huán)能處理多個(gè)數(shù)據(jù)。充分利用寄存器資源以及ARM桶形寄存器對(duì)移位所提供的硬件支持，使程序運(yùn)行在性能最優(yōu)化狀態(tài)。

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

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

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

該代碼經(jīng)過(guò)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指令一次寫(xiě)入多個(gè)字節(jié)。因此，首先需對(duì)齊數(shù)組指針s邊界。但只有當(dāng)循環(huán)次數(shù)n足夠大時(shí)，對(duì)齊才有意義。因此，設(shè)足夠大的循環(huán)次數(shù)為N1，在n≥N1時(shí)，對(duì)齊數(shù)組指針s邊界。且N1必須≥3，否則數(shù)據(jù)不足4 Byte，也就無(wú)所謂字邊界對(duì)齊問(wèn)題。 對(duì)齊處理后，一次循環(huán)使用4條批量存儲(chǔ)指令，每條指令寫(xiě)8個(gè)字，這樣每次可操作128 Byte存儲(chǔ)單元。但只有在n≥N2≥128的前提下才值得這樣做，此處N2為上限值。最后，還剩下n≤N2個(gè)字節(jié)要設(shè)置。但STR指令一次存儲(chǔ)4 Byte，當(dāng)n<4時(shí)，再使用STRB指令單字節(jié)操作剩余的字節(jié)單元。上述過(guò)程優(yōu)化后的代碼如下

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

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

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的形式進(jìn)行，則按塊分解循環(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時(shí)，與(2)中類(lèi)似，總周期數(shù)為5(n4+z4+n1+z1)+32，列表如表1所示。

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

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

3　實(shí)驗(yàn)

3.1實(shí)驗(yàn)環(huán)境

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

3.2實(shí)驗(yàn)過(guò)程

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

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

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

圖4　程序運(yùn)行平均時(shí)間圖

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

表3　圖像合并程序性能指標(biāo)統(tǒng)計(jì)表

表4　內(nèi)存設(shè)置程序性能指標(biāo)統(tǒng)計(jì)表

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

4　結(jié)束語(yǔ)

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

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

[2]三恒星科技.ARM9原理與應(yīng)用設(shè)計(jì)[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]劉露,李小進(jìn),張宏,等.基于訪存特性的嵌入式移動(dòng)設(shè)備軟件低功耗優(yōu)化方法[J].計(jì)算機(jī)應(yīng)用研究,2014,31(11):3392-3396.

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

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

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

[12]周海亮,高軍,張民選.一種基于流處理器的多重循環(huán)優(yōu)化技術(shù)[C].北京:全國(guó)高性能計(jì)算學(xué)術(shù)會(huì)議,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