On Fri, Sep 4, 2026 at 5:38 AM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> Reassociation rebalances a chain of four or more comparisons into a tree.
> The reassociation width of the boolean mode is the width of an integer
> bitwise operation. A conditional-compare sequence cannot use that
> parallelism because every conditional comparison tests the flags that the
> previous comparison set. 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;
>
> 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 only when every operand is a scalar comparison in the
> same block and at least one comparison can be folded into the flags. Put a
> forwarded trapping comparison in the innermost pair. The expander tries
> both orders of that pair and can make this comparison unconditional.
> 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
>
> Tests cover linear and balanced source forms, unsupported operands,
> trapping comparisons in every source position, and comparison results with
> other uses.
>
> Changes since v1:
> - Require the complete operand list to form one CCMP sequence.
> - Put a trapping comparison first and reject conflicting heads.
> - Add tests for trapping positions and comparison results with other uses.
>
> gcc/
>
> * tree-ssa-reassoc.cc (ccmp_comparison_p): New function.
> (prepare_ccmp_chain): Likewise.
> (reassociate_bb): Keep a complete conditional-compare chain linear
> and put its required first operand in the innermost pair.
>
> 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.
> * gcc.target/aarch64/ccmp_12.c: Likewise.
> * gcc.target/aarch64/ccmp_14.c: Likewise.
> * gcc.target/aarch64/fccmp_6.c: Likewise.
> * gcc.target/aarch64/fccmp_8.c: Likewise.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
>
> ---
> 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..b67b2410484
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/ccmp_10.c
> @@ -0,0 +1,33 @@
> +/* { 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);
> +}
> +
> +/* A nested integer IOR is not a conditional compare sequence. */
> +
> +int
> +integer_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-tree-dump-times "was chosen for reassociation" 1
> "reassoc2" } } */
> +/* { dg-final { scan-assembler-times {\tccmp\t} 5 } } */
> +/* { dg-final { scan-assembler-times {\tand\tw[0-9]+, w[0-9]+, w[0-9]+} 1 }
> } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_12.c
> b/gcc/testsuite/gcc.target/aarch64/ccmp_12.c
> new file mode 100644
> index 00000000000..0d9fcb00c89
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/ccmp_12.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 --param tree-reassoc-width=2
> -fdump-tree-reassoc2-details" } */
> +
> +/* Comparison leaves can have uses outside the chain. A chain stays linear
> + when another comparison can be folded into the flags. */
> +
> +volatile int result;
> +
> +int
> +one_multi_use (int a, int b, int c, int d, int e, int f, int g, int h)
> +{
> + int x = a < b;
> + result = x;
> + return x & (c < d) & (e < f) & (g < h);
> +}
> +/* { dg-final { scan-assembler-times {\tccmp\t} 3 } } */
> +/* { dg-final { scan-tree-dump-not "was chosen for reassociation" "reassoc2"
> } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_14.c
> b/gcc/testsuite/gcc.target/aarch64/ccmp_14.c
> new file mode 100644
> index 00000000000..0ff0cd5ae7d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/ccmp_14.c
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 --param tree-reassoc-width=2
> -fdump-tree-reassoc2-details" } */
> +
> +/* If no comparison can be folded, the chain keeps the parallel form. */
> +
> +volatile int results[4];
> +
> +int
> +all_multi_use (int a, int b, int c, int d, int e, int f, int g, int h)
> +{
> + int x0 = a < b;
> + int x1 = c < d;
> + int x2 = e < f;
> + int x3 = g < h;
> + results[0] = x0;
> + results[1] = x1;
> + results[2] = x2;
> + results[3] = x3;
> + return x0 & x1 & x2 & x3;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "was chosen for reassociation" 1
> "reassoc2" } } */
> +/* { dg-final { scan-assembler-not {\tccmp\t} } } */
> 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/testsuite/gcc.target/aarch64/fccmp_6.c
> b/gcc/testsuite/gcc.target/aarch64/fccmp_6.c
> new file mode 100644
> index 00000000000..5ded1304f03
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/fccmp_6.c
> @@ -0,0 +1,19 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +
> +/* A trapping comparison must start the sequence. Test every source
> + position in a chain that is long enough for parallel reassociation. */
> +
> +#define DEF(N, EXPR) \
> + int f##N (double a, double b, int c, int d, int e, int f, int g, int h) \
> + { return (EXPR); }
> +
> +DEF (0, (a < b) & (c < d) & (e < f) & (g < h))
> +DEF (1, (c < d) & (a < b) & (e < f) & (g < h))
> +DEF (2, (c < d) & (e < f) & (a < b) & (g < h))
> +DEF (3, (c < d) & (e < f) & (g < h) & (a < b))
> +
> +/* { dg-final { scan-assembler-times {\tfcmpe\t} 4 } } */
> +/* { dg-final { scan-assembler-times {\tccmp\t} 12 } } */
> +/* { dg-final { scan-assembler-times {\tcset\t} 4 } } */
> +/* { dg-final { scan-assembler-not {\tand\t} } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/fccmp_8.c
> b/gcc/testsuite/gcc.target/aarch64/fccmp_8.c
> new file mode 100644
> index 00000000000..1f49069b710
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/fccmp_8.c
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 --param tree-reassoc-width=2
> -fdump-tree-reassoc2-details" } */
> +
> +/* Two trapping comparisons cannot both start one sequence. */
> +
> +int
> +two_traps (double a, double b, double c, double 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" } } */
> diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
> index dec64883891..737d30ba0a4 100644
> --- a/gcc/tree-ssa-reassoc.cc
> +++ b/gcc/tree-ssa-reassoc.cc
> @@ -5165,6 +5165,66 @@ 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 scalar comparison. */
> + 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));
While doing the newsletter I came across this patch. I think this is
incorrect. TImode could be done using ccmp (and is being worked on
right now). So having the check against UNITS_PER_WORD seems wrong.
If anything it should be against MAX_FIXED_MODE_SIZE .
> +}
> +
> +/* Return true if all operands in OPS form one conditional compare sequence
> + for CODE in BB. Put the operand that must start the sequence last in OPS,
> + where rewrite_expr_tree builds the innermost pair. Every operand must be
> a
> + comparison, and at least one must be foldable into the flags. */
> +
> +static bool
> +prepare_ccmp_chain (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_foldable = false;
> + int head = -1;
> +
> + for (unsigned int i = 0; i < ops.length (); ++i)
> + {
> + const operand_entry *oe = ops[i];
> + if (!ccmp_comparison_p (oe->op, bb))
> + return false;
> +
> + bool foldable = has_single_use (oe->op);
> + if (foldable
> + && gimple_could_trap_p (SSA_NAME_DEF_STMT (oe->op)))
> + {
> + if (head >= 0)
> + return false;
> + head = i;
> + }
> +
> + /* Comparison leaves can have uses outside this chain. */
> + seen_foldable |= foldable;
> + }
> +
> + if (head >= 0)
> + std::swap (*ops[head], *ops.last ());
> + 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 +7213,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
> + && prepare_ccmp_chain (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))
> @@ -7178,7 +7246,7 @@ reassociate_bb (basic_block bb)
> to make sure the ones that get the double
> binary op are chosen wisely. */
> int len = ops.length ();
> - if (!reassoc_insert_powi_p
> + if (!reassoc_insert_powi_p && !ccmp_chain
> && len >= 3
> && (!has_fma
> /* width > 1 means ranking ops results in better
> --
> 2.50.1 (Apple Git-155)
