[autovect][PATCH]: Re: Simple loops not interchanged?
Daniel Berlin
dberlin@dberlin.org
Sun Dec 12 03:58:00 GMT 2004
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.
:)
-------------- next part --------------
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"
@@ -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"} } */
More information about the Gcc
mailing list