[Bug c/99623] New: Code behaves differently at -O2 optimization

[Bug c/99623] New: Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

            Bug ID: 99623
           Summary: Code behaves differently at -O2 optimization
           Product: gcc
           Version: 10.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sebastiano.vigna at unimi dot it
  Target Milestone: ---

Created attachment 50406
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50406&action=edit
Output of --save-temps

The included code compares two variants of Ben Pfaff's GNU LibAVL library. One
implementation is the original one, and it stores pointers to uint64_t values,
comparing them with a user-supplied function. The second implementation is a
mild variation storing the uint64_t values directly into the map, and comparing
them directly using the language operators. The two implementations should be
equivalent--the code builds the same RB tree with the same values and compares
the results after each insertion.

The two trees are identical:

- with clang, any level optimization, Mac OS X, Linux
- with gcc 10.2.1, no optimization or -O1, Mac OS X, Linux

The two trees diverge after 5 insertions:

- with gcc 10.2.1, -O2, Mac OS X, Linux

We have tried all possible diagnostics, including the sanitizer, but any
perturbation to the code makes the two trees identical. The problem seems to
lie in myprob_probe()--even adding a printf(""); anywhere between lines 207-231
makes the test work.

Note that this test is reported using a compare() function for trees that might
be bugged, but the original bug was that when deleting the tree the library
would give a segmentation fault. We tracked down the problem to a divergence in
the construction of the tree.

To replicate the bug, try

gcc -O1 bug.c
./a.out
gcc -O2 bug.c
./a.out

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #1 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Created attachment 50407
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50407&action=edit
Output of gcc with -O2

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #2 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Created attachment 50408
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50408&action=edit
Source

[Bug c/99623] Code behaves differently at -O2 optimization

[zeccav at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

Vittorio Zecca <zeccav at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zeccav at gmail dot com

--- Comment #3 from Vittorio Zecca <zeccav at gmail dot com> ---
Where is prb.h ?

[Bug c/99623] Code behaves differently at -O2 optimization

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Goes away with -fno-strict-aliasing and -Wstrict-aliasing=2 warns about it:
bug.c: In function ‘prb_probe’:
bug.c:105:42: warning: dereferencing type-punned pointer might break
strict-aliasing rules [-Wstrict-aliasing]
bug.c:139:42: warning: dereferencing type-punned pointer might break
strict-aliasing rules [-Wstrict-aliasing]
bug.c: In function ‘myprb_probe’:
bug.c:251:44: warning: dereferencing type-punned pointer might break
strict-aliasing rules [-Wstrict-aliasing]
bug.c:285:44: warning: dereferencing type-punned pointer might break
strict-aliasing rules [-Wstrict-aliasing]
bug.c: In function ‘compare’:
bug.c:375:9: warning: format ‘%d’ expects argument of type ‘int’, but argument
2 has type ‘size_t’ {aka ‘long unsigned int’} [-Wformat=]
bug.c:375:9: warning: format ‘%d’ expects argument of type ‘int’, but argument
3 has type ‘size_t’ {aka ‘long unsigned int’} [-Wformat=]
I bet the program is invalid, just don't have time to prove it now.

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #5 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Created attachment 50409
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50409&action=edit
Source

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #6 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Created attachment 50410
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50410&action=edit
Source

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

Sebastiano Vigna <sebastiano.vigna at unimi dot it> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #7 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Thank you for the prompt answer.

It is all very weird, and certainly unexpected, but this could be a problem
with GNU libavl.

The four assignments marked by -Wstrict-aliasing=2 are completely wrong: there
is an additional & that shouldn't be there. Since this is a GNU library with
two decades of development behind, we did not check in particular the code we
did not change.

If we remove the &, the warnings go away and the problem disappears.

Adding some assertions we established that the nonsensical assignment are,
simply, never executed. This is why, in spite of being nonsensical, they do not
cause any harm. But their very existence, even if they are not executed,
appears to trigger the problem we faced with -O2.

I guess that once you have undefined statements all bets are off, so this is
not a gcc bug. We will report the problem to the libavl authors.

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #8 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
I'm sorry, I did the test on the wrong file. No, you cannot eliminate the &,
even if the type is correct, and h can be NULL at that point. I'll ask the
libavl maintainers their opinion. We can compile with that option but other
people might incur in the same problem.

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #9 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Finally solved: the problematic statement

if (h == NULL) h = (struct prb_node *)&tree->prb_root;

should just be

if (h == NULL) h = tree->prb_root->prb_link[0];

The position in memory of the two pointers is the same, but the second access
has the right type. I guess the GNU libavl author wanted to save an
indirection, but did not realize the possible dangers.

For the user, this behavior of the optimizer remains very confusing tho.

[Bug c/99623] Code behaves differently at -O2 optimization

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99623

--- Comment #10 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Ahem no, my correction goes in the opposite direction it should go. I'll ask
suggestions to the library authors.

I really apologize for all the noise.