跳到内容

类型推断

摘要

概览

类型推断通过以下方式实现：分析值、根据这些分析结果预测操作将产生哪些类型、根据类型预测插入类型检查，然后尝试根据类型检查构建关于值类型的类型证明。

考虑此示例，以说明 JavaScript 类型推断和优化的动机。

o.x * o.x + o.y * o.y

假设在使用此代码的上下文中，'o' 是一个对象，它确实具有属性 'x' 和 'y'，并且这些属性没有什么特别之处——特别是它们不是访问器。我们还假设 'o.x' 和 'o.y' 通常返回双精度浮点数（doubles），但有时可能返回整数——JavaScript 没有内置的整数值概念，但为了效率，JavaScriptCore 会将大多数整数表示为 int32 而不是 double。为了理解类型推断的问题及其在 JavaScriptCore 中的解决方案，首先考虑如果 JavaScript 引擎对 'o'、'o.x' 或 'o.y' 没有信息时它必须做什么会很有用。

表达式 'o.x' 必须首先检查 'o' 是否对属性访问有任何特殊处理。它可能是一个 DOM 对象，而 DOM 对象可能会以不明显的方式拦截对其属性的访问。如果它没有特殊处理，引擎必须在对象中查找名为 "x" 的属性（其中 "x" 字面上是一个字符串）。对象只是将字符串映射到值或访问器的表格。如果映射到访问器，则必须调用该访问器。如果不是访问器，则返回值。如果在 'o' 中未找到 "x"，则对 o 的原型重复此过程。本节不涵盖优化对象访问所需的推断。表达式 'o.x * o.x' 中的二进制乘法操作必须首先检查其操作数的类型。任一操作数都可能是对象，在这种情况下必须调用其 'valueOf' 方法。任一操作数都可能是字符串，在这种情况下必须将其转换为数字。一旦两个操作数都适当地转换为数字（或者如果它们已经是数字），引擎必须检查它们是否都是整数；如果是，则执行整数乘法。这可能会溢出，在这种情况下将执行双精度浮点数乘法。如果任一操作数是双精度浮点数，则两者都转换为双精度浮点数，并执行双精度浮点数乘法。因此 'o.x * o.x' 可能返回整数或双精度浮点数。对于通用的 JavaScript 乘法，无法证明它将返回哪种数字以及该数字将如何表示。表达式 'o.x * o.x + o.y * o.y' 中的二进制加法操作必须大致按照乘法进行，不同之处在于它必须考虑其操作数是字符串的可能性，在这种情况下会执行字符串连接。在这种情况下，我们可以静态地证明这不是事实——乘法必须返回一个数字。但加法仍然必须对两个操作数进行整数与双精度浮点数的检查，因为我们不知道乘法表达式返回的是哪种类型。因此，加法也可能返回整数或双精度浮点数。JavaScriptCore 类型推断的直觉是，如果我们能猜测流向操作的类型，那么我们就可以很有可能地判断数字操作（如加法或乘法）将返回何种类型，以及它将采取哪条路径。这形成了一种归纳步骤，适用于通常不操作堆的操作：如果我们能预测它们的输入，那么我们就能预测它们的输出。但归纳需要一个基本情况。在 JavaScript 操作的情况下，基本情况是获取非局部值的操作：例如，从堆中加载值（如 'o.x'）、访问函数的参数或使用函数调用返回的值。为简单起见，我们将所有此类非局部值称为堆值，并将所有将堆值放入局部变量的操作称为堆操作。对于参数，我们将函数序言视为一种“堆操作”，它将参数“加载”到参数变量中。我们通过使用值剖析来引导关于类型预测的归纳推理：LLInt 和 Baseline JIT 都将记录在任何堆操作处看到的最新值。每个堆操作都只关联一个值剖析桶，并且每个值剖析桶将只存储一个最新值。

JavaScriptCore 类型推断的粗略观点是，我们将每个值剖析的最新值转换为一种类型，然后应用归纳步骤将这种类型传播到函数中的所有操作。这为函数中每个产生值的操作提供了类型预测。所有变量也都会进行预测性类型化。

实际上，JavaScriptCore 在每个值剖析中都包含第二个字段，它是一种类型，用于界定所见值的一个随机子集。这种类型使用 SpeculatedType（简称 SpecType）类型系统，该系统在 ​SpeculatedType.h 中实现。每个值剖析的类型最初为 SpecNone——即对应于无值的类型。你也可以将其视为底部（参见 ​Lattice），或“矛盾”。当 Baseline JIT 的执行计数器超过阈值时（参见 ​JIT.cpp 中的 JIT::emitOptimizationCheck），它将生成一个新类型，以同时界定上次的类型和最新值。它还可能选择调用 DFG，或者选择让基线代码运行更长时间。我们的启发式算法倾向于后者，这意味着当 DFG 编译启动时，每个值剖析通常会具有一个界定多个不同值的类型。

将从值剖析中推断出的 SpecType 传播到函数中的所有操作和变量，是使用标准的 ​前向数据流公式（作为流不敏感不动点实现）进行的。这是 DFG 编译的最初阶段之一，仅在 Baseline JIT 根据其执行计数决定某个函数最好执行优化代码时才会被激活。参见 ​DFGPredictionPropagationPhase.cpp。

在函数中的每个值都标记了预测类型后，我们根据这些预测插入推测性类型检查。例如，在数字操作（如 'o.x * o.y'）中，我们会在乘法的操作数上插入推测为双精度浮点数的检查。如果推测检查失败，执行将从优化的 DFG 代码转回到 Baseline JIT。这会起到证明 DFG 中后续代码类型的作用。考虑如果 'a' 和 'b' 都具有 SpecInt32 作为其预测类型，简单的加法操作 'a + b' 将如何分解。

check if a is Int32 -> else OSR exit to Baseline JIT
check if b is Int32 -> else OSR exit to Baseline JIT
result = a + b // integer addition
check if overflow -> else OSR exit to Baseline JIT

此操作完成后，我们知道：

  • 'a' 是一个整数。
  • 'b' 是一个整数。
  • 结果是一个整数。

对 'a' 或 'b' 的任何后续操作都不需要检查其类型。对结果的操作也是如此。后续检查的消除是通过第二次数据流分析实现的，简称为 DFG CFA。与关注构建类型预测的预测传播阶段不同，CFA 关注构建类型证明。CFA，位于 ​DFGCFAPhase.cpp 和 ​DFGAbstractInterpreterInlines.cpp 中，遵循流敏感前向数据流公式。它还实现了稀疏条件常量传播，这使得它有时能够证明值是常量，以及证明它们的类型。

综合来看，表达式 'o.x * o.x + o.y * o.y' 将只需要对从 'o.x' 加载的值和从 'o.y' 加载的值进行类型检查。之后，我们知道这些值是双精度浮点数，并且我们知道只需要发出一个双精度浮点数乘法路径，然后是一个双精度浮点数加法。当与类型检查提升相结合时，DFG 代码通常会在每次堆加载时最多执行一次类型检查。