Value Numbering：编译器优化中的“去重”艺术

背景

在编译器优化的广阔领域中，静态单赋值形式（Static Single Assignment, SSA）是一个基石。SSA 的核心思想是为程序中的每个值赋予唯一的名称：每一个表达式都有一个名字，且每个名字仅对应一个表达式。

这种变换将原本在源代码中多次赋值的变量（例如 x = 0; x = x + 1; x = x + 1）转化为一系列使用新鲜变量名的赋值（例如 v0 = 0; v1 = v0 + 1; v2 = v1 + 1）。SSA 的优势在于它清晰地揭示了不同表达式之间的差异。虽然 x + 1 在文本上看起来相似，但在 SSA 形式下，它们计算的是不同的值（第一个是 1，第二个是 2）。由于 x 的不同实例对应不同的 SSA 变量，因此无法直接复用前一个 x + 1 的结果。

然而，当我们在 SSA 形式下遇到两个“文本上”完全相同的指令时，情况就不同了。由于 SSA 转换消除了大部分的状态依赖性，如果两个指令在编译时已知在运行时总是产生相同的值，我们是否可以复用其中一个的结果？这种识别并复用等价指令的技术，就是 Value Numbering（值编号）。

核心内容

Value Numbering 的本质是识别那些在编译时已知在运行时必然产生相同值的指令，从而避免重复计算。为了理解这一过程，我们需要从局部优化扩展到全局优化，并深入其实现细节。

1. 局部值编号（Local Value Numbering, LVN）

让我们通过一个扩展的中间表示（IR）片段来看局部值编号的工作方式：

v0 = 0
v1 = v0 + 1
v2 = v1 + 1
v3 = v0 + 1 # 新增指令
v4 = do_something(v2, v3) # 新增指令

在这个片段中，v3 的指令 v0 + 1 与 v1 的指令在文本上完全相同。假设加法运算是理想的数学加法，那么 v3 和 v1 计算出的值必然相等。因此，我们可以安全地复用 v1 的结果，将 IR 重写为：

v0 = 0
v1 = v0 + 1
v2 = v1 + 1
v3 = v1 # 复用 v1
v4 = do_something(v2, v3)

这类似于 JavaScriptCore 等编译器使用的破坏性并查集（Union-Find）表示法。优化器并不急于重写所有使用点，而是留下一个 Identity 或 Assign 指令作为“breadcrumbs”（线索）。随后，通过运行副本传播（Copy Propagation）传递，可以进一步简化为：

v0 = 0
v1 = v0 + 1
v2 = v1 + 1
v4 = do_something(v2, v1)

2. 如何实现“文本相同”的判断？

在 IR 中，通常没有实际的“文本”。因此，一种流行的解决方案是为每条指令计算一个哈希值（Hash）。任何具有相同哈希值（且在发生冲突时比较相等）的指令都被视为等价。这种方法被称为 Hash-Consing。

以 Maxine VM 的实现为例，对于大多数二元运算，其值编号逻辑如下：

public abstract class Op2 extends Instruction {
    public final int opcode; // 操作码，如 IMUL, IADD
    Value x;
    Value y;

    @Override
    public int valueNumber() {
        // 仅对 opcode 和操作数进行哈希计算
        // 确保至少设置一位，以防哈希回绕为零
        return 0x20000000
             | (opcode
             + 7 * System.identityHashCode(x)
             + 11 * System.identityHashCode(y));
    }

    @Override
    public boolean valueEqual(Instruction i) {
        if (i instanceof Op2) {
            Op2 o = (Op2) i;
            // 检查操作码和操作数引用是否完全相同
            return opcode == o.opcode && x == o.x && y == o.y;
        }
        return false;
    }
}

如果 valueNumber() 返回 0，该指令将不参与值编号。这通常是因为该指令不是“纯”的（Pure）。

3. 纯操作与非纯操作

纯度（Purity） 是指指令是否仅对其操作数进行平凡计算，而不与外部世界状态交互。

• 非纯操作示例：
  • I/O 操作：如 printf，去重或缓存会导致输出行为改变。
  • 内存加载（Load）：从数组对象加载数据不是纯操作，因为它隐式依赖于内存状态。即使数组是常量，在某些运行时系统中，加载操作可能会抛出异常。改变异常抛出的源位置通常是不被允许的，因为像 Java 这样的语言在规范中规定了异常抛出的位置。

因此，局部值编号通常只处理纯操作。

4. 算法流程

局部值编号可以在基本块（Basic Blocks）或追踪（Traces）等线性指令序列上运行。算法流程如下：

1. 初始化一个从指令编号到指令指针的映射（Map）。
2. 遍历每条指令 i：
   • 如果 i 希望参与值编号：
     • 如果 i 的值编号已存在于映射中，则将程序中所有指向 i 的指针替换为映射中对应的值。
     • 否则，将 i 添加到映射中。

在 Maxine VM 的实现中，这一过程可以简化为：

// 局部值编号
BlockBegin block = ...;
ValueMap currentMap = new ValueMap();
InstructionSubstituter subst = new InstructionSubstituter();

// 访问此块的所有指令
for (Instruction instr = block.next(); instr != null; instr = instr.next()) {
    // 尝试值编号（使用 valueNumber() 和 valueEqual()）
    // 如果映射中存在之前的指令，则返回该指令；
    // 否则将当前指令插入映射并返回它
    Instruction f = currentMap.findInsert(instr);
    
    if (f != instr) {
        // 在并查集中记录替换关系
        subst.setSubst(instr, f);
    }
}

这段简短的代码足以构建局部值编号，能够消除代码生成器留下的许多重复计算。

5. 全局值编号（Global Value Numbering, GVN）

当计算跨越控制流（如 if、循环）分布在多个基本块时，就需要全局值编号。GVN 不仅要求在每个块内运行局部值编号，还要求表达式可以在块之间去重和共享。

为了共享值，我们必须按照拓扑顺序（即逆后序，Reverse Post Order, RPO）遍历基本块。这确保了前驱块（Predecessors）在后继块（Successors）之前被访问。例如，如果存在 bb0 -> bb1 的路径，必须先访问 bb0，再访问 bb1，以便将 bb0 中计算出的值编号传播给 bb1。

关键要点

• SSA 是基础：SSA 形式通过消除变量的多重赋值，使得识别相同的表达式变得更容易，为值编号提供了理想的前提。
• 哈希一致性（Hash-Consing）：通过计算指令的哈希值（结合操作码和操作数）来快速识别等价的指令，是值编号的核心技术。
• 纯度约束：值编号主要适用于“纯”操作。涉及副作用（如 I/O）或依赖外部状态（如内存加载、异常抛出）的操作通常被排除在外，除非有特殊的处理机制。
• 局部 vs 全局：
  • LVN：在基本块内按顺序处理，利用哈希映射查找并