| Message ID | 4DFB2F3A.3040706@codesourcery.com |
|---|---|
| State | New |
| Headers | show |
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 >
> >> 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
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 >
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
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 >
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
-----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-----
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----- >
> 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
> > 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
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 >
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.
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);