为什么死代码检测不能完全靠编译器来解决？
Why can't dead code detection be fully solved by a compiler?
我一直在 C 或 Java 中使用的编译器具有死代码预防功能（当某行永远不会执行时发出警告）。我的教授说编译器永远无法完全解决这个问题。我想知道为什么会这样。我不太熟悉编译器的实际编码，因为这是基于理论的class。但我想知道他们检查了什么（例如可能的输入字符串与可接受的输入等），以及为什么这还不够。
看这个例子：
public boolean isEven(int i){
if(i % 2 == 0)
return true;
if(i % 2 == 1)
return false;
return false;
}
编译器无法知道一个int只能是偶数或奇数。因此，编译器必须能够理解您的代码的语义。这应该如何实施？编译器无法确保最低的 return 永远不会被执行。因此编译器无法检测到死代码。
一个简单的例子：
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 被设计为 return 只有 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 总是 returns true.
死码问题与Halting problem有关。
Alan Turing 证明了不可能编写一个通用算法来给定一个程序并能够决定该程序是否针对所有输入停止。您也许能够为特定类型的程序编写这样的算法，但不是为所有程序。
这与死代码有什么关系？
停机问题可归结为寻找死代码的问题。也就是说，如果你找到一个可以检测any程序中的死代码的算法，那么你可以使用该算法来测试any程序是否会停止.由于这已被证明是不可能的，因此为死代码编写算法也是不可能的。
如何将死代码算法转换为停机问题算法？
简单：在要检查暂停的程序结束后添加一行代码。如果你的死代码检测器检测到这条线是死的，那么你就知道程序没有停止。如果没有，那么您就知道您的程序停止了（到达最后一行，然后到您添加的代码行）。
编译器通常会检查可以在编译时证明是死的东西。例如，依赖于可在编译时确定为假的条件的块。或 return 之后的任何语句（在同一范围内）。
这些是特定情况，因此可以为它们编写算法。可以为更复杂的情况编写算法（比如检查条件在句法上是否矛盾并因此总是 return false 的算法），但仍然无法涵盖所有可能的情况。
编译器总会缺少一些上下文信息。例如。您可能知道，double 值永远不会超过 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")
编译器无法确定。编译代码时，编译器只知道某个字符串值被传递给该方法。它直到运行时才检查该方法是否存在。如果该方法未在其他地方调用，通过更正常的方法，试图找到死方法可能 return 误报。任何允许通过反射调用代码的语言都存在同样的问题。
好吧，让我们采用停机问题不可判定性的经典证明，并将停机检测器更改为死代码检测器！
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) returns false，那么System.Console.WriteLn("Dead code!");行永远不会被执行，所以这个程序实际上确实[=29] =] 有死代码，检测器错误。
但是如果是returnstrue，那么System.Console.WriteLn("Dead code!");行就会被执行，而且由于程序中没有更多的代码，所以根本就没有死代码，所以又一次，检测器是错误的。
所以你有它，一个 returns 只有 "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() 永远不会被调用...吗？
其他人评论了停机问题等等。这些通常适用于部分功能。然而，可以 hard/impossible 知道是否使用了整个类型 (class/etc)。
在 .NET/Java/JavaScript 和其他运行时驱动的环境中，没有什么可以阻止通过反射加载类型。这在依赖注入框架中很流行，并且在面对反序列化或动态模块加载时更难推理。
编译器不知道是否会加载此类类型。它们的名称可能来自运行时的外部配置文件。
您可能想四处搜索 tree shaking，这是一个常用术语，指的是试图安全删除未使用的代码子图的工具。
如果停机问题太晦涩难懂，请这样想。
举一个被认为对所有正整数 n 都成立但尚未证明对每个 n[= 都成立的数学问题35=]。一个很好的例子是 Goldbach's conjecture，任何大于 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() 的实现留作 reader 的练习，但为此目的可以对所有小于 n[= 的素数进行简单迭代35=]
现在，从逻辑上讲，上面的内容必须等价于：
for (; ;) {
}
（即无限循环）或
print("Conjecture is false for at least one value of n\n");
因为哥德巴赫猜想要么为真，要么不为真。如果编译器总能消除死代码，那么在任何一种情况下，这里肯定会有要消除的死代码。但是，这样做至少您的编译器需要解决任意困难的问题。我们可以提供 provably 难以解决的问题（例如 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 次迭代的顺序。事实上，这将是一个很好的优化，因为我预测上述程序会（或可能）运行 直到宇宙热寂，而不是在没有优化的情况下打印任何东西。
编译器不一定能看到整个程序。我可以有一个调用共享库的程序，它回调到我的程序中的一个函数，该函数没有被直接调用。
因此，如果该库在运行时发生更改，则相对于其编译所针对的库而言已死的函数可能会变得活跃。
我不同意停机问题。我不会说这样的代码已经死了，即使在现实中它永远不会被实现。
相反，让我们考虑：
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() 可以包含任意代码，为了让编译器确定它 returns 是真还是假，它要么必须 运行 代码，要么做一些是在功能上等同于 运行ning 代码。
编译器的想法是它只对代码执行部分分析，从而简化了单独的 运行ning 环境的工作。如果进行全面分析，那将不再是编译器。
如果将编译器视为函数c()，其中c(source)=compiled code，将运行ning环境视为r()，其中r(compiled code)=program output，则要确定任何源代码的输出，您必须计算 r(c(source code)) 的值。如果计算 c() 需要知道任何输入的 r(c()) 的值，则不需要单独的 r() 和 c()：您可以只导出一个函数 i() 来自 c() 这样 i(source)=program output.
我一直在 C 或 Java 中使用的编译器具有死代码预防功能（当某行永远不会执行时发出警告）。我的教授说编译器永远无法完全解决这个问题。我想知道为什么会这样。我不太熟悉编译器的实际编码，因为这是基于理论的class。但我想知道他们检查了什么（例如可能的输入字符串与可接受的输入等），以及为什么这还不够。
看这个例子：
public boolean isEven(int i){
if(i % 2 == 0)
return true;
if(i % 2 == 1)
return false;
return false;
}
编译器无法知道一个int只能是偶数或奇数。因此，编译器必须能够理解您的代码的语义。这应该如何实施？编译器无法确保最低的 return 永远不会被执行。因此编译器无法检测到死代码。
一个简单的例子：
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 被设计为 return 只有 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 总是 returns true.
死码问题与Halting problem有关。
Alan Turing 证明了不可能编写一个通用算法来给定一个程序并能够决定该程序是否针对所有输入停止。您也许能够为特定类型的程序编写这样的算法，但不是为所有程序。
这与死代码有什么关系？
停机问题可归结为寻找死代码的问题。也就是说，如果你找到一个可以检测any程序中的死代码的算法，那么你可以使用该算法来测试any程序是否会停止.由于这已被证明是不可能的，因此为死代码编写算法也是不可能的。
如何将死代码算法转换为停机问题算法？
简单：在要检查暂停的程序结束后添加一行代码。如果你的死代码检测器检测到这条线是死的，那么你就知道程序没有停止。如果没有，那么您就知道您的程序停止了（到达最后一行，然后到您添加的代码行）。
编译器通常会检查可以在编译时证明是死的东西。例如，依赖于可在编译时确定为假的条件的块。或 return 之后的任何语句（在同一范围内）。
这些是特定情况，因此可以为它们编写算法。可以为更复杂的情况编写算法（比如检查条件在句法上是否矛盾并因此总是 return false 的算法），但仍然无法涵盖所有可能的情况。
编译器总会缺少一些上下文信息。例如。您可能知道，double 值永远不会超过 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")
编译器无法确定。编译代码时，编译器只知道某个字符串值被传递给该方法。它直到运行时才检查该方法是否存在。如果该方法未在其他地方调用，通过更正常的方法，试图找到死方法可能 return 误报。任何允许通过反射调用代码的语言都存在同样的问题。
好吧，让我们采用停机问题不可判定性的经典证明，并将停机检测器更改为死代码检测器！
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) returns false，那么System.Console.WriteLn("Dead code!");行永远不会被执行，所以这个程序实际上确实[=29] =] 有死代码，检测器错误。
但是如果是returnstrue，那么System.Console.WriteLn("Dead code!");行就会被执行，而且由于程序中没有更多的代码，所以根本就没有死代码，所以又一次，检测器是错误的。
所以你有它，一个 returns 只有 "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() 永远不会被调用...吗？
其他人评论了停机问题等等。这些通常适用于部分功能。然而，可以 hard/impossible 知道是否使用了整个类型 (class/etc)。
在 .NET/Java/JavaScript 和其他运行时驱动的环境中，没有什么可以阻止通过反射加载类型。这在依赖注入框架中很流行，并且在面对反序列化或动态模块加载时更难推理。
编译器不知道是否会加载此类类型。它们的名称可能来自运行时的外部配置文件。
您可能想四处搜索 tree shaking，这是一个常用术语，指的是试图安全删除未使用的代码子图的工具。
如果停机问题太晦涩难懂，请这样想。
举一个被认为对所有正整数 n 都成立但尚未证明对每个 n[= 都成立的数学问题35=]。一个很好的例子是 Goldbach's conjecture，任何大于 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() 的实现留作 reader 的练习，但为此目的可以对所有小于 n[= 的素数进行简单迭代35=]
现在，从逻辑上讲，上面的内容必须等价于：
for (; ;) {
}
（即无限循环）或
print("Conjecture is false for at least one value of n\n");
因为哥德巴赫猜想要么为真，要么不为真。如果编译器总能消除死代码，那么在任何一种情况下，这里肯定会有要消除的死代码。但是，这样做至少您的编译器需要解决任意困难的问题。我们可以提供 provably 难以解决的问题（例如 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 次迭代的顺序。事实上，这将是一个很好的优化，因为我预测上述程序会（或可能）运行 直到宇宙热寂，而不是在没有优化的情况下打印任何东西。
编译器不一定能看到整个程序。我可以有一个调用共享库的程序，它回调到我的程序中的一个函数，该函数没有被直接调用。
因此，如果该库在运行时发生更改，则相对于其编译所针对的库而言已死的函数可能会变得活跃。
我不同意停机问题。我不会说这样的代码已经死了，即使在现实中它永远不会被实现。
相反，让我们考虑：
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() 可以包含任意代码，为了让编译器确定它 returns 是真还是假，它要么必须 运行 代码，要么做一些是在功能上等同于 运行ning 代码。
编译器的想法是它只对代码执行部分分析，从而简化了单独的 运行ning 环境的工作。如果进行全面分析，那将不再是编译器。
如果将编译器视为函数c()，其中c(source)=compiled code，将运行ning环境视为r()，其中r(compiled code)=program output，则要确定任何源代码的输出，您必须计算 r(c(source code)) 的值。如果计算 c() 需要知道任何输入的 r(c()) 的值，则不需要单独的 r() 和 c()：您可以只导出一个函数 i() 来自 c() 这样 i(source)=program output.