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).
