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

我在 C 或 Java 中使用的编译器具有死代码预防(当一行永远不会被执行时发出警告)。我的教授说，这个问题永远不能完全解决编译器虽然。我想知道为什么。我不太熟悉编译器的实际编码，因为这是一个基于理论的类。但我想知道他们检查什么(例如可能的输入字符串与可接受的输入等) ，以及为什么这是不够的。

16255 次浏览
小开

看看这个例子:

public boolean isEven(int i){


if(i % 2 == 0)
return true;
if(i % 2 == 1)
return false;
return false;
}

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

小开

举个简单的例子:

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。

小开
最佳答案

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

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

这和死代码有什么关系？

停机问题是 还原对于查找死代码的问题。也就是说，如果您找到一个算法，可以检测死代码的 任何程序，然后您可以使用该算法来测试是否 任何程序将停止。由于这已被证明是不可能的，因此编写一个死代码算法也是不可能的。

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

简单: 在程序结束后添加一行代码以检查是否暂停。如果死代码检测器检测到该行已死，那么您就知道程序不会停止。如果没有，那么您就知道您的程序停止了(到达最后一行，然后到达添加的代码行)。

编译器通常会检查在编译时可以证明已经死亡的内容。例如，依赖于可以在编译时确定为 false 的条件的块。或 return之后的任何语句(在同一范围内)。

这些都是特定的情况，因此有可能为它们编写一个算法。也许可以为更复杂的情况编写算法(比如一个算法检查一个条件是否在语法上是矛盾的，因此总是返回 false) ，但仍然不能覆盖所有可能的情况。

小开

编译器总是缺少一些上下文信息。例如，你可能知道，一个双精度值永远不会超过2，因为这是数学函数的一个特性，你从一个库中使用。编译器甚至看不到库中的代码，它永远不可能知道所有数学函数的所有特性，并检测所有复杂的实现方法。

小开

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

但也有条件死代码。这是在编译时无法知道的代码，只能在运行时检测到。例如，一个软件可以根据用户的偏好来配置包含或排除某些特性，使得某些代码段在特定的场景中看起来死气沉沉。这不是真正的死代码。

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

小开

我不知道 C + + 或 Java 是否有 Eval类型的函数，但是许多语言都允许调用方法 名字。考虑以下(人为设计的) VBA 示例。

Dim methodName As String


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


Application.Run(methodName)

要调用的方法的名称在运行时之前是不可能知道的。因此，根据定义，编译器不能绝对肯定地知道从未调用某个特定方法。

实际上，给定一个按名称调用方法的例子，甚至不需要分支逻辑

Application.Run("Bar")

超过编译器可以确定的范围。编译代码时，编译器只知道某个字符串值正在传递给该方法。它直到运行时才检查该方法是否存在。如果不在其他地方调用该方法，通过更普通的方法，尝试查找死方法可能会返回假阳性。任何允许通过反射调用代码的语言都存在同样的问题。

小开

那么，让我们用经典的证据证明停止问题的不确定性，并将停止检测器改为死代码检测器！

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!");行，因为程序中没有更多的代码，所以根本没有死代码，所以再一次，检测器是错误的。

所以，一个只返回“ There is dead code”或“ There is no dead code”的死代码检测器有时一定会产生错误的答案。

小开

做一个功能

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

你能证明 actnumber永远不会是 2吗? 这样 Action2()就永远不会被叫做... ？

小开

其他人则对停车问题等等发表了评论。这些通常适用于函数的某些部分。然而，甚至很难/不可能知道是否使用了整个类型(class/etc)。

进去。NET/Java/JavaScript 和其他运行时驱动的环境没有什么可以阻止通过反射加载类型。这在依赖注入框架中非常流行，而在反序列化或动态模块加载的情况下更是难以推断。

编译器无法知道是否会加载这些类型。它们的名称 可以来自运行时的外部配置文件。

您可能想搜索一下 摇树，它是一个常见的术语，指试图安全地删除未使用的代码子图的工具。

小开

如果停顿问题太模糊，可以这样想。

以一个数学问题为例，这个问题被认为适用于所有正整数的 N，但是还没有被证明适用于每个 N。哥德巴赫猜想就是一个很好的例子，任何大于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");

因为哥德巴赫的猜想要么是真的，要么是假的。如果编译器总是能够消除死代码，那么在这两种情况下肯定都会有死代码需要消除。然而，在这样做时，编译器至少需要解决任意的难题。我们可以提供 可以证明难以解决的问题(例如 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");

我们知道程序会打印出“发现 SHA 值”或“未发现 SHA 值”(如果你能告诉我哪一个是真的，那就加分)。然而，对于一个编译器能够合理地优化，将采取2 ^ 2048次迭代的顺序。事实上，这将是一个伟大的优化，因为我预测上述程序将(或可能)运行，直到宇宙的热死亡，而不是打印任何没有优化。

小开

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

因此，如果一个函数在运行时被更改，那么它所编译的库的死函数可能会变成活函数。

小开

我不同意停车的问题。我不会说这样的代码死亡，即使在现实中它永远不会达到。

相反，让我们考虑一下:

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();
}

(忽略类型和溢出错误)死代码？

小开

如果一个 编译器能够准确地消除所有的死代码，那么它将被称为一个 翻译。

想想这个简单的场景:

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

my_func()可以包含任意的代码，为了让编译器确定它是否返回 true 或 false，它将不得不运行代码或执行与运行代码在功能上等效的操作。

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

如果将编译器看作函数 c()，其中 c(source)=compiled code为函数，运行环境为 r()，其中 r(compiled code)=program output为函数，那么要确定任何源代码的输出，必须计算 r(c(source code))的值。如果计算 c()需要知道任何输入的 r(c())的值，那么就不需要单独的 r()和 c(): 你只需从 c()派生一个函数 i()，这样 c(source)=compiled code1就可以了。


提交答案