c - 编译器是否允许消除无限循环？

Question

优化编译器是否可以删除无限循环，这不会更改任何数据，例如

while(1) 
  /* noop */;

通过分析数据流图，编译器可以得出这样的循环是“死代码”，没有任何副作用。

C90/C99 标准是否禁止删除无限循环？

C90 或 C99 标准是否允许编译器删除此类循环？

更新:“Microsoft C 版本 6.0 本质上做了这种优化。”，请参阅 caf 的链接。

label: goto label;
return 0;

将转换为

return 0;

Answer 1

C11为了澄清这个问题的答案，在C11标准草案6.8.5Iteration statements中添加了以下段落:

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.¹⁵⁷⁾

和脚注157说:

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

所以你的具体例子:

while(1) 
  /* noop */;

对于优化来说这不是公平的游戏，因为控制表达式是常量表达式。

无限循环作为 UB

那么，为什么允许编译器优化无限循环(除了上面提供的异常(exception))，Hans Boehm 提供了使无限循环未定义行为的基本原理:N1528: Why undefined behavior for infinite loops? ，以下引用对所涉及的问题给出了很好的感觉:

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

由于 C99 没有这种划分，我们将引用 5.1.2.3 节中介绍的as-if 规则，它基本上说编译器只需要模拟程序的可观察行为，要求如下:

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.

严格阅读此内容似乎允许实现优化无限循环。我们当然可以想出优化无限循环会导致可观察行为发生变化的场景:

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

许多人认为影响进程的终止也是可观察的行为，这个立场在 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.

更新

我不知何故错过了上述文章的后续内容，Compilers and Termination Revisited其中关于 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.)

人们还可以提出一个较弱的论点，即需要在 C11 中创建一个雕刻以允许删除空循环，这意味着这在以前不是允许的优化。

这也适用于无限 goto 循环吗？

我相信其目的是这也适用于无限 goto 循环。在 C++ 中，情况显然如此，因为 1.10 [intro.multithread] 节说:

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.

然后，N1528 中表达的意图是 C 和 C++ 标准达成一致:

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.

最后说:

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

目前，C11 标准在 5.1.2.4 节中不包含类似的措辞 多线程执行和数据竞争，但考虑到 N1528假设编译器将无限 goto 循环视为 C 和 C++ 中的未定义行为似乎是明智的。

请注意另请参阅US comment 38 here和 N3196这是应用此更改的论文。