Hi Robin, thanks for the feedback!
On Wed, May 27, 2026 at 4:44 PM Robin Dapp <[email protected]> wrote:
> 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?
FWIK, the testcases don't need to follow the GNU coding style conventions,
so we
didn't even try to follow them. That said, the fixes are trivial and we
could apply them anyway.
>
>
> /* 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?
>
Will do.
>
> > +/* 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?
Right. SSA_NAME_DEF_STMT never returns NULL (a default def yields a
GIMPLE_NOP),
so !def_stmt is dead, and since an SSA name is never defined by a debug
statement, the is_gimple_debug check is dead as well.
Will drop them both, along with the matching !def_stmt in solve_expr.
>
> > + {
> > + 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?
>
We will replace them with three-way comparisons.
>
> > +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 :)
>
A bitmap is possible but wouldn't be a simplification here. The
terminal-node
sets hold non-SSA_NAME leaves too, which have no SSA version to key on, so a
bitmap indexed by SSA_NAME_VERSION can't represent them directly.
Supporting them would mean numbering the nodes in a side hash_map<tree,
unsigned>
and using sbitmaps over that index, which is what PRE/SCCVN do for
constants.
That's an extra structure on top of what we have, rather than a replacement.
Either way the sets are tiny in practice — bounded by the operands of the
AND/OR
chain (single digits), each unfolding to a few leaves — so the hash_set cost
is negligible.
>
> > + 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?
>
Right, calc_stmts only collects the EQ/NE defining statements within a
single
related-term set, which is a handful at most, so the linear contains() is
negligible. We also iterate calc_stmts in order and remove from it, so
a vector is the natural container.
>
>
> > + && !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?
>
You're right that the body never reads i, the inner declaration is a
separate variable that shadows it. We'll rename it to avoid confusion.
>
> > + 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)
>
> We do use the operand list for terms that are direct members of the chain,
in
the OR case we drop the matching operand, in the AND case we zero it. But
the
definition we fold to 0 frequently isn't a chain operand itself: it can be a
nested subexpression (e.g. the (d1 ^ d2) feeding a comparison that is the
chain
operand) or a condition that lives in a predecessor block. Those uses aren't
reachable by editing ops, so we rewrite them directly in the IL via
replace_uses_by and remove the now-dead def, letting later folding simplify
the
result. If there's a cleaner way to express the inter-bb / nested case
through
the operand list, I'd be glad to hear it.
>
> --
> Regards
> Robin
>
> Konstantinos
