值编号：用于消除公共子表达式的编译器优化技术

欢迎重返编译器的世界。今天，我们将探讨“值编号”这一概念——它与 SSA 有些相似，但又有所不同。

静态单赋值（SSA）为变量赋予了名称：每个表达式都有一个唯一的名称，而每一个名称都对应着且仅对应一个表达式。通过这种转换，我们可以将如下程序：

其中变量 x 在程序代码中被多次赋值，转化为如下形式：

其中对 x 的每一次赋值，都被替换为对一个全新的、全新的名字的赋值。

这种方法非常出色，因为它清晰地揭示了两个 x + 1 表达式之间的差异：尽管它们在文本上看起来几乎相同，但计算结果却截然不同——第一个表达式计算出 1，而第二个表达式则计算出 2。

在这个例子中，我们无法直接将某个变量的值代入到表达式中并重复使用 x + 1 的值，因为这两个表达式的 x 值是不同的。

那么，如果我们在 SSA 中看到两条“在文本上”完全相同的指令，会怎样呢？ 这听起来比非 SSA 的方式要更有前景，因为经过 SSA 形式的转换，原本复杂的程序状态得到了极大的简化。 那么，我们什么时候才能重新利用这些结果呢？

识别那些在编译时已知，但在运行时总是会产生相同值的指令，就称为“值编号”。

消除公共子表达式

为了更好地理解值编号，我们先在上述 IR 片段的基础上，新增两条指令：v3 和 v4。

在新片段中，v3 与 v1 的外观完全一致：都是将 v0 与 1 相加。假设我们的加法运算是一种理想的数学运算，那么我们完全可以复用 v1；无需再次进行加法运算。

于是，我们可以将 IR 重写为如下形式：

这与 JavaScriptCore 以及几款其他编译器所采用的破坏性联合查找表示法颇为相似——在该方法中，优化器并不会急于将所有用法都重新改写， 而是留下一些细微的“线索”。例如，Identity/Assign 指令1。

接下来，我们可以通过复制传播遍历（“联合查找清理”？）来完成这项工作，最终得到：

太棒了！但是，这一切究竟是如何实现的呢？ 优化器又是如何识别出那些“在文本上完全相同”的可重用指令候选的呢？ 一般来说，IR 中并没有真正的“文本”——或者说，我们根本无法从 IR 中直接找到“文本”。

一种常见的解决方案是为每条指令计算一个哈希值。 然后，只要两条指令拥有相同的哈希值（在发生冲突时，它们的哈希值也相等）， 就可以被视为等价的。这一过程被称为“哈希合并”。

在尝试理解这一切的过程中，我阅读了几种不同的实现方案。 其中，我特别喜欢Maxine VM 的实现方式。

以最常用的二元运算为例，这里提供了 valueNumber（哈希）和 valueEqual 函数，为了更清晰起见，我们对它们进行了略微修改：

值编号的其余实现部分假定：如果 valueNumber 函数返回 0，那么它就不希望被纳入值编号的考量范围。那么，为什么某些指令会选择不参与值编号呢？

纯函数 vs 不纯函数

如果一条指令不是“纯函数”，那么它可能选择不参与值编号。

有些指令并不纯粹。纯度因人而异，但通常来说，纯函数意味着这条指令不会与外界的状态发生交互， 除非是对操作数进行一些微不足道的计算。 （那么，“去重、缓存、复用 printf”又意味着什么呢？）

从数组对象中加载数据同样算不上纯粹的操作2。 加载操作往往隐含着对内存状态的依赖。 此外，即使数组的大小在运行时是已知常量，但在某些运行时系统中，加载操作仍可能引发异常。 通常情况下，改变异常发生的源位置是不被提倡的。 像 Java 这样的语言，其规范中往往会对异常的抛出位置作出明确的规定。

目前我们只专注于纯操作，不过稍后我们再回头讨论这个问题。事实上，我们常常也希望对不纯操作进行优化！

我们先从最简单的值编号形式入手——这种形式仅适用于线性指令序列，比如基本块或执行轨迹。

局部值编号

让我们来构建一个小型的局部值编号（LVN）实现。我们从直行代码开始——没有分支，也没有任何复杂的设计。

大多数编译器对控制流图（CFG）的优化操作都是从“自上而下”遍历指令3，而我们似乎也可以在这里做同样的事情。

根据我们迄今为止对这个虚构的 IR 片段所做的优化，我们可以这样处理：

• 初始化一个从指令编号到指令指针的映射表

• 对于每条指令 i

• 如果 i 想要参与值编号

• 如果 i 的值编号已经存在于映射表中，则将程序中所有指向 i 的指针，全部替换成映射表中的对应值

• 否则，将 i 添加到映射表中

记住，这里的“查找并替换”并不是字面意义上的“查找并替换”，而是类似这样的操作：

或者：

（如果你一直在跟随 玩具优化器系列的课程）

只要具备一个哈希表和一个联合查找结构，这个只需几行代码的函数就足以实现局部值编号！而真正的编译器也正是这样构建的。

如果你还不相信我，不妨看看 Maxine 的值编号实现中这段经过轻微修改的代码。它包含了我们刚才提到的所有组件：遍历指令、映射查找，以及一些替换操作。

仅仅依靠这一点，你就能取得相当大的进展。各种各样的代码生成器往往会在生成的代码中留下大量重复的计算，而这些计算正是导致代码效率低下的主要原因。

不过，有时你的计算会跨越多个控制流——贯穿多个基本块。那么，我们该怎么办呢？

全局值编号

为整个函数计算值编号，就称为全局值编号（GVN），而这需要我们处理控制流（如 if 语句、循环等）。我所说的“为整个函数计算值编号”，并不是仅仅逐个基本块进行局部值编号。 全局值编号意味着，表达式可以在各个基本块之间被去重、共享。

接下来，我们逐一来解决控制流的问题。

首先，我们来看上面提到的简单情况：只有一个基本块。在这种情况下，我们可以按照自上而下的顺序进行值编号，效果还不错。

第二种情况也同样可以轻松应对：一个基本块流入另一个基本块。在这种情况下，我们依然可以自上而下地进行遍历。我们只需要找到一种方法，来依次遍历各个基本块。

如果我们不打算在各个基本块之间共享值映射表，那么顺序就无关紧要。 然而，由于全局值编号的核心目标就是共享值，我们必须按照拓扑顺序（逆后序遍历， RPO）来遍历这些基本块。这样做能确保前驱节点在后继节点之前被访问。 如果存在 bb0 -> bb1，我们就必须先访问 bb0，然后再访问 bb1。

由于 SSA 和 CFG 的工作原理，第二个基本块可以“向上查询”第一个基本块，并利用其中的值。 为了让全局值编号正常运作，我们必须在开始处理 bb1 之前，先复制 bb0 的值映射表，以便能够复用这些指令。

也许可以这样：

这样一来，表达式就可以跨块累积。bb1 可以复用 bb0 已经计算好的 Add v0, 1，因为这些值仍然保存在映射表中。

不过，一旦出现控制流的分支，这种情况就会立刻失效。考虑以下的形状图：

我们将在该图中按照两种顺序之一进行遍历：A B C 或 A C B。无论哪种顺序，我们都会把所有这些内容添加到值映射表中——从一个基本块（比如 B）开始，而这个基本块其实并不属于它的兄弟基本块（比如 C）。

当我提到“不属”时，我的意思是“之前从未被计算过”。 这是因为我们要么先执行 A 再执行 B，要么先执行 A 再执行 C。不存在这样一种情况：我们先执行 B，再执行 C。

不过，让我们来看看第三种情况：当存在这样的世界时，也就是控制流的交汇点。 在这张图中，两个前驱基本块 B 和 C 都流入 D。在图中，B 总是流入 D，C 也总是在 D 流入。因此，迭代顺序是没有问题的，对吧？

然而，问题依旧存在。我们依然面临着和之前一样的“兄弟”问题：B 和 C 仍然无法共享值映射表。

当我们进入 D 时，还有一个奇怪的问题：我们到底是从哪里来的？ 如果我们是从 B 来的，那么我们可以复用 B 中的表达式；如果我们是从 C 来的，那么我们可以复用 C 中的表达式。但一般来说，我们并不能确切知道自己的前驱基本块究竟是哪个。

我们唯一可以确定的是，在 D 之前执行过的只有 A。这意味着，我们可以在 D 中复用 A 的值映射表，因为我们能够保证，所有进入 D 的执行路径，此前都曾经过 A。

这种关系被称为“支配关系”，也是我们将在本文中重点讨论的一种全局值编号模式的关键所在。 一个基本块始终可以使用任何支配它的基本块的值映射表。 为了完整性起见，在菱形图中，A 也支配着 B 和 C。

我们可以通过几种不同的方式来计算支配关系4，但这超出了这篇博客的讨论范围。 如果我们假设在控制流图中已经掌握了支配关系的信息，那么我们就可以利用这些信息来进行全局值编号。 而这也正是——你猜对了——Maxine VM 所做的。

它会按照逆后序遍历所有基本块，进行局部值编号，并从支配基本块的值映射表中逐步推进。 在这种情况下，它的“支配者”方法会直接获取当前基本块的“最近”支配者：即所有支配当前基本块的基本块中， 距离最近的一个支配者。

就这样！这就是 Maxine 的 GVN 实现的核心。我非常喜欢它的简洁性：只需寥寥几行代码，就能去除大量重复的纯 SSA 指令。

虽然这个方法同样适用于循环，但有一些需要注意的地方。正如 Briggs GVN 的第 7 页所指出的：

φ 函数需要特殊处理。在编译器分析一个基本块中的 φ 函数之前，它必须先为所有输入分配值编号。 然而，这并非在所有情况下都可行；特别是，那些值会沿着反向边（相对于支配树）流动的 φ 函数输入，无法获得值编号。如果 φ 函数的任何一个参数尚未被分配值编号，那么编译器就无法分析该 φ 函数，只能为结果分配一个独一无二的新值编号。

此外，文中还提到了消除无用的 φ 函数，这虽然是可选的，但也能让全局值编号的优化更加透明。

那么，如果我们想要处理不纯的指令呢？

状态管理与无效化

像 Java 这样的语言允许我们在方法中从 this/自我对象中读取字段，仿佛这些字段只是普通的变量名。因此，像下面这样的代码十分常见：

这些引用分别指向 regA 和 fetched_data，它们实际上隐含地指向 this.regA 或 this.fetched_data——从语义上讲，这相当于从对象中加载了一个字段。 你可以在字节码（感谢 Matt Godbolt）：

当你从 JVM 字节码直接构建一个 SSA IR 时，你会得到一堆看起来像这样的 IR：

几乎与字节码一模一样。尽管中间的代码无法修改 regA 字段（否则就需要重新加载），但我们仍然遇到了重复的加载操作。真让人沮丧。

我不想过多赘述这个问题，不过你可以通过以下方式，将“加载-存储转发”融入你的 GVN 实现中：

• 将加载-存储转发作为局部值编号的一部分，在每个基本块结束时清除值映射表中的内存信息，或者

• 在各个基本块之间持续追踪影响

你看，根本没有任何限制，让你在编译时跨块跟踪堆的状态。你只需要多做一些额外的记录工作。以我们基于支配关系的 GVN 实现为例，你可以：

1. 在每个基本块中追踪堆的写入影响

2. 在每个基本块 B 开始时，将所有基本块的“杀戮”集合，统一到其直接支配者的基本块中

3. 最后，从支配者的基本块的值映射表中移除那些被“杀死”的内容

这其实不算太糟。

Maxine 并没有进行全局内存跟踪，不过他们在从字节码构建 HIR 时，确实采用了有限形式的“加载-存储转发”：参见 GraphBuilder——该工具使用了 MemoryMap 来帮助追踪这些信息。

至少，他们不会在上面的示例中出现相同的重复 LoadField 指令！

至此，我们已经了解了一种值编号的方式及其对应的实现方案。那么，还有哪些其他的实现方式呢？

放眼世界

显然，如果你能使用一个统一的哈希表（Briggs GVN 的第 9 页）来存储表达式，而不是将值映射表局限于仅限于支配者可用的表达式，那么效果可能会更好。 不过，我们目前还不完全清楚这种做法的具体运作机制。

他们指出：

使用统一哈希表有一个重要的算法层面的后果。由于哈希表不再反映表达式的可用性，因此无法在线进行替换操作。

这让我第一次意识到，基于哈希的值编号，结合支配关系，其实只是对可用表达式分析的一种近似方法。

此外，还有一种完全不同的值编号方式，叫做“值分区”（Briggs GVN 的第 12 页）。另外，Allen Wang 在 康奈尔编译器课程上发表了一篇精彩的博客文章， 专门介绍了这一概念。我认为，这种方式主要取代了哈希值的计算环节，不过对于可用表达式这一部分， 你仍然需要借助其他手段。

Ben Titzer 和 Seth Goldstein 提供了一些不错的 CMU 的幻灯片。在这些幻灯片中，他们谈到了工作列表数据流的方法。 虽然这种方法的速度较慢，但它能为你提供更多的可用表达式，而不仅仅是单纯依赖支配者基本块。 我很好奇，这种方法与基于支配关系的哈希表相比，究竟有多大的差别？

Maxine 使用哈希表克隆技术，从支配者基本块中复制值映射表； 而像 Cranelift 这样的编译器，则使用scoped hash maps 来更高效地追踪这些信息。（不过，Amanieu 提醒说，你或许不需要使用 scoped hash map，而是可以直接在值映射表中为每个值打上标记，注明其来自哪个基本块， 同时通过快速检查忽略那些非支配性的值。 虽然支配关系的检查很有意义，但我还没有真正理解这种检查是如何影响可用表达式的集合的。 ）

你也许会想：这种算法在动态语言的 JIT 环境中真的有用吗？毕竟，一切都太动态了，不是吗？ 其实不然！JIT 期望通过消除大量的方法调用和动态行为，用保护器、假设以及更简单的操作来替代它们。 这些性能提升往往会导致大量重复的指令残留。 就在前几天，Kokubun 提交了一项< a href="https://github.com/ruby/ruby/pull/16654">类似值编号的 PR,旨在清理一些冗余的代码。

ART 在最近的一篇 博客文章中， 也分享了关于加速 GVN 的经验。

实现方案：

• Maxine

• ART

• V8 Hydrogen

• HHVM

• HotSpot C1

总结：点滴与细节

继续前行，为你的值赋予更多数字吧。

我和 Phil Zucker 一直就 SSI、GVN、无环图以及作用域联合查找展开过深入讨论。待补充总结。

无环图

交换律；规范化

在 GVN 中引入替代性表示方式

在 GVN 过程中，有向图与联合查找 cfallin.org/blog/2026/04/09/aegraph 进行规范化

github.com/bytecodealliance/rfcs/blob/main/accepted/cranelift-egraph.mdgithub.com/bytecodealliance/wasmtime/issues/9049github.com/bytecodealliance/wasmtime/issues/4371

部分冗余消除

1. 撰写这篇文章的时候，我刚刚意识到：原来一直以来，我都在疑惑 Cinder 为何没有使用联合查找来实现重写，而实际上，它早就已经用了！将指令 X = A + 0 优化为 X = Assign A 后，再通过复制传播将其替换，这与联合查找的效果是等价的。↩

2. 在某些形式的 SSA 中，比如堆-数组 SSA 或节点之海，由于内存表示已经被内嵌（或建模）进 IR 中，因此更容易实现去重加载。↩

3. 顺序稍微复杂一些：逆后序遍历（RPO）。此外，有一篇名为“用于全局数据流分析问题的简单算法”的论文，我目前还没有 PDF 版本，但该论文声称 RPO 是解决数据流问题的最佳算法。↩

4. 还有迭代式数据流方法（如 Cooper 的论文中所描述的 PDF）、Lengauer-Tarjan 的 PDF、Engineered Algorithm 的 PDF、混合/半-NCA 方法的 PDF……↩