允许编译器消除无限循环吗? [英] 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.

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

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

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

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

更新:Microsoft C 版本 6.0 基本上做了这种优化."，参见 caf 的链接.

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

label: goto label;
return 0;

将转化为

return 0;

推荐答案

C11 阐明了这个问题的答案，在草案 C11 标准部分 6.8.5 Iteration statements 中添加了以下段落:

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

控制表达式不是常量的迭代语句不执行输入/输出操作的表达式，¹⁵⁶⁾访问 volatile 对象，并且不执行同步或原子操作其主体中的操作、控制表达式或(在for 语句)它的表达式 3，可以由实现假定终止.¹⁵⁷⁾

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 */;

因为控制表达式是一个常量表达式，所以优化不是公平的游戏.

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

无限循环作为UB

那么为什么允许编译器优化掉无限循环，除了上面提供的例外，Hans Boehm 提供了一个使无限循环未定义行为的基本原理:N1528:为什么无限循环的行为未定义?，下面的引用很好地说明了所涉及的问题:

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:

正如 N1509 正确指出的那样，当前的草案基本上给出了6.8.5p6 中无限循环的未定义行为.的一个主要问题这样做是因为它允许代码跨越潜在的非终止循环.例如，假设我们有以下循环，其中 count 和 count2 是全局变量(或者有它们的地址取)，而p是一个局部变量，其地址未被取:

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;
}

如果没有 6.8.5p6 中对无限循环的特殊规定，这将被禁止:如果第一个循环没有终止，因为 q指向一个循环列表，原来的从不写入count2.因此它可以与另一个访问或访问的线程并行运行更新计数2.转换后的版本不再安全尽管无限循环，它确实访问了 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.

在这种情况下，编译器不太可能能够证明循环终止；它必须了解q点到一个非循环列表，我认为这超出了大多数人的能力主流编译器，如果没有整个程序通常是不可能的信息.

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 规则，它基本上说编译器只需要模拟程序的可观察行为，要求如下:

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:

• 在序列点，volatile 对象是稳定的，因为之前的访问是尚未完成且后续访问.
• 在程序终止时，写入文件的所有数据都应与以下结果相同根据抽象语义执行程序会产生.
• 交互设备的输入和输出动态应按照7.19.3.这些要求的目的是无缓冲或行缓冲输出尽快出现，以确保提示消息实际出现在之前等待输入的程序.

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

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
" ) ;

许多人会争辩说，影响进程的终止也是可观察到的行为，这一立场在 C 编译器证明费马大定理:

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:

编译器在如何实现 C 程序方面具有相当大的自由度，但其输出必须具有与标准中描述的C 抽象机"解释程序时相同的外部可见行为.许多知识渊博的人(包括我)读到这篇文章是说程序的终止行为不能改变.显然，一些编译器作者不同意，或者不相信这很重要.理性的人不同意解释这一事实似乎表明 C 标准存在缺陷.

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部分的内容如下:

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:

第二个要求是棘手的.如果说的是在抽象机上运行的程序的终止，那么它是空谈的，因为我们的程序没有终止.如果它谈论终止编译器生成的实际程序，那么 C 实现是错误的，因为写入文件(stdout 是文件)的数据与抽象机写入的数据不同.(此读数应归功于 Hans Boehm；我未能从标准中挑出这种微妙之处.)

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 中创建一个分割以允许删除空循环意味着这在以前是不允许的优化.

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.

这是否也适用于无限 goto 循环?

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

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

• 终止，
• 调用库 I/O 函数，
• 访问或修改 volatile 对象，或
• 执行同步操作或原子操作.

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

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

由于编译器后端通常在 C 和 C++ 编译器之间共享，因此最重要的是 WG14 和 WG21 就采用的任何解决方案达成一致.替代方案是后端对这两种语言进行特殊处理，或者在处理 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 正在考虑改进措辞，以使处理方式保持一致.希望 WG14 将跟踪任何由此产生的变化.

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++ 中的未定义行为似乎是明智的.

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++.

注意另见 美国评论 38这里和N3196这是应用此更改的论文.

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

这篇关于允许编译器消除无限循环吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！