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.
Bootstrappedtested 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.
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.
Index: except.h
===
--- except.h(revision 196410)
+++ except.h(working copy)
@@ -229,6 +229,7 @@ extern void init_eh_for_function (void);
extern void remove_eh_landing_pad (eh_landing_pad);
extern void remove_eh_handler (eh_region);
+extern void remove_unreachable_eh_regions (sbitmap);
extern bool current_function_has_exception_handlers (void);
extern void output_function_exception_table (const char *);
Index: except.c
===
--- except.c(revision 196410)
+++ except.c(working copy)
@@ -1505,12 +1505,12 @@ remove_eh_landing_pad (eh_landing_pad lp
(*cfun-eh-lp_array)[lp-index] = NULL;
}
-/* Splice REGION from the region tree. */
+/* Splice the EH region at PP from the region tree. */
-void
-remove_eh_handler (eh_region region)
+static void
+remove_eh_handler_splicer (eh_region *pp)
{
- eh_region *pp, *pp_start, p, outer;
+ eh_region region = *pp;
eh_landing_pad lp;
for (lp = region-landing_pads; lp ; lp = lp-next_lp)
@@ -1520,15 +1520,11 @@ remove_eh_handler (eh_region region)
(*cfun-eh-lp_array)[lp-index] = NULL;
}
- outer = region-outer;
- if (outer)
-pp_start = outer-inner;
- else
-pp_start = cfun-eh-region_tree;
- for (pp = pp_start, p = *pp; p != region; pp = p-next_peer, p = *pp)
-continue;
if (region-inner)
{
+ eh_region p, outer;
+ outer = region-outer;
+
*pp = p = region-inner;
do
{
@@ -1543,6 +1539,59 @@ remove_eh_handler (eh_region region)
(*cfun-eh-region_array)[region-index] = NULL;
}
+/* Splice a single EH region REGION from the region tree.
+
+ To unlink REGION, we need to
