Re: [PATCH] match: fold two comparisons of a masked value

On Tue, Aug 4, 2026 at 11:44=E2=80=AFAM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
>   ((X + C1) & LOWMASK) =3D=3D/!=3D C2 -> (X & LOWMASK) =3D=3D/!=3D C2 - C=
1
>   (X & HIGHMASK) >/<=3D C -> X >/<=3D (C | ~HIGHMASK)
>
> Only the low bits of the addition survive the first mask, so the constant
> moves to the other side of the comparison and the addition goes away.  A
> comparison constant that does not fit the mask makes the result fixed.
>
> Clearing the low bits rounds the value down, and a rounded value passes a
> relational comparison exactly when the value itself passes it against the
> constant with those bits set, so the second mask goes away too.  The
> other two predicates are already canonicalised into these.
>
>   int f (int x) { return (x & -8) > 16; }
>
> aarch64 -O2:
>
>   before                          after
>     and   w0, w0, -8                cmp   w0, 23
>     cmp   w0, 16                    cset  w0, gt
>     cset  w0, gt
>
> Two existing tests observe shapes this rewrite now folds.  bic-bitmask-19=
.c
> scans for "> 1" and the loop guard (n & -16) > 0 becomes n > 15, which th=
e
> regex also matches, so it is anchored on the statement end.  pr68217.c
> relies on the comparison keeping the masked value live, so the value is
> returned instead.
>
> Keep signed additions that trap or carry sanitizer instrumentation.
> Also accept high-mask constants whose discarded low bits are already set.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?

OK.

Thanks,
Richard.

> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
>         * match.pd (((X + C1) & LOWMASK) =3D=3D/!=3D C2): New simplificat=
ion.
>         ((X & HIGHMASK) >/<=3D C): Likewise.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/maskcmp-1.c: New test.
>         * gcc.dg/bic-bitmask-19.c: Anchor the comparison scan.
>         * gcc.dg/pr68217.c: Return the masked value.
>         * gcc.dg/tree-ssa/maskcmp-overflow-1.c: New test.
>         * gcc.dg/tree-ssa/maskcmp-overflow-2.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
>  gcc/match.pd                                  | 28 +++++++++++++++++++
>  gcc/testsuite/gcc.dg/bic-bitmask-19.c         |  4 ++-
>  gcc/testsuite/gcc.dg/pr68217.c                | 12 ++++++--
>  gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c     | 23 +++++++++++++++
>  .../gcc.dg/tree-ssa/maskcmp-overflow-1.c      | 10 +++++++
>  .../gcc.dg/tree-ssa/maskcmp-overflow-2.c      | 10 +++++++
>  6 files changed, 83 insertions(+), 4 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 9924f95c4cc..b27d9a0bad0 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5354,6 +5354,34 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>          && wi::lshift (wi::to_wide (@0), cand) =3D=3D wi::to_wide (@2))
>       (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); }))))))
>
> +/* Fold ((X + C1) & LOWMASK) =3D=3D/!=3D C2 into (X & LOWMASK) =3D=3D/!=
=3D C2 - C1.
> +   Only the low bits of the addition survive the mask, so the constant c=
an
> +   move to the other side of the comparison and the addition goes away. =
 */
> +(for cmp (eq ne)
> + (simplify
> +  (cmp (bit_and:s (plus:s @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3=
)
> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +       && !TYPE_OVERFLOW_TRAPS (TREE_TYPE (@0))
> +       && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0))
> +       && wi::popcount (wi::to_wide (@2) + 1) =3D=3D 1)
> +   (with { wide_int mask =3D wi::to_wide (@2);
> +          wide_int rhs =3D (wi::to_wide (@3) - wi::to_wide (@1)) & mask;=
 }
> +    (if ((wi::to_wide (@3) & ~mask) =3D=3D 0)
> +     (cmp (bit_and @0 @2)
> +         { wide_int_to_tree (TREE_TYPE (@0), rhs); })
> +     { constant_boolean_node (cmp =3D=3D NE_EXPR, type); }))))
> +
> +/* Fold (X & HIGHMASK) >/<=3D C into X >/<=3D (C | ~HIGHMASK).  Clearing=
 the
> +   low bits of X rounds it down, and a rounded value passes the comparis=
on
> +   exactly when X passes it against the constant with those bits set.  *=
/
> +(for cmp (gt le)
> + (simplify
> +  (cmp (bit_and:s @0 INTEGER_CST@1) INTEGER_CST@2)
> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +       && bitmask_inv_cst_vector_p (@1))
> +   (with { wide_int c =3D wi::to_wide (@2) | wi::bit_not (wi::to_wide (@=
1)); }
> +    (cmp @0 { wide_int_to_tree (TREE_TYPE (@0), c); })))))
> +
>  /* Fold ((X << C1) & C2) cmp C3 into (X & (C2 >> C1)) cmp (C3 >> C1)
>         ((X >> C1) & C2) cmp C3 into (X & (C2 << C1)) cmp (C3 << C1).  */
>  (for cmp (ne eq)
> diff --git a/gcc/testsuite/gcc.dg/bic-bitmask-19.c b/gcc/testsuite/gcc.dg=
/bic-bitmask-19.c
> index aa139da5c1e..d1574fbff80 100644
> --- a/gcc/testsuite/gcc.dg/bic-bitmask-19.c
> +++ b/gcc/testsuite/gcc.dg/bic-bitmask-19.c
> @@ -19,6 +19,8 @@ void fun2(uint32_t *x, int n)
>
>  #include "bic-bitmask.h"
>
> -/* { dg-final { scan-tree-dump-times {>\s* 1} 1 dce7 { target vect_int }=
 } } */
> +/* The loop guard (n & -16) > 0 now folds to n > 15, so anchor the scan =
on
> +   the statement end to keep it matching only the comparison under test.=
  */
> +/* { dg-final { scan-tree-dump-times {>\s* 1;} 1 dce7 { target vect_int =
} } } */
>  /* { dg-final { scan-tree-dump-not {&\s* 4294967294} dce7 { target vect_=
int } } } */
>
> diff --git a/gcc/testsuite/gcc.dg/pr68217.c b/gcc/testsuite/gcc.dg/pr6821=
7.c
> index 60c80106760..279fedd86f4 100644
> --- a/gcc/testsuite/gcc.dg/pr68217.c
> +++ b/gcc/testsuite/gcc.dg/pr68217.c
> @@ -1,13 +1,19 @@
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fno-tree-ccp"=
 } */
>
> -int foo (void)
> +#include <limits.h>
> +
> +/* Return x so that its range is still exported after the comparison fol=
ds
> +   away.  (x & LLONG_MIN) < 1 is true for both values x can take, so the
> +   test of it no longer keeps x live by itself.  */
> +
> +long long foo (void)
>  {
>      volatile int a =3D -1;
> -    long long b =3D (1LL << (sizeof (b) * 8 - 1)); // LLONG_MIN
> +    long long b =3D LLONG_MIN;
>      long long x =3D (a & b); // x =3D=3D 0x8000000000000000
>      if (x < 1LL) { ; } else { __builtin_abort(); }
> -    return 0;
> +    return x;
>  }
>
>  /* { dg-final { scan-tree-dump "\\\[-INF, -INF\\\]\\\[0, 0\\\]" "vrp1" }=
 } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c b/gcc/testsuite/gc=
c.dg/tree-ssa/maskcmp-1.c
> new file mode 100644
> index 00000000000..97025c45b1d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* Only the low bits of the addition survive the mask, so the constant
> +   moves to the other side of the comparison.  */
> +int f1 (unsigned int x) { return ((x + 3u) & 7u) =3D=3D 5u; }
> +int f2 (unsigned int x) { return ((x + 300u) & 255u) !=3D 7u; }
> +
> +/* The comparison constant does not fit the mask, the result is fixed.  =
*/
> +int f3 (unsigned int x) { return ((x + 3u) & 7u) =3D=3D 9u; }
> +
> +/* Clearing the low bits rounds down, so the comparison constant can abs=
orb
> +   them and the mask goes away.  */
> +int f4 (int x) { return (x & -8) > 16; }
> +int f5 (int x) { return (x & -8) <=3D -16; }
> +int f6 (unsigned int x) { return (x & 0xfffffff0u) > 100u; }
> +
> +/* { dg-final { scan-tree-dump-not " \\+ " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " & 7;" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " & 255" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " > 23" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " < -8" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " > 111" 1 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c b/gcc/tes=
tsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c
> new file mode 100644
> index 00000000000..02e6d04bfff
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c
> @@ -0,0 +1,10 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */
> +
> +int
> +f (int x)
> +{
> +  return ((x + 1) & 7) =3D=3D 0;
> +}
> +
> +/* { dg-final { scan-tree-dump "\\+ 1" "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c b/gcc/tes=
tsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c
> new file mode 100644
> index 00000000000..bacec863f28
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c
> @@ -0,0 +1,10 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fsanitize=3Dsigned-integer-overflow -fdump-tree-op=
timized" } */
> +
> +int
> +f (int x)
> +{
> +  return ((x + 1) & 7) =3D=3D 0;
> +}
> +
> +/* { dg-final { scan-tree-dump "UBSAN_CHECK_ADD" "optimized" } } */
> --
> 2.50.1 (Apple Git-155)
>