
CompCert(GitHub)是一个用 Rocq 和 OCaml 编写的经过形式化验证的 C 编译器。与 gcc 或 clang 一样,它将 C 编译为汇编,并在过程中对程序进行优化以使其更快;不同之处在于,CompCert 证明了这些优化在其形式化语义下保持了程序的行为。你将一个 C 程序送入前端,它通过一系列优化和中间表示对程序进行变换,一路下降到 x86-64 汇编代码。这些在已验证流水线中的每一次变换(在编译器术语中也称为 pass),要么在 Rocq 中实现,要么由一个经过验证的验证器检查,并被证明在 CompCert 的 C 和 x86-64 形式化语义下保持程序行为:即 C 程序含义以及每条 x86-64 指令作用的精确数学定义。最后,一个机器校验的定理确保生成的汇编保持了源 C 程序的一种允许行为,前提是源程序在这些语义下没有未定义行为。1 这使得 CompCert 特别适合安全关键软件——在这类软件中正确性与性能同等重要——因为 GCC 和 LLVM 等主流编译器已被证明会悄悄生成错误的代码。234
然而,形式化验证目前伴随着陡峭的运行时代价。例如,CompCert 基准测试(一套随 CompCert 发布的测试程序)的运行速度比用 gcc -O2 编译时大约慢 28%,而 PolyBench 循环嵌套基准测试大约慢 55%。5
对于这一差距,一种常见的理论是 CompCert 对 C 和 x86-64 的严格且相当简单的语义模型,它排除了 GCC 用来优化的一些假设:
- 有符号整数溢出。C 标准将其留为未定义,因此 GCC 假设它永远不会发生;例如,它可以将 i + 1 > i 视为恒为真并简化循环计数器。CompCert 的语义将溢出定义为回绕,因此它不能做出该假设。
- 基于类型的别名。C 的别名规则让 GCC 可以假设 int 和 float 永远不会指向同一内存,因此它可以在通过另一个指针进行存储的过程中将某个值保留在寄存器中。CompCert 的内存模型不包含这些规则。
- 融合乘加。GCC 可能将 a * b + c 合并为单条 FMA 指令,这更快且只舍入一次。CompCert 对每个浮点运算分别舍入。
- SIMD。GCC 对循环进行向量化,以每条指令处理多个元素。CompCert 的 x86-64 模型没有向量指令。
我想知道这些语义限制是否真的解释了 CompCert 为何慢,或者 CompCert 只是缺少许多标准编译器优化和后端代码生成打磨。而如果差距主要是缺少 pass,
- 证明生成是瓶颈吗?(CompCert 最初发布于 2008 年……)
- AI 智能体能否在没有任何人工干预的情况下,在 Rocq 中找到、实现并证明这些变换?(数学领域的最新进展表明可以……)
我们所有的 pass、证明和基准测试脚本均可在 github.com/UT-InfraAI/CompCert 获取。
1. 检验民间理论:是语义模型的问题吗?
在改动 CompCert 之前,我们在 GCC 上检验了语义模型假说。CompCert 语义中的每项主要限制在 GCC 中都有一个对应的标志来禁用相应优化:
| 限制 | 在 CompCert 中 | GCC 标志 |
|---|---|---|
| 有符号整数溢出 | 定义为回绕 | -fwrapv |
| 基于类型的别名 | 内存模型中无这些规则 | -fno-strict-aliasing |
| 融合乘加 | 每个运算分别舍入 | -ffp-contract=off |
| SIMD | x86-64 模型中没有向量指令 | -fno-tree-vectorize |
形式化验证的 C 编译器性能能与 gcc -O2 相当吗?
如果 CompCert 的形式语义是主要瓶颈,那么在 GCC 中禁用这四项功能就会抹平 GCC 的大部分领先优势。
然而,这并不是我们看到的情况。即使在 gcc -O2 中限制这些标志之后,CompCert 在 CompCert 基准测试上仍慢 26%,在 PolyBench 套件上慢 54%。这意味着语义模型不是主要瓶颈。大部分差距来自 CompCert 的规则已经允许、但 CompCert 从未执行的优化。
2. 汇编手术:那么时间到底花在哪里了?
我们首先需要知道哪些缺失的变换实际上造成了真实硬件上的性能差距。思路很简单:我们取一个慢基准测试的 CompCert .s 汇编输出,手动编辑它以一次应用一个缺失的优化。然后重新汇编二进制文件,对照参考结果检查其输出,并计时。一旦我们知道哪些优化真正有帮助,就可以在 CompCert 中证明并实现它们。多亏了编码智能体,这并没有听起来那么痛苦。
以下是我们通过这种方式发现的一些缺失优化:
spectral 中的循环携带重载
CompCert 的一个基准测试 spectral,大部分时间花在一个内层循环中,该循环将乘积累加到数组元素 Au[i] 中:
/* spectral.c: inner product loop */
for (j = 0; j < n; j++)
Au[i] += u[j] / (double)((i + j) * (i + j + 1) / 2 + i + 1);
正常情况下,CompCert 的公共子表达式消除(CSE)遍(backend/CSE.v)会避免重新加载程序已经拥有的值。但 CSE 只在一段只有单一入口的代码内记住值,而循环顶部有两个入口:来自循环之前的代码,以及来自上一次迭代末尾。因此 CSE 在每次迭代开始时都会忘记它所知道的一切。结果,CompCert 在每一次内层循环迭代中都会从内存重新加载 Au[i],对其相加,再存回内存:
# CompCert (126 ms): reload and store on every iteration; excerpt
.L102: movsd 0(%rdx,%rax,8), %xmm1 # reload Au[i] from memory
mulsd %xmm4, %xmm0 # multiply matrix term by u[j]
addsd %xmm0, %xmm1 # add product to accumulator
movsd %xmm1, 0(%rdx,%rax,8) # store Au[i] back to memory
# ... remaining loop arithmetic and control omitted ...
仅仅使用一个临时寄存器在循环迭代间累加和,就能把 spectral 的运行时间几乎减半,从 126 ms 降到 73 ms:
# Hand-edited (73 ms, -42%): Au[i] kept in %xmm1 across iterations
.L103: mulsd %xmm4, %xmm0 # multiply matrix term by u[j]
addsd %xmm0, %xmm1 # accumulate directly into %xmm1
jl .L103 # loop back with %xmm1 live (no reload or store)
movsd %xmm1, 0(%rdx,%r9,8) # store Au[i] once after the loop finishes
这种变换可以通过 GCC 和 LLVM 已经执行但 CompCert 缺少的两个标准循环优化来实现:循环不变量代码外提(LICM)和循环旋转。二者结合起来,会在循环之前加载一次 Au[i],并在循环之后存储一次。
sha3 中过于保守的栈别名
另一个 CompCert 基准测试 sha3,大部分时间花在 keccakf 中,这个函数在 24 轮中打乱 SHA-3 的内部状态。它把临时值写入栈上的局部数组 bc[5]:
/* sha3.c: temporary slice buffer in keccakf */
uint64_t bc[5];
for (i = 0; i < 5; i++)
bc[i] = st[i] ^ st[i + 5] ^ st[i +
文章标题:一个经过形式化验证的C编译器能否像gcc -O2一样高效?
正文:
CompCert的死代码消除遍(backend/Deadcode.v)本应移除它们,但并没有。keccakf通过调用者传入的指针st读取其状态。CompCert的分析(backend/NeedDomain.v)已经知道st不可能指向keccakf自己的栈帧,但它却把每一次通过st的加载都视为可能读取该栈帧上的任何内容,包括bc。因此,每次对bc的存储看起来都可能在之后被需要:
CompCert:对 bc[] 的存储从未被读取
movq %rax, 0(%rsp) # 将 bc[0] 存储到栈上 movq %rbx, 8(%rsp) # 将 bc[1] 存储到栈上 movq %rcx, 16(%rsp) # 将 bc[2] 存储到栈上
... 每轮还有 31 条类似指令;每条都在被读取之前被覆盖 ...
CompCert 全部保留:它假设之后通过 st 的加载可能读取它们
移除这些死存储后,每轮的栈存储减少了80%,并将sha3的运行时间缩短了18%。
## 冗余的零扩展与虚假的寄存器依赖
当我们检查aes和nbody时,在CompCert的x86-64后端模型和代码生成中发现了两个问题。
首先,在x86-64上,写入32位寄存器会自动将64位寄存器的高32位清零。CompCert的指令选择器没有为移位和位掩码建模这一硬件规则。当aes使用(u64)(x >> 24)索引查找表时,CompCert生成了一条显式的零扩展:
CompCert:冗余的 movl 零扩展
shrl $24, %edx # 将表索引逻辑右移 24 位 movl %edx, %edx # 冗余!32 位移位已经将高 32 位清零 movl 0(%r9,%rdx,4), %r10d # 从查找表 Te0 加载 32 位字
这为每个加密轮增加了23条无用指令。仅移除这些指令就将aes的运行时间从85.2 ms降至77.6 ms(运行时间减少9%)。结合LICM,我们能够达到约67 ms(相对于约84 ms的基线,运行时间减少约20%)。这略快于gcc -O2。
其次,我们发现CompCert生成标量SSE指令(如cvtsi2sd和sqrtsd)时存在次优的降级处理。虽然这些指令只写入低64位,但硬件在执行时会考虑%xmm寄存器的全部128位,并且必须保持高位不变。这些高位在标量代码中从未被使用(没有SIMD)。这会造成虚假的写后读依赖,CPU会等待对该寄存器的前一次写入完成,从而阻塞指令流水线。
GCC和Clang都通过先发射xorpd %xmm, %xmm来修复此问题(详见LLVM的BreakFalseDeps.cpp和这篇Stack Overflow分析)。现代x86处理器在寄存器重命名器中将以自身为操作数的xor识别为零执行周期指令,从而以零额外成本打破虚假依赖:
CompCert(184 ms):对旧 %xmm3 内容的虚假依赖
cvtsi2sd %r11d, %xmm3 # 写入低 64 位,等待旧 %xmm3 流水线而阻塞 sqrtsd %xmm3, %xmm3 # 在虚假依赖链完整的情况下计算 sqrt
手工编辑(112 ms,-40%):零成本的 xorpd 打破依赖链
xorpd %xmm3, %xmm3 # 重命名器以零延迟分配新寄存器 cvtsi2sd %r11d, %xmm3 # 立即写入低 64 位,无流水线阻塞 sqrtsd %xmm3, %xmm3 # 以完整硬件吞吐量计算 sqrt
当sqrt被编译为CompCert的__builtin_sqrt时,这使nbody获得了40%的加速。(存在虚假依赖时,该版本甚至比原版CompCert的132 ms libm调用还要慢。)
3. CompCert如何证明编译器遍
文章标题:一个经过形式化验证的 C 编译器能像 gcc -O2 一样高效吗?
正文: 在让 AI 智能体编写新的变换之前,我们先来理解 CompCert 是如何证明这些变换是正确的。CompCert 中的每一个编译阶段都附带一个用 Rocq 编写的数学证明,证明变换后的代码与原始程序行为完全一致。CompCert 使用了两种根本不同的方法,每种方法都有各自不同的工程权衡。
方法一:直接验证的数据流
在直接验证中,优化阶段直接用 Rocq 的纯函数式语言(Gallina)编写,并提取为 OCaml 以构建编译器二进制文件。一个编译阶段会证明一个全局模拟定理:对于每一个程序 \(P\),执行变换后的程序 \(P'\) 与 \(P\) 的可观测行为完全一致。由于优化阶段本身就是被证明的形式化对象,算法与证明融为一体。CompCert 在其核心编译阶段中采用了这种设计,例如常量传播(Constprop.v)、公共子表达式消除(CSE.v)和死代码消除(Deadcode.v)。
这一类别中的大多数编译阶段都是数据流分析。为了优化代码,编译器会跟踪函数中每个点上成立的事实:
- 定义编译器已知的信息:你定义一组关于变量和内存的事实。一个变量可能持有一个已知的数值(r1 = 42),也可能持有一个未知的运行时值。这些事实会沿着函数的控制流图传播。
- 在每条指令上更新事实:你编写一个函数,为每个操作更新这些事实。像 r1 = 5 这样的赋值会向当前状态添加一个已知常量。像 *p = r3 这样的指针存储会更新状态,并清除任何可能与 p 共享内存的缓存加载。
- 循环直到事实不再变化:当两个基本块在 if-else 之后合并,或在循环上迭代时,编译器会合并它们的事实。例如,如果一个分支说 r1 = 42,另一个说 r1 = 10,编译器会丢弃具体数值并将 r1 标记为未知。CompCert 运行一个求解器(Kildall 算法),反复遍历控制流图,直到事实稳定下来。
直接验证对于规则清晰、可预测的教科书式编译阶段效果很好。然而,许多优化依赖于复杂的启发式规则和边界情况。由于优化算法与其数学证明不可分割,你不能简单地调整某个编译阶段的行为而不重新证明其底层定理。对单条分析规则的修改可能会使数百行 Rocq 代码中的证明链失效。这种紧密耦合使得对复杂优化的迭代变得缓慢。
方法二:翻译验证
直接验证证明的是变换算法本身,而翻译验证证明的是一个检查器。
可以把它想象成解一个数独谜题与检查一个数独谜题的区别。编写一个从不出错的求解器很难验证。编写一个检查器来检查已完成的棋盘,确认数字 1 到 9 出现且不重复,则要简单得多。
翻译验证不是去证明一个优化算法对每一个可能的输入程序都能产生正确的输出,而是将编译阶段拆分为两半:
- 一个不可信的预言机(用标准 OCaml 编写),运行复杂的启发式规则并执行变换。
- 一个经过验证的验证器(在 Rocq 中编写并证明,然后提取为 OCaml),检查该变换对于特定函数是否正确。
CompCert 已经在具有复杂图算法的编译阶段中使用了这种设计:
- 寄存器分配(Allocation.v):一个不可信的 OCaml 求解器运行迭代寄存器合并图着色,一个紧凑的 Rocq 验证器检查每个变量的值是否仍然位于分配代码读取它时所使用的寄存器或栈槽中。
- 基本块布局(Linearize.v):一个不可信的 OCaml 启发式规则对基本块进行排序以最小化跳转,一个经过验证的 Rocq 验证器检查所有控制流路径是否保持完整。
文章标题:一个经过形式化验证的 C 编译器能否像 gcc -O2 一样高效?
正文: 这种架构不会削弱数学上的保证。在相同的可信假设下,该编译遍仍保持其验证保证。在构建编译器时,你只需为验证器证明一次定理:
当你编译一个 C 程序时,CompCert 会运行验证器,以保证该转换对那个特定程序是正确的。由于验证器已在数学上被证明永远不会对无效的重写返回 OK,不可信的预言机无法破坏正确性。如果预言机有 bug,并提出了一个错误的转换,验证器保证会拒绝它,编译器要么回退到原始代码,要么报告编译错误。我们在本项目中所实现的绝大多数编译遍都采用了这种架构。
4. 用编码智能体扩展已验证的编译遍
一旦确定了需要实现哪些编译遍(第 2 节),我们就使用编码智能体来扩展优化编译遍的生成与验证。每个优化都被分配给一个智能体,在隔离的 git worktree 中工作。智能体所做的每一处改动都必须在所有目标架构上干净编译,并通过 CompCert 的回归测试套件。证明还必须引入零个 Admitted 证明或未经批准的 Axiom 声明。
虽然 Rocq 能验证这些转换本身在数学上是可靠的,但它无法验证对硬件模型的改动。如果智能体错误地修改了某条 x86 指令的定义,Rocq 仍会接受该证明,但编译器会生成有问题的机器码。因此,未经明确的人工批准,智能体被禁止修改可信计算基(C 语义、x86 汇编指令和内存模型)。不幸的是,流程中那只猴子(也就是我)也批准了对硬件模型的错误改动,但我们会在第 6 节讨论这一点。
我们实现了 5 个新编译遍,并对现有编译遍做了改进:
| 编译遍与中间层 | 转换 | 运行时变化 |
|---|---|---|
| IVwiden(RTL,新增) | 将 32 位 IV 扩宽到 64 位;折叠仿射数组偏移 | gemm -26%,sha1 -13% |
| LICM + Looprot(RTL,新增) | 提升不变量链(行跨度和基地址) | gemm -28%,syrk -27% |
| Loadfwd(RTL,新增) | 跨 join 点和循环回边转发加载 | spectral -40%,3mm -47% |
| Tailacc + Inlining(2)(RTL) | 将尾递归重写为循环;第二轮内联 | integr -54%,fib -46% |
| CSE + Deadcode(RTL,改进) | 不相交别名分析;字节加载合并( Mint64u ) | siphash24 -21%,sha3 -18% |
| Loadop + x86 Asm(Linear/Asm) | 将加载融合进内存操作数;零扩展移位 | gemm -9%,nsievebits -6% |
| Pure libm Builtins(C/common) | 重写 sqrt / fabs ;将 50 个数学调用视为纯函数以用于 CSE | nbody -17%,perlin -15% |
5. 从孤立的收益到完整流水线
编写 Rocq 证明通常很直接。在 Claude Code 中使用 Opus 5.5,大多数编译遍只需几个小时,约 10 到 40 轮编译-修复迭代即可完成。然而,工作并未就此结束,在证明完成之后,一些真正的挑战浮现出来,涉及留出代码、编译遍之间的相互作用以及真实硬件。
5.1 编译遍相互作用与自动调优的理由
我们实现的每一个编译遍在单独应用时都能让基准测试更快。然而,将它们全部合并到一个静态流水线中后,暴露出编译遍之间微妙的相互作用。在某些程序上,组合所有优化甚至会让它们比只应用一小部分子集还慢。我们用 -fno-* 标志来定位不良的相互作用,例如:
- 在 sha3 中,Loadfwd 在内存操作之后插入了影子副本。虽然 Deadcode 通常会消除它们,但 CSE 将这些影子寄存器用作规范替换,合并了 27 个不同的值,并增加了寄存器压力,直到 keccakf 溢出到栈上。
- 在 nsieve 中,循环旋转把出口测试复制到了底部,将无条件跳转变成了条件分支。这使得该块不符合 CompCert 在 Linearizeaux.ml 中的 latch-placement 启发式规则,从而在热路径上增加了额外的跳转。
虽然我们能够通过改进局部启发式规则来解决这两种情况,但这种模式指向了一个更广泛的现实:没有单一的固定 pass 顺序或启发式规则能在所有代码库中达到最优。诸如此类的 pass 交互为 profile-driven autotuning 和/或 agentic optimization 提供了强有力的理由。对于经过形式化验证的编译器来说尤其如此,因为每个优化 pass 都保证是正确的(或 no-op)——所以我们只需要担心交互问题!这与传统编译器非常不同,在传统编译器中,错误的 pass 顺序不仅可能次优,还可能引入 bug。
5.2 超越 CompCert 基准的评估:PolyBench 与更大的程序
在解决这些交互问题之后,我们修改后的编译器的初始版本 faster-compcert (v0) 能够击败 gcc -O1,并在 CompCert 基准上达到基线 CompCert 运行时间的 0.871x。这缩小了与 gcc -O2(restricted)(0.794x) 之间 60% 的差距。
为了测试这些加速是否能在 CompCert 基准之外泛化,我们在两个最初留出的套件上评估了该编译器:big(五个较大的程序:raytracer、spass、arcode、lzw 和 lzss)和 polybench(来自 PolyBench/C 4.2.1 的全部 30 个 loop-nest 内核)。结果较为有限,两者都落后于 gcc -O1。
- 在 big 上,编译器达到基线的 0.982x(相比之下 gcc -O1 为 0.949x)。
- 在 polybench 上,编译器达到基线的 0.845x(相比之下 gcc -O1 为 0.739x)。6
检查 gemm(C[i][j] += alpha A[i][k] B[k][j])的汇编代码立即揭示了 PolyBench 为何仍然很慢。我们的编译器在内层循环中执行了 22 条指令,而 gcc -O1 执行了 8 条:
之前(faster-compcert v0:内层循环 22 条指令):
.L114: movq %rsi, %r8 imulq $8800, %r8 # C[i] row base recomputed every j! leaq 0(%rbp,%r8,1), %r8 movslq %edx, %r11 # 32-to-64 sign extension of j movq %r11, %rcx movsd 0(%r8,%rcx,8), %xmm0 movq %rsi, %r10 imulq $9600, %r10 # A[i] row base recomputed every j! leaq 0(%r12,%r10,1), %r10 movslq %r9d, %rax movsd 0(%r10,%rax,8), %xmm6 # A[i][k] movapd %xmm2, %xmm3 mulsd %xmm6, %xmm3 imulq $8800, %rax # B[k] row base recomputed every j! leaq 0(%rbx,%rax,1), %r10 movsd 0(%r10,%rcx,8), %xmm4 mulsd %xmm4, %xmm3 addsd %xmm3, %xmm0 movsd %xmm0, 0(%r8,%r11,8) leal 1(%edx), %edx cmpl $1100, %edx jl .L114
之后(faster-compcert v1,带有 dependent-chain LICM + IVwiden:内层循环 11 条指令):
.L114: movsd 0(%rdi,%rcx,8), %xmm6 # C[i][j]: row base hoisted, 64-bit index movsd 0(%rdx,%r11,8), %xmm7 # A[i][k]: row base hoisted movapd %xmm3, %xmm4 mulsd %xmm7, %xmm4 movsd 0(%rsi,%rcx,8), %xmm8 # B[k][j]: row base hoisted mulsd %xmm8, %xmm4 addsd %xmm4, %xmm6 movsd %xmm6, 0(%rdi,%rcx,8) leaq 1(%rcx), %rcx # 64-bit induction variable, no movslq cmpq $1100, %rcx jl .L114
为什么 LICM 最初未能提升行基地址 C[i]、A[i] 和 B[k]?在二维数组中,计算行基需要一条由三条依赖指令组成的链:对外层索引进行符号扩展(movslq %esi, %r8)、乘以行步长(imulq $8800, %r8),以及加上数组基地址(leaq 0(%rbp,%r8,1), %r8)。我们的第一个 LICM pass 只提升了那些参数已在循环外定义的单条操作。
对于 v1,我们扩展了 LICM.v,以提升依赖的不变操作链,并构建了 IVwiden.v,将 32 位循环索引拓宽为 64 位归纳变量。这两个 pass 合在一起,使 gemm 的运行时间几乎减半(从 1.96 秒降至 1.05 秒),并将我们的 PolyBench 几何平均值从 0.845x 降至 0.738x。
## 6. 人工关卡:当证明无法拯救你
在 CompCert 中,这些变换使用 Rocq 进行形式化验证。如果 agent 在变换中出错,比如 Loadfwd 或 LICM,make proof 会拒绝它。然而,一旦我们触及可信基——C 语义、内存模型、x86 汇编语义,或打印最终汇编的代码——这层安全网就消失了。可信基中的错误假设会使正确性保证失效,而 Rocq 却会欣然报告 Qed。
即使我们有规则要求对可信文件进行人工签核,我还是两次批准了可信基提案,而事后证明这些提案在数学上是错误的。
在其中一次中,一个 agent 试图提升 siphash24 的性能,这是 CompCert 的基准测试之一。siphash24 从一个未对齐的 uint8_t * 指针读取小端序 64 位字。在 C 中,每个字由八个字节加载移位并 OR 在一起构建:
#define U8TO64_LE(p) \ (((uint64_t)((p)[0])) | ((uint64_t)((p)[1]) << 8) | \ ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) | \ ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) | \ ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56))
GCC 将这八个字节加载折叠成单个未对齐的 movq (%rdi), %rax。CompCert 无法做到这一点,因为其 64 位内存块(Mint64)在内存模型中要求 8 字节对齐。
为了解决这个问题,一个 agent 建议向内存模型添加一个未对齐的 8 字节块(Mint64u),并声称一个简单的引理:如果 ptr + 0 .. ptr + 7 处的 8 个连续 Mint8unsigned 加载全部成功,那么 ptr 处的单个 Mint64u 加载也成功,并返回组合后的 64 位字。
这听起来显然是真的。我批准了。
然后负责实现的 agent 坐下来在 Rocq 中证明该引理,结果却证明了一个反例。
在 CompCert 的内存模型中,指针偏移是 64 位模整数(Ptrofs.int),Mem.loadv 将其解释为 \([0, 2^{64})\) 中的无符号整数。特别地,Mem.load 要求整个连续字节范围 \([\text{ofs}, \text{ofs} + \text{size})\) 有效,且不能绕过 \(2^{64}\)。假设一个内存块在 64 位地址空间的最顶端(\(2^{64} - 4\) 到 \(2^{64} - 1\))和最底端(\(0\) 到 \(3\))都有有效权限,而 ptr 位于偏移 \(2^{64} - 4\):
- 所有八个单独的字节加载 ptr + 0 到 ptr + 7 都成功,因为指针加法 Ptrofs.add 在每次 1 字节检查之前按模 \(2^{64}\) 回绕。
- 合并后的 8 字节加载在 ptr 处失败(None),因为 \([2^{64} - 4, 2^{64} + 4)\) 跨越了 \(2^{64}\) 边界!
如果这个声明作为假设而不是待证明的引理进入可信基,所有证明仍会通过,而编译器将是不健全的。由于 agent 被指示在遇到可信基缺陷时停止而不是即兴发挥,我们立即发现了错误。我们用对内存模型本身的更改(common/Memtype.v 和 common/Memory.v)替换了有缺陷的提案。具体来说,我们添加了一个全局不变式 access_bounded,声明没有内存块在偏移 \(\ge 2^{64} - 8\) 处拥有权限(perm_limit := Ptrofs.modulus - 8)。无论如何,没有真实的 x86-64 用户空间对象能有大小 \(\ge 2^{64} - 8\)。有了 access_bounded,8 个连续的字节加载不会绕过 \(2^{64}\)。合并引理顺利通过,siphash24 运行时间下降了 21%(从 86.2 ms 降至 68.4 ms)。
来自人工把关的教训:对形式化规范的人工签署确认是必要的,但仅凭人的直觉并不够可靠。此后我们改变了流程:每个可信基提案都必须先在 scratch 分支中进行机械化原型验证(关键可靠性引理已证明且零 admit),并针对真实 CPU 或 glibc 做差分测试,之后才提交给我审批。
7. 当前性能状况
以下是在一台安静机器上 faster-compcert 的表现,以相对于 CompCert 的几何平均运行时间表示(数值越低越快):
| 编译器配置 | CompCert 基准测试(24 个程序,调优) | big(5 个程序,留出) | PolyBench(30 个内核,开发中使用) |
|---|---|---|---|
| CompCert(基线) | 1.000 | 1.000 | 1.000 |
| gcc -O1 | 0.893 | 0.950 | 0.756 |
| faster-compcert(默认) | 0.831 | 0.967 | 0.738 |
| faster-compcert(全部可选标志) | 0.815 | 0.961 | 0.733 |
| gcc -O2(受限) | 0.795 | 0.887 | 0.648 |
| gcc -O2(完整) | 0.784 | 0.886 | 0.646 |
| gcc -O3 | 0.790 | 0.913 | 0.583 |
(注:“默认”包含所有经过验证的中端 pass,外加 -fshift-mask、-fzext-load 和 -fmerge-bytes。“全部可选标志”额外加入 -fload-op 和 -ftrust-libm。)
如果以完整 gcc -O2 为基准来看同一组数据(1.00x = gcc -O2),情况就很清楚了:
- 在 CompCert 基准测试上,CompCert 起初落后 gcc -O2 28%。现在差距在 4.0% 到 6.1% 之间(相对于 gcc -O2(受限)缩小了 81% 到 89% 的差距)。7
- 在 PolyBench 循环嵌套上,CompCert 起初落后 gcc -O2 55%。现在差距在 13.5% 到 14.2% 之间(缩小了 70% 到 72% 的差距),并且超过了 gcc -O1。
- 在留出的 big 程序(spass、raytracer、arcode、lzw、lzss)上,CompCert 起初落后 gcc -O2 13%,现在落后 8.5% 到 9.1%(缩小了 28% 到 33% 的差距)。
8. 我们与 GCC -O2 持平仍面临的障碍
尽管在这次试点中我们在缩小性能差距方面取得了显著进展,但仍有很长的路要走。CompCert 基准测试与留出的 big 程序之间的差距,反映了我们优化工作(以及 token 投入)的聚焦所在。我们聚焦于容易摘取的果实,比如单个函数内部的循环级优化。该策略对小型数值内核效果很好。但在 spass 和 raytracer 这样的大型程序中,运行时间主要受函数调用开销、指针间接寻址和内存布局驱动。这些我们甚至还没有开始处理。
要缩小与 gcc -O2 的剩余差距,需要超越单函数标量 pass。以下是我们识别出但未实施的一些优化示例。
1. 粗粒度别名分析与循环不变量加载
在 PolyBench 循环嵌套上,faster-compcert 仍落后 gcc -O2 13%,部分原因是缺少循环不变量加载提升。以 gemm(C[i][j] += alpha A[i][k] B[k][j])为例:在内层 j 循环中,A[i][k] 的值从不改变。GCC 会在循环开始前将其一次提升到寄存器中。但 CompCert 目前缺少堆指向分析,因此无法证明向 C[i][j] 存储不会影响 A[i][k]。结果,CompCert 在每一次迭代中都从内存重新加载 A[i][k]。
需要什么:要么为堆提供经过验证的指向分析,要么为 C99 restrict 注解提供翻译验证,使编译器能够证明这些数组不重叠。
2. 过程间寄存器分配(IPA-RA)
在 spass 和 arcode 这类调用密集的代码中,函数不断调用其他函数。CompCert 一次编译一个函数。当函数执行调用指令时,它假定所有调用者保存寄存器都被清空。即使被调用的小函数只触及两个寄存器,调用者仍然需要事先将自己的活跃变量保存到栈内存,之后再重新加载。
需要什么:跨编译单元的全程序分析,让编译器能够自定义调用约定,使调用者只保存被调用者实际触及的寄存器。
3. 栈帧反向链接
文章标题:一个经过形式化验证的 C 编译器能否像 gcc -O2 一样高效?
正文: 在 x86-64 上,优化后的函数序言只是从栈指针减去一个常量偏移(subq $sz, %rsp)。
而 CompCert 的形式化模型则通过从内存读取存储的回链来拆解每个栈帧(Pfreeframe),因此每个序言(Pallocframe)也必须写入该回链(额外一条 leaq 和 movq)。本来完全可以只在 CPU 寄存器中运行的小型非内联函数,被迫在每次调用时把栈指针存储到内存。
需要付出的代价:要么采用更激进的内联以完全消除栈帧,要么重构 Mach 和 Asm 的栈帧语义,使 Pfreeframe 不再读取回链,从而可以去掉该存储。
9. 要点总结
我们从两个问题开始:为什么 CompCert 比 gcc -O2 慢,以及 LLM 智能体能否弥合这一差距?
首先,CompCert 的形式化模型并不是它慢的主要原因。CompCert 与 gcc -O2 之间几乎所有的差距都来自缺失的优化 pass 和次优的指令选择。
其次,LLM 智能体可以在极少人工监督下大规模地编写并证明严肃的编译器优化。编写近 15,000 行 Rocq 代码(包括实现和证明)既快又可靠。经典性能工程(捕捉负面的 pass 交互、防止编译时间二次方膨胀、用留出测试套件检查过拟合、修复共享机器的计时噪声)所需的人工投入比证明工程更多。
最后,形式化验证只有在真实系统的模型准确时才有效。智能体自动化了传统上困难的部分工作,如构建 pass 和生成证明,但在界定系统范围和验证模型是否准确方面仍然需要人工把关。像差分测试这样的方法未来可以帮助弥合这一差距,进一步减少所需的人工投入。
Written by Aananth V, a first-year master’s student working with InfraAI on AI for systems and formal verification. Edited by Rohit Dwivedula. This work was supported by AWS credits from Amazon.
- 该定理覆盖从 CompCert C 抽象语法到汇编抽象语法的已验证流水线。前端展开、汇编打印、汇编和链接仍属于可信部分。参见 CompCert 手册。↩
- Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. Finding and Understanding Bugs in C Compilers. PLDI 2011. ↩
- Vu Le, Mehrdad Afshari, and Zhendong Su. Compiler Validation via Equivalence Modulo Inputs. PLDI 2014. ↩
- Chengnian Sun, Vu Le, Qirun Zhang, and Zhendong Su. Toward Understanding Compiler Bugs in GCC and LLVM. ISSTA 2016. ↩
- CompCert 基准测试:CompCert 3.18 的 test/c 目录中的程序(CompCert-small-tests)。PolyBench:PolyBench/C 4.2.1 的 30 个循环嵌套内核。本文中所有测量均在 Intel Xeon Silver 4314 上进行;基准测试框架位于我们 fork 中的 faster-compcert/ 目录。 ↩
- 本节中的 v0 数字来自更早的一次测量会话。在第 7 节的最终运行中,由于机器运行的漂移,gcc -O1 在大测试集上测得 0.950x,在 PolyBench 上测得 0.756x。 ↩
- “差距缩小”是相对 gcc -O2(受限)在对数尺度上测量的:ln(faster-compcert) / ln(gcc -O2 restricted),使用上表中的几何平均数。 ↩