功能优化为无限循环'gcc

2018-06-10 09:04:09

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

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("%dn", 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 vs gcc -S -O2编译该文件并进行比较时，它清楚地显示了gcc在函数fn保持无限循环。

题
我明白，因为代码调用未定义的行为，不能称之为错误。但是编译器为什么以及如何分析行为并在O2留下无限循环？

许多人评论知道如果某些变量变为易变的行为。预期的结果是：

如果i或j更改为volatile ，程序行为保持不变。

如果数组a变得volatile ，程序不会受到无限循环。

此外，如果我应用以下补丁

-  int a[1] = {0};
+  int aa[1] = {0};
+  int *a = aa;

程序行为保持不变（无限循环）

如果我使用gcc -O2 -fdump-tree-optimized编译代码， 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

这验证了下面的答案后作出的断言。

这是未定义的行为，因此编译器可以真正做任何事情，我们可以在GCC 4.8之前的版本中找到类似的示例，其中包括断开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编译器中看到驳斥费马的最后一个定理，即在C11之前至少有一些解释的余地：

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

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

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

在测试之前，数组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可读的数据。

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

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

volatile

只包含0

永远不会被写入

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

即使它没有这样做，你的方法也很容易失败。例如，有些编译器可能会优化代码而不会使循环无限，但会将i的内容填充到寄存器中，使其无法从堆栈中获得。

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

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  printf("10n"); /* 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("10n"); /* Output 10 */
  exit(0); /* Exit gracefully */
  /* write something before this comment */
}

链接地址: http://www.djcxy.com/p/30721.html

上一篇: Function optimized to infinite loop at 'gcc

下一篇: Does the C++ volatile keyword introduce a memory fence?