From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id F28833857838; Wed, 21 Dec 2022 09:46:23 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F28833857838 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1671615983; bh=gYxcgj93PDhOqMaW+sKbdGiBzS4EURVyoQNSw7xUnaU=; h=From:To:Subject:Date:In-Reply-To:References:From; b=OIsfDeJqjawsnL7q5+I9tKHJT0WfuEN6bQaUKG7Mj7ZtosC3D17RUgyV2TVJ41hlh YrloTDh+aN8BXJsRrxW7C3WmvfuPkErP26Aqr1OYU9ZL1f+JRuC3lSNJfSLVKlcYeQ 2VoSNd1dBeyNwNmwvlEXHMpqvqNKQ0bukuTw/AoU= From: "rguenth at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/107767] [13 Regression] switch to table conversion happening even though using btq is better Date: Wed, 21 Dec 2022 09:46:23 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: tree-optimization X-Bugzilla-Version: 13.0 X-Bugzilla-Keywords: missed-optimization X-Bugzilla-Severity: normal X-Bugzilla-Who: rguenth at gcc dot gnu.org X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: 13.0 X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: cc Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D107767 Richard Biener changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |rguenth at gcc dot gnu.org --- Comment #14 from Richard Biener --- 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 =3D gimplify_ctxp->in_switch_expr; gimplify_ctxp->in_switch_expr =3D true; + gimple_push_condition (); gimplify_stmt (&SWITCH_BODY (switch_expr), &switch_body_seq); + gimple_pop_condition (pre_p); gimplify_ctxp->in_switch_expr =3D 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 : dst_port_5 =3D MEM[(const uint16_t *)data_3(D) + 64B]; switch (dst_port_5) [INV], case 1: [INV], case 2: <= L17> [INV], case 3: [INV], case 15: [INV], case 23: [INV], case 42: [INV], case 45: [INV], case 47: [INV]> : : : # _2 =3D PHI <1(3), 0(2)> : 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 =3D 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 fw_edges; + m_uniq =3D 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) =3D=3D 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 =3D 0; i < fw_edges.length (); ++i) + if (phi_alternatives_equal (m_final_bb, fw_edges[i], e)) + break; + if (i =3D=3D 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 =3D=3D 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 =3D EDGE_COUNT (gimple_bb (swtch)->succs) - 1; } /* Checks whether the range given by individual case statements of the swi= tch=