[GCC 4.3] Strange -O2 optimization issue

[GCC 4.3] Strange -O2 optimization issue

[Mateusz Loskot]

Hello,

I'm experiencing a strange problem while building a small program
using GCC 4.3.1 (Debian, Lenny) with -O2 optimization.
The program is a simple hash generator from 2D point,
using high and low word of a coordinate (object of double type).
I include a small test program [1]

Here are 3 test cases that differ in optimization flag only

$ g++ -W -Wall -o bar bar.cpp
$ ./bar
1073741824
1073741824
1073741824
1073741824
1073741824

$ g++ -O1 -W -Wall -o bar bar.cpp
$ ./bar
1073741824
1073741824
1073741824
1073741824
1073741824

$ g++ -O2 -W -Wall -o bar bar.cpp
$ ./bar
136623933
1073741824
1073741824
1073741824
1073741824


Why the first value printed is different (136623933) in the 3rd
test case.

Also, could anyone enlighten me and explain what kind of optimization is 
applied when -O2 flag is used, so the first value printed is different?

I'd be also very thankful for references in C/C++ standards
explaining this behavior of GCC.

I've noticed, that if I uncomment the printf in HashDouble function,
third test case (-O2 optimization) returns all the same values.

Perhaps my test program is buggy, for example I suspect the cast in 
HashDouble function. Is it?

I run my tests cases using GCC 4.0.1 and the problem
does not leak there.

Thanks in advance for your help!



[1] Test program

// bar.cpp ////////////////////////////////////////////////
#include <cstdio>

struct Point
{
public:
     double x;
     double y;
     double getX() const { return x;}
     double getY() const { return y;}
};
static unsigned long HashDouble(double* pdfVal)
{
     unsigned int* pnValue = (unsigned int*)pdfVal;

     // printf("%p\n", pnValue); // Seems to fix the problem

     return pnValue[0] ^ pnValue[1];
}
static unsigned long HashPoint(const Point* point)
{
     double x = point->getX();
     double y = point->getY();
     return HashDouble(&x) ^ HashDouble(&y);
}
int main()
{
     Point* po = new Point();
     po->x = 1;
     po->y = 2;

     for (int i = 0; i < 5; ++i)
     {
         std::printf("%lu\n", HashPoint(po));
     }
     delete po;
     return 0;
}
///////////////////////////////////////////////////////////

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org

Re: [GCC 4.3] Strange -O2 optimization issue

[Brian Dessent]

Mateusz Loskot wrote:

> Why the first value printed is different (136623933) in the 3rd
> test case.

Your suspicion is correct, as this violates the ISO C aliasing rules:

> static unsigned long HashDouble(double* pdfVal)
> {
>      unsigned int* pnValue = (unsigned int*)pdfVal;

You're accessing a variable of type double through a pointer of type
unsigned int.  For the purposes of optimization the compiler is allowed
to assume that values of type double will only be accessed through
variables of type double, and thus it can assume that pdfVal and pnValue
can't refer to the same thing.  It may seem nonsensical in this instance
that it would assume that, but it's still legal for the compiler to do
so.  And being able to make this assumption allows for interesting
optimizations, for example consider something like:

typedef struct { int size; float *data; } foo;

void bar (foo *src, foo *dest)
{
  for (int i = 0; i < src->size; i++)
    dest->data[i] += src->data[i];
}

In this example all the stuff happening in the loop with the data arrays
involves floats so the compiler can prove to itself that src->size (an
integer) cannot change, and thus it can hoist it out of the loop so that
it only need be computed once.  This comes up in code that uses STL
containers for example.  (This example was brought up in the following
thread which has more to say on the topic:
<http://gcc.gnu.org/ml/gcc/2006-11/threads.html#00877>.)

If you want to rewrite your code in a conformant way you can use a union
or memcpy; or you can disable strict aliasing with
-fno-strict-aliasing.  -Wstrict-aliasing is intended to warn about
things like this, but since it's included in -Wall it obviously failed
to warn in your case.  There are several levels of -Wstrict-aliasing
though, so you may need to turn to -Wstrict-aliasing=2 to catch this
case.  See the docs for details:
<http://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wstrict_002daliasing-312>

As to why only the first value printed differs, or why taking the
address of pnValue changes the outcome, or why older versions of gcc
worked fine: that is the general nature of undefined behavior.  It can
take on any form whatsoever, from working perfectly, to failing
spectacularly, or anywhere in between.  All rules are out the window. 
It is best not to try to understand the effects or outcome but rather to
understand how to fix the code so that it is no longer undefined.

> Also, could anyone enlighten me and explain what kind of optimization is
> applied when -O2 flag is used, so the first value printed is different?

To quote the manual:
<http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#index-fstrict_002daliasing-698>

    The -fstrict-aliasing option is enabled at levels -O2, -O3, -Os. 

> I'd be also very thankful for references in C/C++ standards
> explaining this behavior of GCC.

See section 6.5.7 of the C99 standard.

Brian

Re: [GCC 4.3] Strange -O2 optimization issue

[Mateusz Loskot]

Brian Dessent wrote:
> Mateusz Loskot wrote:
> 
>> Why the first value printed is different (136623933) in the 3rd
>> test case.
> 
> Your suspicion is correct, as this violates the ISO C aliasing rules:

Brian,

Good to hear I was close ;-)

>> static unsigned long HashDouble(double* pdfVal)
>> {
>>      unsigned int* pnValue = (unsigned int*)pdfVal;
> 
> You're accessing a variable of type double through a pointer of type
> unsigned int.  For the purposes of optimization the compiler is allowed
> to assume that values of type double will only be accessed through
> variables of type double, and thus it can assume that pdfVal and pnValue
> can't refer to the same thing.  It may seem nonsensical in this instance
> that it would assume that, but it's still legal for the compiler to do
> so.  
 > [...]

Thank you very much for in-depth explanation of the problem.
It was greatly helpful.

> If you want to rewrite your code in a conformant way you can use a union
> or memcpy; or you can disable strict aliasing with
> -fno-strict-aliasing.

I fixed my code with memcpy option.

> -Wstrict-aliasing is intended to warn about
> things like this, but since it's included in -Wall it obviously failed
> to warn in your case.  There are several levels of -Wstrict-aliasing
> though, so you may need to turn to -Wstrict-aliasing=2 to catch this
> case.  See the docs for details:
> <http://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wstrict_002daliasing-312>

-Wstrict-aliasing=2 does not warn about aliasing rules broken in that 
line with the case, but -Wstrict-aliasing=1 does. Yes, I've read the 
manual and understand it why.

> As to why only the first value printed differs, or why taking the
> address of pnValue changes the outcome, or why older versions of gcc
> worked fine: that is the general nature of undefined behavior.  It can
> take on any form whatsoever, from working perfectly, to failing
> spectacularly, or anywhere in between.  All rules are out the window. 

Right, I suspected UB from the beginning of my investigation.

> It is best not to try to understand the effects or outcome but rather to
> understand how to fix the code so that it is no longer undefined.

Very good point :-)

>> I'd be also very thankful for references in C/C++ standards
>> explaining this behavior of GCC.
> 
> See section 6.5.7 of the C99 standard.
> 
> Brian


Thank you very much again!

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org