在'gcc -O2'上优化了函数无限循环

上下文
我的一个朋友被问到了下面的难题:

void fn(void) { /* write something after this comment so that the program output is 10 */ /* write something before this comment */ } int main() { int i = 5; fn(); printf("%d\n", i); return 0; } 

我知道可以有多种解决scheme,一些涉及macros观,一些假设一些关于实施和违反C.

我感兴趣的一个特别的解决scheme是对堆栈做一些假设,然后编写下面的代码:(我明白这是未定义的行为,但在许多实现上可能按预期工作)

 void fn(void) { /* write something after this comment so that the program output is 10 */ int a[1] = {0}; int j = 0; while(a[j] != 5) ++j; /* Search stack until you find 5 */ a[j] = 10; /* Overwrite it with 10 */ /* write something before this comment */ } 

问题
这个程序在MSVC和gcc没有优化工作正常。 但是当我用gcc -O2标志编译它或者尝试ideone时 ,它在函数fn无限循环。

我的观察
当我用gcc -S vs gcc -S -O2编译这个文件并进行比较时,它清楚地显示了gcc在函数fn保持了一个无限循环。


我明白,因为代码调用未定义的行为,不能称之为错误。 但是为什么编译器会分析这个行为,并在O2留下一个无限循环呢?


许多人评论知道如果一些variables变为易变的行为。 预期的结果是:

  • 如果ij更改为volatile ,程序行为保持不变。
  • 如果数组a被制成volatile ,程序不会受到无限循环。
  • 此外,如果我申请以下补丁
 - int a[1] = {0}; + int aa[1] = {0}; + int *a = aa; 

程序行为保持不变(无限循环)

如果我用gcc -O2 -fdump-tree-optimized编译代码,我得到下面的中间文件:

 ;; Function fn (fn) (executed once) Removing basic block 3 fn () { <bb 2>: <bb 3>: goto <bb 3>; } ;; Function main (main) (executed once) main () { <bb 2>: fn (); } Invalid sum of incoming frequencies 0, should be 10000 

这validation了在下面的答案之后做出的断言。

这是未定义的行为,所以编译器可以做任何事情,我们可以在GCC 4.8之前的版本中find一个类似的例子,在这个例子中gcc采取了一个未定义行为的循环,并优化它以:

 L2: jmp .L2 

文章说( 重点是我的 ):

当然这是一个无限循环。 由于SATD()无条件地执行未定义的行为(这是一个types3函数), 所以对于正确的C编译器来说任何翻译(或者根本没有)是完全可以接受的行为 。 未定义的行为是在退出循环之前访问d [16]。 在C99中,创build一个指向元素的指针是合法的,但是该指针不能被解除引用 。 同样,数组单元格不能访问数组末尾的一个元素。

如果我们用godbolt检查你的程序,我们会看到:

 fn: .L2: jmp .L2 

优化器使用的逻辑可能如下所示:

  • a的所有元素都初始化为零
  • a在循环之前或之内从不修改
  • 所以a[j] != 5永远是真的 – >无限循环
  • 由于无限, a[j] = 10; 是无法达到的,所以可以优化,所以可以aj因为他们不再需要确定循环条件。

这与文章中的情况类似:

 int d[16]; 

分析以下循环:

 for (dd=d[k=0]; k<16; dd=d[++k]) 

喜欢这个:

当看到d [++ k]时,可以假设k的增加值在数组边界内,否则就会出现未定义的行为。 对于这里的代码,GCC可以推断k在0..15范围内。 稍后GCC看到k <16时,它自己说:“啊哈,表情总是如此,所以我们有一个无限循环。

也许有一个有趣的次要点,就是无限循环是否被认为是可观测行为( 与as-if规则相对应 ),这影响着无限循环是否也可以被优化掉。 从C编译器中可以看出, 驳斥费马最后一个定理 ,在C11之前至less有一些解释的余地​​:

许多知识渊博的人(包括我)都认为,程序的终止行为是不能改变的。 很显然,一些编译器的作者不同意,或者不相信这很重要。 合理的人对解释的不同意见似乎表明C标准是有缺陷的。

C11在第6.8.5迭代语句中增加了一些说明,在本答案中有更详细的介绍。

在优化版本中,编译器决定了几件事情:

  1. 数组a在testing之前不会改变。
  2. 数组a不包含5

因此,我们可以将代码重写为:

 void fn(void) { int a[1] = {0}; int j = 0; while(true) ++j; a[j] = 10; } 

现在,我们可以做出进一步的决定:

  1. while循环之后的所有代码都是死代码(unreachable)。
  2. j是书面的,但从来没有读过。 所以我们可以摆脱它。
  3. a永远不会被读取。

在这一点上,你的代码已经被缩减为:

 void fn(void) { int a[1] = {0}; while(true); } 

而且我们可以做出这样的说明,即现在从来没有读过,所以我们也要去掉它:

 void fn(void) { while(true); } 

现在,未经优化的代码:

在未经优化的生成代码中,数组将保留在内存中。 而且你会在运行时逐字地走。 一旦你走过数组的末尾,可能会有5可读的数据。

这就是为什么未优化版本有时不会崩溃和烧毁的原因。

如果循环没有被优化成无限循环,那么可能是由于静态代码分析发现你的数组是

  1. volatile

  2. 只包含0

  3. 永远不会被写入

因此它不可能包含数字5 。 这意味着一个无限循环。

即使不这样做,你的方法也很容易失败。 例如,有些编译器可能会优化你的代码而不会使你的循环无限,但是会把i的内容塞进一个寄存器,使它不能从堆栈中获得。

作为一个便笺,我打赌你的朋友实际上期望的是这样的:

 void fn(void) { /* write something after this comment so that the program output is 10 */ printf("10\n"); /* Output 10 */ while(1); /* Endless loop, function won't return, i won't be output */ /* write something before this comment */ } 

或者这个(如果包含stdlib.h ):

 void fn(void) { /* write something after this comment so that the program output is 10 */ printf("10\n"); /* Output 10 */ exit(0); /* Exit gracefully */ /* write something before this comment */ }