Re: [PATCH] match: fold two idioms built from the negation of a value

On Thu, Aug 6, 2026 at 2:23 AM Andrea Pinski
<[email protected]> wrote:
>
> On Tue, Aug 4, 2026 at 3:18 AM <[email protected]> wrote:
> >
> > From: Kyrylo Tkachov <[email protected]>
> >
> > X | -X has every bit from the lowest set bit of X upwards, so adding X to
> > it clears that bit, and masking with it isolates the padding needed to
> > round X up:
> >
> >   X + (X | -X) -> X & (X - 1)
> >   X + ((-X) & (C - 1)) -> (X + C - 1) & -C   for a power of two C
> >
> > The second is the alignment round up written with the padding computed
> > first, which is how allocators tend to spell it.
> >
> > Neither needs a wrapping type.  X - 1 overflows only for the most
> > negative value, where the source already does, and rounding X up is
> > representable exactly when X + C - 1 is, because the largest multiple of
> > C below the maximum leaves room for C - 1.  The inclusive or and the
> > conjunction already force an integral type.
> >
> >   int f (int x) { return x + ((-x) & 15); }
> >
> > aarch64 -O2:
> >
> >   before                          after
> >     neg   w1, w0                    add   w0, w0, 15
> >     and   w1, w1, 15                and   w0, w0, -16
> >     add   w0, w1, w0
> >
> > The vector spelling folds too, a uniform vector constant is matched with
> > uniform_integer_cst_p.
> >
> > Keep trapping and sanitized negations.
> > Require the consumed padding value to become dead so that the fold cannot add work.
> >
> > Bootstrapped and tested on aarch64-none-linux-gnu.
> > Ok for trunk?
> > Thanks,
> > Kyrill
> >
> > gcc/ChangeLog:
> >
> >         * match.pd (X + (X | -X)): New simplification.
> >         (X + ((-X) & (C - 1))): Likewise.
> >
> > gcc/testsuite/ChangeLog:
> >
> >         * gcc.dg/tree-ssa/signbit-1.c: New test.
> >         * gcc.dg/tree-ssa/alignup-2.c: New test.
> >         * gcc.dg/tree-ssa/vector-alignup-1.c: New test.
> >         * gcc.dg/tree-ssa/alignup-overflow-1.c: New test.
> >         * gcc.dg/tree-ssa/alignup-overflow-2.c: New test.
> >
> > Signed-off-by: Kyrylo Tkachov <[email protected]>
> > ---
> >  gcc/match.pd                                  | 21 ++++++++++++++
> >  gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c     | 28 +++++++++++++++++++
> >  .../gcc.dg/tree-ssa/alignup-overflow-1.c      | 10 +++++++
> >  .../gcc.dg/tree-ssa/alignup-overflow-2.c      | 10 +++++++
> >  gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c     | 26 +++++++++++++++++
> >  .../gcc.dg/tree-ssa/vector-alignup-1.c        | 15 ++++++++++
> >  6 files changed, 110 insertions(+)
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c
> >
> > diff --git a/gcc/match.pd b/gcc/match.pd
> > index 2d172b5f5a0..800864ce9e2 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -2088,6 +2088,27 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >         && !TYPE_OVERFLOW_SANITIZED (type) && !TYPE_OVERFLOW_TRAPS (type))
> >     (maxmin @0 @1))))
> >
> > +/* X + (X | -X) -> X & (X - 1).  X | -X has every bit from the lowest set
> > +   bit of X upwards, so adding it clears that bit.  */
> > +(simplify
> > + (plus:c @0 (bit_ior:c@2 @0 (negate @0)))
> > + (if (single_use (@2))

Using :s on the bit_ior should work fine in this case and would
allow the transform when (plus @0 -1) is already available.

I think you need to at least guard it with ANY_INTEGRAL_TYPE_P,
fixed-point [saturating] types also allow bit_ior.

> > +  (bit_and @0 (plus @0 { build_minus_one_cst (type); }))))
> > +
> > +/* X + ((-X) & (C - 1)) -> (X + C - 1) & -C for a power of two C, the
> > +   round up to a multiple of C written with the padding computed first.  */
> > +(simplify
> > + (plus:c @0 (bit_and:c@2 (negate @0) uniform_integer_cst_p@1))
> > + (with { tree cst = uniform_integer_cst_p (@1);
> > +        tree etype = TREE_TYPE (cst);
> > +        wide_int c = wi::to_wide (cst); }
> > +  (if (single_use (@2)

Likewise here.

> > +       && !TYPE_OVERFLOW_TRAPS (type)
> > +       && !TYPE_OVERFLOW_SANITIZED (type)

And these should always be paired with [ANY_]INTEGRAL_TYPE_P
checks.

OK with those changes and the testcase adjustment to require int32plus

Richard.

> > +       && wi::popcount (c + 1) == 1)
> > +   (bit_and (plus @0 @1)
> > +           { build_uniform_cst
> > +               (type, wide_int_to_tree (etype, wi::bit_not (c))); }))))
> >  /* (x | y) - y -> (x & ~y) */
> >  (simplify
> >   (minus (bit_ior:cs @0 @1) @1)
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c b/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
> > new file mode 100644
> > index 00000000000..eb9212e728c
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
> > @@ -0,0 +1,28 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +
> > +/* Rounding up by adding the padding is the same as rounding up with a
> > +   mask.  */
> > +
> > +unsigned int f1 (unsigned int x) { return x + ((-x) & 15u); }
> > +unsigned int f2 (unsigned int x) { return ((-x) & 4095u) + x; }
> > +unsigned long f3 (unsigned long x) { return x + ((-x) & 63ul); }
> > +
> > +/* The identity needs no wrapping type, a signed operand works too.  */
> > +int f5 (int x) { return x + ((-x) & 15); }
> > +
> > +unsigned int f6 (unsigned int x, unsigned int *p)
> > +{
> > +  unsigned int pad = (-x) & 15u;
> > +  *p = pad;
> > +  return x + pad;
> > +}
> > +
> > +/* Not a power of two, leave it alone.  */
> > +unsigned int f4 (unsigned int x) { return x + ((-x) & 14u); }
> > +
> > +/* { dg-final { scan-tree-dump-times " & 14;" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & 4294967280" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & 4294963200" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & -16" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & 15" 1 "optimized" } } */
>
> This testcase depends on int being 32bits ... so needs at least int32.
> I have not done any other review of the patch though.
>
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c
> > new file mode 100644
> > index 00000000000..f4995d08cc0
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c
> > @@ -0,0 +1,10 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */
> > +
> > +int
> > +f (int x)
> > +{
> > +  return x + ((-x) & 15);
> > +}
> > +
> > +/* { dg-final { scan-tree-dump " -x" "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c
> > new file mode 100644
> > index 00000000000..75e29d60189
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c
> > @@ -0,0 +1,10 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fsanitize=signed-integer-overflow -fdump-tree-optimized" } */
> > +
> > +int
> > +f (int x)
> > +{
> > +  return x + ((-x) & 15);
> > +}
> > +
> > +/* { dg-final { scan-tree-dump "UBSAN_CHECK_SUB" "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c b/gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c
> > new file mode 100644
> > index 00000000000..d7bcd91173b
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c
> > @@ -0,0 +1,26 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +
> > +/* X | -X has the sign bit set exactly when X is non-zero.  */
> > +
> > +int f1 (int x)
> > +{ return (x | -x) >> (__SIZEOF_INT__ * __CHAR_BIT__ - 1); }
> > +unsigned int f2 (unsigned int x)
> > +{ return (x | -x) >> (__SIZEOF_INT__ * __CHAR_BIT__ - 1); }
> > +long f3 (long x) { return (x | -x) >> (__SIZEOF_LONG__ * __CHAR_BIT__ - 1); }
> > +
> > +/* X + (X | -X) clears the lowest set bit of X.  The identity holds for a
> > +   signed operand too, X - 1 overflows only where the source does.  */
> > +unsigned int f4 (unsigned int x) { return x + (x | -x); }
> > +int f5 (int x) { return x + (x | -x); }
> > +
> > +unsigned int f6 (unsigned int x, unsigned int *p)
> > +{
> > +  unsigned int y = x | -x;
> > +  *p = y;
> > +  return x + y;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-times " \\| " 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " != 0" 3 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c b/gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c
> > new file mode 100644
> > index 00000000000..fec5c5c6b93
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c
> > @@ -0,0 +1,15 @@
> > +/* { dg-do compile } */
> > +/* { dg-require-effective-target vect_int } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +
> > +/* Rounding up by adding the padding, spelled with vectors.  */
> > +
> > +typedef unsigned int v4ui __attribute__((vector_size (16)));
> > +typedef int v4si __attribute__((vector_size (16)));
> > +
> > +v4ui f1 (v4ui x) { return x + ((-x) & 15); }
> > +v4si f2 (v4si x) { return x + ((-x) & 63); }
> > +
> > +/* { dg-final { scan-tree-dump-not "= -" "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " \\+ " 2 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
> > --
> > 2.50.1 (Apple Git-155)
> >