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: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR

On 02/06/2017 08:33 AM, Richard Biener wrote:

On Mon, Feb 6, 2017 at 4:18 PM, Jeff Law <law@redhat.com> wrote:

On 02/06/2017 08:15 AM, Jeff Law wrote:


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:


I matched the above hunk to the following context:

  else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
           && (mineq || operand_less_p (vr1min, *vr0min) == 1))
    {
      /* ( [  ] ) or ([  ] ) or ( [  ]) */
      if (*vr0type == VR_RANGE
          && vr1type == VR_RANGE)
        /* Choose the inner range.  */
        ;
      else if (*vr0type == VR_ANTI_RANGE
               && vr1type == VR_RANGE)
        {
...
          /* Choose the anti-range if the range is effectively varying.  */
          else if (vrp_val_is_min (vr1min)
                   && vrp_val_is_max (vr1max))
            ;
          /* Else choose the range.  */
          else
            {
              *vr0type = vr1type;
              *vr0min = vr1min;
              *vr0max = vr1max;
            }
        }

ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case
of a range with an anti-range "inside".  This also covers [-1,1] v ~[0,0]
where you choose the much larger anti-range now.  So at least we
want to have some idea about the sizes of the ranges (ideally we'd
choose the smaller though for most further propagations anti-ranges
often degenerate to varying...)

Hmm, let me do some refining on that hunk.
What's kind of interesting here is that the wider range ~[0,0] is sometimes more useful, but we may not have enough context here to know when that's true. Making guesses based on the size of vr1 may be the best we can do. 

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