[autovect][PATCH]: Re: Simple loops not interchanged?

[Daniel Berlin <dberlin@dberlin.org>]

[-- 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"} } */