Patchwork [17/20] use isl's datadep analysis

login
register
mail settings
Submitter Sebastian Pop
Date Aug. 15, 2011, 7:12 a.m.
Message ID <1313392379-1525-17-git-send-email-sebpop@gmail.com>
Download mbox | patch
Permalink /patch/110004/
State New
Headers show

Comments

Sebastian Pop - Aug. 15, 2011, 7:12 a.m.
---
 gcc/graphite-dependences.c                      |  169 ++++++++++++++++++++++-
 gcc/graphite-poly.c                             |    8 +
 gcc/graphite-poly.h                             |    3 +
 gcc/testsuite/gcc.dg/graphite/interchange-14.c  |    3 +-
 gcc/testsuite/gcc.dg/graphite/interchange-15.c  |    3 +-
 gcc/testsuite/gcc.dg/graphite/interchange-8.c   |    2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-mvt.c |    3 +-
 7 files changed, 183 insertions(+), 8 deletions(-)

Patch

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 9ba2731..eb8d40f 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -25,6 +25,7 @@  along with GCC; see the file COPYING3.  If not see
 #include <isl/set.h>
 #include <isl/map.h>
 #include <isl/union_map.h>
+#include <isl/flow.h>
 #include <cloog/cloog.h>
 #include <cloog/isl/domain.h>
 #endif
@@ -722,6 +723,151 @@  graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
   return true;
 }
 
+/* Add the constraints from the set S to the domain of MAP.  */
+
+static isl_map *
+constrain_domain (isl_map *map, isl_set *s)
+{
+  isl_dim *d = isl_map_get_dim (map);
+  isl_id *id = isl_dim_get_tuple_id (d, isl_dim_in);
+
+  s = isl_set_set_tuple_id (s, id);
+  isl_dim_free (d);
+  return isl_map_intersect_domain (map, s);
+}
+
+/* Constrain pdr->accesses with pdr->extent and pbb->domain.  */
+
+static isl_map *
+add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
+{
+  isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
+					isl_set_copy (pdr->extent));
+  x = constrain_domain (x, isl_set_copy (pbb->domain));
+  return x;
+}
+
+/* Returns all the memory reads in SCOP.  */
+
+static isl_union_map *
+scop_get_sink (scop_p scop)
+{
+  int i, j;
+  poly_bb_p pbb;
+  poly_dr_p pdr;
+  isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context));
+  isl_union_map *res = isl_union_map_empty (dim);
+
+  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
+    {
+      FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), j, pdr)
+	if (pdr_read_p (pdr))
+	  res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+    }
+
+  return res;
+}
+
+/* Returns all the memory must writes in SCOP.  */
+
+static isl_union_map *
+scop_get_must_source (scop_p scop)
+{
+  int i, j;
+  poly_bb_p pbb;
+  poly_dr_p pdr;
+  isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context));
+  isl_union_map *res = isl_union_map_empty (dim);
+
+  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
+    {
+      FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), j, pdr)
+	if (pdr_write_p (pdr))
+	  res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+    }
+
+  return res;
+}
+
+/* Returns all the memory may writes in SCOP.  */
+
+static isl_union_map *
+scop_get_may_source (scop_p scop)
+{
+  int i, j;
+  poly_bb_p pbb;
+  poly_dr_p pdr;
+  isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context));
+  isl_union_map *res = isl_union_map_empty (dim);
+
+  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
+    {
+      FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), j, pdr)
+	if (pdr_may_write_p (pdr))
+	  res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+    }
+
+  return res;
+}
+
+/* Returns all the original schedules in SCOP.  */
+
+static isl_union_map *
+scop_get_original_schedule (scop_p scop)
+{
+  int i;
+  poly_bb_p pbb;
+  isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context));
+  isl_union_map *res = isl_union_map_empty (dim);
+
+  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
+    {
+      res = isl_union_map_add_map
+	(res, constrain_domain (isl_map_copy (pbb->schedule),
+				isl_set_copy (pbb->domain)));
+    }
+
+  return res;
+}
+
+/* Returns all the transformed schedules in SCOP.  */
+
+static isl_union_map *
+scop_get_transformed_schedule (scop_p scop)
+{
+  int i;
+  poly_bb_p pbb;
+  isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context));
+  isl_union_map *res = isl_union_map_empty (dim);
+
+  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
+    {
+      res = isl_union_map_add_map
+	(res, constrain_domain (isl_map_copy (pbb->transformed),
+				isl_set_copy (pbb->domain)));
+    }
+
+  return res;
+}
+
+/* Return true when SCHEDULE does not violate the data dependences DEPS.  */
+
+static bool
+no_violations (isl_union_map *schedule, isl_union_map *deps)
+{
+  bool res;
+  isl_dim *dim = isl_dim_reverse (isl_union_map_get_dim (schedule));
+  isl_map *lex = isl_map_lex_ge (dim);
+
+  deps = isl_union_map_apply_domain (deps, isl_union_map_copy (schedule));
+  deps = isl_union_map_apply_range (deps, schedule);
+  deps = isl_union_map_intersect (deps, isl_union_map_from_map (lex));
+  res = isl_union_map_is_empty (deps);
+
+  isl_union_map_free (deps);
+  return res;
+}
+
 /* Iterates over the SCOP and detect whether the transformed schedule
    is correct.  */
 
@@ -730,9 +876,31 @@  graphite_legal_transform (scop_p scop)
 {
   int i, j;
   poly_bb_p pbb1, pbb2;
+  int res;
+  isl_union_map *transformed;
 
   timevar_push (TV_GRAPHITE_DATA_DEPS);
 
+  if (!scop->must_deps)
+    {
+      isl_union_map *sink = scop_get_sink (scop);
+      isl_union_map *must_source = scop_get_must_source (scop);
+      isl_union_map *may_source = scop_get_may_source (scop);
+      isl_union_map *original = scop_get_original_schedule (scop);
+      res = isl_union_map_compute_flow (sink, must_source, may_source,
+					original, &scop->must_deps, &scop->may_deps,
+					&scop->must_no_source, &scop->may_no_source);
+      gcc_assert (res == 0);
+    }
+
+  transformed = scop_get_transformed_schedule (scop);
+  res = (no_violations (isl_union_map_copy (transformed),
+			isl_union_map_copy (scop->must_deps))
+	 && no_violations (transformed, isl_union_map_copy (scop->may_deps)));
+
+  timevar_pop (TV_GRAPHITE_DATA_DEPS);
+  return res;
+
   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
     FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
       if (!graphite_legal_transform_bb (pbb1, pbb2))
@@ -741,7 +909,6 @@  graphite_legal_transform (scop_p scop)
 	  return false;
 	}
 
-  timevar_pop (TV_GRAPHITE_DATA_DEPS);
   return true;
 }
 
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index 2835311..10e9fc0 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -1028,6 +1028,10 @@  new_scop (void *region)
 
   SCOP_CONTEXT (scop) = NULL;
   scop->context = NULL;
+  scop->must_deps = NULL;
+  scop->may_deps = NULL;
+  scop->must_no_source = NULL;
+  scop->may_no_source = NULL;
   scop_set_region (scop, region);
   SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
   SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
@@ -1057,6 +1061,10 @@  free_scop (scop_p scop)
     ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
 
   isl_set_free (scop->context);
+  isl_union_map_free (scop->must_deps);
+  isl_union_map_free (scop->may_deps);
+  isl_union_map_free (scop->must_no_source);
+  isl_union_map_free (scop->may_no_source);
   htab_delete (SCOP_ORIGINAL_PDDRS (scop));
   free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
   free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index bf537b1..5ae7fad 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -1436,6 +1436,9 @@  struct scop
   /* The context used internally by ISL.  */
   isl_ctx *ctx;
 
+  /* The original dependence information.  */
+  isl_union_map *must_deps, *may_deps, *must_no_source, *may_no_source;
+
   /* A hashtable of the data dependence relations for the original
      scattering.  */
   htab_t original_pddrs;
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
index cf62033..53809b5 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-14.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
@@ -54,6 +54,5 @@  main (void)
   return 0;
 }
 
-/* PRE destroys the perfect nest and we can't cope with that yet.  */
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-15.c b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
index ee7aed6..9eeef66 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-15.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
@@ -48,7 +48,6 @@  main (void)
   return 0;
 }
 
-/* PRE destroys the perfect nest and we can't cope with that yet.  */
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
 
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-8.c b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
index ca99dbc..120a83c 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
@@ -82,5 +82,5 @@  main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "graphite" } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 4 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
index 11f8b2a..ee262e9 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
@@ -58,7 +58,6 @@  main (void)
   return 0;
 }
 
-/* PRE destroys the perfect nest and we can't cope with that yet.  */
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */