基于Trace的CMinus語言即時編譯技術

陶勝召 廖湖聲 蘇 航 高紅雨

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

基于Trace的CMinus語言即時編譯技術

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

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

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

CMinus 即時編譯 基于蹤跡 環境切換

0 引 言

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

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

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

1) 提出了一種即時編譯系統的實現方法。基于Trace和基于函數的CMinus語言即時編譯，這種方法可用于實現各種程序設計語言的即時編譯。

2) 實現了從CMinus語言到Java字節碼的即時編譯，其他語言只要翻譯為CMinus就可以通過即時編譯技術得到程序優化。

3) 研制了一個CMinus執行引擎，采用解釋執行和熱蹤編譯執行的混合模式，實現運行時的CMinus程序動態優化。

1 基礎概念

1.1 CMinus概述

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

表1 CMinus語言核心文法

1.2 即時編譯

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

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

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

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

Trace= (Head, BlockLists)

其中：Head是Trace中的第一個基本塊標識。BlockLists是Trace中的基本塊順序序列。控制流只能從基本塊中第一個指令進入該塊，并且除了基本塊中最后一個指令，控制流在離開基本塊之前不會停機或者跳轉，因此一個基本塊列表唯一的標識了一條Trace。

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

表2 CMinus程序示例

圖1 fun函數基本塊流圖

1.3 JVM與Java棧幀

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

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

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

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

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

2 基于Trace的即時編譯技術

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

圖2 熱點Trace探測執行流程

2.1 錨點識別

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

2.2 Trace探測

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

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

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

2.3 生成目標代碼

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

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

圖3 局部變量的對應關系

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

表3 翻譯成目標代碼

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

2.4 執行目標代碼

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

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

2.5Trace合并

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

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

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

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

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

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

圖4 Trace合并

2.6 環境切換

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

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

圖5 環境切換

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

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

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

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

3 即時編譯的系統框架

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

圖6 整體框架

4 實 驗

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

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

表4 測試案例

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

圖7 解釋執行與熱蹤編譯比較

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

圖8 加速比

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

圖9 編譯時間

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

5 相關工作

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

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

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

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

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

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

6 結 語

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

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

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

[2] 勞頓(KennethCLouden).編譯原理及實踐[M].馮博琴,等譯.北京:機械工業出版社,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)。陶勝召，碩士生，主研領域：動態編譯。廖湖聲，教授。蘇航，講師。高紅雨，副教授。

TP314

A

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