功能优化为'gcc -O2'的无限循环

Question

背景
我被一位朋友问过以下谜题:

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;
}

我知道可以有多个解决方案,一些涉及宏,一些假设有关实现和违反C.

我感兴趣的一个特定解决方案是对堆栈做出某些假设并编写以下代码:(我知道它是未定义的行为,但可能在许多实现中按预期工作)

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 -O2flag 编译它或尝试使用ideone时,它在函数中无限循环fn.

我的观察
当我使用gcc -Svs 编译文件gcc -S -O2并进行比较时,它清楚地显示gcc了函数中保持无限循环fn.

问题
我理解,因为代码调用未定义的行为,不能称之为bug.但编译器为什么以及如何分析行为并留下无限循环O2呢？

---

如果将某些变量更改为volatile,许多人会评论该行为.预期的结果是:

• 如果i或j更改为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

这将验证以下答案后的断言.

Answer 1

这是未定义的行为,因此编译器可以真正做任何事情,我们可以在GCC 4.8之前的Breaks Broken SPEC 2006基准测试中找到类似的例子,其中gcc采用未定义行为的循环并将其优化为:

L2:
    jmp .L2

文章说(强调我的):

当然这是一个无限循环.由于SATD()无条件地执行未定义的行为(它是类型3函数),因此对于正确的C编译器,任何转换(或根本不转换)都是完全可接受的行为.未定义的行为是在退出循环之前访问d [16].在C99中,创建指向一个位置超过数组末尾的元素的指针是合法的,但不能取消引用该指针.同样,不得访问超出数组末尾的一个元素的数组单元格.

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

fn:
.L2:
    jmp .L2

优化器使用的逻辑可能是这样的:

• 所有元素a都被初始化为零
• a 永远不会在循环之前或之内修改
• 所以 a[j] != 5总是如此 - >无限循环
• 由于无限,a[j] = 10;无法到达,因此可以优化,因此可以a并且j因为它们不再需要确定循环条件.

这与给出的文章中的情况类似:

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 Compilers Disprove Fermat的最后定理中看到,在C11之前至少有一些解释空间:

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

C11为部分6.8.5 迭代语句添加了说明,并在本答复中有更详细的介绍.

Answer 2

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

1. a在该测试之前,阵列不会更改.
2. 该数组a不包含5.

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

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

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

1. while循环之后的所有代码都是死代码(无法访问).
2. j是写的但从未读过.所以我们可以摆脱它.
3. a 永远不会读.

此时,您的代码已减少为:

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

而且我们可以制作a现在从未读过的音符,所以让我们也去除它:

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

现在,未经优化的代码:

在未经优化的生成代码中,数组将保留在内存中.而且你会在运行时完成它.5一旦你走过数组的末尾,它就有可能在它之后可读.

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

Answer 3

如果循环确实被优化到无限循环中,那可能是由于静态代码分析看到了你的数组

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 */
}