一種高效解決間接轉(zhuǎn)移的反饋式靜態(tài)二進(jìn)制翻譯方法

王 軍 龐建民 傅立國(guó) 岳 峰 張家豪

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室(戰(zhàn)略支援部隊(duì)信息工程大學(xué)) 鄭州 450002)

二進(jìn)制翻譯[1]的核心目標(biāo)是將源指令集的指令序列通過代碼翻譯操作，翻譯成等價(jià)的其他指令集的指令序列.二進(jìn)制翻譯已廣泛用于軟件安全分析[2-3]、程序行為分析[4]、軟件逆向工程、系統(tǒng)虛擬等領(lǐng)域，并已成為軟件移植[5]的主流技術(shù).如FX!32把x86平臺(tái)下的Win32應(yīng)用程序移植到Alpha平臺(tái)[6-7]；昆士蘭大學(xué)開發(fā)的跨平臺(tái)靜態(tài)二進(jìn)制翻譯器UQBT(University of Queensland binary translator)，可以支持不同源平臺(tái)應(yīng)用程序到目的平臺(tái)的翻譯；動(dòng)態(tài)二進(jìn)制翻譯器QEMU (quick emulator) 同時(shí)支持進(jìn)程級(jí)和系統(tǒng)級(jí)程序翻譯，并已成功實(shí)現(xiàn)對(duì)國(guó)產(chǎn)龍芯平臺(tái)的支持[8].

主流的二進(jìn)制翻譯可以分為動(dòng)態(tài)二進(jìn)制翻譯、靜態(tài)二進(jìn)制翻譯和動(dòng)靜結(jié)合的二進(jìn)制翻譯[9].動(dòng)態(tài)二進(jìn)制翻譯[10]是一種即時(shí)翻譯(邊翻譯邊執(zhí)行)技術(shù)，在運(yùn)行目標(biāo)代碼時(shí)能很好地解決代碼發(fā)現(xiàn)和代碼定位問題[11-12]，但是動(dòng)態(tài)二進(jìn)制翻譯需要在動(dòng)態(tài)翻譯源平臺(tái)二進(jìn)制可執(zhí)行程序的同時(shí)執(zhí)行翻譯生成的目標(biāo)平臺(tái)二進(jìn)制程序，翻譯時(shí)間和代碼優(yōu)化時(shí)間占據(jù)程序執(zhí)行時(shí)間，所以動(dòng)態(tài)二進(jìn)制翻譯不能采用深度優(yōu)化的方法.即便目前有很多優(yōu)化方法，如熱路徑優(yōu)化[13]、寄存器映射[14]、多線程并行優(yōu)化[8]等，在一定程度上提高了動(dòng)態(tài)二進(jìn)制翻譯的效率，但動(dòng)態(tài)二進(jìn)制翻譯效率低的問題仍然比較突出.靜態(tài)二進(jìn)制翻譯在不運(yùn)行程序的情況下，靜態(tài)分析源平臺(tái)可執(zhí)行文件，提取程序指令進(jìn)行翻譯，能夠采用較復(fù)雜的代碼分析和優(yōu)化算法，能生成高質(zhì)量的代碼，程序執(zhí)行效率較高；而且靜態(tài)二進(jìn)制翻譯方式一次翻譯多次執(zhí)行的特性也十分適用于高性能計(jì)算程序的翻譯，但是靜態(tài)二進(jìn)制翻譯難以處理下段的代碼發(fā)現(xiàn)和代碼定位問題[15].

代碼發(fā)現(xiàn)問題是指在靜態(tài)條件下難以獲取間接轉(zhuǎn)移(具體可分為間接跳轉(zhuǎn)和間接調(diào)用[16])目標(biāo)地址的問題，間接轉(zhuǎn)移指令的目標(biāo)地址可能是一個(gè)寄存器或者存儲(chǔ)器的值；代碼定位問題是指難以在程序執(zhí)行時(shí)確定源平臺(tái)轉(zhuǎn)移目的地址對(duì)應(yīng)的目標(biāo)平臺(tái)代碼地址.

目前現(xiàn)有的解決靜態(tài)二進(jìn)制翻譯中由間接轉(zhuǎn)移引起的代碼發(fā)現(xiàn)和代碼定位問題的方法，無論是解釋器法還是地址映射表法，都存在一個(gè)共同的缺陷：生成代碼質(zhì)量不高且含有較多的冗余代碼.為了更高效地解決靜態(tài)二進(jìn)制翻譯面臨的代碼發(fā)現(xiàn)問題，本文對(duì)課題組之前實(shí)現(xiàn)的基于動(dòng)態(tài)二進(jìn)制翻譯器QEMU的靜態(tài)二進(jìn)制翻譯器SQEMU[17](static QEMU)進(jìn)行了優(yōu)化和改進(jìn)，提出了以基本塊為單位進(jìn)行翻譯的反饋式靜態(tài)二進(jìn)制翻譯框架(feedback static QEMU, FD-SQEMU)，并提出了二級(jí)地址映射表法，更快速地實(shí)現(xiàn)了代碼定位.為了解決基本塊翻譯引入的代碼定位問題，設(shè)計(jì)了高效的二級(jí)地址映射表來快速定位轉(zhuǎn)移指令目標(biāo)地址.在翻譯過程中，使用數(shù)組結(jié)構(gòu)Address保存源平臺(tái)每個(gè)基本塊對(duì)應(yīng)的目標(biāo)平臺(tái)的代碼基本塊起始地址，并使用索引數(shù)組Index保存源平臺(tái)指令地址在Address中對(duì)應(yīng)的索引位置，從而根據(jù)Index和Address數(shù)組快速得到源平臺(tái)指令塊在目的平臺(tái)上的對(duì)應(yīng)地址.為了解決靜態(tài)二進(jìn)制翻譯中的代碼定位問題，本文引入了反饋機(jī)制，在靜態(tài)翻譯目標(biāo)程序時(shí)對(duì)間接轉(zhuǎn)移指令添加監(jiān)控反饋代碼，之后運(yùn)行翻譯后的目標(biāo)程序，依據(jù)監(jiān)控反饋信息[6]確定間接轉(zhuǎn)移目標(biāo)地址進(jìn)行代碼發(fā)現(xiàn).之后，依據(jù)反饋的間接轉(zhuǎn)移目標(biāo)信息對(duì)源程序重新進(jìn)行基本塊劃分，然后繼續(xù)翻譯、執(zhí)行、反饋，重復(fù)此過程直至程序能正常執(zhí)行結(jié)束.

本文的主要貢獻(xiàn)有3個(gè)方面:

1) 針對(duì)現(xiàn)有靜態(tài)二進(jìn)制翻譯中由間接轉(zhuǎn)移指令引起的代碼發(fā)現(xiàn)和代碼定位問題解決方法效率較低的缺陷，提出了基于基本塊翻譯的反饋式靜態(tài)二進(jìn)制翻譯框架FD-SQEMU，以基本塊方式進(jìn)行翻譯能更好地進(jìn)行代碼優(yōu)化，生成更高質(zhì)量的目標(biāo)代碼.

2) 針對(duì)SQEMU線性逐行遍歷翻譯方式不能兼顧程序上下文以及引入大量冗余代碼的缺陷，改進(jìn)了地址映射方式，提出了二級(jí)地址映射表法，更快速地解決了靜態(tài)二進(jìn)制翻譯中代碼定位問題.

3) 提出了新的代碼發(fā)現(xiàn)的思路，利用動(dòng)態(tài)執(zhí)行、監(jiān)控、反饋進(jìn)行代碼發(fā)現(xiàn)，更有效地解決了數(shù)據(jù)段代碼問題.另外，該方法雖然是針對(duì)基于QEMU的靜態(tài)二進(jìn)制翻譯框架SQEMU實(shí)現(xiàn)的，但具有相當(dāng)強(qiáng)的通用性，不限于目標(biāo)平臺(tái)和指令形式，對(duì)降低二進(jìn)制翻譯后的代碼膨脹率有重要意義，有很強(qiáng)的可擴(kuò)展性.

1 相關(guān)工作

目前，靜態(tài)二進(jìn)制翻譯在不同的平臺(tái)已有不同的實(shí)現(xiàn)，本節(jié)首先對(duì)靜態(tài)二進(jìn)制翻譯中間接轉(zhuǎn)移處理的相關(guān)方法進(jìn)行介紹，然后重點(diǎn)對(duì)二進(jìn)制翻譯系統(tǒng)HBT(hybrid binary translation)和SQEMU的工作方式及其優(yōu)缺點(diǎn)進(jìn)行介紹.

1.1 常見的靜態(tài)二進(jìn)制翻譯中間接轉(zhuǎn)移處理方法

一種主流的解決靜態(tài)二進(jìn)制翻譯中間接轉(zhuǎn)移問題的方法是引入解釋器.

目前已有成熟的靜態(tài)二進(jìn)制翻譯系統(tǒng)引入解釋器模塊來處理二進(jìn)制翻譯中的間接轉(zhuǎn)移問題，例如跨平臺(tái)靜態(tài)二進(jìn)制翻譯器UQBT系統(tǒng)[7].UQBT系統(tǒng)先將源平臺(tái)二進(jìn)制文件Ms抽象為機(jī)器無關(guān)語言HRTL(higher-level register transfer language)，之后對(duì)HRTL中間語言進(jìn)行優(yōu)化，生成目的平臺(tái)可執(zhí)行文件.在將HRTL中間語言翻譯為目標(biāo)機(jī)器指令遇到間接轉(zhuǎn)移指令時(shí)，UQBT系統(tǒng)使用解釋器再次使用源二進(jìn)制文件解釋執(zhí)行獲得Ms到Mt的地址映射.

使用解釋器法處理間接轉(zhuǎn)移存在著2個(gè)問題：1)處理速度較慢;2)需要重復(fù)使用源二進(jìn)制文件的代碼段.

另一種主流的解決靜態(tài)二進(jìn)制翻譯中間接轉(zhuǎn)移問題的方法是地址映射表法，地址映射表實(shí)質(zhì)上替代了上述解釋器獲取間接轉(zhuǎn)移目標(biāo)的功能.

比較成熟的使用地址映射表法處理間接轉(zhuǎn)移問題的二進(jìn)制翻譯系統(tǒng)如Shen等人[18]提出的基于LLVM(low level virtual machine)的動(dòng)靜結(jié)合的二進(jìn)制翻譯系統(tǒng)HBT和盧帥兵等人[17]提出的基于QEMU的靜態(tài)翻譯器SQEMU.

1.2 基于LLVM的動(dòng)靜結(jié)合的二進(jìn)制翻譯系統(tǒng)HBT

HBT系統(tǒng)將動(dòng)態(tài)翻譯器作為目標(biāo)代碼的一個(gè)動(dòng)態(tài)庫(kù)鏈接入二進(jìn)制文件，在翻譯源程序完畢開始執(zhí)行時(shí)若遇到間接轉(zhuǎn)移指令，則查找地址映射表確認(rèn)分支目標(biāo)地址，如未找到，則啟動(dòng)動(dòng)態(tài)二進(jìn)制翻譯器進(jìn)行處理.可見，地址映射表結(jié)構(gòu)的設(shè)計(jì)直接關(guān)系到系統(tǒng)執(zhí)行的效率.

另外，HBT采用LLVM switch 指令，生成一系列的if-else指令，這些指令需要比較和跳轉(zhuǎn)才能定位到目標(biāo)跳轉(zhuǎn)地址，該方法的又一個(gè)局限性是不可能將所有的目標(biāo)地址放入LLVM switch列表.實(shí)際上，HBT僅將返回地址、函數(shù)指針、函數(shù)入口點(diǎn)作為地址映射表項(xiàng)，對(duì)switch語句產(chǎn)生的間接跳轉(zhuǎn)指令并沒有統(tǒng)一的解決方法，在實(shí)現(xiàn)中僅對(duì)ARM平臺(tái)二進(jìn)制文件進(jìn)行了處理.

1.3 基于QEMU的靜態(tài)翻譯器SQEMU

SQEMU是基于QEMU改造的一個(gè)靜態(tài)翻譯器，其實(shí)質(zhì)是采用地址映射表法處理間接轉(zhuǎn)移問題，其具體翻譯過程如圖1所示，其中TCG(tiny code generator)為QEMU自帶的中間表示.

Fig. 1 Framework of SQEMU圖1 SQEMU框架設(shè)計(jì)

SQEMU分離了翻譯時(shí)間、代碼優(yōu)化時(shí)間和目標(biāo)程序執(zhí)行時(shí)間[17]，使得目標(biāo)程序在翻譯中及翻譯后能夠采用不同層次的優(yōu)化算法，生成更高質(zhì)量的執(zhí)行代碼，這也是靜態(tài)二進(jìn)制翻譯器的優(yōu)勢(shì).首先，SQEMU線性遍歷、逐行翻譯源程序，并使用地址索引映射表記錄每一條源平臺(tái)指令對(duì)應(yīng)的目的平臺(tái)指令塊起始地址，成功解決了靜態(tài)二進(jìn)制翻譯中由間接跳轉(zhuǎn)和間接轉(zhuǎn)移指令引起的代碼發(fā)現(xiàn)和代碼定位問題.另外，SQEMU實(shí)現(xiàn)了對(duì)本地庫(kù)函數(shù)的封裝[19]，在目標(biāo)平臺(tái)模擬源平臺(tái)參數(shù)傳遞和返回規(guī)則，實(shí)現(xiàn)了目標(biāo)程序調(diào)用本地庫(kù)函數(shù)的功能，提高了程序執(zhí)行效率.

但是，為解決靜態(tài)二進(jìn)制翻譯面臨的代碼發(fā)現(xiàn)和代碼定位問題，SQEMU采用線性遍歷、逐行翻譯的方法，通過生成每一條x86指令對(duì)應(yīng)的標(biāo)簽來輔助進(jìn)行代碼定位。該方法存在2個(gè)問題:1)逐行翻譯的方式忽略了程序上下文信息，無法借助基本塊優(yōu)化算法等對(duì)翻譯代碼進(jìn)行有效優(yōu)化；2)逐行翻譯引入了較多的冗余代碼，導(dǎo)致代碼膨脹率較高，程序整體執(zhí)行效率較低.

為解決SQEMU逐行翻譯無法進(jìn)行塊內(nèi)優(yōu)化以及引入較多冗余代碼、目標(biāo)程序執(zhí)行效率較低的問題，本文引入了基本塊翻譯方式.但與此同時(shí)，基本塊翻譯方式，又帶來了代碼發(fā)現(xiàn)和代碼定位的問題.為解決代碼發(fā)現(xiàn)問題，本文提出反饋式二進(jìn)制翻譯框架，將代碼發(fā)現(xiàn)放入程序執(zhí)行過程，在程序執(zhí)行時(shí)進(jìn)行監(jiān)控，利用執(zhí)行反饋情況獲取程序間接轉(zhuǎn)移目標(biāo)地址；為與反饋框架相匹配并高效解決代碼定位問題，本文改進(jìn)了SQEMU地址索引映射表，提出了基于基本塊首地址的二級(jí)地址映射表和映射方法.

2 反饋式靜態(tài)二進(jìn)制翻譯框架FD-SQEMU

靜態(tài)翻譯是將源平臺(tái)的二進(jìn)制可執(zhí)行文件完全翻譯到目標(biāo)機(jī)器上，通常一次翻譯后就可以多次在目標(biāo)平臺(tái)上運(yùn)行，并且因?yàn)槠浞g過程耗費(fèi)的時(shí)間不計(jì)入執(zhí)行時(shí)間，所以靜態(tài)翻譯可以花費(fèi)大量的時(shí)間用于生成代碼的優(yōu)化，而且靜態(tài)翻譯可以利用程序以往執(zhí)行的記錄進(jìn)行優(yōu)化，以獲得更高的效率.

但是，靜態(tài)二進(jìn)制翻譯在翻譯帶有間接轉(zhuǎn)移指令的程序時(shí)，由于無法獲得運(yùn)行時(shí)信息，可能無法獲得間接跳轉(zhuǎn)和間接調(diào)用的目標(biāo)地址，無法準(zhǔn)確定位到目標(biāo)平臺(tái)上該轉(zhuǎn)移地址，進(jìn)而無法正確實(shí)現(xiàn)源二進(jìn)制程序的功能，不能保證程序翻譯的等價(jià)性.逐行翻譯方式，雖然能夠很好地進(jìn)行代碼定位，因?yàn)槊恳恍性创a均對(duì)應(yīng)一個(gè)目的平臺(tái)代碼塊，直接或者間接跳轉(zhuǎn)的任意地址均可以被準(zhǔn)確定位，但是該方法無法進(jìn)行塊內(nèi)優(yōu)化且程序效率較低.而基本塊翻譯方式只記錄了基本塊的首地址，對(duì)于轉(zhuǎn)移目的地址在基本塊中間的間接跳轉(zhuǎn)或者間接調(diào)用指令則無法處理.

為了確定間接跳轉(zhuǎn)和間接調(diào)用的目的地址，本文設(shè)計(jì)并實(shí)現(xiàn)了反饋式靜態(tài)二進(jìn)制翻譯框架.其基本思想是，先翻譯源二進(jìn)制程序，進(jìn)而執(zhí)行、監(jiān)控，在遇到無法確定目標(biāo)地址的間接跳轉(zhuǎn)或者間接調(diào)用時(shí)，終止執(zhí)行并反饋回跳轉(zhuǎn)的目標(biāo)地址；然后將該跳轉(zhuǎn)目標(biāo)地址作為一個(gè)新的基本塊起始地址，重新對(duì)源平臺(tái)二進(jìn)制文件進(jìn)行基本塊劃分，重新翻譯，直至能完整實(shí)現(xiàn)源二進(jìn)制文件的功能，實(shí)現(xiàn)程序等價(jià)性翻譯[20].

本文設(shè)計(jì)的反饋式靜態(tài)二進(jìn)制翻譯框架如圖2所示，主要包括8個(gè)模塊：預(yù)處理模塊、源文件解析器、前端解碼器、TCG分析優(yōu)化器、后端編碼器、目標(biāo)文件生成器、動(dòng)態(tài)執(zhí)行模塊和反饋地址處理模塊.

Fig. 2 Framework of FD-SQEMU圖2 FD-SQEMU框架設(shè)計(jì)

1) 預(yù)處理模塊.分析源平臺(tái)可執(zhí)行文件，獲取源程序的代碼段，對(duì)程序的代碼段進(jìn)行基本塊劃分，生成基本塊信息表Tb，基本塊劃分方式與《編譯與反編譯技術(shù)》這本書中介紹的相同.

2) 源文件解析器.分析源平臺(tái)可執(zhí)行文件，獲取程序入口地址，提取代碼段、數(shù)據(jù)段、只讀數(shù)據(jù)段、初始化段、動(dòng)態(tài)鏈接表、全局符號(hào)表等.代碼段，用于結(jié)合基本塊信息表進(jìn)行靜態(tài)翻譯；數(shù)據(jù)段和只讀數(shù)據(jù)段用于翻譯后程序的執(zhí)行；動(dòng)態(tài)鏈接表和全局符號(hào)表用于對(duì)系統(tǒng)函數(shù)和用戶函數(shù)的定位以及使用.

3) 前端解碼器.以基本塊為單位對(duì)源平臺(tái)指令解碼.FD-SQEMU采用了QEMU前端，保留了QEMU能對(duì)多源平臺(tái)如x86，ARM，MIPS等平臺(tái)的指令解碼功能，并根據(jù)譯碼器分析出的指令生成相對(duì)應(yīng)的TCG指令，在遇到間接轉(zhuǎn)移指令時(shí)，在該間接轉(zhuǎn)移指令前加上異常處理指令.

4) TCG分析優(yōu)化器.對(duì)中間表示無關(guān)語言TCG進(jìn)行平臺(tái)無關(guān)化優(yōu)化，如活性分析、塊內(nèi)寄存器分配、塊內(nèi)代碼優(yōu)化等.

5) 后端編碼器.依據(jù)TCG中間表示生成目標(biāo)平臺(tái)機(jī)器指令.在目標(biāo)代碼層次，根據(jù)目標(biāo)平臺(tái)特點(diǎn)采取可行的優(yōu)化措施，如用戶函數(shù)調(diào)用與返回時(shí)冗余操作的消除、調(diào)用庫(kù)函數(shù)時(shí)寄存器快速傳遞參數(shù)等.

6) 目標(biāo)文件生成器.重新組合從源文件分析器獲得的可執(zhí)行文件的數(shù)據(jù)段、只讀數(shù)據(jù)段和全局符號(hào)表信息，從TCG生成器獲得的代碼段、初始化段對(duì)應(yīng)的TCG中間表示序列，生成TCG對(duì)應(yīng)的目標(biāo)平臺(tái)可執(zhí)行elf文件，需要處理庫(kù)函數(shù)接口、間接跳轉(zhuǎn)和間接調(diào)用指令.

7) 動(dòng)態(tài)執(zhí)行模塊.提供執(zhí)行環(huán)境，保障由目標(biāo)文件生成器生成的目標(biāo)機(jī)器代碼執(zhí)行.若程序完整地正確執(zhí)行，則說明程序翻譯完成；若執(zhí)行遇到間接轉(zhuǎn)移地址找不到的情況，則返回該轉(zhuǎn)移目標(biāo)地址，此處返回的地址是源平臺(tái)可執(zhí)行文件中的跳轉(zhuǎn)目標(biāo)地址.

8) 反饋地址處理模塊.該模塊依據(jù)動(dòng)態(tài)執(zhí)行模塊返回的跳轉(zhuǎn)目標(biāo)地址，對(duì)源平臺(tái)可執(zhí)行文件重新劃分基本塊，并更新基本塊信息表Tb，以供系統(tǒng)重新翻譯.

實(shí)質(zhì)上，該翻譯框架依舊是基于QEMU[21]設(shè)計(jì)的，繼續(xù)沿用了QEMU的前端文件分析和TCG中間表示，并繼承了QEMU的跨平臺(tái)特性[22].另外，在FD-SQEMU中，對(duì)庫(kù)函數(shù)的處理繼續(xù)采用了SQEMU中庫(kù)函數(shù)封裝方法以及庫(kù)函數(shù)本地化調(diào)用方法，以提升程序的運(yùn)行效率.

3 間接轉(zhuǎn)移指令的處理

間接轉(zhuǎn)移指令在靜態(tài)分析時(shí)無法確定該指令跳轉(zhuǎn)的目標(biāo)地址，針對(duì)不同運(yùn)行環(huán)境或者運(yùn)行對(duì)象，其轉(zhuǎn)移目標(biāo)可能不同，本文通過動(dòng)態(tài)執(zhí)行反饋機(jī)制獲取間接轉(zhuǎn)移目標(biāo)地址，進(jìn)而結(jié)合二級(jí)地址映射表來確定目的平臺(tái)上轉(zhuǎn)移目標(biāo)地址.下面對(duì)二級(jí)地址映射表的構(gòu)造和查找過程以及間接轉(zhuǎn)移目標(biāo)地址的獲取進(jìn)行詳述.

3.1 相關(guān)定義與符號(hào)約定

本文定義下述符號(hào)表示翻譯過程中涉及的概念.

Ms：源平臺(tái);

Mt：目的平臺(tái);

Is:源機(jī)器平臺(tái)指令；

Asi:源平臺(tái)間接轉(zhuǎn)移目標(biāo)地址；

Bs：源平臺(tái)二進(jìn)制文件；

Bt：使用FD-SQEMU翻譯源平臺(tái)二進(jìn)制文件Bs到Mt所得的二進(jìn)制文件；

B0,B1,…,Bn,…：源平臺(tái)劃分的各基本塊，B0表示從程序入口開始的第1個(gè)基本塊；

A0，A1,…,An,…：源平臺(tái)劃分的各基本塊的起始地址(指令塊第1條指令的地址)；

LB0,LB1,…,LBn,…：源平臺(tái)指令基本塊對(duì)應(yīng)的目標(biāo)平臺(tái)指令塊；

LA0，LA1,…,LAn,…：源平臺(tái)劃分的各基本塊的起始地址對(duì)應(yīng)的目標(biāo)平臺(tái)指令塊起始地址.

3.2 間接轉(zhuǎn)移處理過程

對(duì)于間接轉(zhuǎn)移來說，通過靜態(tài)分析確定間接轉(zhuǎn)移的目標(biāo)地址是非常難的問題，而且該間接轉(zhuǎn)移指令可能跳轉(zhuǎn)到程序的任何一個(gè)位置，本文采用反饋方式，借助動(dòng)態(tài)執(zhí)行profile信息獲取間接轉(zhuǎn)移目標(biāo)地址，具體獲取過程算法流程如圖3所示：

Fig. 3 Solving process of indirect branch圖3 間接轉(zhuǎn)移處理過程

1) 預(yù)處理模塊對(duì)源平臺(tái)二進(jìn)制文件Bs進(jìn)行基本塊劃分，獲取各基本塊起始和結(jié)束地址信息，存入基本塊信息表Tb，初始基本塊劃分算法如算法1所示.

2) 根據(jù)源平臺(tái)二進(jìn)制文件Bs以及基本塊信息表Tb，結(jié)合靜態(tài)二進(jìn)制翻譯器生成目標(biāo)平臺(tái)二進(jìn)制文件Bt，并在生成Bt的過程中在間接轉(zhuǎn)移指令前添加異常處理反饋指令進(jìn)行監(jiān)控反饋，詳細(xì)算法見3.4節(jié)的算法4.

3) 將生成的目標(biāo)平臺(tái)二進(jìn)制文件Bt，在動(dòng)態(tài)執(zhí)行模塊執(zhí)行，如果程序正常結(jié)束，則說明程序已翻譯完成，可存儲(chǔ)供后續(xù)使用；如程序找不到轉(zhuǎn)移目標(biāo)地址Asi(說明該地址不是已劃分基本塊首地址)，異常結(jié)束，則返回該轉(zhuǎn)移目標(biāo)地址供反饋模塊處理.

4) 反饋處理模塊依據(jù)程序異常結(jié)束拋出的轉(zhuǎn)移目標(biāo)地址Asi，對(duì)源平臺(tái)二進(jìn)制文件Bs重新進(jìn)行基本塊劃分，并更新基本塊信息表Tb；之后，依據(jù)更新后的基本塊信息表Tb，重新對(duì)源平臺(tái)二進(jìn)制文件進(jìn)行翻譯，待再次翻譯完成后重新執(zhí)行；重復(fù)此過程，直至程序能正常執(zhí)行、正常結(jié)束，完成該源程序的翻譯.

算法1. 初始基本塊劃分算法.

功能：對(duì)x86源代碼進(jìn)行初始基本塊劃分；

輸入：x86匯編代碼；

輸出：基本塊信息表Tb.

① 獲取每個(gè)基本塊的入口語句：程序的第1條語句，能由跳轉(zhuǎn)語句或者函數(shù)調(diào)用語句轉(zhuǎn)移到的語句，緊跟在條件轉(zhuǎn)移或者函數(shù)調(diào)用語句后的語句.

② 確定每條入口語句所屬的基本塊：由該入口語句到下一條入口語句、轉(zhuǎn)移語句或者停語句之間的語句序列.

③ 刪除掉未被納入到基本塊中間的語句，并根據(jù)基本塊起止地址信息生成基本塊信息表Tb.

在對(duì)源程序重新進(jìn)行基本塊劃分時(shí)，重點(diǎn)便是更新基本塊信息表Tb，主要是更新該表中基本塊的起始地址和結(jié)束地址.在反饋模塊更新基本塊信息表Tb時(shí)，如發(fā)現(xiàn)某一轉(zhuǎn)移目標(biāo)地址Asi在某一基本塊Bx的中間(該地址大于基本塊起始地址，小于該基本塊結(jié)束地址)，則將該基本塊Bx劃分為2個(gè)基本塊，并以轉(zhuǎn)移目標(biāo)地址Asi為下一基本塊的起始地址，該轉(zhuǎn)移目標(biāo)地址上一條指令的地址為上一基本塊的結(jié)束地址，以圖4 QUICKSORT程序的核心代碼片段為例進(jìn)行說明.

如圖4所示，如在原先劃分的起始地址Ax為0x4007f5、結(jié)束地址是0x400899的基本塊Bx中有一間接轉(zhuǎn)移目標(biāo)地址Asin為0x40080d，則將原來的基本塊拆分為2個(gè)基本塊，這2個(gè)基本塊的起止地址分別是0x4007f5～0x400809，0x40080d～0x400899，并據(jù)此更新基本塊信息表Tb，為源平臺(tái)二進(jìn)制程序后續(xù)的靜態(tài)翻譯提供基本塊劃分信息.

針對(duì)間接轉(zhuǎn)移目標(biāo)地址的確定，本系統(tǒng)將其作為基本塊首地址進(jìn)行處理，并存入二級(jí)地址映射表,以方便轉(zhuǎn)移地址的快速查找及定位.

3.3 地映射表的構(gòu)造

在確定源平臺(tái)間接轉(zhuǎn)移目標(biāo)地址后，其就成為一基本塊的起始地址，為了保證程序的邏輯關(guān)系以及正確翻譯，在翻譯時(shí)必須保證各基本塊首地址映射的正確性.

為了解決Ms指令塊地址到Mt指令塊地址的映射問題，需要保存所有Ms基本塊對(duì)應(yīng)的Mt基本塊的地址，并采用合適的方式來保證映射過程的高效性，以提高程序的效率及質(zhì)量.

地址映射表的構(gòu)造是在翻譯階段完成的.首先使用源文件解析器，分析源可執(zhí)行文件的各個(gè)段數(shù)據(jù)，提取出包含指令的代碼段、初始化段、附加段信息，然后使用前端解碼器按照地址從小到大(即A0，A1,…,An，…)的順序逐塊翻譯Ms指令到TCG中間表示，再借助后端編碼器翻譯為Mt指令.在生成目標(biāo)代碼的過程中，如在翻譯以An為起始地址的一個(gè)指令塊Bn時(shí)，在生成目標(biāo)代碼首部加上標(biāo)簽LAn，并且使用數(shù)組Address保存此標(biāo)簽值，此標(biāo)簽值即目標(biāo)地址信息.另外，使用An相對(duì)A0的偏移量作為索引，能夠快速定位目的地址.

圖5給出了在翻譯中二級(jí)地址映射表的構(gòu)造過程及源平臺(tái)和目標(biāo)平臺(tái)指令塊地址映射信息.

圖5詳細(xì)給出了存儲(chǔ)源平臺(tái)代碼塊首地址到目的平臺(tái)代碼塊首地址信息的二級(jí)地址映射表的構(gòu)造過程，其中二級(jí)地址映射表的具體生成算法如算法2所示.在算法2中，使用數(shù)組Address存儲(chǔ)源平臺(tái)Ms指令塊翻譯為Mt平臺(tái)指令塊的首地址，使用數(shù)組Index存儲(chǔ)與Ms指令塊對(duì)應(yīng)的Mt指令塊在數(shù)組Address中的索引位置.

Fig. 5 Construction of two-level address mapping table圖5 二級(jí)地址映射表的構(gòu)造過程

算法2. 地址映射表的構(gòu)造算法.

功能：構(gòu)造源程序地址到目標(biāo)平臺(tái)程序地址的映射表；

輸入：包含基本塊Bn起始地址An和結(jié)束地址En的基本塊信息表Tb；

輸出：地址數(shù)組Address和索引數(shù)組Index.

① FOR每一個(gè){A0,A1,…,An,…} 中的Ax

② 分析起始地址為Ax的基本塊Bx中的操作碼和操作數(shù)，并將分析結(jié)果翻譯成TCG中間代碼；

③ 將TCG中間代碼翻譯至目標(biāo)機(jī)器代碼，并使用LAx記錄目標(biāo)機(jī)器代碼塊的起始地址，令A(yù)ddress[x]=LAx,Index[Ax-A0]=x;

④ END FOR

在構(gòu)造二級(jí)地址映射表后，本文設(shè)計(jì)了間接轉(zhuǎn)移分支指令目的地址的查找算法，如算法3所示.

算法3. 間接轉(zhuǎn)移分支指令目的地址查找算法.

功能：獲得間接轉(zhuǎn)移分支指令的目的地址；

輸入：Ms源平臺(tái)程序起始地址和Mt目標(biāo)平臺(tái)上間接轉(zhuǎn)移指令的目的地址；

輸出：目標(biāo)平臺(tái)Mt上間接轉(zhuǎn)移目標(biāo)地址.

① 獲取Ms源平臺(tái)程序起始地址Ax和源程序間接轉(zhuǎn)移目標(biāo)地址A0；

② 計(jì)算Ax相對(duì)于A0的偏移地址：Ax-A0；

③ 返回Mt目標(biāo)平臺(tái)上間接轉(zhuǎn)移目標(biāo)地址：

Address[Index[Ax-A0]].

如算法3所示，結(jié)合二級(jí)地址映射，采用算法3，利用源平臺(tái)程序基本塊起始地址信息，僅需3條指令即可定位到間接轉(zhuǎn)移目標(biāo)地址.

下面舉例說明該二級(jí)地址映射表構(gòu)造及查找算法的執(zhí)行效果.當(dāng)Ms為x86平臺(tái)、Mt為某國(guó)產(chǎn)平臺(tái)時(shí)，基本塊B0的起始地址A0=0x400530，前3個(gè)指令塊的第1條指令分別為xor，pop，mov，對(duì)應(yīng)的TCG中間表示代碼塊和生成的申威國(guó)產(chǎn)平臺(tái)指令塊如圖6所示.

Fig. 6 Example of translating x86 ISA to national ISA圖6 x86指令塊翻譯為某類國(guó)產(chǎn)平臺(tái)的指令舉例

在目標(biāo)平臺(tái)二進(jìn)制文件運(yùn)行遇到間接轉(zhuǎn)移指令如call *%rax時(shí)，以間接轉(zhuǎn)移指令目標(biāo)地址rax為0x4005ce為例,使用間接轉(zhuǎn)移分支指令目的地址查找算法僅使用3條指令即可獲得標(biāo)簽L_0x4005ce的值，然后轉(zhuǎn)移到該標(biāo)簽的位置.具體定位間接跳轉(zhuǎn)過程為：首先依據(jù)源平臺(tái)間接轉(zhuǎn)移地址0x4005ce，訪問Index[0x4005ce-0x400530]即Index[158]，獲得以0x4005ce為起始地址的代碼塊對(duì)應(yīng)的目的平臺(tái)代碼塊起始地址L_0x4005ce在數(shù)組Address中的位置1；繼而訪問Address[1]獲得L_0x4005ce的值，即定位到間接轉(zhuǎn)移分支目的地址.

從算法2可以看出，Address保存了所有Ms指令塊對(duì)應(yīng)的目標(biāo)代碼塊地址，Index保存了該所有Ms指令塊在Address中的索引位置.如此設(shè)計(jì)，一是思路簡(jiǎn)單明了、利于實(shí)現(xiàn)，二是查找目標(biāo)平臺(tái)間接轉(zhuǎn)移目標(biāo)地址效率較高，以地址索引映射表查找方法、以最小的查詢代價(jià)，解決了間接跳轉(zhuǎn)和間接調(diào)用的代碼發(fā)現(xiàn)問題.

3.4 間接轉(zhuǎn)移目標(biāo)地址的反饋

實(shí)際上，在對(duì)源平臺(tái)二進(jìn)制文件進(jìn)行基本塊劃分后，經(jīng)過翻譯對(duì)于大部分間接調(diào)用地址基本都能夠在二級(jí)地址映射表中查詢得到，這是因?yàn)殚g接調(diào)用一般都是調(diào)用的子函數(shù)，而子函數(shù)的入口地址已經(jīng)被處理為某一基本塊的起始地址，并且該地址已經(jīng)存儲(chǔ)在二級(jí)地址映射表中，在動(dòng)態(tài)執(zhí)行時(shí)可以查詢得到；而對(duì)于部分間接跳轉(zhuǎn)指令，因?yàn)樘D(zhuǎn)指令地址的不確定性，其可能跳轉(zhuǎn)到程序的任何位置，比如原先劃分的基本塊中間某地址，此時(shí)該目標(biāo)地址的確定是重中之重，這也是反饋機(jī)制存在的必要性.本文通過借助QEMU的Helper機(jī)制在翻譯源平臺(tái)可執(zhí)行程序時(shí)添加異常處理反饋代碼，采用監(jiān)控程序執(zhí)行的方式獲取間接轉(zhuǎn)移目標(biāo)地址，該間接轉(zhuǎn)移地址反饋算法如算法4所示：

算法4. 間接轉(zhuǎn)移地址反饋算法.

輸入：Ms源平臺(tái)上指令I(lǐng)s,如callq *%rax和jmpq *0x200c04(%rip)指令；

輸出：Ms源平臺(tái)上不是塊首地址的間接轉(zhuǎn)移目標(biāo)地址.

① 分析Ms源平臺(tái)上間接轉(zhuǎn)移指令I(lǐng)s，獲取操作碼opcodes和操作數(shù)oprands.

② IFIs是間接轉(zhuǎn)移指令

③ IFIndex[oprands-A0]≤0

④ 將該操作碼oprands寫入間接轉(zhuǎn)移地址存儲(chǔ)文件IndirectAdd；

⑤ 程序終止；

⑥ END IF

⑦ ELSE

⑧ 將源平臺(tái)指令I(lǐng)s翻譯成TCG中間表示；

⑨ 將TCG中間表示翻譯成Mt目標(biāo)平臺(tái)本地代碼；

⑩ END IF

下面舉例說明算法4的工作原理，依舊以圖4中的間接調(diào)用指令callq *%rax為例，在對(duì)這條指令進(jìn)行翻譯時(shí)，根據(jù)如算法4所示的間接轉(zhuǎn)移地址反饋過程，在實(shí)際將該指令翻譯成目標(biāo)平臺(tái)指令前，首先檢查該間接轉(zhuǎn)移的源平臺(tái)目標(biāo)地址(rax寄存器中的值0x4005ce)是否已經(jīng)在二級(jí)地址映射表中，根據(jù)二級(jí)地址映射的構(gòu)造方法，此時(shí)Index[0x4005ce-A0]>0，則Address[Index[0x4005ce-A0]]=L_0x4005ce即為callq *%rax間接調(diào)用目標(biāo)平臺(tái)的跳轉(zhuǎn)地址，此時(shí)使用翻譯器正常對(duì)該指令翻譯即可.

以間接跳轉(zhuǎn)指令jmpq *0x200c04(%rip)為例，若Address[Index[0x200c04(%rip)-A0]]==0，則說明該跳轉(zhuǎn)目標(biāo)地址未存儲(chǔ)在數(shù)組Address中，此時(shí)即跳轉(zhuǎn)目標(biāo)地址未定，需在jmpq *0x200c04(%rip)指令執(zhí)行前將0x200c04(%rip)中的值通過文件進(jìn)行反饋，并終止程序的執(zhí)行，否則可能會(huì)造成不可預(yù)知的異常終止情況；待將該間接跳轉(zhuǎn)的源目標(biāo)平臺(tái)轉(zhuǎn)移地址確定后，即可更新基本塊信息表Tb，并在翻譯時(shí)將該間接轉(zhuǎn)移的源平臺(tái)目標(biāo)地址和目標(biāo)平臺(tái)地址存入數(shù)組Address，如此即可在程序執(zhí)行時(shí)準(zhǔn)確定位該間接轉(zhuǎn)移的目標(biāo)地址.

4 實(shí)驗(yàn)和結(jié)果

下面對(duì)FD-SQEMU進(jìn)行測(cè)試，測(cè)試的結(jié)果分別與QEMU和SQEMU進(jìn)行比較.測(cè)試內(nèi)容主要包括3個(gè)方面:1)正確性測(cè)試;2)性能測(cè)試;3)反饋次數(shù)測(cè)試.考慮到程序執(zhí)行的局部性原理，性能測(cè)試中又分為熱代碼測(cè)試和整體性能測(cè)試2個(gè)方面.

熱代碼測(cè)試主要針對(duì)循環(huán)體和遞歸函數(shù)，對(duì)循環(huán)熱代碼的測(cè)試主要依托NBENCH測(cè)試集進(jìn)行，對(duì)遞歸熱代碼的測(cè)試主要通過FIBONACCI,N-QUEEN,QUICKSORT,MERGESORT進(jìn)行測(cè)試；整體性能測(cè)試主要通過選取SPEC2006測(cè)試集中的部分程序進(jìn)行測(cè)試；與此同時(shí)，在各個(gè)對(duì)象的測(cè)試中，記錄每個(gè)測(cè)試程序含有的所有及需要反饋處理的間接調(diào)用和間接跳轉(zhuǎn)個(gè)數(shù).

令TFD-SQEMU,TQEMU,TSQEMU分別表示FD -SQEMU,QEMU,SQEMU執(zhí)行翻譯后可執(zhí)行程序的執(zhí)行時(shí)間，定義速度比：

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

Ms為x86體系架構(gòu)的機(jī)器，Mt為國(guó)產(chǎn)某處理器，主頻1.4 GHz，內(nèi)存4 GB，操作系統(tǒng)為Fedora，內(nèi)核版本3.8.0,編譯器為gcc，版本4.5.3.

QEMU與FD-SQEMU運(yùn)行在Mt機(jī)器上.測(cè)試用例是NBENCH版本2.2.3，手動(dòng)實(shí)現(xiàn)的主流遞歸算法和SPEC2006測(cè)試集[23].

4.2 正確性測(cè)試

針對(duì)FD-SQEMU的正確性測(cè)試主要分為2個(gè)部分:1)指令翻譯測(cè)試;2)實(shí)際程序翻譯測(cè)試.

指令翻譯測(cè)試借助QEMU自帶的test-i386測(cè)試集，重點(diǎn)對(duì)x86架構(gòu)用戶態(tài)的指令進(jìn)行了測(cè)試.依據(jù)x86指令分類情況，具體的測(cè)試結(jié)果如表1所示:

Table 1 Correctness Test of Instruction Translation 表1 指令翻譯的正確性測(cè)試

在保證了單條指令翻譯的正確性后，對(duì)實(shí)際程序翻譯進(jìn)行了正確性測(cè)試.具體測(cè)試過程如下：首先，在x86平臺(tái)上編譯SPEC CPU2006和NBENCH測(cè)試集等測(cè)試程序并運(yùn)行記錄結(jié)果；然后，在目標(biāo)平臺(tái)上運(yùn)行翻譯后的可執(zhí)行程序，并與x86上運(yùn)行結(jié)果相比對(duì).部分程序的測(cè)試結(jié)果如表2所示：

Table 2 Correctness Test of Program表2 實(shí)際程序的正確性測(cè)試

Notes: “√” mean that the test cases have passed the correctness verification.

表2的實(shí)驗(yàn)結(jié)果表明，翻譯后的目標(biāo)程序執(zhí)行結(jié)果與源x86平臺(tái)上程序執(zhí)行結(jié)果相同，驗(yàn)證了本文提出的翻譯框架和算法能夠進(jìn)行正確翻譯，做到了程序翻譯的功能等價(jià).

4.3 循環(huán)熱代碼性能測(cè)試

NBENCH測(cè)試集的主要功能是通過計(jì)算一定時(shí)間內(nèi)(一般是5 s)單項(xiàng)測(cè)試代碼塊的循環(huán)迭代次數(shù)來評(píng)價(jià)系統(tǒng)性能，其中每一個(gè)測(cè)試塊都是典型的熱代碼，具體的NBENCH測(cè)試集各部分功能如表3所示:

Table 3 NBENCH Tasks 表3 NBENCH測(cè)試任務(wù)

為了展示FD-SQEMU處理熱代碼的能力，我們分別用FD-SQEMU,SQEEMU和QEMU翻譯系統(tǒng)對(duì)NBENCH測(cè)試集進(jìn)行測(cè)試，并將測(cè)試結(jié)果進(jìn)行對(duì)比.針對(duì)NBENCH測(cè)試集，F(xiàn)S-QEMU和SQEMU相對(duì)于QEMU的性能提升情況如圖7所示:

Fig. 7 Speedup ratio on NBENCH圖7 FD-SQEMU，SQEMU在NBENCH測(cè)試集上的加速比

如圖7所示，對(duì)于不同的測(cè)試項(xiàng)目，SQEMU和QEMU展示了各自的性能優(yōu)勢(shì)；而FD-QEMU保持了SQEMU和QEMU兩個(gè)的性能優(yōu)勢(shì)，并有一定程度上的性能提升.對(duì)于STRING_SORT功能測(cè)試，因?yàn)樽址僮黝l繁使用strcmp,strncmp等字符串相關(guān)庫(kù)函數(shù)，F(xiàn)D-SQEMU和SQEMU分別獲得42.57倍和39.25倍的加速比；類似地，因?yàn)镕OURIER,IDEA,FP EMULATION功能測(cè)試使用了pow,sin,cos,memmove等庫(kù)函數(shù)，F(xiàn)D-SQEMU和SQMEU獲得相應(yīng)的加速比，并且針對(duì)這些功能的測(cè)試，F(xiàn)D-SQEMU相對(duì)于SQEMU有12%左右的加速比，這是因?yàn)镕D-SQEMU在繼續(xù)沿用SQEMU庫(kù)函數(shù)本地化的基礎(chǔ)上，采用了基本塊的翻譯方式，在翻譯時(shí)進(jìn)行了更多的優(yōu)化，提高了生成代碼的質(zhì)量；對(duì)于NUEURAL NET和LU DECOMPOSITION功能測(cè)試，SQEMU運(yùn)行反而比QEMU要慢，但此時(shí)FD-SQEMU相比于SQEMU有較高的加速，最高加速可達(dá)到36%，因?yàn)镾QEMU在單條翻譯NEURAL NET和LU DECOMPOSITION時(shí)缺少上下文關(guān)系，并引入了較多的冗余指令，而FD-SQEMU采用基本塊翻譯，一定程度上保留了源可執(zhí)行文件的上下文關(guān)系，并在翻譯中使用了少量的塊內(nèi)優(yōu)化方法，所以對(duì)于NUEURAL NET和LU DECOMPOSITION功能測(cè)試，F(xiàn)D-SQEMU相比于QEMU有少量的加速，相對(duì)于SQEMU的性能提升較為明顯.對(duì)于NBENCH測(cè)試集，F(xiàn)D-SQEMU相對(duì)于QEMU的平均加速比為6.913，相對(duì)于SQEMU的平均加速比為1.16.

從NBENCH的測(cè)試結(jié)果看，F(xiàn)D-SQEMU繼承了SQEMU的優(yōu)點(diǎn)，并有效去除了SQEMU逐行翻譯引入的部分冗余指令，F(xiàn)D-SQEMU相比于SQEMU的平均性能提升了16.14%.

4.4 遞歸熱代碼性能測(cè)試

遞歸算法是會(huì)反復(fù)執(zhí)行的熱代碼，遞歸中對(duì)單一或某些函數(shù)的反復(fù)調(diào)用會(huì)產(chǎn)生大量的函數(shù)調(diào)用和返回指令，能否高效地處理函數(shù)調(diào)用，直接影響目標(biāo)程序執(zhí)行的效率，本文對(duì)典型的遞歸算法進(jìn)行了測(cè)試，并給出了FD-SQEMU和SQEMU相比于QEMU的加速比，具體情況如圖8所示:

Fig. 8 Speedup ratio on recursive algorithms圖8 FD-SQEMU,SQEMU對(duì)QEMU在遞歸算法的加速比

如圖8所示，F(xiàn)D-SQEMU繼承了SQEMU對(duì)遞歸熱代碼的處理能力，并在性能上有一定的提升，平均性能提升了17.25%.這是因?yàn)镕D-SQEMU繼承了SQEMU的本地棧作為影子棧[24]實(shí)現(xiàn)用戶自定義函數(shù)本地化調(diào)用的思想，有效減少了函數(shù)調(diào)用和返回時(shí)代碼切換的消耗，保證了相對(duì)QEMU的性能提升；在此基礎(chǔ)上FD-SQEMU使用基本塊方式翻譯，一是有效去除了SQEMU逐行翻譯中的冗余代碼并對(duì)代碼進(jìn)行了一定程度的塊內(nèi)優(yōu)化，在翻譯代碼膨脹率上FD-SQEMU整體比SQEMU降低了約20%.

4.5 整體性能測(cè)試

在對(duì)FD-SQEMU整體性能進(jìn)行測(cè)試時(shí)，使用的是SPEC2006測(cè)試集.SPEC2006測(cè)試集中的程序基本都是實(shí)際應(yīng)用中常用到的程序，該測(cè)試集的執(zhí)行結(jié)果能夠反映出一個(gè)翻譯系統(tǒng)的整體性能.圖9展示了對(duì)SPEC2006中部分應(yīng)用進(jìn)行測(cè)試時(shí)FD-SQEMU和SQEMU相對(duì)QEMU的性能提升情況.

Fig. 9 Speedup ratio on part of SPEC2006圖9 FD-SQEMU,SQEMU在SPEC2006測(cè)試集上的加速比

如圖9所示，對(duì)于BZIP2，MILC程序，F(xiàn)D-SQEMU和SQEMU相比于QEMU獲得了1倍多的加速，這是因?yàn)檫@些實(shí)際應(yīng)用中大量代碼迭代次數(shù)少，函數(shù)重復(fù)調(diào)用較少，F(xiàn)D-SQEMU和SQEMU在目標(biāo)代碼執(zhí)行階段不需要再翻譯和代碼維護(hù)，消除了QEMU的代碼塊切換的時(shí)間，提高了目標(biāo)平臺(tái)代碼的執(zhí)行效率；在SPEC 2006測(cè)試集中SPECRAND和MCF程序獲得了較高的加速比，對(duì)于SPECRAND程序，F(xiàn)D-SQEMU相比于QEMU的加速比高達(dá)6.91，這是因?yàn)镾PECRAND程序反復(fù)使用到了產(chǎn)生隨機(jī)數(shù)的庫(kù)函數(shù)，對(duì)于MCF程序同樣也是如此.

與SQEMU相比，對(duì)于SPEC2006中調(diào)用庫(kù)函數(shù)較少的程序進(jìn)行測(cè)試，F(xiàn)D-SQEMU比SQEMU整體性能提升了19.1%；對(duì)于反復(fù)調(diào)用庫(kù)函數(shù)的SPEC2006程序進(jìn)行測(cè)試，F(xiàn)D-SQEMU對(duì)SQEMU性能僅提升了約15%，這是因?yàn)镕D-SQEMU相比于SQEMU在對(duì)庫(kù)函數(shù)處理上并沒有較大的改進(jìn).總體上，對(duì)部分SPEC2006程序的測(cè)試，F(xiàn)D-SQEMU相比于SQEMU整體性能平均提升了16.75%.

4.6 反饋情況測(cè)試

作為反饋式靜態(tài)二進(jìn)制翻譯器FD-SQEMU，在翻譯程序時(shí)所需反饋次數(shù)也是其性能的重要衡量標(biāo)準(zhǔn).

在測(cè)試時(shí)，針對(duì)可能存在的因參數(shù)不同執(zhí)行路徑不同的情況，本文做了多種參數(shù)的測(cè)試，并將各測(cè)試實(shí)例代碼段中所有間接跳轉(zhuǎn)和間接調(diào)用以及需要通過反饋處理的間接跳轉(zhuǎn)和間接調(diào)用情況進(jìn)行統(tǒng)計(jì)，如表4所示.

如表4中所示，F(xiàn)D-SQEMU對(duì)各測(cè)試項(xiàng)的反饋運(yùn)行次數(shù)情況并不相同，MCF,FIBONACCI,QUICKSORT,MERGESORT,N-QUEEN,SPECRAND中反饋次數(shù)為0，這是因?yàn)樵谶@些應(yīng)用程序中的間接跳轉(zhuǎn)和間接調(diào)用目標(biāo)地址都為某一函數(shù)或者基本塊的首地址，不存在跳轉(zhuǎn)到某一基本塊中間的情況，此時(shí)在數(shù)組Address中可以查詢得到該跳轉(zhuǎn)目標(biāo)地址在目標(biāo)平臺(tái)上的指令地址，不需要反饋執(zhí)行；而對(duì)于NBENCH測(cè)試集的BZIP2和MILC，因?yàn)檫@些程序中部分間接跳轉(zhuǎn)和間接調(diào)用目標(biāo)地址在原先劃分的基本塊中間，所以需要通過反饋來獲得該地址并對(duì)原先基本塊重新劃分，以方便將該地址存入二級(jí)地址映射表中進(jìn)行間接轉(zhuǎn)移目標(biāo)定位.實(shí)際上在NBENCH,BZIP2,MILC中雖然有較多的間接跳轉(zhuǎn)和間接調(diào)用指令，但是需要進(jìn)行反饋處理的并不多，其中大部分間接轉(zhuǎn)移目標(biāo)地址為某一子程序的起始地址或者某一基本塊的起始地址.實(shí)際完成源程序翻譯所需的反饋次數(shù)與該程序中間接轉(zhuǎn)移目標(biāo)地址在之前劃分的基本塊中間的轉(zhuǎn)移指令數(shù)成線性關(guān)系.最初的基本塊信息表Tb的生成，直接影響著程序需要執(zhí)行、反饋、重翻譯的次數(shù).

Table 4 Translation Feedback Situation of FD-SQEMU表4 FD-SQEMU翻譯反饋情況

5 總 結(jié)

本文在分析現(xiàn)有靜態(tài)二進(jìn)制翻譯中解決間接轉(zhuǎn)移問題方法的基礎(chǔ)上，針對(duì)現(xiàn)有間接轉(zhuǎn)移問題處理方法中線性遍歷翻譯方式代碼優(yōu)化較少、冗余代碼較多的缺陷，對(duì)基于動(dòng)態(tài)QEMU的靜態(tài)二進(jìn)制翻譯器SQEMU進(jìn)行了改進(jìn)，提出了基于基本塊翻譯的反饋式靜態(tài)二進(jìn)制翻譯框架FD-SQEMU，并結(jié)合二級(jí)地址映射表實(shí)現(xiàn)了間接轉(zhuǎn)移目標(biāo)地址的快速映射.首先，F(xiàn)D-SQEMU在繼承SQEMU庫(kù)函數(shù)本地化的基礎(chǔ)上，引入基本塊翻譯方式，解決了SQEMU逐行翻譯無法兼顧程序上下文進(jìn)行塊內(nèi)優(yōu)化以及引入大量冗余代碼的缺陷；接著，采用反饋機(jī)制，并結(jié)合新的二級(jí)地址映射表及查找算法，以較高效率解決了靜態(tài)二進(jìn)制翻譯中間接跳轉(zhuǎn)和間接調(diào)用中的代碼發(fā)現(xiàn)及定位的問題;最后，通過與SQEMU和QEMU的性能對(duì)比實(shí)驗(yàn)，驗(yàn)證了反饋式靜態(tài)二進(jìn)制翻譯器FD-SQEMU的正確性和有效性.

但在反饋式靜態(tài)二進(jìn)制翻譯中，針對(duì)源二進(jìn)制程序的最初基本塊信息表Tb的建立直接關(guān)系到反饋次數(shù)，如何根據(jù)源二進(jìn)制程序特性建立更合適的起始基本塊信息表以減少反饋次數(shù)還需要進(jìn)一步分析；另外，在該翻譯過程中，采用的代碼優(yōu)化較少，還可利用現(xiàn)有的代碼優(yōu)化方法進(jìn)一步對(duì)翻譯代碼進(jìn)行優(yōu)化，以生成更高質(zhì)量的目標(biāo)代碼，提高目標(biāo)代碼的執(zhí)行效率.