On Tue, Jul 21, 2026 at 4:11 AM Andrea Pinski <[email protected]> wrote: > > On Mon, Jul 20, 2026 at 8:16 AM <[email protected]> wrote: > > > > From: Kyrylo Tkachov <[email protected]> > > > > For one-bit values, forward propagation can leave an inverted value and a > > comparison on opposite sides of a bit operation: > > > > _1 = ~a_2; > > _3 = b_4 <= 0; > > _5 = _1 | _3; > > > > Apply De Morgan's law and invert the comparison to expose the associative > > operation: > > > > _3 = b_4 > 0; > > _5 = a_2 & _3; > > _6 = ~_5; > > > I am not sure which way we want here; ~(a&b) or (a & ~b). Especially > when both are reasonable to do. And `a & ~b` has an optab too.There is > an optab for `a | ~b` too: > OPTAB_D (andn_optab, "andn$a3") > OPTAB_D (iorn_optab, "iorn$a3") > > I have seen some cases where we have: > _1 = _2 CMP _3; > _4 = _5 CMP _6; > _7 = _1 & _4; > _8 = ~_1; > which was not folding info: > _t = _2 CMP' _3; > _tt = _5 CMP' _6; > _8 = _t | _tt;
It's difficult to say which one we should make canonical as we are likely not seeing the larger expression context. IMO most of the patterns that do not reduce expression complexity in this area should be integrated into a framework like backprop (get rid of ~), reassoc (simplify larger expressions) and VN/reassoc (reassoc to form common subexpressions). That said, I'm not sure we want this kind of pattern - those tend to facilitate oscillations of some sort. > > Handle the corresponding AND form in the same way. Use > > invert_tree_comparison so that unordered floating-point behavior is > > preserved, and leave the expression unchanged when the comparison cannot be > > inverted. > > This reads very verbose. And really does not mention why the > comparison can't be inverted; an ordered comparison traps while an > unordered one does not. > > > > Require the negation and comparison to have single uses to avoid > > duplicating work. > > This is not exactly right either. Yes it is a 1 bit complement > negation but normally it is called a bitwise not. These all together > make it feel like a LLM write this. > > > Restrict the simplification to scalar integral one-bit > > results. > > But why? The reason is because in generic the result of a comparison > can be any integral type rather than a boolean type. > > > > > The focused tests pass on AArch64 and x86_64. They cover both bit > > operations > > and the unordered comparison needed for a NaN operand. On AArch64 the > > integer > > OR case changes from: > > > > cmp > > eor > > cset > > orr > > > > to: > > > > and > > cmp > > ccmp > > cset > > > > The instruction count is unchanged, but the new form avoids materializing an > > intermediate comparison result and exposes conditional-compare formation. > > > > This comes out of the thread at: > > https://gcc.gnu.org/pipermail/gcc-patches/2026-July/723788.html > > and this patch is needed as a prerequisite for that work. > > For which part? Because it is not obvious. > > So I think for the testcases here we should be producing: > ``` > f_ior: > cmp w1, #1 > cset w8, lt > orn w8, w8, w0 > and w0, w8, #0x1 > ret > > f_and: > cmp w1, #1 > cset w9, lt > andn w0, w9, w0 > and w0, w0, #0x1 > ret > ``` > > That is form BIT_ANDN/BIT_IORN internal functions for this if they > exist for `a & ~b`/`a | ~b` during the last match. > > Thanks, > Andrea > > > > > Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux. > > > > gcc/ChangeLog: > > > > * match.pd: Apply De Morgan's law to a one-bit negation combined > > with a > > comparison. > > > > gcc/testsuite/ChangeLog: > > > > * gcc.dg/tree-ssa/forwprop-44.c: New test. > > * gcc.dg/tree-ssa/forwprop-45.c: Likewise. > > > > Signed-off-by: Kyrylo Tkachov <[email protected]> > > --- > > gcc/match.pd | 20 ++++++++++++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 25 ++++++++++++++++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 29 +++++++++++++++++++++ > > 3 files changed, 74 insertions(+) > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > > > diff --git a/gcc/match.pd b/gcc/match.pd > > index d1a12c35ed3..20a1f9e79d3 100644 > > --- a/gcc/match.pd > > +++ b/gcc/match.pd > > @@ -2057,6 +2057,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > > && element_precision (type) <= element_precision (TREE_TYPE (@1))) > > (bit_not (rop (convert @0) (convert @1)))))) > > > > +/* For one-bit values, expose an associative operation by applying De > > Morgan's > > + law and inverting the comparison: > > + ~X & (Y CMP Z) -> ~(X | (Y ICMP Z)) > > + ~X | (Y CMP Z) -> ~(X & (Y ICMP Z)) > > + where ICMP is the inverse of CMP. */ > > +(for op (bit_and bit_ior) > > + rop (bit_ior bit_and) > > + (for cmp (tcc_comparison) > > + icmp (inverted_tcc_comparison) > > + ncmp (inverted_tcc_comparison_with_nans) > > + (simplify > > + (op:c (bit_not:s @0) (cmp:s @1 @2)) > > + (if (INTEGRAL_TYPE_P (type) && TYPE_PRECISION (type) == 1) > > + (with { enum tree_code ic = invert_tree_comparison > > + (cmp, HONOR_NANS (@1)); } > > + (if (ic == icmp) > > + (bit_not (rop @0 (icmp @1 @2))) > > + (if (ic == ncmp) > > + (bit_not (rop @0 (ncmp @1 @2)))))))))) > > + > > /* If we are XORing or adding two BIT_AND_EXPR's, both of which are and'ing > > with a constant, and the two constants have no bits in common, > > we should treat this as a BIT_IOR_EXPR since this may produce more > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > new file mode 100644 > > index 00000000000..6cb79c742cc > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > @@ -0,0 +1,25 @@ > > +/* { dg-do compile } */ > > +/* { dg-options "-O2 -fdump-tree-forwprop1" } */ > > + > > +_Bool > > +f_ior (_Bool a, int b) > > +{ > > + _Bool na = !a; > > + _Bool cmp = b <= 0; > > + return na | cmp; > > +} > > + > > +_Bool > > +f_and (_Bool a, int b) > > +{ > > + _Bool na = !a; > > + _Bool cmp = b <= 0; > > + return na & cmp; > > +} > > + > > +/* The inverted comparisons expose an AND in f_ior and an OR in f_and. */ > > +/* { dg-final { scan-tree-dump-times " > 0;" 2 "forwprop1" } } */ > > +/* { dg-final { scan-tree-dump-not " <= 0;" "forwprop1" } } */ > > +/* { dg-final { scan-tree-dump-times " & " 1 "forwprop1" } } */ > > +/* { dg-final { scan-tree-dump-times " \\| " 1 "forwprop1" } } */ > > +/* { dg-final { scan-tree-dump-times " = ~" 2 "forwprop1" } } */ > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > new file mode 100644 > > index 00000000000..f2dfcb0f04e > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > @@ -0,0 +1,29 @@ > > +/* { dg-do run } */ > > +/* { dg-require-effective-target flt_dbl_ldbl_inf_nan } */ > > +/* { dg-options "-O2 -fno-trapping-math -fdump-tree-forwprop1" } */ > > +/* { dg-additional-options "-fno-finite-math-only" } */ > > + > > +__attribute__ ((noipa)) _Bool > > +f_ior_nan (_Bool a, float b) > > +{ > > + _Bool na = !a; > > + _Bool cmp = b <= 0.0f; > > + return na | cmp; > > +} > > + > > +int > > +main (void) > > +{ > > + float nan = __builtin_nanf (""); > > + > > + if (f_ior_nan (1, nan) != 0 > > + || f_ior_nan (0, nan) != 1 > > + || f_ior_nan (1, -1.0f) != 1 > > + || f_ior_nan (1, 1.0f) != 0) > > + __builtin_abort (); > > + return 0; > > +} > > + > > +/* The inverse of <= is unordered greater when NaNs are honored. */ > > +/* { dg-final { scan-tree-dump-times " u> " 1 "forwprop1" } } */ > > +/* { dg-final { scan-tree-dump-times " = ~" 1 "forwprop1" } } */ > > -- > > 2.50.1 (Apple Git-155) > >
