戴　濤,單　征,盧帥兵,石　強(qiáng),潭　捷

(解放軍信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室,河南 鄭州 450002)

?

基于優(yōu)先級(jí)動(dòng)態(tài)二進(jìn)制翻譯寄存器分配算法

戴濤,單征,盧帥兵,石強(qiáng),潭捷

(解放軍信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室,河南 鄭州 450002)

摘要:針對(duì)動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)QEMU寄存器分配不考慮基本塊之間對(duì)寄存器需求的差異性,造成不必要寄存器溢出而導(dǎo)致重復(fù)訪存開銷的問題,提出高效的基于優(yōu)先級(jí)線性掃描寄存器分配算法.該算法基于中間表示與源平臺(tái)寄存器之間的映射關(guān)系,獲取每一次生成基本塊中間指令預(yù)分配寄存器次數(shù)并統(tǒng)計(jì)排序確定寄存器的優(yōu)先級(jí),寄存器分配時(shí)動(dòng)態(tài)調(diào)整寄存器分配順序,減少寄存器溢出次數(shù),降低生成本地代碼指令數(shù)量.QEMU動(dòng)態(tài)翻譯x86、mips及arm平臺(tái)的nbench測(cè)試集實(shí)驗(yàn)結(jié)果表明,該算法基于中間代碼改進(jìn)具有很好的跨平臺(tái)性,有效減少了生成本地代碼指令數(shù)目,比QEMU優(yōu)化前翻譯性能分別提升了6.7%、6.8%、4.7%.

關(guān)鍵詞：動(dòng)態(tài)二進(jìn)制翻譯；寄存器分配；QEMU；中間指令

二進(jìn)制翻譯是一種即時(shí)的編譯技術(shù),將一種體系結(jié)構(gòu)的指令集轉(zhuǎn)換成另外一種指令集并可執(zhí)行的技術(shù)[1].翻譯的過程分成前端解碼器、中端優(yōu)化器以及后端編碼器[2].前端解碼依據(jù)源機(jī)器指令的特點(diǎn),將機(jī)器指令翻譯成成匯編指令,分離出每條機(jī)器指令完成類似反匯編的功能.中端優(yōu)化器的主要工作是變換生成的中間代碼[3-4],通過分析基本塊內(nèi)中間代碼組織關(guān)系簡化中間代碼,如常量傳播[5]、變量活性分析[6]、標(biāo)志位優(yōu)化[7]等方法剔除冗余指令[8].后端編碼器的作用是將中間代碼轉(zhuǎn)換生成本地可執(zhí)行的指令流.

與傳統(tǒng)編譯器不同的是動(dòng)態(tài)二進(jìn)制翻譯的寄存器分配是在程序運(yùn)行的過程中,即后端編碼過程,傳統(tǒng)編譯器高效的寄存器圖著色法[9-10]無法在動(dòng)態(tài)二進(jìn)制翻譯中使用,動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)中常采用基于線性掃描方法的寄存器分配方法[11-12].Alei等[13]對(duì)QEMU寄存器的管理及分配機(jī)制進(jìn)行詳細(xì)的描述,但未給出一種有效的改進(jìn)方法.吳浩[14]基于在X86平臺(tái)翻譯ARM程序,采用直接映射寄存器分配策略,通過大量對(duì)比實(shí)驗(yàn)驗(yàn)證中間表示的存在降低了二進(jìn)制翻譯的性能,但是需要大幅度的修改QEMU的翻譯機(jī)制.文延華等[15]在Alpha平臺(tái)翻譯PowerPC程序時(shí),對(duì)PowerPC的特殊寄存器的二進(jìn)制翻譯中模擬,提出分段映射和特殊寄存器裁剪相結(jié)合的方法并獲得一定的優(yōu)化效果,但由于寄存器裁剪函數(shù)的復(fù)雜性,可被優(yōu)化的程序比較少.廖銀等[16]在MIPS平臺(tái)模擬X86平臺(tái)寄存器時(shí)采用直接映射的策略,利用本地平臺(tái)通用寄存器數(shù)量多的特點(diǎn),直接將X86的8個(gè)通用寄存器分配到MIPS的通用寄存器上,一一映射,簡化指令翻譯的規(guī)則,降低了代碼膨脹率.該方法需求特定平臺(tái)硬件基礎(chǔ),不具有很好的通用性,移植性較差.Cai等[17]在cross-bit系統(tǒng)中提出簡化的寄存器圖著色法,使用3個(gè)鏈表收集變量定值引用信息,將使用到的變量構(gòu)造成一個(gè)圖,此后在每次發(fā)生一次溢出時(shí)重新構(gòu)造沖突圖,該方法因?yàn)榧拇嫫饕绯鲂枰看芜M(jìn)行圖的構(gòu)造大大增大了翻譯的開銷,整體的效率提升有限.Liang等[18]基于QEMU的中間表示分析變量的定值與引用,使用鏈表存儲(chǔ)變量的生命周期和使用,減少中間表示指令數(shù)目,由于需要多次遍歷采集基本塊內(nèi)變量的定值與引用信息,算法的復(fù)雜度較高且不具有良好的移植性.

本文重點(diǎn)闡述QEMU翻譯原理、中間表示的臨時(shí)變量與寄存器分配之間的關(guān)系以及寄存器分配機(jī)制,基于中間代碼與平臺(tái)無關(guān)的特點(diǎn),提出改進(jìn)的基于優(yōu)先級(jí)線性掃描寄存器分配方法.通過統(tǒng)計(jì)基本塊內(nèi)中間表示每條指令預(yù)分配寄存器數(shù)量,對(duì)寄存器預(yù)分配次數(shù)排序確定各個(gè)寄存器在基本塊內(nèi)分配的優(yōu)先順序,減少因寄存器溢出導(dǎo)致冗余訪存指令,提高程序的執(zhí)行效率.

1相關(guān)工作

QEMU[19]是一個(gè)廣泛使用的多源到多目標(biāo)動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng),可以支持用戶級(jí)和系統(tǒng)級(jí)二進(jìn)制翻譯.采用一種與平臺(tái)無關(guān)(Tinycodegeneration,TCG)微指令的中間表示,不同源平臺(tái)程序只需要變換前端解碼器而不需要改動(dòng)后端編碼器,即可實(shí)現(xiàn)多源到多目標(biāo)平臺(tái)的動(dòng)態(tài)翻譯,具有很好的跨平臺(tái)特性.QEMU動(dòng)態(tài)翻譯的基本原理是利用指令變換時(shí)的語義等價(jià),將源體系程序的指令翻譯成一條或者多條TCG中間語言表示,然后將TCG中間表示指令變換成目標(biāo)平臺(tái)的一條或者多條指令,保證上述兩者轉(zhuǎn)換過程中指令語義的一致,實(shí)現(xiàn)不同平臺(tái)上指令的等價(jià).

基本塊是QEMU翻譯和執(zhí)行的基本單位,擁有單個(gè)入口和單個(gè)出口,以跳轉(zhuǎn)指令結(jié)尾若干條指令序列.基本塊的執(zhí)行流程可以分為以下兩種.

一種是塊鏈執(zhí)行,塊鏈的形成是在執(zhí)行多個(gè)基本塊指令時(shí)可能發(fā)生,指的是將翻譯好的幾個(gè)tb(translationblock)直接通過jmp指令連接起來,執(zhí)行完一個(gè)tb時(shí),不再需要跳轉(zhuǎn)到翻譯流程去查找下個(gè)要被執(zhí)行的tb,直接通過jmp指令跳轉(zhuǎn)到已翻譯好的tb,直到無法確定跳轉(zhuǎn)目標(biāo)地址或者發(fā)生異常才返回翻譯流程.基本思路是基于在直接跳轉(zhuǎn)的情況下,跳轉(zhuǎn)目標(biāo)是確定的且不發(fā)生變化,翻譯時(shí)在該分支插入一條原地跳轉(zhuǎn)指令,待前驅(qū)翻譯確定跳轉(zhuǎn)地址后,將原地跳轉(zhuǎn)指令的地址改成真實(shí)的地址,下一次執(zhí)行該分支時(shí),直接跳轉(zhuǎn)到指定的基本塊中,省去上下文切換和重復(fù)翻譯開銷.如圖1(b)所示為經(jīng)過塊鏈后程序的執(zhí)行流程.

另外一種是基本塊交替執(zhí)行,即翻譯和執(zhí)行交叉進(jìn)行,如圖1(a)所示為未進(jìn)行塊鏈程序執(zhí)行的過程.翻譯后主體代碼由三部分實(shí)體組成：Prologue、Epilogue及一個(gè)或多個(gè)基本塊.Prologue代碼用于保存目標(biāo)平臺(tái)上狀態(tài),包括通用寄存器、堆棧等信息；然后利用jmp指令跳轉(zhuǎn)入基本塊的入口地址,完成目標(biāo)平臺(tái)到虛擬機(jī)狀態(tài)的轉(zhuǎn)換.基本塊指令流執(zhí)行完后,都需要執(zhí)行exit_tb指令,表明虛擬機(jī)的指令流已執(zhí)行完成,下一步執(zhí)行翻譯流程,跳轉(zhuǎn)Epilogue代碼入口地址,進(jìn)行本地寄存器恢復(fù),退出虛擬機(jī),執(zhí)行本機(jī)指令.以上即為動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)QEMU翻譯和執(zhí)行兩個(gè)狀態(tài)切換流程.

圖1　多個(gè)基本塊執(zhí)行過程Fig.1　Multiple basic blocks execution process

1.1TCG微指令

TCG指令格式定義為DEF(name,oargs,iargs,cargs,flags),所有微指令包含在tcg/tcg-opc.h中.在結(jié)構(gòu)體TCGOpDef中對(duì)每一個(gè)成員變量有詳細(xì)的說明,其中name為微指令的名字,oargs為指令輸出參數(shù)個(gè)數(shù),iargs為指令輸入?yún)?shù)個(gè)數(shù),cargs為指令常數(shù)個(gè)數(shù),flags標(biāo)志指令是否影響內(nèi)存內(nèi)容.此外,還有args_ct與sorted表示參數(shù)約束屬性,該參數(shù)與結(jié)構(gòu)體系的寄存器緊密相關(guān).TCG指令類似于一種精簡指令,和普通處理器一樣,擁有數(shù)據(jù)傳送、算術(shù)運(yùn)算、邏輯運(yùn)算、程序控制指令及其他指令[20].

TCG指令的操作數(shù)稱為臨時(shí)變量,構(gòu)成TCG中間表示基礎(chǔ),通過使用臨時(shí)變量作為源機(jī)器指令操作數(shù)到目標(biāo)機(jī)器指令數(shù)據(jù)存儲(chǔ)、傳送與計(jì)算.根據(jù)臨時(shí)變量生命周期的不同劃分,TCG定義了4種變量類型：普通變量(temp)、普通本地變量(temp_local)、全局變量(globaltemp)和全局寄存器變量(globalregtemp).TCG變量統(tǒng)一用結(jié)構(gòu)體TCGTemp進(jìn)行描述,默認(rèn)可分配TCGTemp個(gè)數(shù)為512.若超過該數(shù)目,則異常中止程序翻譯.變量類型依靠結(jié)構(gòu)體TCGTemp的標(biāo)志位進(jìn)行區(qū)分.此外,4種類型臨時(shí)變量作用域各不相同,程序處理機(jī)制也不同.其中全局變量和全局寄存器變量生命周期存在于整個(gè)程序的翻譯過程,只有程序退出時(shí)才被回收.全局寄存器變量一般是固定分配宿主機(jī)某一個(gè)寄存器值,用來保存源機(jī)器CPUState結(jié)構(gòu)體的指針,實(shí)現(xiàn)源機(jī)器狀態(tài)數(shù)據(jù)的快速讀取,加快程序執(zhí)行速度.普通變量生命周期范圍為一個(gè)基本塊,基本塊執(zhí)行結(jié)束變量被標(biāo)注為“釋放”狀態(tài),備下一條指令使用.普通本地變量的生命周期為一個(gè)函數(shù)范圍內(nèi),與普通變量不同的是在某些基本塊末尾處需要程序保存執(zhí)行時(shí)的數(shù)據(jù)流信息以供下一個(gè)基本塊使用,需要將基本塊的執(zhí)行信息進(jìn)行回寫.

1.2臨時(shí)變量

臨時(shí)變量內(nèi)容均存儲(chǔ)在TCG上下文的512個(gè)TCGTemp的static_temps靜態(tài)數(shù)組中.其中全局變量和全局寄存器變量采取一次性分配策略建立運(yùn)行時(shí)環(huán)境,在以后翻譯的過程中不會(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ǔ)空間布局如圖2所示.

TCG分成4種不同類型的臨時(shí)變量,各種變量空間分配機(jī)制不盡相同,釋放機(jī)制也各不相同,TCG采用不同的函數(shù)接口進(jìn)行釋放.為了管理臨時(shí)變量內(nèi)存釋放空間,TCG在上下文結(jié)構(gòu)體TCGContext用4個(gè)first_free_temp整型靜態(tài)數(shù)組存儲(chǔ)記錄static_temps數(shù)組中32位普通變量、32位普通本地變量、64位普通變量和64位普通本地變量類型釋放空間位置.該數(shù)組存儲(chǔ)值表示static_temps數(shù)組中的已被釋放索引,每釋放出一個(gè)空間先將該空間的分配標(biāo)識(shí)清除,其次將first_free_temp存儲(chǔ)的索引賦值給下一個(gè)釋放出空間,即TCGTemp->next_free_temp=TCGContext->first_free_temp,同時(shí)修改TCGContext->first_free_temp的值,于是TCGContext->first_free_temp實(shí)際上是一個(gè)擁有4個(gè)釋放空間的鏈表數(shù)組,TCGContext->first_free_temp存儲(chǔ)的永遠(yuǎn)是該鏈表的頭,如圖3所示.

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

圖3　釋放的空閑空間鏈表組織方式Fig.3　Free space linked list organization

圖3中,P為全局寄存器變量,Q為全局變量,R為32位普通變量,S為32位普通本地變量,T為64位普通變量,U為64位普通本地變量.static_temps索引序號(hào)3, 4, 5, 6, 8, 9,a,c,d均為釋放空間,索引序號(hào)0, 1, 2, 7,b表示已分配空間,3→5→9→d是32位普通局部變量釋放的空閑空間鏈表,4→8→c為32位普通變量已釋放的空閑空間鏈表,6→a為64位普通變量釋放的空閑空間鏈表.first_free_temp存放的是釋放空間鏈表頭在臨時(shí)變量static_temps存儲(chǔ)空間的索引,圖中共有3個(gè)鏈表,頭索引號(hào)分別為3、4、6,所以數(shù)組first_free_temp的前3個(gè)字節(jié)存儲(chǔ)3個(gè)鏈表的頭索引值,由于臨時(shí)變量存儲(chǔ)空間中沒有釋放出64位普通本地變量已分配的空間,在靜態(tài)數(shù)組first_free_temp第4個(gè)字節(jié)用-1表示.

2TCG寄存器分配策略

寄存器作為CPU體系最重要的信息存儲(chǔ)部件,它的取值與存儲(chǔ)速度遠(yuǎn)比內(nèi)存快很多,是CPU的寶貴資源.它的利用效率直接影響程序的執(zhí)行速度.動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)的機(jī)制是將源體系的可執(zhí)行代碼翻譯成中間代碼,然后將中間代碼轉(zhuǎn)換成本地代碼指令的過程.從寄存器映射的角度來看,是從源體系的寄存器直接映射到虛擬機(jī)維護(hù)的一套內(nèi)存虛擬寄存器,再由虛擬寄存器映射到目標(biāo)體系上的寄存器的過程,臨時(shí)變量是上述寄存器轉(zhuǎn)換的“傳輸者”.寄存器本地分配的主體包括以下兩部分：一部分是內(nèi)存虛擬寄存器,另外一部分是中間代碼使用的變量.傳統(tǒng)編譯器寄存器分配時(shí)是為每個(gè)變量分配虛擬寄存器變量,然后在寄存器分配階段為每個(gè)虛擬寄存器分配真實(shí)的寄存器.TCG與此相類似,其中的臨時(shí)變量類似傳統(tǒng)編譯器中的虛擬寄存器.一套虛擬寄存器是一連續(xù)的內(nèi)存區(qū)域,目標(biāo)體系寄存器與虛擬寄存器一一對(duì)應(yīng).內(nèi)存虛擬寄存器相對(duì)于通用寄存器而言不存在差異性,為存儲(chǔ)中一段內(nèi)存空間.源體系的寄存器與內(nèi)存虛擬寄存器的映射思想比較簡單,實(shí)現(xiàn)兩者一對(duì)一的映射即可,以翻譯x86可執(zhí)行程序?yàn)槔?如圖4所示.

圖4　源體系寄存器與虛擬寄存器之間的映射Fig.4　Mapping between source system register and virtual register

對(duì)于內(nèi)存虛擬寄存器,QEMU采用直接映射方法,分配成固定的寄存器綁定方法,如x86的宿主機(jī)用ebp寄存器指向env,利用ebp寄存器偏移即可獲取整個(gè)虛擬寄存器,實(shí)現(xiàn)源體系寄存器到本地寄存器的映射.

2.1臨時(shí)變量與本地寄存器分配關(guān)系

中間代碼臨時(shí)變量進(jìn)行本地寄存器分配時(shí),思想復(fù)雜得多.因中間指令語義各不相同,操作數(shù)個(gè)數(shù)差異或操作數(shù)之間的依賴關(guān)系等,臨時(shí)變量寄存器分配與中間指令緊密相關(guān).為了確定每條中間指令可分配的寄存器,在QEMU定義了一結(jié)構(gòu)體TCGTargetOpDef數(shù)組,確定了每條中間指令的操作數(shù)與目標(biāo)平臺(tái)寄存器之間的關(guān)系,包括每個(gè)操作數(shù)可分配本地寄存器范圍、操作數(shù)之間的依賴關(guān)系等.以可供分配的寄存器共有7個(gè)的宿主機(jī)x86為例,如圖5所示.

st8_i32指令的原型聲明是st8_i32t0,t1,offsetadd_i32指令的原型聲明是add_i32t0,t1,t2.結(jié)構(gòu)體數(shù)組的第一行INDEX_op_st8_i32是st8_i32指令索引,后面的字符串?dāng)?shù)組限定t0、t1操作數(shù)可分配寄存器范圍,用字符串表示,如圖中的“q”,“r”,分別表示t0可分配的寄存器范圍為EAX、EDX、ECX、EBX,t1可分配的寄存器范圍為EAX、EDX、ECX、EBX、ESI、EDI、EBP、ESP.圖5所示的INDEX_op_add_i32為加法add_i32指令的索引,其中第二字符串?dāng)?shù)組“0”表示指令add_i32的t0操作數(shù)和t1操作數(shù)之間可能存在依賴關(guān)系,即t0和t1為同一個(gè)臨時(shí)變量,既作為輸入也作為輸出參數(shù),“ri”表示操作數(shù)t2可分配4個(gè)通用寄存器一個(gè)或者是一個(gè)立即數(shù).圖5所示的INDEX_op_shl_i32為算術(shù)移位指令shl_i32的索引,第1個(gè)參數(shù)和第2個(gè)參數(shù)寄存器的分配范圍與加法指令add_i32的相同,第3個(gè)參數(shù)只可為立即數(shù)或寄存器ECX.

基本塊內(nèi)臨時(shí)變量寄存器分配采用線性掃描固定寄存器順序(first-mean-busy,FMB)分配機(jī)制,即“最靠前意味著最忙碌”,通過線性掃描目標(biāo)體系提供的寄存器數(shù)組索引進(jìn)行本地寄存器的分配.分配機(jī)制的實(shí)現(xiàn)過程如下：當(dāng)中間變量需要進(jìn)行本地寄存器分配時(shí), 依據(jù)中間指令操作碼和中間變量位

圖5中間操作碼與寄存器之間的約束

Fig.5Constraintsbetweenoperationcodeandregister置,確定臨時(shí)變量可分配寄存器范圍；然后從數(shù)組的起點(diǎn)開始遍歷,當(dāng)遇到寄存器索引處于"空閑狀態(tài)"時(shí),即作為指定分配的寄存器.將該寄存器的狀態(tài)置成"忙碌",中止遍歷,等對(duì)應(yīng)中間變量使用結(jié)束后,則釋放該寄存器,恢復(fù)成”空閑”狀態(tài).若遍歷完的寄存器數(shù)組索引都處于"忙碌"的狀態(tài),采用線性遍歷寄存器數(shù)組從數(shù)組中強(qiáng)制“溢出”一個(gè)寄存器作為指定分配的寄存器.因溢出的寄存器保存著上一個(gè)臨時(shí)變量的值,在釋放寄存器的同時(shí)將“溢出”的寄存器保存的值回寫入內(nèi)存中,保證寄存器中的值不丟失.

2.2當(dāng)前機(jī)制存在的缺陷

當(dāng)前指令間的寄存器分配方法采取簡單的線性掃描和溢出,指令內(nèi)變量的寄存器分配采用優(yōu)先級(jí)的方法.利用操作數(shù)可分配寄存器個(gè)數(shù)劃分優(yōu)先級(jí),避免寄存器分配競(jìng)爭(zhēng)時(shí)導(dǎo)致操作數(shù)分配不到寄存器資源,但指令間寄存器分配競(jìng)爭(zhēng)沒有相關(guān)的優(yōu)化算法.若發(fā)生資源競(jìng)爭(zhēng),進(jìn)行寄存器溢出的方法處理,顯然存在不合理之處.以在x86宿主機(jī)翻譯aplha可執(zhí)行程序?yàn)槔?如圖6所示.

圖6　中間表示與翻譯后的本地指令Fig.6　Intermediate representation and local instruction after translation

圖6中,左邊為中間代碼,右邊為經(jīng)翻譯后生成x86本地指令.每條中間指令的序號(hào)與翻譯生成本地指令序號(hào)是一一對(duì)應(yīng)關(guān)系,其中④指令將ecx寄存器分配給了tmp0,⑨指令是一條算術(shù)移位指令,在2.1節(jié)中shl_i32指令第3個(gè)操作數(shù)只能為立即數(shù)或者分配為寄存器ECX,但因ECX寄存器已分配,只能采取寄存器溢出的方法.將寄存器值寫回到內(nèi)存,如圖6右邊⑨指令地址0xb7f9ff9b將寄存器ECX的值寫回到虛擬寄存器.若后續(xù)引用該虛擬寄存器,則從虛擬寄存器中讀回,如圖中指令0xb7f9ffa3處從虛擬寄存器0x6b1c(%ebp)取值并賦值給寄存器ESI.若在處理④指令時(shí)將寄存器ESI分配給變量tmp0,顯然生成⑨本地指令中虛擬寄存器的讀寫指令是冗余的.存在上述冗余訪存虛擬寄存器指令的原因是因?yàn)橹噶睥芗拇嫫鞣峙洳呗允呛唵蔚陌凑占拇嫫黜樞蚓€性掃描方法分配寄存器,未考慮指令間的寄存器分配競(jìng)爭(zhēng)會(huì)造成冗余的指令產(chǎn)生.

針對(duì)上述由于寄存器溢出導(dǎo)致冗余訪存的情況,提出基于優(yōu)先級(jí)線性掃描寄存器分配算法(linearscanregisterallocationalgorithmbasedonpriorty,LSRAP),以指令內(nèi)操作數(shù)可分配寄存器個(gè)數(shù)最少作為優(yōu)先級(jí)的基礎(chǔ).首先在變量活性分析階段分析基本塊內(nèi)指令,以指令內(nèi)操作數(shù)寄存器分配個(gè)數(shù),避免指令間寄存器分配不必要的寄存器溢出,減少生成本地代碼指令數(shù)目,提高本地代碼指令的執(zhí)行效率.

3LSRAP算法

目前寄存器分配方法存在的問題是對(duì)所有的基本塊指令間寄存器分配采用統(tǒng)一的固定順序,但基本塊與基本塊之間是存在差異性的,基本塊內(nèi)的指令組成各不相同,對(duì)寄存器的需求也不一致,固定的寄存器分配順序與單條指令的最優(yōu)分配結(jié)合沒有使整個(gè)基本塊寄存器分配達(dá)到最優(yōu).本文提出基于優(yōu)先級(jí)線性掃描寄存器分配算法,線性掃描基本塊內(nèi)有效的中間指令,統(tǒng)計(jì)并排序指令操作數(shù)預(yù)分配寄存器數(shù)目,依據(jù)寄存器預(yù)分配需求數(shù)量動(dòng)態(tài)調(diào)整寄存器分配順序.若可分配的寄存器的統(tǒng)計(jì)數(shù)目越大,則基本塊內(nèi)指令對(duì)該寄存器的需求越大,分配該寄存器的優(yōu)先級(jí)越高,最先分配出去,剩余指令寄存器分配時(shí)壓力越小,反之優(yōu)先級(jí)越低,最慢分配出去,剩余指令分配該寄存器越困難,從而寄存器溢出的可能性變小,使基本塊內(nèi)每條指令寄存器分配達(dá)到最優(yōu).該算法的流程圖如圖7所示.

圖7　LSRAP算法流程圖Fig.7　LSRAP algorithm flowchart

首先,TCG上下文是動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)前端二進(jìn)制文件解析與后端代碼生成的橋梁,記錄了基本塊的全局變量個(gè)數(shù)、tb塊鏈地址及內(nèi)存池等信息.該算法以該數(shù)據(jù)結(jié)構(gòu)作為基礎(chǔ),在該結(jié)構(gòu)體中定義一最大可分配寄存器數(shù)目大小的數(shù)組regAllocatedNum及寄存器分配順序索引的數(shù)組regOrder,分別用于記錄基本塊內(nèi)寄存器可被允許分配次數(shù)及基本塊內(nèi)寄存器分配時(shí)順序,翻譯基本塊時(shí)初始化數(shù)組regOrder為默認(rèn)的分配順序,清空數(shù)組regAllocatedNum為0.

其次,在變量活性分析階段線性掃描基本塊內(nèi)的中間指令獲取該指令操作數(shù)預(yù)分配的寄存器,統(tǒng)計(jì)寄存器分配數(shù)目.對(duì)預(yù)分配寄存器計(jì)數(shù)時(shí)分成2種情況,因全局變量分配成一個(gè)固定的寄存器,翻譯成本地指令時(shí),其他變量均不能使用該寄存器,該固定寄存器的計(jì)數(shù)器采取直接置0的方法,其他寄存器只須將對(duì)應(yīng)序號(hào)寄存器的分配計(jì)數(shù)器regAllocatedNum采取累加的方法,反復(fù)迭代完成寄存器分配計(jì)數(shù)器的統(tǒng)計(jì),算法的偽代碼如圖8所示.

圖8　寄存器分配次數(shù)統(tǒng)計(jì)偽代碼Fig.8　Register allocation count pseudo-code

最后,依據(jù)寄存器分配計(jì)數(shù)器regAllocatedNum進(jìn)行降序排序,數(shù)值越大說明基本塊內(nèi)支持分配該寄存器指令越多,優(yōu)先級(jí)越高,越容易分配出去；反之,數(shù)值越小說明只允許基本塊內(nèi)部分指令能分配該寄存器,分配該寄存器越困難,若數(shù)值為0,則說明該寄存器只能分配成固定的全局變量,其他變量沒權(quán)利分配該寄存器.

4實(shí)驗(yàn)與分析

該實(shí)驗(yàn)采用QEMU模擬器作為動(dòng)態(tài)二進(jìn)制翻譯平臺(tái),它的寄存器分配采用默認(rèn)固定順序寄存器分配方法.為了驗(yàn)證固定順序分配法存在的缺陷和該算法的跨平臺(tái)實(shí)際優(yōu)化效果,通過正確性測(cè)試、本地代碼指令統(tǒng)計(jì)和整體性能測(cè)試對(duì)提出的算法進(jìn)行評(píng)估,對(duì)比不同固定順序的寄存器分配方法在不同平臺(tái)上的運(yùn)行效果.

為了對(duì)比說明實(shí)驗(yàn)的效果,除QEMU采用固定默認(rèn)寄存器分配順序外,手動(dòng)修改源平臺(tái)寄存器分配順序,如表1的寄存器分配模式所示.其中,順序0是QEMU采用的默認(rèn)固定寄存器分配順序.

表1　寄存器分配模式

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

在QEMU上運(yùn)行nbench-2.2.3benchmarksuite(QEMU官方網(wǎng)站推薦用于評(píng)測(cè)性能的測(cè)試程序)作為實(shí)驗(yàn)的測(cè)試集.所有的執(zhí)行速度是5次測(cè)試的算術(shù)平均值.

實(shí)驗(yàn)均是在宿主機(jī)Intel(R)Core(TM)2QuadCPUQ8200 @ 2.33GHz平臺(tái)翻譯mips交叉編譯器、arm交叉編譯器及i386的gcc編譯器編譯nbench測(cè)試集,各編譯器的版本如表2所示.

表2　編譯器版本

4.2正確性測(cè)試

開啟nbench-2.2.3benchmarksuite的調(diào)試選項(xiàng),在x86平臺(tái)上使用arm、mips交叉編譯器編譯nbench測(cè)試集；啟動(dòng)源平臺(tái)算法改進(jìn)后的QEMU,傳入編譯好的測(cè)試案例可執(zhí)行文件,從調(diào)試信息獲取執(zhí)行結(jié)果,如表3所示.

表3　nbench運(yùn)行正確性測(cè)試

實(shí)驗(yàn)顯示,該算法翻譯執(zhí)行不同目標(biāo)平臺(tái)的nbench,且執(zhí)行的結(jié)果與改進(jìn)前nbench執(zhí)行的結(jié)果是一致的,表明該算法能夠進(jìn)行正確的翻譯,具有很高的可信度.

4.3本地代碼指令測(cè)試

為了對(duì)比不同平臺(tái)nbench下測(cè)試案例在算法優(yōu)化前、后對(duì)生成本地代碼指令的影響,利用QEMU的日志輸出功能,統(tǒng)計(jì)了不同平臺(tái)下采取不同模式寄存器分配方法的本地代碼指令數(shù)目,如表4所示.

本地代碼指令數(shù)目反映了運(yùn)行nbench運(yùn)行的時(shí)間.生成的本地代碼指令越少,間接執(zhí)行本地代碼時(shí)間越少.從表4的數(shù)據(jù)結(jié)果來看,不同的寄存器分配順序生成的目標(biāo)代碼指令數(shù)目各不相同,表明寄存器分配順序影響QEMU翻譯系統(tǒng)生成本地代碼指令；其次通過LSRAP算法改進(jìn)生成本地代碼指令數(shù)目比QEMU固定順序寄存器分配都少,比寄存器默認(rèn)分配方法少2.2%～3.4%.

表4　不同寄存器分配模式下本地指令數(shù)目統(tǒng)計(jì)

4.4整體性能評(píng)價(jià)

為了對(duì)比LSRAP算法對(duì)QEMU整體性能的影響,采用統(tǒng)計(jì)QEMU翻譯執(zhí)行測(cè)試程序每秒迭代次數(shù).該測(cè)試集的執(zhí)行結(jié)果直接反映該算法對(duì)翻譯系統(tǒng)的性能影響效果,采取不同目標(biāo)平臺(tái)的nbench和不同寄存器分配模式進(jìn)行實(shí)驗(yàn).記QEMU默認(rèn)寄存器分配方法每秒迭代次數(shù)為IQEMU,QEMU經(jīng)LSRAP算法優(yōu)化后每秒迭代次數(shù)為IAQEMU,加速比記作nsp=IAQEMU/IQEMU,如表5～7所示.

表5　i386體系nbench測(cè)試結(jié)果

表6　mips體系nbench測(cè)試結(jié)果

表7　arm體系nbench測(cè)試結(jié)果

通過不同平臺(tái)上nbench測(cè)試結(jié)果可以驗(yàn)證不同寄存器分配順序程序執(zhí)行效果表現(xiàn)各不相同,其中默認(rèn)的寄存器分配順序測(cè)試案例執(zhí)行效果明顯略差于手動(dòng)修改寄存器分配順序；其次動(dòng)態(tài)調(diào)整寄存器分配順序每秒迭代次數(shù)略大于固定寄存器分配順序,經(jīng)算法改進(jìn)后nbench的測(cè)試案例每秒迭代次數(shù)arm、mpis、i386平臺(tái)都有不錯(cuò)的提升效果,性能提升效果與具體測(cè)試用例相關(guān),其中STRING_SORT和BITFIELD的測(cè)試案例優(yōu)化提升性能最高.依據(jù)表5～7的測(cè)試數(shù)據(jù)可得,動(dòng)態(tài)翻譯i386平臺(tái)下的nbench各個(gè)測(cè)試案例性能提升1.2%～16.4%,所有測(cè)試案例的平均性能提升約為6.7%；動(dòng)態(tài)翻譯mips平臺(tái)下的nbench各個(gè)測(cè)試案例性能提升1.6%～17.2%,所有測(cè)試案例的平均性能提升約為6.8%；動(dòng)態(tài)翻譯arm平臺(tái)下的nbench各個(gè)測(cè)試案例性能提升1.0%～14.1%,所有測(cè)試案例的平均性能提升約為4.7%,說明該算法具有良好的跨平臺(tái)性.由此可以推斷LSRAP算法雖然作為程序執(zhí)行開銷的一部分,但是相對(duì)于整體性能的提升而言影響很小.實(shí)驗(yàn)結(jié)果表明,本文的優(yōu)化方法是行之有效的.

5結(jié)語

本文重點(diǎn)介紹了QEMU的運(yùn)行原理,分析闡述QEMU的寄存器分配算法機(jī)制,舉例說明該機(jī)制存在的缺點(diǎn),并提出基于優(yōu)先級(jí)的動(dòng)態(tài)二進(jìn)制翻譯寄存器分配算法.該算法利用中間表示操作碼和本地指令指令之間的映射關(guān)系統(tǒng)計(jì)基本塊內(nèi)預(yù)分配寄存器次數(shù),確定寄存器使用分配的優(yōu)先級(jí)順序.該算法具有很好的跨平臺(tái)特性,不同目標(biāo)平臺(tái)的可執(zhí)行nbench測(cè)試案例執(zhí)行效果都有一定的提升.實(shí)驗(yàn)結(jié)果表明,采用該算法可以有效地提高QEMU的執(zhí)行效率.

參考文獻(xiàn)(References)：

[1]PENNEMANN,KUDINSKASD,RAWSTHORNEA,etal.EvaluationofdynamicbinarytranslationtechniquesforfullsystemvirtualisationonARMv7-A[J].JournalofSystemsArchitecture, 2016, 65: 30-45．

[2] 馬湘寧. 二進(jìn)制翻譯關(guān)鍵技術(shù)研究[D]. 北京：中國科學(xué)院計(jì)算技術(shù)研究所, 2004．

MAXiang-ning.Researchonkeytechnologytobinarytranslation[D].Beijing:InstituteofComputingTechnologyChineseAcademyofSciences, 2004．

[3]HAWKINSB,DEMSKYB,BRUENINGD,etal.Optimizingbinarytranslationofdynamicallygeneratedcode[C]∥Proceedingsofthe13thAnnualIEEE/ACMInternationalSymposiumonCodeGenerationandOptimization.IEEE/ACMInternationalSymposiumonCodeGenerationandOptimization, 2015: 68-78．

[4]GSCHWINDM,ALLMANER,SATHAYES.etal.Dynamicandtransparentbinarytranslation[J].IEEEComputer, 2000, 33(3): 54-59．

[5]WEGMANMN,ZADECKFK.Constantpropagationwithconditionalbranches[J].ACMTransactionsonProgrammingLanguagesandSystems(TOPLAS), 1991, 13(2): 181-210．

[6]MUTHR.Registerlivenessanalysisofexecutablecode[EB/OL].[2015-07-07].www.cs.arizona.edu/alto/papers/liveness.ps．

[7] 馬湘寧, 武成崗, 唐鋒, 等. 二進(jìn)制翻譯中的標(biāo)志位優(yōu)化技術(shù) [J]. 計(jì)算機(jī)研究與發(fā)展, 2005, 42(2): 329-337．

MAXiang-ning,WUCheng-gang,TANGFeng,etal.Twoconditioncodeoptimizationapproachesinbinarytranslation[J].JournalofComputerResearchandDevelopment,2005, 42(2): 329-337．

[8]EBCIOGLUK,ALTMANE,GSCHWINDM,etal.Dynamicbinarytranslationandoptimization[J].IEEETransactionsonComputers, 2001, 50(6): 529-548．

[9]CHAITINGJ,AUSLANDERMA,CHANDRAAK,etal.Registerallocationviacoloring[J].ComputerLanguages, 1981, 6(1): 47-57．

[10]CHAITINGJ.Registerallocationandspillingviagraphcoloring[J].ACMSigplanNotices, 1982, 17(6): 98-101．

[11]TRAUBO,HOLLOWAYG,SMITHMD.Qualityandspeedinlinear-scanregisterallocation[J].AcmSigplanNotices, 2010, 33(5):142-151.

[12]POLETTOM,SARKARV.Linearscanregisterallocation[J].ACMTransactionsonProgrammingLanguagesandSystems(TOPLAS), 1999, 21(5): 895-913．

[13]ALEILiang,GUANHai-bing,LIZeng-xing.AresearchonregistermappingstrategiesofQEMU[C]∥Proceedingsofthe2ndInternationalSymposiumonIntelligenceComputationandApplications(ISICA'2007).Wuhan: [s.n.], 2007: 168-172．

[14] 吳浩. 二進(jìn)制翻譯系統(tǒng)QEMU中的優(yōu)化技術(shù)[D]. 上海：上海交通大學(xué), 2007．

WUHao.OptimizationtechnologyofQEMU[D].Shanghai:ShanghaiJiaoTongUniversity, 2007．

[15] 文延華, 唐大國, 漆鋒濱. 二進(jìn)制翻譯中的寄存器映射與剪裁的實(shí)現(xiàn) [J]. 軟件學(xué)報(bào), 2009, 20(2): 1-7．

WENYan-hua,TANGDa-guo,QIFeng-bin.Registermappingandregisterfunctioncuttingoutimplementationinbinarytranslation[J].JournalofSoftware, 2009, 20(2): 1-7．

[16] 廖銀, 孫廣中, 姜海濤, 等. 動(dòng)態(tài)二進(jìn)制翻譯中全寄存器直接映射方法 [J]. 計(jì)算機(jī)應(yīng)用與軟件, 2011, 28(11): 21-24．

LIAOYin,SUNGuang-zhong,JIANGHai-tao,etal.Allregistersdirectmappingmethodindynamicbinarytranslation[J].ComputerApplicationsandSoftware, 2011, 28(11): 21-24．

[17]CAIZ,LIANGA,QIZ,etal.Performancecomparisonofregisterallocationalgorithmsindynamicbinarytranslation[C]∥InternationalConferenceonKnowledgeandSystemsEngineering.Hanoi:IEEE, 2009: 113-119．

[18]LIANGY,SHAOY,YANGG,etal.RegisterallocationforQEMUdynamicbinarytranslationsystems[J].InternationalJournalofHybridInformationTechnology, 2015, 8(2): 199-210．

[19]FABRICEB.QEMU,afastandportabledynamictranslator[C]∥Atec05:ConferenceonUsenixTechnicalConference.[S.l.]:Usenix,2005．

[20] 張西超,郭向英,趙雷,等.TCG動(dòng)態(tài)二進(jìn)制翻譯技術(shù)研究 [J]. 計(jì)算機(jī)應(yīng)用與研究,2013,30(11)：34-37．

ZHANGXi-chao,GUOXiang-ying,ZHAOLei,etal.StudyonTCGdynamicbinarytranslationtechnique[J].ComputerApplicationandSoftware, 2013, 30(11): 34-37.

收稿日期：2015-07-07.浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61472447).

作者簡介：戴濤(1990-)，男，碩士生，從事二進(jìn)制翻譯及軟件逆向研究.ORCID：0000-0001-7009-9227.E-mail: daitworld@126.com 通信聯(lián)系人：單征，男，副教授.ORCID：0000-0001-9618-8551.E-mail: zzzhengming@163.com

DOI:10.3785/j.issn.1008-973X.2016.07.016

中圖分類號(hào)：TP 314; TN 332

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-973X(2016)07-1338-09

Registerallocationalgorithmofdynamicbinarytranslationbasedonpriority

DAITao,SHANZheng,LUShuai-bing,SHIQiang,TANJie

(State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Information Engineering University, Zhengzhou 450002, China)

Abstract:QEMU uses a simple sequential allocation algorithm to deal with all the basic blocks without considering the difference between the basic block, which causes a lot of register overflow. A more efficient priority-based linear scan register allocation algorithm was presented based on the mapping between intermediate representation and the source platform register, dynamically adjusting register allocation sequence to reduce register spilling times and the number of generated native code instructions by counting and ordering the pre-allocated registers of a basic block. The improved algorithm has a good cross-platform based on intermediate code, effectively reducing the generation of local code instructions. Experimental results show that the algorithm is better than the performance of QEMU before optimization, which respectively upgrades about 6.7%, 6.8%, 4.7% in x86 platform, mips platform and arm platform.

Key words:dynamic binary translation; register allocation; QEMU; intermediate code