陶勝召 廖湖聲 蘇 航 高紅雨

1(北京工業(yè)大學計算機學院 北京 100124)2(北京工業(yè)大學軟件學院 北京 100124)

基于Trace的CMinus語言即時編譯技術(shù)

陶勝召1廖湖聲2蘇 航1高紅雨1

1(北京工業(yè)大學計算機學院 北京 100124)2(北京工業(yè)大學軟件學院 北京 100124)

即時編譯技術(shù)是改進動態(tài)語言性能的有效手段?；谯欅E(Trace)的即時編譯技術(shù)能夠在運行時識別出頻繁執(zhí)行的程序片段(熱蹤)并進行編譯優(yōu)化，在相當多的場景下能夠提高程序整體的執(zhí)行效率。然而，這種涉及底層代碼優(yōu)化的即時編譯系統(tǒng)開發(fā)難度較大，導致其應(yīng)用范圍受到一定限制。為此，一種針對C語言子集CMinus的熱蹤編譯技術(shù)被提出。利用這種熱蹤編譯技術(shù)及其支撐工具，任何能夠翻譯為CMinus的開發(fā)語言都可以使用該技術(shù)提高程序執(zhí)行效率，任何采用CMinus語言實現(xiàn)的算法也都可以得到熱蹤編譯的支持。實驗結(jié)果表明這種即時編譯技術(shù)能夠有效地提高程序的執(zhí)行效率。

CMinus 即時編譯 基于蹤跡 環(huán)境切換

0 引 言

為了提高虛擬機環(huán)境中程序解釋執(zhí)行的效率，各種即時編譯技術(shù)已經(jīng)得到了廣泛的應(yīng)用。和早期的熱點編譯(Hotspot[1])技術(shù)相比，基于Trace的即時編譯技術(shù)按照控制流中頻繁使用的執(zhí)行路徑作為即時編譯的應(yīng)用對象，能夠完成細粒度的程序優(yōu)化。這種熱蹤編譯技術(shù)近年來已經(jīng)成功地應(yīng)用于Java、JavaScript、Python和Microsoft CIL等多種解釋型語言的程序優(yōu)化。

然而，基于Trace的即時編譯系統(tǒng)具有較高的開發(fā)難度。對于特定的虛擬機及其機器語言，開發(fā)者必須充分了解虛擬機的工作原理，熟悉各種語言功能的實現(xiàn)方法，經(jīng)過艱苦的底層軟件開發(fā)才能實現(xiàn)這種即時編譯。

為了擴展基于Trace的即時編譯技術(shù)的應(yīng)用范圍，減輕開發(fā)難度，本文提出一種軟件開發(fā)方法及其支撐工具。按照這種開發(fā)方法，開發(fā)者只要將開發(fā)語言翻譯為C語言的一個子集CMinus[2]，就可以利用本項目提供的CMinus即時編譯系統(tǒng)，實現(xiàn)這種語言的即時編譯。本文的主要貢獻是：

1) 提出了一種即時編譯系統(tǒng)的實現(xiàn)方法?；赥race和基于函數(shù)的CMinus語言即時編譯，這種方法可用于實現(xiàn)各種程序設(shè)計語言的即時編譯。

2) 實現(xiàn)了從CMinus語言到Java字節(jié)碼的即時編譯，其他語言只要翻譯為CMinus就可以通過即時編譯技術(shù)得到程序優(yōu)化。

3) 研制了一個CMinus執(zhí)行引擎，采用解釋執(zhí)行和熱蹤編譯執(zhí)行的混合模式，實現(xiàn)運行時的CMinus程序動態(tài)優(yōu)化。

1 基礎(chǔ)概念

1.1 CMinus概述

CMinus是C語言的子集。作為一種命令式語言，CMinus支持一般的函數(shù)和遞歸函數(shù)的定義和調(diào)用，支持順序、選擇、循環(huán)等結(jié)構(gòu)且支持基本數(shù)據(jù)類型和一維數(shù)組等數(shù)據(jù)結(jié)構(gòu)，這使得它足以實現(xiàn)常用編程語言的主要程序設(shè)計功能。表1是CMinus文法的核心部分(其中*代表0或多個，[]代表0或1個)。

表1 CMinus語言核心文法

1.2 即時編譯

JIT(Just-In-Time)編譯是一種在解釋執(zhí)行時通過識別原有程序中頻繁執(zhí)行的代碼并將其編譯為目標代碼，當再次執(zhí)行到該段代碼時直接調(diào)用已生成的目標代碼以獲得更高運行效率的動態(tài)優(yōu)化技術(shù)。目前，按照編譯的粒度可以將即時編譯技術(shù)分為兩種，一種是基于函數(shù)的，一種是基于Trace的。

基于函數(shù)的即時編譯是對頻繁執(zhí)行的整個函數(shù)進行編譯，利用生成的目標代碼來代替函數(shù)的解釋執(zhí)行，以求獲得效率的提升。然而，按照這種方法，函數(shù)中非頻繁執(zhí)行的片段也會被編譯，因此增加了不必要的編譯時間。

基于Trace的即時編譯是將一段頻繁執(zhí)行的代碼片段(路徑)作為一個編譯單元，并僅對該代碼片段進行編譯。該代碼片段由一個線性且連續(xù)的指令序列組成，僅有一個入口，但有一個或多個出口。而且基于Trace的即時編譯對熱點的記錄并不局限于一個函數(shù)中，一條Trace可能對應(yīng)多個函數(shù)，如果在一個程序中有多個頻繁執(zhí)行的路徑，這些路徑可以分別被識別成不同的Trace。因此相比基于函數(shù)的即時編譯，基于Trace的即時編譯的識別精度更高且能通過避免編譯不是頻繁執(zhí)行的代碼，減少不必要的編譯開銷。

在CMinus程序中，Trace代表控制流圖中遇到的一段循環(huán)路徑，一條Trace可以表示為一個如下的二元組:

Trace= (Head, BlockLists)

其中：Head是Trace中的第一個基本塊標識。BlockLists是Trace中的基本塊順序序列?？刂屏髦荒軓幕緣K中第一個指令進入該塊，并且除了基本塊中最后一個指令，控制流在離開基本塊之前不會停機或者跳轉(zhuǎn)，因此一個基本塊列表唯一的標識了一條Trace。

表2是一個簡單的CMinus程序，該程序生成的基本塊流圖[3]如圖1所示。執(zhí)行引擎針對該基本塊流圖解釋執(zhí)行時，B2作為循環(huán)的開始塊被稱作一條Trace的起點，從該處開始記錄一條Trace，并將之后遇到的普通塊陸續(xù)加入到當前Trace中，當再次執(zhí)行到B2時即完成當前Trace的記錄。如果偶數(shù)個數(shù)較多時，則粗體箭頭所組成的路徑(B2→B3→B4→B6)首先被識別成熱點路徑并編譯為Java字節(jié)碼，再次執(zhí)行到該路徑時直接通過JVM調(diào)用生成的字節(jié)碼。

表2 CMinus程序示例

圖1 fun函數(shù)基本塊流圖

1.3 JVM與Java棧幀

JVM用于執(zhí)行生成的Java字節(jié)碼，其中Java棧幀[4]主要用于方法調(diào)用和執(zhí)行，每當調(diào)用一個方法就對應(yīng)一個棧幀的入棧過程，而一個方法執(zhí)行完成則對應(yīng)一個棧幀的出棧過程。棧幀中存儲了每個方法對應(yīng)的局部變量表、操作數(shù)棧、動態(tài)鏈接和方法返回地址等信息。其中：

(1) 局部變量表：是一組變量值的存儲空間，用于存儲方法參數(shù)和方法內(nèi)部定義的局部變量。

(2) 操作數(shù)棧：是一個后入先出棧，當JVM進行方法執(zhí)行時，各種字節(jié)碼指令通過出棧和入棧操作往操作數(shù)棧中寫入和提取內(nèi)容。

(3) 動態(tài)鏈接：指向該棧幀所屬的方法的引用。

(4) 方法返回地址：指向一個該方法被調(diào)用的位置，方便該方法返回后繼續(xù)執(zhí)行。

2 基于Trace的即時編譯技術(shù)

一般來說，基于Trace的即時編譯劃分為錨點識別、Trace探測、生成目標代碼、執(zhí)行目標代碼四個階段，執(zhí)行引擎在對每個基本塊進行解釋執(zhí)行時都會激活如圖2所示Trace探測執(zhí)行過程。

圖2 熱點Trace探測執(zhí)行流程

2.1 錨點識別

在不同的基于Trace的探測技術(shù)中，錨點的定義并不完全相同，而且由于探測的代碼一般都是底層的代碼，缺乏翻譯的高級信息，因此這些錨點無法預(yù)先進行標識，導致錨點識別耗費了一部分時間開銷。為了省去這部分開銷，在本文中，我們將CMinus程序中所有循環(huán)體的頭部作為錨點，并從該位置進行Trace的記錄。

2.2 Trace探測

解釋執(zhí)行過程中，需要通過判斷一段代碼塊的執(zhí)行次數(shù)是否達到閾值作為該段代碼是否需要被編譯的條件，此時需要借助Trace探測技術(shù)。

在進行Trace探測之前，先會創(chuàng)建一個映射表TraceCountMap，用于記錄Trace的執(zhí)行次數(shù)。如果當前Trace記錄完畢，若該Trace在TraceCountMap中已存在，則將其計數(shù)值加1，如果該計數(shù)超過閾值，則進入目標代碼生成階段。如果該Trace還不在TraceCountMap中，則將其計數(shù)值初始化為1。

如圖2所示，在解釋執(zhí)行過程中，將會針對遇到的基本塊B是否是錨點進行判斷。如果B為普通基本塊，直接將該基本塊B加到當前Trace中，并對B進行解釋執(zhí)行。如果B是錨點，則查找是否存在以B為錨點的目標代碼，如果存在，直接調(diào)用目標代碼執(zhí)行；如果不存在，便以該錨點為起點記錄一條新的Trace，并將后續(xù)的普通塊加到當前Trace中，直到再次遇到該錨點即完成該Trace的記錄。

2.3 生成目標代碼

CMinus指令翻譯成目標代碼時可以對生成的控制流圖進行遍歷并根據(jù)控制流圖對應(yīng)的抽象語法樹上的各運算節(jié)點的語義翻譯成對應(yīng)的Java字節(jié)碼。如果該節(jié)點沒有直接對應(yīng)的字節(jié)碼指令，可以定義一個實現(xiàn)該功能的Java靜態(tài)方法，并將調(diào)用該靜態(tài)方法的指令添加到該節(jié)點處生成的Java字節(jié)碼中。

熱點Trace翻譯成Java字節(jié)碼后，當需要執(zhí)行熱點Trace翻譯成的Java字節(jié)碼時，Trace此時仍處于解釋環(huán)境中，需要將其中的變量值傳遞到編譯環(huán)境。而解釋環(huán)境和JVM的運行時環(huán)境中變量的索引位置并不一定相同，為了保證解釋環(huán)境和編譯環(huán)境中的變量值的順利傳遞，在生成目標代碼前需要先對該Trace中的變量進行一次遍歷，生成一個<變量名，<解釋環(huán)境索引，編譯環(huán)境索引>>的映射表VarMap。如圖3所示，根據(jù)映射表中變量的個數(shù)在生成的Java字節(jié)碼類中定義一個同樣大小的局部變量表，用于存放從解釋環(huán)境中傳遞過來的變量值，并根據(jù)VarMap中保存的變量在編譯環(huán)境中的索引來生成Java字節(jié)碼中對應(yīng)的loadn或storen等指令。其中環(huán)境指保存著多個變量名/變量值對應(yīng)關(guān)系的列表，由于列表中變量的保存位置與名字存在一一對應(yīng)關(guān)系，因此在實現(xiàn)中會用值的保存位置來替代變量名。

圖3 局部變量的對應(yīng)關(guān)系

如果對熱點Trace進行翻譯時遇到分支節(jié)點，可能一個分支在該Trace中而另一分支不在該Trace中，JVM在執(zhí)行該分支處翻譯的目標代碼時可能導致執(zhí)行引擎從編譯環(huán)境切換到解釋環(huán)境，因此需要在跳轉(zhuǎn)到另一個分支處插入一個Guard指令進行標記。如圖1中B3→B4和B3→B5各有一個路徑，如果偶數(shù)個數(shù)較多，加粗的箭頭所組成的路徑(B2→B3→B4→B6)首先被識別為熱點Trace，該Trace翻譯生成的Java字節(jié)碼如表3 所示。由于B5不在該Trace中，因此在B3→B5處應(yīng)插入一個Guard標記(如表3中右側(cè)Java字節(jié)碼中GUARD部分所示)，并將所有的Guard標記所在的位置進行記錄，在字節(jié)碼生成完成后在所有記錄的Guard標記處插入從編譯環(huán)境切換到解釋環(huán)境的代碼。

表3 翻譯成目標代碼

翻譯生成的Java字節(jié)碼是一個以該Trace的錨點名為函數(shù)名的靜態(tài)方法，并保存在一個以該函數(shù)名為索引的映射表TraceMap中。為了節(jié)省類加載的時間，我們將所有的Trace翻譯的靜態(tài)方法保存在一個class文件中。同時為了盡可能減少編譯所帶來的開銷，本課題將使用ASM來生成對應(yīng)的Java字節(jié)碼文件。

2.4 執(zhí)行目標代碼

解釋執(zhí)行時遇到錨點，首先從存放生成的Java字節(jié)碼的映射表TraceMap中檢索是否存在已編譯好的以該錨點為起點的Trace，如果存在則將解釋環(huán)境中的必要信息傳遞到編譯環(huán)境，并直接通過JVM調(diào)用生成的Java字節(jié)碼執(zhí)行。

JVM執(zhí)行熱點Trace生成的Java字節(jié)碼時，如果遇到未編譯的分支，即遇到Guard指令，將導致執(zhí)行環(huán)境從編譯執(zhí)行切換到解釋執(zhí)行，此時需要將編譯環(huán)境中的變量值等信息傳遞到解釋執(zhí)行環(huán)境，這種現(xiàn)象被稱作旁路退出。CMinus解釋器將繼續(xù)解釋執(zhí)行Guard所指向的基本塊，并從該基本塊繼續(xù)進行Trace的探測。 如圖1中，如果T1:{B2, (B2,B3,B4,B6)}首先被編譯，在解釋執(zhí)行過程中如果遇到B2，將通過JVM執(zhí)行該Trace對應(yīng)的字節(jié)碼，如果在B3處發(fā)生旁路退出進入B3→B5分支，將導致從編譯環(huán)境切換到解釋解釋環(huán)境，并從B5處繼續(xù)進行Trace的探測，同時將B5加入到當前Trace中。

2.5Trace合并

當一條路徑識別為熱點Trace且該Trace中包含其他Trace中的錨點或者其他熱點Trace中包含當前Trace對應(yīng)的錨點時，如果不進行Trace合并，將導致在執(zhí)行這些熱點Trace生成的字節(jié)碼時在這些錨點處頻繁的進行環(huán)境切換，增加執(zhí)行開銷。如圖 4所示，以4為錨點的Trace:T1(4→5→6→8→9)首先被識別成熱點Trace并被編譯為目標代碼，由于此時以5為分支的路徑5→6在T1中而5→7不在T1中，因此將在T1的5→7處生成的字節(jié)碼中插入Guard標記。如果另外一條以4為錨點的路徑T2(4→5→7→8→9)也被識別為熱點Trace, 若不進行Trace合并，將在T2的5→6處生成的字節(jié)碼中也插入Guard標記。當執(zhí)行T1生成的目標代碼時，如果執(zhí)行到分支節(jié)點5處的條件導致進入5→7分支，因為遇到Guard標記導致發(fā)生旁路退出。同理，當執(zhí)行T2生成的目標代碼時，如果執(zhí)行到分支節(jié)點5處的條件導致進入5→6分支，將再次因為遇到Guard標記而發(fā)生旁路退出，從而由編譯環(huán)境切換到解釋環(huán)境，返回到4處時再次從解釋環(huán)境進入編譯環(huán)境。如果這種切換頻繁發(fā)生，會造成一定的性能損耗。

為了解決上述問題，我們將分如下三種情況對熱點Trace進行合并：

(1) 當前Trace的計數(shù)超過閾值時，如果其他已編譯的Trace中包含了該Trace的錨點，則將當前Trace添加到其他Trace中進行合并。

(2) 當前Trace的計數(shù)超過閾值時，如果當前Trace中包含了其他已編譯的Trace中對應(yīng)的錨點，則將其他熱蹤中的節(jié)點去重后合并到當前Trace中。

(3) 當前Trace有部分基本塊在其他Trace中，且錨點一致，則將當前Trace中的基本塊去重后并入其他熱蹤中。

如圖4所示，T1: ({4}, {4, 5, 6, 8, 9})首先被編譯為目標代碼，當T2 ({4}, {4, 5, 7, 8, 9})也被識別為熱點Trace時。由于T1和T2包含了同一個錨點4且有部分基本塊重合，對應(yīng)Trace合并的第3種情況。因此在生成T2的目標代碼時將利用T1中已生成的目標代碼進行合并得到Trace：T1-2:( {4}, {4, 5, 6, 7, 8, 9}) 對應(yīng)的目標代碼。當T3最后被識別為熱點Trace時，由于T3中包含錨點4并存在以4為錨點的Trace：T1-2的目標代碼，符合Trace合并的第二種情況，因此在生成T3對應(yīng)的目標代碼時將利用T1-2已生成的目標代碼生成合并后的Trace：T1-2-3:( ({2}, {2, 3, 4, 5, 6, 7, 8, 9,10})) 對應(yīng)的目標代碼。

圖4 Trace合并

2.6 環(huán)境切換

解釋執(zhí)行遇到錨點，如果該錨點已存在編譯好的目標代碼，需要從解釋環(huán)境切換到編譯環(huán)境，而從編譯執(zhí)行切換到解釋執(zhí)行時也需要將編譯環(huán)境中的變量值等信息返回到解釋執(zhí)行環(huán)境。因此需要在Java字節(jié)碼的開始位置生成調(diào)用代碼序列，將解釋執(zhí)行環(huán)境中的變量值傳遞到編譯環(huán)境的局部變量表中。并在熱點Trace生成的Java字節(jié)碼的Guard處插入從編譯環(huán)境切換到解釋環(huán)境的代碼，JVM根據(jù)該Guard處插入的代碼將編譯環(huán)境中的變量值傳遞到解釋環(huán)境。

如圖5中所示，由于解釋和編譯環(huán)境各自需要維護一個保存其變量值的環(huán)境，為了方便環(huán)境的切換，我們在解釋環(huán)境中定義了一個Environment對象，并在編譯環(huán)境中定義了一個該對象的引用，用于在編譯環(huán)境中使用解釋環(huán)境中的Environment對象。同時在編譯環(huán)境中維護一個Trace中所有變量在解釋環(huán)境和編譯環(huán)境中位置索引的映射表VarMap，以便實現(xiàn)變量值在解釋和編譯環(huán)境中的順利切換。

圖5 環(huán)境切換

(1) 解釋執(zhí)行到編譯執(zhí)行的切換

解釋執(zhí)行遇到已編譯好的Trace，為了保證解釋執(zhí)行環(huán)境中的變量值準確地傳遞到編譯環(huán)境，我們在生成Java字節(jié)碼的類中設(shè)計了一個靜態(tài)、公有的方法initFields，在生成Java字節(jié)碼時(如表3中L0之前)，先調(diào)用該靜態(tài)方法。該方法根據(jù)之前得到的變量映射表VarMap以及編譯環(huán)境中指向解釋環(huán)境對象Environment的引用從解釋環(huán)境中取變量值并賦給編譯環(huán)境對應(yīng)的局部變量表中，如圖5中實線所示。

(2) 解釋執(zhí)行到編譯執(zhí)行的切換

在執(zhí)行編譯好的Java字節(jié)碼的過程中，如果遇到了Guard指令引起控制流從該Trace進入未編譯分支，為了保證編譯執(zhí)行環(huán)境中的變量值準確地傳遞到解釋環(huán)境，我們定義了一個方法resetEnv用于在所有的Guard處插入從編譯環(huán)境切換到解釋環(huán)境的代碼。該方法根據(jù)變量映射表VarMap以及指向解釋環(huán)境中Environment對象的引用將當前JVM對應(yīng)棧幀的局部變量表中的變量值更新到解釋環(huán)境中，如圖5中虛線所示。

3 即時編譯的系統(tǒng)框架

本系統(tǒng)首先對CMinus程序進行分析生成控制流圖，然后在對其進行解釋執(zhí)行時進行Trace探測，識別出其中的熱點Trace，并將熱點Trace送入JIT編譯器翻譯為Java字節(jié)碼。當解釋執(zhí)行過程中遇到已編譯的熱點Trace時通過JVM調(diào)用已編譯好的Java字節(jié)碼編譯執(zhí)行，并將執(zhí)行結(jié)果返回。未編譯的分支仍然解釋執(zhí)行，同時繼續(xù)進行熱點Trace的記錄。同時在CMinus執(zhí)行引擎中考慮了解釋執(zhí)行和編譯執(zhí)行環(huán)境的切換，如圖6所示。

圖6 整體框架

4 實 驗

為了驗證本文提到的基于Trace的即時編譯執(zhí)行引擎的性能，在Java平臺下實現(xiàn)了圖6所示的一個通用執(zhí)行引擎，并設(shè)計了一組實驗來比較CMinus程序在解釋執(zhí)行與基于Trace的即時編譯執(zhí)行下的效率。測試環(huán)境如下：Windows7操作系統(tǒng)，Intel(R)Xeon(R)CPUE5-1607 0 @ 3.00GHz(3 000MHz)，內(nèi)存:8.00GB，主硬盤1 000GB。開發(fā)環(huán)境為Eclipse+Java+jdk1.7。

本文的實驗中使用的程序均為自定義用例，測試案例中包含了單重循環(huán)及多重循環(huán)，以及單分支與多分支的情況，并分別測試程序在解釋執(zhí)行、基于Trace的即時編譯情況下的性能。如表4所示。

表4 測試案例

如圖7所示，一般情況下，當執(zhí)行次數(shù)足夠多時，采用基于Trace的即時編譯比單純的解釋執(zhí)行效率都有一定程度的提高。案例1.4、1.6、1.7、1.10由于執(zhí)行次數(shù)較多，采用即時編譯技術(shù)相對于解釋執(zhí)行的時間開銷減少了將近一半，但是案例1.1為單重循環(huán)且執(zhí)行次數(shù)較少，由于Trace探測和編譯的開銷，其執(zhí)行效率反而不如解釋執(zhí)行高。

圖7 解釋執(zhí)行與熱蹤編譯比較

圖8顯示了不同案例的加速比(加速比= 解釋執(zhí)行時間/即時編譯時間×100%)，由于案例1.6和1.10分別為三重循環(huán)和四重循環(huán)且循環(huán)內(nèi)無分支節(jié)點，而且內(nèi)循環(huán)次數(shù)較多，所以加速比也比較高。

圖8 加速比

如圖9所示，不同案例在采用基于Trace的即時編譯時其編譯時間也有明顯的特征， 其中案例1.1、1.3和1.5都是單重循環(huán)，因此編譯時間較短。案例1.2、1.4、1.7、1.8和1.9由于包含雙重或三重循環(huán)且包含分支節(jié)點，因此多個Trace之間包含重復(fù)節(jié)點，從而增加了Trace合并及編譯的時間。案例1.10由于包含四重循環(huán)，盡管沒有分支節(jié)點，但由于增加了Trace合并時間，因而編譯時間也較長。

圖9 編譯時間

實驗結(jié)果表明：當執(zhí)行次數(shù)足夠多時，使用基于Trace的即時編譯，其執(zhí)行效率相對于解釋執(zhí)行能有明顯的提升。在包含多重循環(huán)或分支節(jié)點時，由于Trace探測及合并的開銷，其總的編譯時間也稍長，因此需要在較多的執(zhí)行次數(shù)時才能超過解釋執(zhí)行效率。但是當執(zhí)行次數(shù)較少時，如案例1.1中所示，由于Trace探測和編譯的開銷，其執(zhí)行效率可能還不如解釋執(zhí)行效率高。

5 相關(guān)工作

1999年，Sun公司提出Hotspot[1]技術(shù)，從Java1.3開始，JVM默認支持該技術(shù)。它通過自適應(yīng)優(yōu)化技術(shù)，使Java應(yīng)用程序的性能大步提升。該技術(shù)先對代碼進行分析，以檢測程序的關(guān)鍵熱點，然后集中編譯并優(yōu)化這些熱點代碼。但是該方法以整個方法為單位進行即時編譯，在這種情況下，方法內(nèi)執(zhí)行頻率不高的代碼也將參與到即時編譯中，增加了編譯開銷。

為此，GalA等人提出了基于Trace的即時編譯[5]，在進行熱點探測、即時編譯時以trace為單位，每個trace僅僅包含程序中執(zhí)行頻繁的代碼。因此，就編譯粒度而言，基于trace的即時編譯比基于方法的即時編譯要精細得多。

Dynamo[6]是第一個基于Trace優(yōu)化的編譯器，但是由于Dynamo探測的對象是機器指令，記錄的熱點trace也停留在機器碼層面，缺乏解釋器層面的高級信息。

HotpathVM和TraceMonkey[7]都將字節(jié)碼作為探測對象，動態(tài)識別出頻繁執(zhí)行的熱點trace，并將其翻譯為機器碼。但是這兩種技術(shù)中并沒有考慮Trace的合并，可能會因為遇到旁路退出的情況而導致頻繁地進行環(huán)境切換，增加了執(zhí)行開銷。而本文中由于對包含重復(fù)節(jié)點的Trace之間進行了合并，省去了頻繁的進行環(huán)境切換的時間開銷，可以更好地提高性能。

此外，基于Trace的即時編譯廣泛用于腳本語言的開發(fā)中，例如為Python開發(fā)的PyPy[8]，為JavaScript開發(fā)的SPUR[9]，以及為Lua開發(fā)的LuaJIT[10]。安卓Dalvik[11]虛擬機中也使用了基于Trace的熱點探測技術(shù)。

但是目前實現(xiàn)的基于Trace的即時編譯器通常是在字節(jié)碼或機器碼這種低層代碼上進行Trace探測，缺乏解釋器的高級信息，這使得Trace的探測需要增加大量的額外標注，而且這些代碼的閱讀難度較大。而本文直接針對CMinus這種較高級的語言進行Trace探測及編譯，可以方便地對控制流信息進行跟蹤且便于理解。

6 結(jié) 語

為了擴展基于Trace的即時編譯技術(shù)的應(yīng)用范圍，本文針對CMinus語言設(shè)計了一個基于Trace的即時編譯系統(tǒng)，介紹了基于Trace的熱點探測技術(shù)，并將解釋執(zhí)行過程中識別的熱點Trace翻譯成Java字節(jié)碼，通過JVM進行調(diào)用。同時為了避免多個Trace因包含重復(fù)節(jié)點而頻繁的進行環(huán)境切換，引入了Trace之間的合并技術(shù)。由于該系統(tǒng)支持解釋執(zhí)行和編譯執(zhí)行兩種模式，為了順利地實現(xiàn)執(zhí)行環(huán)境之間的相互切換，本文同時介紹了環(huán)境切換的設(shè)計及方法，實現(xiàn)了運行時的CMinus程序動態(tài)優(yōu)化。

通過實驗證明，與解釋執(zhí)行相比，當識別出的熱點Trace執(zhí)行次數(shù)足夠多時，該技術(shù)切實有效地提高了程序的執(zhí)行效率。在今后的工作中，我們將對識別出的Trace生成的字節(jié)碼進行一些優(yōu)化工作，以期進一步提高程序執(zhí)行效率。

[1]KotzmannT,WimmerC,MossenbockH,etal.DesignoftheJavaHotSpotclientcompilerforJava6[J].TransactionsonArchitectureandCodeOptimization,2008,5(1):7-10.

[2] 勞頓(KennethCLouden).編譯原理及實踐[M].馮博琴,等譯.北京:機械工業(yè)出版社,2000.

[3]AlfredvAho,RaviSethi,JeffreyDUllman.CompilersPrinciplesTechniquesandTools[M].3rded.Addision-WesleyPublishingCompany,1996.

[4]LindholmT,YellinF,BrachaG,etal.TheJavavirtualmachinespecification[M].3rded.AddisonWesley,2013.

[5]GalA,ProbstCW.HotpathVM:aneffectiveJITcompilerforresource-constraineddevices[C]//Proceedingsofthe2ndinternationalconferenceonVirtualexecutionenvironments.NewYorkUSA:ACMNewYork,2006:144-153.

[6]BalaV,DuesterwaldE,BanerjiaS.Dynamo:Atransparentdynamicoptimizationsystem[C]//Proceedingsofthe2000ACMSIGPLANConferenceonProgrammingLanguageDesignandImplementation.Canada:ACMSIGPLANNotices,2011:41-52.

[7]GalA,EichB,ShaverM,etal.Trace-basedjust-in-timetypespecializationfordynamiclanguages[C]//Proceedingsofthe2009ACMSIGPLANconferenceonProgramminglanguagedesignandimplementation.NewYorkUSA:ACMNewYork,2009:465-478.

[8]BolzFC,CuniA,FijalkowskiM,etal.Tracingthemeta-level:PyPy’stracingJITcompiler[C]//Proceedingsofthe4thworkshopontheImplementation,Compilation,OptimizationofObject-OrientedLanguagesandProgrammingSystems.NewYorkUSA:ACMNewYork,2009:18-25.

[9]BebenitaM,BrandnerF,FahndrichM,etal.SPUR:atrace-basedJITcompilerforCIL[C]//ProceedingsoftheACMinternationalconferenceonObjectorientedprogrammingsystemslanguagesandapplications.NewYorkUSA:ACMNewYork,2010:708-725.

[10]YermolovichA,WimmerC,FranzM.Optimizationofdynamiclanguagesusinghierarchicallayeringofvirtualmachines[C]//Proceedingsofthe5thSymposiumonDynamicLanguages.USA:Florida,2009:79-88.

[11]PerezGA,KaoCM,ChungYC,etal.Ahybridjust-in-timecompilerforandroid:comparingJITtypesandtheresultofcooperation[C]//Proceedingsofthe2012internationalconferenceonCompilers,architecturesandsynthesisforembeddedsystems.ACM,2012:41-50.

A TRACE-BASED JUST-IN-TIME COMPILATION TECHNIQUE OF CMINUS

Tao Shengzhao1Liao Husheng2Su Hang1Gao Hongyu1

1(CollegeofComputerSciences,BeijingUniversityofTechnology,Beijing100124,China)2(SchoolofSoftwareEngineering,BeijingUniversityofTechnology,Beijing100124,China)

JIT (Just-In-Time) compilation technique is an effective method to improve the performance of dynamic language; a Trace-based JIT compilation technique can detect the frequently executed parts of the program at runtime, and compiles it into target language or doing some optimization work. Moreover, it can improve the overall efficiency of the program in a considerable number of scenarios. However, it is difficult to develop a JIT Compiler, which involves the optimization of the underlying code, thus limited its application range. Therefore, we proposed a Trace-based JIT compilation technique used on CMinus which is a subset of C language for this purpose. Any language can be translated into CMinus can use this technique to improve the execution efficiency of the program. Any algorithm implemented by CMinus can be supported by this Trace-based compilation technique. The experimental results show that this method can effectively improve the efficiency of the program.

CMinus JIT compilation Trace-based Environment alternation

2016-01-10。國家自然科學基金青年

61202074)；北京市自然科學

基金項目(4122011)。陶勝召，碩士生，主研領(lǐng)域：動態(tài)編譯。廖湖聲，教授。蘇航，講師。高紅雨，副教授。

TP314

A

10.3969/j.issn.1000-386x.2017.03.010