===================================================================
@@ -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 *);
===================================================================
@@ -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 find the pointer to it with a relatively
+ expensive search in REGION's outer region. If you are going to
+ remove a number of handlers, using remove_unreachable_eh_regions may
+ be a better option. */
+
+void
+remove_eh_handler (eh_region region)
+{
+ eh_region *pp, *pp_start, p, outer;
+
+ 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;
+
+ remove_eh_handler_splicer (pp);
+}
+
+/* Worker for remove_unreachable_eh_regions.
+ PP is a pointer to the region to start a region tree depth-first
+ search from. R_REACHABLE is the set of regions that have to be
+ preserved. */
+
+static void
+remove_unreachable_eh_regions_worker (eh_region *pp, sbitmap r_reachable)
+{
+ while (*pp)
+ {
+ eh_region region = *pp;
+ remove_unreachable_eh_regions_worker (®ion->inner, r_reachable);
+ if (!bitmap_bit_p (r_reachable, region->index))
+ remove_eh_handler_splicer (pp);
+ else
+ pp = ®ion->next_peer;
+ }
+}
+
+/* Splice all EH regions *not* marked in R_REACHABLE from the region tree.
+ Do this by traversing the EH tree top-down and splice out regions that
+ are not marked. By removing regions from the leaves, we avoid costly
+ searches in the region tree. */
+
+void
+remove_unreachable_eh_regions (sbitmap r_reachable)
+{
+ remove_unreachable_eh_regions_worker (&cfun->eh->region_tree, r_reachable);
+}
+
/* Invokes CALLBACK for every exception handler landing pad label.
Only used by reload hackery; should not be used by new code. */
===================================================================
@@ -3519,22 +3519,37 @@ struct gimple_opt_pass pass_lower_eh_dis
}
};
-/* Walk statements, see what regions are really referenced and remove
- those that are unused. */
+/* Walk statements, see what regions and, optionally, landing pads
+ are really referenced.
+
+ Returns in R_REACHABLEP an sbitmap with bits set for reachable regions,
+ and in LP_REACHABLE an sbitmap with bits set for reachable landing pads.
+
+ Passing NULL for LP_REACHABLE is valid, in this case only reachable
+ regions are marked.
+
+ The caller is responsible for freeing the returned sbitmaps. */
static void
-remove_unreachable_handlers (void)
+mark_reachable_handlers (sbitmap *r_reachablep, sbitmap *lp_reachablep)
{
sbitmap r_reachable, lp_reachable;
- eh_region region;
- eh_landing_pad lp;
basic_block bb;
- int lp_nr, r_nr;
+ bool mark_landing_pads = (lp_reachablep != NULL);
+ gcc_checking_assert (r_reachablep != NULL);
r_reachable = sbitmap_alloc (cfun->eh->region_array->length ());
- lp_reachable = sbitmap_alloc (cfun->eh->lp_array->length ());
bitmap_clear (r_reachable);
- bitmap_clear (lp_reachable);
+ *r_reachablep = r_reachable;
+
+ if (mark_landing_pads)
+ {
+ lp_reachable = sbitmap_alloc (cfun->eh->lp_array->length ());
+ bitmap_clear (lp_reachable);
+ *lp_reachablep = lp_reachable;
+ }
+ else
+ lp_reachable = NULL;
FOR_EACH_BB (bb)
{
@@ -3543,20 +3558,24 @@ remove_unreachable_handlers (void)
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
- lp_nr = lookup_stmt_eh_lp (stmt);
- /* Negative LP numbers are MUST_NOT_THROW regions which
- are not considered BB enders. */
- if (lp_nr < 0)
- bitmap_set_bit (r_reachable, -lp_nr);
-
- /* Positive LP numbers are real landing pads, are are BB enders. */
- else if (lp_nr > 0)
+ if (mark_landing_pads)
{
- gcc_assert (gsi_one_before_end_p (gsi));
- region = get_eh_region_from_lp_number (lp_nr);
- bitmap_set_bit (r_reachable, region->index);
- bitmap_set_bit (lp_reachable, lp_nr);
+ int lp_nr = lookup_stmt_eh_lp (stmt);
+
+ /* Negative LP numbers are MUST_NOT_THROW regions which
+ are not considered BB enders. */
+ if (lp_nr < 0)
+ bitmap_set_bit (r_reachable, -lp_nr);
+
+ /* Positive LP numbers are real landing pads, and BB enders. */
+ else if (lp_nr > 0)
+ {
+ gcc_assert (gsi_one_before_end_p (gsi));
+ eh_region region = get_eh_region_from_lp_number (lp_nr);
+ bitmap_set_bit (r_reachable, region->index);
+ bitmap_set_bit (lp_reachable, lp_nr);
+ }
}
/* Avoid removing regions referenced from RESX/EH_DISPATCH. */
@@ -3573,6 +3592,19 @@ remove_unreachable_handlers (void)
}
}
}
+}
+
+/* Remove unreachable handlers and unreachable landing pads. */
+
+static void
+remove_unreachable_handlers (void)
+{
+ sbitmap r_reachable, lp_reachable;
+ eh_region region;
+ eh_landing_pad lp;
+ unsigned i;
+
+ mark_reachable_handlers (&r_reachable, &lp_reachable);
if (dump_file)
{
@@ -3584,21 +3616,24 @@ remove_unreachable_handlers (void)
dump_bitmap_file (dump_file, lp_reachable);
}
- for (r_nr = 1;
- vec_safe_iterate (cfun->eh->region_array, r_nr, ®ion); ++r_nr)
- if (region && !bitmap_bit_p (r_reachable, r_nr))
- {
- if (dump_file)
- fprintf (dump_file, "Removing unreachable region %d\n", r_nr);
- remove_eh_handler (region);
- }
+ if (dump_file)
+ {
+ FOR_EACH_VEC_SAFE_ELT (cfun->eh->region_array, i, region)
+ if (region && !bitmap_bit_p (r_reachable, region->index))
+ fprintf (dump_file,
+ "Removing unreachable region %d\n",
+ region->index);
+ }
+
+ remove_unreachable_eh_regions (r_reachable);
- for (lp_nr = 1;
- vec_safe_iterate (cfun->eh->lp_array, lp_nr, &lp); ++lp_nr)
- if (lp && !bitmap_bit_p (lp_reachable, lp_nr))
+ FOR_EACH_VEC_SAFE_ELT (cfun->eh->lp_array, i, lp)
+ if (lp && !bitmap_bit_p (lp_reachable, lp->index))
{
if (dump_file)
- fprintf (dump_file, "Removing unreachable landing pad %d\n", lp_nr);
+ fprintf (dump_file,
+ "Removing unreachable landing pad %d\n",
+ lp->index);
remove_eh_landing_pad (lp);
}
@@ -3624,12 +3659,12 @@ void
maybe_remove_unreachable_handlers (void)
{
eh_landing_pad lp;
- int i;
+ unsigned i;
if (cfun->eh == NULL)
return;
-
- for (i = 1; vec_safe_iterate (cfun->eh->lp_array, i, &lp); ++i)
+
+ FOR_EACH_VEC_SAFE_ELT (cfun->eh->lp_array, i, lp)
if (lp && lp->post_landing_pad)
{
if (label_to_block (lp->post_landing_pad) == NULL)
@@ -3642,45 +3677,38 @@ maybe_remove_unreachable_handlers (void)
/* Remove regions that do not have landing pads. This assumes
that remove_unreachable_handlers has already been run, and
- that we've just manipulated the landing pads since then. */
+ that we've just manipulated the landing pads since then.
+
+ Preserve regions with landing pads and regions that prevent
+ exceptions from propagating further, even if these regions
+ are not reachable. */
static void
remove_unreachable_handlers_no_lp (void)
{
- eh_region r;
- int i;
+ eh_region region;
sbitmap r_reachable;
- basic_block bb;
+ unsigned i;
- r_reachable = sbitmap_alloc (cfun->eh->region_array->length ());
- bitmap_clear (r_reachable);
+ mark_reachable_handlers (&r_reachable, /*lp_reachablep=*/NULL);
- FOR_EACH_BB (bb)
+ FOR_EACH_VEC_SAFE_ELT (cfun->eh->region_array, i, region)
{
- gimple stmt = last_stmt (bb);
- if (stmt)
- /* Avoid removing regions referenced from RESX/EH_DISPATCH. */
- switch (gimple_code (stmt))
- {
- case GIMPLE_RESX:
- bitmap_set_bit (r_reachable, gimple_resx_region (stmt));
- break;
- case GIMPLE_EH_DISPATCH:
- bitmap_set_bit (r_reachable, gimple_eh_dispatch_region (stmt));
- break;
- default:
- break;
- }
+ if (! region)
+ continue;
+
+ if (region->landing_pads != NULL
+ || region->type == ERT_MUST_NOT_THROW)
+ bitmap_set_bit (r_reachable, region->index);
+
+ if (dump_file
+ && !bitmap_bit_p (r_reachable, region->index))
+ fprintf (dump_file,
+ "Removing unreachable region %d\n",
+ region->index);
}
- for (i = 1; cfun->eh->region_array->iterate (i, &r); ++i)
- if (r && r->landing_pads == NULL && r->type != ERT_MUST_NOT_THROW
- && !bitmap_bit_p (r_reachable, i))
- {
- if (dump_file)
- fprintf (dump_file, "Removing unreachable region %d\n", i);
- remove_eh_handler (r);
- }
+ remove_unreachable_eh_regions (r_reachable);
sbitmap_free (r_reachable);
}
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. 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.