Fix PR42334: correct the update of the LST on loop interchange and distribution.

2009-12-15  Sebastian Pop  <sebastian.pop@amd.com>

        PR middle-end/42178
        PR middle-end/42334
        * graphite-interchange.c (lst_perfect_nestify): Reset to NULL the LSTs
        that are empty.
        (lst_do_interchange_1): Renamed lst_interchange_select_inner.
        (lst_try_interchange): Reimplemented.
        (lst_interchange_select_inner): Same.
        (lst_do_interchange): Renamed lst_interchange_select_outer.
        Reimplemented.
        (scop_do_interchange): Update use of lst_interchange_select_outer.

        * graphite-interchange.c (lst_try_interchange): Do not increment the
        the OUTER index when there is no AFTER kernel.  Do not increment the
        OUTER index for after processing the AFTER kernel.
        (lst_interchange_select_inner): Call lst_try_interchange only on loops.
        (lst_interchange_select_outer): Do not pass in a pointer to the OUTER
        index.  Do not pass to lst_interchange_select_inner the OUTER index.
        (scop_do_interchange): Update use of lst_interchange_select_outer.

        * graphite-interchange.c (lst_try_interchange): Do not modify OUTER
        index.  Call lst_interchange_select_inner only once.
        (lst_interchange_select_inner): Update use of lst_try_interchange.
        (lst_interchange_select_outer): Update.

        * testsuite/g++.dg/graphite/pr42130.C: Add -fgraphite-identity.
        * testsuite/gcc.dg/graphite/block-0.c: Un-XFAILed.
        * testsuite/gcc.dg/graphite/pr42211.c: New.
        * testsuite/gfortran.dg/graphite/pr42334.f90: New.

        * testsuite/gfortran.dg/graphite/graphite.exp
        (DEFAULT_FLAGS_GRAPHITE_IDENTITY): Remove -fdump-tree-graphite-all.
        * testsuite/gfortran.dg/graphite/interchange-1.f: Add comment.  Clean
        the graphite dump file.
        * testsuite/gfortran.dg/graphite/interchange-2.f: Same.
        * testsuite/gfortran.dg/graphite/pr42334-1.f: New.

From-SVN: r155418

10 files changed, 174 insertions, 54 deletions

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index b17f3d4..232e13d 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,49 @@
+2009-12-17  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/42178
+	PR middle-end/42334
+	* graphite-interchange.c (lst_try_interchange): Do not modify OUTER
+	index.  Call lst_interchange_select_inner only once.
+	(lst_interchange_select_inner): Update use of lst_try_interchange.
+	(lst_interchange_select_outer): Update.
+
+2009-12-15  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/42178
+	PR middle-end/42334
+	* graphite-interchange.c (lst_try_interchange): Do not increment the
+	the OUTER index when there is no AFTER kernel.  Do not increment the
+	OUTER index for after processing the AFTER kernel.
+	(lst_interchange_select_inner): Call lst_try_interchange only on loops.
+	(lst_interchange_select_outer): Do not pass in a pointer to the OUTER
+	index.  Do not pass to lst_interchange_select_inner the OUTER index.
+	(scop_do_interchange): Update use of lst_interchange_select_outer.
+
+	* testsuite/gfortran.dg/graphite/graphite.exp
+	(DEFAULT_FLAGS_GRAPHITE_IDENTITY): Remove -fdump-tree-graphite-all.
+	* testsuite/gfortran.dg/graphite/interchange-1.f: Add comment.  Clean
+	the graphite dump file.
+	* testsuite/gfortran.dg/graphite/interchange-2.f: Same.
+	* testsuite/gfortran.dg/graphite/pr42334-1.f: New.
+
+2009-12-15  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/42178
+	PR middle-end/42334
+	* graphite-interchange.c (lst_perfect_nestify): Reset to NULL the LSTs
+	that are empty.
+	(lst_do_interchange_1): Renamed lst_interchange_select_inner.
+	(lst_try_interchange): Reimplemented.
+	(lst_interchange_select_inner): Same.
+	(lst_do_interchange): Renamed lst_interchange_select_outer.
+	Reimplemented.
+	(scop_do_interchange): Update use of lst_interchange_select_outer.
+
+	* testsuite/g++.dg/graphite/pr42130.C: Add -fgraphite-identity.
+	* testsuite/gcc.dg/graphite/block-0.c: Un-XFAILed.
+	* testsuite/gcc.dg/graphite/pr42211.c: New.
+	* testsuite/gfortran.dg/graphite/pr42334.f90: New.
+
 2009-12-14  Sebastian Pop  <sebastian.pop@amd.com>
 
 	PR middle-end/42181
diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
index 280a14e..d4bc232 100644
--- a/gcc/graphite-interchange.c
+++ b/gcc/graphite-interchange.c
@@ -585,6 +585,13 @@ lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
 
   lst_remove_all_before_excluding_pbb (*nest, first, true);
   lst_remove_all_before_excluding_pbb (*nest, last, false);
+
+  if (lst_empty_p (*before))
+    *before = NULL;
+  if (lst_empty_p (*after))
+    *after = NULL;
+  if (lst_empty_p (*nest))
+    *nest = NULL;
 }
 
 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
@@ -650,92 +657,91 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2,
   return false;
 }
 
-static bool lst_do_interchange_1 (scop_p, lst_p, int *);
+static bool lst_interchange_select_inner (scop_p, lst_p, int, lst_p);
 
-/* Try to interchange LOOP with all the loops contained in the body of
-   LST.  Return true if it did interchanged some loops.  INDEX points
-   to the next element to be processed by lst_do_interchange.  */
+/* Try to interchange loop OUTER of LST_SEQ (OUTER_FATHER) with all
+   the loop INNER and with all the loops contained in the body of
+   INNER.  Return true if it did interchanged some loops.  */
 
 static bool
-lst_try_interchange (scop_p scop, lst_p loop, lst_p lst, int *index)
+lst_try_interchange (scop_p scop, lst_p outer_father, int outer, lst_p inner)
 {
-  int i;
-  lst_p l;
   lst_p before, nest, after;
   bool res;
+  lst_p loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
+  lst_p loop2 = inner;
 
-  if (!lst || !LST_LOOP_P (lst))
-    return false;
+  gcc_assert (LST_LOOP_P (loop1)
+	      && LST_LOOP_P (loop2));
 
-  res = lst_try_interchange_loops (scop, loop, lst, &before, &nest, &after);
+  res = lst_try_interchange_loops (scop, loop1, loop2, &before, &nest, &after);
 
   if (before)
-    {
-      res |= lst_do_interchange_1 (scop, before, index);
-      (*index)++;
-    }
-
-  if (nest)
-    res |= lst_do_interchange_1 (scop, nest, index);
+    res |= lst_interchange_select_inner (scop, outer_father, outer, before);
+  else if (nest)
+    res |= lst_interchange_select_inner (scop, outer_father, outer, nest);
   else
-    for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
-      res |= lst_try_interchange (scop, loop, l, index);
+    res |= lst_interchange_select_inner (scop, outer_father, outer, loop2);
 
-  if (after)
-    {
-      res |= lst_do_interchange_1 (scop, after, index);
-      (*index)++;
-    }
-
-  (*index)++;
   return res;
 }
 
-/* Interchanges all the loops of LOOP that are considered profitable
-   to interchange.  Return true if it did interchanged some loops.
-   INDEX points to the next element to be processed by
-   lst_do_interchange.  */
+/* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
+   with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
 
 static bool
-lst_do_interchange_1 (scop_p scop, lst_p loop, int *index)
+lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
+			      lst_p inner_father)
 {
-  int i;
   lst_p l;
   bool res = false;
+  int inner;
 
-  if (!loop || !LST_LOOP_P (loop))
-    return false;
+  gcc_assert (outer_father
+	      && LST_LOOP_P (outer_father)
+	      && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
+	      && inner_father
+	      && LST_LOOP_P (inner_father));
 
-  for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++)
-    res |= lst_try_interchange (scop, loop, l, index);
+  for (inner = 0; VEC_iterate (lst_p, LST_SEQ (inner_father), inner, l); inner++)
+    if (LST_LOOP_P (l))
+      res |= lst_try_interchange (scop, outer_father, outer, l);
 
   return res;
 }
 
 /* Interchanges all the loops of LOOP and the loops of its body that
    are considered profitable to interchange.  Return true if it did
-   interchanged some loops.  INDEX points to the next element to be
-   processed in the LST_SEQ (LOOP) vector.  */
+   interchanged some loops.  OUTER is the index in LST_SEQ (LOOP) that
+   points to the next outer loop to be considered for interchange.  */
 
 static bool
-lst_do_interchange (scop_p scop, lst_p loop, int *index)
+lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
 {
   lst_p l;
   bool res = false;
+  int i = 0;
+  lst_p father;
 
   if (!loop || !LST_LOOP_P (loop))
     return false;
 
-  if (lst_depth (loop) >= 0)
-    res = lst_do_interchange_1 (scop, loop, index);
+  father = LST_LOOP_FATHER (loop);
+  if (father)
+    {
+      res = lst_interchange_select_inner (scop, father, outer, loop);
+
+      if (VEC_length (lst_p, LST_SEQ (father)) <= (unsigned) outer)
+	return res;
 
-  while (VEC_iterate (lst_p, LST_SEQ (loop), *index, l))
-    if (LST_LOOP_P (l))
-      res |= lst_do_interchange (scop, l, index);
-    else
-      (*index)++;
+      loop = VEC_index (lst_p, LST_SEQ (father), outer);
+    }
+
+  if (LST_LOOP_P (loop))
+    for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++)
+      if (LST_LOOP_P (l))
+	res |= lst_interchange_select_outer (scop, l, i);
 
-  (*index)++;
   return res;
 }
 
@@ -744,8 +750,8 @@ lst_do_interchange (scop_p scop, lst_p loop, int *index)
 bool
 scop_do_interchange (scop_p scop)
 {
-  int i = 0;
-  bool res = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop), &i);
+  bool res = lst_interchange_select_outer
+    (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 
   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
 
diff --git a/gcc/testsuite/g++.dg/graphite/pr42130.C b/gcc/testsuite/g++.dg/graphite/pr42130.C
index ca00227..ee31aba 100644
--- a/gcc/testsuite/g++.dg/graphite/pr42130.C
+++ b/gcc/testsuite/g++.dg/graphite/pr42130.C
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -fno-tree-ch" } */
+/* { dg-options "-O2 -fgraphite-identity -fno-tree-ch" } */
 #include <vector>
 
 using std::vector;
@@ -9,11 +9,11 @@ vector<unsigned> & __attribute__((noinline, noclone)) foo(unsigned n)
   return *vv;
 }
 
-
 int main()
 {
   foo(0);
   return 0;
 }
+
 /* { dg-do run  } */
 
diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c
index 55b9036..a00694c 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-0.c
@@ -19,5 +19,5 @@ main()
   return toto();
 }
 
-/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */ 
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/pr42211.c b/gcc/testsuite/gcc.dg/graphite/pr42211.c
new file mode 100644
index 0000000..d8fb915
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/pr42211.c
@@ -0,0 +1,22 @@
+/* { dg-options "-O3 -floop-interchange" } */
+
+typedef unsigned char uint8_t;
+
+void border_mirror(uint8_t *outer_img, int w, int h, int rb, int border)
+{
+  uint8_t *img = outer_img + border * rb + border;
+  int x, y;
+
+  for (y = -border; y < 0; y++) {
+    for (x = -border; x < 0; x++)
+      img[y*rb + x] = img[(-y)*rb + (-x)];
+
+    for (x = 0; x < w; x++)
+      img[y*rb + x] = img[(-y)*rb + x];
+  }
+}
+
+void border_mirror_480(uint8_t *outer_img)
+{
+  border_mirror(outer_img, 640, 480, 640 + 16*2, 16);
+}
diff --git a/gcc/testsuite/gfortran.dg/graphite/graphite.exp b/gcc/testsuite/gfortran.dg/graphite/graphite.exp
index 997453d..99b46de 100644
--- a/gcc/testsuite/gfortran.dg/graphite/graphite.exp
+++ b/gcc/testsuite/gfortran.dg/graphite/graphite.exp
@@ -49,7 +49,7 @@ gfortran-dg-runtest $block_files $DEFAULT_FLAGS_GRAPHITE_BLOCK
 foreach block_file $block_files {lremove wait_to_run_files $block_file}
 
 # Flags using for id-* files.
-set DEFAULT_FLAGS_GRAPHITE_IDENTITY "-O2 -fgraphite-identity -fdump-tree-graphite-all"
+set DEFAULT_FLAGS_GRAPHITE_IDENTITY "-O2 -fgraphite-identity"
 set id_files [lsort [glob -nocomplain $srcdir/$subdir/id-*.\[fF\]{,90,95,03,08} ] ]
 gfortran-dg-runtest $id_files $DEFAULT_FLAGS_GRAPHITE_IDENTITY
 foreach id_file $id_files {lremove wait_to_run_files $id_file}
diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-1.f b/gcc/testsuite/gfortran.dg/graphite/interchange-1.f
index 0440de6..334fbd8 100644
--- a/gcc/testsuite/gfortran.dg/graphite/interchange-1.f
+++ b/gcc/testsuite/gfortran.dg/graphite/interchange-1.f
@@ -37,4 +37,9 @@
       end
 
 
+! We should be able to interchange this as the number of iterations is
+! known to be 4 in the inner two loops.  See interchange-2.f for the
+! kernel from bwaves.
+
 ! { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } }
+! { dg-final { cleanup-tree-dump "graphite" } }
diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-2.f b/gcc/testsuite/gfortran.dg/graphite/interchange-2.f
index 6418c0c..8e2e87f 100644
--- a/gcc/testsuite/gfortran.dg/graphite/interchange-2.f
+++ b/gcc/testsuite/gfortran.dg/graphite/interchange-2.f
@@ -32,7 +32,12 @@
                enddo
             enddo
          enddo
-      enddo          
+      enddo
       return
       end
 
+! This is the kernel extracted from bwaves: this cannot be interchanged
+! as the number of iterations for f4 is not known.
+
+! { dg-final { scan-tree-dump-times "will be interchanged" 0 "graphite" } }
+! { dg-final { cleanup-tree-dump "graphite" } }
diff --git a/gcc/testsuite/gfortran.dg/graphite/pr42334-1.f b/gcc/testsuite/gfortran.dg/graphite/pr42334-1.f
new file mode 100644
index 0000000..2503dc3
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/pr42334-1.f
@@ -0,0 +1,16 @@
+! { dg-options "-O2 -floop-interchange" }
+
+      subroutine linel(icmdl,stre,anisox)
+      real*8 stre(6),tkl(3,3),ekl(3,3),anisox(3,3,3,3)
+            do m1=1,3
+               do m2=1,m1
+                  do m3=1,3
+                     do m4=1,3
+                        tkl(m1,m2)=tkl(m1,m2)+
+     &                       anisox(m1,m2,m3,m4)*ekl(m3,m4)
+                     enddo
+                  enddo
+               enddo
+            enddo
+            stre(1)=tkl(1,1)
+      end
diff --git a/gcc/testsuite/gfortran.dg/graphite/pr42334.f90 b/gcc/testsuite/gfortran.dg/graphite/pr42334.f90
new file mode 100644
index 0000000..4080c9f
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/pr42334.f90
@@ -0,0 +1,20 @@
+! { dg-options "-O2 -floop-interchange -ftree-loop-distribution" }
+
+subroutine blockdis(bl1eg,bl2eg)
+  implicit real*8 (a-h,o-z)
+  parameter(nblo=300)
+  common/str /mblo
+  common/str2 /mel(nblo)
+  dimension h(nblo,2,6),g(nblo,2,6)
+  dimension bl1eg(nblo,2,6),bl2eg(nblo,2,6)
+  do k=1,mblo
+     jm=mel(k)
+     do l=1,2
+        do m=1,6
+           bl1eg(k,l,m)=h(jm,l,m)
+           bl2eg(k,l,m)=g(jm,l,m)
+        enddo
+     enddo
+  enddo
+  return
+end subroutine blockdis