针对SECD抽象机的基于踪迹的即时编译技术

于成龙，廖湖声，武辰之，苏 航

（1.北京工业大学 计算机学院，北京100124；2.北京工业大学 软件学院，北京100124）

0 引 言

即时编译技术是在程序运行时将部分程序片段的解释执行转化为编译执行的程序优化技术。例如，在HotSpot虚拟机中，Java字节码程序最初是由解释器直接解释执行，当虚拟机发现某个方法或是代码块执行次数非常频繁时，就会把这些代码识别为 “热点”，由即时编译器将其编译成本地平台相关的机器码［1］。

传统的即时编译器以整个方法为单位进行即时编译（如HotSpot），这将导致方法内执行频度不高的代码也参与编译，增加了编译开销。为解决这一问题，Gal A 等提出了基于 踪 迹 的 即 时 编 译（trace－based just－in－time compilation）［2］进行热点探测。即时编译时以 “踪迹”（trace）为单位，比以方法为单位要精细得多，而且踪迹可以跨越方法，能提供更多优化机会。

本文提出了一种基于踪迹的通用即时编译技术，将在SECD 指令序列的执行过程中，监测程序执行情况，将执行频繁的代码编译为Java字节码。为保证编译所得的Java字节码能正常运行，本文还介绍了解释执行环境与Java字节码程序执行环境的动态转换方法。任何用SECD 抽象机实现的编程语言都可采用该技术来提高程序执行效率。此外，本文研制了一个采用该技术的通用执行引擎框架，并使用该框架实现了XQuery语言。实验结果表明，采用本文所给出的即时编译技术可以加快XQuery程序的执行速度。

1 基础概念

1.1 SECD抽象机

SECD抽象机［3］是一种经典的操作语义，可以用于λ表达式的求值，经常用在程序设计语言的验证与实现中。SECD 抽象机本身由操作数栈 （stack，简记为ss）、环境（environment，简记 为se）、代 码 序 列 （control，简 记 为sc）、转储区 （dump，简记为sd）4 部分组成，ss、se、sd的初始状态均为空，sc则保存着将被抽象机执行的SECD指令。在执行SECD 指令的过程中，中间结果保存在ss中等待后续使用，局部变量保存在se中，sd 则保存着函数调用的相关信息，用于函数调用现场的保护与恢复。表1给出了一个SECD 指令集实例。

表1 SECD 抽象机常用指令集

1.2 Java虚拟机与Java栈帧

Java虚拟机 （Java virtual machine，JVM）是Java程序运行的基础，Java程序源代码经过编译之后得到Java字节码，JVM 解释执行字节码指令。另外，现代JVM 常用即时编译技术来加快程序的执行速度。

栈帧 （stack frame）［4］则是JVM 进行方法调用和方法执行的数据结构，每当JVM 执行一个方法时，会创建一个栈帧并将其压入到JVM 的Java虚拟机栈中，方法执行完毕后该栈帧将被弹出。栈帧中保存一个Java方法的局部变量区、操作数栈、方法返回地址等信息。一个方法在运行过程中，将根据字节码指令从栈帧局部变量区或是其它JVM 组件中读取数据并将其压入到栈帧中的操作数栈，在栈上计算出结果后，再将结果弹栈、写入局部变量区或是将其作为方法调用结果返回。

1.3 基于踪迹的即时编译

下面给出基于踪迹的即时编译中的一些基本概念：

标签：划分基本块的标志，是基本块的入口，用于标记分支。

锚点：是踪迹的入口，是一种特殊的标签。

踪迹：是一条可跨越函数边界的指令序列，由锚点、标签和子踪迹组成，热点踪迹则是指执行频率超过预设阈值、需要进行即时编译的踪迹，下文将简称作 “热踪”。

踪迹树：以一个踪迹作为主干，多个踪迹为分支所组成的树，用于表示较复杂的程序结构。

一般来讲，基于踪迹的即时编译主要分为识别锚点、记录踪迹、代码生成和执行4个阶段。当识别出一个锚点后，执行引擎在继续执行程序的同时，将从该锚点开始记录正在执行的指令，再次遇到该锚点则结束记录操作，此时即得到一个完整的踪迹。每个踪迹的执行次数将被记录，执行次数超过预设阈值的踪迹被识别为热踪，并进一步编译为目标代码。当执行引擎再次执行热踪时则执行目标代码。

以表2所给出的程序为例，该程序的控制流如图1 （a）所示，假定识别热踪的阈值为200，根据基于踪迹的热点探测算法，该程序在运行过程中，基本块2→3→4→6所组成的循环将被识别为热踪并被编译成目标代码，当获得目标代码后、再次执行2→3→4→6时，该循环所对应的目标代码将被执行，执行结束后再切换到解释执行，执行后续代码。

表2 示例程序

图1 示例程序控制流图及其热踪

2 针对SECD抽象机的基于踪迹的即时编译技术

2.1 基本过程

在读取用户编写的程序代码之后，首先将源代码翻译成等价的SECD 指令序列，并且指令序列中的循环头部设置为锚点。在解释执行指令序列的过程中，进行如下操作：

（1）记录踪迹：当执行引擎遇到一个锚点，则创建一个踪迹并将之后执行的每条指令记录到这个踪迹中，直至再次遇到这个锚点。如果在记录过程中遇到新的锚点，则将正在记录的踪迹暂存起来，开始新的踪迹的记录，而这条新的踪迹可以作为子踪迹与之前暂存的踪迹进行合并。一个踪迹记录的是一个程序某次执行的路径，而之后该程序的执行可能会与这条路径不同。因此，在记录踪迹的过程中，如果程序中出现分支，则在踪迹中加入一条GUARD 指令，用于代替没有被执行的程序分支。此外，记录每个踪迹的运行次数，当运行次数超过阈值时则将其视为热踪，将其提交给即时编译器。

（2）代码生成：即时编译器将热踪编译成Java字节码，并以回填的方式在字节码中生成用于切换执行方式的代码，包括调用代码序列、返回代码序列两部分。调用代码序列为JVM 栈帧中的操作数栈分配空间、向栈帧中填写信息；返回代码序列则用于恢复SECD 抽象机的机器状态，保证编译执行结束后SECD 执行引擎能继续往下执行。更详细说明参见2.3.3。

（3）执行：在热踪被编译成Java 字节码之后，当SECD 执行引擎再次执行到热踪时则切换到编译执行，调用Java字节码，字节码执行结束后则切换回解释执行，继续执行后续代码。

2.2 SECD指令翻译

根据设计目的的不同，SECD 抽象机的指令集可以有不同的实现，而本文采用表1中给出的指令集作为文章中提到的SECD 抽象机的指令集，则表2所给出的源程序对应的SECD 指令序列见表3。

表3 示例程序SECD 指令序列

2.3 即时编译

2.3.1 记录踪迹

根据起始位置的不同，踪迹可分为方法踪迹 （method trace）、循环踪迹 （loop trace）两种［5］。方法踪迹的锚点位于某个方法的入口，而循环踪迹的锚点则位于某个循环结构的开始位置。本技术在探测热踪时，主要探测循环踪迹，当执行引擎解释执行SECD 指令序列时，如果碰到一个循环，则对该循环计数，当超过预设阈值时则将循环体中常用部分提取出来，作为一个循环踪迹，提交给即时编译器编译成Java字节码。例如，在执行表3中SECD 指令序列时，从标签f1＿loop开始到JMP f1＿loop指令这段SECD指令序列是对应于表2中的for循环，当这段指令序列执行次数超过阈值时，将被视为热踪提取出来，见表4。

假设正在被执行引擎执行的程序中包含有两个分支pa和pb，只有pb分支被记录到一个热踪中，但在该热踪的目标代码的某次执行时，却需要执行pa分支，这种现象被称作旁路退出 （side exit）。当旁路退出发生时，需要从编译执行切换到解释执行。为此，在记录一个踪迹时需要向踪迹中插入GUARD 指令，用于标记可能发生旁路退出的位置。在代码生成阶段将根据GUARD 指令生成用于切换执行环境的Java字节码。以图1 （a）为例，基本块3中包含有两个分支，路径3→5→6并没有被记录到图1 （b）所给出的踪迹中，因此在这个踪迹中加入一个GUARD 指令。

表4 示例程序热踪及其字节码

2.3.2 代码生成

SECD 抽象机和JVM 都是基于栈的虚拟机，组成SECD抽象机的每个部分都可以在JVM 中找到功能相似的部分：SECD 操作数栈对应于JVM 栈帧的操作数栈 （简记为fs），SECD 环境对应于栈帧局部变量区 （简记为fe），SECD 指令序列对应于Java字节码，而SECD 转储区则对应于Java虚拟机栈 （简记为fd）。同时，大部分SECD 指令都可以找到功能相同的JVM 指令，因而在将热踪翻译成Java字节码时按照对应关系逐条翻译SECD 指令即可。对于没有对应的JVM 指令的SECD 指令，则可以根据这条SECD 指令的语义，生成一个等价的Java方法，在字节码文件中对应位置加入调用该方法的指令。表4给出了一个热踪翻译成字节码的实例，为方便阐述，将翻译热踪所得的字节码记作bcode。

另一方面，解释执行的运行时环境主要包括SECD 抽象机的ss、se和sd，而编译执行的运行时环境则是JVM 中的fs、fe、fd 以及Java堆等组件。不同执行方式下运行时数据保存在不同的位置。要保证热踪对应的字节码在JVM 中能正确地执行，就必须在字节码执行前，将SECD抽象机中的部分数据写入到JVM 中相应位置；当发生旁路退出、需要切回到解释执行时，也需要将执行字节码所得的中间结果回写到解释运行时环境中。本文将这些操作统称为环境切换，具体过程参见2.3.3。

此外，为了生成将se中的变量写入到fe 或是利用fe更新se 的代码，还需要保存热踪中各个变量在se、fe中存储位置的映射关系。为此，在代码生成过程中，需要维护一张映射表 （以下记作varMap），每当在热踪中遇到对se中的变量进行读、写操作的指令时，则将该变量位置以及fe对应变量的位置保存到该映射表中。

2.3.3 环境切换

在将热踪翻译成字节码之后，为了进行环境切换，需要在bcode 的开始位置生成调用代码序列，在bcode 中GUARD 指令对应的位置生成返回代码序列。

调用代码序列为fs分配空间，将即时编译所需的ss内部分元素按照顺序压入fs内，并根据varMap 将se 内相关变量写入fe，为此需要先计算fs需要分配多大空间。这一计算在生成bcode之后进行，通过统计热踪中每条分支的所有指令对ss的压栈、弹栈次数，可得出整个热踪所需的fs的空间大小 （记作stackNum），具体算法参见表5。假设热踪中指令条数为n，算法至多对所有指令遍历一遍，因此算法时间复杂度为O（n），空间复杂度为O（n）。计算出stack－Num 后，根据stackNum 和varMap，即可在已有的字节码中回填调用代码序列。

环境切换大体流程如图2 所示，切换为编译执行后，首先执行调用代码序列，fs、fe 将会准备好必要的数据（fs中压入val0、val1，fe中存入val0、val1），热踪对应的字节码就可以正确地执行；当字节码执行完毕后，fs、fe保存着热踪的执行结果 （fs中的val2、val3，fe中新的变量值val0’、val1’），执行返回代码序列后这些执行结果将被回写到SECD 抽象机中，执行引擎继续解释执行后续代码。

图2 环境切换中各部件的变化

表5 计算栈帧操作数栈容量的算法

返回代码序列则用于将fs内的数据按照顺序全部压入ss，根据varMap 将fe 数据写入se 对应位置。如果在热踪中有自定义函数调用且调用自定义函数时执行了没有包含在热踪中的代码，还需要向sd 中写入函数调用信息，用于恢复SECD 抽象机的状态。

完成上述工作后，最终用于即时编译的Java字节码见表6 （限于篇幅，仅给出了大体框架）。

表6 示例程序的Java字节码

当热踪中包含自定义函数部分代码时，环境切换会更复杂。例如，图3 （a）表示在运行时刻，foo2函数中提取出traceFunc作为热踪、进行了即时编译，该热踪又调用了自定义函数foo3，而foo3 中仅有一条分支被记录到热踪中。如果在某次编译执行foo3函数时发生旁路退出，则需中止即时编译、沿图3 （a）中虚线所示路径返回到SECD执行引擎，从foo3中GUARD 指令对应位置继续解释执行后续代码。由于foo3、traceFunc 还没有执行完，必须在foo3中GUARD 指令所在位置添加返回代码序列，进行如下操作：

将foo3函数所对应的fs、fe中的数据、foo3的返回地址保存在一个变量中，并将该变量压入sd 中；

终止foo3的运行，并返回一个特定标记值G，以便和正常的函数调用过程相区分；

图3 对包含自定义函数的热踪的处理

在traceFunc调用foo3的位置加入对foo3返回值的判断，如果返回值为G 则同样将traceFunc函数对应的fs、fe、traceFunc的返回地址保存在一个变量中，并将该变量压入sd，终止traceFunc的运行，返回标记值G （如果热踪中包含多个自定义函数的嵌套调用，则可能需要重复这一过程，直至返回到SECD 解释执行引擎）。

当即时编译结束后，SECD 解释执行引擎读取编译执行的结果，如果是G 则说明调用自定义函数时发生了旁路退出，此时将sd 内部分元素逆序 （保证与函数调用顺序一致），然后读取sd 栈顶元素用来更新当前SECD 抽象机中的ss、se和指令PC，恢复现场，然后继续解释执行即可，如图3 （b）所示。

对于递归函数调用，目前本技术所采用的热点探测策略将任何递归函数都视为热点，因而递归函数的定义将被包含在热踪中并被翻译成字节码，编译执行时调用递归函数只需将参数传递给该函数即可，不需要进行环境切换。

2.4 通用执行引擎框架

基于踪迹的即时编译通用执行引擎框架的基本结构如图4所示，该框架主要由以下4部分组成：

SECD 翻译器：将源程序翻译成语义等价的SECD 指令序列；

内建函数库：保存库函数，需要根据要实现的语言而变化；

SECD 执行引擎：执行SECD 指令序列，实现SECD 指令的即时编译，并将计算结果返回；

JVM：执行Java字节码。

图4 通用执行引擎框架

任何编程语言，只要能够将该语言翻译为SECD 指令序列，都可以利用该框架来实现这种语言的执行引擎。

3 实 验

本文实现了2.4中提到的通用执行引擎框架，并利用该框架实现了一个XQuery［6］执行引擎。实验环境如下：Intel Xeon CPU E5－1607 3GHz，8G 内 存，Ubuntu 12.04 LTS，JDK 1.6update 27。

实验中分别在解释执行、函数级即时编译、基于踪迹的即时编译3种执行方式下对13个测试用例进行了测试，其中10 个用例来自于W3C XML Query Use Cases，Q1、Q2、Q3参见表7。实验结果如图5所示，需要说明的，函数级即时编译、基于踪迹的即时编译的运行时间包括了在运行时编译目标代码的时间。

在所有测试用例中，基于踪迹的即时编译对解释执行的加速比平均可以达到1.11，最好情况下可以达到1.43。在这些用例中，1.2.4.6、Q1、Q2、Q3包含有多重循环或是多次被调用的自定义函数，导致这些用例中的大部分代码被识别为热踪并编译执行，因而可以获得比较好的性能提升。其它用例则只包含单重循环，识别出的热踪运行次数相对较少，不足以带来明显的性能提升。在增大输入文件，使得XQuery查询的执行次数增加后，加速比变化如图6所示。显然，随着XQuery查询的执行次数增加，基于踪迹的即时编译所带来的加速效果也会变得更明显。

表7 测试用例

另一方面，所有测试用例中，仅1.2.4.6、Q2、Q3中包含有自定义函数。而为了保证实验条件相同，实验中所采用的函数级即时编译并没有引入现代虚拟机中的栈上替换等优化技术，使得函数级即时编译只会对程序中多次执行的自定义函数进行编译。因此，对于不包含自定义函数的测试用例，由于探测热点所带来的开销，函数级即时编译的运行速度略微慢于解释执行。而对于包含自定义函数的用例 （1.2.4.6、Q2、Q3），函数级编译执行要快于解释执行，但仍比基于踪迹的即时编译执行要慢。这是由于在1.2.4.6、Q2、Q3中自定义函数调用出现在循环中，而热踪会将整个循环编译，在函数级编译中被编译的代码必然包含在热踪中。在这些例子中，热踪的编译不但可以减少自定义函数本身的执行时间，而且可以减少他们的调用开销和外围循环执行时间。

图5 运行时间比较

图6 不同输入规模下的加速比变化

4 相关工作

4.1 基于踪迹的即时编译

Dynamo［7］是第一个实现了基于踪迹的即时编译的编译器，它在运行时使用循环体的头部来标识一个踪迹，并没有创建实际循环踪迹。而本技术中同样采用循环体头部来标识踪迹，省却了基于踪迹的即时编译一般处理流程中的分析阶段。

DynamoRIO 发展了Dynamo，它是一个包含了踪迹和部分求值的解释框架，但是DynamoRIO 的踪迹仍然在机器码层面，没有包含解释器层面的高级信息。这使得踪迹的探测需要增加大量的额外标注，一些编译优化也无法在这个层面上进行。

Gal A等人开发了第一个高性能的基于踪迹的即时编译器HotpathVM，该虚拟机动态探测频繁运行的字节码，将其翻译为SSA （static single assignment）作 为 中 间 表 示，之 后SSA将被编译为机器码。本技术中程序以SECD 指令作为中间代码，找到热踪后将会把热踪翻译成Java字节码并执行。

Hubl C等人基于HotSpot，开发了不跨越函数的基于踪迹的热点探测器，该解决方案由于不跨越函数，踪迹都很短小，节约了探测和编译的时间，但无法进行全局优化。

此外，基于踪迹的即时编译技术还被广泛应用于其它项目中，如Python语言的实现PyPy［8］，Mozilla的Trace－Monkey［9］，微 软 公 司 的SPUR［10］项 目，Android 的Dalvik虚拟机［11，12］等。

4.2 XQuery相关实现

目前XQuery执行引擎多数以解释方式执行XQuery查询。Axyana Software开发的Qizx／Open是一个开源的使用Java实现的XML查询解释器。Galax是一个轻量级可移植的XQuery的开源实现，已成为研究各种XQuery优化方法的实验平台。

另一方面，为了提高XQuery执行效率，不少研究人员已展开编译实现XQuery语言的研究。Qexo是GNU 实现的XQuery执行引擎，它部分实现了XQuery 语言。Qexo采用编译实现的方式，将XQuery源程序编译为可执行的Java字节码，并加载到JVM 中执行。但Qexo侧重于从编程语言角度实现XQuery，与XML 相关的优化策略应用较少。XQC编译系统［13］则将XQuery程序全部翻译成Java字节码，但如果XQuery程序中大部分代码执行频度较低，编译时间较长，可能执行效率反而不及直接解释执行，并且XQC并不支持树模式查询。而XQuery Hotspot编译系统［14］则采用HotSpot的热点探测策略，同样不支持树模式，并且没有充分利用JVM 中已有的栈、堆等结构。

5 结束语

本文讨论了一种针对SECD 抽象机的基于踪迹的即时编译技术，该技术将编程语言翻译成SECD 指令序列，以解释方式执行SECD 指令序列，将程序中执行频率高的踪迹翻译成Java字节码，进行即时编译。实验结果表明，利用该技术可以提升程序的运行速度。

目前本文中已给出的SECD 指令集并不支持高阶函数，因而还不能对包含有高阶函数特性的编程语言进行即时编译，并且翻译目标代码的过程中还可以利用函数内联、逃逸分析等技术对目标代码进行优化。

［1］ZHOU Zhiming.Understanding Java virtual machine ［M］.Beijing：China Machine Press，2011：287 （in Chinese）. ［周志明.深入理解Java虚拟机 ［M］.北京：机械工业出版社，2011：287.］

［2］Bebenita M，Chang M，Wagner G，et al.Trace－based compilation in execution environments without interpreters ［C］／／Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java.ACM，2010：59－68.

［3］Narita K，Nishizaki S Y，Mizuno T.A simple abstract machine for functional first－class continuations ［C］／／International Symposium on Communications and Information Technologies.IEEE，2010：111－114.

［4］Lindholm T，Yellin F，Bracha G，et al.The Java virtual machine specification ［M］.Addison Wesley，2013：17.

［5］Hubl C，Mssenbck H.Trace－based compilation for the Java HotSpot virtual machine［C］／／Proceedings of the 9th International Conference on Principles and Practice of Programming in Java.ACM，2011：129－138.

［6］W3CXML query working group，XQuery 1.0：An XML query language［EB／OL］.［2010－12－14］.http：／／www.w3.org／TR／2010／REC－xquery－20101214／.

［7］Hayashizaki H，Wu P，Inoue H，et al.Improving the performance of trace－based systems by false loop filtering ［J］.ACM SIGPLAN Notices，2012，47 （4）：405－418.

［8］Bolz F C，Cuni A，Fijalkowski M，et al.Tracing the metalevel：PyPy’s tracing JIT compiler［C］／／Proceedings of the 4th Workshop on the Implementation，Compilation，Optimization of Object－Oriented Languages and Programming Systems.ACM，2009：18－25.

［9］Gal A，Eich B，Shaver M，et al.Trace－based just－in－time type specialization for dynamic languages［J］.ACM SIGPLAN Notices，2009，44 （6）：465－478.

［10］Bebenita M，Brandner F，Fahndrich M，et al.SPUR：A trace－based JIT compiler for CIL ［J］.ACM SIGPLAN Notices，2010，45 （10）：708－725.

［11］Perez G A，Kao C M，Chung Y C，et al.A hybrid just－intime compiler for android：Comparing JIT types and the result of cooperation ［C］／／Proceedings of the International Conference on Compilers，Architectures and Synthesis for Embedded Systems.ACM，2012：41－50.

［12］Cheng B，Buzbee B.A JIT compiler for Android’s Dalvik VM［C］／／Google I／O Developer Conference，2010.

［13］Yuan F，Chen Y，Liao H.XQC：A compiler for XQuery［C］／／International Conference on Computer Science and Software Engineering.IEEE，2008：360－363.

［14］ZHANG Kailian，LIAO Husheng，SU Hang.Supporting framework of hotspot compiler system for XQuery ［J］.Computer Engineering，2011，37 （24）：28－31 （in Chinese）.［张开练，廖湖声，苏航.XQuery语言HotSpot编译系统的支撑框架 ［J］.计算机工程，2011，37 （24）：28－31.］