胡 敏,盧永江,劉 兵

(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)

基于CK810處理器的匯編鏈接時優(yōu)化

胡 敏,盧永江,劉 兵

(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)

提出基于CK810處理器的16/32位混編指令集匯編鏈接時優(yōu)化技術(shù)。利用匯編輸出二進(jìn)制文件,根據(jù)CK810處理器的16/32位混編指令集中指令及操作數(shù)的特征,動態(tài)選擇指令的編碼方式,實現(xiàn)對指令relax,最大程度地提高了程序的代碼密度。對于在匯編時不能確定編碼方式的指令,通過留出重定位的方式,由鏈接時完成優(yōu)化。在鏈接時,利用信息的確定性,實現(xiàn)對整個程序的壓縮和指令的替換,使得程序執(zhí)行效率更高,代碼占用空間更小。匯編鏈接時優(yōu)化技術(shù)克服了傳統(tǒng)編譯器只限于一個模塊優(yōu)化的缺點,把優(yōu)化范圍擴(kuò)展到整個程序,實現(xiàn)了跨模塊的優(yōu)化,使得基于CK810處理器的程序代碼密度平均提高7.52%,性能平均提升7.91%。

匯編優(yōu)化;鏈接優(yōu)化;動態(tài)編碼;重定位;壓縮;替換

1 概述

在計算機(jī)系統(tǒng)中,現(xiàn)今16/32位混編指令集架構(gòu)已經(jīng)成為主流。通常在 16/32位混合編碼集中［1-2］,32位指令用于提升指令集的運算性能,采用3操作數(shù)尋址模式,可以訪問所有寄存器資源,具有尋址范圍大的特點;16位指令是32位指令中出現(xiàn)頻率最高的指令子集,用于提升指令代碼密度,16位指令多采用兩操作數(shù)尋址模式,只能訪問部分寄存器資源,立即數(shù)尋址范圍較小。為獲得代碼密度和性能提升的有機(jī)結(jié)合,對16/32位混編指令集的優(yōu)化必不可少。目前,大部分對代碼的優(yōu)化主要集中在編譯階段［3-4］,雖然文獻(xiàn)［5-6］有對程序在鏈接時做過優(yōu)化,但也是在對可執(zhí)行程序重新反匯編和鏈接來達(dá)到優(yōu)化,屬于鏈接后的優(yōu)化,不是本文所論述的匯編鏈接時優(yōu)化,所以當(dāng)前在匯編與鏈接時對代碼優(yōu)化幾乎為空白。傳統(tǒng)編譯器是指通過詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成的編譯翻譯過程。這個過程通常的優(yōu)化是對單個函數(shù)而言,并且是生成一個個獨立不相關(guān)的匯編文件［7］,即不能對整個程序進(jìn)行優(yōu)化,故傳統(tǒng)編譯器對16/32位混編指令集的編譯優(yōu)化存在3個不足:

(1)從文獻(xiàn)［8］可知,傳統(tǒng)編譯器對程序的分析和優(yōu)化一般都是限于單個函數(shù)和過程,損失了過程間的優(yōu)化機(jī)會;

(2)從文獻(xiàn)［9］可概括出,傳統(tǒng)編譯器無法獲得整個程序的所有信息,在編譯時無法獲得指令和數(shù)據(jù)的地址信息;

(3)傳統(tǒng)編譯器不能決定指令是以16位編碼還是以32位編碼,而指令以何種形式編碼是程序代碼密度和性能優(yōu)劣的關(guān)鍵因素,若指令本可以以16位形式編碼卻被編碼成了32位的指令,無疑是浪費了代碼空間;反之,若本該編碼成32位的指令,卻被編碼成多條16位指令,性能則會受到影響。

針對傳統(tǒng)編譯器在16/32位混編指令集編譯時存在的局限性,本文提出匯編鏈接時的指令編碼優(yōu)化方法。匯編時,運用relax優(yōu)化機(jī)制,實現(xiàn)對指令動態(tài)選擇的編碼方式,以達(dá)到代碼密度和性能的最優(yōu)化;鏈接時,根據(jù)地址信息的確定性,提出鏈接時指令替換、空間壓縮、地址索引優(yōu)化和靜態(tài)地址優(yōu)化等優(yōu)化策略。

2 16/32位指令混合編碼的優(yōu)化

2.1 匯編時relax優(yōu)化

在針對16/32位混編指令集的匯編階段,當(dāng)指令在操作數(shù)確定的情況下,根據(jù)操作數(shù)個數(shù)和操作數(shù)是否超出16位指令編碼范圍來選擇采用16位或32位指令。

如編碼無符號加法指令addurz,rx(CK810指令,下同),當(dāng)z和x的值落入16位指令的操作數(shù)范圍時,采用16位指令編碼,否則以32位指令編碼。當(dāng)指令的操作數(shù)不確定時,指令只能無條件編碼成為32位的指令,這就可能導(dǎo)致代碼密度的損失。為最大可能性對指令選擇合適的編碼方式,本文提出一種relax優(yōu)化機(jī)制。relax機(jī)制是指,在編碼階段,把指令存放在一個個稱為frag的緩沖區(qū),在匯編某條指令時,當(dāng)指令操作數(shù)不能確定時,把指令暫且編碼成16位的指令,把這條指令作為當(dāng)前frag的最后一條指令并預(yù)留出32指令的空間,之后開辟新的frag來存放接下來的指令,當(dāng)再次遇到操作數(shù)不能確定的情況,重復(fù)上述過程。圖1是CK810的匯編代碼片段的匯編示意圖。

在圖1中,根據(jù)relax機(jī)制,在匯編bsr指令時,操作數(shù)label不能確定,把bsr指令編碼成16位指令,結(jié)束當(dāng)前frag1。在最后匯編輸出的階段,bsr指令與lable的距離為0x1f,滿足16位指令的操作數(shù)范圍,bsr編碼成16位指令。

在引入relax機(jī)制時,在匯編輸出階段,若操作數(shù)的范圍仍不能確定,則把指令編碼為32位的指令,并留出重定位信息給連接器,在鏈接器中對指令再做優(yōu)化。

圖1 匯編代碼的過程示意圖

圖2是在IA64linux主機(jī)平臺上,匯編目標(biāo)處理器為CK810的測試結(jié)果(以下各個優(yōu)化的環(huán)境相同)。測試實驗采用標(biāo)準(zhǔn)的benchmark CSiBE,對其在沒有引入relax和引入relax優(yōu)化的一個代碼密度進(jìn)行對比。從圖2可以看出,所有程序的代碼密度都有提到,代碼密度最低提高了 3%,最高提升6.38%,平均提升4.5%。

圖2 relax優(yōu)化代碼密度對比

2.2 鏈接時壓縮替換優(yōu)化

利用鏈接時代碼信息都確定的優(yōu)勢［10-11］,可以對指令進(jìn)一步壓縮與替換。本文針對嵌入式CPU指令集的特征,引入下面3種壓縮優(yōu)化策略:

(1)把32位指令壓縮成16位指令;

(2)把帶常量池的指令替換成不需要常量池的指令;

(3)由上面2個壓縮,引起新的壓縮,即曾經(jīng)PC偏移量超出指令編碼的,由于遞歸壓縮PC偏移量變小而可以在指令編碼中編碼。如絕對地址函數(shù)調(diào)用jsri指令,隨著程序的不斷遞歸壓縮,使得可以用相對地址偏移函數(shù)調(diào)用bsr指令來替代,從而刪除常量池,進(jìn)一步提高代碼密度和性能。

圖3是鏈接時壓縮替換的示意圖。

圖3 鏈接時壓縮替換的示意圖

根據(jù)上述鏈接壓縮示意圖,通過對上述3種類型不斷的遞歸壓縮,使得程序代碼密度都處于最優(yōu)狀態(tài)。圖4是CSiBEbenchmark使用鏈接時壓縮優(yōu)化策略的代碼密度對比圖。從圖中可以看出,利用鏈接時壓縮優(yōu)化,代碼密度最高提升6.1%,平均提升4.6%。

圖4 壓縮前后代碼密度對比

2.3 地址索引優(yōu)化

在load/store架構(gòu)嵌入式CPU中,獲取全局變量地址、函數(shù)地址或大立即數(shù)時,無法將立即數(shù)直接在指令中編碼,需將立即數(shù)存放在相對當(dāng)前PC偏移一段距離處(即常量池),再通過相對PC偏移內(nèi)存尋址指令讀取立即數(shù)(本文稱其為“地址立即數(shù)裝載指令”,如CK810的lrw指令)。在C語言的程序中,獲得某個全局變量的值,或絕對地址函數(shù)調(diào)用隨處可見,也就是說匯編代碼會包含大量的“地址立即數(shù)裝載指令”,通常在所有指令中占比為8%左右。大量的“地址立即數(shù)裝載指令”勢必會引起常量池的訪問而導(dǎo)致性能和代碼密度下降,一方面,“地址立即數(shù)裝載指令”從常量池內(nèi)存讀取數(shù)據(jù),頻繁的內(nèi)存讀取增加了CPU和數(shù)據(jù)總線的開銷,導(dǎo)致性能的下降;另一方面,“地址立即數(shù)裝載指令”借助常量池來獲得數(shù)據(jù),大量常量池的存在,必定使得代碼密度下降。

為此,本文提出一種名為“錨地址優(yōu)化”的指令替換策略,把“地址立即數(shù)裝載指令”替換成立即數(shù)加法指令,從而提高代碼密度的同時提高性能。匯編時代碼段或數(shù)據(jù)段基地址放在某個預(yù)留的寄存器rb中,通過加法指令計算“地址立即數(shù)裝載指令”中的地址立即數(shù),如CK810中采用匯編指令“addirx, rb,#offset”實現(xiàn)。在鏈接時,“地址立即數(shù)裝載指令”中的地址立即數(shù)已經(jīng)確定,#offset等于把目標(biāo)地址減去代碼段或數(shù)據(jù)段基地址rb。當(dāng)程序執(zhí)行時rx等于代碼段或數(shù)據(jù)段基地址rb加上#offset,就是需要裝載的地址立即數(shù)。通過“錨地址優(yōu)化”的指令替換策略,不僅可以提高運行效率,也提高了代碼密度。圖5是通過CSiBEbenchmark使用“錨地址優(yōu)化”的指令替換策略前后的性能比較圖,從圖中可以看出,通過靜態(tài)地址優(yōu)化策略,性能平均提升2.33%,最高提升3%。

圖5 指令替換策略前后性能對比

2.4 靜態(tài)鏈接地址優(yōu)化

在RISC架構(gòu)嵌入式CPU中,絕對地址函數(shù)調(diào)用的目標(biāo)地址立即數(shù)無法在指令中直接編碼,需要借助常量池,使得函數(shù)的跳轉(zhuǎn)范圍在4 GB內(nèi)。但是在嵌入式領(lǐng)域里,函數(shù)通常只需要在一個很小的范圍內(nèi)跳轉(zhuǎn),如果能把絕對地址函數(shù)調(diào)用指令替換成PC相對跳轉(zhuǎn)指令,不僅能提高程序運行性能,而且還可以刪除常量池,從而提高代碼密度?；谶@個思路,本文提出一種在靜態(tài)鏈接時的函數(shù)調(diào)用優(yōu)化策略,即在靜態(tài)鏈接程序時［12］,根據(jù)鏈接地址信息確定的優(yōu)勢,在重定位絕對地址函數(shù)調(diào)用指令的目標(biāo)地址時,根據(jù)地址的范圍,計算要跳轉(zhuǎn)的地址與當(dāng)前PC距離,若小于PC相對跳轉(zhuǎn)指令的偏移范圍(如CK810為前后64 MB偏移),則把絕對地址函數(shù)調(diào)用指令替換為PC相對跳轉(zhuǎn)指令。

圖6是CSiBEbenchmark使用靜態(tài)鏈接地址優(yōu)化策略的性能對比圖。從圖中可以看出,通過靜態(tài)地址優(yōu)化策略,性能平均提升 5.7%,最高提升6.5%。

圖6 靜態(tài)鏈接地址優(yōu)化策略性能對比

3 實驗與結(jié)果分析

實驗平臺以GCC4.5.1為編譯器,實驗的Case采用標(biāo)準(zhǔn)的benchmark CSiBE,通過編譯器編譯出匯編目標(biāo)文件,再通過匯編鏈接優(yōu)化生成目標(biāo)程序,使目標(biāo)程序運行于小端的CK810處理器上,對CSiBE使用所有的優(yōu)化手段和不使用任何優(yōu)化策略,來比較整體的優(yōu)化效果。

從圖7和圖8可以看出,對程序使用所有的優(yōu)化策略,代碼密度最低提高也有6.12%,最高可達(dá)到11.06%,平均提升 7.52%;而性能最低提升有5.8%,最高有11%,平均提高7.91%。對程序使用所有的優(yōu)化策略,并不是簡單的每個優(yōu)化策略之和相加,這是因為一些優(yōu)化策略,比如壓縮優(yōu)化和地址索引優(yōu)化,在地址索引優(yōu)化中,有壓縮優(yōu)化的功能。另外,在壓縮優(yōu)化時,隨著指令的替換與壓縮,性能會所有提高。所以所有的優(yōu)化放在一起,會比單個優(yōu)化的效果更好,但不是每個優(yōu)化的相加。

圖7 優(yōu)化前后代碼密度對比

圖8 優(yōu)化前后性能對比

4 結(jié)束語

根據(jù)嵌入式16/32位混編指令集特征,在兼顧性能和代碼密度的情況下,本文充分利用編碼特性和鏈接后信息的確定性,對基于16/32位混編指令集在匯編鏈接時做出優(yōu)化,取得較好的效果。另外,在實驗過程中,還發(fā)現(xiàn)在匯編鏈接時,仍有其他優(yōu)化空間。如寄存器編碼優(yōu)化,對整個函數(shù)過程進(jìn)行寄存器生命周期分析,對寄存器進(jìn)行重分配,盡量采用低編碼寄存器,使得指令盡可能用16位進(jìn)行編碼;再如,對常量池重新排序,使得存放同一個變量的常量池合并,把分散在程序中的常量池盡量集中在一起,達(dá)到共享常量池的作用,提高代碼密度。

［1］ Bunda J,Fussell D,Jenevein R,et al.16-bit vs.32-bit Instructions for Pipelined Micro-processors［C］//Proceedings of the 20th Annual International Symposium on Computer Architecture.［S.l.］:IEEE Press,1993:237-246.

［2］ Gupta A R.Enhancing the Performance of 16-bit Code Using Augmenting Instructions［C］//Proceedings of ACM SIGPLAN Conference on Languages Compilers.［S.l.］:ACM Press,2003.

［3］ 劉 博,李蜀瑜,阮 園.一種面向CoSy編譯框架的編譯優(yōu)化開發(fā)方法［J］.計算機(jī)技術(shù)與發(fā)展,2013,23(3): 61-64.

［4］ 張茉莉,楊海鋼,劉 峰,等.針對遞歸函數(shù)的高級綜合編譯優(yōu)化算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2013,25(10):1557-1565.

［5］ 陳 瑜,朱曉靜,鄒 瓊.龍芯鏈接后優(yōu)化器設(shè)計與分析［J］.計算機(jī)研究與發(fā)展,2006,43(8):1450-1456.

［6］ 陳 瑜.龍芯2號鏈接后優(yōu)化器的實現(xiàn)與分析［D］.北京:中國科學(xué)院計算技術(shù)研究所,2004.

［7］ Li D X,Ashok R,Hundt R.Lightweight Feedbackdirected Cross-module Optimization［C］//Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization.［S.l.］:ACM Press,2010:53-61.

［8］ Liu Xianhua,Zhang Jiyu,Cheng Xu.Efficient Code Size Reduction Without Performance Loss［C］//Proceedings of ACM Symposium on Applied Computing.［S.l.］: ACM Press,2007:666-672.

［9］ Bus B,Kaster D,Chanet D,et al.Post-pass Compaction Techniques 2003［J］.Communications of the ACM, 2003,46(8):41-46.

［10］ Phela R.Improving ARM Code Density and Performance［EB/OL］.(2003-05-07).http://www.cs.uiuc.edu/ class/fa05/cs433ug/PROCESSORS/Thumb2.pdf.

［11］ Sutter B.Link-time Binary Rewriting Techniques for Program Compaction［J］.ACM Transactions on Programming Languages and Systems,2005,27(5): 882-945.

［12］ Jones T M,BartoliniS,Maebe J,etal.Link-time Optimization for Power Efficiency in a Tagless Instruction Cache［C］//Proceedings of the 9th Annual IEEE/ACM InternationalSymposium on Code Generation and Optimization.［S.l.］:IEEE Press,2011:32-41.

編輯 顧逸斐

Assembly and Link Time Optimization Based on CK810 Processor

HU Min,LU Yongjiang,LIU Bing
(Institute of Very Large Scale Integrated Circuits Design,Zhejiang University,Hangzhou 310027,China)

According to feature of 16/32 bit mixed instruction set of CK810,assembly and link time optimization techniques based on the 16/32 mixed instruction set of CK810 make use of assembler output binary files to achieve instructions relax and coding instructions dynamically.The assembler gives relocations to linker for instructions that can' t decide how to code at assembly time,the techniques fully utilizes the information only available at link time to realize of the entire program for compression and replacement of instructions to make program more efficient and small.Assembly and link optimization techniques overcome the limitations of traditional compilers by enlarging the optimizing scope from a single function or a module to the whole program,making the code density on CK810 increase an average of 7.52%, the average performance improvement of 7.91%.

assembly optimization;link optimization;dynamic coding;relocation;compaction;replace

1000-3428(2014)11-0250-05

A

TP313

10.3969/j.issn.1000-3428.2014.11.050

國家“863”計劃基金資助項目(2009AA011706)。

胡 敏(1987-),男,碩士,主研方向:嵌入式系統(tǒng);盧永江,副教授、博士;劉 兵,碩士研究生。

2013-10-25

2014-01-06E-mail:zju21110143@163.com

中文引用格式:胡 敏,盧永江,劉 兵.基于CK810處理器的匯編鏈接時優(yōu)化［J］.計算機(jī)工程,2014,40(11):250-254.

英文引用格式:Hu Min,Lu Yongjiang,Liu Bing.Assembly and Link Time Optimization Based on CK810 Processor［J］.Computer Engineering,2014,40(11):250-254.