Pros and cons of treating endless loops as "anything can happen" UB, versus merely allowing limited reordering

Question

Many programming languages, including C89, specify that the behavior of a program in terms of sequentially executed steps, whose behavior is in turn defined in terms of the program's state when the step is executed, without regard for any program states that may have occurred in the past or might occur in the future. In such a language, once an implementation starts executing a program fragment like:

extern unsigned short arr[65537];
unsigned test(unsigned q)
{
  unsigned short i=0;
  while (arr[i] != q)
    i++;
  if (q < 65536)
    arr[q] = 2;
  return i;
}

program actions would be limited to reading and writing to i or reading the first 65536 elements of arr unless or until it reached a state where arr[i] was equal to q.

In some situations, it may be difficult for a compiler to determine whether a loop will terminate, but easy for a compiler to recognize that none of the actions within a loop interact in any way with any other program actions which would be performed after the loop executed.

Execution of such loops could never serve any useful purpose in cases where they terminate, and would generally not be useful in cases where they fail to terminate, and it would thus be advantageous to eliminate them. In order to avoid having to write detailed rules about when compilers may eliminate such loops, some language standards simply treat any failure of a side-effect-free loop to terminate as "anything can happen" Undefined Behavior.

This allows some useful transformations "as-if" rules, but also allows compilers to turn code that would have been memory safe (and thus free of Arbitrary Code Execution exploits) if executed as described, or even if loops had been cleanly omitted, with code that is no longer memory safe and could thus be exploited by a malefactor to execute arbitrary code.

Such a compiler, given the above code, might omit both the loop and the following if test, performing an unconditional store to arr[q] even if q was larger than 65535.

When processing tasks that involve input from potentially untrustworthy sources, and are required to be free of Arbitrary Code Execution exploits, what advantages are there--aside from saving a little ink in a language specification--to treating endless loops as "anything can happen" Undefined Behavior rather than specifying that a compiler need only treat a loop or other region of code with a single statically reachable exit as sequenced relative to surrounding code if some individual action (other than a branch) would be sequenced likewise?

Treating endless loops as "anything can happen" UB may simplify the design of compilers specialized for tasks that will never receive input from untrustworthy sources.

But for other tasks, it would seem to allow a compiler fewer optimization opportunities than would be available in a language where programmers could rely upon seemingly-side-effect-free loops that might fail to terminate having no side effects beyond possibly causing program execution to get "stuck".

What advantages, if any, does treating endless loops as "anything can happen" UB, as opposed to allowing more limited reordering, offer when processing tasks involving potentially untrustworthy inputs?

Answer 1

Modern compiler designs are not well equipped to handle situations where two pieces of code, if performed as written, would render each other redundant, but where omitting either would render the other essential. It will be difficult (NP hard, actually) to determine which optimizing transforms should be performed if a decision to perform one optimizing transform might prevent an optimizer from performing what could have been a far more useful transform downstream. It's much easier for compilers to optimize if any piece of code that would be redundant if all other parts were executed may be omitted as redundant without regard for what other parts might have also been omitted.

Answer 2

what advantages are there--aside from saving a little ink in a language specification--to treating endless loops as "anything can happen" Undefined Behavior

"Little ink" is not a side effect: it's the whole point. Where is it written that endless loops are undefined behaviour? In the language standard specification.

Put yourself in the shoes of the language standard person responsible for writing a unique standard that codifies the common denominator of several compiler behaviours, as explained by various compiler representatives that also are part of the standard committee. You ask each representant about the specific things that each compiler does. The replies are:

• Compiler 1: We do not do any optimization. The standard must accommodate this behaviour;
• Compiler 2: We detect endless loops and optimize this to no op. Sometimes. The standard must accommodate this behaviour;
• Compiler 3: We are a decade long project, where hundred programmes worked, some long gone, and our compiler does several dozen optimization passes, some of these passes are repeated in an indeterminate, chaotic order. The compiler passes are so complex that someone actually proved the optimization passes themselves are Turing complete. The standard must accommodate this behaviour.

Let's summarize this as:

Compiler 1	Compiler 2	Compiler 3
No optimizations	We optimize to no-op, sometimes	We do eldritch things

Now, let's rewrite this summary in a more formal language, appropriate for a published standart.

Compiler 1	Compiler 2	Compiler 3
Defined behaviour	Implementation-defined behavior	Indescriptible horror behaviour

These are not consistent behaviors, yet it is still your responsability to write down a consistent description that encompasses all these behaviors for the standard publication.

Basically, you need to find the intersection of:

$$ Know \cap Knowable \cap Unknowable $$

And that's easy. You only need to remember that:

3.63 undefined behavior

behavior for which this document imposes no requirements

Done.

You always can make your compiler to have no undefined behaviour, and also can formalize a new standart where there is no undefined behaviour. But C/C++ standards need to have things like defined, implementation-defined and undefined behaviour because it's a result of a committee tasked with two seemly opposite objectives:

• To have one standart;
• That codifies several practices.