[PATCH] Fix PR93199, quadraticness in cleanup_all_empty_eh

[Richard Biener]

The following manages to avoid high EH indegree of landing pads
during the sequence of cleaning up empty EH with a chain of those.
By walking the landing pads in reverse order we mimic walking of
the EH tree depth-first (which I am too lazy to write...).  It
looks like EH build assures that this is effectively the same.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

OK?

With this the RedHat bugzilla testcase is down to a "flat" profile:

 parser function body               :  14.60 ( 17%)   1.77 ( 31%)  16.37 ( 
18%)  720798 kB ( 23%)
 tree eh                            :  14.80 ( 17%)   0.06 (  1%)  14.87 ( 
16%)  246315 kB (  8%)
 integrated RA                      :  13.08 ( 15%)   0.30 (  5%)  13.40 ( 
15%)  227799 kB (  7%)
 TOTAL                              :  85.07          5.68         90.77        
3183334 kB

and memory usage is down as well to 4GB (it's actually this very patch
that helps here for reasons I have not investigated - maybe we never
shrink some EH data structures, who knows).

Thanks,
Richard.

2020-01-10  Richard Biener  <rguent...@suse.de>

        PR middle-end/93199
        * tree-eh.c (redirect_eh_edge_1): Avoid some work if possible.
        (cleanup_all_empty_eh): Walk landing pads in reverse order to
        avoid quadraticness.

Index: gcc/tree-eh.c
===================================================================
--- gcc/tree-eh.c       (revision 280097)
+++ gcc/tree-eh.c       (working copy)
@@ -2310,7 +2310,7 @@ redirect_eh_edge_1 (edge edge_in, basic_
   old_lp = get_eh_landing_pad_from_number (old_lp_nr);
 
   throw_stmt = last_stmt (edge_in->src);
-  gcc_assert (lookup_stmt_eh_lp (throw_stmt) == old_lp_nr);
+  gcc_checking_assert (lookup_stmt_eh_lp (throw_stmt) == old_lp_nr);
 
   new_label = gimple_block_label (new_bb);
 
@@ -4307,9 +4307,10 @@ cleanup_empty_eh_merge_phis (basic_block
        |  | EH
        <..>
      which CFG verification would choke on.  See PR45172 and PR51089.  */
-  FOR_EACH_EDGE (e, ei, old_bb->preds)
-    if (find_edge (e->src, new_bb))
-      return false;
+  if (!single_pred_p (new_bb))
+    FOR_EACH_EDGE (e, ei, old_bb->preds)
+      if (find_edge (e->src, new_bb))
+       return false;
 
   FOR_EACH_EDGE (e, ei, old_bb->preds)
     redirect_edge_var_map_clear (e);
@@ -4698,9 +4699,15 @@ cleanup_all_empty_eh (void)
   eh_landing_pad lp;
   int i;
 
-  for (i = 1; vec_safe_iterate (cfun->eh->lp_array, i, &lp); ++i)
-    if (lp)
-      changed |= cleanup_empty_eh (lp);
+  /* Ideally we'd walk the region tree and process LPs inner to outer
+     to avoid quadraticness in EH redirection.  Walking the LP array
+     in reverse seems to be an approximation of that.  */
+  for (i = vec_safe_length (cfun->eh->lp_array) - 1; i >= 1; --i)
+    {
+      lp = (*cfun->eh->lp_array)[i];
+      if (lp)
+       changed |= cleanup_empty_eh (lp);
+    }
 
   return changed;
 }