This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


On Sat, Nov 29, 2008 at 9:14 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> This PR has two parts, this patch addresses just the part why
> tree optimizers weren't able to optimize the division and modulo away
> and only RTL optimizers were able to DCE it away.
>
> On the tree side, fold doesn't optimize away 0 / x into x, 0
> as simplify-rtx does (not addressed in this patch) and VRP isn't
> able to optimize almost anything related to divisions (yielding
> almost always VARYING ranges).  In many cases we can do much better.
> Say for int x (VARYING) and int y ([4, __INT_MAX__]) we know the
> range is [__INT_MIN__ / 4, __INT_MAX__ / 4], or for x's VR
> [-4, 8] and y VARYING we know x / y is [-8, 8] (integer
> division never makes the number bigger, only if the divisor isn't
> known to be non-negative it can change the sign).  VRP was bailing
> out even if both ranges were RANGE, if divisor's range could include 0,
> but I don't think we guarantee anything about preserving code that divides
> by 0 (it is undefined behavior in both C and C++ and we happily optimize
> away say void foo () { 2 / 0; } at gimplification time, or return 0 / x;
> into return 0 in simplify-rtx and other places).  My guess is that
> it was done because the generic MULT_EXPR + RSHIFT_EXPR + *_DIV_EXPR
> algorithm of computing min0 op min1, min0 op max1, max0 op min1, max0 op
> max1 and using minimum and maximum of these values doesn't work in that
> case.
>
> The following patch has been bootstrapped/regtested on x86_64-linux
> (and the testcase from PR now works), ok for trunk?

Comments inline

> 2008-11-29  Jakub Jelinek  <jakub@redhat.com>
>
>        PR rtl-optimization/38245
>        * tree-vrp.c (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-11-29 12:12:45.000000000 +0100
> @@ -2108,11 +2108,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
> @@ -2289,83 +2295,189 @@ extract_range_from_binary_expr (value_ra
>         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)))
> +              && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
>        {
> -         set_value_range_to_varying (vr);
> -         return;
> +         /* For division, if op1 has VR_RANGE, 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));
> +             if (!vr0.min || !vr0.max)
> +               {
> +                 set_value_range_to_varying (vr);
> +                 return;
> +               }
> +           }
> +         else
> +           {
> +             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
> +      /* For divisions, if op0 is VR_RANGE, we can deduce a range
> +        even if op1 is VARYING, ANTI_RANGE, symbolic or can include 0.  */
> +      if (code != MULT_EXPR
> +         && code != RSHIFT_EXPR
> +         && (vr0.type != vr1.type
> +             || symbolic_range_p (&vr1)
> +             || range_includes_zero_p (&vr1)))

While one can deduce from earlier predicates that the predicates above match
the comment IMHO it would be less fragile with future extensions in mind if you
instead enumerate the division codes and duplicate the check for VR_RANGE for
vr0.

>        {
> -         val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
> -         if (val[1] == NULL_TREE)
> -           sop = true;
> -       }
> +         tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
> +         int cmp;
>
> -      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;
> +         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.  */
> +             gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (vr0.min)));
> +             cmp = compare_values (vr0.min, zero);
> +             if (cmp == 0 || cmp == 1)
> +               {
> +                 min = fold_unary (NEGATE_EXPR, TREE_TYPE (vr0.min), vr0.max);
> +                 max = vr0.max;
> +               }
> +             else if (cmp == -1)
> +               {
> +                 if (vrp_val_is_min (vr0.min))
> +                   type = VR_VARYING;
> +                 else
> +                   {
> +                     tree tem = fold_unary (NEGATE_EXPR, TREE_TYPE (vr0.min),
> +                                            vr0.min);

why can this be NULL while the above case cannot (can vr0 be a symbolic range)?
All this code confusesto me as it doesn't match what the comment says.  The
comment suggests to compare the absolute of vr0.min and vr0.max, but you seem
to at least mixing the building of the final value-range with this
test.  May I suggest
to re-structure this to

    min = compute-absolute-of-vr0.min
    max = compute-absolute-of-vr0.max
    compare them and build the final range

IMHO clear and understandable code should be favored in VRP instead of
maybe avoiding one compare_values or value negation.

Btw, in this case a context-diff would have been easier to review (or
a diff with -b) ;)

The patch is ok with the above suggested changes.

Thanks,
Richard.

> +                     if (tem == NULL)
> +                       type = VR_VARYING;
> +                     else
> +                       {
> +                         cmp = compare_values (tem, vr0.max);
> +                         if (cmp == -1 || cmp == 0)
> +                           {
> +                             min = vr0.min;
> +                             max = tem;
> +                           }
> +                         else if (cmp == 1)
> +                           {
> +                             min = fold_unary (NEGATE_EXPR,
> +                                               TREE_TYPE (vr0.min), vr0.max);
> +                             max = vr0.max;
> +                           }
> +                         else
> +                           type = VR_VARYING;
> +                       }
> +                   }
> +               }
> +             else
> +               type = VR_VARYING;
> +           }
> +         if (type == VR_VARYING)
> +           {
> +             set_value_range_to_varying (vr);
> +             return;
> +           }
>        }
> -
> -      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)
> +         /* 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 (sop)
> -       {
> -         set_value_range_to_varying (vr);
> -         return;
> -       }
> +         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;
> +           }
>
> -      /* 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.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;
> +           }
>
> -         if (val[i])
> +         if (vr0.min == vr0.max || vr1.min == vr1.max)
> +           val[3] = NULL_TREE;
> +         else
>            {
> -             if (!is_gimple_min_invariant (val[i])
> -                 || (TREE_OVERFLOW (val[i])
> -                     && !is_overflow_infinity (val[i])))
> +             val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
> +             if (val[3] == NULL_TREE)
> +               sop = true;
> +           }
> +
> +         if (sop)
> +           {
> +             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
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]