石磊 田娜 康爍

摘要：動態(tài)二進制翻譯技術(shù)是構(gòu)造高性能異構(gòu)虛擬機的關(guān)鍵技術(shù)，而代碼翻譯的質(zhì)量則是動態(tài)二進制翻譯性能的關(guān)鍵。本文實現(xiàn)了一種基于LLVM動態(tài)二進制翻譯框架，利用LLVM優(yōu)化技術(shù)以及多目標(biāo)編譯的特點，實現(xiàn)了可以針對多個目標(biāo)體系結(jié)構(gòu)的高性能動態(tài)二進制翻譯。基于開源Skyeye實現(xiàn)了這種翻譯框架，并在兩種目標(biāo)體系結(jié)構(gòu)ARM和PowerPC上驗證了框架的可移植性和運行效率，與QEMU在ARM目標(biāo)平臺上做了性能對比，結(jié)果表明該模擬器比Qemu性能平均快10%以上。

關(guān)鍵詞：動態(tài)二進制翻譯；異構(gòu)虛擬機；翻譯性能；LLVM；多目標(biāo)編譯

中圖分類號：TP314文獻標(biāo)識碼：ADOI：10.19452/j.issn1007-5453.2020.08.012

基金項目：航空科學(xué)基金（2017ZD12013）

測試性驗證是指“為確定裝備是否達(dá)到規(guī)定的測試性要求而進行的試驗與評價工作”。當(dāng)前絕大多數(shù)測試驗證通過硬件來實現(xiàn)，受制于硬件條件，在硬件平臺下基于目標(biāo)碼的異常、傷害性驗證無法實現(xiàn)，軟件測試的充分性無法保證。而基于目標(biāo)碼的虛擬測試驗證則是建模仿真技術(shù)在測試性領(lǐng)域的一個具體應(yīng)用[1]，已成為驗證技術(shù)的重要發(fā)展方向之一，核心技術(shù)包括中央處理器（CPU）虛擬化、芯片虛擬化、接口虛擬化等，重點是CPU虛擬化，其實現(xiàn)目標(biāo)機與主機（PC）的即時翻譯，保證PC能夠正確識別與運行目標(biāo)機的目標(biāo)碼程序。

動態(tài)二進制翻譯技術(shù)是一種即時翻譯（JIT）技術(shù)，是把某種指令體系結(jié)構(gòu)的二進制代碼在運行過程中翻譯成另外一種指令集體系結(jié)構(gòu)的技術(shù)[2]。目標(biāo)平臺與PC體系結(jié)構(gòu)相同，則為同構(gòu)二進制翻譯器，一般有兩種用途：（1）實現(xiàn)熱點執(zhí)行路徑優(yōu)化，達(dá)到加速程序的目的，如Dynamo[3]；（2）對程序執(zhí)行行為進行剖析，達(dá)到確定程序性能瓶頸的目的，如 DynamoRIO，PIN，Valgrind等[4]。

當(dāng)翻譯目標(biāo)指令集體系結(jié)構(gòu)不同于PC指令集體系結(jié)構(gòu)，則為異構(gòu)二進制翻譯器[5]。如谷歌的Android模擬器，使用Qemu二進制翻譯技術(shù)，把ARM體系結(jié)構(gòu)翻譯成PC指令集體系結(jié)構(gòu)（X86或者X86_64）[6]，其他還包括FX！32[7]、UQDBT[8]和Walkabout[9]等。可把一個特定硬件平臺的應(yīng)用移植到另外一個異構(gòu)的硬件平臺，或者提供一個硬件平臺無關(guān)的虛擬運行環(huán)境[10]，或者利用多物理域仿真技術(shù)構(gòu)建仿真運行環(huán)境[11]。

彈載軟件大多數(shù)是嵌入式系統(tǒng)，若要實現(xiàn)目標(biāo)碼的解釋與運行，需構(gòu)建一個多目標(biāo)的異構(gòu)二進制翻譯器，實現(xiàn)對多目標(biāo)架構(gòu)所有指令集的解釋翻譯。實踐表明，由于實現(xiàn)過程的高復(fù)雜性、通用性差，需要大量的時間、人力和優(yōu)化才有可能完成[12]。

針對上述問題，利用LLVM[13]構(gòu)建一個多目標(biāo)高性能二進制翻譯器Dyncom，目標(biāo)是利用LLVM的代碼優(yōu)化和生成完成二進制翻譯過程中不同目標(biāo)架構(gòu)代碼的優(yōu)化以及生成本地指令等較為復(fù)雜又影響執(zhí)行性能的操作，實現(xiàn)多目標(biāo)、高性能翻譯的目的，生成高效的PC二進制代碼。

為了提高動態(tài)翻譯執(zhí)行性能又降低實現(xiàn)的復(fù)雜性，Dyncom的代碼優(yōu)化基于LLVM中間語言實現(xiàn)，其是一種硬件無關(guān)語言，通過優(yōu)化可用于所有不同目標(biāo)指令集體系結(jié)構(gòu)的翻譯，大幅減少對不同目標(biāo)指令架構(gòu)的優(yōu)化實現(xiàn)難度。主要有三個優(yōu)化：帶有一定閾值的混合執(zhí)行、基于蹤跡（trace）的超級塊構(gòu)造以及基于寄存器映射的冗余讀寫消除。

1 Dyncom：設(shè)計和實現(xiàn)

Dyncom以LLVM為基礎(chǔ)，包含指令翻譯和通用框架，前者把目標(biāo)體系結(jié)構(gòu)的指令集逐條翻譯為LLVM的中間語言，后者實現(xiàn)中間語言到PC指令的翻譯，總體體系結(jié)構(gòu)如圖1所示。

1.1 LLVM模塊

LLVM是一種類精簡指令集架構(gòu)的低級語言，加入一些高級語言特性，如類型系統(tǒng)、矢量表示和矢量運算等。借助類型，可對LLVM中間代碼進行直接優(yōu)化，而這在只有二進制信息的代碼上是無法做到的，類型可分為基本類型（整型、浮點型、Void類型和標(biāo)記類型等）和衍生類型（復(fù)合類型、Function類型和指針類型等）。Dyncom的中間語言為LLVM的虛擬指令集，目的是降低開源項目風(fēng)險、降低開發(fā)成本以及易于各種虛擬機的開發(fā)。

LLVM中間語言指令有50條左右，包括二元、位、矢量、內(nèi)存和終止操作指令等。例如，終止指令用于改變程序的執(zhí)行流程，內(nèi)存指令完成復(fù)雜內(nèi)存操作，二元指令用于處理支持條件執(zhí)行的架構(gòu)指令集。

1.2翻譯過程

Dyncom指令翻譯使用LLVM的虛擬指令集實現(xiàn)目標(biāo)每一條指令翻譯，是一個目標(biāo)平臺指令到LLVM指令間地址的一對多變換過程，包含三個部分：寄存器獲取與條件執(zhí)行檢查、指令主體與條件標(biāo)志更新以及寄存器寫回。首先獲取寄存器結(jié)構(gòu)體指針，獲取到相應(yīng)通用寄存器/狀態(tài)寄存器值，對于ARM架構(gòu)，通過檢查對應(yīng)狀態(tài)寄存器值決定是否執(zhí)行指令，通過指令主體完成操作映射，通過條件標(biāo)志更新完成通用寄存器值和PC更新，最后將其寫回到對應(yīng)結(jié)構(gòu)體中。

ARM和SPARC（scalable processor ARChitecture）兩條指令翻譯過程示例見表1。

指令翻譯以基本塊（basic block，BB）為粒度，使用bb表示將被分析的BB塊。第一行的SPARC指令不支持條件執(zhí)行，對add指令的翻譯按照一對多且不需要更新條件標(biāo)志的步驟實現(xiàn)。第二行的ARM指令包含條件執(zhí)行，在運行時對相應(yīng)的標(biāo)志進行判斷，變換時，首先需要加載狀態(tài)寄存器值，根據(jù)判斷指令是否執(zhí)行，其次生成兩個bb塊：L2和L3，L2包含and指令的翻譯以及執(zhí)行后Z和N標(biāo)志位的更新，L3則是PC的更新，即無論and指令是否執(zhí)行，PC都會更新。

指令翻譯是一個中間無跳轉(zhuǎn)指令的順序指令流，當(dāng)前端翻譯到函數(shù)調(diào)用、跳轉(zhuǎn)、返回指令時，即從上一個bb塊結(jié)束后的第一條指令到該條指令為止劃分為一個基本塊，Dyncom則使用指令執(zhí)行蹤跡的方式將多個基本塊組成一個包含控制流的超級塊，其具體實現(xiàn)如圖2所示。

整個翻譯過程被拆分成兩個部分，標(biāo)記（tag）和翻譯（translate），對代碼進行兩次掃描，第一遍是預(yù)先分析代碼的性質(zhì)，識別基本塊和超級塊，保存每一條目標(biāo)代碼指令的信息；第二遍對真正的掃描代碼進行翻譯。經(jīng)過統(tǒng)計，掃描代碼并打tag所占的時間是微乎其微的，會消耗一定量的內(nèi)存，但為真正的翻譯提供了必要的信息，簡化了系統(tǒng)的復(fù)雜度，降低了開發(fā)難度和風(fēng)險。翻譯完成后，將每個基本塊的地址作為哈希值記錄到哈希表中，該哈希表被稱為全局映射表，用于每個JIT執(zhí)行退出返回到Dyncom時，查找下一個要執(zhí)行的bb塊所在的JIT入口地址。

1.3執(zhí)行過程

Dyncom采用混合執(zhí)行方式，先使用解釋模式執(zhí)行目標(biāo)指令的基本塊，對執(zhí)行過的目標(biāo)指令塊做統(tǒng)計。當(dāng)發(fā)現(xiàn)某個基本塊執(zhí)行到一個閾值，認(rèn)為該基本塊是一個熱點，然后使用Dyncom進行指令翻譯，其翻譯過程如上所述。指令繼續(xù)解釋執(zhí)行直到翻譯完成，并且執(zhí)行到當(dāng)前基本塊結(jié)束，下一個跳轉(zhuǎn)的基本塊位于JIT中，此時開始動態(tài)執(zhí)行，該方法可有效利用解釋執(zhí)行時間掩蓋動態(tài)翻譯的時間過載。

JIT內(nèi)部執(zhí)行則需要依靠本地映射表的存在，用來解析基本塊的地址到本地代碼。本地映射表在JIT中為一個dispatch基本塊，其由一個大的switch指令構(gòu)成，類似于C語言的switch控制流。每次進入JIT后，就會進入該基本塊，dispatch根據(jù)PC的值確定在本地映射表中選擇需要執(zhí)行的基本塊地址并跳轉(zhuǎn)執(zhí)行，基本塊執(zhí)行完畢后再次回到dispatch塊，直到PC值不存在于本地映射表中，直接退出，將控制權(quán)交給Dyncom，通過全局映射表決定跳到下一個JIT執(zhí)行還是進行翻譯操作。至此，目標(biāo)二進制程序不斷被動態(tài)翻譯并執(zhí)行。

1.4目標(biāo)架構(gòu)ARM和PowerPC

選擇軍工領(lǐng)域常用的ARM和PowerPC架構(gòu)，用于驗證動態(tài)二進制翻譯框架對多目標(biāo)架構(gòu)的支持。通過Dyncom能夠較為容易地把ARM指令或者PowerPC指令的應(yīng)用程序翻譯為中間語言，而從中間語言翻譯到PC指令（X86或者X86_ 64）則由LLVM的后端完成。同理，如果需要支持更多目標(biāo)體系結(jié)構(gòu)，只需要把該目標(biāo)體系結(jié)構(gòu)的指令利用Dyncom翻譯為LLVM的中間指令即可，本方案可以實現(xiàn)動態(tài)二進制翻譯框架對多目標(biāo)翻譯的支持，具有良好的通用性。

2運行時優(yōu)化

2.1 JIT跳轉(zhuǎn)優(yōu)化

Dyncom動態(tài)翻譯執(zhí)行的粒度是逐塊（block-by-block）方式，每執(zhí)行完一個基本塊，就回到基本塊，通過本地映射表確定下一個跳轉(zhuǎn)塊，JIT中基本塊沒有控制流，而是構(gòu)成了一個基本塊同其他所有基本塊組成的一個樹狀結(jié)構(gòu)。LLVM對這種情況的優(yōu)化程度有限，因此，本文對跳轉(zhuǎn)類型分類，對能夠在JIT內(nèi)跳轉(zhuǎn)的情況不再調(diào)度，減少本地映射表中存儲地址的數(shù)量。

Dyncom的分支類型有兩類：直接分支是在JIT編譯時目的地址已知的分支，間接分支是在JIT編譯時未知目的地址的分支。當(dāng)翻譯到一個分支時，會有以下情況：

（1）直接分支

若目標(biāo)分支不在JIT區(qū)域內(nèi)，直接返回，由全局映射表決定執(zhí)行步驟。

（2）直接分支

若目標(biāo)分支在JIT區(qū)域內(nèi)，直接跳轉(zhuǎn)到目標(biāo)基本塊，不再調(diào)度，從本地映射表中刪除目標(biāo)項。

（3）間接分支

直接跳轉(zhuǎn)到基本塊處理。

經(jīng)過跳轉(zhuǎn)分類處理后JIT內(nèi)部能夠?qū)Ψ种D(zhuǎn)情況形成控制流，獲取更多信息，分析發(fā)現(xiàn)，優(yōu)化跳轉(zhuǎn)后JIT代碼體積明顯變小，性能有一定提升。

2.2全局寄存器映射

雖然LLVM中間表示（IR）提供了無窮虛擬寄存器，但其是靜態(tài)單一賦值（SSA）形式，且目標(biāo)架構(gòu)的寄存器運行時狀態(tài)值會一直變化，很難維護運行時狀態(tài)，因此不能把每個目標(biāo)架構(gòu)的寄存器都匹配到一個LLVM寄存器。Dyncom通過指針將寄存器結(jié)構(gòu)體傳入JIT，每次獲取寄存器值時，首先獲取相應(yīng)寄存器對應(yīng)的地址，再通過加載指令獲取到對應(yīng)的值。分析發(fā)現(xiàn)，生成的IR中包含大量的地址計算，屬于冗余指令。

使用LLVM的alloca指令實現(xiàn)JIT基本的寄存器的映射，用于在程序棧上分配空間給局部變量，一般用于處理函數(shù)參數(shù)。在JIT的entry基本塊，首先獲取所有寄存器對應(yīng)的地址，其次使用alloca指令分配?？臻g并將寄存器地址存入后，再次讀取該棧空間的值，后續(xù)使用時，直接通過load指令讀取該地址的值即可，該優(yōu)化可減少每次獲取寄存器值時需要的地址計算，且只在entry基本塊中存儲和加載。

2.3基本塊粒度冗余指令消除

經(jīng)過全局映射優(yōu)化處理后的JIT，雖然地址計算大大減少，但在基本塊中，對于寄存器狀態(tài)的處理過程一般為在基本塊起始位置讀入寄存器到內(nèi)存的臨時變量中，然后對其進行操作，在基本塊運行結(jié)束之前再將對應(yīng)臨時變量的值寫回到原有寄存器，而且指令與指令操作數(shù)之間原有的依賴導(dǎo)致通過LLVM原有的優(yōu)化策略無法消除由于SSA形式產(chǎn)生冗余指令的情況。

本文是針對單一執(zhí)行流的基本塊進行冗余指令的優(yōu)化，更大范圍的交由LLVM處理。翻譯過程中，為每個基本塊建立一個LLVM虛擬寄存器到目標(biāo)寄存器的映射表，每次加載寄存器之前，先掃描映射表，若表中沒有，則加載，并存入到表中，若存在，則直接使用。寫回寄存器之前，同樣掃描映射表，若表中沒有，則存入；否則，更新表中存在的值。當(dāng)基本塊翻譯結(jié)束時，將表中所有已標(biāo)記值寫回到對應(yīng)寄存器，同時清空映射表。該項優(yōu)化減少了大量包含依賴關(guān)系的load/store指令，性能提升較大。

3試驗以及評估

為評估Dyncom的性能，進行對比試驗，試驗環(huán)境見表2。

使用基于LLVM 2.8的Skyeye 1.3.4-rc1同QEMU 2.0.0進行性能比對測試，測試用例為EEMBC的cjpeg1000，運行結(jié)果以時間秒為單位，為了減少誤差，樣本運行100次，并取平均值。運行結(jié)果見表3，結(jié)果顯示，優(yōu)化后平均性能比QEMU高10%以上。

4結(jié)論

本文首先闡述了動態(tài)二進制翻譯的基本概念，說明Dyncom使用LLVM作為動態(tài)二進制翻譯框架的原因。其次，分析Dyncom的實現(xiàn)框架和工作原理，詳述翻譯過程和執(zhí)行過程，并在LLVM IR層次實現(xiàn)跳轉(zhuǎn)優(yōu)化和基本塊粒度的冗余消除優(yōu)化，提升了性能。最后，通過與QEMU進行對比，證明基于LLVM的Dyncom動態(tài)翻譯的高性能，以及多目標(biāo)翻譯框架代碼的可實現(xiàn)性。

相比于QEMU，Dyncom只關(guān)注目標(biāo)體系架構(gòu)到LLVM中間指令的翻譯過程，中間語言到PC體系架構(gòu)的指令翻譯由LLVM自動完成。在最新的LLVM 10.0版本中，LLVM支持常用的ARM、PowerPC、X86、RiscV等不同的體系結(jié)構(gòu)，幾乎不用做任何移植工作，即可把目標(biāo)體系架構(gòu)翻譯為LLVM支持的數(shù)十種后端體系結(jié)構(gòu)，但QEMU支持新的PC體系結(jié)構(gòu)則需要大量的手動翻譯的編碼實現(xiàn)，由此可見，Dyncom的可移植性遠(yuǎn)高于QEMU。

Dyncom在冗余消除粒度上仍然過小，JIT中仍然有很多冗余指令，由于其操作數(shù)跨基本塊使用，導(dǎo)致無法對其進行刪除，另外由于局部映射表對所有的基本塊都進行了存儲，也限制了處理能力，本文后續(xù)將從這兩點入手進行優(yōu)化。

參考文獻

[1]張勇，邱靜，劉冠軍，等.面向測試性虛擬驗證的功能-故障-行為-測試-環(huán)境一體化模型[J].航空學(xué)報，2012，33（2）：273-286. Zhang Yong， Qiu Jing， Liu Guanjun， et al.Integrated functionfault-behavior-test-environment model for virtual testability verfication[J]. Acta Aeronautica et Astroautica Sinica， 2012，33（2）：273-286.（in Chinese）

[2]Tom S，Harry W，Bj？rn F，et al. Efficient code generation in a region-based dynamic binary translator[C]// LCTES 14：Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages，Compilers and Tools for Embedded Systems. Edinburgh，United Kingdom，2014：3-12.

[3]Hsu C C，Liu P，Wu J J，et al. Improving dynamic binary optimization through early-exit guided code region formation[C]// Proceedings of the 9th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. New York，United States，2013：23-32.

[4]Rodríguez R J，Artal J A，Merseguer J. Performance evaluation of dynamic binary instrumentation framework[J]. IEEE LatinAmerica Transactions，2014，12（8）：1572-1580.

[5]Hsu C C，Liu P，Wang C M，et al. Lnq：Building high performance dynamic binary translators with existing compiler backends[C]// 2011 International Conference on Parallel Processing. Taipei，Taiwan，2011：226-234.

[6]Hsu C C，Hong D Y，Hsu W C，et al. A dynamic binary translation system in a client/server environment[J]. Journal of SystemsArchitecture，2015，61（7）：307-319.

[7]李劍慧，馬湘寧，朱傳琪.動態(tài)二進制翻譯與優(yōu)化技術(shù)研究[J].計算機研究與發(fā)展， 2007， 44（1）： 161-168. Li Jianhui， Ma Xiangning， Zhu Chuanqi. Dynamic binary translation and optimization[J]. Journal of Computer Research and Development， 2007， 44（1）： 161-168.（in Chinese）

[8]Ung D，Cifuentes C. Dynamic binary translation using runtime feedbacks[J]. Science of Computer Programming，2006，60（2）：189-204.

[9]Cristina C，Brian L，David U. Walkabout：A retargetable dynamic binary translation framework[R]. Forth Workshop on Binary Translation. Virginia，United States，2002：1-30.

[10]董衛(wèi)宇，劉金鑫，戚旭衍，等.基于熱例程的動態(tài)二進制翻譯優(yōu)化[J].計算機科學(xué)， 2016 （5）：27-41. Dong Weiyu， Liu Jinxin， Qi Xuyan， et al. Hot-routine based optimization of dynamic binary translation[J]. Computer Science， 2016 （5）： 27-41.（in Chinese）

[11]聶同攀.基于模型的機電系統(tǒng)多物理域仿真技術(shù)應(yīng)用研究[J].航空科學(xué)技術(shù)， 2017（7）：68-72. Nie Tongpan. The simulation technology application research ofmodel-basedelectromechanicalsystemsmuti-physical domain[J].Aeronautical Science & Technology，2017（7）：68-72.（in Chinese）

[12]陳頊顥，鄭重，沈立，等.二進制翻譯中代碼生成的子圖覆蓋算法[J].計算機科學(xué)與探索， 2011， 5（7）：613-623. Chen Xuhao， Zheng Zhong， Shen Li， et al. Subgraph covering for efficient code generation in binary translation[J]. Journal of Frontiers of Computer Science and Technology， 2011， 5（7）： 613-623.（in Chinese）

[13]Carsten S，F(xiàn)lorian M，Stephan F. LLBMC：a bounded model checkerforLLVMsintermediaterepresentation[C]// International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Tallinn，Estonia，2012：542-544.（責(zé)任編輯陳東曉）

作者簡介

石磊（1978-）男，碩士，高級工程師。主要研究方向：彈載軟件測試驗證技術(shù)。

Tel：15538868517

E-mail：smxsuperboy@126.com

田娜（1983-）女，學(xué)士，工程師。主要研究方向：嵌入式系統(tǒng)、處理器驗證。

Tel：13501153049

E-mail：tianna@digiproto.com

康爍（1978-）男，碩士，工程師。主要研究方向：處理器仿真及驗證，軟件安全。

Tel：13651119140

E-mail：ksh@skyeye.org

LLVM-Based Multiple Targets High-Performance Dynamic Binary Translation Framework

Shi Lei1，*，Tian Na2，Kang Shuo3

1. China Air to Air Missile Research Institute，Luoyang 471000，China

2. Beijing Digiproto Technology Co.，Ltd.，Beijing 100085，China

3. Research Institute of Information Technology，Tsinghua University，Beijing 100084，China

Abstract： Dynamic binary translation is a key technology of constructing high-performance heterogeneous virtual machine， while the quality of the code translation is the key of dynamic binary translation performance. An LLVMbased dynamic binary translation framework is implemented. Utilizing LLVM optimization technology and the features of multiple target compiling， the high performance dynamic binary translation for multiple target architectures is implemented. The dynamic binary translation framework is implemented based on open source software Skyeye. The portability and performance were verified on two target architectures ARM and PowerPC. Compared with Qemu on ARM target platform， experiment results show that the average performance is faster than QEMU by over 10%.

Key Words： dynamic binary translation； heterogeneous virtual machine； translation performance； LLVM； multiple targets translation