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

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))
> +  (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)
> +       && !TYPE_OVERFLOW_TRAPS (type)
> +       && !TYPE_OVERFLOW_SANITIZED (type)
> +       && 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)
>