Re: [PATCH] Improve VRP of integer division (PR rtl-optimization/38245)

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

On Mon, Dec 1, 2008 at 2:10 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> Here is the updated patch, bootstrapped/regtested on x86_64-linux
> (and with the tree-vrp.c changes also diffed with -ubp attached
> for better readability - there was a lot of code reindented).

Ok.

Thanks,
Richard.

> 2008-11-29  Jakub Jelinek  <jakub@redhat.com>
>
>        PR rtl-optimization/38245
>        * tree-vrp.c (abs_extent_range): New function.
>        (extract_range_from_binary_expr): Compute range
>        for *_DIV_EXPR even if vr1 is VR_VARYING, VR_ANTI_RANGE
>        or includes zero or if vr1 is VR_RANGE and op0 has some
>        other range.
>
>        * gcc.dg/pr38245-1.c: New test.
>        * gcc.dg/pr38245-2.c: New test.
>
> --- gcc/tree-vrp.c.jj   2008-10-02 11:10:48.000000000 +0200
> +++ gcc/tree-vrp.c      2008-12-01 12:12:06.000000000 +0100
> @@ -599,6 +599,42 @@ set_value_range_to_undefined (value_rang
>  }
>
>
> +/* If abs (min) < abs (max), set VR to [-max, max], if
> +   abs (min) >= abs (max), set VR to [-min, min].  */
> +
> +static void
> +abs_extent_range (value_range_t *vr, tree min, tree max)
> +{
> +  int cmp;
> +
> +  gcc_assert (TREE_CODE (min) == INTEGER_CST);
> +  gcc_assert (TREE_CODE (max) == INTEGER_CST);
> +  gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
> +  gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
> +  min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
> +  max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
> +  if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
> +    {
> +      set_value_range_to_varying (vr);
> +      return;
> +    }
> +  cmp = compare_values (min, max);
> +  if (cmp == -1)
> +    min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
> +  else if (cmp == 0 || cmp == 1)
> +    {
> +      max = min;
> +      min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
> +    }
> +  else
> +    {
> +      set_value_range_to_varying (vr);
> +      return;
> +    }
> +  set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
> +}
> +
> +
>  /* Return value range information for VAR.
>
>    If we have no values ranges recorded (ie, VRP is not running), then
> @@ -2108,11 +2144,17 @@ extract_range_from_binary_expr (value_ra
>   /* Refuse to operate on VARYING ranges, ranges of different kinds
>      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
>      because we may be able to derive a useful range even if one of
> -     the operands is VR_VARYING or symbolic range.  TODO, we may be
> -     able to derive anti-ranges in some cases.  */
> +     the operands is VR_VARYING or symbolic range.  Similarly for
> +     divisions.  TODO, we may be able to derive anti-ranges in
> +     some cases.  */
>   if (code != BIT_AND_EXPR
>       && code != TRUTH_AND_EXPR
>       && code != TRUTH_OR_EXPR
> +      && code != TRUNC_DIV_EXPR
> +      && code != FLOOR_DIV_EXPR
> +      && code != CEIL_DIV_EXPR
> +      && code != EXACT_DIV_EXPR
> +      && code != ROUND_DIV_EXPR
>       && (vr0.type == VR_VARYING
>          || vr1.type == VR_VARYING
>          || vr0.type != vr1.type
> @@ -2276,6 +2318,86 @@ extract_range_from_binary_expr (value_ra
>            }
>        }
>
> +      else if ((code == TRUNC_DIV_EXPR
> +               || code == FLOOR_DIV_EXPR
> +               || code == CEIL_DIV_EXPR
> +               || code == EXACT_DIV_EXPR
> +               || code == ROUND_DIV_EXPR)
> +              && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
> +       {
> +         /* For division, if op1 has VR_RANGE but op0 does not, something
> +            can be deduced just from that range.  Say [min, max] / [4, max]
> +            gives [min / 4, max / 4] range.  */
> +         if (vr1.type == VR_RANGE
> +             && !symbolic_range_p (&vr1)
> +             && !range_includes_zero_p (&vr1))
> +           {
> +             vr0.type = type = VR_RANGE;
> +             vr0.min = vrp_val_min (TREE_TYPE (op0));
> +             vr0.max = vrp_val_max (TREE_TYPE (op1));
> +           }
> +         else
> +           {
> +             set_value_range_to_varying (vr);
> +             return;
> +           }
> +       }
> +
> +      /* For divisions, if op0 is VR_RANGE, we can deduce a range
> +        even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
> +        include 0.  */
> +      if ((code == TRUNC_DIV_EXPR
> +          || code == FLOOR_DIV_EXPR
> +          || code == CEIL_DIV_EXPR
> +          || code == EXACT_DIV_EXPR
> +          || code == ROUND_DIV_EXPR)
> +         && vr0.type == VR_RANGE
> +         && (vr1.type != VR_RANGE
> +             || symbolic_range_p (&vr1)
> +             || range_includes_zero_p (&vr1)))
> +       {
> +         tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
> +         int cmp;
> +
> +         sop = false;
> +         min = NULL_TREE;
> +         max = NULL_TREE;
> +         if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
> +           {
> +             /* For unsigned division or when divisor is known
> +                to be non-negative, the range has to cover
> +                all numbers from 0 to max for positive max
> +                and all numbers from min to 0 for negative min.  */
> +             cmp = compare_values (vr0.max, zero);
> +             if (cmp == -1)
> +               max = zero;
> +             else if (cmp == 0 || cmp == 1)
> +               max = vr0.max;
> +             else
> +               type = VR_VARYING;
> +             cmp = compare_values (vr0.min, zero);
> +             if (cmp == 1)
> +               min = zero;
> +             else if (cmp == 0 || cmp == -1)
> +               min = vr0.min;
> +             else
> +               type = VR_VARYING;
> +           }
> +         else
> +           {
> +             /* Otherwise the range is -max .. max or min .. -min
> +                depending on which bound is bigger in absolute value,
> +                as the division can change the sign.  */
> +             abs_extent_range (vr, vr0.min, vr0.max);
> +             return;
> +           }
> +         if (type == VR_VARYING)
> +           {
> +             set_value_range_to_varying (vr);
> +             return;
> +           }
> +       }
> +
>       /* Multiplications and divisions are a bit tricky to handle,
>         depending on the mix of signs we have in the two ranges, we
>         need to operate on different values to get the minimum and
> @@ -2288,84 +2410,82 @@ extract_range_from_binary_expr (value_ra
>         (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
>         MAX1) and then figure the smallest and largest values to form
>         the new range.  */
> -
> -      /* Divisions by zero result in a VARYING value.  */
> -      else if (code != MULT_EXPR
> -              && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
> -       {
> -         set_value_range_to_varying (vr);
> -         return;
> -       }
> -
> -      /* Compute the 4 cross operations.  */
> -      sop = false;
> -      val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
> -      if (val[0] == NULL_TREE)
> -       sop = true;
> -
> -      if (vr1.max == vr1.min)
> -       val[1] = NULL_TREE;
>       else
>        {
> -         val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
> -         if (val[1] == NULL_TREE)
> -           sop = true;
> -       }
> +         gcc_assert ((vr0.type == VR_RANGE
> +                      || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
> +                     && vr0.type == vr1.type);
>
> -      if (vr0.max == vr0.min)
> -       val[2] = NULL_TREE;
> -      else
> -       {
> -         val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
> -         if (val[2] == NULL_TREE)
> +         /* Compute the 4 cross operations.  */
> +         sop = false;
> +         val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
> +         if (val[0] == NULL_TREE)
>            sop = true;
> -       }
>
> -      if (vr0.min == vr0.max || vr1.min == vr1.max)
> -       val[3] = NULL_TREE;
> -      else
> -       {
> -         val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
> -         if (val[3] == NULL_TREE)
> -           sop = true;
> -       }
> +         if (vr1.max == vr1.min)
> +           val[1] = NULL_TREE;
> +         else
> +           {
> +             val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
> +             if (val[1] == NULL_TREE)
> +               sop = true;
> +           }
>
> -      if (sop)
> -       {
> -         set_value_range_to_varying (vr);
> -         return;
> -       }
> +         if (vr0.max == vr0.min)
> +           val[2] = NULL_TREE;
> +         else
> +           {
> +             val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
> +             if (val[2] == NULL_TREE)
> +               sop = true;
> +           }
>
> -      /* Set MIN to the minimum of VAL[i] and MAX to the maximum
> -        of VAL[i].  */
> -      min = val[0];
> -      max = val[0];
> -      for (i = 1; i < 4; i++)
> -       {
> -         if (!is_gimple_min_invariant (min)
> -             || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
> -             || !is_gimple_min_invariant (max)
> -             || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
> -           break;
> +         if (vr0.min == vr0.max || vr1.min == vr1.max)
> +           val[3] = NULL_TREE;
> +         else
> +           {
> +             val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
> +             if (val[3] == NULL_TREE)
> +               sop = true;
> +           }
>
> -         if (val[i])
> +         if (sop)
>            {
> -             if (!is_gimple_min_invariant (val[i])
> -                 || (TREE_OVERFLOW (val[i])
> -                     && !is_overflow_infinity (val[i])))
> +             set_value_range_to_varying (vr);
> +             return;
> +           }
> +
> +         /* Set MIN to the minimum of VAL[i] and MAX to the maximum
> +            of VAL[i].  */
> +         min = val[0];
> +         max = val[0];
> +         for (i = 1; i < 4; i++)
> +           {
> +             if (!is_gimple_min_invariant (min)
> +                 || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
> +                 || !is_gimple_min_invariant (max)
> +                 || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
> +               break;
> +
> +             if (val[i])
>                {
> -                 /* If we found an overflowed value, set MIN and MAX
> -                    to it so that we set the resulting range to
> -                    VARYING.  */
> -                 min = max = val[i];
> -                 break;
> -               }
> +                 if (!is_gimple_min_invariant (val[i])
> +                     || (TREE_OVERFLOW (val[i])
> +                         && !is_overflow_infinity (val[i])))
> +                   {
> +                     /* If we found an overflowed value, set MIN and MAX
> +                        to it so that we set the resulting range to
> +                        VARYING.  */
> +                     min = max = val[i];
> +                     break;
> +                   }
>
> -             if (compare_values (val[i], min) == -1)
> -               min = val[i];
> +                 if (compare_values (val[i], min) == -1)
> +                   min = val[i];
>
> -             if (compare_values (val[i], max) == 1)
> -               max = val[i];
> +                 if (compare_values (val[i], max) == 1)
> +                   max = val[i];
> +               }
>            }
>        }
>     }
> --- gcc/testsuite/gcc.dg/pr38245-2.c.jj 2008-11-28 22:23:07.000000000 +0100
> +++ gcc/testsuite/gcc.dg/pr38245-2.c    2008-11-29 20:53:20.000000000 +0100
> @@ -0,0 +1,110 @@
> +/* PR rtl-optimization/38245 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +extern void link_error (void);
> +
> +void
> +f1 (unsigned int a)
> +{
> +  if (a != 28)
> +    {
> +      if (4 / a == 5)
> +       link_error ();
> +    }
> +}
> +
> +void
> +f2 (unsigned int a)
> +{
> +  if (4 / a == 5)
> +    link_error ();
> +}
> +
> +void
> +f3 (unsigned int a)
> +{
> +  if (4 / (a & 0xff) == 5)
> +    link_error ();
> +}
> +
> +void
> +f4 (unsigned int a, unsigned int b)
> +{
> +  if ((b & 3) / ((a & 0xff) + 1) == 5)
> +    link_error ();
> +}
> +
> +void
> +f5 (int a)
> +{
> +  if (a != 28)
> +    {
> +      if (4 / a == 5)
> +       link_error ();
> +    }
> +}
> +
> +void
> +f6 (int a)
> +{
> +  if (4 / a == 5)
> +    link_error ();
> +}
> +
> +void
> +f7 (int a)
> +{
> +  if (4 / (a & 0xff) == 5)
> +    link_error ();
> +}
> +
> +void
> +f8 (int a, int b)
> +{
> +  if ((b & 3) / ((a & 0xff) + 1) == 5)
> +    link_error ();
> +}
> +
> +void
> +f9 (int a, int b)
> +{
> +  if (b >= 4)
> +    if ((a / b) == __INT_MAX__ / 2)
> +      link_error ();
> +}
> +
> +void
> +f10 (unsigned int a, unsigned int b)
> +{
> +  if (b >= 16)
> +    if ((a / b) == __INT_MAX__ / 4)
> +      link_error ();
> +}
> +
> +void
> +f11 (int a, int b)
> +{
> +  if (b <= -32)
> +    if ((a / b) == -__INT_MAX__ / 16)
> +      link_error ();
> +}
> +
> +void
> +f12 (int a, int b)
> +{
> +  if (a >= -6 && a <= 4)
> +    if ((a / b) == -7 || (a / b) == 7)
> +      link_error ();
> +}
> +
> +void
> +f13 (unsigned int a, unsigned int b)
> +{
> +  if (a <= 4)
> +    if ((a / b) == 5)
> +      link_error ();
> +}
> +
> +/* { dg-final { scan-tree-dump-not "link_error" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> --- gcc/testsuite/gcc.dg/pr38245-1.c.jj 2008-11-28 22:23:07.000000000 +0100
> +++ gcc/testsuite/gcc.dg/pr38245-1.c    2008-11-28 22:23:07.000000000 +0100
> @@ -0,0 +1,36 @@
> +/* PR rtl-optimization/38245 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +static inline int
> +f1 (int si1, int si2)
> +{
> +  return si2 == 0 ? si1 : si1 / si2;
> +}
> +
> +static inline unsigned long long
> +f2 (unsigned long long ui1, unsigned long long ui2)
> +{
> +  return ui1 % ui2;
> +}
> +
> +unsigned char g;
> +volatile unsigned int h;
> +
> +void
> +f3 (void)
> +{
> +  if (!((signed char) f1 (0, f2 (g, 2123)) - 1))
> +    h;
> +}
> +
> +int
> +main (void)
> +{
> +  f3 ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "% 2123" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "0 / " "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
>
>        Jakub
>