From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1851) id 4EB913858036; Fri, 18 Dec 2020 13:18:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4EB913858036 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Martin Liska To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/marxin/heads/PR94779-switchconv-part1)] Make switchconv smarter. X-Act-Checkin: gcc X-Git-Author: Martin Liska X-Git-Refname: refs/users/marxin/heads/PR94779-switchconv-part1 X-Git-Oldrev: 11f07ef37786d10517121fc6226681cd1aa2aea2 X-Git-Newrev: 726654578a8502027089f2e05ac077cf5c48b8a0 Message-Id: <20201218131827.4EB913858036@sourceware.org> Date: Fri, 18 Dec 2020 13:18:27 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 18 Dec 2020 13:18:27 -0000 https://gcc.gnu.org/g:726654578a8502027089f2e05ac077cf5c48b8a0 commit 726654578a8502027089f2e05ac077cf5c48b8a0 Author: Martin Liska Date: Thu Dec 17 14:17:08 2020 +0100 Make switchconv smarter. gcc/ChangeLog: PR tree-optimization/94779 * tree-switch-conversion.c (switch_conversion::switch_conversion): Initialize m_default_unreachable, m_missing_return_in_default and m_inbound_check_needed. (switch_conversion::collect): Start with first edge also if m_default_unreachable or m_missing_return_in_default. (switch_conversion::check_all_empty_except_final): Ignore default edge for case where m_default_unreachable is true. (switch_conversion::phi_leads_to_return): New. (switch_conversion::build_one_array): Drop boundary check for linear transformation where m_missing_return_in_default is true (switch_conversion::analyze_default_bb): New. (switch_conversion::gen_inbound_check): Generate if TRUE when m_default_unreachable or we don't need boundary check. (switch_conversion::expand): Do transformation as we can't be sure that the switch will be expaded with JT. * tree-switch-conversion.h: Declare new functions and variables. gcc/testsuite/ChangeLog: PR tree-optimization/94779 * gcc.dg/tree-ssa/cswtch-6.c: New test. * gcc.dg/tree-ssa/cswtch-7.c: New test. Diff: --- gcc/testsuite/gcc.dg/tree-ssa/cswtch-6.c | 22 +++++++++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-7.c | 19 ++++++++ gcc/tree-switch-conversion.c | 78 +++++++++++++++++++++++++++----- gcc/tree-switch-conversion.h | 14 ++++++ 4 files changed, 122 insertions(+), 11 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cswtch-6.c b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-6.c new file mode 100644 index 00000000000..e5aa09fdbde --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-6.c @@ -0,0 +1,22 @@ +/* PR tree-optimization/94779 */ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ +/* { dg-do compile { target nonpic } } */ + +int global; + +int f1(unsigned x) +{ + int v; + switch (x) + { + case 0: + return 1; + case 1: + return 2; + case 2: + return 3; + } +} + +/* { dg-final { scan-tree-dump-times "Linear transformation with A = 1 and B = 1" 1 "switchconv" } } */ +/* { dg-final { scan-tree-dump-not "if " "switchconv" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cswtch-7.c b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-7.c new file mode 100644 index 00000000000..15ca9849f9d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-7.c @@ -0,0 +1,19 @@ +/* PR tree-optimization/94779 */ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ +/* { dg-do compile { target nonpic } } */ + +int global; + +int f1(unsigned x) +{ + switch (x) + { + case 0: + return 1; + case 1: + return 2; + } +} + +/* { dg-final { scan-tree-dump-times "Linear transformation with A = 1 and B = 1" 1 "switchconv" } } */ +/* { dg-final { scan-tree-dump "Switch converted" "switchconv" } } */ diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 08dfd6f3580..dd64daf4b92 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -64,7 +64,9 @@ using namespace tree_switch_conversion; switch_conversion::switch_conversion (): m_final_bb (NULL), m_constructors (NULL), m_default_values (NULL), m_arr_ref_first (NULL), m_arr_ref_last (NULL), - m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false) + m_reason (NULL), m_default_unreachable (false), + m_missing_return_in_default (false), m_inbound_check_needed (true), + m_default_case_nonstandard (false), m_cfg_altered (false) { } @@ -90,6 +92,8 @@ switch_conversion::collect (gswitch *swtch) m_default_bb = e_default->dest; m_default_prob = e_default->probability; + analyze_default_bb (); + /* Get upper and lower bounds of case values, and the covered range. */ min_case = gimple_switch_label (swtch, 1); max_case = gimple_switch_label (swtch, branch_num - 1); @@ -113,7 +117,9 @@ switch_conversion::collect (gswitch *swtch) last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); } - if (m_contiguous_range) + if (m_contiguous_range + || m_default_unreachable + || m_missing_return_in_default) e_first = gimple_switch_edge (cfun, swtch, 1); else e_first = e_default; @@ -142,7 +148,7 @@ switch_conversion::collect (gswitch *swtch) && single_succ (e->dest) == m_final_bb) continue; - if (e == e_default && m_contiguous_range) + if (e == e_default && (m_contiguous_range || m_default_unreachable)) { m_default_case_nonstandard = true; continue; @@ -211,6 +217,9 @@ switch_conversion::check_all_empty_except_final () if (e->dest == m_final_bb) continue; + if (e == e_default && m_default_unreachable) + continue; + if (!empty_block_p (e->dest)) { if (m_contiguous_range && e == e_default) @@ -572,6 +581,24 @@ switch_conversion::array_value_type (tree type, int num) return smaller_type; } +/* Return true if PHI leads only to a return statement. */ + +bool +switch_conversion::phi_leads_to_return (gphi *phi) +{ + use_operand_p use_p; + imm_use_iterator iterator; + + FOR_EACH_IMM_USE_FAST (use_p, iterator, PHI_RESULT (phi)) + { + gimple *stmt = USE_STMT (use_p); + if (!is_a (stmt) && !is_gimple_debug (stmt)) + return false; + } + + return true; +} + /* Create an appropriate array type and declaration and assemble a static array variable. Also create a load statement that initializes the variable in question with a value from the static array. SWTCH is @@ -609,6 +636,10 @@ switch_conversion::build_one_array (int num, tree arr_index_type, " and B = %" PRId64 "\n", coeff_a.to_shwi (), coeff_b.to_shwi ()); + if (m_phi_count == 1 && phi_leads_to_return (phi) + && m_missing_return_in_default) + m_inbound_check_needed = false; + /* We must use type of constructor values. */ gimple_seq seq = NULL; tree tmp = gimple_convert (&seq, type, m_index_expr); @@ -807,6 +838,34 @@ switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) } } +/* Analyze default BB. */ + +void +switch_conversion::analyze_default_bb () +{ + gimple_seq stmts = bb_seq (m_default_bb); + if (gimple_seq_unreachable_p (stmts)) + m_default_unreachable = true; + + gimple_stmt_iterator gsi = gsi_last (stmts); + greturn *ret = dyn_cast (gsi_stmt (gsi)); + if (ret == NULL + || gimple_return_retval (ret) != NULL_TREE + || VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl)))) + return; + + for (gsi_prev (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (gimple_code (stmt) != GIMPLE_LABEL + && !is_gimple_debug (stmt) + && !gimple_clobber_p (stmt)) + return; + } + + m_missing_return_in_default = true; +} + /* Creates a check whether the switch expression value actually falls into the range given by all the cases. If it does not, the temporaries are loaded with default values instead. */ @@ -841,7 +900,11 @@ switch_conversion::gen_inbound_check () gsi_next (&gsi); bound = fold_convert_loc (loc, utype, m_range_size); - cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); + if (m_default_unreachable || !m_inbound_check_needed) + cond_stmt = gimple_build_cond (EQ_EXPR, integer_one_node, integer_one_node, + NULL_TREE, NULL_TREE); + else + cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); update_stmt (cond_stmt); @@ -993,13 +1056,6 @@ switch_conversion::expand (gswitch *swtch) return; } - if (m_uniq <= 2) - { - /* This will be expanded as a decision tree . */ - m_reason = "expanding as jumps is preferable"; - return; - } - /* If there is no common successor, we cannot do the transformation. */ if (!m_final_bb) { diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 62cfde168c8..5a380dd1ffb 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -800,6 +800,12 @@ public: bbf description in the comment below). */ void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf); + /* Analyze default BB. */ + void analyze_default_bb (); + + /* Return true if PHI leads only to a return statement. */ + bool phi_leads_to_return (gphi *phi); + /* Creates a check whether the switch expression value actually falls into the range given by all the cases. If it does not, the temporaries are loaded with default values instead. */ @@ -869,6 +875,14 @@ public: range_max inclusive. */ bool m_contiguous_range; + /* True if default case is unreachable. */ + bool m_default_unreachable; + + /* True if default BB misses return statement for non-void functions. */ + bool m_missing_return_in_default; + + bool m_inbound_check_needed; + /* True if default case does not have the required shape for other case labels. */ bool m_default_case_nonstandard;