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

发布于 2024-08-19 17:10:53 字数 357 浏览 4 评论 0原文

优化编译器可以删除无限循环，这不会改变任何数据，就像

while(1) 
  /* noop */;

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

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

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

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

label: goto label;
return 0;

将转变为

return 0;

原文

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;

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

冰雪之触 2024-08-26 17:10:53

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

控制表达式不是常量的迭代语句
不执行输入/输出操作的表达式，¹⁵⁶⁾
访问易失性对象，并且不执行同步或原子操作
其主体中的操作，控制表达式，或（在
for 语句）其表达式-3，可以由实现假设
终止。¹⁵⁷⁾

和脚注 157 说：

这是为了允许编译器进行转换，例如即使在以下情况下也可以删除空循环
无法证明终止。

所以你的具体例子：

while(1) 
  /* noop */;

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

无限循环作为 UB

那么为什么允许编译器优化无限循环（除了上面提供的例外），Hans Boehm 提供了使无限循环未定义行为的基本原理：N1528：为什么无限循环的未定义行为？，下面的引用给人一种很好的感觉问题涉及：

正如 N1509 正确指出的那样，当前草案基本上给出了
6.8.5p6 中无限循环的未定义行为。一个主要问题是
这样做的目的是它允许代码跨潜在的
非终止循环。例如，假设我们有以下循环，
其中 count 和 count2 是全局变量（或者有它们的地址
已取），p是局部变量，其地址尚未被取：
for (p = q; p != 0; p = p -> next) {
    ++计数；
}
for (p = q; p != 0; p = p -> 下一个) {
    ++计数2；
}
这两个循环可以合并并用下面的循环代替吗？
for (p = q; p != 0; p = p -> next) {
        ++计数；
        ++计数2；
}
如果没有 6.8.5p6 中针对无限循环的特殊分配，这
将被禁止：如果第一个循环没有终止，因为 q
指向一个循环列表，原始列表永远不会写入count2。因此
它可以与访问或的另一个线程并行运行
更新计数2。对于转换后的版本来说，这不再安全
尽管存在无限循环，但它确实访问了 count2 。因此
转型可能会引发数据竞争。
在这种情况下，编译器不太可能能够
证明循环终止；它必须明白 q 点
到一个非循环列表，我相信这超出了大多数人的能力
主流编译器，如果没有整个程序通常是不可能的
信息。

C99

由于 C99 没有这种划分，我们将参考 5.1.2.3 节中涵盖的as-if 规则，该规则基本上表示：编译器只需模拟程序的可观察行为，要求如下：

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

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

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

许多人会认为影响进程的终止也是可观察行为，这个立场是在 C 编译器反驳费马大定理：

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

更新

我不知何故错过了上述文章的后续内容，重新审视编译器和终止其中关于 5.1.2.3 部分的内容如下：

第二个要求是棘手的。如果它谈论的是抽象机上运行的程序的终止，那么它是空洞的，因为我们的程序不会终止。如果它谈论的是编译器生成的实际程序的终止，那么C实现是有错误的，因为写入文件（stdout是一个文件）的数据与抽象机写入的数据不同。（这篇文章是汉斯·伯姆（Hans Boehm）写的；我没能从标准中剔除这种微妙之处。）

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

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

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

实现可能假设任何线程最终都会执行以下操作之一
终止，
调用库 I/O 函数，
访问或修改易失性对象，或者
执行同步操作或原子操作。

然后，N1528 中表达的意图是 C 和 C++ 标准同意：

由于编译器后端通常在 C 和 C++ 编译器之间共享，因此 WG14 和 WG21 就采用的任何解决方案达成一致似乎是最重要的。替代方案是后端对两种语言进行特殊处理，或者在处理 C 代码时禁用优化。两者似乎都不可取。

最后说：

WG21 正在考虑改进措辞，以使处理方法保持一致。希望 WG14 能够跟踪由此产生的任何变化。

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

另请注意，请参阅此处的美国评论 38 和 N3196 这是对此进行了更改的纸张被应用。

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.

回复收藏 0 原文