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

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.5 迭代声明中添加了以下段落:

一个迭代语句,其控制表达式不是常量表达式,¹⁵⁶⁾不执行输入/输出操作,不访问易失性对象,并且不在其体内执行同步或原子操作,控制表达式,或(在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) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

这两个循环可以合并并由以下循环替换吗？

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

如果没有6.8.5p6中针对无限循环的特殊分配,则不允许这样做:如果第一个循环没有因为q指向循环列表而终止,则原始的永远不会写入count2.因此,它可以与访问或更新count2的另一个线程并行运行.对于转换版本,尽管存在无限循环,但它不再安全.因此,转型可能引入数据竞争.

在这种情况下,编译器不太可能证明循环终止; 它必须理解q指向非循环列表,我认为这超出了大多数主流编译器的能力,并且如果没有完整的程序信息通常是不可能的.

C99

由于C99没有这样做,我们会看到章节中所述的as-if规则,5.1.2.3它基本上说编译器只需要模拟程序的可观察行为,要求如下:

符合实施的最低要求是:

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

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

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

许多人认为影响一个过程的终止也是可观察到的行为,这个位置是在C Compilers Disprove Fermat的最后定理中得出的:

编译器在如何实现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,这是应用此更改的论文.

Answer 2

普遍无法检测无限循环:请参阅暂停问题.因此,任何编译器所能做的最好的事情就是采取一个不错的猜测 - 例如OP中提到的明显情况.

但为什么这会是可取的呢？我可以看到发出警告并仍然允许行为,但是删除循环不是"优化" - 它改变了程序的行为!

Answer 3

循环不是死代码,它基本上阻止程序达到它后面的任何东西.如果删除循环,则不会发生这种情况,因此编译器无法删除循环.

它可以用平台相关的空闲指令代替它,以通知处理器线程不再执行任何操作.

编译器可以做的是删除循环后出现的任何代码,因为它无法访问并且永远不会被执行.