玻尔百科编译器是迄今为止被创造出来的最复杂的软件之一，它扮演着一个精密的翻译角色，将人类可读的源代码转换成机器的原生语言。但这种复杂性也带来了出错的风险。我们如何能相信编译器的翻译完美地保留了原始程序的逻辑和意图？回答这个问题极其困难，因为对于任何非平凡的程序，我们都缺少一个明确的“预言机”（oracle）来告诉我们正确的输出应该是什么。程序本身往往就是其最精确的规约。
本文深入探讨了编译器测试这一巧妙的领域，该领域已经发展出强大的技术来应对这一挑战。您将了解到测试人员是如何在世界上最先进的编译器中发现微小错误的，他们不是通过问“这个结果正确吗？”而是通过提出更易于回答的问题。我们将首先探讨使现代编译器测试成为可能的基本思想。《原理与机制》一章将介绍差分测试（解决预言机问题的巧妙方案），解释未定义行为带来的巨大挑战，并详细介绍模糊测试和蜕变测试等用于生成有效测试用例的自动化方法。随后，《应用与跨学科联系》一章将展示这些原理在实践中如何应用，以验证编译器是否遵守了其与硬件、语言标准以及它所帮助构建的数字世界的安全性之间的关键契约。
想象一下，您雇佣了两位专家级翻译，将一份复杂的法律文件从英文翻译成法文。您会如何检查他们的工作？您可以雇佣第三位翻译来检查前两位，但谁又来检查第三位呢？一个更实际的方法或许是直接比较这两份法文译稿。如果它们在任何有意义的方面存在差异，您就知道至少其中一位犯了错。您并没有在绝对意义上证明哪一份是“正确”的，但您成功地发现了一个错误。
这正是编译器测试的核心所在。编译器是一个翻译器，将人类可读的源代码转换成机器的原生语言。询问“这个编译器的翻译是否正确？”通常是一个极其困难的问题。我们正在编译的程序本身可能就是我们想要执行任务的最精确规约！因此，我们转而提出一个更易于处理的问题：“两种不同的编译器，或同一编译器的两个不同版本，所产生的翻译在行为上是否完全相同？”这个强大的思想被称为差分测试（differential testing）。
在测试领域，预言机（oracle）是一种能为任何给定输入提供“正确”答案的机制。对于编译器而言，一个完美的预言机应该能对任何源程序 和输入 ，准确地告诉我们一个正确编译的程序应有的可观察行为是什么。对于简单的程序，我们或许可以充当预言机，手动计算答案。但对于天气模拟或数据库引擎这样的程序，这是不可能的。程序就是它自身的规约。
差分测试巧妙地回避了“预言机问题”。我们不使用一个编译器和一个预言机，而是使用两个编译器 和 。我们给它们相同的源程序 。它们产生两个不同的可执行二进制文件 和 。然后，我们在相同的受控环境中，用相同的输入 运行这两个二进制文件，并比较它们的可观察行为——比如程序的退出码、屏幕打印内容以及写入的任何文件。如果 和 的行为不同，我们就发现了一个差异。假设源程序 是行为良好的，这个差异就表明至少有一个编译器存在错误。我们已经让编译器互为对方的预言机。
这听起来很简单，但在“假设源程序是行为良好的”这句话背后，隐藏着巨大的复杂性鸿沟。
像 C 和 C++ 这样的编程语言由一个标准来约束，这个标准就像程序员和编译器之间的一份合同。这份合同充满了规则，但也包含一些条款，其大意是：“如果你做了 X，那么一切后果自负。”这就是未定义行为（UB）的领域。一个经典的例子是带符号整数溢出：将两个大的正 int 相加，结果回绕成一个负数。当一个程序触发了 UB，标准对编译器没有任何要求。程序可能会崩溃，可能会产生无意义的结果，可能会格式化你的硬盘，也可能看起来工作得很好。
这对差分测试来说是一个巨大的问题。假设我们找到了一个程序，编译器 和 对它产生了不同的输出。这是编译器错误吗？不一定。如果程序调用了 UB，那么两个编译器在技术上都符合标准。一个编译器可能产生整数 ，另一个可能产生 ；两者都是未定义行为的有效结果。我们的错误报告将是一个误报。
要构建一个健壮的测试系统，我们必须首先过滤掉这些“无效的”测试程序。现代的解决方案是使用称为清理器（sanitizer）的工具。我们可以用一个可信的编译器来编译我们的测试程序，并启用像 AddressSanitizer (ASan) 这样的工具来检测内存错误，以及 UndefinedBehaviorSanitizer (UBSan) 来检测像整数溢出这样的多种 UB。如果一个程序在启用这些清理器的情况下运行并报告了问题，我们就将其从测试套件中丢弃。只有“干净的”程序才会被传递到差分测试阶段。这确保了我们发现的任何差异都更有可能是真正的编译器错误。
确立了我们的核心原则后，接下来的问题是：我们从哪里获得数以百万计的测试程序来发现微小的错误？手动编写它们是不切实际的。现代的方法是模糊测试（fuzzing），即自动生成测试输入。一个模糊测试器可能会随机组合代码片段，创造出一个庞大而混乱的测试程序“动物园”，然后用它们来轰炸我们的编译器。
但我们可以比纯粹的随机混乱更聪明。一种优美而强大的技术是蜕变测试（metamorphic testing）。其思想是测试数学或逻辑关系（即蜕变关系）的保持性，而无需知道具体的正确输出。
考虑简单的算术表达式 。另一个不同的表达式是 。我们从基础代数中知道，这两个表达式通常不相等。然而，它们在特定条件下是相等的：当且仅当 或 时。这给了我们一个微小而完美的预言机！我们可以编写一个程序，计算这两个表达式并检查其相等性。然后，我们检查 和 的条件。对于一个正确的编译器，程序中观察到的相等性必须与我们从代数规则中预测的相等性完全匹配。如果它们不匹配，那么编译器就违反了算术规则，例如，尽管有括号，它还是错误地重新组合了运算。
这个蜕变原则的用途极其广泛。我们可以用它来测试语言标准中无数个隐晦的角落：
char 变量相加时，它们首先被提升为 int。我们可以测试 C 语言加法的结果是否与提升后整数值的数学加法结果相匹配。float* 和 int*）不会指向同一内存位置。我们可以通过创建一个 float 变量，然后使用到 int* 的转换将一个整数字位模式写入其内存来测试这一点。一个假设了严格别名的编译器可能会忽略这次写入，因为它认为这不可能影响到该 float 变量。我们可以将这种“不安全”的方法与使用 memcpy 的“安全”方法进行比较，看编译器的优化是否改变了行为。这是在单个程序内部进行的差分测试。编译器不是一个单一的整体。它是一条流水线。前端解析源代码（如 C 语言）并将其翻译成一种中间表示（IR）。这种 IR 是一种更通用、更抽象的语言。然后，后端接收这个 IR，执行一系列优化，并最终为特定处理器生成二进制机器码。
这种结构使我们的测试更具策略性。我们不仅可以测试从源代码到二进制的完整流水线，还可以创建在不同层次上操作的模糊测试器。
通过在这些不同阶段进行差分测试，我们不仅可以发现错误，还可以确定错误位于编译器复杂机制中的哪个位置。这对开发者来说是无价的。这种分层方法也为更强大的技术打开了大门。在 IR 层面，程序的逻辑以更形式化的方式表示，有时可以利用形式化验证中的数学方法来证明优化后的 IR 与原始 IR 是等价的。像互模拟（bisimulation）这样的技术可以构建一个形式化的见证，保证等价性，提供任何数量的测试都无法达到的确定性水平。
我们已经构建了一个强大的工具包来寻找编译器错误。这引出了一个最终且深刻的问题：我们能否构建终极测试工具？我们能否编写一个程序，接收任意两个编译器 和 ，并绝对确定地告诉我们是否存在任何程序和输入会导致它们产生分歧？
这是一个关于计算基本极限的问题。让我们正式地表述它。考虑所有存在分歧的程序对 的集合，或称“语言”。我们称这个语言为 。 我们的模糊测试和测试工具，本质上是在试图确定给定的一对已编译程序是否属于这个集合。
计算机科学告诉我们， 是递归可枚举的。这是一种花哨的说法，意思是我们可以编写一个识别器——一个程序，如果存在分歧，它最终会找到它并停机，大喊“不匹配！”这正是一个模糊测试器所做的事情：它系统地搜索无限的输入空间，如果它找到了一个导致错误的“见证”输入 ，它就成功了。
但这个问题是可判定的吗？我们的终极工具能否总是停机，要么找到一个错误，要么明确报告“永远不会发生分歧”？答案或许令人惊讶，是否定的。确定 成员资格的问题是不可判定的。可以证明，如果我们能解决这个问题，我们也能解决 Alan Turing 著名的停机问题，而我们知道那是不可能的。
这是一个优美而又令人谦卑的领悟。我们构建更好编译器的实际工程追求，正面撞上了支配所有计算的相同理论极限。编译器测试是在寻找一个见证。我们可以设计出越来越巧妙的方法来引导这个搜索，但我们永远无法仅通过测试来证明一个错误的不存在。这个搜索是，并且将永远是，潜在无限的。
想象一下，您雇用了世界上最杰出的翻译家。他们不仅仅是翻译词语；他们会重构句子、替换习语、改写整个段落，使其更优雅、更高效，同时声称完美保留了原文的含义。对于一份关键的法律文件，您会盲目地信任他们吗？当然不会。您会想办法检查他们的工作。您会给他们一些已知译文的文本，或者一些带有微妙陷阱和双关语的段落，只是为了确保万无一失。
现代编译器就是那个杰出、永不满足的创新翻译家，而我们的程序就是它所转换的文档。前一章探讨了编译器施展其魔法的复杂机制。但我们如何信任这种魔法？答案是一门与编译器设计本身同样深刻和巧妙的学科：编译器测试。这并非我们可能联想到的质量保证中那种单调的勾选检查。这是一场智力游戏，一次科学探究，也是一次对真理的持续求索，其对手是迄今为止被创造出来的最复杂的软件之一。这是一个关于我们如何确保编译器遵守其基本契约的故事——与它所面向的硬件、与它所使用的语言，以及与它帮助构建的数字世界的安全之间的契约。
在最底层，程序必须在物理机器上运行，这是一个由无情逻辑支配的硅世界。编译器必须遵守的第一个也是最神圣的契约是，完美无瑕地使用其目标硬件的语言。这比仅仅了解指令集要深刻得多；它关乎深刻理解机器的“个性”——它如何表示数字，如何处理算术，以及伴随有限精度整数和浮点值而来的所有怪癖。
考虑一个看似简单的任务：您有一个表示 的 8 位带符号数。在二进制补码算术中，其位模式是 11111111。现在，假设您将其与一个 16 位数相加。编译器必须首先将这个 8 位值提升为 16 位。如何提升？一个天真的翻译器可能只是在前面加上八个零，产生 0000000011111111，硬件会将其解释为正数 。程序的逻辑会瞬间崩溃。一个正确的编译器知道*符号扩展*规则：为了保持负数的值，它必须将符号位（前导的 '1'）复制到新的比特位中，产生 1111111111111111，这才是 的正确 16 位表示。
为确保这份契约得到履行，编译器编写者构建了“参考求值器”。这些是小而精细的程序，严格按照硬件的算术规则实现，作为机器语言的完美字典。通过生成数百万个混合宽度算术的测试用例——加法、乘法、位移——并将编译器的输出与参考求值器的输出进行比较，我们可以对编译器对硬件的理解是否健全获得高度的信心。这是信任的基石；没有它，所有更高层次的逻辑都建立在沙滩之上。
一旦我们相信编译器能够使用硬件的语言，我们就必须确保它遵守编程语言本身的法则。当编译器变得“聪明”时，这一点变得尤其具有挑战性。优化是编译器改进我们代码的尝试，但这种雄心可能导致它违反语言的语义规则。
安全优化的一个基本规则是，它绝不能改变程序的可观察行为。一个优化器可能会看到像 f(x) - f(x) 这样的表达式。从数学上看，这是零。如果结果未被使用，优化器可能会想：“啊哈！这是死代码”，然后完全消除对 f(x) 的两次调用。但如果函数 f(x) 不仅仅是返回一个值呢？如果它递增一个计数器、写入一个文件或发送一个网络数据包呢？这些是“副作用”，消除它们会从根本上改变程序的功能。
为了捕捉这种过于热心的优化，我们设置了陷阱。我们可以设计一个测试，其中 f(x) 是一个不纯的函数——一个明确修改某些可观察状态的函数，比如一个语言标准禁止编译器优化的特殊 volatile 或 atomic 计数器。然后，我们向编译器提供一个像 f(x) - f(x) 这样结果未被使用的表达式。一个正确的编译器，会尊重副作用的神圣性，必须执行这些调用。一个不正确的编译器则会消除它们。通过事后检查计数器，我们就能立刻知道编译器是否违反了规则。这个原则也适用于其他构造，比如三元运算符 (condition ? a : b)。C 语言保证 a 或 b 这两个分支中只有一个会被求值。一个测试可以在两个分支中都放置副作用，并验证根据条件，只有一个副作用实际发生，无论编译器选择如何生成机器码。
一些最强大的优化涉及重构程序的流程，比如将一个复杂的递归解开成一个简单的循环。我们如何验证这样一种彻底的转换？编译器测试中最优美的技术之一是使用蜕变预言机——一个外部的、不容置疑的真理。
考虑前 个整数的和。我们从数学中知道，答案总是 。我们可以写几十种不同的循环来计算这个和：一个标准的 for 循环、一个 while 循环、一个倒数计数的循环、一个用 goto 语句构建的古怪循环。所有这些在语法上都不同，但在语义上，它们都应该产生相同的结果。这个测试简单而强大：对于给定的 ，我们运行所有循环变体，并同时根据数学公式计算结果。如果任何结果不一致，我们就发现了编译器循环优化逻辑中的一个错误。我们正在使用一个永恒的数学定律来验证一个现代软件。
同样的想法也适用于更复杂的转换，比如尾递归消除，即将一个递归函数转换成循环以防止栈溢出。我们可以编写一个极其复杂的递归函数和一个等价的迭代版本。如果编译器对递归版本的自动优化没有产生与我们手工制作的迭代版本完全相同、逐位一致的结果，我们就知道它的转换是有缺陷的。
在现代世界，编译器扮演着第三个关键角色：它是构建安全软件的合作伙伴。像栈金丝雀（stack canaries）这样的特性旨在检测缓冲区溢出攻击。但是，当优化与安全特性发生冲突时会发生什么？
这正是尾调用优化（TCO）和栈金丝雀的情况。栈金丝雀是在栈上放置的一个秘密值，函数在返回前会检查它，以确保其控制数据未被破坏。然而，TCO 的工作方式是让函数 f 直接跳转到函数 g，从而绕过了 f 自己的返回序列——因此也绕过了它的金丝雀检查。攻击者可能会在 f 中溢出一个缓冲区，破坏 g 最终将使用的返回地址，而本应阻止此事的 f 中的检查却永远不会运行。
一个具有安全意识的编译器必须解决这个冲突。正确的解决方案是，编译器必须在进行到 g 的尾调用跳转之前，插入一个对 f 金丝雀的特殊检查，我们可以通过测试来验证这一点。优化得以保留，但不是以牺牲安全为代价。
威胁可能更加微妙。优化器可能会执行“函数克隆”，为不同的上下文创建特定、更快的函数版本。想象一个函数包含一个关键的权限检查。编译器可能会为某个特定上下文创建一个克隆，并认为在该上下文中检查是多余的，从而将其优化掉。如果编译器的分析是错误的，它就刚刚制造了一个安全漏洞。先进的编译器测试使用形式化方法，利用称为 SMT 求解器的逻辑推理引擎，来分析函数的每个克隆版本。验证器会检查，对于通往敏感操作的每条可能路径，安全检查要么存在，要么其条件在逻辑上被该特定克隆的上下文保证为真。如果它发现一条路径没有保护，就会标记一个潜在的安全漏洞。
我们所见的应用不仅仅是孤立的技巧；它们构成了一个系统性验证编译器的宏大策略。当前最先进的技术通常被称为基于属性的差分测试。
我们不是手动编写测试，而是构建一个程序——一个“生成器”——来创建数以百万计的随机、通常很古怪但语义上有效的程序。对于每个生成的程序，我们有两个真理来源：一个执行代码缓慢但正确的解释器，以及我们想要测试的编译器。我们通过这两者运行程序，如果它们的输出有任何不一致，我们就发现了一个错误。为了精确定位原因，我们可以使用自动化工具，通过逐个有条不紊地禁用优化模式（一个类似二分法的过程），然后将失败的程序缩减到仍然能触发该错误的最小可能示例。
这种严谨的方法延伸到编译器的所有角落。我们可以根据正式的应用程序二进制接口（ABI）规范自动生成测试，以确保我们编译的代码能够正确地与操作系统和其他库通信——检查参数是否在正确的寄存器中传递，栈是否正确对齐，以及函数调用“契约”中所有精细部分是否都得到遵守。
在即时（JIT）编译器的世界里，挑战达到了顶峰。JIT 编译器在代码运行时根据运行时假设进行优化。如果一个假设被证明是错误的，JIT 必须安全地“去优化”回一个较慢的版本。这需要保存程序状态的快照，称为栈图（stack maps）。一个复杂的优化，比如为了消除分支而复制代码，很容易使这些快照失效。测试这一点需要强制在每个可能的代码路径上进行去优化，并确保重建的状态是完美的，同时还要验证在触发去优化之前没有执行任何不可逆的副作用。这类似于测试一台时间机器，确保它总能返回过去而不会产生悖论。
从验证 CPU 的二进制补码算术到确保克隆函数中安全检查的逻辑完整性，编译器测试是支撑整个软件世界可靠性和安全性的无形学科。它是硬件知识、语言理论、数理逻辑和安全工程的美妙综合——所有这些都为了一个不懈的努力：信任，但要验证。