[PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1590 bytes --]

Hi,

Consider the following example.

extern unsigned int foo (int*) __attribute__((pure));
unsigned int
tr (int array[], int n)
{
  unsigned int i;
  unsigned int sum = 0;
  for (i = 0; i < n; i++)
    sum += foo (&array[i]);
  return sum;
}

For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith
currently concludes that the range of valid &array[i] is &array[0x0] to
&array[0x3fffffff], meaning 0x40000000 distinct values.
This implies that i < n is executed at most 0x40000001 times, and i < n
cannot be eliminated by an 32-bit iterator with step 4, since that one has
only 0x40000000 distinct values.

The patch reasons that NULL cannot be used or produced by pointer
arithmetic, and that we can exclude the possibility of the NULL pointer in the
range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe],
meaning 0x3fffffff distinct values.
This implies that i < n is executed at most 0x40000000 times and i < n can be
eliminated.

The patch implements this new limitation by changing the (low, high, step)
triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4)
to (0x4, 0xffffffff, 0x4).

I'm not too happy about the test for C-like language: ptrdiff_type_node !=
NULL_TREE, but I'm not sure how else to test for this.

Bootstrapped and reg-tested on x86_64.

I will sent the adapted test cases in a separate email.

OK for trunk?

Thanks,
- Tom

2011-06-15  Tom de Vries  <tom@codesourcery.com>

	PR target/45098
	* tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Disallow
	NULL pointer for pointer arithmetic.

[-- Attachment #2: 14_pr45098-null.patch --]
[-- Type: text/x-patch, Size: 998 bytes --]

diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy)
--- gcc/tree-ssa-loop-niter.c (working copy)
+++ gcc/tree-ssa-loop-niter.c (working copy)
@@ -2875,6 +2875,16 @@
   low = lower_bound_in_type (type, type);
   high = upper_bound_in_type (type, type);
 
+  /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
+     produce a NULL pointer.  The contrary would mean NULL points to an object,
+     while NULL is supposed to compare unequal with the address of all objects.
+     Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
+     NULL pointer since that would mean wrapping, which we assume here not to
+     happen.  So, we can exclude NULL from the valid range of pointer
+     arithmetic.  */
+  if (ptrdiff_type_node != NULL_TREE && int_cst_value (low) == 0)
+    low = fold_build2 (PLUS_EXPR, TREE_TYPE (low), low, step);
+
   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
 }
 

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 340 bytes --]

On 06/16/2011 08:39 AM, Tom de Vries wrote:
> I will sent the adapted test cases in a separate email.

Update 2 test cases to be more strict, and more like the original example.

Thanks,
- Tom

2011-06-15  Tom de Vries  <tom@codesourcery.com>

	PR target/45098
	* gcc.target/arm/ivopts-3.c: Update test.
	* gcc.target/arm/ivopts-5.c: Same.

[-- Attachment #2: 15_pr45098-null.test.patch --]
[-- Type: text/x-patch, Size: 954 bytes --]

diff -u gcc/testsuite/gcc.target/arm/ivopts-3.c (revision 0) gcc/testsuite/gcc.target/arm/ivopts-3.c (revision 0)
--- gcc/testsuite/gcc.target/arm/ivopts-3.c (revision 0)
+++ gcc/testsuite/gcc.target/arm/ivopts-3.c (revision 0)
@@ -8,14 +8,8 @@
 {
   int sum = 0;
   unsigned int x;
-  x = 0;
-  while (1)
-    {
-      sum += foo2 (&array[x]);
-      if (!(x < n))
-        break;
-      x++;
-    }
+  for (x = 0; x < n; ++x)
+    sum += foo2 (&array[x]);
   return sum;
 }
 
diff -u gcc/testsuite/gcc.target/arm/ivopts-5.c (revision 0) gcc/testsuite/gcc.target/arm/ivopts-5.c (revision 0)
--- gcc/testsuite/gcc.target/arm/ivopts-5.c (revision 0)
+++ gcc/testsuite/gcc.target/arm/ivopts-5.c (revision 0)
@@ -8,14 +8,8 @@
 {
   int sum = 0;
   unsigned int x;
-  x = 0;
-  while (1)
-    {
-      sum += foo (&array[x]);
-      if (!(x < n))
-        break;
-      x++;
-    }
+  for (x = 0; x < n; ++x)
+    sum += foo (&array[x]);
   return sum;
 }
 

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

Hi,

> Consider the following example.
> 
> extern unsigned int foo (int*) __attribute__((pure));
> unsigned int
> tr (int array[], int n)
> {
>   unsigned int i;
>   unsigned int sum = 0;
>   for (i = 0; i < n; i++)
>     sum += foo (&array[i]);
>   return sum;
> }
> 
> For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith
> currently concludes that the range of valid &array[i] is &array[0x0] to
> &array[0x3fffffff], meaning 0x40000000 distinct values.
> This implies that i < n is executed at most 0x40000001 times, and i < n
> cannot be eliminated by an 32-bit iterator with step 4, since that one has
> only 0x40000000 distinct values.

this reasoning seems slightly inaccurate to me: the loop is typically translated
as

if (n > 0)
  {
    i = 0;
    start:
      sum += foo (&array[i]);
      i++;
      if (i < n)
        goto start;
  }

This means that if the array access is performed <= x times, then the exit condition
of the loop is tested <= x times (not counting the copied header).  This could be
exploited to fix the problem as well.

> The patch reasons that NULL cannot be used or produced by pointer
> arithmetic, and that we can exclude the possibility of the NULL pointer in the
> range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe],
> meaning 0x3fffffff distinct values.
> This implies that i < n is executed at most 0x40000000 times and i < n can be
> eliminated.

Sounds reasonable to me.

> The patch implements this new limitation by changing the (low, high, step)
> triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4)
> to (0x4, 0xffffffff, 0x4).

At least in principle, the variable could have initial value 0x1, so this is a bit
incorrect.  (alignment of the memory reference, 0xffffffff, 0x4) should work, though.

> I'm not too happy about the test for C-like language: ptrdiff_type_node !=
> NULL_TREE, but I'm not sure how else to test for this.

The middle-end operations in general follow the C semantics, unless explicitly
specified otherwise (e.g. language-specific alias analysis rules, ...).  So, I think
you can drop this test.

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2615 bytes --]

On 06/16/2011 09:24 AM, Zdenek Dvorak wrote:
> Hi,
> 
>> Consider the following example.
>>
>> extern unsigned int foo (int*) __attribute__((pure));
>> unsigned int
>> tr (int array[], int n)
>> {
>>   unsigned int i;
>>   unsigned int sum = 0;
>>   for (i = 0; i < n; i++)
>>     sum += foo (&array[i]);
>>   return sum;
>> }
>>
>> For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith
>> currently concludes that the range of valid &array[i] is &array[0x0] to
>> &array[0x3fffffff], meaning 0x40000000 distinct values.
>> This implies that i < n is executed at most 0x40000001 times, and i < n
>> cannot be eliminated by an 32-bit iterator with step 4, since that one has
>> only 0x40000000 distinct values.
> 
> this reasoning seems slightly inaccurate to me: the loop is typically translated
> as
> 
> if (n > 0)
>   {
>     i = 0;
>     start:
>       sum += foo (&array[i]);
>       i++;
>       if (i < n)
>         goto start;
>   }
> 
> This means that if the array access is performed <= x times, then the exit condition
> of the loop is tested <= x times (not counting the copied header).  This could be
> exploited to fix the problem as well.

Indeed, when the header is copied, the elimination is done.
But when optimizing for size (which is the case for this PR), the header is not
copied and the control flow structure at ivopts is the same as at source level.

>> The patch reasons that NULL cannot be used or produced by pointer
>> arithmetic, and that we can exclude the possibility of the NULL pointer in the
>> range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe],
>> meaning 0x3fffffff distinct values.
>> This implies that i < n is executed at most 0x40000000 times and i < n can be
>> eliminated.
> 
> Sounds reasonable to me.
> 
>> The patch implements this new limitation by changing the (low, high, step)
>> triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4)
>> to (0x4, 0xffffffff, 0x4).
> 
> At least in principle, the variable could have initial value 0x1, so this is a bit
> incorrect.  (alignment of the memory reference, 0xffffffff, 0x4) should work, though.
> 

That's better indeed, thanks.

>> I'm not too happy about the test for C-like language: ptrdiff_type_node !=
>> NULL_TREE, but I'm not sure how else to test for this.
> 
> The middle-end operations in general follow the C semantics, unless explicitly
> specified otherwise (e.g. language-specific alias analysis rules, ...).  So, I think
> you can drop this test.
> 

Ok, dropped it.

Bootstrapped and reg-tested on x86_64.

Ok for trunk?

Thanks,
- Tom

[-- Attachment #2: 14_pr45098-null.patch --]
[-- Type: text/x-patch, Size: 981 bytes --]

diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy)
--- gcc/tree-ssa-loop-niter.c (working copy)
+++ gcc/tree-ssa-loop-niter.c (working copy)
@@ -2875,6 +2875,16 @@
   low = lower_bound_in_type (type, type);
   high = upper_bound_in_type (type, type);
 
+  /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
+     produce a NULL pointer.  The contrary would mean NULL points to an object,
+     while NULL is supposed to compare unequal with the address of all objects.
+     Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
+     NULL pointer since that would mean wrapping, which we assume here not to
+     happen.  So, we can exclude NULL from the valid range of pointer
+     arithmetic.  */
+  if (int_cst_value (low) == 0)
+    low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
+
   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
 }
 

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

Hi,

> diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy)
> --- gcc/tree-ssa-loop-niter.c (working copy)
> +++ gcc/tree-ssa-loop-niter.c (working copy)
> @@ -2875,6 +2875,16 @@
>    low = lower_bound_in_type (type, type);
>    high = upper_bound_in_type (type, type);
>  
> +  /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
> +     produce a NULL pointer.  The contrary would mean NULL points to an object,
> +     while NULL is supposed to compare unequal with the address of all objects.
> +     Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
> +     NULL pointer since that would mean wrapping, which we assume here not to
> +     happen.  So, we can exclude NULL from the valid range of pointer
> +     arithmetic.  */
> +  if (int_cst_value (low) == 0)
> +    low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
> +
>    record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
>  }

OK,

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Richard Guenther]

On Thu, Jun 16, 2011 at 5:24 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy)
>> --- gcc/tree-ssa-loop-niter.c (working copy)
>> +++ gcc/tree-ssa-loop-niter.c (working copy)
>> @@ -2875,6 +2875,16 @@
>>    low = lower_bound_in_type (type, type);
>>    high = upper_bound_in_type (type, type);
>>
>> +  /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
>> +     produce a NULL pointer.  The contrary would mean NULL points to an object,
>> +     while NULL is supposed to compare unequal with the address of all objects.
>> +     Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
>> +     NULL pointer since that would mean wrapping, which we assume here not to
>> +     happen.  So, we can exclude NULL from the valid range of pointer
>> +     arithmetic.  */
>> +  if (int_cst_value (low) == 0)
>> +    low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
>> +
>>    record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
>>  }
>
> OK,

I think this is only valid for !flag_delete_null_pointer_checks, on
architectures where that isn't the default we have to assume that
NULL may point to an object.

Richard.

> Zdenek
>

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

> >> diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy)
> >> --- gcc/tree-ssa-loop-niter.c (working copy)
> >> +++ gcc/tree-ssa-loop-niter.c (working copy)
> >> @@ -2875,6 +2875,16 @@
> >>    low = lower_bound_in_type (type, type);
> >>    high = upper_bound_in_type (type, type);
> >>
> >> +  /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
> >> +     produce a NULL pointer.  The contrary would mean NULL points to an object,
> >> +     while NULL is supposed to compare unequal with the address of all objects.
> >> +     Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
> >> +     NULL pointer since that would mean wrapping, which we assume here not to
> >> +     happen.  So, we can exclude NULL from the valid range of pointer
> >> +     arithmetic.  */
> >> +  if (int_cst_value (low) == 0)
> >> +    low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
> >> +
> >>    record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
> >>  }
> >
> > OK,
> 
> I think this is only valid for !flag_delete_null_pointer_checks, on
> architectures where that isn't the default we have to assume that
> NULL may point to an object.

agreed.  Thanks for the correction.

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Tom de Vries]

On 06/16/2011 05:42 PM, Zdenek Dvorak wrote:
>>>> diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy)
>>>> --- gcc/tree-ssa-loop-niter.c (working copy)
>>>> +++ gcc/tree-ssa-loop-niter.c (working copy)
>>>> @@ -2875,6 +2875,16 @@
>>>>    low = lower_bound_in_type (type, type);
>>>>    high = upper_bound_in_type (type, type);
>>>>
>>>> +  /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
>>>> +     produce a NULL pointer.  The contrary would mean NULL points to an object,
>>>> +     while NULL is supposed to compare unequal with the address of all objects.
>>>> +     Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
>>>> +     NULL pointer since that would mean wrapping, which we assume here not to
>>>> +     happen.  So, we can exclude NULL from the valid range of pointer
>>>> +     arithmetic.  */
>>>> +  if (int_cst_value (low) == 0)
>>>> +    low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
>>>> +
>>>>    record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
>>>>  }
>>>
>>> OK,
>>
>> I think this is only valid for !flag_delete_null_pointer_checks, on
>> architectures where that isn't the default we have to assume that
>> NULL may point to an object.
> 
> agreed.  Thanks for the correction.
> 
> Zdenek

committed with test for flag_delete_null_pointer_checks added.

Thanks,
- Tom

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 06/16/11 00:39, Tom de Vries wrote:
> Hi,
> 
> Consider the following example.
> 
> extern unsigned int foo (int*) __attribute__((pure));
> unsigned int
> tr (int array[], int n)
> {
>   unsigned int i;
>   unsigned int sum = 0;
>   for (i = 0; i < n; i++)
>     sum += foo (&array[i]);
>   return sum;
> }
> 
> For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith
> currently concludes that the range of valid &array[i] is &array[0x0] to
> &array[0x3fffffff], meaning 0x40000000 distinct values.
> This implies that i < n is executed at most 0x40000001 times, and i < n
> cannot be eliminated by an 32-bit iterator with step 4, since that one has
> only 0x40000000 distinct values.
> 
> The patch reasons that NULL cannot be used or produced by pointer
> arithmetic, and that we can exclude the possibility of the NULL pointer in the
> range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe],
> meaning 0x3fffffff distinct values.
> This implies that i < n is executed at most 0x40000000 times and i < n can be
> eliminated.
> 
> The patch implements this new limitation by changing the (low, high, step)
> triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4)
> to (0x4, 0xffffffff, 0x4).
> 
> I'm not too happy about the test for C-like language: ptrdiff_type_node !=
> NULL_TREE, but I'm not sure how else to test for this.
> 
> Bootstrapped and reg-tested on x86_64.
> 
> I will sent the adapted test cases in a separate email.
Interesting.  I'd never thought about the generation/use angle to prove
a pointer was non-null.  ISTM we could use that same logic to infer that
more pointers are non-null in extract_range_from_binary_expr.

Interested in tackling that improvement, obviously as an independent patch?

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJN+n0cAAoJEBRtltQi2kC7aRYH/1jyc0xmWEnzkxaMxdn9t5+p
asGN79nl8BSPifZapn2R7brEt9uQQNT6oAe/4wlCr0qf5f0FwMUV8U2QH8uMuez3
gqO+PuqcF6dSxR5+qskgljSjjLndxdFuaiN1Lb95jR9Wg3l/Nv6NGpjdgAaWHiVk
cmiuwAkVGSB46TGMMVnumFWTbXbXAK7udSk1PBDUZlY8Da+B9M2eGX9MuaPBNWvd
YSHRpkVVFAlyJIpwdtAojE6T2korZQyHAmYqiuArBPYxAN7cLuV8Gl4AagzyHcVz
Epkg7e0ayS1PnnQuH1JpAKGKH1DSlOmqo69JJpuL/kyaBh5lo4wu32RWHm/aGkY=
=fESM
-----END PGP SIGNATURE-----

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Tom de Vries]

On 06/17/2011 12:01 AM, Jeff Law wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> On 06/16/11 00:39, Tom de Vries wrote:
>> Hi,
>>
>> Consider the following example.
>>
>> extern unsigned int foo (int*) __attribute__((pure));
>> unsigned int
>> tr (int array[], int n)
>> {
>>   unsigned int i;
>>   unsigned int sum = 0;
>>   for (i = 0; i < n; i++)
>>     sum += foo (&array[i]);
>>   return sum;
>> }
>>
>> For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith
>> currently concludes that the range of valid &array[i] is &array[0x0] to
>> &array[0x3fffffff], meaning 0x40000000 distinct values.
>> This implies that i < n is executed at most 0x40000001 times, and i < n
>> cannot be eliminated by an 32-bit iterator with step 4, since that one has
>> only 0x40000000 distinct values.
>>
>> The patch reasons that NULL cannot be used or produced by pointer
>> arithmetic, and that we can exclude the possibility of the NULL pointer in the
>> range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe],
>> meaning 0x3fffffff distinct values.
>> This implies that i < n is executed at most 0x40000000 times and i < n can be
>> eliminated.
>>
>> The patch implements this new limitation by changing the (low, high, step)
>> triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4)
>> to (0x4, 0xffffffff, 0x4).
>>
>> I'm not too happy about the test for C-like language: ptrdiff_type_node !=
>> NULL_TREE, but I'm not sure how else to test for this.
>>
>> Bootstrapped and reg-tested on x86_64.
>>
>> I will sent the adapted test cases in a separate email.

> Interesting.  I'd never thought about the generation/use angle to prove
> a pointer was non-null.  ISTM we could use that same logic to infer that
> more pointers are non-null in extract_range_from_binary_expr.
> 
> Interested in tackling that improvement, obviously as an independent patch?
> 

I'm not familiar with vrp code, but.. something like this?

Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 173703)
+++ tree-vrp.c	(working copy)
@@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
 	{
 	  /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))
+	    {
+	      set_value_range_to_nonnull (vr, expr_type);
+	      set_value_range_to_nonnull (&vr0, expr_type);
+	    }
+	  else if (range_is_nonnull (&vr0) || range_is_nonnull (&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);

Thanks,
- Tom

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Richard Guenther]

On Fri, Jun 17, 2011 at 12:40 PM, Tom de Vries <vries@codesourcery.com> wrote:
> On 06/17/2011 12:01 AM, Jeff Law wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> On 06/16/11 00:39, Tom de Vries wrote:
>>> Hi,
>>>
>>> Consider the following example.
>>>
>>> extern unsigned int foo (int*) __attribute__((pure));
>>> unsigned int
>>> tr (int array[], int n)
>>> {
>>>   unsigned int i;
>>>   unsigned int sum = 0;
>>>   for (i = 0; i < n; i++)
>>>     sum += foo (&array[i]);
>>>   return sum;
>>> }
>>>
>>> For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith
>>> currently concludes that the range of valid &array[i] is &array[0x0] to
>>> &array[0x3fffffff], meaning 0x40000000 distinct values.
>>> This implies that i < n is executed at most 0x40000001 times, and i < n
>>> cannot be eliminated by an 32-bit iterator with step 4, since that one has
>>> only 0x40000000 distinct values.
>>>
>>> The patch reasons that NULL cannot be used or produced by pointer
>>> arithmetic, and that we can exclude the possibility of the NULL pointer in the
>>> range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe],
>>> meaning 0x3fffffff distinct values.
>>> This implies that i < n is executed at most 0x40000000 times and i < n can be
>>> eliminated.
>>>
>>> The patch implements this new limitation by changing the (low, high, step)
>>> triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4)
>>> to (0x4, 0xffffffff, 0x4).
>>>
>>> I'm not too happy about the test for C-like language: ptrdiff_type_node !=
>>> NULL_TREE, but I'm not sure how else to test for this.
>>>
>>> Bootstrapped and reg-tested on x86_64.
>>>
>>> I will sent the adapted test cases in a separate email.
>
>> Interesting.  I'd never thought about the generation/use angle to prove
>> a pointer was non-null.  ISTM we could use that same logic to infer that
>> more pointers are non-null in extract_range_from_binary_expr.
>>
>> Interested in tackling that improvement, obviously as an independent patch?
>>
>
> I'm not familiar with vrp code, but.. something like this?
>
> Index: tree-vrp.c
> ===================================================================
> --- tree-vrp.c  (revision 173703)
> +++ tree-vrp.c  (working copy)
> @@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
>        {
>          /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))

the latter would always return true

Btw, I guess you'll "miscompile" a load of code that is strictly
undefined.  So I'm not sure we want to do this against our users ...

Oh, and of course it's even wrong.  I thing it needs &&
!range_includes_zero (&vr1) (which we probably don't have).  The
offset may be 0 and NULL + 0
is still NULL.

Richard.

> +           {
> +             set_value_range_to_nonnull (vr, expr_type);
> +             set_value_range_to_nonnull (&vr0, expr_type);
> +           }
> +         else if (range_is_nonnull (&vr0) || range_is_nonnull (&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);
>
> Thanks,
> - Tom
>

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

> >> Interesting.  I'd never thought about the generation/use angle to prove
> >> a pointer was non-null.  ISTM we could use that same logic to infer that
> >> more pointers are non-null in extract_range_from_binary_expr.
> >>
> >> Interested in tackling that improvement, obviously as an independent patch?
> >>
> >
> > I'm not familiar with vrp code, but.. something like this?
> >
> > Index: tree-vrp.c
> > ===================================================================
> > --- tree-vrp.c  (revision 173703)
> > +++ tree-vrp.c  (working copy)
> > @@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
> >        {
> >          /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))
> 
> the latter would always return true
> 
> Btw, I guess you'll "miscompile" a load of code that is strictly
> undefined.  So I'm not sure we want to do this against our users ...

Probably not, at least unless the user explicitly asks for it -- for example,
we could have -fdelete-null-pointer-checks=2.  In fact, it might be a good idea
to implement this flag anyway, since some current uses of flag_delete_null_pointer_checks
can lead to "miscompilations" when user makes an error in their code and would
probably appreciate more having their program crash.

> Oh, and of course it's even wrong.  I thing it needs &&
> !range_includes_zero (&vr1) (which we probably don't have).  The
> offset may be 0 and NULL + 0
> is still NULL.

actually, the result of NULL + 0 is undefined (pointer arithmetics is only defined
for pointers to actual objects, and NULL cannot point to one).

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Richard Guenther]

2011/6/17 Zdenek Dvorak <rakdver@kam.mff.cuni.cz>:
>> >> Interesting.  I'd never thought about the generation/use angle to prove
>> >> a pointer was non-null.  ISTM we could use that same logic to infer that
>> >> more pointers are non-null in extract_range_from_binary_expr.
>> >>
>> >> Interested in tackling that improvement, obviously as an independent patch?
>> >>
>> >
>> > I'm not familiar with vrp code, but.. something like this?
>> >
>> > Index: tree-vrp.c
>> > ===================================================================
>> > --- tree-vrp.c  (revision 173703)
>> > +++ tree-vrp.c  (working copy)
>> > @@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
>> >        {
>> >          /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))
>>
>> the latter would always return true
>>
>> Btw, I guess you'll "miscompile" a load of code that is strictly
>> undefined.  So I'm not sure we want to do this against our users ...
>
> Probably not, at least unless the user explicitly asks for it -- for example,
> we could have -fdelete-null-pointer-checks=2.  In fact, it might be a good idea
> to implement this flag anyway, since some current uses of flag_delete_null_pointer_checks
> can lead to "miscompilations" when user makes an error in their code and would
> probably appreciate more having their program crash.
>
>> Oh, and of course it's even wrong.  I thing it needs &&
>> !range_includes_zero (&vr1) (which we probably don't have).  The
>> offset may be 0 and NULL + 0
>> is still NULL.
>
> actually, the result of NULL + 0 is undefined (pointer arithmetics is only defined
> for pointers to actual objects, and NULL cannot point to one).

It's maybe undefined in C, but is it undefined in the middle-end?  Thus,
are you sure we never generate it from (void *)((uintptr_t)p + obfuscated_0)?
I'm sure we simply fold that to p + obfuscated_0.

Richard.

> Zdenek
>

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

Hi,

> >> > Index: tree-vrp.c
> >> > ===================================================================
> >> > --- tree-vrp.c  (revision 173703)
> >> > +++ tree-vrp.c  (working copy)
> >> > @@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
> >> >        {
> >> >          /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))
> >>
> >> the latter would always return true
> >>
> >> Btw, I guess you'll "miscompile" a load of code that is strictly
> >> undefined.  So I'm not sure we want to do this against our users ...
> >
> > Probably not, at least unless the user explicitly asks for it -- for example,
> > we could have -fdelete-null-pointer-checks=2.  In fact, it might be a good idea
> > to implement this flag anyway, since some current uses of flag_delete_null_pointer_checks
> > can lead to "miscompilations" when user makes an error in their code and would
> > probably appreciate more having their program crash.
> >
> >> Oh, and of course it's even wrong.  I thing it needs &&
> >> !range_includes_zero (&vr1) (which we probably don't have).  The
> >> offset may be 0 and NULL + 0
> >> is still NULL.
> >
> > actually, the result of NULL + 0 is undefined (pointer arithmetics is only defined
> > for pointers to actual objects, and NULL cannot point to one).
> 
> It's maybe undefined in C, but is it undefined in the middle-end?  Thus,
> are you sure we never generate it from (void *)((uintptr_t)p + obfuscated_0)?
> I'm sure we simply fold that to p + obfuscated_0.

if we do, we definitely should not -- the only point of such a construction is
to bypass the pointer arithmetics restrictions,

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Richard Guenther]

2011/6/17 Zdenek Dvorak <rakdver@kam.mff.cuni.cz>:
> Hi,
>
>> >> > Index: tree-vrp.c
>> >> > ===================================================================
>> >> > --- tree-vrp.c  (revision 173703)
>> >> > +++ tree-vrp.c  (working copy)
>> >> > @@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
>> >> >        {
>> >> >          /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))
>> >>
>> >> the latter would always return true
>> >>
>> >> Btw, I guess you'll "miscompile" a load of code that is strictly
>> >> undefined.  So I'm not sure we want to do this against our users ...
>> >
>> > Probably not, at least unless the user explicitly asks for it -- for example,
>> > we could have -fdelete-null-pointer-checks=2.  In fact, it might be a good idea
>> > to implement this flag anyway, since some current uses of flag_delete_null_pointer_checks
>> > can lead to "miscompilations" when user makes an error in their code and would
>> > probably appreciate more having their program crash.
>> >
>> >> Oh, and of course it's even wrong.  I thing it needs &&
>> >> !range_includes_zero (&vr1) (which we probably don't have).  The
>> >> offset may be 0 and NULL + 0
>> >> is still NULL.
>> >
>> > actually, the result of NULL + 0 is undefined (pointer arithmetics is only defined
>> > for pointers to actual objects, and NULL cannot point to one).
>>
>> It's maybe undefined in C, but is it undefined in the middle-end?  Thus,
>> are you sure we never generate it from (void *)((uintptr_t)p + obfuscated_0)?
>> I'm sure we simply fold that to p + obfuscated_0.
>
> if we do, we definitely should not -- the only point of such a construction is
> to bypass the pointer arithmetics restrictions,

Ok, we don't.  Where does the C standard say that NULL + 0 is undefined?

Richard.

> Zdenek
>

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

Hi,

> >> >> > Index: tree-vrp.c
> >> >> > ===================================================================
> >> >> > --- tree-vrp.c  (revision 173703)
> >> >> > +++ tree-vrp.c  (working copy)
> >> >> > @@ -2273,7 +2273,12 @@ extract_range_from_binary_expr (value_ra
> >> >> >        {
> >> >> >          /* 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 (flag_delete_null_pointer_checks && nowrap_type_p (expr_type))
> >> >>
> >> >> the latter would always return true
> >> >>
> >> >> Btw, I guess you'll "miscompile" a load of code that is strictly
> >> >> undefined.  So I'm not sure we want to do this against our users ...
> >> >
> >> > Probably not, at least unless the user explicitly asks for it -- for example,
> >> > we could have -fdelete-null-pointer-checks=2.  In fact, it might be a good idea
> >> > to implement this flag anyway, since some current uses of flag_delete_null_pointer_checks
> >> > can lead to "miscompilations" when user makes an error in their code and would
> >> > probably appreciate more having their program crash.
> >> >
> >> >> Oh, and of course it's even wrong.  I thing it needs &&
> >> >> !range_includes_zero (&vr1) (which we probably don't have).  The
> >> >> offset may be 0 and NULL + 0
> >> >> is still NULL.
> >> >
> >> > actually, the result of NULL + 0 is undefined (pointer arithmetics is only defined
> >> > for pointers to actual objects, and NULL cannot point to one).
> >>
> >> It's maybe undefined in C, but is it undefined in the middle-end?  Thus,
> >> are you sure we never generate it from (void *)((uintptr_t)p + obfuscated_0)?
> >> I'm sure we simply fold that to p + obfuscated_0.
> >
> > if we do, we definitely should not -- the only point of such a construction is
> > to bypass the pointer arithmetics restrictions,
> 
> Ok, we don't.  Where does the C standard say that NULL + 0 is undefined?

I don't think it explicitly states that it is undefined.  But 6.5.6 #7 and #8 only
give semantics for pointers to objects,

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 06/17/11 08:12, Zdenek Dvorak wrote:

>>> if we do, we definitely should not -- the only point of such a construction is
>>> to bypass the pointer arithmetics restrictions,
>>
>> Ok, we don't.  Where does the C standard say that NULL + 0 is undefined?
> 
> I don't think it explicitly states that it is undefined.  But 6.5.6 #7 and #8 only
> give semantics for pointers to objects,
Right.  I think we need to review the standard closely, but IIRC
pointers are allowed to be NULL, point into an object or point to one
element beyond an object.

If that's correct P+C could only result in a NULL value if P was one
element beyond the end of an object and C happened to be the exact magic
value to wrap P to zero.  I have a hard time seeing how code could which
did that (and relied upon it) could ever be standard conforming.

Closely related, given P+C where the result is a pointer ought to tells
us that P is non-null since the only way it could be null would be if C
was the exact magic constant to make the result point to a valid object.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJN+5ZSAAoJEBRtltQi2kC7H34H/RG+9VrV6RqeolgSIqjyLsUf
WbJwl2AWo3xIMt/8OKpWG5zzhgJk67tW+PpSHhzs615kjRPryOiiNq+GBIelteKT
ho3mgbBeU5qJsPLU6j2feBR4+OEdo/oJZxHm/m8zUwWcGuZtazNGtoiuq7rlNr52
PDl7DM7ZWK731nFZfKYPq/fYMgNxWhxTBo9ucH3s9yXKJ6LYbUGHpKNyP14nB3n3
bJhdPF8A365uLYz5xCmP0QOKInbzNclN+gbTVZXc+NxtOYNUM16NalsxWhHSALCB
U0S9hpDMDznWWEwPDNdNN2oRphSGmIB0oYxeuaga5RgviNiPNVgEzANkGIv7OEo=
=z8kH
-----END PGP SIGNATURE-----

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Richard Guenther]

2011/6/17 Jeff Law <law@redhat.com>:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 06/17/11 08:12, Zdenek Dvorak wrote:
>
>>>> if we do, we definitely should not -- the only point of such a construction is
>>>> to bypass the pointer arithmetics restrictions,
>>>
>>> Ok, we don't.  Where does the C standard say that NULL + 0 is undefined?
>>
>> I don't think it explicitly states that it is undefined.  But 6.5.6 #7 and #8 only
>> give semantics for pointers to objects,
> Right.  I think we need to review the standard closely, but IIRC
> pointers are allowed to be NULL, point into an object or point to one
> element beyond an object.
>
> If that's correct P+C could only result in a NULL value if P was one
> element beyond the end of an object and C happened to be the exact magic
> value to wrap P to zero.  I have a hard time seeing how code could which
> did that (and relied upon it) could ever be standard conforming.
>
> Closely related, given P+C where the result is a pointer ought to tells
> us that P is non-null since the only way it could be null would be if C
> was the exact magic constant to make the result point to a valid object.

So you propose we compile the following to an abort()?

int __attribute__((noinline)) foo (void *p, int i)
{
  return p + i != NULL;
}
int main()
{
  if (foo(NULL, 0))
    abort ();
  return 0;
}

?  Thus, would it be ok to fold ptr + offset ==/!= NULL to false/true?

I don't think we should move this kind of undefinedness from C to
the GIMPLE semantics.  What do other languages allow that
we have to support (what did K&R C specify?).

Richard.

> Jeff
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJN+5ZSAAoJEBRtltQi2kC7H34H/RG+9VrV6RqeolgSIqjyLsUf
> WbJwl2AWo3xIMt/8OKpWG5zzhgJk67tW+PpSHhzs615kjRPryOiiNq+GBIelteKT
> ho3mgbBeU5qJsPLU6j2feBR4+OEdo/oJZxHm/m8zUwWcGuZtazNGtoiuq7rlNr52
> PDl7DM7ZWK731nFZfKYPq/fYMgNxWhxTBo9ucH3s9yXKJ6LYbUGHpKNyP14nB3n3
> bJhdPF8A365uLYz5xCmP0QOKInbzNclN+gbTVZXc+NxtOYNUM16NalsxWhHSALCB
> U0S9hpDMDznWWEwPDNdNN2oRphSGmIB0oYxeuaga5RgviNiPNVgEzANkGIv7OEo=
> =z8kH
> -----END PGP SIGNATURE-----
>

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

> I don't think we should move this kind of undefinedness from C to
> the GIMPLE semantics.  What do other languages allow that
> we have to support (what did K&R C specify?).

I don't think there is a formal specification of K&R C, just the (somewhat
informal) book.  On topic of pointer arithmetics, the case of addition
is not completely clear.  It does say that you can only subtract pointers
to members of the same array, though.

On topic of addition of integer to a pointer, it says that "The construction
p + n means the address of the n-th object beyond the one p currently points to. This is true
regardless of the kind of object p points to; n is scaled according to the size of the objects p
points to, which is determined by the declaration of p."

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Zdenek Dvorak]

> > I don't think we should move this kind of undefinedness from C to
> > the GIMPLE semantics.  What do other languages allow that
> > we have to support (what did K&R C specify?).
> 
> I don't think there is a formal specification of K&R C, just the (somewhat
> informal) book.  On topic of pointer arithmetics, the case of addition
> is not completely clear.  It does say that you can only subtract pointers
> to members of the same array, though.
> 
> On topic of addition of integer to a pointer, it says that "The construction
> p + n means the address of the n-th object beyond the one p currently points to. This is true
> regardless of the kind of object p points to; n is scaled according to the size of the objects p
> points to, which is determined by the declaration of p."

Anyway, I don't think that this should be a matter of lawyer scrutiny of the specifications;
rather, we should consider whether there is a situation where a user could reasonably expect
NULL + 0 to be valid.  In the example by Richard,

int __attribute__((noinline)) foo (void *p, int i)
{
  return p + i != NULL;
}

I think it would be hard to argue that this construction is natural.

Zdenek

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Richard Guenther]

On Mon, Jun 20, 2011 at 2:25 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
>> > I don't think we should move this kind of undefinedness from C to
>> > the GIMPLE semantics.  What do other languages allow that
>> > we have to support (what did K&R C specify?).
>>
>> I don't think there is a formal specification of K&R C, just the (somewhat
>> informal) book.  On topic of pointer arithmetics, the case of addition
>> is not completely clear.  It does say that you can only subtract pointers
>> to members of the same array, though.
>>
>> On topic of addition of integer to a pointer, it says that "The construction
>> p + n means the address of the n-th object beyond the one p currently points to. This is true
>> regardless of the kind of object p points to; n is scaled according to the size of the objects p
>> points to, which is determined by the declaration of p."
>
> Anyway, I don't think that this should be a matter of lawyer scrutiny of the specifications;
> rather, we should consider whether there is a situation where a user could reasonably expect
> NULL + 0 to be valid.  In the example by Richard,
>
> int __attribute__((noinline)) foo (void *p, int i)
> {
>  return p + i != NULL;
> }
>
> I think it would be hard to argue that this construction is natural.

Nor does it feel natural that 'p' is different from 'p + 0'.

Richard.

> Zdenek
>

Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Michael Matz]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1359 bytes --]

Hi,

On Mon, 20 Jun 2011, Richard Guenther wrote:

> > of the specifications; rather, we should consider whether there is a 
> > situation where a user could reasonably expect NULL + 0 to be valid. 
> >  In the example by Richard,
> >
> > int __attribute__((noinline)) foo (void *p, int i)
> > {
> >  return p + i != NULL;
> > }
> >
> > I think it would be hard to argue that this construction is natural.
> 
> Nor does it feel natural that 'p' is different from 'p + 0'.

Right.  If we would include such reasoning in GIMPLE, we already could 
infer simply from the presence of any POINTER_PLUS_EXPR that the pointer 
operand is != NULL (which means != zero-bit-pattern in our case) in the 
control region containing it.

This might be tempting, but it would be quite confusing, and I'm not sure 
at all that we should include such reasoning for an IR that is supposed to 
be able to implement all languages, which in my book would include 
languages that simply define pointers as addresses in a wrapping space.

Hence, if the language in question does guarantee certain specifics (here 
non-null of p in 'p + i'), it should explicitely say so via assert_expr.  
Possibly this doesn't work currently that well, because we recompute and 
throw away assert_exprs sometimes, but I argue that we should work towards 
making this possible.


Ciao,
Michael.