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.

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;
}

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.