yuqi-zheng
· also available in English · based on Matt Godbolt's blog ↗

编译器优化：Clang 的代数化简

compileroptimization

编译器不只是翻译器。它们是推理系统，能把数学知识应用到代码上，转换成更高效的等价形式。一个最令人印象深刻的演示是：Clang 能识别出一个简单的求和循环，用高斯求和公式取而代之 —— 完全消除了循环。

本文是 Matt Godbolt 的《Advent of Compiler Optimisations 2025》系列中的一篇。

示例

考虑一个函数，计算从 0 到 value - 1 所有整数的和：

int sum_up_to(int value) {
    int result = 0;
    for (int x = 0; x < value; ++x) {
        result += x;
    }
    return result;
}

这是 O(n) 的。循环执行 value 次，每次迭代做一次加法。当 value 很大时，它会耗费可观的时间。

GCC：聪明，但仍是循环

GCC 会应用若干优化。它会加一个边界检查来处理 value 为零或负数的情况，用 lea 指令做高效加法。最有趣的是，它会把迭代两两配对 —— 每次循环处理两个 x，利用恒等式 x + (x+1) = 2x + 1：

.L3:
    lea edx, [rdx + 1 + rax * 2]  ; result += 2x + 1（即 x + (x+1)）
    add eax, 2                    ; x += 2
    cmp edi, eax
    jne .L3

这把迭代次数减半，是一个有意义的优化 —— 但算法仍然是 O(n)，循环还在。

Clang：根本没有循环

Clang 在 -O2 下完全没有生成循环。整个函数被编译成寥寥几条算术指令：

lea   eax, [rdi - 1]     ; eax = value - 1
lea   ecx, [rdi - 2]     ; ecx = value - 2
imul  rcx, rax           ; rcx = (value - 1) * (value - 2)
shr   rcx                ; rcx /= 2
lea   eax, [rdi + rcx]   ; eax = value + rcx
dec   eax                ; eax -= 1
ret

它在计算：

result = value + ((value - 1) * (value - 2) / 2) - 1

用代数展开化简一下：

  value + ((value - 1)(value - 2) / 2) - 1
= value + (value² - 3·value + 2) / 2 - 1
= (2·value + value² - 3·value + 2 - 2) / 2
= (value² - value) / 2
= value · (value - 1) / 2

这正是高斯求和公式：从 0 到 n-1 的整数之和等于 n(n-1)/2。Clang 识别出了这个循环模式，并用闭式表达式替换了它。算法从 O(n) 变成了 O(1)。

Clang 是如何做到的

Clang 的优化器包含一个叫做标量演化（scalar evolution，SCEV）分析的优化 pass，它跟踪值在循环迭代之间的变化。在这个循环中：

  • x 每次迭代加 1（线性归纳变量）
  • result 每一步累加 x（一个线性序列的求和）
  • 连续整数 0 到 n-1 的和是一个众所周知的闭式

SCEV 识别出累加模式和循环边界，然后应用代数恒等式，把循环替换为公式。这并不是为”高斯求和”这一特例硬编码的逻辑 —— 而是归纳变量分析和代数化简框架的通用能力。

这种优化只在条件干净时才会触发：一个边界非负的简单循环、没有副作用、累加结构直截了当。带条件分支或提前退出的更复杂的循环不会触发这一变换。

既然公式都有了，为什么还要写循环？

一个自然会冒出来的问题是：如果公式是已知的，为什么还要在源代码里写循环？

在源码中保留循环的几个理由：

意图清晰。 循环对任何读者来说都一目了然：从 0 加到 value - 1。而公式 value * (value - 1) / 2 则需要读者”认出”它在算什么。对更复杂的累加，公式可能根本无法一眼看出。

通用性。 循环结构让你很容易添加条件、跳过某些值、改变累加运算。而公式则需要为每一种变体重新推导。

天然的正确性。 循环很难写错。公式在整数溢出、value == 0 的边界处理上有若干陷阱，需要小心。

相信编译器。 这个例子恰恰证明：编译器能从循环中推导出公式。开发者不必手工来做。

这种优化的边界

不是所有带累加的循环都会被转成闭式。Clang 在以下条件下会触发这种优化：

  • 循环边界是已知的，或能用循环变量表达
  • 累加值在迭代中呈现多项式模式
  • 循环体中没有函数调用、没有内存写入、没有其他副作用

当这些条件不满足时，Clang 会退回到常规循环，应用通常的优化。

小结

这个例子展示了现代编译器所应用的优化深度。Clang 的优化器不仅是在简化单条指令 —— 它在对整个循环做高层次的数学推理。通过代数分析，一个 O(n) 的算法被变成了 O(1)，源代码不必做任何改动。

写清晰、直接的代码。开启优化。必要时在 Compiler Explorer 上验证一下。编译器经常知道你代码中那些”看代码并不明显”的事情。