[PATCH PR45098] Disallow NULL pointer in pointer arithmetic

Tom de Vries vries@codesourcery.com
Fri Jun 17 10:44:00 GMT 2011


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



More information about the Gcc-patches mailing list