基于熱點(diǎn)函數(shù)的代碼體積優(yōu)化

黃昕

摘 要：為解決嵌入式系統(tǒng)存儲(chǔ)受限的問題，編譯器往往禁止一些會(huì)增大代碼體積的優(yōu)化，如循環(huán)展開、過程內(nèi)聯(lián)等，導(dǎo)致性能下降。大部分程序中存在占據(jù)程序90%以上執(zhí)行時(shí)間的“熱”代碼，但其體積僅占程序代碼小部分。利用該程序?qū)傩裕岢龌跓狳c(diǎn)代碼的可執(zhí)行代碼體積優(yōu)化方法，即通過程序執(zhí)行剖視信息獲取“熱”、“冷”代碼并采用不同優(yōu)化方法。測(cè)試表明，與針對(duì)性能的優(yōu)化相比，該方法典型測(cè)試程序代碼體積平均下降15.2%，性能僅下降3.4%。

關(guān)鍵詞：體積優(yōu)化;編譯;熱點(diǎn)函數(shù);嵌入式應(yīng)用

DOI：10. 11907/rjdk. 182595

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）006-0042-04

Abstract： Due to limit memory capacity of embedded systems， compilers often prohibit some of the optimization that will increase the size of the code， such as loop unroll， procedure inline， etc. This may cause the loss of performance too much. It is observed that in most of programs， the "hot" code consuming 90% or above time of program execution consists of a small part of the whole program. Based on this observation， the paper proposes an executable code optimization methods based on hot code. ?This idea is to use the program execution profile to discover "hot" and "code" codes of a program， and then employ different strategies to optimize these "hot" and "code" codes. The experiment shows that， compared to the existing performance optimization methods， the result by the proposed method can save 15.2% volume of the code with only 3.4% loss of performance on average.

Key Words： code size optimization; compile; hot function; embedded application

0 引言

存儲(chǔ)受限是嵌入式領(lǐng)域面臨的難題，隨著嵌入式系統(tǒng)的發(fā)展，越來越復(fù)雜的軟件運(yùn)行在嵌入式系統(tǒng)中，使矛盾日益突出。第一，嵌入式系統(tǒng)本身資源有限，但軟件越來越龐大復(fù)雜，要求更大的存儲(chǔ)空間;第二，代碼復(fù)雜龐大，使代碼執(zhí)行開銷日益增加，但用戶對(duì)性能的要求也日益提高。因此需要嵌入式軟件既不能占用過多的內(nèi)存，又要保證提供高效的程序性能。

在嵌入式領(lǐng)域，針對(duì)代碼體積優(yōu)化一般有3種方法[1-2]：

（1）處理器設(shè)計(jì)上，使用高密度的指令集。例如，Thumb指令集是ARM指令集的子集[3-4]，支持壓縮至16位寬的操作碼，代碼密度更高。ARM程序與Thumb程序可以相互調(diào)用，且狀態(tài)切換的開銷基本為0。用戶可以根據(jù)實(shí)際環(huán)境切換指令模式生成16位或32位指令，或增加一些復(fù)雜指令，實(shí)現(xiàn)原來需要兩條指令才能完成的功能。

（2）代碼壓縮技術(shù)[5]針對(duì)指令編碼進(jìn)行一系列變化，對(duì)可執(zhí)行代碼進(jìn)行壓縮，刪除原文件中冗余的信息，減少代碼大小。

（3）編譯優(yōu)化[6-9]。編譯器在將源程序轉(zhuǎn)換為可執(zhí)行程序過程中，以優(yōu)化代碼體積為目標(biāo)，執(zhí)行各種轉(zhuǎn)換，例如冗余代碼刪除、循環(huán)合并等。

與前兩種方法相比，編譯優(yōu)化技術(shù)由于不需要對(duì)硬件進(jìn)行修改，且操作靈活，已在商用與開源編譯器中得到了廣泛應(yīng)用。例如Intel商用編譯器與開源編譯器GCC、LLVM均提供“Os”選項(xiàng)[6-9]，指明進(jìn)行針對(duì)代碼體積的優(yōu)化，生成的代碼體積小于缺省的“O2”優(yōu)化及針對(duì)性能的“O3”優(yōu)化。但現(xiàn)有編譯優(yōu)化技術(shù)在縮小代碼體積的同時(shí)，由于對(duì)一些會(huì)增大代碼體積的優(yōu)化進(jìn)行限制，較大程度地影響了性能。

本文首先對(duì)在嵌入式領(lǐng)域中應(yīng)用廣泛的GCC編譯器現(xiàn)有代碼體積優(yōu)化進(jìn)行分析、評(píng)測(cè)，在此基礎(chǔ)上提出基于熱代碼的代碼體積優(yōu)化技術(shù)，通過性能分析工具中找出程序中的“冷”、“熱”代碼，進(jìn)行分別優(yōu)化，從而在代碼體積優(yōu)化的同時(shí)盡可能減少對(duì)性能的影響，利用Python語言[10]實(shí)現(xiàn)自動(dòng)工具。測(cè)試結(jié)果證明了該技術(shù)的有效性。

1 面向代碼體積的編譯優(yōu)化

1.1 代碼體積優(yōu)化技術(shù)

無論是Intel商用編譯器，還是開源編譯器GCC、LLVM[6-9]，編譯器針對(duì)代碼體積的優(yōu)化一般包括兩類：

（1）采用刪除冗余代碼、向量化等方法減少代碼體積。冗余代碼刪除指通過刪除程序不必要的計(jì)算，減少可執(zhí)行代碼體積[11]。常用冗余代碼刪除優(yōu)化方法包括：死代碼刪除、公共表達(dá)式刪除、循環(huán)不變量外提、常數(shù)傳播、復(fù)制傳播、代碼提升、值編號(hào)、部分冗余刪除等[12-13]。例如在GCC中， GIMPLE語法樹和RTL[14]中間語言均執(zhí)行了多種冗余刪除優(yōu)化。向量執(zhí)行是目前處理器提高性能的主要途徑之一[15]。編譯向量化指利用處理器提供的向量功能部件，包括向量寄存器、向量執(zhí)行部件，生成可以并發(fā)執(zhí)行的向量指令。一條向量指令同時(shí)可以處理多個(gè)數(shù)據(jù)。因此，向量化能夠減少可執(zhí)行代碼體積。循環(huán)合并[16]把多個(gè)相鄰且具有相同迭代空間的循環(huán)合并成一個(gè)循環(huán)，一方面增加單個(gè)循環(huán)體積，為指令調(diào)度、冗余刪除等優(yōu)化提供更多的機(jī)會(huì);另一方面，合并循環(huán)也刪除了重復(fù)的循環(huán)判斷、控制變量修改等操作。

以上優(yōu)化方法通常在減少可執(zhí)行代碼體積的同時(shí)也提升了程序性能。

（2）禁止增大代碼體積的編譯優(yōu)化。為減少生成的可執(zhí)行代碼大小，編譯器會(huì)禁止一些增大代碼體積的優(yōu)化。例如，在GCC編譯器[7-8]中，禁止循環(huán)展開、基本塊重排與分布、循環(huán)分布、插入預(yù)取指令等優(yōu)化。具體指除了禁止循環(huán)展開、過程內(nèi)聯(lián)、循環(huán)分布等，Os選項(xiàng)會(huì)關(guān)閉以下優(yōu)化選項(xiàng)：①align-functions ：函數(shù)對(duì)齊。align-functions=N 將所有函數(shù)起始地址在N（N=1，2，4，8，16…）的邊界上對(duì)齊，默認(rèn)為機(jī)器自身默認(rèn)值，指定為1表示禁止對(duì)齊;②align-jumps：跳轉(zhuǎn)對(duì)齊。align-jumps=N 將分支目標(biāo)在N（N=1，2，4，8，16…）的邊界上對(duì)齊，默認(rèn)為機(jī)器自身默認(rèn)值，指定為1表示禁止對(duì)齊;③align-loops ：循環(huán)對(duì)齊，確保不會(huì)在分支目標(biāo)前插入多余的空指令;④falign-labels ：標(biāo)號(hào)對(duì)齊，確保不與falign-jumps產(chǎn)生沖突。對(duì)齊優(yōu)化通常用于提高Cache利用率，為保證對(duì)齊，編譯器會(huì)進(jìn)行空指令插入、數(shù)據(jù)墊塞等，從而增大可執(zhí)行代碼體積;⑤reorder-blocks/ reorder-blocks-and-partition：基本塊重排和基本塊重排與劃分。通過基本塊重排可提升指令Cache的利用率，但是可能會(huì)插入較長(zhǎng)的跳轉(zhuǎn)指令;⑥prefetch- loop-arrays：插入數(shù)據(jù)預(yù)取取指令，以隱藏訪存延遲。

1.2 GCC針對(duì)代碼體積的優(yōu)化評(píng)測(cè)

對(duì)GCC針對(duì)可執(zhí)行代碼體積的優(yōu)化能力進(jìn)行測(cè)試，測(cè)試分為兩個(gè)方面：一是使用了Os后代碼體積的減少;二是使用Os對(duì)代碼性能的影響。測(cè)試在lenoveEdge531機(jī)器上進(jìn)行，測(cè)試環(huán)境為L(zhǎng)inux 內(nèi)核3.14、gcc 7.2.0編譯器，測(cè)試程序選用通用的NPB 3.3-SER[17]基準(zhǔn)測(cè)試集。

首先對(duì)比測(cè)試可執(zhí)行代碼的體積，結(jié)果如圖1所示。

顯然，與O3相比，針對(duì)代碼體積的Os優(yōu)化取得了良好效果，可執(zhí)行代碼體積平均下降了30.5%，尤其是BT、LU和SP，體積下降超過40%。程序EP由于自身代碼量小，去掉注釋僅約230行，因此效果不明顯。代碼體積減少主要得益于Os禁止了會(huì)顯著增大代碼體積的優(yōu)化，但是對(duì)性能會(huì)產(chǎn)生較大的負(fù)面影響，使用Os與O3時(shí)性能對(duì)比如圖2所示。

與O3相比，采用Os選項(xiàng)，NPB平均執(zhí)行時(shí)間增加了18.3%，尤其是LU與MG程序，執(zhí)行時(shí)間分別上升了59%與43%。

因此目前通過編譯器進(jìn)行針對(duì)代碼體積的優(yōu)化，最大問題在于對(duì)性能的影響，即減小了代碼體積的同時(shí)，性能也明顯下降。

2 基于熱點(diǎn)函數(shù)的代碼體積優(yōu)化

2.1 熱點(diǎn)函數(shù)

幾乎所有軟件皆存在“熱點(diǎn)”。熱點(diǎn)是指占據(jù)程序絕大多數(shù)運(yùn)行時(shí)間的代碼。該部分代碼往往僅占程序一小部分。例如，為保證程序正確性、魯棒性，程序中許多代碼用于邊界及錯(cuò)誤處理，在程序正常運(yùn)行時(shí)通常不被調(diào)用或者極少被調(diào)用，但代碼量巨大。通過性能分析工具[18-19]，可快速獲得程序熱點(diǎn)函數(shù)。以NPB為例，程序熱點(diǎn)函數(shù)及熱點(diǎn)函數(shù)占據(jù)的代碼比例如表1所示，多數(shù)程序占據(jù)程序執(zhí)行時(shí)間90%以上的熱點(diǎn)函數(shù)，代碼量?jī)H為總代碼量的30%。

2.2 可執(zhí)行代碼體積優(yōu)化

利用程序“熱點(diǎn)”函數(shù)屬性，可通過對(duì)“熱”、“冷”代碼區(qū)別對(duì)待，在降低對(duì)程序性能影響前提下，盡可能優(yōu)化可執(zhí)行代碼體積，即針對(duì)占據(jù)程序大部分執(zhí)行時(shí)間的“熱點(diǎn)”函數(shù)，進(jìn)行代碼性能優(yōu)化;針對(duì)占據(jù)程序大部分代碼體積的“冷”代碼，進(jìn)行代碼體積優(yōu)化。算法流程如圖3所示。

優(yōu)化主要分為3步：①獲取熱點(diǎn)函數(shù);②設(shè)置熱點(diǎn)函數(shù)標(biāo)記位，在編譯該函數(shù)時(shí)，采用性能優(yōu)先的優(yōu)化方法;③使用帶按摩大小有限的編譯選項(xiàng)Os，生成編譯命令。利用代碼運(yùn)行時(shí)獲取的性能信息（運(yùn)行剖視profile文件）[18-19]，可較為精確地獲取程序熱點(diǎn)代碼。在沒有運(yùn)行剖視文件的情況下，利用編譯基于啟發(fā)信息的靜態(tài)分析，也可大致獲取熱點(diǎn)函數(shù)。編譯器編譯時(shí)通常以函數(shù)為單位，設(shè)置熱點(diǎn)函數(shù)標(biāo)記位，編譯到該函數(shù)時(shí)，修改選項(xiàng)為性能優(yōu)先。其它函數(shù)均使用代碼大小優(yōu)先的選項(xiàng)進(jìn)行編譯，保證頻繁執(zhí)行的熱點(diǎn)函數(shù)執(zhí)行時(shí)間不發(fā)生大幅下降。其它程序部分進(jìn)行針對(duì)代碼大小的優(yōu)化，減少可執(zhí)行代碼體積。

3 測(cè)試

測(cè)試在lenoveEdge531機(jī)器上進(jìn)行。對(duì)于熱點(diǎn)函數(shù)采用O3優(yōu)化，其它函數(shù)采用Os優(yōu)化。優(yōu)化后的結(jié)果對(duì)比如表2-表8所示。

從測(cè)試結(jié)果可以看出，基于熱點(diǎn)函數(shù)的可執(zhí)行代碼體積優(yōu)化取得了較理想結(jié)果：①和O3相比，性能最多僅下降15.5%（LU），平均下降3.4%，但是代碼積平均下降15.2%;②和Os相比，代碼體積平均僅增加8.3%，但是性能提高了7.5%。

4 結(jié)語

存儲(chǔ)受限是嵌入領(lǐng)域面臨的主要問題之一。目前針對(duì)代碼體積的編譯優(yōu)化對(duì)性能有較大影響，本文提出基于熱點(diǎn)代碼的可執(zhí)行代碼體積優(yōu)化，在盡可能不影響性能的前提下，減少程序可執(zhí)行代碼體積。利用NPB測(cè)試程序驗(yàn)證了方法及工具的效果，下一步研究將使用典型嵌入式程序，例如Arduino智能小車[20]，對(duì)方法進(jìn)行驗(yàn)證;同時(shí)將自動(dòng)工具與程序Makefile等結(jié)合，進(jìn)一步實(shí)現(xiàn)優(yōu)化過程的完全自動(dòng)化。

參考文獻(xiàn)：

[1] BESAEDES A，F(xiàn)ERENC R，GYIMóTHY T，et al. Survey of code-size reduction methods[J]. ACM Computing Surveys，2003，35（3）：223-267.

[2] 廉玉龍.面向嵌入式處理器的編譯優(yōu)化技術(shù)研究[D]. ?杭州：浙江大學(xué)， 2016.

[3] ARM Ltd. Thumb？ 16-bit Instruction Set[R/OL] ?http：//infocenter.arm.com/help/topic/com.arm.doc.qrc0001l/QRC0001_UAL.pdf.Accessed：2018-10-02.

[4] ARM Ltd. ARMv7-M Architecture Reference Manual[R/OL]. https：//static.docs.arm.com/ddi0403/e/DDI0403E_B_armv7m_arm.pdf.

[5] SUTTER B and BOSSCHERE K. Software techniques for program compaction[J]. ?Communications of the ACM， 2003， 46（8）：33-34.

[6] INTEL Corp. Intel？ Parallel Studio XE 2018[R/OL]. https：//software.intel.com/en-us/parallel-studio-xe， 2018.

[7] BESZéDES A，GERGELY T，GYIMOTHY T，et al. Optimizing for space ： measurements and possibilities for improvement[C]. ?Proceedings of the 2003 GCC Developers' Summit， 2003：7-20.

[8] ANORMITY. Using the GNU compiler collection（GCC）[EB/OL]. ?http：//gcc.gnu.org/onlinedocs/gcc-8.2.0/gcc.

[9] ANORMITY. LLVM user guides[EB/OL]. http：// https：//llvm.org/docs/GettingStarted.html.2018.

[10] BEAZLEY D & JONES B K. Python cookbook. [M]. ?3rd Edition. Sebastopol ：ORelly Media. Inc，2013.

[11] STEVEN M. Advanced compiler design and implementation[M]. ?San Francisco：？ Morgan Kaufmann， 1997.

[12] BRIGGS P， COOPER K D， SIMPSON L T. Value numbering[J]. ?Software-Practice and Experience， 1997，17（6）：701-724.

[13] XUE J ，CAI Q. A life optimal algorithm for speculative PRE[J]. ?ACM Transactions on Architecture and Code Optimizaion， 2006， 3（3）： 115-155.

[14] ANORMITY. GNU compiler collection （GCC） internals. [EB/OL]， https：//gcc.gnu.org/onlinedocs/gccint/index.html. 2018

[15] 高偉，趙榮彩，韓林，等. ?SIMD自動(dòng)向量化編譯優(yōu)化概述[J]. ?軟件學(xué)報(bào)，2015，25（6）：1265-1284.

[16] KENNEDY K， RANDY A. Optimizing compilers for modern architectures： a dependence-based approach[M]. San Francisco：Morgan Kaufmann. 2001.

[17] NASA. NPS ?parallel benchmarks[R/OL]. http：//nas.nasa.gov/Software/NPB.

[18] GNU Gprof. [EB/OL]. http：//sourceware.org/binutils/docs/gprof/index.html. 2018.

[19] INTEL Corp. Intel Vtune Amplifier[R/OL]. ?https：//software.intel.com/en-us/intel-vtune-amplifier-xe/.

[20] ANOMITY. Adruino smart car[EB/OL]. ?https：//create.arduino.cc.

（責(zé)任編輯：江 艷）