Re: [PATCH] Improve VRP of BIT_AND_EXPR

[Richard Guenther <richard dot guenther at gmail dot com>]

On Thu, Jul 8, 2010 at 7:07 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> Looking at PR44858, I was surprised VRP doesn't figure out
> for
> x = (a > b);
> y = x & 2;
> that y is 0. ?Similarly say for x & y when
> x is [1024, 1039] and y is [2048, 2063], we can count
> on the result being [0, 15] (the 0x400 and 0x800 bits are both cleared),
> etc.
>
> The following patch improves handling of BIT_AND_EXPR.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux. ?Ok for trunk?
>
> In the testsuite slp-perm-4.c was the only failure, because in
> for (i = 0; i < 16; i++)
> ?{
> ? ?i %= 256;
> ? ?if (i > 200)
> ? ? ?abort ();
> ? ?...
> ?}
> with the patch the conditional and abort is now optimized away - previously
> i &= 255; was VARYING, now is [0, 15].
>
> As next step, I guess VRP should be able to optimize that &= 255 away
> completely, because the argument is known to be [0, 15], so doesn't need
> any masking.

Ok.

Thanks,
Richard.

> 2010-07-08 ?Jakub Jelinek ?<jakub@redhat.com>
>
> ? ? ? ?* tree-vrp.c (extract_range_from_binary_expr) <BIT_AND_EXPR>: If
> ? ? ? ?both ranges are range_int_cst_p with non-negative minimum,
> ? ? ? ?try harder to derive smaller range.
>
> ? ? ? ?* gcc.dg/tree-ssa/vrp50.c: New test.
> ? ? ? ?* gcc.dg/vect/slp-perm-4.c (main): Make sure loop isn't vectorized.
>
> --- gcc/tree-vrp.c.jj ? 2010-07-05 12:37:01.000000000 +0200
> +++ gcc/tree-vrp.c ? ? ?2010-07-08 16:03:11.000000000 +0200
> @@ -2577,6 +2577,58 @@ extract_range_from_binary_expr (value_ra
>
> ? ? ? if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
> ? ? ? ?min = max = int_const_binop (code, vr0.max, vr1.max, 0);
> + ? ? ?else if (range_int_cst_p (&vr0)
> + ? ? ? ? ? ? ?&& range_int_cst_p (&vr1)
> + ? ? ? ? ? ? ?&& tree_int_cst_sgn (vr0.min) >= 0
> + ? ? ? ? ? ? ?&& tree_int_cst_sgn (vr1.min) >= 0)
> + ? ? ? {
> + ? ? ? ? double_int vr0_mask = tree_to_double_int (vr0.min);
> + ? ? ? ? double_int vr1_mask = tree_to_double_int (vr1.min);
> + ? ? ? ? double_int maxd, diff;
> + ? ? ? ? tree mask;
> +
> + ? ? ? ? min = build_int_cst (expr_type, 0);
> + ? ? ? ? /* Compute non-zero bits mask from both ranges. ?*/
> + ? ? ? ? if (!vr0_int_cst_singleton_p)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? maxd = tree_to_double_int (vr0.max);
> + ? ? ? ? ? ? diff = double_int_sub (maxd, vr0_mask);
> + ? ? ? ? ? ? if (diff.high)
> + ? ? ? ? ? ? ? {
> + ? ? ? ? ? ? ? ? diff.low = ~(unsigned HOST_WIDE_INT)0;
> + ? ? ? ? ? ? ? ? diff.high = ((HOST_WIDE_INT) 2
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?<< floor_log2 (diff.high)) - 1;
> + ? ? ? ? ? ? ? }
> + ? ? ? ? ? ? else
> + ? ? ? ? ? ? ? diff.low = ((HOST_WIDE_INT) 2 << floor_log2 (diff.low)) - 1;
> + ? ? ? ? ? ? vr0_mask = double_int_ior (vr0_mask,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?double_int_ior (maxd, diff));
> + ? ? ? ? ? }
> + ? ? ? ? if (!vr1_int_cst_singleton_p)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? maxd = tree_to_double_int (vr1.max);
> + ? ? ? ? ? ? diff = double_int_sub (maxd, vr1_mask);
> + ? ? ? ? ? ? if (diff.high)
> + ? ? ? ? ? ? ? {
> + ? ? ? ? ? ? ? ? diff.low = ~(unsigned HOST_WIDE_INT)0;
> + ? ? ? ? ? ? ? ? diff.high = ((HOST_WIDE_INT) 2
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?<< floor_log2 (diff.high)) - 1;
> + ? ? ? ? ? ? ? }
> + ? ? ? ? ? ? else
> + ? ? ? ? ? ? ? diff.low = ((HOST_WIDE_INT) 2 << floor_log2 (diff.low)) - 1;
> + ? ? ? ? ? ? vr1_mask = double_int_ior (vr1_mask,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?double_int_ior (maxd, diff));
> + ? ? ? ? ? }
> + ? ? ? ? mask = double_int_to_tree (expr_type,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?double_int_and (vr0_mask, vr1_mask));
> + ? ? ? ? max = vr0.max;
> + ? ? ? ? if (tree_int_cst_lt (vr1.max, max))
> + ? ? ? ? ? max = vr1.max;
> + ? ? ? ? if (!TREE_OVERFLOW (mask)
> + ? ? ? ? ? ? && tree_int_cst_lt (mask, max)
> + ? ? ? ? ? ? && tree_int_cst_sgn (mask) >= 0)
> + ? ? ? ? ? max = mask;
> + ? ? ? }
> ? ? ? else if (vr0_int_cst_singleton_p
> ? ? ? ? ? ? ? && tree_int_cst_sgn (vr0.max) >= 0)
> ? ? ? ?{
> --- gcc/testsuite/gcc.dg/tree-ssa/vrp50.c.jj ? ?2010-07-08 16:24:42.000000000 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/vrp50.c ? ? ? 2010-07-08 16:32:26.000000000 +0200
> @@ -0,0 +1,36 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp1" } */
> +
> +int
> +foo (unsigned int i, unsigned int j)
> +{
> + ?i &= 15;
> + ?j &= 15;
> + ?i += 1024;
> + ?j += 2048;
> + ?i &= j;
> + ?return i < 16;
> +}
> +
> +int
> +bar (int i)
> +{
> + ?int c = 2;
> + ?c &= i > 6;
> + ?return c == 0;
> +}
> +
> +int baz (int x, int y)
> +{
> + ?x &= 15;
> + ?y &= 15;
> + ?x += 4;
> + ?y += 16;
> + ?x &= y;
> + ?return x < 20;
> +}
> +
> +/* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
> +/* { dg-final { scan-tree-dump "Folding predicate c_\[^\n\r\]* to 1" "vrp1" } } */
> +/* { dg-final { scan-tree-dump "Folding predicate x_\[^\n\r\]* to 1" "vrp1" } } */
> +/* { dg-final { cleanup-tree-dump "vrp1" } } */
> --- gcc/testsuite/gcc.dg/vect/slp-perm-4.c.jj ? 2010-06-11 11:00:46.000000000 +0200
> +++ gcc/testsuite/gcc.dg/vect/slp-perm-4.c ? ? ?2010-07-08 18:53:40.102558207 +0200
> @@ -69,6 +69,7 @@ int main (int argc, const char* argv[])
> ? ? ? if (input[i] > 200)
> ? ? ? ? abort();
> ? ? ? output[i] = 0;
> + ? ? ?__asm__ volatile ("");
> ? ? }
>
> ? foo (input, output);
>
>
> ? ? ? ?Jakub
>