为什么编译器无法完全解决死代码检测问题？

Question

我一直在使用C或Java编译器进行开发，它们具有死代码检测（当一行代码永远不会被执行时会发出警告）。然而，我的教授表示，这个问题永远无法完全由编译器解决。我想知道为什么会这样。尽管我对编译器的实际编码并不太熟悉，因为这是一门基于理论的课程。但我想知道编译器检查什么（例如可能的输入字符串与可接受的输入等），以及为什么这是不足够的。

- Learner

---

创建一个循环，将代码放在其后，然后运用https://en.wikipedia.org/wiki/Halting_problem。 - zapl

如果（isPrime（1234234234332232323423））{callSomething（）;} 这段代码是否会调用某些东西？还有许多其他示例，其中决定函数是否被调用远比将其包含在程序中昂贵得多。 这段代码是否会调用callSomething函数取决于isPrime（）的返回值。判断一个函数是否被调用可能比将其包含在程序中更加昂贵。 - 463035818_is_not_a_number

这个代码段的意思是：公共静态方法main，接受一个字符串类型的数组参数args。该方法内部调用了一个名为findCollatzConjectureCounterexample()函数并将其返回值存储在整型变量counterexample中。最后，使用System.out.println()语句将counterexample打印出来。至于println调用是否是无效代码，则需要查看findCollatzConjectureCounterexample()函数的具体实现以确定。 - user253751

@tobi303不是一个好的例子，质数分解很容易...只是相对高效地分解它们比较困难。停机问题不属于NP问题，它是不可解的。 - en_Knight

@alephzero和en_Knight - 你们都错了。isPrime是一个很好的例子。你们假设这个函数检查质数。也许那个数字是一个序列号，它执行数据库查询以查看用户是否是亚马逊Prime会员？之所以它是一个很好的例子，是因为唯一知道条件是否恒定的方法是实际执行isPrime函数。现在这将要求编译器也成为解释器。但这仍然无法解决数据易变的情况。 - Dunk

Answer 1

死代码问题与停机问题有关。

Alan Turing证明了，不可能编写一个通用算法，能够给出一个程序并能够决定该程序是否对所有输入都会停机。你可能能够为特定类型的程序编写这样的算法，但不能针对所有程序。

这与死代码有什么关系呢？

停机问题可以归约为寻找死代码的问题。也就是说，如果你找到一个可以检测任何程序中死代码的算法，那么你可以使用该算法来测试任何程序是否会停机。由于已经证明这是不可能的，因此编写死代码的算法也是不可能的。

如何将死代码算法转换为停机问题的算法？

简单：在要检查停机的程序结束后添加一行代码。如果你的死代码检测器检测到这行代码是死的，那么你就知道该程序不会停机。如果它没有检测到，那么你就知道你的程序会停机（到达最后一行，然后到达你添加的代码行）。

---

Compilers通常会检查在编译时可以证明为无用的内容。例如，依赖于条件且在编译时可以确定为false的块，或在同一范围内的return后的任何语句。

这些都是特定情况，因此可以为它们编写算法。可能还可以为更复杂的情况编写算法（例如检查条件在语法上是否矛盾，因此将始终返回false），但仍然无法涵盖所有可能的情况。

- RealSkeptic

---

我认为停机问题在这里不适用，因为现实世界中每个编译器的编译目标平台都有其可以访问的最大数据量，因此它将具有最大数量的状态，这意味着它实际上是一个有限状态机，而不是图灵机。对于有限状态机来说，停机问题是可以解决的，因此现实世界中的任何编译器都可以执行死代码检测。 - Vality

@Vality 64位处理器可以寻址2^64字节。尽情搜索所有256^(2^64)个状态吧！ - Daniel Wagner

这不应该是个问题。搜索256^(2^64)个状态是O(1)，因此死代码检测可以在多项式时间内完成。 - aebabis

@Leliel，那是讽刺。 - Paul Draper

大多数现代计算机都有磁盘、输入设备、网络通信等等。任何完整的分析都必须考虑到所有这些设备——包括字面上与互联网连接并挂接在其上的一切设备。这不是一个可解决的问题。 - Nat

Answer 2

好的，让我们采用经典的停机问题不可判定证明，并将停机检测器更改为死代码检测器！

C#程序

using System;
using YourVendor.Compiler;

class Program
{
    static void Main(string[] args)
    {
        string quine_text = @"using System;
using YourVendor.Compiler;

class Program
{{
    static void Main(string[] args)
    {{
        string quine_text = @{0}{1}{0};
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {{
            System.Console.WriteLine({0}Dead code!{0});
        }}
    }}
}}";
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {
            System.Console.WriteLine("Dead code!");
        }
    }
}

如果YourVendor.Compiler.HasDeadCode(quine_text)返回false，那么行System.Console.WriteLine("Dead code!");将永远不会被执行，因此这个程序实际上确实有死代码，而检测器是错误的。

但是如果它返回true，那么行System.Console.WriteLine("Dead code!");将被执行，由于程序中没有其他代码，所以根本没有死代码，因此检测器再次出错。

因此，你有了一个只返回“存在死代码”或“不存在死代码”的死代码检测器，它必须有时会产生错误的答案。

- Joker_vD

---

如果我正确理解了你的论点，那么从技术上讲，另一个选项是不可能编写一个完全是死代码检测器的引用，但在一般情况下编写死代码检测器是可能的。 :-) - abligh

Godelian答案的增量。 - Jared Smith

@abligh 哎呀，我用词不当。我实际上并没有将死代码检测器的源代码馈送给它自己，而是馈送使用它的程序的源代码。当然，在某个时候它可能需要查看自己的代码，但这是它自己的事情。 - Joker_vD

Answer 3

如果停机问题太难理解，可以这样想。

拿一个被认为对于所有正整数n都成立，但尚未被证明对于每个n都成立的数学问题。一个很好的例子是哥德巴赫猜想，即任何大于二的正偶数都可以表示为两个质数之和。然后（使用适当的bigint库）运行以下程序（伪代码如下）：

 for (BigInt n = 4; ; n+=2) {
     if (!isGoldbachsConjectureTrueFor(n)) {
         print("Conjecture is false for at least one value of n\n");
         exit(0);
     }
 }

实现isGoldbachsConjectureTrueFor()的功能留给读者自己完成，但可以简单地迭代所有小于n的质数来实现这个目的。

现在，从逻辑上讲，以上内容必须等同于：

 for (; ;) {
 }

(即无限循环)或

print("Conjecture is false for at least one value of n\n");

由于哥德巴赫猜想要么是真的要么不是真的。如果编译器总能消除死代码，那么无论哥德巴赫猜想的真假如何，在这里肯定会有死代码要被消除。然而，为了做到这一点，至少需要解决任意难度的问题。我们可以提供一些证明难度的问题（例如NP完全问题）来确定要消除哪一部分代码。例如，如果我们取这个程序：

 String target = "f3c5ac5a63d50099f3b5147cabbbd81e89211513a92e3dcd2565d8c7d302ba9c";
 for (BigInt n = 0; n < 2**2048; n++) {
     String s = n.toString();
     if (sha256(s).equals(target)) {
         print("Found SHA value\n");
         exit(0);
     }
 }
 print("Not found SHA value\n");

我们知道这个程序要么会打印出"Found SHA value"，要么会打印出"Not found SHA value"（如果你能告诉我哪一个是正确的，我会给你加分）。然而，要让编译器能够合理地优化这个过程需要大约2^2048次迭代。实际上，如果没有优化，我预测上述程序可能会一直运行到宇宙热死亡而不打印任何内容，这将是一个很大的优化。

- abligh

---

迄今为止这是最佳答案。+1 - jean

有趣的是，关于C标准允许或不允许假设循环将终止存在歧义，这使得事情变得特别有趣。允许编译器推迟缓慢计算的价值在于，它们的结果可能会被使用，也可能不会被使用，直到实际需要它们的结果为止；即使编译器无法证明计算终止，这种优化在某些情况下仍然有用。 - supercat

2^2048次迭代？即使是深思也会放弃。 - Peter Mortensen

它将以非常高的概率打印“找到SHA值”，即使该目标是一个由64个十六进制数字随机组成的字符串。除非sha256返回一个字节数组，而字节数组在您的语言中不能与字符串相等。 - user253751

“Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the reader” 这句话让我感到好笑。 （说明：该句话是一种常见的幽默方式，它意味着虽然作者提出了一个有趣的问题或挑战，但实现这个问题或挑战的任务留给读者自己去完成。） - biziclop

Answer 4

我不知道C++或Java是否有Eval类型的函数，但许多语言允许您按名称调用方法。考虑以下（人为制造的）VBA示例。

Dim methodName As String

If foo Then
    methodName = "Bar"
Else
    methodName = "Qux"
End If

Application.Run(methodName)

在运行时，我们无法确定要调用的方法名称。因此，根据定义，编译器无法绝对确定某个特定的方法是否被调用。

实际上，以按名称调用方法的示例为例，分支逻辑甚至不是必要的。只需说

Application.Run("Bar")

超出编译器的能力。当编译代码时，编译器只知道某个字符串值被传递给该方法。它在运行时之前不会检查该方法是否存在。如果该方法没有在其他地方被调用，通过更正常的方式，尝试查找无用的方法可能会返回错误的结果。任何允许通过反射调用代码的语言都存在相同的问题。

- RubberDuck

---

在Java（或C#）中，可以使用反射来完成这项工作。在C++中，您可能需要使用宏来实现一些不好看的操作。但是C++很少会变得美观。 - Darrel Hoffman

宏在代码交给编译器之前被展开，所以宏绝不是您执行此操作的方法。函数指针才是正确的做法。我已经好多年没有使用C++了，如果我的类型名称不准确，请见谅。您可以简单地存储一个从字符串到函数指针的映射表，然后编写一个接受用户输入的字符串，并在映射表中查找该字符串，然后执行相应的函数。 - ArtOfWarfare

@ArtOfWarfare 我们不是在讨论如何做到这一点。显然，可以对代码进行语义分析以找到这种情况，但重点是编译器没有这样做。它可能会，也许会，但它没有。 - RubberDuck

如果你想挑剔的话，可以。虽然我知道预处理器技术不算编译器的一部分，但我认为它是编译器的一部分。总之，函数指针可能会破坏规则，使函数被直接引用 - 实际上它们是被引用了的，只不过以指针而不是直接调用的方式，就像 C# 中的委托一样。C++ 对于编译器来说通常更难预测，因为它有许多间接执行的方法。即使是像“查找所有引用”这样简单的任务也不是微不足道的，因为它们可能隐藏在 typedefs、macros 等中。难怪编译器不能轻松地发现死代码。 - Darrel Hoffman

Java可以（使用类加载器）。C++本身不能。但是共享库实际上允许相同的功能。因此，这取决于您的C++编译成什么。如果它编译成具有允许加载共享库的运行时（如*nix和Win），则调用约定可以按名称进行。事实上，您甚至可以让您的程序生成代码，将其编译并在程序的同一运行时中作为共享库加载。 - Dmitry Rubanovich

Answer 5

一个简单的例子：

int readValueFromPort(const unsigned int portNum);

int x = readValueFromPort(0x100); // just an example, nothing meaningful
if (x < 2)
{
    std::cout << "Hey! X < 2" << std::endl;
}
else
{
    std::cout << "X is too big!" << std::endl;
}

现在假设端口0x100设计为只返回0或1。在这种情况下，编译器无法确定else块永远不会被执行。

然而，在这个基本示例中：

bool boolVal = /*anything boolean*/;

if (boolVal)
{
  // Do A
}
else if (!boolVal)
{
  // Do B
}
else
{
  // Do C
}

编译器可以计算出else块是死代码。当编译器有足够的数据来判断死代码，并且知道如何应用这些数据来判断给定的块是否为死代码时，它才能警告有关死代码。

编辑

有时在编译时数据并不可用：

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

if (boolVal)
{
  // Do A
}
else
{
  // Do B
}

//............
// File b.cpp
bool boolMethod()
{
    return true;
}

在编译 a.cpp 时，编译器无法知道 boolMethod 始终返回 true。

- Alex Lop.

---

虽然编译器确实不知道，但我认为在问题的精神上也要问链接器是否能知道。 - Casey Kuball

@Darthfett 这不是链接器的责任。链接器不分析编译代码的内容。链接器（一般来说）只是链接方法和全局数据，它不关心内容。然而，有些编译器确实有将源文件连接起来（如ICC）并进行优化的选项。在这种情况下，EDIT下的情况就被覆盖了，但这个选项会影响编译时间，特别是当项目很大时。 - Alex Lop.

这个答案对我来说似乎是误导性的；你给出了两个例子，其中并不可能因为并非所有信息都可用，但即使信息存在，难道你不应该说它是不可能的吗？ - Cactus Golov

@abforce 只是一段代码而已。它本来可以是任何其他东西。 :) - Alex Lop.

@abfotce 很好的发现！我会进行编辑。但我相信你是想说 cout 而不是 count。 - Alex Lop.

Answer 6

高级编译器可以检测并删除无条件的死代码。

但还有一种条件死代码。这种代码在编译时无法确定，只能在运行时检测到。例如，软件可能可配置以包含或排除某些特性，具体取决于用户偏好，使得某些代码段在特定情况下看似死代码。那不是真正的死代码。

有特定的工具可以进行测试、解决依赖关系、删除条件死代码并在运行时重新组合有用的代码以提高效率。这被称为动态死代码消除。但是，如您所见，这超出了编译器的范围。

- dspfnder

---

"高级编译器可以检测和删除无条件死代码。"这似乎不太可能。代码的死亡取决于给定函数的结果，而给定函数可以解决任意问题。因此，您的陈述断言高级编译器可以解决任意问题。" - Taemyr

如果这样做，那么它就不会被认为是毫无疑问地死亡，不是吗？ - JAB

@Taemyr，您似乎误解了“无条件”这个词。如果代码死亡取决于函数的结果，则它是有条件的死代码。 “条件”是函数结果。要“无条件”，它就不能依赖于任何结果。 - Kyeotic

Answer 7

编译器总是缺乏一些上下文信息。例如，您可能知道double值永远不会超过2，因为这是您从库中使用的数学函数的特性。编译器甚至无法看到库中的代码，并且它永远无法知道所有数学函数的所有特性，以及检测所有奇怪和复杂的实现方式。

- cdonat

Answer 8

编译器并不一定能看到整个程序。我可能有一个调用共享库的程序，该共享库会回调到我的程序中未直接调用的函数。

因此，对于它编译的库来说已经死掉的函数，在运行时如果该库被更改，就可能变得活跃起来。

- Steve Sanbeg

Answer 9

如果一个编译器可以准确地消除所有死代码，它将被称为解释器。

考虑下面这个简单的场景：

if (my_func()) {
  am_i_dead();
}

my_func() 可以包含任意代码，为了使编译器能够确定它返回 true 还是 false，它要么必须运行该代码，要么执行与运行该代码功能等效的操作。

编译器的理念在于它只对代码执行部分分析，从而简化了独立运行环境的工作。如果执行完整的分析，那么它就不再是一个编译器了。

---

如果您将编译器视为函数 c()，其中 c(源代码)=编译好的代码，将运行环境视为函数 r()，其中 r(编译好的代码)=程序输出，那么为了确定任何源代码的输出，您必须计算 r(c(源代码)) 值。如果计算 c() 需要知道任何输入的 r(c()) 值，那么就不需要单独的 r() 和 c()：您可以从 c() 推导出一个函数 i()，使得 i(源代码)=程序输出。

- biziclop

Answer 10

拿一个函数举例

void DoSomeAction(int actnumber) 
{
    switch(actnumber) 
    {
        case 1: Action1(); break;
        case 2: Action2(); break;
        case 3: Action3(); break;
    }
}

你能证明actnumber永远不会是2，这样Action2()就永远不会被调用吗？

- CiaPan

---

如果您能分析函数的调用者，那么您可能可以做到这一点。 - abligh

@abligh但编译器通常无法分析所有调用代码。 无论如何，即使它能够，完整的分析可能需要模拟所有可能的控制流，这几乎总是由于资源和所需时间而不可能。 因此，即使在理论上存在证明"Action2（）永远不会被调用"的证明，实践中也不可能证明该声明- 编译器无法完全解决。 这种差异就像“存在一个数字X”与“我们可以用十进制写下数字X”。 对于某些X，后者将永远不会发生，尽管前者是真实的。 - CiaPan

这是一个糟糕的回答。其他答案证明了无法知道actnumber==2，而这个回答仅声称很难，甚至没有说明复杂度。 - MSalters