On Mon, Jun 8, 2026 at 3:17 AM Konstantinos Eleftheriou
<[email protected]> wrote:
>
> 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" } */
Add a variant for =0 instead.
>
> 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" } } */
for not regex just use 2 instead of an `|` here.
That is:
/* { dg-final { scan-tree-dump-not "d1_\[0-9\]+.D. \\^ d2_\[0-9\]+.D."
"optimized" } } */
/* { dg-final { scan-tree-dump-not "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" } } */
Likewise.
> 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" } */
Likewise about the variant for =0.
>
> 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" } } */
Likewise of the regex issue.
> 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,
Change visited to be a bitmap of ssanames.
> + 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;
if (!is_a<gassign*>(def_stmt))
> +
> + unsigned int op_num = gimple_num_ops (def_stmt);
This won't work for some cases. e.g. VIEW_CONVERT_EXPR or BIT_FIELD_REF.
> + 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;
This should never be NULL.
> + tree solve_result = solve_expr (op, calc_stmts, stmts_to_fold, visited,
> + is_or_expr);
This is an unbounded recusive. Can you use a worklist instead? And is
there a way to bound it?
> + 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. */
/* Treat BIT_XOR_EXPR as a NE_EXPR; they have the same effect. */
> + 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))
def_code == (is_or_expr ? stmt_rhs_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;
> + }
Swap around visited/ssa name check.
And this allows visited to be a bitmap for ssa names.
> +
> + gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
> +
> + if (!is_gimple_assign (def_stmt))
!is_a<gassign*> (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;
This should not be NULL here.
> + find_terminal_nodes (op, terminal_nodes, visited);
Similar, recusive; can you use a worklist instead?
> + }
> +}
> +
> +/* 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 *))
sorted_hashset_vec is a better name
> +{
I would assert vect is empty here.
> + 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;
if (opcode != BIT_AND_EXPR && opcode != BIT_IOR_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)
> + {
bool is_or_expr = opcode == BIT_IOR_EXPR;
Move the definition of e and ei here.
> + FOR_EACH_EDGE (e, ei, curr_bb->preds)
Or better yet just do:
for (edge e : curr_bb->preds)
> + {
> + basic_block pred = e->src;
> + gimple_stmt_iterator gsi = gsi_last_bb (pred);
if (gsi_end_p (gsi))
continue;
> + gimple *last_stmt = gsi_stmt (gsi);
last_stmt = *gsi;
> +
> + if (!last_stmt || gimple_code (last_stmt) != GIMPLE_COND)
!is_a <gcond *>(last_stmt)
> + 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 count better be 2 for GIMPLE_COND. So remove the edge count.
> + {
> + 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);
extract_true_false_edges_from_block (pred, &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))
if (gassign *assign = dyn_cast <gassign *>(cond_lhs_def))
> + {
> + tree_code c = gimple_assign_rhs_code (cond_lhs_def);
// assign
> + 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))
`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> *elt = terminal_nodes.quick_push (hash_set<tree> ());
> + hash_set<tree> visited;
> + find_terminal_nodes (term, &terminal_nodes.last (), &visited);
find_terminal_nodes (term, elt, &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;
> + }
if (!next_op_term_nodes.contains (term_node))
continue;
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;
See below on the question about creating ssa names. Otherwise a bitmap
is better and smaller and faster here.
> + 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;
Do you create new ssa names during this loop?
If not then you could check if SSA_NAME_IN_FREE_LIST is set.
> + 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)
> --
