g++优化破坏for循环

Question

几天前，我遇到了一些我认为是g++ 5.3中关于嵌套for循环在更高的-OX优化级别下的错误。(具体表现在-O2和-O3上)。问题是如果你有两个嵌套的for循环，其中有一些内部总和来跟踪总迭代次数，一旦这个总和超过其最大值，它会防止外层循环终止。我能复制出最小的代码集是：

int main(){
    int sum = 0;
    //                 Value of 100 million. (2047483648 less than int32 max.)
    int maxInner = 100000000;

    int maxOuter = 30;

    // 100million * 30 = 3 billion. (Larger than int32 max)

    for(int i = 0; i < maxOuter; ++i)
    {
        for(int j = 0; j < maxInner; ++j)
        {
            ++sum;
        }
        std::cout<<"i = "<<i<<" sum = "<<sum<<std::endl;
    }
}

使用 g++ -o run.me main.cpp 进行编译后，输出与预期一致：

i = 0 sum = 100000000
i = 1 sum = 200000000
i = 2 sum = 300000000
i = 3 sum = 400000000
i = 4 sum = 500000000
i = 5 sum = 600000000
i = 6 sum = 700000000
i = 7 sum = 800000000
i = 8 sum = 900000000
i = 9 sum = 1000000000
i = 10 sum = 1100000000
i = 11 sum = 1200000000
i = 12 sum = 1300000000
i = 13 sum = 1400000000
i = 14 sum = 1500000000
i = 15 sum = 1600000000
i = 16 sum = 1700000000
i = 17 sum = 1800000000
i = 18 sum = 1900000000
i = 19 sum = 2000000000
i = 20 sum = 2100000000
i = 21 sum = -2094967296
i = 22 sum = -1994967296
i = 23 sum = -1894967296
i = 24 sum = -1794967296
i = 25 sum = -1694967296
i = 26 sum = -1594967296
i = 27 sum = -1494967296
i = 28 sum = -1394967296
i = 29 sum = -1294967296

然而，当使用 g++ -O2 -o run.me main.cpp 编译时，外部循环无法终止。（只有当 maxInner * maxOuter > 2^31 时才会出现这种情况）尽管 sum 不断溢出，但它不应以任何方式影响其他变量。我还在 Ideone.com 上使用了这个测试示例进行了测试：https://ideone.com/5MI5Jb 我的问题有两个：

1. 如何可能使 sum 值以某种方式影响系统? 没有根据其值做出任何决策，它仅仅被用作一个计数器和 std::cout 语句。
2. 什么可能导致在不同优化级别下产生截然不同的结果？

非常感谢您花时间阅读并考虑我的问题。 注意：此问题与现有问题不同，例如：为什么在 x86 上使用 GCC 的整数溢出会导致无限循环？，因为该问题的问题是标志变量溢出。但是，在这个问题中，两个标志变量 i 和 j 都不超过100m，更不用说 2^31 了。

- Lilith Daemon

---

当你写出未定义行为时，你的程序可以做任何事情。人们通过启用优化功能经常发现“编译器错误”。到目前为止，我还没有看到过他们的代码没有问题的情况。 - BoBTFish

有符号整数溢出将触发未定义行为。你很幸运只是遇到了一个无限循环 - 现在你的鼻子里可能会冒出龙。 - Frédéric Hamidi

无法“约束”未定义行为。即使随着时间的推移 - 如果您在代码中某个时刻执行了一些非法操作，则在接近该操作之前发生的所有事情都是未定义的。 - BoBTFish

@Chris，这就是为什么它被称为“未定义行为”。对于优化器来说，我们人类认为合理的事情并不重要，因为它是一个相当复杂的东西。 - Frédéric Hamidi

可能是为什么在x86上使用GCC的整数溢出会导致无限循环？的重复问题。 - phuclv

Answer 1

这是一种对于正确代码完全有效的优化。你的代码不正确。

GCC 看到的是，唯一可能达到循环退出条件 i >= maxOuter 的方式是在计算 sum 的早期循环迭代中发生了有符号整数溢出。编译器假设没有有符号整数溢出，因为标准 C 不允许有符号整数溢出。因此，i < maxOuter 可以被优化为只是 true。

这由 -faggressive-loop-optimizations 标志控制。您可以通过将 -fno-aggressive-loop-optimizations 添加到命令行参数中来获得您期望的行为。但更好的方法是确保您的代码有效。使用无符号整数类型可以获得保证有效的环绕行为。

- user743382

Answer 2

您的代码引发了未定义行为，因为int类型的sum溢出了。您说“这不应该以任何方式影响其他变量”。错了。一旦出现未定义行为，所有情况都没有保障，任何事情都可能发生。

gcc以其优化而闻名（或臭名），假设不存在未定义行为，并且在发生未定义行为时进行某些有趣的操作。

解决方案：不要这样做。

- gnasher729

Answer 3

答案

正如@hvd所指出的，问题在于您的代码无效，而不是编译器的问题。

在程序执行期间，sum值超出了 int 范围。由于int默认为signed，因此C中signed值的溢出会导致未定义行为*，编译器可以任意处理。如某人在某处指出的那样，龙可能从您的鼻子里飞出来。结果只是未定义的。

-O2的区别在于测试结束条件。当编译器优化循环时，它意识到可以优化掉内部循环，使其变得更快。

int sum = 0;
for(int i = 0; i < maxOuter; i++) {
    sum += maxInner;
    std::cout<<"i = "<<i<<" sum = "<<sum<<std::endl;
}

并且它可能会进一步转化为，将其转换为

int i = 0;
for(int sum = 0; sum < (maxInner * maxOuter); sum += maxInner) {
    i++;
    std::cout<<"i = "<<i<<" sum = "<<sum<<std::endl;
}

坦白说，我不是很清楚它的功能，重点是它可以做到这一点。或者其他任何事情，记住龙，你的程序会导致未定义的行为。

突然间，在循环结束条件中使用了您的“sum”变量。请注意，对于定义良好的行为，这些优化是完全有效的。如果您的“sum”是“unsigned”（以及您的“maxInner”和“maxOuter”），则在“maxOuter”循环后将达到“（maxInner * maxOuter）”值（这也将是“unsigned”）。无符号操作被定义为按预期溢出。

现在，由于我们处于有符号域中，编译器可以自由地假设始终满足“sum < (maxInner * maxOuter)” ，仅仅因为后者溢出并且因此未定义。因此，优化编译器最终可能会得到以下结果：

int i = 0;
for(int sum = 0;/* nothing here evaluates to true */; sum += maxInner) {
    i++;
    std::cout<<"i = "<<i<<" sum = "<<sum<<std::endl;
}

这似乎是观察到的行为。

*: 根据C11标准草案第6.5节表达式:

如果在表达式求值期间发生异常情况（即，如果结果在其类型的可表示值范围内数学上未定义或不在范围内），则行为未定义。

**: 根据C11标准草案附录H，H.2.2：

C的无符号整数类型按LIA−1的意义进行“模运算”，即溢出或超出边界的结果会自动回绕。

---

我对这个主题进行了一些研究。我使用gcc和g++（在Manjaro上的版本为5.3.0）编译了上面的代码，并得到了一些有趣的结果。

描述

为了成功地使用gcc（即C编译器）编译它，我已经替换了

#include <iostream>
...
std::cout<<"i = "<<i<<" sum = "<<sum<<std::endl;

使用

#include <stdio.h>
...
printf("i = %d sum = %d\n", i, sum);

我用#ifndef ORIG包裹了这个替换，这样我就可以拥有两个版本。然后我运行了8个编译：{gcc, g++} x {-O2, ""} x {-DORIG=1, ""}。这产生了以下结果：

结果

1. gcc，-O2，-DORIG=1：无法编译，缺少<iostream>。 不意外。

2. gcc，-O2，""：产生编译器警告并表现“正常”。查看汇编代码可知内部循环已被优化掉（j增加100000000），而外部循环变量与硬编码的值-1294967296进行比较。所以，GCC可以检测到这一点，在程序正常工作时做出一些聪明的事情。更重要的是，发出警告以警告用户关于未定义行为。

3. gcc，""，-DORIG=1：无法编译，缺少<iostream>。 不意外。

4. gcc，""，""：编译时没有警告。没有优化，程序按预期运行。

5. g++，-O2，-DORIG=1：编译时没有警告，进入无限循环。这是OP的原始代码运行。C++汇编对我来说很难跟踪。不过增加了100000000。

6. g++，-O2，""：编译带有警告。只需更改输出方式即可更改编译器警告发出方式。运行“正常”。根据汇编代码，我认为内部循环被优化掉了。至少还有与-1294967296进行比较和增量100000000。

7. g++，""，-DORIG=1：编译时没有警告。没有优化，运行“正常”。

8. g++，""，""：同上

对我来说最有趣的部分是发现更改打印方式的差异。实际上，从所有组合中，只有OP使用的那个产生无限循环程序，其他组合均无法编译、不优化或优化警告并保持正常。

代码

以下是示例构建命令和完整代码：

$ gcc -x c -Wall -Wextra -O2 -DORIG=1 -o gcc_opt_orig  main.cpp

main.cpp:

#ifdef ORIG
#include <iostream>
#else
#include <stdio.h>
#endif

int main(){
    int sum = 0;
    //                 Value of 100 million. (2047483648 less than int32 max.)
    int maxInner = 100000000;

    int maxOuter = 30;

    // 100million * 30 = 3 billion. (Larger than int32 max)

    for(int i = 0; i < maxOuter; ++i)
    {
        for(int j = 0; j < maxInner; ++j)
        {
            ++sum;
        }
#ifdef ORIG
        std::cout<<"i = "<<i<<" sum = "<<sum<<std::endl;
#else
        printf("i = %d sum = %d\n", i, sum);
#endif
    }
}

- Honza Remeš

---

这可能是有趣的评论，但它没有回答OP提出的两个明确问题，也没有尝试回答。鉴于OP仍然以某种原因决定接受您的帖子作为正确答案，它不太可能发生任何事情，但只是提醒一下，通常这样的帖子会被删除。将您的测试作为额外评论放在也回答了问题的帖子中是完全适当的。 - user743382

有趣的一点：使用'\n'替代std::endl，g++仍然会警告关于未定义行为。请注意，std::endl即使流是完全缓冲的而不是行缓冲的，也会强制刷新，所以在循环中使用endl会发生更多的事情。虽然我不知道为什么代码变得如此复杂。甚至还调用了一个虚函数（call rax），还有一些关于std::ctype<char>::do_widen(char)的废话。 - Peter Cordes

将循环优化为 += 100000000 不被称为循环展开。我不确定它的技术术语是什么，但是循环展开有一个具体的含义，而这不是它。关于如何使这个答案更好：将gcc的警告复制到新的第一段，并说它来自有符号溢出。这会导致gcc对循环的预期做出意外的假设。如果您不想深入探讨这个问题，也可以说“请参见其他答案”，因为其他人已经很好地涵盖了这个问题。 - Peter Cordes

@hvd和Peter Cordes：感谢你们的评论和建议。我已经修改了答案，使其更好。 - Honza Remeš

好的编辑，第一部分很好地解释了问题。有趣的分析可能会将循环转换为什么，其中sum作为循环终止条件的一部分。产生这种效果的编译器转换可能并不是为了产生这种效果而设计的。这只是它们在其他情况下工作以产生有用的优化的副作用。至少，我希望它们在某些情况下产生有用的效果！ - Peter Cordes