VRP: make range_includes_zero_p handle value_ranges

On 08/21/2018 05:46 AM, Richard Biener wrote:
> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:

>> Finally, my apologies for including a tiny change to the
>> POINTER_PLUS_EXPR handling code as well.  It came about the same set of
>> auditing tests.
> 
> Bah, please split up things here ;)  I've done a related change there
> yesterday...
> 
>>
>> It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without
>> bailing as VR_VARYING in extract_range_from_binary_expr_1.  In doing so,
>> I also noticed that ~[0,0] is not the only non-null.  We could also have
>> ~[0,2] and still know that the pointer is not zero.  I have adjusted
>> range_is_nonnull accordingly.
> 
> But there are other consumers and it would have been better to
> change range_includes_zero_p to do the natural thing (get a VR) and
> then remove range_is_nonnull as redundant if possible.

Indeed.  Cleaning up range_includes_zero_p makes VRP and friends a lot 
cleaner.  Thanks for the suggestion.

I lazily avoided cleaning up the division code affected in this patch 
too much, since it's going to be superseded by my division changes in 
the other patch.

OK pending tests?

Aldy

On Wed, Aug 22, 2018 at 11:31 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 08/21/2018 05:46 AM, Richard Biener wrote:
> > On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> >> Finally, my apologies for including a tiny change to the
> >> POINTER_PLUS_EXPR handling code as well.  It came about the same set of
> >> auditing tests.
> >
> > Bah, please split up things here ;)  I've done a related change there
> > yesterday...
> >
> >>
> >> It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without
> >> bailing as VR_VARYING in extract_range_from_binary_expr_1.  In doing so,
> >> I also noticed that ~[0,0] is not the only non-null.  We could also have
> >> ~[0,2] and still know that the pointer is not zero.  I have adjusted
> >> range_is_nonnull accordingly.
> >
> > But there are other consumers and it would have been better to
> > change range_includes_zero_p to do the natural thing (get a VR) and
> > then remove range_is_nonnull as redundant if possible.
>
> Indeed.  Cleaning up range_includes_zero_p makes VRP and friends a lot
> cleaner.  Thanks for the suggestion.
>
> I lazily avoided cleaning up the division code affected in this patch
> too much, since it's going to be superseded by my division changes in
> the other patch.
>
> OK pending tests?

-/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
-   include the value zero, -2 if we cannot tell.  */
+/* Return 1 if *VR includes the value zero, 0 if it does not include
+   the value zero, or -2 if we cannot tell.  */

 int
-range_includes_zero_p (tree min, tree max)
+range_includes_zero_p (const value_range *vr)
 {
-  tree zero = build_int_cst (TREE_TYPE (min), 0);
-  return value_inside_range (zero, min, max);
+  if (vr->type == VR_UNDEFINED || vr->type == VR_VARYING)
+    return -2;
+
+  tree zero = build_int_cst (TREE_TYPE (vr->min), 0);
+  if (vr->type == VR_RANGE)
+    return value_inside_range (zero, vr->min, vr->max);
+  else
+    return !value_inside_range (zero, vr->min, vr->max);
 }

please make it return a bool.  VR_VARYING means the range does
include zero.  For VR_UNDEFINED we could say it doesn't or we choose
to not possibly optimize and thus return true (just do that for now).
That's because VR_VARYING is [-INF, INF] and VR_UNDEFINED is
an empty range.

I suppose the -2 for we cannot tell was for the case of symbolic
ranges where again we can conservatively return true
(and your return !value_inside_range for VR_ANTI_RANGE botched
the tri-state return value anyways...).

So, can you please rework that?

Thanks,
Richard.

> Aldy

On 08/23/2018 05:59 AM, Richard Biener wrote:
> On Wed, Aug 22, 2018 at 11:31 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 08/21/2018 05:46 AM, Richard Biener wrote:
>>> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>>> Finally, my apologies for including a tiny change to the
>>>> POINTER_PLUS_EXPR handling code as well.  It came about the same set of
>>>> auditing tests.
>>>
>>> Bah, please split up things here ;)  I've done a related change there
>>> yesterday...
>>>
>>>>
>>>> It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without
>>>> bailing as VR_VARYING in extract_range_from_binary_expr_1.  In doing so,
>>>> I also noticed that ~[0,0] is not the only non-null.  We could also have
>>>> ~[0,2] and still know that the pointer is not zero.  I have adjusted
>>>> range_is_nonnull accordingly.
>>>
>>> But there are other consumers and it would have been better to
>>> change range_includes_zero_p to do the natural thing (get a VR) and
>>> then remove range_is_nonnull as redundant if possible.
>>
>> Indeed.  Cleaning up range_includes_zero_p makes VRP and friends a lot
>> cleaner.  Thanks for the suggestion.
>>
>> I lazily avoided cleaning up the division code affected in this patch
>> too much, since it's going to be superseded by my division changes in
>> the other patch.
>>
>> OK pending tests?
> 
> -/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
> -   include the value zero, -2 if we cannot tell.  */
> +/* Return 1 if *VR includes the value zero, 0 if it does not include
> +   the value zero, or -2 if we cannot tell.  */
> 
>   int
> -range_includes_zero_p (tree min, tree max)
> +range_includes_zero_p (const value_range *vr)
>   {
> -  tree zero = build_int_cst (TREE_TYPE (min), 0);
> -  return value_inside_range (zero, min, max);
> +  if (vr->type == VR_UNDEFINED || vr->type == VR_VARYING)
> +    return -2;
> +
> +  tree zero = build_int_cst (TREE_TYPE (vr->min), 0);
> +  if (vr->type == VR_RANGE)
> +    return value_inside_range (zero, vr->min, vr->max);
> +  else
> +    return !value_inside_range (zero, vr->min, vr->max);
>   }
> 
> please make it return a bool.  VR_VARYING means the range does
> include zero.  For VR_UNDEFINED we could say it doesn't or we choose
> to not possibly optimize and thus return true (just do that for now).
> That's because VR_VARYING is [-INF, INF] and VR_UNDEFINED is
> an empty range.

Done.

> 
> I suppose the -2 for we cannot tell was for the case of symbolic
> ranges where again we can conservatively return true
> (and your return !value_inside_range for VR_ANTI_RANGE botched
> the tri-state return value anyways...).

Bah!  I sure botched up the anti range return.  That was the last 
bootstrap failure I was investigating.  You'd be amazed how many things 
mysteriously fail when things like ~[SYMBOL, SYMBOL] are assumed to be 
non-zero.

Thanks for spotting this.  Bootstrap is happy now :-P.

> 
> So, can you please rework that?

Sure can!

Attached.
gcc/

	* gimple-ssa-evrp-analyze.c (set_ssa_range_info): Pass value_range
	to range_includes_zero_p.  Do not special case VR_ANTI_RANGE.
	* tree-vrp.c (range_is_nonnull): Remove.
	(range_includes_zero_p): Accept value_range instead of min/max.
	(extract_range_from_binary_expr_1): Do not early bail on
	POINTER_PLUS_EXPR.
	Use range_includes_zero_p instead of range_is_nonnull.
	(extract_range_from_unary_expr): Use range_includes_zero_p instead
	of range_is_nonnull.
	(vrp_meet_1): Pass value_range to range_includes_zero_p.  Do not
	special case VR_ANTI_RANGE.
	(vrp_finalize): Same.
	* tree-vrp.h (range_includes_zero_p): Pass value_range as argument
	instead of min/max.
	(range_is_nonnull): Remove.
	* vr-values.c (vrp_stmt_computes_nonzero): Use
	range_includes_zero_p instead of range_is_nonnull.
	(extract_range_basic): Pass value_range to range_includes_zero_p
	instead of range_is_nonnull.

diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
index b9dcf906ff7..e9afa80e191 100644
--- a/gcc/gimple-ssa-evrp-analyze.c
+++ b/gcc/gimple-ssa-evrp-analyze.c
@@ -119,12 +119,7 @@ evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr)
 			wi::to_wide (vr->max));
     }
   else if (POINTER_TYPE_P (TREE_TYPE (lhs))
-	   && ((vr->type == VR_RANGE
-		&& range_includes_zero_p (vr->min,
-					  vr->max) == 0)
-	       || (vr->type == VR_ANTI_RANGE
-		   && range_includes_zero_p (vr->min,
-					     vr->max) == 1)))
+	   && range_includes_zero_p (vr) == 0)
     set_ptr_nonnull (lhs);
 }
 
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 735b3646e81..84da2635624 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -502,17 +502,6 @@ vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 	      && bitmap_equal_p (b1, b2)));
 }
 
-/* Return true if VR is ~[0, 0].  */
-
-bool
-range_is_nonnull (value_range *vr)
-{
-  return vr->type == VR_ANTI_RANGE
-	 && integer_zerop (vr->min)
-	 && integer_zerop (vr->max);
-}
-
-
 /* Return true if VR is [0, 0].  */
 
 static inline bool
@@ -880,14 +869,25 @@ value_ranges_intersect_p (value_range *vr0, value_range *vr1)
 }
 
 
-/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
-   include the value zero, -2 if we cannot tell.  */
+/* Return TRUE if *VR includes the value zero.  */
 
-int
-range_includes_zero_p (tree min, tree max)
+bool
+range_includes_zero_p (const value_range *vr)
 {
-  tree zero = build_int_cst (TREE_TYPE (min), 0);
-  return value_inside_range (zero, min, max);
+  if (vr->type == VR_VARYING)
+    return true;
+
+  /* Ughh, we don't know.  We choose not to optimize.  */
+  if (vr->type == VR_UNDEFINED)
+    return true;
+
+  tree zero = build_int_cst (TREE_TYPE (vr->min), 0);
+  if (vr->type == VR_ANTI_RANGE)
+    {
+      int res = value_inside_range (zero, vr->min, vr->max);
+      return res == 0 || res == -2;
+    }
+  return value_inside_range (zero, vr->min, vr->max) != 0;
 }
 
 /* Return true if *VR is know to only contain nonnegative values.  */
@@ -1407,7 +1407,10 @@ extract_range_from_binary_expr_1 (value_range *vr,
       && code != POINTER_PLUS_EXPR
       && (vr0.type == VR_VARYING
 	  || vr1.type == VR_VARYING
-	  || vr0.type != vr1.type
+	  || (vr0.type != vr1.type
+	      /* We can handle POINTER_PLUS_EXPR(~[0,0], [x,y]) below,
+		 even though we have differing range kinds.  */
+	      && code != POINTER_PLUS_EXPR)
 	  || symbolic_range_p (&vr0)
 	  || symbolic_range_p (&vr1)))
     {
@@ -1424,7 +1427,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
 	     nullness, if both are non null, then the result is nonnull.
 	     If both are null, then the result is null. Otherwise they
 	     are varying.  */
-	  if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
+	  if (!range_includes_zero_p (&vr0) && !range_includes_zero_p (&vr1))
 	    set_value_range_to_nonnull (vr, expr_type);
 	  else if (range_is_null (&vr0) && range_is_null (&vr1))
 	    set_value_range_to_null (vr, expr_type);
@@ -1435,11 +1438,8 @@ extract_range_from_binary_expr_1 (value_range *vr,
 	{
 	  /* For pointer types, we are really only interested in asserting
 	     whether the expression evaluates to non-NULL.  */
-	  if (range_is_nonnull (&vr0)
-	      || range_is_nonnull (&vr1)
-	      || (vr1.type == VR_RANGE
-		  && !symbolic_range_p (&vr1)
-		  && !range_includes_zero_p (vr1.min, vr1.max)))
+	  if (!range_includes_zero_p (&vr0)
+	      || !range_includes_zero_p (&vr1))
 	    set_value_range_to_nonnull (vr, expr_type);
 	  else if (range_is_null (&vr0) && range_is_null (&vr1))
 	    set_value_range_to_null (vr, expr_type);
@@ -1450,7 +1450,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
 	{
 	  /* For pointer types, we are really only interested in asserting
 	     whether the expression evaluates to non-NULL.  */
-	  if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
+	  if (!range_includes_zero_p (&vr0) && !range_includes_zero_p (&vr1))
 	    set_value_range_to_nonnull (vr, expr_type);
 	  else if (range_is_null (&vr0) || range_is_null (&vr1))
 	    set_value_range_to_null (vr, expr_type);
@@ -1888,7 +1888,7 @@ extract_range_from_unary_expr (value_range *vr,
 	 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
       if (POINTER_TYPE_P (type))
 	{
-	  if (range_is_nonnull (&vr0))
+	  if (!range_includes_zero_p (&vr0))
 	    set_value_range_to_nonnull (vr, type);
 	  else if (range_is_null (&vr0))
 	    set_value_range_to_null (vr, type);
@@ -6020,17 +6020,9 @@ vrp_meet_1 (value_range *vr0, const value_range *vr1)
     {
       /* Failed to find an efficient meet.  Before giving up and setting
 	 the result to VARYING, see if we can at least derive a useful
-	 anti-range.  FIXME, all this nonsense about distinguishing
-	 anti-ranges from ranges is necessary because of the odd
-	 semantics of range_includes_zero_p and friends.  */
-      if (((saved.type == VR_RANGE
-	    && range_includes_zero_p (saved.min, saved.max) == 0)
-	   || (saved.type == VR_ANTI_RANGE
-	       && range_includes_zero_p (saved.min, saved.max) == 1))
-	  && ((vr1->type == VR_RANGE
-	       && range_includes_zero_p (vr1->min, vr1->max) == 0)
-	      || (vr1->type == VR_ANTI_RANGE
-		  && range_includes_zero_p (vr1->min, vr1->max) == 1)))
+	 anti-range.  */
+      if (range_includes_zero_p (&saved) == 0
+	  && range_includes_zero_p (vr1) == 0)
 	{
 	  set_value_range_to_nonnull (vr0, TREE_TYPE (saved.min));
 
@@ -6540,10 +6532,7 @@ vrp_prop::vrp_finalize (bool warn_array_bounds_p)
 	continue;
 
       if (POINTER_TYPE_P (TREE_TYPE (name))
-	  && ((vr->type == VR_RANGE
-	       && range_includes_zero_p (vr->min, vr->max) == 0)
-	      || (vr->type == VR_ANTI_RANGE
-		  && range_includes_zero_p (vr->min, vr->max) == 1)))
+	  && range_includes_zero_p (vr) == 0)
 	set_ptr_nonnull (name);
       else if (!POINTER_TYPE_P (TREE_TYPE (name)))
 	set_range_info (name, vr->type,
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 0c1fb3637cf..f8c1c0c8f72 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -86,7 +86,7 @@ extern void register_edge_assert_for (tree, edge, enum tree_code,
 				      tree, tree, vec<assert_info> &);
 extern bool stmt_interesting_for_vrp (gimple *);
 extern void set_value_range_to_varying (value_range *);
-extern int range_includes_zero_p (tree, tree);
+extern bool range_includes_zero_p (const value_range *);
 extern bool infer_value_range (gimple *, tree, tree_code *, tree *);
 
 extern void set_value_range_to_nonnull (value_range *, tree);
@@ -96,7 +96,6 @@ extern void set_and_canonicalize_value_range (value_range *,
 					      enum value_range_type,
 					      tree, tree, bitmap);
 extern bool vrp_bitmap_equal_p (const_bitmap, const_bitmap);
-extern bool range_is_nonnull (value_range *);
 extern tree value_range_constant_singleton (value_range *);
 extern bool symbolic_range_p (value_range *);
 extern int compare_values (tree, tree);
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 33335f3da31..072d9a7b454 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -343,7 +343,7 @@ vr_values::vrp_stmt_computes_nonzero (gimple *stmt)
 	  && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
 	{
 	  value_range *vr = get_value_range (TREE_OPERAND (base, 0));
-	  if (range_is_nonnull (vr))
+	  if (!range_includes_zero_p (vr))
 	    return true;
 	}
     }
@@ -1107,12 +1107,8 @@ vr_values::extract_range_basic (value_range *vr, gimple *stmt)
 	  if (TREE_CODE (arg) == SSA_NAME)
 	    {
 	      value_range *vr0 = get_value_range (arg);
-	      /* If arg is non-zero, then ffs or popcount
-		 are non-zero.  */
-	      if ((vr0->type == VR_RANGE
-		   && range_includes_zero_p (vr0->min, vr0->max) == 0)
-		  || (vr0->type == VR_ANTI_RANGE
-		      && range_includes_zero_p (vr0->min, vr0->max) == 1))
+	      /* If arg is non-zero, then ffs or popcount are non-zero.  */
+	      if (range_includes_zero_p (vr0) == 0)
 		mini = 1;
 	      /* If some high bits are known to be zero,
 		 we can decrease the maximum.  */

On Thu, Aug 23, 2018 at 4:50 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 08/23/2018 05:59 AM, Richard Biener wrote:
> > On Wed, Aug 22, 2018 at 11:31 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 08/21/2018 05:46 AM, Richard Biener wrote:
> >>> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>>> Finally, my apologies for including a tiny change to the
> >>>> POINTER_PLUS_EXPR handling code as well.  It came about the same set of
> >>>> auditing tests.
> >>>
> >>> Bah, please split up things here ;)  I've done a related change there
> >>> yesterday...
> >>>
> >>>>
> >>>> It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without
> >>>> bailing as VR_VARYING in extract_range_from_binary_expr_1.  In doing so,
> >>>> I also noticed that ~[0,0] is not the only non-null.  We could also have
> >>>> ~[0,2] and still know that the pointer is not zero.  I have adjusted
> >>>> range_is_nonnull accordingly.
> >>>
> >>> But there are other consumers and it would have been better to
> >>> change range_includes_zero_p to do the natural thing (get a VR) and
> >>> then remove range_is_nonnull as redundant if possible.
> >>
> >> Indeed.  Cleaning up range_includes_zero_p makes VRP and friends a lot
> >> cleaner.  Thanks for the suggestion.
> >>
> >> I lazily avoided cleaning up the division code affected in this patch
> >> too much, since it's going to be superseded by my division changes in
> >> the other patch.
> >>
> >> OK pending tests?
> >
> > -/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
> > -   include the value zero, -2 if we cannot tell.  */
> > +/* Return 1 if *VR includes the value zero, 0 if it does not include
> > +   the value zero, or -2 if we cannot tell.  */
> >
> >   int
> > -range_includes_zero_p (tree min, tree max)
> > +range_includes_zero_p (const value_range *vr)
> >   {
> > -  tree zero = build_int_cst (TREE_TYPE (min), 0);
> > -  return value_inside_range (zero, min, max);
> > +  if (vr->type == VR_UNDEFINED || vr->type == VR_VARYING)
> > +    return -2;
> > +
> > +  tree zero = build_int_cst (TREE_TYPE (vr->min), 0);
> > +  if (vr->type == VR_RANGE)
> > +    return value_inside_range (zero, vr->min, vr->max);
> > +  else
> > +    return !value_inside_range (zero, vr->min, vr->max);
> >   }
> >
> > please make it return a bool.  VR_VARYING means the range does
> > include zero.  For VR_UNDEFINED we could say it doesn't or we choose
> > to not possibly optimize and thus return true (just do that for now).
> > That's because VR_VARYING is [-INF, INF] and VR_UNDEFINED is
> > an empty range.
>
> Done.
>
> >
> > I suppose the -2 for we cannot tell was for the case of symbolic
> > ranges where again we can conservatively return true
> > (and your return !value_inside_range for VR_ANTI_RANGE botched
> > the tri-state return value anyways...).
>
> Bah!  I sure botched up the anti range return.  That was the last
> bootstrap failure I was investigating.  You'd be amazed how many things
> mysteriously fail when things like ~[SYMBOL, SYMBOL] are assumed to be
> non-zero.
>
> Thanks for spotting this.  Bootstrap is happy now :-P.
>
> >
> > So, can you please rework that?
>
> Sure can!

@@ -1407,7 +1407,10 @@ extract_range_from_binary_expr_1 (value_range *vr,
       && code != POINTER_PLUS_EXPR
       && (vr0.type == VR_VARYING
          || vr1.type == VR_VARYING
-         || vr0.type != vr1.type
+         || (vr0.type != vr1.type
+             /* We can handle POINTER_PLUS_EXPR(~[0,0], [x,y]) below,
+                even though we have differing range kinds.  */
+             && code != POINTER_PLUS_EXPR)
          || symbolic_range_p (&vr0)
          || symbolic_range_p (&vr1)))
     {

is redundant now (spot the code != POINTER_PLUS_EXPR check at the
beginning of context)

OK with this hunk removed.

Thanks,
Richard.

> Attached.
>

On 08/24/2018 05:08 AM, Richard Biener wrote:

> @@ -1407,7 +1407,10 @@ extract_range_from_binary_expr_1 (value_range *vr,
>         && code != POINTER_PLUS_EXPR
>         && (vr0.type == VR_VARYING
>            || vr1.type == VR_VARYING
> -         || vr0.type != vr1.type
> +         || (vr0.type != vr1.type
> +             /* We can handle POINTER_PLUS_EXPR(~[0,0], [x,y]) below,
> +                even though we have differing range kinds.  */
> +             && code != POINTER_PLUS_EXPR)
>            || symbolic_range_p (&vr0)
>            || symbolic_range_p (&vr1)))
>       {
> 
> is redundant now (spot the code != POINTER_PLUS_EXPR check at the
> beginning of context)

Hey, no fair making my code irrelevant mid way through a review! :)

> 
> OK with this hunk removed.

Done.

Thanks.
Aldy