Hi Andrew, Thanks for the feedback. We submitted a new version that addresses the issues that you noted: https://gcc.gnu.org/pipermail/gcc-patches/2026-June/720024.html
Konstantinos On Tue, Jun 9, 2026 at 9:11 AM Andrew Pinski <[email protected]> wrote: > 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) > > -- >
