Undefined behavior can result in time travel

To summarize at least one of them, the compiler doesn't really see it as “detecting undefined behavior and optimizing accordingly”. It sees it as doing the right thing for all defined behaviors. The sort of imprecise analysis it does lead it to consider plenty of possible undefined behaviors, many of which cannot happen in real executions. It ignores these as a matter of fact, but reporting them would not tell the programmer anything it doesn't know, and would be perceived as noise.

On the example for (int i=1; i==0; i++) …, the compiler does not infer that i eventually overflows (undefined behavior). It infers that i is always positive, and thus that the condition is always false.

For a trivial NULL-related example, the standard C free() function does a NULL check on its parameter. free(NULL) is legal and does nothing. A naive "does this check for NULL after dereferencing the pointer?" checker would therefore warn for this code:

    printf("the pointer's value is %d", *p);
    free(p);

Issuing an error or warning about this would flood stuff with warnings due to inlining/macros, you name it.

This happens all the time.

Basically, distinguishing between the things that are accidents, and things that are on purpose and expected to be optimized away, is very very very hard.

If you know that p is not NULL, the code is just fine. The compiler has to compile it.

If the compiler is indeed allowed to assume that the pointer passed to realloc() becomes invalid, then I would expect it to actually optimize out that entire if-check, under the assumption that the `*p` is undefined behavior, and therefore that `p == q` must never be true.

Getting different values for the print if you move the assignments inside the if statement suggests to me that a) it's assuming the pointers don't alias, and therefore b) that it assumes it doesn't have to read the values back out of the pointer when printing them but can just reuse the values it knows it wrote to the pointer. But if it assumes the pointers don't alias, then I would think it would assume that means `p == q` can't be true.

http://en.m.wikipedia.org/wiki/Heisenbug

Basically, since i=4 causes undefined behaviour, the compiler assumes that it can't possibly happen[1] and the only way that it can't happen is if one of the prior (i < 4) checks were true.

Therefore all legal code paths (ie all code paths that don't result in undefined behaviour) return true.

So it optimises it to simply return true. Because otherwise i=4 would have happened, but that's undefined, so impossible[1]

[1] but if it does happen, that's ok, because that would be undefined behaviour, which allows the compiler to do whatever it feels like anyway

And, i=4 is not ignored by the compiler, it is declared as undefined behaviour. What the compiler MAY do is to always return true.

In this cause, it will always return true, either because it reached the 5th value ([4]), or because there was a match in the first 4 values.

As the result will always be true, the compiler may then simply return true and skip the loop.

In this particular case, the 'contract' and the actual code imply that "The only allowed values of 'int v' are those that actually are found in the table"; for those values the function correctly returns true; and for all the possible 'illegal' arguments any and every possible behavior would be correct.

Furthermore, when undefined behaviour is invoked anywhere within a program, the whole program is undefined.

The problem is that programmers probably assume that many things which are undefined are implementation defined.

An example of something that is implementation defined are struct layouts: the standard (I think) does say that the order must be the same as defined in the struct definition, but it allows the implementation to put as much space as it wants inbetween those values (for optimal architecture alignment.) Things that are implementation defined are typically going to be things which must happen, but if the standard defined exactly how, it would unnecessarily constrain the implementation (such as being able to perform optimizations).

It's also worth noting that your trivial example would result in basically everything be removed, but most non-trivial examples don't do that. The most common 'optimization' from undefined-behaviour is that the compiler doesn't need to check for those conditions and can let whatever will happen happen, and that only works if it's defined in a program-wide anything-goes sense. If it's defined on a local sense, then if say 'data' was passed-in as a parameter instead of declared, the compiler would have to insert a NULL check to make sure no undefined-behaviour happens and the program doesn't crash (So that "Bar" prints). By defining undefined-behaviour like it is, there's no requirement for the compiler to do a NULL check, it can instead just assume the programmer will never let it happen and produce code with that in mind. Same thing with integer overflow and similar cases (Though things get a bit hairier there).

    if(x){
        foo();
    }else{
        undefined();
    }

The compiler often can't verify it (halting problem and friends), but it allows for nice optimizations by assuming that the code as written is actually correct, and the check was skipped intentionally.

  $ g++ -O2 -Wall -Werror -o asdf asdf.cpp
  asdf.cpp: In function ‘int main(int, char**)’:
  asdf.cpp:9:29: error: iteration 3u invokes undefined behavior [-Werror=aggressive-loop-optimizations]
     std::cout << (i*1000000000) << std::endl;
                               ^
  asdf.cpp:7:2: note: containing loop
    for (int i = 0; i < 4; ++i)
    ^
  cc1plus: all warnings being treated as errors

You can get defined behaviour by casting to unsigned:

  std::cout << (int)(((unsigned) i) * 1000000000U) << std::endl;

To invoke undefined behavior and strange optimizations, you'd need to rearrange the code a bit:

    a = *b;
    if (!b)
        a = 3;

A check for NULL before you dereference is always safe. It's when you do it the other way around that the compiler can start doing strange things.