I recently came across an issue where my compiler was not able to eliminate some "obviously" dead code - it was a function that returned nothing, with no side effects, and a cursory analysis of the code revealed that it would obviously terminate.
Investigating this further, I found it was extremely easy to write very short programs for which basically every major compiler will emit a bunch of dead code. (Side note - it's worse when using a C++ compiler - AFAIU 'forward progress' is guaranteed so even infinite loops should be able to be removed!)
// when m <= 0 this will never enter the loop, so will terminate
// when n >= m, j will be incremented each time through the loop until
// j == m, so the loop will terminate
void naught(int n, int m) {
int i = 0, j = 0;
while(j < m) {
if (i < n) {
i++;
j++;
}
}
}
// each two loop iterations the value of i gets incremented by 3, and
// then decremented by 1. eventually it will be greater than or equal
// to the value of n and so the loop will terminate. We can ignore
// overflow since it is undefined; a language with unbounded integer
// types would also terminate.
void zip(int n) {
int i=0;
while (i < n) {
if (i % 2 == 0)
i += 3;
else
i--;
}
}
// each time through the loop the value of i is increased; so it will
// terminate. same comments about undefined behaviour / unbounded types
// apply here
void nothing(int n) {
int i=2;
while (i < n) {
i *= i;
}
}
// on the first iteration through the loop i becomes equal to n + 1,
// so it will terminate. ditto on undef / unbounded
void zilch(int n) {
int i=0;
while (i < n) {
i += (n / (i + 1)) + 1;
}
}
// if i <= 0 we never enter the loop. otherwise, on the first iteration,
// i gets divided by i + 1 which equals zero from rounding.
// ditto on undef / unbounded
void nada(int n) {
int i=n;
while (i > 0) {
i /= i + 1;
}
}
Is there some fundamental reason that compilers fail in these simple cases? This lack of optimization does not seem to be compiler-specific, or language specific, so I thought it might be because of lack of research (hence posting here). Has there been much research in this area? When a compiler sees the snippets above, what are the obstacles in its way that prevent it from removing the code?
To my human brain, the "obvious" thing to do would be to work out where the loops terminate and where not, and replace the entire thing with a simple if statement. If optimizing for C++, I would immediately remove all the loops since forward progress is guaranteed. Why can't the compiler do the same?
Edit:
Maybe I should have been more clear in my question; I am aware that the problem is undecidable in general, but to me these seem like relatively "easy" examples (especially in a C++ compiler, where AFAIU they should all be able to be removed). Optimization in general is an undecidable problem but it has not stopped optimizers from being written. I am interested whether there has been any research in this area.
naught()
will loop forever if m > 0 and n < 0 -- not what I'd call dead code. $\endgroup$naught
, yes it can loop forever, but I would expect the compiler to replace it withif (m > 0 && n < m) while(1);
at the very least $\endgroup$