追查 antcc 中的 -O2 性能劣化

# 追踪 antcc 中一个 -O2 反优化问题 来源: https://386s.org/w/lua-antcc-pessimization/ 2026 Oct 12 — [c](https://386s.org/tags/c)、[compilers](https://386s.org/tags/compilers)、[optimization](https://386s.org/tags/optimization)、[antcc](https://386s.org/tags/antcc) 最近我在为我的 C 编译器 [antcc](https://codeberg.org/lsof/antcc/) 做生成代码效率的基准测试，注意到一个令人担忧的现象——在一个简单的 Lua 基准测试中： ``` 基准测试 优化级别 运行时间 lua 无 1.048s lua -O1 1.077s lua -O2 1.410s ``` "优化后的"构建反而更慢了。目前我的编译器还没有实现太多优化，所以我并不期望看到巨大的提升，但慢了 1.4 倍绝对不应该发生。[^1] antcc *确实*实现了的一个优化是内联，这通常是影响最大的编译器优化之一，通常能全面提升各项基准测试的表现。 ## 内联？ 我的第一个想法是：内联的启发式规则和阈值非常简单，基本上没有经过调优，所以可能是过于激进了，导致代码体积膨胀，进而引发严重的指令缓存冲突。如果我禁用内联，反优化现象似乎就消失了，这可以支持该理论。但这个解释并不太令人满意，而且我想修复它，所以我做了更深入的调查。 主要的罪魁祸首在函数 `luaV_execute`，其代码在 -O2 下膨胀到了约 43KB，**比 -O1 构建大约 2.4 倍**。 现在，[这个函数](https://github.com/lua/lua/blob/c33b1728aeb7dfeec4013562660e07d32697aa6b/lvm.c#L1127)是 Lua VM 的主字节码解释器循环，这类函数是编译器最难处理的函数之一：它是一个巨大的函数，包含一个热循环、大量分支和控制流、图中嵌套着不同的热路径和冷路径，一个错误的优化器或寄存器分配决策就可能拖慢整个循环……[^2] 基线函数本身就很难优化，但这并不能解释这个现象。调整内联阈值似乎也没有帮助：要么很少东西被内联（如 -O1），二进制大小和性能基本不变；要么小函数开始被内联，反优化就发生了。 具体来说，以下函数被内联了（有些在多个实例中）：`floatforloop`、`lessequalothers`、`lessthanothers`、`luaV_idiv`、`luaV_mod`、`luaV_modf`、`luaV_shiftl`、`luaV_tointegerns`，以及它们各自的被调用者。在上面的 Lua 源代码链接中可以看到，这些都是一些相当小的简单函数。 查看最终生成的代码没有太大帮助，但检查 IR[^3] 揭示了一些有趣的事情：在所有优化之后，-O2 的 IR 仅比 -O1 **大 11%**。这怎么会在二进制中放大到 **2.4 倍**的差异呢？ ## 代码生成？ 在优化之后、代码生成之前运行的最终阶段是[指令选择](https://en.wikipedia.org/wiki/Instruction_selection)和[寄存器分配](https://en.wikipedia.org/wiki/Register_allocation)。指令选择主要负责确保指令操作数已准备好降级到机器代码，但临时变量仍然保持为虚拟寄存器。例如，对于 x86-64，它会建模内存操作数，并将这样的 IR 指令序列： ``` ;; int *ptr, res; i64 %t2 = shl %index, 2 ptr %t3 = add %ptr, %t2 ;; res = ptr[index] i32 %res = load i32 %t3 ``` 转换为： ``` i32 %res = load i32 addr [%ptr + %index * 4] ``` 它还做其他事情，比如为某些操作引入寄存器约束，但不管怎样，由于它只展开成这样的小段指令序列，不可能是问题的原因。 ## 寄存器分配 寄存器分配是将虚拟临时变量映射到目标架构物理寄存器的过程。对于上面的代码片段，可能得到： ``` i32 RAX = load i32 addr [RSI + RDX * 4] ``` 它被编译为 x86 指令 `mov eax, DWORD PTR [rsi + rdx * 4]`。 问题在于虚拟临时变量是无限的，而寄存器数量有限，所以你必须选择哪些变量获得哪些寄存器，当所有变量不够用时，其中一些不得不放到栈上，这被称为*spilling*（溢出）。大多数操作要求值在寄存器中，所以被溢出的变量经常需要在寄存器之间来回移动。或者更糟的是，在某些情况下它们需要在两个不同的栈槽之间移动。 antcc 有一个基础的[线性扫描寄存器分配](https://c9x.me/compile/bib/Wimmer10a.pdf)实现。如果寄存器压力很大，很多临时变量被溢出，可能仅仅为了在栈和寄存器之间搬运值就会产生大量指令。 确实，比较 -O2 下寄存器分配前后的 IR 体积增长，+11% 的差异在寄存器分配后变成了 **+70%** 的膨胀……查看反汇编代码，`luaV_execute` 中**超过 40%** 的指令仅仅是栈⇄寄存器的 `mov` 操作。这真的很糟糕，某些被内联的东西一定导致了这种可怕的寄存器压力和溢出，但原因并不明显。 所以让我们检查寄存器分配前的 IR： ``` << 寄存器分配前 >> function luaV_execute : void(struct lua_State *, struct CallInfo *) abi: (RDI, RSI) .... ptr %4613 = add %0, 56 ptr %5340 = add %0, 40 b @2 @2: ; preds: @1, @892 ; loop depth: 1 i64 %4489 = phi @1 undef, @892 %3124 i64 %3030 = phi @1 undef, @892 %3065 i64 %4636 = phi @1 undef, @892 %2287 i64 %4764 = phi @1 undef, @892 %3869 i64 %2874 = phi @1 undef, @892 %3929 i64 %2694 = phi @1 undef, @892 %3981 i64 %4872 = phi @1 undef, @892 %3804 i64 %2297 = phi @1 undef, @892 %3497 i64 %5062 = phi @1 undef, @892 %3158 i64 %2208 = phi @1 undef, @892 %3145 i64 %2161 = phi @1 undef, @892 %4191 i64 %5275 = phi @1 undef, @892 %4225 i64 %5290 = phi @1 undef, @892 %4252 i64 %1791 = phi @1 undef, @892 %4370 i64 %3813 = phi @1 undef, @892 %3195 i64 %3807 = phi @1 undef, @892 %4403 .... ``` 哦。这看起来很奇怪。 ## SSA 与 phi 我的编译器和大多数现代后端一样，使用[静态单赋值](https://en.wikipedia.org/wiki/Static_single-assignment_form)（SSA）表示。在这种形式中，直线代码如（我使用类似 C 的伪代码来简化）： ``` x = a + b x = x + y # 重新赋值 x use(x) ``` 变为： ``` x1 = a + b x2 = x1 + y # 新的定义 use(x2) ``` 也就是说，没有变量变更指令。这种表示对编译器来说很好的原因是，它简化了各种数据流分析，并且比非 SSA 形式允许更强大的优化。 对于控制流，数据流合并在 IR 中是显式的： ``` if (cond) { x = a + 1 } else { x = b - 1 } use(x) ``` 在 SSA 形式中表示为： ``` if (cond) B0: { x1 = a + 1 } else B1: { x2 = b - 1 } x3 = phi(B0: x1, B1: x2) use(x3) ``` 这个神奇的 `phi` 指令[^4]的结果是 `x1` 或 `x2` 的值，取决于控制流走了哪个分支。同样的方法可以应用于在循环中被修改的变量： ``` i = 0 while (cond) { use(i) i += 1 } ``` 在 SSA 中： ``` i0 = 0 Entry: while (cond) { LoopBegin: i_l = phi(Entry: i0, LoopEnd: i_n) use(i_l) i_n = i_l + 1 LoopEnd: } ``` 从字面上看，`phi` 函数似乎在 `i_n` 定义之前就引用了它，但重要的是，该值仅在循环回边（`LoopEnd --> LoopBegin`）时被取用，在那个点上 `i_n` 的值是可用的。 这里需要意识到的一个关键是，`i_l` 这个临时变量是循环 phi，它的生命周期覆盖整个循环，因为它的值用于计算下一次迭代。 回到 Lua 的 IR 转储： ``` @2: ; preds: @1, @892 ; loop depth: 1 i64 %4489 = phi @1 undef, @892 %3124 i64 %3030 = phi @1 undef, @892 %3065 ... ``` 先忽略 undef，注意 `; preds` 行表示该基本块的前驱：`@1`（函数的开始）和 `@892`（数百个块之后：主解释器循环的结束）。这意味着我们有 16 个 phi，其生命周期覆盖了整个循环。 这就是造成大量寄存器压力、破坏寄存器分配、并导致栈溢出流量造成代码体积大幅膨胀的原因。 那么，这些 phi 是什么？它们来自哪里？为什么会有 `undef`…… ## mem2reg C 程序不会以 SSA 形式开始，所以它们必须经过一个转换阶段。我在编译器中借鉴了 clang/LLVM 的术语和设计： 1. 变量总是从虚拟栈槽开始，用 `alloca` 伪指令定义。[^5] 因为 C 中局部变量可以取地址[^6]，这直接建模了 C 抽象机对"自动变量"的定义：一个可以读写的可寻址物理栈槽。 2. 变量读取变成内存 `load` 指令，写入变成 `store` 指令。 3. 之后，`mem2reg` 阶段收集地址未逃逸的栈 `alloca`（意味着它们只用于编译器可观察的直接读写），并将它们"提升"为 SSA 临时变量，在需要的地方插入 phi 指令。 所以这样的 C 代码： ``` int x; x = foo(); ... if (x < 0) { x = -x; } return x; ``` 最初生成的 IR 类似： ``` @1: ptr %x = alloca 4 bytes i32 %t1 = call foo() store i32 %x, %t1 ... i32 %t2 = load i32 %x bool %cond = lth %t2, 0 br %cond, true -> @2, false -> @3 @2: i32 %t3 = load i32 %x i32 %t4 = neg %t3 store i32 %x, %t4 b @3 @3: i32 %t5 = load i32 %x ret %t5 ``` mem2reg 将其转换为： ``` @1: i32 %x1 = call foo() ... bool %cond = lth %x1, 0 br %cond, true -> @2, false -> @3 @2: i32 %x2 = neg %x1 b @3 @3: i32 %x3 = phi @1 %x1, @2 %x2 ret %x3 ``` 我跳过了其中最棘手的部分，即在一般情况下知道何时何地插入这些 phi 指令。基本上有两种算法，我使用的是来自论文["Simple and Efficient Construction of SSA Form" (Braun et al, 2013)](https://pp.ipd.kit.edu/uploads/publikationen/braun13cc.pdf) 的方法。 其要点是：以逆后序（RPO）遍历控制流图（CFG）；当你看到一个写入时，按块记录当前定义；当你看到一个读取时，查找该定义或递归查询前驱的定义，在查找发现不同定义时插入 phi。循环更棘手：因为回边前驱尚未被访问，你必须插入一个临时 phi 并在之后解析。 C 中有一个几乎所有后来的语言都将其作为"坏主意"而移除的特性：允许变量不初始化。例如： ``` int x; if (foo()) { int y = bar(); x = y; } use(x); ``` 在控制流合并之后，`x` 是 `phi(未初始化, y)`。这就是我 IR 中的 `undef`。在我的 mem2reg 中，它被引入的方式是：如果递归的"读取当前定义"函数一路到达函数开头都没有找到定义，就给它 `undef`。（之后，对 `undef` 的移动和操作可以被有效地优化掉。） ## 这在 Lua 中是如何表现的 那么 Lua 解释器是在读取未初始化的变量吗？其实不是。看看解释器函数中一些受影响的代码： ``` vmcase(OP_SHRI) { TValue *rb = vRB(i); int ic = GETARG_sC(i); lua_Integer ib; if (tointegerns(rb, &ib)) { pc++; setivalue(s2v(ra), luaV_shiftl(ib, -ic)); } vmbreak; } // 还有几个其他指令遵循同样的模板 ``` 关键是 `tointegerns` 宏，它进而调用函数 `luaV_tointegerns`： ``` int luaV_tointegerns (const TValue *obj, lua_Integer *p, F2Imod mode) { if (ttisfloat(obj)) return luaV_flttointeger(fltvalue(obj), p, mode); // <- 这个被内联了 else if (ttisinteger(obj)) { *p = ivalue(obj); return 1; } else return 0; } ``` 在 -O2 下，这个函数和 `luaV_flttointeger` 被内联了，导致这样的展开（已简化）： ``` vmcase(OP_SHRI) { ... lua_Integer ib; // <--- 声明 int tointegerns_ret; if (ttisinteger(rb)) { ib = ivalue(rb); // <--- 写入 tointegerns_ret = 1; } else if (ttisfloat(rb)) { ... ib = (lua_Integer)fvalue(f); // <--- 写入 tointegerns_ret = 1; } else { tointegerns_ret = 0; } if (tointegerns_ret) { ... (使用 ib) } vmbreak; } ``` `mem2reg` 在每次内联之后都会运行。问题中的 `undef` 来自我标记的局部变量 `ib`。你可以看到，在内联函数返回 `1` 的每条路径中局部变量都被初始化了，但 `mem2reg` 无法将此与后面的 `if (tointegerns_ret)` 守卫关联起来，所以它看到了一个可能未初始化的读取。 但这*并不是*全部的故事！它解释了 `undef`，但没有解释为什么 phi 的生命周期覆盖整个循环。毕竟，这个局部变量作用域在循环中一个分支内的代码块里，它不应该跨越循环迭代…… ## 问题所在 最终我找到了根本原因：我在 mem2reg 中对"变量以未初始化开始"这个概念理解*过于*字面了。当它遇到一个 `alloca` 时，它没有为当前块给它一个定义。 这听起来是对的，算法中的递归查找在函数入口以 `undef` 终止。但回想循环的陷阱：当你遇到一个回边时，你不知道是否有后来的定义，因为你还没有访问整个循环，所以你插入一个临时 phi…… 本质上，我的 mem2reg 的行为就好像这样的代码： ``` int foo() { while (...) { int x; if (...) { x = bar(); } use(x); } } ``` 实际上是： ``` int foo() { int x; while (...) { if (...) { x = bar(); } use(x); } } ``` 在第二个函数中，`x` 的值跨迭代保留；而在第一个函数中，每次 `if` 分支未被采纳时，`x` 的值都是一个'全新的'未初始化值…… 这并不是一个错误编译：就 C 而言，这是没问题的，因为未初始化变量的值本来就不可合法使用。如果从栈分配变量的角度来看，这是一种合理的方法：x 的栈槽在整个函数中是固定的，不会在循环迭代之间重置，所以它保留了上一次迭代的值，无论那是什么，都无关紧要。 但在 SSA 形式下，这会生成类似这样的代码： ``` while (...) { %x = phi(undef, %x2) if (...) { %x1 = bar(); } %x2 = phi(%x, %x1) use(%x2); } ``` 正是这些循环 phi 导致了病态的寄存器分配。 修复只需一行： ``` --- a/src/ir_mem2reg.c +++ b/src/ir_mem2reg.c @@ -244,6 +244,8 @@ mem2reg(Function *fn) v->cls = k; v->i = var; sb.vars[var] = v; + v->curdefs[blk->id] = UNDREF; } else { sb.vars[var] = DEAD; } ``` 在 `alloca` 的位置将变量初始化为未定义（一个漂亮的矛盾修辞）确保了递归查找不会跨越循环回边并在循环头插入 phi。这就足以修复这个情况，这个改动让那个神秘的反优化消失了。 ## 结语 这个问题对于那些老式地在函数顶部声明所有变量的 C 代码仍然可能出现。可以通过使用 [Tarjan 算法](https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm)查找 phi 数据流的图强连通分量来检测循环，从而修复这个一般情况，并在将 phi 分类为冗余时利用这些 undef 语义；但我还没有实现这个。跳转线程化（jump threading）直接被用作分支条件的内联函数，或者更一般地，SSA 感知的 phi 跳转线程化，也可以修复那个分支关联问题——正是那个问题导致 `mem2reg` 看不到那些变量的支配性写入从而引入了 undef。 我使用了 AI 智能助手来……