[PATCH] tree-optimization/107767 - not profitable switch conversion

[PATCH] tree-optimization/107767 - not profitable switch conversion

[Richard Biener]

When the CFG has not merged equal PHI defs in a switch stmt the
cost model from switch conversion gets off and we prefer a
jump table over branches.  The following fixes that by recording
cases that will be merged later and more appropriately counting
unique values.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Martin, OK with you?

Thanks,
Richard.

	PR tree-optimization/107767
	* tree-cfgcleanup.cc (phi_alternatives_equal): Export.
	* tree-cfgcleanup.h (phi_alternatives_equal): Declare.
	* tree-switch-conversion.cc (switch_conversion::collect):
	Count unique non-default targets accounting for later
	merging opportunities.

	* gcc.dg/tree-ssa/pr107767.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/pr107767.c | 20 ++++++++++
 gcc/tree-cfgcleanup.cc                   |  2 +-
 gcc/tree-cfgcleanup.h                    |  1 +
 gcc/tree-switch-conversion.cc            | 49 ++++++++++++++++++------
 4 files changed, 60 insertions(+), 12 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr107767.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr107767.c b/gcc/testsuite/gcc.dg/tree-ssa/pr107767.c
new file mode 100644
index 00000000000..bace8abfd9c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr107767.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-Os -fdump-tree-switchconv" } */
+
+int firewall2(const unsigned char *restrict data)
+{
+  const unsigned short dst_port = *((const unsigned short *)data + 32);
+
+  if (dst_port == 15) return 1;
+  if (dst_port == 23) return 1;
+  if (dst_port == 47) return 1;
+  if (dst_port == 45) return 1;
+  if (dst_port == 42) return 1;
+  if (dst_port == 1) return 1;
+  if (dst_port == 2) return 1;
+  if (dst_port == 3) return 1;
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "CSWTCH" "switchconv" } } */
diff --git a/gcc/tree-cfgcleanup.cc b/gcc/tree-cfgcleanup.cc
index 075b1560cdd..ca0cb633f2c 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-cfgcleanup.h b/gcc/tree-cfgcleanup.h
index c26831915c0..b7c7ff1ebcd 100644
--- a/gcc/tree-cfgcleanup.h
+++ b/gcc/tree-cfgcleanup.h
@@ -27,5 +27,6 @@ extern bool fixup_noreturn_call (gimple *stmt);
 extern bool delete_unreachable_blocks_update_callgraph (cgraph_node *dst_node,
 							bool update_clones);
 extern unsigned clean_up_loop_closed_phi (function *);
+extern bool phi_alternatives_equal (basic_block, edge, edge);
 
 #endif /* GCC_TREE_CFGCLEANUP_H */
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 6aeabb96c26..c08c22039c9 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -51,6 +51,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "tree-into-ssa.h"
 #include "omp-general.h"
 #include "gimple-range.h"
+#include "tree-cfgcleanup.h"
 
 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
    type in the GIMPLE type system that is language-independent?  */
@@ -132,16 +133,42 @@ 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)
       {
+	edge phi_e = nullptr;
 	if (e->dest == m_final_bb)
-	  continue;
-
-	if (single_pred_p (e->dest)
-	    && single_succ_p (e->dest)
-	    && single_succ (e->dest) == m_final_bb)
-	  continue;
+	  phi_e = e;
+	else if (single_pred_p (e->dest)
+		 && single_succ_p (e->dest)
+		 && single_succ (e->dest) == m_final_bb)
+	  phi_e = single_succ_edge (e->dest);
+	if (phi_e)
+	  {
+	    if (e == e_default)
+	      ;
+	    else if (phi_e == e || empty_block_p (e->dest))
+	      {
+		/* For empty blocks consider forwarders with equal
+		   PHI arguments in m_final_bb as unique.  */
+		unsigned i;
+		for (i = 0; i < fw_edges.length (); ++i)
+		  if (phi_alternatives_equal (m_final_bb, fw_edges[i], phi_e))
+		    break;
+		if (i == fw_edges.length ())
+		  {
+		    /* But limit the above possibly quadratic search.  */
+		    if (fw_edges.length () < 10)
+		      fw_edges.quick_push (phi_e);
+		    m_uniq++;
+		  }
+	      }
+	    else
+	      m_uniq++;
+	    continue;
+	  }
 
 	if (e == e_default && m_contiguous_range)
 	  {
@@ -153,6 +180,11 @@ switch_conversion::collect (gswitch *swtch)
 	break;
       }
 
+  /* When there's not a single common successor block conservatively
+     approximate the number of unique non-default targets.  */
+  if (!m_final_bb)
+    m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
+
   m_range_size
     = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
 
@@ -168,11 +200,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
-- 
2.35.3

Re: [PATCH] tree-optimization/107767 - not profitable switch conversion

[Martin Liška]

On 1/9/23 12:09, Richard Biener wrote:
> |Martin, OK with you?|

Yes, thanks for handling that.

Martin