* [PATCH] Use match-and-simplify in phi-opt
@ 2021-05-24 1:45 apinski
2021-05-25 13:41 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: apinski @ 2021-05-24 1:45 UTC (permalink / raw)
To: gcc-patches; +Cc: Andrew Pinski
From: Andrew Pinski <apinski@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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] Use match-and-simplify in phi-opt
2021-05-24 1:45 [PATCH] Use match-and-simplify in phi-opt apinski
@ 2021-05-25 13:41 ` Richard Biener
2021-06-01 0:49 ` Andrew Pinski
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2021-05-25 13:41 UTC (permalink / raw)
To: apinski; +Cc: GCC Patches
On Mon, May 24, 2021 at 4:09 AM apinski--- via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> From: Andrew Pinski <apinski@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;
Can we do this in steps please? First only handle
single_non_singleton_phi_for_edges,
thus a plain else if (!early_p && ...) in the above chain? In particular ...
> }
>
> 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))
It feels like we must have two or three "similar" copies of such function around
already ...?
> + 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. */
... this is now general (late) if-conversion on GIMPLE which should be done
separately. In particular when dealing with multiple PHIs it needs some
better cost modeling IMHO.
What's the reason you want to push it with this general change?
So I'd like to have an initially simpler approach of just replacing some of the
handling by match.pd patterns after which we could see to handle multiple PHIs
in general - even the other matchers could benefit from that (but I see some
refactoring necessary to have a analysis and a transform stage, maybe just
an added bool to the functions...).
Thanks for working on this,
Richard.
> + 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
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] Use match-and-simplify in phi-opt
2021-05-25 13:41 ` Richard Biener
@ 2021-06-01 0:49 ` Andrew Pinski
0 siblings, 0 replies; 3+ messages in thread
From: Andrew Pinski @ 2021-06-01 0:49 UTC (permalink / raw)
To: Richard Biener; +Cc: Andrew Pinski, GCC Patches
On Tue, May 25, 2021 at 7:12 AM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Mon, May 24, 2021 at 4:09 AM apinski--- via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > From: Andrew Pinski <apinski@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;
>
> Can we do this in steps please? First only handle
> single_non_singleton_phi_for_edges,
> thus a plain else if (!early_p && ...) in the above chain? In particular ...
Yes I agree. These are the steps I am going to take to begin with:
* match and simplify with an empty basic block, to be able to remove
conditional_replacement
* add support for non-empty basic block, to be able to remove xor_replacement
* and then see if the non-single_non_singleton_phi_for_edges case is
still needed.
* and then add the conditional move support
I should have the first patch done by tomorrow; just finish writing
it, it is much shorter.
Thanks,
Andrew Pinski
>
> > }
> >
> > 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))
>
> It feels like we must have two or three "similar" copies of such function around
> already ...?
>
> > + 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. */
>
> ... this is now general (late) if-conversion on GIMPLE which should be done
> separately. In particular when dealing with multiple PHIs it needs some
> better cost modeling IMHO.
>
> What's the reason you want to push it with this general change?
>
> So I'd like to have an initially simpler approach of just replacing some of the
> handling by match.pd patterns after which we could see to handle multiple PHIs
> in general - even the other matchers could benefit from that (but I see some
> refactoring necessary to have a analysis and a transform stage, maybe just
> an added bool to the functions...).
>
> Thanks for working on this,
> Richard.
>
> > + 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
> >
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2021-06-01 0:50 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-24 1:45 [PATCH] Use match-and-simplify in phi-opt apinski
2021-05-25 13:41 ` Richard Biener
2021-06-01 0:49 ` Andrew Pinski
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).