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

控制表达式不是常量的迭代语句表达式,¹⁵⁶⁾ 不执行输入/输出操作，不执行访问易失性对象，并且不执行同步或原子操作其主体中的操作，控制表达式，或(如果是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:

• 在序列点，易失性对象是稳定的，因为先前的访问是尚未发生完整和后续访问.
• 在程序终止时，所有写入文件的数据应与结果相同根据抽象语义执行程序会产生.
• 交互设备的输入和输出动态应按照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.

更新

我不知何故错过了上述文章的后续内容，重新审视编译器和终止关于 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 函数，
• 访问或修改易失性对象，或
• 执行同步操作或原子操作.

然后在 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屋！