When did Undefined Behavior in C jump the causality barrier

Question

Some hyper-modern C compilers will infer that if a program will invoke Undefined Behavior when given certain inputs, such inputs will never be received. Consequently, any code which would be irrelevant unless such inputs are received may be eliminated.

As a simple example, given:

void foo(uint32_t);

uint32_t rotateleft(uint_t value, uint32_t amount)
{
  return (value << amount) | (value >> (32-amount));
}

uint32_t blah(uint32_t x, uint32_t y)
{
  if (y != 0) foo(y);
  return rotateleft(x,y);
}

a compiler may infer that because evaluation of value >> (32-amount) will yield Undefined Behavior when amount is zero, function blah will never be called with y equal to zero; the call to foo can thus be made unconditional.

From what I can tell, this philosophy seems to have caught hold sometime around 2010. The earliest evidence I've seen of its roots goes back to 2009, and it's been enshrined in the C11 standard which explicitly states that if Undefined Behavior occurs at any point in a program's execution, the behavior of the entire program retroactively becomes undefined.

Was the notion that compilers should attempt to use Undefined Behavior to justify reverse-causal optimizations (i.e. the Undefined Behavior in the rotateleft function should cause the compiler to assume that blah must have been called with a non-zero y, whether or not anything would ever cause y to hold a non-zero value) seriously advocated prior to 2009? When was such a thing first seriously proposed as an optimization technique?

[Addendum]

Some compilers have, even in the 20th Century, included options to enable certain kinds of inferences about loops and the values computed therein. For example, given

int i; int total=0;
for (i=n; i>=0; i--)
{
  doSomething();
  total += i*1000;
}

a compiler, even without the optional inferences, might rewrite it as:

int i; int total=0; int x1000;
for (i=n, x1000=n*1000; i>0; i--, x1000-=1000)
{
  doSomething();
  total += x1000;
}

since the behavior of that code would precisely match the original, even if the compiler specified that int values always wrap in mod-65536 two's-complement fashion. The additional-inference option would let the compiler recognize that since i and x1000 should cross zero at the same time, the former variable can be eliminated:

int total=0; int x1000;
for (x1000=n*1000; x1000 > 0; x1000-=1000)
{
  doSomething();
  total += x1000;
}

On a system where int values wrapped mod 65536, an attempt to run either of the first two loops with n equal to 33 would result in doSomething() being invoked 33 times. The last loop, by contrast, wouldn't invoke doSomething() at all, even though the first invocation of doSomething() would have preceded any arithmetic overflow. Such a behavior might be considered "non-causal", but the effects are reasonably well constrained and there many cases where the behavior would be demonstrably harmless (in cases where a function is required to yield some value when given any input, but the value may be arbitrary if the input is invalid, having the loop finish faster when given an invalid value of n would actually be beneficial). Further, compiler documentation tended to be apologetic for the fact that it would change the behavior of any programs--even those that engaged in UB.

I'm interested in when compiler writers' attitudes changed away from the idea that platforms should when practical document some usable behavioral constraints even in cases not mandated by the Standard, to the idea that any constructs which would rely upon any behaviors not mandated by the Standard should be branded illegitimate even if on most existing compilers it would work as well or better than any strictly-compliant code meeting the same requirements (often allowing optimizations which would not be possible in strictly-compliant code).

Answer 1

Undefined behavior is used in situations where it is not feasible for the spec to specify the behavior, and it has always been written to allow absolutely any behavior possible.

The extremely ultra-loose rules for UB are helpful when you think about what a spec conforming compiler must go through. You may have sufficient compiling horsepower to emit an error when you do some bad UB in one case, but add a few layers of recursion and now the best you can do is a warning. The spec has no concept of "warnings," so if the spec had given a behavior, it would have to be "an error."

The reason we see more and more side effects of this is the push for optimization. Writing a spec conforming optimizer is hard. Writing a spec conforming optimizer which also happens to do a remarkably good job guessing what you intended when you went outside the spec is brutal. It is much easier on the compilers if they get to assume UB means UB.

This is especially true for gcc, which tries to support many many instruction sets with the same compiler. It is far easier to let UB yield UB behaviors than it is to try to grapple with all the ways every single UB code could go wrong on every platform, and factor it into the early phrases of the optimizer.

Answer 2

"Undefined behaviour might cause the compiler to rewrite code" has happened for a long time, in loop optimisations.

Take a loop (a and b are pointer to double, for example)

for (i = 0; i < n; ++i) a [i] = b [i];

We increment an int, we copy an array element, we compare with a limit. An optimising compiler first removes the indexing:

double* tmp1 = a;
double* tmp2 = b;
for (i = 0; i < n; ++i) *tmp1++ = *tmp2++;

We remove the case n <= 0:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    for (; i < n; ++i) *tmp1++ = *tmp2++;
}

Now we eliminate the variable i:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    double* limit = tmp1 + n;
    for (; tmp1 != limit; tmp1++, tmp2++) *tmp1 = *tmp2;
    i = n;
}

Now if n = 2^29 on a 32 bit system or 2^61 on a 64 bit system, on typical implementations we will have tmp1 == limit, and no code is executed. Now replace the assignment with something that takes a long time so that the original code will never run into the inevitable crash because it takes too long, and the compiler has changed the code.

Answer 3

It has always been the case in C and C++ that as a result of undefined behaviour, anything can happen. Therefore it has also always been the case that a compiler can make the assumption that your code doesn't invoke undefined behaviour: Either there is no undefined behaviour in your code, then the assumption was correct. Or there is undefined behaviour in your code, then whatever happens as a result of the incorrect assumption is covered by "anything can happen".

If you look at the "restrict" feature in C, the whole point of the feature is that the compiler can assume there is no undefined behaviour, so there we reached the point where the compiler not only may but actually should assume there is no undefined behaviour.

In the example that you give, the assembler instructions usually used on x86 based computers to implement left or right shift will shift by 0 bits if the shift count is 32 for 32 bit code or 64 for 64 bit code. This will in most practical cases lead to undesirable results (and results that are not the same as on ARM or PowerPC, for example), so the compiler is quite justified to assume that this kind of undefined behaviour doesn't happen. You could change your code to

uint32_t rotateleft(uint_t value, uint32_t amount)
{
   return amount == 0 ? value : (value << amount) | (value >> (32-amount));
}

and suggest to the gcc or Clang developers that on most processors the "amount == 0" code should be removed by the compiler, because the assembler code generated for the shift code will produce the same result as value when amount == 0.

Answer 4

"and it's been enshrined in the C11 standard which explicitly states that if Undefined Behavior occurs at any point in a program's execution, the behavior of the entire program retroactively becomes undefined." This is not incorrect. The ISO C standard never said anything like this and such an interpretation is not consistent with the wording in the standard. There is also a new note to C23 that explicitly makes clear that this is not the case.

Answer 5

This is because there is a bug in your code:

uint32_t blah(uint32_t x, uint32_t y)
{
    if (y != 0) 
    {
        foo(y);
        return x; ////// missing return here //////
    }
    return rotateleft(x, y);
}

In other words, it only jumps the causality barrier if the compiler sees that, given certain inputs, you are invoking undefined behavior beyond doubt.

By returning right before the invocation of undefined behavior, you tell the compiler that you are consciously preventing that undefined behavior from executing, and the compiler acknowledges that.

In other words, when you have a compiler that tries to enforce the specification in a very strict way, you have to implement every possible argument validation in your code. Furthermore, these validation must occur before the invocation of the said undefined behavior.

Wait! And there is more!

Now, with compilers doing these super-crazy yet super-logical things, it is your imperative to tell the compiler that a function isn't supposed to continue execution. Thus, the noreturn keyword on the foo() function now becomes mandatory.