被编译器可以消除无限循环？ [英] Are compilers allowed to eliminate infinite loops?

问题描述

能否优化编译器删除无限循环，不改变任何数据，如

 而（1）
  / *空操作* /;
 

从分析数据流图的编译器可以推导出，这样的循环是死code无任何副作用。

时删除由C90 / C99标准禁止无限循环？

请问C90 C99或标准允许编译器来删除这样的循环？

UPD：微软C ++ 6.0版本基本上是这样做优化，看到咖啡馆的链接

 标签：转到标号;
返回0;
 

将转换为

 返回0;
 

解决方案

的 C11 阐明了这个问题的答案，在C11标准草案 6.8.5 的迭代语句的补充以下段：

  

这是循环语句的控制前pression不是一个常数
  前pression， ^156）执行没有输入/输出操作，不
  访问易失性的目的，并且不执行同步或原子
  在其体内的操作，控制前pression，或（在一个时
  for语句）的前pression-3，可以通过执行假定
  终止 ^157）

和脚注 157 说：

  

这是为了让编译器转换，如去除空循环即使当
  终端无法证明。

所以，你的具体的例子：

 而（1）
  / *空操作* /;
 

不是优化公平的游戏，因为控制前pression是一个不断前pression。

无限循环为UB

那么，为什么编译器允许上述规定的例外优化掉无限循环，以及汉斯·贝姆提供了一种生产无限循环中未定义行为的理由：的 N1528：为什么无限循环不确定的行为，下面的报价提供了一个很好的感觉所涉及的问题：

  

由于N1509正确地指出，目前的草案实质上给
  未定义行为在6.8.5p6无限循环。对于一个主要问题
  这样做是，它允许code键横跨一个潜在的移动
  非终止循环。例如，假设我们有下面的循环，
  其中，数量和COUNT2都是全局变量（或有他们的地址
  取），p是一个局部变量，其地址没有被考虑：

 为（P = Q，P = 0;！P =  - ＆gt;接下来）{
    ++计数;
}
为（P = Q; P = 0;！P =  - ＆gt;接着）{
    ++ COUNT2;
}
 

  
  

难道这两个循环由下面的循环进行合并，并取代？

 为（P = Q，P = 0;！P =  - ＆gt;接下来）{
        ++计数;
        ++ COUNT2;
}
 

  
  

如果没有6.8.5p6的特别豁免的无限循环，这
  将被禁止：如果第一循环不会终止，因为q
  指向一个圆形的名单，原来从来没有写入COUNT2。从而
  它可以在平行于访问或另一个线程运行
  更新COUNT2。这已不再是与转换版本安全
  这确实访问COUNT2尽管无限循环。因此，
  转型可能引入了数据竞争。

  
  

在这样的情况下，这是非常不可能的编译器将能够
  证明循环终止;那就要明白在于q点
  这样的无环名单，我相信这是超出了大多数的能力
  主流的编译器，往往不可能没有整个程序
  信息。

C99

由于C99没有这种能开出，我们期待着的 AS-if规则的覆盖部分 5.1.2.3 这基本上是说编译器仅具有模拟程序的可观察行为的要求如下：

  

在一个符合标准的实现最低要求是：

  
  

  
• 在序列点，挥发性对象是在previous访问是稳定感
    完整的后续访问还没有发生。

  
• 在程序终止时，写入文件的所有数据必须是相同的结果
    根据抽象语义程序的执行将产生

  交互式设备的
• 输入和输出动态中规定应采取的地方
    7.19.3。这些要求的目的是使无缓冲或行缓冲输出
    尽快出现，以确保提示信息实际出现之前，
    一个程序等待输入。

  

这方面的一个严格的阅读似乎允许实现优化一个无限循环的路程。当然，我们可以拿出场景中优化掉一个无限循环会导致在观察行为的改变：

 而（1）;
的printf（世界你好\\ n）;
 

很多人认为，影响一个进程的终止也可观察到的行为，这个位置被采取 C编译器反驳费马大定理：

  

编译器给予相当自由它是如何实现的C程序，但它的输出必须有相同的外部可见的行为，该方案将时间$ P $由在所述的C抽象机PTED标准。许多知识渊博的人（包括我）阅读的话说，程序的终止行为，不得更改。显然，一些编译器作者不同意，否则不认为它很重要。即合理的人持反对意见的跨pretation的事实似乎表明，在C标准是有缺陷的。

更新

我莫名其妙地错过了后续的上述文章，编译器和再探终止其说以下有关章节 5.1.2.3 ：

  

第二个要求是很棘手的。如果谈论抽象的机器上运行的程序终止时，那么它是空洞满足，因为我们的计划不会终止。如果它被谈论由编译器生成的实际程序的终止，则C实现是越野车，因为写入到文件中的数据（stdout是一个文件）从由抽象机写入的数据不同。 （这个读数是由于汉斯贝姆;我没能逗这个微妙超出标准）

你也可以做一个较弱的论点，即需要在C11创造出雕琢，让空循环的清除意味着这不是一个允许的优化previously。

这是否适用于无限循环转到以及？

相信意图是，这也适用于无限转到循环为好。在C ++中这显然是因为部分案件 1.10 的 [intro.multithread] 的说道：

  

的实施可能会认为任何线程最终将执行下列操作之一

  
  

  
• 终止

  
• 请打电话给库I / O功能，

  
• 访问或修改volatile对象，或

  
• 执行同步操作或一个原子操作。

  

和意图，然后在 N1528 pssed前$ P $是，C和C ++标准一致：

  

由于编译器后端的C和C ++编译器之间通常共享，看来最重要的是WG14 WG21和上采取任何的解决方案达成一致。该方案将是后端特殊处理两种语言的，或处理C code当禁用优化。无论是出现在所有可取的。

和结尾说：

  

WG21正在考虑改进的措词，使处理办法相一致。希望WG14将跟踪任何变化。

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

请注意又见美国评论38这里和 N3196 这是这更改了纸张从应用。

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

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