Why is it so difficult to eliminate dead loops?

Question

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.

Answer 1

The conceptual problem here is that dead code elimination is not computable. That is, we know that there is no algorithm that can remove all instances of dead code.

Of course, tools can be created that recognize some instances of dead code and remove them. Which patterns to look for is a matter of taste and skill of the tool creator; it's better to be conservative and err on the site of not breaking things. Language semantics play a huge role as well. I don't think there are overarching conceptual issues there, but I could be wrong.

There may be language-specific subtleties at work that prevent elimination of apparently dead code. For instance, a Java compiler can never remove a private method that is never called from within the class -- it can be executed using reflection. Such special cases are beyond the scope of this site, and best discussed one by one on Stack Overflow.

In the end, I expect there to be trade-offs (as there always are): how much time do you spend on developing the optimizer, how much time do you spend during compilation, for what gain? Maybe an optimization that often creates more efficient code occasionally creates some dead code, which you are willing to accept.