From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 6677D3858C62; Wed, 11 Jan 2023 12:13:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6677D3858C62 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1673439239; bh=NV9zJW91lY917N1WtHkJi8ZabK6amczArEqAzSmRN+4=; h=From:To:Subject:Date:From; b=dtaJnL6TB5N39elj04GrVAWIIo3gAINb71AERq0WiA55+0/chURE9HaNCpwRLd8P7 dMeWyFKJ3ZJoNj7yRld8GKQI6m8FErgYEyTrohDOXguG3reNubVscxqFgfH1N7UhNj G5rtNYW0j1NiLMJfIe/aQBjH6ZBuWhbHDYVSfKWQ= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-5106] tree-optimization/107767 - not profitable switch conversion X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: b39c1bea5bae9aee1df25cab1064f983b9ec6941 X-Git-Newrev: f99d7d669eaa2830eb5878df4da67e77ec791522 Message-Id: <20230111121359.6677D3858C62@sourceware.org> Date: Wed, 11 Jan 2023 12:13:59 +0000 (GMT) List-Id: https://gcc.gnu.org/g:f99d7d669eaa2830eb5878df4da67e77ec791522 commit r13-5106-gf99d7d669eaa2830eb5878df4da67e77ec791522 Author: Richard Biener Date: Mon Jan 9 09:42:22 2023 +0100 tree-optimization/107767 - not profitable switch conversion 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. 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. Diff: --- 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(-) 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 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