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

陶勝召 廖湖聲 蘇 航 高紅雨

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

1 基礎(chǔ)概念

1.1 CMinus概述

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

表1 CMinus語(yǔ)言核心文法

1.2 即時(shí)編譯

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

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

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

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

Trace= (Head, BlockLists)

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

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

表2 CMinus程序示例

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

1.3 JVM與Java棧幀

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

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

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

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

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

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

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

圖2 熱點(diǎn)Trace探測(cè)執(zhí)行流程

2.1 錨點(diǎn)識(shí)別

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

2.2 Trace探測(cè)

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

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

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

2.3 生成目標(biāo)代碼

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

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

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

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

表3 翻譯成目標(biāo)代碼

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

2.4 執(zhí)行目標(biāo)代碼

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

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

2.5Trace合并

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

為了解決上述問題，我們將分如下三種情況對(duì)熱點(diǎn)Trace進(jìn)行合并：

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

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

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

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

圖4 Trace合并

2.6 環(huán)境切換

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

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

圖5 環(huán)境切換

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

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

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

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

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

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

圖6 整體框架

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

為了驗(yàn)證本文提到的基于Trace的即時(shí)編譯執(zhí)行引擎的性能，在Java平臺(tái)下實(shí)現(xiàn)了圖6所示的一個(gè)通用執(zhí)行引擎，并設(shè)計(jì)了一組實(shí)驗(yàn)來比較CMinus程序在解釋執(zhí)行與基于Trace的即時(shí)編譯執(zhí)行下的效率。測(cè)試環(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。

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

表4 測(cè)試案例

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

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

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

圖8 加速比

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

圖9 編譯時(shí)間

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

5 相關(guān)工作

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

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

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

HotpathVM和TraceMonkey[7]都將字節(jié)碼作為探測(cè)對(duì)象，動(dòng)態(tài)識(shí)別出頻繁執(zhí)行的熱點(diǎn)trace，并將其翻譯為機(jī)器碼。但是這兩種技術(shù)中并沒有考慮Trace的合并，可能會(huì)因?yàn)橛龅脚月吠顺龅那闆r而導(dǎo)致頻繁地進(jìn)行環(huán)境切換，增加了執(zhí)行開銷。而本文中由于對(duì)包含重復(fù)節(jié)點(diǎn)的Trace之間進(jìn)行了合并，省去了頻繁的進(jìn)行環(huán)境切換的時(shí)間開銷，可以更好地提高性能。

此外，基于Trace的即時(shí)編譯廣泛用于腳本語(yǔ)言的開發(fā)中，例如為Python開發(fā)的PyPy[8]，為JavaScript開發(fā)的SPUR[9]，以及為L(zhǎng)ua開發(fā)的LuaJIT[10]。安卓Dalvik[11]虛擬機(jī)中也使用了基于Trace的熱點(diǎn)探測(cè)技術(shù)。

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

6 結(jié) 語(yǔ)

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

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

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

[2] 勞頓(KennethCLouden).編譯原理及實(shí)踐[M].馮博琴,等譯.北京:機(jī)械工業(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。國(guó)家自然科學(xué)基金青年

61202074)；北京市自然科學(xué)

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

TP314

A

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