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

[Diego Novillo]

On Sat, Nov 29, 2008 at 15:14, Jakub Jelinek <jakub@redhat.com> wrote:

> @@ -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)))
>        {
> -         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);
> +                     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;
> +           }

This is very hard to follow, it should be factored out into a separate
function.  VRP is already hard to follow and it needs some TLC.

The patch is fine otherwise.


Diego.