Ignition: 寄存器等值优化 #

目录 #

本说明描述了一种在线优化技术，用于减少 Ignition 字节码生成器（bytecode generator）生成的字节码的寄存器传输次数（register transfers）。寄存器传输的减少转化为更少的指令分派、更低的内存消耗和可能更小的字节码帧。

简介 #

V8 Ignition 解释器实现了寄存器机加累加器（accumulator）模型。累加器是一个非用户可见的寄存器，用于保存中间结果。函数参数和局部变量保存在用户可见寄存器中，非用户可见临时寄存器用以将中间结果保存在表达式堆栈（expression stacks）中。临时寄存器在其他地方也有用途，例如为 for..in 等结构管理非程序员可见的状态。

当前的字节码生成器注意避免赋值风险（assignment hazards）（见附录）并且总是发出多对 move-register-to-accumulator、move-accumulator-to-register 可以更紧凑地表示为单个 move-register-to-register 字节码。字节码生成器还创建了临时变量来隐藏局部变量，这些临时变量显示为字节码的操作数。在很多情况下可以避免使用临时寄存器，直接使用本地对应的寄存器作为操作数。今天这些改进的障碍是字节码生成器（bytecode generator）和字节码数组构建器（bytecode array builder）都没有足够的字节码流可见性。

Ignition 源代码的最新更改对寄存器操作数进行了注释，以标记它们是否用于输入和输出，以及类似地，累加器是由字节码读取还是写入。我们在字节码数组生成器之后插入的新组件中一起使用这些信息，以在线算法优化寄存器传输。该问题比传统的寄存器内存分配和寄存器赋值要严格简单，但在对于分支和源代码位置，在处理基本块边界和保留偏移量时仍然需要小心。我们已经构建了这里提出的想法的原型实现，它没有显着的测试回归（与 mjsunit 中的源码位置相关的 11 个失败）。

寄存器等值 #

核心思想是推迟与用户不可观察的寄存器之间的寄存器传输，直到确定它们是必需的。出于调试目的，对应于局部变量和参数的寄存器必须始终是可观察的正确的。但是，字节码生成器触发的累加器和临时寄存器对用户或调试器是不可见的，如果不需要，可以推迟或忽略。

我们将寄存器等价集定义为一组寄存器（包括累加器），由于一个寄存器被转移到另一个寄存器而具有等价值。如果可以看到该集合的成员当前在输出字节码流中持有值，则称它们已物化。寄存器传输操作（Ldar、Star、Mov）具有将寄存器添加到等价集和在等价集之间移动寄存器的效果。这些操作有时会导致发出寄存器传输。评估其他字节码的寄存器依赖性，并具体化寄存器以满足它们的要求。当寄存器处于等效集合中时，它们可能会在与字节码关联的操作数中被替换。这些字节码对寄存器状态的副作用也被评估以更新寄存器等价集。

例如，考虑以下简单的函数：

function demo(x, y) {
  return Math.pow(x, y) + x * y;
}

Ignition 字节码生成器生成下方左侧的代码，通过寄存器等效优化 (REO) 对其进行细化以生成右侧的代码。

寄存器等效优化器读取字节码生成器输出并按如下所示进行。寄存器上方的条形表示在评估来自字节码生成器的代码时此时寄存器已具体化，没有条形表示寄存器未具体化。

在原型实现中，字节码生成器能够为寄存器等效优化器提供临时寄存器何时失效的详细信息。这使得当临时寄存器不复存在时可以从等价集中删除它们。字节码生成器使用作用域来分配临时寄存器，用于确保第 9 行调用的连续寄存器范围的临时寄存器在第 11 行时已失效。

基本块边界 #

等价关系在基本块边界处被打破。在转换到新的基本块之前，所有活动寄存器都被具体化为它们自己的集合。字节码生成器中的作用域寄存器分配意味着大多数临时对象不需要被具体化，只有那些是活的。实时临时变量可以合法地存在于基本块边界处，例如用于发出 for..in 循环的模式使用三个临时变量来保持状态，并且这些临时变量存在于 for..in 循环的外部范围内。其他情况，例如表达式中的逻辑条件，可能会导致临时对象在基本块边界上保持活动状态，因为基本块被引入表达式评估的范围。大多数临时变量用于表达式或仅用于特定语句，并且这些临时变量在到达基本块边界之前就消失了。

当新的基本块即将转换到标签绑定之前和跳转发出之前的点时，该实现会从字节码数组构建器获得通知。然后，该实现确保包括累加器在内的所有活动寄存器都被具体化并放置在这些边界处它们自己唯一的等效集合中。

当访问基本块中的代码时，建立新的等价关系并将优化过程应用于基本块。

原型实现 #

存在寄存器等效优化器的原型实现。在字节码生成器用来发出字节码的字节码数组生成器之后，它被引入到字节码生成过程中。优化器需要大约 500 行 C++ 代码才能实现。

字节码数组构建器中现有的字节码窥视孔优化器需要在 REO 优化器之后移动，因为窥视孔优化器查看字节码输出，当窥视孔优化器由于加载和存储的抑制而查看时，字节码输出不一定一致。此外，现有的窥孔优化适用于某些加载和存储模式，窥孔优化器不会观察到它的当前位置（嵌入在字节码数组构建器中）。

在原型中，字节码生成管道如下所示：

寄存器等效优化器、窥孔优化器和字节码向量编写器支持通用的 BytecodeWriter 接口。这允许每个阶段独立测试，并使功能与其他组件隔离。

字节码编写器接口支持通过 Write () 方法将字节码推送到管道中。它还支持两种冲洗来清除管道。当字节码数组构建器需要确定字节码中的偏移量时，需要刷新，用于计算跳转偏移量（也是异常偏移量）或源位置信息的偏移量。对应的 flush 方法是 FlushForBranch () 和 FlushForSourcePosition ()。每个管道元素在本地执行冲洗，然后调用下游继续冲洗操作。

FlushForBranch () 实现未实现的寄存器并打破等价集，假设一个分支即将在寄存器等价优化器中发出。它将加载和存储推入管道，并将它们从窥视孔优化器中冲出。 FlushForSourcePosition () 对寄存器等效优化器没有影响，但会导致窥孔优化器刷新所有缓冲指令以确保将源位置标记在正确的位置。

BytecodeWriter 接口还有一个 LeaveBasicBlock () 方法，它会导致窥孔优化器将缓冲输出推送到下游并将其内部缓冲区大小设置为零。

新的窥孔优化器可能会保留基本块中指令的历史记录，即使它们已被刷新。它仅在刷新不对应于基本块边界时才执行此操作。保留历史记录是因为在查看刷新的最后一条指令以及下一条下推到管道的指令时，可以应用一些窥孔优化。例如，字节码生成过程将 JumpIfToBooleanTrue 传递给窥孔优化器，然后如果已知前一条指令用布尔值加载累加器，则可以将其专门化为普通的 JumpIfTrue，例如测试指令或布尔加载。如果在这些指令之间发生刷新，则当前的 JumpIfToBooleanTrue 指令仍然可以被特化。

原型性能 #

发出的字节码数量及其大小是提供给字节码生成器的代码的函数。在原型开发过程中，我们一直专注于 Octane 2.1 基准测试。观察到的尺寸减小显示在下表中。

在这些测量中，zlib 运行时间最长，而 typescript 导致生成的代码最多。 Ignition 正在树中的这一点急切地编译字节码，这可能是为 typescript 基准生成的代码量的原因。

尽管 REO 减少了 Octane 的总运行时间，但所有组件的分数平均变化实际上为零。我们目前的结果如下图所示。大约 50% 的基准分数下降了。我们正在检查最坏的情况，看看是否有缓解措施来改善这种情况。

讨论 #

REO 开始是为了避免在字节码图生成器中避免分配风险的复杂性。字节码生成器是解释器中的一个复杂组件，它将 AST 翻译成字节码并处理控制流、异常和 AST 中公开的所有语言结构。过度关注字节码生成器中的分配危险冲突是导致难以理解的复杂性的途径。 REO 优化器与字节码生成器和字节码数组生成器完全不同。这使得它可以独立测试，并且可以选择轻松打开和关闭。

REO 通过用 Mov 替换 Ldar;Star 的序列来节省内存并减少要分派的字节码数量，从而改善了我们在许多场景中的寄存器使用。

当前的原型已将窥孔优化器移至下游，并使其与字节码数组构建器区分开来。这对于窥孔优化器不干扰 REO 的行为是必不可少的，并且有利于测试。

本文档不详细讨论原型的实现细节。我们苦思冥想如何高效地实现等价集，将每个寄存器的集合信息放到链表中。列表中的节点包含寄存器，一位指示寄存器是否被物化，以及一个用于为临时对象选择最佳物化替代方案的序列号。该实现使用一个区域来分配节点，但在寄存器死亡时将它们保留在空闲列表中，以避免在大型代码体上分配过多负载。

未来的机会 #

减少帧大小 —— 目前字节码数组生成器根据临时寄存器的使用情况计算字节码帧大小。 REO 意味着输出字节码中可能存在更少的临时文件。

窥孔优化器现在可以更好地查看以前的字节码。对于我们通过性能分析发现的序列，它非常适合用超级字节码替换字节码序列，并且可以在维护去优化要求的情况下实现。

LoadIc;Star 和 LdaGlobal;Star 的潜在窥孔优化，以减少分派字节码的数量。这种模式似乎在基准测试中反复出现。

寄存器恒定负载的窥孔优化，例如用新的字节码 LdrSmi 替换 LdaSmi;Star。与 LdaConstant 类似；Star 可与 LdrConstant 互换。

LdaZero;Star r1;LdaZero;Star r2 的窥孔优化，以移除第二个和后续的 LdaZero。这也可以通过将 LdaZero 视为加载累加器等效的 “魔法” 寄存器来完成。由于帧布局，我们在寄存器空间中的参数和本地 / 临时变量之间存在差距。

基本块边界的具体化在某些情况下会具体化后继块中未使用的临时对象。可选的第二个优化器可以执行一次传递以消除这些，并在 REO 消除临时寄存器后压缩剩余的临时寄存器空间中的间隙。

REO 主要保留对用户可见寄存器的更新，以便调试正确。如果知道调试器未附加，则可以更积极地删除更多寄存器和计算上不必要的加载和存储。使用不同的代码进行调试和优化执行可能没有吸引力，但在技术上是可行的。

解决 11 个 mjsunit 测试失败中的源位置问题。

附录 I - 赋值风险 #

当表达式中的中间结果可能会通过对表达式中的项进行进一步评估来修改时，寄存器机器会出现赋值风险。它们不会出现在堆栈计算机中，因为中间结果被压入堆栈并且不可用。具有潜在危险的示例表达式是：

var x = 10;
var y = x + (x = 3);

在 y 的赋值中涉及二元运算符的评估。首先评估左侧，然后右侧修改左侧使用的术语。对此的简单解决方案是在评估左手时将其分配给临时寄存器，然后评估右手。只有在计算表达式中的后续项并与前面的项发生冲突时，才需要临时寄存器。在没有冲突的情况下，生成器会向临时对象发出不必要的移动。

我们尝试通过三种不同的方式来避免分配风险：

• 两次传球。字节码生成器积极地将术语解析为寄存器，并在评估表达式时维护一个冲突集。冲突集包含表达式评估期间读取的所有寄存器，如果在评估期间对这些寄存器中的任何一个进行写入，则会发生危险。如果发现冲突，则在完全评估表达式后进行第二次传递。在第二遍中，临时对象用于有冲突的寄存器。我们不喜欢这种方法的两次通过性质，也不喜欢两次通过时对寄存器的不同处理。
• 当发现写入时，在右侧使用临时项。该技术维护了冲突集并将 rhs 上的寄存器写入动态重新映射到临时变量，然后在计算表达式后更新寄存器值。这无法处理涉及命名和键控加载和存储操作的情况。
• 基于票证的方案导致在检测到冲突时为左侧的中间值分配临时值。它目前由于与 2 类似的原因而失败，并且同样难以推理。

所有这三种技术都给本已复杂的字节码生成器增加了相当大的复杂性。他们很难推理和测试。我们当前的字节码生成器实现采用最保守的方法，始终为中间表达式值分配临时值。很容易推理并导致 v8 测试套件的正确执行。

这是一个更微妙的分配风险示例 (mjsunit/regress/regress-286.js)：

function test() {
  var o = [1];
  var a = o[o ^= 1];
  return a;
};

它返回值 1。此函数转换为以下字节码：

由于 AST 访问者方法的嵌套，我们发现这个例子很难在字节码生成器中干净地解决。字节码生成器使用两个临时文件发出正确的解决方案。 REO 等价物保持相同的正确性，但有一个临时字节码和 3 个少数字节码。

参考 #

• Ignition: Register Equivalence Optimization - Google DocsIgnition: Register Equivalence Optimization - Google Docs - 中英对照