功能优化，在无限循环“的gcc -O2” [英] Function optimized to infinite loop at 'gcc -O2'

问题描述

上下文

我被我的一个朋友提出以下谜：

Context
I was asked the following puzzle by one of my friends:

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

我知道可以有多种解决方案，涉及的一些宏观和一些假设一些有关的执行和违反℃。

I know there can be multiple solutions, some involving macro and some assuming something about the implementation and violating C.

一个特别的解决方案，我感兴趣的是使有关堆栈的某些假设和写入以下code：（我的理解是不确定的行为，但可能工作为预期的许多实现）

One particular solution I was interested in is to make certain assumptions about stack and write following code: (I understand it is undefined behavior, but may work as expected on many implementations)

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 。

Problem
This program worked fine in MSVC and gcc without optimization. But when I compiled it with gcc -O2 flag or tried on ideone, it loops infinitely in function fn.

我的观察

当我编译文件， GCC -S VS GCC -S -O2 相比，它清楚地表明 GCC 保持一个无限循环的功能 FN 。

My Observation
When I compiled the file with gcc -S vs gcc -S -O2 and compared, it clearly shows gcc kept an infinite loop in function fn.

问

我理解，因为在code调用未定义行为，不能称之为一个bug。但是，为什么和如何编译分析其行为，并保留为 O2 ？

许多人评论知道行为，如果某些变量被改变为不稳定。如预期的结果是：

Many people commented to know the behavior if some of the variables are changed to volatile. The result as expected is:

• 如果 I 或Ĵ更改为挥发性 ，程序行为保持不变。


• 如果数组 A 是由挥发性，程序不吃亏无限循环。


• 此外，如果我使用下面的补丁

• If i or j is changed to volatile, program behavior remains same.
• If array a is made volatile, program does not suffer infinite loop.
• Moreover if I apply the following patch

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

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

The program behavior remains same (infinite loop)

如果我编译的code的gcc -O2 -fdump树优化，我得到以下中间文件：

If I compile the code with gcc -O2 -fdump-tree-optimized, I get the following intermediate file:

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

此验证下面的答案后做出的声明。

This verifies the assertions made after the answers below.

推荐答案

这是不确定的行为，因此编译器真的可以做任何事情，我们可以找到的 GCC pre-4.8休息残破的SPEC基准2006年，其中 GCC 需要与未定义行为的循环，它以优化

This is undefined behavior so the compiler can really do anything at all, we can find a similar example in GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks, where gcc takes a loop with undefined behavior and optimizes it to:

L2:
    jmp .L2

文章说（的重点煤矿的）：

当然，这是一个无限循环。由于SATD（）无条件地
  执行未定义行为（这是一个3型功能），任何
  翻译（或没有）是一个完全可以接受的行为
  正确的C编译器即可。未定义行为正在访问D [16]刚
  之前退出循环。在C99的是合法的创建一个指针
  一个元件的一个位置过去的数组的末尾，但该指针
  不得解除引用。类似地，阵列单元的一个元素过去
  数组的末端必须不能被访问。

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程序我们看到：

which if we examine your program with godbolt we see:

fn:
.L2:
    jmp .L2

的逻辑正在使用的优化可能是这样的：

The logic being used by the optimizer probably goes something like this:

• 所有的元素 A 初始化为零


• A 前或内环路，从不修改


• 所以 A [J] = 5 始终是真实的！ - >无限循环


• 因为无限的，在 A [J] = 10; 无法访问，这样就可以优化掉，这样可以 A 和Ĵ，因为他们不再需要来确定循环状态。

• All the elements of a are initialized to zero
• a is never modified before or within the loop
• So a[j] != 5 is always true -> infinite loop
• Because of the infinite, the a[j] = 10; is unreachable and so that can be optimized away, so can a and j since they are no longer needed to determine the loop condition.

int d[16];

分析以下循环：

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

是这样的：

在看见D [++ k]的，被允许假定递增值
  k的是阵列范围之内，否则未定义的行为
  发生。对于code在这里，GCC​​可以推断，k是范围0..15。
  过了一会儿，GCC时看到K＆LT; 16，就对自己说：这AHA-
  前pression始终是真实的，所以我们有一个无限循环。

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。到AS-if规则的）或没有，这是否影响一个无限循环，也可以优化掉。我们可以从 C编译器反驳费尔马大定理的C11之前有至少有一些余地间pretation看到：

Perhaps an interesting secondary point, is whether an infinite loop is considered observable behavior(w.r.t. to the as-if rule) or not, which effects whether an infinite loop can also be optimized away. We can see from C Compilers Disprove Fermat’s Last Theorem that before C11 there was at least some room for interpretation:

许多知识渊博的人（包括我）阅读的话说，
  程序的终止行为不能被改变。显然，一些
  编译器作者不同意，否则不认为它很重要。该
  事实是合理的人持反对意见的跨pretation似乎
  以表明C标准是有缺陷的。

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 的迭代语句和覆盖更详细的的这个答案。

C11 adds clarification to section 6.8.5 Iteration statements and is covered in more detail in this answer.

这篇关于功能优化，在无限循环“的gcc -O2”的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！