返回资讯中心
外部精选
软件工程
#开发者实时流

研究者用1.5万行Rocq代码试图让CompCert性能逼近GCC -O2

来源标题:Performance of a formally-verified C compiler vs. GCC -O2

一项实验尝试通过编写1.5万行Rocq代码,缩小形式化验证C编译器CompCert与GCC -O2之间28%的性能差距。CompCert用Rocq和OCaml编写,能在证明优化保持程序行为不变的前提下将C编译为x86-64汇编,但其生成的代码性能仍落后于工业级GCC。该工作探索经过形式化验证的编译器能否达到与GCC -O2相当的运行效率。

Hacker News 最新frostbyte72026/11/17 · 今天30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

当编写15000行Rocq代码,试图弥合一个形式化验证编译器与业界标准GCC之间28%的性能差距时,会发生什么?

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用来优化的一些假设:

我想知道这些语义限制是否真的解释了CompCert为何慢,还是说CompCert只是缺少许多标准编译器优化和后端代码生成打磨。而如果差距主要是缺少pass,

我们所有的pass、证明和基准测试脚本都可在github.com/UT-InfraAI/CompCert获取。

在改动CompCert之前,我们在GCC上测试了语义模型假说。CompCert语义中的每一项主要限制在GCC中都有一个对应的标志来禁用相应的优化:

如果CompCert的形式化语义是主要瓶颈,那么在GCC中禁用这四个特性将消除GCC的大部分领先优势。

然而,这并不是我们观察到的情况。即使在gcc -O2中限制了这些标志,CompCert在CompCert基准测试上仍然慢26%,在PolyBench套件上慢54%。这意味着语义模型不是主要瓶颈。大部分差距来自CompCert的规则已经允许、但CompCert从未执行的优化。

我们首先需要知道哪些缺失的变换实际上导致了真实硬件上的性能差距。思路很简单:我们取一个慢基准测试的CompCert .s汇编输出,手动编辑它,一次应用一个缺失的优化。然后我们重新汇编二进制文件,检查其输出与参考结果是否一致,并计时。一旦我们知道哪些优化确实有帮助,我们就可以在CompCert中证明并实现它们。多亏了编码代理,这并没有听起来那么痛苦。

以下是我们通过这种方式发现的一些缺失优化:

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)pass(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],在循环之后存储一次。

另一个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 + 10] ^ st[i + 15] ^ st[i + 20];

到每一轮结束时,有34次对bc[]的存储是死存储,因为这些槽位在被再次读取之前就被覆盖了。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →