Ping. https://gcc.gnu.org/pipermail/gcc-patches/2026-August/727175.html Thanks, Kyrill
> On 11 Aug 2026, at 12:42, Kyrylo Tkachov <[email protected]> wrote: > > From: Kyrylo Tkachov <[email protected]> > > Reassociation rebalances a chain of four or more comparisons into a tree, > because the reassociation width of the boolean mode is the width of an > integer bitwise operation. A conditional compare sequence cannot use that > parallelism: every conditional comparison tests the flags that the previous > comparison set. Splitting the chain therefore costs a sequence. For > > int > f (int a, int b, int c, int d, int e, int f, int g, int h) > { > return (a < b) & (c < d) & (e < f) & (g < h); > } > > reassociation produced > > _3 = _1 & _2; > _16 = _4 & _5; > _17 = _3 & _16; > > and AArch64 emitted two sequences and a bitwise operation: > > cmp w0, w1 > ccmp w2, w3, 0, lt > cset w1, lt > cmp w4, w5 > ccmp w6, w7, 0, lt > cset w0, lt > and w0, w1, w0 > > Keep the chain linear when it expands to one conditional compare sequence. > That needs every operand to be a scalar comparison in the same block, at > least one of them foldable into the flags, and at most one that can trap, > since only the first comparison of a sequence is unconditional. One operand > may be an AND/IOR of its own, which the expander emits first. AArch64 then > emits one sequence: > > cmp w4, w5 > ccmp w6, w7, 0, lt > ccmp w2, w3, 0, lt > ccmp w0, w1, 0, lt > cset w0, lt > > The chain that a balanced tree of the same comparisons produces is now the > same, so the source shape no longer decides the result. > > Bootstrapped and tested on aarch64-none-linux-gnu. > Ok for trunk? > Thanks, > Kyrill > > gcc/ > > * tree-ssa-reassoc.cc (ccmp_comparison_p): New function. > (ccmp_sequence_p): Likewise. > (ccmp_chain_p): Likewise. > (reassociate_bb): Do not rewrite a conditional compare chain to > parallel form. > > gcc/testsuite/ > > * gcc.c-torture/execute/ccmp-tree-1.c: New test. > * gcc.target/aarch64/ccmp_6.c: New test. > * gcc.target/aarch64/ccmp_10.c: Likewise. > > Signed-off-by: Kyrylo Tkachov <[email protected]> > --- > .../gcc.c-torture/execute/ccmp-tree-1.c | 90 +++++++++++++++++++ > gcc/testsuite/gcc.target/aarch64/ccmp_10.c | 24 +++++ > gcc/testsuite/gcc.target/aarch64/ccmp_6.c | 63 +++++++++++++ > gcc/tree-ssa-reassoc.cc | 86 ++++++++++++++++++ > 4 files changed, 263 insertions(+) > create mode 100644 gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/ccmp_10.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/ccmp_6.c > > diff --git a/gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c > b/gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c > new file mode 100644 > index 00000000000..9d7f5241f19 > --- /dev/null > +++ b/gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c > @@ -0,0 +1,90 @@ > +/* Execution test for conditional-compare chains built from AND/IOR trees of > + comparisons. Each function is compared against a reference computed with > + volatile operands so that it cannot be folded into the same code. */ > + > +extern void abort (void); > + > +#define OPS int a, int b, int c, int d, int e, int f, int g, int h > +#define ARGS a, b, c, d, e, f, g, h > + > +/* Balanced AND tree. */ > +static int __attribute__((noipa)) t1 (OPS) > +{ return ((a < b) & (c < d)) & ((e < f) & (g < h)); } > + > +/* Balanced OR tree. */ > +static int __attribute__((noipa)) t2 (OPS) > +{ return ((a < b) | (c < d)) | ((e < f) | (g < h)); } > + > +/* AND of an OR chain and an AND chain. */ > +static int __attribute__((noipa)) t3 (OPS) > +{ return ((a < b) | (c < d)) & ((e < f) & (g < h)); } > + > +/* OR of an AND chain and an OR chain. */ > +static int __attribute__((noipa)) t4 (OPS) > +{ return ((a < b) & (c < d)) | ((e < f) | (g < h)); } > + > +/* Deeper: eight leaves. */ > +static int __attribute__((noipa)) t5 (OPS) > +{ > + return (((a < b) & (c < d)) & ((e < f) & (g < h))) > + & (((a < c) & (b < d)) & ((e < g) & (f < h))); > +} > + > +/* Mixed signed and unsigned leaves. */ > +static int __attribute__((noipa)) t6 (OPS) > +{ > + return (((unsigned) a < (unsigned) b) & (c < d)) > + & ((e < f) & ((unsigned) g < (unsigned) h)); > +} > + > +/* Immediates, some inside and some outside the CCMP 5-bit range. */ > +static int __attribute__((noipa)) t7 (OPS) > +{ return ((a == 3) & (b == 31)) & ((c == 32) & (d == -4)); } > + > +/* Reference versions. V forces separate evaluation of every leaf. */ > +#define V(x) ({ volatile int v_ = (x); v_; }) > + > +static int r1 (OPS) > +{ return (V(a < b) & V(c < d)) & (V(e < f) & V(g < h)); } > +static int r2 (OPS) > +{ return (V(a < b) | V(c < d)) | (V(e < f) | V(g < h)); } > +static int r3 (OPS) > +{ return (V(a < b) | V(c < d)) & (V(e < f) & V(g < h)); } > +static int r4 (OPS) > +{ return (V(a < b) & V(c < d)) | (V(e < f) | V(g < h)); } > +static int r5 (OPS) > +{ > + return ((V(a < b) & V(c < d)) & (V(e < f) & V(g < h))) > + & ((V(a < c) & V(b < d)) & (V(e < g) & V(f < h))); > +} > +static int r6 (OPS) > +{ > + return (V((unsigned) a < (unsigned) b) & V(c < d)) > + & (V(e < f) & V((unsigned) g < (unsigned) h)); > +} > +static int r7 (OPS) > +{ return (V(a == 3) & V(b == 31)) & (V(c == 32) & V(d == -4)); } > +static const int vals[] = { -4, 0, 3, 31, 32, 33 }; > +#define NV ((int) (sizeof (vals) / sizeof (vals[0]))) > + > +int > +main (void) > +{ > + for (int i0 = 0; i0 < NV; i0++) > + for (int i1 = 0; i1 < NV; i1++) > + for (int i2 = 0; i2 < NV; i2++) > + for (int i3 = 0; i3 < NV; i3++) > + { > + int a = vals[i0], b = vals[i1], c = vals[i2], d = vals[i3]; > + int e = vals[i3], f = vals[i0], g = vals[i2], h = vals[i1]; > + > + if (t1 (ARGS) != r1 (ARGS)) abort (); > + if (t2 (ARGS) != r2 (ARGS)) abort (); > + if (t3 (ARGS) != r3 (ARGS)) abort (); > + if (t4 (ARGS) != r4 (ARGS)) abort (); > + if (t5 (ARGS) != r5 (ARGS)) abort (); > + if (t6 (ARGS) != r6 (ARGS)) abort (); > + if (t7 (ARGS) != r7 (ARGS)) abort (); > + } > + return 0; > +} > diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_10.c > b/gcc/testsuite/gcc.target/aarch64/ccmp_10.c > new file mode 100644 > index 00000000000..a7fd4f2400e > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/ccmp_10.c > @@ -0,0 +1,24 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 --param tree-reassoc-width=2 > -fdump-tree-reassoc2-details" } */ > + > +/* A vector comparison does not set the condition flags, so a chain of them > + is not a conditional compare sequence and keeps the parallel form. */ > + > +typedef int v4si __attribute__ ((vector_size (16))); > + > +v4si > +vector_chain (v4si a, v4si b, v4si c, v4si d, v4si e, v4si f, v4si g, v4si h) > +{ > + return (a < b) & (c < d) & (e < f) & (g < h); > +} > + > +/* A chain of scalar comparisons becomes one sequence instead. */ > + > +int > +scalar_chain (int a, int b, int c, int d, int e, int f, int g, int h) > +{ > + return (a < b) & (c < d) & (e < f) & (g < h); > +} > + > +/* { dg-final { scan-tree-dump-times "was chosen for reassociation" 1 > "reassoc2" } } */ > +/* { dg-final { scan-assembler-times {\tccmp\t} 3 } } */ > diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_6.c > b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c > new file mode 100644 > index 00000000000..9feec51d8de > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c > @@ -0,0 +1,63 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2" } */ > +/* { dg-final { check-function-bodies "**" "" } } */ > + > +/* A chain of four comparisons is wide enough for reassociation to build a > + balanced tree. Both source shapes have to reach expansion as one chain, > + which a conditional compare sequence can hold in the flags. */ > + > +/* > +** and_chain: > +** cmp w4, w5 > +** ccmp w6, w7, 0, lt > +** ccmp w2, w3, 0, lt > +** ccmp w0, w1, 0, lt > +** cset w0, lt > +** ret > +*/ > +int > +and_chain (int a, int b, int c, int d, int e, int f, int g, int h) > +{ > + return (a < b) & (c < d) & (e < f) & (g < h); > +} > + > +/* > +** and_tree: > +** cmp w4, w5 > +** ccmp w6, w7, 0, lt > +** ccmp w2, w3, 0, lt > +** ccmp w0, w1, 0, lt > +** cset w0, lt > +** ret > +*/ > +int > +and_tree (int a, int b, int c, int d, int e, int f, int g, int h) > +{ > + return ((a < b) & (c < d)) & ((e < f) & (g < h)); > +} > + > +/* > +** ior_tree: > +** cmp w4, w5 > +** ccmp w6, w7, 1, ge > +** ccmp w2, w3, 1, ge > +** ccmp w0, w1, 1, ge > +** cset w0, lt > +** ret > +*/ > +int > +ior_tree (int a, int b, int c, int d, int e, int f, int g, int h) > +{ > + return ((a < b) | (c < d)) | ((e < f) | (g < h)); > +} > + > +/* Both operands hold a value in the flags at the same time, so this one > + needs two sequences and a bitwise operation. */ > + > +int > +and_of_ior (int a, int b, int c, int d, int e, int f, int g, int h) > +{ > + return ((a < b) | (c < d)) & ((e < f) | (g < h)); > +} > + > +/* { dg-final { scan-assembler-times {\tand\tw[0-9]+, w[0-9]+, w[0-9]+} 1 } > } */ > diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc > index dec64883891..d424dff7406 100644 > --- a/gcc/tree-ssa-reassoc.cc > +++ b/gcc/tree-ssa-reassoc.cc > @@ -5165,6 +5165,84 @@ swap_ops_for_binary_stmt (const vec<operand_entry *> > &ops, > std::swap (*oe1, *oe2); > } > > +/* Return true if OP is set by a comparison in BB, which a conditional > + compare can compute into the condition flags. */ > + > +static bool > +ccmp_comparison_p (tree op, basic_block bb) > +{ > + if (TREE_CODE (op) != SSA_NAME) > + return false; > + > + gimple *def = SSA_NAME_DEF_STMT (op); > + if (!is_gimple_assign (def) > + || gimple_bb (def) != bb > + || TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison) > + return false; > + > + /* A conditional compare sets the flags from one comparison of two > + registers. */ > + machine_mode mode = TYPE_MODE (TREE_TYPE (gimple_assign_rhs1 (def))); > + return ((SCALAR_INT_MODE_P (mode) || SCALAR_FLOAT_MODE_P (mode)) > + && known_le (GET_MODE_SIZE (mode), UNITS_PER_WORD)); > +} > + > +/* Return true if OP is an AND/IOR in BB, which the expander can emit as a > + conditional compare sequence of its own. */ > + > +static bool > +ccmp_sequence_p (tree op, basic_block bb) > +{ > + if (TREE_CODE (op) != SSA_NAME || !has_single_use (op)) > + return false; > + > + gimple *def = SSA_NAME_DEF_STMT (op); > + if (!is_gimple_assign (def) || gimple_bb (def) != bb) > + return false; > + > + tree_code code = gimple_assign_rhs_code (def); > + return code == BIT_AND_EXPR || code == BIT_IOR_EXPR; > +} > + > +/* Return true if the CODE chain in BB with operands OPS expands to one > + conditional compare sequence. Such a sequence holds a single value in > + the condition flags, so every operand has to be a comparison that the > + next conditional compare tests, and at least one of them has to be a > + comparison that the expander can fold into the flags. Only the first > + comparison of the sequence is unconditional, so at most one operand may > + trap. One operand may be a sequence of its own, which the expander then > + has to emit first. */ > + > +static bool > +ccmp_chain_p (const vec<operand_entry *> &ops, tree_code code, basic_block > bb) > +{ > + if (!targetm.have_ccmp () > + || (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)) > + return false; > + > + bool seen_sequence = false; > + bool seen_foldable = false; > + unsigned trapping = 0; > + > + for (const operand_entry *oe : ops) > + { > + if (!ccmp_comparison_p (oe->op, bb)) > + { > + if (seen_sequence || !ccmp_sequence_p (oe->op, bb)) > + return false; > + seen_sequence = true; > + continue; > + } > + > + if (gimple_could_trap_p (SSA_NAME_DEF_STMT (oe->op)) && ++trapping > 1) > + return false; > + > + seen_foldable |= has_single_use (oe->op); > + } > + > + return seen_foldable; > +} > + > /* If definition of RHS1 or RHS2 dominates STMT, return the later of those > two definitions, otherwise return STMT. Sets INSERT_BEFORE to indicate > whether RHS1 op RHS2 can be inserted before or needs to be inserted > @@ -7153,11 +7231,19 @@ reassociate_bb (basic_block bb) > mult_num = rank_ops_for_fma (&ops); > } > > + /* A chain that expands to a conditional compare sequence > + has to stay linear. Every conditional compare tests the > + flags that the previous comparison set, so the sequence > + cannot be split into independent parts. */ > + bool ccmp_chain = (ops_num > 2 > + && ccmp_chain_p (ops, rhs_code, bb)); > + > /* Only rewrite the expression tree to parallel in the > last reassoc pass to avoid useless work back-and-forth > with initial linearization. */ > bool has_fma = mult_num >= 2 && mult_num != ops_num; > if (!reassoc_insert_powi_p > + && !ccmp_chain > && ops.length () > 3 > && (width = get_reassociation_width (&ops, mult_num, lhs, > rhs_code, mode)) > -- > 2.50.1 (Apple Git-155) >
