* Simple loops not interchanged? @ 2004-12-10 15:36 Richard Guenther 2004-12-10 16:21 ` Andrew Pinski 2004-12-10 16:34 ` Daniel Berlin 0 siblings, 2 replies; 8+ messages in thread From: Richard Guenther @ 2004-12-10 15:36 UTC (permalink / raw) To: gcc Hi! I expected -ftree-loop-linear to exchange loops in double foo(double *a) { int i,j; double r = 0.0; for (i=0; i<8; ++i) for (j=0; j<8; ++j) r += a[j*8+i]; return r; } but it tells me (regardless of loop order) that "Won't transform loop. Optimal transform is the identity transform" which I cannot believe, obviously. From further experiments, if I don't pass a as a function parameter, but make its declaration globally available, the transform succeeds. The main difference in tree dumps before the transformation attempt is the data access: <L1>:; D.1129_12 = j_4 * 8; D.1130_13 = i_3 + D.1129_12; - D.1131_14 = (unsigned int) D.1130_13; - D.1132_15 = D.1131_14 * 8; - D.1133_16 = (double *) D.1132_15; - D.1134_18 = D.1133_16 + a_17; - D.1135_19 = *D.1134_18; + D.1131_15 = a[D.1130_13]; r_6 = r_5 + D.1131_15; j_17 = j_4 + 1; if (N_7 > j_17) goto <L16>; else goto <L3>; which is just D.1131_15 = a[D.1130_13] in case of the global. Note that is the difference starting from the generic tree dump. What's going wrong here? Richard. -- Richard Guenther <richard dot guenther at uni-tuebingen dot de> WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/ ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Simple loops not interchanged? 2004-12-10 15:36 Simple loops not interchanged? Richard Guenther @ 2004-12-10 16:21 ` Andrew Pinski 2004-12-10 16:39 ` Daniel Berlin 2004-12-10 16:34 ` Daniel Berlin 1 sibling, 1 reply; 8+ messages in thread From: Andrew Pinski @ 2004-12-10 16:21 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc On Dec 10, 2004, at 10:36 AM, Richard Guenther wrote: > Hi! > > I expected -ftree-loop-linear to exchange loops in > > double foo(double *a) > { > int i,j; > double r = 0.0; > for (i=0; i<8; ++i) > for (j=0; j<8; ++j) > r += a[j*8+i]; > return r; > } > > but it tells me (regardless of loop order) that > "Won't transform loop. Optimal transform is the identity transform" > which I cannot believe, obviously. > > What's going wrong here? First file a bug. Second the loop linearizer loves ARRAY_REF and not INDIRECT_REF for 4.1, we should be able to get MEM_REF which is like ARRAY_REF and the loop lineaerizer will just do its job. I tested the theory by having a local array instead of passing the pointer. Thanks, Andrew Pinski ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Simple loops not interchanged? 2004-12-10 16:21 ` Andrew Pinski @ 2004-12-10 16:39 ` Daniel Berlin 0 siblings, 0 replies; 8+ messages in thread From: Daniel Berlin @ 2004-12-10 16:39 UTC (permalink / raw) To: Andrew Pinski; +Cc: Richard Guenther, gcc On Fri, 10 Dec 2004, Andrew Pinski wrote: > > On Dec 10, 2004, at 10:36 AM, Richard Guenther wrote: > >> Hi! >> >> I expected -ftree-loop-linear to exchange loops in >> >> double foo(double *a) >> { >> int i,j; >> double r = 0.0; >> for (i=0; i<8; ++i) >> for (j=0; j<8; ++j) >> r += a[j*8+i]; >> return r; >> } >> >> but it tells me (regardless of loop order) that >> "Won't transform loop. Optimal transform is the identity transform" >> which I cannot believe, obviously. >> >> What's going wrong here? > > First file a bug. > Second the loop linearizer loves ARRAY_REF and not INDIRECT_REF First, i probably need to change the name, since some people think it linearizes loops, which it doesn't. It performs linear transforms :P. Second, it doesn't care about array-ref or indirect-ref, actually. It just uses what the data dependence info tells it. The autovect branch has code to start to teach the data dependence analyzer about indirect_refs. MEM_REFS in their current form look big, so i'm not sure they are an optimal solution (i'd rather see array_refs be changed to allow accesses to non-array_type things. After all, this is a fricking array he's accessing, so why isn't array_ref the right thing?) --Dan ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Simple loops not interchanged? 2004-12-10 15:36 Simple loops not interchanged? Richard Guenther 2004-12-10 16:21 ` Andrew Pinski @ 2004-12-10 16:34 ` Daniel Berlin 2004-12-12 3:58 ` [autovect][PATCH]: " Daniel Berlin 1 sibling, 1 reply; 8+ messages in thread From: Daniel Berlin @ 2004-12-10 16:34 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc On Fri, 10 Dec 2004, Richard Guenther wrote: > Hi! > > I expected -ftree-loop-linear to exchange loops in > > double foo(double *a) > { > int i,j; > double r = 0.0; > for (i=0; i<8; ++i) > for (j=0; j<8; ++j) > r += a[j*8+i]; > return r; > } > > but it tells me (regardless of loop order) that > "Won't transform loop. Optimal transform is the identity transform" > which I cannot believe, obviously. Unfortunately, there is no array_ref in these :( > What's going wrong here? The data dependence analyzer doesn't understand pointer-refs. I started to make it nuderstand them on the autovect branch, but i'm not sure it's good enough yet to disambiguate your case (as easy as it may seem). In fact, it doesn't, though it does see the data reference. Data ref b: (Data Ref: stmt: D.1134_18 = *D.1133_17; ref: *D.1133_17; base_name: a_16 Access function 0: {{a_16, +, 8B}_1, +, 64B}_2 ) affine dependence test not usable: access function not affine or constant. (dependence classified: scev_not_known) ) When we don't know the data dependences of the loop, we can't touch them (the message it prints should probably be changed in that case :P) --Dan ^ permalink raw reply [flat|nested] 8+ messages in thread
* [autovect][PATCH]: Re: Simple loops not interchanged? 2004-12-10 16:34 ` Daniel Berlin @ 2004-12-12 3:58 ` Daniel Berlin 2004-12-12 17:59 ` Devang Patel 2004-12-13 9:46 ` Sebastian Pop 0 siblings, 2 replies; 8+ messages in thread From: Daniel Berlin @ 2004-12-12 3:58 UTC (permalink / raw) To: Richard Guenther, Sebastian Pop, dorit; +Cc: gcc [-- Attachment #1: Type: TEXT/PLAIN, Size: 791 bytes --] I've attached a patch that lets us interchange this. It does two things: 1. It lets the chrec code consider variables invariant in the loop that matches the chrec variable (loop number) as constant for purposes for the chrec. 2. It informs the data dependence tester that chrecs that are equal (ie the same chrec) overlap on every iteration. This is enough to get this loop to interchange. Sebastian, unless you have a problem with this, then Dorit, i'd like to apply this to the autovect branch (Feel free to use evolution_function_is_invariant_p in the tests in the vectorizer. It should let you catch some more loops than the simple constant test, if you can transform them properly) It includes Richard's testcase in order to make sure we don't regress here later on. :) [-- Attachment #2: Type: TEXT/PLAIN, Size: 6386 bytes --] 2004-12-08 Daniel Berlin <dberlin@dberlin.org> * Makefile.in (tree-chrec.o): Add cfgloop.h * tree-chrec.c: Add cfgloop.h, tree-flow.h. (evolution_function_is_invariant_p): New function. (evolution_function_is_affine_multivariate_p): Use evolution_function_is_invariant_p instead of evolution_function_is_constant_p. * tree-chrec.h: Add prototype for evolution_function_is_invariant_p. (evolution_function_is_affine_p): Use evolution_function_is_invariant_p. * tree-data-ref.c (analyze_overlapping_iterations): chrecs that are equal overlap on every iteration. Index: Makefile.in =================================================================== RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v retrieving revision 1.1419.2.1 diff -u -p -r1.1419.2.1 Makefile.in --- Makefile.in 17 Nov 2004 18:37:51 -0000 1.1419.2.1 +++ Makefile.in 12 Dec 2004 03:47:20 -0000 @@ -1750,7 +1750,7 @@ tree-browser.o : tree-browser.c tree-bro $(TREE_H) errors.h tree-inline.h diagnostic.h $(HASHTAB_H) \ $(TM_H) coretypes.h tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ - errors.h $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h + errors.h $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h cfgloop.h tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \ coretypes.h $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) \ $(BASIC_BLOCK_H) diagnostic.h $(TREE_FLOW_H) $(TREE_DUMP_H) \ Index: tree-chrec.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v retrieving revision 2.11 diff -u -p -r2.11 tree-chrec.c --- tree-chrec.c 13 Oct 2004 03:48:03 -0000 2.11 +++ tree-chrec.c 12 Dec 2004 03:47:20 -0000 @@ -35,6 +35,8 @@ Software Foundation, 59 Temple Place - S #include "varray.h" #include "tree-chrec.h" #include "tree-pass.h" +#include "cfgloop.h" +#include "tree-flow.h" \f @@ -844,6 +846,25 @@ tree_contains_chrecs (tree expr) } } + +/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ + +bool +evolution_function_is_invariant_p (tree chrec, int loopnum) +{ + if (evolution_function_is_constant_p (chrec)) + return true; + + if (current_loops != NULL) + { + if (TREE_CODE (chrec) == SSA_NAME + && expr_invariant_in_loop_p (current_loops->parray[loopnum], + chrec)) + return true; + } + return false; +} + /* Determine whether the given tree is an affine multivariate evolution. */ @@ -856,9 +877,11 @@ evolution_function_is_affine_multivariat switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (evolution_function_is_constant_p (CHREC_LEFT (chrec))) + if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), + CHREC_VARIABLE (chrec))) { - if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))) + if (evolution_function_is_invariant_p (CHREC_RIGHT (chrec), + CHREC_VARIABLE (chrec))) return true; else { @@ -874,7 +897,8 @@ evolution_function_is_affine_multivariat } else { - if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)) + if (evolution_function_is_invariant_p (CHREC_RIGHT (chrec), + CHREC_VARIABLE (chrec)) && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) && evolution_function_is_affine_multivariate_p Index: tree-chrec.h =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-chrec.h,v retrieving revision 2.5 diff -u -p -r2.5 tree-chrec.h --- tree-chrec.h 13 Oct 2004 03:48:03 -0000 2.5 +++ tree-chrec.h 12 Dec 2004 03:47:20 -0000 @@ -147,6 +147,7 @@ evolution_function_is_constant_p (tree c } } +extern bool evolution_function_is_invariant_p (tree, int); /* Determine whether the given tree is an affine evolution function or not. */ static inline bool @@ -158,8 +159,10 @@ evolution_function_is_affine_p (tree chr switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (evolution_function_is_constant_p (CHREC_LEFT (chrec)) - && evolution_function_is_constant_p (CHREC_RIGHT (chrec))) + if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), + CHREC_VARIABLE (chrec)) + && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), + CHREC_VARIABLE (chrec))) return true; else return false; Index: tree-data-ref.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v retrieving revision 2.15.4.2 diff -u -p -r2.15.4.2 tree-data-ref.c --- tree-data-ref.c 30 Nov 2004 20:28:38 -0000 2.15.4.2 +++ tree-data-ref.c 12 Dec 2004 03:47:21 -0000 @@ -1812,12 +1812,19 @@ analyze_overlapping_iterations (tree chr fprintf (dump_file, ")\n"); } - if (chrec_a == NULL_TREE - || chrec_b == NULL_TREE - || chrec_contains_undetermined (chrec_a) - || chrec_contains_undetermined (chrec_b) - || chrec_contains_symbols (chrec_a) - || chrec_contains_symbols (chrec_b)) + /* If they are the same chrec, they overlap on every iteration. */ + if (chrec_a == chrec_b) + { + *overlap_iterations_a = integer_zero_node; + *overlap_iterations_b = integer_zero_node; + *last_conflicts = chrec_dont_know; + } + else if (chrec_a == NULL_TREE + || chrec_b == NULL_TREE + || chrec_contains_undetermined (chrec_a) + || chrec_contains_undetermined (chrec_b) + || chrec_contains_symbols (chrec_a) + || chrec_contains_symbols (chrec_b)) { dependence_stats.num_unimplemented++; Index: ltrans-8.c =================================================================== RCS file: ltrans-8.c diff -N ltrans-8.c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ ltrans-8.c 12 Dec 2004 03:56:39 -0000 @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */ +double foo(double *a) +{ + int i,j; + double r = 0.0; + for (i=0; i<8; ++i) + for (j=0; j<8; ++j) + r += a[j*8+i]; + return r; +} + +/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [autovect][PATCH]: Re: Simple loops not interchanged? 2004-12-12 3:58 ` [autovect][PATCH]: " Daniel Berlin @ 2004-12-12 17:59 ` Devang Patel 2004-12-12 18:02 ` Daniel Berlin 2004-12-13 9:46 ` Sebastian Pop 1 sibling, 1 reply; 8+ messages in thread From: Devang Patel @ 2004-12-12 17:59 UTC (permalink / raw) To: Daniel Berlin; +Cc: gcc mailing list On Dec 11, 2004, at 7:58 PM, Daniel Berlin wrote: > * Makefile.in (tree-chrec.o): Add cfgloop.h > > * tree-chrec.c: Add cfgloop.h, tree-flow.h. Make tree-chrec.o depend on TREE_FLOW_H. - Devang ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [autovect][PATCH]: Re: Simple loops not interchanged? 2004-12-12 17:59 ` Devang Patel @ 2004-12-12 18:02 ` Daniel Berlin 0 siblings, 0 replies; 8+ messages in thread From: Daniel Berlin @ 2004-12-12 18:02 UTC (permalink / raw) To: Devang Patel; +Cc: gcc mailing list On Sun, 12 Dec 2004, Devang Patel wrote: > > On Dec 11, 2004, at 7:58 PM, Daniel Berlin wrote: > >> * Makefile.in (tree-chrec.o): Add cfgloop.h >> >> * tree-chrec.c: Add cfgloop.h, tree-flow.h. > > Make tree-chrec.o depend on TREE_FLOW_H. Will do. > > - > Devang > > ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [autovect][PATCH]: Re: Simple loops not interchanged? 2004-12-12 3:58 ` [autovect][PATCH]: " Daniel Berlin 2004-12-12 17:59 ` Devang Patel @ 2004-12-13 9:46 ` Sebastian Pop 1 sibling, 0 replies; 8+ messages in thread From: Sebastian Pop @ 2004-12-13 9:46 UTC (permalink / raw) To: Daniel Berlin; +Cc: Richard Guenther, dorit, gcc On Sat, Dec 11, 2004 at 10:58:50PM -0500, Daniel Berlin wrote: > > Index: tree-data-ref.c > =================================================================== > RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v > retrieving revision 2.15.4.2 > diff -u -p -r2.15.4.2 tree-data-ref.c > --- tree-data-ref.c 30 Nov 2004 20:28:38 -0000 2.15.4.2 > +++ tree-data-ref.c 12 Dec 2004 03:47:21 -0000 > @@ -1812,12 +1812,19 @@ analyze_overlapping_iterations (tree chr > fprintf (dump_file, ")\n"); > } > > - if (chrec_a == NULL_TREE > - || chrec_b == NULL_TREE > - || chrec_contains_undetermined (chrec_a) > - || chrec_contains_undetermined (chrec_b) > - || chrec_contains_symbols (chrec_a) > - || chrec_contains_symbols (chrec_b)) > + /* If they are the same chrec, they overlap on every iteration. */ > + if (chrec_a == chrec_b) > + { > + *overlap_iterations_a = integer_zero_node; > + *overlap_iterations_b = integer_zero_node; > + *last_conflicts = chrec_dont_know; > + } Are you really sure that you want this behavior? chrec_a = chrec_dont_know chrec_b = chrec_dont_know or even the following: chrec_a = {0, +, chrec_dont_know} chrec_b = {0, +, chrec_dont_know} results in having determined overlap iterations when the analysis should have answered "don't know". The condition is a little too strong I think. > + else if (chrec_a == NULL_TREE > + || chrec_b == NULL_TREE > + || chrec_contains_undetermined (chrec_a) > + || chrec_contains_undetermined (chrec_b) > + || chrec_contains_symbols (chrec_a) > + || chrec_contains_symbols (chrec_b)) > { > dependence_stats.num_unimplemented++; > What you want is something like: if (chrec_a == NULL_TREE || chrec_b == NULL_TREE || chrec_contains_undetermined (chrec_a) || chrec_contains_undetermined (chrec_b)) { undetermined } else if (chrec_a == chrec_b && symbols_in_chrec_are_invariant_p (chrec_a)) { overlaps every iteration } else if (chrec_contains_symbols (chrec_a) || chrec_contains_symbols (chrec_b)) { undetermined } ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2004-12-13 9:46 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2004-12-10 15:36 Simple loops not interchanged? Richard Guenther 2004-12-10 16:21 ` Andrew Pinski 2004-12-10 16:39 ` Daniel Berlin 2004-12-10 16:34 ` Daniel Berlin 2004-12-12 3:58 ` [autovect][PATCH]: " Daniel Berlin 2004-12-12 17:59 ` Devang Patel 2004-12-12 18:02 ` Daniel Berlin 2004-12-13 9:46 ` Sebastian Pop
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).