Message ID | 4D6B6DB9.7050302@codesourcery.com |
---|---|
State | New |
Headers | show |
On 02/28/2011 10:41 AM, Tom de Vries wrote: > The difficulty is that this replacement is only valid under the > guarantee that base + n does not overflow. I think this should be done unconditionally under -funsafe-loop-optimizations. Look in the code for examples of how to add warnings, it should be something like: bool last_iter_may_overflow; if (TYPE_OVERFLOW_WRAPS (...)) last_iter_may_overflow = false; else { last_iter_may_overflow = !flag_unsafe_loop_optimizations; if (warn_unsafe_loop_optimizations) { if (flag_unsafe_loop_optimizations) warning ("assuming ... does not overflow"); else warning ("not optimizing ... because ... could overflow"); } } if (last_iter_may_overflow && stmt_after_increment (loop, cand, use->stmt)) Looks like good work, thanks! Paolo
Hi, > 23-02-2011 Tom de Vries <tom@codesourcery.com> > > gcc/ > * tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix boundary checks. > * testsuite/gcc.dg/tree-ssa/ivopts-max.c: New test. > * testsuite/gcc.dg/tree-ssa/ivopts-max-2.c: New test. > * testsuite/gcc.dg/tree-ssa/ivopts-max-3.c: New test. > diff -u gcc/tree-ssa-loop-ivopts.c gcc/tree-ssa-loop-ivopts.c > --- gcc/tree-ssa-loop-ivopts.c (revision 162585) > +++ gcc/tree-ssa-loop-ivopts.c (working copy) > @@ -4079,8 +4079,12 @@ > /* If the number of iterations is constant, compare against it directly. */ > if (TREE_CODE (nit) == INTEGER_CST) > { > - /* See cand_value_at. */ > - if (stmt_after_increment (loop, cand, use->stmt)) > + /* An iv with TYPE_PRECISION 32 has 2^32 distinct values, and an iv_period > + of 2^32 - 1. Such an iv can handle at most a nit of 2^32 - 1. If the > + exit test is after the increment, the bound calculation will overflow. > + If overflow wraps, that's not a problem. */ > + if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) > + && stmt_after_increment (loop, cand, use->stmt)) > { > if (!tree_int_cst_lt (nit, period)) > return false; > @@ -4100,7 +4104,9 @@ > double_int period_value, max_niter; > > max_niter = desc->max; > - if (stmt_after_increment (loop, cand, use->stmt)) > + /* See comment at TREE_CODE (nit) == INTEGER_CST. */ > + if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) > + && stmt_after_increment (loop, cand, use->stmt)) > max_niter = double_int_add (max_niter, double_int_one); > period_value = tree_to_double_int (period); > if (double_int_ucmp (max_niter, period_value) > 0) This looks strange. If indeed there is an off-by-one error here, it should not depend on whether TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) is true or not. The only candidates that satisfy !TYPE_OVERFLOW_WRAPS are those for that we are certain that their computations cannot overflow (e.g., if they are the original induction variables of the loop computed in a !TYPE_OVERFLOW_WRAPS type). > 23-02-2011 Tom de Vries <tom@codesourcery.com> > > gcc/ > * tree-ssa-loop-ivopts.c (struct cost_pair): Add comp field. > (set_use_iv_cost): Add comp parameter. > (set_use_iv_cost): Use comp parameter to init comp field. > (determine_use_iv_cost_generic, determine_use_iv_cost_address) > (determine_use_iv_cost_condition): Add comp argument to set_use_iv_cost > call. > (may_eliminate_iv): Add comp parameter and set. > (determine_use_iv_cost_condition): Add comp argument to may_eliminate_iv > call. > (determine_use_iv_cost_condition): Reset comp if too expensive. > (rewrite_use_compare): Use compare from comp field of cp. This is ok. > 23-02-2011 Tom de Vries <tom@codesourcery.com> > > gcc/ > * tree-ssa-loop-ivopts.c (fold_build_plus): New function factored out of > add_autoinc_candidates. > (add_autoinc_candidates): Use fold_build_plus. OK. > 23-02-2011 Tom de Vries <tom@codesourcery.com> > > gcc/ > * tree-ssa-loop-ivopts.c (niter_for_exit): Return COND_EXPR if > !integer_zerop (desc->may_be_zero). > (cand_valid_pointer_at_use_p, get_lt_bound, iv_elimination_compare_lt): > New function. > (may_eliminate_iv): Use iv_elimination_compare_lt. > +/* Tries to determine if the iterator CAND is a valid pointer at USE. */ For consistency with the rest of the comments in ivopts, please use "candidate" instead of "iterator" in similar comments. > +static bool > +cand_valid_pointer_at_use_p (struct ivopts_data *data, struct iv_cand *cand, > + struct iv_use *use) > +{ > + struct iv_use *cand_iv_use = iv_use (data, cand->iv->use_id); This is rather strange. cand->iv->use_id is never being set (all candidates are allocated through add_candidate_1, which creates a new iv for them from the given base and step). So this just chooses a random use (the first one appearing in the loop), regrardless whether it has anything to do with cand or not. Zdenek
On Mon, Feb 28, 2011 at 11:46 AM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote: > Hi, > >> 23-02-2011 Tom de Vries <tom@codesourcery.com> >> >> gcc/ >> * tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix boundary checks. >> * testsuite/gcc.dg/tree-ssa/ivopts-max.c: New test. >> * testsuite/gcc.dg/tree-ssa/ivopts-max-2.c: New test. >> * testsuite/gcc.dg/tree-ssa/ivopts-max-3.c: New test. > >> diff -u gcc/tree-ssa-loop-ivopts.c gcc/tree-ssa-loop-ivopts.c >> --- gcc/tree-ssa-loop-ivopts.c (revision 162585) >> +++ gcc/tree-ssa-loop-ivopts.c (working copy) >> @@ -4079,8 +4079,12 @@ >> /* If the number of iterations is constant, compare against it directly. */ >> if (TREE_CODE (nit) == INTEGER_CST) >> { >> - /* See cand_value_at. */ >> - if (stmt_after_increment (loop, cand, use->stmt)) >> + /* An iv with TYPE_PRECISION 32 has 2^32 distinct values, and an iv_period >> + of 2^32 - 1. Such an iv can handle at most a nit of 2^32 - 1. If the >> + exit test is after the increment, the bound calculation will overflow. >> + If overflow wraps, that's not a problem. */ >> + if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) >> + && stmt_after_increment (loop, cand, use->stmt)) >> { >> if (!tree_int_cst_lt (nit, period)) >> return false; >> @@ -4100,7 +4104,9 @@ >> double_int period_value, max_niter; >> >> max_niter = desc->max; >> - if (stmt_after_increment (loop, cand, use->stmt)) >> + /* See comment at TREE_CODE (nit) == INTEGER_CST. */ >> + if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) >> + && stmt_after_increment (loop, cand, use->stmt)) >> max_niter = double_int_add (max_niter, double_int_one); >> period_value = tree_to_double_int (period); >> if (double_int_ucmp (max_niter, period_value) > 0) > > This looks strange. If indeed there is an off-by-one error here, it should not depend > on whether TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) is true or not. The only > candidates that satisfy !TYPE_OVERFLOW_WRAPS are those for that we are certain that their > computations cannot overflow (e.g., if they are the original induction variables of the loop > computed in a !TYPE_OVERFLOW_WRAPS type). > >> 23-02-2011 Tom de Vries <tom@codesourcery.com> >> >> gcc/ >> * tree-ssa-loop-ivopts.c (struct cost_pair): Add comp field. >> (set_use_iv_cost): Add comp parameter. >> (set_use_iv_cost): Use comp parameter to init comp field. >> (determine_use_iv_cost_generic, determine_use_iv_cost_address) >> (determine_use_iv_cost_condition): Add comp argument to set_use_iv_cost >> call. >> (may_eliminate_iv): Add comp parameter and set. >> (determine_use_iv_cost_condition): Add comp argument to may_eliminate_iv >> call. >> (determine_use_iv_cost_condition): Reset comp if too expensive. >> (rewrite_use_compare): Use compare from comp field of cp. > > This is ok. > >> 23-02-2011 Tom de Vries <tom@codesourcery.com> >> >> gcc/ >> * tree-ssa-loop-ivopts.c (fold_build_plus): New function factored out of >> add_autoinc_candidates. >> (add_autoinc_candidates): Use fold_build_plus. > > OK. > >> 23-02-2011 Tom de Vries <tom@codesourcery.com> >> >> gcc/ >> * tree-ssa-loop-ivopts.c (niter_for_exit): Return COND_EXPR if >> !integer_zerop (desc->may_be_zero). >> (cand_valid_pointer_at_use_p, get_lt_bound, iv_elimination_compare_lt): >> New function. >> (may_eliminate_iv): Use iv_elimination_compare_lt. > >> +/* Tries to determine if the iterator CAND is a valid pointer at USE. */ > > For consistency with the rest of the comments in ivopts, please use "candidate" > instead of "iterator" in similar comments. > >> +static bool >> +cand_valid_pointer_at_use_p (struct ivopts_data *data, struct iv_cand *cand, >> + struct iv_use *use) >> +{ >> + struct iv_use *cand_iv_use = iv_use (data, cand->iv->use_id); > > This is rather strange. cand->iv->use_id is never being set (all candidates are > allocated through add_candidate_1, which creates a new iv for them from the given > base and step). So this just chooses a random use (the first one appearing in the > loop), regrardless whether it has anything to do with cand or not. Btw, patches like this should get some benchmarking for a primary platform. Richard. > Zdenek >
Hi Paolo, On 02/28/2011 11:37 AM, Paolo Bonzini wrote: > On 02/28/2011 10:41 AM, Tom de Vries wrote: >> The difficulty is that this replacement is only valid under the >> guarantee that base + n does not overflow. > > I think this should be done unconditionally under > -funsafe-loop-optimizations. void f (char *base, unsigned long int i, unsigned long int n) { char *p = base + i; do { *p = '\0'; p++; i++; } while (i < n); } AFAIU, -funsafe-loop-optimizations allows me to assume that i does not overflow. Are you saying that -funsafe-loop-optimizations also implies that p does not overflow? - Tom
On 02/28/2011 03:22 PM, Tom de Vries wrote: >> > >> > I think this should be done unconditionally under >> > -funsafe-loop-optimizations. > void > f (char *base, unsigned long int i, unsigned long int n) > { > char *p = base + i; > do > { > *p = '\0'; > p++; > i++; > } > while (i< n); > } > > AFAIU, -funsafe-loop-optimizations allows me to assume that i does not > overflow. Are you saying that -funsafe-loop-optimizations also implies > that p does not overflow? I'm wondering if the C standard doesn't allow you to accept this always, at least if the increment to i (and p) is positive. I'm thinking that "undefined behavior for NULL pointer access" implies that an object cannot be allocated across a NULL pointer. And since pointer arithmetic beyond object boundaries is undefined, an overflow of p (which would cross a NULL pointer) is also undefined. I'm not sure what your code's intentions would be in a more general case that incrementing by 1. But, in particular, this is valid code: void f (char *base, unsigned long int i, unsigned long int n) { char *p = base + i; do { *p = '\0'; p--; i--; } while (i > n); } while this isn't (assuming sizeof(long)==sizeof(void *) of course): void f (char *base, unsigned long int i, unsigned long int n) { char *p = base + i; do { *p = '\0'; p += ~0UL; i += ~0UL; } while (i > n); } Paolo
On Mon, Feb 28, 2011 at 3:43 PM, Paolo Bonzini <bonzini@gnu.org> wrote: > On 02/28/2011 03:22 PM, Tom de Vries wrote: >>> >>> > >>> > I think this should be done unconditionally under >>> > -funsafe-loop-optimizations. >> >> void >> f (char *base, unsigned long int i, unsigned long int n) >> { >> char *p = base + i; >> do >> { >> *p = '\0'; >> p++; >> i++; >> } >> while (i< n); >> } >> >> AFAIU, -funsafe-loop-optimizations allows me to assume that i does not >> overflow. Are you saying that -funsafe-loop-optimizations also implies >> that p does not overflow? > > I'm wondering if the C standard doesn't allow you to accept this always, at > least if the increment to i (and p) is positive. > > I'm thinking that "undefined behavior for NULL pointer access" implies that > an object cannot be allocated across a NULL pointer. And since pointer > arithmetic beyond object boundaries is undefined, an overflow of p (which > would cross a NULL pointer) is also undefined. The important thing is that IVOPTs is not allowed to introduce IVs that overflow either. And it is known to create weird IVs starting from -4 ... Richard.
On 02/28/2011 11:46 AM, Zdenek Dvorak wrote: > Hi, > >> 23-02-2011 Tom de Vries <tom@codesourcery.com> >> >> gcc/ >> * tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix boundary checks. >> * testsuite/gcc.dg/tree-ssa/ivopts-max.c: New test. >> * testsuite/gcc.dg/tree-ssa/ivopts-max-2.c: New test. >> * testsuite/gcc.dg/tree-ssa/ivopts-max-3.c: New test. > >> diff -u gcc/tree-ssa-loop-ivopts.c gcc/tree-ssa-loop-ivopts.c >> --- gcc/tree-ssa-loop-ivopts.c (revision 162585) >> +++ gcc/tree-ssa-loop-ivopts.c (working copy) >> @@ -4079,8 +4079,12 @@ >> /* If the number of iterations is constant, compare against it directly. */ >> if (TREE_CODE (nit) == INTEGER_CST) >> { >> - /* See cand_value_at. */ >> - if (stmt_after_increment (loop, cand, use->stmt)) >> + /* An iv with TYPE_PRECISION 32 has 2^32 distinct values, and an iv_period >> + of 2^32 - 1. Such an iv can handle at most a nit of 2^32 - 1. If the >> + exit test is after the increment, the bound calculation will overflow. >> + If overflow wraps, that's not a problem. */ >> + if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) >> + && stmt_after_increment (loop, cand, use->stmt)) >> { >> if (!tree_int_cst_lt (nit, period)) >> return false; >> @@ -4100,7 +4104,9 @@ >> double_int period_value, max_niter; >> >> max_niter = desc->max; >> - if (stmt_after_increment (loop, cand, use->stmt)) >> + /* See comment at TREE_CODE (nit) == INTEGER_CST. */ >> + if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) >> + && stmt_after_increment (loop, cand, use->stmt)) >> max_niter = double_int_add (max_niter, double_int_one); >> period_value = tree_to_double_int (period); >> if (double_int_ucmp (max_niter, period_value) > 0) > > This looks strange. If indeed there is an off-by-one error here, it should not depend > on whether TYPE_OVERFLOW_WRAPS (TREE_TYPE (cand->iv->base)) is true or not. The only > candidates that satisfy !TYPE_OVERFLOW_WRAPS are those for that we are certain that their > computations cannot overflow (e.g., if they are the original induction variables of the loop > computed in a !TYPE_OVERFLOW_WRAPS type). > Ok, in that case I'll remove the stmt_after_increment related code in may_eliminate_iv. >> +static bool >> +cand_valid_pointer_at_use_p (struct ivopts_data *data, struct iv_cand *cand, >> + struct iv_use *use) >> +{ >> + struct iv_use *cand_iv_use = iv_use (data, cand->iv->use_id); > > This is rather strange. cand->iv->use_id is never being set (all candidates are > allocated through add_candidate_1, which creates a new iv for them from the given > base and step). So this just chooses a random use (the first one appearing in the > loop), regrardless whether it has anything to do with cand or not. > I see, that needs fixing indeed. Thanks for noticing that. - Tom
Hi, > >>> > I think this should be done unconditionally under > >>> > -funsafe-loop-optimizations. > >> > >> void > >> f (char *base, unsigned long int i, unsigned long int n) > >> { > >> char *p = base + i; > >> do > >> { > >> *p = '\0'; > >> p++; > >> i++; > >> } > >> while (i< n); > >> } > >> > >> AFAIU, -funsafe-loop-optimizations allows me to assume that i does not > >> overflow. Are you saying that -funsafe-loop-optimizations also implies > >> that p does not overflow? > > > > I'm wondering if the C standard doesn't allow you to accept this always, at > > least if the increment to i (and p) is positive. > > > > I'm thinking that "undefined behavior for NULL pointer access" implies that > > an object cannot be allocated across a NULL pointer. And since pointer > > arithmetic beyond object boundaries is undefined, an overflow of p (which > > would cross a NULL pointer) is also undefined. > > The important thing is that IVOPTs is not allowed to introduce IVs that > overflow either. And it is known to create weird IVs starting from > -4 ... as long as we do the arithmetics in unsigned integer type and only cast to the pointer type the final result, C standard (plus the gcc-specific interpretation of casts) allows us to do that. Nevertheless, pointer arithmetics has defined behavior only within a single memory object or at most one array element after it; which more or less forbids overflows, when the arithmetics is performed in pointer type, Zdenek
Index: gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c (revision 0) @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts -fno-tree-vectorize -fno-tree-loop-ivcanon" } */ + +void +f (char *p, unsigned long int i, unsigned long int n) +{ + p += i; + do + { + *p = '\0'; + p += 1; + i++; + } + while (i < n); +} + +/* { dg-final { scan-tree-dump-times "PHI" 1 "ivopts"} } */ +/* { dg-final { scan-tree-dump-times "PHI <p_" 1 "ivopts"} } */ +/* { dg-final { scan-tree-dump-times "p_\[0-9\]* <" 1 "ivopts"} } */ +/* { dg-final { cleanup-tree-dump "ivopts" } } */