Are compilers allowed to eliminate infinite loops?

Can optimizing compiler delete infinite loops, which does not changes any data, like

while(1) 
  /* noop */;

From analyzing a data flow graph compiler can derive, that such loop is \"dead code\" without any side effects.

Is deleting of infinite loops prohibited by C90/C99 standards?

Does C90 or C99 standards permit compiler to deleting such loops?

Upd: \"Microsoft C version 6.0 did essentially this optimization.\", see link by caf.

label: goto label;
return 0;

will be transformed to

return 0;

回答1:

C11 clarifies the answer to this question, in the draft C11 standard section 6.8.5 Iteration statements added the following paragraph:

An iteration statement whose controlling expression is not a constant expression,¹⁵⁶⁾ that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.¹⁵⁷⁾

and footnote 157 says:

This is intended to allow compiler transformations such as removal of empty loops even when termination cannot be proven.

So your specific example:

while(1) 
  /* noop */;

is not fair game for optimization since the controlling expression is a constant expression.

Infinite loops as UB

So why are compilers allowed to optimize away infinite loops with the exception provided above, well Hans Boehm provides a rationale for making infinite loops undefined behavior in: N1528: Why undefined behavior for infinite loops?, the following quote gives a good feeling for the issue involved:

As N1509 correctly points out, the current draft essentially gives undefined behavior to infinite loops in 6.8.5p6. A major issue for doing so is that it allows code to move across a potentially non-terminating loop. For example, assume we have the following loops, where count and count2 are global variables (or have had their address taken), and p is a local variable, whose address has not been taken:
for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}
Could these two loops be merged and replaced by the following loop?
for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}
Without the special dispensation in 6.8.5p6 for infinite loops, this would be disallowed: If the first loop doesn\'t terminate because q points to a circular list, the original never writes to count2. Thus it could be run in parallel with another thread that accesses or updates count2. This is no longer safe with the transformed version which does access count2 in spite of the infinite loop. Thus the transformation potentially introduces a data race.

In cases like this, it is very unlikely that a compiler would be able to prove loop termination; it would have to understand that q points to an acyclic list, which I believe is beyond the ability of most mainstream compilers, and often impossible without whole program information.

C99

Since C99 does not have this carve out, we would look to the as-if rule covered in section 5.1.2.3 which basically says that the compiler only has to emulate the observable behavior of a program, the requirements are as follows:

The least requirements on a conforming implementation are:

At sequence points, volatile objects are stable in the sense that previous accesses are complete and subsequent accesses have not yet occurred.

At program termination, all data written into files shall be identical to the result that execution of the program according to the abstract semantics would have produced.

The input and output dynamics of interactive devices shall take place as specified in 7.19.3. The intent of these requirements is that unbuffered or line-buffered output appear as soon as possible, to ensure that prompting messages actually appear prior to a program waiting for input.

A strict reading of this would seem to allow an implementation to optimize an infinite loop away. We can certainly come up with scenarios where optimizing away an infinite loop would cause a change in observable behavior:

while(1) ;
printf( \"hello world\\n\" ) ;

Many would argue that effecting the termination of a process is also observable behavior, this position is taken in C Compilers Disprove Fermat’s Last Theorem:

The compiler is given considerable freedom in how it implements the C program, but its output must have the same externally visible behavior that the program would have when interpreted by the “C abstract machine” that is described in the standard. Many knowledgeable people (including me) read this as saying that the termination behavior of a program must not be changed. Obviously some compiler writers disagree, or else don’t believe that it matters. The fact that reasonable people disagree on the interpretation would seem to indicate that the C standard is flawed.

Update

I somehow missed the the follow-up to the above article, Compilers and Termination Revisited which says the following about section 5.1.2.3:

The second requirement is the tricky one. If it is talking about termination of the program running on the abstract machine, then it is vacuously met because our program does not terminate. If it is talking about termination of the actual program generated by the compiler, then the C implementation is buggy because the data written into files (stdout is a file) differs from the data written by the abstract machine. (This reading is due to Hans Boehm; I had failed to tease this subtlety out of the standard.)

One could also make a weaker argument that the need to create a carve out in C11 to allow empty loop removal implies this was not an allowable optimization previously.

Does this apply to infinite goto loops as well?

I believe the intent is that this also applies to infinite goto loops as well. In C++ this is clearly the case since section 1.10 [intro.multithread] says:

The implementation may assume that any thread will eventually do one of the following

terminate,

make a call to a library I/O function,

access or modify a volatile object, or

perform a synchronization operation or an atomic operation.

and then intent as expressed in N1528 is that the C and C++ standard agree:

Since compiler back-ends are typically shared between C and C++ compilers, it appears most important that WG14 and WG21 agree on whatever solution is adopted. The alternatives would be special treatment of the two languages by the back-end, or disabling optimizations when processing C code. Neither appears at all desirable.

and at the end says:

WG21 is considering improved wording that makes the treatment consistent. Hopefully WG14 will track any resulting changes.

Currently the C11 standard does not contain the similar wording in section 5.1.2.4 Multi-threaded executions and data races but considering N1528 it seems wise to assume compilers will treat infinite goto loops as undefined behavior in C and C++.

Note also see US comment 38 here and N3196 which is the paper that this changed was applied from.

回答2:

There\'s no way to detect infinite loops universally: see the Halting Problem. So the best any compiler could do is take a decent guess - for example the obvious case mentioned in the OP.

But why would this be desirable? I could see emitting a warning and still allowing the behavior, but to remove the loop is not an \"optimization\" - it changes the behavior of the program!

回答3:

The loop is not dead code, it is basically preventing the program from ever reaching whatever comes after it. This is not what would happen if the loop was removed, so the compiler can not remove the loop.

It might replace it with a platform-dependent idle-instruction to signal the processor that the thread is not going to do anything any more.

What the compiler can do is remove any code that comes after the loop, because it is unreachable and will never be executed.

回答4:

This has been discussed many times before on comp.lang.c (eg. here) without, as far as I know, any consensus outcome.

回答5:

They are a necessity when writing daemons. Why\'d you want to call them dead code?

回答6:

I believe that newer standards explicitly provide that if a piece of code does not access any volatile variables, perform I/O, etc. any other code which does not rely upon anything computed in the first piece may be arbitrarily sequenced before it. If an infinite loop does not perform any I/O, nor compute any value which is used later in the program, a compiler may simply defer execution of the loop until everything else has completed.