針對SECD抽象機(jī)的基于蹤跡的即時(shí)編譯技術(shù)

于成龍，廖湖聲，武辰之，蘇 航

（1.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京100124；2.北京工業(yè)大學(xué) 軟件學(xué)院，北京100124）

0 引 言

即時(shí)編譯技術(shù)是在程序運(yùn)行時(shí)將部分程序片段的解釋執(zhí)行轉(zhuǎn)化為編譯執(zhí)行的程序優(yōu)化技術(shù)。例如，在HotSpot虛擬機(jī)中，Java字節(jié)碼程序最初是由解釋器直接解釋執(zhí)行，當(dāng)虛擬機(jī)發(fā)現(xiàn)某個(gè)方法或是代碼塊執(zhí)行次數(shù)非常頻繁時(shí)，就會(huì)把這些代碼識(shí)別為 “熱點(diǎn)”，由即時(shí)編譯器將其編譯成本地平臺(tái)相關(guān)的機(jī)器碼［1］。

傳統(tǒng)的即時(shí)編譯器以整個(gè)方法為單位進(jìn)行即時(shí)編譯（如HotSpot），這將導(dǎo)致方法內(nèi)執(zhí)行頻度不高的代碼也參與編譯，增加了編譯開銷。為解決這一問題，Gal A 等提出了基于 蹤 跡 的 即 時(shí) 編 譯（trace－based just－in－time compilation）［2］進(jìn)行熱點(diǎn)探測。即時(shí)編譯時(shí)以 “蹤跡”（trace）為單位，比以方法為單位要精細(xì)得多，而且蹤跡可以跨越方法，能提供更多優(yōu)化機(jī)會(huì)。

本文提出了一種基于蹤跡的通用即時(shí)編譯技術(shù)，將在SECD 指令序列的執(zhí)行過程中，監(jiān)測程序執(zhí)行情況，將執(zhí)行頻繁的代碼編譯為Java字節(jié)碼。為保證編譯所得的Java字節(jié)碼能正常運(yùn)行，本文還介紹了解釋執(zhí)行環(huán)境與Java字節(jié)碼程序執(zhí)行環(huán)境的動(dòng)態(tài)轉(zhuǎn)換方法。任何用SECD 抽象機(jī)實(shí)現(xiàn)的編程語言都可采用該技術(shù)來提高程序執(zhí)行效率。此外，本文研制了一個(gè)采用該技術(shù)的通用執(zhí)行引擎框架，并使用該框架實(shí)現(xiàn)了XQuery語言。實(shí)驗(yàn)結(jié)果表明，采用本文所給出的即時(shí)編譯技術(shù)可以加快XQuery程序的執(zhí)行速度。

1 基礎(chǔ)概念

1.1 SECD抽象機(jī)

SECD抽象機(jī)［3］是一種經(jīng)典的操作語義，可以用于λ表達(dá)式的求值，經(jīng)常用在程序設(shè)計(jì)語言的驗(yàn)證與實(shí)現(xiàn)中。SECD 抽象機(jī)本身由操作數(shù)棧 （stack，簡記為ss）、環(huán)境（environment，簡記 為se）、代 碼 序 列 （control，簡 記 為sc）、轉(zhuǎn)儲(chǔ)區(qū) （dump，簡記為sd）4 部分組成，ss、se、sd的初始狀態(tài)均為空，sc則保存著將被抽象機(jī)執(zhí)行的SECD指令。在執(zhí)行SECD 指令的過程中，中間結(jié)果保存在ss中等待后續(xù)使用，局部變量保存在se中，sd 則保存著函數(shù)調(diào)用的相關(guān)信息，用于函數(shù)調(diào)用現(xiàn)場的保護(hù)與恢復(fù)。表1給出了一個(gè)SECD 指令集實(shí)例。

表1 SECD 抽象機(jī)常用指令集

1.2 Java虛擬機(jī)與Java棧幀

Java虛擬機(jī) （Java virtual machine，JVM）是Java程序運(yùn)行的基礎(chǔ)，Java程序源代碼經(jīng)過編譯之后得到Java字節(jié)碼，JVM 解釋執(zhí)行字節(jié)碼指令。另外，現(xiàn)代JVM 常用即時(shí)編譯技術(shù)來加快程序的執(zhí)行速度。

棧幀 （stack frame）［4］則是JVM 進(jìn)行方法調(diào)用和方法執(zhí)行的數(shù)據(jù)結(jié)構(gòu)，每當(dāng)JVM 執(zhí)行一個(gè)方法時(shí)，會(huì)創(chuàng)建一個(gè)棧幀并將其壓入到JVM 的Java虛擬機(jī)棧中，方法執(zhí)行完畢后該棧幀將被彈出。棧幀中保存一個(gè)Java方法的局部變量區(qū)、操作數(shù)棧、方法返回地址等信息。一個(gè)方法在運(yùn)行過程中，將根據(jù)字節(jié)碼指令從棧幀局部變量區(qū)或是其它JVM 組件中讀取數(shù)據(jù)并將其壓入到棧幀中的操作數(shù)棧，在棧上計(jì)算出結(jié)果后，再將結(jié)果彈棧、寫入局部變量區(qū)或是將其作為方法調(diào)用結(jié)果返回。

1.3 基于蹤跡的即時(shí)編譯

下面給出基于蹤跡的即時(shí)編譯中的一些基本概念：

標(biāo)簽：劃分基本塊的標(biāo)志，是基本塊的入口，用于標(biāo)記分支。

錨點(diǎn)：是蹤跡的入口，是一種特殊的標(biāo)簽。

蹤跡：是一條可跨越函數(shù)邊界的指令序列，由錨點(diǎn)、標(biāo)簽和子蹤跡組成，熱點(diǎn)蹤跡則是指執(zhí)行頻率超過預(yù)設(shè)閾值、需要進(jìn)行即時(shí)編譯的蹤跡，下文將簡稱作 “熱蹤”。

蹤跡樹：以一個(gè)蹤跡作為主干，多個(gè)蹤跡為分支所組成的樹，用于表示較復(fù)雜的程序結(jié)構(gòu)。

一般來講，基于蹤跡的即時(shí)編譯主要分為識(shí)別錨點(diǎn)、記錄蹤跡、代碼生成和執(zhí)行4個(gè)階段。當(dāng)識(shí)別出一個(gè)錨點(diǎn)后，執(zhí)行引擎在繼續(xù)執(zhí)行程序的同時(shí)，將從該錨點(diǎn)開始記錄正在執(zhí)行的指令，再次遇到該錨點(diǎn)則結(jié)束記錄操作，此時(shí)即得到一個(gè)完整的蹤跡。每個(gè)蹤跡的執(zhí)行次數(shù)將被記錄，執(zhí)行次數(shù)超過預(yù)設(shè)閾值的蹤跡被識(shí)別為熱蹤，并進(jìn)一步編譯為目標(biāo)代碼。當(dāng)執(zhí)行引擎再次執(zhí)行熱蹤時(shí)則執(zhí)行目標(biāo)代碼。

以表2所給出的程序?yàn)槔摮绦虻目刂屏魅鐖D1 （a）所示，假定識(shí)別熱蹤的閾值為200，根據(jù)基于蹤跡的熱點(diǎn)探測算法，該程序在運(yùn)行過程中，基本塊2→3→4→6所組成的循環(huán)將被識(shí)別為熱蹤并被編譯成目標(biāo)代碼，當(dāng)獲得目標(biāo)代碼后、再次執(zhí)行2→3→4→6時(shí)，該循環(huán)所對應(yīng)的目標(biāo)代碼將被執(zhí)行，執(zhí)行結(jié)束后再切換到解釋執(zhí)行，執(zhí)行后續(xù)代碼。

表2 示例程序

圖1 示例程序控制流圖及其熱蹤

2 針對SECD抽象機(jī)的基于蹤跡的即時(shí)編譯技術(shù)

2.1 基本過程

在讀取用戶編寫的程序代碼之后，首先將源代碼翻譯成等價(jià)的SECD 指令序列，并且指令序列中的循環(huán)頭部設(shè)置為錨點(diǎn)。在解釋執(zhí)行指令序列的過程中，進(jìn)行如下操作：

（1）記錄蹤跡：當(dāng)執(zhí)行引擎遇到一個(gè)錨點(diǎn)，則創(chuàng)建一個(gè)蹤跡并將之后執(zhí)行的每條指令記錄到這個(gè)蹤跡中，直至再次遇到這個(gè)錨點(diǎn)。如果在記錄過程中遇到新的錨點(diǎn)，則將正在記錄的蹤跡暫存起來，開始新的蹤跡的記錄，而這條新的蹤跡可以作為子蹤跡與之前暫存的蹤跡進(jìn)行合并。一個(gè)蹤跡記錄的是一個(gè)程序某次執(zhí)行的路徑，而之后該程序的執(zhí)行可能會(huì)與這條路徑不同。因此，在記錄蹤跡的過程中，如果程序中出現(xiàn)分支，則在蹤跡中加入一條GUARD 指令，用于代替沒有被執(zhí)行的程序分支。此外，記錄每個(gè)蹤跡的運(yùn)行次數(shù)，當(dāng)運(yùn)行次數(shù)超過閾值時(shí)則將其視為熱蹤，將其提交給即時(shí)編譯器。

（2）代碼生成：即時(shí)編譯器將熱蹤編譯成Java字節(jié)碼，并以回填的方式在字節(jié)碼中生成用于切換執(zhí)行方式的代碼，包括調(diào)用代碼序列、返回代碼序列兩部分。調(diào)用代碼序列為JVM 棧幀中的操作數(shù)棧分配空間、向棧幀中填寫信息；返回代碼序列則用于恢復(fù)SECD 抽象機(jī)的機(jī)器狀態(tài)，保證編譯執(zhí)行結(jié)束后SECD 執(zhí)行引擎能繼續(xù)往下執(zhí)行。更詳細(xì)說明參見2.3.3。

（3）執(zhí)行：在熱蹤被編譯成Java 字節(jié)碼之后，當(dāng)SECD 執(zhí)行引擎再次執(zhí)行到熱蹤時(shí)則切換到編譯執(zhí)行，調(diào)用Java字節(jié)碼，字節(jié)碼執(zhí)行結(jié)束后則切換回解釋執(zhí)行，繼續(xù)執(zhí)行后續(xù)代碼。

2.2 SECD指令翻譯

根據(jù)設(shè)計(jì)目的的不同，SECD 抽象機(jī)的指令集可以有不同的實(shí)現(xiàn)，而本文采用表1中給出的指令集作為文章中提到的SECD 抽象機(jī)的指令集，則表2所給出的源程序?qū)?yīng)的SECD 指令序列見表3。

表3 示例程序SECD 指令序列

2.3 即時(shí)編譯

2.3.1 記錄蹤跡

根據(jù)起始位置的不同，蹤跡可分為方法蹤跡 （method trace）、循環(huán)蹤跡 （loop trace）兩種［5］。方法蹤跡的錨點(diǎn)位于某個(gè)方法的入口，而循環(huán)蹤跡的錨點(diǎn)則位于某個(gè)循環(huán)結(jié)構(gòu)的開始位置。本技術(shù)在探測熱蹤時(shí)，主要探測循環(huán)蹤跡，當(dāng)執(zhí)行引擎解釋執(zhí)行SECD 指令序列時(shí)，如果碰到一個(gè)循環(huán)，則對該循環(huán)計(jì)數(shù)，當(dāng)超過預(yù)設(shè)閾值時(shí)則將循環(huán)體中常用部分提取出來，作為一個(gè)循環(huán)蹤跡，提交給即時(shí)編譯器編譯成Java字節(jié)碼。例如，在執(zhí)行表3中SECD 指令序列時(shí)，從標(biāo)簽f1＿loop開始到JMP f1＿loop指令這段SECD指令序列是對應(yīng)于表2中的for循環(huán)，當(dāng)這段指令序列執(zhí)行次數(shù)超過閾值時(shí)，將被視為熱蹤提取出來，見表4。

假設(shè)正在被執(zhí)行引擎執(zhí)行的程序中包含有兩個(gè)分支pa和pb，只有pb分支被記錄到一個(gè)熱蹤中，但在該熱蹤的目標(biāo)代碼的某次執(zhí)行時(shí)，卻需要執(zhí)行pa分支，這種現(xiàn)象被稱作旁路退出 （side exit）。當(dāng)旁路退出發(fā)生時(shí)，需要從編譯執(zhí)行切換到解釋執(zhí)行。為此，在記錄一個(gè)蹤跡時(shí)需要向蹤跡中插入GUARD 指令，用于標(biāo)記可能發(fā)生旁路退出的位置。在代碼生成階段將根據(jù)GUARD 指令生成用于切換執(zhí)行環(huán)境的Java字節(jié)碼。以圖1 （a）為例，基本塊3中包含有兩個(gè)分支，路徑3→5→6并沒有被記錄到圖1 （b）所給出的蹤跡中，因此在這個(gè)蹤跡中加入一個(gè)GUARD 指令。

表4 示例程序熱蹤及其字節(jié)碼

2.3.2 代碼生成

SECD 抽象機(jī)和JVM 都是基于棧的虛擬機(jī)，組成SECD抽象機(jī)的每個(gè)部分都可以在JVM 中找到功能相似的部分：SECD 操作數(shù)棧對應(yīng)于JVM 棧幀的操作數(shù)棧 （簡記為fs），SECD 環(huán)境對應(yīng)于棧幀局部變量區(qū) （簡記為fe），SECD 指令序列對應(yīng)于Java字節(jié)碼，而SECD 轉(zhuǎn)儲(chǔ)區(qū)則對應(yīng)于Java虛擬機(jī)棧 （簡記為fd）。同時(shí)，大部分SECD 指令都可以找到功能相同的JVM 指令，因而在將熱蹤翻譯成Java字節(jié)碼時(shí)按照對應(yīng)關(guān)系逐條翻譯SECD 指令即可。對于沒有對應(yīng)的JVM 指令的SECD 指令，則可以根據(jù)這條SECD 指令的語義，生成一個(gè)等價(jià)的Java方法，在字節(jié)碼文件中對應(yīng)位置加入調(diào)用該方法的指令。表4給出了一個(gè)熱蹤翻譯成字節(jié)碼的實(shí)例，為方便闡述，將翻譯熱蹤所得的字節(jié)碼記作bcode。

另一方面，解釋執(zhí)行的運(yùn)行時(shí)環(huán)境主要包括SECD 抽象機(jī)的ss、se和sd，而編譯執(zhí)行的運(yùn)行時(shí)環(huán)境則是JVM 中的fs、fe、fd 以及Java堆等組件。不同執(zhí)行方式下運(yùn)行時(shí)數(shù)據(jù)保存在不同的位置。要保證熱蹤對應(yīng)的字節(jié)碼在JVM 中能正確地執(zhí)行，就必須在字節(jié)碼執(zhí)行前，將SECD抽象機(jī)中的部分?jǐn)?shù)據(jù)寫入到JVM 中相應(yīng)位置；當(dāng)發(fā)生旁路退出、需要切回到解釋執(zhí)行時(shí)，也需要將執(zhí)行字節(jié)碼所得的中間結(jié)果回寫到解釋運(yùn)行時(shí)環(huán)境中。本文將這些操作統(tǒng)稱為環(huán)境切換，具體過程參見2.3.3。

此外，為了生成將se中的變量寫入到fe 或是利用fe更新se 的代碼，還需要保存熱蹤中各個(gè)變量在se、fe中存儲(chǔ)位置的映射關(guān)系。為此，在代碼生成過程中，需要維護(hù)一張映射表 （以下記作varMap），每當(dāng)在熱蹤中遇到對se中的變量進(jìn)行讀、寫操作的指令時(shí)，則將該變量位置以及fe對應(yīng)變量的位置保存到該映射表中。

2.3.3 環(huán)境切換

在將熱蹤翻譯成字節(jié)碼之后，為了進(jìn)行環(huán)境切換，需要在bcode 的開始位置生成調(diào)用代碼序列，在bcode 中GUARD 指令對應(yīng)的位置生成返回代碼序列。

調(diào)用代碼序列為fs分配空間，將即時(shí)編譯所需的ss內(nèi)部分元素按照順序壓入fs內(nèi)，并根據(jù)varMap 將se 內(nèi)相關(guān)變量寫入fe，為此需要先計(jì)算fs需要分配多大空間。這一計(jì)算在生成bcode之后進(jìn)行，通過統(tǒng)計(jì)熱蹤中每條分支的所有指令對ss的壓棧、彈棧次數(shù)，可得出整個(gè)熱蹤所需的fs的空間大小 （記作stackNum），具體算法參見表5。假設(shè)熱蹤中指令條數(shù)為n，算法至多對所有指令遍歷一遍，因此算法時(shí)間復(fù)雜度為O（n），空間復(fù)雜度為O（n）。計(jì)算出stack－Num 后，根據(jù)stackNum 和varMap，即可在已有的字節(jié)碼中回填調(diào)用代碼序列。

環(huán)境切換大體流程如圖2 所示，切換為編譯執(zhí)行后，首先執(zhí)行調(diào)用代碼序列，fs、fe 將會(huì)準(zhǔn)備好必要的數(shù)據(jù)（fs中壓入val0、val1，fe中存入val0、val1），熱蹤對應(yīng)的字節(jié)碼就可以正確地執(zhí)行；當(dāng)字節(jié)碼執(zhí)行完畢后，fs、fe保存著熱蹤的執(zhí)行結(jié)果 （fs中的val2、val3，fe中新的變量值val0’、val1’），執(zhí)行返回代碼序列后這些執(zhí)行結(jié)果將被回寫到SECD 抽象機(jī)中，執(zhí)行引擎繼續(xù)解釋執(zhí)行后續(xù)代碼。

圖2 環(huán)境切換中各部件的變化

表5 計(jì)算棧幀操作數(shù)棧容量的算法

返回代碼序列則用于將fs內(nèi)的數(shù)據(jù)按照順序全部壓入ss，根據(jù)varMap 將fe 數(shù)據(jù)寫入se 對應(yīng)位置。如果在熱蹤中有自定義函數(shù)調(diào)用且調(diào)用自定義函數(shù)時(shí)執(zhí)行了沒有包含在熱蹤中的代碼，還需要向sd 中寫入函數(shù)調(diào)用信息，用于恢復(fù)SECD 抽象機(jī)的狀態(tài)。

完成上述工作后，最終用于即時(shí)編譯的Java字節(jié)碼見表6 （限于篇幅，僅給出了大體框架）。

表6 示例程序的Java字節(jié)碼

當(dāng)熱蹤中包含自定義函數(shù)部分代碼時(shí)，環(huán)境切換會(huì)更復(fù)雜。例如，圖3 （a）表示在運(yùn)行時(shí)刻，foo2函數(shù)中提取出traceFunc作為熱蹤、進(jìn)行了即時(shí)編譯，該熱蹤又調(diào)用了自定義函數(shù)foo3，而foo3 中僅有一條分支被記錄到熱蹤中。如果在某次編譯執(zhí)行foo3函數(shù)時(shí)發(fā)生旁路退出，則需中止即時(shí)編譯、沿圖3 （a）中虛線所示路徑返回到SECD執(zhí)行引擎，從foo3中GUARD 指令對應(yīng)位置繼續(xù)解釋執(zhí)行后續(xù)代碼。由于foo3、traceFunc 還沒有執(zhí)行完，必須在foo3中GUARD 指令所在位置添加返回代碼序列，進(jìn)行如下操作：

將foo3函數(shù)所對應(yīng)的fs、fe中的數(shù)據(jù)、foo3的返回地址保存在一個(gè)變量中，并將該變量壓入sd 中；

終止foo3的運(yùn)行，并返回一個(gè)特定標(biāo)記值G，以便和正常的函數(shù)調(diào)用過程相區(qū)分；

圖3 對包含自定義函數(shù)的熱蹤的處理

在traceFunc調(diào)用foo3的位置加入對foo3返回值的判斷，如果返回值為G 則同樣將traceFunc函數(shù)對應(yīng)的fs、fe、traceFunc的返回地址保存在一個(gè)變量中，并將該變量壓入sd，終止traceFunc的運(yùn)行，返回標(biāo)記值G （如果熱蹤中包含多個(gè)自定義函數(shù)的嵌套調(diào)用，則可能需要重復(fù)這一過程，直至返回到SECD 解釋執(zhí)行引擎）。

當(dāng)即時(shí)編譯結(jié)束后，SECD 解釋執(zhí)行引擎讀取編譯執(zhí)行的結(jié)果，如果是G 則說明調(diào)用自定義函數(shù)時(shí)發(fā)生了旁路退出，此時(shí)將sd 內(nèi)部分元素逆序 （保證與函數(shù)調(diào)用順序一致），然后讀取sd 棧頂元素用來更新當(dāng)前SECD 抽象機(jī)中的ss、se和指令PC，恢復(fù)現(xiàn)場，然后繼續(xù)解釋執(zhí)行即可，如圖3 （b）所示。

對于遞歸函數(shù)調(diào)用，目前本技術(shù)所采用的熱點(diǎn)探測策略將任何遞歸函數(shù)都視為熱點(diǎn)，因而遞歸函數(shù)的定義將被包含在熱蹤中并被翻譯成字節(jié)碼，編譯執(zhí)行時(shí)調(diào)用遞歸函數(shù)只需將參數(shù)傳遞給該函數(shù)即可，不需要進(jìn)行環(huán)境切換。

2.4 通用執(zhí)行引擎框架

基于蹤跡的即時(shí)編譯通用執(zhí)行引擎框架的基本結(jié)構(gòu)如圖4所示，該框架主要由以下4部分組成：

SECD 翻譯器：將源程序翻譯成語義等價(jià)的SECD 指令序列；

內(nèi)建函數(shù)庫：保存庫函數(shù)，需要根據(jù)要實(shí)現(xiàn)的語言而變化；

SECD 執(zhí)行引擎：執(zhí)行SECD 指令序列，實(shí)現(xiàn)SECD 指令的即時(shí)編譯，并將計(jì)算結(jié)果返回；

JVM：執(zhí)行Java字節(jié)碼。

圖4 通用執(zhí)行引擎框架

任何編程語言，只要能夠?qū)⒃撜Z言翻譯為SECD 指令序列，都可以利用該框架來實(shí)現(xiàn)這種語言的執(zhí)行引擎。

3 實(shí) 驗(yàn)

本文實(shí)現(xiàn)了2.4中提到的通用執(zhí)行引擎框架，并利用該框架實(shí)現(xiàn)了一個(gè)XQuery［6］執(zhí)行引擎。實(shí)驗(yàn)環(huán)境如下：Intel Xeon CPU E5－1607 3GHz，8G 內(nèi) 存，Ubuntu 12.04 LTS，JDK 1.6update 27。

實(shí)驗(yàn)中分別在解釋執(zhí)行、函數(shù)級即時(shí)編譯、基于蹤跡的即時(shí)編譯3種執(zhí)行方式下對13個(gè)測試用例進(jìn)行了測試，其中10 個(gè)用例來自于W3C XML Query Use Cases，Q1、Q2、Q3參見表7。實(shí)驗(yàn)結(jié)果如圖5所示，需要說明的，函數(shù)級即時(shí)編譯、基于蹤跡的即時(shí)編譯的運(yùn)行時(shí)間包括了在運(yùn)行時(shí)編譯目標(biāo)代碼的時(shí)間。

在所有測試用例中，基于蹤跡的即時(shí)編譯對解釋執(zhí)行的加速比平均可以達(dá)到1.11，最好情況下可以達(dá)到1.43。在這些用例中，1.2.4.6、Q1、Q2、Q3包含有多重循環(huán)或是多次被調(diào)用的自定義函數(shù)，導(dǎo)致這些用例中的大部分代碼被識(shí)別為熱蹤并編譯執(zhí)行，因而可以獲得比較好的性能提升。其它用例則只包含單重循環(huán)，識(shí)別出的熱蹤運(yùn)行次數(shù)相對較少，不足以帶來明顯的性能提升。在增大輸入文件，使得XQuery查詢的執(zhí)行次數(shù)增加后，加速比變化如圖6所示。顯然，隨著XQuery查詢的執(zhí)行次數(shù)增加，基于蹤跡的即時(shí)編譯所帶來的加速效果也會(huì)變得更明顯。

表7 測試用例

另一方面，所有測試用例中，僅1.2.4.6、Q2、Q3中包含有自定義函數(shù)。而為了保證實(shí)驗(yàn)條件相同，實(shí)驗(yàn)中所采用的函數(shù)級即時(shí)編譯并沒有引入現(xiàn)代虛擬機(jī)中的棧上替換等優(yōu)化技術(shù)，使得函數(shù)級即時(shí)編譯只會(huì)對程序中多次執(zhí)行的自定義函數(shù)進(jìn)行編譯。因此，對于不包含自定義函數(shù)的測試用例，由于探測熱點(diǎn)所帶來的開銷，函數(shù)級即時(shí)編譯的運(yùn)行速度略微慢于解釋執(zhí)行。而對于包含自定義函數(shù)的用例 （1.2.4.6、Q2、Q3），函數(shù)級編譯執(zhí)行要快于解釋執(zhí)行，但仍比基于蹤跡的即時(shí)編譯執(zhí)行要慢。這是由于在1.2.4.6、Q2、Q3中自定義函數(shù)調(diào)用出現(xiàn)在循環(huán)中，而熱蹤會(huì)將整個(gè)循環(huán)編譯，在函數(shù)級編譯中被編譯的代碼必然包含在熱蹤中。在這些例子中，熱蹤的編譯不但可以減少自定義函數(shù)本身的執(zhí)行時(shí)間，而且可以減少他們的調(diào)用開銷和外圍循環(huán)執(zhí)行時(shí)間。

圖5 運(yùn)行時(shí)間比較

圖6 不同輸入規(guī)模下的加速比變化

4 相關(guān)工作

4.1 基于蹤跡的即時(shí)編譯

Dynamo［7］是第一個(gè)實(shí)現(xiàn)了基于蹤跡的即時(shí)編譯的編譯器，它在運(yùn)行時(shí)使用循環(huán)體的頭部來標(biāo)識(shí)一個(gè)蹤跡，并沒有創(chuàng)建實(shí)際循環(huán)蹤跡。而本技術(shù)中同樣采用循環(huán)體頭部來標(biāo)識(shí)蹤跡，省卻了基于蹤跡的即時(shí)編譯一般處理流程中的分析階段。

DynamoRIO 發(fā)展了Dynamo，它是一個(gè)包含了蹤跡和部分求值的解釋框架，但是DynamoRIO 的蹤跡仍然在機(jī)器碼層面，沒有包含解釋器層面的高級信息。這使得蹤跡的探測需要增加大量的額外標(biāo)注，一些編譯優(yōu)化也無法在這個(gè)層面上進(jìn)行。

Gal A等人開發(fā)了第一個(gè)高性能的基于蹤跡的即時(shí)編譯器HotpathVM，該虛擬機(jī)動(dòng)態(tài)探測頻繁運(yùn)行的字節(jié)碼，將其翻譯為SSA （static single assignment）作 為 中 間 表 示，之 后SSA將被編譯為機(jī)器碼。本技術(shù)中程序以SECD 指令作為中間代碼，找到熱蹤后將會(huì)把熱蹤翻譯成Java字節(jié)碼并執(zhí)行。

Hubl C等人基于HotSpot，開發(fā)了不跨越函數(shù)的基于蹤跡的熱點(diǎn)探測器，該解決方案由于不跨越函數(shù)，蹤跡都很短小，節(jié)約了探測和編譯的時(shí)間，但無法進(jìn)行全局優(yōu)化。

此外，基于蹤跡的即時(shí)編譯技術(shù)還被廣泛應(yīng)用于其它項(xiàng)目中，如Python語言的實(shí)現(xiàn)PyPy［8］，Mozilla的Trace－Monkey［9］，微 軟 公 司 的SPUR［10］項(xiàng) 目，Android 的Dalvik虛擬機(jī)［11，12］等。

4.2 XQuery相關(guān)實(shí)現(xiàn)

目前XQuery執(zhí)行引擎多數(shù)以解釋方式執(zhí)行XQuery查詢。Axyana Software開發(fā)的Qizx／Open是一個(gè)開源的使用Java實(shí)現(xiàn)的XML查詢解釋器。Galax是一個(gè)輕量級可移植的XQuery的開源實(shí)現(xiàn)，已成為研究各種XQuery優(yōu)化方法的實(shí)驗(yàn)平臺(tái)。

另一方面，為了提高XQuery執(zhí)行效率，不少研究人員已展開編譯實(shí)現(xiàn)XQuery語言的研究。Qexo是GNU 實(shí)現(xiàn)的XQuery執(zhí)行引擎，它部分實(shí)現(xiàn)了XQuery 語言。Qexo采用編譯實(shí)現(xiàn)的方式，將XQuery源程序編譯為可執(zhí)行的Java字節(jié)碼，并加載到JVM 中執(zhí)行。但Qexo側(cè)重于從編程語言角度實(shí)現(xiàn)XQuery，與XML 相關(guān)的優(yōu)化策略應(yīng)用較少。XQC編譯系統(tǒng)［13］則將XQuery程序全部翻譯成Java字節(jié)碼，但如果XQuery程序中大部分代碼執(zhí)行頻度較低，編譯時(shí)間較長，可能執(zhí)行效率反而不及直接解釋執(zhí)行，并且XQC并不支持樹模式查詢。而XQuery Hotspot編譯系統(tǒng)［14］則采用HotSpot的熱點(diǎn)探測策略，同樣不支持樹模式，并且沒有充分利用JVM 中已有的棧、堆等結(jié)構(gòu)。

5 結(jié)束語

本文討論了一種針對SECD 抽象機(jī)的基于蹤跡的即時(shí)編譯技術(shù)，該技術(shù)將編程語言翻譯成SECD 指令序列，以解釋方式執(zhí)行SECD 指令序列，將程序中執(zhí)行頻率高的蹤跡翻譯成Java字節(jié)碼，進(jìn)行即時(shí)編譯。實(shí)驗(yàn)結(jié)果表明，利用該技術(shù)可以提升程序的運(yùn)行速度。

目前本文中已給出的SECD 指令集并不支持高階函數(shù)，因而還不能對包含有高階函數(shù)特性的編程語言進(jìn)行即時(shí)編譯，并且翻譯目標(biāo)代碼的過程中還可以利用函數(shù)內(nèi)聯(lián)、逃逸分析等技術(shù)對目標(biāo)代碼進(jìn)行優(yōu)化。

［1］ZHOU Zhiming.Understanding Java virtual machine ［M］.Beijing：China Machine Press，2011：287 （in Chinese）. ［周志明.深入理解Java虛擬機(jī) ［M］.北京：機(jī)械工業(yè)出版社，2011：287.］

［2］Bebenita M，Chang M，Wagner G，et al.Trace－based compilation in execution environments without interpreters ［C］／／Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java.ACM，2010：59－68.

［3］Narita K，Nishizaki S Y，Mizuno T.A simple abstract machine for functional first－class continuations ［C］／／International Symposium on Communications and Information Technologies.IEEE，2010：111－114.

［4］Lindholm T，Yellin F，Bracha G，et al.The Java virtual machine specification ［M］.Addison Wesley，2013：17.

［5］Hubl C，Mssenbck H.Trace－based compilation for the Java HotSpot virtual machine［C］／／Proceedings of the 9th International Conference on Principles and Practice of Programming in Java.ACM，2011：129－138.

［6］W3CXML query working group，XQuery 1.0：An XML query language［EB／OL］.［2010－12－14］.http：／／www.w3.org／TR／2010／REC－xquery－20101214／.

［7］Hayashizaki H，Wu P，Inoue H，et al.Improving the performance of trace－based systems by false loop filtering ［J］.ACM SIGPLAN Notices，2012，47 （4）：405－418.

［8］Bolz F C，Cuni A，F(xiàn)ijalkowski M，et al.Tracing the metalevel：PyPy’s tracing JIT compiler［C］／／Proceedings of the 4th Workshop on the Implementation，Compilation，Optimization of Object－Oriented Languages and Programming Systems.ACM，2009：18－25.

［9］Gal A，Eich B，Shaver M，et al.Trace－based just－in－time type specialization for dynamic languages［J］.ACM SIGPLAN Notices，2009，44 （6）：465－478.

［10］Bebenita M，Brandner F，F(xiàn)ahndrich M，et al.SPUR：A trace－based JIT compiler for CIL ［J］.ACM SIGPLAN Notices，2010，45 （10）：708－725.

［11］Perez G A，Kao C M，Chung Y C，et al.A hybrid just－intime compiler for android：Comparing JIT types and the result of cooperation ［C］／／Proceedings of the International Conference on Compilers，Architectures and Synthesis for Embedded Systems.ACM，2012：41－50.

［12］Cheng B，Buzbee B.A JIT compiler for Android’s Dalvik VM［C］／／Google I／O Developer Conference，2010.

［13］Yuan F，Chen Y，Liao H.XQC：A compiler for XQuery［C］／／International Conference on Computer Science and Software Engineering.IEEE，2008：360－363.

［14］ZHANG Kailian，LIAO Husheng，SU Hang.Supporting framework of hotspot compiler system for XQuery ［J］.Computer Engineering，2011，37 （24）：28－31 （in Chinese）.［張開練，廖湖聲，蘇航.XQuery語言HotSpot編譯系統(tǒng)的支撐框架 ［J］.計(jì)算機(jī)工程，2011，37 （24）：28－31.］