过程间稀疏条件类型传播分析 Interprocedural Sparse Conditional Type Propagation

Interprocedural Sparse Conditional Type Propagation

Source | HN Comments

文章介绍了作者构建的针对类似Ruby动态语言的静态类型分析原型——过程间稀疏条件类型传播分析 (Interprocedural Sparse Conditional Type Propagation)。该分析通过跟踪跨函数的数据流，结合稀疏条件常量传播和有限高度格，实现对变量类型的精确推导，从而为编译器优化提供依据。文章还探讨了调用点敏感性、对象和方法查找等技术，并通过生成的“酷刑测试”评估了分析的扩展性，结果表明该分析在处理大型代码库时具有较好的性能。最后，作者开源了相关代码，并推荐了进一步学习程序分析的资源。

过程间稀疏条件类型传播分析 Interprocedural Sparse Conditional Type Propagation

2025-02-24 • Max Bernstein, Maxime Chevalier-Boisvert

现在 11 点了。你知道你的变量指向哪里吗？

def shout(obj)
 obj.to_s + "!"
end

仅仅看代码很难知道 obj 的类型。我们假设它有一个 to_s 方法，但许多类都定义了名为 to_s 的方法。我们调用的是哪个 to_s 方法？shout 的返回类型是什么？如果 to_s 没有返回 String，那就真的很难说了。

添加类型注解会有所帮助……但只是稍微。有了类型，看起来我们对每件事都了如指掌，但实际上并非如此。像许多其他面向对象的语言一样，Ruby 有一种称为继承的东西，这意味着像 Integer 和 String 这样的类型签名意味着该类的一个实例……或者该类的一个子类的实例。

此外，像 Sorbet 这样的渐进类型检查器（例如）具有诸如 T.unsafe 和 T.untyped 之类的功能，这使得可以向类型检查器撒谎。不幸的是，这些注释使类型系统在没有运行时类型检查的情况下变为不健全的，这使得它成为我们希望在程序优化中使用的一个糟糕的基础。（有关更多信息，请参阅这篇博客文章，了解它如何以类似的方式影响 Python。）

为了为 Ruby 这样的动态语言构建一个有效的编译器，编译器需要精确的类型信息。这意味着作为编译器设计者，我们必须自己动手，自己跟踪类型。

在这篇文章中，我们展示了一个非常小的 Ruby 子集的过程间类型分析。这种分析可以被足够高级的编译器用于程序优化。这不是 Shopify 正在做的事情，但我们分享这篇文章和附加的分析代码，因为我们认为你会觉得它很有趣。

请注意，此分析不是人们通常所说的类型推断引擎或类型检查器；与 Hindley-Milner（另见以前的文章）或类似的基于约束的类型系统不同，此类型分析跟踪跨函数的数据流。

这种分析可能能够识别 shout 的所有调用者，确定所有参数的 to_s 都返回 String，因此得出结论，返回类型是 String。所有这些都来自一个没有注解的程序。

这篇文章介绍之后的示例将使用比典型的 Ruby 程序更多的括号，因为我们还编写了一个迷你 Ruby 解析器，它不支持没有括号的方法调用。

静态分析

让我们从头开始。我们将回顾一些例子，然后继续进行代码和一些基准测试。

你知道这个程序返回什么类型吗？

没错，它是 Integer[1]。它不仅是一个 Integer，而且我们还有关于其在分析时可用的确切值的额外信息。这将在稍后派上用场。

那么这个变量呢？a 是什么类型？

a = 1

不是一个棘手的问题，至少现在还不是。它仍然是 Integer[1]。但是如果我们给它赋值两次呢？

a = 1
a = "hello"

啊。棘手。事情变得有点复杂。如果我们根据逻辑执行“时间”将程序分成几段，我们可以说 a 最初是 Integer[1]，然后变成 String["hello"]。这不是非常令人愉快，因为这意味着在分析代码时，你必须在分析中携带一些“时间”状态的概念。如果有一些东西重写输入代码，使其看起来更像这样，那就好多了：

a0 = 1
a1 = "hello"

然后我们可以随时轻松地区分这两个变量，因为它们有不同的名称。这就是静态单赋值 (SSA) 形式的用武之地。自动将你的输入程序转换为 SSA 引入了一些复杂性，但可以保证每个变量都具有单个不变的类型。这就是为什么我们分析 SSA 而不是其他形式的中间表示 (IR)。假设在这篇文章的其余部分中，我们正在使用 SSA。

让我们继续我们的分析。

以下程序中的变量具有哪些类型？

a = 1
b = 2
c = a + b

我们知道 a 和 b，因为它们是常量，那么我们可以将 a+b 常量折叠为 3 吗？某种程度上。在 Ruby 中，如果没有全局知识表明有人没有也不会修补 Integer 类或做各种其他讨厌的事情，那么就不能。

但是，让我们在这篇文章的其余部分中假装我们生活在一个不可能重新定义现有类的含义（记住，我们正在研究一种类似 Ruby 的语言，但具有不同的语义但相似的语法）或在运行时添加新类（这称为封闭世界假设）的世界中。在这种情况下，绝对有可能折叠这些常量。所以 c 的类型是 Integer[3]。

让我们把事情复杂化。

if condition
 a = 3
else
 a = 4
end

我们说过每个变量只会被赋值一次，但是 SSA 可以使用 Φ (phi) 节点来表示这样的程序。Phi 节点是特殊的伪指令，用于跟踪可能来自多个位置的数据流。在这种情况下，SSA 会在 if 之后放置一个，以将两个不同名称的变量合并为第三个变量。

if condition
 a0 = 3
else
 a1 = 4
end
a2 = phi(a0, a1)

当使用 if 表达式的返回值时，也会发生这种情况：

a = if condition
   3
  else
   4
  end

phi 函数用于合并多个输入值。

对于我们的分析，phi 节点除了计算其输入的类型联合之外，什么也不做。我们这样做是因为我们将类型视为它可以表示的所有可能值的集合。例如，Integer[3] 是集合 {3}。而 Integer 是无限的且难以放入内存的集合 {..., -2, -1, 0, 1, 2, ...}。

这使得 a (a2) 的类型类似于 Integer[3 or 4]，但是正如我们所看到的，该集合可能会无限增长。为了使用合理数量的内存并确保我们的分析在合理的时间内运行，我们必须限制我们的集合大小。这就是有限高度格的概念的由来。等等，别走开！一切都会好起来的！

我们使用格作为具有一点结构的集合。我们没有一个只是扩展和扩展和扩展的 union 操作，而是在每个集合级别给出一个有限数量的条目，然后它会溢出到下一个不太具体的级别。这有点像有限状态机。这是我们的类型格的一个子集的图：

类型格图与我们在演示静态分析中使用的格类似的示例格。底部是更具体的类型，顶部是不太具体的类型。箭头表示随着更多合并的发生，结果只能变得不太精确。

我们程序分析中的所有格元素都从 Empty（无法访问）开始，并逐步添加元素，随着它们的增长，遵循状态转换箭头。如果我们看到一个常量整数，我们可以进入 Integer[N] 状态。如果我们看到另一个 不同的 整数，我们必须丢失一些信息并转换到 Integer 状态。此状态象征性地表示 Integer 类的所有实例。像这样丢失信息是精度和分析时间之间的权衡。

为了将其带回到我们的例子中，这意味着 a（它合并了 Integer[3] 和 Integer[4]）在我们的格中将具有 Integer 类型。

让我们进一步复杂化事情。假设我们在分析时以某种方式知道条件为真，也许是因为它是一个内联常量：

a = if true
   3
  else
   4
  end

许多分析此程序的分析会看到 a 的两个具有不同值的输入，因此会继续得出结论，a 的类型仍然是 Integer——即使作为人类看着它，我们也知道 else 分支永远不会发生。可以在另一个分析中进行简化以删除 else 分支，但我们将使用 Zadeck 及其同事的一些出色的工作，称为稀疏条件常量传播 (SCCP)。

稀疏条件常量传播 Sparse conditional constant propagation

与许多基于抽象解释的分析不同，SCCP 使用类型信息来通知其基于工作列表的控制流图 (CFG) 探索。如果它从其他信息中得知分支指令的条件是一个常量，它不会探索条件的两个分支。相反，它只将相关的分支推送到工作列表上。

因为我们在 SSA (CFG) 中工作，所以我们将控制流分成基本块作为我们的粒度单位。这些基本块是指指令块，其中允许的唯一控制流是最后一条指令。

fn sctp(prog: &Program) -> AnalysisResult {
  // ...
  while block_worklist.len() > 0 || insn_worklist.len() > 0 {
    // Read an instruction from the instruction worklist
    while let Some(insn_id) = insn_worklist.pop_front() {
      let Insn { op, block_id, .. } = &prog.insns[insn_id.0];
      if let Op::IfTrue { val, then_block, else_block } = op {
        // If we know statically we won't execute a branch, don't
        // analyze it
        match type_of(val) {
          // Empty represents code that is not (yet) reachable;
          // it has no value at run-time.
          Type::Empty => {},
          Type::Const(Value::Bool(false)) => block_worklist.push_back(*else_block),
          Type::Const(Value::Bool(true)) => block_worklist.push_back(*then_block),
          _ => {
            block_worklist.push_back(*then_block);
            block_worklist.push_back(*else_block);
          }
        }
        continue;
      };
    }
    // ...
  }
  // ...
}

这给我们留下了一个只看到一个输入操作数 Integer[3] 的 phi 节点，这为我们在程序的后续部分中提供了更多的精度。最初的 SCCP 论文到此为止（毕竟论文有页面限制），但我们更进一步。我们不仅推理常量，还使用我们的完整类型格。我们以过程间的方式进行。

在我们继续研究更棘手的代码片段之前，让我们看一个过程间分析很重要的小例子。这里我们有一个函数 decisions，它有一个可见的调用点，并且该调用点传递了 true：

def decisions(condition)
 if condition
  3
 else
  4
 end
end
decisions(true)

如果我们只是孤立地看待 decisions，我们仍然会认为返回类型是 Integer。但是，如果我们让来自所有调用点的信息流入该函数，我们可以看到所有（一个）调用点都将 true 传递给该函数……因此我们应该只查看 if 的一个分支。

现在，熟悉 SCCP 的读者可能想知道这如何在过程间工作。根据定义，SCCP 需要预先知道哪些指令使用哪些其他指令：如果你了解有关输出指令 A 的新事实，则必须将此新信息传播到所有用途。在单个函数的控制流图中，这还不错。我们对定义和用途有充分的了解。当我们扩展到多个函数时，它变得更加困难。在此示例中，我们必须将 condition 参数标记为正在传递的所有（当前常量）实际参数的用途。

但是我们如何知道调用者呢？

过程间 SCCP Interprocedural SCCP

让我们从应用程序的入口点开始。这通常是某个地方的 main 函数，该函数分配一些对象并调用一些其他函数。这些函数可能会依次调用其他函数，依此类推，直到应用程序终止。

这些调用和返回形成一个图，但我们静态地不知道它——我们在分析开始时不知道它。相反，当我们发现调用边缘时，我们必须逐步构建它。

在以下代码段中，我们将从入口点开始分析，在此代码段中，入口点是 main 函数。在其中，我们看到了对 foo 函数的直接调用。我们将 foo 标记为由 main 调用——不仅仅是由 main 调用，而是由 main 中的特定调用点调用。然后，我们将 bar 函数的开头——它的入口基本块——排队到块工作列表中。

def bar(a, b)
 a + b
end
def foo()
 bar(1, 2) + bar(3, 4)
end
def main()
 foo()
end

在某个时刻，分析会将 foo 的入口基本块从工作列表中弹出并分析 foo。对于每个对 bar 的直接调用，它将创建一个调用边缘。此外，因为我们传递了参数，它会将 1 和 3 连接到 a 参数，将 2 和 4 连接到 b 参数。它会将 bar 的入口块排队。

此时，我们正在 a 参数（以及 b 参数）处合并 Integer[1] 和 Integer[3]。这有点像过程间 phi 节点，我们必须在我们的类型格上进行相同的并集操作。

不幸的是，这意味着我们将无法为对 bar 的任何调用折叠 a+b，但我们仍然会得到 Integer 的返回类型，因为我们知道 Integer+Integer=Integer。

现在，如果有第三个对 bar 的调用传递了 String，那么每个调用点都会丢失。我们最终会在每个参数上得到 ClassUnion[String, Integer]，更糟糕的是，函数结果为 Any。我们甚至不会得到 ClassUnion[String, Integer]，因为我们没有将每个调用点分开，所以从分析的角度来看，我们可能正在查看 String+Integer，它没有已知的类型（事实上，它可能会引发异常或其他什么）。

但是如果我们保持每个调用点分开呢？

敏感性 Sensitivity

这种事情通常被称为 something -敏感性，其中 something 取决于你对分析进行分区的策略。敏感性的一个例子是 调用点敏感性 call-site sensitivity。

特别是，我们可能希望使用 1-调用点-敏感性 来扩展我们当前的分析。这个数字，我们可以拨动 k 变量以获得更高的精度和更慢的分析，是我们想要在分析中跟踪的“调用帧”的数量。这对于非常常用的库函数（例如 to_s 和 each）很有用，其中每个调用者可能完全不同。

在上面非常不具代表性的示例中，1-调用点-敏感性将允许我们将整个程序完全常量折叠为 Integer[10]（因为 1 + 2 + 3 + 4 = 10）。哇！但这会减慢分析速度，因为它需要复制分析工作。为了并排粗略的步骤：

没有调用点敏感性/0-调用点-敏感性（我们目前拥有的）：

看到使用参数 1 和 2 调用 bar
将 bar 的参数标记为 Integer[1] 和 Integer[2]
看到 bar 添加节点，其左右操作数是常量
将 bar 添加结果标记为 Integer[3]
将 bar 返回标记为 Integer[3]
将 bar(1, 2) 的结果标记为 Integer[3]
看到使用参数 3 和 4 调用 bar
将 bar 的参数标记为 Integer 和 Integer（我们必须联合）
将 bar 添加结果标记为 Integer（参数不是常量）
将 bar 返回标记为 Integer
看到 foo 自己的添加，其操作数是 Integer 和 Integer
将 foo 的添加标记为返回 Integer

具有 1-调用点-敏感性：

看到从函数 foo 使用参数 1 和 2 调用 bar
从 foo 创建一个新的调用上下文
将 foo0->bar 参数标记为 Integer[1] 和 Integer[2]
看到 foo0->bar 添加节点，其左右操作数是常量
将 foo0->bar 添加结果标记为 Integer[3]
将 foo0->bar 返回标记为 Integer[3]
将 bar(1, 2) 的结果标记为 Integer[3]
看到使用参数 3 和 4 调用 bar
从 foo 创建一个新的调用上下文
将 foo1->bar 参数标记为 Integer[3] 和 Integer[4]
将 foo1->bar 添加结果标记为 Integer[7]
将 foo1->bar 返回标记为 Integer[7]
看到 foo 自己的添加，其操作数是常量 Integer[3] 和 Integer[7]
将 foo 的添加标记为返回 Integer[10]

看到我们必须为每个调用点分析一次 bar，而不是合并调用输入和返回并向上移动格吗？这会减慢分析速度。

还有 上下文敏感性 ，它是关于根据给定调用点的某些计算属性而不是它在程序中的位置来划分调用的。也许它是参数类型的元组，或者删除了任何常量值的参数类型的元组，或者完全是其他的东西。理想情况下，它应该能够快速生成并在不同的其他调用点之间进行比较。

还有其他类型的敏感性，如 对象敏感性 、 字段敏感性 等——但由于这有点偏离了主要文章，而且我们没有实现它们中的任何一个，因此我们将它们作为线索供你阅读。

让我们回到主要的 Interprocedural SCCP，并在组合中添加一些技巧：对象。

对象和方法查找 Objects and method lookup

Ruby 不仅仅处理整数和字符串。这些是更大的对象系统的特例，其中对象具有实例变量、方法等，并且是用户定义的类的实例。

class Point
 attr_accessor :x
 attr_accessor :y
 def initialize(x, y)
  @x = x
  @y = y
 end
end
p = Point.new(3, 4)
puts(p.x, p.y)

这意味着我们必须开始跟踪静态分析中的所有类，否则在回答诸如“变量 p 是什么类型？”之类的问题时，我们将很难做到精确。

知道 p 的类型很好——也许我们可以在 SCCP 中折叠一些 is_a? 分支——但如果我们能够跟踪对象上实例变量的类型，分析会变得更有用。这将让我们回答问题“p.x 是什么类型？”

根据这篇论文 (PDF)，至少有两种方法可以考虑我们如何存储这种信息。一种，该论文称之为 基于字段的 field-based，根据它们的名称统一字段类型的存储。因此，在这种情况下，所有可能写入任何字段 x 的内容可能会落入同一个存储桶并合并在一起。

另一种，该论文称之为 字段敏感的 field-sensitive，根据接收者（持有该字段的对象）类统一字段类型的存储。在这种情况下，我们在写入和读取 p.x 时会区分给定程序点上 p 的所有可能类型。

我们选择在我们的静态分析中采用后一种方法：我们使其具有字段敏感性。

fn sctp(prog: &Program) -> AnalysisResult {
  // ...
  while block_worklist.len() > 0 || insn_worklist.len() > 0 {
    // Read an instruction from the instruction worklist
    while let Some(insn_id) = insn_worklist.pop_front() {
      let Insn { op, block_id, .. } = &prog.insns[insn_id.0];
      // ...
      match op {
        Op::GetIvar { self_val, name } => {
          let result = match type_of(self_val) {
            Type::Object(classes) => {
              // ...
              classes.iter().fold(Type::Empty, |acc, class_id| union(&acc, &ivar_types[class_id][name]))
            }
            ty => panic!("getivar on non-Object type {ty:?}"),
          };
          result
        }
      }
    }
  }
}

这意味着我们必须做两件事：1) 跟踪每个类的每个实例变量 (ivar) 的字段类型，然后 2) 在给定的 ivar 读取时，合并来自接收者的所有可能类的所有字段类型。

不幸的是，它也创建了一个复杂的 用途 uses 关系：任何 GetIvar 指令都是可能影响它的所有可能的 SetIvar 指令的用途。这意味着如果我们看到一个 SetIvar 写入某个类 T 和字段名称 X 的 T.X，我们必须去重新分析所有可能从该类读取的 GetIvar（并将此信息像往常一样递归地传播到其他用途）。

所有这些合并、重流和图探索听起来很慢。即使使用非常有效的数据结构，也有很多迭代在进行。它到底有多慢？为了回答这个问题，我们构建了一些“酷刑测试”，以人为地创建一些最坏情况的基准。

测试它的扩展性：生成酷刑测试 Testing how it scales: generating torture tests

在编译器设计的任何相关问题中，一大挑战在于很难找到大型的、具有代表性的基准。这有很多原因。大型程序往往带有许多依赖项，这使得它们难以分发、安装和维护。一些软件是闭源的或受版权保护的。在我们的例子中，我们正在使用我们创建的一个迷你语言来进行实验，所以根本没有用该语言编写的真实程序，那么我们该怎么办呢？

要问的第一个问题是：我们试图衡量什么？在实施和测试此分析时，我们的主要担忧之一是了解它在执行时间方面的表现如何。我们希望确信该分析可以应对大型具有挑战性的程序。我们从经验中得知，YJIT 在运行 Shopify 的生产代码时编译了 9000 多个方法。如果 YJIT 编译了 9000 个“热”方法，那么有人可能会猜测完整的程序可能包含 10 倍或更多的代码，所以假设 100,000 个方法。因此，我们认为，虽然我们没有为我们的迷你语言手工制作的这种规模的程序，但我们可以生成一些具有类似规模的合成程序。我们认为，如果我们的分析可以应对旨在既大又具有挑战性的“酷刑测试”，那么这会让我们对它能够应对“真实”程序有很好的信心。

为了生成合成测试程序，我们想要生成一个函数调用图，这些函数相互调用。虽然对于我们的类型分析来说，这并不是绝对必要的，但我们希望生成一个不是无限递归且总是终止的程序。这并不难实现，因为我们可以编写一段代码来直接生成有向无环图 (DAG)。请参阅这篇文章末尾描述的 loupe 存储库中的 random_dag 函数。此函数生成一个有向图，该图具有一个“根”节点和多个相互连接的子节点，因此节点之间没有循环。

对于我们的第一个酷刑测试（参见 gen_torture_test），我们生成了一个由 200,000 个相互调用的函数组成的图。一些函数具有叶节点，这意味着它们不调用任何人，这些函数直接返回一个常量整数或 nil。具有被调用者的函数将对其子项的返回值求和。如果子项返回 nil，它将向总和添加零。这意味着非叶函数包含依赖于类型信息的动态分支。

作为第二个酷刑测试（参见 gen_torture_test_2），我们想评估我们的分析在多态和超多态调用点方面的表现如何。多态调用点是必须处理多个类的函数调用。超多态调用点是必须处理大量类（例如 5-10 个或更多）的调用点。我们首先生成大量的合成类，我们选择了 5000 个类，因为这似乎是大型真实世界程序可能包含的类数量的真实数字。为了方便起见，每个类都有 10 个实例变量和 10 个具有相同名称的方法（这使得生成代码更容易）。

为了生成多态和超多态调用点，我们生成每个类的实例，然后我们从该集合中采样随机数量的类实例。我们使用 Pareto 分布来采样类的数量，因为我们认为这与真实程序的通常结构方式相似。也就是说，大多数调用点是单态的，但少数调用点是高度超多态的。我们生成 200 个随机 DAG，每个 DAG 有 750 个节点，并使用随机数量的类实例调用每个 DAG 的根节点。然后，每个 DAG 通过其所有子项传递它从根节点接收的对象。这会创建大量的多态和超多态调用点。我们的合成程序包含接收多达 144 个不同类的调用点。

第二个酷刑测试中每个 DAG 的结构与第一个酷刑测试类似，区别在于每个函数都调用它作为参数接收的对象的随机选择的方法，然后在 DAG 中调用它的子函数。方便的是，由于对于每个类，方法始终具有相同的名称，因此很容易选择一个我们通过构造知道在所有类上都定义了的随机方法。这会创建更多的多态调用点，这就是我们想要进行压力测试的内容。每个类的方法都是叶子方法，它们可以返回 nil、一个随机整数或一个随机选择的实例变量。

它到底如何扩展？ How does it scale really?

使用酷刑测试生成器，我们生成了两个程序：一个有类，一个没有类。

具有类的程序有 175,000 个可访问函数，总共生成了 205,000 个函数，300 万条指令和超多态（最多 144 个类）方法查找。我们在一个单核上在 2.5 秒内完成了分析。

没有类的程序有 200,000 个函数，我们在一个单核上在 1.3 秒内分析了它。

现在，这些数字在绝对意义上并没有多大意义——人们有不同的硬件、不同的代码库等——但在相对意义上，它们意味着这种分析比没有分析更容易处理。它不需要运行 数小时。而且我们的分析甚至没有特别优化。我们实际上对分析运行的速度感到惊讶。我们最初希望分析可以在具有 20,000 个方法的程序上在不到 60 秒内运行，但我们可以比预期快得多地分析大约 10 倍大小的程序。这使得它看起来很可能该分析可以在大型手工制作的软件上工作。

添加对象敏感性或增加调用点敏感性的 k 可能会大大减慢速度。但是，由于我们知道分析速度非常快，因此似乎可以想象我们可以有选择地拆分/专门化内置方法的调用点，以在特定位置添加敏感性，而不会使运行时间增加很多。例如，在具有 Array 类上的方法的语言（例如 Ruby）中，我们可以对所有 Array 方法调用进行拆分，以提高这些高度多态函数的精度。

总结 Wrapping up

感谢您阅读我们的小型大型静态类型分析原型。我们已将代码发布在 GitHub 上作为与本文一起使用的静态配套工件，仅此而已。这是我们构建的一个实验，但不是更大项目的前奏，也不是我们期望其他人贡献的工具。

如果您想阅读更多关于程序分析的广阔世界的信息，我们建议搜索诸如控制流分析 (CFA) 和 points-to 分析之类的术语。这是 Ondřej Lhoták 的精彩讲座 (PDF)，它对该领域进行了介绍。