面向ARM平臺的二進制翻譯系統(tǒng)標志位優(yōu)化

杜 彬,趙瑞珍,李 瓊

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

面向ARM平臺的二進制翻譯系統(tǒng)標志位優(yōu)化

杜 彬,趙瑞珍,李 瓊

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

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

定義 定值標志位的ARM指令為模式頭,使用標志位的ARM指令為模式尾。

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

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

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

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

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

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

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

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

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

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

2.2 各種模式的翻譯

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

2.2.1 一頭一尾

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

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

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

2.2.2 一頭多尾

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

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

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

2.2.3 多頭多尾

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

圖4 多頭多尾的翻譯代碼

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

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

3 實驗數(shù)據(jù)

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

3.1 指令數(shù)比

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

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

這里用指令數(shù)比作為衡量系統(tǒng)性能的一個指標。指令數(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ù)減少達14%。

3.2 系統(tǒng)性能

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

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

4 結(jié)束語

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

[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] 白童心.動態(tài)二進制翻譯與動態(tài)優(yōu)化相關(guān)問題研究[D].北京:中國科學院計算技術(shù)研究所,2004.

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

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

[7] 唐 鋒,武成崗,馮曉兵,等.基于動態(tài)反饋的標志位線性分析算法[J].軟件學報,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-),男,碩士研究生,主研方向:二進制翻譯,編譯優(yōu)化;趙瑞珍,教授、博士生導師;李 瓊,碩士研究生。

2013-09-09

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

中文引用格式:杜 彬,趙瑞珍,李 瓊.面向ARM平臺的二進制翻譯系統(tǒng)標志位優(yōu)化[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.