理解tracing JIT

本文是基于对Tracing JIT的翻译解释。
除了直译原文外,还根据luajit具体实现来补充对应的描述,以供迁移luajit时对其整体功能有一个指导性的理解。

Tracing just-in-time(JIT) compilation是一种运行时优化技术,被虚拟机等用来优化目标程序。
和传统的method-based JIT compilers相反, Tracing JIT通过recording(记录)经常被执行的代码序列,将它们编译成机器码并执行。

概述

Just-in-time compilation是一种在运行时通过编译程序中的部分字节码为机器码来提供执行速度的技术。
编译范围可以作为一种区分JIT编译器种类的方式。
尽管method-based JIT编译器一次将一整个函数编译为机器码,但tracing JITs将经常被执行的loops作为最小编译单元。
Tracing JITs的原理是基于一种假设,即程序将大部分时间都花费在部分loops中(“hot loops”)并且在开始hot loop后,后续的迭代很有可能执行的是相同的代码路径。
配备tracing JIT的虚拟机一般都是支持混合模式执行环境,也就是它们除了有tracing JIT的功能外,还有一个解释器或method编译器。

技术细节

tracing JIT编译器在运行时会处于多个阶段。
首先,loops的性能数据被收集。
然后,当一个hot loop被识别出来,VM会进入一个特殊的tracing mode(跟踪模式),它会记录这个loop执行过程中的所有操作。这些”所有的操作”被称作一个trace。 这些trace接下来会被优化,然后编译成机器码。
最后,当这个hot loop再次被执行时,VM会执行对应的trace而非对应的字节码。

性能剖析阶段

性能剖析的目的是为了识别hot loops。
一般是通过计数器来记录loop的迭代次数。当计数器超过某个阀值时,对应的loop就被认为是hot的,紧接着就会进入tracing模式。

体现在luajit中就是,在解释执行BC_LOOP时简单的对hotcount计数器进行+1操作,若溢出了则将进行一些列准备工作,
开始调用lj_trace_hot,进而进入tracing模式。
hotcountGG_State的一个成员,是一个计数器数组,索引是以ByteCode的PC值进行hash后所得。

typedef struct GG_State {
  lua_State L;              /* Main thread. */
  global_State g;           /* Global state. */
#if LJ_HASJIT
  jit_State J;              /* JIT state. */
  HotCount hotcount[HOTCOUNT_SIZE]; /* Hot counters. */
#endif
  ASMFunction dispatch[GG_LEN_DISP];    /* Instruction dispatch tables. */
  BCIns bcff[GG_NUM_ASMFF];     /* Bytecode for ASM fast functions. */
} GG_State;

这一阶段的性能负担非常小,只是在每个BC_LOOP前进行一次技术和比较操作,只有在计数器溢出后才会有额外的性能负担,
但此时往往就是即将进行JIT进行性能跳跃了。

跟踪阶段

在tracing阶段,loop的执行依旧是按照正常的方式处理,但除此之外loop中的每一个操作都会被记录到对应的trace中。

这些被记录的操作通常会转换为一种中介表示方式后进行存储。

函数调用也是会被tracing的,因此可以让这些函数调用被内联后直接存储到trace中.
tracing会一直持续到loop的末尾,然后loop会继续正常回到loop的开始行。

因为trace记录的是loop中的某一个具体的执行路径,所以trace的后续执行可能需要偏离之前记录的执行路径。
一些特殊的guard指令会被插入到trace中,用来标示这些可能偏离的执行点,并保证他们不会出现偏离。
if条件判断语句就是一个可能会导致偏离的执行点。guard指令用来检测trace执行时的状态是否和之前记录时的状态一致。
如果guard指令失败,则trace的执行就会被中断。

因为tracing是在runtime进行的,因此trace可以保函一些运行时特有的信息,比如类型信息。
这些信息可以被后续的优化阶段利用来提高代码效率。

体现在luajit中就是,
VM会进入lj_trace_ins,进而修改GG_state.dispatch这个结构体,将相关ByteCode替换为JIT版本。
dispatch这个数组成员的索引是VM ByteCode的数值,每个索引对应的值就是对应的ByteCode handler也就是对应的处理
函数。 在VM中响应进行模式替换、功能修改、代码监听等,往往就是临时修改这个GG_state.dispatch,比如
FORI替换为JFORI
lj_trace_ins除了更新dispatch外,还会创建一个trace,对执行的每一个ByteCode进行记录,
并检测当前实际的寄存器值和base内存记录一些必要的信息,如类型信息,以便在代码生成阶段来制作guard指令。
IR code就是在这里第一次出现,
trace负责把当前实际执行的ByteCode序列 + 当前内存状态转换为带类型信息和guard指令的IR code

优化以及代码生成阶段

实际上trace是很容易优化的,因为他们只包含一个具体的执行路径,意味着trace没有条件分支,也就不需要对此类控制流进行处理。
典型的优化方式包括constant-subexpression elimination(cse), dead-code elimination(dce), register allocation,
invariant-code motion, constant folding以及escape analysis.[1]

在优化处理后,trace才会被编译为机器码。和优化处理类似,因为trace里只包含一些按需执行的线性代码,所以编译成机器码也是比较容易的。

体现在luajit中就是,
JIT state进入LJ_TRACE_ASM,此时对应的trace里已经包含了完整的某个代码执行路径的ByteCode执行记录,并以SSA IR
的形式存储,在进行教科书里经典的处理后(代码集中在lj_opt_xxx.c中),调用lj_asm_xxx.c里的架构相关函数生成对应的机器码就行了。

这一步在概念上是比较容易的,但因为架构相关代码集中在此,所以移植上还是有很多困难的点的。不过只要从整体上理解了tracing JIT
的原理,后面的就只是花时间去验证自己的理解。 这一块的进一步信息可以参考这里(涉密原因,需要权限才能查看)。 

在具体实现时,这里主要是根据对应CPU、架构的具体情况来尽可能利用高级特性,比如base+idx*8这种典型的乘8后加这类高级指令在MIPS
就没有对应的指令。如果参考MIPS之类的架构实现,则需要注意替换这些实现。

执行阶段

在trace被编译为机器码之后,后续的loop迭代就可以被替换为执行对应的trace了。 trace会持续执行直到某个guard失败。

体现在luajit中就是,因为前序阶段已经替换了GG_state.dispatch,此时只需要在修改后的关键点(实现时选择的是BC_FORL)里跳转到trace.mcode就能执行优化后的指令了。控制权的返回是由guard指令来调整的。

在刚开始移植luajit的时候可能会有一点迷惑,luajit的VM已经是用汇编编写的了(而且是开发了一个dynasm的宏语言来实现了整个VM),JIT
模式生成的也是汇编代码(准确来说是机器码),为何要做两套。
这里简单的解释下

  1. VM用汇编仅仅是为了提供一个更好的base performance,这里和直接用C语言编写在性能上一般不会有数量级的区别,仅仅是一个
    可选项。
  2. JIT的汇编和VM的汇编是两码事,前者的性能关键不取决于用什么语言编写的(毕竟CPU只认识机器码,任何语言最终都是到了机器码)。性能的关键(几十倍的差异)主要是执行逻辑的不同。前者是一个ByteCode一个ByteCode的解释,每一个ByteCode的解释都至少是一个函数上百条机器码的级别。而后者是直接将用户逻辑编译为最终机器码,不算控制流跳转这种耗能大户,仅仅在执行指令的数量上也比前者减少了至少两个数量级。

如果说luajit这个用汇编写的luajit VM(luajit不开启jit时)比,C语言写的luajit VM(也就是lua C)更快一点,我们单纯的靠直觉可以很以为然的理解,
那么当年PyPy一个用python语言写的python虚拟机却可以号称比用C语言编写的python虚拟机性能更好的原因,可能就不会那么容易理解,会不断引起
初学者的讨论。

1 条思考于 “理解tracing JIT

发表评论

电子邮件地址不会被公开。 必填项已用*标注