Simple loops not interchanged?

Simple loops not interchanged?

[Richard Guenther]

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/

Re: Simple loops not interchanged?

[Andrew Pinski]

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

Re: Simple loops not interchanged?

[Daniel Berlin]

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

Re: Simple loops not interchanged?

[Daniel Berlin]

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

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

[Daniel Berlin]

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

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

[Devang Patel]

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

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

[Daniel Berlin]

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
>
>

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

[Sebastian Pop]

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
}