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

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

0 引 言

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

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

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

1 基礎(chǔ)概念

1.1 SECD抽象機

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

表1 SECD 抽象機常用指令集

1.2 Java虛擬機與Java棧幀

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

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

1.3 基于蹤跡的即時編譯

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

標簽：劃分基本塊的標志，是基本塊的入口，用于標記分支。

錨點：是蹤跡的入口，是一種特殊的標簽。

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

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

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

以表2所給出的程序為例，該程序的控制流如圖1 （a）所示，假定識別熱蹤的閾值為200，根據(jù)基于蹤跡的熱點探測算法，該程序在運行過程中，基本塊2→3→4→6所組成的循環(huán)將被識別為熱蹤并被編譯成目標代碼，當獲得目標代碼后、再次執(zhí)行2→3→4→6時，該循環(huán)所對應(yīng)的目標代碼將被執(zhí)行，執(zhí)行結(jié)束后再切換到解釋執(zhí)行，執(zhí)行后續(xù)代碼。

表2 示例程序

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

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

2.1 基本過程

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

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

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

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

2.2 SECD指令翻譯

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

表3 示例程序SECD 指令序列

2.3 即時編譯

2.3.1 記錄蹤跡

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

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

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

2.3.2 代碼生成

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

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

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

2.3.3 環(huán)境切換

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實 驗

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

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

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

表7 測試用例

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

圖5 運行時間比較

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

4 相關(guān)工作

4.1 基于蹤跡的即時編譯

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

［1］ZHOU Zhiming.Understanding Java virtual machine ［M］.Beijing：China Machine Press，2011：287 （in Chinese）. ［周志明.深入理解Java虛擬機 ［M］.北京：機械工業(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］.計算機工程，2011，37 （24）：28－31.］