On Mon, Mar 4, 2013 at 8:13 PM, Steven Bosscher <stevenb....@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.
