譚 捷 龐建民 單 征 岳 峰 盧帥兵 戴 濤

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室 鄭州 450002)

二進(jìn)制翻譯中冗余指令優(yōu)化算法

譚 捷 龐建民 單 征 岳 峰 盧帥兵 戴 濤

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室 鄭州 450002)

(jessie_tanjie@hotmail.com)

二進(jìn)制翻譯是實(shí)現(xiàn)軟件移植的主要方法.動(dòng)態(tài)二進(jìn)制翻譯受動(dòng)態(tài)執(zhí)行限制而不能深度優(yōu)化導(dǎo)致效率較低而傳統(tǒng)的靜態(tài)二進(jìn)制翻譯難以處理間接分支，且現(xiàn)有的優(yōu)化方法大部分集中在中間代碼層，對(duì)目標(biāo)碼中存在的大量冗余指令較少關(guān)注.針對(duì)這一現(xiàn)狀，提出一種靜態(tài)二進(jìn)制翻譯框架SQEMU，基于該框架提出了一種對(duì)目標(biāo)碼冗余指令進(jìn)行刪除的優(yōu)化算法.該算法通過(guò)分析目標(biāo)碼生成指令特定數(shù)據(jù)依賴圖(instruction-specific data dependence graph, IDDG)，再利用該圖將活性分析和窺孔優(yōu)化的2種理論相結(jié)合，有效刪除目標(biāo)碼中的冗余指令.實(shí)驗(yàn)結(jié)果表明，利用該算法對(duì)目標(biāo)碼優(yōu)化后，其執(zhí)行效率得到顯著提升，最大提升可達(dá)42%，整體性能測(cè)試表明，優(yōu)化后nbench測(cè)試集翻譯效率提高約20%，SPEC CINT2006測(cè)試集翻譯效率提高約17%.

二進(jìn)制翻譯；冗余指令；活性分析；窺孔優(yōu)化；SQEMU框架

二進(jìn)制翻譯技術(shù)是實(shí)現(xiàn)軟件移植的主要方法，現(xiàn)已廣泛應(yīng)用于遺產(chǎn)代碼移植、系統(tǒng)安全防護(hù)等國(guó)內(nèi)外諸多領(lǐng)域，是解決不同體系結(jié)構(gòu)處理器之間軟件移植的主要途徑，如開(kāi)源的跨平臺(tái)動(dòng)態(tài)二進(jìn)制翻譯器QEMU[1]，已被移植到多種處理器平臺(tái)，其中包括國(guó)產(chǎn)龍芯平臺(tái)[2].

二進(jìn)制翻譯可按翻譯的時(shí)機(jī)不同分為動(dòng)態(tài)二進(jìn)制翻譯和靜態(tài)二進(jìn)制翻譯.動(dòng)態(tài)二進(jìn)制翻譯是一種即時(shí)翻譯技術(shù)，它是在目標(biāo)程序運(yùn)行時(shí)動(dòng)態(tài)生成可執(zhí)行代碼，代碼優(yōu)化占用程序執(zhí)行時(shí)間，其翻譯過(guò)程受動(dòng)態(tài)執(zhí)行的限制而不能進(jìn)行深度細(xì)致優(yōu)化[3].另外，動(dòng)態(tài)二進(jìn)制翻譯需要在執(zhí)行所生成目標(biāo)代碼的同時(shí)，完成加載分析、運(yùn)行環(huán)境設(shè)置、實(shí)時(shí)翻譯、代碼緩存管理、代碼塊切換等工作.一些技術(shù)如熱路徑優(yōu)化、寄存器映射、多線程優(yōu)化等提高了動(dòng)態(tài)二進(jìn)制翻譯的效率，但仍未解決動(dòng)態(tài)二進(jìn)制翻譯效率偏低的問(wèn)題.靜態(tài)二進(jìn)制翻譯在不運(yùn)行目標(biāo)程序的情況下，靜態(tài)分析可執(zhí)行程序，提取指令進(jìn)行翻譯，能采用復(fù)雜的代碼分析和優(yōu)化算法，它有充足的時(shí)間進(jìn)行完整細(xì)致的優(yōu)化，生成代碼質(zhì)量較高，運(yùn)行效率較高.靜態(tài)二進(jìn)制翻譯還可以利用程序以往執(zhí)行的記錄進(jìn)行優(yōu)化，即profiling，獲取更好的優(yōu)化結(jié)果.

QEMU是一個(gè)二進(jìn)制動(dòng)態(tài)翻譯器[1]，針對(duì)中間代碼實(shí)施簡(jiǎn)單的活性分析以得到優(yōu)化后的代碼.但由于其優(yōu)化算法本身占用運(yùn)行時(shí)間并且提高生成代碼的質(zhì)量并不能減少基本塊切換和生成代碼維護(hù)開(kāi)銷，優(yōu)化效果并不理想.為了提高翻譯后代碼段的質(zhì)量，在二進(jìn)制翻譯中針對(duì)編譯器設(shè)計(jì)采取了很多復(fù)雜的優(yōu)化，將LLVM和QEMU結(jié)合的HQEMU[4]就是典型的例子，HQEMU在生成的中間代碼層上針對(duì)改進(jìn)的LLVM編譯器進(jìn)行優(yōu)化，比如寄存器優(yōu)化和標(biāo)量運(yùn)算矢量化等.與QEMU相比，這種優(yōu)化導(dǎo)致了整體翻譯效率的下降.為了降低優(yōu)化開(kāi)銷，HQEMU拋棄了在多核系統(tǒng)中的其他硬件線程或內(nèi)核的優(yōu)化，這又導(dǎo)致系統(tǒng)吞吐量明顯降低.由于優(yōu)化算法本身的開(kāi)銷，QEMU在TCG中間表示層未能實(shí)現(xiàn)有效的優(yōu)化.一些基于LLVM的動(dòng)態(tài)二進(jìn)制翻譯器[5-9]雖然能夠生成較高質(zhì)量代碼，但是翻譯和塊切換開(kāi)銷在運(yùn)行時(shí)仍然存在.現(xiàn)有靜態(tài)二進(jìn)制翻譯難以處理間接分支，而動(dòng)態(tài)二進(jìn)制翻譯效率低，為處理以上問(wèn)題，本文采用基于QEMU的靜態(tài)二進(jìn)制翻譯框架Static-QEMU(SQEMU)[10]，SQEMU能夠分離翻譯時(shí)間、代碼優(yōu)化時(shí)間與目標(biāo)程序執(zhí)行時(shí)間，并且代碼優(yōu)化的時(shí)間不受運(yùn)行時(shí)的限制，能夠采用不同層次的優(yōu)化算法，使得SQEMU能夠生成更高質(zhì)量的目標(biāo)代碼.

因此，本文以SQEMU作為靜態(tài)二進(jìn)制翻譯平臺(tái)，對(duì)生成的目標(biāo)代碼中常規(guī)冗余指令和冗余存取LOADSTORE指令進(jìn)行優(yōu)化，通過(guò)分析目標(biāo)碼生成指令特定數(shù)據(jù)依賴圖(instruction-specific data dependence graph, IDDG)，再利用該圖將活性分析和窺孔優(yōu)化的2種理論相結(jié)合，提出基于IDDG的冗余指令刪除優(yōu)化算法，有效刪除目標(biāo)碼中冗余指令，以達(dá)到提高目標(biāo)代碼執(zhí)行效率的目的.

本文的主要工作有4點(diǎn)：

1) 針對(duì)動(dòng)態(tài)二進(jìn)制翻譯器QEMU因其翻譯過(guò)程受動(dòng)態(tài)執(zhí)行的限制而不能進(jìn)行深度細(xì)致優(yōu)化等缺點(diǎn)，以及現(xiàn)有靜態(tài)二進(jìn)制翻譯器難以處理間接分支的現(xiàn)狀，提出一種基于QEMU的靜態(tài)二進(jìn)制翻譯框架SQEMU，SQEMU能夠分離翻譯時(shí)間、代碼優(yōu)化時(shí)間與目標(biāo)程序執(zhí)行時(shí)間，并且代碼優(yōu)化的時(shí)間不受運(yùn)行時(shí)的限制，能夠采用不同層次的優(yōu)化算法，使得SQEMU生成的目標(biāo)代碼質(zhì)量更高.

2) 將SQEMU后端生成的目標(biāo)代碼作為輸入?yún)?shù)，利用指令寄存器之間存在的數(shù)據(jù)依賴關(guān)系，生成指令特定數(shù)據(jù)依賴圖(IDDG)，將圖理論靈活運(yùn)用到冗余代碼優(yōu)化過(guò)程中，拓展了處理冗余代碼的手段.

3) 利用IDDG分別對(duì)常規(guī)冗余代碼進(jìn)行活性分析、對(duì)冗余訪存指令進(jìn)行窺孔優(yōu)化，將2種理論相結(jié)合，雙重優(yōu)化的思路避免了因方法單一而導(dǎo)致優(yōu)化不夠完備的弊端.實(shí)驗(yàn)結(jié)果表明，以SPEC CPU2006和nbench測(cè)試集為例，該算法對(duì)代碼執(zhí)行效率提升顯著，最大提升可達(dá)42%，整體性能測(cè)試表明優(yōu)化后nbench測(cè)試集翻譯效率平均提高約20%，SPEC CINT2006平均提高約17%.

4) 本文提出的算法雖然是針對(duì)基于QEMU的靜態(tài)二進(jìn)制翻譯框架SQEMU后端目標(biāo)碼實(shí)現(xiàn)的，但該算法具有相當(dāng)強(qiáng)的通用性，不限于目標(biāo)平臺(tái)和指令形式，對(duì)降低二進(jìn)制翻譯后的代碼膨脹率有重要意義.

1 基于QEMU的靜態(tài)翻譯框架——SQEMU

QEMU系統(tǒng)是目前較為先進(jìn)的可實(shí)現(xiàn)多種異構(gòu)平臺(tái)映射的動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)，具有支持平臺(tái)多樣、翻譯效率相對(duì)較高、開(kāi)源易移植等優(yōu)點(diǎn)[11].QEMU為實(shí)現(xiàn)多源多目標(biāo)虛擬機(jī)，采用將源二進(jìn)制代碼翻譯為TCG中間代碼再翻譯為目標(biāo)代碼的方式，可以實(shí)現(xiàn)將X86，ARM，MIPS下的ELF格式可執(zhí)行文件翻譯為TCG中間表示，再翻譯為目標(biāo)代碼.

本文設(shè)計(jì)了基于QEMU的靜態(tài)二進(jìn)制翻譯框架Static-QEMU(SQEMU)，采用QEMU的前端分析和TCG中間表示，繼承了QEMU跨平臺(tái)的特性.與QEMU和基于LLVM的動(dòng)態(tài)二進(jìn)制翻譯器[5-6,8-9]相比，SQEMU分離翻譯、代碼優(yōu)化與目標(biāo)程序執(zhí)行階段，使得在同等優(yōu)化手段下SQEMU能夠更高效.并且，由于代碼優(yōu)化時(shí)間不受運(yùn)行時(shí)的限制，能夠采用不同層次的優(yōu)化算法生成高質(zhì)量的執(zhí)行代碼.

SQEMU包括前端源指令提取、TCG中端分析優(yōu)化、后端目標(biāo)代碼生成3個(gè)階段，基本設(shè)計(jì)結(jié)構(gòu)如圖1所示.其中，源文件解析器、前端解碼器構(gòu)成SQEMU前端，負(fù)責(zé)將源平臺(tái)二進(jìn)制代碼(本文即X86代碼)翻譯成中間代碼TCG(tiny code generator)，TCG中端分析優(yōu)化器對(duì)中間表示進(jìn)行平臺(tái)無(wú)關(guān)優(yōu)化，后端翻譯器負(fù)責(zé)將TCG中間代碼翻譯成目標(biāo)平臺(tái)的二進(jìn)制代碼(本文中為Alpha代碼).前端和TCG中端分析優(yōu)化器采用QEMU的相應(yīng)模塊，刪除了QEMU中控制中心、緩存管理和執(zhí)行模塊，后端添加了目標(biāo)文件生成器.

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

其中，前端解碼器逐條對(duì)源平臺(tái)指令進(jìn)行解碼，SQEMU使用了QEMU的指令譯碼部分，根據(jù)譯碼器分析出的指令，生成相同語(yǔ)義的TCG指令.傳統(tǒng)的優(yōu)化策略僅在TCG分析優(yōu)化器中針對(duì)TCG中間代碼層進(jìn)行平臺(tái)無(wú)關(guān)優(yōu)化[12]，如活性分析和塊內(nèi)寄存器分配.而事實(shí)上由于僅靠軟件翻譯，一條X86指令翻譯后經(jīng)TCG中間代碼優(yōu)化后仍會(huì)生成多條Alpha代碼，其中含有大量冗余指令和冗余訪存操作，執(zhí)行效率很低.針對(duì)這一現(xiàn)狀，本文在目標(biāo)代碼層實(shí)現(xiàn)冗余代碼優(yōu)化.

2 冗余指令的發(fā)現(xiàn)

SQEMU系統(tǒng)后端生成的Alpha代碼的冗余是影響代碼膨脹的最直接因素，通過(guò)分析SQEMU后端生成的Alpha代碼，原SQEMU系統(tǒng)并沒(méi)有對(duì)目標(biāo)碼進(jìn)行冗余刪除的優(yōu)化，其中存在少量含有非活躍變量的常規(guī)指令和大量冗余訪存指令，本節(jié)著重描述冗余訪存指令.

冗余訪存指令是指在該訪存指令之前，有對(duì)同一個(gè)內(nèi)存地址的讀或者寫(xiě)指令，并且該地址的值仍保留在同一寄存器中，那么當(dāng)前訪存指令即可定義為冗余訪存指令.在靜態(tài)二進(jìn)制翻譯器SQEMU后端產(chǎn)生的目標(biāo)碼中，如果參與運(yùn)算的寄存器值先用ldl指令從內(nèi)存中取出，運(yùn)算結(jié)束后再使用stl指令存入內(nèi)存中，這樣，當(dāng)這2條指令之間存在數(shù)據(jù)相關(guān)性時(shí)，就會(huì)產(chǎn)生訪存冗余的情況；或先使用stl指令將運(yùn)算結(jié)束后的寄存器值存入內(nèi)存中，當(dāng)遇到下一條需要從相同位置取出同一寄存器值的ldl指令前，并沒(méi)有對(duì)該寄存器值進(jìn)行重新賦值，此時(shí)也會(huì)產(chǎn)生訪存冗余，即存在類似圖2所示的匯編程序段.

Fig. 2 Redundant code examples圖2 冗余代碼示例

通過(guò)對(duì)SQEMU的后端編碼器按TCG中間表示生成的目標(biāo)平臺(tái)代碼進(jìn)行語(yǔ)義分析，通過(guò)提取操作碼和寄存器，總結(jié)歸納出其執(zhí)行特性，發(fā)現(xiàn)其中含有大量如表1所示的冗余指令對(duì).

1) stl-ldl型.如果匹配到的stl和ldl指令之間并沒(méi)有對(duì)同一寄存器進(jìn)行重新賦值，且偏移量不變，則ldl指令為冗余指令.

2) stl-stl型.如果匹配到的2條stl指令之間并沒(méi)有對(duì)同一寄存器進(jìn)行重新賦值，且偏移量不變，則第2條stl指令為冗余指令.

3) ldl-ldl型.如果匹配到的2條ldl指令之間并沒(méi)有對(duì)同一寄存器進(jìn)行重新賦值，且偏移量不變，則第2條ldl指令為冗余指令.

4) ldl-stl型.如果匹配到的ldl和stl指令之間并沒(méi)有對(duì)同一寄存器進(jìn)行重新賦值，且偏移量不變，則stl指令為冗余指令.

Table 1 Redundancy Types of Instruction

3 冗余指令的優(yōu)化思路

目標(biāo)碼中使用大量的臨時(shí)寄存器來(lái)處理指令中數(shù)據(jù)運(yùn)算與傳遞，針對(duì)目標(biāo)平臺(tái)后端生成的Alpha代碼的特點(diǎn)，將活性分析和窺孔優(yōu)化理論應(yīng)用到SQEMU的后端代碼優(yōu)化過(guò)程中，以達(dá)到刪除冗余代碼，降低代碼膨脹率的目的.活性分析理論通常用于編譯器中以判斷臨時(shí)變量的活躍，對(duì)基本塊的正確劃分是活性分析的前提.正確劃分基本塊的關(guān)鍵就是確定基本塊的首地址，基本塊首地址按照一定規(guī)則確定，例如程序入口點(diǎn)、分支指令的下一條指令、分支指令的目標(biāo)地址等.其中，在處理分支指令的目標(biāo)地址時(shí)情況較復(fù)雜，首先分析X86指令，找到分支指令，并分析其后的目標(biāo)地址，以分支指令的目標(biāo)地址作為基本塊的首地址.若間接跳轉(zhuǎn)指令為call指令，由于其目的地址一定是某函數(shù)的首地址，而該函數(shù)的首地址往往在上一個(gè)函數(shù)的return指令之后，則根據(jù)劃分規(guī)則，必然會(huì)被確定為基本塊首地址；若分支指令jump是直接跳轉(zhuǎn)指令，則其目的地址一定是一個(gè)常數(shù)，能夠從靜態(tài)二進(jìn)制翻譯后得到的目標(biāo)代碼中直接獲取到；若jump為間接跳轉(zhuǎn)指令，由于間接跳轉(zhuǎn)指令的目標(biāo)地址依賴于程序運(yùn)行時(shí)寄存器的值，在靜態(tài)二進(jìn)制翻譯中無(wú)法確定該指令的目標(biāo)地址，因此間接跳轉(zhuǎn)指令的目標(biāo)地址確定問(wèn)題成為靜態(tài)二進(jìn)制翻譯的關(guān)鍵問(wèn)題之一.

間接跳轉(zhuǎn)指令的存在會(huì)導(dǎo)致靜態(tài)翻譯模式自動(dòng)翻譯某些程序時(shí)失敗，但當(dāng)靜態(tài)翻譯成功翻譯時(shí)，生成程序的正確性是可以保證的.解決間接跳轉(zhuǎn)指令目標(biāo)確定問(wèn)題是為了完備的代碼挖掘，即使用間接轉(zhuǎn)移指令的目標(biāo)地址來(lái)定位后繼指令位置以確定基本塊.針對(duì)間接跳轉(zhuǎn)指令的目標(biāo)地址確定問(wèn)題，課題組相繼進(jìn)行了不懈探索：吳偉峰提出一個(gè)改善其完備性的亞純靜態(tài)二進(jìn)制翻譯框架[13]，該框架基于靜態(tài)二進(jìn)制翻譯，并為翻譯器提供此待翻譯二進(jìn)制程序?qū)?yīng)的制導(dǎo)文件，翻譯時(shí)根據(jù)制導(dǎo)信息提取系統(tǒng)(control and guide information picking system, CGIPS)提供的信息，有效解決間接跳轉(zhuǎn)、間接調(diào)用和自修改代碼等制約靜態(tài)二進(jìn)制發(fā)展的翻譯完備性問(wèn)題；盧帥兵提出在SQEMU中使用源地址索引映射表來(lái)確定間接跳轉(zhuǎn)指令目標(biāo)地址[10]，以解決在靜態(tài)二進(jìn)制翻譯中目標(biāo)地址依賴于程序運(yùn)行時(shí)寄存器的值，且在多次運(yùn)行時(shí)分支目標(biāo)地址可能改變而無(wú)法確定該指令目標(biāo)地址的問(wèn)題，但SQEMU是針對(duì)逐條指令翻譯，破壞了基本塊的整體性，無(wú)法采用針對(duì)基本塊中冗余訪存指令的優(yōu)化算法.

結(jié)合實(shí)驗(yàn)室目前的研究成果，在實(shí)際處理間接跳轉(zhuǎn)指令時(shí)，本文在靜態(tài)二進(jìn)制翻譯框架SQEMU的基礎(chǔ)上，使用文獻(xiàn)[13]提出的執(zhí)行路徑逆向構(gòu)造算法和特定路徑的控制執(zhí)行算法，利用線性掃描反匯編工具objdump處理待翻譯程序，獲得逆向構(gòu)造所需匯編指令，進(jìn)而定位出靜態(tài)二進(jìn)制翻譯中影響基本塊劃分的間接跳轉(zhuǎn)指令目標(biāo)地址.

按照上述分析和算法，能夠確定基本塊首地址，進(jìn)而全面正確地劃分基本塊.

3.1 針對(duì)常規(guī)冗余指令的優(yōu)化

在對(duì)冗余訪存指令優(yōu)化前，先根據(jù)指令特性以及相鄰目標(biāo)碼間寄存器的使用關(guān)系，通過(guò)分析目標(biāo)碼生成指令特定數(shù)據(jù)依賴圖IDDG.它以TCG中間表示生成的匯編碼qemu.asm作為輸入，將目標(biāo)碼順序生成相對(duì)應(yīng)的指令相關(guān)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)由相應(yīng)指令的信息(操作碼、寄存器、立即數(shù)等)組成.一旦指令相關(guān)節(jié)點(diǎn)確立，節(jié)點(diǎn)之間的數(shù)據(jù)依賴關(guān)系則根據(jù)源寄存器和目的寄存器之間的使用關(guān)系被同時(shí)確立，且這2個(gè)節(jié)點(diǎn)用定向性依賴邊相連.因此，整個(gè)IDDG包括指令特性節(jié)點(diǎn)和依賴邊.

在生成數(shù)據(jù)依賴圖以前，先給出以下相關(guān)定義:

定義1. 輸出變量集合Out(S).輸出變量代表著對(duì)寄存器的寫(xiě)操作，由語(yǔ)句S的所有輸出變量組成的集合稱為S的輸出變量集合.

定義2. 輸入變量集合In(S).輸入變量代表著對(duì)寄存器的讀操作，由語(yǔ)句S的所有輸入變量組成的集合稱為S的輸入變量集合.

定義3. 引用變量集合Use(S).表示語(yǔ)句S中被引用到的變量的集合.

定義4. 定值變量集合Def(S).表示語(yǔ)句S中被定值變量的集合.

定義5. 依賴關(guān)系.對(duì)于計(jì)算機(jī)程序，當(dāng)事件或動(dòng)作A必須先于事件B而發(fā)生時(shí)，稱B依賴于A.

1) 若同時(shí)有x∈Out(S)，x∈In(T)，且T使用由S計(jì)算出的x的值，則稱T流依賴于S，記為TδfS，用弧線表示.

2) 若同時(shí)有x∈In(S)，x∈Out(T)，但S使用x的值先于T對(duì)x的定值，則稱T反依賴于S，記SδaT，用帶×的弧線表示.

3) 若同時(shí)有x∈Out(S)，x∈Out(T)，且S對(duì)x的定值先于T對(duì)x的定值，則稱T輸出依賴于S，記為SδoT，用帶°的弧線表示.

活性分析理論是一種全局?jǐn)?shù)據(jù)流分析，在此，我們將活性分析理論用于基本塊內(nèi)任意路徑數(shù)據(jù)流分析，從全局范圍來(lái)看一個(gè)變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當(dāng)前值還要被引用.

針對(duì)SQEMU后端代碼的活性分析算法是以基本塊為單位逆向線性掃描生成的目標(biāo)碼，分析目標(biāo)碼并生成指令相關(guān)節(jié)點(diǎn)，確定節(jié)點(diǎn)之間的數(shù)據(jù)依賴關(guān)系即源寄存器和目的寄存器之間的使用關(guān)系，根據(jù)源寄存器在執(zhí)行本條指令后基本塊后續(xù)指令是否改變寄存器的值來(lái)判斷寄存器的活躍性.通過(guò)對(duì)目標(biāo)碼的活性分析，就能識(shí)別出當(dāng)前值不再活躍的那些寄存器.若該條語(yǔ)句中寄存器均失去活性，則可判定為冗余代碼.

令S為基本塊內(nèi)一條語(yǔ)句，定義F(S)為基本塊內(nèi)語(yǔ)句S的前驅(qū)語(yǔ)句集合，N(S)為語(yǔ)句S的后繼語(yǔ)句集合,則根據(jù)定義6中規(guī)定的數(shù)據(jù)依賴關(guān)系一定存在至少一個(gè)寄存器x使得：

Sδfi，即x∈Out(i)∩In(S)；

jδfS，即x∈Out(S)∩In(j).

其中，i∈F(S)，j∈N(S).

定義LiveIn(S)為在語(yǔ)句輸入變量集合中為活躍變量的集合，定義LiveOut(S)為語(yǔ)句輸出變量集合中為活躍變量的集合.其中，LiveIn和LiveOut并不是相互獨(dú)立的，則有：

∪LiveOut(i)=∪LiveIn(j)，

(1)

其中，i∈F(S)，j∈N(S).

也就是說(shuō)，一個(gè)基本塊內(nèi)，某條指令之前的語(yǔ)句其目的寄存器是活躍的僅當(dāng)該條指令后繼指令源寄存器為活躍的.如果該指令沒(méi)有后繼，則其LiveOut為空.

根據(jù)定義3，Use(S)是一個(gè)集合常量，其值由語(yǔ)句S唯一確定，易得，如果x∈Use(S)，則x∈LiveIn(S)，即：

LiveIn(S)?Use(S).

(2)

根據(jù)定義4，Def(S)也是一個(gè)集合常量，其值由語(yǔ)句S唯一確定，如果一個(gè)寄存器在語(yǔ)句S的輸出變量集合中為活躍的且x?Def(S)，則它在S的輸入變量集合中一定為活躍值，即：

LiveIn(S)?LiveOut(S)-Def(S).

(3)

通過(guò)分析可知，一個(gè)寄存器在語(yǔ)句輸入變量中為活躍的，則一定有：或者它在語(yǔ)句的Use中，或者它在語(yǔ)句的輸出變量中為活躍的且在語(yǔ)句中沒(méi)有被重新定值.因此，有等式：

LiveIn(S)=Use(S)∪(LiveOut(S)-Def(S))，

(4)

式(4)對(duì)于基本塊內(nèi)每條語(yǔ)句均成立.

若對(duì)于語(yǔ)句S中被定值的變量集合不屬于語(yǔ)句S輸出變量中活躍變量的集合，則這條定值指令可判定為冗余指令，即:

LiveOut(S)∩Def(S)=?.

(5)

設(shè)靜態(tài)二進(jìn)制翻譯目標(biāo)碼中指令規(guī)則為∏，定義指令輸入變量數(shù)、輸出變量數(shù)、變量總數(shù)等性質(zhì)，∏in(S)表述語(yǔ)句S這條指令輸入變量數(shù)，∏out(S)表示該指令輸出變量數(shù)，∏all(S)表示該指令變量總數(shù)，N表示基本塊內(nèi)語(yǔ)句總數(shù).

① 如果∏out(S)=0，指令只引用變量，并未對(duì)變量定值；

② 否則，該指令對(duì)變量重定：

(6)

其中，∏all(S)=∏out(S)∪∏in(S).

若存在jδfS，則有：

Def(j)=Def(S)-∏(S)*Def(S)，

(7)

Use(j)=Use(S)+∏(S)*Def(S)，

(8)

其中，“*”表示對(duì)∏(S)的重定義.

設(shè)Use～(S)表示語(yǔ)句S在按照指令規(guī)則語(yǔ)句中寄存器被引用集合，由式(8)可得：

Use(j)=Use～(S).

(9)

首先設(shè)定對(duì)活躍寄存器x重新定值的語(yǔ)句j是距離源寄存器所在語(yǔ)句S最短的語(yǔ)句.依據(jù)冗余指令的判定公式可得：

.

(10)

(11)

綜上所述，若存在語(yǔ)句T使得SδoT，且在S與T之間并沒(méi)有對(duì)寄存器使用或重定值，則S語(yǔ)句中的寄存器被判定為失去活性，該指令為冗余訪存指令.

失去活性的寄存器所在指令用“#”標(biāo)識(shí)，不再翻譯成目標(biāo)指令.將生成的指令相關(guān)節(jié)點(diǎn)以基本塊為單位存儲(chǔ)在數(shù)組charbb[][BBCOLUMS]中，用指針STLD_INFO *temp逆向順次移動(dòng).為標(biāo)識(shí)基本塊內(nèi)寄存器的所有使用情況，開(kāi)辟一個(gè)大小為基本塊寄存器總體數(shù)量的數(shù)組空間，并初始化為1，表示基本塊內(nèi)寄存器全部為非活躍.然后利用指針STLD_INFO *temp對(duì)生成的指令相關(guān)節(jié)點(diǎn)進(jìn)行分析，判斷指令目標(biāo)寄存器對(duì)應(yīng)在數(shù)組空間是否標(biāo)記為1：

1) 若全為1，即寄存器已經(jīng)失去活性，該指令即可視為冗余訪存指令；

2) 若不全為1，將指令的源寄存器和目的寄存器對(duì)應(yīng)在數(shù)組空間的值標(biāo)記清0，表明寄存器是活躍的.

依次循環(huán)迭代直到基本塊入口點(diǎn)，完成整個(gè)基本塊的寄存器活性分析.

Table 2 Usage Rule of Register

算法1.活性分析算法.

① 初始化基本塊內(nèi)寄存器； 將所有特殊寄存器標(biāo)記為活，即0； 將一般寄存器標(biāo)記為死，即1； 設(shè)基本塊總共有n條語(yǔ)句；

② for (i=n-1；i≥0；i--)

③ 提取語(yǔ)句S的In(S),Out(S)；

④ end for

⑤ if (Out(S)是活性的)

⑥ 把Out(S)標(biāo)記為死，把In(S)標(biāo)記為活性；

⑦ end if

⑧ if (Out(S)為特殊寄存器)

⑨ 把Out(S)標(biāo)記為活性；

⑩ else

從SQEMU系統(tǒng)后端生成的類Alpha代碼中選取一段用于活性分析，如圖3所示：

Fig. 3 Redundant code of common instruction圖3 常規(guī)指令冗余代碼

Fig. 4 Activity analysis diagram coloring process圖4 活性分析圖著色過(guò)程

圖4中inst7寄存器R4為輸出變量，通過(guò)逆向活性分析發(fā)現(xiàn)，R4在語(yǔ)句2)中被重新賦值，且在這2條指令之間寄存器R4并未被引用，判定輸出變量R4已不活躍，所以R4所在的語(yǔ)句2)為冗余指令，可在后續(xù)優(yōu)化過(guò)程中直接刪除.

3.2 針對(duì)訪存冗余指令的優(yōu)化

通過(guò)對(duì)目標(biāo)碼中寄存器進(jìn)行活性分析，刪除一定的失去活性的寄存器和冗余代碼，但對(duì)SQEMU生成的后端Alpha代碼分析時(shí)發(fā)現(xiàn)這種冗余代碼并不常見(jiàn)，利用活性分析技術(shù)進(jìn)行優(yōu)化對(duì)整體翻譯性能提升程度有限，無(wú)法從全局做到代碼最優(yōu)化，且仍存在如冗余代碼發(fā)現(xiàn)所述大量冗余訪存指令.代碼產(chǎn)生器依次逐條將中間代碼翻譯為目標(biāo)代碼時(shí)，通常使目標(biāo)代碼中產(chǎn)生冗余指令或者不太優(yōu)的結(jié)構(gòu).在目標(biāo)代碼級(jí)上，可以利用窺孔優(yōu)化(peephole optimization)有效處理冗余代碼，改進(jìn)代碼質(zhì)量.

窺孔優(yōu)化是一種局部?jī)?yōu)化方法，其基本原理是通過(guò)考察編譯器所生成的目標(biāo)代碼中一小段相鄰指令(稱為窺孔)，比如一個(gè)基本塊中的目標(biāo)碼，通過(guò)整體分析和指令轉(zhuǎn)換，把這些指令替換為更短和更快的一段指令，以此來(lái)提高代碼質(zhì)量.

美國(guó)Stanford大學(xué)的靜態(tài)二進(jìn)制翻譯器利用窺孔優(yōu)化對(duì)目標(biāo)代碼實(shí)施高質(zhì)量的等價(jià)替換，獲得了更為優(yōu)化的執(zhí)行效率.窺孔優(yōu)化一般包括冗余訪存指令的刪除、不可達(dá)代碼的刪除、控制流優(yōu)化、強(qiáng)度削弱等.由于窺孔優(yōu)化需要對(duì)目標(biāo)碼進(jìn)行若干遍處理，開(kāi)銷較大，較少應(yīng)用在動(dòng)態(tài)二進(jìn)制翻譯中，是靜態(tài)二級(jí)制翻譯和編譯器的常用優(yōu)化手段.雖然代碼轉(zhuǎn)換限于局部，只需很少訪問(wèn)內(nèi)存，但可能會(huì)帶來(lái)很大性能提升.

從SQEMU系統(tǒng)生成的后端Alpha代碼中隨機(jī)抽取一段目標(biāo)碼如圖5所示：

Fig. 5 Register renaming圖5 寄存器重命名

Table 3 Input and Output Variables Set

Fig. 6 Instruction-specific data dependence graph圖6 指令特定數(shù)據(jù)依賴圖

指令相關(guān)節(jié)點(diǎn)包含了指令的特性，如操作碼、立即數(shù)段、寄存器段，一個(gè)節(jié)點(diǎn)Si與預(yù)先定義的LOADSTORE指令格式相匹配，根據(jù)IDDG，由節(jié)點(diǎn)間定向性依賴邊可對(duì)節(jié)點(diǎn)Si與其目標(biāo)節(jié)點(diǎn)Sj之間的數(shù)據(jù)依賴關(guān)系依據(jù)冗余指令匹配類型進(jìn)行以下分類判定：

判定1. 若冗余訪存指令類型為stl-stl型或ldl-ldl型，則一定存在寄存器x與寄存器y，其中：

如果2條語(yǔ)句Si與Sj之間存在語(yǔ)句Sp對(duì)寄存器重新賦值，即y∈Out(Sp)且x?In(Sp)，同時(shí)滿足SpδoSj，則2條語(yǔ)句Si與Sj不是冗余訪存指令；如果3條語(yǔ)句之間不存在對(duì)寄存器重新賦值的指令，則依據(jù)活性分析結(jié)論，一定存在一條語(yǔ)句Sq使用寄存器y作為輸入變量，否則，語(yǔ)句Si與Sj為冗余訪存指令，可刪除Sj.

即若冗余訪存指令為stl-stl型或ldl-ldl型時(shí)，有：

R=(y∈Out(Sp)∩x?In(Sp))∪(y∈In(Sq))，

其中i

判定2. 若冗余訪存指令類型為stl-ldl型或ldl-stl型，則一定存在寄存器x與寄存器y，其中：

如果2條語(yǔ)句Si與Sj之間存在語(yǔ)句Sp對(duì)寄存器重新賦值，即y∈Out(Sp)且x?In(Sp)，同時(shí)滿足SpδoSj，則2條語(yǔ)句Si與Sj不是冗余訪存指令；如果2條語(yǔ)句之間不存在對(duì)寄存器重新賦值的指令，則依據(jù)活性分析結(jié)論，一定存在一條語(yǔ)句Sq使用寄存器x作為輸入變量，否則，語(yǔ)句Si與Sj為冗余訪存指令，可刪除Sj.

即若冗余訪存指令為ldl-ldl型時(shí)，有：

R=(y∈Out(Sp)∩x?In(Sp))∪(y∈In(Sq))，

其中i

4 冗余指令優(yōu)化算法

本文提出的優(yōu)化方法是基于IDDG實(shí)現(xiàn)的，將針對(duì)常規(guī)冗余指令活性分析與冗余訪存在指令窺孔優(yōu)化相結(jié)合，實(shí)現(xiàn)對(duì)目標(biāo)碼冗余指令的優(yōu)化刪除算法.

根據(jù)第2節(jié)和第3節(jié)的分析，SQEMU系統(tǒng)生成后端Alpha代碼仍存在大量冗余，影響編譯效率，對(duì)此，本文提出一種靜態(tài)二進(jìn)制翻譯冗余目標(biāo)代碼刪除優(yōu)化算法，對(duì)基本塊內(nèi)冗余代碼進(jìn)一步分析.在經(jīng)過(guò)控制流分析和數(shù)據(jù)流分析之后，其方法為只需要記錄每次循環(huán)迭代基本塊內(nèi)一條ldl或stl指令和寄存器被重寫(xiě)指令序號(hào)，每當(dāng)記錄一條新的ldl和stl指令時(shí)，遍歷已經(jīng)記錄的ldl和stl指令，2條匹配的ldl或stl指令之間若不存在寄存器被重寫(xiě)的情況，即可判斷為冗余指令，過(guò)程如下：

1) 從SQEMU系統(tǒng)后端生成的Alpha代碼中順次獲取相應(yīng)的指令信息，如操作碼、寄存器和立即數(shù)等，根據(jù)指令特性以及相鄰目標(biāo)碼間寄存器的使用關(guān)系，生成指令相關(guān)節(jié)點(diǎn)和指令特性數(shù)據(jù)依賴圖IDDG，對(duì)基本塊內(nèi)寄存器進(jìn)行活性分析，失去活性的寄存器所在指令用“#”標(biāo)識(shí)，不再翻譯成目標(biāo)指令.將生成的指令相關(guān)節(jié)點(diǎn)以基本塊為單位存儲(chǔ)在數(shù)組charbb[][BBCOLUMS]中，創(chuàng)建一雙鏈表記錄基本塊內(nèi)ldl和stl指令序號(hào)，指令類型和全局變量的偏移量.

算法流程如圖7所示：

Fig. 7 Algorithm flow chart圖7 算法流程圖

分別初始化ldl和stl指令的雙鏈表和非ldl或stl指令的單鏈表，依次分析獲取到的指令和寄存器值，確定語(yǔ)句S的輸入變量集合In(S)和輸出變量集合Out(S)，再判斷獲取到的指令類型是否為ldl或stl指令.若獲取到的指令非ldl或stl指令，根據(jù)相應(yīng)指令特點(diǎn)，則記錄輸出變量即指令中被改變的寄存器值，依據(jù)寄存器值將此語(yǔ)句的序號(hào)插入單鏈表數(shù)組中；若獲取到的指令是ldl或stl指令，遍歷存儲(chǔ)ldl和stl指令的雙鏈表，順次檢查匹配雙鏈表中指令的操作碼、寄存器值和立即數(shù)，判斷雙鏈表中的指令與待插入的ldl或stl指令對(duì)應(yīng)變量是否相等，若不相等，直接把指令插入到雙鏈表中，若雙鏈表中存在指令與待插入指令相匹配，則依據(jù)冗余指令對(duì)的類型分2種情況討論：

① stl-stl型或ldl-ldl型，即雙鏈表中已存在的指令與待插入指令為同一指令；

② stl-ldl型或ldl-stl型，首先根據(jù)IDDG確定雙鏈表中已匹配的指令節(jié)點(diǎn)與待插入指令節(jié)點(diǎn)之間的數(shù)據(jù)依賴關(guān)系，設(shè)雙鏈表中已匹配的指令節(jié)點(diǎn)為Si，待插入的指令節(jié)點(diǎn)為Sj，則根據(jù)上文提到的冗余節(jié)點(diǎn)的判定條件可知，若Si流依賴于Sj且Sj反依賴于Si，則2條指令存在是冗余訪存指令的可能.

若出現(xiàn)以上2種情況之一，下一步可依據(jù)IDDG確定2條指令節(jié)點(diǎn)之間的數(shù)據(jù)依賴關(guān)系，判斷匹配的2條語(yǔ)句之間是否存在其他指令節(jié)點(diǎn)與這條指令節(jié)點(diǎn)形成輸出依賴關(guān)系，即2條語(yǔ)句之間是否存在對(duì)寄存器重新賦值的新指令，同時(shí)遍歷該寄存器所在單鏈表，依據(jù)指令序號(hào)確認(rèn)這條新指令是否在2條匹配的指令之間.若存在，則2條已匹配的指令并不是冗余訪存指令，可將待插入指令直接插入雙鏈表中，待后續(xù)指令與其匹配；若不存在，則待插入指令即可判斷為冗余訪存指令，同時(shí)用“#”標(biāo)識(shí)該條指令，進(jìn)而完成整個(gè)冗余訪存指令刪除的優(yōu)化過(guò)程.

5 實(shí)驗(yàn)與分析

為驗(yàn)證冗余訪存優(yōu)化算法的實(shí)際優(yōu)化效果，采用上述SQEMU作為靜態(tài)二進(jìn)制翻譯平臺(tái)，通過(guò)正確性測(cè)試、整體性能測(cè)試和測(cè)試數(shù)據(jù)分析對(duì)提出的算法進(jìn)行評(píng)估.

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

1) 測(cè)試集.在SQEMU上運(yùn)行基準(zhǔn)測(cè)試集SPEC CPU2006和nbench-2.2.3 benchmark suite(QEMU官方網(wǎng)站推薦用于評(píng)測(cè)性能的測(cè)試程序).所有的執(zhí)行速度(iterations)都是5次測(cè)試的算術(shù)平均值.

2) 源平臺(tái).32位X86平臺(tái)，F(xiàn)edora11 Linux 2.6.29.4，gcc 4.4.0.

3) 目標(biāo)平臺(tái).64位Alpha平臺(tái)，中標(biāo)麒麟Linux 3.8.0，gcc 4.3.0.

5.2 正確性測(cè)試

在X86平臺(tái)上編譯SPEC CPU2006和nbench測(cè)試集，啟動(dòng)優(yōu)化后的SQEMU，輸入編譯好的X86測(cè)試集可執(zhí)行文件，從調(diào)試信息獲取執(zhí)行結(jié)果.實(shí)驗(yàn)顯示本算法翻譯執(zhí)行的結(jié)果與SPEC CPU2006和nbench正確執(zhí)行時(shí)的結(jié)果一致，說(shuō)明本算法能夠進(jìn)行正確的翻譯，具有較高可信度.

5.3 整體性能評(píng)價(jià)

為體現(xiàn)冗余訪存優(yōu)化算法對(duì)SQEMU整體性能的提高效果，分別統(tǒng)計(jì)算法改進(jìn)前后SQEMU翻譯執(zhí)行nbench和SPEC CPU2006測(cè)試集性能指標(biāo).

對(duì)nbench測(cè)試集進(jìn)行測(cè)試，記SQEMU優(yōu)化前執(zhí)行性能指標(biāo)為I1，SQEMU優(yōu)化后性能指標(biāo)為I2，性能指標(biāo)單位為iterations，即每秒循環(huán)次數(shù).加速比記作I2I1.

對(duì)基準(zhǔn)測(cè)試集SPEC CPU2006進(jìn)行測(cè)試，由于C++程序間接調(diào)用情況更復(fù)雜更頻繁，是影響靜態(tài)二進(jìn)制翻譯性能的主要瓶頸之一，未選取C++程序進(jìn)行對(duì)比.且不同語(yǔ)言程序所需編譯器不同，為增加數(shù)據(jù)可比性，對(duì)SPEC CPU2006采用其中C程序作測(cè)試用例.分別統(tǒng)計(jì)算法改進(jìn)前后SQEMU翻譯執(zhí)行SPEC CPU2006所用時(shí)間，記SQEMU優(yōu)化前執(zhí)行時(shí)間為T1，SQEMU優(yōu)化后執(zhí)行時(shí)間為T2，加速比記作T1T2.

從上述測(cè)試結(jié)果中可以發(fā)現(xiàn)，基準(zhǔn)測(cè)試集SPEC CPU2006和nbench測(cè)試集在優(yōu)化后執(zhí)行效率明顯提升，測(cè)試用例不同其性能提升的效果也不同.由表4及圖8中數(shù)據(jù)可得，通過(guò)采用針對(duì)冗余訪存指令的優(yōu)化算法可使得nbench測(cè)試集性能提升6%～42%，且平均性能提升約為20%；由圖9中數(shù)據(jù)發(fā)現(xiàn)使用優(yōu)化算法后SPEC CPU2006測(cè)試集性能提升1%～32%，SPEC CINT2006平均性能提升約17%，SPEC CFP2006平均性能提升僅約為5%.從實(shí)驗(yàn)結(jié)果中不難發(fā)現(xiàn)，該算法具有明顯的優(yōu)化效果.

Table 4 nbench Test Results

Fig. 8 nbench speed-up ratio圖8 nbench加速比

Fig. 9 SPEC CPU2006 speed-up ratio圖9 SPEC CPU2006加速比

5.4 測(cè)試數(shù)據(jù)分析

從表4針對(duì)nbench測(cè)試集得出的測(cè)試結(jié)果以及圖8和圖9中分別針對(duì)nbench和SPEC CPU2006測(cè)試用例所得加速比中發(fā)現(xiàn)，測(cè)試用例不同，加速比也不同，該冗余指令優(yōu)化算法對(duì)不同程序的優(yōu)化程度也不盡相同.由此推斷，優(yōu)化效果與程序自身指令特性和程序任務(wù)相關(guān).

分別統(tǒng)計(jì)nbench和SPEC CPU2006測(cè)試集中選取的測(cè)試用例在優(yōu)化前和優(yōu)化后的指令總數(shù)，得到如圖10、圖11所示柱狀圖.分析柱狀圖中指令總數(shù)，并設(shè)優(yōu)化效益為γ，則有公式：

不難發(fā)現(xiàn)，nbench執(zhí)行時(shí)間的加速比與指令的優(yōu)化效益成正相關(guān)，由此可推斷，冗余指令越多，被優(yōu)化掉的指令數(shù)也越多，優(yōu)化效益γ也越大，最終獲得的執(zhí)行時(shí)間的加速比也越大，即冗余指令刪除算法的效果更明顯.而SPEC CPU2006由于其規(guī)模較大、測(cè)試集較為復(fù)雜、間接跳轉(zhuǎn)指令數(shù)較多等原因，執(zhí)行時(shí)間的加速比與指令的優(yōu)化效益γ并不完全正相關(guān).

Fig. 10 nbench instruction number圖10 nbench指令數(shù)

Fig. 11 SPEC CPU2006 instruction number圖11 SPEC CPU2006指令數(shù)

首先分析nbench測(cè)試用例任務(wù)，如表5所示：

Table 5 nbench Tasks

下面對(duì)nbench測(cè)試加速比最小的測(cè)試用例FP EMULATION與所得加速比最大的前3個(gè)測(cè)試用例BITFIELD,NUMERIC_SORT,STRING_SORT進(jìn)行深入分析.

1) 查看加速比最小的FP EMULATION源碼發(fā)現(xiàn)，該測(cè)試用例內(nèi)包含3個(gè)主要函數(shù)：DoFPU-TransIteration，TrapezoidIntegrate，thefunction.分別統(tǒng)計(jì)3個(gè)函數(shù)優(yōu)化后各自的指令數(shù)，并計(jì)算其占FP EMULATION指令總數(shù)的百分比，如圖12所示.FP EMULATION測(cè)試用例中主要占用執(zhí)行時(shí)間的函數(shù)是DoFPUTransIteration，且其指令數(shù)也最多，而DoFPUTransIteration函數(shù)中主要操作為模擬基本數(shù)學(xué)運(yùn)算，主要涉及memmove，與優(yōu)化算法關(guān)系不大.

Fig. 12 Ratio of FP EMULATION instruction number圖12 FP EMULATION指令數(shù)比例

2) 對(duì)BITFIELD測(cè)試用例使用冗余指令刪除算法優(yōu)化，其所得加速比最大即達(dá)到1.418.BITFIELD是一系列位操作函數(shù)，位操作需要大量使用通用寄存器，而本文提出的冗余指令刪除優(yōu)化算法對(duì)通用寄存器優(yōu)化效果最為明顯，且BITFIELD測(cè)試用例中冗余指令數(shù)目較多，所以優(yōu)化效果最好.

3) NUMERIC_SORT和STRING_SORT加速比分別為1.373和1.222，NUMERIC_SORT實(shí)現(xiàn)對(duì)32位整型數(shù)組排序的任務(wù)，而STRING_SORT實(shí)現(xiàn)的任務(wù)是對(duì)任意長(zhǎng)度字符串?dāng)?shù)組的排序，這2個(gè)測(cè)試用例使用整型寄存器和通用寄存器較多，如果2條指令使用同一寄存器，則極大可能產(chǎn)生冗余存取指令.而冗余指令刪除優(yōu)化算法主要針對(duì)冗余存取指令，所以優(yōu)化效果也比較好.

其次分析基準(zhǔn)測(cè)試集SPEC CPU2006，利用執(zhí)行路徑逆向構(gòu)造算法和特定路徑的控制執(zhí)行算法定位出阻礙靜態(tài)二進(jìn)制翻譯間接跳轉(zhuǎn)指令的目標(biāo)地址.針對(duì)基準(zhǔn)測(cè)試集SPEC CPU2006分別統(tǒng)計(jì)出其間接跳轉(zhuǎn)指令數(shù)和間接調(diào)用指令數(shù)，如表6所示.

從5.3節(jié)整體性能評(píng)價(jià)中得知，通過(guò)采用針對(duì)冗余訪存指令的優(yōu)化算法可使nbench測(cè)試集平均性能提升約為20%，SPEC CINT2006平均性能提升約17%，SPEC CFP2006平均性能提升僅約為5%.SPEC CPU2006整體測(cè)試優(yōu)化效益低于nbench測(cè)試集，一方面由于SPEC CPU2006測(cè)試集復(fù)雜度較高，另一方面從定位到的阻礙靜態(tài)二進(jìn)制翻譯間接跳轉(zhuǎn)指令的目標(biāo)地址來(lái)看，SPEC CPU2006含有較多間接分支指令，而nbench熱路徑中不存在間接跳轉(zhuǎn)指令.間接分支指令影響基本塊的劃分，例如，當(dāng)間接跳轉(zhuǎn)指令跳轉(zhuǎn)到原有基本塊內(nèi)部時(shí)，根據(jù)基本塊劃分規(guī)則，該基本塊需要進(jìn)行重新劃分，導(dǎo)致基本塊規(guī)模減小，而本文所述冗余訪存指令優(yōu)化算法是基于基本塊進(jìn)行優(yōu)化，基本塊規(guī)模減小將導(dǎo)致優(yōu)化程度隨之降低.通過(guò)分析表6中間接分支指令數(shù)測(cè)試結(jié)果與圖9中SPEC CPU2006加速比發(fā)現(xiàn)，優(yōu)化加速比與間接跳轉(zhuǎn)指令數(shù)大致成反比例關(guān)系.

Table 6 Indirect Branch Instruction Test Results

從測(cè)試用例類型來(lái)看，SPEC CINT2006平均性能提升程度接近nbench測(cè)試集，而SPEC CFP2006遠(yuǎn)低于nbench.由于SPEC CFP2006浮點(diǎn)測(cè)試用例中熱代碼主要是浮點(diǎn)指令，SQEMU使用函數(shù)模擬浮點(diǎn)指令的功能，該算法對(duì)此類指令優(yōu)化效果較差.

從上述分析可得，本文提出的冗余指令優(yōu)化算法對(duì)不同測(cè)試用例得到的優(yōu)化效果也不盡相同，主要取決于程序自身指令特性和程序任務(wù).待優(yōu)化的程序冗余指令數(shù)目越多，在執(zhí)行過(guò)程中主要使用整型寄存器和通用寄存器，則會(huì)取得較好的優(yōu)化效果.而間接分支指令和浮點(diǎn)操作也會(huì)影響實(shí)際優(yōu)化效果，間接跳轉(zhuǎn)指令和浮點(diǎn)操作越少則取得的優(yōu)化效果將越好.

6 相關(guān)研究

文獻(xiàn)[14-15]中針對(duì)TCG使用大量臨時(shí)變量來(lái)處理指令數(shù)據(jù)運(yùn)算與傳遞，QEMU引入寄存器活性分析優(yōu)化技術(shù)和存儲(chǔ)轉(zhuǎn)發(fā)優(yōu)化技術(shù)來(lái)刪除中間表示中存在的冗余變量，減少中間表示指令，降低代碼的膨脹率，但是中間表示優(yōu)化對(duì)整體翻譯性能提升程度有限且仍存在冗余指令.

文獻(xiàn)[4]中為了提高翻譯后代碼的質(zhì)量，使用改進(jìn)LLVM編譯器針對(duì)生成的LLVM中間代碼進(jìn)行優(yōu)化，其中包括增加寄存器優(yōu)化和標(biāo)量運(yùn)算矢量化等，和QEMU相比，這種優(yōu)化過(guò)程卻導(dǎo)致整體翻譯效率損失超過(guò)60倍，為了降低優(yōu)化開(kāi)銷，HQEMU卸載了在多核系統(tǒng)中的其他硬件線程或內(nèi)核的優(yōu)化過(guò)程，嚴(yán)重降低了系統(tǒng)吞吐量.

文獻(xiàn)[2]中引用活性分析技術(shù)對(duì)QEMU后端MIPS冗余MOVE指令提出了刪除算法，優(yōu)化了目標(biāo)代碼的冗余指令，但僅僅針對(duì)冗余MOVE指令，優(yōu)化方法過(guò)于單一，不能取得較完備的優(yōu)化效益.

文獻(xiàn)[16]中針對(duì)動(dòng)態(tài)翻譯時(shí)高速緩存負(fù)荷數(shù)倍膨脹導(dǎo)致翻譯器性能下降的問(wèn)題，提出基于指令高速緩存與數(shù)據(jù)高速緩存訪問(wèn)負(fù)荷動(dòng)態(tài)均衡的軟硬件協(xié)同翻譯方法，該方法主要為處理器設(shè)計(jì)高速緩存負(fù)荷平衡狀態(tài)和負(fù)荷轉(zhuǎn)化通道，通過(guò)軟硬件協(xié)同配合的方式把調(diào)度器地址轉(zhuǎn)換操作在指令高速緩存上產(chǎn)生的負(fù)荷轉(zhuǎn)化到數(shù)據(jù)高速緩存，有效提高了數(shù)據(jù)高速緩存的利用率和動(dòng)態(tài)翻譯器性能.但并未提及對(duì)大量冗余代碼造成代碼膨脹導(dǎo)致翻譯器性能下降的處理.

7 結(jié)束語(yǔ)

本文提出了一種基于靜態(tài)二進(jìn)制翻譯器SQEMU的冗余代碼優(yōu)化算法，該算法針對(duì)X86指令使用SQEMU翻譯生成多條Alpha目標(biāo)代碼的過(guò)程中，含有大量冗余操作的缺陷，利用指令特定數(shù)據(jù)依賴圖結(jié)合活性分析和窺孔優(yōu)化思想，分別針對(duì)常規(guī)冗余指令和冗余訪存指令進(jìn)行優(yōu)化.實(shí)驗(yàn)結(jié)果表明，經(jīng)優(yōu)化后，在64位Alpha目標(biāo)平臺(tái)上利用SQEMU翻譯X86程序其運(yùn)行速度得到可觀提升，該算法優(yōu)化效益最高可達(dá)到42%.該算法具有相當(dāng)強(qiáng)的通用性，很多二進(jìn)制翻譯框架存在訪存指令的冗余問(wèn)題，不限于目標(biāo)平臺(tái)和指令形式，例如文獻(xiàn)[13]中提到的二進(jìn)制翻譯系統(tǒng)UQBT和文獻(xiàn)[17]提到的一個(gè)動(dòng)態(tài)翻譯結(jié)合解釋執(zhí)行的二進(jìn)制翻譯系統(tǒng)DigitalBridge，由于其對(duì)源平臺(tái)指令的每一次訪問(wèn)寄存器都需要進(jìn)行訪存操作，必然存在冗余訪存指令，效率較低.所以該算法對(duì)跨平臺(tái)應(yīng)用程序的移植具有極高的現(xiàn)實(shí)意義，對(duì)降低二進(jìn)制翻譯后的代碼膨脹率和推動(dòng)國(guó)產(chǎn)處理器的發(fā)展有重要意義.

[1]Bellard F. QEMU, a fast and portable dynamic translator[C]Proc of the 9th IEEE Working Conf on Reverse Engineering. Piscataway, NJ: IEEE, 2002: 35-44

[2]Song Qiang. Research of optimization for binary translator QEMU based on Godson[D]. Hefei: University of Science and Technology of China, 2012 (in Chinese)(宋強(qiáng). 基于龍芯的二進(jìn)制翻譯器QEMU優(yōu)化研究[D]. 合肥: 中國(guó)科學(xué)技術(shù)大學(xué), 2012)

[3]Li Jianhui, Ma Xiangning, Zhu Chuanqi, et al. Research on dynamic binary translation and optimization[J]. Journal of Computer Research and Development, 2007, 44(1): 161-168 (in Chinese)(李劍慧, 馬湘寧, 朱傳琪, 等, 動(dòng)態(tài)二進(jìn)制翻譯與優(yōu)化技術(shù)研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(1): 161-168)

[4]Hong Ding-Yong, Hsu Chun-Chen, Yew Pen-Chung, et al. HQEMU: A multi-threaded and retargetable dynamic binary translator on multicores[C]Proc of CGO’12. New York: ACM, 2012: 104-113

[5]Shen B, You J, Yang W, et al. An LLVM-based hybrid binary translation system[C]Proc of the 7th IEEE Int Symp on Industrial Embedded Systems. Piscataway, NJ: IEEE, 2012: 229-236

[6]Lyu Yihong, Hong Dingyong, Wu Taiyi, et al. DBILL: An efficient and retargetable dynamic binary instrumentation framework using LLVM backend[C]Proc of the 10th ACM SIGPLANSIGOPS Int Conf on Virtual Execution Environments(VEE). New York: ACM, 2014: 141-152

[7]Zhang Xiaochun, Guo Qi, Chen Yunji, et al. HERMES: A fast cross-ISA binary translator with post-optimization[C]Proc of the 13th Annual IEEEACM Int Symp on Code Generation and Optimization (CGO ). New York: ACM, 2015: 246-256

[8]Jeffery A. Using the LLVM compiler infrastructure for optimised, asynchronous dynamic translation in Qemu[D]. Adelaide, Australia: the University of Adelaide, 2009

[9]Chipounov V, Candea G. Dynamically translating x86 to LLVM using QEMU, EPFL-TR-149975[R]. Lausanne, Switzerland: Swiss Federal Institute of Technology in Lausanne, 2010

[10]Lu Shuaibing, Pang Jianmin, Shan Zheng, et al. Retargetable static binary translator based on QEMU[J]. Journal of Zhejiang University, 2016, 50(1): 158-165 (in Chinese)(盧帥兵, 龐建民, 單征, 等. 基于QEMU的跨平臺(tái)靜態(tài)二進(jìn)制翻譯系統(tǒng)[J]. 浙江大學(xué)學(xué)報(bào), 2016, 50(1): 158-165)

[11]Filipe de A G, Fernanda L K, Jose E P S, et al. Soft error injection methodology based on QEMU software platform[C]Proc of the 15th Latin American Test Workshop( LATW). Piscataway, NJ: IEEE, 2014: 1-5

[12]Shao Yuanhua. Research and implementation of instruction optimization technique based on QEMU emulator[D]. Chengdu: University of Electronic Science and Technology, 2013 (in Chinese)(邵院華. 基于QEMU仿真器的指令優(yōu)化技術(shù)的研究與實(shí)現(xiàn)[D]. 成都: 電子科技大學(xué), 2013)

[13]Wu Weifeng. Research on completeness of static binary translation and analysis of code[D]. Zhengzhou: PLA Information Engineering University, 2012 (in Chinese)(吳偉峰. 靜態(tài)二進(jìn)制翻譯完備性及代碼分析研究[D]. 鄭州: 解放軍信息工程大學(xué), 2012)

[14]Payer M, Gross T R. Generating low overhead dynamic binary translators[C]Proc of the 3rd Annual Haifa Experimental Systems Conf. New York: ACM, 2010: 1-14

[15]Guha A, Hazelwood K, Soffa M L. Memory optimization of dynamic binary translators for embedded systems[J]. ACM Trans on Architecture and Code Optimization, 2012, 9(3): 1-29

[16]Li Zhanhui, Liu Chang, Meng Jianyi, et al. Cache load balancing oriented dynamic binary translation[J]. Journal of Computer Research and Development, 2015, 52(9): 2105-2113 (in Chinese)(李戰(zhàn)輝, 劉暢, 孟建熠, 等. 基于高速緩存負(fù)荷均衡的動(dòng)態(tài)二進(jìn)制翻譯研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(9): 2105-2113)

[17]Wang Wenwen, Wu Chenggang, Bai Tongxin, et al. A pattern translation method for flags in binary translation[J]. Journal of Computer Research and Development, 2014, 51(10): 2336-2347 (in Chinese)( 王文文, 武成崗, 白童心, 等. 二進(jìn)制翻譯中標(biāo)志位的模式化翻譯方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(10): 2336-2347)

Tan Jie, born in 1991. PhD candidate. Her main research interests include binary translation and high performance computing.

Pang Jianmin, born in 1964. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include high performance computing and information security (jianmin_pang@hotmail.com).

Shan Zheng, born in 1977. PhD, associate professor. Senior member of CCF. His main research interests include high performance computing and information security (zzzhengming@163.com).

Yue Feng, born in 1985. PhD. Student member of CCF. His main research interests include dynamic compiling and system virtualization (firstchoiceyf@163.com).

Lu Shuaibing, born in 1990. Master. His main research interests include binary translation and high performance computing (yeaxxx@163.com).

Dai Tao, born in 1990. Master. His main research interests include software reverse engineering (daitworld@126.com).

Redundant Instruction Optimization Algorithm in Binary Translation

Tan Jie, Pang Jianmin, Shan Zheng, Yue Feng, Lu Shuaibing, and Dai Tao

(StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,Zhengzhou450002)

Binary translation is a main method to implement software migration.Dynamic binary translation is limited by dynamic execution and cannot be deeply optimized, resulting in low efficiency.Traditional static binary translation has difficulty to deal with indirect branch, and conventional optimization methods mostly affect in the intermediate code layer, paying less attention to a large number of redundant instructions that exist in the target code.According to this situation, this paper presents a static binary translation framework SQEMU and a target code optimization algorithm to delete redundant instructions based on the framework.The algorithm generates an instruction-specific data dependence graph(IDDG) based on the analysis of target codes, then combines liveness analysis with peephole optimization using IDDG, and effectively removes redundant instructions in target codes.Experimental results show that using the optimization algorithm for target codes, the execution efficiency is significantly increased, the maximal increase up to 42%, and the overall performance test shows that the optimized translation efficiency of nbench is increased by about 20% on average, and it is increased about 17% of SPEC CINT2006 on average.

binary translation; redundant instruction; liveness analysis; peephole optimization; SQEMU frame

2015-12-21；

2016-06-02

國(guó)家自然科學(xué)基金項(xiàng)目(61472447)；國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2009AA012201)；“核高基”國(guó)家科技重大專項(xiàng)基金項(xiàng)目(2009ZX01036-001-001) This work was supported by the National Natural Science Foundation of China (61472447), the National High Technology Research and Development Program of China (863 Program) (2009AA012201), and the National Science and Technology Major Projects of Hegaoji (2009ZX01036-001-001).

TP314