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
