e-maxx's blog

By e-maxx, 13 years ago, translation, In English

During the yesterday contest we were "lucky" enough to discover a new bug in the g++ (here is the previous bug, which was discussed here some time ago).

The bug becomes apparent in complex recursive functions with -O2 option turned on.

In our case it was a segment tree, and the bug lead to wrong answer even on the sample test case (though without -O2 everything works ok). Interestingly, if we try to add debug output to our program, it started working right :) Of course, these symptoms may signify that it's our bad solution, but, to all appearance, it is not.


So, after the contest I simplified the program, and this is a minimal version of our program to show the bugs: at pastebin.

From debug-outputs we can see, that with -O2 options turned on, the auxillary() function is called twice, returning 1 and 0, but query() in result returns zero, though its result is simply a sum of all results of auxillary() calls.


However, in bugtracker another man managed to create much simpler example: at pastebin.



Link to the bug is here: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837.

By this moment the bug is confirmed, and also it is confirmed that it exhibits on (!attention!) g++ 4.3.3 - 4.6.0.

So, all versions of GCC by the last 2.5 years. Hmm....



P.S. During our trainings we meet with such strange behaviour of g++ compiler, but usually we didn't take it into account - maybe it's a wrong solution, and it's just a luck that it passed on MS VC. But it turned out that everything is not so simple, and we should take into account the factor of bad compilers.

P.P.S. There will be the same g++ compiler on the ACM ICPC finals...

  • Vote: I like it
  • +62
  • Vote: I do not like it

13 years ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

People from bugtracker say that the following compiler option fixes the problem:

-fno-optimize-sibling-calls

I think it would be fair to add this option on the codeforces (btw, the previous bug with -fno-strict-aliasing option was not specified for C++ 0x compiler).

13 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Also it turned out that we can fool the optimizer using complex enough expression, such as:

int ans = ans1 + ans2;

if (ans1 & 1)
  ans = ans2 + ans1 % 2 * ans1;

Two these expressions are not equivalent (when ans1<0), but in our program all numbers were non-negative.


Our solution with this hack gives OK in the upsolving...