g++ 优化中断循环

Question

几天前，我遇到了我认为是 g++ 5.3 中的错误，涉及在更高 -OX 优化级别嵌套 for 循环。（专门为 -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

因此，我的问题是双重的。

sum 的值怎么可能以某种方式影响系统？没有任何决定基于它的价值，它仅用于计数器和 std::cout 语句的目的。
什么可能导致不同优化级别的结果截然不同？

提前非常感谢您花时间阅读和考虑我的问题。

注意：此问题不同于现有问题，例如：Why does integer overflow on x86 with GCC cause an infinite loop?，因为该问题的问题是哨兵变量溢出。然而，这个问题中的两个哨兵变量 i 和 j 都没有超过 100m 的值，更不用说 2^31.

Answer 1

您的代码调用了未定义的行为，因为 int 和溢出。你说 "this shouldn't in any way affect the other variables"。错误的。一旦你有未定义的行为，所有的可能性都会消失。任何事情都可能发生。

gcc 以假设没有未定义行为的优化而闻名，如果未定义行为发生，让我们说一些有趣的事情。

解决方案：不要这样做。

Answer 2

这是对正确代码完全有效的优化。您的代码不正确。

GCC 看到的是，如果您在计算 sum 的早期循环迭代期间有符号整数溢出，则可以达到循环退出条件 i >= maxOuter 的唯一方法。编译器假定不存在有符号整数溢出，因为标准 C 中不允许有符号整数溢出。因此，i < maxOuter 可以优化为 true.

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

Answer 3

答案

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

在您的程序执行期间，sum 值溢出 int 运行ge。由于 int 默认情况下是 signed 并且 signed 值的溢出会导致 C 中的未定义行为*，编译器可以自由地做任何事情。正如有人在某处指出的那样，龙可能会从你的鼻子里飞出来。结果只是未定义。

差异 -O2 原因在于测试结束条件。当编译器优化你的循环时，它意识到它可以优化内部循环，使其成为

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

它可能会更进一步，t运行将它变成

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

说实话，我真的不知道它有什么作用，关键是，它可以做这个。或者其他什么，记住龙，你的程序导致 undefined 行为。

突然，你的sum变量被用于循环结束条件。请注意，对于定义的行为，这些优化是完全有效的。如果您的 sum 是 unsigned（以及您的 maxInner 和 maxOuter），则将达到 (maxInner * maxOuter) 值（也将是 unsigned）在 maxOuter 循环之后，因为 unsigned 操作定义为预期的溢出。

现在因为我们在 signed 域中，编译器可以自由假设，在任何时候 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 standard draft，第 6.5 节表达式：

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined.

**: 根据C11 standard draft, Annex H, H.2.2:

C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense in that overflows or out-of-bounds results silently wrap.

我对这个话题做了一些研究。我用 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,"" }.这会产生以下结果：

结果

gcc、-O2、-DORIG=1：无法编译，缺少 <iostream>。 不足为奇.
gcc、-O2、""：产生编译器警告并执行 "normally"。查看程序集显示内部循环已优化（j 递增 100000000）并且外部循环变量与硬编码值 -1294967296 进行比较。 因此，GCC 可以检测到这一点并在程序按预期运行时做一些聪明的事情。更重要的是，发出警告以警告用户未定义的行为。
gcc、""、-DORIG=1：无法编译，缺少 <iostream>。 不足为奇。
gcc、""、""：编译时没有警告。没有优化，程序按预期运行。
g++、-O2、-DORIG=1：无警告编译，无限循环运行。这是OP的原始代码运行。 C++ 汇编对我来说很难理解。不过还有100000000的加法。
g++、-O2、""：编译 时带有 警告。改变输出的打印方式足以改变编译器警告的发出。运行 "normally"。 通过组装，AFAIK 内部循环得到了优化。至少再次与 -1294967296 进行比较并增加 100000000.
g++、""、-DORIG=1：编译时没有警告。没有优化，运行 "normally".
g++, "", "": dtto

对我来说最有趣的部分是找出印刷变化时的差异。其实从所有的组合来看，只有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
    }
}

g++ 优化中断循环

g++ optimization breaks for loops

c++

optimization

for-loop

nested-loops

答案

描述

结果

代码