有哪些常用 JIT 算法?

可能不是很准确,总之就是如何入门 JIT?
关注者
117
被浏览
3844
其实JIT编译器中的核心部分就是个编译器,没啥特别的。它的原理和算法都跟传统编译器一样,所以学好编译原理就好了。
更有趣的问题是:题主出于什么目的、什么场景而需要“入门JIT”?

====================================

概述JIT编译器与AOT编译器的比较

JIT编译器跟传统静态编译器(AOT编译器)的主要差别,大概有5个吧:
  1. JIT编译器可以使用运行时才可以获取的信息,而AOT编译器不可以;
  2. JIT编译器不需要生成PIC(地址无关代码)就可以天然地实现动态链接;AOT编译器如果要支持动态链接的话则必须生成PIC;
  3. JIT编译器可以在运行时灵活地选择编译的范围和编译的时机;并且,一段代码已经被JIT编译后,仍然可以在有需要的时候抛弃之前编译的结果而再次JIT编译。这使得JIT编译可以兼顾激进优化与语义的完备性。
  4. 当然,既然是在运行时编译,JIT编译器常常(并非必然)会受限于时间与空间开销的限制而需要选择只使用比较轻量的数据结构和算法来做分析/优化/代码生成,所以可以花在优化上的资源常常比AOT编译器少,但这可以通过前面3点来得到低开销的弥补方式。
    1. 同时也存在JIT编译器是偏向让峰值性能最大化的,它就可能会仍然选取跟AOT编译器相似开销的优化算法,舍弃一点编译速度来换取编译生成更好的代码质量。鄙司Azul SystemsZing® JVM里新的Falcon编译器就是这样的例子。
  5. JIT编译器作为运行时系统(runtime system)的一部分,有可能需要更紧密地与运行时系统中的其它部分(例如说代码的动态加载/链接器、解释器、线程管理、异常处理、GC等可能存在的组件)相配合,例如可能要生成额外的元数据,也可能要支持某些事件响应/回调。

特别的,如果要为一个已有的使用解释器实现的运行时系统添加JIT编译的支持,而这个已有实现本身非常糟糕,那么光是添加JIT编译器是提升不了多少性能的,一定要运行时系统自身也做相应的改变来更好地适应JIT编译的需求才可以有效、显著提升性能。
放俩传送门:

关于JIT编译器可能比AOT带来的优势,先放个传送门:如果没有PGO,JIT 编译相比AOT 编译有哪些优势?

关于JIT编译器的编译时机、多层执行模式配合的话题,放几个传送门:
特别注意JIT编译器并不一定要阻塞/暂停应用线程,而是可以异步/后台/并发+并行编译。这样就减少了JIT编译器追求编译速度的压力,允许JIT编译器使用开销更高的优化算法。

还有一些细节上的差异也值得一提。例如说:
  • 编译单元:
    • AOT编译器:常常以源码文件或模块为编译单元,里面的所有函数/方法定义都放在一起一股脑全部编译到目标代码;多个编译单元编译出来的目标代码可以选择通过静态链接形成一个可执行文件或者一个库文件,也可以选择生成动态链接库然后等到运行时再分别做动态加载与动态链接。
    • JIT编译器:常常以函数/方法为编译单元,这种叫做 function-JIT 或者 method-JIT。也有别的粒度的编译单元,例如说以一条代码踪迹(trace)为编译单元(trace-based JIT 或者叫 tracing-JIT),或者以一颗调用树(call tree)上的一个区域(region)为编译单元(region-based JIT)。这些编译单元常常比AOT编译器所使用的编译单元小,所以可以“看到”的代码范围也比较小。同时,JIT编译器常常会与运行时系统中的动态链接器配合,天然实现代码的动态链接。由于可以跟运行时系统的其它组件协作,JIT编译器在编译的时候,甚至不必把编译单元中的所有代码都编译为目标代码,而可以把其中一些执行频次低而且逻辑复杂 / 影响性能的代码交给别的组件(例如说解释器)去执行。

JIT编译与AOT编译也不是矛盾的。设计得当的话,同一个编译器既可以被用作AOT编译场景,也可以被用作JIT编译场景。比较新的Android Runtime(ART)里名为“Optimizing”的编译器就是这样的一个例子,既充当ART在安装应用时或者再次启动应用时的AOT编译器,也在运行时充当JIT编译器。相似的例子还有很多,就不一一列举了。

====================================

实现JIT编译器的一些基本切入点

首先要再次强调上面已经提到的一点:JIT编译器作为运行时系统的一部分,要能够与其它组件充分协作才可以达到理想的效果。设计一个“JIT编译器”常常不只是要设计一个编译器,而是要连配套的运行时系统也一起考虑进去设计。

实现JIT编译器有几种不同的切入点:
  1. 正统做法:从正统编译原理出发,实现一个与运行时系统搭配使用的编译器。这样要实现不怎么优化的初级编译器也行,要实现高度优化的编译器也行。这种做法完全自己撸也行,借助一些现成的编译器框架来撸也行,例如说以LLVMOMR JIT、LibJITlibgccjit等库为后端都可以。
  2. 偷懒做法:从改进解释器效率的角度出发,把解释器改造成初级编译器。
  3. 省力做法:在一个自带JIT编译器的平台上实现编程语言,这样只要编译到这个平台所支持的输入形式即可得到JIT编译器。例如说在JVM、.NET平台上实现编程语言,把自己的编程语言编译到Java字节码或者MSIL,就可以自然地让JVM / CLR里的JIT编译器去干活。这样只要实现“半个编译器”(编译器前端,将源码编译到某种中间表现形式,例如上面说的两种字节码),就可以得到一个完整的编译器支持。
  4. 炫酷做法:通过partial evaluation,让用户只要编写一个解释器,与这个partial evaluator结合起来就得到了一个JIT编译器。如果这个partial evaluator做得好的话,得到的JIT编译器可以是高度优化的。目前比较出名的例子是PyPy框架与Truffle / Graal框架。

就题主所给的简短的问题描述来说:
有哪些常用 JIT 算法?
可能不是很准确,总之就是如何入门 JIT?
如果不介意基于某个现成的框架来实现JIT编译器的话,考虑上述的(4),基于PyPy或Truffle / Graal来做那是最炫酷不过了。写个解释器+部分运行时系统的实现,就可以得到全套带JIT和GC的运行时系统了。
放个传送门:PyPy 为什么会比 CPython 还要快? - RednaxelaFX的回答 - 知乎

如果已有一个现成的解释器,想要小幅度提升解释器性能,可以考虑上述的(2),小幅度改造解释器来构成简易的JIT编译器。
Apple的WebKit里JavaScriptCore,最初是衍生自KJS的一个纯解释器实现,是基于AST的解释器。后来在“SquirrelFish”项目中实现了一个新的基于字节码的解释器,然后在进一步深化的“SquirrelFish Extreme”项目中通过“context-threading”方式实现了从解释器向简易JIT编译器的转变,这就是上述的(2)的思路。然而…后来JavaScriptCore为了追求更好的性能,还是不得不回头走(1)的思路,使用正统的编译原理来实现一个初级JIT编译器(Baseline)和一个优化JIT编译器(DFG),还有后来的更优化JIT编译器FTL。

关于(2)都有些什么具体的思路,请先从这个经典的网页开始学习:Anton Ertl大大的Threaded Code
有几种思路都可以看作是把解释器改造为简单初级JIT编译器的:
  • subroutine-threading
  • context-threading
  • inline-threading
另外还有所谓“superinstruction”的思路,把它扩展为“dynamic superinstruction”其实就可以看做基本块(basic block)层面上的JIT编译。
——各位同学有没有听说过有些所谓“trace-based JIT”实际上只用一两个基本块作为编译单元的(此时一条trace限定在1-2个基本块的长度),其实达到的效果只不多就是跟“dynamic superinstruction”思路差不多而已,根本发挥不出先进的trace-based JIT的优化潜力发挥出来。

====================================

现代常见的JIT编译器的几种典型案例

待续

====================================