On Mon, Aug 10, 2026 at 6:26 AM <[email protected]> wrote: > > From: Kyrylo Tkachov <[email protected]> > > Reassociation can turn a chain of four comparisons into a balanced tree: > > return ((a < b) & (c < d)) & ((e < f) & (g < h));
Then Reassociation should be fixed rather than changing ccmp. > > The conditional-compare expander rejects this when both operands are > subtrees. AArch64 then emits two separate chains: > > 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 > > A subtree can be appended when all its operators match the parent. Recognise > these uniform subtrees, expand the other operand first, then append each > comparison. AArch64 then emits one chain: > > cmp w0, w1 > ccmp w2, w3, 0, lt > ccmp w4, w5, 0, lt > ccmp w6, w7, 0, lt > cset w0, lt > > Expand each recursive operand only once. Cache uniform-tree results so the > analysis remains linear for nested mixed trees. Mixed trees that cannot use > one condition-code value remain rejected. > > Bootstrapped and tested on aarch64-none-linux-gnu. > Ok for trunk? > Thanks, > Kyrill > > gcc/ > > * ccmp.cc (ccmp_uniform_cache): New typedef. > (ccmp_uniform_chain_p): New function. > (ccmp_candidate_p): Accept a node with a uniform operand. > (expand_ccmp_chain): New function. > (expand_ccmp_expr_1): Append a uniform operand. > (expand_ccmp_expr): Create the uniform-tree cache. > > gcc/testsuite/ > > * gcc.c-torture/execute/ccmp-tree-1.c: New test. > * gcc.target/aarch64/ccmp_6.c: New test. > > Signed-off-by: Kyrylo Tkachov <[email protected]> > --- > gcc/ccmp.cc | 94 ++++++++++++++++--- > .../gcc.c-torture/execute/ccmp-tree-1.c | 90 ++++++++++++++++++ > gcc/testsuite/gcc.target/aarch64/ccmp_6.c | 89 ++++++++++++++++++ > 3 files changed, 260 insertions(+), 13 deletions(-) > create mode 100644 gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/ccmp_6.c > > diff --git a/gcc/ccmp.cc b/gcc/ccmp.cc > index f63e44dcc84..1c540f641b2 100644 > --- a/gcc/ccmp.cc > +++ b/gcc/ccmp.cc > @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. If not see > #include "cfgexpand.h" > #include "ccmp.h" > #include "predict.h" > +#include "hash-map.h" > > /* Check whether T is a simple boolean variable or a SSA name > set by a comparison operator in the same basic block. */ > @@ -90,10 +91,40 @@ ccmp_tree_comparison_p (tree t, basic_block bb) > If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then > insns in gen_seq. */ > > +typedef hash_map<tree, bool> ccmp_uniform_cache; > + > +/* Return true if T is a CODE tree in BB whose leaves are comparisons. > + CACHE records results for logical SSA definitions. */ > + > +static bool > +ccmp_uniform_chain_p (tree t, tree_code code, basic_block bb, > + ccmp_uniform_cache &cache) > +{ > + if (ccmp_tree_comparison_p (t, bb)) > + return true; > + > + gimple *g = get_gimple_for_ssa_name (t); > + if (!g || !is_gimple_assign (g) || gimple_assign_rhs_code (g) != code) > + return false; > + > + if (bool *value = cache.get (t)) > + return *value; > + > + tree op0 = gimple_assign_rhs1 (g); > + tree op1 = gimple_assign_rhs2 (g); > + bool value = (TREE_CODE (op0) == SSA_NAME > + && TREE_CODE (op1) == SSA_NAME > + && ccmp_uniform_chain_p (op0, code, bb, cache) > + && ccmp_uniform_chain_p (op1, code, bb, cache)); > + cache.put (t, value); > + return value; > +} > + > /* Check whether G is a potential conditional compare candidate; OUTER is > true if > G is the outer most AND/IOR. */ > static bool > -ccmp_candidate_p (gimple *g, bool outer = false) > +ccmp_candidate_p (gimple *g, ccmp_uniform_cache &cache, > + bool outer = false) > { > tree lhs, op0, op1; > gimple *gs0, *gs1; > @@ -121,13 +152,16 @@ ccmp_candidate_p (gimple *g, bool outer = false) > > if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb)) > return true; > - if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1)) > + if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1, cache)) > return true; > - if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0)) > + if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0, cache)) > return true; > - /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since > - there is no way to set and maintain the CC flag on both sides of > - the logical operator at the same time. */ > + /* A uniform chain can be appended to the other operand one comparison at > + a time. */ > + if (ccmp_uniform_chain_p (op1, tcode, bb, cache)) > + return ccmp_candidate_p (gs0, cache); > + if (ccmp_uniform_chain_p (op0, tcode, bb, cache)) > + return ccmp_candidate_p (gs1, cache); > return false; > } > > @@ -179,6 +213,26 @@ expand_ccmp_next (tree op, tree_code code, rtx prev, > rhs1, rhs2, get_rtx_code (code, 0)); > } > > +/* Append the leaves of uniform CODE tree OP to conditional comparison PREV. > + Return the extended comparison, or NULL_RTX if expansion fails. */ > + > +static rtx > +expand_ccmp_chain (tree op, tree_code code, rtx prev, > + rtx_insn **prep_seq, rtx_insn **gen_seq) > +{ > + gimple *g = get_gimple_for_ssa_name (op); > + if (!g || gimple_assign_rhs_code (g) != code) > + return expand_ccmp_next (op, code, prev, prep_seq, gen_seq); > + > + prev = expand_ccmp_chain (gimple_assign_rhs1 (g), code, prev, > + prep_seq, gen_seq); > + if (!prev) > + return NULL_RTX; > + > + return expand_ccmp_chain (gimple_assign_rhs2 (g), code, prev, > + prep_seq, gen_seq); > +} > + > /* Expand conditional compare gimple G. A typical CCMP sequence is like: > > CC0 = CMP (a, b); > @@ -191,7 +245,8 @@ expand_ccmp_next (tree op, tree_code code, rtx prev, > PREP_SEQ returns all insns to prepare operand. > GEN_SEQ returns all compare insns. */ > static rtx > -expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq) > +expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq, > + ccmp_uniform_cache &cache) > { > tree_code code = gimple_assign_rhs_code (g); > basic_block bb = gimple_bb (g); > @@ -270,22 +325,34 @@ expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, > rtx_insn **gen_seq) > } > else > { > - tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq); > + tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq, cache); > if (!tmp) > return NULL_RTX; > return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq); > } > } > - else > + else if (ccmp_tree_comparison_p (op1, bb)) > { > gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR > || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR); > - gcc_assert (ccmp_tree_comparison_p (op1, bb)); > - tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq); > + tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq, cache); > if (!tmp) > return NULL_RTX; > return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq); > } > + else > + { > + /* Start with one operand and append the uniform operand. */ > + tree first = op0, rest = op1; > + if (!ccmp_uniform_chain_p (op1, code, bb, cache)) > + std::swap (first, rest); > + > + tmp = expand_ccmp_expr_1 (get_gimple_for_ssa_name (first), > + prep_seq, gen_seq, cache); > + if (!tmp) > + return NULL_RTX; > + return expand_ccmp_chain (rest, code, tmp, prep_seq, gen_seq); > + } > } > > /* Main entry to expand conditional compare statement G. > @@ -296,14 +363,15 @@ expand_ccmp_expr (gimple *g, machine_mode mode) > { > rtx_insn *last; > rtx tmp; > + ccmp_uniform_cache cache; > > - if (!ccmp_candidate_p (g, true)) > + if (!ccmp_candidate_p (g, cache, true)) > return NULL_RTX; > > last = get_last_insn (); > > rtx_insn *prep_seq = NULL, *gen_seq = NULL; > - tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq); > + tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq, cache); > > if (tmp) > { > 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_6.c > b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c > new file mode 100644 > index 00000000000..aa2710775e5 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c > @@ -0,0 +1,89 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2" } */ > +/* { dg-final { check-function-bodies "**" "" } } */ > + > +/* Reassociation rebalances a chain of four comparisons into a tree, so the > + conditional compare expander has to linearise it again. */ > + > +/* > +** and_tree: > +** cmp w0, w1 > +** ccmp w2, w3, 0, lt > +** ccmp w4, w5, 0, lt > +** ccmp w6, w7, 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 w0, w1 > +** ccmp w2, w3, 1, ge > +** ccmp w4, w5, 1, ge > +** ccmp w6, w7, 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)); > +} > + > +/* An AND chain that has to come first and a uniform OR chain. */ > + > +/* > +** ior_of_and: > +** cmp w4, w5 > +** ccmp w6, w7, 0, lt > +** ccmp w2, w3, 1, ge > +** ccmp w0, w1, 1, ge > +** cset w0, lt > +** ret > +*/ > +int > +ior_of_and (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)); > +} > + > +/* An OR chain that has to come first and a uniform AND chain. */ > + > +/* > +** and_of_ior_chain: > +** cmp w4, w5 > +** ccmp w6, w7, 1, ge > +** ccmp w2, w3, 0, lt > +** ccmp w0, w1, 0, lt > +** cset w0, lt > +** ret > +*/ > +int > +and_of_ior_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)); > +} > + > +/* The chain is linear, so neither of these can be expressed as one sequence > + of conditional compares. Both operands would have to keep a value in the > + flags at the same time. */ > + > +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)); > +} > + > +int > +ior_of_and_2 (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 } > } */ > +/* { dg-final { scan-assembler-times {\torr\tw[0-9]+, w[0-9]+, w[0-9]+} 1 } > } */ > -- > 2.50.1 (Apple Git-155) >
