死代码消除

在软件开发领域，一个惊人的事实是，编译器的重要工作之一并非生成代码，而是将其丢弃。这个过程被称为死代码消除（DCE），是编译器所执行的最基本、最强大的优化之一。它基于一个简单而深刻的前提：程序中任何对其最终可观察行为没有贡献的部分都是可以被移除的“废物”，移除后可以使程序更小、更快、更高效。然而，核心挑战在于区分什么是真正“死的”代码和什么是必要的代码，这项任务需要对程序的结构、数据流和潜在的副作用有深刻的理解。

本文将深入探讨死代码消除的艺术与科学。首先，在 ​​原理与机制​​ 一章中，我们将剖析 DCE 的两大支柱——可达性与活跃性——探讨编译器如何绘制程序路径图并追踪变量使用情况，以识别无用代码。我们还将研究制约这一过程的关键约束，例如处理异常和副作用，这些约束确保了优化绝不会损害程序的正确性。随后，在 ​​应用与跨领域关联​​ 一章中，将揭示 DCE 作为主要“使能者”的角色，展示它如何与其他优化协同工作以实现显著的代码转换，如何弥合软件逻辑与硬件性能之间的鸿沟，甚至如何在软件安全中扮演意想不到的角色。

要理解编译器如何能审视你编写的程序并丢弃其中一部分而又不破坏它，我们需要像编译器一样思考。编译器的首要指令是保持程序的 ​​可观察行为​​。任何你能看到程序所做的事情——打印消息、写入文件、改变像素颜色、更新硬件寄存器中的值——都必须被保留。从编译器的角度来看，任何对这个可观察世界没有影响的东西都只是在白白浪费算力。这种“无用”的代码就是我们所说的 ​​死代码​​。

但是，什么使代码变得“无用”呢？这个简单的问题有两个基本答案，它们构成了死代码消除的两大支柱：​​可达性​​ 和 ​​活跃性​​。想象一下你工作室里的一个工具。如果你从不进入工作室，那么这个工具就是无用的——这是可达性问题。或者，你进入了工作室，拿起工具，看了看，然后又放了回去，从未使用它来制造任何东西——这是活跃性问题。编译器的任务就是识别并丢弃这两种无用的“工具”。

最直接的一种死代码是那些在任何情况下都永远不会被执行的代码。我们称之为 ​​不可达​​ 代码。编译器总是在寻找这些不可能的路径。

考虑一段简单的逻辑：

编译器可能会执行一种名为 ​​常量传播​​ 的优化。它看到 $x$ 是一个常量 $3$。然后它看到 $a$ 是通过 $3 + 2$ 计算得出的，结果恒为 $5$。于是条件检查变成了 if (5 0)。即使是机器也知道这永远为假。通往 A 块的路径是不可能的；它是不可达的。编译器可以自信地将 A 块完全删除，无论它有多复杂，甚至无需理解它的功能。这种证明路径不可能的简单行为，就从程序的可能性之树上剪掉了一个完整的枝干。

但这提出了一个深刻的问题：什么构成了“路径”？我们通常认为路径是由 if-else 分支和 goto 语句定义的。编译器会构建一个这些连接的映射图，称为 ​​控制流图（CFG）​​，用来进行可达性推理。但这张图是完整的吗？

让我们想象一个程序，它有一个特殊的代码块 $H$，用于处理像除以零这样的严重错误。在我们简单的 CFG 中，可能没有任何 goto 或 if 语句能导向代码块 $H$。一个朴素的可达性分析会断定 $H$ 块是不可达的，并将其删除。但如果代码的其他地方存在像 q := a / b 这样的语句呢？如果 $b$ 恰好为零，程序的执行就不会遵循常规路径。它会发生一次异常跳转，通过一条隐藏的路径，直接到达 $H$ 块中的处理程序。如果我们已经删除了 $H$ 块，程序就会崩溃。我们的优化就会引入一个灾难性的故障。

这个在诸如 的问题中探讨过的假设情景，揭示了一个深刻的真理：为了保证优化的安全性，编译器对程序行为的模型必须是完整的。它不仅要考虑地图上可见的道路（if 和 goto），还必须考虑隐藏的隧道和紧急空运（异常和其他特殊的控制转移）。

第二种，也是更微妙的一种死代码，涉及那些 被执行 但其结果对最终输出没有任何影响的计算。这是一个 ​​活跃性​​ 的问题。如果一个变量的当前值可能在程序的未来某个点被使用，我们就说这个变量在当前点是 ​​活跃的（live）​​。如果一个变量不是活跃的，它就是 ​​死的（dead）​​。

最明显的例子是为一个立即被覆盖的变量赋值：

值 $5$ 被赋给 $x$，但在任何代码有机会读取它之前，它就被 $10$ 替换了。第一个赋值语句 x ← 5 是死代码，因为变量 x 在该语句执行后立即就不是活跃的了。编译器可以安全地移除它。

活跃性分析通常是向后进行的。它从可观察点——比如 print(x)——开始，并推断：“好的，$x$ 在这里被使用了，所以它在此之前必须是活跃的。”然后，它向后追溯代码，记录哪些变量需要为其未来的使用而保持其值。

这正是各种优化开始协同工作的地方，其产生的效果远超各部分之和。让我们回到常量传播的例子。原始程序可能在很多地方都使用了变量 $x$。但在常量传播将每一次对 $x$ 的使用都替换为常量 $3$ 之后，$x$ 就再也没有“用武之地”了。此时，向后的活跃性分析找不到任何保留 $x$ 值的理由。因此，最初的赋值语句 x ← 3——即这些常量的来源——就成了死代码，并被消除。

这种“连锁反应”很常见。某一项优化并不直接加速代码，而是通过消除变量的用途来“杀死”一个变量。然后，死代码消除会跟进，清除掉现在已无用的定义。

到目前为止，我们一直假设，如果一个计算的值被另一个计算读取或被打印出来，那么这个计算就是“被使用”的。但这个定义是危险且不完整的。在这里，我们必须更深入地探究：一个程序的真正“工作”是什么？

考虑一下看似微不足道的表达式 $f(z) - f(z)$。从代数上看，结果是零。如果我们将这个结果存储在一个名为 unused_result 的变量中，并且再也不使用它，我们能消除整个计算过程吗？答案是响亮的：“这取决于 $f$ 做了什么。”

• 如果 $f$ 是一个 ​​纯函数​​，比如 double f_pure(double x) { return x * x; }，那么它唯一的目的就是根据其输入计算一个值。如果这个值被丢弃，那么这次函数调用就毫无意义。这个计算就真的是死代码。

• 但如果函数是 double f_vol(double x) { g_volatile_counter++; return x * x; } 呢？这个函数有 ​​副作用​​。根据像 C 和 C++ 这类语言的规则，访问一个 volatile 变量本身就是一种可观察行为。它可能是一个需要被读取的硬件寄存器，或者是一个被其他进程监视的内存位置。读取它的行为本身就是程序与世界交互的一部分。在这种情况下，即使 f_vol 的返回值参与的计算结果被丢弃，对 f_vol 的调用也 不能 被移除。它们的副作用——对计数器的递增操作——是活跃的。计算 f_vol(z) - f_vol(z) 不仅仅是为了产生一个数字；其执行本身 就是 工作。

副作用可能更加微妙。像 *p = s 这样的语句会将 $s$ 的值写入 $p$ 指向的内存位置。这看起来像一个简单的局部更新。但如果指针 p 是一个 ​​别名​​（alias）——即另一个名字——指向一个完全不同函数中的变量呢？正如在 中所探讨的，像 f(x) 这样的调用可以创建这样一个别名，使得函数 f 内部的一个指针实际上指向了调用函数中的变量 x。现在，存储操作 *p = s 不再是一个局部效应；它是一个修改调用者状态的副作用，而且这个效应可能在稍后被观察到。突然之间，这个存储操作变成了活跃的，计算 s 的过程以及 s 所依赖的任何东西也都是活跃的。一个健全的编译器必须像一个多疑的侦探，除非能证明相反的情况，否则就必须假设任何通过指针进行的写操作都是一个可观察的副作用。

这可能会给人一种印象，即死代码消除主要关乎安全性和避免错误。但其真正的力量在于它扮演着“清理队”的角色，为其他更激进的优化创造了条件。通常，一项优化会将代码转换成一个正确但混乱的中间状态，而 DCE 正是收获最终利益的关键。

让我们通过一个来自 的经典例子来观察这个过程：

首先，​​公共子表达式消除（CSE）​​ 遍发现 y + z 被计算了两次。它重写代码以复用第一个结果：

接下来，​​代数简化​​ 遍识别出 t₁ - t₁ 总是 $0$：

程序已经变得更简单了，但我们还没完。现在，活跃性分析开始运行。它看到 x 是活跃的（它的值稍后会被使用），但 t₁ 不是。它的值被计算出来，然后……就再也没用过。它是机器中的一个幽灵。死代码消除迅速介入，移除了这个无用的赋值：

看看发生了什么。一系列简单的局部转换，以 DCE 作为最后一步，将三条指令减少到一条。DCE 本身并没有让代码变快；它解锁了之前各项优化的全部潜力。

在数百万行代码中执行这些分析——追踪使用、定义和副作用——似乎是一项艰巨的任务。现代编译器通过巧妙的数据结构和更宏观的视角来处理这个问题。

许多编译器将代码转换成一种称为 ​​静态单赋值（SSA）​​ 的形式。在 SSA 中，每个变量只被赋值一次。像 x = 1; x = x + 2; 这样的序列会变成 x₁ = 1; x₂ = x₁ + 2;。这创建了一个明确的 ​​定义-使用图（def-use graph）​​，其中变量的每次使用都直接链接到其唯一的定义。在这种形式下，检查死代码变得异常简单：如果图中一个定义的节点没有任何出边，就意味着它没有任何用途。这个定义就是死的。整个活跃性分析过程可以简化为一次图遍历：从所有具有可观察副作用（如存储和返回）的节点开始，将它们标记为活跃，然后沿着图的边向后追溯，标记所有为活跃节点提供输入的节点。最后，任何未被标记的东西都是待宰的羔羊。

这种思想可以从单个函数扩展到整个程序，这被称为 ​​过程间分析​​。如果一个函数 F 被调用时传入了一个它从未实际使用的参数，那么该参数就是死的。编译器可以从函数签名中移除它，并且至关重要的是，从每个调用 F 的地方也移除它。这可以节省计算参数和传递它的成本。当然，旧规则仍然适用：如果参数表达式有副作用（例如，F(read_sensor())），那么产生副作用的部分仍然必须被执行。

但在现实世界中，程序是由许多在不同时间编译的模块和库构建而成的，这时会发生什么呢？一个正在优化你代码的编译器可能没有它所调用的库函数的源代码。解决方案是一种优雅的抽象：​​接口摘要​​。当一个库被编译时，编译器也可以生成一个小的摘要文件。对于函数 f，这个文件可能会说：“函数 f 返回一个值，如果其输入为正，它会修改全局变量 G。它没有其他可观察的效应。”当你编译调用 f 的代码时，你的编译器会读取这个摘要。它不需要看到 f 的内部实现；这个摘要是一份契约，一份关于 f 行为的承诺，足以让编译器做出安全而智能的优化决策。

从删除一个不可达的 if 分支的简单行为，到在庞大的、分别编译的项目间协调优化，死代码消除是一个深刻原理在实践中运作的优美范例。它迫使我们去思考一个程序“做”某件事的真正含义，并在此过程中，找到并移除我们机器中的幽灵，留下的代码不仅更快，而且更纯粹地表达了我们最初意图完成的工作。

在建筑艺术中，如同在雕塑艺术中一样，伟大往往不是通过增加，而是通过减少来实现的，这是一个奇特而优美的事实。雕塑家从一块大理石开始，凿去所有不属于雕像的部分。以一种非常相似的方式，现代编译器——我们的数字雕塑家——接收程序员编写的庞大代码块，然后凿去所有不属于那个必不可少、优雅且高效的最终程序的部分。实现这种减法魔术的主要工具就是死代码消除（DCE）。

我们已经探讨了编译器如何识别“死”代码的原理——这些代码要么因为永远不会被执行到，要么因为其结果永远不会被使用。但要真正领会其威力，我们必须观察它的实际作用。它的角色不仅仅是清扫垃圾的清洁工，更是一位大师级的协作者，一个关键的“使能者”，与其他优化产生深刻的协同效应，以既微妙又显著的方式转换程序。它是连接抽象软件逻辑与具体硬件性能的桥梁，而且最令人惊讶的是，它还是软件安全的一个无意识的守护者。

关于死代码消除，首先要理解的一点是它很少单独工作。它是一套组合拳的后半部分。另一个优化遍首先暴露出“死的”组织，然后 DCE 介入将其移除。而这次清理，反过来又可能为更多的优化揭示新的机会。这是一个良性循环，一场级联的转换之舞。

DCE 最简单的伙伴是常量折叠。如果你写下像 $a + 0 \times b - 2 \times (c - c)$ 这样的表达式，编译器的常量折叠遍会推断出 $0 \times b$ 永远是 $0$，并且只要 $c$ 是一个纯变量，$c-c$ 也为 $0$。表达式简化为 $a + 0 - 0$。这第一步创造了一连串现在已无用的临时变量和中间计算。DCE 紧随其后，一丝不苟地移除每一个如今已无意义的计算，最终留下简单而优雅的结果：只有 $a$。

这个原理可以优美地从简单的表达式扩展到整个程序区域。考虑一个程序员写了一个循环，其循环条件经过一连串推理后被编译器发现永远为假，比如 while(0)。循环体内的代码现在变得不可达。它可能长达数千行，但 DCE 会以手术般的精度将其切除。这种移除可能会带来意想不到的后果。也许在循环之前定义了一个变量，其唯一用途就是在循环内部。随着循环的消失，该变量的定义现在也变成了死的，DCE 也会移除它，从而清理了甚至不在不可达块内部的代码。

这种移除不可达代码的能力不仅仅是为了整洁，它对正确性至关重要。在具有短路求值特性的语言中，像 $A \land B$ 这样的表达式意味着“求值 $A$，仅当其为真时，才求值 $B$。”如果编译器能在编译时证明 $A$ 为假，它就 绝不能 生成求值 $B$ 的代码，特别是当 $B$ 是一个带有副作用（如写入文件或更改全局变量）的函数调用时。常量传播会将条件变为 false，然后 DCE 会正确地移除求值 $B$ 的代码，从而保留原始程序的确切语义 [@problem_t_id:3677568]。雕塑家的凿子剔除了不应存在的部分，确保最终的形态忠于艺术家的意图。

当与高级结构优化结合时，这种协同效应变得更加深刻。一些优化，如 循环判断外提（loop unswitching），为了提升性能会有意增加代码体积。如果一个循环包含一个基于循环内不变条件（“循环不变量”条件）的判断，编译器可以将该判断移到循环外部，创建两个独立的循环副本或克隆。这看起来很浪费！但奇妙之处在于：在其中一个克隆的循环里，该条件现在是一个已知的常量。这可能使得该循环体的大部分内容变为死代码。DCE 介入并移除这些死代码，甚至可能发现整个克隆的循环现在是空的并且没有副作用，从而将其完全移除。一个起初使代码量翻倍的转换，最终在 DCE 的帮助下，变成了一个既小又快的简化。

有时，DCE 能促成一些改变函数间调用结构的优化。尾调用优化（TCO）是一种绝佳的技术，能将特定类型的递归调用转换为简单的循环，从而节省内存并防止栈溢出。但它只能在函数调用是函数做的最后一件事时才能应用。想象一个函数，在调用 g() 之后紧跟着一个看似重要的检查，比如 null 指针测试。这个检查会阻碍 TCO 的进行。然而，如果一个复杂的数据流分析能够证明，函数中一个 更早 的操作在指针为 null 时已经会导致程序崩溃，那么这个调用后的检查就是多余的——它是死代码！DCE 将其移除，为 TCO 施展其魔法扫清了道路。

程序逻辑的抽象世界最终必须在处理器的物理硅片上运行。现代 CPU 中最受限、最宝贵的资源之一是其通用寄存器组——所有实际计算都发生在这些微小、快如闪电的存储位置。如果一个程序需要处理的变量数量超过了可用寄存器的数量，它就必须将这些变量“溢出”（spill）到慢得多的主内存中，这会带来显著的性能损失。

正是在这里，死代码消除提供了一个显著而实际的好处。通过简化程序，DCE 减少了在任何给定时间点“活跃”（其值将在未来被使用）的变量数量。这反过来又使得寄存器分配器的工作变得异常轻松。

一种称为条件常量传播（CCP）的强大技术可以追踪程序的复杂分支，并发现由于某些初始常量值，代码中的整个路径都是不可达的。DCE 会移除这些路径。在这些路径本应合并的点上，特殊的 SSA $\phi$-函数被简化或移除。这常常揭示出，一个曾经被认为可能持有多个值的变量，现在实际上只持有一个单一的常量值。这个常量被传播，其定义指令变为死的，然后 DCE 将其移除。最终效果是减少了寄存器分配器需要操心的变量数量。

利用图染色理论，可以优美而精确地量化这种效应。寄存器分配问题可以被建模为对一个“干涉图”进行染色，其中每个变量是一个节点，任何两个同时活跃的变量之间都有一条边连接。所需的最少寄存器数量就是该图的“色数”。考虑一段代码，在某个特定点，四个变量 $a, b, c, d$ 同时活跃。这会在干涉图中形成一个 $K_4$ 团（clique）——一个四个节点两两相连的结构——这需要四种不同的颜色，即四个寄存器。现在，假设导致它们全部活跃的指令被发现是死代码并被消除。变量的活跃性发生了变化。也许现在，$d$ 不再与 $a$ 和 $b$ 同时活跃。这个团被打破了。之前需要四个寄存器的图，现在可能只需要三种颜色即可着色。通过移除一行无用的代码，编译器节省了一个物理寄存器，从而可衡量地减少了 CPU 在可能数百万个时钟周期内需要进行的“腾挪”（juggling）操作。

将我们的视野放大，DCE 的影响超越了单个函数，延伸到整个程序的架构。在链接时优化（LTO）的现代，编译器可以一次性分析整个项目——包括其所有文件和库。

想象一个大型应用程序，它有两个主要模式：“生产”模式和“开发”模式，由一个在编译时设置的配置标志来选择。这个标志的值在整个程序中通过函数调用传播。如果程序是为生产环境编译的，编译器就知道导向仅用于开发的代码路径的条件将永远为假。DCE 此时扮演的就不是凿子，而是一把大锤，移除属于仅开发功能集的每一个函数、每一个变量、每一行代码。可能高达数兆字节的不可达代码就这样消失了。

一个经典的现实世界例子是程序的日志框架。开发者可能会在代码中散布数千个 if (logging_enabled) 检查来打印诊断信息。对于发布版本，logging_enabled 标志在一个文件中被设置为 false。通过 LTO，编译器能看到这一点。它将 false 值传播到各处，然后 DCE 不仅消除了对 log_msg() 的调用，还可能消除了 log_msg() 函数本身，甚至包括负责初始化日志系统的复杂全局对象和构造函数。最终的可执行文件就像日志代码从未被编写过一样，变得更小、更快，并且禁用的功能不会带来任何运行时开销。当然，这种能力也有其局限性；在构建一个未来可能与未知代码链接的共享库时，编译器必须保持保守，不能基于可能被其他模块违反的假设来移除代码。

死代码消除最令人惊讶的角色或许是它与软件安全的联系。这种联系源于编译器“阶段顺序”（phase ordering）——即不同优化运行顺序——的复杂编排。

考虑一下防御缓冲区溢出攻击的问题。一种常见的防御措施是“栈金丝雀”（stack canary），即在函数开始时在栈上放置一个秘密值，并在函数返回前检查该值。如果缓冲区溢出破坏了栈，金丝雀的值就会被损坏，检查将失败，从而终止程序，而不是让攻击者劫持其执行。

那么，这个对安全至关重要的检查应该在优化管道的哪个位置插入呢？一个看似合乎逻辑的地方是在接近末尾处。但如果像尾调用消除这样的优化遍在插入金丝雀检查 之后 运行会怎么样？TCE 可能会优化掉该检查所依附的 return 语句，从而悄无声息地移除了安全功能，重新打开了漏洞！

解决方案在于精心设计的阶段顺序。结构性优化如内联和尾调用消除必须首先运行，以最终确定程序的控制流。只有在那之后，金丝雀插入遍才应该运行，在所有最终退出点——包括正常返回和尾调用跳转——之前放置检查。最后，像 DCE 这样的清理遍才可以运行。这确保了安全机制被编织进程序的最终结构中，并且不会被意外撤销。因此，DCE 的位置和交互不仅仅是性能上的实现细节，它关乎安全工程。这个使我们的程序变快的工具，在使其变得安全方面也扮演着角色，但这只有在对其在整个编译宏图中的位置有深刻理解的情况下才能实现。

从整理简单的表达式到塑造程序的硬件级性能，从构建大型软件项目到参与其安全防护，死代码消除远不止是一个简单的清理工具。它是一股简化的基本力量，一位无形的雕塑家，揭示出隐藏在程序员最初蓝图中的那个必不可少、高性能且健壮的程序。