| Message ID | alpine.LSU.2.11.1410161540510.20733@zhemvz.fhfr.qr |
|---|---|
| State | New |
| Headers | show |
> > The following makes us infer loop bounds for loops like > > <bb 3>: > # str_28 = PHI <"foo"(2), str_10(4)> > ... > str_10 = str_28 + 1; > _4 = *str_10; > if (_4 != 0) > goto <bb 4>; > else > goto <bb 8>; > > <bb 4>: > goto <bb 3>; > > or > > <bb 3>: > # p_15 = PHI <p_6(3), &a(2)> > p_6 = p_15 + 1; > *p_15 = 0; > ... > if (n.1_5 > i_8) > goto <bb 3>; > else > goto <bb 4>; > > Boostrap and regtest pending on x86_64-unknown-linux-gnu. > > Honza - is there a symtab way of querying whether DECL_SIZE of > a decl is "correct"? I know to better exclude extern decls > and commons, but for example C++ may have stronger rules. Not at the moment - you can probably check availability, but that is not strong enogh. I can add predicate for that. Honza > > Thanks, > Richard. > > 2014-10-16 Richard Biener <rguenther@suse.de> > > PR tree-optimization/63278 > * tree-ssa-loop-niter.c: Include tree-dfa.h. > (struct ilb_data): Add pointer to outermost reference. > (idx_infer_loop_bounds): Handle plain MEM_REFs of STRING_CSTs > and DECLs. > (infer_loop_bounds_from_ref): Adjust. > > * gcc.dg/tree-ssa/loop-41.c: New testcase. > * gcc.dg/tree-ssa/loop-42.c: Likewise. > > Index: gcc/tree-ssa-loop-niter.c > =================================================================== > --- gcc/tree-ssa-loop-niter.c (revision 216258) > +++ gcc/tree-ssa-loop-niter.c (working copy) > @@ -56,6 +56,7 @@ along with GCC; see the file COPYING3. > #include "stringpool.h" > #include "tree-ssanames.h" > #include "wide-int-print.h" > +#include "tree-dfa.h" > > > #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) > @@ -2775,6 +2776,7 @@ struct ilb_data > { > struct loop *loop; > gimple stmt; > + tree ref; > }; > > static bool > @@ -2787,7 +2789,10 @@ idx_infer_loop_bounds (tree base, tree * > struct loop *loop = data->loop; > bool reliable = true; > > - if (TREE_CODE (base) != ARRAY_REF) > + if (TREE_CODE (base) != ARRAY_REF > + && (TREE_CODE (base) != MEM_REF > + || base != data->ref > + || !integer_zerop (TREE_OPERAND (base, 1)))) > return true; > > /* For arrays at the end of the structure, we are not guaranteed that they > @@ -2816,8 +2821,46 @@ idx_infer_loop_bounds (tree base, tree * > || chrec_contains_symbols_defined_in_loop (init, loop->num)) > return true; > > - low = array_ref_low_bound (base); > - high = array_ref_up_bound (base); > + if (TREE_CODE (base) == MEM_REF) > + { > + HOST_WIDE_INT offset; > + tree decl; > + if (TREE_CODE (init) != ADDR_EXPR) > + return true; > + decl = get_addr_base_and_unit_offset (TREE_OPERAND (init, 0), &offset); > + if (!decl > + || offset != 0) > + return true; > + /* If this is a bare MEM_REF with a pointer IV that starts at > + offset zero of an object with known size we can easily compute > + an upper bound for the pointer IV. */ > + if (TREE_CODE (decl) == STRING_CST) > + { > + low = size_zero_node; > + high = size_int (TREE_STRING_LENGTH (decl)); > + } > + else if (DECL_P (decl) > + && ((TREE_STATIC (decl) && !DECL_COMMON (decl)) > + || auto_var_in_fn_p (decl, cfun->decl))) > + { > + low = size_zero_node; > + if (TREE_CODE (DECL_SIZE_UNIT (decl)) != INTEGER_CST) > + return true; > + high = DECL_SIZE_UNIT (decl); > + } > + else > + return true; > + /* We only require an upper estimate for high. So only > + if we can, subtract the size of the access. */ > + if (TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (base))) == INTEGER_CST) > + high = size_binop (MINUS_EXPR, > + high, TYPE_SIZE_UNIT (TREE_TYPE (base))); > + } > + else > + { > + low = array_ref_low_bound (base); > + high = array_ref_up_bound (base); > + } > > /* The case of nonconstant bounds could be handled, but it would be > complicated. */ > @@ -2879,6 +2922,7 @@ infer_loop_bounds_from_ref (struct loop > > data.loop = loop; > data.stmt = stmt; > + data.ref = ref; > for_each_index (&ref, idx_infer_loop_bounds, &data); > } > > Index: gcc/testsuite/gcc.dg/tree-ssa/loop-42.c > =================================================================== > --- gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (revision 0) > +++ gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (working copy) > @@ -0,0 +1,19 @@ > +/* { dg-do run } */ > +/* { dg-options "-O2 -fdump-tree-cunroll-details" } */ > + > +extern void abort (void); > +int a = -1; > +int n = sizeof (int); > +int main() > +{ > + char *p; > + int i; > + for (i = 0, p = (char *)&a; i < n; ++i) > + *p++ = 0; > + if (a != 0) > + abort (); > + return 0; > +} > + > +/* { dg-final { scan-tree-dump "loop with 4 iterations completely unrolled" "cunroll" } } */ > +/* { dg-final { cleanup-tree-dump "cunroll" } } */ > Index: gcc/testsuite/gcc.dg/tree-ssa/loop-41.c > =================================================================== > --- gcc/testsuite/gcc.dg/tree-ssa/loop-41.c (revision 0) > +++ gcc/testsuite/gcc.dg/tree-ssa/loop-41.c (working copy) > @@ -0,0 +1,25 @@ > +/* { dg-do run } */ > +/* { dg-options "-O3 -fdump-tree-cunroll-details" } */ > + > +extern void abort (void); > + > +static inline unsigned int hashString2(const char* str) > +{ > + unsigned int hash = 5381; > + while (*str) { > + hash += (hash << 5) + *str; > + str++; > + } > + return hash; > +} > + > +int main() > +{ > + unsigned int hash = hashString2("foo"); > + if (hash != 193491849) > + abort (); > + return 0; > +} > + > +/* { dg-final { scan-tree-dump "loop with 4 iterations completely unrolled" "cunroll" } } */ > +/* { dg-final { cleanup-tree-dump "cunroll" } } */
On Thu, Oct 16, 2014 at 03:44:50PM +0200, Richard Biener wrote: > --- gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (revision 0) > +++ gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (working copy) > @@ -0,0 +1,19 @@ > +/* { dg-do run } */ > +/* { dg-options "-O2 -fdump-tree-cunroll-details" } */ > + > +extern void abort (void); > +int a = -1; > +int n = sizeof (int); > +int main() > +{ > + char *p; > + int i; > + for (i = 0, p = (char *)&a; i < n; ++i) > + *p++ = 0; > + if (a != 0) > + abort (); > + return 0; > +} > + > +/* { dg-final { scan-tree-dump "loop with 4 iterations completely unrolled" "cunroll" } } */ This will fail on all targets where sizeof (int) is not 4 :(. So, I think you need to guard this scan-tree-dump with { target int32 }. Jakub
On Thu, 16 Oct 2014, Jakub Jelinek wrote: > On Thu, Oct 16, 2014 at 03:44:50PM +0200, Richard Biener wrote: > > --- gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (revision 0) > > +++ gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (working copy) > > @@ -0,0 +1,19 @@ > > +/* { dg-do run } */ > > +/* { dg-options "-O2 -fdump-tree-cunroll-details" } */ > > + > > +extern void abort (void); > > +int a = -1; > > +int n = sizeof (int); > > +int main() > > +{ > > + char *p; > > + int i; > > + for (i = 0, p = (char *)&a; i < n; ++i) > > + *p++ = 0; > > + if (a != 0) > > + abort (); > > + return 0; > > +} > > + > > +/* { dg-final { scan-tree-dump "loop with 4 iterations completely unrolled" "cunroll" } } */ > > This will fail on all targets where sizeof (int) is not 4 :(. > So, I think you need to guard this scan-tree-dump with { target int32 }. I'll adjust the testcase to scan for "loop with . iterations" instead. Richard.
Index: gcc/tree-ssa-loop-niter.c =================================================================== --- gcc/tree-ssa-loop-niter.c (revision 216258) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -56,6 +56,7 @@ along with GCC; see the file COPYING3. #include "stringpool.h" #include "tree-ssanames.h" #include "wide-int-print.h" +#include "tree-dfa.h" #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) @@ -2775,6 +2776,7 @@ struct ilb_data { struct loop *loop; gimple stmt; + tree ref; }; static bool @@ -2787,7 +2789,10 @@ idx_infer_loop_bounds (tree base, tree * struct loop *loop = data->loop; bool reliable = true; - if (TREE_CODE (base) != ARRAY_REF) + if (TREE_CODE (base) != ARRAY_REF + && (TREE_CODE (base) != MEM_REF + || base != data->ref + || !integer_zerop (TREE_OPERAND (base, 1)))) return true; /* For arrays at the end of the structure, we are not guaranteed that they @@ -2816,8 +2821,46 @@ idx_infer_loop_bounds (tree base, tree * || chrec_contains_symbols_defined_in_loop (init, loop->num)) return true; - low = array_ref_low_bound (base); - high = array_ref_up_bound (base); + if (TREE_CODE (base) == MEM_REF) + { + HOST_WIDE_INT offset; + tree decl; + if (TREE_CODE (init) != ADDR_EXPR) + return true; + decl = get_addr_base_and_unit_offset (TREE_OPERAND (init, 0), &offset); + if (!decl + || offset != 0) + return true; + /* If this is a bare MEM_REF with a pointer IV that starts at + offset zero of an object with known size we can easily compute + an upper bound for the pointer IV. */ + if (TREE_CODE (decl) == STRING_CST) + { + low = size_zero_node; + high = size_int (TREE_STRING_LENGTH (decl)); + } + else if (DECL_P (decl) + && ((TREE_STATIC (decl) && !DECL_COMMON (decl)) + || auto_var_in_fn_p (decl, cfun->decl))) + { + low = size_zero_node; + if (TREE_CODE (DECL_SIZE_UNIT (decl)) != INTEGER_CST) + return true; + high = DECL_SIZE_UNIT (decl); + } + else + return true; + /* We only require an upper estimate for high. So only + if we can, subtract the size of the access. */ + if (TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (base))) == INTEGER_CST) + high = size_binop (MINUS_EXPR, + high, TYPE_SIZE_UNIT (TREE_TYPE (base))); + } + else + { + low = array_ref_low_bound (base); + high = array_ref_up_bound (base); + } /* The case of nonconstant bounds could be handled, but it would be complicated. */ @@ -2879,6 +2922,7 @@ infer_loop_bounds_from_ref (struct loop data.loop = loop; data.stmt = stmt; + data.ref = ref; for_each_index (&ref, idx_infer_loop_bounds, &data); } Index: gcc/testsuite/gcc.dg/tree-ssa/loop-42.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/loop-42.c (working copy) @@ -0,0 +1,19 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-cunroll-details" } */ + +extern void abort (void); +int a = -1; +int n = sizeof (int); +int main() +{ + char *p; + int i; + for (i = 0, p = (char *)&a; i < n; ++i) + *p++ = 0; + if (a != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump "loop with 4 iterations completely unrolled" "cunroll" } } */ +/* { dg-final { cleanup-tree-dump "cunroll" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/loop-41.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/loop-41.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/loop-41.c (working copy) @@ -0,0 +1,25 @@ +/* { dg-do run } */ +/* { dg-options "-O3 -fdump-tree-cunroll-details" } */ + +extern void abort (void); + +static inline unsigned int hashString2(const char* str) +{ + unsigned int hash = 5381; + while (*str) { + hash += (hash << 5) + *str; + str++; + } + return hash; +} + +int main() +{ + unsigned int hash = hashString2("foo"); + if (hash != 193491849) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump "loop with 4 iterations completely unrolled" "cunroll" } } */ +/* { dg-final { cleanup-tree-dump "cunroll" } } */
The following makes us infer loop bounds for loops like <bb 3>: # str_28 = PHI <"foo"(2), str_10(4)> ... str_10 = str_28 + 1; _4 = *str_10; if (_4 != 0) goto <bb 4>; else goto <bb 8>; <bb 4>: goto <bb 3>; or <bb 3>: # p_15 = PHI <p_6(3), &a(2)> p_6 = p_15 + 1; *p_15 = 0; ... if (n.1_5 > i_8) goto <bb 3>; else goto <bb 4>; Boostrap and regtest pending on x86_64-unknown-linux-gnu. Honza - is there a symtab way of querying whether DECL_SIZE of a decl is "correct"? I know to better exclude extern decls and commons, but for example C++ may have stronger rules. Thanks, Richard. 2014-10-16 Richard Biener <rguenther@suse.de> PR tree-optimization/63278 * tree-ssa-loop-niter.c: Include tree-dfa.h. (struct ilb_data): Add pointer to outermost reference. (idx_infer_loop_bounds): Handle plain MEM_REFs of STRING_CSTs and DECLs. (infer_loop_bounds_from_ref): Adjust. * gcc.dg/tree-ssa/loop-41.c: New testcase. * gcc.dg/tree-ssa/loop-42.c: Likewise.