Fix VRP with -fno-delete-null-pointer-checks (PR c/88367)

Hi!

If we consider -fno-delete-null-pointer-checks as a way to support e.g. AVR
and other targets which can validly place objects at NULL rather than a way
to workaround UBs in code, I believe the following testcase must pass if
there is e.g.
char a[32];		// And this object ends up at address 0
void bar (void);
int main () { foo (&a[3]); baz (&a[6]); }
but fails right now.  As mentioned in the PR, in GCC 8 we used to do:
      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_is_nonnull (&vr0) || range_is_nonnull (&vr1))
            set_value_range_to_nonnull (vr, expr_type);
and that triggered pretty much never, as range_is_nonnull requires that the
offset is ~[0, 0] exactly, e.g. if it is a constant, it is never that way,
but now we do:
	  if (!range_includes_zero_p (&vr0) || !range_includes_zero_p (&vr1))
which is e.g. always if the offset is constant non-zero.

I hope we can still say that pointer wrapping even with
-fno-delete-null-pointer-checks is UB, so this patch differentiates between
positive offsets (in ssizetype), negative offsets (in ssizetype) and zero
offsets and handles both the same for both ptr p+ offset and &MEM_REF[ptr, offset]
If offset is 0 and ptr is ~[0, 0], then the result is ~[0, 0] as before.
If offset is positive in ssizetype, then even for VARYING ptr the result is
~[0, 0] pointer.  If the offset is (or maybe could be) negative in
ssizetype, then for -fno-delete-null-pointer-checks the result is VARYING,
as we could go from a non-NULL pointer back to NULL on those targets; for
-fdelete-null-pointer-checks we do what we've done before, i.e. ~[0, 0].

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2018-12-06  Jakub Jelinek  <jakub@redhat.com>

	PR c/88367
	* tree-vrp.c (extract_range_from_binary_expr): For POINTER_PLUS_EXPR
	with -fno-delete-null-pointer-checks, set_nonnull only if the pointer
	is non-NULL and offset is known to have most significant bit clear.
	* vr-values.c (vr_values::vrp_stmt_computes_nonzero): For ADDR_EXPR
	of MEM_EXPR, return true if the MEM_EXPR has non-zero offset with
	most significant bit clear.  If offset does have most significant bit
	set and -fno-delete-null-pointer-checks, don't return true even if
	the base pointer is non-NULL.

	* gcc.dg/tree-ssa/pr88367.c: New test.


	Jakub

On Thu, 6 Dec 2018, Jakub Jelinek wrote:

> Hi!
> 
> If we consider -fno-delete-null-pointer-checks as a way to support e.g. AVR
> and other targets which can validly place objects at NULL rather than a way
> to workaround UBs in code, I believe the following testcase must pass if
> there is e.g.
> char a[32];		// And this object ends up at address 0
> void bar (void);
> int main () { foo (&a[3]); baz (&a[6]); }
> but fails right now.  As mentioned in the PR, in GCC 8 we used to do:
>       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_is_nonnull (&vr0) || range_is_nonnull (&vr1))
>             set_value_range_to_nonnull (vr, expr_type);
> and that triggered pretty much never, as range_is_nonnull requires that the
> offset is ~[0, 0] exactly, e.g. if it is a constant, it is never that way,
> but now we do:
> 	  if (!range_includes_zero_p (&vr0) || !range_includes_zero_p (&vr1))
> which is e.g. always if the offset is constant non-zero.
> 
> I hope we can still say that pointer wrapping even with
> -fno-delete-null-pointer-checks is UB, so this patch differentiates between
> positive offsets (in ssizetype), negative offsets (in ssizetype) and zero
> offsets and handles both the same for both ptr p+ offset and &MEM_REF[ptr, offset]
> If offset is 0 and ptr is ~[0, 0], then the result is ~[0, 0] as before.
> If offset is positive in ssizetype, then even for VARYING ptr the result is
> ~[0, 0] pointer.  If the offset is (or maybe could be) negative in
> ssizetype, then for -fno-delete-null-pointer-checks the result is VARYING,
> as we could go from a non-NULL pointer back to NULL on those targets; for
> -fdelete-null-pointer-checks we do what we've done before, i.e. ~[0, 0].
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

Note I wonder if with -fwrapv-pointer NULL automatically becomes a
valid address?  Or is only wrapping around half of the address
space UB?

Richard.

> 2018-12-06  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR c/88367
> 	* tree-vrp.c (extract_range_from_binary_expr): For POINTER_PLUS_EXPR
> 	with -fno-delete-null-pointer-checks, set_nonnull only if the pointer
> 	is non-NULL and offset is known to have most significant bit clear.
> 	* vr-values.c (vr_values::vrp_stmt_computes_nonzero): For ADDR_EXPR
> 	of MEM_EXPR, return true if the MEM_EXPR has non-zero offset with
> 	most significant bit clear.  If offset does have most significant bit
> 	set and -fno-delete-null-pointer-checks, don't return true even if
> 	the base pointer is non-NULL.
> 
> 	* gcc.dg/tree-ssa/pr88367.c: New test.
> 
> --- gcc/tree-vrp.c.jj	2018-12-04 13:00:02.408635579 +0100
> +++ gcc/tree-vrp.c	2018-12-05 19:07:36.187567781 +0100
> @@ -1673,9 +1673,25 @@ extract_range_from_binary_expr (value_ra
>        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))
> +	     whether the expression evaluates to non-NULL.
> +	     With -fno-delete-null-pointer-checks we need to be more
> +	     conservative.  As some object might reside at address 0,
> +	     then some offset could be added to it and the same offset
> +	     subtracted again and the result would be NULL.
> +	     E.g.
> +	     static int a[12]; where &a[0] is NULL and
> +	     ptr = &a[6];
> +	     ptr -= 6;
> +	     ptr will be NULL here, even when there is POINTER_PLUS_EXPR
> +	     where the first range doesn't include zero and the second one
> +	     doesn't either.  As the second operand is sizetype (unsigned),
> +	     consider all ranges where the MSB could be set as possible
> +	     subtractions where the result might be NULL.  */
> +	  if ((!range_includes_zero_p (&vr0)
> +	       || !range_includes_zero_p (&vr1))
> +	      && (flag_delete_null_pointer_checks
> +		  || (range_int_cst_p (&vr1)
> +		      && !tree_int_cst_sign_bit (vr1.max ()))))
>  	    vr->set_nonnull (expr_type);
>  	  else if (range_is_null (&vr0) && range_is_null (&vr1))
>  	    vr->set_null (expr_type);
> --- gcc/vr-values.c.jj	2018-11-29 08:41:33.152749436 +0100
> +++ gcc/vr-values.c	2018-12-05 19:37:56.222582823 +0100
> @@ -303,8 +303,17 @@ vr_values::vrp_stmt_computes_nonzero (gi
>  	  && TREE_CODE (base) == MEM_REF
>  	  && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
>  	{
> -	  value_range *vr = get_value_range (TREE_OPERAND (base, 0));
> -	  if (!range_includes_zero_p (vr))
> +	  if (integer_zerop (TREE_OPERAND (base, 1))
> +	      || flag_delete_null_pointer_checks)
> +	    {
> +	      value_range *vr = get_value_range (TREE_OPERAND (base, 0));
> +	      if (!range_includes_zero_p (vr))
> +		return true;
> +	    }
> +	  /* If MEM_REF has a "positive" offset, consider it non-NULL
> +	     always.  */
> +	  if (integer_nonzerop (TREE_OPERAND (base, 1))
> +	      && !tree_int_cst_sign_bit (TREE_OPERAND (base, 1)))
>  	    return true;
>  	}
>      }
> --- gcc/testsuite/gcc.dg/tree-ssa/pr88367.c.jj	2018-12-05 19:24:36.386727781 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr88367.c	2018-12-05 19:40:43.228839763 +0100
> @@ -0,0 +1,31 @@
> +/* PR c/88367 */
> +/* { dg-do compile } */
> +/* { dg-options "-fno-delete-null-pointer-checks -O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-not "link_error \\(\\);" "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "bar \\(\\);" 2 "optimized" } } */
> +
> +void bar (void);
> +void link_error (void);
> +
> +void
> +foo (char *p)
> +{
> +  if (!p)
> +    return;
> +  p += 3;
> +  if (!p)
> +    link_error ();
> +  p -= 6;
> +  if (!p)
> +    bar ();
> +}
> +
> +void
> +baz (char *p)
> +{
> +  if (!p)
> +    return;
> +  p -= 6;
> +  if (!p)
> +    bar ();
> +}
> 
> 	Jakub
> 
>

On 12/5/18 11:45 PM, Jakub Jelinek wrote:
> Hi!
> 
> If we consider -fno-delete-null-pointer-checks as a way to support e.g. AVR
> and other targets which can validly place objects at NULL rather than a way
> to workaround UBs in code, I believe the following testcase must pass if
> there is e.g.
Well, the intent was to be able to turn off the assumption that *0 would
cause a fault and halt the program.  That assumption allows us to use an
earlier pointer dereference to infer it currently has a non-NULL value
and eliminate subsequent tests against NULL.

It was never really meant to be a general escape hatch to allow other
forms of undefined behavior.

Though the name is particularly bad since it implies we never delete any
null pointer checks.


> 
> I hope we can still say that pointer wrapping even with
> -fno-delete-null-pointer-checks is UB, so this patch differentiates between
> positive offsets (in ssizetype), negative offsets (in ssizetype) and zero
> offsets and handles both the same for both ptr p+ offset and &MEM_REF[ptr, offset]
> If offset is 0 and ptr is ~[0, 0], then the result is ~[0, 0] as before.
> If offset is positive in ssizetype, then even for VARYING ptr the result is
> ~[0, 0] pointer.  If the offset is (or maybe could be) negative in
> ssizetype, then for -fno-delete-null-pointer-checks the result is VARYING,
> as we could go from a non-NULL pointer back to NULL on those targets; for
> -fdelete-null-pointer-checks we do what we've done before, i.e. ~[0, 0].
I'm not sure why we'd treat subtraction and addition any differently,
but maybe I'm missing something subtle (or not so subtle).

ISTM that ~[0,0] +- <whatever> still results in ~[0,0] for
-fdelete-null-pointer-checks.  For -fno-delete-null-pointer-checks ISTM
we should indicate "we don't know anything about the result" of such an
operation.


Jeff

On Thu, Dec 06, 2018 at 01:08:34PM -0700, Jeff Law wrote:
> > I hope we can still say that pointer wrapping even with
> > -fno-delete-null-pointer-checks is UB, so this patch differentiates between
> > positive offsets (in ssizetype), negative offsets (in ssizetype) and zero
> > offsets and handles both the same for both ptr p+ offset and &MEM_REF[ptr, offset]
> > If offset is 0 and ptr is ~[0, 0], then the result is ~[0, 0] as before.
> > If offset is positive in ssizetype, then even for VARYING ptr the result is
> > ~[0, 0] pointer.  If the offset is (or maybe could be) negative in
> > ssizetype, then for -fno-delete-null-pointer-checks the result is VARYING,
> > as we could go from a non-NULL pointer back to NULL on those targets; for
> > -fdelete-null-pointer-checks we do what we've done before, i.e. ~[0, 0].
> I'm not sure why we'd treat subtraction and addition any differently,
> but maybe I'm missing something subtle (or not so subtle).
> 
> ISTM that ~[0,0] +- <whatever> still results in ~[0,0] for
> -fdelete-null-pointer-checks.

Yes, the patch preserves that (unless -fwrapv-pointers).
Additionally, it does VARYING += ~[0,0] in that mode to ~[0,0].

>  For -fno-delete-null-pointer-checks ISTM
> we should indicate "we don't know anything about the result" of such an
> operation.

There are cases where we still know something.  The largest valid object
that can be supported is half of the address space, so without pointer
wrapping, positive additions to the pointer shouldn't wrap around and yield
NULL, negative ones can.  With -fwrapv-pointers anything can happen, sure,
the only case handled in that case is &[ptr + 0] if ptr is ~[0, 0] then
&[ptr + 0] is also ~[0, 0].

	Jakub

On 12/6/18 1:32 PM, Jakub Jelinek wrote:
>>  For -fno-delete-null-pointer-checks ISTM
>> we should indicate "we don't know anything about the result" of such an
>> operation.
> 
> There are cases where we still know something.  The largest valid object
> that can be supported is half of the address space, so without pointer
> wrapping, positive additions to the pointer shouldn't wrap around and yield
> NULL, negative ones can.  With -fwrapv-pointers anything can happen, sure,
> the only case handled in that case is &[ptr + 0] if ptr is ~[0, 0] then
> &[ptr + 0] is also ~[0, 0].
Yea.  I just didn't figure those were worth worrying about.
jeff