V8 之旅：优化编译器 Crankshaft #

目录 #

在之前的两篇文章中，我们讨论了 V8 的 Full Compiler 和对象的内部表示。在几年前，FC 生成的原生代码相对于 JavaScript 来说已经不错了，但人们对性能的要求与日俱增，其速度标杆也越来越高，因此衍生出了 Crankshaft。

Crankshaft 是 V8 的优化编译器。回忆一下，V8 有两个编译器，另一个编译器 FC 负责尽快生成未优化的代码。对于只执行几次的代码，FC 生成的代码还是比较理想的。当 FC 产生的代码运行过一段时间之后，V8 会挑选出 “热门” 的函数，重新用 Crankshaft 编译。这大大提升了性能。

热身完毕 #

如果只看脚本，很难说哪个函数最应当得到优化。V8 使用一个运行时性能分析器在脚本运行的时候识别热门的函数。

Crankshaft 刚开始部署时，V8 选择在另一线程跑栈采样分析器（stack sampling profiler）。几乎每隔一段时间（桌面版本为 1ms，移动版本为 5ms），此线程就被唤醒一次，然后向主线程发送 SIGPROF 信号。主线程的信号处理代码会重置栈顶的高度（一般是一个标志栈结束的地址）。每当一个函数被调用以及每轮循环的时候，经过 JIT 的代码会检查是否达到栈顶，如果栈指针超过了栈顶，就会调用运行时来报错。这给了性能分析器一个打断脚本执行的时机。V8 运行时会在检查出栈溢出是因为信号 SIGPROF 时调用性能分析器，于是性能分析器就可以在这时看到栈顶的几帧，然后标注这些函数进而优化。

这种性能分析器有几个短板。由于采样是几近随机的，性能因素并不主导采样。尽管分析器在统计上倾向于挑选出最热门的函数，但其可能在页面每次重载时得出不同顺序或不同次数的结果。想象一下当时的情景，性能测试的时候得出的是差异很大的结果，V8 测试集当中的某些测试甚至能在多次运行时差距达 50%。同时这种方案会因其打断代码执行的机制，在整体上对不含循环的大函数有失偏颇。

V8 如今用基于计数的性能分析器（counter-based profiler）。每个经过 FC 的函数都包含一个计数器，当函数返回或完成一轮循环的时候，就会减少计数的值。而减多少则依据函数或循环的大小，因此这对于大函数和循环来说更加公平。分析器在计数减到 0 的时候调用，然后和栈采样分析器类似（实际上更加出色），但更侧重性能地选出热门函数。另外这样对于已优化的代码来说没有任何影响，因为只有未优化的代码才会有计数器。

一旦一个函数被分析器标记为需要优化，指向其代码的指针就会被改写指向为一个 V8 内置的函数 —— LazyRecompile ，来调用编译器。这样函数就会在下次调用时得到优化。

剖析 Crankshaft #

Crankshaft 经过以下几个阶段生成代码：

• 语法分析（Parsing）：这一阶段负责将源代码翻译为 AST。Crankshaft 与 FC 共享同一个语法分析器，但出于空间占用考虑，V8 并不保留任何编译器所得到的 AST（以及其他中间产物）。而且 AST 也不常用，生成也很容易。
• 作用域分析（Scope analysis）：在这一阶段，V8 将确定变量是如何被使用的，将其与各自的定义链接。局部变量、闭包变量、全局变量的对待方式会各不相同。这个阶段也与 FC 共享。某些代码的写法（比如用 eval 动态引入变量）会使一个函数失去优化或内联（inlining）的资格。
• 图生成（Graph generation）：Crankshaft 使用 AST、作用域信息以及 FC 代码反馈而来的类型信息，来构建 Hydrogen 控制流程图。内联（inlining）也发生在这一阶段。Hydrogen 是 Crankshaft 中一个高层次、架构无关的中间代码。
• 优化（Optimization）：在这一阶段绝大多数优化都作用于 Hydrogen 控制流程图。这是 Crankshaft 唯一能够与 JS 线程并行的时候。虽然本文撰写时还不是并行的。
• 低级化（Lowering）：优化结束之后，Hydrogen 外会生成一个 Lithium 图。Lithium 图是一个低级且架构相关的中间代码。寄存器的分配就是在这一阶段施行的。
• 代码生成（Code generation）：在这个最后阶段中，Crankshaft 按照 Lithium 图中的每个指令发送原生指令（native instructions）。元数据，比如重定位信息以及去优化数据，也是在这一阶段生成。完成之后，经过 JIT 的代码会放在一个 Code 对象中，然后继续脚本的执行。

整个结构对于优化编译器来说非常典型，然而某些方面可能会让你惊讶。首先，Crankshaft 并没有一个真正的低级表达形式。Hydrogen 和 Lithium 的指令基本上和 JS 中的操作相对应。在某些情况下，十来个原生指令才对应一个 Lithium 指令。这可能会导致生成出来的代码中有一定的冗余。第二，Crankshaft 一种指令调度都没有。对于 x86 处理器来说不算大问题，因其最终是乱序执行；但对于一些相对简单的 RISC 指令集架构，比如 ARM，会造成一些麻烦。

这些缺点大多是因为 Crankshaft 在性能影响上的重要地位。JS 代码在 Crankshaft 执行时是中断的，这就意味着 Crankshaft 必须尽快完成任务，而任何附加的阶段和优化都可能得不偿失。V8 的开发者们正在为 Crankshaft 的并行上努力，但这一功能目前还没有打开。V8 的堆并不支持多线程访问，而如果不访问堆，则只有优化阶段能够并行。然而使堆变得线程安全是一项复杂的任务，可能会引入额外的同步负担。

Hydrogen 与 Lithium #

V8 的高级中间代码叫做 Hydrogen，而低级中间代码叫 Lithium。如果你曾经用过 LLVM，Hydrogen 的结构看起来会有些熟悉。函数被表达为一个由一组区块构成的流程图，其中的每个区块都包含一系列静态单赋值形式（SSA，static single assignment）的指令。每条指令则包含一组操作符和一组操作符调用，因此你可以将其想象为一个叠在流程图之上的数据流图。每个 Hydrogen 指令表示一个较为高级的操作，比如算术运算、属性的存 / 取、函数调用或者类型检查。

大多数优化过程发生在 Hydrogen 身上或构造 Hydrogen 的时候。这是 Crankshaft 所执行的优化：

• 动态类型反馈（Dynamic type feedback）：在图生成的同时，大多数操作会特化为对一个类型的操作。这些类型在 FC 代码的内联缓存中得到。比如，如果 IC 实现的是一个读取操作，而这个读取只作用于一种对象的某个属性，特化的 Hydrogen 代码会将被优化为只处理这一种对象的代码。为此，必要时会加入类型检查。
• 内联（Inlining）：发生在图的生成阶段。内联的启发规则非常简单：基本上如果一个函数在调用时已知且内联它是安全的，那么就内联它。大函数（源码中大于 600 个包括空格在内的字符，或超过 196 个 AST 节点）则不会内联。最多只有 196 个语法节点可在一个函数中内联。
• 形式推断（Representation inference）：Hydrogen 支持三种寄存器中的值：标记值、整型值和双精度浮点。所谓标记值，就是指这个值是封箱的。字符串和对象总是标记值，但数字则不一定。原生整型和双精度浮点更有效率，但所有的值都必须在存到内存中或传递给另一个函数前标记。这一环决定了每个值应有的表达形式。
• 静态类型推断（Static type inference）：这一步 Crankshaft 尝试确定函数中各种值的类型。由于一次只能针对一个函数而且大多数操作（比如函数调用、属性读取）产生的类型无法推断，这步效率很低。不过有些类型检查会因为该值有精确的类型信息而省去。
• UInt32 分析（UInt32 analysis）：V8 使用 31bits 来表示小整数。其最低位保留给垃圾回收器用以判定它是指针还是数字（0 表示数字，1 表示指针）。Crankshaft 可以使用全部 32-bit 来保存不经过内存的局部变量和临时值，而当超出这一区间时，则需要特殊处理。语义上，JavaScript 将所有数字都视为 64 位双精度浮点，因此允许用整数来表达原本是错误的。但这一步将某些操作归纳为无符号的，于是微小的溢出并不会在这些特定情况下造成麻烦。这对于诸如密码学、压缩和图形处理相关的程序来说非常有用。
• 标准化（Canonicalization）：这步是用来进行简化的。它去掉了不必要的操作，并进行一些简化。
• 值编号（GVN，Global value numbering）：这是去除冗余的标准步骤。依次处理每个指令，当一个指令处理之后，会生成一个基于其操作、输入以及任何相关数据的哈希值，插入到一个哈希表中。后续如果遇到同样哈希值的指令，则 GVN 会删除后续的那个。但每当遇到对该指令存在副作用的指令，则从哈希表中清除原先存入的这个指令。比如，对于两个完全一样的读取操作来说，如果中间还有一个存储操作，则这两个读取操作并不能合并。
• 移出循环无关代码（LICM，Loop invariant code motion）：这个和 GVN 同时执行。循环中并不依赖循环中其他代码的指令，将被提到循环之前。对循环无关值的类型检查也会被提到循环之前，但这可能会导致某些场景下并不会发生的类型检查也被执行，因此编译器会在这时趋于保守。
• 范围分析（Range analysis）：这步会确定每个整数操作的上限和下限。这样就有可能去掉一些溢出检查。在实践中，这个并不太精确。
• 去除冗余的数组范围检查（Redundant bounds check elimination）：去掉某些已在数组元素访问中执行过的多余数组范围检查。
• 后推数组下标计算（Array index dehoisting）：这一步会反转 LICM 对一些非常简单的表达式（如数组下标增加或减去一个常数）的效果。所有 V8 支持的架构都有指令来完成寻址时对下标的简单加减，因此提前这些代码通常也没什么大的好处。
• 去除无效代码（Dead code elimination）：这是一种清理工作。它会移除掉 Hydrogen 指令中无效或者没有副作用的部分。这些指令往往是其他优化所产生的副产品，而程序员自己所写的无效代码则不包含在内：V8 可能会在函数运行的过程当中，在优化代码和未优化代码之间切换，而如果优化后的代码缺失了某个未优化代码所需要的值，则可能会造成崩溃。（ 译注：也就是说，在 Crankshaft 看来可能无效的代码，很可能只是整个脚本的一部分，而整个脚本中的其它未优化部分，实际是需要那部分看似无效的代码的。 ）

Lithium 是 V8 的低级、机器相关的中间代码。实际上它并不是特别的低级：每个 Hydrogen 指令至多被低级化为一个 Lithium 指令。有些 Hydrogen 指令，例如 HConstant 、 HParameter 原封不动变成了 Lithium 指令。其他一些 Hydrogen 指令会被低级化为某些由操作数衔接起来的指令（而在 Hydrogen 中它们本是直接相连的）。这里的操作数可能是常数、寄存器，或者栈槽。寄存器分配器将决定每个操作数的类型和其存放位置。大多数指令只支持寄存器操作数，因此寄存器分配器需要在这些操作数中间增加存取的指令。

原生代码将从 Lithium 指令得出。简单的 Lithium 指令可能只对应一条原生指令，而某些复杂的 Lithium 指令则会对应 10-20 条原生指令（ARM 如此，其他架构可能有差异）。

即使是在只处理常规使用的优化代码当中，你也会因 JavaScript 脚本最终产生的复杂代码而咋舌。举例来说，以下是为一个 JS 对象增加一个属性的代码：

 ;; HCheckNonSmi: 检查低位，确定目标是整数
 ;; 整数的最低位总是0
  40  tst r0, #1
  44  beq +188 -> 232

 ;; HCheckMaps: 将目标的Map与已知Map对比
  48  ldr r9, [r0, #-1]
  52  movw ip, #41857             ;; object:  
  56  movt ip, #17120
  60  cmp r9, ip
  64  bne +172 -> 236

 ;; HCheckPrototypeMaps: 检查目标的原型链，
 ;; 以防有同名的只读属性
  68  movw r2, #38241             ;; object:  Cell for  
  72  movt r2, #15696
  76  ldr r2, [r2, #+3]
  80  ldr r1, [r2, #-1]
  84  movw ip, #41937             ;; object:  
  88  movt ip, #17120
  92  cmp r1, ip
  96  bne +144 -> 240
 100  movw r2, #46869             ;; object:  
 104  movt r2, #14674
 108  ldr r1, [r2, #-1]
 112  movw ip, #36057             ;; object:  
 116  movt ip, #17120
 120  cmp r1, ip
 124  bne +116 -> 240

 ;; HConstant: 这才是我们要存储的值
 128  mov r1, #198

 ;; HStoreNamedField: 以下是存储操作
 ;; 首先，读取Transition的Map
 132  movw r9, #41977             ;; object:  
 136  movt r9, #17120

 ;; 接着，将其存入该对象的首字
 140  str r9, [r0, #-1]

 ;; 可能还需要将Map的变动通知垃圾回收器
 ;; 这里是一个写操作的内存屏障，
 ;; 递增标记需要这样的保证
 144  sub r2, r0, #1
 148  bfc r9, #0, #20
 152  ldr r9, [r9, #+12]
 156  tst r9, #4
 160  beq +36 -> 196
 164  mov r9, r0
 168  bfc r9, #0, #20
 172  ldr r9, [r9, #+12]
 176  tst r9, #8
 180  beq +16 -> 196
 184  movw ip, #37056
 188  movt ip, #10611
 192  blx ip

 ;; 现在我们终于可以存储那个属性了
 ;; 因为这次存储的是整数，无需通知垃圾回收器
 ;; 但通常这里还需要另一个内存屏障
 196  str r1, [r0, #+11]

栈上替换 #

我们讲性能分析器时说过，经过分析器标记的函数，编译器会在下一次调用时对其进行优化编译，而当编译工作结束后，运行时即会载入新的优化代码来执行。对于大多数函数来说，这种机制已经足够好了，但对于包含热门循环，且只运行一次的函数来说，这个机制就有瑕疵了。

function calledOnce() {
 for (var i = 0; i < 100000; i++)
   // ... 这里是需要优化的部分
}

这类函数仍然需要优化，因此一种略复杂的机制应运而生。如果性能分析器被触发时，一个函数已被标记为需要优化但还没有再次被调用，则分析器会尝试栈上替换。分析器会直接调用 Crankshaft，立即生成出优化代码；当 Crankshaft 执行完毕时，V8 会依据原先包含该函数的栈帧中的其他代码，构造一个新的栈帧来存放优化后的代码。这时将旧的栈帧弹出，压入新的栈帧，恢复脚本的运行。

这一过程需要两个编译器的支持。FC 需要产生包含该栈帧中其他值的位置信息，而 Crankshaft 需要生成这些值即将存放的新位置的信息。同时，Crankshaft 还需要生成额外的 “接入层”，来将这些值从栈帧读取到正确的寄存器当中。

去优化 #

上面提到过，Crankshaft 生成的代码只是特化针对于 FC 所遇到的类型，因此 Crankshaft 无法处理所有可能的值。我们需要一种机制来在遇到未知类型和算术运算溢出时优雅降级，换用 FC 的代码。这种机制就叫做去优化。通常去优化就是进行栈上替换的逆操作。然而这里面有个小问题：Crankshaft 支持内联，因此类型问题有可能会在内联代码之内发生。这时去优化过程将不得不对多个栈帧进行操作。

为了使去优化器的工作更加容易，Crankshaft 会生成去优化的输入数据，每个去优化可能发生的地方，都会有相应的命令关联。去优化器将通过这些命令，来将寄存器、栈槽等从优化代码中的值，转换为未优化代码中的值。每条命令都包含有与栈相关的操作，比如 “从寄存器 r6 中获取值，将其封箱为数字，然后压入下一栈槽”。去优化器的任务就是寻找正确的命令，将其执行，然后弹出优化的栈帧，压入相应未优化的栈帧。

总结 #

Crankshaft 是 V8 的秘密武器。通过运行时的性能分析器，V8 能够检测出最需要优化的函数。由于 V8 的去优化随时可能需要将代码降为未优化代码，Crankshaft 可以在一定程度上具有推断能力，只优化特定情况下的代码。

在将来，Crankshaft 很可能会并行。由于可以腾出更多的时间优化更多的代码，这能够让 V8 的性能更高。

参考 #

• A tour of V8: Crankshaft, the optimizing compiler — jayconrod.com
• V8 之旅：优化编译器 Crankshaft – NewHTML
• 静态单赋值形式 - Wikiwand