Re: [patch] PR c++/55135

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Mar 4, 2013 at 8:13 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> Bug c++/55135 is another one of those almost-insane large test cases
> that triggers some of the worst time complexity behavior GCC has to
> offer. The attached patch doesn't actually fix anything the bug poster
> complained about, but something I ran into myself while trying to
> compile the file at -O0. It's a regression from older GCC releases and
> a test case for which clang kicks our butts.
>
> What happens at -O0 for this test case, is that there are 179972 EH
> regions and all but 3 of them are removed in
> remove_unreachable_handlers, which calls remove_eh_handler one region
> at a time in a loop. Because the EH tree is almost flat (almost a
> linked list), and remove_eh_handler has to look up the dead region in
> the tree, this results in O(N_EH_regions^2) run time in
> pass_cleanup_eh.
>
> The solution I propose in the attached patch, is to remove all
> unreachable regions in a single walk over the EH tree. This makes
> remove_unreachable_handlers run in no worse than O(N_EH_regions) time.
> If there are only a few regions to be removed, then this is
> potentially slower than the existing algorithm, but there is already a
> complete function walk in remove_unreachable_handlers and in the
> non-O0 case the EH tree is usually relatively small even for large
> functions. In any case, I have measured compile time on some C++ and
> Java cases and there were no measurable compile time regressions at
> -O1+, and a few improvements at -O0.
>
> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK for trunk?

Ok.

Thanks,
Richard.

> Ciao!
> Steven
>
>
> gcc/
>         PR c++/55135
>         * except.h (remove_unreachable_eh_regions): New prototype.
>         * except.c (remove_eh_handler_splicer): New function, split out
>         of remove_eh_handler.
>         (remove_eh_handler): Use remove_eh_handler_splicer.  Add comment
>         warning about running it on many EH regions one at a time.
>         (remove_unreachable_eh_regions_worker): New function, walk the
>         EH tree in depth-first order and remove non-marked regions.
>         (remove_unreachable_eh_regions): New function.
>         * tree-eh.c (mark_reachable_handlers): New function, split out
>         from remove_unreachable_handlers.
>         (remove_unreachable_handlers): Use mark_reachable_handlers and
>         remove_unreachable_eh_regions.
>         (remove_unreachable_handlers_no_lp): Use mark_reachable_handlers
>         and remove_unreachable_eh_regions.