在 '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 -O2 标志编译它或尝试 ideone 时，它在函数 fn.

中无限循环

我的观察
当我用 gcc -S 和 gcc -S -O2 编译文件并进行比较时，它清楚地表明 gcc 在函数 fn.

中保持无限循环

问题
我理解因为代码调用了未定义的行为，所以不能称之为错误。但是编译器为什么以及如何分析行为并在 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 pre-4.8 Breaks Broken SPEC 2006 Benchmarks 中找到一个类似的示例，其中 gcc 采用具有未定义行为的循环并将其优化为：

L2:
    jmp .L2

文章说（强调我的）：

Of course this is an infinite loop. Since SATD() unconditionally executes undefined behavior (it’s a type 3 function), any translation (or none at all) is perfectly acceptable behavior for a correct C compiler. The undefined behavior is accessing d[16] just before exiting the loop. In C99 it is legal to create a pointer to an element one position past the end of the array, but that pointer must not be dereferenced. Similarly, the array cell one element past the end of the array must not be accessed.

如果我们用 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])

像这样：

upon seeing d[++k], is permitted to assume that the incremented value of k is within the array bounds, since otherwise undefined behavior occurs. For the code here, GCC can infer that k is in the range 0..15. A bit later, when GCC sees k<16, it says to itself: “Aha– that expression is always true, so we have an infinite loop.”

或许还有一个有趣的次要问题，即无限循环是否被视为可观察行为（w.r.t。假设规则），这会影响是否无限循环也可以被优化掉。我们从C Compilers Disprove Fermat’s Last Theorem可以看出，在C11之前至少还有一些解释的余地：

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.

C11 向 6.8.5 迭代语句 部分添加了说明，并在 this answer 中进行了更详细的介绍。

Answer 2

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

数组 a 在该测试之前没有改变。
数组 a 不包含 5。

因此，我们可以将代码重写为：

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

现在，我们可以做出进一步的决定：

while循环之后的所有代码都是死代码（无法访问）。
j 已写入但从未读取。所以我们可以摆脱它。
a 从未被阅读。

此时，您的代码已缩减为：

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

我们可以注意到 a 现在从未被阅读过，所以我们也把它去掉：

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

现在，未优化的代码：

在未优化的生成代码中，数组将保留在内存中。你会在运行时真正地走它。一旦你走过数组的末尾，它后面可能会有一个可读的 5。

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

Answer 3

如果循环被优化为无限循环，可能是由于静态代码分析发现您的数组是

不是volatile
仅包含 0
永远不会写入

因此它不可能包含数字 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 */
}

在 'gcc -O2' 优化为无限循环的函数

Function optimized to infinite loop at 'gcc -O2'

c

optimization

gcc

undefined-behavior

现在，未优化的代码：