基于哈希的值编号算法：从局部到全局的冗余消除实践

值编号（Value Numbering）是编译器优化中识别并消除冗余计算的核心技术。其核心思想在于区分 "值" 与 "变量"—— 同一计算结果可能通过不同变量名存储，但本质上代表相同的值。通过为每个唯一计算分配标识符，编译器能够在保证语义正确的前提下，将多次出现的等价表达式替换为对已计算值的引用。

局部值编号的哈希实现

局部值编号（Local Value Numbering, LVN）作用于单个基本块内部，实现相对直接。工程实践中通常采用三表结构：值编号表（ValueNumberTable）将表达式映射到唯一值编号；哈希表（HashTable）支持 O (1) 时间复杂度的表达式查找；名称表（NameTable）则维护变量名与值编号的关联，处理块内的变量重赋值。

算法流程遵循单次遍历原则。对于每个操作指令，首先查询其操作数的值编号，然后构建哈希键（operator, VN (left), VN (right)）。若该键已存在于哈希表中，说明当前表达式与之前某计算等价，可直接复用其值编号；否则分配新值编号并插入哈希表。这种设计使得局部值编号在基本块规模较大时仍能保持高效。

实际实现中需考虑操作符的交换律特性。对于加法、乘法等可交换运算，应同时检查（op, VN (a), VN (b)）和（op, VN (b), VN (a)）两种键形式。此外，识别代数恒等式（如 a+0=a、a*1=a）可在值编号阶段直接传播已知值，无需生成新计算。

全局值编号的 SSA 依赖

当冗余表达式跨越基本块边界时，局部值编号无能为力。全局值编号（Global Value Numbering, GVN）通过分析整个控制流图来识别跨块的等价计算，另需引入静态单赋值形式（SSA）作为前置条件。

SSA 的核心约束是每个变量仅被赋值一次。原始代码中的多次赋值被转换为不同版本的新变量名，而在控制流汇合处通过 phi 节点合并不同分支的变量版本。这种表示消除了变量名歧义，使得全局值编号能够安全地追踪值在程序中的流动。

基于支配树的值编号算法（Dominator-Based Value Numbering）是工业编译器的常用方案。算法从入口块开始，沿支配树深度优先遍历。对于每个基本块，首先处理 phi 节点 —— 移除无意义（参数全相同）或冗余（与前面 phi 等价）的 phi；然后处理普通指令，使用与局部值编号相同的哈希查找逻辑；最后递归处理支配树子节点。离开块时需清理本块添加的哈希条目，避免污染兄弟分支的分析。

phi 节点的处理需要特别谨慎。算法需记录每个 phi 参数来自哪个前驱块，在遍历子节点时将其替换为对应的值编号。这种延迟替换机制确保了跨块值引用的正确解析。

扩展优化与工程权衡

值编号框架可自然扩展至常量折叠。维护变量名到常量值的映射后，当遇到算术运算且所有操作数均为常量时，可直接在编译期计算结果并插入新的常量定义。这种优化与值编号协同工作：折叠产生的常量获得新的值编号，后续可能触发更多冗余消除。

复制传播（Copy Propagation）也可纳入同一框架。对于标识指令（id），直接查找其参数的值编号并复用，消除不必要的变量复制链。在 SSA 形式下，这种查找简化为直接取用参数变量本身。

工程实现需在优化力度与编译时间之间权衡。全局值编号虽能发现更多优化机会，但 SSA 转换和支配树计算引入额外开销。实践中可采用分层策略：先执行轻量的局部值编号获取基础收益，再对热点函数启用全局分析。

落地参数与监控要点

部署值编号优化时，建议关注以下可配置参数：哈希表初始容量（避免频繁扩容）、最大基本块大小阈值（超大块可考虑分段处理）、以及代数简化规则集（根据目标架构特性定制）。

监控层面应追踪值编号消除的指令数量、哈希表命中率以及处理时间占比。异常低的命中率可能暗示哈希冲突严重，需调整哈希函数或增大表容量。同时需警惕 phi 节点膨胀问题 —— 过度的全局优化可能导致 phi 节点数量激增，反而增加后续阶段的处理负担。

值编号的价值在于以相对简单的数据结构实现显著的代码压缩。从教学用的 Bril 语言到生产级的 LLVM NewGVN，这一优化技术始终是编译器后端不可或缺的基础组件。

参考来源

• Cornell CS6120 课程博客《Global Value Numbering》，作者 Alexa VanHattum 与 Gregory Yauney，详细阐述了基于支配树的全局值编号实现。
• Briggs, Cooper, Simpson (1997) "Value Numbering"，经典论文提出了 dominator-based value numbering 算法框架。

compilers