spent all day in a haze, blowin’ my mind with global value numbering.
——Adrian Sampson
听了一个关于此算法的报告，主讲人的口音一股芒果味，让人感到略微忍俊不禁的同时也使我小小地思乡了一把。
跟 LVN 类似，GVN 的本质是基于哈希的操作，它尝试用一条指令处理一组重复，或者说冗余的指令（它们计算相同的值），根据具体情况不同，将其替换或者作为新值加入值表中。GVN 通过寻找具有相同操作和相同输入的代数恒等式或指令来找到这些重复指令集合。类似 LVN，GVN 的架构也是有利于常量折叠的，像其他表达式一样，GVN 会对常量表达式进行值编号。在这里，我们通过哈希表来查找具有相同操作和相同输入的两个指令。在大多数程序中，同一个变量会被赋值多次；相同的输入要求相同的值，而不是相同的变量名。因此，GVN 严重依赖于静态单赋值 (SSA) 形式。GVN 用一条指令替换一组等价的指令，然而这条替换指令并没有被放置在任何基本块中（或者说，考虑到 GVN 会随机选择一个块，结果程序显然是不正确的）。可以看到，它的过程跟 LVN 的相似点实在是太多了。
GCM 的后续传递仅根据指令的依赖边来选择正确的放置位置。由于 GCM 忽略了原始调度，所以 GVN 不需要构建一个正确的调度。
最后，GVN 速度很快，只需要对程序进行一次传递。
值编号技术将程序中的指令分成计算相同值的组，具体的细节我在关于 LVN 的文章里已经讨论过了，其实在 GVN 的视角下是差不多的过程。我们知道，值编号技术是一个简单的基于哈希表的自下而上方法。我们访问每条指令一次，使用一个哈希表来确定该指令是否应该与之前访问的某些指令位于同一个分区中（也就是前面叙述的所谓“计算相同值的组”）。以前，这种方法在 LVN 算法中得到了很大的成功。现在，我们通过简单地忽略基本块边界，将它扩展为全局值编号技术 GVN。
GVN 使用了以下算法：
- 使用逆后序方法（Reverse PostOrder，RPO）遍历 CFG 的依赖边，访问每个指令。
- 注：逆后序遍历可以保证对一个 node 的访问一定在其子节点之前，避免指令替换导致发生段错误。
- 关于逆后序遍历的算法细节，这个博客讲得不错：有向图的遍历讨论
- 在每条指令尝试折叠常数时，使用代数恒等式，或者通过查找我们构造的哈希表找到与之等价的指令。
- 哈希表允许我们在常数时间内将相同的 value-number 哈希键赋给等价的指令。
- 由于此时我们在进行全局优化，因此这个哈希表不会在基本块边界被重置。
- 事实上，基本块在这一阶段根本没有发挥作用。
使用 RPO 的动机是显然的：在大多数情况下，指令的输入都是在对指令本身进行值编号之前进行值编号的，使用逆后序遍历可以使得指令被替换时，替换值已经在 IR 中被定义过，这样一来就可以最大程度上防止 GVN 过后指令使用了未定义值作为操作数的情况（此时会引发段错误 Segmentation Fault）。循环结构有可能会引起结果的异常，因为我们没有到达一个固定的点，此时运行第二遍 GVN 可能是有利可图的。不过这句话是论文里的论述，根据实践的经验，pass 一遍通常就够了，值表的操作特性使得指令可以最大程度上被替换。
了解了值编号技术的前置知识后这一块还是蛮好理解的。
参考：
- Cliff Click, Global Code Motion Global Value Numbering, 1995