二進制翻譯中冗余指令優化算法

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

(數學工程與先進計算國家重點實驗室 鄭州 450002)

二進制翻譯中冗余指令優化算法

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

(數學工程與先進計算國家重點實驗室 鄭州 450002)

(jessie_tanjie@hotmail.com)

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

二進制翻譯；冗余指令；活性分析；窺孔優化；SQEMU框架

二進制翻譯技術是實現軟件移植的主要方法，現已廣泛應用于遺產代碼移植、系統安全防護等國內外諸多領域，是解決不同體系結構處理器之間軟件移植的主要途徑，如開源的跨平臺動態二進制翻譯器QEMU[1]，已被移植到多種處理器平臺，其中包括國產龍芯平臺[2].

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

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

因此，本文以SQEMU作為靜態二進制翻譯平臺，對生成的目標代碼中常規冗余指令和冗余存取LOADSTORE指令進行優化，通過分析目標碼生成指令特定數據依賴圖(instruction-specific data dependence graph, IDDG)，再利用該圖將活性分析和窺孔優化的2種理論相結合，提出基于IDDG的冗余指令刪除優化算法，有效刪除目標碼中冗余指令，以達到提高目標代碼執行效率的目的.

本文的主要工作有4點：

1) 針對動態二進制翻譯器QEMU因其翻譯過程受動態執行的限制而不能進行深度細致優化等缺點，以及現有靜態二進制翻譯器難以處理間接分支的現狀，提出一種基于QEMU的靜態二進制翻譯框架SQEMU，SQEMU能夠分離翻譯時間、代碼優化時間與目標程序執行時間，并且代碼優化的時間不受運行時的限制，能夠采用不同層次的優化算法，使得SQEMU生成的目標代碼質量更高.

2) 將SQEMU后端生成的目標代碼作為輸入參數，利用指令寄存器之間存在的數據依賴關系，生成指令特定數據依賴圖(IDDG)，將圖理論靈活運用到冗余代碼優化過程中，拓展了處理冗余代碼的手段.

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

4) 本文提出的算法雖然是針對基于QEMU的靜態二進制翻譯框架SQEMU后端目標碼實現的，但該算法具有相當強的通用性，不限于目標平臺和指令形式，對降低二進制翻譯后的代碼膨脹率有重要意義.

1 基于QEMU的靜態翻譯框架——SQEMU

QEMU系統是目前較為先進的可實現多種異構平臺映射的動態二進制翻譯系統，具有支持平臺多樣、翻譯效率相對較高、開源易移植等優點[11].QEMU為實現多源多目標虛擬機，采用將源二進制代碼翻譯為TCG中間代碼再翻譯為目標代碼的方式，可以實現將X86，ARM，MIPS下的ELF格式可執行文件翻譯為TCG中間表示，再翻譯為目標代碼.

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

SQEMU包括前端源指令提取、TCG中端分析優化、后端目標代碼生成3個階段，基本設計結構如圖1所示.其中，源文件解析器、前端解碼器構成SQEMU前端，負責將源平臺二進制代碼(本文即X86代碼)翻譯成中間代碼TCG(tiny code generator)，TCG中端分析優化器對中間表示進行平臺無關優化，后端翻譯器負責將TCG中間代碼翻譯成目標平臺的二進制代碼(本文中為Alpha代碼).前端和TCG中端分析優化器采用QEMU的相應模塊，刪除了QEMU中控制中心、緩存管理和執行模塊，后端添加了目標文件生成器.

Fig. 1 Framework of SQEMU圖1 SQEMU框架設計

其中，前端解碼器逐條對源平臺指令進行解碼，SQEMU使用了QEMU的指令譯碼部分，根據譯碼器分析出的指令，生成相同語義的TCG指令.傳統的優化策略僅在TCG分析優化器中針對TCG中間代碼層進行平臺無關優化[12]，如活性分析和塊內寄存器分配.而事實上由于僅靠軟件翻譯，一條X86指令翻譯后經TCG中間代碼優化后仍會生成多條Alpha代碼，其中含有大量冗余指令和冗余訪存操作，執行效率很低.針對這一現狀，本文在目標代碼層實現冗余代碼優化.

2 冗余指令的發現

SQEMU系統后端生成的Alpha代碼的冗余是影響代碼膨脹的最直接因素，通過分析SQEMU后端生成的Alpha代碼，原SQEMU系統并沒有對目標碼進行冗余刪除的優化，其中存在少量含有非活躍變量的常規指令和大量冗余訪存指令，本節著重描述冗余訪存指令.

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

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

通過對SQEMU的后端編碼器按TCG中間表示生成的目標平臺代碼進行語義分析，通過提取操作碼和寄存器，總結歸納出其執行特性，發現其中含有大量如表1所示的冗余指令對.

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

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

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

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

Table 1 Redundancy Types of Instruction

3 冗余指令的優化思路

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

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

結合實驗室目前的研究成果，在實際處理間接跳轉指令時，本文在靜態二進制翻譯框架SQEMU的基礎上，使用文獻[13]提出的執行路徑逆向構造算法和特定路徑的控制執行算法，利用線性掃描反匯編工具objdump處理待翻譯程序，獲得逆向構造所需匯編指令，進而定位出靜態二進制翻譯中影響基本塊劃分的間接跳轉指令目標地址.

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

3.1 針對常規冗余指令的優化

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

在生成數據依賴圖以前，先給出以下相關定義:

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

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

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

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

定義5. 依賴關系.對于計算機程序，當事件或動作A必須先于事件B而發生時，稱B依賴于A.

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

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

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

活性分析理論是一種全局數據流分析，在此，我們將活性分析理論用于基本塊內任意路徑數據流分析，從全局范圍來看一個變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當前值還要被引用.

針對SQEMU后端代碼的活性分析算法是以基本塊為單位逆向線性掃描生成的目標碼，分析目標碼并生成指令相關節點，確定節點之間的數據依賴關系即源寄存器和目的寄存器之間的使用關系，根據源寄存器在執行本條指令后基本塊后續指令是否改變寄存器的值來判斷寄存器的活躍性.通過對目標碼的活性分析，就能識別出當前值不再活躍的那些寄存器.若該條語句中寄存器均失去活性，則可判定為冗余代碼.

令S為基本塊內一條語句，定義F(S)為基本塊內語句S的前驅語句集合，N(S)為語句S的后繼語句集合,則根據定義6中規定的數據依賴關系一定存在至少一個寄存器x使得：

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

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

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

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

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

(1)

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

也就是說，一個基本塊內，某條指令之前的語句其目的寄存器是活躍的僅當該條指令后繼指令源寄存器為活躍的.如果該指令沒有后繼，則其LiveOut為空.

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

LiveIn(S)?Use(S).

(2)

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

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

(3)

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

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

(4)

式(4)對于基本塊內每條語句均成立.

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

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

(5)

設靜態二進制翻譯目標碼中指令規則為∏，定義指令輸入變量數、輸出變量數、變量總數等性質，∏in(S)表述語句S這條指令輸入變量數，∏out(S)表示該指令輸出變量數，∏all(S)表示該指令變量總數，N表示基本塊內語句總數.

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

② 否則，該指令對變量重定：

(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)

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

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

Use(j)=Use～(S).

(9)

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

.

(10)

(11)

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

失去活性的寄存器所在指令用“#”標識，不再翻譯成目標指令.將生成的指令相關節點以基本塊為單位存儲在數組charbb[][BBCOLUMS]中，用指針STLD_INFO *temp逆向順次移動.為標識基本塊內寄存器的所有使用情況，開辟一個大小為基本塊寄存器總體數量的數組空間，并初始化為1，表示基本塊內寄存器全部為非活躍.然后利用指針STLD_INFO *temp對生成的指令相關節點進行分析，判斷指令目標寄存器對應在數組空間是否標記為1：

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

2) 若不全為1，將指令的源寄存器和目的寄存器對應在數組空間的值標記清0，表明寄存器是活躍的.

依次循環迭代直到基本塊入口點，完成整個基本塊的寄存器活性分析.

Table 2 Usage Rule of Register

算法1.活性分析算法.

① 初始化基本塊內寄存器； 將所有特殊寄存器標記為活，即0； 將一般寄存器標記為死，即1； 設基本塊總共有n條語句；

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

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

④ end for

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

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

⑦ end if

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

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

⑩ else

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

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

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

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

3.2 針對訪存冗余指令的優化

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

窺孔優化是一種局部優化方法，其基本原理是通過考察編譯器所生成的目標代碼中一小段相鄰指令(稱為窺孔)，比如一個基本塊中的目標碼，通過整體分析和指令轉換，把這些指令替換為更短和更快的一段指令，以此來提高代碼質量.

美國Stanford大學的靜態二進制翻譯器利用窺孔優化對目標代碼實施高質量的等價替換，獲得了更為優化的執行效率.窺孔優化一般包括冗余訪存指令的刪除、不可達代碼的刪除、控制流優化、強度削弱等.由于窺孔優化需要對目標碼進行若干遍處理，開銷較大，較少應用在動態二進制翻譯中，是靜態二級制翻譯和編譯器的常用優化手段.雖然代碼轉換限于局部，只需很少訪問內存，但可能會帶來很大性能提升.

從SQEMU系統生成的后端Alpha代碼中隨機抽取一段目標碼如圖5所示：

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

Table 3 Input and Output Variables Set

Fig. 6 Instruction-specific data dependence graph圖6 指令特定數據依賴圖

指令相關節點包含了指令的特性，如操作碼、立即數段、寄存器段，一個節點Si與預先定義的LOADSTORE指令格式相匹配，根據IDDG，由節點間定向性依賴邊可對節點Si與其目標節點Sj之間的數據依賴關系依據冗余指令匹配類型進行以下分類判定：

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

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

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

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

其中i

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

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

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

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

其中i

4 冗余指令優化算法

本文提出的優化方法是基于IDDG實現的，將針對常規冗余指令活性分析與冗余訪存在指令窺孔優化相結合，實現對目標碼冗余指令的優化刪除算法.

根據第2節和第3節的分析，SQEMU系統生成后端Alpha代碼仍存在大量冗余，影響編譯效率，對此，本文提出一種靜態二進制翻譯冗余目標代碼刪除優化算法，對基本塊內冗余代碼進一步分析.在經過控制流分析和數據流分析之后，其方法為只需要記錄每次循環迭代基本塊內一條ldl或stl指令和寄存器被重寫指令序號，每當記錄一條新的ldl和stl指令時，遍歷已經記錄的ldl和stl指令，2條匹配的ldl或stl指令之間若不存在寄存器被重寫的情況，即可判斷為冗余指令，過程如下：

1) 從SQEMU系統后端生成的Alpha代碼中順次獲取相應的指令信息，如操作碼、寄存器和立即數等，根據指令特性以及相鄰目標碼間寄存器的使用關系，生成指令相關節點和指令特性數據依賴圖IDDG，對基本塊內寄存器進行活性分析，失去活性的寄存器所在指令用“#”標識，不再翻譯成目標指令.將生成的指令相關節點以基本塊為單位存儲在數組charbb[][BBCOLUMS]中，創建一雙鏈表記錄基本塊內ldl和stl指令序號，指令類型和全局變量的偏移量.

算法流程如圖7所示：

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

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

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

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

若出現以上2種情況之一，下一步可依據IDDG確定2條指令節點之間的數據依賴關系，判斷匹配的2條語句之間是否存在其他指令節點與這條指令節點形成輸出依賴關系，即2條語句之間是否存在對寄存器重新賦值的新指令，同時遍歷該寄存器所在單鏈表，依據指令序號確認這條新指令是否在2條匹配的指令之間.若存在，則2條已匹配的指令并不是冗余訪存指令，可將待插入指令直接插入雙鏈表中，待后續指令與其匹配；若不存在，則待插入指令即可判斷為冗余訪存指令，同時用“#”標識該條指令，進而完成整個冗余訪存指令刪除的優化過程.

5 實驗與分析

為驗證冗余訪存優化算法的實際優化效果，采用上述SQEMU作為靜態二進制翻譯平臺，通過正確性測試、整體性能測試和測試數據分析對提出的算法進行評估.

5.1 實驗環境

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

2) 源平臺.32位X86平臺，Fedora11 Linux 2.6.29.4，gcc 4.4.0.

3) 目標平臺.64位Alpha平臺，中標麒麟Linux 3.8.0，gcc 4.3.0.

5.2 正確性測試

在X86平臺上編譯SPEC CPU2006和nbench測試集，啟動優化后的SQEMU，輸入編譯好的X86測試集可執行文件，從調試信息獲取執行結果.實驗顯示本算法翻譯執行的結果與SPEC CPU2006和nbench正確執行時的結果一致，說明本算法能夠進行正確的翻譯，具有較高可信度.

5.3 整體性能評價

為體現冗余訪存優化算法對SQEMU整體性能的提高效果，分別統計算法改進前后SQEMU翻譯執行nbench和SPEC CPU2006測試集性能指標.

對nbench測試集進行測試，記SQEMU優化前執行性能指標為I1，SQEMU優化后性能指標為I2，性能指標單位為iterations，即每秒循環次數.加速比記作I2I1.

對基準測試集SPEC CPU2006進行測試，由于C++程序間接調用情況更復雜更頻繁，是影響靜態二進制翻譯性能的主要瓶頸之一，未選取C++程序進行對比.且不同語言程序所需編譯器不同，為增加數據可比性，對SPEC CPU2006采用其中C程序作測試用例.分別統計算法改進前后SQEMU翻譯執行SPEC CPU2006所用時間，記SQEMU優化前執行時間為T1，SQEMU優化后執行時間為T2，加速比記作T1T2.

從上述測試結果中可以發現，基準測試集SPEC CPU2006和nbench測試集在優化后執行效率明顯提升，測試用例不同其性能提升的效果也不同.由表4及圖8中數據可得，通過采用針對冗余訪存指令的優化算法可使得nbench測試集性能提升6%～42%，且平均性能提升約為20%；由圖9中數據發現使用優化算法后SPEC CPU2006測試集性能提升1%～32%，SPEC CINT2006平均性能提升約17%，SPEC CFP2006平均性能提升僅約為5%.從實驗結果中不難發現，該算法具有明顯的優化效果.

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 測試數據分析

從表4針對nbench測試集得出的測試結果以及圖8和圖9中分別針對nbench和SPEC CPU2006測試用例所得加速比中發現，測試用例不同，加速比也不同，該冗余指令優化算法對不同程序的優化程度也不盡相同.由此推斷，優化效果與程序自身指令特性和程序任務相關.

分別統計nbench和SPEC CPU2006測試集中選取的測試用例在優化前和優化后的指令總數，得到如圖10、圖11所示柱狀圖.分析柱狀圖中指令總數，并設優化效益為γ，則有公式：

不難發現，nbench執行時間的加速比與指令的優化效益成正相關，由此可推斷，冗余指令越多，被優化掉的指令數也越多，優化效益γ也越大，最終獲得的執行時間的加速比也越大，即冗余指令刪除算法的效果更明顯.而SPEC CPU2006由于其規模較大、測試集較為復雜、間接跳轉指令數較多等原因，執行時間的加速比與指令的優化效益γ并不完全正相關.

Fig. 10 nbench instruction number圖10 nbench指令數

Fig. 11 SPEC CPU2006 instruction number圖11 SPEC CPU2006指令數

首先分析nbench測試用例任務，如表5所示：

Table 5 nbench Tasks

下面對nbench測試加速比最小的測試用例FP EMULATION與所得加速比最大的前3個測試用例BITFIELD,NUMERIC_SORT,STRING_SORT進行深入分析.

1) 查看加速比最小的FP EMULATION源碼發現，該測試用例內包含3個主要函數：DoFPU-TransIteration，TrapezoidIntegrate，thefunction.分別統計3個函數優化后各自的指令數，并計算其占FP EMULATION指令總數的百分比，如圖12所示.FP EMULATION測試用例中主要占用執行時間的函數是DoFPUTransIteration，且其指令數也最多，而DoFPUTransIteration函數中主要操作為模擬基本數學運算，主要涉及memmove，與優化算法關系不大.

Fig. 12 Ratio of FP EMULATION instruction number圖12 FP EMULATION指令數比例

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

3) NUMERIC_SORT和STRING_SORT加速比分別為1.373和1.222，NUMERIC_SORT實現對32位整型數組排序的任務，而STRING_SORT實現的任務是對任意長度字符串數組的排序，這2個測試用例使用整型寄存器和通用寄存器較多，如果2條指令使用同一寄存器，則極大可能產生冗余存取指令.而冗余指令刪除優化算法主要針對冗余存取指令，所以優化效果也比較好.

其次分析基準測試集SPEC CPU2006，利用執行路徑逆向構造算法和特定路徑的控制執行算法定位出阻礙靜態二進制翻譯間接跳轉指令的目標地址.針對基準測試集SPEC CPU2006分別統計出其間接跳轉指令數和間接調用指令數，如表6所示.

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

Table 6 Indirect Branch Instruction Test Results

從測試用例類型來看，SPEC CINT2006平均性能提升程度接近nbench測試集，而SPEC CFP2006遠低于nbench.由于SPEC CFP2006浮點測試用例中熱代碼主要是浮點指令，SQEMU使用函數模擬浮點指令的功能，該算法對此類指令優化效果較差.

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

6 相關研究

文獻[14-15]中針對TCG使用大量臨時變量來處理指令數據運算與傳遞，QEMU引入寄存器活性分析優化技術和存儲轉發優化技術來刪除中間表示中存在的冗余變量，減少中間表示指令，降低代碼的膨脹率，但是中間表示優化對整體翻譯性能提升程度有限且仍存在冗余指令.

文獻[4]中為了提高翻譯后代碼的質量，使用改進LLVM編譯器針對生成的LLVM中間代碼進行優化，其中包括增加寄存器優化和標量運算矢量化等，和QEMU相比，這種優化過程卻導致整體翻譯效率損失超過60倍，為了降低優化開銷，HQEMU卸載了在多核系統中的其他硬件線程或內核的優化過程，嚴重降低了系統吞吐量.

文獻[2]中引用活性分析技術對QEMU后端MIPS冗余MOVE指令提出了刪除算法，優化了目標代碼的冗余指令，但僅僅針對冗余MOVE指令，優化方法過于單一，不能取得較完備的優化效益.

文獻[16]中針對動態翻譯時高速緩存負荷數倍膨脹導致翻譯器性能下降的問題，提出基于指令高速緩存與數據高速緩存訪問負荷動態均衡的軟硬件協同翻譯方法，該方法主要為處理器設計高速緩存負荷平衡狀態和負荷轉化通道，通過軟硬件協同配合的方式把調度器地址轉換操作在指令高速緩存上產生的負荷轉化到數據高速緩存，有效提高了數據高速緩存的利用率和動態翻譯器性能.但并未提及對大量冗余代碼造成代碼膨脹導致翻譯器性能下降的處理.

7 結束語

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

[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)(宋強. 基于龍芯的二進制翻譯器QEMU優化研究[D]. 合肥: 中國科學技術大學, 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)(李劍慧, 馬湘寧, 朱傳琪, 等, 動態二進制翻譯與優化技術研究[J]. 計算機研究與發展, 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的跨平臺靜態二進制翻譯系統[J]. 浙江大學學報, 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仿真器的指令優化技術的研究與實現[D]. 成都: 電子科技大學, 2013)

[13]Wu Weifeng. Research on completeness of static binary translation and analysis of code[D]. Zhengzhou: PLA Information Engineering University, 2012 (in Chinese)(吳偉峰. 靜態二進制翻譯完備性及代碼分析研究[D]. 鄭州: 解放軍信息工程大學, 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)(李戰輝, 劉暢, 孟建熠, 等. 基于高速緩存負荷均衡的動態二進制翻譯研究[J]. 計算機研究與發展, 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]. 計算機研究與發展, 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

國家自然科學基金項目(61472447)；國家“八六三”高技術研究發展計劃基金項目(2009AA012201)；“核高基”國家科技重大專項基金項目(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