This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
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? 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.
Attachment:
PR55135_O0_EH.diff.txt
Description: Text document
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |