Lazy Basic Block Versioning

Simple and Effective Type Check Removal through Lazy Basic Block Versioning，这篇论文来自ECOOP2015，介绍了一种可以有效消除类型检查的技术，用于动态类型语言的JIT编译。

简介

动态类型语言需要动态的进行类型检查。在性能敏感的场景下，动态语言的虚拟机会选择消除冗余的类型检查。

传统上，语言虚拟机倾向于使用type infer来消除类型检查。但是对于JS、Python这样的动态类型语言，存在三个主要问题：

  • 这些语言通常不适合于whole-program的类型分析，eval和模块的动态加载等特性会破坏以前的类型信息；
  • 在时间和内存上的代价使得其并不适合在JIT上使用，特别是某些追求编译速度的基线编译器上；
  • 某些代码单纯通过分析是无法消除类型检查的，需要进行某些变形；

由于上述原因，普遍的JS虚拟机设计比如V8、SpiderMonkey等都通过multi-tiered和OSR这样的复杂机制在激进优化的同时保证语义正确。

这篇论文提出一种可以在JIT编译时对关键代码路径消除冗余类型检查的方法——lazy basic block versioning（以下简称BBV）。不需要代价昂贵的程序分析技术，不受传统类型分析的精度限制，避免了激进优化导致的实现上的复杂性。

简单来说Code Generator维护了typing context，保存每个变量的类型。一个类型检查指令会分化出新的typing context，对每个context而言，其中的每个变量的类型都是经过检查的。当遇到一个类型测试分支指令并且参数的类型已知，在代码生成时就可以根据分支方向消除类型检查。

而编译器可能会对一个basic block生成多个version的代码。在该基本块的分支上遇到的每个类型环境都有一个版本。这就允许了可以对该基本块以及它的后继中的活跃变量进行类型特化。虽然基本块的版本是建立在单个基本块的层面上的，但typing context向后继的继续传播带来了对整个控制流图进行type-specializing的机会。

与传统的type infer相比最大的区别在于，BBV不需要在推导时计算不动点。对于一个程序点而言，变量的类型可能是多种的。在传统的类型分析中，几种可能的类型将被联合起来，从而导致分析的保守性。BBV则对不同的基本块版本或程序路径，精确的根据上下文来控制类型。

在BBV中循环也不需要被特殊处理，如果首次执行到loop header时的context是C1，那么再次回到loop header时将生成新的C2，以此类推。但由于可能的context是有限的，并且实际上大多数变量在函数中总是维持一种类型，所以生成的version数量也总是有限并且相当少。

实现

论文实现基于JS虚拟机——Higgs，支持ES5标准，但是作出了一些限制，比如eval只能访问全局变量。

下面用一个例子来说明。对于一个简单的JS函数：

function sum (n) {
    for ( var i=0, s=0; i<n; i++)
    	s += i;
    return s;
}

上图是代码对应的CFG，省略了其中一些处理非int32类型、处理Exception的基本块。

如图所示存在5条type check的判断条件。

  • 当编译该函数时，block A会生成一个version A1，当中的变量s和i都是int32类型；
  • 对于block B则不会再编译任何东西，因为i在当前context中已经是int32类型；
  • 之后生成block C的version C1，而变量n的类型检查则会被保留；
  • 以此类推，在typing context向后继续传播，s和i的类型检查都会被消除；
  • 代码连续执行，一直到循环的结束。在最后一次循环迭代中，D1的小于比较失败。这就触发了循环退出块E1的编译。最终结果如下所示：

Evaluation

评估的Benchmark来自于SunSpider和Google V8的总共26个基准测试用例。

Type test count

首先测试的是相对于无优化情况，最终执行的type check的比例。analysis表示通过常用type infer算法优化之后所执行的type check个数，maxvers表示对于一个基本块可以生成的版本个数的上限，通过限制版本个数上限，可以控制编译时长和内存占用。

上图中可以发现，即便版本上限低至1个，BBV也能达到通过分析算法优化的效果，这可能是因为大多数变量的类型都是单态的。bitwise-and基准测试只对全局变量进行操作，而实现的系统无法提取这些变量的类型，因此在这个基准测试中，类型分析和BBV都没有什么作用。

Code Size

上图是对应version数量的基本块的比例。大多数基本块只有一个版本，5.2%有两个版本，只有0.16%的区块有5个或更多的版本。因此，拥有大量版本的基本块是一种罕见的情况。

上图是生成的最终代码大小的对比。程序分析的方法几乎总是能轻微减少代码体积。因为分析消除类型测试，并生成更多的优化代码，这些代码通常更小。另一方面，BBV会生成多个基本块的版本，但并不总是会导致生成更多的代码，生成的代码量不会随着版本个数限制的上升而线性增加。一个原因是如前图所示，需要多版本的基本块的占比相当低。另一个原因是优化导致的体积下降。

Execution Time

Compilation Time

Baseline Compiler

Speedup relative to V8 baseline

Speedup relative to TraceMonkey

Speedup relative to Truffle JS

个人评价

最早知道BBV是来自于PyPy那篇著名的blog，在回顾PyPy JIT技术发展时提到使用了类似的技术。BBV的想法和我之前的一个想法比较象——必需要check类型的变量（即在同一个程序点存在多种类型）在大多数情况下是有限的，如果可以准确收集到它们，那么就可以用他们来构造一个上下文类型环境，在这个范围内的代码就可以像静态类型那样优化，而当环境发生变化，就新特化出一个版本。

所以从根本来讲，本质是希望对于每一次type check可以支配尽可能多的代码路径。

BBV则是从代码本身出发，将type check的最作用传播出去，而typing context就是传播的载体。通过context对比找到能适用的（或者不能适用的）基本块，从而实现优化、减少冗余。

另一方面，这篇文章的优化是一个后向传播的，那么是不是存在某些情况，需要做前向分析呢？比如对于一个基本块的context，可以在它的前趋块上与其他context合并。

还有一点是当Native Code与解释器交替执行的时候，可能并不需要太过严格的类型约束。当然这点也许可以从type check本身的优化入手。

图片数据来源：《Simple and Effective Type Check Removal through Lazy Basic Block Versioning》

Higgs：https://github.com/higgsjs/Higgs