基于中間表示規(guī)則替換的二進制翻譯中間代碼優(yōu)化方法

李 男，龐建民

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

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

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

1 問題的提出

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

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

Fig.1 env structure on X86 platform

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

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

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

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

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

2 優(yōu)化方法

2.1 中間表示函數(shù)

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

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

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

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

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

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

四種特定指令動作的描述如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

替換規(guī)則C1：如果存在相鄰的特定指令動作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的典型應用場景：將立即數(shù)移動到虛擬內(nèi)存。

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

替換規(guī)則C2：如果存在相鄰的特定指令動作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的典型應用場景：虛擬內(nèi)存與立即數(shù)的計算結(jié)果存入同一虛擬內(nèi)存。

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

替換規(guī)則C3：如果存在相鄰的特定指令動作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的典型應用場景：僅操作同一虛擬內(nèi)存數(shù)據(jù)。

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

替換規(guī)則C4：如果存在相鄰的特定指令動作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的典型應用場景：僅涉及不同虛擬內(nèi)存間的數(shù)據(jù)移動。

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

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

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

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

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

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

同樣，圖4展示了應用替換規(guī)則后，X86平臺的棧操作被翻譯到中間代碼的優(yōu)化過程。應用替換規(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 實驗部分

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

表3 實驗環(huán)境

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

5.1 正確性測試

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

5.2 性能測試

實驗借助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)化效果越好。

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

表4 測試用例說明

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

6 結(jié)論

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

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