Patchwork PR c++/55135

login
register
mail settings
Submitter Steven Bosscher
Date March 4, 2013, 7:13 p.m.
Message ID <CABu31nM78ayVa-ptj_PgQ+-bjUM-hEJRiEit5sGLRaRT7WaENQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/224784/
State New
Headers show

Comments

Steven Bosscher - March 4, 2013, 7:13 p.m.
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.
Richard Guenther - March 5, 2013, 9:25 a.m.
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.

Patch

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 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 (&region->inner, r_reachable);
+      if (!bitmap_bit_p (r_reachable, region->index))
+	remove_eh_handler_splicer (pp);
+      else
+	pp = &region->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.  */
 
Index: tree-eh.c
===================================================================
--- tree-eh.c	(revision 196410)
+++ tree-eh.c	(working copy)
@@ -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, &region); ++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);
 }