玻尔百科在现代软件开发中，编译器的角色远不止简单的翻译。它如同一位技艺精湛的工匠，通过应用一系列转换（即“遍”）来优化代码，以提升其速度、减小其体积并提高其效率。然而，一个深刻而持久的挑战并不在于这些优化遍本身，而在于它们的执行顺序。这就是阶段排序问题：确定运行优化的最佳顺序。一个次优的序列可能导致各个遍相互掣肘，抵消优化效果，甚至降低性能。本文旨在揭开这一复杂主题的神秘面纱。首先，在“原理与机制”一节中，我们将探讨优化遍之间相互作用的基本方式，从协同的促成行为到破坏性的失效碰撞，再到复杂的权衡。随后，“应用与跨学科联系”一节将展示这些选择在现实世界中的后果，将该问题与硬件架构、资源管理以及编译器本身的工程设计联系起来。
想象一下你正在制作一把木椅。你有一系列任务：切割木块、打磨光滑、钻孔、组装部件，最后涂上一层清漆。你应该按什么顺序来做这些事？显而易见，你应该在涂漆之前打磨木块。试图打磨一个黏糊糊的、上了漆的表面将是一场灾难。同样，你必须在组装之前切割木块。操作的顺序并非任意，而是受到一个深刻的逻辑结构所约束。一些步骤会促成其他步骤，而某些顺序则纯粹是事倍功半。
软件编译器的世界也惊人地相似。编译器的任务是将人类编写的高级源代码翻译成计算机处理器能实际执行的低级机器指令。但现代编译器所做的远不止翻译，它还进行优化。它运行一系列称为遍（passes）的转换，每个遍都旨在使最终程序运行得更快、使用更少内存或消耗更少电力。就像制作椅子一样，应用这些遍的顺序——即阶段排序——不仅重要，它还是计算机科学中最深刻、最具挑战性的问题之一。处理得当，就能将一个迟缓的程序变成一个高性能的杰作；处理不当，则意味着优化会相互掣肘，有时甚至会使代码变得更糟。
在最理想的情况下，编译器优化遍会以完美的协同作用协同工作。一个遍搭建好舞台，为下一个遍施展其魔法创造绝佳机会。这是一种促成交互（enabling interaction）。
考虑消除冗余计算的任务。如果你的代码多次计算$a + b$，这是一种浪费。一个名为全局值编号（Global Value Numbering, GVN）的优化遍旨在找到这些相同的计算，并用一个单一的结果替换它们。但如果代码中同时包含$a + b$和$b + a$呢？对人来说，它们显然是相同的。但对于一个寻找相同文本的简单计算机程序来说，它们是不同的。这时，一个称为规范化（canonicalization）的遍，通常叫做指令合并（Instruction Combining），就派上用场了。它的工作是通过应用代数规则来整理代码。例如，它可以强制规定，对于像加法这样的可交换操作，操作数必须始终按字母顺序排序。
如果我们先运行指令合并，它会将所有$b + a$的实例转换为$a + b$。当GVN接下来运行时，它面对的是一个一目了然的场景，所有等价的表达式现在在语法上都是相同的。它可以轻松地消除每一个冗余。但如果我们颠倒顺序，GVN先运行，它将无法识别$a + b$和$b + a$是相同的。后来的指令合并遍虽然整理了表达式，但为时已晚——GVN的机会已经错失。第一个遍促成了第二个遍。
这种促成关系随处可见。现代编译器通常希望将变量保存在处理器超高速的本地存储器，即寄存器中。一种名为内存到寄存器提升（Memory to Register Promotion, Mem2Reg）的优化可以做到这一点，但它通常只对简单的标量变量（如单个整数）起作用。如果你的代码使用了一个包含多个字段的复合对象或struct呢？Mem2Reg无法处理它。这时，一个名为聚合体的标量替换（Scalar Replacement of Aggregates, SROA）的遍就登场了。它的唯一目的是将这些聚合对象分解为一组简单的标量变量。如果SROA先运行，它将复杂的对象解构成多个部分，Mem2Reg随后可以轻松地将这些部分提升到寄存器中。如果Mem2Reg先运行，它只看到那个庞大而无法处理的对象，什么也不做，而后来的SROA遍创建了新的标量变量，但这些变量永远不会被提升，因为Mem2Reg已经完成了它的工作。
在循环优化中可以看到一个优美且更长的促成遍链。首先，一个构建静态单赋值（Static Single Assignment, SSA）形式的遍通过为每个新值赋予唯一名称来明确数据流。这消除了歧义，并允许依赖性分析（Dependence Analysis）遍确定地证明两个相邻的循环可以安全地合并为一个。这种循环融合（Loop Fusion）随后将生成值的代码紧挨着消费它的代码放置。最后，寄存器分配器（Register Allocator）看到这种紧密的局部性，便可以将该值保存在一个快速寄存器中，避免了到主内存的缓慢往返。每一个遍都为下一个铺平了道路，形成了一系列级联的优化。
阶段排序的阴暗面是，一个遍无意中破坏了另一个遍正在寻找的模式。这是一种失效交互（disabling interaction）。
一个经典的例子涉及尾调用优化（Tail-Call Optimization, TCO），这是编写高效递归函数的关键技术。TCO可以将递归调用转换为一个简单的循环，防止程序在深度递归时耗尽内存（即“栈溢出”）。然而，TCO通常很脆弱；它寻找一种非常特定的语法模式，如return F(x-1);。现在，假设一个程序员写了一个辅助函数，代码看起来像return Identity(F(x-1));，其中Identity只是返回其输入。一个名为内联（Inlining）的遍可能会看到这个简单的辅助函数，并决定通过用辅助函数的主体替换调用来“帮忙”。这将代码转换为类似tmp = F(x-1); return tmp;的形式。程序的含义没有改变，但TCO正在寻找的语法模式现在被破坏了。TCO被失效了。
相反，如果我们先运行TCO，它会识别出尾调用（也许它足够聪明，能看穿恒等函数）并将递归转换为循环。随后的内联遍便无事可做，因为它本想内联的调用已经被优化掉了。在真实世界的场景中，这种顺序选择可能意味着一个程序能以恒定的内存量完美运行，而另一个程序则在消耗数GB内存后崩溃。
有时，一个优化甚至可能“聪明反被聪明误”。考虑一个循环不变量表达式$x + y$，它在循环内的某些路径上计算，但并非所有路径。一个高级的部分冗余消除（Partial Redundancy Elimination, PRE）遍可以识别这一点，并将计算完全提升到循环之外，只执行一次。这是一个巨大的胜利。然而，像GVN这样的另一个优化可能会先到一步。看到部分冗余，它可能会决定通过在缺少计算的路径上插入$x+y$的计算，使表达式完全冗余。这样做时，它用一个特殊的$\phi$-function替换了原始表达式，这是一种合并来自不同控制流路径的值的构造。虽然这是一个有效且局部有益的转换，但它现在向PRE遍隐藏了那个简单的、可提升的$x + y$表达式。GVN的局部聪明破坏了将代码提升出循环的更强大的全局优化。
通常，阶段排序问题不是关于一个正确和错误的答案，而是关于在相互竞争的目标之间进行权衡。两个遍可能陷入根本性的冲突中，而“最佳”顺序取决于我们最看重什么：原始速度、代码大小还是功耗。
最著名的冲突是“可怕的双胞胎”：指令调度（Instruction Scheduling）和寄存器分配（Register Allocation）。调度器的目标是重排指令，以保持处理器功能单元的繁忙并隐藏延迟（例如，等待内存数据的延迟）。为此，它通常会将一个值的定义移到远离其最后一次使用的地方。寄存器分配器的目标是将程序中所有“存活”的变量装入数量有限的物理寄存器中。通过将定义和使用分开，调度器延长了变量的存活区间（live range），增加了在同一时间有太多变量存活的可能性。这种高寄存器压力（register pressure）可能迫使分配器将值溢出（spill）到慢速内存中，引入了代价高昂的内存操作，这些操作可能会抵消调度器辛苦获得的所有收益。你应该先调度，冒着溢出的风险吗？还是应该先分配，过度约束调度器？这是一个深刻的两难问题，编译器通过复杂的迭代启发式方法来解决。
内联（Inlining）和寄存器分配（Register Allocation）之间也存在类似的权衡。内联函数对性能非常有利；它消除了调用开销，并向其他优化器暴露了更多代码。但它也增加了函数的大小，并且像调度一样，显著增加了寄存器压力。编译器必须做出选择。也许在寄存器分配之前积极内联更好，希望性能提升能超过一些额外溢出的成本。或者，也许先进行寄存器分配，然后只保守地内联几个函数更好。
“正确”的选择可能取决于上下文。如果你正在为一台强大的服务器编译，你可能最看重速度。如果你正在为内存有限的微型嵌入式设备编译，你可能会对代码大小的增长给予非常重的惩罚。这可以通过一个成本模型来形式化，例如，其中是执行时间，S是代码大小，权重和代表你的优先级。通过对不同阶段顺序的影响进行建模，编译器可以基于这些权重做出有原则的决策。
面对数十甚至数百个优化遍，可能的排序数量是天文数字（对于个遍，有种），大到无法穷尽探索。这就是阶段排序问题的核心：寻找一个“黄金序列”在计算上是不可行的（NP难问题）。
那么，编译器编写者该怎么办呢？他们结合使用理论、经验证据和巧妙的搜索策略。他们研究常见的交互作用，并建立一个对大多数程序都表现良好的默认顺序（例如，在冗余消除之前进行规范化）。对于特别重要的序列，他们可能会使用像集束搜索（beam search）这样的启发式方法，即探索几个有希望的部分序列并剪除其余部分，希望能找到一个好的解决方案而无需搜索整个空间。他们越来越多地转向机器学习，在庞大的代码库上训练模型，以预测给定代码段的最佳阶段排序。没有一刀切的答案。
仿佛这还不够复杂，机器中还有一个最终的、微妙的幽灵：确定性（determinism）。你会期望，在完全相同的机器上编译完全相同的代码，每次都应该产生完全相同的输出。令人震惊的是，这并非总是如此。
想象一个处理一组指令的优化。如果它将这些指令存储在标准的哈希表中，它遍历它们的顺序可能取决于随机的内存地址或环境库实现的细微差异。如果该优化的逻辑中有一个依赖于这种不稳定顺序的平局决胜规则，编译器的输出就可能变得不确定。一次运行可能产生一个与下一次略有不同，也许更快或更慢的程序。
对于专业工具来说，这是不可接受的。为了解决这个问题，编译器必须以极大的纪律性进行工程设计。平局决胜规则不能依赖于编译过程本身的任何产物。相反，它们必须基于被编译程序固有的属性——例如，从程序的控制流图和指令在其基本块内的位置派生出的稳定排序。这确保了优化那美丽而复杂的舞蹈不是一场混乱的即兴表演，而是一场每次都完美编排和可重复的演出。
从简单的促成行为到复杂的权衡，再到对确定性的深切需求，阶段排序问题揭示了编译器优化远非一个已解决的清单问题。它是一个充满活力且引人入胜的领域，在这里，逻辑、启发式方法和工程严谨性相遇，共同释放我们软件的真正潜力。
在探索了编译器优化遍之间错综复杂的舞蹈之后，人们可能会想：这仅仅是计算机科学家的一个抽象谜题，一场与机器对弈的棋局吗？答案是响亮的“不”。阶段排序问题不是一个理论上的奇谈；它是一个核心的、实际的挑战，为数字世界注入了生命和效率。它的触角从处理器最深的硅谷延伸到软件系统的宏伟架构，它所体现的原则在我们如何处理科学和工程中的复杂问题上产生共鸣。让我们踏上一段旅程，探索其中一些引人入胜的联系。
从本质上讲，编译器是一个翻译器，将人类思想的抽象语言转换为处理器具体的物理动作。但它不仅仅是一个翻译器，它是一位大师级的工匠。它必须雕琢代码，使其完美契合处理器的架构。阶段排序问题就是决定使用哪些凿子，以及按什么顺序使用的问题。
想象一个具有SIMD（单指令，多数据流）能力的处理器——这是一个强大的工具，可以同时对一整组数字执行相同的操作，就像一个面包师用一个饼干模具一次压出十几块饼干一样。要使用这个工具，“面团”（我们的数据）必须被整齐地、足够大地铺开。我们代码中的一个简单循环可能就像一系列小的、独立的面团块。如果我们首先运行向量化遍（），它会看到这些小面团块，并断定它的大饼干模具毫无用处。然而，如果我们首先运行循环展开遍（），我们实际上是将这些小面团块合并成一个大的、平坦的面片。现在，当向量化遍运行时，它看到了应用其强大工具的绝佳机会，可以并行地压出操作，从而极大地加速程序。顺序不仅重要，它还是使优化成为可能的根本原因。
这种“促成”原则无处不在。有时，一个循环包含混合操作，其中一些依赖于前一次迭代，而另一些则不依赖。循环携带的依赖关系就像一根穿过我们面团的线，阻止饼干模具干净利落地压制。一个聪明的编译器可以首先应用循环分发（），这就像把面团切成两个独立的薄片：一个带有缠结的线，一个没有。向量化器仍然无法在缠结的那块上操作，但它现在可以在干净的薄片上大显身手，将其完全向量化。通过首先隔离有问题部分，我们促成了对其余部分的优化。
这种艺术性甚至更深。现代处理器拥有高度专门化的指令。例如，一个融合乘加（Fused Multiply-Add, FMA）操作可以在一个步骤内计算$a \cdot b + c$，这比一个独立的乘法后跟一个加法要快。编译器可能在原始代码中找不到这种模式。然而，在对一个循环进行向量化之后，它可能会创建一系列向量乘法和向量加法指令。随后的一个“窥孔”优化遍（）——它寻找小的、局部的模式——现在可以发现这个相邻的对，并将它们融合成一个单一、更高效的FMA指令。这个机会完全是由前面的向量化遍创造的。以相反的顺序应用这些遍将不会带来任何好处，因为窥孔优化器将找不到任何可以融合的向量指令。
并非所有的优化都是关于促成。通常，它是一场关于权衡的微妙游戏，一场在冲突目标之间的平衡表演。在保持处理器执行单元繁忙与管理其有限的短期内存——寄存器——之间的永恒斗争中，这一点最为清晰。
指令调度（）旨在重排操作以最大化并行度并隐藏延迟，使处理器的电路不停地嗡嗡作响。一个激进的调度器可能会试图尽早开始一个循环迭代的所有数据加载操作。这听起来是个好主意，但它制造了一个问题：所有加载的数据都必须存放在某个地方。处理器的“手”是它的寄存器，而且数量非常有限。如果调度器迫使处理器一次性持有太多临时值，寄存器分配器（）会发现它已经没有“手”可用了。它被迫将值“溢出”到主内存中——这个过程类似于把一个工具放在一个遥远的工作台上，片刻之后又不得不走过去再把它捡起来。这些溢出可能非常慢，以至于完全抵消了激进调度所带来的收益。
替代方案是什么？一种不同的阶段排序：在调度之前进行寄存器分配。寄存器分配器意识到其局限性，可能会以最小化存活值峰值的方式将值分配给寄存器，即使这在局部看来不是最优的。调度器在之后运行，现在受到了这种分配的约束。它可能会产生一个并行度较低的调度，但却避免了溢出的灾难性成本。结果呢？一个实际上更快的程序。指令级并行与寄存器压力之间的这种张力是一个经典的阶段排序困境，正确的选择取决于具体的代码和目标硬件。
这种平衡行为超出了处理器本身。考虑一下嵌入式系统的世界，比如汽车、医疗设备或卫星中的计算机。在这里，内存不仅仅是一种性能资源；它是一种硬性的物理约束。最终编译的代码必须符合严格的大小预算（）。内联一个函数（）是一种强大的性能优化；它通过将callee（被调用者）的代码直接复制到caller（调用者）中来消除函数调用的开销。但这种复制可能导致代码体积膨胀。另一个单独的遍，大小优化（），可以通过共享公共指令序列来缩小代码。
现在，哪种顺序更好？如果先进行内联，你可能会创建出超过代码大小预算的庞大、单一的函数。之后运行的大小优化器可能无法充分压缩重复的代码。但如果你先运行大小优化器，它会缩小将被内联的函数。现在，当内联器运行时，它复制的是更小、优化过的版本。最终的代码更紧凑，可能在符合预算的同时，仍然获得内联的性能优势。在这种高风险的环境中，正确的阶段顺序可能决定了一个产品是成功上市还是不可行。
编译器并非在真空中运行。它是庞大的工具、惯例和动态行为生态系统的一部分。一个智能的编译器必须意识到这个上下文，而阶段排序通常是整合这种外部知识的机制。
考虑一个即时（Just-In-Time, JIT）编译器，就是那种驱动现代Web浏览器和高级语言运行时的编译器。它在程序运行时编译代码。这给了它一个超能力：它可以观察程序实际上是如何被使用的。一个基于性能剖析的优化（Profile-Guided Optimization, ）遍可以收集关于哪些分支被采用、哪些没有的数据。例如，它可能会发现一个函数调用位于执行了90%时间的“热路径”上。没有这些数据，编译器可能会假设一个50/50的概率。
这些信息对内联遍（）来说是黄金。内联是一种权衡，编译器使用一个“热度”阈值来决定何时值得这样做。如果内联器在PGO之前运行，它会使用天真的50%猜测，并可能判定一个调用点不够热，不值得内联。如果它在PGO之后运行，它会看到90%的概率，意识到这个调用至关重要，并急切地将其内联以获得显著的加速。顺序决定了编译器是根据真实世界的证据行动，还是根据盲目的猜测行动。
这种意识还必须延伸到管理软件模块如何交互的静态、正式的契约。应用程序二进制接口（Application Binary Interface, ABI）就是这样一种契约。它规定了（除其他外）一个函数在使用寄存器前必须保存哪些（被调用者保存），以及哪些必须由其调用者保存（调用者保存）。这有直接的成本。当编译器考虑内联一个函数时，它实际上是在考虑消除这个契约及其相关成本。但这个成本有多大？这取决于ABI！一个重调用者保存的ABI可能会对特定函数调用的调用者施加很大的成本。内联将消除这个高昂的成本，使其成为一个非常有吸引力的优化。而在另一个重被调用者保存的ABI下，同一次调用的成本可能很低，使得内联不那么引人注目。一个真正智能的内联启发式方法，即使是在“机器无关”的层面上运行，也必须对这些下游的、ABI特定的成本有所了解，才能做出正确的权衡。阶段排序问题就变成了：我们何时注入这种特定于目标的知识？答案是，它甚至必须影响那些看似高层次的决策。
鉴于这些交互的令人眼花缭乱的复杂性，阶段排序原则的最后一个应用是在编译器本身的工程设计中。我们如何管理这种复杂性？我们如何试验新的优化遍顺序？
传统上，优化流水线被硬编码到编译器的源代码中，这是一个不透明且僵化的命令式调用序列。这使得它难以理解、修改和复现。现代编译器基础设施，如MLIR，采取了一种革命性的方法。它们不将流水线视为代码，而是视为数据。整个优化遍序列及其特定选项都在一个简单的文本格式中定义。
这种声明式的、文本化的流水线是一项启示。它自我记录且人类可读。无需重新编译编译器即可轻松修改，从而实现快速实验。最重要的是，它确保了完美的可复现性。通过将流水线字符串与编译产物一同保存，我们就拥有了该产物是如何被创建的完整且可执行的配方。任何拥有相同编译器版本的人都可以在相同的输入上重新运行那个确切的配方，并得到一个完全相同的结果。这将编译器优化的黑暗艺术转变为一门严谨且可共享的科学。虽然这并没有解决阶段排序问题，但它为我们研究和掌握它提供了所需的整洁、模块化和可配置的框架。
从与硬件的精妙共舞，到软件工程的宏大战略，阶段排序问题揭示了自己并非一个狭隘的技术问题，而是一个深刻而统一的原则。它关乎顺序、上下文和权衡——这正是构建复杂系统的本质。