基于Trace合并和寄存器分配的Dalvik優(yōu)化

余超君,李春強(qiáng),尚云海,張培勇

(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)

基于Trace合并和寄存器分配的Dalvik優(yōu)化

余超君,李春強(qiáng),尚云海,張培勇

(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)

Dalvik虛擬機(jī)作為Android系統(tǒng)上運(yùn)行所有應(yīng)用程序的基礎(chǔ),其性能瓶頸一直制約著Android系統(tǒng)的用戶體驗。通過研究Android系統(tǒng)中的Dalvik架構(gòu),分析其解釋器和JIT模塊的工作原理,發(fā)現(xiàn)熱Trace選擇過程中短Trace編譯損耗大以及即時編譯過程中寄存器分配不合理的情況。結(jié)合Java虛擬機(jī)技術(shù)和編譯器技術(shù),在現(xiàn)有熱Trace選擇和寄存器分配機(jī)制的基礎(chǔ)上,提出基于Trace合并和寄存器分配的優(yōu)化算法,在國產(chǎn)高性能嵌入式CPU CSKY體系下移植Dalvik虛擬機(jī)并實現(xiàn)了上述優(yōu)化算法。通過實驗證明優(yōu)化后Dalvik執(zhí)行Java程序的性能提高了近10%。

Dalvik虛擬機(jī);JIT技術(shù);性能優(yōu)化;Trace合并;寄存器分配;生命周期

1 概述

Android是Google公司針對嵌入式領(lǐng)域推出的操作系統(tǒng),其Java虛擬機(jī)采用Dalvik VM。與PC機(jī)Java虛擬機(jī)相比,Dalvik針對內(nèi)存和處理器速度有限的嵌入式設(shè)備進(jìn)行優(yōu)化,使其占用更少內(nèi)存等硬件資源,運(yùn)行效率更高。Dalvik工作于解釋執(zhí)行模式,并根據(jù)運(yùn)行情況通過基于Trace的JIT(Just in Time)技術(shù)將熱點代碼塊編譯成本地機(jī)器代碼并執(zhí)行以加快程序運(yùn)行[1]。

雖然基于Trace的JIT技術(shù)的Dalvik虛擬機(jī)提高了Java程序運(yùn)行速度,但其Dalvik虛擬機(jī)的性能仍是Android系統(tǒng)運(yùn)行速度的瓶頸。筆者在移植Dalvik到國產(chǎn)嵌入式CPU C-SKY平臺的過程中,通過對基于Trace的JIT技術(shù)的Dalvik虛擬機(jī)研究,發(fā)現(xiàn)Dalvik現(xiàn)階段基于Trace的JIT技術(shù)存在如下問題:(1)Hot-Trace的某些熱點代碼塊短導(dǎo)致編譯比執(zhí)行代碼時間長,相應(yīng)的編譯消耗大,而且編譯的本地機(jī)器碼短,代碼優(yōu)化空間小[2];(2)Trace編譯時,寄存器分配策略簡單,導(dǎo)致Java虛擬寄存器的冗余載入和存回,即增加了冗余的 load/store操作[3]。第(1)個問題可以通過Trace合并來增加Trace代碼塊長度,第(2)個問題可以通過寄存器分配策略優(yōu)化來減少冗余的load/sotre指令。

本文簡要介紹Dalvik虛擬機(jī)的特性并闡述其工作原理。在詳細(xì)分析基于Trace的JIT技術(shù)的Dalvik虛擬機(jī)基礎(chǔ)上,針對上述問題,設(shè)計并實現(xiàn)一種Trace合并和寄存器分配的優(yōu)化方法,并用標(biāo)準(zhǔn)Benchmark程序?qū)?yōu)化前后的Dalvik進(jìn)行性能評測。

2 Dalvik虛擬機(jī)

Dalvik是一個標(biāo)準(zhǔn)的Java運(yùn)行環(huán)境,但在內(nèi)部實現(xiàn)上,和標(biāo)準(zhǔn)JVM存在差異,具有如下特點[4]:

(1)不同于標(biāo)準(zhǔn)JVM運(yùn)行class文件,Dalvik虛擬機(jī)運(yùn)行的是由dx工具封裝好的dex文件。這樣做不僅減少了整體的文件尺寸,也加快了I/O操作,提高了類的查找速度。

(2)不同于標(biāo)準(zhǔn)JVM的基于棧的構(gòu)架,Dalvik虛擬機(jī)是基于寄存器的。基于寄存器的架構(gòu)雖然每條指令占用較多空間,但總體上減少了字節(jié)碼總條數(shù),即減少了指令分派次數(shù)及內(nèi)存訪問次數(shù)。

(3)不同于標(biāo)準(zhǔn) JVM運(yùn)行的 Java字節(jié)碼, Dalvik運(yùn)行根據(jù)基于寄存器的架構(gòu)設(shè)計了專有Bytecode[5]。

Dalvik執(zhí)行引擎采用基于Trace的JIT技術(shù)[6-7],其流程如圖1所示。

圖1 Dalvik的JIT流程

Dalvik虛擬機(jī)開始運(yùn)行時由解釋器解釋執(zhí)行Bytecode,并在各可能的Trace入口點記錄執(zhí)行過的次數(shù)。當(dāng)執(zhí)行次數(shù)達(dá)到某個閾值(如armv7閾值為40次),會檢查在該Trace入口點是否在保存編譯結(jié)果的內(nèi)存區(qū)域存在對應(yīng)的已編譯好的機(jī)器碼,若存在則跳轉(zhuǎn)到該機(jī)器碼直接運(yùn)行;否則繼續(xù)解釋執(zhí)行并開始記錄執(zhí)行軌跡(即Trace開始生成),直到Trace結(jié)束點,并提交這段Trace給編譯線程編譯。編譯好的機(jī)器碼會放入內(nèi)存區(qū)域,當(dāng)下次再執(zhí)行這個Trace入口地址時,就可跳轉(zhuǎn)到該機(jī)器碼塊直接執(zhí)行[6]。

3 JIT優(yōu)化

本文針對基于Trace的JIT模式的Dalvik虛擬機(jī)的缺點,提出通過Trace合并和寄存器分配策略進(jìn)行優(yōu)化。作為基于Trace的JIT特性的Dalvik虛擬機(jī),Trace的長度是影響其生成的機(jī)器碼的質(zhì)量的一個決定性因素,若Trace的長度比較短,則會導(dǎo)致解釋器和編譯線程的通信消耗加大,且生成機(jī)器碼時的可優(yōu)化空間變小[8],本文通過 Trace合并增加Trace長度,從而降低解釋器和編譯線程之間的通信消耗,同時使得在Trace編譯時可以通過更多的優(yōu)化技術(shù)提高生成的機(jī)器碼質(zhì)量[9]。本文還針對Dalvik在動態(tài)編譯時采用的基于輪詢機(jī)制的簡單寄存器分配策略,通過分析生命周期[10],減少虛擬寄存器中數(shù)據(jù)的載入和存回。

3.1 Trace合并

通過對標(biāo)準(zhǔn) Java測試程序 CaffeineMark在Dalvik上運(yùn)行時的分析,筆者發(fā)現(xiàn)作為Dalvik JIT在Trace劃分時的結(jié)束標(biāo)志性Bytecode類型中,69%的類型是條件跳轉(zhuǎn)Bytecode(即Branch類)。因此,筆者提出當(dāng)Trace以條件跳轉(zhuǎn)Bytecode結(jié)束時,選擇Branch Bytecode后的2個分支Trace中的1個和該Trace合并[11],從而加大Trace長度,提高編譯時優(yōu)化的可能性[12]。

考慮到Branch的2個出口都可能是其他Trace的入口。如圖2所示,If_eq Bytecode所在的Trace1連接著2個Trace(Trace 2和Trace 3)的入口。對此可以將其中一個Trace(如Trace 2)和Trace 1合并,如圖2(b)所示,合并后的Trace 4變長。

圖2 Trace合并

條件跳轉(zhuǎn)有2個分支,選擇哪個分支Trace合并到新的Trace將是一個問題。根據(jù)程序執(zhí)行的可預(yù)測性,為降低內(nèi)存開銷、減少Trace合并的性能損耗,采取如下預(yù)測算法:對于重復(fù)執(zhí)行的字節(jié)碼代碼段,條件分支的跳轉(zhuǎn)具有重復(fù)性。也就是說,在重復(fù)的代碼段中,條件跳轉(zhuǎn)第n次跳轉(zhuǎn)出口很有可能也是第n+1次跳轉(zhuǎn)的出口(比如在循環(huán)體中有if語句,一般情況下2個跳轉(zhuǎn)出口中的一個執(zhí)行的比較多)。筆者通過修改Dalvik解釋器,統(tǒng)計類似上述類型條件跳轉(zhuǎn)的跳轉(zhuǎn)出口,發(fā)現(xiàn)同一出口的執(zhí)行概率有81%。此實驗也驗證了預(yù)測算法的可行性。所以,在重復(fù)執(zhí)行代碼到達(dá)閾值后,其下一次跳轉(zhuǎn)的字節(jié)碼分支,作為合并的目標(biāo)字節(jié)碼分支。

圖3表示了圖2所示的Bytecode編譯成機(jī)器碼(CSKY指令集)后的情況(假設(shè)分支都被編譯)。圖3(a)中左分支由bf指令跳至鏈接單元chaining celln-1(用于跳轉(zhuǎn)到解釋器或者其他已編譯好的Trace)再跳入Trace 2的代碼中,Trace 2需要將虛擬寄存器v1的值載入實際寄存器中;右分支由bt指令跳至chaining celln再跳入Trace 3的代碼中,Trace 3需要將虛擬寄存器v1的值載入實際寄存器中。而如果通過合并Trace,編譯出來的機(jī)器碼將如圖3(b)所示,編譯Trace 4代碼,而原Trace 2中需要載入的虛擬寄存器如在原Trace 1中載入過則不需要重新載入。相比較可以發(fā)現(xiàn)如下優(yōu)點:bf指令和對應(yīng)的chaining celln-1由于代碼流將直接在預(yù)測分支執(zhí)行而不再需要,減少了整體內(nèi)存占用;原Trace 2中將減少若干用于虛擬寄存器載入的load指令,這對性能提升作用很大。

圖3 Trace合并后編譯的機(jī)器碼

3.2 寄存器分配

通過合并Trace來增加Trace長度,可以加大優(yōu)化窗口,從而提升性能。鑒于load/store一直是嵌入式設(shè)備的性能瓶頸[13],本文提出基于生命周期分析的寄存器分配算法,以減少Dalvik虛擬寄存器(存在內(nèi)存中)和物理寄存器之間的傳遞,從而有效減少load/store操作。特別是結(jié)合Trace合并優(yōu)化,代碼塊越長,越容易提升性能[14]。

如圖4中Bytecode部分所示(v0,v17,v0’等表示Bytecode的虛擬寄存器,a0,a1等表示物理寄存器),開始時對v0進(jìn)行運(yùn)算,經(jīng)過多條Bytecode后,又出現(xiàn)對v0運(yùn)算的Bytecode。在Dalvik現(xiàn)有的寄存器分配策略下,生成如圖4中優(yōu)化前部分所示的類似代碼:v0載入a0,在若干Bytecode后空閑物理寄存器用完,重新取a0用于v17的載入,當(dāng)遇到add v0,#6,需要重新載入v0到a1。其實這條load指令可以通過分析寄存器生命周期,并用適當(dāng)?shù)募拇嫫鞣峙洳呗韵Ｈ鐖D4中優(yōu)化后部分所示,當(dāng)空閑寄存器全部用完時,優(yōu)先分配那些生命周期已經(jīng)結(jié)束的寄存器給接下來的Bytecode(比如此例中的l9)使用,這樣在編譯add v0,#6這條指令時不需要重新load虛擬寄存器v0,因為v0的值已經(jīng)存在a0中,因而減少了load指令。實際應(yīng)用中,這種情況會很多(特別是Trace增長后),優(yōu)化后將有明顯效果。

圖4 寄存器分配優(yōu)化

3.3 優(yōu)化算法的實現(xiàn)

現(xiàn)有基于Trace的JIT技術(shù)的Dalvik虛擬機(jī)中建立Trace的過程如圖5(a)所示,在建立Trace階段,對每個Bytecode判斷其是否符合Trace結(jié)束條件,即當(dāng)前指令是否是Branch,Invoke,Switch,Return類指令或者當(dāng)前Trace超過最大限定長度。當(dāng)條件符合時,表示從前一個Trace入口到當(dāng)前Bytecode為一個可以編譯為機(jī)器碼的 Trace,將收集到的Trace信息(包括當(dāng)前Trace開始點位置,Trace中 Bytecode的數(shù)目等)以結(jié)構(gòu)數(shù)組Trace[MAX_JIT_ RUN_LEN]的方式存儲,以等待compiler線程獲取并編譯。Trace合并優(yōu)化流程如圖5(b)所示。在全局結(jié)構(gòu)Thread中加入整型Combination變量,其初值設(shè)為COMBINE宏(表示合并的最大Trace數(shù))。考慮到以Invoke,Switch,Return類Bytecode結(jié)束的Trace或超長Trace與后續(xù)Trace合并后對系統(tǒng)優(yōu)化起到的比例較低,只針對以Branch類Bytecode結(jié)束的Trace與后續(xù)Trace進(jìn)行合并。

圖5 Trace合并優(yōu)化

當(dāng)Trace將以Branch指令結(jié)束,根據(jù)Combination變量是否已經(jīng)等于1判斷其是否已經(jīng)到了合并Trace數(shù)目最大值。若未等于1,對Combination值減1并將Trace信息放入結(jié)構(gòu)數(shù)組Trace[MAX_JIT_RUN_LEN]下一個組成員中,繼續(xù)建立Trace。若已經(jīng)等于1, Combination恢復(fù)為COMBINE并結(jié)束Trace的建立,將Trace[MAX_JIT_RUN_LEN]存儲等待編譯。

在編譯線程中,若 Trace[MAX_JIT_RUN_ LEN]指示的Trace最后一個字節(jié)碼是Branch類的,則它的跳轉(zhuǎn)目標(biāo)為相應(yīng)指令(即合并后的下一個塊),而不是 Chaining Cell,并不再建立相應(yīng)的Chaining Cell。

Dalvik編譯過程中的寄存器分配策略比較簡單,如圖6(a)所示。寄存器分配優(yōu)先分配那些當(dāng)前Bytecode不用且之前也沒有分配過(即不在活動中)的寄存器,如果不存在,則只需保證當(dāng)前Bytecode不用的寄存器即可。但是,當(dāng)編譯單元長度增加,寄存器分配次數(shù)增多,就可能出現(xiàn)一個物理寄存器多次分配給不同的虛擬寄存器,導(dǎo)致虛擬寄存器內(nèi)的值在其生命周期內(nèi)會被多次存回和重載入,從而增加load/store指令。

為優(yōu)化寄存器分配策略,本文在編譯階段使用靜態(tài)單一賦值(Static Single Assignment,SSA)法轉(zhuǎn)換時,為每個SSA寄存器存儲其生命周期消失點,以消失點的Bytecode距離Trace首的偏移值表示,并用變量useend_offset保存。然后在代表物理寄存器狀態(tài)的RegisterInfo結(jié)構(gòu)中加入整型變量useend,用于對SSA寄存器分配物理寄存器時保存對應(yīng)的useend_offset。

圖6 寄存器優(yōu)化

在寄存器分配時,如圖6(b)所示,優(yōu)先分配那些當(dāng)前Bytecode不用、之前也沒有分配過的寄存器且寄存器RegisterInfo結(jié)構(gòu)中useend的值小于當(dāng)前編譯的Bytecode距Trace頭的偏移值(即表示該寄存器在后續(xù)不會被用到,也就減少了 load/store指令),然后再同原分配策略類似分配。

4 性能分析

CaffeineMark是常用的針對嵌入式設(shè)備進(jìn)行性能評測的一款Java軟件,其分?jǐn)?shù)高低體現(xiàn)了其性能的好壞,采用該軟件來測評優(yōu)化的效果。

實驗硬件平臺是C-SKY公司的國產(chǎn)高性能嵌入式CPU CK810 16 MHz FPGA板,軟件平臺是Android 4.0.3。CaffeineMark包括 Sieve,Loop, Logic,String,Float,Method,Overall 7個組件。筆者針對未優(yōu)化、僅Trace合并優(yōu)化、僅寄存器分配優(yōu)化、兩者都優(yōu)化這4種情況進(jìn)行測評,實驗結(jié)果如表1所示,表中數(shù)據(jù)表示相應(yīng)測試項目的得分。

表1 性能測試數(shù)據(jù)

由實驗數(shù)據(jù)可見,優(yōu)化實現(xiàn)后性能提高接近10%?？梢钥闯?僅有Trace合并優(yōu)化時效果一般,僅有寄存器分配優(yōu)化時效果不明顯,而當(dāng)兩者同時使用時,優(yōu)化效果比較明顯。這也說明了Trace合并的優(yōu)化使Trace長度增加,基于其上的寄存器優(yōu)化的效果更加明顯。

5 結(jié)束語

在已經(jīng)移植好的Android4.0.3基礎(chǔ)上,本文描述了對其Dalvik虛擬機(jī)的優(yōu)化,包括Trace合并和寄存器分配優(yōu)化,并通過實驗對Dalvik優(yōu)化前后的性能進(jìn)行了對比,結(jié)果表明Dalvik的優(yōu)化效果比較明顯。下一步工作包括確定Trace合并數(shù)目的最優(yōu)解以及嘗試一些其他傳統(tǒng)編譯器的優(yōu)化方法。

[1] Bornstein D.The Dalvik VM Internals[C]//Proc.of Google I/O Developer Conference.San Francisco,USA: [s.n.],2008:1-8.

[2] Hiroshi I.A Trace-based Java JIT Compiler for Large-scale Applications[C]//Proc.of the 6th ACM Workshop on Virtual Machines and Inter-mediate Languages.New York, USA:ACM Press,2012:1-2.

[3] Hsu Wei-Chung,Charles N F,Goodman J R.On the Minimization of Load/stores in Local Register Allocation[J].IEEE Transactions on Software Engineering, 1989,15(10):1250-1260.

[4] Security Engineering Research Group.Analysis of Dalvik Virtual Machine and Class Path Library[EB/OL]. (2009-07-12).http://imsciences.edu.pk/serg/wp-content/ uploads/2009/07/Analysis-of-Dalvik-VM.pdf.

[5] 葉 云,李春強(qiáng),胡軍山.基于CK610的Dalvik虛擬機(jī)移植與優(yōu)化[J].計算機(jī)工程,2011,37(16):291-292.

[6] Ben C,Bill B.A JIT Compiler for Android’s Dalvik VM [EB/OL].(2010-05-19).http://www.google.com/intl/ zh-CN/events/io/2010/sessions/jit-compiler-androidsdalvik-vm.html.

[7] 周毅敏,陳 榕.Dalvik虛擬機(jī)進(jìn)程模型分析[J].計算機(jī)技術(shù)與發(fā)展,2010,20(2):83-86.

[8] Hiroshi I,Hiroshige H,Peng W.A Trace-based Java JIT Compiler Retrofitted from a Method-based Compiler[C]// Proc.of the 9th AnnualIEEE/ACM International Symposium on Code Generation and Optimization. Chamonix,France:IEEE Press,2011:246-256.

[9] Gal A,Eich B,Shaver M,et al.Trace-based Just-in-time Type Specialization for Dynamic Languages[C]//Proc. ofACM SIGPLAN Conferenceon Programming Language Design and Implementation.New York,USA: ACM Press,2009:465-478.

[10] Byung-Sun Y,Junpyo E,SeungIl L,et al.Efficient Register Mapping and Allocation in LaTTe,An Open-Source Java Just-in-time Compiler[J].IEEE Transactions on Parallel and Distributed Systems,2007,18 (1):57-69.

[11] Bebenita M,Brabdner F,Fahndrich M,et al.SPUR:A Trace-based JIT Compiler for CIL[R].Microsoft Corporation,Technical Report:MSR-TR-2010-27,2010.

[12] Cramer T,Richard F R,Miler T.Compiling Java Just in Time[Z].1997.

[13] Suganuma T,Yasue T,Nakatani T.A Region-based Compilation Technique for Dynamic Compilers[J]. ACM Transactions on Programming Languages and Systems,2006,28(1):134-174.

[14] Gal A.Efficient Bytecode Verification and Compilation in a Virtual Machine[D].Long Beach,USA:University of California,2006.

編輯 陸燕菲

Optimization of Dalvik Based on Trace-combination and Register Allocation

YU Chao-jun,LI Chun-qiang,SHANG Yun-hai,ZHANG Pei-yong
(Institute of VLSI Design,Zhejiang University,Hangzhou 310027,China)

As the basics of running application on Android system,performance of Dalvik virtual machine restricts the Android’s user experience.By researching Dalvik architecture in the Android system and analyzing some key techniques of the interpreter and Just in Time(JIT)module,it finds that short Trace’s compiler dissipation is large and there are some irrational situations on register allocation in JIT.Combining nowadays JVM technology with modern compiler technology,and based on the Trace selection strategy and register allocation mechanism of Dalvik,this paper proposes algorithms of combining Trace and optimizing strategy of register allocation.These algorithms are implemented in high performance embedded CPU CSKY architecture.The experiments prove that this Dalvik can improve the performance by about 10%.

Dalvik virtual machine;Just in Time(JIT)technology;performance optimization;Trace-combination; register allocation;life cycle

1000-3428(2014)10-0061-05

A

TP314

10.3969/j.issn.1000-3428.2014.10.012

國家自然科學(xué)基金資助項目(61204111);“核高基”重大專項(2010ZX01030-001-001-002)。

余超君(1989-),男,碩士,主研方向:虛擬機(jī)技術(shù)與應(yīng)用;李春強(qiáng)、尚云海,碩士;張培勇,副教授、博士。

2013-09-13

2013-11-30E-mail:67146172@qq.com

中文引用格式:余超君,李春強(qiáng),尚云海,等.基于Trace合并和寄存器分配的Dalvik優(yōu)化[J].計算機(jī)工程,2014, 40(10):61-65,70.

英文引用格式:Yu Chaojun,Li Chunqiang,Shang Yunhai,et al.Optimization of Dalvik Based on Trace-combination and Register Allocation[J].Computer Engineering,2014,40(10):61-65,70.