On Fri, Jun 17, 2011 at 12:40 PM, Tom de Vries <vr...@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
>
