王 軍 龐建民 傅立國 岳 峰 單 征 張家豪

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

二進制翻譯[1]是一種即時編譯技術(shù)，其核心目標是將一種體系結(jié)構(gòu)的指令序列轉(zhuǎn)換成功能等價的另一種可執(zhí)行指令序列，已廣泛用于軟件安全分析[2-3]、程序行為分析[4]、軟件逆向工程、系統(tǒng)虛擬等領(lǐng)域，并已成為軟件移植[5]的主流技術(shù)之一.二進制翻譯的過程可分為前端解碼、中間優(yōu)化以及后端編碼3個部分.前端解碼的主要工作類似于反匯編，依據(jù)源指令的特點分離出每條機器指令，將二進制可執(zhí)行程序翻譯成中間代碼；中端優(yōu)化的主要工作是優(yōu)化生成的中間代碼，通過分析中間代碼組織關(guān)系簡化中間代碼，常用的冗余代碼消除方法有常量傳播[6]、變量活性分析[7]和標志位優(yōu)化等[8]；后端編碼的主要工作是本地目標代碼的生成，將優(yōu)化后的中間代碼轉(zhuǎn)換生成本地可執(zhí)行的代碼序列，其中包含寄存器分配過程.

寄存器分配無論是在高性能應(yīng)用程序編譯，還是在高性能程序翻譯，又或者在充分利用高性能處理器的目標上，都有著重要的研究意義，好的寄存器分配方式可以有效提高程序執(zhí)行效率.寄存器分配的目的是盡可能地將程序中的值保存在寄存器中，從而最大限度地減少訪存次數(shù)，提高程序的執(zhí)行效率，寄存器分配優(yōu)化的重點在如何處理寄存器溢出問題.

不同于傳統(tǒng)編譯器中的寄存器分配，二進制翻譯中寄存器分配的實質(zhì)更像是寄存器映射，需要重點考慮源平臺寄存器使用情況.目前常用的寄存器分配方法主要是寄存器圖著色法、線性掃描法以及基于這2種方法的優(yōu)化變種.二進制翻譯，尤其是動態(tài)二進制翻譯最常采用基于線性掃描的寄存器分配方法.

目前，已有較多人針對二進制翻譯中的寄存器分配進行了研究.Liang等人[9]對動態(tài)二進制翻譯器QEMU(quick emulator)中寄存器的管理及分配機制進行了詳細的描述，但并未給出一種有效的改進方法；吳浩[10]通過對比實驗說明了中間表示降低了二進制翻譯的性能，并在x86平臺翻譯ARM程序時采用寄存器直接映射策略提高了翻譯效率，但是該方法需要大幅度地修改QEMU的翻譯機制且通用性不強.文延華等人[11]在Alpha平臺翻譯PowerPC程序時，對PowerPC中的特殊寄存器采用二進制翻譯模擬、提出分段映射和特殊寄存器裁剪相結(jié)合的方法獲得了一定的優(yōu)化效果，但寄存器裁剪函數(shù)較為復(fù)雜且可被優(yōu)化的程序較少；廖銀等人[12]在MIPS平臺模擬x86平臺寄存器時采用直接映射策略，利用本地平臺通用寄存器數(shù)量多的特點，直接將x86的8個通用寄存器一一映射到MIPS的通用寄存器上，簡化了指令翻譯的規(guī)則，降低了代碼膨脹率，但該方法依賴于特定的硬件基礎(chǔ)，通用性和可移植性不夠強；Cai等人[13]在cross-bit系統(tǒng)中提出了簡化的寄存器圖著色法，使用3個鏈表收集變量定值引用信息，將活躍變量構(gòu)造成一個圖，之后遇到寄存器溢出情況則重新構(gòu)造沖突圖，但沖突圖的構(gòu)造大大增加了翻譯的開銷，整體的效率提升有限；Liang等人[14]基于QEMU的中間表示，分析變量的定值與引用，使用鏈表存儲變量的生命周期和使用情況，減少了中間表示指令數(shù)目，但由于需要多次遍歷采集基本塊內(nèi)變量的定值與引用信息，算法的復(fù)雜度較高且不具有良好的移植性.

本文結(jié)合QEMU[15]的翻譯原理、QEMU使用的中間表示TCG (tiny code generation)中臨時變量與寄存器分配之間的關(guān)系以及QEMU的寄存器分配機制[9]，引入全局寄存器靜態(tài)映射和局部寄存器動態(tài)分配思想[16]，提出了基于優(yōu)先級的動靜結(jié)合二進制翻譯寄存器分配優(yōu)化算法.首先，根據(jù)x86平臺應(yīng)用程序各寄存器使用情況的整體統(tǒng)計數(shù)據(jù)進行全局寄存器靜態(tài)映射；然后依據(jù)基本塊內(nèi)中間表示每條指令需求的寄存器數(shù)量及寄存器分配次數(shù)，排序確定各寄存器在基本塊內(nèi)分配的優(yōu)先級順序，動態(tài)分配寄存器；最后溢出循環(huán)塊內(nèi)未使用的全局寄存器供局部變量使用，并將全局寄存器的維護放在循環(huán)之外，盡可能減少因寄存器溢出而導(dǎo)致的冗余訪存指令，尤其是循環(huán)體內(nèi)的冗余訪存指令，提高程序的執(zhí)行效率.

1 相關(guān)工作

QEMU是一個廣泛使用的支持用戶級和系統(tǒng)級翻譯的多源到多目標的動態(tài)二進制翻譯系統(tǒng)[15].QEMU的動態(tài)翻譯過程如圖1所示，其中寄存器分配工作在QEMU翻譯后端進行.

Fig. 1 QEMU translation process圖1 QEMU翻譯過程

為了實現(xiàn)多源到多目標的翻譯，QEMU中采用了機器無關(guān)的中間表示TCG.基于TCG，不同源平臺只需要變換前端解碼器而不需要改動后端編碼器，即可實現(xiàn)多源到目標平臺的翻譯，具有很好的跨平臺特性.QEMU動態(tài)翻譯的基本原理是利用指令變換時的語義等價，將源體系架構(gòu)程序的指令翻譯成一條或者多條TCG中間表示，然后將TCG中間表示變換成目標平臺的一條或者多條指令，保證上述兩者轉(zhuǎn)換過程中指令語義的一致，實現(xiàn)不同平臺上指令的等價.

本文提出的基于優(yōu)先級的二進制翻譯寄存器分配優(yōu)化算法，主要是針對課題組基于QEMU研發(fā)的反饋式靜態(tài)二進制翻譯器FD-SQEMU(feedback static QEMU)設(shè)計的，但是該算法具有很好的跨平臺特性和擴展性，稍加改動即可在動態(tài)二進制翻譯中使用.

1.1 基于QEMU的反饋式靜態(tài)翻譯器FD-SQEMU

課題組基于QEMU，采用了QEMU的前端分析和TCG中間表示，設(shè)計了反饋式靜態(tài)二進制翻譯框架FD-SQEMU，該靜態(tài)翻譯器繼承了QEMU跨平臺的特性.FD-SQEMU除了前端源指令提取、TCG中端分析優(yōu)化和后端目標代碼生成3個過程外，還添加了動態(tài)執(zhí)行反饋階段，用以解決靜態(tài)二進制翻譯中存在的代碼發(fā)現(xiàn)和代碼定位問題.FD-SQEMU的框架結(jié)構(gòu)如圖2所示:

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

FD-SQEMU前端的源文件解析器和前端解碼器以及中端TCG分析優(yōu)化器均采用QEMU的相應(yīng)模塊，刪除了QEMU中控制中心、緩存管理和執(zhí)行模塊，后端則添加了目標文件生成器，重點是引入了動態(tài)執(zhí)行反饋模塊實現(xiàn)靜態(tài)二進制翻譯中代碼發(fā)現(xiàn)和代碼定位.

源文件解析器、前端解碼器和新添加的預(yù)處理模塊構(gòu)成FD-SQEMU的前端，負責將源平臺二進制代碼(本文即x86代碼)翻譯成中間代碼TCG；

TCG分析優(yōu)化器構(gòu)成FD-SQEMU的中端，負責對TCG中間表示進行平臺無關(guān)優(yōu)化，包括TCG的優(yōu)化，同時對源程序變量信息進行統(tǒng)計；

后端翻譯器和目標文件生成器，構(gòu)成FD-SQEMU的后端，負責將TCG中間代碼翻譯成目標平臺的二進制代碼(本文為申威架構(gòu)的代碼)；

動態(tài)執(zhí)行反饋模塊主要是模擬執(zhí)行,用以獲取反饋靜態(tài)無法得到的間接跳轉(zhuǎn)和間接調(diào)用目標地址，輔助解決靜態(tài)二進制翻譯中代碼發(fā)現(xiàn)和代碼定位問題.

與QEMU和基于LLVM的動態(tài)二進制翻譯器[17]相比，F(xiàn)D-SQEMU分離翻譯、代碼優(yōu)化與目標程序執(zhí)行階段，使得在同等優(yōu)化手段下，F(xiàn)D-SQEMU能夠采用不同層次的優(yōu)化算法，生成高質(zhì)量的執(zhí)行代碼.本文提出的寄存器優(yōu)化方法在中端TCG分析優(yōu)化器內(nèi)進行相關(guān)信息分析，在后端代碼生成階段進行實際實現(xiàn).

1.2 TCG指令

TCG指令類似于一種RISC(reduced instruction set computer)的指令，同樣擁有數(shù)據(jù)傳送、算術(shù)運算、邏輯運算、程序控制指令及其他指令[18].QEMU在tcg/tcg-opc.h中對所有TCG指令進行了定義，TCG指令格式定義為DEF(name,oargs,iargs,cargs,flags)，其中name為微指令的名字，oargs為指令輸出參數(shù)個數(shù)，iargs為指令輸入?yún)?shù)個數(shù)，cargs為指令常數(shù)個數(shù)，flags標志指令是否影響內(nèi)存內(nèi)容.此外，該結(jié)構(gòu)體中還有參數(shù)args_ct與sorted，該參數(shù)與具體體系結(jié)構(gòu)的寄存器緊密相關(guān).

TCG指令的操作數(shù)稱為臨時變量，構(gòu)成TCG中間表示的基礎(chǔ)，是源機器指令操作數(shù)到目標機器指令數(shù)傳遞、存儲與計算的橋梁.根據(jù)臨時變量生命周期的不同劃分，TCG定義了普通變量(temp)、普通本地變量(localtemp)、全局變量(globaltemp)和全局寄存器變量(globalregtemp)四種臨時變量類型.TCG變量統(tǒng)一用結(jié)構(gòu)體TCGTemp進行描述，變量類型通過結(jié)構(gòu)體TCGTemp中的標志位進行區(qū)分.

全局變量和全局寄存器變量生命周期貫穿程序的整個翻譯過程，分配的地址只有程序退出時才被收回.全局寄存器變量一般固定分配宿主機某一個寄存器值，用來保存源機器CPUState結(jié)構(gòu)體的指針，實現(xiàn)源機器狀態(tài)數(shù)據(jù)的快速讀取，加快程序執(zhí)行速度；普通變量生命周期范圍為一個基本塊，基本塊執(zhí)行結(jié)束變量被標注為“釋放”狀態(tài)，備下一個指令塊使用.普通本地變量的生命周期為一個函數(shù)，與普通變量不同的是在某些基本塊末尾處需要保存執(zhí)行時的數(shù)據(jù)流信息以供函數(shù)內(nèi)另一個基本塊使用，即需要將基本塊的執(zhí)行信息進行回寫.

臨時變量內(nèi)容均存儲在TCG上下文的512個TCGTemp的靜態(tài)數(shù)組static_temps中.其中全局變量和全局寄存器變量采取一次性分配策略建立運行時環(huán)境，在以后翻譯的過程中不會再進行分配，生命周期貫穿程序始終.全局變量源機器平臺運行環(huán)境env一般用全局寄存器變量表示，源機器平臺如標志寄存器用全局內(nèi)存變量表示，存儲分布在靜態(tài)數(shù)組static_temps的起始處；普通變量和普通本地變量依據(jù)源機器指令進行動態(tài)分配，存儲在數(shù)組后面部分，每分配出一個，則將該空間打上標記進行標識.臨時變量的存儲空間分布如圖3所示：

Fig. 3 Temporary variable memory format圖3 臨時變量內(nèi)存布局

2 QEMU中TCG寄存器分配機制研究

寄存器作為CPU體系最重要的信息存儲部件，它的讀寫速度遠遠快于存儲器，它的利用效率直接影響程序的執(zhí)行速度；在二進制翻譯中，寄存器分配的好壞同樣對目標程序的執(zhí)行效率有著重要影響.

如引言所述，二進制翻譯的過程是將源體系的可執(zhí)行代碼翻譯成中間代碼再翻譯成本地可執(zhí)行代碼的過程；從寄存器映射的角度看，二進制翻譯是從源體系的寄存器直接映射到虛擬機維護的一套內(nèi)存虛擬寄存器，再由虛擬寄存器映射到目標體系上的寄存器的過程，臨時變量是上述寄存器轉(zhuǎn)換的“傳輸者”.

2.1 QEMU中TCG寄存器分配機制

QEMU中寄存器分配的主體包括2個部分[19]：1)內(nèi)存虛擬寄存器;2)中間代碼使用的臨時變量.一套虛擬寄存器是一片連續(xù)的內(nèi)存區(qū)域，內(nèi)存虛擬寄存器主要是TCG中間表示源自于源體系寄存器的一一映射，以x86代碼為例，如圖4所示.對于內(nèi)存虛擬寄存器，QEMU采用靜態(tài)直接映射方法，使用固定的寄存器綁定方式實現(xiàn)源體系寄存器到本地寄存器的映射.如x86的宿主機用ebp寄存器指向env，利用ebp寄存器偏移即可獲取整個虛擬寄存器，實現(xiàn)源體系寄存器到本地寄存器的映射.

Fig. 4 Mapping from source register to TCG virtual register圖4 源體系寄存器到TCG虛擬寄存器的映射

TCG中間代碼使用的臨時變量類似于傳統(tǒng)編譯器中的虛擬寄存器，對于翻譯程序而言，相對于通用寄存器不存在差異性，但其到本地目標寄存器的映射要復(fù)雜得多.

對于QEMU中間代碼使用的臨時變量，其寄存器分配采用線性掃描靜態(tài)固定分配機制(first-mean-busy, FMB)，即“最靠前者最忙碌”，通過線性掃描目標體系提供的寄存器數(shù)組索引進行本地寄存器的分配.分配的具體實現(xiàn)過程為：1)當中間變量需要進行本地寄存器分配時，依據(jù)中間指令操作碼和中間變量位置，確定臨時變量可分配寄存器范圍.2)從數(shù)組的起點開始遍歷，當遇到某寄存器處于“空閑狀態(tài)”時，即分配該寄存器,并將該寄存器的狀態(tài)置為“忙碌”，中止遍歷，待對應(yīng)中間變量使用結(jié)束后即釋放該寄存器；若遍歷完的寄存器數(shù)組索引都處于“忙碌”的狀態(tài)，則采用線性遍歷寄存器數(shù)組從數(shù)組中強制“溢出”一個寄存器作為指定分配的寄存器，因溢出的寄存器保存著上一個臨時變量的值，在釋放寄存器的同時需將“溢出”的寄存器中的值寫回內(nèi)存中，以保證寄存器中的值不丟失.

2.2 TCG寄存器分配機制的缺陷

根據(jù)2.1節(jié)對TCG寄存器分配機制的分析，TCG指令內(nèi)變量的寄存器分配采用優(yōu)先級的方法，利用操作數(shù)可分配寄存器個數(shù)劃分優(yōu)先級，避免了寄存器分配競爭時導(dǎo)致操作數(shù)分配不到寄存器資源；指令間的寄存器分配方法采取簡單的線性掃描和溢出，缺少指令間寄存器分配的優(yōu)化算法，若發(fā)生資源競爭，則進行現(xiàn)行的寄存器溢出處理，顯然存在不合理之處，以申威宿主機翻譯x86可執(zhí)行程序為例，如圖5所示：

Fig. 5 TCG intermediate representation and local instruction after translation 圖5 TCG中間表示與翻譯后的本地代碼

圖5中左邊為TCG中間代碼(為觀察方便，在TCG中間表示中添加了對應(yīng)的x86匯編碼);右邊為翻譯后生成的申威本地指令，每條中間指令對應(yīng)生成相應(yīng)的申威本地指令.其中x指令部分將$9寄存器分配給了tmp0，y指令部分也給tmp0分配$9寄存器時，z指令部分分別將$9和$10寄存器分配給tmp0和tmp1.在這里，QEMU實際上沒有考慮指令間寄存器的使用情況，鑒于可能存在的寄存器溢出情況，在每條指令寄存器使用完畢后，都做了回寫處理，引入了冗余訪存指令①②③④，這是因為QEMU在進行寄存器分配時忽略了指令間的聯(lián)系，引入了冗余指令，另外若下一指令或者指令塊要繼續(xù)使用rdx和rax中值，則⑤⑥⑦訪存指令也是冗余且可以消除的.

Fig. 6 Example of registers allocation for loops圖6 有關(guān)循環(huán)的寄存器分配例子

另外，QEMU中TCG寄存器分配機制也沒考慮到程序上下文對寄存器分配的影響，忽略了循環(huán)體內(nèi)寄存器分配對程序整體效率的影響，以圖6為例進行說明.

如圖6(a)所示，基本塊或者幾個基本塊拼接成的循環(huán)塊CB1位于循環(huán)體內(nèi)，假設(shè)執(zhí)行頻率N=1 000，當對CB1循環(huán)塊進行寄存器分配時,若發(fā)現(xiàn)寄存器不夠用，則很可能會溢出一個寄存器，假設(shè)是A，那么循環(huán)塊的頭尾會各添加一個訪存指令如圖6(b)所示，如此store和load指令都在循環(huán)體內(nèi)部，顯然會降低程序性能，如果在寄存器分配前進行評估，優(yōu)先滿足循環(huán)體內(nèi)部的寄存器需求，如此A可能因為無法分配到寄存器而溢出，如圖6(c)所示，這樣成功把訪存指令移到了循環(huán)之外，有效提高了翻譯后本地程序的性能.

針對上述由于寄存器溢出而導(dǎo)致的冗余訪存問題，本文結(jié)合全局寄存器靜態(tài)分配和局部寄存器動態(tài)分配思想，提出基于優(yōu)先級的動靜結(jié)合寄存器分配算法(a dynamic and static combined registers allocation algorithm based on priority).首先依據(jù)程序的靜態(tài)統(tǒng)計特征，實現(xiàn)靜態(tài)全局寄存器的直接映射，以減少全局寄存器的維護開銷；然后借助程序的控制流程圖，結(jié)合變量活性分析基本塊內(nèi)指令操作數(shù)寄存器分配個數(shù)，減少指令間寄存器以及循環(huán)體內(nèi)不必要的寄存器溢出，以減少本地代碼的膨脹率，提高翻譯目標程序的執(zhí)行效率.

3 基于優(yōu)先級的動靜結(jié)合寄存器分配算法

目前QEMU中使用的TCG寄存器分配機制的主要缺陷在于僅解決了指令內(nèi)操作數(shù)分配的競爭，讓指令內(nèi)操作數(shù)分配到最優(yōu)的寄存器，而對指令間寄存器采用固定的分配順序，忽略了基本塊內(nèi)指令組成以及對寄存器需求的差異性，指令間固定的寄存器分配順序與指令內(nèi)的寄存器最優(yōu)分配并沒有實現(xiàn)整個基本塊以及整個程序中寄存器分配的最優(yōu).

寄存器分配效率提高的關(guān)鍵在于如何最大限度減少寄存器溢出帶來的開銷.基于此，考慮到將目標程序中最常用的寄存器固定映射到本地機器的寄存器，可以有效避免過多的訪存操作，提高翻譯后的程序性能.因此，對x86應(yīng)用程序和部分系統(tǒng)程序中寄存器使用情況進行統(tǒng)計對于寄存器的分配是有指導(dǎo)意義的.以系統(tǒng)Linux-0.2啟動過程為例，x86上各寄存器使用情況統(tǒng)計結(jié)果如表1所示：

Table 1 Register Usage Statistics on x86 Program表1 x86程序寄存器使用情況統(tǒng)計

表1給出了系統(tǒng)Linux-0.2在啟動時x86平臺各寄存器的使用情況，從表1中可以看出x86架構(gòu)運行時最常使用的寄存器是eax，ebx，edx，esp.x86應(yīng)用程序寄存器的使用情況與此相似.

基于x86平臺各寄存器使用情況的統(tǒng)計特征，在翻譯程序具體進行寄存器分配時，首先根據(jù)x86寄存器使用情況，采用寄存器直接映射方式進行全局寄存器靜態(tài)分配.如在翻譯中具體進行寄存器分配時，可首先將x86上eax，ebx，edx，esp寄存器映射到申威處理器通用寄存器$9，$10，$11，$12上；然后當翻譯x86指令時，即可直接使用對應(yīng)的已固定映射到本地的通用寄存器替換x86中eax，ebx，edx，esp寄存器，而無需再從內(nèi)存模擬的虛擬寄存器中加載，可以有效減少訪存操作，提高程序運行效率.

在全局寄存器靜態(tài)直接映射分配的基礎(chǔ)上，再根據(jù)翻譯程序基本塊的特性進行局部的動態(tài)寄存器分配.具體做法是:首先通過變量活性分析遍歷基本塊內(nèi)有效的中間指令，預(yù)估統(tǒng)計指令內(nèi)操作數(shù)需求寄存器數(shù);然后依據(jù)預(yù)估的寄存器數(shù)排序確定寄存器分配優(yōu)先順序.若可分配的寄存器預(yù)估需求數(shù)目越大，則基本塊內(nèi)指令對該寄存器的需求就越大，分配該寄存器的優(yōu)先級越高，優(yōu)先分配該寄存器，依次進行，優(yōu)先級最低的寄存器最慢分配出去.如此，剩余指令對寄存器需求的可能性變小，從而最大限度地減少寄存器溢出的可能性并使寄存器溢出的代價減少.具體的算法流程圖如圖7所示:

Fig. 7 Algorithm flowchart圖7 算法流程圖

1) TCG作為FD-SQEMU前端代碼解析和后端目標代碼生成的紐帶，記錄了基本塊內(nèi)全局變量個數(shù)和基本塊跳轉(zhuǎn)等信息.在此基礎(chǔ)上，添加基本塊內(nèi)寄存器需求數(shù)組regRequestNum和寄存器優(yōu)先級數(shù)組regPriority，分別記錄基本塊內(nèi)需求寄存器的局部變量個數(shù)(即寄存器需求數(shù))和基本塊內(nèi)各寄存器分配的次序(即需求該寄存器的優(yōu)先程度).在翻譯每個基本塊之初，對這2個數(shù)組進行初始化.

2) 借助變量活性分析線性掃描基本塊內(nèi)TCG指令，統(tǒng)計寄存器需求數(shù)目.這里對已固定分配寄存器的全局變量不作變量處理，但進行塊內(nèi)使用標記；對于其他變量，只須將對應(yīng)各TCG指令內(nèi)需求寄存器的計數(shù)器regRequestNum采取迭代累加的方法，即可完成寄存器分配計數(shù)器的統(tǒng)計，該迭代累加算法的偽代碼如圖8所示：

Fig. 8 Pseudo-code algorithm
圖8 部分算法偽代碼

4) 依據(jù)控制流程圖判斷該基本塊是否是循環(huán)體內(nèi)的基本塊，若是且該循環(huán)塊內(nèi)仍有多次使用的變量未分配到寄存器，則將該循環(huán)體內(nèi)未使用的全局寄存器溢出，供該循環(huán)塊內(nèi)變量使用；并依據(jù)循環(huán)優(yōu)化中代碼外提方法將該全局寄存器的狀態(tài)維護代碼外提到循環(huán)體外.如此，可進一步提高目標平臺寄存器的利用率，減少寄存器溢出開銷，提高程序運行效率.

4 實驗和結(jié)果

實驗采用由QEMU改造的FD-SQEMU模擬器作為二進制翻譯平臺，首先借助FD-SQEMU翻譯器使用QEMU中默認的寄存器分配方法對測試用例進行翻譯;然后借助FD-SQEMU翻譯器在進行寄存器分配優(yōu)化后對測試用例進行翻譯，對比兩次翻譯后得到的目標程序的運行時間，以評估基于優(yōu)先級的動靜結(jié)合寄存器分配優(yōu)化算法的實際優(yōu)化效果.

令Tbefore和Tafter分別表示在使用寄存器分配優(yōu)化算法前和使用寄存器分配優(yōu)化算法后的本地目標程序的執(zhí)行時間，則使用寄存器分配優(yōu)化后與優(yōu)化前的加速比為

在實際進行測試驗證時，實驗通過正確性測試、循環(huán)熱代碼測試、遞歸熱代碼測試和整體性能測試對提出的算法進行整體評估.

4.1 實驗環(huán)境

1) 源平臺.x86平臺，操作系統(tǒng)為Fedora11 Linux 2.6.29.4 編譯器gcc-4.6.4.

2) 目標平臺.國產(chǎn)申威處理器，主頻1.4 GHz，內(nèi)存4 GB，操作系統(tǒng)為Fedora，內(nèi)核版本3.8.0，編譯器為 gcc，版本 4.5.3.

3) 測試集.NBENCH-2.2.3，手動實現(xiàn)的主流遞歸算法和SPEC2006測試集[19].

4.2 正確性測試

針對寄存器優(yōu)化算法的正確性測試主要分為2個部分：指令翻譯測試和實際程序翻譯測試.

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

在保證了單條指令翻譯的正確性后，對實際程序翻譯進行了正確性測試.具體測試過程為：1)在x86平臺上編譯SPEC CPU2006和NBENCH測試集等測試程序并運行記錄結(jié)果；2)在目標平臺上運行翻譯后的可執(zhí)行程序，并與x86上運行結(jié)果相比對.部分程序的測試結(jié)果如表3所示.

實驗結(jié)果表明，優(yōu)化前后的目標程序執(zhí)行結(jié)果與源x86平臺上程序執(zhí)行結(jié)果相同，表明基于優(yōu)先級的動靜結(jié)合寄存器分配算法能夠進行正確的翻譯，保證了程序的等價翻譯，具有較高的可信度.

Table 2 Correctness Testing of Instruction Translation表2 指令翻譯的正確性測試

Note：“√” mean that the test instructions have passed the correctness verification.

Table 3 Correct Test表3 正確性測試

Note：“√” mean that the test cases have passed the correctness verification.

4.3 寄存器分配相關(guān)信息分析

申威處理器共計有6個全局寄存器S0～S5、12個臨時寄存器T0～T11.使用QEMU現(xiàn)有的寄存器分配機制進行二進制翻譯時，大量使用了S0，S1，S2寄存器，并在每次全局寄存器使用完畢后將其中的值寫回存儲器，一是對其余現(xiàn)有的寄存器利用率較低，二是引入了不必要的寄存器維護開銷；在改進寄存器分配方式后，各基本塊對申威寄存器的使用更加均衡，能有效減少因寄存器溢出導(dǎo)致的訪存次數(shù).寄存器分配方式改進前，各申威本地寄存器使用頻率如表4所示:

所謂盈利能力，通常來講是指企業(yè)獲取利潤的能力，表現(xiàn)為一定時期內(nèi)企業(yè)收益數(shù)額的多少，一般用凈資產(chǎn)收益率、成本費用利潤率、銷售利潤率、總資產(chǎn)報酬率、盈余現(xiàn)金保障倍數(shù)和資本收益率六項。由前文分析可知，生產(chǎn)性服務(wù)業(yè)“營改增”會影響企業(yè)營業(yè)稅金及附加、所得稅費、企業(yè)利潤等項目，通過減少企業(yè)的稅負，帶來企業(yè)成本的降低與更多資金的流動。企業(yè)將這筆節(jié)省出來的資金用于研發(fā)設(shè)備的投入或者擴大再生產(chǎn)時，由于《企業(yè)所得稅法》規(guī)定了研發(fā)費用的加計扣除等稅收優(yōu)惠政策，這就會使得企業(yè)在進一步減輕其稅負時，盈利能力得到提高。

Table 4 Registers Usage Frequency of SW Before Optimization表4 優(yōu)化前部分申威本地寄存器使用頻率

改進寄存器分配方式后，各申威本地寄存器使用頻率所占百分比如表5所示:

Table 5 Register Usage Frequency of SW After Optimization表5 優(yōu)化后部分申威本地寄存器使用頻率

如表5所示，該寄存器分配方式，有效地提高了本地臨時寄存器的使用率，并且使申威寄存器的使用更加均衡，可以減少寄存器的溢出次數(shù).在寄存器分配優(yōu)化后，翻譯后程序的指令平均減少了約2.3%.

4.4 循環(huán)熱代碼性能測試

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

使用寄存器分配優(yōu)化前和優(yōu)化后的FD-SQEMU在國產(chǎn)申威處理器上對NBENCH測試集進行對比測試，優(yōu)化后相對于優(yōu)化前的加速情況如圖9所示.

如圖9所示，對于不同的NBENCH測試項目，寄存器分配優(yōu)化后獲得的加速比也不同.

Table 6 NBENCH Tasks表6 NBENCH測試任務(wù)

Fig. 9 Speedup ratio on NBENCH after optimization 圖9 優(yōu)化后NBENCH加速情況

4.5 遞歸熱代碼性能測試

Fig. 10 Speedup ratio on recursive algorithms after optimization圖10 優(yōu)化后遞歸熱代碼加速情況

4.6 整體性能測試

SPEC2006測試集中的程序基本都是實際應(yīng)用中常用到的程序，該測試集的執(zhí)行結(jié)果能夠反映出一個翻譯系統(tǒng)的整體性能.在具體實驗時，挑選了部分SPEC2006中常用的測試應(yīng)用進行測試，采用FD-SQEMU在寄存器分配優(yōu)化后翻譯源程序為本地目標程序，該程序性能提升情況如圖11所示:

Fig. 11 Speed up ratio on part of SPEC2006 after optimization圖11 優(yōu)化后部分SPEC2006測試項的加速情況

4.7 實驗結(jié)果分析

通過對不同程序進行測試，根據(jù)圖9～11中結(jié)果可以看出改進了寄存器分配方式后，各程序都有不錯的性能提升，其中NBENCH測試集中STRING_SORT和BITFIELD的測試程序性能提升最高，最高達到了17.36%.改進寄存器分配方式后，根據(jù)圖9中測試結(jié)果NBENCH各測試項性能提升4.35%～17.24%，平均性能提升約為8.56%；根據(jù)圖10中測試結(jié)果， FIBONACCI, QUICKSORT等遞歸程序性能提升7.86%～8.54%，平均性能提升了8.14%；根據(jù)圖11，SPEC2006程序性能提升了6.94%～9.62%，平均性能提升了8.01%.根據(jù)測試結(jié)果，說明該寄存器分配優(yōu)化算法是有效的，且對于含循環(huán)、遞歸較多的程序，有更好的優(yōu)化效果.

5 總 結(jié)

本文在分析QEMU的寄存器分配方法后，舉例指出了該機制存在的缺陷，并在介紹了由QEMU改造的靜態(tài)二進制翻譯器FD-SQEMU后，借鑒傳統(tǒng)編譯器靜態(tài)全局寄存器分配和動態(tài)局部寄存器分配思想后，提出了基于優(yōu)先級的動靜結(jié)合寄存器分配方法.該算法，首先依據(jù)x86應(yīng)用程序統(tǒng)計特征進行全局寄存器靜態(tài)直接映射分配;然后考慮各循環(huán)塊以及基本塊間寄存器需求的差異，利用TCG中間表示操作碼與本地指令之間的映射關(guān)系統(tǒng)計基本塊內(nèi)需求的各寄存器次數(shù)，并排序確定優(yōu)先級順序進行寄存器分配;最后，溢出循環(huán)塊內(nèi)未使用的全局寄存器，給塊內(nèi)未分配到寄存器的變量使用，進一步減少了寄存器溢出的開銷.通過NBENCH、某些經(jīng)典遞歸程序和部分SPEC2006程序?qū)υ撍惴ㄟM行測試，結(jié)果表明該寄存器分配優(yōu)化算法能有效提高目標程序的執(zhí)行效率.另外，該算法對具體的目標平臺依賴不大，具有很好的跨平臺特性，另外，舍去該算法中依據(jù)程序控制流程圖對循環(huán)塊的處理亦可適用于動態(tài)二進制翻譯.

寄存器分配的研究無論是對于傳統(tǒng)編譯器，還是對于二進制翻譯，從更好地發(fā)揮CPU的性能以及提高高性能計算程序的執(zhí)行效率方面都有重要的意義.