@@ -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;
}
@@ -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));
@@ -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;
@@ -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" } } */
@@ -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" } } */
@@ -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" } } */
@@ -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" } } */