Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR

[Jeff Law <law at redhat dot com>]

On 02/06/2017 01:11 AM, Richard Biener wrote:
> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
> > This is the first of a 4 part series to address the issues around 79095.
> >
> > This patch addresses improvements in determining ranges of binary
> > expressions in three ways.
> >
> > First if we are otherwise unable to find a range for the result of a
> > MINUS_EXPR, if we know the arguments are not equal, then we know the
> > resultant range is ~[0,0].
> >
> > Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
> > resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
> > rarely a useful range.   A resultant range of ~[0,0] is actually more useful
> > since it often tells us something important about the difference of two
> > pointers.
> >
> > Finally, when vrp2 discovers an updated range for an object that had a range
> > discovered by vrp1, if the new range is ~[0,0], prefer that new range in
> > some cases.  This is needed to avoid losing the newly discovered ~[0,0]
> > range for EXACT_DIV_EXPR.
> >
> > Bootstrapped and regression tested with the other patches in this series.
> > OK for the trunk?
> >
> > Jeff
> >
> >         * tree-vrp.c (extract_range_from_binary_expr): For EXACT_DIV_EXPR,
> >         if the numerator has the range ~[0,0] make the resultant range
> >         ~[0,0].  For MINUS_EXPR with no derived range, if the operands are
> >         known to be not equal, then the resulting range is ~[0,0].
> >         (intersect_ranges): In some cases prefer ~[0,0].
> >
> > commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
> > Author: Jeff Law <law@torsion.usersys.redhat.com>
> > Date:   Fri Feb 3 15:45:58 2017 -0500
> >
> >     Improved ranges
> >
> > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> > index b429217..3338d8b 100644
> > --- a/gcc/tree-vrp.c
> > +++ b/gcc/tree-vrp.c
> > @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
> >
> >        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
> >      }
> > +
> > +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
> > +     as a result a ~[0,0] may be better than what has already
> > +     been computed.
> > +
> > +     In particular if numerator has the range ~[0,0], then the
> > +     result range is going to be something like
> > +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
> > +
> > +     So instead make the result range ~[0,0].  */
> > +  if (code == EXACT_DIV_EXPR
> > +      && TREE_CODE (op0) == SSA_NAME
> > +      && vr0.type == VR_ANTI_RANGE
> > +      && vr0.min == vr0.max
> > +      && integer_zerop (vr0.min))
> > +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>
> The above belongs in extract_range_from_binary_expr_1, in principle the
> cases below as well (though there's pre-existing VARYING result handling).
Do you want those existing cases moved, it's easy enough to do.

> The _1 ones are supposed to be the actual range computations while
> the routine you patched is responsible for interfacing with a lattice.  The
> _1 routines can be used from code outside of VRP.
OK.  Good to know.

> >  /* Extract range information from a unary operation CODE based on
> > @@ -8620,6 +8651,12 @@ intersect_ranges (enum value_range_type *vr0type,
> >           else if (vrp_val_is_min (vr1min)
> >                    && vrp_val_is_max (vr1max))
> >             ;
> > +         /* Choose the anti-range if it is ~[0,0], that range is special
> > +            enough to special case.  */
> > +         else if (*vr0type == VR_ANTI_RANGE
> > +                  && *vr0min == *vr0max
> > +                  && integer_zerop (*vr0min))
> > +           ;
>
> Huh.  If I spotted the place of the change correctly then we cannot arrive
> here with vr0 == ~[0,0] as *vr0type is VR_RANGE.  In the case covered
> we'd have the only case intersecting [-1, 1] and ~[0,0] that you'd change
> to ~[0,0] instead of [-1,1] which generally would be a bad choice (apart
> from your implementation error as vr1 is the anti-range here).
Nope.  It's in the right place.  We have a ~[0,0] for vr0 and vr1 is 
typically going to be [4,4] or [8.8].  Thus we're in this case:

  else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
           && (mineq || operand_less_p (vr1min, *vr0min) == 1))
    {
      /* ( [  ] ) or ([  ] ) or ( [  ]) */

mineq and maxeq are both false.  So neither of these subcases apply:

          /* Choose the right gap if the left is empty.  */
          if (mineq)
[ ... ]
          /* Choose the left gap if the right is empty.  */
          else if (maxeq)

This doesn't apply either:

         /* Choose the anti-range if the range is effectively varying.  */
          else if (vrp_val_is_min (vr1min)
                   && vrp_val_is_max (vr1max))

Even if vr1 is something larger, we're almost never going to derive 
anything useful from vr1 because vr0 is ~[0,0].