基于LLVM的多目標高性能動態二進制翻譯框架

石磊 田娜 康爍

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

關鍵詞：動態二進制翻譯；異構虛擬機；翻譯性能；LLVM；多目標編譯

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

基金項目：航空科學基金（2017ZD12013）

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

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

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

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

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

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

1 Dyncom：設計和實現

Dyncom以LLVM為基礎，包含指令翻譯和通用框架，前者把目標體系結構的指令集逐條翻譯為LLVM的中間語言，后者實現中間語言到PC指令的翻譯，總體體系結構如圖1所示。

1.1 LLVM模塊

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

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

1.2翻譯過程

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

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

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

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

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

1.3執行過程

Dyncom采用混合執行方式，先使用解釋模式執行目標指令的基本塊，對執行過的目標指令塊做統計。當發現某個基本塊執行到一個閾值，認為該基本塊是一個熱點，然后使用Dyncom進行指令翻譯，其翻譯過程如上所述。指令繼續解釋執行直到翻譯完成，并且執行到當前基本塊結束，下一個跳轉的基本塊位于JIT中，此時開始動態執行，該方法可有效利用解釋執行時間掩蓋動態翻譯的時間過載。

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

1.4目標架構ARM和PowerPC

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

2運行時優化

2.1 JIT跳轉優化

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

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

（1）直接分支

若目標分支不在JIT區域內，直接返回，由全局映射表決定執行步驟。

（2）直接分支

若目標分支在JIT區域內，直接跳轉到目標基本塊，不再調度，從本地映射表中刪除目標項。

（3）間接分支

直接跳轉到基本塊處理。

經過跳轉分類處理后JIT內部能夠對分支跳轉情況形成控制流，獲取更多信息，分析發現，優化跳轉后JIT代碼體積明顯變小，性能有一定提升。

2.2全局寄存器映射

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

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

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

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

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

3試驗以及評估

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

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

4結論

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

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

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

參考文獻

[1]張勇，邱靜，劉冠軍，等.面向測試性虛擬驗證的功能-故障-行為-測試-環境一體化模型[J].航空學報，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]李劍慧，馬湘寧，朱傳琪.動態二進制翻譯與優化技術研究[J].計算機研究與發展， 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]董衛宇，劉金鑫，戚旭衍，等.基于熱例程的動態二進制翻譯優化[J].計算機科學， 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]聶同攀.基于模型的機電系統多物理域仿真技術應用研究[J].航空科學技術， 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].計算機科學與探索， 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，Florian 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.（責任編輯陳東曉）

作者簡介

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

Tel：15538868517

E-mail：smxsuperboy@126.com

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

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