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

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

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

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

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

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

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

1 概述

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

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

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

2 Dalvik虛擬機(jī)

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

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

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

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

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

圖1 Dalvik的JIT流程

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

3 JIT優(yōu)化

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

3.1 Trace合并

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

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

圖2 Trace合并

條件跳轉(zhuǎn)有2個(gè)分支,選擇哪個(gè)分支Trace合并到新的Trace將是一個(gè)問(wèn)題。根據(jù)程序執(zhí)行的可預(yù)測(cè)性,為降低內(nèi)存開(kāi)銷(xiāo)、減少Trace合并的性能損耗,采取如下預(yù)測(cè)算法:對(duì)于重復(fù)執(zhí)行的字節(jié)碼代碼段,條件分支的跳轉(zhuǎn)具有重復(fù)性。也就是說(shuō),在重復(fù)的代碼段中,條件跳轉(zhuǎn)第n次跳轉(zhuǎn)出口很有可能也是第n+1次跳轉(zhuǎn)的出口(比如在循環(huán)體中有if語(yǔ)句,一般情況下2個(gè)跳轉(zhuǎn)出口中的一個(gè)執(zhí)行的比較多)。筆者通過(guò)修改Dalvik解釋器,統(tǒng)計(jì)類(lèi)似上述類(lèi)型條件跳轉(zhuǎn)的跳轉(zhuǎn)出口,發(fā)現(xiàn)同一出口的執(zhí)行概率有81%。此實(shí)驗(yàn)也驗(yàn)證了預(yù)測(cè)算法的可行性。所以,在重復(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的值載入實(shí)際寄存器中;右分支由bt指令跳至chaining celln再跳入Trace 3的代碼中,Trace 3需要將虛擬寄存器v1的值載入實(shí)際寄存器中。而如果通過(guò)合并Trace,編譯出來(lái)的機(jī)器碼將如圖3(b)所示,編譯Trace 4代碼,而原Trace 2中需要載入的虛擬寄存器如在原Trace 1中載入過(guò)則不需要重新載入。相比較可以發(fā)現(xiàn)如下優(yōu)點(diǎn):bf指令和對(duì)應(yīng)的chaining celln-1由于代碼流將直接在預(yù)測(cè)分支執(zhí)行而不再需要,減少了整體內(nèi)存占用;原Trace 2中將減少若干用于虛擬寄存器載入的load指令,這對(duì)性能提升作用很大。

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

3.2 寄存器分配

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

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

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

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

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

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

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

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

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

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

4 性能分析

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

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

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

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

5 結(jié)束語(yǔ)

在已經(jīng)移植好的Android4.0.3基礎(chǔ)上,本文描述了對(duì)其Dalvik虛擬機(jī)的優(yōu)化,包括Trace合并和寄存器分配優(yōu)化,并通過(guò)實(shí)驗(yàn)對(duì)Dalvik優(yōu)化前后的性能進(jìn)行了對(duì)比,結(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ì)算機(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ì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61204111);“核高基”重大專(zhuān)項(xiàng)(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ì)算機(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.