On Wed, Aug 12, 2026 at 12:17 AM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> Linux spells a power-of-two round up as:
>
> ((x - 1) | (2^k - 1)) + 1
>
> For wrapping arithmetic, this is:
>
> (x + (2^k - 1)) & -(2^k)
>
> The latter form needs one fewer operation and exposes the zero low bits.
> Apply the identity to scalar and vector integral types. Use :s on the
> inclusive-or expression so the fold does not add work when that value
> remains live.
>
> unsigned long round_up (unsigned long x)
> {
> return ((x - 1) | 4095) + 1;
> }
>
> aarch64 -O2:
>
> before:
>
> round_up:
> sub x0, x0, #1
> orr x0, x0, 4095
> add x0, x0, 1
> ret
>
> after:
>
> round_up:
> add x0, x0, 4095
> and x0, x0, -4096
> ret
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
> * match.pd (((X - 1) | C) + 1): New simplification.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/round-up-ior-1.c: New test.
> * gcc.dg/tree-ssa/round-up-ior-2.c: Likewise.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
> gcc/match.pd | 17 ++++++++++
> .../gcc.dg/tree-ssa/round-up-ior-1.c | 34 +++++++++++++++++++
> .../gcc.dg/tree-ssa/round-up-ior-2.c | 10 ++++++
> 3 files changed, 61 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 0ba97b32cb1..40dcd886478 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2062,6 +2062,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> (bit_and (plus @0 @1)
> { build_uniform_cst
> (type, wide_int_to_tree (etype, wi::bit_not (c))); }))))
> +
> +/* ((X - 1) | C) + 1 -> (X + C) & ~C, for C a low mask 2^k - 1.
> + Both forms round X up to a multiple of 2^k. */
> +(simplify
> + (plus (bit_ior:s (plus @0 integer_minus_onep)
> + uniform_integer_cst_p@1)
> + integer_onep)
> + (with { tree cst = uniform_integer_cst_p (@1);
> + tree etype = TREE_TYPE (cst);
> + wide_int c = wi::to_wide (cst); }
> + (if (ANY_INTEGRAL_TYPE_P (type)
ANY_INTEGRAL_TYPE_P will always be true because of
uniform_integer_cst_p and the matching of bit_ior with plus (pointers
can't use plus, and floating point should not be using BIT_IOR but we
don't check that yet).
> + && TYPE_OVERFLOW_WRAPS (type)
> + && c != 0
> + && wi::popcount (c + 1) == 1)
> + (bit_and (plus @0 @1)
> + { build_uniform_cst
> + (type, wide_int_to_tree (etype, wi::bit_not (c))); }))))
Add a return here.
Otherwise ok.
> /* (x + y) - min (x, y) -> max (x, y)
> (x + y) - max (x, y) -> min (x, y)
> The sum of the minimum and the maximum is the sum of the operands. */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
> new file mode 100644
> index 00000000000..991a429742c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
> @@ -0,0 +1,34 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +typedef unsigned int v4ui __attribute__ ((vector_size (16)));
> +
> +unsigned long
> +round_up (unsigned long x)
> +{
> + return ((x - 1) | 4095) + 1;
> +}
> +
> +unsigned long
> +round_up_pages (unsigned long x)
> +{
> + return (((x - 1) | 4095) + 1) >> 12;
> +}
> +
> +v4ui
> +round_up_vec (v4ui x)
> +{
> + v4ui one = { 1, 1, 1, 1 };
> + v4ui mask = { 15, 15, 15, 15 };
> + return ((x - one) | mask) + one;
> +}
> +
> +unsigned long
> +keep (unsigned long x)
> +{
> + return ((x - 1) | 4096) + 1;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "\\| 4095" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "\\|.*15" "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "\\| 4096" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
> new file mode 100644
> index 00000000000..014aeed4c61
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
> @@ -0,0 +1,10 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fwrapv -fdump-tree-optimized" } */
> +
> +int
> +round_up (int x)
> +{
> + return ((x - 1) | 15) + 1;
> +}
> +
> +/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */
> --
> 2.50.1 (Apple Git-155)
>
