[graphite] Fix 464.h264 from CPU2006 runtime test

[Sebastian Pop <sebpop at gmail dot com>]

Hi,

This patch fixes the h264 runtime bug.  This bug was due to graphite
executing a loop fusion without checking the dependences!  Yes, loop
fusion was code generated for two adjacent loops.  The bug was that we
inadvertently built a scheduling that asked for loop fusion:

       A B C
stmt1: 0 0 0
stmt2: 0 0 1

Because the prefix "A B" is common to both stmt1 and stmt2, we were
sequentially including "stmt1; stmt2" in the loop nest "A B".

After this patch we generate the following schedule that respects the
original loop nesting of statements:

       A B C
stmt1: 0 0 0
stmt2: 0 1 0

On a side note, even if this was a bug in the static schedule info,
the stability of Graphite's code generator on loop fusion was a nice
surprise!

The patch is under test in trunk on amd64-linux.  Okay for trunk once
regstrap passes?

Thanks,
Sebastian Pop
--
AMD - GNU Tools

2009-01-15  Sebastian Pop  <sebastian.pop@amd.com>
	    Tobias Grosser  <tobi.grosser@amd.com>

	* graphite.c (compare_prefix_loops): New.
	(build_scop_canonical_schedules): Rewritten.
	(graphite_transform_loops): Move build_scop_canonical_schedules
	after build_scop_iteration_domain.

Index: graphite.c
===================================================================
--- graphite.c	(revision 143408)
+++ graphite.c	(working copy)
@@ -2488,6 +2488,29 @@ build_scop_dynamic_schedules (scop_p sco
     }
 }
 
+/* Returns the number of loops that are identical at the beginning of
+   the vectors A and B.  */
+
+static int
+compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
+{
+  int i;
+  loop_p ea;
+  int lb;
+
+  if (!a || !b)
+    return 0;
+
+  lb = VEC_length (loop_p, b);
+
+  for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
+    if (i >= lb
+	|| ea != VEC_index (loop_p, b, i))
+      return i;
+
+  return 0;
+}
+
 /* Build for BB the static schedule.
 
    The STATIC_SCHEDULE is defined like this:
@@ -2524,34 +2547,23 @@ build_scop_dynamic_schedules (scop_p sco
 static void
 build_scop_canonical_schedules (scop_p scop)
 {
-  int i, j;
+  int i;
   graphite_bb_p gb;
-  int nb = scop_nb_loops (scop) + 1;
-
-  SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb);
+  int nb_loops = scop_nb_loops (scop);
+  lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
+  VEC (loop_p, heap) *loops_previous = NULL;
 
   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
     {
-      int offset = nb_loops_around_gb (gb);
+      int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
+      int nb = gbb_nb_loops (gb);
 
-      /* After leaving a loop, it is possible that the schedule is not
-	 set at zero.  This loop reinitializes components located
-	 after OFFSET.  */
-
-      for (j = offset + 1; j < nb; j++)
-	if (SCOP_STATIC_SCHEDULE (scop)[j])
-	  {
-	    memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0,
-		    sizeof (int) * (nb - j));
-	    ++SCOP_STATIC_SCHEDULE (scop)[offset];
-	    break;
-	  }
-
-      GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1);
-      lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop), 
-			  GBB_STATIC_SCHEDULE (gb), offset + 1);
-
-      ++SCOP_STATIC_SCHEDULE (scop)[offset];
+      loops_previous = GBB_LOOPS (gb);
+      memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
+      ++static_schedule[prefix];
+      GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
+      lambda_vector_copy (static_schedule, 
+			  GBB_STATIC_SCHEDULE (gb), nb + 1);
     }
 }
 
@@ -6065,7 +6077,6 @@ graphite_transform_loops (void)
       if (!build_scop_loop_nests (scop))
 	continue;
 
-      build_scop_canonical_schedules (scop);
       build_bb_loops (scop);
 
       if (!build_scop_conditions (scop))
@@ -6087,6 +6098,7 @@ graphite_transform_loops (void)
 	continue;
 
       add_conditions_to_constraints (scop);
+      build_scop_canonical_schedules (scop);
 
       build_scop_data_accesses (scop);
       build_scop_dynamic_schedules (scop);