玻尔百科在对更快软件的不懈追求中，编译器优化是默默无闻的英雄，它们一丝不苟地优化代码，以消除浪费性能的操作。虽然简单的技术可以移除明显的重复工作，但面对复杂的程序结构时，它们往往力不从心，导致显著的性能提升空间未能被利用。部分冗余消除（Partial Redundancy Elimination, PRE）这一更复杂、更强大的策略正是为了解决这一问题。本文将深入探讨 PRE 的优雅世界，这项技术不仅能发现冗余，还会主动地重排代码，为优化创造更多机会。首先，在“原理与机制”部分，我们将剖析赋予编译器“远见”的核心数据流分析——可用性分析和预期性分析。随后，在“应用与跨学科联系”部分，我们将探讨 PRE 如何统一众多其他优化，以及其基本理念如何延伸至区块链和 Web 浏览器等不同领域，揭示出一种高效系统设计的普适模式。
想象你是一位一丝不苟的记账员，发现自己一遍又一遍地对同一列数字求和。你的常识会告诉你，第一次计算后就应该写下结果，然后直接复用。这个简单而强大的想法是许多编译器优化的灵魂。编译器在力求让我们的程序运行得更快的过程中，总是在寻找可以不必做的工作。
最直接的情况是公共子表达式消除（Common Subexpression Elimination, CSE）。如果编译器看到 $x := a + b$，稍后又看到 $y := a + b$，它通常可以直接将第二条指令重写为 $y := x$，从而避免一次冗余计算。但如果情况更复杂呢？
考虑程序中的一个岔路，一个简单的 if-else 语句。在 then 分支，你计算了 $a + b$。在 else 分支，你也计算了 $a + b$。在两个分支重新汇合后，编译器可能会发现另一次对 $a + b$ 的计算。我们的直觉强烈地感觉到这是浪费。无论走哪条路径，我们都在做同样的工作。为什么不在岔路之前就算好一次 $a + b$ 呢？
这正是简单的 CSE 常常力有不逮之处。在许多经典设计中，要消除一个后来的计算，它必须被一个更早的计算所支配（dominate），这意味着在通往后来计算的每一条可能路径上，更早的那个计算都保证已经运行过。在我们的 if-else 例子中，then 分支中的计算并不支配 else 分支中的计算，反之亦然。它们位于平行的“时间线”上。
正是这类难题引导我们走向一个更深刻、更优美的思想：部分冗余消除（Partial Redundancy Elimination, PRE）。PRE 是一种具有远见的优化。它不仅审视已经做了什么，还主动地推断将要做什么，并且不畏于重排程序以创造更多优化机会。例如，它可以像我们的直觉所建议的那样，将 $a + b$ 的计算提升到 if-else 分支之前。PRE 将一个仅部分冗余的计算——在某些路径上冗余，但在其他路径上不冗余——转化为一个完全冗余的计算，从而可以被轻易消除。
编译器如何培养出这种远见？它不能仅仅“感觉”到某个计算是浪费的。它需要一种严谨的方法。这种方法就是数据流分析（data-flow analysis），一种优美的技术，它让编译器能够系统地推断程序的属性。对于 PRE，这种分析建立在两个优雅而对立的支柱之上。
首先，编译器审视过去。在程序的任何给定点，它会问：“在通往此点的每一条路径上，有哪些表达式保证已经被计算过，并且其操作数未曾改变？” 这被称为可用表达式分析（Available Expressions analysis）。这是一种前向分析（forward analysis），因为信息“流动”的方向与程序执行的方向相同。如果基本块 计算了 $a + b$，该信息会向前流动到它的后继节点。如果来自基本块 和基本块 的路径汇合，只有当该表达式在两条路径上都可用时，才认为它在汇合点之后可用。这是一个严格的“全路径”要求。
第二个支柱提供了远见的关键要素。在任何给定点，编译器会展望未来并提问：“从这里开始，是否保证表达式 $a + b$ 会在每一条可能采取的路径上，在其操作数 或 被改变之前，被计算？” 这个属性被称为预期性（anticipatability）（或在某些文献中称为十分繁忙表达式 (very busy expressions)）。这是一种后向分析（backward analysis）。对未来计算的需求向后传递信号，逆着程序执行流的方向。如果一个 if-else 语句的两个分支最终都会计算 $a + b$，那么在 if 语句开始之前，该表达式就被认为是可预期的。
这告诉编译器，提早进行计算是安全的。如果你无论如何都要做这项工作，早点做并不会改变结果（假设该工作没有副作用），但可能会让你免于多次重复。
PRE 的精妙之处在于这两种相反分析的相互作用。算法寻找程序中某个表达式可预期（未来需要它）但尚不可用（它没有在所有先前的路径上都被计算过）的点。这正是部分冗余的定义。接下来的策略异常简单：在缺失该计算的路径上插入它。这使得表达式变为完全可用，将部分冗余转化为完全冗余，然后就可以毫不犹豫地将其消除。
让我们观察这一策略的展开。在一个程序中，如果 $a+b$ 在 if 的一个分支中需要，但在另一个分支中不需要，然后在它们汇合后又需要一次，那么汇合后的计算就是部分冗余的。编译器在完成分析后，看到 $a+b$ 在缺少它的那条路径上是可预期的。就像棋手走一步准备棋一样，它将 $a+b$ 的计算插入到那个“空”分支中。突然之间，$a+b$ 在所有通往汇合点的路径上都变得可用。曾经部分冗余的计算现在变成了完全冗余，编译器便将其移除。
但一个优秀的棋手看到的不仅是显而易见的棋步。如果冗余的表达式被伪装起来了呢？程序可能在一个地方计算 $a + c$，在另一个地方计算 $b + a$，而实际上 $c$ 只是 $b$ 的一个副本。简单的文本比较无法发现冗余。但更复杂的分析，如全局值编号（Global Value Numbering, GVN），能够看穿这种伪装。GVN 为程序中每个不同的值分配一个唯一的“值编号”。它理解 $+$ 是可交换的，并且 $c$ 和 $b$ 持有相同的值。因此，它能识别出 $a+c$ 和 $b+a$ 实际上是相同的计算。这使得 PRE 能够在一个更深的语义层面上运作，将不同形式的冗余统一到一个强大框架中。
到目前为止，我们的世界是纯粹的算术世界。但真实的程序是混乱的。它们有副作用，会引发异常，还包含复杂的循环。一个真正 masterful 的优化器必须小心翼翼地驾驭这个世界。
考虑一个看似无害的除法 $z/w$。如果移动它，这可能是一颗定时炸弹。如果 $w$ 恰好为零，原始代码可能在一个 try-catch 块内捕获了由此产生的异常。如果我们把这个除法提升到 try 块之外，异常现在就会在一个没有被捕获的地方发生，从而使程序崩溃。这对编译器来说是一个根本性的错误：它改变了程序的可观察行为。
解决方案是所需谨慎操作的绝佳示范。编译器不会盲目地移动 $z/w$，而是可以有条件地移动它。在 try 块之前，它可以插入 if (w != 0) t := z/w;。这只在安全的情况下预先计算结果。然后，在 try 块内部，它用一个检查替换原来的除法：如果 $w$ 不为零，就使用预先计算的值 ；否则，再次执行 $z/w$。第二次执行看似多余，但这是一个巧妙的佯动。它被放在那里，正是为了在原始程序会触发异常的精确时刻重新触发它，从而完美地保留程序的行为。
对于有副作用的操作，也必须同样小心。考虑短路表达式 x y。如果 $x$ 有副作用（比如向屏幕打印信息）并且其值为 false，原始程序将永远不会求值 $y$。我们不能不考虑 $x$ 的情况就简单地优化 $y$。解决方案是让隐藏的依赖关系显式化。编译器可以创建一个新的布尔“卫兵”变量 ，只有当 $x$ 被求值并且结果为 true 时， 才被设为 true。现在，对 $y$ 的计算就由 明确地守护。这将程序的控制依赖（执行流程）转化为了*数据依赖*（对 值的依赖）。一旦条件被捕获在一个变量中，被守护的 $y$ 的计算就可以像任何其他表达式一样被优化。
在循环中，PRE 必须与其他优化协同工作。它可能会发现像 $L(A[i])$ 这样的表达式（从数组中加载）在单次迭代内部是冗余的。它可以消除这种冗余。但它也必须认识到 $L(A[i])$ 不是循环不变的——它的值随着索引 $i$ 的变化而变化——因此它不能被完全提升到循环之外。
最后，编译器的工作不是在真空中完成的。它编写的程序可能有一天需要人类来调试。如果 PRE 将一个计算从第 50 行移到第 20 行，那么在第 50 行设置断点的程序员会感到完全困惑。一个现代的、支持调试（debug-aware） 的编译器知道这一点。它将源代码行视为软性障碍，倾向于不以会违反程序员心智模型的方式移动代码。当必须这样做时，它会生成一个丰富的映射（使用像 DWARF 这样的格式），作为调试器的指南，告知：“我知道源代码说这个值是在第 50 行计算的，但在我的优化版本中，你可以在这个寄存器中找到它的结果，这个结果是在第 20 行计算的”。这是一种协定，是在对机器性能不懈追求与人类对理解的基本需求之间的妥协。
从一个避免重复工作的简单想法出发，我们穿行于优雅的算法、对偶分析以及真实世界代码的 messy 现实。部分冗余消除不仅仅是一项优化；它是一种思维模式，一种洞察程序隐藏结构和潜力的方式，也是现代编译器中蕴含的宁静而优美的智能的证明。
在掌握了部分冗余消除（PRE）的精巧机制后，我们现在踏上一段旅程，去见证它的实际应用。如同万能钥匙，PRE 的原理不仅在代码的隐秘角落解锁效率，更在广阔的计算问题领域中大显身手。我们将看到，PRE 不仅仅是一项单一的优化；它是一个统一的框架，一个强大的透镜，通过它我们可以理解冗余工作的本质。它的理念远远超出了编译器，回响在 Web 浏览器的架构中，甚至在区块链的逻辑里。
初看起来，编译器的优化套件可能像一个杂乱的工具箱，装满了数十种专用工具：循环不变代码外提、强度削减、公共子表达式消除等等。然而，深入观察会发现，PRE 常常作为一个统一理论，优雅地涵盖了许多这些看似分离的思想。
让我们从一个简单的循环开始。想象一个表达式如 $a+b$ 在一个循环体内的几个不同条件分支中被计算。如果在单次迭代内，变量 和 在这些计算之间没有被修改，但其中一个（比如 ）在迭代结束时被修改了，那么表达式 $a+b$ 就不是循环不变的。它不能被完全提升到循环之外。然而，在循环的任何一次遍历中，多次计算它都是浪费的。这正是 PRE 大放异彩的地方。它认识到该表达式在循环体内的第一次计算之后的所有路径上都是完全可用的。一个简单的公共子表达式消除（CSE）可能难以处理分支的复杂控制流，但 PRE 提供了一种系统性的方法。它识别出循环体中支配所有使用的最早点——通常就在循环顶部——并插入一次计算，比如 $c := a+b$。该迭代内所有后续的使用都被替换为 。这个简单的行为消除了跨条件路径存在的部分冗余，确保加法在每次迭代中只发生一次。
当我们考虑涉及循环归纳变量的表达式时，这种“智能代码移动”的概念变得更加深刻。一个经典的优化是强度削减（strength reduction），旨在将循环内昂贵的操作（如乘法）替换为廉价的操作（如加法）。考虑一个数组地址计算，如 $\text{base} + i \cdot \text{stride}$，其中 $i$ 是一个每次迭代递增 1 的归纳变量。乘法 $i \cdot \text{stride}$ 的代价很高。粗略一看，这个表达式似乎不是循环不变的，因为 $i$ 在变化。然而，当 PRE 应用于这种结构时，它会执行一个漂亮的转换。表达式 $\text{base} + i \cdot \text{stride}$ 是我们所谓的*派生归纳变量*。它在一次迭代中的值与下一次迭代中的值通过一次简单的加法相关联：新值就是旧值加上 stride。
PRE，或像 Lazy Code Motion 这样的专门变体，可以利用这一点。它将初始计算 提升到循环的预备头（preheader）。然后，在循环内部，它用临时变量 替换所有 $\text{base} + i \cdot \text{stride}$ 的出现。最后，在循环体的末尾，它插入一个简单的更新：。昂贵的乘法被简化为每次迭代一次加法。这揭示了一个非凡的真理：强度削减不是一个独立的、临时的技巧；它是将 PRE 的原则性数据流分析应用于算术序列的自然结果。在使用静态单赋值（SSA）形式的现代编译器中，这通过循环头部的 -函数优雅地处理，这些函数合并了来自预备头的初始值和来自循环回边的更新值。
然而，这种统一的力量取决于 PRE 是否是一个“团队合作者”。PRE 通常在代码的句法结构上操作。它可能不会意识到 $(a+b)+c$ 和 $a+(c+b)$ 是相同的。这时，阶段顺序（phase ordering）就变得至关重要。一个更早的遍，如全局值编号（GVN），它理解代数属性如结合律和交换律，可以首先将这些表达式规范化为一种共同的句法形式。一旦 GVN 揭示了这种“深层相等性”，PRE 就可以介入并识别出之前隐藏的部分冗余，从而移动代码并消除浪费。类似地，一个简单的复写传播（copy propagation）遍，在赋值 $t := x$ 后用 $x$ 替换变量 $t$，可以使 $t+y$ 和 $x+y$ 这两个表达式在句法上相同，从而使 PRE 能够找到它原本会错过的冗余。
这种协同作用还延续到过程内联（procedure inlining）。编译器通常不能跨函数调用边界进行优化。函数 f() 内的内存加载 $A[i]$ 对调用者来说是一个黑盒。但如果 f() 被内联，它的代码就被暴露出来。突然间，PRE 可以看到这次加载与调用者代码中另一次对 $A[i]$ 的加载是部分冗余的。然后，它可以将一次加载提升到一个支配点，将值存储在寄存器中，并重用它，从而消除一次昂贵的内存访问。
PRE 的适用性远不止简单的算术运算。它消除的“计算”可以是任何有值的操作，包括语言中隐含的安全检查。在像 Java 这样的语言中，每次对象解引用 p.field 都包含一个对 p 的隐式空指针检查。如果你程序的一条路径解引用了 p，编译器现在就知道 p 不为 null。如果该路径后来与另一条没有检查过 p 的路径汇合，并且它们收敛到一个包含显式检查 if (p == null) 的块，那么这个显式检查就是部分冗余的。PRE 的数据流框架可以用来在第二条路径上插入一个空指针检查，使得汇合点的检查完全冗余，从而可以被移除。这将安全检查的开销转变成了优化的候选对象。
但如果优化并非明确的胜利呢？提升一个计算有时会将其引入到一个以前从不需要它的路径上。这可能会加速原本存在该计算的“热”路径，但会减慢新引入它的“冷”路径。这种权衡值得吗？
这就是 PRE 进入基于剖析的优化（Profile-Guided Optimization, PGO）现代世界的地方。编译器可以在典型工作负载下运行程序，并收集关于哪些执行路径最常被采用的数据或“剖析”。有了这些统计知识，编译器可以做出数据驱动的决策。它可以计算预期的性能增益：在热路径上节省的周期数乘以它们的频率，减去在冷路径上损失的周期数乘以它们的频率。如果净结果为正，就应用 PRE 变换；否则，保留原来的、优化程度较低的代码。这将 PRE 从一个纯粹的机械变换提升为一个复杂的、基于概率的决策引擎。
也许部分冗余消除最迷人的方面在于其核心逻辑——在一个具有分支路径和共享状态的系统中识别并移除冗余工作——是一种在截然不同的领域中出现的根本模式。
考虑区块链技术的世界。一个核心任务是验证一个新的交易区块。这通常涉及多个可能发生在不同逻辑“分支”上的步骤，例如验证分支（检查内部一致性）和共识分支（检查与网络的一致性）。两个分支可能都需要计算加密的 hash(block)。这个昂贵的计算是部分冗余的。应用 PRE 哲学，我们希望在分支发散之前只计算一次哈希。但这安全吗？如果一个分支在另一个分支使用提升后的哈希值之前修改了 block 对象的某个字段怎么办？提升后的值就会是过时的。
这正是编译器在移动代码时所担心的同一种“扼杀”（kill）条件。解决方案与编译器的方法如出一辙。一种方法是静态证明：严格分析代码，证明在提升的计算与其使用之间，不可能发生对区块哈希字段的任何修改。一种更灵活的方法是动态卫兵：在区块对象内部嵌入一个版本号，每次修改时递增。优化过程将读取版本号，计算哈希，然后在即将使用预计算的哈希值之前，检查版本号是否未变。如果未变，该值就是安全的。否则，重新计算哈希。这是 PRE 所体现的严谨推理在现实世界中的一个优美类比。
另一个惊人的相似之处出现在Web 浏览器的架构中。渲染一个网页涉及一个操作流水线：样式计算、布局（或“回流”）和绘制。对单个元素的更改可能会使其父元素和兄弟元素的布局失效，从而强制重新计算。想象一个场景，两个独立的失效触发了两个不同的更新路径，两者都需要重新计算同一个父容器的布局。这次重新计算，你猜对了，是部分冗余的。浏览器的渲染引擎要高效，就必须像一个优化编译器那样行事。它必须找到一种方法，只计算一次这个布局信息。高效地在变更后重新计算网页布局的挑战，在结构上类似于 PRE 为程序控制流图解决的问题。此外，“遮挡剔除”（occlusion culling）——不费力去绘制被其他元素遮挡的元素——的做法，与 PRE 经常促成的死代码消除（Dead Code Elimination）直接对应。渲染流水线的数据依赖图就是一个程序，而要使其快速运行，需要同样深刻的冗余消除原则。
从一个简单的循环优化，到浏览器性能的核心，再到区块链的安全性，PRE 的影子无处不在。它教导我们，高效的系统设计往往在于洞察隐藏的冗余，并拥有一种有原则的方法来消除它们。这证明了计算机科学中最强大的思想并非狭隘的技巧，而是可推广的思维模式，揭示了复杂世界中潜在的统一性。