值编号

# 值编号 来源：https://bernsteinbear.com/blog/value-numbering/ 欢迎回到编译器领域。今天我们来讨论*值编号*，它类似于 SSA，但更强大。静态单赋值（SSA）为每个值赋予名称：每个表达式都有一个名称，每个名称恰好对应一个表达式。它将像这样的程序： `` x = 0 x = x + 1 x = x + 1 ``（其中变量`x`在程序文本中被多次赋值）转换为这样的程序： `` v0 = 0 v1 = v0 + 1 v2 = v1 + 1 `` 其中每次对`x`的赋值都被替换为一个全新名称的赋值。这很棒，因为它清晰地展示了两个`x + 1`表达式之间的差异。虽然它们在文本上看起来相似，但计算的是不同的值。第一个计算出 1，第二个计算出 2。在这个例子中，无法通过代入变量来重用`x + 1`的值，因为这里的`x`是不同的。但如果我们看到 SSA 形式中有两个“文本上”相同的指令呢？这比非 SSA 形式更有希望，因为转换为 SSA 形式已经移除了（大部分）状态依赖性。什么时候可以重用结果？在编译时就能确定两条指令在运行时总是产生相同结果的过程，称为*值编号*。 ## 消除公共子表达式 为了理解值编号，让我们在上面的 IR 片段中添加两条新指令 v3 和 v4。 `` v0 = 0 v1 = v0 + 1 v2 = v1 + 1 v3 = v0 + 1 # 新增 v4 = do_something(v2, v3) # 新增 `` 在这个新片段中，v3 看起来和 v1 一样：都是将 v0 与 1 相加。假设我们的加法操作是理想的数学加法，那么我们可以绝对地重用 v1；无需再次计算加法。我们可以将 IR 重写为： `` v0 = 0 v1 = v0 + 1 v2 = v1 + 1 v3 = v1 v4 = do_something(v2, v3) `` 这类似于 JavaScriptCore 和其他一些编译器使用的销毁式并查集表示法：优化器不会急于重写所有使用点，而是留下一个小的“面包屑”——一个`Identity`/`Assign`指令1（https://bernsteinbear.com/blog/value-numbering/#fn:cinder）。然后我们可以运行复制传播遍（“并查集清理”？）得到： `` v0 = 0 v1 = v0 + 1 v2 = v1 + 1 v4 = do_something(v2, v1) `` 太好了。但这是如何发生的呢？优化器如何识别“文本上相同”的可重用指令候选？一般来说，IR 中并没有实际的文本（https://pointersgonewild.com/2011/10/07/optimizing-global-value-numbering/）。一种流行的解决方案是计算每条指令的哈希值。然后，具有相同哈希值（并且还需要比较相等性以防止冲突）的任何指令都被认为是等价的。这称为*哈希表共享*。 为了弄清楚这一切，我阅读了几种不同的实现。我特别喜欢Maxine 虚拟机（https://maxine-vm.readthedocs.io/en/stable/）的实现。例如，这里是大多数二元操作的`valueNumber`（哈希）和`valueEqual`函数，为了清晰稍作修改： `` public abstract class Instruction extends Value { ... } // 二元操作的基础类 public abstract class Op2 extends Instruction { // 每个二元操作都有一个操作码和两个操作数 public final int opcode; // (IMUL, IADD, ...) Value x; Value y; @Override public int valueNumber() { // 还有其他字段，但只有操作码和操作数会被哈希。 // 总是设置至少一位，以防哈希值回绕到零。 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，则表示该指令不希望参与值编号。为什么指令可能会选择退出值编号呢？ ## 纯与不纯 如果一条指令不是“纯的”，它可能会选择退出值编号。有些指令是不纯的。纯度取决于观察者，但一般来说，它意味着指令除了对其操作数进行简单的计算外，不与外部世界的状态交互。（重复使用/缓存`printf`意味着什么？）从数组对象加载也不是一个纯操作2（https://bernsteinbear.com/blog/value-numbering/#fn:heap-ssa）。加载操作隐式依赖于内存状态。此外，即使数组是已知常量，在某些运行时系统中，加载也可能引发异常。改变异常抛出的源代码位置通常是不被鼓励的。像 Java 这样的语言通常在其规范中规定异常抛出的位置。 现在我们只处理纯操作，但稍后还会回来讨论这一点。我们通常也希望优化不纯操作！我们将从最简单的值编号形式开始，它只在线性指令序列上操作，比如基本块或跟踪。 ## 局部值编号 让我们构建一个局部值编号（LVN）的小型实现。我们将从直线代码开始——没有分支或任何棘手的东西。编译器对控制流图（CFG）的大多数优化都是“从上到下”迭代指令3（https://bernsteinbear.com/blog/value-numbering/#fn:order），看来我们这里也可以做同样的事情。 根据我们目前优化虚构 IR 片段所看到的，我们可以这样做： - 初始化一个从指令编号到指令指针的映射 - 对于每条指令`i` - 如果`i`希望参与值编号 - 如果`i`的值编号已经在映射中，则将程序中所有指向`i`的指针替换为映射中对应的值 - 否则，将`i`添加到映射中 记住，查找并替换并不是字面意义上的查找并替换，而是类似于： `` instr.opcode = "Assign" instr.operands[0] = replacement `` 或者 `` instr.make_equal_to(replacement) `` （如果你一直在关注toy 优化器（https://pypy.org/categories/toy-optimizer.html）系列） 这个只有几行的函数（只要你已经有一个哈希映射和一个并查集可用）就足以构建局部值编号了！真实的编译器也是以这种方式构建的。如果你不相信我，可以看看来自Maxine（https://maxine-vm.readthedocs.io/en/stable/）值编号实现的这段稍作编辑的片段。它包含了我们刚讨论的所有组件：遍历指令、映射查找和某些替换。 `` // 局部值编号 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); } } `` 仅此而已就能让你走得很远。各种形状的代码生成器往往会在生成的代码中留下重复的杂乱计算，而这将轻松处理它们。但有时，你的计算会分散到控制流中——跨越多个基本块。那么该怎么办呢？ ## 全局值编号 为整个函数计算值编号称为*全局值编号*（GVN），它需要处理控制流（if、循环等）。我并不是说对于整个函数，我们逐个块地运行局部值编号。全局值编号意味着表达式可以在块之间去重和共享。 让我们逐个情况处理控制流。首先是上面的简单情况：一个块。在这种情况下，我们可以从上到下进行值编号，一切正常。 第二种情况也合理处理：一个块流入另一个块。在这种情况下，我们仍然可以从上到下进行。我们只需要找到一种迭代块的方法。如果我们不打算在块之间共享值映射，那么顺序无关紧要。但由于全局值编号的目的是共享值，我们必须以拓扑顺序（逆后序 RPO）迭代它们。这确保前驱块在后继块之前被访问。如果你有`bb0 -> bb1`，我们必须先访问`bb0`，然后访问`bb1`。由于 SSA 和 CFG 的工作方式，第二个块可以“向上查找”到第一个块并使用其中的值。 要让全局值编号工作，我们必须在开始处理`bb1`之前复制`bb0`的值映射，以便重用指令。可能像这样： `` value_map = ValueMap() for block in function.reverse_post_order(): local_value_numbering(block, value_map) `` 然后表达式可以在块之间累积。`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（https://bernsteinbear.com/blog/value-numbering/#fn:compute-doms），但这有点超出本博客的范围。如果我们假设 CFG 中可用支配信息，我们就可以将其用于全局值编号。而这正是——你猜对了——Maxine VM 所做的。它按逆后序迭代所有块，执行局部值编号，并从支配块传入值映射。在这种情况下，它们的方法`dominator`获取*直接支配者*：所有支配当前块的块中“最近”的支配块。 `` public class GlobalValueNumberer { final HashMap valueMaps; final InstructionSubstituter subst; ValueMap currentMap; public GlobalValueNumberer(IR ir) { this.subst = new InstructionSubstituter(ir); // 逆后序 List blocks = ir.linearScanOrder(); valueMaps = new HashMap(blocks.size()); optimize(blocks); subst.finish(); } void optimize(List blocks) { int numBlocks = blocks.size(); BlockBegin startBlock = blocks.get(0); // 初始值映射，嵌套深度为 0 valueMaps.put(startBlock, new ValueMap()); for (int i = 1; i < numBlocks; i++) { // 遍历所有块 BlockBegin block = blocks.get(i); BlockBegin dominator = block.dominator(); // 创建具有增加嵌套深度的新值映射 currentMap = new ValueMap(valueMaps.get(dominator)); // << 在此插入局部值编号 >> // 为后继块记住值映射 valueMaps.put(block, currentMap); } } } `` 就是这样！这就是 Maxine 的GVN 实现（https://github.com/beehive-lab/Maxine-VM/blob/e213a842f78983e2ba112ae46de8c64317bc206e/com.sun.c1x/src/com/sun/c1x/opt/GlobalValueNumberer.java）的核心。我喜欢它简洁得惊人。用很少的代码，你就可以消除大量重复的纯 SSA 指令。 这在循环中仍然有效，但有一些注意事项。来自 Briggs GVN 的 p7（https://bernsteinbear.com/assets/img/briggs-gvn.pdf）： > φ-函数需要特殊处理。在编译器可以分析块中的 φ-函数之前，它必须已经为所有输入分配了值编号。这并非在所有情况下都可行；具体来说，任何输入的值沿着回边（相对于支配树）流动的 φ-函数输入都无法获得值编号。如果 φ-函数的任何参数尚未分配值编号，则编译器无法分析该 φ-函数，它必须为结果分配一个唯一的、新的值编号。 它还讨论了消除无用的 φ-函数，这是可选的，但会增强全局值编号遍：它使更多信息透明化。 但如果我们想要处理不纯指令呢？ ## 状态管理与失效 像 Java 这样的语言允许在方法内从`this`/`self`对象读取字段，就好像字段是变量名一样。这使得以下代码很常见： `` class CPU { private void exec_adc() { int result_int = regA + fetched_data + flagCARRY; byte result = (byte) result_int; // ... int a = result_int ^ regA; int b = result_int ^ fetched_data; // ... regA = result; } } `` 这里对`regA`和`fetched_data`的每个引用都是对`this.regA`或`this.fetched_data`的隐式引用，语义上是对象字段加载。你可以在字节码中看到它（https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:java,selection:(endColumn:19,endLineNumber:14,positionColumn:19,positionLineNumber:14,selectionStartColumn:19,selectionStartLineNumber:14,startColumn:19,startLineNumber:14),source:'class+CPU+%7B%0A++++private+void+exec_adc()+%7B%0A++++++++int+result_int+%3D+regA+%2B+fetched_data+%2B+flagCARRY%3B%0A++++++++byte+result+%3D+(byte)+result_int%3B%0A++++++++//+...%0A++++++++int+a+%3D+result_int+%5E+regA%3B%0A++++++++int+b+%3D+result_int+%5E+fetched_data%3B%0A++++++++//+...%0A++++++++regA+%3D+result%3B%0A++++%7D%0A%0A++++int+regA%3B%0A++++int+fetched_data%3B%0A++++int+flagCARRY%3B%0A%7D%0A'),l:'5',n:'0',o:'Java+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:java2501,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:java,libs:!(),options:'',overrides:!(),selection:(endColumn:19,endLineNumber:40,positionColumn:1,positionLineNumber:1,selectionStartColumn:19,selectionStartLineNumber:40,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+jdk+25.0.1+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)（感谢 Matt Godbolt）：