DRLVM Jitrino即时编译器

参见: http://harmony.apache.org/subcomponents/drlvm/JIT.html

修订历史

1. 关于本文档

2. 概览

3. Jitrino.OPT

4. Jitrino.JET

5. 实用程序

6. 公共接口

7. 参考文献

修订历史

版本

版本信息

日期

初版

Intel, Nadya Morozova: 创建文档.

2006年6月5日

1. 关于本文档

1.1. 目的

本文档描述了Jitrino即时编译器的内部结构,该组件是作为动态运行时层(Dynamic Runtime Layer, DRL)计划的一部分部署在虚拟机中。本文探讨即时编译器的内部结构设计和它与DRLVM其他组件的交互。通过本文档,读者可以了解即时编译器的具体实现细节。至于JIT在整个虚拟机设计中的作用和VM层的需求等一般的信息超出本文的讨论范围,这些内容参阅虚拟机源代码包中提供的DRLVM开发者指南

1.2. 面向的读者

本文面向的读者是对代码编译算法特别感兴趣的DRLVM开发者。文中的信息对DRL编译技术的进一步开发会有帮助,可以为那些从头开始实现JIT编译器的人提供范例。本文假设读者了解即时编译和优化算法等概念。

1.3. 文档使用

对DRLVM即时编译器从如下主要部分进行描述:

1.4. 约定和符号

本文使用对DRL文档包的统一约定

回到顶部

2. 概览

Jitrino是当前DRLVM所带有的即时(JIT)编译器[2]的代号。JItrino由两个不同的JIT编译器组成,它们共享源码并打包成一个库:

本文档描述了两种编译器和它们的操作。所有关于Jitrino的不含特定副标题(JET或OPT)的引用等同于对这两种编译器的引用。

回到顶部

2.1. 主要特点

JIT编译器的主要特点如下:

Jitrino.OPT还有如下特有的特点:

回到顶部

2.2. 关于编译处理过程

Jitrino编译器提供一些方法来编译和优化分发到Java*运行时环境的代码并使之适应不同的硬件体系结构。图1显示了编译器的结构和它们与虚拟机之间的交互。

Jitrino.JET和Jitrino.OPT编译器都有一个平台无关的前端和一个平台相关的后端。编译将它们连接起来并将前端从原始字节码中提取的类型信息传播到特定平台的后端。要想支持新的硬件平台就需要实现一个新的平台相关的后端。

Jitrino可以遵循不同的代码编译策略。编译过程的优化可以是为了获得最短的编译时间、为了获得最好的性能,还可以是可接受的编译时间和合理的性能的折中。编译过程可以包含Jitrino.JET基线编译器、Jitrino.OPT优化编译器或包含这两者。在很多应用中,只有很少的方法消耗了运行时的大部分时间,所以当Jitrino积极地优化这些方法时,还是能提高总体性能的。执行管理器(EM)定义实际的编译策略。

Jitrino.JET基线编译器通过将Java*字节码直接翻译成本地代码而提供最快的编译时间。此编译器执行的是快而简单的编译,几乎没有应用优化。

Jitrino.OPT— 重要的Jitrino编译引擎,它以牺牲较多的编译时间为代价,提供最优化的本地码。JItrino.OPT的编译过程也在图1中显示,重点集中在下列各项:

Jitrino的体系结构是模块化的,这使得实现更多的前端变得容易,比如公共语言基础(CLI)的字节码前端。

本文档描述了Jitrino.JET和Jitrino.OPT编译器的内部结构和运行在它们内部的处理过程。

http://harmony.apache.org/subcomponents/drlvm/images/compilation_process.gif

图 1. Jitrino编译器体系结构

回到顶部

3. Jitrino.OPT

3.1. 体系结构

本节描述了优化编译器Jitrino.OPT的内部结构。

3.1.1. 流水线管理框架

流水线管理框架(pipeline management framework,PMF)定义了编译过程在Jitrino.OPT内部是如何执行的。在PMF下,编译过程表示成一条流水线(pipeline),它是步骤的线性序列。每个步骤存储对一个操作对象的引用、所需的参数和其他相关信息。操作(Actions)表示独立的代码变换,比如优化遍(pass)。流水线中不同的步骤可以引用相同的操作,例如,多次运行同样的变换。各流水线的步骤序列可以不同。

为了选择编译一个给定的Java*方法的流水线,系统使用由类名、方法名以及方法标记构成的方法过滤器作为选择标准。每一个JIT实例有一个公共的流水线,该公共流水线带有一个接受所有方法编译请求的空方法过滤器。除此之外,可以创建带有唯一且非空的过滤表达式的可选流水线来编译特定的Java*方法集。

Jitrino.OPT中的流水线用VM属性机制进行配置。PMF分析属性、构造流水线并向操作传递参数。因为OPT编译器没有“硬编码”(hard-coded)流水线,因此你需要在EM配置文件中或通过VM属性配置流水线。要使用Jitrino命令行接口和有效地运用Jitrino日志记录系统,需要理解流水线的配置规则。关于PMF内部的细节,参阅PMF详细描述

回到顶部

3.1.2. 逻辑组件

本节定义编译器的主要部件。这仅是和主要编译阶段相匹配的抽象的、逻辑上的划分。每个逻辑组件包括在编译流水线中连续使用的操作。

翻译器


优化器


代码生成器


回到顶部

3.1.3. 中间表示

中间表示是正被编译的代码的内部编译器表示。Jitrino.JET没有代码的中间表示,它直接把字节码编译成本地代码。Jitrino.OPT使用两种IR形式:高级中间表示(high-level intermediate representation ,HIR)和低级中间表示(low-level intermediate representation ,LIR)。为了编译一个方法的代码,Jitrino.OPT编译器把Java*字节码翻译成一个带有节点、边和指令的基于图的结构。图中的节点和边表示程序的控制流。图中每一个节点包含表示简单操作的指令。

http://harmony.apache.org/subcomponents/drlvm/images/HIR.png

http://harmony.apache.org/subcomponents/drlvm/images/LIR.png

高级IR


低级IR


回到顶部

3.2. 处理过程

本节描述在Jitrino优化编译器内部进行的主要处理过程。

3.2.1. 字节码翻译

初始的编译步骤是将字节码翻译成HIR,它包括以下两个阶段:

3.2.2. 高级优化

高级优化是优化器执行的平台无关的变换。优化器应用一套能平衡优化效果和编译时间的经典的面向对象优化。每一个高级优化表示成一个HIR上的独立变换遍。每个Jitrino.OPT优化有如下的一个或多个目标:

优化模式


作用域增强遍(Scope Enhancement Passes) 


冗余消除遍(Redundancy Elimination Passes )


HIR简化遍(HIR Simplification Passes)


静态profile估计器(Static profile estimator,statprof)


回到顶部

3.2.3. 代码选择

在优化遍之后,HIR被翻译成LIR。代码选择(CS)是基于被编译的方法的HIR层次结构的,如图2.所示。

http://harmony.apache.org/subcomponents/drlvm/images/code_selector.gif

图 2. 代码选择器框架

对于方法、多重定义的操作数集合、控制流图和CFG基本块节点的集合,代码选择器框架定义如下:

因此,CS框架在优化器和可插拔的代码生成器之间建立了一个良定义的边界。同样,代码选择器框架也提供对IR变换的结构化方法,这样CG能在不同层次上重写它。

图3.显示了代码选择的过程,其中循环用黄色突出显示。

http://harmony.apache.org/subcomponents/drlvm/images/code_selection_seq.gif

图 3. 代码选择顺序图

图3说明了变换过程的具体过程,分析如下:

回到顶部

3.2.4. 代码生成

代码生成过程特定于实现它的可插拔代码生成器。本节简要介绍Jitrino IA-32/Intel? 64代码生成器的当前实现,以及为确保它是线程安全的所做的度量

为了为一个方法生成代码,代码生成器需要做大量工作,其执行步骤粗略地分成以下阶段:

LIR创建


LIR变换


代码和数据发射(Code and Data Emission)


全局锁


回到顶部

4. Jitrino.JET

4.1. 体系结构

Jitrino.JET基线编译器是Jitrino的子组件,用于将Java*字节码几乎不带优化地翻译成本地代码。这个编译器通过组合本地栈和寄存器来仿真基于栈的机器操作。

4.1.1. 运行时支持

在代码生成阶段,方法的操作数栈的状态是拟态的。这种状态有助于计算GC映射图,它用于以后运行时支持GC操作。

GC映射图表明局部变量或栈槽上是否包含一个对象。每当定义对一个局部槽的操作时,局部变量的GC映射图都要进行更新,如下所示:

栈的GC映射图只有在GC点进行更新,也就是在一条可能导致GC事件的指令之前,比如,一个VM helper调用。在方法编译期间计算出来的栈的深度和状态在调用前得到保存:通过生成代码来保存状态。状态保存到方法的本地栈中预先分配的特定区域。这些区域包括GC信息,也即操作数栈的深度、栈的GC映射图、局部变量的GC映射图。

此外,Jitrino.JET为每个方法在编译期间准备和存储一个特定的结构:方法信息块。这些结构以后用来支持运行时操作,比如栈展开、字节码和本地代码之间的映射。

回到顶部

4.2. 处理过程

4.2.1. 基线编译

基线编译是带有极小优化的编译代码过程。Jitrino.JET的子组件按如下描述执行操作:

Jitrino.JET在字节码上执行两遍,如图4所示。第一遍建立基本块边界,第二遍生成本地代码。

http://harmony.apache.org/subcomponents/drlvm/images/bytecode_to_native.gif

图 4. 基线编译路径

下面是对这两遍的描述。

第一遍


在一个方法的字节码上执行第一遍时,编译器得到基本块的边界和它们的引用计数。

这里的引用计数是指到达一个基本块(BB)的路径数。

为了得到基本块的边界,Jitrino.JET对字节码进行一次线形扫描并用如下规则来分析指令:

在第一遍中,编译器还为每个块算出引用计数。

图5是一个关于引用计数的例子。第二个基本块(BB2)的引用计数ref_count=1,因为它只能由第一个基本块(BB1)到达。第三个基本块的引用计数是2,因为它既可以作为BB1的分支目标到达也可以从BB2直接到达。

http://harmony.apache.org/subcomponents/drlvm/images/reference_count.gif

图 5. 基本块的引用计数

Jitrino.JET在代码生成期间利用引用计数来减少转存数量。

第二遍


在第二遍执行中,Jitrino.JET完成代码生成,如下所示:

关于基线编译的实现细节,参阅用Doxygen从源码生成的文档。

回到顶部

5. 实用程序

JIT编译器依赖于下面的实用程序:

JIT编译器的实用程序和VM的实用程序类似,但并不完全相同。例如,JIT编译器和虚拟机内核使用不同的日志记录程序。

回到顶部

5.1. 内存管理器

在Jitrino.OPT编译器中,使用常规的内存管理器例程进行内存分配。这种机制保证在编译过程中分配的所有内存在编译结束后被释放。此外,内存管理器通过使用快速的线程局部内存分配算法来减少系统调用的次数。重载内存分配的内存管理器代码和操作在jitrino/src/shared/directory中的.h.cpp文件里。

要开始使用内存管理器,一个JIT编译器的开发者必须创建一个内存管理器实例,它能提供初始堆大小和用于记录日志的名字。

内存管理器从操作系统那在叫做arenas的大块中分配内存。在MemoryManager中,一个arena块的最小大小是4096个字节。当JIT编译器要为一个对象分配内存时,从当前arena块分配内存而无需系统调用。如果当前arena没有足够的空闲空间,内存管理器就从另外一个arena进行分配。

下面是一个使用MemoryManager类的典型模式。

用内存管理器分配的内存在它的析构函数中释放,而用内存管理器分配的对象却不调用析构函数。内存管理器的这一特点要求JIT编译器代码中满足下列规则:

Jitrino.OPT有两个专用的内存管理器:

使用MemoryManager,你可能无法得到关于内存破坏的系统通知。 例子

当一个值被存到超过下标范围的数组元素中时,可能发生内存破坏:

这段代码可以成功地执行是因为内存管理器分配的默认内存块的大小比数组大小要大。

为了能够检测到内存破坏错误,在MemoryManager.cpp文件中定义了宏JIT_MEM_CHECK。在这个宏定义之后,内存管理器为所有的arena空间填写预定义的值并在对象之间添加填充空间。每次分配一个对象时,内存管理器都检查arena中的这些预定义的值。如果在限制区域内执行了写操作,内存管理器就会报错。

回到顶部

5.2. 计数器和计时器

Jitrino维护计数器(counters)来收集统计数据。计数器可以用于任一Jitrino操作中,在整个VM执行期间,对所有流水线中的一个特定的事件进行计数。每个计数器都有一个名字以区别于其他计数器。

要计算一个Jitrino操作的总执行时间,Jitrino也提供了计时器(timers),它是计数器的一个特殊形式。要激活计数器和时间度量,可使用下面的命令语法。

每一操作的所有实例的执行时间被单独进行测量,在VM停止运转时进行汇总。操作执行时间的结果数据都被写到一个表格中并按操作名进行分类。

回到顶部

5.3. 日志记录系统

Jitrino的日志记录系统做如下工作:

日志记录系统是Jitrino PMF的一个主要的部分。日志记录由两个接口组成:

日志记录系统是基于的。每个流都有一个名字用来在程序和命令行选项中对它寻址。Jitrino为几个经常使用的流提供预定义的名字。下面的这些流启用时能够产生特定的输出:

名字

输出

info

编译协议:JIT和流水线名字,方法名和数量等

rt

与编译方法无关的运行时输出

ct

编译时诊断

irdump

转储对一个已编译方法的内部Jitrino结构

dotdump

用.dot格式转储内部Jitrino结构

dbg

调试信息

日志记录命令的通用语法遵循下面的PMF规则:

在这个命令语法中,<path>代表被启用的流的Jitrino操作集。当不指定具体路径时,这个命令可以应用到所有现存的操作中。

为了使所有JIT的所有流水线能启用编译协议,键入:

为了转储编译时的诊断信息和IR 转储,键入:

5.3.1. 控制流图可视化

要调试JIT,需要为编译的方法提供编译阶段间的控制流图的修改信息,包括指令和操作数。Jitrino编译器能够生成表示两个IR级的控制流图的dot文件。.dot文件能被转换成描述性的图,就是CFG的图形表示,见3.1.3节中间表示中的用图形来可视化代码的例子。对于.dot文件的转换有各种各样的图形可视化工具可用,比如Graphviz[6]。

用下面的命令能够转储 .dot文件

关于Jitrino日志记录系统的更多细节,参阅PMF描述中的相应部分。

回到顶部

5.4. 控制流图

高级和低级中间表示用一个统一的基本结构来表示一个编译的方法的逻辑结构,就是控制流图(CFG)。这种统一使得Jitrino可以避免其内部中的代码复制,减少代码大小和改进所生成的代码质量。

当前的CFG实现在jitrino/src/shared/ControlFlowGraph .h.cpp文件中。这些文件包含CFG的核心结构和算法,并且能被直接重用和扩展自定义的功能。

控制流图实现的目标是提供下列各项:

控制流图支持两类控制流:

因为IR可以表示异常控制流,优化器和代码生成器考虑这点来对异常和异常处理程序进行优化。在控制流图中,对异常控制流的显式建模使得编译器可以跨越多个抛出-捕获边界进行优化。对于局部处理的异常,编译器可以用代价更低的直接分支来代替代价高的抛出-捕获组合。

5.4.1. 控制流图结构

CFG的结构有节点、边和指令,分别用NodeEdgeCFGInst类表示。

子类化


节点



指令


5.4.2. 图算法

当前的CFG实现提供如下的图算法:

对于每个算法的细节,参阅用DoxygenControlFlowGraph.h文件生成的文档。

5.4.3. 支配树

一个支配树表示为一个控制流图计算的(被)支配信息。该树能用来查询或操纵节点间的支配关系。树根是图中进入或退出节点的DominatorNode。除了根节点,任何支配者节点的双亲就是直接支配者或被支配者。

支配树的源文件是jitrino/src/shared/DominatorTree.h.cpp

当基本的CFG被修改后,支配树就无效了。虽然仍可以查询和操纵支配树,但支配树可能不再反映控制流图的当前状态。

5.4.4. 循环树

一个循环树包含控制流图中的循环信息。它用来查询控制流图中的每个节点的循环信息。循环树用 LoopTreeLoopNode 类来表示。每个 LoopNode 类实例在图中都有一个关联的节点且代表一个循环的开头。 LoopNode 的所有孩子节点都是嵌套循环的循环开始节点。循环树的根节点是一个人为的节点用来连接方法的顶层循环和它的孩子节点。

循环树的源文件在jitrino/src/shared/LoopTree.h.cpp文件中

当基本的CFG改变时,循环树是无效的。在CFG修改后,你就不能操纵循环树。

回到顶部

6. 公共接口

本节描述JIT编译器输出的、用于和其他组件交互的接口。Jitrino公开所有必要的接口并作为运行时环境的一部分工作。Jitrino显式地支持精确的移动垃圾收集器,它要求JIT能枚举出活引用。

6.1. JIT_VM接口

这个接口包括JIT编译器输出的、用于和虚拟机内核组件进行交互的函数。在JIT_VM接口内部的函数分成如下几类:

字节码编译


根集枚举


栈展开


JVMTI支持


6.2. JIT_EM接口

JIT编译器输出这个接口来支持执行管理器。这些函数集负责如下操作:

关于执行管理器输出的、用于与JIT编译器交互的出口,参见执行管理器描述中的公共接口部分。

关于JIT输出给EM的函数细节,参阅用Doxygeninclude/open/ee_em_intf.h生成的文档。

回到顶部

7. 参考文献

[1] Java* Virtual Machine Specification, http://java.sun.com/docs/books/vmspec/2nd-edition/html/VMSpecTOC.doc.html

[2] JIT Compiler Interface Specification, Sun Microsystems, http://java.sun.com/docs/jit_interface.html

[3] S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, San Francisco, CA, 1997.

[4] P. Briggs, K.D., Cooper and L.T. Simpson, Value Numbering. Software-Practice and Experience, vol. 27(6), June 1997, http://www.informatik.uni-trier.de/~ley/db/journals/spe/spe27.html

[5] R. Bodik, R. Gupta, and V. Sarkar, ABCD: Eliminating Array-Bounds Checks on Demand, in proceedings of the SIGPLAN ’00 Conference on Program Language Design and Implementation, Vancouver, Canada, June 2000, http://portal.acm.org/citation.cfm?id=349342&dl=acm&coll=&CFID=15151515&CFTOKEN=6184618

[6] Graphviz, Graph Visualization Software, http://www.graphviz.org/

回到顶部

* Other brands and names are the property of their respective owners.

Contributors:

DRLVM_Jitrino即时编译器 (last edited 2009-09-20 21:55:22 by localhost)