李 男，龐建民

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

二進(jìn)制翻譯技術(shù)[1-2]是作為程序等價(jià)變換工具產(chǎn)生并發(fā)展起來的，被定義為一種機(jī)器上的指令序列到另一種機(jī)器上指令序列的等價(jià)轉(zhuǎn)換過程。它在豐富國產(chǎn)平臺(tái)軟件生態(tài)的過程中，發(fā)揮了重要作用。

二進(jìn)制翻譯按照實(shí)現(xiàn)方式主要包含靜態(tài)翻譯和動(dòng)態(tài)翻譯[3]。靜態(tài)翻譯采用的是一種先翻譯后執(zhí)行的“離線翻譯”方式，實(shí)現(xiàn)了“一次翻譯，多次執(zhí)行”，其翻譯過程與執(zhí)行過程彼此獨(dú)立，翻譯時(shí)間不計(jì)入系統(tǒng)時(shí)間。動(dòng)態(tài)翻譯采用的是一種邊翻譯、邊執(zhí)行的“捆綁式”工作方式，可以實(shí)現(xiàn)多源到多目標(biāo)的程序翻譯，由于可以獲得運(yùn)行時(shí)信息，因此動(dòng)態(tài)翻譯能夠解決靜態(tài)翻譯難以解決的動(dòng)態(tài)地址發(fā)現(xiàn)和自修改代碼的問題。但是，動(dòng)態(tài)翻譯本身需要占用部分系統(tǒng)時(shí)間。翻譯優(yōu)化問題一直是動(dòng)態(tài)翻譯的研究熱點(diǎn)[4-6]。本文在不引起歧義的情況下，將待翻譯二進(jìn)制文件的生成平臺(tái)稱為源平臺(tái)，將動(dòng)態(tài)二進(jìn)制翻譯器運(yùn)行的平臺(tái)稱本地平臺(tái)或目標(biāo)平臺(tái)。

1 問題的提出

動(dòng)態(tài)二進(jìn)制翻譯在實(shí)現(xiàn)多源到多目標(biāo)的程序翻譯過程中，為了屏蔽不同源平臺(tái)間的硬件差異，引入了中間代碼，可以將任何源平臺(tái)的指令先轉(zhuǎn)化成中間代碼，再轉(zhuǎn)化成目標(biāo)平臺(tái)指令。在中間代碼生成過程中，動(dòng)態(tài)二進(jìn)制翻譯采用了內(nèi)存虛擬機(jī)制，借助臨時(shí)變量和環(huán)境變量，將對源平臺(tái)特定寄存器的訪問操作轉(zhuǎn)化為與寄存器無關(guān)的內(nèi)存訪問操作。臨時(shí)變量用來暫存變量，一般使用tempX的形式來表示，例如temp0，temp1等；環(huán)境變量是一種全局變量，用來模擬源平臺(tái)的CPU環(huán)境，負(fù)責(zé)將臨時(shí)變量存儲(chǔ)到本地內(nèi)存，一般使用env的形式來表示。env有多種實(shí)現(xiàn)形式，例如X86平臺(tái)對應(yīng)的env數(shù)據(jù)結(jié)構(gòu)如圖1中的CPUX86State所示，其成員變量regs[CPU_NB_REGS]用來模擬X86平臺(tái)的寄存器，此時(shí)常量CPU_NB_REGS=9。

圖1 X86平臺(tái)下的env結(jié)構(gòu)

Fig.1 env structure on X86 platform

利用內(nèi)存虛擬機(jī)制，二進(jìn)制翻譯器在處理與源平臺(tái)寄存器有關(guān)的指令時(shí)，借助env將其轉(zhuǎn)化成對本地內(nèi)存空間的操作。圖 2展示了X86平臺(tái)的立即數(shù)加法被翻譯到中間代碼的過程。源平臺(tái)第1條movl匯編指令是立即數(shù)傳送指令，使用了通用寄存器eax，經(jīng)過內(nèi)存虛擬機(jī)制，被翻譯為2條中間代碼：第1條中間代碼是movi_i32 temp0,S|0x1，表示將立即數(shù)0x1暫存于臨時(shí)變量temp0中；第2條中間代碼是st_i32 temp0 env,S|0x0，表示將temp0存儲(chǔ)于由環(huán)境變量env和偏移量0指定的本地內(nèi)存位置。由環(huán)境變量env與偏移量構(gòu)成的虛擬內(nèi)存位置等價(jià)表示了源平臺(tái)的位置，實(shí)現(xiàn)了去源平臺(tái)化，這就是內(nèi)存虛擬的含義。

圖2 立即數(shù)加法的翻譯過程Fig.2 Translation process of immediate addition instruction

內(nèi)存虛擬策略在屏蔽源平臺(tái)硬件差異的同時(shí)，會(huì)帶來中間代碼的膨脹問題。在圖 2的示例中，源平臺(tái)的前2條指令被分別翻譯為2條中間代碼，第3條指令被翻譯為6條中間代碼?？偟拇a膨脹達(dá)到3.3倍。造成中間代碼膨脹的原因在于中間代碼生成機(jī)制依賴于頻繁的內(nèi)存模擬操作。

在針對中間代碼優(yōu)化的相關(guān)研究中，主要采用的方法有兩類：第一類與后端冗余指令相關(guān)，文獻(xiàn)[7]提出了線性掃描冗余l(xiāng)dM和stM指令的匹配刪除算法來刪除冗余指令；文獻(xiàn)[8]引用活性分析技術(shù)對快速模擬器(Quick EMUlator, QEMU)[9]后端無內(nèi)部互鎖流水級(jí)的微處理器(Microprocessor without Interlocked Piped Stages, MIPS)冗余MOVE指令提出了刪除算法。另一類方法與寄存器分配策略相關(guān)，文獻(xiàn)[10]詳細(xì)分析了QEMU下的寄存器管理機(jī)制，但并未提出自己的優(yōu)化方案；文獻(xiàn)[11]實(shí)現(xiàn)了X86平臺(tái)到龍芯平臺(tái)的寄存器映射，映射的寄存器范圍限于源平臺(tái)的eax、esp、ebp三個(gè)寄存器和龍芯平臺(tái)的S4、S5、S6三個(gè)寄存器；文獻(xiàn)[12]提出了一種在寄存器映射過程中進(jìn)行裁剪的方法，借助裁剪函數(shù)實(shí)現(xiàn)了PowerPC平臺(tái)到ALPHA平臺(tái)的寄存器映射；文獻(xiàn)[13]實(shí)現(xiàn)了X86平臺(tái)下的8個(gè)通用寄存器向MIPS平臺(tái)的映射；文獻(xiàn)[14]提出一種基于優(yōu)先級(jí)的動(dòng)靜結(jié)合寄存器映射優(yōu)化算法，首先根據(jù)源平臺(tái)寄存器的統(tǒng)計(jì)特征進(jìn)行靜態(tài)全局寄存器映射，然后通過獲取基本塊中間指令需求確定寄存器分配的優(yōu)先級(jí)，進(jìn)行動(dòng)態(tài)寄存器分配。

基于上述研究，本文將特殊指令匹配與寄存器直接映射思想應(yīng)用在二進(jìn)制翻譯中間代碼的優(yōu)化過程中，對造成中間代碼膨脹的典型場景進(jìn)行分析歸納，找出特定指令動(dòng)作的組合，通過建立相應(yīng)的映射規(guī)則，將內(nèi)存虛擬表示轉(zhuǎn)化為對本地寄存器的直接操作，從而提高翻譯效率。

2 優(yōu)化方法

2.1 中間表示函數(shù)

動(dòng)態(tài)二進(jìn)制翻譯使用內(nèi)存虛擬策略時(shí)，中間代碼的生成是通過調(diào)用中間表示函數(shù)(序列)實(shí)現(xiàn)的，一次內(nèi)存模擬操作需要調(diào)用一個(gè)中間表示函數(shù)序列，由多個(gè)中間表示函數(shù)的組合進(jìn)行實(shí)現(xiàn)。例如，對于x86平臺(tái)下的數(shù)據(jù)傳送指令MOVIm,reg，內(nèi)存虛擬機(jī)制會(huì)調(diào)用兩條中間表示函數(shù)gen_op_movl_T0_im()和gen_op_movl_reg_T0()生成中間代碼。表1給出了這兩條中間表示函數(shù)的功能描述和定義。

表1 中間表示函數(shù)示例

中間表示函數(shù)gen_op_movl_T0_im()用來實(shí)現(xiàn)將立即數(shù)暫存于臨時(shí)變量CPU_T[0]中，中間表示函數(shù)gen_op_movl_reg_T0()用來實(shí)現(xiàn)將立即數(shù)存入對應(yīng)于源寄存器的本地內(nèi)存區(qū)域。類似于這樣的中間表示函數(shù)還有很多，它們的函數(shù)名稱都以gen_op_作為前綴，以特定的指令動(dòng)作名稱作為后綴。基于中間表示函數(shù)，可以進(jìn)一步對相關(guān)機(jī)器指令操作，特別是造成中間代碼膨脹的寄存器操作進(jìn)行描述。

2.2 基于中間表示函數(shù)的特定指令動(dòng)作描述

在圖2的示例中，源平臺(tái)的代碼翻譯到中間代碼后，反復(fù)出現(xiàn)了立即數(shù)提取指令movi_i32，加載指令ld_i32，以及存儲(chǔ)指令st_i32等。通過大量的代碼分析得出，中間代碼膨脹主要與四種寄存器操作相關(guān)，包括立即數(shù)提取操作、加載操作、存儲(chǔ)操作和臨時(shí)變量操作，本文將上述四種造成中間代碼膨脹的特殊指令操作稱為特定指令動(dòng)作。

使用中間表示函數(shù)可以對這四種特定指令動(dòng)作進(jìn)行描述，并進(jìn)一步抽象，方便后續(xù)的優(yōu)化工作。例如，立即數(shù)提取操作可以使用中間表示函數(shù)類gen_op_movl_A_im表示，并可進(jìn)一步簡化表示為op_mov_im(A,Im)。

四種特定指令動(dòng)作的描述如下：

1)立即數(shù)提取操作：op_mov_im(A,Im)∈{gen_op_movl_A_im}。

2)加載操作：op_ld(A,α)∈{gen_op_movl_A_reg(α)}。

3)存儲(chǔ)操作：op_st(α,A)∈{gen_op_movl_reg(α)_A}。

4)臨時(shí)變量操作：op(A),op(A,B)。第一個(gè)參數(shù)A用于存儲(chǔ)運(yùn)算后的結(jié)果。

其中，A,B∈{T0,T1,A0}。

以此為基礎(chǔ)，分析造成中間代碼膨脹的典型場景，找到與其相關(guān)的特定指令動(dòng)作組合，然后運(yùn)用寄存器直接映射思想，使用少量的本地寄存器操作進(jìn)行等價(jià)替換，從而降低中間代碼膨脹。

3 優(yōu)化方法的實(shí)現(xiàn)

在實(shí)現(xiàn)將內(nèi)存虛擬操作映射到本地寄存器的過程中，需要解決好兩個(gè)問題：一是要保證寄存器在映射過程中的一致性。二是要建立等價(jià)的中間表示替換規(guī)則。

針對第一個(gè)問題，首先需要構(gòu)建合適的映射公式，同時(shí)，還要保證源平臺(tái)每一個(gè)待映射的寄存器都能夠映射到本地平臺(tái)的某個(gè)寄存器上。當(dāng)本地平臺(tái)的寄存器數(shù)量遠(yuǎn)大于或等于源平臺(tái)的寄存器數(shù)量時(shí)，可以選擇本地平臺(tái)的部分寄存器進(jìn)行映射。當(dāng)本地平臺(tái)的寄存器數(shù)量小于源平臺(tái)的寄存器數(shù)量時(shí)，可以采用活性分析技術(shù)加以解決。3.1節(jié)給出了實(shí)現(xiàn)過程。

針對第二個(gè)問題，需要找到與中間代碼膨脹相關(guān)的特定指令動(dòng)作的組合，通過構(gòu)建相應(yīng)的映射規(guī)則，實(shí)現(xiàn)將原有的內(nèi)存虛擬操作轉(zhuǎn)化為對本地平臺(tái)的寄存器操作。3.2節(jié)給出了實(shí)現(xiàn)過程。

3.1 映射公式的構(gòu)建

本文研究的源平臺(tái)為X86平臺(tái)，目標(biāo)平臺(tái)是國產(chǎn)申威平臺(tái)，源平臺(tái)包含9個(gè)通用寄存器，目標(biāo)平臺(tái)包含32個(gè)通用寄存器。目標(biāo)平臺(tái)寄存器的數(shù)量遠(yuǎn)多于源平臺(tái)寄存器的數(shù)量，滿足映射的前提條件，因此，適用于本文的優(yōu)化方法。

原有的內(nèi)存虛擬策略是借助環(huán)境變量env通過調(diào)用使用env→regs[α]實(shí)現(xiàn)的，本文在實(shí)現(xiàn)內(nèi)存虛擬操作到本地寄存器映射時(shí)，引入臨時(shí)變量數(shù)組reg[i]，建立了式(1)和表2所示的映射關(guān)系。

env→regs[α]→reg[i] (1)

在式(1)中，臨時(shí)變量數(shù)組reg[i]的自變量取值范圍由源平臺(tái)寄存器的數(shù)量決定，例如，源平臺(tái)X86平臺(tái)包含9個(gè)通用寄存器，則reg[i]中i的取值為0≤i≤8。而目標(biāo)申威平臺(tái)包含32個(gè)通用寄存器，僅需要選用其中的部分寄存器進(jìn)行本地映射即可。本文選用申威平臺(tái)下的r7到r15作為本地寄存器進(jìn)行映射，表2顯示了具體的映射關(guān)系。

3.2 中間表示替換規(guī)則的建立

2.2節(jié)中已經(jīng)提到中間代碼的膨脹往往和一些特定指令動(dòng)作的組合相關(guān)，針對中間代碼膨脹呈現(xiàn)出的幾種典型場景，應(yīng)用式(1)，可以建立以下4條基本替換規(guī)則：

替換規(guī)則C1：如果存在相鄰的特定指令動(dòng)作op_mov_im(A,Im)和op_st(reg(α),A)其中A∈{T0,T1,A0}，則可以使用op_mov_im(reg[α],Im))替代op_mov_im(A,Im)和op_st(reg(α),A)。

C1的典型應(yīng)用場景：將立即數(shù)移動(dòng)到虛擬內(nèi)存。

分析：將立即數(shù)Im提取到中間變量A，然后將中間變量A存儲(chǔ)到虛擬內(nèi)存reg(α)的操作序列，這與將立即數(shù)Im存儲(chǔ)到寄存器reg(α)的操作功能等價(jià)。

替換規(guī)則C2：如果存在相鄰的特定指令動(dòng)作op(A)、op_ld(B,reg(α))、op(B，A)和op_st(reg(α),B)，其中A、B∈{T0,T1,A0}，則可以使用op(reg[α]，A)替代op_ld(B,reg(α))、op(B，A)和op_st(reg(α),B)。

C2的典型應(yīng)用場景：虛擬內(nèi)存與立即數(shù)的計(jì)算結(jié)果存入同一虛擬內(nèi)存。

分析：將虛擬內(nèi)存reg(α)提取到中間變量B，然后將中間變量B和A的計(jì)算結(jié)果臨時(shí)存儲(chǔ)到B中，再將B存儲(chǔ)到虛擬內(nèi)存reg(α)的操作序列，這與將虛擬內(nèi)存reg(α)和中間變量A的計(jì)算結(jié)果存儲(chǔ)到虛擬內(nèi)存reg(α)的操作功能等價(jià)。

替換規(guī)則C3：如果存在相鄰的特定指令動(dòng)作op_ld(A,reg(α))、op(A)和op_st(reg(α),A)，其中A∈{T0,T1,A0}，則可以使用op(reg[α])替代op_ld(A,reg(α))、op(A)和op_st(reg(α),A)。

C3的典型應(yīng)用場景：僅操作同一虛擬內(nèi)存數(shù)據(jù)。

分析：將虛擬內(nèi)存reg(α)提取到中間變量A，然后對A進(jìn)行相關(guān)計(jì)算并保存計(jì)算結(jié)果到A，再將A寫回虛擬內(nèi)存reg(α)的操作序列，這與將虛擬內(nèi)存reg(α)計(jì)算后存儲(chǔ)到自身的操作功能等價(jià)。

替換規(guī)則C4：如果存在相鄰的特定指令動(dòng)作op(A)、op_ld(A,reg(α))和op_st(reg(β),A)，其中A∈{T0,T1,A0}，則可以使用mov_reg_reg(reg[β],reg[α])替代op(A)、op_ld(A,reg(α))和op_st(reg(β),A)。

C4的典型應(yīng)用場景：僅涉及不同虛擬內(nèi)存間的數(shù)據(jù)移動(dòng)。

分析：將虛擬內(nèi)存reg(α)提取到中間變量A，然后將A的值存儲(chǔ)到虛擬內(nèi)存reg(β)的操作，這與將虛擬內(nèi)存reg(α)存儲(chǔ)到虛擬內(nèi)存reg(β)的操作功能等價(jià)。

在上述4條基本替換規(guī)則基礎(chǔ)上，還可以衍生出以下2條擴(kuò)展的替換規(guī)則：

替換規(guī)則C5：如果存在相鄰的特定指令動(dòng)作op_ld(A,reg(α))、op(B,A)和op_st(reg(β),B)，則可以使用op(reg[β],reg[α])替代op_ld(A,reg(α))、op(B,A)和op_st(reg(β),B)。

替換規(guī)則C6：如果存在相鄰的特定指令動(dòng)作op_ld(A,reg(α))，op_ld(B,reg(β))，op(B,A)和op_st(reg(β),B)，其中A,B∈{T0,T1,A0}，則可以使用op(reg[β],reg[α])替代op_ld(A,reg(α))、op_ld(B,reg(β))、op(B,A)和op_st(reg(β),B)。

上述規(guī)則提到的相鄰特定指令動(dòng)作并不要求位置連續(xù)，但必須存在于同一基本塊，這是由語義環(huán)境一致性要求決定的。通過以上6條替換規(guī)則，可以實(shí)現(xiàn)功能等價(jià)條件下的寄存器直接映射策略，將原有內(nèi)存模擬操作替換為本地寄存器操作。

4 優(yōu)化方法的應(yīng)用

下面分別以翻譯源平臺(tái)X86下的立即數(shù)加法指令和棧操作指令為例，闡述中間表示替換規(guī)則的運(yùn)用。

圖3展示了應(yīng)用替換規(guī)則后，X86平臺(tái)的立即數(shù)加法指令被翻譯到中間代碼的優(yōu)化過程。源平臺(tái)中第一條movl指令應(yīng)用替換規(guī)則C1后，將立即數(shù)0x1直接存入eax寄存器對應(yīng)的本地寄存器reg[0]中；類似地，源平臺(tái)第二條movl指令應(yīng)用替換規(guī)則C1后，將立即數(shù)0x3存入ebx寄存器對應(yīng)的本地寄存器reg[3]中；源平臺(tái)第三條addl指令應(yīng)用替換規(guī)則C6后，使用本地寄存器reg[0]和reg[3]完成相應(yīng)操作。最終，中間代碼由優(yōu)化前的10條指令簡化為優(yōu)化后的5條，中間代碼規(guī)?？s減為原來的50%。

同樣，圖4展示了應(yīng)用替換規(guī)則后，X86平臺(tái)的棧操作被翻譯到中間代碼的優(yōu)化過程。應(yīng)用替換規(guī)則后，中間代碼數(shù)量由優(yōu)化前的29條指令簡化為優(yōu)化后的16條，規(guī)模減少了44.8%。

圖3 立即數(shù)加法指令的中間代碼優(yōu)化示例Fig.3 Example of intermediate code optimization for immediate addition instruction

圖4 棧操作指令的中間代碼優(yōu)化示例Fig.4 Example of intermediate code optimization for stack operation instruction

5 實(shí)驗(yàn)部分

將提出的中間代碼優(yōu)化方法在開源二進(jìn)制翻譯器QEMU1.7.2[15]進(jìn)行了實(shí)現(xiàn)。使用如表3所示的實(shí)驗(yàn)環(huán)境，源平臺(tái)采用的是X86-64架構(gòu)處理器，本地平臺(tái)采用的是國產(chǎn)申威411[16]處理器。

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

采用了正確性測試和性能測試兩種方法來驗(yàn)證優(yōu)化方法的正確性和有效性。正確性測試通過對比優(yōu)化前和優(yōu)化后的執(zhí)行結(jié)果是否一致來進(jìn)行驗(yàn)證，性能測試通過計(jì)算優(yōu)化后的中間代碼指令數(shù)量相對于優(yōu)化前的中間代碼指令數(shù)量的壓縮率來進(jìn)行驗(yàn)證，壓縮率越高優(yōu)化效果越好。測試用例選取了SPEC CPU2006[17]中的CINT2006的測試用例，如表4所示。

5.1 正確性測試

實(shí)驗(yàn)使用SPEC CPU2006進(jìn)行了正確性測試，采用的測試方法是比較優(yōu)化前后測試用例的執(zhí)行結(jié)果是否一致。表 5顯示了選取的測試用例和測試結(jié)果，測試結(jié)果表明優(yōu)化方法的正確性達(dá)到100%。

5.2 性能測試

實(shí)驗(yàn)借助QEMU翻譯SPEC CPU2006測試用例過程中產(chǎn)生的中間代碼日志文件，通過對比優(yōu)化前后日志文件中的中間指令數(shù)量，測試中間代碼優(yōu)化的效果。為了更清楚地說明測試效果，引入了代碼縮減率R，如式(2)中所示：

R=1-Nopt/Nori×100%

(2)

式(2)中，Nori代表優(yōu)化前的中間指令數(shù)量，Nopt代表優(yōu)化后的中間指令數(shù)量，R值越高表明中間代碼優(yōu)化效果越好。

實(shí)驗(yàn)記錄了每個(gè)測試用例的R值，測試結(jié)果見圖5。結(jié)果表明，中間表示規(guī)則的建立對于中間代碼的優(yōu)化效果作用明顯，各用例的代碼縮減率R平均達(dá)到32.59%?？梢钥闯觯煌美募铀傩Ч顒e較大，優(yōu)化效果最好的用例是xalancbmk，其R值達(dá)到了37.31%；優(yōu)化效果最差的用例是gcc，其R值為30.68%。通過分析用例源代碼發(fā)現(xiàn)，xalancbmk用例中包含了大量的寄存器操作，使得中間表示替換規(guī)則可以被充分使用，所以優(yōu)化效果明顯；gcc用例只包含少量的寄存器移位操作，替換規(guī)則應(yīng)用較少，所以優(yōu)化作用有限。

表4 測試用例說明

圖5 中間代碼優(yōu)化性能測試Fig.5 Performance test of intermediate code optimization

6 結(jié)論

針對動(dòng)態(tài)二進(jìn)制翻譯過程中的中間代碼膨脹問題，本文對內(nèi)存虛擬策略的實(shí)現(xiàn)機(jī)制進(jìn)行了深入分析，提出了一種基于中間表示規(guī)則替換的二進(jìn)制翻譯中間代碼優(yōu)化方法，在對中間表示函數(shù)進(jìn)行分類歸納的基礎(chǔ)上，建立了針對特定指令函數(shù)匹配的中間表示替換規(guī)則，對于能夠匹配規(guī)則的特定指令動(dòng)作，應(yīng)用建立的映射公式，使用少量的本地寄存器操作替代原有的內(nèi)存虛擬操作，進(jìn)而達(dá)到優(yōu)化中間代碼的目的。

另外，本文研究的基礎(chǔ)平臺(tái)是QEMU，具備多源到多目標(biāo)的二進(jìn)制翻譯功能，因此，本文提出的方法具有一定的泛化能力。同時(shí)，需要進(jìn)一步完善等價(jià)替換規(guī)則，從而取得更好的翻譯效果。