The compilers I've been using in C or Java have dead code prevention (warning when a line won't ever be executed). My professor says that this problem can never be fully solved by compilers though. I was wondering why that is. I am not too familiar with the actual coding of compilers as this is a theory-based class. But I was wondering what they check (such as possible input strings vs acceptable inputs, etc.), and why that is insufficient.
13 Answers
The dead code problem is related to the Halting problem.
Alan Turing proved that it is impossible to write a general algorithm that will be given a program and be able to decide whether that program halts for all inputs. You may be able to write such an algorithm for specific types of programs, but not for all programs.
How does this relate to dead code?
The Halting problem is reducible to the problem of finding dead code. That is, if you find an algorithm that can detect dead code in any program, then you can use that algorithm to test whether any program will halt. Since that has been proven to be impossible, it follows that writing an algorithm for dead code is impossible as well.
How do you transfer an algorithm for dead code into an algorithm for the Halting problem?
Simple: you add a line of code after the end of the program you want to check for halt. If your dead-code detector detects that this line is dead, then you know that the program does not halt. If it doesn't, then you know that your program halts (gets to the last line, and then to your added line of code).
Compilers usually check for things that can be proven at compile-time to be dead. For example, blocks that are dependent on conditions that can be determined to be false at compile time. Or any statement after a return
(within the same scope).
These are specific cases, and therefore it's possible to write an algorithm for them. It may be possible to write algorithms for more complicated cases (like an algorithm that checks whether a condition is syntactically a contradiction and therefore will always return false), but still, that wouldn't cover all possible cases.
-
9I would argue that the halting problem is not applicable here, as every platform which is a compile target of every compiler in the real world has a maximum ammunt of data which it may access, it will therefore have a maximum number of states meaning it is in fact a finite state machine, not a turing machine. The halting problem is not insoluable for FSMs so any compiler in the real world can perform dead code detection.– ValityOct 21, 2015 at 23:32
-
51@Vality 64-bit processors can address 2^64 bytes. Have fun searching all 256^(2^64) states! Oct 22, 2015 at 0:20
-
83@DanielWagner This shouldn't be a problem. Searching
256^(2^64)
states isO(1)
, so dead code detection can be done in polynomial time.– aebabisOct 22, 2015 at 3:12 -
13
-
44@Vality: Most modern computers have disks, input devices, network communications, etc. Any complete analysis would have to consider all such devices - including, literally, the internet and everything hooked up to it. This isn't a tractable problem.– NatOct 22, 2015 at 4:38
Well, let's take the classical proof of the undecidability of the halting problem and change the halting-detector to a dead-code detector!
C# program
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!");
}
}
}
If YourVendor.Compiler.HasDeadCode(quine_text)
returns false
, then the line System.Console.WriteLn("Dead code!");
won't be ever executed, so this program actually does have dead code, and the detector was wrong.
But if it returns true
, then the line System.Console.WriteLn("Dead code!");
will be executed, and since there is no more code in the program, there is no dead code at all, so again, the detector was wrong.
So there you have it, a dead-code detector that returns only "There is dead code" or "There is no dead code" must sometimes yield wrong answers.
-
1If I've understood your argument correctly, then technically another option would be that it is not possible to write a quite which is a dead code detector, but it is possible to write a dead code detector in the general case. :-)– ablighOct 22, 2015 at 13:51
-
1
-
@abligh Ugh, that was a bad choice of words. I am not actually feeding the dead-code detector's source code to itself, but the source code of the program that uses it. Surely, at some point it probably would have to look at its own code, but it's its business.– Joker_vDOct 22, 2015 at 17:19
If the halting problem is too obscure, think of it this way.
Take a mathematical problem that is believed to be true for all positive integer's n, but hasn't been proven to be true for every n. A good example would be Goldbach's conjecture, that any positive even integer greater than two can be represented by the sum of two primes. Then (with an appropriate bigint library) run this program (pseudocode follows):
for (BigInt n = 4; ; n+=2) {
if (!isGoldbachsConjectureTrueFor(n)) {
print("Conjecture is false for at least one value of n\n");
exit(0);
}
}
Implementation of isGoldbachsConjectureTrueFor()
is left as an exercise for the reader but for this purpose could be a simple iteration over all primes less than n
Now, logically the above must either be the equivalent of:
for (; ;) {
}
(i.e. an infinite loop) or
print("Conjecture is false for at least one value of n\n");
as Goldbach's conjecture must either be true or not true. If a compiler could always eliminate dead code, there would definitely be dead code to eliminate here in either case. However, in doing so at the very least your compiler would need to solve arbitrarily hard problems. We could provide problems provably hard that it would have to solve (e.g. NP-complete problems) to determine which bit of code to eliminate. For instance if we take this program:
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");
we know that the program will either print out "Found SHA value" or "Not found SHA value" (bonus points if you can tell me which one is true). However, for a compiler to be able to reasonably optimise that would take of the order of 2^2048 iterations. It would in fact be a great optimisation as I predict the above program would (or might) run until the heat death of the universe rather than printing anything without optimisation.
-
4
-
2What makes things particularly interesting is the ambiguity about what the C Standard allows or doesn't allow when it comes to assuming that loops will terminate. There is value in allowing a compiler to defer slow calculations whose results may or may not be used until the point where their results would actually be needed; this optimization could in some cases be useful even if the compiler can't prove the calculations terminate.– supercatOct 22, 2015 at 21:19
-
2
-
It will print "Found SHA value" with very high probability, even if that target was a random string of 64 hex digits. Unless
sha256
returns a byte array and byte arrays don't compare equal to strings in your language. Oct 23, 2015 at 10:46 -
5
Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the reader
This made me chuckle.– biziclopOct 23, 2015 at 14:41
I don't know if C++ or Java have an Eval
type function, but many languages do allow you do call methods by name. Consider the following (contrived) VBA example.
Dim methodName As String
If foo Then
methodName = "Bar"
Else
methodName = "Qux"
End If
Application.Run(methodName)
The name of the method to be called is impossible to know until runtime. Therefore, by definition, the compiler cannot know with absolute certainty that a particular method is never called.
Actually, given the example of calling a method by name, the branching logic isn't even necessary. Simply saying
Application.Run("Bar")
Is more than the compiler can determine. When the code is compiled, all the compiler knows is that a certain string value is being passed to that method. It doesn't check to see if that method exists until runtime. If the method isn't called elsewhere, through more normal methods, an attempt to find dead methods can return false positives. The same issue exists in any language that allows code to be called via reflection.
-
2In Java (or C#), this could be done with reflection. C++ you could probably pull off some nastiness using macros to do it. Wouldn't be pretty, but C++ rarely is. Oct 22, 2015 at 13:36
-
8@DarrelHoffman - Macros are expanded before the code is given to the compiler, so macros definitely aren't how you would do this. Pointers to functions is how you would do this. I haven't used C++ in years so excuse me if my exact type names are wrong, but you can just store a map of strings to function pointers. Then have something that accepts a string from user input, looks up that string in the map, and then executes the function that is pointed at. Oct 22, 2015 at 14:10
-
1@ArtOfWarfare we're not talking about how it could be done. Obviously, semantic analysis of the code can be done to find this situation, the point was that the compiler doesn't. It could, possibly, maybe, but it doesn't. Oct 22, 2015 at 15:59
-
4@ArtOfWarfare: If you want to nitpick, sure. I consider the preprocessor to be part of the compiler, though I know it technically isn't. Anyhow, function pointers might break the rule that the functions are not directly referenced anywhere - they are, just as a pointer instead of a direct call, much like a delegate in C#. C++ is in general much more difficult for a compiler to predict since it has so many ways of doing things indirectly. Even tasks as simple as "find all references" aren't trivial, as they can hide in typedefs, macros, etc. No surprise it can't find dead code easily. Oct 22, 2015 at 17:20
-
1You don't even need dynamic method calls to face this problem. Any public method can be called by a not-yet-written function that will depend on the already compiled class in Java or C# or any other compiled language with some mechanism for dynamic linking. If compilers eliminated these as "dead code," then we wouldn't be able to package precompiled libraries for distribution (NuGet, jars, Python wheels with binary component).– jpmc26Oct 23, 2015 at 6:22
Unconditional dead code can be detected and removed by advanced compilers.
But there is also conditional dead code. That is code that cannot be known at the time of compilation and can only be detected during runtime. For example, a software may be configurable to include or exclude certain features depending on user preference, making certain sections of code seemingly dead in particular scenarios. That is not be real dead code.
There are specific tools that can do testing, resolve dependencies, remove conditional dead code and recombine the useful code at runtime for efficiency. This is called dynamic dead code elimination. But as you can see it is beyond the scope of compilers.
-
5"Unconditional dead code can be detected and removed by advanced compilers." This does not seem likely. Code deadness can depend on the outcome of a given function, and that given function can solve arbitrary problems. So your statement asserts that advanced compilers can solve arbitrary problems.– TaemyrOct 23, 2015 at 11:24
-
7@Taemyr Then it wouldn't be known to be unconditionally dead, now would it?– JABOct 23, 2015 at 14:41
-
2@Taemyr You seem to misunderstand the word "unconditional." If the code deadness depends on the outcome of a function, then it is conditional dead code. The "condition" being the outcome of the function. To be "unconditional" it would have to not depend on any outcome.– KyeoticOct 23, 2015 at 21:40
A simple example:
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;
}
Now assume that the port 0x100 is designed to return only 0 or 1. In that case the compiler cannot figure out that the else
block will never be executed.
However in this basic example:
bool boolVal = /*anything boolean*/;
if (boolVal)
{
// Do A
}
else if (!boolVal)
{
// Do B
}
else
{
// Do C
}
Here the compiler can calculate out the the else
block is a dead code.
So the compiler can warn about the dead code only if it has enough data to to figure out the dead code and also it should know how to apply that data in order to figure out if the given block is a dead code.
EDIT
Sometimes the data is just not available at the compilation time:
// File a.cpp
bool boolMethod();
bool boolVal = boolMethod();
if (boolVal)
{
// Do A
}
else
{
// Do B
}
//............
// File b.cpp
bool boolMethod()
{
return true;
}
While compiling a.cpp the compiler cannot know that boolMethod
always returns true
.
-
1While strictly true that the compiler doesn't know, I think it is in the spirit of the question to also ask whether the linker can know. Oct 22, 2015 at 16:38
-
1@Darthfett It is not the linkers responsibility. Linker doesn't analyze the content of the compiled code. The linker (generally speaking) just links the methods and the global data, it doesn't care about the content. However some compilers do have the option to concatenate the source files (like ICC) and then perform the optimization. In such case the case under EDIT is covered but this option will effect the compilation time especially when the project is large. Oct 22, 2015 at 16:48
-
This answer seems misleading to me; you're giving two examples where it isn't possible because not all information is available, but shouldn't you say that it's impossible even if the information is there? Oct 22, 2015 at 18:39
-
@AntonGolovIt os not always true. In many cases when the information is there, the compilers can detect the dead code and optimize it out. Oct 22, 2015 at 18:52
-
@abforce just a block of code. It could have been anything else. :) Oct 22, 2015 at 20:22
The compiler will always lack some context information. E.g. you might know, that a double value never exeeds 2, because that is a feature of the mathematical function, you use from a library. The compiler does not even see the code in the library, and it can never know all features of all mathematical functions, and detect all weired and complicated ways to implement them.
The compiler doesn't necessarily see the whole program. I could have a program that calls a shared library, which calls back into a function in my program which isn't called directly.
So a function which is dead with respect to the library it's compiled against could become alive if that library was changed at runtime.
If a compiler could eliminate all dead code accurately, it would be called an interpreter.
Consider this simple scenario:
if (my_func()) {
am_i_dead();
}
my_func()
can contain arbitrary code and in order for the compiler to determine whether it returns true or false, it will either have to run the code or do something that is functionally equivalent to running the code.
The idea of a compiler is that it only performs a partial analysis of the code, thus simplifying the job of a separate running environment. If you perform a full analysis, that isn't a compiler any more.
If you consider the compiler as a function c()
, where c(source)=compiled code
, and the running environment as r()
, where r(compiled code)=program output
, then to determine the output for any source code you have to compute the value of r(c(source code))
. If calculating c()
requires the knowledge of the value of r(c())
for any input, there is no need for a separate r()
and c()
: you can just derive a function i()
from c()
such that i(source)=program output
.
Others have commented on the halting problem and so forth. These generally apply to portions of functions. However it can be hard/impossible to know whether even an entire type (class/etc) is used or not.
In .NET/Java/JavaScript and other runtime driven environments there's nothing stopping types being loaded via reflection. This is popular with dependency injection frameworks, and is even harder to reason about in the face of deserialisation or dynamic module loading.
The compiler cannot know whether such types would be loaded. Their names could come from external config files at runtime.
You might like to search around for tree shaking which is a common term for tools that attempt to safely remove unused subgraphs of code.
-
I don't know about Java, and javascript, but .NET actually has a resharper plugin for that kind of DI detection (called Agent Mulder). Of course, it won't be able to detect configuration files, but it is able to detect confit in code (which is much more popular).– TiesOct 28, 2015 at 21:07
Take a function
void DoSomeAction(int actnumber)
{
switch(actnumber)
{
case 1: Action1(); break;
case 2: Action2(); break;
case 3: Action3(); break;
}
}
Can you prove that actnumber
will never be 2
so that Action2()
is never called...?
-
7If you can analyse the callers of the function, then you may be able to, yes.– ablighOct 22, 2015 at 13:42
-
2@abligh But compiler usually can't analyse all the calling code. Anyway even if it could, the full analysis might require just a simulation of all possible control flows, which is almost always just impossible due to resources and time needed. So even if theoretically there exists a proof that '
Action2()
will never be called' it is impossible to prove the claim in practice — can't be fully solved by a compiler. The difference is like 'there exists a number X' vs. 'we can write the number X in decimal'. For some X's the latter will never happen although the former is true.– CiaPanOct 23, 2015 at 12:58 -
1This is a poor answer. the other answers prove that it's impossible to know whether
actnumber==2
. This answer merely claims it's hard without even stating a complexity.– MSaltersOct 26, 2015 at 9:45
I disagree about the halting problem. I wouldn't call such code dead even though in reality it will never be reached.
Instead, lets consider:
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();
}
(Ignore the type and overflow errors) Dead code?
-
2Fermat's last theorem was proven in 1994. So a correct implementation of your method would never run FermatWasWrong. I suspect your implementation will run FermatWasWrong, because you can hit the limit of precision of floats.– TaemyrOct 23, 2015 at 7:31
-
@Taemyr Aha! This program does not correctly test Fermat's Last Theorem; a counterexample for what it does test is N=3, A=65536, B=65536 (which yields Test=0) Oct 23, 2015 at 10:51
-
@immibis Yes, I missed that it will overflow int before precision on the floats becoming an issue.– TaemyrOct 23, 2015 at 11:11
-
@immibis Note the bottom of my post: Ignore the type and overflow errors. I was just taking what I thought was an unsolved problem as the basis of a decision--I know the code isn't perfect. It's a problem that can't be brute-forced anyway. Oct 23, 2015 at 17:15
Look at this example:
public boolean isEven(int i){
if(i % 2 == 0)
return true;
if(i % 2 == 1)
return false;
return false;
}
The compiler can't know that an int can only be even or odd. Therefore the compiler must be able to understand the semantics of your code. How should this be implemented? The compiler can't ensure that the lowest return will never be executed. Therefore the compiler can't detect the dead code.
-
1Umm, really? If I write that in C# + ReSharper I get a couple of hints. Following them finally gives me the code
return i%2==0;
. Oct 21, 2015 at 21:37 -
10Your example is too simple to be convincing. The specific case of
i % 2 == 0
andi % 2 != 0
doesn't even require reasoning about the value of an integer modulo a constant (which is still easy to do), it only requires common subexpression elimination and the general principle (canonicalization, even) thatif (cond) foo; if (!cond) bar;
can be simplified toif (cond) foo; else bar;
. Of course "understanding semantics" is a very hard problem, but this post neither shows that it is, nor shows that solving this hard problem is necessary for dead code detection.– user395760Oct 21, 2015 at 21:39 -
5In your example, an optimizing compiler will spot the common subexpression
i % 2
and pull it out into a temporary variable. It will then recognize that the twoif
statements are mutually exclusive and can be written asif(a==0)...else...
, and then spot that all possible execution paths go through the first tworeturn
statements and therefore the thirdreturn
statement is dead code. (A good optimizing compiler is even more aggressive: GCC turned my test code into a pair of bit-manipulation operations).– MarkOct 21, 2015 at 23:16 -
1This example is good for me. It represents the case when a compiler does not know about some factual circunstances. The same goes for
if (availableMemory()<0) then {dead code}
. Oct 22, 2015 at 12:25 -
1@LittleSanti: Actually, GCC will detect that everything you wrote there is dead code ! It's not just the
{dead code}
part. GCC discovers this by proving there's an unavoidable signed integer overflow. All code on that arc in the execution graph is therefore dead code. GCC can even remove the conditional branch that leads to that arc.– MSaltersOct 23, 2015 at 14:10
if (isPrime(1234234234332232323423)){callSomething();}
will this code ever call something or not? There are many other examples, where deciding wether a function is ever called is by far more expensive than just including it in the program.public static void main(String[] args) {int counterexample = findCollatzConjectureCounterexample(); System.out.println(counterexample);}
<- is the println call dead code? Not even humans can solve that one!