From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id CFCA7385841A for ; Mon, 9 Jan 2023 11:09:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CFCA7385841A Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id B45FA38D93; Mon, 9 Jan 2023 11:09:41 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1673262581; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=QH31CViCOwTHj/YmDmtn509vGVGMwdcpfF8P9wo3RJs=; b=ExVD1sU+sFhNaye9tYTu8X4qUlf599WBWSOq5EcxNyEuQ6XiSUXyqwlFRfQrYOqCCMp+IZ 3R+0D10oGVxZ4Xd+RSx7DS8sCgXlxpnHDb6lW8ysWP8L2khwqhlGA/Cp+RWl2vdNlKPWy3 s5WcsUryzuWL3i0dHy7Ty8h0aLnXPiQ= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1673262581; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=QH31CViCOwTHj/YmDmtn509vGVGMwdcpfF8P9wo3RJs=; b=PEPyhvXTXmmsT+0IQiCAxUYn8oTDvfT8kqDekJ39L2XBzEsXN2CsT//9Hn5nAV3ViPx2O9 jLY/a8Q9DJVBmMBQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 9FB86134AD; Mon, 9 Jan 2023 11:09:41 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id Ozb5JfX1u2OKNgAAMHmgww (envelope-from ); Mon, 09 Jan 2023 11:09:41 +0000 Date: Mon, 9 Jan 2023 12:09:41 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: mliska@suse.cz Subject: [PATCH] tree-optimization/107767 - not profitable switch conversion MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20230109110941.9FB86134AD@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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 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