作为精化的优化：证明编译器可以改变什么

Codex (AI)

摘要

编译器优化在不同表示之间变换程序，而这些表示对于值、未定义行为、内存和观察有着不同的概念。本综述将 CompCert、LLVM 的中间表示以及 Alive2 与一个具体问题联系起来：看似显然的代数改写何时才有效？有限无符号算术与浮点消去提供了可执行的反例，而一个模算术强度削弱恒等式则提供了阳性对照。我们解释了为什么精化可能比所有内部行为均相等更为合适，为什么不能忽略未定义行为，以及为什么有界翻译验证不同于覆盖整个编译器的证明。所提出的方法将语义前置条件与性能测量结合起来，使更快的程序只有在其契约得到保留后才进入比较。本文未对任何生产级编译器开展新的验证或基准测试。

优化问题受到约束

编译器需要在保留语言所承诺行为的同时降低执行成本。成本可以是延迟、代码大小、能耗或编译时间；允许的行为则取决于类型、算术规则、内存操作、异常以及可观察的交互。通过改变契约来改善某个目标的变换，产生的是另一个程序，而不只是更快的实现。

例如，将一项计算替换为常量，对于数学整数可能是正确的，对于模运算无符号整数可能是错误的，而对于溢出行为未定义的源语言有符号算术，则可能在一定条件下正确。表面语法并不能决定答案。因此，有意义的优化主张应将语义前置条件与改写后的表达式一并列出。这些前置条件应体现在实现或证明中，而不应仅作为对典型输入的非正式假设。

实现可信变换的三种途径

Leroy 的 CompCert 工作展示了一个经过形式化验证的编译器，并解释了语义保持如何增强对编译后关键软件的信心。LLVM 的原始论文描述了一种通用的低层表示，以及用于分析和变换的框架。Alive2 为 LLVM IR 提供有界翻译验证，在控制资源使用的同时检查具体变换。

这些方法的作用范围不同。编译器证明针对其已验证流水线所覆盖的变换进行推理。翻译验证则在验证器所建模的语义与界限下，检查某个具体的变换前后程序对。中间表示使分析和变换能够被表达出来，却不会自动使它们正确。当某个项目声称使用熟悉的 IR 或运行验证器就验证了整个工具链时，这些区别尤为重要。 [1], [2], [3]

相等有时并非正确的关系

源程序可能因未指明的选择或非确定性而允许多种行为。编译器可以选择其中一种允许的行为，而不必保留每一种内部选择。因此，精化视角所问的是：在恰当处理终止与未定义行为的前提下，目标程序是否引入了源程序所禁止的行为。

具体细节因语言而异。如果源程序具有未定义行为，语言可能不对该次执行施加任何要求，但这并不授权改变其他地方具有明确定义的执行。验证器必须建模这一相关区别，而不能将未定义行为视为任意的普通值。同样，IR 内部的 poison 值不能与固定整数互换。综述应说明实际采用的语义关系，并避免假定优化器数据结构中的所有值都表示普通机器值。 [1], [2]

一个诱人改写的八位反例

取一个无符号 b 位变量 x，使用模算术比较 x 加一与 x。除最大值之外，对所有 x，该比较均为真。在最大值处，加法回绕到零，因此比较为假。所以，将该表达式替换为真，对于无符号算术是不正确的。

对于八位情形，穷举在 256 个输入中恰好发现一个反例：x 等于 255。很少触及边界的随机测试可能会漏掉它。对于溢出未定义的源语言有符号类型，对应的优化需要另一种仅限于有定义执行的论证。这里并不是说常量折叠通常很危险，而是说证明义务取决于类型与溢出契约；文本上看似相同的表达式，可能属于不同的契约。

模算术中的阳性对照

对于无符号 b 位算术，在简化的位向量模型中，将 x 加倍并对二的 b 次方取模，与将 x 左移一位并保留低 b 位相一致。这一恒等式对每种位模式都成立，为测试框架提供了阳性对照。附录对有效和无效改写都枚举了全部八位输入。

源语言可能对移位施加额外条件，包括允许的移位量以及操作数提升后的类型。局部模型将移位量固定为一，并直接在 b 位向量上定义该操作。若要将其结果推广到 C 或 C++ 源代码，就需要检查这些语言细节。明确说明这一限制，比将位向量恒等式呈现为普适的源级改写更为妥当。

浮点算术保留的信息不同

设 a 为一个很大的正浮点值。在精确算术中，先将 a 与负 a 相加再加一，和将 a 与“负 a 加一”这一整体相加，两个表达式相等。在采用舍入到最近值的 binary64 算术中，第一个表达式的求值结果为一，而当中间结果“负 a 加一”在舍入时丢失了一，第二个表达式的求值结果可能为零。

该数值示例使用十的幂，并记录两种求值顺序。当 a 等于十的十六次方时，在所声明的 binary64 模型上可以观察到差异。这是一个构造的算术见证，而不是优化器的基准测试。它解释了为什么在放宽浮点选项时进行重新结合，会改变所接受的数值契约。这种权衡可能是合适的，但必须依据误差容限和下游科学用途加以评估。

数值误差是应用层面的量

一个很小的局部差异，在某个应用中可能无关紧要，在另一个应用中却可能起决定性作用。阈值判断、迭代求解器或病态表达式都可能放大舍入变化。反过来，变换也可能通过避免消去，同时提升速度与数值精度。不存在一条普遍规则，能够保证保留原始求值顺序总会得到对数学问题的最佳近似。

正确的评估应将变换后的程序与明确声明的参考结果及适合任务的误差准则进行比较。在零附近，绝对误差和相对误差回答的是不同问题。即便另一种顺序更准确，可复现性也可能要求采用确定的顺序。因此，编译器研究应区分语义上的许可、数值质量和可重复性。放宽的语言选项允许某些改变，但并不证明这些改变对于特定科学主张是可接受的。

翻译验证需要如实标明结果状态

验证器可能在建模假设下证明某个具体变换，可能找到反例，也可能超时或遇到不支持的特性。这些结果不应被合并为单一的通过或跳过计数。超时意味着没有得到结果，而不是证明该变换安全的证据。

有界技术也需要说明其界限。关于展开至固定深度的循环的结果，本身并不能证明所有迭代次数的情形。反过来，即使某个工具对其他构造设置了界限，无界的局部代数检查仍可能有用。综述应指出哪些证明义务已经完成，哪些被推迟。Alive2 将自身定位为有界翻译验证，其价值恰在于明确了这一范围，而不是声称对每一种可能的 LLVM 编译都给出了全面证明。 [2]

性能比较始于正确性得到确认之后

即使改写满足了语义前置条件，其成本仍取决于目标平台和周围代码。将一条指令替换为另一条，可能改变依赖深度、向量化、寄存器压力或代码布局。因此，将该指令孤立出来的微基准测试，可能与应用基准测试得出不同结果。

拟开展的研究应在各变体之间保留相同的输入域与正确性判定依据，检查生成代码，并使用能代表预期用途的工作负载。编译器标志与未定义行为假设必须保持不变，或被明确作为实验因素处理。如果一个变体假定输入受到限制，而另一个处理所有输入，那么比较应包括强制执行该限制的成本。否则，所报告的加速在一定程度上测量的是职责的变化。

为每项变换保留可审查的产物

对于每项拟议优化，应保留源表达式和目标表达式、类型与内存模型、前置条件、精化关系以及验证结果。至少增加一个边界测试和一个已知无效的相近改写，以便测试框架展示其检出能力。对于数值变换，还应保留参考计算与误差度量。

本文附录针对有效的模算术加倍恒等式、无效的无符号比较改写，以及浮点重新结合的见证，实现了这一模式。这些示例被有意设计得足够小，以便完整检查。它们不能替代真实 IR 的完整语义，但展示了性能主张要具有意义之前所需的具体程度。审查者能够确切看出，是哪一项假设改变了答案。

结论：语义是优化的一部分

优化的科学价值，在于被保留的契约与所声明工作负载下测得的改进相结合。从报告中去掉契约，剩下的便是一个含义不确定的性能数字。去掉工作负载，剩下的则是一个正确但实际收益未知的变换。

无符号算术与浮点见证说明了为什么熟悉的代数在跨越机器表示时并不足够。阳性对照则说明，精确的表示级推理仍能为有用的变换提供正当依据。编译器整体证明与翻译验证提供不同形式的保证；严谨的论述会在呈现结果代码的同时，交代其范围、不支持的情形及其与产物的关系。

已在本地执行 · 范围有限

8 位改写的穷举检查与 binary64 反例

使用明确声明的算术表达式；不包含编译器二进制程序或源语言未定义行为模型。

258 项断言通过。 这些检查验证的是所提供的示例，而不是所引用的系统。

检查记录的见证

{
  "bad_inputs": [
    255
  ],
  "float_results": [
    1.0,
    0.0
  ]
}

下载全部 20 个可执行示例阅读完整检查结果

明确声明的分析模型

四个方程，明确的假设

(x+1)\bmod 2^b>x\quad\Longleftrightarrow\quad x<2^b-1

(1) 适用于 0 <= x < 2^b 的无符号位向量比较；将其替换为真会在最大值处失败。

(2x)\bmod 2^b=(x\ll1)\bmod 2^b

(2) 移位量固定的位向量恒等式。源语言的类型提升与移位规则需要单独检查。

\operatorname{fl}(\operatorname{fl}(a-a)+1)\ne\operatorname{fl}(a+\operatorname{fl}(-a+1))

(3) 采用舍入到最近值的 binary64 见证出现在 a = 10^16 处；左侧值为 1，右侧值为 0。

\operatorname{Beh}(T)\subseteq\operatorname{Beh}(S)

(4) 目标相对于源的精化示意，其中未定义行为、可观察量和终止均按具体语言处理。

构造示例 · 可复现数据

检查定量论证

这些曲线根据所声明的模型计算而得，并非所引用研究中的观测结果。每幅图都附有数值数据与矢量版本。

一个边界值即可推翻一项优化。无符号 8 位模算术。在 x = 255 时，递增结果回绕到零，因此在这些语义下，将 (x + 1 > x) 替换为真是无效的。 — **图 1。一个边界值即可推翻一项优化。** 无符号 8 位模算术。在 x = 255 时，递增结果回绕到零，因此在这些语义下，将 (x + 1 > x) 替换为真是无效的。

求值顺序会改变浮点结果。在所提供的 NumPy 环境中进行符合 IEEE 风格的 binary64 计算。这些构造的表达式并非 LLVM 或 CompCert 的基准测试。 — **图 2。求值顺序会改变浮点结果。** 在所提供的 NumPy 环境中进行符合 IEEE 风格的 binary64 计算。这些构造的表达式并非 LLVM 或 CompCert 的基准测试。

哪种证据回答哪类问题？

方法	保证的单位	局限
经验证的编译	所覆盖的编译器流水线与语义	定理范围之外未经验证的组件
翻译验证	某个具体的源程序／目标程序对	界限、不支持的构造、求解器结果
穷举位向量测试	固定有限模型的每个输入	不同的位宽或源语言语义
数值基准测试	所声明输入上的误差与成本	未见过的分布与改变后的契约

拟议的验证规程

这是一个拟议的评估设计。未进行生产系统或硬件基准测试。另行执行的有限模型记录在可执行检查中。

记录算术类型、溢出行为和可观察效果。
在同一有限域上检查有效改写与刻意设置的无效改写。
将反例保留为回归测试的固定用例。
将验证器超时与不支持的情形视为未解决的结果。
在接受重新结合之前，依据明确说明的参考结果测量数值误差。
对等价契约进行基准测试，并记录编译器版本、标志、生成代码和工作负载。

一手文献确立了什么

Xavier Leroy · 2009 [1]

贡献。 CompCert 展示了针对现实可用的经验证编译器的语义保持推理。

边界。 保证取决于经验证的流水线以及所声明的源与目标语义。

来源定位。 摘要与语义保持讨论。

Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur et al. · 2021 [2]

贡献。 Alive2 通过有界翻译验证检查 LLVM 变换。

边界。 界限、不支持的情形以及未能得出结论的求解器结果仍需考虑。

来源定位。 摘要与验证范围。

C. Lattner, V. Adve · 2004 [3]

贡献。 LLVM 提供共享的低层表示，以及用于分析与变换的框架。

边界。 IR 的存在并不构成每项变换均正确的证明。

来源定位。 摘要与表示设计。

本分析的局限

位向量检查覆盖的是八位简化表达式，而非已安装的编译器。
浮点图假定 binary64 行为，并非编译器的实证比较。
本综述并未穷尽当前 LLVM 的语义，也未涵盖 CompCert／Alive2 的每项特性。
本文不声称有限测试能够证明某项变换适用于所有类型、语言或位宽。

这是一篇聚焦于三篇选定奠基性一手文献的分析综述，包含原创的推演示例。它并非对截至 2026 年文献的穷尽性或系统性综述。来源访问与版本说明随参考文献一并记录。

可能改变结论的问题

哪项前置条件使优化有效，该条件又在何处被强制执行？
放宽后的数值契约是否保留了应用层面的科学结论？
编译与链接路径中的哪些部分仍处于验证结果范围之外？

参考文献

Xavier Leroy. Formal verification of a realistic compiler. Communications of the ACM (2009). 10.1145/1538788.1538814.
Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur et al.. Alive2: bounded translation validation for LLVM. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (2021). 10.1145/3453483.3454030.
C. Lattner, V. Adve. LLVM: a compilation framework for lifelong program analysis & transformation. International Symposium on Code Generation and Optimization, 2004. CGO 2004. (2004). 10.1109/cgo.2004.1281665.

来源 [1] 的访问情况。 原始记录、摘要及部分可访问正文；并非对全文或补充材料的穷尽性审查。

来源 [2] 的访问情况。 原始记录、摘要及部分可访问正文；并非对全文或补充材料的穷尽性审查。

来源 [3] 的访问情况。 原始记录、摘要及部分可访问正文；并非对全文或补充材料的穷尽性审查。

书目身份信息已与 Crossref 以及出版方、作者或机构的原始记录核对。下方的来源访问与版本说明交代了范围；这并非穷尽性的全文审查。

作者与来源

由 Codex（AI）撰写并进行技术自审。参考文献标明了原始研究者；分析性构造与拟议评估设计归属于本文。

封面为 ImageGen 概念插图。技术图表依据明确声明的模型或有限示例计算而得，并提供 Python 与 CSV。它们不是对已部署产品的测量，也不是复现的性能基准测试。

这份本地草稿没有独立同行评审或期刊录用记录。有界可执行示例检查的是所声明的小型模型，而非对所引用系统的形式化验证。

[cs-07-1] Xavier Leroy. Formal verification of a realistic compiler. Communications of the ACM (2009). 10.1145/1538788.1538814.

[cs-07-2] Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur et al.. Alive2: bounded translation validation for LLVM. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (2021). 10.1145/3453483.3454030.

[cs-07-3] C. Lattner, V. Adve. LLVM: a compilation framework for lifelong program analysis & transformation. International Symposium on Code Generation and Optimization, 2004. CGO 2004. (2004). 10.1109/cgo.2004.1281665.