[Bug rtl-optimization/69609] [6 Regression] block reordering consumes an inordinate amount of time, REE consumes much memory

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69609

--- Comment #3 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
Something like this maybe? Tries to determine if too large a fraction of blocks
are only reachable by computed jumps in a large function (which I'm guessing is
what triggers the compile time issues).

diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 8cbde89..10d106a 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -2435,13 +2435,39 @@ reorder_basic_blocks (void)
 {
   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);

-  if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
+  int n_bbs = n_basic_blocks_for_fn (cfun);
+  if (n_bbs <= NUM_FIXED_BLOCKS + 1)
     return;

   set_edge_can_fallthru_flag ();
   mark_dfs_back_edges ();

-  switch (flag_reorder_blocks_algorithm)
+  enum reorder_blocks_algorithm alg = flag_reorder_blocks_algorithm;
+  /* Try to detect cases where the STC algorithm is too expensive
+     and likely to be ineffective.  */
+  if (alg == REORDER_BLOCKS_ALGORITHM_STC && n_bbs > 2000)
+    {
+      basic_block bb;
+      int abnormals = 0;
+      FOR_EACH_BB_FN (bb, cfun)
+       {
+         edge e;
+         edge_iterator ei;
+         bool all_abnormal = true;
+         FOR_EACH_EDGE (e, ei, bb->preds)
+           if (!(e->flags & EDGE_ABNORMAL))
+             {
+               all_abnormal = false;
+               break;
+             }
+         if (all_abnormal)
+           abnormals++;
+       }
+      if ((double)abnormals * 16 / n_bbs > 3)
+       alg = REORDER_BLOCKS_ALGORITHM_SIMPLE;
+    }
+
+  switch (alg)
     {
     case REORDER_BLOCKS_ALGORITHM_SIMPLE:
       reorder_basic_blocks_simple ();