37

优化编译器可以删除无限循环,它不会改变任何数据,比如

while(1) 
  /* noop */;

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

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

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

更新:“Microsoft C 版本 6.0 基本上做了这种优化。”,请参见 caf 的链接。

label: goto label;
return 0;

将转变为

return 0;
4

6 回答 6

34

C11澄清了这个问题的答案,在草案 C11 标准部分6.8.5 迭代语句中添加了以下段落:

一个迭代语句,其控制表达式不是常量表达式,156)不执行输入/输出操作,不访问易失性对象,并且在其主体、控制表达式或(在 for 的情况下)不执行同步或原子操作statement) 其表达式 3,可被实现假定为终止。157)

脚注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 的线程并行运行。尽管存在无限循环,但对于确实访问 count2 的转换版本来说,这不再安全。因此,转换可能会引入数据竞争。

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

C99

由于 C99 没有这种划分,我们将查看部分介绍的as-if 规则5.1.2.3,该规则基本上说编译器只需要模拟程序的可观察行为,要求如下:

对一致性实现的最低要求是:

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

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

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

许多人会争辩说,影响进程的终止也是可观察到的行为,这一立场在C Compilers Disprove Fermat's Last Theorem中采取:

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

更新

我不知何故错过了上述文章的后续,编译器和终止重新访问,其中说以下关于部分5.1.2.3

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

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

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

我相信其意图是这也适用于无限 goto 循环。在 C++ 中,这显然是这种情况,因为1.10 [intro.multithread]部分说:

实现可能假设任何线程最终都会执行以下操作之一

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

然后表达的意图N1528是 C 和 C++ 标准同意:

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

最后说:

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

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

另请注意,请参见此处的美国评论 38N3196,这是应用此更改的论文。

于 2015-02-23T18:44:21.537 回答
9

没有办法普遍检测无限循环:请参阅停止问题。因此,任何编译器所能做的最好的事情就是做出一个体面的猜测——例如 OP 中提到的明显案例。

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

于 2010-02-01T16:19:05.857 回答
8

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

它可能会用一个依赖于平台的空闲指令来代替它,以向处理器发出线程不会再做任何事情的信号。

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

于 2010-02-01T16:18:20.473 回答
4

据我所知,这已在comp.lang.c(例如此处)上多次讨论过,但没有任何共识结果。

于 2010-02-02T00:17:49.850 回答
2

在编写守护程序时,它们是必需的。你为什么要称它们为死代码?

于 2010-02-01T16:14:07.757 回答
0

我相信较新的标准明确规定,如果一段代码不访问任何易失性变量、执行 I/O 等,则任何其他不依赖于第一段中计算的任何内容的代码都可以在它之前任意排序。如果无限循环不执行任何 I/O,也不计算任何稍后在程序中使用的值,编译器可能会简单地推迟循环的执行,直到其他一切都完成。

于 2010-12-08T05:30:40.080 回答