基于Trace合并和寄存器分配的Dalvik优化

余超君,李春强,尚云海,张培勇

(浙江大学超大规模集成电路设计研究所,杭州310027)

基于Trace合并和寄存器分配的Dalvik优化

余超君,李春强,尚云海,张培勇

(浙江大学超大规模集成电路设计研究所,杭州310027)

Dalvik虚拟机作为Android系统上运行所有应用程序的基础,其性能瓶颈一直制约着Android系统的用户体验。通过研究Android系统中的Dalvik架构,分析其解释器和JIT模块的工作原理,发现热Trace选择过程中短Trace编译损耗大以及即时编译过程中寄存器分配不合理的情况。结合Java虚拟机技术和编译器技术,在现有热Trace选择和寄存器分配机制的基础上,提出基于Trace合并和寄存器分配的优化算法,在国产高性能嵌入式CPU CSKY体系下移植Dalvik虚拟机并实现了上述优化算法。通过实验证明优化后Dalvik执行Java程序的性能提高了近10%。

Dalvik虚拟机;JIT技术;性能优化;Trace合并;寄存器分配;生命周期

1 概述

Android是Google公司针对嵌入式领域推出的操作系统,其Java虚拟机采用Dalvik VM。与PC机Java虚拟机相比,Dalvik针对内存和处理器速度有限的嵌入式设备进行优化,使其占用更少内存等硬件资源,运行效率更高。Dalvik工作于解释执行模式,并根据运行情况通过基于Trace的JIT(Just in Time)技术将热点代码块编译成本地机器代码并执行以加快程序运行[1]。

虽然基于Trace的JIT技术的Dalvik虚拟机提高了Java程序运行速度,但其Dalvik虚拟机的性能仍是Android系统运行速度的瓶颈。笔者在移植Dalvik到国产嵌入式CPU C-SKY平台的过程中,通过对基于Trace的JIT技术的Dalvik虚拟机研究,发现Dalvik现阶段基于Trace的JIT技术存在如下问题:(1)Hot-Trace的某些热点代码块短导致编译比执行代码时间长,相应的编译消耗大,而且编译的本地机器码短,代码优化空间小[2];(2)Trace编译时,寄存器分配策略简单,导致Java虚拟寄存器的冗余载入和存回,即增加了冗余的 load/store操作[3]。第(1)个问题可以通过Trace合并来增加Trace代码块长度,第(2)个问题可以通过寄存器分配策略优化来减少冗余的load/sotre指令。

本文简要介绍Dalvik虚拟机的特性并阐述其工作原理。在详细分析基于Trace的JIT技术的Dalvik虚拟机基础上,针对上述问题,设计并实现一种Trace合并和寄存器分配的优化方法,并用标准Benchmark程序对优化前后的Dalvik进行性能评测。

2 Dalvik虚拟机

Dalvik是一个标准的Java运行环境,但在内部实现上,和标准JVM存在差异,具有如下特点[4]:

(1)不同于标准JVM运行class文件,Dalvik虚拟机运行的是由dx工具封装好的dex文件。这样做不仅减少了整体的文件尺寸,也加快了I/O操作,提高了类的查找速度。

(2)不同于标准JVM的基于栈的构架,Dalvik虚拟机是基于寄存器的。基于寄存器的架构虽然每条指令占用较多空间,但总体上减少了字节码总条数,即减少了指令分派次数及内存访问次数。

(3)不同于标准 JVM运行的 Java字节码, Dalvik运行根据基于寄存器的架构设计了专有Bytecode[5]。

Dalvik执行引擎采用基于Trace的JIT技术[6-7],其流程如图1所示。

图1 Dalvik的JIT流程

Dalvik虚拟机开始运行时由解释器解释执行Bytecode,并在各可能的Trace入口点记录执行过的次数。当执行次数达到某个阈值(如armv7阈值为40次),会检查在该Trace入口点是否在保存编译结果的内存区域存在对应的已编译好的机器码,若存在则跳转到该机器码直接运行;否则继续解释执行并开始记录执行轨迹(即Trace开始生成),直到Trace结束点,并提交这段Trace给编译线程编译。编译好的机器码会放入内存区域,当下次再执行这个Trace入口地址时,就可跳转到该机器码块直接执行[6]。

3 JIT优化

本文针对基于Trace的JIT模式的Dalvik虚拟机的缺点,提出通过Trace合并和寄存器分配策略进行优化。作为基于Trace的JIT特性的Dalvik虚拟机,Trace的长度是影响其生成的机器码的质量的一个决定性因素,若Trace的长度比较短,则会导致解释器和编译线程的通信消耗加大,且生成机器码时的可优化空间变小[8],本文通过 Trace合并增加Trace长度,从而降低解释器和编译线程之间的通信消耗,同时使得在Trace编译时可以通过更多的优化技术提高生成的机器码质量[9]。本文还针对Dalvik在动态编译时采用的基于轮询机制的简单寄存器分配策略,通过分析生命周期[10],减少虚拟寄存器中数据的载入和存回。

3.1 Trace合并

通过对标准 Java测试程序 CaffeineMark在Dalvik上运行时的分析,笔者发现作为Dalvik JIT在Trace划分时的结束标志性Bytecode类型中,69%的类型是条件跳转Bytecode(即Branch类)。因此,笔者提出当Trace以条件跳转Bytecode结束时,选择Branch Bytecode后的2个分支Trace中的1个和该Trace合并[11],从而加大Trace长度,提高编译时优化的可能性[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合并

条件跳转有2个分支,选择哪个分支Trace合并到新的Trace将是一个问题。根据程序执行的可预测性,为降低内存开销、减少Trace合并的性能损耗,采取如下预测算法:对于重复执行的字节码代码段,条件分支的跳转具有重复性。也就是说,在重复的代码段中,条件跳转第n次跳转出口很有可能也是第n+1次跳转的出口(比如在循环体中有if语句,一般情况下2个跳转出口中的一个执行的比较多)。笔者通过修改Dalvik解释器,统计类似上述类型条件跳转的跳转出口,发现同一出口的执行概率有81%。此实验也验证了预测算法的可行性。所以,在重复执行代码到达阈值后,其下一次跳转的字节码分支,作为合并的目标字节码分支。

图3表示了图2所示的Bytecode编译成机器码(CSKY指令集)后的情况(假设分支都被编译)。图3(a)中左分支由bf指令跳至链接单元chaining celln-1(用于跳转到解释器或者其他已编译好的Trace)再跳入Trace 2的代码中,Trace 2需要将虚拟寄存器v1的值载入实际寄存器中;右分支由bt指令跳至chaining celln再跳入Trace 3的代码中,Trace 3需要将虚拟寄存器v1的值载入实际寄存器中。而如果通过合并Trace,编译出来的机器码将如图3(b)所示,编译Trace 4代码,而原Trace 2中需要载入的虚拟寄存器如在原Trace 1中载入过则不需要重新载入。相比较可以发现如下优点:bf指令和对应的chaining celln-1由于代码流将直接在预测分支执行而不再需要,减少了整体内存占用;原Trace 2中将减少若干用于虚拟寄存器载入的load指令,这对性能提升作用很大。

图3 Trace合并后编译的机器码

3.2 寄存器分配

通过合并Trace来增加Trace长度,可以加大优化窗口,从而提升性能。鉴于load/store一直是嵌入式设备的性能瓶颈[13],本文提出基于生命周期分析的寄存器分配算法,以减少Dalvik虚拟寄存器(存在内存中)和物理寄存器之间的传递,从而有效减少load/store操作。特别是结合Trace合并优化,代码块越长,越容易提升性能[14]。

如图4中Bytecode部分所示(v0,v17,v0’等表示Bytecode的虚拟寄存器,a0,a1等表示物理寄存器),开始时对v0进行运算,经过多条Bytecode后,又出现对v0运算的Bytecode。在Dalvik现有的寄存器分配策略下,生成如图4中优化前部分所示的类似代码:v0载入a0,在若干Bytecode后空闲物理寄存器用完,重新取a0用于v17的载入,当遇到add v0,#6,需要重新载入v0到a1。其实这条load指令可以通过分析寄存器生命周期,并用适当的寄存器分配策略消除。如图4中优化后部分所示,当空闲寄存器全部用完时,优先分配那些生命周期已经结束的寄存器给接下来的Bytecode(比如此例中的l9)使用,这样在编译add v0,#6这条指令时不需要重新load虚拟寄存器v0,因为v0的值已经存在a0中,因而减少了load指令。实际应用中,这种情况会很多(特别是Trace增长后),优化后将有明显效果。

图4 寄存器分配优化

3.3 优化算法的实现

现有基于Trace的JIT技术的Dalvik虚拟机中建立Trace的过程如图5(a)所示,在建立Trace阶段,对每个Bytecode判断其是否符合Trace结束条件,即当前指令是否是Branch,Invoke,Switch,Return类指令或者当前Trace超过最大限定长度。当条件符合时,表示从前一个Trace入口到当前Bytecode为一个可以编译为机器码的 Trace,将收集到的Trace信息(包括当前Trace开始点位置,Trace中 Bytecode的数目等)以结构数组Trace[MAX_JIT_ RUN_LEN]的方式存储,以等待compiler线程获取并编译。Trace合并优化流程如图5(b)所示。在全局结构Thread中加入整型Combination变量,其初值设为COMBINE宏(表示合并的最大Trace数)。考虑到以Invoke,Switch,Return类Bytecode结束的Trace或超长Trace与后续Trace合并后对系统优化起到的比例较低,只针对以Branch类Bytecode结束的Trace与后续Trace进行合并。

图5 Trace合并优化

当Trace将以Branch指令结束,根据Combination变量是否已经等于1判断其是否已经到了合并Trace数目最大值。若未等于1,对Combination值减1并将Trace信息放入结构数组Trace[MAX_JIT_RUN_LEN]下一个组成员中,继续建立Trace。若已经等于1, Combination恢复为COMBINE并结束Trace的建立,将Trace[MAX_JIT_RUN_LEN]存储等待编译。

在编译线程中,若 Trace[MAX_JIT_RUN_ LEN]指示的Trace最后一个字节码是Branch类的,则它的跳转目标为相应指令(即合并后的下一个块),而不是 Chaining Cell,并不再建立相应的Chaining Cell。

Dalvik编译过程中的寄存器分配策略比较简单,如图6(a)所示。寄存器分配优先分配那些当前Bytecode不用且之前也没有分配过(即不在活动中)的寄存器,如果不存在,则只需保证当前Bytecode不用的寄存器即可。但是,当编译单元长度增加,寄存器分配次数增多,就可能出现一个物理寄存器多次分配给不同的虚拟寄存器,导致虚拟寄存器内的值在其生命周期内会被多次存回和重载入,从而增加load/store指令。

为优化寄存器分配策略,本文在编译阶段使用静态单一赋值(Static Single Assignment,SSA)法转换时,为每个SSA寄存器存储其生命周期消失点,以消失点的Bytecode距离Trace首的偏移值表示,并用变量useend_offset保存。然后在代表物理寄存器状态的RegisterInfo结构中加入整型变量useend,用于对SSA寄存器分配物理寄存器时保存对应的useend_offset。

图6 寄存器优化

在寄存器分配时,如图6(b)所示,优先分配那些当前Bytecode不用、之前也没有分配过的寄存器且寄存器RegisterInfo结构中useend的值小于当前编译的Bytecode距Trace头的偏移值(即表示该寄存器在后续不会被用到,也就减少了 load/store指令),然后再同原分配策略类似分配。

4 性能分析

CaffeineMark是常用的针对嵌入式设备进行性能评测的一款Java软件,其分数高低体现了其性能的好坏,采用该软件来测评优化的效果。

实验硬件平台是C-SKY公司的国产高性能嵌入式CPU CK810 16 MHz FPGA板,软件平台是Android 4.0.3。CaffeineMark包括 Sieve,Loop, Logic,String,Float,Method,Overall 7个组件。笔者针对未优化、仅Trace合并优化、仅寄存器分配优化、两者都优化这4种情况进行测评,实验结果如表1所示,表中数据表示相应测试项目的得分。

表1 性能测试数据

由实验数据可见,优化实现后性能提高接近10%。可以看出,仅有Trace合并优化时效果一般,仅有寄存器分配优化时效果不明显,而当两者同时使用时,优化效果比较明显。这也说明了Trace合并的优化使Trace长度增加,基于其上的寄存器优化的效果更加明显。

5 结束语

在已经移植好的Android4.0.3基础上,本文描述了对其Dalvik虚拟机的优化,包括Trace合并和寄存器分配优化,并通过实验对Dalvik优化前后的性能进行了对比,结果表明Dalvik的优化效果比较明显。下一步工作包括确定Trace合并数目的最优解以及尝试一些其他传统编译器的优化方法。

[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] 叶 云,李春强,胡军山.基于CK610的Dalvik虚拟机移植与优化[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].计算机技术与发展,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

国家自然科学基金资助项目(61204111);“核高基”重大专项(2010ZX01030-001-001-002)。

余超君(1989-),男,硕士,主研方向:虚拟机技术与应用;李春强、尚云海,硕士;张培勇,副教授、博士。

2013-09-13

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

中文引用格式:余超君,李春强,尚云海,等.基于Trace合并和寄存器分配的Dalvik优化[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.