From: Andrew Pinski <apin...@marvell.com> To simplify PHI-OPT and future improvements to it in most (but not all) cases, using match-and-simplify simplifies how much code is needed to be added.
This depends on the following two patches: https://gcc.gnu.org/pipermail/gcc-patches/2021-May/571033.html https://gcc.gnu.org/pipermail/gcc-patches/2021-May/571054.html As this patch removes those parts from phiopt. Note I will be looking to move two_value_replacement and value_replacement to match-and-simplify next. Note also there is one latent bug found while working on this: https://gcc.gnu.org/PR100733 . OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions and all languages. Thanks, Andrew Pinski gcc/ChangeLog: * tree-ssa-phiopt.c: Include explow.h. Fix up comment before the pass struction. (conditional_replacement): Remove function. (xor_replacement): Remove function. (match_simplify_replacement): New function. (tree_ssa_phiopt_worker): Don't call conditional_replacement or xor_replacement. Call match_simplify_replacement if everything else fails to happen. (block_with_single_simple_statement): New function. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr96928-1.c: Fix testcase for now that ~ happens on the outside of the bit_xor. --- gcc/testsuite/gcc.dg/tree-ssa/pr96928-1.c | 4 +- gcc/tree-ssa-phiopt.c | 478 ++++++++++------------ 2 files changed, 229 insertions(+), 253 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr96928-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr96928-1.c index a2770e5e896..2e86620da11 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr96928-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr96928-1.c @@ -1,9 +1,9 @@ /* PR tree-optimization/96928 */ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-phiopt2" } */ +/* { dg-options "-O2 -fdump-tree-phiopt2 -fdump-tree-optimized" } */ /* { dg-final { scan-tree-dump-times " = a_\[0-9]*\\\(D\\\) >> " 5 "phiopt2" } } */ /* { dg-final { scan-tree-dump-times " = ~c_\[0-9]*\\\(D\\\);" 1 "phiopt2" } } */ -/* { dg-final { scan-tree-dump-times " = ~" 1 "phiopt2" } } */ +/* { dg-final { scan-tree-dump-times " = ~" 1 "optimized" } } */ /* { dg-final { scan-tree-dump-times " = \[abc_0-9\\\(\\\)D]* \\\^ " 5 "phiopt2" } } */ /* { dg-final { scan-tree-dump-not "a < 0" "phiopt2" } } */ diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index f133659a781..f7c82cf192f 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -48,12 +48,11 @@ along with GCC; see the file COPYING3. If not see #include "tree-eh.h" #include "gimple-fold.h" #include "internal-fn.h" +#include "explow.h" /* For promote_mode. */ static unsigned int tree_ssa_phiopt_worker (bool, bool, bool); static bool two_value_replacement (basic_block, basic_block, edge, gphi *, tree, tree); -static bool conditional_replacement (basic_block, basic_block, - edge, edge, gphi *, tree, tree); static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree, gimple *); static int value_replacement (basic_block, basic_block, @@ -62,8 +61,6 @@ static bool minmax_replacement (basic_block, basic_block, edge, edge, gphi *, tree, tree); static bool abs_replacement (basic_block, basic_block, edge, edge, gphi *, tree, tree); -static bool xor_replacement (basic_block, basic_block, - edge, edge, gphi *, tree, tree); static bool spaceship_replacement (basic_block, basic_block, edge, edge, gphi *, tree, tree); static bool cond_removal_in_popcount_clz_ctz_pattern (basic_block, basic_block, @@ -71,6 +68,8 @@ static bool cond_removal_in_popcount_clz_ctz_pattern (basic_block, basic_block, tree, tree); static bool cond_store_replacement (basic_block, basic_block, edge, edge, hash_set<tree> *); +static bool match_simplify_replacement (basic_block, basic_block, + edge, edge, gimple_seq, bool, bool); static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); static hash_set<tree> * get_non_trapping (); static void replace_phi_edge_with_variable (basic_block, edge, gphi *, tree); @@ -319,7 +318,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p) phi = single_non_singleton_phi_for_edges (phis, e1, e2); if (!phi) - continue; + goto try_match_simplify; arg0 = gimple_phi_arg_def (phi, e1->dest_idx); arg1 = gimple_phi_arg_def (phi, e2->dest_idx); @@ -345,14 +344,9 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p) /* Do the replacement of conditional if it can be done. */ if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0, arg1)) cfgchanged = true; - else if (!early_p - && conditional_replacement (bb, bb1, e1, e2, phi, - arg0, arg1)) - cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; - else if (!early_p - && xor_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) + else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; else if (!early_p && cond_removal_in_popcount_clz_ctz_pattern (bb, bb1, e1, @@ -363,7 +357,14 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p) cfgchanged = true; else if (spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; + else + goto try_match_simplify; } + continue; +try_match_simplify: + if (match_simplify_replacement (bb, bb1, e1, e2, phi_nodes (bb2), + early_p, /*late_p = */false)) + cfgchanged = true; } free (bb_order); @@ -775,142 +776,6 @@ two_value_replacement (basic_block cond_bb, basic_block middle_bb, return true; } -/* The function conditional_replacement does the main work of doing the - conditional replacement. Return true if the replacement is done. - Otherwise return false. - BB is the basic block where the replacement is going to be done on. ARG0 - is argument 0 from PHI. Likewise for ARG1. */ - -static bool -conditional_replacement (basic_block cond_bb, basic_block middle_bb, - edge e0, edge e1, gphi *phi, - tree arg0, tree arg1) -{ - tree result; - gimple *stmt; - gassign *new_stmt; - tree cond; - gimple_stmt_iterator gsi; - edge true_edge, false_edge; - tree new_var, new_var2; - bool neg = false; - int shift = 0; - tree nonzero_arg; - - /* FIXME: Gimplification of complex type is too hard for now. */ - /* We aren't prepared to handle vectors either (and it is a question - if it would be worthwhile anyway). */ - if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0)) - || POINTER_TYPE_P (TREE_TYPE (arg0))) - || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1)) - || POINTER_TYPE_P (TREE_TYPE (arg1)))) - return false; - - /* The PHI arguments have the constants 0 and 1, or 0 and -1 or - 0 and (1 << cst), then convert it to the conditional. */ - if (integer_zerop (arg0)) - nonzero_arg = arg1; - else if (integer_zerop (arg1)) - nonzero_arg = arg0; - else - return false; - if (integer_pow2p (nonzero_arg)) - { - shift = tree_log2 (nonzero_arg); - if (shift && POINTER_TYPE_P (TREE_TYPE (nonzero_arg))) - return false; - } - else if (integer_all_onesp (nonzero_arg)) - neg = true; - else - return false; - - if (!empty_block_p (middle_bb)) - return false; - - /* At this point we know we have a GIMPLE_COND with two successors. - One successor is BB, the other successor is an empty block which - falls through into BB. - - There is a single PHI node at the join point (BB) and its arguments - are constants (0, 1) or (0, -1) or (0, (1 << shift)). - - So, given the condition COND, and the two PHI arguments, we can - rewrite this PHI into non-branching code: - - dest = (COND) or dest = COND' or dest = (COND) << shift - - We use the condition as-is if the argument associated with the - true edge has the value one or the argument associated with the - false edge as the value zero. Note that those conditions are not - the same since only one of the outgoing edges from the GIMPLE_COND - will directly reach BB and thus be associated with an argument. */ - - stmt = last_stmt (cond_bb); - result = PHI_RESULT (phi); - - /* To handle special cases like floating point comparison, it is easier and - less error-prone to build a tree and gimplify it on the fly though it is - less efficient. */ - cond = fold_build2_loc (gimple_location (stmt), - gimple_cond_code (stmt), boolean_type_node, - gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - - /* We need to know which is the true edge and which is the false - edge so that we know when to invert the condition below. */ - extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); - if ((e0 == true_edge && integer_zerop (arg0)) - || (e0 == false_edge && !integer_zerop (arg0)) - || (e1 == true_edge && integer_zerop (arg1)) - || (e1 == false_edge && !integer_zerop (arg1))) - cond = fold_build1_loc (gimple_location (stmt), - TRUTH_NOT_EXPR, TREE_TYPE (cond), cond); - - if (neg) - { - cond = fold_convert_loc (gimple_location (stmt), - TREE_TYPE (result), cond); - cond = fold_build1_loc (gimple_location (stmt), - NEGATE_EXPR, TREE_TYPE (cond), cond); - } - else if (shift) - { - cond = fold_convert_loc (gimple_location (stmt), - TREE_TYPE (result), cond); - cond = fold_build2_loc (gimple_location (stmt), - LSHIFT_EXPR, TREE_TYPE (cond), cond, - build_int_cst (integer_type_node, shift)); - } - - /* Insert our new statements at the end of conditional block before the - COND_STMT. */ - gsi = gsi_for_stmt (stmt); - new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true, - GSI_SAME_STMT); - - if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var))) - { - location_t locus_0, locus_1; - - new_var2 = make_ssa_name (TREE_TYPE (result)); - new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var); - gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); - new_var = new_var2; - - /* Set the locus to the first argument, unless is doesn't have one. */ - locus_0 = gimple_phi_arg_location (phi, 0); - locus_1 = gimple_phi_arg_location (phi, 1); - if (locus_0 == UNKNOWN_LOCATION) - locus_0 = locus_1; - gimple_set_location (new_stmt, locus_0); - } - - replace_phi_edge_with_variable (cond_bb, e1, phi, new_var); - - /* Note that we optimized this PHI. */ - return true; -} - /* Update *ARG which is defined in STMT so that it contains the computed value if that seems profitable. Return true if the statement is made dead by that rewriting. */ @@ -1413,6 +1278,219 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, return 0; } +/* Return true if basic block BB has no statements or + a statement (that has no side effects) with one cheap + preparation statement. Const/pure functions can only be the last + statmenent. */ +static bool +block_with_single_simple_statement (basic_block bb, gimple **stmt) +{ + /* BB must have no executable statements. */ + gimple *stmt1; + gimple_stmt_iterator gsi = gsi_after_labels (bb); + *stmt = NULL; + if (phi_nodes (bb)) + return false; + if (gsi_end_p (gsi)) + return true; + if (is_gimple_debug (gsi_stmt (gsi))) + gsi_next_nondebug (&gsi); + if (gsi_end_p (gsi)) + return true; + stmt1 = gsi_stmt (gsi); + gsi_next_nondebug (&gsi); + if (!gsi_end_p (gsi)) + return false; + if (gimple_could_trap_p (stmt1)) + return false; + if (gimple_has_side_effects (stmt1)) + return false; + *stmt = stmt1; + if (is_gimple_assign (stmt1) + && TREE_CODE (gimple_assign_lhs (stmt1)) == SSA_NAME) + return true; + if (is_gimple_call (stmt1) + && gimple_inexpensive_call_p (as_a <gcall *> (stmt1))) + return true; + return false; +} + +/* The function match_simplify_replacement does the main work of using the + match and simplify infastructure to do the replacement. Return true if the replacement is done. Otherwise return false. + BB is the basic block where the replacement is going to be done on. ARG0 + is argument 0 from the PHI. Likewise for ARG1. */ + +static bool +match_simplify_replacement (basic_block cond_bb, basic_block middle_bb, + edge e0, edge e1, gimple_seq phis, bool early_p, + bool late_p) +{ + gimple *stmt; + edge true_edge, false_edge; + tree cond; + tree type; + gimple_stmt_iterator gsi; + int reverse = false; + gimple *stmt_to_move; + gimple_seq seq = NULL; + bool allhappened = true; + bool happened_once = false; + auto_vec<std::pair<gimple *,tree>, 4> changedphis; + + if (!block_with_single_simple_statement (middle_bb, &stmt_to_move)) + return false; + + /* If there is a statement to move and is early, then don't do. */ + if (early_p && stmt_to_move) + return false; + + stmt = last_stmt (cond_bb); + + /* We need to know which is the true edge and which is the false + edge so that we know if have abs or negative abs. */ + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); + if (e1 == true_edge || e0 == false_edge) + reverse = true; + + /* Don't use fold_build2 here as that might create (bool)a instead of just + "a != 0". */ + cond = build2_loc (gimple_location (stmt), gimple_cond_code (stmt), + boolean_type_node, gimple_cond_lhs (stmt), + gimple_cond_rhs (stmt)); + + for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *p = gsi_stmt (gsi); + tree conditional; + tree arg0, arg1; + gimple_seq seq1 = NULL; + bool happened = false; + + /* If the PHI arguments are equal then we can skip this PHI. */ + arg0 = gimple_phi_arg_def (p, e0->dest_idx); + arg1 = gimple_phi_arg_def (p, e1->dest_idx); + + /* Skip the equal case as it will be optimize to the same thing. */ + if (operand_equal_for_phi_arg_p (arg0, arg1)) + continue; + + if (reverse) + std::swap (arg0, arg1); + + type = TREE_TYPE (gimple_phi_result (p)); + + conditional = gimple_simplify (COND_EXPR, type, + unshare_expr (cond), + arg0, arg1, + &seq1, NULL); + + /* If we did not simplify, then emit a COND_EXPR if we can. */ + if (!conditional) + { + gimple *stmt; + + /* Only emit a COND_EXPR if this is the late PHI-OPT. */ + if (!late_p) + { + /* Note some transformations can happen even without having + extra staments. */ + allhappened = false; + continue; + } + + if (!can_conditionally_move_p (TYPE_MODE (TREE_TYPE (PHI_RESULT (p))))) + { + tree type = TREE_TYPE (PHI_RESULT (p)); + enum machine_mode mode = TYPE_MODE (type); + int unsignedp = TYPE_UNSIGNED (type); + mode = promote_mode (type, mode, &unsignedp); + if (!can_conditionally_move_p (mode)) + { + allhappened = false; + continue; + } + } + /* Manually create the final assignment so the aliasing info + for the ssa name will be up todate. */ + conditional = duplicate_ssa_name (PHI_RESULT (p), NULL); + stmt = gimple_build_assign (conditional, COND_EXPR, + unshare_expr (cond), arg0, arg1); + gimple_seq_add_stmt_without_update (&seq1, stmt); + } + /* If the simplification can be done without any extra statement, + do this transformation all the time. + For an example a == 0 ? 0 : a -> a . + This requires there to be no statement to be moved as: + a == 0 ? 0 : (t = a * b) will be replaced with just t and then + later on the statement might not be moved. */ + if (!seq1 && !stmt_to_move) + { + /* Set both of the edges of the PHI node to be the result. */ + SET_USE (PHI_ARG_DEF_PTR (p, e1->dest_idx), conditional); + SET_USE (PHI_ARG_DEF_PTR (p, e0->dest_idx), conditional); + happened = true; + } + else if (early_p || !allhappened) + { + happened = false; + allhappened = false; + } + else + { + gimple_seq_add_seq_without_update (&seq, seq1); + changedphis.safe_push (std::make_pair (p, conditional)); + happened = true; + } + + if (happened && dump_file && (dump_flags & TDF_DETAILS)) + { + if (!seq1 && !stmt_to_move) + fprintf (dump_file, "Committed: "); + fprintf (dump_file, "PHI "); + print_generic_expr (dump_file, gimple_phi_result (p)); + fprintf (dump_file, + " trying change to straight line code for COND_EXPR in block %d: COND_EXPR: ", + cond_bb->index); + print_generic_expr (dump_file, cond); + fprintf (dump_file, "PHI elements to: "); + print_generic_expr (dump_file, conditional); + fprintf (dump_file, "\n"); + } + happened_once |= happened; + } + + if (!happened_once || !allhappened) + return false; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "commited the above changes.\n"); + + for(auto phi_to_change : changedphis) + { + gimple *phi = phi_to_change.first; + tree conditional = phi_to_change.second; + /* Set both of the edges of the PHI node to be the result. */ + SET_USE (PHI_ARG_DEF_PTR (phi, e1->dest_idx), conditional); + SET_USE (PHI_ARG_DEF_PTR (phi, e0->dest_idx), conditional); + } + + gsi = gsi_for_stmt (stmt); + if (stmt_to_move) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "statement un-sinked:\n"); + print_gimple_stmt (dump_file, stmt_to_move, 0, + TDF_VOPS|TDF_MEMSYMS); + } + gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt_to_move); + gsi_move_before (&gsi1, &gsi); + } + + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); + return true; +} + /* The function minmax_replacement does the main work of doing the minmax replacement. Return true if the replacement is done. Otherwise return false. @@ -2649,108 +2727,6 @@ abs_replacement (basic_block cond_bb, basic_block middle_bb, return true; } -/* Optimize x < 0 ? ~y : y into (x >> (prec-1)) ^ y. */ - -static bool -xor_replacement (basic_block cond_bb, basic_block middle_bb, - edge e0 ATTRIBUTE_UNUSED, edge e1, - gphi *phi, tree arg0, tree arg1) -{ - if (!INTEGRAL_TYPE_P (TREE_TYPE (arg1))) - return false; - - /* OTHER_BLOCK must have only one executable statement which must have the - form arg0 = ~arg1 or arg1 = ~arg0. */ - - gimple *assign = last_and_only_stmt (middle_bb); - /* If we did not find the proper one's complement assignment, then we cannot - optimize. */ - if (assign == NULL) - return false; - - /* If we got here, then we have found the only executable statement - in OTHER_BLOCK. If it is anything other than arg = ~arg1 or - arg1 = ~arg0, then we cannot optimize. */ - if (!is_gimple_assign (assign)) - return false; - - if (gimple_assign_rhs_code (assign) != BIT_NOT_EXPR) - return false; - - tree lhs = gimple_assign_lhs (assign); - tree rhs = gimple_assign_rhs1 (assign); - - /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */ - if (!(lhs == arg0 && rhs == arg1) && !(lhs == arg1 && rhs == arg0)) - return false; - - gimple *cond = last_stmt (cond_bb); - tree result = PHI_RESULT (phi); - - /* Only relationals comparing arg[01] against zero are interesting. */ - enum tree_code cond_code = gimple_cond_code (cond); - if (cond_code != LT_EXPR && cond_code != GE_EXPR) - return false; - - /* Make sure the conditional is x OP 0. */ - tree clhs = gimple_cond_lhs (cond); - if (TREE_CODE (clhs) != SSA_NAME - || !INTEGRAL_TYPE_P (TREE_TYPE (clhs)) - || TYPE_UNSIGNED (TREE_TYPE (clhs)) - || TYPE_PRECISION (TREE_TYPE (clhs)) != TYPE_PRECISION (TREE_TYPE (arg1)) - || !integer_zerop (gimple_cond_rhs (cond))) - return false; - - /* We need to know which is the true edge and which is the false - edge so that we know if have xor or inverted xor. */ - edge true_edge, false_edge; - extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); - - /* For GE_EXPR, if the true edge goes to OTHER_BLOCK, then we - will need to invert the result. Similarly for LT_EXPR if - the false edge goes to OTHER_BLOCK. */ - edge e; - if (cond_code == GE_EXPR) - e = true_edge; - else - e = false_edge; - - bool invert = e->dest == middle_bb; - - result = duplicate_ssa_name (result, NULL); - - gimple_stmt_iterator gsi = gsi_last_bb (cond_bb); - - int prec = TYPE_PRECISION (TREE_TYPE (clhs)); - gimple *new_stmt - = gimple_build_assign (make_ssa_name (TREE_TYPE (clhs)), RSHIFT_EXPR, clhs, - build_int_cst (integer_type_node, prec - 1)); - gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); - - if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (clhs))) - { - new_stmt = gimple_build_assign (make_ssa_name (TREE_TYPE (result)), - NOP_EXPR, gimple_assign_lhs (new_stmt)); - gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); - } - lhs = gimple_assign_lhs (new_stmt); - - if (invert) - { - new_stmt = gimple_build_assign (make_ssa_name (TREE_TYPE (result)), - BIT_NOT_EXPR, rhs); - gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); - rhs = gimple_assign_lhs (new_stmt); - } - - new_stmt = gimple_build_assign (result, BIT_XOR_EXPR, lhs, rhs); - gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); - - replace_phi_edge_with_variable (cond_bb, e1, phi, result); - - /* Note that we optimized this PHI. */ - return true; -} /* Auxiliary functions to determine the set of memory accesses which can't trap because they are preceded by accesses to the same memory @@ -3618,8 +3594,8 @@ gate_hoist_loads (void) Conditional Replacement ----------------------- - This transformation, implemented in conditional_replacement, - replaces + This transformation, using the match and simplify infastructure and implemented in + match_simplify_replacement, replaces bb0: if (cond) goto bb2; else goto bb1; -- 2.17.1
