On Wed, Jul 29, 2026 at 12:30 PM Jakub Jelinek <[email protected]> wrote:
>
> Hi!
>
> This simplification for power of two @1 and @2 folds to false (resp.
> to true for the == version) if @1 is larger than @2 (in unsigned
> comparison), because @1 & @2 is known to be zero (i.e. for shift count 0)
> and for shift count larger than that it will be zero too, either because
> @1 << @0 is even larger, or if @0 is too large @1 << @0 overflows to zero.
> This is the case of e.g. ((4 << x) & 2) != 0, which is always false.
> Now, this PR is about a different problem, if @1 is smaller than @2, say
> ((1 << x) & 256) != 0, but x has a very narrow type, say unsigned _BitInt(3),
> then the largest possible value of x is 7 and ((1 << 7) & 256) is
> still 0, 1 << 7 is 128 and so still smaller than 256.
> So, if c1 - c2 is larger than maximum value of the shift count type
> (resp. for the other case c2 - c1), it will be also always false (resp.
> true).
> Trying to improve it and using range of x (aka @0) is not needed,
> this simplification folds it into @0 != (c1 - c2) and so will be folded
> later. Just the case where c1 - c2 overflows is problematic because
> we've lost the details (unless we'd promote both operands or something).
> Another possible way to do this would be build_int_cst and check for
> the overflow flags, but I think this is shorter.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk/16.2?
>
> 2026-07-29 Jakub Jelinek <[email protected]>
>
> PR tree-optimization/126476
> * match.pd (((C << A) & D) != 0 -> A == 0,
> ((C << A) & D) == 0 -> A != 0): Fold to false/true if
> c1 - c2 resp. c2 - c1 is larger than maximum value of
> A.
>
> * gcc.dg/torture/bitint-103.c: New test.
>
> --- gcc/match.pd.jj 2026-07-29 17:21:33.893285488 +0200
> +++ gcc/match.pd 2026-07-29 17:17:59.855012063 +0200
> @@ -5293,7 +5293,11 @@ (define_operator_list SYNC_FETCH_AND_AND
> (cmp (bit_and (lshift integer_pow2p@1 @0) integer_pow2p@2) integer_zerop)
> (with { int c1 = wi::clz (wi::to_wide (@1));
> int c2 = wi::clz (wi::to_wide (@2)); }
> - (if (c1 < c2)
> + (if (c1 < c2
> + /* If c1 - c2 isn't representable in TREE_TYPE (@0), it is also
> + never true, because for any valid x C << x will be smaller
> + than D. See PR126476. */
> + || c1 - c2 > wi::to_widest (TYPE_MAX_VALUE (TREE_TYPE (@0))))
I was worried that TYPE_MAX_VALUE might not be constant but we depend
on it being constant in other places.
Approved.
> { constant_boolean_node (cmp == NE_EXPR ? false : true, type); }
> (icmp @0 { build_int_cst (TREE_TYPE (@0), c1 - c2); }))))
> (simplify
> @@ -5301,7 +5305,8 @@ (define_operator_list SYNC_FETCH_AND_AND
> (if (tree_int_cst_sgn (@1) > 0)
> (with { int c1 = wi::clz (wi::to_wide (@1));
> int c2 = wi::clz (wi::to_wide (@2)); }
> - (if (c1 > c2)
> + (if (c1 > c2
> + || c2 - c1 > wi::to_widest (TYPE_MAX_VALUE (TREE_TYPE (@0))))
> { constant_boolean_node (cmp == NE_EXPR ? false : true, type); }
> (icmp @0 { build_int_cst (TREE_TYPE (@0), c2 - c1); }))))))
>
> --- gcc/testsuite/gcc.dg/torture/bitint-103.c.jj 2026-07-29
> 17:19:45.916660975 +0200
> +++ gcc/testsuite/gcc.dg/torture/bitint-103.c 2026-07-29 17:20:08.750370102
> +0200
> @@ -0,0 +1,22 @@
> +/* PR tree-optimization/126476 */
> +/* { dg-do run { target bitint } } */
> +
> +[[gnu::noipa]] int
> +foo (unsigned _BitInt(4) n)
> +{
> + return ((1ULL << n) & (1ULL << 20)) != 0;
> +}
> +
> +[[gnu::noipa]] int
> +bar (unsigned _BitInt(4) n)
> +{
> + return (((1ULL << 40) >> n) & (1ULL << 20)) != 0;
> +}
> +
> +int
> +main ()
> +{
> + for (unsigned i = 0; i < 16; i++)
> + if (foo (i) != 0 || bar (i) != 0)
> + __builtin_abort ();
> +}
>
> Jakub
>
