Hi Konstantinos,
just a few things/nits I noticed but I didn't go through everything.
> 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..593cbaebcc5b
> --- /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. */
Nit: GNU coding style (two spaces after full stop, no space at the end of a
line. Seems a bit inconsistent throughout the patch, but easily fixed.
> +/* { 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) {
Here and for the following cases: Missing space after opening parenthesis.
Given the same oversight occurs several times, are the tests auto-generated or
copied from the same single one?
> /* 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" } } */
> +/* { 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..dde8952c84e6
> --- /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) {
Same here.
> +/* 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. */
> +
> +static tree
> +solve_expr (tree expr, auto_vec<gimple *> *calc_stmts,
> + hash_set<gimple *> *stmts_to_fold, hash_set<tree> *visited,
> + bool is_or_expr)
Just clarifying: It looks like stmts_to_fold can change even if the function
returns NULL due to its recursion? Maybe add a note regarding the return value
in the function-level comment?
> +/* 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_debug (def_stmt))
> + return;
> +
> + if (!def_stmt || !is_gimple_assign (def_stmt))
I guess !def_stmt will be optimized away here because we called is_gimple_debug
on it already?
> + {
> + 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);
> + }
> +}
> +
> +/* Functions to sort two TREE nodes or GIMPLE statements. */
> +
> +template<typename T>
> +static int sort_elements (const void *p1, const void *p2);
> +
> +template<>
> +int sort_elements<tree> (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);
> +
> + return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
Isn't this a potential overflow when b > a? Does that work with qsort?
> +template<>
> +int sort_elements<gimple *> (const void *p1, const void *p2)
> +{
> + const gimple *s1 = *(const gimple* const*)p1;
> + const gimple *s2 = *(const gimple* const*)p2;
> +
> + return gimple_uid (s1) - gimple_uid (s2);
> +}
Same here.
> + for (const tree &term : terms_in_preds)
> + expr_terms.add (term);
> +
> + /* 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);
> +
> + /* 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;
This doesn't look cheap. I didn't go through all code but would a bitmap work
here?
In general the patch seems to prefer hash sets and vectors over bitmaps :)
> + 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)
That looks like a linear search. I guess we don't usually add many statements
to the vector?
> + && !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);
> +
> + 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 i;
No big deal but i seems unused in the outer loop and overridden here?
> + tree zero = build_zero_cst (TREE_TYPE (stmt_lhs));
> + FOR_EACH_VEC_ELT (*ops, i, oe)
> +
> + replace_uses_by (stmt_lhs, zero);
Out of curiosity and I might be late to the party, but why does the regular
reassoc way of handling ops not apply here? (modifying an operands list)
--
Regards
Robin
