# Why is it so difficult to eliminate dead loops?

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
// 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
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. – j_random_hacker Aug 13 '17 at 13:14
• The rough problem is that is far harder to prove these things about algorithms than it's to run them. All of these examples have finite state and could be proven exhaustively, but not in a reasonable timeframe. – MSalters Aug 13 '17 at 13:39
• @j_random_hacker if n == -2 the loop is never entered. in naught, yes it can loop forever, but I would expect the compiler to replace it with if (m > 0 && n < m) while(1); at the very least – Djzin Aug 13 '17 at 15:48
• C++ declaring infinite loops without side-effects undefined behavior is so horrifying. – CodesInChaos Aug 13 '17 at 16:39
• Please tell us which of the above functions do terminate in all cases (with a justification). Don't forget to take UB in consideration. – Yves Daoust Aug 13 '17 at 19:38