[PR45098] Disallow NULL pointer in pointer arithmetic

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

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

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
>

> >> 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

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