在使用'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

这证实了下面答案给出的论断。

- Mohit Jain

---

解谜的一个可能解决方案是在函数体内（在注释“在此注释之前编写一些内容”之前），放置 return;，并在调用 fn 之前或之后（在注释“在此注释之后编写一些内容”之后）放置 i = 10;。这可能是预期的解决方案，但我更喜欢您的方法。 - 2012rcampion

在 void fn() 内部，printf("%d\n", 10); exit(0); 不会产生未定义行为。 - chux - Reinstate Monica

我比起我自己的代码 #define fn() i=10 更喜欢你的那个。 - Mark B

我不感兴趣的替代方案，我想知道为什么这个解决方案会出现无限循环。 - Mohit Jain

这里描述并解释了一个非常相似的事情：http://blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx - Pawel

Answer 1

这是未定义行为，因此编译器实际上可以做任何事情，在GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks中可以找到一个类似的例子，其中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编译器证明费马大定理中看到，在C11之前至少存在一些解释的余地：

许多知识渊博的人（包括我）将其视为程序的终止行为不能更改。显然，有些编译器编写者不同意，或者认为这并不重要。合理人士对解释持不同态度似乎表明C标准存在缺陷。

C11 在第 6.8.5 节 迭代语句中添加了澄清，并在此答案中详细介绍。

- Shafik Yaghmour

---

我希望标准能够为各种形式的未定义行为定义一些规范模型。许多程序可以从行为模型中受益，该模型不允许完全无约束的 UB，但允许许多有用的优化。一个相当典型的模型会说，可能存在某些地址，如果写入或读取，可能导致其他内存内容任意重写（在现实世界中，触发读取的地址并不罕见），编译器可以安排变量，使得越界数组访问会命中这样的地址。在这样的模型下... - supercat

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - supercat

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。

这就是为什么未经过优化的版本有时不会崩溃和失败的原因。

- Bill Lynch

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

- user3079266

---

或者} int main() { /* 做任何事情 */ #define main this_is_not_main - jingyu9575

你的第一个解决方案可能不会实际输出任何内容：在 while 循环之前需要一个 fflush。 - Emil Jeřábek

@EmilJeřábek：嗯，你为什么这么认为？我印象中printf在每个换行符上自动刷新... - user3079266

不，这取决于stdout当前的缓冲模式，它可以明确设置或具有实现定义的默认值。在实践中，我看到的是当stdout连接到终端时，它会以行缓冲模式启动，否则完全缓冲，但结果可能因情况而异。 - Emil Jeřábek