I encountered an unusual runtime error during today's Div 2 round on problem D. http://codeforces.net/contest/706/problem/D
I implemented a simple trie, and received runtime error on test 1. http://codeforces.net/contest/706/submission/19803196
After some more submissions, I got to this: http://codeforces.net/contest/706/submission/19805829
With a couple of custom invocations, I narrowed the problem down to function mx. Implementing it a bit differently, I got AC. http://codeforces.net/contest/706/submission/19808959
After the contest, I tried submiting my code to several other sites: SPOJ, UVa, ideone. I also ran the code locally both on Windows and Linux. Out of all of these, CodeForces was the only platform on which the program crashed.
Is there a bug in the compiler, or am I missing something?
GCC-4.6.4, GCC-5.3.0 and GCC-6.1.0 on my x86_64-linux-gnu all works well.
I used
#pragma GCC optimize
to control GCC optimize options and tried some combinations on Codeforces custom invocations. The result is "interesting":-O2
and-O1 -fipa-sra -fipa-cp
leads to RE, but-O1
does not.I think this should be a GCC-5.1 regression. I'll checkout GCC-5.1 source code.
It's wired. GCC-5.1.0 also works well on my machine. I really don't know what happened on Codeforces...
Codeforces uses MinGW, not original GCC. So it has many problems.
Yes you are right. even GCC-6.1.0 is still generating wrong code for target i686-w64-mingw32.
I was able to reduce it this far:
Great, do you know in which depth it crashes? And, if I'm not mistaken, if (v->l == v->r) should always evaluate to true, right?
Looks like an optimization bug, because it crashes, when it returns:
return mx(pref[1], poz-1, x)
and pointer p is optimized. So maybe return addr is broken, but I'm not sure.Running the reduced version by KarlisS through gdb indeed shows very funky stuff happening with the return address:
Edit: I'm using mingw-w64 locally, this was on g++ 4.9.2, i686-posix-dwarf. I downloaded g++ 6.1.0, x86_64-posix-seh and it didn't crash.
My GCC-6.1.0 is still generating wrong assembly code for target i686-w64-mingw32.
Now I only know GCC seems using a strange calling convention for
trie::mx
, and violated this convention during optimize. If we force a "standard" convention using__attribute__((cdecl))
(stdcall, thiscall, and fastcall also work), GCC will generate right code.This BUG is already fixed in GCC-7.0 (SVN 20160813). GCC-7.0 is seperating
trie::mx
to two functions, in order to optimize the code without violation of calling convention.