[Bug middle-end/39326] Segmentation fault with -O1, out of memory with -O2

["steven at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39326

--- Comment #25 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-07 00:08:26 UTC ---
(In reply to comment #24)
> (In reply to comment #22)
> > 4.8.0  -O2  (terminated after 9 minutes waiting, LIM being the offender, I
> > suspect domwalk ...)  >2.5GB
> > 
> > applying domwalk fix ...
> 
> It is LIM, for sure. I've been watching in GDB for a while at some
> back traces, and it's spent minutes already in this DOM walk:

After this, it's spending even more time in refs_independent_p, doing
bitmap tests (ah! a test case for my splay tree bitmaps!).

Is the refs_independent_p relation symmetric? It certainly looks that
way.  If so, one way to halve the work done here is to build only half
the "independence" graph.  Currently it builds a full square:

  if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
                            &memory_accesses.ttae_cache))
    { 
      bitmap_set_bit (ref1->dep_ref, ref2->id);
      bitmap_set_bit (ref2->dep_ref, ref1->id);
      if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "dependent.\n");
      return false;
    }
  else
    {
      bitmap_set_bit (ref1->indep_ref, ref2->id);
      bitmap_set_bit (ref2->indep_ref, ref1->id);
      if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "independent.\n");
      return true;
    }

It's hard to say how much memory is wasted here (obstack_memory_used
is still broken and overflows), but it's probably x*100MB if not more.