王 軍 龐建民 傅立國(guó) 岳 峰 單 征 張家豪

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

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

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

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

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

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

1 相關(guān)工作

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

Fig. 1 QEMU translation process圖1 QEMU翻譯過(guò)程

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

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

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

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

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

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

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

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

后端翻譯器和目標(biāo)文件生成器，構(gòu)成FD-SQEMU的后端，負(fù)責(zé)將TCG中間代碼翻譯成目標(biāo)平臺(tái)的二進(jìn)制代碼(本文為申威架構(gòu)的代碼)；

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

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

1.2 TCG指令

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

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

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

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

Fig. 3 Temporary variable memory format圖3 臨時(shí)變量?jī)?nèi)存布局

2 QEMU中TCG寄存器分配機(jī)制研究

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

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

2.1 QEMU中TCG寄存器分配機(jī)制

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

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

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

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

2.2 TCG寄存器分配機(jī)制的缺陷

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) 借助變量活性分析線性掃描基本塊內(nèi)TCG指令，統(tǒng)計(jì)寄存器需求數(shù)目.這里對(duì)已固定分配寄存器的全局變量不作變量處理，但進(jìn)行塊內(nèi)使用標(biāo)記；對(duì)于其他變量，只須將對(duì)應(yīng)各TCG指令內(nèi)需求寄存器的計(jì)數(shù)器regRequestNum采取迭代累加的方法，即可完成寄存器分配計(jì)數(shù)器的統(tǒng)計(jì)，該迭代累加算法的偽代碼如圖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)維護(hù)代碼外提到循環(huán)體外.如此，可進(jìn)一步提高目標(biāo)平臺(tái)寄存器的利用率，減少寄存器溢出開銷，提高程序運(yùn)行效率.

4 實(shí)驗(yàn)和結(jié)果

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

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

在實(shí)際進(jìn)行測(cè)試驗(yàn)證時(shí)，實(shí)驗(yàn)通過(guò)正確性測(cè)試、循環(huán)熱代碼測(cè)試、遞歸熱代碼測(cè)試和整體性能測(cè)試對(duì)提出的算法進(jìn)行整體評(píng)估.

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

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

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

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

4.2 正確性測(cè)試

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

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

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

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

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

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

Table 3 Correct Test表3 正確性測(cè)試

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5 遞歸熱代碼性能測(cè)試

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

4.6 整體性能測(cè)試

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

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

4.7 實(shí)驗(yàn)結(jié)果分析

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

5 總 結(jié)

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

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