为什么不能通过编译器完全解决死代码检测？

在C或Java中使用的编译器具有死代码预防function（警告线路不会被执行）。 我的教授说，这个问题永远不可能由编译器完全解决。 我想知道这是为什么。 我不太熟悉编译器的实际编码，因为这是一个基于理论的类。 但是我想知道他们检查了什么（例如可能的inputstringvs可接受的input等），以及为什么这是不够的。

Answer 1

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

Alan Turingcertificate，编写一个通用algorithm是不可能的，该algorithm将被赋予一个程序，并能够决定该程序是否停止所有的input。 您可能可以为特定types的程序编写这样的algorithm，但不能为所有程序编写。

这与死代码有什么关系？

停机问题可以归结为寻找死代码的问题。 也就是说，如果你发现一个algorithm可以在任何程序中检测到死代码，那么你可以使用该algorithm来testing是否有程序停止。 既然这已经被certificate是不可能的，那么写死代码algorithm也是不可能的。

如何将死代码algorithm转换为Halting问题的algorithm？

很简单：在程序结束后，你要添加一行代码来检查暂停。 如果你的死代码检测器检测到这条线已经死了，那么你知道程序不会停止。 如果没有，那么你知道你的程序暂停（到最后一行，然后到你添加的代码行）。

---

编译器通常会检查可以在编译时被certificate死的事情。 例如，在编译时依赖于可以被确定为假的条件的块。 或return后的任何声明（在相同的范围内）。

这些是特定的情况，因此可以为它们编写algorithm。 可能为更复杂的情况编写algorithm（比如检查条件在语法上是否矛盾，因此总是返回错误的algorithm），但是仍然不能涵盖所有可能的情况。

Answer 2

那么，让我们拿出暂停问题的不确定性的经典certificate，并将停止检测器改为死代码检测器！

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.WriteLn("Dead code!"); 将永远不会被执行，所以这个程序实际上确实有死码，检测器是错误的。

但如果它返回true ，那么行System.Console.WriteLn("Dead code!"); 将被执行，并且由于程序中没有更多的代码，根本没有死码，所以检测器是错误的。

所以你有它，一个死码检测器，只返回“有死代码”或“没有死代码”有时必须得到错误的答案。

Answer 3

如果停滞的问题太模糊，就这样想。

对所有正整数n都有一个相信是正确的math问题，但是对于每一个n都没有certificate是正确的。 哥德巴赫猜想就是一个很好的例子，任何大于2的正偶数都可以用两个素数之和来表示。 然后（用一个合适的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"); 

因为哥德巴赫猜想必须是真实的或不真实的。 如果一个编译器总是可以消除死代码，那么在这两种情况下肯定会有无用代码。 但是，至less你的编译器需要解决任意严重的问题。 我们可以提供难以解决的问题（例如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"); 

我们知道该程序将打印出“findSHA值”或“未findSHA值”（如果你能告诉我哪一个是真的，那就奖励点数）。 然而，编译器能够合理地优化2 ^ 2048次迭代。 这实际上是一个很好的优化，因为我预测上面的程序将（或可能）运行到宇宙的热死亡，而不是没有优化地打印任何东西。

Answer 4

我不知道C ++或Java是否具有Evaltypes的函数，但是许多语言允许您通过名称来调用方法。 考虑以下（人为的）VBA示例。

 Dim methodName As String If foo Then methodName = "Bar" Else methodName = "Qux" End If Application.Run(methodName) 

被调用的方法的名称直到运行时才可能知道。 因此，根据定义，编译器不能绝对肯定地知道一个特定的方法永远不会被调用。

实际上，以名称调用方法为例，分支逻辑甚至是不必要的。 简单地说

 Application.Run("Bar") 

不止是编译器可以确定的。 编译代码时，所有编译器都知道某个string值正在传递给该方法。 它不检查直到运行时是否存在该方法。 如果方法没有在其他地方调用，通过更常规的方法，试图find死的方法可能会返回误报。 任何允许通过reflection调用代码的语言都存在同样的问题。

Answer 5

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

但也有条件的死代码。 这是在编译时无法知道的代码，只能在运行时检测到。 例如，软件可以被configuration为根据用户偏好来包括或排除某些特征，使特定部分的代码在特定情况下看似死亡。 这不是真正的死码。

有一些特定的工具可以进行testing，解决依赖性，删除条件死代码，并在运行时重新组合有用的代码以提高效率。 这被称为dynamic死码消除。 但是正如你所看到的，这超出了编译器的范围。

Answer 6

一个简单的例子：

 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被devise为只返回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 。

Answer 7

编译器将总是缺less一些上下文信息。 例如，你可能知道，一个double值永远不会放弃2，因为这是math函数的一个特性，你可以从库中使用。 编译器甚至不会看到库中的代码，也不可能知道所有math函数的所有特征，并且检测所有这些实现它们的复杂方式。

Answer 8

编译器不一定能看到整个程序。 我可以有一个程序调用一个共享库，这个库调用我的程序中的函数，而不是直接调用。

因此，如果库在运行时发生了更改，那么针对它所编译的库就会死掉的函数会变得活跃起来。

Answer 9

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

考虑这个简单的情况：

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

my_func()可以包含任意代码，为了让编译器确定它是返回true还是false，它将不得不运行代码或者做一些function上等同于运行代码的东西。

编译器的思想是只对代码进行部分分析，从而简化单独运行环境的工作。 如果你执行完整的分析，那不再是编译器了。

---

如果你认为编译器是一个函数c() ，其中c(source)=compiled code ，运行环境为r() ，其中r(compiled code)=program output ，那么确定任何源代码的输出必须计算r(c(source code)) 。 如果计算c()需要知道任何input的r(c())的值，则不需要单独的r()和c() ：你可以从c()导出一个函数i() c()这样i(source)=program output 。

Answer 10

其他人就停止问题等等进行了评论。 这些通常适用于部分function。 然而，要知道是否使用了整个types（类/ etc）是很难/不可能的。

在.NET / Java / JavaScript和其他运行时驱动的环境中，没有任何停止types通过reflection加载。 这在dependency injection框架中很受欢迎，而面对反序列化或dynamic模块加载更是难以推理。

编译器无法知道这样的types是否会被加载。 他们的名字可能来自运行时的外部configuration文件。

您可能想要search树震动 ，这是试图安全删除未使用的代码子图的工具的通用术语。

Answer 11

采取function

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

你能certificateactnumber永远不会是2所以actnumber Action2()永远不会被调用…？

Answer 12

我不同意停止问题。 即使在现实中，我也不会把这样的代码称为死亡。

相反，让我们考虑：

 for (int N = 3;;N++) for (int A = 2; A < int.MaxValue; A++) for (int B = 2; B < int.MaxValue; B++) { int Square = Math.Pow(A, N) + Math.Pow(B, N); float Test = Math.Sqrt(Square); if (Test == Math.Trunc(Test)) FermatWasWrong(); } private void FermatWasWrong() { Press.Announce("Fermat was wrong!"); Nobel.Claim(); } 

（忽略types和溢出错误）死代码？

Answer 13

看看这个例子：

 public boolean isEven(int i){ if(i % 2 == 0) return true; if(i % 2 == 1) return false; return false; } 

编译器不能知道一个int只能是偶数或奇数。 因此编译器必须能够理解你的代码的语义。 这应该如何实施？ 编译器不能确保最低的回报永远不会被执行。 因此，编译器无法检测到死码。