g ++优化打破了循环 [英] g++ optimization breaks for loops

问题描述

几天前，我遇到了我认为是g ++ 5.3中的一个错误，该错误涉及在更高的-OX优化级别上嵌套的for循环. (以前专门针对-O2和-O3进行体验).问题是，如果您有两个嵌套的for循环，它们具有一些内部总和以跟踪总迭代次数，则一旦该总和超过其最大值，就可以防止外部循环终止.我能够复制的最小代码集是:

A few days ago, I encountered what I believe to be a bug in g++ 5.3 concerning the nesting of for loops at higher -OX optimization levels. (Been experiencing it specifically for -O2 and -O3). The issue is that if you have two nested for loops, that have some internal sum to keep track of total iterations, once this sum exceeds its maximum value it prevents the outer loop from terminating. The smallest code set that I have been able to replicate this with is:

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编译时，它会按预期输出运行:

When this is compiled using g++ -o run.me main.cpp it runs just as expected outputting:

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

However, when this is compiled using g++ -O2 -o run.me main.cpp, the outer loop fails to terminate. (This only occurs when maxInner * maxOuter > 2^31) While sum continually overflows, it shouldn't in any way affect the other variables. I have also tested this on Ideone.com with the test case demonstrated here: https://ideone.com/5MI5Jb

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

My question is thus twofold.

1. 和值如何以某种方式影响系统?没有任何决定基于它的值，它仅用于计数器和std::cout语句的目的.
2. 在不同的优化级别上可能会导致截然不同的结果吗?

1. How is it possible for the value of sum to in some way effect the system? No decisions are based upon its value, it is merely utilized for the purposes of a counter and the std::cout statement.
2. What could possibly be causing the dramatically different outcomes at different optimization levels?

非常感谢您抽出宝贵的时间阅读并考虑我的问题.

注意:此问题与现有问题不同，例如:

Note: This question differs from existing questions such as: Why does integer overflow on x86 with GCC cause an infinite loop? because the issue with that problem was an overflow for the sentinal variable. However, both sentinal variables in this question i and j never exceed the value of 100m let alone 2^31.

推荐答案

答案

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

Answers

As @hvd pointed out, the problem is in your invalid code, not in the compiler.

在程序执行期间，sum值溢出int范围.由于默认情况下int是signed，并且signed值的溢出会导致C中的未定义行为*，因此编译器可以自由地执行任何操作.正如某人指出的那样，龙可能会从您的鼻子中飞出来.结果只是不确定的.

During your program execution, the sum value overflows int range. Since int is by default signed and overflow of signed values causes undefined behavior* in C, the compiler is free to do anything. As someone noted somewhere, dragons could be flying out of your nose. The result is just undefined.

-O2引起的差异在于测试结束条件.当编译器优化您的循环时，它意识到可以优化内部循环，从而使其得以实现

The difference -O2 causes is in testing the end condition. When the compiler optimizes your loop, it realizes that it can optimize away the inner loop, making it

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

它可能会更进一步，将其转换为

and it may go further, transforming it to

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

说实话，我真的不知道它做什么，关键是，它可以做到这一点.还是别的什么，请记住这些小龙，您的程序会导致未定义行为.

To be honest, I don't really know what it does, the point is, it can do just this. Or anything else, remember the dragons, your program causes undefined behavior.

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

Suddenly, your sum variable is used in the loop end condition. Note that for defined behavior, these optimizations are perfectly valid. If your sum was unsigned (and your maxInner and maxOuter), the (maxInner * maxOuter) value (which would also be unsigned) would be reached after maxOuter loops, because unsigned operations are defined** to overflow as expected.

现在，由于我们位于signed域，因此编译器可以随时假定sum < (maxInner * maxOuter)，只是因为后者溢出，因此未定义.因此，优化的编译器可能会以类似

Now since we're in the signed domain, the compiler is for one free to assume, that at all times sum < (maxInner * maxOuter), just because the latter overflows, and therefore is not defined. So the optimizing compiler can end up with something like

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

看起来像观察到的行为.

which looks like observed behavior.

* :根据

*: According to the C11 standard draft, section 6.5 Expressions:

如果在表达式的求值过程中发生异常情况(即，如果结果没有在数学上定义或不在其类型的可表示值范围内)，则行为不确定.

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.

** :根据

**: According to the C11 standard draft, Annex H, H.2.2:

在LIA-1的意义上，C的无符号整数类型为模"，因为溢出或越界结果会自动换行.

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版)编译了上面的代码，并得到了一些非常有趣的东西.

---

I did some research on the topic. I compiled the code above with gcc and g++ (version 5.3.0 on Manjaro) and got some pretty interesting things of it.

为了成功用gcc(即C编译器)编译它，我已替换了

To successfully compile it with gcc (C compiler, that is), I have replaced

#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，""}.这将产生以下结果:

and wrapped this replacement with #ifndef ORIG, so I could have both versions. Then I ran 8 compilations: {gcc,g++} x {-O2, ""} x {-DORIG=1,""}. This yields following results:

1. gcc，-O2，-DORIG=1:无法编译，缺少<iostream>. 不足为奇.

1. gcc, -O2, -DORIG=1: Won't compile, missing <iostream>. Not surprising.

gcc，-O2，"":产生编译器警告并表现为正常".程序集中的外观显示出内部循环已被优化(j增加了100000000)，并且外部循环变量与硬编码值-1294967296进行了比较. 因此，GCC 可以在程序正常运行时检测到此错误并做一些聪明的事情.更重要的是，发出警告以警告用户未定义的行为.

gcc, -O2, "": Produces compiler warning and behaves "normally". A look in the assembly shows that the inner loop is optimized out (j being incremented by 100000000) and the outer loop variable is compared with hardcoded value -1294967296. So, GCC can detect this and do some clever things while the program is working expectably. More importantly, warning is emitted to warn user about undefined behavior.

gcc，""，-DORIG=1:无法编译，缺少<iostream>. 不足为奇.

gcc, "", -DORIG=1: Won't compile, missing <iostream>. Not surprising.

gcc，""，"":编译时无警告.没有优化，程序将按预期运行.

gcc, "", "": Compiles without warning. No optimizations, program runs as expected.

g++，-O2，-DORIG=1:编译时无警告，以无限循环运行.这是OP的原始代码. C ++汇编对我来说很难遵循.不过还有100000000.

g++, -O2, -DORIG=1: Compiles without warning, runs in endless loop. This is OP's original code running. C++ assembly is tough to follow for me. Addition of 100000000 is there though.

g++，-O2，"":编译带有警告.更改输出的打印方式以更改编译器警告发出就足够了. 正常"运行. 通过装配，AFAIK的内部循环得到了优化.至少再次与-1294967296进行了比较，并增加了100000000.

g++, -O2, "": Compiles with warning. It is enough to change how the output is printed to change compiler warning emiting. Runs "normally". By the assembly, AFAIK the inner loop gets optimized out. At least there is again comparison against -1294967296 and incrementation by 100000000.

g++，""，-DORIG=1:编译时无警告.没有优化，正常"运行.

g++, "", -DORIG=1: Compiles without warning. No optimization, runs "normally".

g++，""，"":dtto

对我来说，最有趣的部分是找出印刷更改时的区别.实际上，从所有组合来看，OP所使用的只有一种会产生无限循环程序，而其他组合则无法编译，没有进行优化或在没有警告的情况下进行优化并保持理智.

The most interesting part for me was to find out the difference upon change of printing. Actually from all the combinations, only the one used by OP produces endless-loop program, the others fail to compile, do not optimize or optimize with warning and preserve sanity.

遵循示例构建命令和我的完整代码

Follows example build command and my full code

$ 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 ++优化打破了循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！