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