graphite-poly.c (print_scop): Print SCOP_ORIGINAL_SCHEDULE and SCOP_TRANSFORMED_SCHEDULE.

2009-10-06  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-poly.c (print_scop): Print SCOP_ORIGINAL_SCHEDULE and
	SCOP_TRANSFORMED_SCHEDULE.
	(loop_to_lst): New.
	(scop_to_lst): New.
	(print_lst): New.
	(debug_lst): New.
	* graphite-poly.h (lst_p): New.
	(struct lst): New.
	(LST_LOOP_P): New.
	(LST_LOOP_FATHER): New.
	(LST_PBB): New.
	(LST_SEQ): New.
	(scop_to_lst): Declared.
	(print_lst): Declared.
	(debug_lst): Declared.
	(new_lst_loop): New.
	(new_lst_stmt): New.
	(copy_lst): New.
	(lst_depth): New.
	(lst_dewey_number): New.
	(struct scop): Add original_schedule and transformed_schedule fields.
	(SCOP_ORIGINAL_SCHEDULE): New.
	(SCOP_TRANSFORMED_SCHEDULE): New.
	* graphite-sese-to-poly.c (build_poly_scop): Call scop_to_lst.

From-SVN: r154562

4 files changed, 236 insertions, 0 deletions

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index f8c3ff1..d316aac 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,30 @@
+2009-10-06  Sebastian Pop  <sebastian.pop@amd.com>
+
+	* graphite-poly.c (print_scop): Print SCOP_ORIGINAL_SCHEDULE and
+	SCOP_TRANSFORMED_SCHEDULE.
+	(loop_to_lst): New.
+	(scop_to_lst): New.
+	(print_lst): New.
+	(debug_lst): New.
+	* graphite-poly.h (lst_p): New.
+	(struct lst): New.
+	(LST_LOOP_P): New.
+	(LST_LOOP_FATHER): New.
+	(LST_PBB): New.
+	(LST_SEQ): New.
+	(scop_to_lst): Declared.
+	(print_lst): Declared.
+	(debug_lst): Declared.
+	(new_lst_loop): New.
+	(new_lst_stmt): New.
+	(copy_lst): New.
+	(lst_depth): New.
+	(lst_dewey_number): New.
+	(struct scop): Add original_schedule and transformed_schedule fields.
+	(SCOP_ORIGINAL_SCHEDULE): New.
+	(SCOP_TRANSFORMED_SCHEDULE): New.
+	* graphite-sese-to-poly.c (build_poly_scop): Call scop_to_lst.
+
 2009-10-05  Sebastian Pop  <sebastian.pop@amd.com>
 
 	* graphite-dependences.c (reduction_ddr): New.
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index e97b0a8..843640c 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -643,6 +643,14 @@ print_scop (FILE *file, scop_p scop)
     print_pbb (file, pbb);
 
   fprintf (file, ")\n");
+
+  fprintf (file, "original_lst (\n");
+  print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
+  fprintf (file, ")\n");
+
+  fprintf (file, "transformed_lst (\n");
+  print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
+  fprintf (file, ")\n");
 }
 
 /* Print to STDERR the domain of PBB.  */
@@ -807,5 +815,92 @@ pbb_number_of_iterations_at_time (poly_bb_p pbb,
   ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain);
 }
 
+/* Translates LOOP to LST.  */
+
+static lst_p
+loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
+{
+  poly_bb_p pbb;
+  VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
+
+  for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
+    {
+      lst_p stmt;
+      basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
+
+      if (bb->loop_father == loop)
+	stmt = new_lst_stmt (pbb);
+      else
+	{
+	  if (flow_bb_inside_loop_p (loop, bb))
+	    stmt = loop_to_lst (loop->inner, bbs, i);
+	  else
+	    {
+	      loop_p next = loop;
+
+	      while ((next = next->next)
+		     && !flow_bb_inside_loop_p (next, bb));
+
+	      if (!next)
+		return new_lst_loop (seq);
+
+	      stmt = loop_to_lst (next, bbs, i);
+	    }
+	}
+
+      VEC_safe_push (lst_p, heap, seq, stmt);
+    }
+
+  return new_lst_loop (seq);
+}
+
+/* Reads the original scattering of the SCOP and returns an LST
+   representing it.  */
+
+void
+scop_to_lst (scop_p scop)
+{
+  poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), 0);
+  loop_p loop = outermost_loop_in_sese (SCOP_REGION (scop), GBB_BB (PBB_BLACK_BOX (pbb)));
+  int i = 0;
+
+  SCOP_ORIGINAL_SCHEDULE (scop) = loop_to_lst (loop, SCOP_BBS (scop), &i);
+  SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_ORIGINAL_SCHEDULE (scop));
+}
+
+/* Print LST to FILE with INDENT spaces of indentation.  */
+
+void
+print_lst (FILE *file, lst_p lst, int indent)
+{
+  if (!lst)
+    return;
+
+  indent_to (file, indent);
+
+  if (LST_LOOP_P (lst))
+    {
+      int i;
+      lst_p l;
+
+      fprintf (file, "%d (loop", lst_dewey_number (lst));
+
+      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
+	print_lst (file, l, indent + 2);
+
+      fprintf (file, ")");
+    }
+  else
+    fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
+}
+
+/* Print LST to STDERR.  */
+
+void
+debug_lst (lst_p lst)
+{
+  print_lst (stderr, lst, 0);
+}
+
 #endif
 
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index c397f6a..f9e59db 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -580,6 +580,114 @@ psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
   PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
 }
 
+typedef struct lst *lst_p;
+DEF_VEC_P(lst_p);
+DEF_VEC_ALLOC_P (lst_p, heap);
+
+/* Loops and Statements Tree.  */
+struct lst {
+
+  /* LOOP_P is true when an LST node is a loop.  */
+  bool loop_p;
+
+  /* A pointer to the loop that contains this node.  */
+  lst_p loop_father;
+
+  /* Loop nodes contain a sequence SEQ of LST nodes, statements
+     contain a pointer to their polyhedral representation PBB.  */
+  union {
+    poly_bb_p pbb;
+    VEC (lst_p, heap) *seq;
+  } node;
+};
+
+#define LST_LOOP_P(LST) ((LST)->loop_p)
+#define LST_LOOP_FATHER(LST) ((LST)->loop_father)
+#define LST_PBB(LST) ((LST)->node.pbb)
+#define LST_SEQ(LST) ((LST)->node.seq)
+
+void scop_to_lst (scop_p);
+void print_lst (FILE *, lst_p, int);
+void debug_lst (lst_p);
+
+/* Creates a new LST loop with SEQ.  */
+
+static inline lst_p
+new_lst_loop (VEC (lst_p, heap) *seq)
+{
+  lst_p lst = XNEW (struct lst);
+  int i;
+  lst_p l;
+
+  LST_LOOP_P (lst) = true;
+  LST_SEQ (lst) = seq;
+  LST_LOOP_FATHER (lst) = NULL;
+
+  for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
+    LST_LOOP_FATHER (l) = lst;
+
+  return lst;
+}
+
+/* Creates a new LST statement with PBB.  */
+
+static inline lst_p
+new_lst_stmt (poly_bb_p pbb)
+{
+  lst_p lst = XNEW (struct lst);
+
+  LST_LOOP_P (lst) = false;
+  LST_PBB (lst) = pbb;
+  LST_LOOP_FATHER (lst) = NULL;
+  return lst;
+}
+
+/* Returns a copy of LST.  */
+
+static inline lst_p
+copy_lst (lst_p lst)
+{
+  if (!lst)
+    return NULL;
+
+  if (LST_LOOP_P (lst))
+    return new_lst_loop (VEC_copy (lst_p, heap, LST_SEQ (lst)));
+
+  return new_lst_stmt (LST_PBB (lst));
+}
+
+/* Returns the loop depth of LST.  */
+
+static inline int
+lst_depth (lst_p lst)
+{
+  if (!lst)
+    return -1;
+
+  return lst_depth (LST_LOOP_FATHER (lst)) + 1;
+}
+
+/* Returns the Dewey number for LST.  */
+
+static inline int
+lst_dewey_number (lst_p lst)
+{
+  int i;
+  lst_p l;
+
+  if (!lst)
+    return -1;
+
+  if (!LST_LOOP_FATHER (lst))
+    return 0;
+
+  for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++)
+    if (l == lst)
+      return i;
+
+  return -1;
+}
+
 /* A SCOP is a Static Control Part of the program, simple enough to be
    represented in polyhedral form.  */
 struct scop
@@ -595,6 +703,9 @@ struct scop
      representation.  */
   VEC (poly_bb_p, heap) *bbs;
 
+  /* Original and transformed schedules.  */
+  lst_p original_schedule, transformed_schedule;
+
   /* Data dependence graph for this SCoP.  */
   struct graph *dep_graph;
 
@@ -623,6 +734,8 @@ struct scop
 #define SCOP_DEP_GRAPH(S) (S->dep_graph)
 #define SCOP_CONTEXT(S) (S->context)
 #define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
+#define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
+#define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
 
 extern scop_p new_scop (void *);
 extern void free_scop (scop_p);
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 56f89cc..807e287 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2605,6 +2605,7 @@ build_poly_scop (scop_p scop)
   build_scop_context (scop);
 
   add_conditions_to_constraints (scop);
+  scop_to_lst (scop);
   build_scop_scattering (scop);
   build_scop_drs (scop);