玻尔百科volatile 内存访问等挑战的限制。在追求更快、更高效软件的过程中，最强大的工具之一并非更快的处理器，而是更智能的编译器。现代编译器设计的核心在于一系列优化技术，它们将人类可读的代码转换为高效的机器指令。本文将探讨这一过程的基石：公共子表达式消除（Common Subexpression Elimination, CSE）——一种仅执行一次计算并复用其结果的优雅原则。我们将探讨一个根本性问题：编译器如何安全地识别并消除这种冗余工作？这是一项充满微妙复杂性的任务。首先，在“原理与机制”一章中，我们将剖析 CSE 的工作方式，从其使用有向无环图的逻辑基础，到指针和并发带来的实践挑战。随后，“应用与跨学科联系”一章将拓宽我们的视野，揭示 CSE 的核心思想如何远远超出编译器的范畴，影响着从电子表格设计、AI 模型优化到并发编程基本原则的方方面面。读完本文，您将对这一计算效率的基本概念有深刻的理解。
想象一下，您正在解决一个复杂的物理问题，在您的方程式中，您发现需要多次计算 的值。您会一次又一次地在计算器上输入它吗？当然不会。您会计算一次，将结果记在页边，然后在它再次出现时复用这个数字。这样做更快、更省力，并减少了出错的几率。
这种不重复自己的简单直观行为，正是一项强大的编译器优化技术——公共子表达式消除（CSE）的精髓所在。编译器的任务是将您编写的人类可读代码转换成处理器能理解的快速、高效的机器语言。和您一样，智能的编译器总是在寻找避免冗余工作的方法。但是，尽管您“记下的笔记”只是一个简单的记忆行为，编译器为安全地完成这一任务所经历的过程，却是一场深入逻辑、结构和计算本质的奇妙旅程。
编译器究竟是如何“看到”您代码中两部分在做同样的事情呢？它首先将您的数学表达式分解成一种基本结构。假设您写了这样一行代码：
result = (a * b) + (c * d) - (a * b);
一种朴素的表示方法是使用一种称为解析树的结构，它完全镜像您代码的语法。每个操作和每个变量都是一个新节点。您可以看到子表达式 (a * b) 出现了两次，导致树中出现了两个独立的分支。如果我们从这棵树生成代码，我们就会告诉计算机将 a 和 b 相乘两次。
但一个聪明的编译器会做一些更优雅的事情。它会构建一个有向无环图（Directed Acyclic Graph, DAG）。在 DAG 中，每个唯一的子表达式和变量都只对应一个节点。当第二次需要 (a * b) 时，编译器不会创建一组新的节点，而是简单地画另一条边指向它为第一个 (a * b) 创建的节点。冗余的结构随之消失，揭示出真正所需的最少计算集合。DAG 就是编译器的“笔记”，是一张蓝图，显示了哪些结果可以被共享和复用。从这个紧凑的 DAG 生成指令，自然就消除了冗余工作，使程序更快、更高效。
一次性为整个程序构建一个 DAG 会极其复杂。在实践中，编译器通常处理更小、更易于管理的代码片段，称为基本块（basic blocks）——即没有分支进入或流出的直线指令序列。在一个基本块内，CSE 的逻辑异常简单，就像一场“生成（generate）”和“杀死（kill）”的游戏。
让我们跟随编译器的思路来分析一段代码：
t1 := y + zt2 := y + zx := t1 - t2当编译器看到第一行时，它执行加法并将结果存储在临时变量 t1 中。它会记下一笔：“表达式 y + z 的值现在可用于 t1 中。” 这是一个 “生成”（gen） 事件。
在第二行，它再次看到 y + z。它会检查笔记。y + z 可用吗？是的！那么，自 t1 计算以来，其构成部分 y 和 z 是否被改变过？没有。因此，编译器知道重新计算 y + z 是浪费的。它可以简单地复用已有的值。编译器会转换代码，用一个简单的复制操作替换第二条指令：t2 := t1。
但如果代码是这样的呢？
t1 := y + zy := 10t2 := y + z这里，在 t1 计算之后，变量 y 被修改了。这是一个 “杀死”（kill） 事件。编译器必须对自己绝对坦诚：它那条关于 t1 持有 y + z 值的笔记现在已经危险地过时了。原始表达式 y + z 已经失效。当它到达第三行时，它不能复用 t1。它必须用 y 的新值再次执行加法。
这个简单的“生成-杀死”逻辑，当与其他优化结合时，可以带来惊人的简化效果。考虑表达式 x = (y+z) - (y+z)。
y+z 是一个公共子表达式，将代码转换为 t1 := y+z; x := t1 - t1。t1 - t1。它知道任何数减去自身都为零。代码变为 t1 := y+z; x := 0。t1 被计算了，但它的值再也没有被使用过。指令 t1 := y+z 是“死的”。它可以被完全移除。最初的三条指令，通过纯粹的逻辑被提炼成了一条完美的单一指令：x := 0。这就是编译器优化的优雅之处：将看起来复杂的代码转换成其最简单、最快的等价形式。
这种逐块处理的方法很强大，但它就像通过钥匙孔看世界。如果一个冗余计算就藏在眼前，但被一个 if-else 语句分开了怎么办？
一个局部的 CSE 过程，在隔离分析每个块时，会看到两个独立的 a * b 计算，并且无法将它们合并。为了找到这些“全局”的冗余，编译器需要将视野拉远。现代编译器通过一种更先进的表示法——静态单赋值（Static Single Assignment, SSA）来实现这一点。在 SSA 形式中，每个变量只被赋值一次。在控制流汇合的点（比如 if-else 之后），会使用一个特殊的 phi 函数，根据之前走的路径来选择正确的值。
这种结构使得一种更强大的技术——全局值编号（Global Value Numbering, GVN）得以大放异彩。GVN 为每个不同的计算分配一个唯一的“值编号”。在上面的例子中，它会为 if 的两个分支中的 a * b 分配相同的值编号。然后，它会看到 phi 函数正在合并两个持有相同值编号的不同变量。由此，它可以推断出，无论走了哪条路径，if-else 之后的结果都是相同的，因此可以在分支之前完成一次 a*b 的计算。
这展示了一种美妙的协同作用：不同的优化技术协同工作。副本传播（Copy Propagation）可以简化代码，使公共子表达式更加明显。GVN 可以识别等价性，从而让循环不变代码外提（Loop-Invariant Code Motion, LICM）能够将计算完全移出循环。这是一个逻辑推导的流水线，每一步都为下一步创造了条件。
或许科学中最深刻的智慧不在于了解规则，而在于知道规则何时不适用。对于编译器来说，CSE 并不总是安全或正确的。从一个简单的数学思想到现实世界的实现，这个过程充满了微妙的危险。
在我们简单的例子中，x 和 y 只是符号。但在真实的计算机中，它们是内存位置的名称。而指针是持有内存地址的变量。这就引入了一个可怕的问题——别名（aliasing）：两个不同的指针可能指向同一个内存位置。
考虑这段代码：
x = *p; // Read the value at the address p*q = 100; // Write 100 to the address qy = *p; // Read the value at address p again我们能把它优化成 y = x 吗？看起来我们读了两次 *p。但如果 p 和 q 是别名——即它们持有相同的地址，情况会怎样？如果这样，第 2 行对 *q 的写入将会改变 *p 指向的值。复用旧值 x 将是一个灾难性的错误。除非编译器能够证明 p 和 q 绝不可能指向同一块内存，否则它必须保持多疑。它必须假设它们可能存在别名，并执行第二次读取。这使得编译器从一个单纯的代码重排者变成了一个侦探，需要对内存的可能状态进行推理。
同样的问题也发生在函数调用中。一个对函数 f(ref x) 的调用，其中 x 是通过引用传递的，就是一个黑箱。函数 f 可以对 x 做任何事情。在调用返回后，编译器必须假设任何先前涉及 x 的计算现在都已失效。函数调用对于我们所有可用的表达式来说，是一个大规模的“杀死”事件。
在纸面上，加法是满足结合律的： 总是等于 。但在计算机上，对于浮点数而言，这并非事实！由于表示像 甚至 这样的数字时涉及的有限精度和舍入，运算的顺序可能会导致最终结果发生微小但有时至关重要的变化。
一个在“严格”模式下运行的编译器，用于科学或金融应用时，必须尊重程序员编写的括号。它被禁止为了暴露一个公共子表达式而将 重组为 。然而，程序员可以通过使用像 -ffast-math 这样的标志来给予编译器“便宜行事”的许可。这是一种契约：程序员在告诉编译器，“相比严格的 IEEE-754 合规性，我更看重速度，所以我允许你假设数学运算和纸面上一样。”
volatile优化的最终且最绝对的边界是 volatile 关键字。想象一下，你的代码正通过一个内存地址与硬件设备（如网卡或实时时钟）交互。你可能会连续两次从该地址读取数据：
time1 = *hardware_clock;time2 = *hardware_clock;对于一个朴素的编译器来说，这看起来是一个典型的公共子表达式。但消除第二次读取将是一场灾难！这样做的全部意义就在于在两个不同的时刻读取时钟以测量时间间隔。该内存位置的值可以被程序外部的东西——硬件本身——改变。
volatile 关键字是给编译器的直接命令：“别碰！访问这块内存的行为是一个可观察事件。你绝不能将它优化掉，绝不能重排它，也绝不能将它与其他访问合并。” 它告诉编译器，“as-if”规则——即程序的行为必须如同它被逐字执行一样——适用于读写行为本身。这一个关键字在整个编译器流水线中掀起波澜，从前端到后端，约束每一个优化过程都必须尊重程序与外部世界之间的这条神圣界线。
从一个简单的“不重复自己”的愿望出发，我们经历了一场旅程，穿越了计算的优雅结构、数据流的逻辑、全局推理的挑战，以及由计算机物理现实设下的深刻边界。公共子表达式消除远不止是一个简单的提速技巧；它是整个编译器设计领域的一个缩影——一场由逻辑、审慎以及对程序正确性真正含义的深刻理解共同编织的美丽而复杂的舞蹈。
在了解了公共子表达式消除（CSE）的原理之后，你可能会觉得这只是编译器开发者使用的一个聪明但或许小众的技巧。事实远非如此。这个简单的想法——只做一次工作并复用其结果——是计算领域中最为普遍和强大的原则之一。它的回响体现在 CPU 架构、编程语言设计、机器学习基础，甚至编写安全并发软件的警示故事中。让我们一同探索这片广阔的领域，看看这一个想法是如何将一切联系在一起的。
CSE 最自然的归宿当然是编译器。当你编写代码时，你表达的是你的意图。编译器的任务就是将该意图转换为尽可能快、尽可能高效的机器指令序列。其中一个关键部分就是扮演一个不知疲倦的效率专家，追捕并清除任何形式的冗余劳动。
它是如何发现这种冗余的呢？想象一下，编译器将你的代码转换成一种计算路线图——一个有向无环图（DAG），其中每个节点都是一个简单的计算，箭头则显示了结果如何从一个计算流向下一个。手握这张图，编译器可以使用一种巧妙的哈希技术——根据每个计算的操作及其输入为其创建一个唯一的“签名”——来发现图上两条不同的路径何时会通向完全相同的计算交汇点。当它发现一个重复项时，它会简单地将流量改道至第一个交汇点，并拆除第二个。
这看起来可能只是小小的节省，但其效果可能是巨大的。考虑一个在循环中运行一百万次的计算。如果循环内的某个表达式只依赖于每次迭代中都不会改变的变量，那么它就是一个循环不变的公共子表达式。一个智能的编译器，将 CSE 与一种称为循环不变代码外提的技术相结合，会将该计算完全移出循环。程序不再执行一百万次相同的乘法，而是计算一次并复用结果。程序那部分的成本从与迭代次数 成正比，骤降为常数成本 1。这在计算上等同于在烤一千块饼干前只读一次配方的计量，而不是为每一块都重读一遍。
其好处深入到硬件层面。现代处理器就像拥有不同任务流水线的专业工厂。可能有一个算术单元，另一个用于获取数据，还有一个专门用于计算内存地址的地址生成单元（AGU）。如果你的代码反复访问同一个复杂地址，比如 base_register + offset，一个未优化的程序会让 AGU 一遍又一遍地执行相同的计算。通过应用 CSE，编译器计算一次地址，将其存储在寄存器中，并节省宝贵的 AGU 周期。当然，天下没有免费的午餐；这引入了一个权衡。存储该结果会消耗一个寄存器，增加了“寄存器压力”。如果使用的寄存器太多，编译器可能被迫将一个值临时溢出到内存中，这本身就会产生性能成本。这揭示了一种美妙的张力：CSE 是一个强大的工具，但它的应用是许多相互竞争的优化之间精妙舞蹈的一部分。
也许最令人惊讶的是，消除工作可以帮助我们一次做更多的工作。如果多条指令互不依赖，现代 CPU 可以并行执行它们。CSE 有助于揭示这种隐藏的并行性。通过识别和消除冗余计算，编译器简化了代码的数据依赖图，解开了可能迫使两个操作顺序执行的依赖关系。经过 CSE 后，这些操作现在可能变得独立，可以自由地分派到不同的执行单元并并发运行。通过做得更少，机器可以实现得更多。
CSE 的美妙之处在于它不仅仅关乎算术。它是一种基本模式，在令人惊讶的高层次和多样化的领域中都有体现。
想一想一个简单的电子表格。如果你在单元格 C1 中有一个公式 $A1 + B1$，在单元格 C2 中有另一个公式 $C1 * D1$，你就拥有一个隐式的依赖图。电子表格引擎“知道”要计算 C2，它必须首先得到 C1 的结果。本质上，电子表格通过将 $A1 + B1$ 的结果放入中间单元格 C1 以供复用，其结构本身就是一种手动形式的公共子表达式消除！当你改变 A1 中的值时，引擎不会重新计算所有内容；它会智能地沿着依赖图，以完美的拓扑顺序重新计算 C1，然后是 C2。
这种抽象计算的原则以更复杂的方式出现。在面向对象编程中，“虚调用”允许程序在运行时根据对象的实际类型来决定执行哪个版本的方法。这是如何工作的呢？在底层，它通常涉及一系列的类型检查。像 x.method() 这样的调用被编译器展开成类似：“如果 x 的类型是 B，则调用 B 的方法；否则如果 x 的类型是 C，则调用 C 的方法……”。如果你接着在同一个对象 x 上调用另一个虚方法，这整个类型测试的级联就会重复。一个精明的编译器会意识到表达式 typeof(x) 是一个纯粹的公共子表达式。通过应用 CSE，它可以计算一次 x 的类型，存储它，然后用直接的、非虚的调用替换所有后续对 x 的虚调用。这种被称为去虚拟化（devirtualization）的强大优化，被揭示为仅仅是公共子表达式消除的又一个应用。
当我们转向现代人工智能时，这个舞台变得更加宏大。深度学习模型被表示为庞大的计算图，数据在其中流经层层操作。单个模型可能会在不同的数据路径上复用相同的操作块（比如一个特定的卷积层）。训练和运行这些模型的计算成本极高。支持深度学习的框架，如 TensorFlow 和 PyTorch，本质上就是这些图的复杂编译器。它们积极应用 CSE 来寻找这些相同的块，并确保它们在“前向传播”期间只被计算一次。那么学习，即“反向传播”（backpropagation）呢？控制梯度计算方式的链式法则的数学原理，完美地处理了这一点。当图中的一个节点分支出多个消费者时，反向模式微分算法会自然地将来自所有这些路径的传入梯度相加。CSE 优化了计算，而梯度微积分正确地考虑了这一点，确保模型能够正确学习。
尽管 CSE 功能强大，但其天真的应用可能是灾难性的。我们讨论过的优化依赖于一个关键假设：程序的世界是自包含的，并遵循一个单一、可预测的执行线程。当这个假设被打破时，CSE 可能从一个优化器变成一个 bug 制造者。
考虑 Peterson 算法（Peterson's Solution），这是一个允许两个并发进程无冲突地共享资源的经典算法。它依赖于共享变量，如标志位，一个进程设置标志位以向另一个进程发出信号。想象一下进程 处于一个忙等待循环中，反复检查进程 的标志位：while (flag[j] == true) { /* wait */ }。从单线程的角度看， 从不写入 flag[j]，因此表达式 flag[j] 似乎是一个公共子表达式。一个“有进取心”的编译器可能会通过在循环前一次性将 flag[j] 读入寄存器，然后在这个寄存器的值上空转来进行优化。但这是一个灾难性的错误。在另一个 CPU 核心上运行的进程 可能会将主内存中的 flag[j] 改为 false，以示 可以继续。但 永远不会看到这个变化；它被困在一个无限循环中，盯着它那个陈旧的、缓存的标志位副本。系统发生死锁。
这个关键的失败凸显了 CSE 安全应用的边界。它告诉我们，并发线程之间共享的变量是特殊的。它们不能像简单的局部变量一样被优化掉。这一洞见促成了像 C/C++ 中的 volatile 关键字或现代语言中的原子类型等语言特性的诞生。这些本质上是给编译器的明确指令：“暂停你通常的假设。不要在这里应用 CSE。每次读取这个变量都必须是从内存中重新读取，因为世界可能在你背后发生了变化。”
最终，公共子表达式消除是一个宏大的、与机器无关的原则的一个具体实例。它是一种对计算结构的逻辑优化，与那些利用特定处理器特性的、依赖于机器的技巧（如使用融合乘加（FMA）指令）截然不同。
在其核心，CSE 是软件工程师所珍视的“不要重复自己”（Don't Repeat Yourself, DRY）原则的计算体现。它是一种根本性的认知，即冗余是低效的根源。通过发现并消除它，我们创造出的程序不仅更快，而且在某种程度上也更优雅。从电子表格中的依赖图，到编译器优化的复杂舞蹈，再到 AI 模型的庞大网络，计算一次并复用结果这个简单而美妙的想法，是现代性能的基石。它证明了一个单一、清晰的原则如何能贯穿计算机科学的每一层，在对效率的共同追求中统一了不同的领域。
if (condition) {
result = a * b;
} else {
result = a * b;
}