VRP: abstract out POINTER_TYPE_P handling
diff mbox series

Message ID 5db8448c-3822-35ad-016d-274fcfdc90a5@redhat.com
State New
Headers show
Series
  • VRP: abstract out POINTER_TYPE_P handling
Related show

Commit Message

Aldy Hernandez Aug. 29, 2018, 10:54 a.m. UTC
Never say never.  Just when I thought I was done...

It looks like I need the special casing we do for pointer types in 
extract_range_from_binary_expr_1.

The code is simple enough that we could just duplicate it anywhere we 
need it, but I hate code duplication and keeping track of multiple 
versions of the same thing.

No change in functionality.

Tested on x86-64 Linux with all languages.

OK?

Comments

David Malcolm Aug. 29, 2018, 4:32 p.m. UTC | #1
On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
> Never say never.  Just when I thought I was done...
> 
> It looks like I need the special casing we do for pointer types in 
> extract_range_from_binary_expr_1.
> 
> The code is simple enough that we could just duplicate it anywhere
> we 
> need it, but I hate code duplication and keeping track of multiple 
> versions of the same thing.
> 
> No change in functionality.
> 
> Tested on x86-64 Linux with all languages.
> 
> OK?

A couple of nits I spotted:

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index f20730a85ba..228f20b5203 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
     }
 }
 
+/* Value range wrapper for wide_int_range_pointer.  */
+
+static void
+vrp_range_pointer (value_range *vr,
+		   enum tree_code code, tree type,
+		   value_range *vr0, value_range *vr1)

Looking at the signature of the function, I wondered what the source
and destination of the information is...

Could vr0 and vr1 be const?

...which would require extract_range_into_wide_ints to take a const
value_range *

  ... which would require range_int_cst_p to take a const value_range *

(I *think* that's where the yak-shaving would end)

+{
+  signop sign = TYPE_SIGN (type);
+  unsigned prec = TYPE_PRECISION (type);
+  wide_int vr0_min, vr0_max;
+  wide_int vr1_min, vr1_max;
+
+  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
+  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
+  wide_int_range_nullness n;
+  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
vr1_max);
+  if (n == WIDE_INT_RANGE_UNKNOWN)
+    set_value_range_to_varying (vr);
+  else if (n == WIDE_INT_RANGE_NULL)
+    set_value_range_to_null (vr, type);
+  else if (n == WIDE_INT_RANGE_NONNULL)
+    set_value_range_to_nonnull (vr, type);
+  else
+    gcc_unreachable ();
+}
+

Would it be better to use a "switch (n)" here, rather than a series of
"if"/"else if" for each enum value?

[...snip...]


Hope this is constructive
Dave
Aldy Hernandez Aug. 30, 2018, 7:39 a.m. UTC | #2
On 08/29/2018 12:32 PM, David Malcolm wrote:
> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
>> Never say never.  Just when I thought I was done...
>>
>> It looks like I need the special casing we do for pointer types in
>> extract_range_from_binary_expr_1.
>>
>> The code is simple enough that we could just duplicate it anywhere
>> we
>> need it, but I hate code duplication and keeping track of multiple
>> versions of the same thing.
>>
>> No change in functionality.
>>
>> Tested on x86-64 Linux with all languages.
>>
>> OK?
> 
> A couple of nits I spotted:
> 
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index f20730a85ba..228f20b5203 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
>       }
>   }
>   
> +/* Value range wrapper for wide_int_range_pointer.  */
> +
> +static void
> +vrp_range_pointer (value_range *vr,
> +		   enum tree_code code, tree type,
> +		   value_range *vr0, value_range *vr1)
> 
> Looking at the signature of the function, I wondered what the source
> and destination of the information is...

vr being the destination and vr0/vr1 being the sources are standard 
operating procedure within tree-vrp.c.  All the functions are basically 
that, that's why I haven't bothered.

> 
> Could vr0 and vr1 be const?
> 
> ...which would require extract_range_into_wide_ints to take a const
> value_range *

Yes, but that would require changing all of tree-vrp.c to take const 
value_range's.  For instance, range_int_cst_p and a slew of other 
functions throughout.

> 
>    ... which would require range_int_cst_p to take a const value_range *
> 
> (I *think* that's where the yak-shaving would end)
> 
> +{
> +  signop sign = TYPE_SIGN (type);
> +  unsigned prec = TYPE_PRECISION (type);
> +  wide_int vr0_min, vr0_max;
> +  wide_int vr1_min, vr1_max;
> +
> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
> +  wide_int_range_nullness n;
> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
> vr1_max);
> +  if (n == WIDE_INT_RANGE_UNKNOWN)
> +    set_value_range_to_varying (vr);
> +  else if (n == WIDE_INT_RANGE_NULL)
> +    set_value_range_to_null (vr, type);
> +  else if (n == WIDE_INT_RANGE_NONNULL)
> +    set_value_range_to_nonnull (vr, type);
> +  else
> +    gcc_unreachable ();
> +}
> +
> 
> Would it be better to use a "switch (n)" here, rather than a series of
> "if"/"else if" for each enum value?

I prefer ifs for a small amount of options, but having the compiler warn 
on missing enum alternatives is nice, so I've changed it.  Notice 
there's more code now though :-(.

Aldy
gcc/

	* tree-vrp.c (vrp_range_pointer): New.
	(extract_range_from_binary_expr_1): Call vrp_range_pointer.
	* wide-int-range.cc (wide_int_range_pointer): New.
	* wide-int-range.h (enum wide_int_range_nullness): New.
	(wide_int_range_pointer): New.

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index f20730a85ba..b0dad0701b7 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1275,6 +1275,38 @@ set_value_range_with_overflow (value_range &vr,
     }
 }
 
+/* Value range wrapper for wide_int_range_pointer.  */
+
+static void
+vrp_range_pointer (value_range *vr,
+		   enum tree_code code, tree type,
+		   value_range *vr0, value_range *vr1)
+{
+  signop sign = TYPE_SIGN (type);
+  unsigned prec = TYPE_PRECISION (type);
+  wide_int vr0_min, vr0_max;
+  wide_int vr1_min, vr1_max;
+
+  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
+  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
+  wide_int_range_nullness n;
+  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min, vr1_max);
+  switch (n)
+    {
+    case WIDE_INT_RANGE_UNKNOWN:
+      set_value_range_to_varying (vr);
+      break;
+    case WIDE_INT_RANGE_NULL:
+      set_value_range_to_null (vr, type);
+      break;
+    case WIDE_INT_RANGE_NONNULL:
+      set_value_range_to_nonnull (vr, type);
+      break;
+    default:
+      gcc_unreachable ();
+    }
+}
+
 /* Extract range information from a binary operation CODE based on
    the ranges of each of its operands *VR0 and *VR1 with resulting
    type EXPR_TYPE.  The resulting range is stored in *VR.  */
@@ -1416,47 +1448,10 @@ extract_range_from_binary_expr_1 (value_range *vr,
     }
 
   /* Now evaluate the expression to determine the new range.  */
+
   if (POINTER_TYPE_P (expr_type))
     {
-      if (code == MIN_EXPR || code == MAX_EXPR)
-	{
-	  /* For MIN/MAX expressions with pointers, we only care about
-	     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_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);
-	  else
-	    set_value_range_to_varying (vr);
-	}
-      else if (code == POINTER_PLUS_EXPR)
-	{
-	  /* For pointer types, we are really only interested in asserting
-	     whether the expression evaluates to non-NULL.  */
-	  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);
-	  else
-	    set_value_range_to_varying (vr);
-	}
-      else if (code == BIT_AND_EXPR)
-	{
-	  /* For pointer types, we are really only interested in asserting
-	     whether the expression evaluates to non-NULL.  */
-	  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);
-	  else
-	    set_value_range_to_varying (vr);
-	}
-      else
-	set_value_range_to_varying (vr);
-
+      vrp_range_pointer (vr, code, expr_type, &vr0, &vr1);
       return;
     }
 
diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc
index 3cdcede04cd..9ab1b04c4dd 100644
--- a/gcc/wide-int-range.cc
+++ b/gcc/wide-int-range.cc
@@ -733,3 +733,60 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax,
     extra_range_p = false;
   return true;
 }
+
+/* Given a binary operator (CODE) on two pointer ranges, return if the
+   result will be zero, non-zero, or unknown.  */
+
+enum wide_int_range_nullness
+wide_int_range_pointer (enum tree_code code,
+			signop sign,
+			const wide_int &vr0_min,
+			const wide_int &vr0_max,
+			const wide_int &vr1_min,
+			const wide_int &vr1_max)
+{
+  unsigned prec = vr0_min.get_precision ();
+  if (code == MIN_EXPR || code == MAX_EXPR)
+    {
+      /* For MIN/MAX expressions with pointers, we only care about
+	 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 (!wide_int_range_includes_zero_p (vr0_min, vr0_max, sign)
+	  && !wide_int_range_includes_zero_p (vr1_min, vr1_max, sign))
+	return WIDE_INT_RANGE_NONNULL;
+      else if (wide_int_range_zero_p (vr0_min, vr0_max, prec)
+	       && wide_int_range_zero_p (vr1_min, vr1_max, prec))
+	return WIDE_INT_RANGE_NULL;
+      else
+	return WIDE_INT_RANGE_UNKNOWN;
+    }
+  else if (code == POINTER_PLUS_EXPR)
+    {
+      /* For pointer types, we are really only interested in asserting
+	 whether the expression evaluates to non-NULL.  */
+      if (!wide_int_range_includes_zero_p (vr0_min, vr0_max, sign)
+	  || !wide_int_range_includes_zero_p (vr1_min, vr1_max, sign))
+	return WIDE_INT_RANGE_NONNULL;
+      else if (wide_int_range_zero_p (vr0_min, vr0_max, prec)
+	       && wide_int_range_zero_p (vr1_min, vr1_max, prec))
+	return WIDE_INT_RANGE_NULL;
+      else
+	return WIDE_INT_RANGE_UNKNOWN;
+    }
+  else if (code == BIT_AND_EXPR)
+    {
+      /* For pointer types, we are really only interested in asserting
+	 whether the expression evaluates to non-NULL.  */
+      if (!wide_int_range_includes_zero_p (vr0_min, vr0_max, sign)
+	  && !wide_int_range_includes_zero_p (vr1_min, vr1_max, sign))
+	return WIDE_INT_RANGE_NONNULL;
+      else if (wide_int_range_zero_p (vr0_min, vr0_max, prec)
+	       || wide_int_range_zero_p (vr1_min, vr1_max, prec))
+	return WIDE_INT_RANGE_NULL;
+      else
+	return WIDE_INT_RANGE_UNKNOWN;
+    }
+  else
+    return WIDE_INT_RANGE_UNKNOWN;
+}
diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
index 427ef34c6b4..ecdd961df36 100644
--- a/gcc/wide-int-range.h
+++ b/gcc/wide-int-range.h
@@ -20,6 +20,14 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_WIDE_INT_RANGE_H
 #define GCC_WIDE_INT_RANGE_H
 
+/* For an operation on pointers, this specifies whether the resulting
+   operation is null, non-null, or unknown.  */
+enum wide_int_range_nullness {
+  WIDE_INT_RANGE_UNKNOWN = 0,
+  WIDE_INT_RANGE_NULL,
+  WIDE_INT_RANGE_NONNULL
+};
+
 extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
 					  enum tree_code code, signop sign,
 					  const wide_int &, const wide_int &,
@@ -110,6 +118,12 @@ extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
 				bool overflow_wraps,
 				bool &extra_range_p,
 				wide_int &extra_min, wide_int &extra_max);
+enum wide_int_range_nullness wide_int_range_pointer (enum tree_code code,
+						     signop sign,
+						     const wide_int &vr0_min,
+						     const wide_int &vr0_max,
+						     const wide_int &vr1_min,
+						     const wide_int &vr1_max);
 
 /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */
Richard Biener Sept. 4, 2018, 11:42 a.m. UTC | #3
On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 08/29/2018 12:32 PM, David Malcolm wrote:
> > On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
> >> Never say never.  Just when I thought I was done...
> >>
> >> It looks like I need the special casing we do for pointer types in
> >> extract_range_from_binary_expr_1.
> >>
> >> The code is simple enough that we could just duplicate it anywhere
> >> we
> >> need it, but I hate code duplication and keeping track of multiple
> >> versions of the same thing.
> >>
> >> No change in functionality.
> >>
> >> Tested on x86-64 Linux with all languages.
> >>
> >> OK?
> >
> > A couple of nits I spotted:
> >
> > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> > index f20730a85ba..228f20b5203 100644
> > --- a/gcc/tree-vrp.c
> > +++ b/gcc/tree-vrp.c
> > @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
> >       }
> >   }
> >
> > +/* Value range wrapper for wide_int_range_pointer.  */
> > +
> > +static void
> > +vrp_range_pointer (value_range *vr,
> > +                enum tree_code code, tree type,
> > +                value_range *vr0, value_range *vr1)
> >
> > Looking at the signature of the function, I wondered what the source
> > and destination of the information is...
>
> vr being the destination and vr0/vr1 being the sources are standard
> operating procedure within tree-vrp.c.  All the functions are basically
> that, that's why I haven't bothered.
>
> >
> > Could vr0 and vr1 be const?
> >
> > ...which would require extract_range_into_wide_ints to take a const
> > value_range *
>
> Yes, but that would require changing all of tree-vrp.c to take const
> value_range's.  For instance, range_int_cst_p and a slew of other
> functions throughout.
>
> >
> >    ... which would require range_int_cst_p to take a const value_range *
> >
> > (I *think* that's where the yak-shaving would end)
> >
> > +{
> > +  signop sign = TYPE_SIGN (type);
> > +  unsigned prec = TYPE_PRECISION (type);
> > +  wide_int vr0_min, vr0_max;
> > +  wide_int vr1_min, vr1_max;
> > +
> > +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
> > +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
> > +  wide_int_range_nullness n;
> > +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
> > vr1_max);
> > +  if (n == WIDE_INT_RANGE_UNKNOWN)
> > +    set_value_range_to_varying (vr);
> > +  else if (n == WIDE_INT_RANGE_NULL)
> > +    set_value_range_to_null (vr, type);
> > +  else if (n == WIDE_INT_RANGE_NONNULL)
> > +    set_value_range_to_nonnull (vr, type);
> > +  else
> > +    gcc_unreachable ();
> > +}
> > +
> >
> > Would it be better to use a "switch (n)" here, rather than a series of
> > "if"/"else if" for each enum value?
>
> I prefer ifs for a small amount of options, but having the compiler warn
> on missing enum alternatives is nice, so I've changed it.  Notice
> there's more code now though :-(.

I don't like the names *_range_pointer, please change them to sth more
specific like *_range_pointer_binary_op.

What's the advantage of "hiding" the resulting ranges behind the
wide_int_range_nullness enum rather than having regular range output?
What's the value in separating pointer operations at all in the
wide-int interfaces?  IIRC the difference is that whenever unioning
is required that when it's a pointer result we should possibly
preserve non-nullness.  It's of course also doing less work overall.

So - in the end I'm not convinced that adding this kind of interface
to the wide_int_ variants is worth it and I'd rather keep the existing
VRP code?

Richard.

>
> Aldy
Aldy Hernandez Sept. 4, 2018, 12:09 p.m. UTC | #4
On 09/04/2018 07:42 AM, Richard Biener wrote:
> On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 08/29/2018 12:32 PM, David Malcolm wrote:
>>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
>>>> Never say never.  Just when I thought I was done...
>>>>
>>>> It looks like I need the special casing we do for pointer types in
>>>> extract_range_from_binary_expr_1.
>>>>
>>>> The code is simple enough that we could just duplicate it anywhere
>>>> we
>>>> need it, but I hate code duplication and keeping track of multiple
>>>> versions of the same thing.
>>>>
>>>> No change in functionality.
>>>>
>>>> Tested on x86-64 Linux with all languages.
>>>>
>>>> OK?
>>>
>>> A couple of nits I spotted:
>>>
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index f20730a85ba..228f20b5203 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
>>>        }
>>>    }
>>>
>>> +/* Value range wrapper for wide_int_range_pointer.  */
>>> +
>>> +static void
>>> +vrp_range_pointer (value_range *vr,
>>> +                enum tree_code code, tree type,
>>> +                value_range *vr0, value_range *vr1)
>>>
>>> Looking at the signature of the function, I wondered what the source
>>> and destination of the information is...
>>
>> vr being the destination and vr0/vr1 being the sources are standard
>> operating procedure within tree-vrp.c.  All the functions are basically
>> that, that's why I haven't bothered.
>>
>>>
>>> Could vr0 and vr1 be const?
>>>
>>> ...which would require extract_range_into_wide_ints to take a const
>>> value_range *
>>
>> Yes, but that would require changing all of tree-vrp.c to take const
>> value_range's.  For instance, range_int_cst_p and a slew of other
>> functions throughout.
>>
>>>
>>>     ... which would require range_int_cst_p to take a const value_range *
>>>
>>> (I *think* that's where the yak-shaving would end)
>>>
>>> +{
>>> +  signop sign = TYPE_SIGN (type);
>>> +  unsigned prec = TYPE_PRECISION (type);
>>> +  wide_int vr0_min, vr0_max;
>>> +  wide_int vr1_min, vr1_max;
>>> +
>>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
>>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
>>> +  wide_int_range_nullness n;
>>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
>>> vr1_max);
>>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
>>> +    set_value_range_to_varying (vr);
>>> +  else if (n == WIDE_INT_RANGE_NULL)
>>> +    set_value_range_to_null (vr, type);
>>> +  else if (n == WIDE_INT_RANGE_NONNULL)
>>> +    set_value_range_to_nonnull (vr, type);
>>> +  else
>>> +    gcc_unreachable ();
>>> +}
>>> +
>>>
>>> Would it be better to use a "switch (n)" here, rather than a series of
>>> "if"/"else if" for each enum value?
>>
>> I prefer ifs for a small amount of options, but having the compiler warn
>> on missing enum alternatives is nice, so I've changed it.  Notice
>> there's more code now though :-(.
> 
> I don't like the names *_range_pointer, please change them to sth more
> specific like *_range_pointer_binary_op.

Sure.

> 
> What's the advantage of "hiding" the resulting ranges behind the
> wide_int_range_nullness enum rather than having regular range output?

Our upcoming work has another representation for non-nulls in particular 
([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share 
whatever VRP is currently doing for pointers, without having to depend 
on the internals of vrp (value_range *).

> What's the value in separating pointer operations at all in the
> wide-int interfaces?  IIRC the difference is that whenever unioning
> is required that when it's a pointer result we should possibly
> preserve non-nullness.  It's of course also doing less work overall.

I don't follow.  What are you suggesting?

> 
> So - in the end I'm not convinced that adding this kind of interface
> to the wide_int_ variants is worth it and I'd rather keep the existing
> VRP code?

Again, I don't want to depend on vr_values or VRP in general.

Aldy
Richard Biener Sept. 4, 2018, 12:29 p.m. UTC | #5
On Tue, Sep 4, 2018 at 2:09 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 09/04/2018 07:42 AM, Richard Biener wrote:
> > On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 08/29/2018 12:32 PM, David Malcolm wrote:
> >>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
> >>>> Never say never.  Just when I thought I was done...
> >>>>
> >>>> It looks like I need the special casing we do for pointer types in
> >>>> extract_range_from_binary_expr_1.
> >>>>
> >>>> The code is simple enough that we could just duplicate it anywhere
> >>>> we
> >>>> need it, but I hate code duplication and keeping track of multiple
> >>>> versions of the same thing.
> >>>>
> >>>> No change in functionality.
> >>>>
> >>>> Tested on x86-64 Linux with all languages.
> >>>>
> >>>> OK?
> >>>
> >>> A couple of nits I spotted:
> >>>
> >>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> >>> index f20730a85ba..228f20b5203 100644
> >>> --- a/gcc/tree-vrp.c
> >>> +++ b/gcc/tree-vrp.c
> >>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
> >>>        }
> >>>    }
> >>>
> >>> +/* Value range wrapper for wide_int_range_pointer.  */
> >>> +
> >>> +static void
> >>> +vrp_range_pointer (value_range *vr,
> >>> +                enum tree_code code, tree type,
> >>> +                value_range *vr0, value_range *vr1)
> >>>
> >>> Looking at the signature of the function, I wondered what the source
> >>> and destination of the information is...
> >>
> >> vr being the destination and vr0/vr1 being the sources are standard
> >> operating procedure within tree-vrp.c.  All the functions are basically
> >> that, that's why I haven't bothered.
> >>
> >>>
> >>> Could vr0 and vr1 be const?
> >>>
> >>> ...which would require extract_range_into_wide_ints to take a const
> >>> value_range *
> >>
> >> Yes, but that would require changing all of tree-vrp.c to take const
> >> value_range's.  For instance, range_int_cst_p and a slew of other
> >> functions throughout.
> >>
> >>>
> >>>     ... which would require range_int_cst_p to take a const value_range *
> >>>
> >>> (I *think* that's where the yak-shaving would end)
> >>>
> >>> +{
> >>> +  signop sign = TYPE_SIGN (type);
> >>> +  unsigned prec = TYPE_PRECISION (type);
> >>> +  wide_int vr0_min, vr0_max;
> >>> +  wide_int vr1_min, vr1_max;
> >>> +
> >>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
> >>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
> >>> +  wide_int_range_nullness n;
> >>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
> >>> vr1_max);
> >>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
> >>> +    set_value_range_to_varying (vr);
> >>> +  else if (n == WIDE_INT_RANGE_NULL)
> >>> +    set_value_range_to_null (vr, type);
> >>> +  else if (n == WIDE_INT_RANGE_NONNULL)
> >>> +    set_value_range_to_nonnull (vr, type);
> >>> +  else
> >>> +    gcc_unreachable ();
> >>> +}
> >>> +
> >>>
> >>> Would it be better to use a "switch (n)" here, rather than a series of
> >>> "if"/"else if" for each enum value?
> >>
> >> I prefer ifs for a small amount of options, but having the compiler warn
> >> on missing enum alternatives is nice, so I've changed it.  Notice
> >> there's more code now though :-(.
> >
> > I don't like the names *_range_pointer, please change them to sth more
> > specific like *_range_pointer_binary_op.
>
> Sure.
>
> >
> > What's the advantage of "hiding" the resulting ranges behind the
> > wide_int_range_nullness enum rather than having regular range output?
>
> Our upcoming work has another representation for non-nulls in particular
> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share
> whatever VRP is currently doing for pointers, without having to depend
> on the internals of vrp (value_range *).
>
> > What's the value in separating pointer operations at all in the
> > wide-int interfaces?  IIRC the difference is that whenever unioning
> > is required that when it's a pointer result we should possibly
> > preserve non-nullness.  It's of course also doing less work overall.
>
> I don't follow.  What are you suggesting?

I'm thinking out loud.  Here adding sort-of a "preferencing" to the
more general handling of the ops would do the same trick, without
restricting that to "pointers".  For example if a pass would be interested
in knowing whether a divisor is zero it would also rather preserve
non-nullness and trade that for precision in other parts of the range,
say, if you had [-1, -1] [1, +INF] then the smallest unioning result
is [-1, +INF] but ~[0, 0] is also a valid result which preserves non-zeroness.

So for wide-int workers I don't believe in tagging sth as pointers.  Rather
than that ops might get one of

 enum vr_preference { VR_PREF_SMALL, VR_PREF_NONNULL, VR_PREF_NONNEGATIVE, ... }

?

> >
> > So - in the end I'm not convinced that adding this kind of interface
> > to the wide_int_ variants is worth it and I'd rather keep the existing
> > VRP code?
>
> Again, I don't want to depend on vr_values or VRP in general.

Sure.  But the general handling of the ops (just treat POINTER_PLUS like PLUS)
should do range operations just fine.  It's only the preferencing you'd lose
and that preferencing looks like a more general feature than "lets have this
function dealing with a small subset of binary ops on pointers"?

The preferencing above would get passed down to the range unioning code.

Btw, since your wide-int-range code doesn't even have ANTI_RANGE, how
do you represent non-zero in the API?

As said, splitting this out in the way of your patch looks "premature",
there's not enough of the big picture visible for me to say it makes sense.

Richard.

> Aldy
Aldy Hernandez Sept. 4, 2018, 1:21 p.m. UTC | #6
On 09/04/2018 08:29 AM, Richard Biener wrote:
> On Tue, Sep 4, 2018 at 2:09 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 09/04/2018 07:42 AM, Richard Biener wrote:
>>> On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>>
>>>>
>>>> On 08/29/2018 12:32 PM, David Malcolm wrote:
>>>>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
>>>>>> Never say never.  Just when I thought I was done...
>>>>>>
>>>>>> It looks like I need the special casing we do for pointer types in
>>>>>> extract_range_from_binary_expr_1.
>>>>>>
>>>>>> The code is simple enough that we could just duplicate it anywhere
>>>>>> we
>>>>>> need it, but I hate code duplication and keeping track of multiple
>>>>>> versions of the same thing.
>>>>>>
>>>>>> No change in functionality.
>>>>>>
>>>>>> Tested on x86-64 Linux with all languages.
>>>>>>
>>>>>> OK?
>>>>>
>>>>> A couple of nits I spotted:
>>>>>
>>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>>>> index f20730a85ba..228f20b5203 100644
>>>>> --- a/gcc/tree-vrp.c
>>>>> +++ b/gcc/tree-vrp.c
>>>>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
>>>>>         }
>>>>>     }
>>>>>
>>>>> +/* Value range wrapper for wide_int_range_pointer.  */
>>>>> +
>>>>> +static void
>>>>> +vrp_range_pointer (value_range *vr,
>>>>> +                enum tree_code code, tree type,
>>>>> +                value_range *vr0, value_range *vr1)
>>>>>
>>>>> Looking at the signature of the function, I wondered what the source
>>>>> and destination of the information is...
>>>>
>>>> vr being the destination and vr0/vr1 being the sources are standard
>>>> operating procedure within tree-vrp.c.  All the functions are basically
>>>> that, that's why I haven't bothered.
>>>>
>>>>>
>>>>> Could vr0 and vr1 be const?
>>>>>
>>>>> ...which would require extract_range_into_wide_ints to take a const
>>>>> value_range *
>>>>
>>>> Yes, but that would require changing all of tree-vrp.c to take const
>>>> value_range's.  For instance, range_int_cst_p and a slew of other
>>>> functions throughout.
>>>>
>>>>>
>>>>>      ... which would require range_int_cst_p to take a const value_range *
>>>>>
>>>>> (I *think* that's where the yak-shaving would end)
>>>>>
>>>>> +{
>>>>> +  signop sign = TYPE_SIGN (type);
>>>>> +  unsigned prec = TYPE_PRECISION (type);
>>>>> +  wide_int vr0_min, vr0_max;
>>>>> +  wide_int vr1_min, vr1_max;
>>>>> +
>>>>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
>>>>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
>>>>> +  wide_int_range_nullness n;
>>>>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
>>>>> vr1_max);
>>>>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
>>>>> +    set_value_range_to_varying (vr);
>>>>> +  else if (n == WIDE_INT_RANGE_NULL)
>>>>> +    set_value_range_to_null (vr, type);
>>>>> +  else if (n == WIDE_INT_RANGE_NONNULL)
>>>>> +    set_value_range_to_nonnull (vr, type);
>>>>> +  else
>>>>> +    gcc_unreachable ();
>>>>> +}
>>>>> +
>>>>>
>>>>> Would it be better to use a "switch (n)" here, rather than a series of
>>>>> "if"/"else if" for each enum value?
>>>>
>>>> I prefer ifs for a small amount of options, but having the compiler warn
>>>> on missing enum alternatives is nice, so I've changed it.  Notice
>>>> there's more code now though :-(.
>>>
>>> I don't like the names *_range_pointer, please change them to sth more
>>> specific like *_range_pointer_binary_op.
>>
>> Sure.
>>
>>>
>>> What's the advantage of "hiding" the resulting ranges behind the
>>> wide_int_range_nullness enum rather than having regular range output?
>>
>> Our upcoming work has another representation for non-nulls in particular
>> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share
>> whatever VRP is currently doing for pointers, without having to depend
>> on the internals of vrp (value_range *).
>>
>>> What's the value in separating pointer operations at all in the
>>> wide-int interfaces?  IIRC the difference is that whenever unioning
>>> is required that when it's a pointer result we should possibly
>>> preserve non-nullness.  It's of course also doing less work overall.
>>
>> I don't follow.  What are you suggesting?
> 
> I'm thinking out loud.  Here adding sort-of a "preferencing" to the
> more general handling of the ops would do the same trick, without
> restricting that to "pointers".  For example if a pass would be interested
> in knowing whether a divisor is zero it would also rather preserve
> non-nullness and trade that for precision in other parts of the range,
> say, if you had [-1, -1] [1, +INF] then the smallest unioning result
> is [-1, +INF] but ~[0, 0] is also a valid result which preserves non-zeroness.
> 
> So for wide-int workers I don't believe in tagging sth as pointers.  Rather
> than that ops might get one of
> 
>   enum vr_preference { VR_PREF_SMALL, VR_PREF_NONNULL, VR_PREF_NONNEGATIVE, ... }
> 
> ?

Neat.  I think this is worth exploring, but perhaps something to be 
looked at as a further enhancement?

> 
>>>
>>> So - in the end I'm not convinced that adding this kind of interface
>>> to the wide_int_ variants is worth it and I'd rather keep the existing
>>> VRP code?
>>
>> Again, I don't want to depend on vr_values or VRP in general.
> 
> Sure.  But the general handling of the ops (just treat POINTER_PLUS like PLUS)
> should do range operations just fine.  It's only the preferencing you'd lose
> and that preferencing looks like a more general feature than "lets have this
> function dealing with a small subset of binary ops on pointers"?

Something like MIN/MAX, that is specially handled for binary ops, can't 
be treated with the general min/max range operations.  Take for instance 
MIN(NULL, NON-NULL) which is basically MIN([0], [1..MAX]).  Generic 
range ops would yield 0/NULL, whereas current VRP returns VARYING.

Similarly for BIT_AND_EXPR.  Imagine [1,5] & [10,20] for pointers. 
Handling this generically would yield [0] (NULL), whereas the correct 
answer is NON-NULL.  And yes, [1,5] and [10,20] can actually happen, as 
I've mentioned in another thread.  I think it's libgcc that has code 
that does:

if (some_pointer == (pointer_type *) 1)
else if (some_pointer == (pointer_type *) 2)
etc etc.

Again, I think we could address your preference idea as an enhancement 
if you feel strongly about it.

We could make wide_int_range_pointer an inline function, and the penalty 
for VRP would only be the conversion to wide ints in vrp_range_pointer 
(extract_range_into_wide_ints actually).

> 
> The preferencing above would get passed down to the range unioning code.
> 
> Btw, since your wide-int-range code doesn't even have ANTI_RANGE, how
> do you represent non-zero in the API?

The way god intended of course, with the truth!  As I said earlier:

 >> Our upcoming work has another representation for non-nulls in particular
 >> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.

:-)

> 
> As said, splitting this out in the way of your patch looks "premature",
> there's not enough of the big picture visible for me to say it makes sense.

You could always look at svn/ssa-range :-P.  It's been merged with 
mainline as of early last week.

Splitting this out makes my life a lot easier, with virtually no penalty 
to VRP.  And we could always revisit it later.  But if you feel strongly 
about it, I could inline the pointer handling into our code, and revisit 
this later with you.

Aldy
Richard Biener Sept. 4, 2018, 1:41 p.m. UTC | #7
On Tue, Sep 4, 2018 at 3:21 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 09/04/2018 08:29 AM, Richard Biener wrote:
> > On Tue, Sep 4, 2018 at 2:09 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 09/04/2018 07:42 AM, Richard Biener wrote:
> >>> On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>>>
> >>>>
> >>>>
> >>>> On 08/29/2018 12:32 PM, David Malcolm wrote:
> >>>>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
> >>>>>> Never say never.  Just when I thought I was done...
> >>>>>>
> >>>>>> It looks like I need the special casing we do for pointer types in
> >>>>>> extract_range_from_binary_expr_1.
> >>>>>>
> >>>>>> The code is simple enough that we could just duplicate it anywhere
> >>>>>> we
> >>>>>> need it, but I hate code duplication and keeping track of multiple
> >>>>>> versions of the same thing.
> >>>>>>
> >>>>>> No change in functionality.
> >>>>>>
> >>>>>> Tested on x86-64 Linux with all languages.
> >>>>>>
> >>>>>> OK?
> >>>>>
> >>>>> A couple of nits I spotted:
> >>>>>
> >>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> >>>>> index f20730a85ba..228f20b5203 100644
> >>>>> --- a/gcc/tree-vrp.c
> >>>>> +++ b/gcc/tree-vrp.c
> >>>>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
> >>>>>         }
> >>>>>     }
> >>>>>
> >>>>> +/* Value range wrapper for wide_int_range_pointer.  */
> >>>>> +
> >>>>> +static void
> >>>>> +vrp_range_pointer (value_range *vr,
> >>>>> +                enum tree_code code, tree type,
> >>>>> +                value_range *vr0, value_range *vr1)
> >>>>>
> >>>>> Looking at the signature of the function, I wondered what the source
> >>>>> and destination of the information is...
> >>>>
> >>>> vr being the destination and vr0/vr1 being the sources are standard
> >>>> operating procedure within tree-vrp.c.  All the functions are basically
> >>>> that, that's why I haven't bothered.
> >>>>
> >>>>>
> >>>>> Could vr0 and vr1 be const?
> >>>>>
> >>>>> ...which would require extract_range_into_wide_ints to take a const
> >>>>> value_range *
> >>>>
> >>>> Yes, but that would require changing all of tree-vrp.c to take const
> >>>> value_range's.  For instance, range_int_cst_p and a slew of other
> >>>> functions throughout.
> >>>>
> >>>>>
> >>>>>      ... which would require range_int_cst_p to take a const value_range *
> >>>>>
> >>>>> (I *think* that's where the yak-shaving would end)
> >>>>>
> >>>>> +{
> >>>>> +  signop sign = TYPE_SIGN (type);
> >>>>> +  unsigned prec = TYPE_PRECISION (type);
> >>>>> +  wide_int vr0_min, vr0_max;
> >>>>> +  wide_int vr1_min, vr1_max;
> >>>>> +
> >>>>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
> >>>>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
> >>>>> +  wide_int_range_nullness n;
> >>>>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
> >>>>> vr1_max);
> >>>>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
> >>>>> +    set_value_range_to_varying (vr);
> >>>>> +  else if (n == WIDE_INT_RANGE_NULL)
> >>>>> +    set_value_range_to_null (vr, type);
> >>>>> +  else if (n == WIDE_INT_RANGE_NONNULL)
> >>>>> +    set_value_range_to_nonnull (vr, type);
> >>>>> +  else
> >>>>> +    gcc_unreachable ();
> >>>>> +}
> >>>>> +
> >>>>>
> >>>>> Would it be better to use a "switch (n)" here, rather than a series of
> >>>>> "if"/"else if" for each enum value?
> >>>>
> >>>> I prefer ifs for a small amount of options, but having the compiler warn
> >>>> on missing enum alternatives is nice, so I've changed it.  Notice
> >>>> there's more code now though :-(.
> >>>
> >>> I don't like the names *_range_pointer, please change them to sth more
> >>> specific like *_range_pointer_binary_op.
> >>
> >> Sure.
> >>
> >>>
> >>> What's the advantage of "hiding" the resulting ranges behind the
> >>> wide_int_range_nullness enum rather than having regular range output?
> >>
> >> Our upcoming work has another representation for non-nulls in particular
> >> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share
> >> whatever VRP is currently doing for pointers, without having to depend
> >> on the internals of vrp (value_range *).
> >>
> >>> What's the value in separating pointer operations at all in the
> >>> wide-int interfaces?  IIRC the difference is that whenever unioning
> >>> is required that when it's a pointer result we should possibly
> >>> preserve non-nullness.  It's of course also doing less work overall.
> >>
> >> I don't follow.  What are you suggesting?
> >
> > I'm thinking out loud.  Here adding sort-of a "preferencing" to the
> > more general handling of the ops would do the same trick, without
> > restricting that to "pointers".  For example if a pass would be interested
> > in knowing whether a divisor is zero it would also rather preserve
> > non-nullness and trade that for precision in other parts of the range,
> > say, if you had [-1, -1] [1, +INF] then the smallest unioning result
> > is [-1, +INF] but ~[0, 0] is also a valid result which preserves non-zeroness.
> >
> > So for wide-int workers I don't believe in tagging sth as pointers.  Rather
> > than that ops might get one of
> >
> >   enum vr_preference { VR_PREF_SMALL, VR_PREF_NONNULL, VR_PREF_NONNEGATIVE, ... }
> >
> > ?
>
> Neat.  I think this is worth exploring, but perhaps something to be
> looked at as a further enhancement?
>
> >
> >>>
> >>> So - in the end I'm not convinced that adding this kind of interface
> >>> to the wide_int_ variants is worth it and I'd rather keep the existing
> >>> VRP code?
> >>
> >> Again, I don't want to depend on vr_values or VRP in general.
> >
> > Sure.  But the general handling of the ops (just treat POINTER_PLUS like PLUS)
> > should do range operations just fine.  It's only the preferencing you'd lose
> > and that preferencing looks like a more general feature than "lets have this
> > function dealing with a small subset of binary ops on pointers"?
>
> Something like MIN/MAX, that is specially handled for binary ops, can't
> be treated with the general min/max range operations.  Take for instance
> MIN(NULL, NON-NULL) which is basically MIN([0], [1..MAX]).  Generic
> range ops would yield 0/NULL, whereas current VRP returns VARYING.
>
> Similarly for BIT_AND_EXPR.  Imagine [1,5] & [10,20] for pointers.
> Handling this generically would yield [0] (NULL), whereas the correct
> answer is NON-NULL.  And yes, [1,5] and [10,20] can actually happen, as
> I've mentioned in another thread.  I think it's libgcc that has code
> that does:
>
> if (some_pointer == (pointer_type *) 1)
> else if (some_pointer == (pointer_type *) 2)
> etc etc.
>
> Again, I think we could address your preference idea as an enhancement
> if you feel strongly about it.

Ah, OK.  It basically boils down to pointer operations having special semantics
(similar to overflow definedness).

> We could make wide_int_range_pointer an inline function, and the penalty
> for VRP would only be the conversion to wide ints in vrp_range_pointer
> (extract_range_into_wide_ints actually).
>
> >
> > The preferencing above would get passed down to the range unioning code.
> >
> > Btw, since your wide-int-range code doesn't even have ANTI_RANGE, how
> > do you represent non-zero in the API?
>
> The way god intended of course, with the truth!  As I said earlier:
>
>  >> Our upcoming work has another representation for non-nulls in particular
>  >> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.
>
> :-)
>
> >
> > As said, splitting this out in the way of your patch looks "premature",
> > there's not enough of the big picture visible for me to say it makes sense.
>
> You could always look at svn/ssa-range :-P.  It's been merged with
> mainline as of early last week.

Eh.

> Splitting this out makes my life a lot easier, with virtually no penalty
> to VRP.  And we could always revisit it later.  But if you feel strongly
> about it, I could inline the pointer handling into our code, and revisit
> this later with you.

Yeah, please do so - I'm leaving for the Cauldron soon.  Looking at
the current wide-int-range.h header doesn't reveal a consistent API :/

Richard.

> Aldy
Aldy Hernandez Sept. 4, 2018, 1:51 p.m. UTC | #8
On 09/04/2018 09:41 AM, Richard Biener wrote:
> On Tue, Sep 4, 2018 at 3:21 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 09/04/2018 08:29 AM, Richard Biener wrote:
>>> On Tue, Sep 4, 2018 at 2:09 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>>
>>>>
>>>> On 09/04/2018 07:42 AM, Richard Biener wrote:
>>>>> On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 08/29/2018 12:32 PM, David Malcolm wrote:
>>>>>>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
>>>>>>>> Never say never.  Just when I thought I was done...
>>>>>>>>
>>>>>>>> It looks like I need the special casing we do for pointer types in
>>>>>>>> extract_range_from_binary_expr_1.
>>>>>>>>
>>>>>>>> The code is simple enough that we could just duplicate it anywhere
>>>>>>>> we
>>>>>>>> need it, but I hate code duplication and keeping track of multiple
>>>>>>>> versions of the same thing.
>>>>>>>>
>>>>>>>> No change in functionality.
>>>>>>>>
>>>>>>>> Tested on x86-64 Linux with all languages.
>>>>>>>>
>>>>>>>> OK?
>>>>>>>
>>>>>>> A couple of nits I spotted:
>>>>>>>
>>>>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>>>>>> index f20730a85ba..228f20b5203 100644
>>>>>>> --- a/gcc/tree-vrp.c
>>>>>>> +++ b/gcc/tree-vrp.c
>>>>>>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
>>>>>>>          }
>>>>>>>      }
>>>>>>>
>>>>>>> +/* Value range wrapper for wide_int_range_pointer.  */
>>>>>>> +
>>>>>>> +static void
>>>>>>> +vrp_range_pointer (value_range *vr,
>>>>>>> +                enum tree_code code, tree type,
>>>>>>> +                value_range *vr0, value_range *vr1)
>>>>>>>
>>>>>>> Looking at the signature of the function, I wondered what the source
>>>>>>> and destination of the information is...
>>>>>>
>>>>>> vr being the destination and vr0/vr1 being the sources are standard
>>>>>> operating procedure within tree-vrp.c.  All the functions are basically
>>>>>> that, that's why I haven't bothered.
>>>>>>
>>>>>>>
>>>>>>> Could vr0 and vr1 be const?
>>>>>>>
>>>>>>> ...which would require extract_range_into_wide_ints to take a const
>>>>>>> value_range *
>>>>>>
>>>>>> Yes, but that would require changing all of tree-vrp.c to take const
>>>>>> value_range's.  For instance, range_int_cst_p and a slew of other
>>>>>> functions throughout.
>>>>>>
>>>>>>>
>>>>>>>       ... which would require range_int_cst_p to take a const value_range *
>>>>>>>
>>>>>>> (I *think* that's where the yak-shaving would end)
>>>>>>>
>>>>>>> +{
>>>>>>> +  signop sign = TYPE_SIGN (type);
>>>>>>> +  unsigned prec = TYPE_PRECISION (type);
>>>>>>> +  wide_int vr0_min, vr0_max;
>>>>>>> +  wide_int vr1_min, vr1_max;
>>>>>>> +
>>>>>>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
>>>>>>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
>>>>>>> +  wide_int_range_nullness n;
>>>>>>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
>>>>>>> vr1_max);
>>>>>>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
>>>>>>> +    set_value_range_to_varying (vr);
>>>>>>> +  else if (n == WIDE_INT_RANGE_NULL)
>>>>>>> +    set_value_range_to_null (vr, type);
>>>>>>> +  else if (n == WIDE_INT_RANGE_NONNULL)
>>>>>>> +    set_value_range_to_nonnull (vr, type);
>>>>>>> +  else
>>>>>>> +    gcc_unreachable ();
>>>>>>> +}
>>>>>>> +
>>>>>>>
>>>>>>> Would it be better to use a "switch (n)" here, rather than a series of
>>>>>>> "if"/"else if" for each enum value?
>>>>>>
>>>>>> I prefer ifs for a small amount of options, but having the compiler warn
>>>>>> on missing enum alternatives is nice, so I've changed it.  Notice
>>>>>> there's more code now though :-(.
>>>>>
>>>>> I don't like the names *_range_pointer, please change them to sth more
>>>>> specific like *_range_pointer_binary_op.
>>>>
>>>> Sure.
>>>>
>>>>>
>>>>> What's the advantage of "hiding" the resulting ranges behind the
>>>>> wide_int_range_nullness enum rather than having regular range output?
>>>>
>>>> Our upcoming work has another representation for non-nulls in particular
>>>> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share
>>>> whatever VRP is currently doing for pointers, without having to depend
>>>> on the internals of vrp (value_range *).
>>>>
>>>>> What's the value in separating pointer operations at all in the
>>>>> wide-int interfaces?  IIRC the difference is that whenever unioning
>>>>> is required that when it's a pointer result we should possibly
>>>>> preserve non-nullness.  It's of course also doing less work overall.
>>>>
>>>> I don't follow.  What are you suggesting?
>>>
>>> I'm thinking out loud.  Here adding sort-of a "preferencing" to the
>>> more general handling of the ops would do the same trick, without
>>> restricting that to "pointers".  For example if a pass would be interested
>>> in knowing whether a divisor is zero it would also rather preserve
>>> non-nullness and trade that for precision in other parts of the range,
>>> say, if you had [-1, -1] [1, +INF] then the smallest unioning result
>>> is [-1, +INF] but ~[0, 0] is also a valid result which preserves non-zeroness.
>>>
>>> So for wide-int workers I don't believe in tagging sth as pointers.  Rather
>>> than that ops might get one of
>>>
>>>    enum vr_preference { VR_PREF_SMALL, VR_PREF_NONNULL, VR_PREF_NONNEGATIVE, ... }
>>>
>>> ?
>>
>> Neat.  I think this is worth exploring, but perhaps something to be
>> looked at as a further enhancement?
>>
>>>
>>>>>
>>>>> So - in the end I'm not convinced that adding this kind of interface
>>>>> to the wide_int_ variants is worth it and I'd rather keep the existing
>>>>> VRP code?
>>>>
>>>> Again, I don't want to depend on vr_values or VRP in general.
>>>
>>> Sure.  But the general handling of the ops (just treat POINTER_PLUS like PLUS)
>>> should do range operations just fine.  It's only the preferencing you'd lose
>>> and that preferencing looks like a more general feature than "lets have this
>>> function dealing with a small subset of binary ops on pointers"?
>>
>> Something like MIN/MAX, that is specially handled for binary ops, can't
>> be treated with the general min/max range operations.  Take for instance
>> MIN(NULL, NON-NULL) which is basically MIN([0], [1..MAX]).  Generic
>> range ops would yield 0/NULL, whereas current VRP returns VARYING.
>>
>> Similarly for BIT_AND_EXPR.  Imagine [1,5] & [10,20] for pointers.
>> Handling this generically would yield [0] (NULL), whereas the correct
>> answer is NON-NULL.  And yes, [1,5] and [10,20] can actually happen, as
>> I've mentioned in another thread.  I think it's libgcc that has code
>> that does:
>>
>> if (some_pointer == (pointer_type *) 1)
>> else if (some_pointer == (pointer_type *) 2)
>> etc etc.
>>
>> Again, I think we could address your preference idea as an enhancement
>> if you feel strongly about it.
> 
> Ah, OK.  It basically boils down to pointer operations having special semantics
> (similar to overflow definedness).

Yes.

> 
>> We could make wide_int_range_pointer an inline function, and the penalty
>> for VRP would only be the conversion to wide ints in vrp_range_pointer
>> (extract_range_into_wide_ints actually).
>>
>>>
>>> The preferencing above would get passed down to the range unioning code.
>>>
>>> Btw, since your wide-int-range code doesn't even have ANTI_RANGE, how
>>> do you represent non-zero in the API?
>>
>> The way god intended of course, with the truth!  As I said earlier:
>>
>>   >> Our upcoming work has another representation for non-nulls in particular
>>   >> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.
>>
>> :-)
>>
>>>
>>> As said, splitting this out in the way of your patch looks "premature",
>>> there's not enough of the big picture visible for me to say it makes sense.
>>
>> You could always look at svn/ssa-range :-P.  It's been merged with
>> mainline as of early last week.
> 
> Eh.
> 
>> Splitting this out makes my life a lot easier, with virtually no penalty
>> to VRP.  And we could always revisit it later.  But if you feel strongly
>> about it, I could inline the pointer handling into our code, and revisit
>> this later with you.
> 
> Yeah, please do so - I'm leaving for the Cauldron soon.  Looking at
> the current wide-int-range.h header doesn't reveal a consistent API :/

Suggestions welcome :).

Just to make sure, was that OK and approval, provided I make the 
function an inline?

Thanks, and see you at Cauldron (albeit a few days late).
Aldy
Richard Biener Sept. 4, 2018, 2:12 p.m. UTC | #9
On Tue, Sep 4, 2018 at 3:51 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 09/04/2018 09:41 AM, Richard Biener wrote:
> > On Tue, Sep 4, 2018 at 3:21 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 09/04/2018 08:29 AM, Richard Biener wrote:
> >>> On Tue, Sep 4, 2018 at 2:09 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>>>
> >>>>
> >>>>
> >>>> On 09/04/2018 07:42 AM, Richard Biener wrote:
> >>>>> On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>> On 08/29/2018 12:32 PM, David Malcolm wrote:
> >>>>>>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
> >>>>>>>> Never say never.  Just when I thought I was done...
> >>>>>>>>
> >>>>>>>> It looks like I need the special casing we do for pointer types in
> >>>>>>>> extract_range_from_binary_expr_1.
> >>>>>>>>
> >>>>>>>> The code is simple enough that we could just duplicate it anywhere
> >>>>>>>> we
> >>>>>>>> need it, but I hate code duplication and keeping track of multiple
> >>>>>>>> versions of the same thing.
> >>>>>>>>
> >>>>>>>> No change in functionality.
> >>>>>>>>
> >>>>>>>> Tested on x86-64 Linux with all languages.
> >>>>>>>>
> >>>>>>>> OK?
> >>>>>>>
> >>>>>>> A couple of nits I spotted:
> >>>>>>>
> >>>>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> >>>>>>> index f20730a85ba..228f20b5203 100644
> >>>>>>> --- a/gcc/tree-vrp.c
> >>>>>>> +++ b/gcc/tree-vrp.c
> >>>>>>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
> >>>>>>>          }
> >>>>>>>      }
> >>>>>>>
> >>>>>>> +/* Value range wrapper for wide_int_range_pointer.  */
> >>>>>>> +
> >>>>>>> +static void
> >>>>>>> +vrp_range_pointer (value_range *vr,
> >>>>>>> +                enum tree_code code, tree type,
> >>>>>>> +                value_range *vr0, value_range *vr1)
> >>>>>>>
> >>>>>>> Looking at the signature of the function, I wondered what the source
> >>>>>>> and destination of the information is...
> >>>>>>
> >>>>>> vr being the destination and vr0/vr1 being the sources are standard
> >>>>>> operating procedure within tree-vrp.c.  All the functions are basically
> >>>>>> that, that's why I haven't bothered.
> >>>>>>
> >>>>>>>
> >>>>>>> Could vr0 and vr1 be const?
> >>>>>>>
> >>>>>>> ...which would require extract_range_into_wide_ints to take a const
> >>>>>>> value_range *
> >>>>>>
> >>>>>> Yes, but that would require changing all of tree-vrp.c to take const
> >>>>>> value_range's.  For instance, range_int_cst_p and a slew of other
> >>>>>> functions throughout.
> >>>>>>
> >>>>>>>
> >>>>>>>       ... which would require range_int_cst_p to take a const value_range *
> >>>>>>>
> >>>>>>> (I *think* that's where the yak-shaving would end)
> >>>>>>>
> >>>>>>> +{
> >>>>>>> +  signop sign = TYPE_SIGN (type);
> >>>>>>> +  unsigned prec = TYPE_PRECISION (type);
> >>>>>>> +  wide_int vr0_min, vr0_max;
> >>>>>>> +  wide_int vr1_min, vr1_max;
> >>>>>>> +
> >>>>>>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
> >>>>>>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
> >>>>>>> +  wide_int_range_nullness n;
> >>>>>>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
> >>>>>>> vr1_max);
> >>>>>>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
> >>>>>>> +    set_value_range_to_varying (vr);
> >>>>>>> +  else if (n == WIDE_INT_RANGE_NULL)
> >>>>>>> +    set_value_range_to_null (vr, type);
> >>>>>>> +  else if (n == WIDE_INT_RANGE_NONNULL)
> >>>>>>> +    set_value_range_to_nonnull (vr, type);
> >>>>>>> +  else
> >>>>>>> +    gcc_unreachable ();
> >>>>>>> +}
> >>>>>>> +
> >>>>>>>
> >>>>>>> Would it be better to use a "switch (n)" here, rather than a series of
> >>>>>>> "if"/"else if" for each enum value?
> >>>>>>
> >>>>>> I prefer ifs for a small amount of options, but having the compiler warn
> >>>>>> on missing enum alternatives is nice, so I've changed it.  Notice
> >>>>>> there's more code now though :-(.
> >>>>>
> >>>>> I don't like the names *_range_pointer, please change them to sth more
> >>>>> specific like *_range_pointer_binary_op.
> >>>>
> >>>> Sure.
> >>>>
> >>>>>
> >>>>> What's the advantage of "hiding" the resulting ranges behind the
> >>>>> wide_int_range_nullness enum rather than having regular range output?
> >>>>
> >>>> Our upcoming work has another representation for non-nulls in particular
> >>>> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share
> >>>> whatever VRP is currently doing for pointers, without having to depend
> >>>> on the internals of vrp (value_range *).
> >>>>
> >>>>> What's the value in separating pointer operations at all in the
> >>>>> wide-int interfaces?  IIRC the difference is that whenever unioning
> >>>>> is required that when it's a pointer result we should possibly
> >>>>> preserve non-nullness.  It's of course also doing less work overall.
> >>>>
> >>>> I don't follow.  What are you suggesting?
> >>>
> >>> I'm thinking out loud.  Here adding sort-of a "preferencing" to the
> >>> more general handling of the ops would do the same trick, without
> >>> restricting that to "pointers".  For example if a pass would be interested
> >>> in knowing whether a divisor is zero it would also rather preserve
> >>> non-nullness and trade that for precision in other parts of the range,
> >>> say, if you had [-1, -1] [1, +INF] then the smallest unioning result
> >>> is [-1, +INF] but ~[0, 0] is also a valid result which preserves non-zeroness.
> >>>
> >>> So for wide-int workers I don't believe in tagging sth as pointers.  Rather
> >>> than that ops might get one of
> >>>
> >>>    enum vr_preference { VR_PREF_SMALL, VR_PREF_NONNULL, VR_PREF_NONNEGATIVE, ... }
> >>>
> >>> ?
> >>
> >> Neat.  I think this is worth exploring, but perhaps something to be
> >> looked at as a further enhancement?
> >>
> >>>
> >>>>>
> >>>>> So - in the end I'm not convinced that adding this kind of interface
> >>>>> to the wide_int_ variants is worth it and I'd rather keep the existing
> >>>>> VRP code?
> >>>>
> >>>> Again, I don't want to depend on vr_values or VRP in general.
> >>>
> >>> Sure.  But the general handling of the ops (just treat POINTER_PLUS like PLUS)
> >>> should do range operations just fine.  It's only the preferencing you'd lose
> >>> and that preferencing looks like a more general feature than "lets have this
> >>> function dealing with a small subset of binary ops on pointers"?
> >>
> >> Something like MIN/MAX, that is specially handled for binary ops, can't
> >> be treated with the general min/max range operations.  Take for instance
> >> MIN(NULL, NON-NULL) which is basically MIN([0], [1..MAX]).  Generic
> >> range ops would yield 0/NULL, whereas current VRP returns VARYING.
> >>
> >> Similarly for BIT_AND_EXPR.  Imagine [1,5] & [10,20] for pointers.
> >> Handling this generically would yield [0] (NULL), whereas the correct
> >> answer is NON-NULL.  And yes, [1,5] and [10,20] can actually happen, as
> >> I've mentioned in another thread.  I think it's libgcc that has code
> >> that does:
> >>
> >> if (some_pointer == (pointer_type *) 1)
> >> else if (some_pointer == (pointer_type *) 2)
> >> etc etc.
> >>
> >> Again, I think we could address your preference idea as an enhancement
> >> if you feel strongly about it.
> >
> > Ah, OK.  It basically boils down to pointer operations having special semantics
> > (similar to overflow definedness).
>
> Yes.
>
> >
> >> We could make wide_int_range_pointer an inline function, and the penalty
> >> for VRP would only be the conversion to wide ints in vrp_range_pointer
> >> (extract_range_into_wide_ints actually).
> >>
> >>>
> >>> The preferencing above would get passed down to the range unioning code.
> >>>
> >>> Btw, since your wide-int-range code doesn't even have ANTI_RANGE, how
> >>> do you represent non-zero in the API?
> >>
> >> The way god intended of course, with the truth!  As I said earlier:
> >>
> >>   >> Our upcoming work has another representation for non-nulls in particular
> >>   >> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.
> >>
> >> :-)
> >>
> >>>
> >>> As said, splitting this out in the way of your patch looks "premature",
> >>> there's not enough of the big picture visible for me to say it makes sense.
> >>
> >> You could always look at svn/ssa-range :-P.  It's been merged with
> >> mainline as of early last week.
> >
> > Eh.
> >
> >> Splitting this out makes my life a lot easier, with virtually no penalty
> >> to VRP.  And we could always revisit it later.  But if you feel strongly
> >> about it, I could inline the pointer handling into our code, and revisit
> >> this later with you.
> >
> > Yeah, please do so - I'm leaving for the Cauldron soon.  Looking at
> > the current wide-int-range.h header doesn't reveal a consistent API :/
>
> Suggestions welcome :).
>
> Just to make sure, was that OK and approval, provided I make the
> function an inline?

It was to "inline the pointer handling into our code"

>
> Thanks, and see you at Cauldron (albeit a few days late).
> Aldy
Aldy Hernandez Sept. 4, 2018, 2:17 p.m. UTC | #10
On 09/04/2018 10:12 AM, Richard Biener wrote:
> On Tue, Sep 4, 2018 at 3:51 PM Aldy Hernandez <aldyh@redhat.com> wrote:

>>>> Splitting this out makes my life a lot easier, with virtually no penalty
>>>> to VRP.  And we could always revisit it later.  But if you feel strongly
>>>> about it, I could inline the pointer handling into our code, and revisit
>>>> this later with you.
>>>
>>> Yeah, please do so - I'm leaving for the Cauldron soon.  Looking at
>>> the current wide-int-range.h header doesn't reveal a consistent API :/
>>
>> Suggestions welcome :).
>>
>> Just to make sure, was that OK and approval, provided I make the
>> function an inline?
> 
> It was to "inline the pointer handling into our code"

Booo!!!!

Patch
diff mbox series

commit 32a423e3ab5a75eee6de59b1a235a2892dc8ca38
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Tue Aug 28 17:27:26 2018 +0200

            * tree-vrp.c (vrp_range_pointer): New.
            (extract_range_from_binary_expr_1): Call vrp_range_pointer.
            * wide-int-range.cc (wide_int_range_pointer): New.
            * wide-int-range.h (enum wide_int_range_nullness): New.
            (wide_int_range_pointer): New.

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index f20730a85ba..228f20b5203 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1275,6 +1275,32 @@  set_value_range_with_overflow (value_range &vr,
     }
 }
 
+/* Value range wrapper for wide_int_range_pointer.  */
+
+static void
+vrp_range_pointer (value_range *vr,
+		   enum tree_code code, tree type,
+		   value_range *vr0, value_range *vr1)
+{
+  signop sign = TYPE_SIGN (type);
+  unsigned prec = TYPE_PRECISION (type);
+  wide_int vr0_min, vr0_max;
+  wide_int vr1_min, vr1_max;
+
+  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
+  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
+  wide_int_range_nullness n;
+  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min, vr1_max);
+  if (n == WIDE_INT_RANGE_UNKNOWN)
+    set_value_range_to_varying (vr);
+  else if (n == WIDE_INT_RANGE_NULL)
+    set_value_range_to_null (vr, type);
+  else if (n == WIDE_INT_RANGE_NONNULL)
+    set_value_range_to_nonnull (vr, type);
+  else
+    gcc_unreachable ();
+}
+
 /* Extract range information from a binary operation CODE based on
    the ranges of each of its operands *VR0 and *VR1 with resulting
    type EXPR_TYPE.  The resulting range is stored in *VR.  */
@@ -1416,47 +1442,10 @@  extract_range_from_binary_expr_1 (value_range *vr,
     }
 
   /* Now evaluate the expression to determine the new range.  */
+
   if (POINTER_TYPE_P (expr_type))
     {
-      if (code == MIN_EXPR || code == MAX_EXPR)
-	{
-	  /* For MIN/MAX expressions with pointers, we only care about
-	     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_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);
-	  else
-	    set_value_range_to_varying (vr);
-	}
-      else if (code == POINTER_PLUS_EXPR)
-	{
-	  /* For pointer types, we are really only interested in asserting
-	     whether the expression evaluates to non-NULL.  */
-	  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);
-	  else
-	    set_value_range_to_varying (vr);
-	}
-      else if (code == BIT_AND_EXPR)
-	{
-	  /* For pointer types, we are really only interested in asserting
-	     whether the expression evaluates to non-NULL.  */
-	  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);
-	  else
-	    set_value_range_to_varying (vr);
-	}
-      else
-	set_value_range_to_varying (vr);
-
+      vrp_range_pointer (vr, code, expr_type, &vr0, &vr1);
       return;
     }
 
diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc
index 3cdcede04cd..9ab1b04c4dd 100644
--- a/gcc/wide-int-range.cc
+++ b/gcc/wide-int-range.cc
@@ -733,3 +733,60 @@  wide_int_range_div (wide_int &wmin, wide_int &wmax,
     extra_range_p = false;
   return true;
 }
+
+/* Given a binary operator (CODE) on two pointer ranges, return if the
+   result will be zero, non-zero, or unknown.  */
+
+enum wide_int_range_nullness
+wide_int_range_pointer (enum tree_code code,
+			signop sign,
+			const wide_int &vr0_min,
+			const wide_int &vr0_max,
+			const wide_int &vr1_min,
+			const wide_int &vr1_max)
+{
+  unsigned prec = vr0_min.get_precision ();
+  if (code == MIN_EXPR || code == MAX_EXPR)
+    {
+      /* For MIN/MAX expressions with pointers, we only care about
+	 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 (!wide_int_range_includes_zero_p (vr0_min, vr0_max, sign)
+	  && !wide_int_range_includes_zero_p (vr1_min, vr1_max, sign))
+	return WIDE_INT_RANGE_NONNULL;
+      else if (wide_int_range_zero_p (vr0_min, vr0_max, prec)
+	       && wide_int_range_zero_p (vr1_min, vr1_max, prec))
+	return WIDE_INT_RANGE_NULL;
+      else
+	return WIDE_INT_RANGE_UNKNOWN;
+    }
+  else if (code == POINTER_PLUS_EXPR)
+    {
+      /* For pointer types, we are really only interested in asserting
+	 whether the expression evaluates to non-NULL.  */
+      if (!wide_int_range_includes_zero_p (vr0_min, vr0_max, sign)
+	  || !wide_int_range_includes_zero_p (vr1_min, vr1_max, sign))
+	return WIDE_INT_RANGE_NONNULL;
+      else if (wide_int_range_zero_p (vr0_min, vr0_max, prec)
+	       && wide_int_range_zero_p (vr1_min, vr1_max, prec))
+	return WIDE_INT_RANGE_NULL;
+      else
+	return WIDE_INT_RANGE_UNKNOWN;
+    }
+  else if (code == BIT_AND_EXPR)
+    {
+      /* For pointer types, we are really only interested in asserting
+	 whether the expression evaluates to non-NULL.  */
+      if (!wide_int_range_includes_zero_p (vr0_min, vr0_max, sign)
+	  && !wide_int_range_includes_zero_p (vr1_min, vr1_max, sign))
+	return WIDE_INT_RANGE_NONNULL;
+      else if (wide_int_range_zero_p (vr0_min, vr0_max, prec)
+	       || wide_int_range_zero_p (vr1_min, vr1_max, prec))
+	return WIDE_INT_RANGE_NULL;
+      else
+	return WIDE_INT_RANGE_UNKNOWN;
+    }
+  else
+    return WIDE_INT_RANGE_UNKNOWN;
+}
diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
index 427ef34c6b4..ecdd961df36 100644
--- a/gcc/wide-int-range.h
+++ b/gcc/wide-int-range.h
@@ -20,6 +20,14 @@  along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_WIDE_INT_RANGE_H
 #define GCC_WIDE_INT_RANGE_H
 
+/* For an operation on pointers, this specifies whether the resulting
+   operation is null, non-null, or unknown.  */
+enum wide_int_range_nullness {
+  WIDE_INT_RANGE_UNKNOWN = 0,
+  WIDE_INT_RANGE_NULL,
+  WIDE_INT_RANGE_NONNULL
+};
+
 extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
 					  enum tree_code code, signop sign,
 					  const wide_int &, const wide_int &,
@@ -110,6 +118,12 @@  extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
 				bool overflow_wraps,
 				bool &extra_range_p,
 				wide_int &extra_min, wide_int &extra_max);
+enum wide_int_range_nullness wide_int_range_pointer (enum tree_code code,
+						     signop sign,
+						     const wide_int &vr0_min,
+						     const wide_int &vr0_max,
+						     const wide_int &vr1_min,
+						     const wide_int &vr1_max);
 
 /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */