It's a minimized code based on my segment tree solution for 877E - Danil and a Part-time Job. I got RE during the contest and cannot figured out why. Can anyone reproduce the bug and paste the generated assembly? I cannot reproduce the crash on my Mac/Linux machine...QQ
I added some words in this code and it passed...
I have tried to remove the unnamed namespace, and it passed as well...orz
Good job reducing the test case.
It probably doesn't happen without unnamed namespace because it marks the functions as internal linkage — not callable externally from other cpp files. That gives optimizer much more freedom. It might be possible to repeat without unnamed namespace by making my_main static and ask static non member function. Custom invocations currently don't work so I can't investigate it further.
I have one idea for getting compiled code from Codeforces. I hope it doesn't make the bug disappear. Unfortunately I can't try it out as custom invocations don't work.
It'd nice if there was a way to setup programming environment in exactly the same way as CF. I've tried compiling with mingw-w64 g++6.2 and it works fine. But maybe CF uses another mingw package or something like that.
Assembly seems to be different with and without anonymous namespace but it's impossible to guess the reason of the crash without proper debugging.
I assume Codeforces uses its home-made package manager (pbox). I believe the exact binaries run on CF are in one of packages.
Huge thanks! I reproduced it with package "mingw-w64" which contains gcc version 6.2. I will try to investigate further.
So I've done a bit of research and here's some conclusions:
This bug is reproducible only on 32-bit MinGW (or probably if you target 32-bit with 64-bit compiler) and it affects versions starting from at least 4.9 (I didn't check earlier). It was fixed in MinGW starting 7.1 and 6.4.
As far as I can tell for
ask
function gcc ends up using its own "calling convention" where it passes first three arguments aseax
,edx
,ecx
registers and the fourth one on a stack. But on all of the generated calls it doesn't actually pushes the fourth argument to a stack but writes it directly to memory pointed byesp
(stack pointer) register but after each call it for some reason subtracts 4 fromesp
register which I believe shouldn't happen because we didn't move it in any way before call. Soesp
register points to incorrect memory duringret
instruction and program crashes after finishing the first recursive call.Here's screenshot showing that difference between 6.4 and 6.2 generated assembly mostly consists in removal of
esp
subtraction.The things which are unclear to me:
Why it's not reproducible on Linux. It seems to generate the same "calling convention" for
ask
function but code for calls look totally different from MinGW. I don't know what can cause such discrepancy.Where to find relevant bugfix. Have no idea where to find MinGW changelogs, gcc 6.4 fixes doesn't contain anything similar.
gcc inling logic is super crazy. Moving
my_main
out of anonymous namespace leads to whole recursion being inlined inside it but in current code recursive function is actually called.Morale: Updating to new minor gcc versions could actually be useful.