[Bug tree-optimization/107767] [13 Regression] switch to table conversion happening even though using btq is better

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
diff --git a/gcc/gimplify.cc b/gcc/gimplify.cc
index 250782b1140..41f48c30bb9 100644
--- a/gcc/gimplify.cc
+++ b/gcc/gimplify.cc
@@ -2713,7 +2713,9 @@ gimplify_switch_expr (tree *expr_p, gimple_seq *pre_p)
       bool old_in_switch_expr = gimplify_ctxp->in_switch_expr;
       gimplify_ctxp->in_switch_expr = true;

+      gimple_push_condition ();
       gimplify_stmt (&SWITCH_BODY (switch_expr), &switch_body_seq);
+      gimple_pop_condition (pre_p);

       gimplify_ctxp->in_switch_expr = old_in_switch_expr;
       maybe_warn_switch_unreachable_and_auto_init (switch_body_seq);

"properly" adds early return predictors to switch returns and will result in
the same pessimization.  Cutting off early return predictor generation will
make firewall2 produce via if-to-switch

  <bb 2> :
  dst_port_5 = MEM[(const uint16_t *)data_3(D) + 64B];
  switch (dst_port_5) <default: <L18> [INV], case 1: <L17> [INV], case 2: <L17>
[INV], case 3: <L17> [INV], case 15: <L17> [INV], case 23: <L17> [INV], case
42: <L17> [INV], case 45: <L17> [INV], case 47: <L17> [INV]>

  <bb 3> :
<L17>:

  <bb 4> :
  # _2 = PHI <1(3), 0(2)>
<L18>:
  return _2;

and retaining a bit test.

Note that after stripping predict hints it takes tail-merging to unify
the forwarders, this is not something done by CFG cleanup.  That's
because in this case all forwarders have '1' as the PHI argument but
the single non-forwarder has '0'.  CFG cleanup doesn't redirect
forwarders to duplicates.  The default label doesn't have an
early return prediction (the return doesn't happen in conditional
context as far as gimplification is concerned).  If it had a forwarder
as well which forwarder CFG cleanup would remove would be "random".

Note this all would still happen too late for the early switch conversion
pass.

It might be possible to alter the switch conversion heuristics in ::collect
to handle empty_block_p forwarders specially, counting the number of
forwarders with distinct m_final_bb PHI argument sets.  Like with the
following.

diff --git a/gcc/tree-cfgcleanup.cc b/gcc/tree-cfgcleanup.cc
index b4869aee78d..38e40eca164 100644
--- a/gcc/tree-cfgcleanup.cc
+++ b/gcc/tree-cfgcleanup.cc
@@ -450,7 +450,7 @@ tree_forwarder_block_p (basic_block bb, bool phi_wanted)
    those alternatives are equal in each of the PHI nodes, then return
    true, else return false.  */

-static bool
+bool
 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
 {
   int n1 = e1->dest_idx;
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 1d75d7c7fc7..6d2889f6c5a 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -69,6 +69,9 @@ switch_conversion::switch_conversion (): m_final_bb (NULL),
 {
 }

+bool
+phi_alternatives_equal (basic_block dest, edge e1, edge e2);
+
 /* Collection information about SWTCH statement.  */

 void
@@ -132,6 +135,8 @@ switch_conversion::collect (gswitch *swtch)
   /* Require that all switch destinations are either that common
      FINAL_BB or a forwarder to it, except for the default
      case if contiguous range.  */
+  auto_vec<edge, 10> fw_edges;
+  m_uniq = 0;
   if (m_final_bb)
     FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
       {
@@ -141,7 +146,26 @@ switch_conversion::collect (gswitch *swtch)
        if (single_pred_p (e->dest)
            && single_succ_p (e->dest)
            && single_succ (e->dest) == m_final_bb)
-         continue;
+         {
+           if (empty_block_p (e->dest))
+             {
+               /* For empty blocks consider forwarders with equal
+                  PHI arguments in m_final_bb as unique.  */
+               for (unsigned i = 0; i < fw_edges.length (); ++i)
+                 if (phi_alternatives_equal (m_final_bb, fw_edges[i], e))
+                   break;
+               if (i == fw_edges.length ())
+                 {
+                   /* But limit the above possibly quadratic search.  */
+                   if (fw_edges.length () < 10)
+                     fw_edges.quick_push (e);
+                   m_uniq++;
+                 }
+             }
+           else
+             m_uniq++;
+           continue;
+         }

        if (e == e_default && m_contiguous_range)
          {
@@ -168,11 +192,6 @@ switch_conversion::collect (gswitch *swtch)
          && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
        m_count++;
     }
-
-  /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
-     block.  Assume a CFG cleanup would have already removed degenerate
-     switch statements, this allows us to just use EDGE_COUNT.  */
-  m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
 }

 /* Checks whether the range given by individual case statements of the switch