我在C或Java中使用的编译器具有死代码防止功能(当不执行某行时发出警告).我的教授说,编译器永远无法完全解决这个问题.我想知道为什么会这样.我不太熟悉编译器的实际编码,因为这是一个基于理论的类.但我想知道他们检查了什么(例如可能的输入字符串与可接受的输入等),以及为什么这是不够的.
Rea*_*tic 274
死代码问题与停机问题有关.
Alan Turing证明,编写一个通用算法是不可能的,该算法将被赋予一个程序,并能够决定该程序是否为所有输入停止.您可以为特定类型的程序编写此类算法,但不能为所有程序编写.
这与死代码有什么关系？
Halting问题可以简化为查找死代码的问题.也就是说,如果您找到可以在任何程序中检测死代码的算法,那么您可以使用该算法来测试是否有任何程序停止.由于已经证明这是不可能的,因此编写死代码算法也是不可能的.
如何将死代码算法转换为停止问题的算法？
简单:在要检查暂停的程序结束后添加一行代码.如果您的死码检测器检测到该线路已死,那么您就知道该程序没有停止.如果没有,那么您知道您的程序停止(到达最后一行,然后到您添加的代码行).
编译器通常检查在编译时可以证明已经死亡的事情.例如,依赖于在编译时可以确定为false的条件的块.或者在return(在同一范围内)之后的任何陈述.
这些是特定情况,因此可以为它们编写算法.有可能为更复杂的情况编写算法(比如检查条件在语法上是否是矛盾的算法,因此总是返回false),但是,这仍然不能涵盖所有可能的情况.
Jok*_*_vD 77
好吧,让我们采用停止问题不可判定性的经典证明,并将停机检测器更改为死码检测器!
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!");被执行,并且由于程序中没有更多的代码,所以根本没有死代码,所以再次,检测器是错误的.
所以你有它,一个只返回"有死代码"或"没有死代码"的死代码检测器有时必须产生错误的答案.
abl*_*igh 65
如果停止问题太模糊,那就这样想吧.
对于所有正整数n来说,一个被认为是真实的数学问题,但是对于每个n都没有被证明是正确的.一个很好的例子是Goldbach的猜想,任何大于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次迭代.它实际上是一个很好的优化,因为我预测上述程序将(或可能)运行直到宇宙的热量死亡,而不是没有优化打印任何东西.
Rub*_*uck 34
我不知道C++或Java是否具有Eval类型函数,但许多语言允许您按名称调用方法.考虑以下(人为的)VBA示例.
Dim methodName As String
If foo Then
methodName = "Bar"
Else
methodName = "Qux"
End If
Application.Run(methodName)
直到运行时才能知道要调用的方法的名称.因此,根据定义,编译器无法绝对确定地知道永远不会调用特定方法.
实际上,给定按名称调用方法的示例,甚至不需要分支逻辑.简单地说
Application.Run("Bar")
超过编译器可以确定的.编译代码时,所有编译器都知道某个字符串值正在传递给该方法.它不检查该方法是否存在直到运行时.如果在其他地方没有调用该方法,通过更常规的方法,尝试查找死方法可能会返回误报.任何允许通过反射调用代码的语言都存在同样的问题.
Ale*_*op. 12
一个简单的例子:
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.
dsp*_*der 12
高级编译器可以检测并删除无条件的死代码.
但也有条件死代码.这是在编译时无法识别的代码,只能在运行时检测到.例如,软件可以被配置为根据用户偏好包括或排除某些特征,使得某些代码段在特定场景中看起来似乎已经死亡.那不是真正的死代码.
有一些特定的工具可以进行测试,解决依赖关系,删除条件死代码,并在运行时重新组合有用的代码以提高效率.这称为动态死代码消除.但正如您所看到的,它超出了编译器的范围.