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;
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,156) 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.157)
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:
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 worldn" ) ;
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
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.
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!
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.
链接地址: http://www.djcxy.com/p/30712.html上一篇: C ++ 0x内存模型和推测加载/存储
下一篇: 编译器是否允许消除无限循环？