DBradac's blog

Unusual runtime error
By DBradac, history, 8 years ago, In English

I encountered an unusual runtime error during today's Div 2 round on problem D. http://mirror.codeforces.com/contest/706/problem/D

I implemented a simple trie, and received runtime error on test 1. http://mirror.codeforces.com/contest/706/submission/19803196

After some more submissions, I got to this: http://mirror.codeforces.com/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://mirror.codeforces.com/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?

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

»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's wired. GCC-5.1.0 also works well on my machine. I really don't know what happened on Codeforces...

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Codeforces uses MinGW, not original GCC. So it has many problems.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes you are right. even GCC-6.1.0 is still generating wrong code for target i686-w64-mingw32.

        → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I was able to reduce it this far:

#include <cstdio>

struct node {
  node *l, *r;
  int x;
};

node NIL{&NIL, &NIL};

struct trie {
  int mx(node *p, int poz, int x) {
    if (poz == -1)
      return 0;
    node* v = poz ? p->l : p->r;
    if (v->l == v->r)
      return mx(v, poz-1, x) + (1 << poz);
    return 1;
  }
} Tr;

int main(int argc, const char* argv[])
{
    printf("%d\n", Tr.mx(&NIL, 2, argc));
    return 0;
}
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 7   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply