[Bug c++/55135] [4.8 Regression] Segfault of gcc on a big file

[steven at gcc dot gnu.org]

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

--- Comment #16 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-01 14:35:20 UTC ---
(In reply to comment #15)
> > - Queue up to-be-removed EH regions, instead of removing them one-by-one.
> >   Removing them one at a time results in walking the list of EH regions
> >   repeatedly, thus taking O(# of EH regions ** 2) time.
> This (properly cleaned up) looks reasonable to me.

It's not yet complete, I think I need to update the outer region pointers
for the inner region if an outer region is removed. But I think this is
the right approach.


> > - Rewrite init_subregs_of_mode and subroutines to first collect the
> >   invalid mode change subregs in sbitmaps, and then converting the final
> >   sbitmap to a bitmap. This trades memory for time: the bitmap lookups are
> >   also potentially O(# of registers ** 2) and this test case has more than
> >   one million registers, many of them with invalid mode changes (to be fixed
> >   up by IRA/LRA).
> Hmm - this is because we hit the O(n) complexity we have on our bitmap
> implementation?

Yes.

>  Can't we improve init_subregs_of_mode by first collecting
> all mode changes we see for a pseudo (eventually using DF info?) and
> then do the processing in some more optimal order?

Yes. That is the plan, this was just a proof-of-concept fix (I didn't call
it a patch, I called it a hack - for the good reasons you mentioned :-).

I also want to add a better way to lookup bits as random-access in bitmaps:
change the "view" of the bitmap, much like what tree-ssa-live does with its
maps).