Testcases for match.pd patterns
`((a ^ b) & c) cmp d | a != b -> (0 cmp d | a != b)` and
`(a ^ b) cmp c | a != b -> (0 cmp c | a != b)` were failing on some targets,
like PowerPC.
This patch adds an implementation for the optimization in reassoc. Doing so,
we can now handle cases where the related conditions appear in an AND
expression too. Also, we can optimize cases where we have intermediate
expressions between the related ones in the AND/OR expression on some targets.
This is not handled on targets like PowerPC, where each condition of the
AND/OR expression is placed into a different basic block.
Bootstrapped/regtested on x86, AArch64 and PowerPC.
PR tree-optimization/116860
gcc/ChangeLog:
* tree-ssa-reassoc.cc (solve_expr): New function.
(find_terminal_nodes): New function.
(ssa_name_cmp): New function.
(stmt_uid_cmp): New function.
(copy_hashset_to_vec_and_sort): New function.
(optimize_cmp_xor_exprs): New function.
(optimize_range_tests): Add CURR_BB parameter; pass it through
to optimize_cmp_xor_exprs.
(maybe_optimize_range_tests): Adjust optimize_range_tests call.
(reassociate_bb): Likewise; pass the AND/OR statement's BB.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/fold-xor-and-or.c:
Remove logical-op-non-short-circuit=1; broaden XOR scan regex.
* gcc.dg/tree-ssa/fold-xor-or.c: Likewise.
* gcc.dg/tree-ssa/fold-xor-and-or-2.c: New test.
* gcc.dg/tree-ssa/fold-xor-and.c: New test.
---
Changes in v7:
- solve_expr: use vec<> *calc_stmts, not auto_vec<>.
- Replace sort_elements<> specializations with named comparators
passed into copy_hashset_to_vec_and_sort.
- Pred walk: drop redundant terms_in_preds.
Changes in v6:
- sort_elements: explicit three-way comparison instead of subtraction
(avoids the overflow-prone qsort idiom).
- find_terminal_nodes, solve_expr: drop dead !def_stmt and is_gimple_debug
guards; SSA_NAME_DEF_STMT never returns NULL.
- Fold loop: rename shadowed inner index to j.
- solve_expr: note that STMTS_TO_FOLD accumulates independently of the
return value.
- GNU style fixups in tests.
Changes in v5:
- sort_elements<tree>: assert SSA_NAME precondition on operands. The
find_terminal_nodes sets, which may hold non-SSA_NAMEs, are never sorted.
- solve_expr: drop unused gimple_assign_rhs3 reads.
- Pred-walk: polarity-gate cond_lhs for EQ/NE defs.
- Pred-walk: anchor on the AND/OR stmt's BB (deterministic).
- solve_expr: require has_single_use before queueing a fold.
- solve_expr: canonicalize replace_uses_by before gsi_remove.
- solve_expr: skip already-folded SSAs across overlapping sets.
- solve_expr: simplify single-element removal; drop dead post-loop
VEC_ORDERED_REMOVE_IF.
- OR fold loop: drop matched operand instead of truncating chain.
- Pre-compute terminal_nodes once; drop hash_set copies.
- copy_hashset_to_vec_and_sort: out-parameter; fix vec<T> leaks.
- Drop dead solved_exprs.
- Broaden fold-xor scan regex to both XOR operand orders.
.../gcc.dg/tree-ssa/fold-xor-and-or-2.c | 59 +++
.../gcc.dg/tree-ssa/fold-xor-and-or.c | 22 +-
gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and.c | 55 +++
gcc/testsuite/gcc.dg/tree-ssa/fold-xor-or.c | 22 +-
gcc/tree-ssa-reassoc.cc | 462 +++++++++++++++++-
5 files changed, 594 insertions(+), 26 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or-2.c
new file mode 100644
index 000000000000..51cb73c6b51b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or-2.c
@@ -0,0 +1,59 @@
+/* This test is not working across all targets (e.g. it fails on PowerPC,
+ because each condition of the AND/OR expression is placed into
+ a different basic block). Therefore, it is gated for x86-64 and AArch64,
+ where we know that it has to pass. */
+/* { dg-do compile { target { aarch64-*-* x86_64-*-* } } } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+typedef unsigned long int uint64_t;
+
+int cmp1_or_inter (int d1, int d2, int d3) {
+ if (((d1 ^ d2) & 0xabcd) == 0 || d3 != 10 || d1 != d2)
+ return 0;
+ return 1;
+}
+
+int cmp2_or_inter (int d1, int d2, int d3, int d4) {
+ if (((d1 ^ d2) & 0xabcd) == 0 || d3 != 10 || d1 != d2 || d4 == 11)
+ return 0;
+ return 1;
+}
+
+int cmp1_and_inter (int d1, int d2, int d3) {
+ if (!(((d1 ^ d2) & 0xabcd) == 0) && d3 == 10 && d1 == d2)
+ return 0;
+ return 1;
+}
+
+int cmp2_and_inter (int d1, int d2, int d3, int d4) {
+ if (!(((d1 ^ d2) & 0xabcd) == 0) && d3 == 10 && d1 == d2 && d4 != 11)
+ return 0;
+ return 1;
+}
+
+int cmp1_or_inter_64 (uint64_t d1, uint64_t d2, uint64_t d3) {
+ if (((d1 ^ d2) & 0xabcd) == 0 || d3 != 10 || d1 != d2)
+ return 0;
+ return 1;
+}
+
+int cmp2_or_inter_64 (uint64_t d1, uint64_t d2, uint64_t d3, uint64_t d4) {
+ if (((d1 ^ d2) & 0xabcd) == 0 || d3 != 10 || d1 != d2 || d4 == 11)
+ return 0;
+ return 1;
+}
+
+int cmp1_and_inter_64 (uint64_t d1, uint64_t d2, uint64_t d3) {
+ if (!(((d1 ^ d2) & 0xabcd) == 0) && d3 == 10 && d1 == d2)
+ return 0;
+ return 1;
+}
+
+int cmp2_and_inter_64 (uint64_t d1, uint64_t d2, uint64_t d3, uint64_t d4) {
+ if (!(((d1 ^ d2) & 0xabcd) == 0) && d3 == 10 && d1 == d2 && d4 != 11)
+ return 0;
+ return 1;
+}
+
+/* The if should be removed, so the condition should not exist. */
+/* { dg-final { scan-tree-dump-not "(d1_\[0-9\]+.D. \\^
d2_\[0-9\]+.D.|d2_\[0-9\]+.D. \\^ d1_\[0-9\]+.D.)" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or.c
b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or.c
index 99e83d8e5aae..c34fa844b6f4 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and-or.c
@@ -1,55 +1,55 @@
/* { dg-do compile } */
-/* { dg-options "-O3 -fdump-tree-optimized --param
logical-op-non-short-circuit=1" } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
typedef unsigned long int uint64_t;
-int cmp1(int d1, int d2) {
+int cmp1 (int d1, int d2) {
if (((d1 ^ d2) & 0xabcd) == 0 || d1 != d2)
return 0;
return 1;
}
-int cmp2(int d1, int d2) {
+int cmp2 (int d1, int d2) {
if (d1 != d2 || ((d1 ^ d2) & 0xabcd) == 0)
return 0;
return 1;
}
-int cmp3(int d1, int d2) {
+int cmp3 (int d1, int d2) {
if (10 > (0xabcd & (d2 ^ d1)) || d2 != d1)
return 0;
return 1;
}
-int cmp4(int d1, int d2) {
+int cmp4 (int d1, int d2) {
if (d2 != d1 || 10 > (0xabcd & (d2 ^ d1)))
return 0;
return 1;
}
-int cmp1_64(uint64_t d1, uint64_t d2) {
+int cmp1_64 (uint64_t d1, uint64_t d2) {
if (((d1 ^ d2) & 0xabcd) == 0 || d1 != d2)
return 0;
return 1;
}
-int cmp2_64(uint64_t d1, uint64_t d2) {
+int cmp2_64 (uint64_t d1, uint64_t d2) {
if (d1 != d2 || ((d1 ^ d2) & 0xabcd) == 0)
return 0;
return 1;
}
-int cmp3_64(uint64_t d1, uint64_t d2) {
+int cmp3_64 (uint64_t d1, uint64_t d2) {
if (10 > (0xabcd & (d2 ^ d1)) || d2 != d1)
return 0;
return 1;
}
-int cmp4_64(uint64_t d1, uint64_t d2) {
+int cmp4_64 (uint64_t d1, uint64_t d2) {
if (d2 != d1 || 10 > (0xabcd & (d2 ^ d1)))
return 0;
return 1;
}
-/* The if should be removed, so the condition should not exist */
-/* { dg-final { scan-tree-dump-not "d1_\[0-9\]+.D. \\^ d2_\[0-9\]+.D."
"optimized" } } */
+/* The if should be removed, so the condition should not exist. */
+/* { dg-final { scan-tree-dump-not "(d1_\[0-9\]+.D. \\^
d2_\[0-9\]+.D.|d2_\[0-9\]+.D. \\^ d1_\[0-9\]+.D.)" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and.c
b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and.c
new file mode 100644
index 000000000000..7c26bd404ab0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-and.c
@@ -0,0 +1,55 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+typedef unsigned long int uint64_t;
+
+int cmp1 (int d1, int d2) {
+ if (!((d1 ^ d2) == 0xabcd) && d1 == d2)
+ return 0;
+ return 1;
+}
+
+int cmp2 (int d1, int d2) {
+ if (d1 == d2 && !((d1 ^ d2) == 0xabcd))
+ return 0;
+ return 1;
+}
+
+int cmp3 (int d1, int d2) {
+ if (!(((d1 ^ d2) & 0xabcd) == 0) && d1 == d2)
+ return 0;
+ return 1;
+}
+
+int cmp4 (int d1, int d2) {
+ if (d1 == d2 && !(((d1 ^ d2) & 0xabcd) == 0))
+ return 0;
+ return 1;
+}
+
+int cmp1_64 (uint64_t d1, uint64_t d2) {
+ if (!((d1 ^ d2) == 0xabcd) && d1 == d2)
+ return 0;
+ return 1;
+}
+
+int cmp2_64 (uint64_t d1, uint64_t d2) {
+ if (d1 == d2 && !((d1 ^ d2) == 0xabcd))
+ return 0;
+ return 1;
+}
+
+int cmp3_64 (uint64_t d1, uint64_t d2) {
+ if (!(((d1 ^ d2) & 0xabcd) == 0) && d1 == d2)
+ return 0;
+ return 1;
+}
+
+int cmp4_64 (uint64_t d1, uint64_t d2) {
+ if (d1 == d2 && !(((d1 ^ d2) & 0xabcd) == 0))
+ return 0;
+ return 1;
+}
+
+/* The if should be removed, so the condition should not exist. */
+/* { dg-final { scan-tree-dump-not "(d1_\[0-9\]+.D. \\^
d2_\[0-9\]+.D.|d2_\[0-9\]+.D. \\^ d1_\[0-9\]+.D.)" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-or.c
b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-or.c
index 51b7373af0d8..d9b77c39a480 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-or.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fold-xor-or.c
@@ -1,55 +1,55 @@
/* { dg-do compile } */
-/* { dg-options "-O3 -fdump-tree-optimized --param
logical-op-non-short-circuit=1" } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
typedef unsigned long int uint64_t;
-int cmp1(int d1, int d2) {
+int cmp1 (int d1, int d2) {
if ((d1 ^ d2) == 0xabcd || d1 != d2)
return 0;
return 1;
}
-int cmp2(int d1, int d2) {
+int cmp2 (int d1, int d2) {
if (d1 != d2 || (d1 ^ d2) == 0xabcd)
return 0;
return 1;
}
-int cmp3(int d1, int d2) {
+int cmp3 (int d1, int d2) {
if (0xabcd > (d2 ^ d1) || d2 != d1)
return 0;
return 1;
}
-int cmp4(int d1, int d2) {
+int cmp4 (int d1, int d2) {
if (d2 != d1 || 0xabcd > (d2 ^ d1))
return 0;
return 1;
}
-int cmp1_64(uint64_t d1, uint64_t d2) {
+int cmp1_64 (uint64_t d1, uint64_t d2) {
if ((d1 ^ d2) == 0xabcd || d1 != d2)
return 0;
return 1;
}
-int cmp2_64(uint64_t d1, uint64_t d2) {
+int cmp2_64 (uint64_t d1, uint64_t d2) {
if (d1 != d2 || (d1 ^ d2) == 0xabcd)
return 0;
return 1;
}
-int cmp3_64(uint64_t d1, uint64_t d2) {
+int cmp3_64 (uint64_t d1, uint64_t d2) {
if (0xabcd > (d2 ^ d1) || d2 != d1)
return 0;
return 1;
}
-int cmp4_64(uint64_t d1, uint64_t d2) {
+int cmp4_64 (uint64_t d1, uint64_t d2) {
if (d2 != d1 || 0xabcd > (d2 ^ d1))
return 0;
return 1;
}
-/* The if should be removed, so the condition should not exist */
-/* { dg-final { scan-tree-dump-not "d1_\[0-9\]+.D. \\^ d2_\[0-9\]+.D."
"optimized" } } */
+/* The if should be removed, so the condition should not exist. */
+/* { dg-final { scan-tree-dump-not "(d1_\[0-9\]+.D. \\^
d2_\[0-9\]+.D.|d2_\[0-9\]+.D. \\^ d1_\[0-9\]+.D.)" "optimized" } } */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index 4b47fb20f3a7..419acccead4f 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -4043,6 +4043,455 @@ optimize_range_tests_var_bound (enum tree_code opcode,
int first, int length,
return any_changes;
}
+/* Helper function for optimize_cmp_xor_exprs. Visit EXPR operands
+ recursively and try to find comparison or XOR expressions that can be
+ solved using the expressions in CALC_STMTS. Expressions that can be folded
+ to 0 are stored in STMTS_TO_FOLD. IS_OR_EXPR is true for OR expressions
+ and false for AND expressions.
+
+ Return EXPR if it is a terminal node, otherwise NULL_TREE. Only the
+ recursion uses this return value, to count terminal operands.
+ STMTS_TO_FOLD accumulates independently of the return value, so a
+ recursive call may queue a fold there and still return NULL_TREE. */
+
+static tree
+solve_expr (tree expr, vec<gimple *> *calc_stmts,
+ hash_set<gimple *> *stmts_to_fold, hash_set<tree> *visited,
+ bool is_or_expr)
+{
+ /* Return, if have already visited this expression or the expression is not
+ an SSA name. */
+ if (TREE_CODE (expr) != SSA_NAME || visited->add (expr))
+ return NULL_TREE;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
+
+ if (!is_gimple_assign (def_stmt))
+ return expr;
+
+ unsigned int op_num = gimple_num_ops (def_stmt);
+ unsigned int terminal_node_num = 0;
+ /* Visit the expression operands recursively until finding a statement that
+ all of its operands are terminal nodes. */
+ for (unsigned i = 1; i < op_num; ++i)
+ {
+ tree op = gimple_op (def_stmt, i);
+ if (!op)
+ continue;
+ tree solve_result = solve_expr (op, calc_stmts, stmts_to_fold, visited,
+ is_or_expr);
+ if (solve_result == op)
+ terminal_node_num++;
+ }
+
+ /* Check if all of the operands are terminal nodes. */
+ if (terminal_node_num != op_num - 1)
+ return NULL_TREE;
+
+ tree_code def_code = gimple_assign_rhs_code (def_stmt);
+ /* XOR and NE expressions are handled in a similar manner. */
+ if (def_code == BIT_XOR_EXPR)
+ def_code = NE_EXPR;
+
+ tree def_lhs = gimple_assign_lhs (def_stmt);
+ tree def_op1 = gimple_assign_rhs1 (def_stmt);
+ tree def_op2 = gimple_assign_rhs2 (def_stmt);
+
+ /* Find possible statements in calc_stmts that can solve the current
+ expression. We are looking for statements with the same operation and
+ the same operands as the current one in case of an OR expression, or
+ a statement using the inverse operation of the current one, with the same
+ operands, in case of an AND expression. */
+ unsigned int i;
+ gimple *stmt;
+ FOR_EACH_VEC_ELT (*calc_stmts, i, stmt)
+ {
+ tree_code stmt_rhs_code = gimple_assign_rhs_code (stmt);
+ tree_code inverted_code
+ = invert_tree_comparison (stmt_rhs_code,
+ HONOR_NANS (TREE_TYPE (expr)));
+ if (((is_or_expr && def_code == stmt_rhs_code)
+ || (!is_or_expr && def_code == inverted_code))
+ && gimple_assign_lhs (stmt) != def_lhs
+ && gimple_assign_rhs1 (stmt) == def_op1
+ && gimple_assign_rhs2 (stmt) == def_op2)
+ {
+ /* In case of an AND expression, where the related terms are in
+ different blocks, fold the term that is dominated by the
+ other. This ensures the correct handling of cases where
+ a related term may not be part of the AND expression, but
+ only happens to be inside the `if` statement's block. The
+ fold uses replace_uses_by which rewrites the matched lhs
+ globally; require a single use so the rewrite is
+ chain-local. */
+ if (is_or_expr
+ || gimple_bb (stmt) == gimple_bb (def_stmt)
+ || reassoc_stmt_dominates_stmt_p (stmt, def_stmt))
+ {
+ if (!has_single_use (def_lhs))
+ return NULL_TREE;
+ stmts_to_fold->add (def_stmt);
+ }
+ else if (reassoc_stmt_dominates_stmt_p (def_stmt, stmt))
+ {
+ if (!has_single_use (gimple_assign_lhs (stmt)))
+ return NULL_TREE;
+ stmts_to_fold->add (stmt);
+ /* STMT has been queued for folding; drop it from calc_stmts so
+ later iterations do not match against it. */
+ calc_stmts->ordered_remove (i);
+ }
+
+ return expr;
+ }
+ }
+
+ return NULL_TREE;
+}
+
+/* Helper function for optimize_cmp_xor_exprs. Unfold EXPR and get the
+ terminal nodes in which it is analyzed. */
+
+static void
+find_terminal_nodes (tree expr, hash_set<tree> *terminal_nodes,
+ hash_set<tree> *visited)
+{
+ if (visited->add (expr))
+ return;
+
+ if (TREE_CODE (expr) != SSA_NAME)
+ {
+ terminal_nodes->add (expr);
+ return;
+ }
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
+
+ if (!is_gimple_assign (def_stmt))
+ {
+ terminal_nodes->add (expr);
+ return;
+ }
+
+ /* Visit the expression operands recursively. */
+ unsigned int op_num = gimple_num_ops (def_stmt);
+ for (unsigned i = 1; i < op_num; ++i)
+ {
+ tree op = gimple_op (def_stmt, i);
+ if (!op)
+ continue;
+ find_terminal_nodes (op, terminal_nodes, visited);
+ }
+}
+
+/* Comparator for sorting an array of SSA_NAMEs by version. */
+
+static int
+ssa_name_cmp (const void *p1, const void *p2)
+{
+ const tree t1 = *(const tree *) p1;
+ const tree t2 = *(const tree *) p2;
+
+ gcc_checking_assert (TREE_CODE (t1) == SSA_NAME
+ && TREE_CODE (t2) == SSA_NAME);
+
+ if (SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2))
+ return -1;
+ else if (SSA_NAME_VERSION (t1) > SSA_NAME_VERSION (t2))
+ return 1;
+ return 0;
+}
+
+/* Comparator for sorting an array of gimple statements by UID. */
+
+static int
+stmt_uid_cmp (const void *p1, const void *p2)
+{
+ const gimple *s1 = *(const gimple *const *) p1;
+ const gimple *s2 = *(const gimple *const *) p2;
+
+ if (gimple_uid (s1) < gimple_uid (s2))
+ return -1;
+ else if (gimple_uid (s1) > gimple_uid (s2))
+ return 1;
+ return 0;
+}
+
+/* Copy HASHSET into VECT and sort it using CMP. */
+
+template<typename T>
+static void
+copy_hashset_to_vec_and_sort (const hash_set<T> &hashset, vec<T> *vect,
+ int (*cmp) (const void *, const void *))
+{
+ vect->reserve (hashset.elements ());
+ for (const T term : hashset)
+ vect->quick_push (term);
+
+ vect->qsort (cmp);
+}
+
+/* Optimize boolean expressions containing comparisons or xor expressions and
+ the value of one term in the expression implies the value of another, like
+ the following:
+ ((d1 ^ d2) & 0xabcd) == 0 | d1 != d2 --> (0 & 0xabcd) == 0 | d1 != d2,
+ which will later be simplified to true.
+ (d1 ^ d2) == 0xabcd | d1 != d2 --> 0 == 0xabcd | d1 != d2,
+ which will later be simplified to d1 != d2.
+ ((d1 ^ d2) & 0xabcd) == 0 | d3 != 10 | d1 != d2 -->
+ (0 & 0xabcd) == 0 | d3 != 10 | d1 != d2,
+ which will later be simplified to true. */
+
+static bool
+optimize_cmp_xor_exprs (tree_code opcode, vec<operand_entry *> *ops,
+ basic_block curr_bb)
+{
+ auto_vec<vec<tree>> op_subexprsets;
+ bool is_or_expr = opcode == BIT_IOR_EXPR;
+ bool any_changes = false;
+
+ if (!is_or_expr && opcode != BIT_AND_EXPR)
+ return false;
+
+ /* Iterate over the operands in the AND/OR expression and keep those that
+ are SSA names. */
+ hash_set<tree> expr_terms;
+ for (operand_entry *oe : ops)
+ {
+ tree op = oe->op;
+ if (TREE_CODE (op) == SSA_NAME)
+ expr_terms.add (op);
+ }
+
+ /* Find related terms to the AND/OR expression in CURR_BB's predecessors.
+ CURR_BB is the block containing the AND/OR statement being
+ reassociated; its predecessors carry the conditions that establish
+ the operands' truth or falsity at this join point. */
+ if (expr_terms.elements () > 0)
+ {
+ edge e;
+ edge_iterator ei;
+
+ if (curr_bb)
+ {
+ FOR_EACH_EDGE (e, ei, curr_bb->preds)
+ {
+ basic_block pred = e->src;
+ gimple_stmt_iterator gsi = gsi_last_bb (pred);
+ gimple *last_stmt = gsi_stmt (gsi);
+
+ if (!last_stmt || gimple_code (last_stmt) != GIMPLE_COND)
+ continue;
+
+ tree_code cond_code = gimple_cond_code (last_stmt);
+ tree cond_lhs = gimple_cond_lhs (last_stmt);
+
+ if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
+ && TREE_CODE (cond_lhs) == SSA_NAME
+ && integer_zerop (gimple_cond_rhs (last_stmt))
+ && EDGE_COUNT (pred->succs) > 1)
+ {
+ edge true_edge = EDGE_SUCC (pred, 0);
+ edge false_edge = EDGE_SUCC (pred, 1);
+
+ if (!(true_edge->flags & EDGE_TRUE_VALUE))
+ std::swap (true_edge, false_edge);
+
+ /* Skip when CURR_BB is reachable from both or neither
+ successor (degenerate CFG). */
+ bool from_true_edge = (true_edge->dest == curr_bb);
+ bool from_false_edge = (false_edge->dest == curr_bb);
+ if (from_true_edge == from_false_edge)
+ continue;
+
+ /* If COND_LHS's def is an EQ/NE comparison, solve_expr
+ may use it as a match target. Require the right
+ polarity at CURR_BB: OR needs zero, AND needs
+ non-zero. */
+ gimple *cond_lhs_def = SSA_NAME_DEF_STMT (cond_lhs);
+ if (is_gimple_assign (cond_lhs_def))
+ {
+ tree_code c = gimple_assign_rhs_code (cond_lhs_def);
+ if (c == EQ_EXPR || c == NE_EXPR)
+ {
+ bool cond_lhs_known_zero
+ = (cond_code == EQ_EXPR) ? from_true_edge
+ : from_false_edge;
+ if ((is_or_expr && !cond_lhs_known_zero)
+ || (!is_or_expr && cond_lhs_known_zero))
+ continue;
+ }
+ }
+
+ expr_terms.add (cond_lhs);
+ }
+ }
+ }
+ }
+ else
+ return false;
+
+ /* Copy the hash_set into a vector in order to traverse it in a specific
+ order. */
+ auto_vec<tree> expr_terms_vec;
+ copy_hashset_to_vec_and_sort (expr_terms, &expr_terms_vec, ssa_name_cmp);
+
+ /* Pre-compute the terminal nodes for each entry of expr_terms_vec.
+ Reserving up front keeps the storage stable so references taken
+ below remain valid. */
+ auto_vec<hash_set<tree>> terminal_nodes;
+ terminal_nodes.reserve (expr_terms_vec.length ());
+ for (tree term : expr_terms_vec)
+ {
+ terminal_nodes.quick_push (hash_set<tree> ());
+ hash_set<tree> visited;
+ find_terminal_nodes (term, &terminal_nodes.last (), &visited);
+ }
+
+ /* Initialize sets of related expressions. */
+ unsigned int i;
+ tree op;
+ FOR_EACH_VEC_ELT (expr_terms_vec, i, op)
+ {
+ hash_set<tree> related_terms;
+ related_terms.add (op);
+
+ hash_set<tree> &op_terminal_nodes = terminal_nodes[i];
+
+ /* Search the rest of the set for terms related to the current
+ one. */
+ unsigned int j = i + 1;
+ tree next_op;
+ FOR_EACH_VEC_ELT_FROM (expr_terms_vec, j, next_op, j)
+ {
+ hash_set<tree> &next_op_term_nodes = terminal_nodes[j];
+
+ /* If the terms have at least 2 common terminal nodes, add
+ next_op to the set of related terms. */
+ unsigned int common_term_num = 0;
+ for (tree term_node : op_terminal_nodes)
+ {
+ if (next_op_term_nodes.contains (term_node))
+ common_term_num++;
+
+ if (common_term_num == 2)
+ {
+ related_terms.add (next_op);
+ break;
+ }
+ }
+ }
+
+ vec<tree> related_terms_vec {};
+ copy_hashset_to_vec_and_sort (related_terms, &related_terms_vec,
+ ssa_name_cmp);
+
+ op_subexprsets.safe_push (related_terms_vec);
+ }
+
+ /* Iterate over op_subexprsets, analyzing and trying to fold the expressions
+ in each set of related expressions until reaching a fixed-point.
+ ALREADY_FOLDED tracks SSA names whose defining stmts have already been
+ folded by an earlier set; an SSA can appear in more than one set because
+ the "related" relation built above is not transitive. */
+
+ hash_set<tree> already_folded;
+ for (const vec<tree> &expr_set : op_subexprsets)
+ {
+ if (expr_set.length () < 2)
+ continue;
+
+ auto_vec<gimple *> calc_stmts;
+ hash_set<gimple *> stmts_to_fold;
+ bool any_change;
+
+ do
+ {
+ any_change = false;
+ for (tree subexpr : expr_set)
+ {
+ if (already_folded.contains (subexpr))
+ continue;
+ gimple *def_stmt = SSA_NAME_DEF_STMT (subexpr);
+ if (!is_gimple_assign (def_stmt))
+ continue;
+
+ /* If the expression's def is an EQ or NE expression, store it
+ in calc_stmts in order to use it to solve more complex
+ expressions. */
+ tree_code def_stmt_code = gimple_assign_rhs_code (def_stmt);
+ if ((def_stmt_code == EQ_EXPR || def_stmt_code == NE_EXPR)
+ && !calc_stmts.contains (def_stmt)
+ && !stmts_to_fold.contains (def_stmt))
+ {
+ calc_stmts.safe_push (def_stmt);
+ any_change = true;
+ }
+ else
+ {
+ hash_set<tree> visited;
+ solve_expr (subexpr, &calc_stmts, &stmts_to_fold,
+ &visited, is_or_expr);
+ }
+ }
+ }
+ while (any_change);
+
+ auto_vec<gimple *> stmts_to_fold_vec;
+ copy_hashset_to_vec_and_sort (stmts_to_fold, &stmts_to_fold_vec,
+ stmt_uid_cmp);
+
+ unsigned int i;
+ gimple *stmt;
+ FOR_EACH_VEC_ELT (stmts_to_fold_vec, i, stmt)
+ {
+ tree stmt_lhs = gimple_assign_lhs (stmt);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Folding ");
+ print_generic_expr (dump_file, stmt_lhs);
+ fprintf (dump_file, " to 0\n");
+ }
+
+ operand_entry *oe;
+ unsigned int j;
+ tree zero = build_zero_cst (TREE_TYPE (stmt_lhs));
+ FOR_EACH_VEC_ELT (*ops, j, oe)
+ if (oe->op == stmt_lhs)
+ {
+ if (is_or_expr)
+ {
+ /* 0 is the identity for OR: drop just this operand. */
+ ops->ordered_remove (j);
+ reassociate_stats.ops_eliminated++;
+ j--;
+ }
+ else
+ {
+ /* 0 is absorbing for AND: the entire chain folds to 0. */
+ oe->op = zero;
+ reassociate_stats.ops_eliminated += ops->length () - 1;
+ ops->truncate (0);
+ ops->quick_push (oe);
+ }
+ }
+
+ replace_uses_by (stmt_lhs, zero);
+ gimple_stmt_iterator stmt_gsi = gsi_for_stmt (stmt);
+ gsi_remove (&stmt_gsi, true);
+ release_defs (stmt);
+ already_folded.add (stmt_lhs);
+
+ any_changes = true;
+ }
+ }
+
+ for (vec<tree> &v : op_subexprsets)
+ v.release ();
+
+ return any_changes;
+}
+
/* Optimize range tests, similarly how fold_range_test optimizes
it on trees. The tree code for the binary
operation between all the operands is OPCODE.
@@ -4051,11 +4500,14 @@ optimize_range_tests_var_bound (enum tree_code opcode,
int first, int length,
In that case if oe->op is NULL, oe->id is bb->index whose
GIMPLE_COND is && or ||ed into the test, and oe->rank says
the actual opcode.
- FIRST_BB is the first basic block if OPCODE is ERROR_MARK. */
+ FIRST_BB is the first basic block if OPCODE is ERROR_MARK.
+ CURR_BB is the block containing the AND/OR statement being reassociated
+ in the intra-bb case, or NULL otherwise. */
static bool
optimize_range_tests (enum tree_code opcode,
- vec<operand_entry *> *ops, basic_block first_bb)
+ vec<operand_entry *> *ops, basic_block first_bb,
+ basic_block curr_bb)
{
unsigned int length = ops->length (), i, j, first;
operand_entry *oe;
@@ -4134,6 +4586,7 @@ optimize_range_tests (enum tree_code opcode,
ranges, first_bb);
any_changes |= optimize_range_tests_cmp_bitwise (opcode, first, length,
ops, ranges);
+ any_changes |= optimize_cmp_xor_exprs (opcode, ops, curr_bb);
if (any_changes && opcode != ERROR_MARK)
{
@@ -4973,7 +5426,7 @@ maybe_optimize_range_tests (gimple *stmt)
break;
}
if (ops.length () > 1)
- any_changes = optimize_range_tests (ERROR_MARK, &ops, first_bb);
+ any_changes = optimize_range_tests (ERROR_MARK, &ops, first_bb, NULL);
if (any_changes)
{
unsigned int idx, max_idx = 0;
@@ -7070,7 +7523,8 @@ reassociate_bb (basic_block bb)
if (is_vector)
optimize_vec_cond_expr (rhs_code, &ops);
else
- optimize_range_tests (rhs_code, &ops, NULL);
+ optimize_range_tests (rhs_code, &ops, NULL,
+ gimple_bb (stmt));
}
if (rhs_code == MULT_EXPR && !is_vector)
--
