全局公共子表达式消除

从本质上讲，追求效率遵循一个简单的规则：永远不要重复做同样的工作。在软件世界中，这一原则由优化编译器来倡导，它是一种能将人类编写的代码精炼成高效机器指令的复杂工具。其中最强大的技术之一是全局公共子表达式消除 (GCSE)，这是一个在整个程序范围内系统地搜寻并消除重复计算的过程。但这种搜寻充满了风险；过于激进的优化可能会改变程序的行为，甚至导致程序崩溃。这就提出了一个关键问题：编译器如何在积极追求性能与绝对保证正确性之间取得平衡？

本文深入探讨了全局公共子表达式消除的复杂世界，揭示了支配这一基本优化的逻辑和权衡。在第一章 ​​原理与机制​​ 中，我们将剖析可用性和支配性的基本规则，探索静态单赋值 (SSA) 和全局值编号 (GVN) 这些如侦探般的工具，并揭示那些可能使优化变得不安全的现实世界复杂性。随后，在 ​​应用与跨学科联系​​ 中，我们将看到这个避免冗余工作的基本原则如何超越编译器，在数据库查询优化和高性能 GPU 编程等不同领域中展现出惊人的关联性。

想象一下你正在按照食谱做饭。在第2步，食谱上写着：“计算一个5英寸圆形挞模的面积。”你 dutifully 计算出 $A = \pi r^2$。然后，在混合好馅料后的第7步，它又要求你“计算同一个5英寸挞模的面积，看看馅料是否能装下。”你可能会翻个白眼。你已经做过这个计算了！为什么还要再算一次？你只会重用你第一次得到的结果。

这种简单、直观的不重复工作的行为，正是​​全局公共子表达式消除 (GCSE)​​ 的灵魂所在。编译器在追求让你的代码运行得更快的过程中，就像一个非常聪明、非常谨慎的厨师。它会扫描整个食谱（你程序的控制流图），寻找可以只执行一次、并将结果保存以备后用的相同计算（公共子表达式）。但编译器的厨房是一个奇特而危险的地方。如果在第2步和第7步之间，食谱告诉你把挞模拉伸一下，改变了它的半径怎么办？重用旧的面积计算结果现在将是一场灾难。

这就是 GCSE 的精妙之舞：在积极追求效率的同时，保持对正确性绝对、不可动摇的承诺。要理解这场舞蹈，我们必须首先了解它所表演的舞台的基本规则。

为了让编译器安全地消除一个重复的计算，必须满足两个条件。假设我们有一个计算 $t = x + y$，之后又有另一个计算 $u = x + y$。

首先，原始表达式的值必须是​​可用的​​ (available)。这意味着在 $t$ 被计算后，通往 $u$ 的路径上不能包含任何改变操作数 $x$ 或 $y$ 值的指令。如果在中间某个地方 $y$ 被修改了，那么第二个位置的表达式 $x + y$ 即使在文本上完全相同，其值也不再是“同一个”表达式了。这是 中场景的核心挑战，其中变量 $y$ 仅在通往一个公共点的两条路径之一上被更新。表达式 $x - y$ 在一条路径上是可用的，但在另一条路径上则不然。

其次，原始计算必须​​支配​​ (dominate) 其重用点。在控制流图的语言中，如果从程序入口到块 $B$ 的每一条可能路径都必须经过块 $A$，那么我们说块 $A$ 支配块 $B$。这是一种执行上的保证。如果我们在一个支配第二次计算位置的块中计算了 $x + y$，我们就能确定这个值在需要之前已经被计算出来了。 中的计算就是一个完美的例子。块 B3 中的一个计算支配其两个后继块 B4 和 B5。因此，在 B3 中计算的值保证可以在 B4 和 B5 中重用，使得那里的重新计算成为冗余。

这两个原则——可用性和支配性——构成了安全的公共子表达式消除的基石。

陈述规则是一回事，但编译器实际上是如何在一个复杂的、充满分支的程序中找到这些冗余的呢？它需要复杂的侦探工具。

静态单赋值 (SSA)：一个充满常量的世界

想象一个世界，在那里每个变量一旦被赋值，就永远不能改变。它变成了一个常量。这就是​​静态单赋值 (SSA)​​ 形式所创造的美丽而简单的虚构世界。当编译器将程序转换为 SSA 形式时，它会重命名变量，使得每个名称只被赋值一次。

但是，当两条控制路径合并，而一个变量可能来自任一路径时，会发生什么呢？SSA 用一种称为 ​​$\phi$ (phi) 函数​​ 的特殊方程来解决这个问题。如果变量 $x$ 可能来自左路径的 $x_1$ 或右路径的 $x_2$，在合并点我们定义一个新变量 $x_3$，像这样：$x_3 = \phi(x_1, x_2)$。这个方程不计算任何东西；它是一种符号表示，告诉编译器：“如果来自左路径，则 $x_3$ 的值为 $x_1$；如果来自右路径，则为 $x_2$。”

SSA 使全局分析变得异常简单。通过给每个不同的值一个唯一的名称，它让冗余变得显而易见。在 中，一旦我们有了 $t_0 = u_0 + z_3$，任何后来出现的 $u_0 + z_3$ 显然都是冗余的，因为名称 $u_0$ 和 $z_3$ 指的是单一、不变的值。

全局值编号 (GVN)：值的真实名称

GVN 为我们提供了变量的唯一名称，但表达式本身呢？两个表达式可能在值上完全相同，即使它们看起来不同。这就是​​全局值编号 (GVN)​​ 发挥作用的地方。GVN 就像一个通用的值哈希系统。它为程序中计算的每个不同的值分配一个唯一的“值编号”。

最初，每个输入变量都会获得一个唯一的值编号。然后，对于像 $t_1 \leftarrow a + b$ 这样的计算，编译器会创建一个与操作 + 以及 $a$ 和 $b$ 的值编号相关联的新值编号。如果它后来看到一个表达式 $t_2 \leftarrow c + d$，并发现 $a$ 和 $c$ 具有相同的值编号，并且 $b$ 和 $d$ 也一样，它就知道 $t_1$ 和 $t_2$ 是等价的。它们会得到相同的值编号。

这就是编译器如何执行像 中那样的识别壮举，其中像 $t_1 \times t_2$ 和 $t_4 \times t_2$ 这样的表达式被发现是相同的，因为 GVN 证明了 $t_1$ 和 $t_4$（两者都是 $a+b$）是相同的值。

此外，一个真正聪明的 GVN 系统懂得代数。它可以将表达式规范化。在 中，表达式 $x + (x + y)$ 和 $(x + x) + y$ 在语法上是不同的。但是，一个知道加法满足结合律和交换律的 GVN 算法可以将两者都表示为其原始组件的多重集——两个 $x$ 和一个 $y$——并为它们分配相同的值编号，从而揭示它们隐藏的等价性。

当 SSA 和 GVN 结合使用时，它们是一对强大的组合。SSA 提供了一张清晰的值流图，而 GVN 则确定了这些值的真实身份。

如果一个表达式在一条路径上计算了，但在另一条路径上没有，会发生什么？在合并点，该表达式是​​部分冗余的​​：如果你从一个方向来，它是冗余的；但如果你从另一个方向来，它又是必需的。

一个简单的 GCSE 算法会束手无策。但一种更先进的技术，称为​​部分冗余消除 (PRE)​​，可以玩一个聪明的把戏。它会说：“如果我把缺失的计算插入到那条‘裸’路径上会怎么样？”通过这样做，它将部分冗余转化为了完全冗余。现在，该表达式保证在所有通往合并点的路径上都是可用的，并且可以被安全地提升到一个支配块中，只计算一次。这是一种主动的优化，编译器在一个地方增加一点工作，以便在之后节省大量工作。

有时，这个技巧更加微妙。在 中，表达式 $x + y$ 是在 $x$ 在一条路径上被递增之后计算的。简单的提升将是不正确的，因为它会使用 $x$ 的旧值。但一个高级的优化器仍然可以找到优化的机会。它可以提升原始的 $x + y$，称之为 $t$，然后在 $x$ 被递增的那条路径上，将结果计算为 $t + 1$。这种代数补偿展示了可以编码到编译器中的非凡创造力。

到目前为止，我们一直生活在一个纯净的、数学的世界里。但真实的程序是混乱的。它们与操作系统、硬件以及其他线程交互。这正是编译器设计真正挑战和美妙之处的体现。一个好的编译器必须是一个悲观主义者，意识到所有可能出错的事情。

机器中的幽灵：副作用与纯粹性

如果一个表达式不仅仅是计算一个值呢？一个函数调用可能会写入文件、更新全局变量或读取系统时钟。这样的操作具有​​副作用​​，它打破了一个称为​​引用透明性​​的关键属性。如果一个表达式对于相同的输入总是产生相同的输出，并且没有其他可观察到的效果，那么它就是引用透明的。 中的函数 f(n)，其内部调用了 clock()，是一个经典的例子。两个 f(n) + f(n) 的调用不是一个公共子表达式！每次调用 clock() 都会返回一个新值。消除一个调用会改变程序的结果。同样，在 中，一个读取全局 seed 的 hash(s) 函数如果其他函数可能在两次调用之间改变那个 seed，就不能被自由移动。

为了应对这种情况，编译器依赖于注解。一个标记为 pure (纯函数) 的函数是一个承诺，保证它是引用透明的。一个标记为 volatile (易变) 的变量是对编译器的警告：“这个值可能随时因你看不见的原因而改变！不要优化掉对我的读写操作。”

代码中的地雷：异常的危险

有些表达式是地雷。表达式 $a / b$ 是完全安全的，除非 $b$ 是零，那样它会触发一个灾难性的异常。现在考虑 中的程序。表达式 $a / b$ 是在代码已经明确检查了 $b \neq 0$ 的路径上计算的。另一条路径，为 $b = 0$ 的情况，则完全避免了这个表达式。

一个天真的 GCSE 可能会看到重复的 $a / b$ 并将其提升到一个在检查之前执行的支配块中。这是​​不安全的推测执行​​。转换后的程序现在会在一条在原始程序中完全安全的路径上因除零错误而崩溃。一个正确的优化器必须证明一个可能产生异常的指令是安全的，然后才能将其移动到一个它会更频繁执行的位置。

浮点数学的模糊世界

在纸上，$x^2$ 与 $x \times x$ 完全相同。在计算机中，使用浮点数，这可能不完全为真。在 中，我们看到库函数 pow(x, 2) 和直接乘法 x * x 可能会因为四舍五入而产生微小的不同结果。更重要的是，它们可能有不同的副作用。语言标准可能要求 pow 函数在溢出时设置一个全局错误变量 errno，而乘法运算符则不会。如果程序稍后检查 errno，一个用 x * x 替换 pow(x, 2) 的优化将改变程序的可观察行为。

这就是为什么许多编译器都有一个“fast-math”(快速数学)模式。这是程序员和编译器之间的一个协议。程序员说：“我保证我不在乎这些微妙的浮点规则或 errno。只要让我的代码快就行。”只有得到这个许可，编译器才能将 $x^2$ 和 $x \times x$ 视为相同。

并发编程的无序状态

也许对优化最大的现代挑战是并发。如果多个线程同时运行，一个共享变量可能在任何时刻被另一个线程改变。在 中，一个线程执行了两次 atomic_load_acquire(x)。我们可以消除第二次加载吗？绝对不能。原子加载不仅仅是一次读取；它是与并发系统其余部分的通信。在第一次和第二次加载之间，另一个线程可能已经向 x 写入了一个新值。消除第二次加载将意味着该线程对这个更新视而不见，违反了内存模型并导致混乱。

这揭示了一个深刻的转变。在一个并发的世界里，许多经典的优化必须被重新评估或放弃，因为一个看似冗余的操作实际上可能是一个关键的同步点。

我们的旅程始于一个简单的想法：不要重复做同样的工作。我们很快发现，当这个原则应用于复杂的计算机程序世界时，它远非简单。它需要一套复杂的逻辑推导工具——如 SSA 和 GVN——来发现代码背后的真正含义。它需要像 PRE 这样聪明的策略来主动创造优化机会。最重要的是，它要求对机器的现实有深刻而谦逊的尊重：尊重副作用、尊重异常、尊重浮点数学的怪癖，以及尊重并发的狂野、不可预测的本质。

优化编译器的工作是一种无名的艺术形式。它是追求性能与保证正确性之间一场无声而复杂的舞蹈，是几十年计算机科学研究的结晶。下次当你的代码运行得惊人地快时，花点时间欣赏一下编译器隐藏的天才，那个分析了每一条路径、打磨了每一条指令、将你的人类逻辑转化为闪电般现实的不倦侦探。

在我们迄今为止的旅程中，我们已经窥见了编译器最优雅的技巧之一：全局公共子表达式消除 (GCSE) 的幕后。其核心思想非常简单，几乎体现了一种高效工作的普适原则：永远不要重复做同样的工作。一个用积木搭建东西的孩子，当意识到他需要另一块四乘二的红色砖块时，如果桌上已经有一块一模一样的，他不会从头再造一块。编译器以其自身复杂的方式，做的正是同样的事情。

但是，当这个简单的想法应用于计算机程序的复杂织锦时，它就绽放成一门深奥的艺术。它要求编译器不仅是一个记账员，还是一个侦探、一个逻辑学家，有时甚至是一个物理学家，理解计算的深层结构及其运行环境。让我们来探讨一下这种“计算懒惰”原则如何远远超出了简单的教科书示例，连接了不同的领域，并揭示了计算科学中一种美妙的统一性。

两个计算是“相同”的，这到底意味着什么？我们的肉眼可能会被表面的差异所欺骗，但编译器必须看得更深。考虑一个场景，程序在代码的一个部分计算 $x \leftarrow a_1 + f(u)$，在另一部分计算 $y \leftarrow a_2 + f(u)$。对我们来说，这看起来是两个不同的计算。但一个配备了现代 GCSE 技术的聪明编译器，能识别出它们内在的共同灵魂：表达式 $f(u)$。如果它能证明函数 $f$ 是纯的——即它像一个数学函数一样，对于相同的输入总是给出相同的输出，没有任何副作用——并且它的参数 $u$ 没有改变，那么它就可以执行一个漂亮的优化。它只计算一次昂贵的 $f(u)$，将结果保存在一个临时变量中，并在两次加法中重用它。这不仅仅是匹配文本；这是理解表达式的组合结构，就像看到两座不同的建筑共享相同的基础蓝图一样。

这种洞察同一性的艺术延伸到了驾驭逻辑的丛林。想象一个条件语句，如 if (X or (Y and X))。一个程序员可能会写出这样的代码，也许没有意识到其中的冗余。编译器作为一个逻辑学家，可以应用布尔代数的吸收律（$A \lor (B \land A) \equiv A$）来证明整个条件等价于 X。这意味着如果 X 涉及到昂贵的计算，比如比较两个大的内存块，编译器可以转换代码以确保该计算只发生一次，完全消除原始逻辑似乎暗示的第二次实例。编译器不仅仅是在遵循指令；它在对它们进行推理。

当然，这种神奇的洞察力并非凭空产生。一个现代编译器是各种优化协同合作的交响乐，每一遍都为下一遍铺平道路。一个表达式如 $g(3)$ 可能出现两次，但编译器如何知道这两个调用是相同的？这需要另一个优化——过程间常量传播——的工作，它会追踪常量值 3 穿过函数调用，证明两次调用实际上等价于同一个常量值。只有这样，GCSE 才能介入并消除第二次调用。这说明了工程复杂系统中的一个关键概念：“阶段顺序问题”。一个优化流水线——值编号、代码移动、归纳变量分析，以及最后的公共子表达式消除——必须以恰当的顺序排列，就像一系列透镜，才能将最终的优化程序清晰地聚焦。

真实的程序很少是一条直线；它们是分支、循环和递归调用的迷宫。在这个世界里应用 GCSE 需要更复杂的推理。

考虑递归。如果一个函数调用自己，并且一个表达式 $f(n)$ 在递归调用之前和之后都被计算，我们能消除第二个吗？一个过程内 GCSE 遍可以做到！只要函数 $f$ 是纯的，并且它的参数 $n$ 在函数的当前激活中没有改变，编译器就可以安全地重用第一个结果。它明白，中间发生的递归旋风，因为由纯操作组成，所以不能扰乱 $f(n)$ 所依赖的状态。然而，这种洞察力有其局限性。标准的 GCSE 无法轻易地将 $f(n)$ 的结果从一次递归调用共享到下一次更深的调用。这需要重新构建程序，也许通过将值作为新参数传递或构建一个缓存（一种称为记忆化的技术），这些是超越了典型 GCSE 范围的强大转换。

当我们考虑分支路径时，情节变得更加复杂。有时，一个计算在 if-then-else 结构的两个不同分支上重复出现。一个简单的分析可能会禁止重用一个分支的结果到另一个分支，因为在控制流图中，两者都不能严格“支配”对方。这时，对程序结构更深刻的理解——程序依赖图 (PDG)——就发挥了作用。PDG 不仅仅是看可能的控制流，它描绘出真正的依赖关系：一个计算需要什么数据，以及哪个决策控制其执行。如果发现两个 $a/b$ 的计算受完全相同的条件控制（例如，它们都只在 $b \neq 0$ 时运行）并且依赖于完全相同的输入，PDG 就会揭示它们是“控制等价”的，可以被合并，即使控制流路径很复杂。这种更高级的视图也凸显了安全性的至关重要性。如果我们粗心地将像 $a/b$ 这样的计算提升到一个它会无条件运行的地方，我们可能会引入一个在原始程序中永远不会发生的除零错误——这是一个灾难性的失败。

消除冗余工作的原则是如此基础，以至于它超越了传统编译器的世界，在截然不同的计算生态系统中找到了归宿。

想一想现代数据库。当你提交一个复杂的查询时，数据库引擎不会只是盲目地获取数据。它首先创建一个“查询计划”，这本质上是一个数据检索的程序。然后这个查询计划会被优化。假设你的查询涉及一个用户定义函数 (UDF)，比如 f(a,b)，并且这个函数出现在查询管道的两个不同部分。数据库的查询优化器，就像一个编译器一样，可以应用 GCSE，对每一行数据只计算一次 f(a,b)，并将结果送入两个管道。

然而，这只有在该 UDF 表现得像一个真正的函数时才可能。如果它是“易失性”的——例如，如果它的值依赖于当前时间 (now()) 或一个随机数——那么两次调用实际上就不是相同的工作，必须分开执行。同样，如果函数有副作用，比如写入日志文件，执行一次而不是两次会改变程序的可观察行为。数据库优化器在敢于消除一次调用之前，必须绝对确定该函数的纯粹性和确定性。

也许这些原则最迷人的应用是在图形处理器 (GPU) 这个陌生的世界里。GPU 通过让成千上万个微小的处理器在不同数据上同步执行相同的程序（一种称为 SIMT，即单指令多线程的模型）来实现其惊人的速度。当这些线程遇到一个分支时，会发生一件奇特的事情：整个线程组（或“warp”，即线程束）会先走“then”路径，只有相关的线程实际工作，然后又走“else”路径，同样只有相关的线程是活跃的。

现在，想象一个表达式如 $\sin(\theta)$ 出现在“then”分支、“else”分支，以及分支重新汇合之后。在一个分化的 warp 中，这意味着 $\sin$ 指令实际上被执行了三次！一个 GPU 编译器可以应用 GCSE，将 $\sin(\theta)$ 的计算提升到分支之前的一个点，为所有线程只执行一次。这个单一的转换对于一个分化的 warp 来说，几乎可以将那段代码的速度提高三倍。

但在这里，该领域的独特性引入了非凡的微妙之处。如果表达式是一个纹理采样，$\mathrm{texture}(u,v)$ 呢？这看起来像一个简单的函数调用。但它不是。为了产生逼真的图像，GPU 会通过计算导数——纹理坐标 $(u,v)$ 在相邻线程间的变化速度——来自动选择合适的纹理分辨率（一个“mip level”，即多级渐远纹理层级）。如果你将这个调用提升到一个分化分支之前，那么“相邻”线程的集合就改变了，这可能改变导数，从而改变 mip level，最终改变返回的颜色！提升后的计算不再与原始计算“相同”。优化器只有在能证明分支是一致的（所有线程走同一条路）或者纹理查找使用了不依赖于这些来自邻居的秘密、隐藏输入的显式细节级别时，才能执行这种 GCSE 转换。

从避免重复加法的简单优雅，到并行线程宇宙中纹理采样的深刻微妙，全局公共子表达式消除的原则始终如一。它证明了当一个简单、直观的想法以数学的严谨和深刻的领域知识被追求时所产生的美，揭示了一条贯穿所有计算形式的共同智慧线索。