杜 彬,趙瑞珍,李 瓊

(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,北京100044)

面向ARM平臺(tái)的二進(jìn)制翻譯系統(tǒng)標(biāo)志位優(yōu)化

杜 彬,趙瑞珍,李 瓊

(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,北京100044)

二進(jìn)制翻譯系統(tǒng)是不同平臺(tái)之間代碼移植的橋梁,而系統(tǒng)性能是制約其應(yīng)用的主要因素。在二進(jìn)制翻譯中,翻譯經(jīng)過標(biāo)志位分析處理后的非冗余標(biāo)志位需要較多的指令,極大影響了系統(tǒng)的性能。針對(duì)該問題,提出一種標(biāo)志位的模式優(yōu)化方法,在標(biāo)志位分析處理基礎(chǔ)上,將定值標(biāo)志位和使用標(biāo)志位的ARM指令組成固定模式,根據(jù)不同的模式用MIPS指令組合翻譯達(dá)到相同的語義。實(shí)驗(yàn)結(jié)果表明,利用標(biāo)志位的模式優(yōu)化方法可使翻譯產(chǎn)生的MIPS代碼量減少14%,系統(tǒng)性能平均提高13.7%。

二進(jìn)制翻譯;標(biāo)志位的模式優(yōu)化;條件執(zhí)行;模式頭;模式尾

1 概述

在當(dāng)今的手持終端(如手機(jī)、平板電腦)市場(chǎng)中, ARM占據(jù)著絕大多數(shù)的份額,而MIPS作為后來者,缺乏與之相配套的應(yīng)用軟件。由于ARM平臺(tái)上的很多應(yīng)用軟件并不開源,大大增加了程序移植的難度。在這樣的條件下,使用二進(jìn)制翻譯系統(tǒng),將ARM平臺(tái)上的軟件直接移植到MIPS平臺(tái)上,是一個(gè)合適的選擇。而性能是制約二進(jìn)制翻譯系統(tǒng)應(yīng)用的一個(gè)重要因素,為了提高系統(tǒng)的性能,對(duì)它的優(yōu)化必不可少。標(biāo)志位優(yōu)化就是其中一個(gè)非常有效的優(yōu)化。

Fx!32[1]是一個(gè)結(jié)合解釋執(zhí)行和靜態(tài)翻譯2種模式的二進(jìn)制翻譯系統(tǒng)。采用延遲計(jì)算的方法,在執(zhí)行標(biāo)志位定值的指令時(shí),把所有計(jì)算標(biāo)志位需要用的信息(包括操作數(shù),操作碼等信息)保存起來,當(dāng)需要使用到標(biāo)志位時(shí)再通過保存的信息計(jì)算標(biāo)志位。

Queensland大學(xué)開發(fā)的 UQBT[2]可變?cè)础⒖勺兡繕?biāo)的靜態(tài)二進(jìn)制翻譯器,在與ISA相關(guān)的低層中間表示轉(zhuǎn)化到與ISA無關(guān)的高層中間表示的過程中,通過數(shù)據(jù)流分析去除冗余的標(biāo)志位定值,對(duì)非冗余的標(biāo)志位引用標(biāo)志位,按照一定模式轉(zhuǎn)化為相應(yīng)的高層中間表示。但該方法只對(duì)由高級(jí)語言編譯生成的程序才有效,如果源程序本身是匯編代碼而導(dǎo)致不能正確確定模式,這種方法就失效了。

Intel的IA32 EL[3]構(gòu)建不完全數(shù)據(jù)流圖,一般包含多個(gè)基本塊,然后在此數(shù)據(jù)流圖上進(jìn)行標(biāo)志位分析。但是在基本塊邊界上,就會(huì)產(chǎn)生冗余的無法消除的標(biāo)志位定值。

文獻(xiàn)[4-5]提出了基于edge profile的熱路徑選擇算法FHFS,并在熱路徑上實(shí)施基于模式匹配的指令組合優(yōu)化翻譯和標(biāo)志位延遲計(jì)算的優(yōu)化,其中模式匹配是將相鄰的一些指令作為指令組合翻譯。

文獻(xiàn)[6]中提出的立即計(jì)算和延遲計(jì)算相結(jié)合算法以及數(shù)據(jù)流和延遲計(jì)算相結(jié)合算法,這2個(gè)算法本身開銷很小,但是只對(duì)基本塊內(nèi)部進(jìn)行分析,而基本塊間采用延遲計(jì)算,所以只是基本塊內(nèi)的冗余標(biāo)志位定值可以消除。

文獻(xiàn)[7]提出基于動(dòng)態(tài)反饋的標(biāo)志位線性分析算法,該算法分析后繼基本塊的標(biāo)志位定值和引用,可以基本上可以消除冗余標(biāo)志位定值。

文獻(xiàn)[8]描述了一個(gè)為嵌入式系統(tǒng)設(shè)計(jì)的將ARM二進(jìn)制程序翻譯到類MIPS平臺(tái)的靜態(tài)二進(jìn)制翻譯器,在FX!32標(biāo)志位分析處理基礎(chǔ)上,對(duì)于需要計(jì)算的標(biāo)志位,分配4個(gè)獨(dú)立的寄存器來保存4個(gè)標(biāo)志位以減少定值每個(gè)標(biāo)志位時(shí)的移位操作[8]。但當(dāng)目標(biāo)平臺(tái)的寄存器不夠時(shí),該方法有局限性。

文獻(xiàn)[1-3,6-8]中標(biāo)志位分析處理后還需對(duì)非冗余的標(biāo)志位定值及其使用進(jìn)行翻譯,文獻(xiàn)[4-5]中僅對(duì)簡(jiǎn)單的模式進(jìn)行匹配翻譯。本文在上述分析的基礎(chǔ)上,提出模式化翻譯ARM標(biāo)志位的方法,將定值標(biāo)志位的ARM指令與使用標(biāo)志位的ARM指令組成一個(gè)模式,翻譯時(shí)根據(jù)不同模式用不同MIPS指令組合達(dá)到相同的功能,這樣不僅可以消除文獻(xiàn)[8]中寄存器可能不夠用的局限性,還可以減少因翻譯標(biāo)志位的定值和使用而產(chǎn)生的代碼量。

2 標(biāo)志位的模式優(yōu)化

定義 定值標(biāo)志位的ARM指令為模式頭,使用標(biāo)志位的ARM指令為模式尾。

標(biāo)志位的模式優(yōu)化就是以基本塊(translation block,TB)為單位掃描并查找記錄TB內(nèi)模式頭和相應(yīng)的模式尾,翻譯的時(shí)候根據(jù)記錄的頭尾組合信息用相應(yīng)的MIPS指令來實(shí)現(xiàn)標(biāo)志位的定值及其使用。

模式頭尾組合通常有3類:一個(gè)模式頭對(duì)應(yīng)一個(gè)模式尾,即一頭一尾;一個(gè)模式頭對(duì)應(yīng)多個(gè)模式尾,即一頭多尾;一條指令既定值標(biāo)志位又本身是否執(zhí)行需要看條件是否滿足,如addseq,若eq條件滿足才執(zhí)行add并根據(jù)運(yùn)算結(jié)果置相應(yīng)標(biāo)志位,定義add為潛在的模式頭,而這樣的一類模式組合中,既有模式頭和模式尾,也存在潛在的模式頭,稱為多頭多尾。

圖1是SPEC2000中175.vpr程序經(jīng)過標(biāo)志位分析處理后翻譯生成的一段代碼,源平臺(tái)為ARM,目標(biāo)平臺(tái)為MIPS。在這段代碼中,ARM指令cmp比較2個(gè)寄存器r2和r3的值,根據(jù)比較結(jié)果對(duì)C和Z標(biāo)志位定值。指令bls中l(wèi)s是執(zhí)行條件,使用標(biāo)志位C和Z,若C==0或者Z==1則跳轉(zhuǎn)[9]。標(biāo)志位的一次定值,即更新標(biāo)志位寄存器相應(yīng)標(biāo)志位的翻譯,平均需要4條MIPS指令[10],標(biāo)志位一次使用的翻譯平均需要2條MIPS指令。由此可見,在標(biāo)志位分析處理之后,翻譯非冗余的標(biāo)志位定值和使用依然產(chǎn)生較多的指令。

圖1 刪除冗余標(biāo)志位定值后翻譯產(chǎn)生的代碼

2.1 模式頭尾組合的查找和記錄

對(duì)模式頭尾組合的查找和記錄是從TB的最后一條指令開始往前掃描完成的,具體的算法語言描述如下:

(1)從后往前挨個(gè)指令掃描TB,若該指令不是模式尾,即不使用標(biāo)志位,則繼續(xù)往前查找,若是模式尾,則轉(zhuǎn)步驟(2)。

(2)從該模式尾往前掃描對(duì)應(yīng)的模式頭,即模式頭必須定值了該模式尾所有使用到的標(biāo)志位,若找不到對(duì)應(yīng)的模式頭,則轉(zhuǎn)步驟(1)繼續(xù)查找新的模式尾,若能找到,則記錄模式頭尾信息,轉(zhuǎn)步驟(3)。

(3)從該模式尾再往前掃描直到模式頭,查找尾對(duì)應(yīng)的潛在模式頭,同樣潛在模式頭也必須定值了該模式尾所有使用的標(biāo)志位。記錄該模式尾對(duì)應(yīng)的所有潛在模式頭。

(4)重復(fù)步驟(1)～步驟(3)直到掃描到TB的第1條指令結(jié)束。其中,步驟(1)、步驟(2)完成一頭一尾和一頭多尾的查找和記錄,若多個(gè)不同的模式尾對(duì)應(yīng)相同的模式頭即同一條ARM指令,說明這是一頭多尾形式,需要將多個(gè)尾記錄到尾鏈表中,并記錄多個(gè)尾的位置信息,如是第幾個(gè)尾。步驟(3)完成多頭多尾的記錄,模式尾對(duì)應(yīng)的所有潛在模式頭也需記錄在潛在模式頭鏈表中。至此,TB中所有模式記錄完畢,下面就可以根據(jù)不同的模式進(jìn)行翻譯了。

2.2 各種模式的翻譯

各種模式頭包括潛在模式頭的翻譯方法相同,翻譯模式頭的時(shí)候是保存源操作數(shù)還是保存目的操作數(shù)要看尾的信息。在一個(gè)或多個(gè)模式尾的翻譯中有需要源操作數(shù)的,那么翻譯模式頭就保存源操作數(shù),若翻譯遇到需要目的操作數(shù)的模式尾時(shí),只需利用源操作數(shù)運(yùn)算便可得到目的操作數(shù)。另外需要注意的是,若后繼TB使用了該模式頭定值的標(biāo)志位,那么此處標(biāo)志位的定值翻譯不可省略。

2.2.1 一頭一尾

模式中無潛在模式頭且只有一個(gè)模式尾,就用一頭一尾的方法來處理。圖1中的模式是典型的一頭一尾形式,只有一個(gè)模式頭cmp和一個(gè)模式尾bls。這個(gè)模式的翻譯如圖2所示。

圖2 模式優(yōu)化后的代碼

r2,r3為源操作數(shù),翻譯cmp時(shí)只需將源保存,翻譯bls時(shí)利用保存的源比較跳轉(zhuǎn),就可以完成這2條ARM的功能。

2.2.2 一頭多尾

模式中無潛在模式頭且有多個(gè)模式尾,就采用一頭多尾的方法來處理。這里模式尾的翻譯和該模式尾在多個(gè)尾中的相對(duì)位置有關(guān)。一種情況是各個(gè)尾的執(zhí)行條件不同,這種情況可以看成多組一頭一尾的形式,不再贅述。另一種比較特殊且常見的情況是多個(gè)模式尾相鄰且執(zhí)行條件相同,圖3是多個(gè)相同模式尾相鄰且執(zhí)行條件相同的情況,來自SPEC2000中164.bzip程序經(jīng)過標(biāo)志位分析處理后生成的代碼片段。

圖3 多個(gè)模式尾相鄰且執(zhí)行條件相同的翻譯

翻譯第一個(gè)模式尾不再是讓其跳轉(zhuǎn)到下一條指令的地址,而是跳轉(zhuǎn)到最后一個(gè)尾的下一條指令的地址,這樣在實(shí)際運(yùn)行時(shí)如果條件lt不滿足,就直接跳轉(zhuǎn)到add執(zhí)行。其余模式尾的條件可以不用翻譯。

2.2.3 多頭多尾

模式中有潛在的模式頭,那么此模式為多頭多尾形式。圖4是SPEC2000中181.mcf程序經(jīng)過標(biāo)志位分析處理后生成的代碼片段。第1個(gè)和第2個(gè)模式尾的翻譯方式同一頭多尾形式,第3個(gè)模式尾的翻譯有所不同,因第3個(gè)尾使用的標(biāo)志位,既可能是sub定值的,又可能是teq定值的(若第3條ARM指令的執(zhí)行條件滿足)。經(jīng)分析發(fā)現(xiàn),模式sub-eq和teq-eq可以用一種翻譯方式,即跟t8中保存的運(yùn)算結(jié)果比較跳轉(zhuǎn),這樣把第3個(gè)尾翻譯為 bnez t8, target,則t8總是保存定值標(biāo)志位的那條ARM指令的目的操作數(shù),就能保證翻譯的正確性。因此諸如sub-eq,teq-eq這些具有相同執(zhí)行條件但模式頭不同的模式,翻譯時(shí)盡量用相同的MIPS指令。

圖4 多頭多尾的翻譯代碼

圖5統(tǒng)計(jì)了SEPC CINT2000中10個(gè)程序中出現(xiàn)多頭多尾模式的個(gè)數(shù),共計(jì)1 019個(gè)多頭多尾模式都可以用上述方法翻譯而正確執(zhí)行。

圖5 多頭多尾模式的數(shù)量

3 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)的目標(biāo)平臺(tái)是兼容MIPS的龍芯3A機(jī)器,主頻900 MHz,內(nèi)存2 GB。將模式優(yōu)化應(yīng)用一個(gè)從ARM到MIPS的二進(jìn)制翻譯系統(tǒng)中,經(jīng)SPEC2000 CINT2000目錄中10個(gè)整形基準(zhǔn)程序測(cè)試通過。其中 SPEC2000是由 crosstool-ng-1.18.0建立的ARM交叉編譯工具鏈編譯生成,由于工具鏈限制, 253.perlbmk和300.twolf沒有編譯成功,在此不對(duì)這2個(gè)基準(zhǔn)程序做實(shí)驗(yàn)測(cè)試。

3.1 指令數(shù)比

圖6給出了在SPEC2000 test輸入集下,模式優(yōu)化前后的指令數(shù)比。

圖6 模式優(yōu)化前后的指令數(shù)比

這里用指令數(shù)比作為衡量系統(tǒng)性能的一個(gè)指標(biāo)。指令數(shù)比就是翻譯1條ARM指令平均需要MIPS指令的條數(shù)。以164.gzip為例,優(yōu)化前,翻譯1條ARM指令大概需要4.2條MIPS指令,優(yōu)化后,翻譯需要的MIPS指令數(shù)為3.6。平均來看,模式優(yōu)化后比模式優(yōu)化前翻譯需要的MIPS指令數(shù)減少達(dá)14%。

3.2 系統(tǒng)性能

圖7給出了在SPEC2000 test、ref、train3個(gè)輸入集下,應(yīng)用模式優(yōu)化后二進(jìn)制翻譯系統(tǒng)的性能提升。平均來看,應(yīng)用模式優(yōu)化帶來的系統(tǒng)提升在各個(gè)輸入集下到達(dá)13.7%。

圖7 模式優(yōu)化后二進(jìn)制翻譯系統(tǒng)的性能

4 結(jié)束語

本文提出一種在ARM翻譯到MIPS中的標(biāo)志位模式優(yōu)化方法,利用若干MIPS指令組合來達(dá)到某些固定ARM指令組合的功能,這樣可以減少翻譯標(biāo)志位的定值和使用而生成的代碼量。此優(yōu)化方法經(jīng)過正確性驗(yàn)證,可以有效地降低翻譯標(biāo)志位而造成的代碼膨脹,從而提高系統(tǒng)的性能。文中多頭多尾的處理只是對(duì)SPEC2000的10個(gè)整形基準(zhǔn)程序中出現(xiàn)的多頭多尾情況做了討論及處理。下一步將對(duì)該部分內(nèi)容繼續(xù)進(jìn)行研究。另外,文中保存操作數(shù)的指令可以利用經(jīng)典編譯優(yōu)化進(jìn)一步精簡(jiǎn)。

[1] Chernoff A,Herdeg M,Hookway R,et al.FX!32——A Profile-directed Binary Translator[J].IEEE Micro, 1998,18(2):56-64.

[2] Cifuentes C,van Emmerik M.UQBT:Adaptable Binary Translation at Low Cost[J].IEEE Computer,2000,33 (3):60-66.

[3] Baraz L,Devor T,Etzion O,et al.IA-32Execution Layer:A Two-phase Dynamic Translator Designed to SupportIA-32 Applications on Itanium ?-based Systems[C]//Proc.of MICRO’03.Piscataway,USA: IEEE Press,2003:191-201.

[4] 白童心.動(dòng)態(tài)二進(jìn)制翻譯與動(dòng)態(tài)優(yōu)化相關(guān)問題研究[D].北京:中國科學(xué)院計(jì)算技術(shù)研究所,2004.

[5] 白童心,馮曉兵,武成崗,等.優(yōu)化動(dòng)態(tài)二級(jí)制翻譯器DigitalBridge[J].計(jì)算機(jī)工程,2005,31(10):103-105.

[6] 馬湘寧,武成崗,唐 峰,等.二進(jìn)制翻譯中的標(biāo)志位優(yōu)化技術(shù)[J].計(jì)算機(jī)研究與發(fā)展,2005,42(2): 329-337.

[7] 唐 鋒,武成崗,馮曉兵,等.基于動(dòng)態(tài)反饋的標(biāo)志位線性分析算法[J].軟件學(xué)報(bào),2007,18(7):1603-1611.

[8] Chen J Y,Wang W,Huang T H,et al.On Static Binary Translation and Optimization for ARM Based Applications[C]//Proc.ofthe 6th Workshop on Optimizations for DSP and Embedded Systems. New York,USA:ACM Press,2008:1-10.

[9] ARM.Architecture Reference Manual ARM.v7-A and ARM?v7-R Edition[EB/OL].(2011-10-21).http:// infocenter.arm.com/help/topic/com.arm.doc.ddi0406b/ index.html.

[10] MIPS.Architecture for Programmers Volume II-A:The MIPS64.Instruction Set[EB/OL].(2011-05-21).http://scc. ustc.edu.cn/zlsc/lxwycj/200910/W020100308600769158777. pdf.

編輯 索書志

Flag Bit Optimization in Binary Translation System Oriented to ARM Platform

DU Bin,ZHAO Rui-zhen,LI Qiong
(School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China)

Binary translation system is a bridge between codes of different platforms,while the performance of the system restricts its application.In binary translation,after data flow analysis on those flags,the translation of conditional flags still needs plenty of native instructions which greatly affects the performance of systems.To solve this problem,a flag pattern optimization method is presented,this method which is based on data flow analysis makes ARM instruction of definition flag and usage flag become a fixed pattern,and depends on different patterns to achieve the same semantic by choosing appropriate MIPS instructions.Experimental results show that MIPS code generated by translating has a 14% reduction,and the system performance is improved by 13.7%.

binary translation;pattern optimization of flag bit;conditional execution;pattern head;pattern tail

1000-3428(2014)10-0318-04

A

TP391

10.3969/j.issn.1000-3428.2014.10.059

杜 彬(1986-),男,碩士研究生,主研方向:二進(jìn)制翻譯,編譯優(yōu)化;趙瑞珍,教授、博士生導(dǎo)師;李 瓊,碩士研究生。

2013-09-09

2013-10-22E-mail:11120422@bjtu.edu.cn

中文引用格式:杜 彬,趙瑞珍,李 瓊.面向ARM平臺(tái)的二進(jìn)制翻譯系統(tǒng)標(biāo)志位優(yōu)化[J].計(jì)算機(jī)工程,2014, 40(10):318-321.

英文引用格式:Du Bin,Zhao Ruizhen,Li Qiong.Flag Bit Optimization in Binary Translation System Oriented to ARM Platform[J].Computer Engineering,2014,40(10):318-321.