On Thu, May 28, 2026 at 2:34 AM Konstantinos Eleftheriou
<[email protected]> wrote:
>
> 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.
I thought our documentation said you should follow the GCC coding
style for testcases unless it is not possible you can (e.g.
preprocessing tests) but I can't find that statement anywhere.
>>
>>
>>
>> > /* 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.
Just use `vec<gimple*> *` rather than auto_vec. That is auto_vec is
the type used for the original variable but what gets passed is
`vec*`.
>>
>>
>> > +/* 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
