/* Data dependence analysis for Graphite.
- Copyright (C) 2009-2015 Free Software Foundation, Inc.
+ Copyright (C) 2009-2020 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@amd.com> and
Konrad Trifunovic <konrad.trifunovic@inria.fr>.
s = isl_set_set_tuple_id (s, id);
isl_space_free (d);
- return isl_map_intersect_domain (map, s);
+ return isl_map_coalesce (isl_map_intersect_domain (map, s));
}
/* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */
{
isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
isl_set_copy (pdr->subscript_sizes));
- x = constrain_domain (x, isl_set_copy (pbb->domain));
- return x;
+ x = isl_map_coalesce (x);
+ return constrain_domain (x, isl_set_copy (pbb->domain));
}
-/* Returns all the memory reads in SCOP. */
+/* Returns an isl description of all memory operations in SCOP. The memory
+ reads are returned in READS and writes in MUST_WRITES and MAY_WRITES. */
-static isl_union_map *
-scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
+static void
+scop_get_reads_and_writes (scop_p scop, isl_union_map *&reads,
+ isl_union_map *&must_writes,
+ isl_union_map *&may_writes)
{
int i, j;
poly_bb_p pbb;
poly_dr_p pdr;
- isl_space *space = isl_set_get_space (scop->param_context);
- isl_union_map *res = isl_union_map_empty (space);
- FOR_EACH_VEC_ELT (pbbs, i, pbb)
+ FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
{
- FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
if (pdr_read_p (pdr))
{
if (dump_file)
fprintf (dump_file, "Adding read to depedence graph: ");
print_pdr (dump_file, pdr);
}
- res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+ isl_union_map *um
+ = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
+ reads = isl_union_map_union (reads, um);
if (dump_file)
{
fprintf (dump_file, "Reads depedence graph: ");
- print_isl_union_map (dump_file, res);
+ print_isl_union_map (dump_file, reads);
}
}
- }
-
- return res;
-}
-
-/* Returns all the memory must writes in SCOP. */
-
-static isl_union_map *
-scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
-{
- int i, j;
- poly_bb_p pbb;
- poly_dr_p pdr;
- isl_space *space = isl_set_get_space (scop->param_context);
- isl_union_map *res = isl_union_map_empty (space);
-
- FOR_EACH_VEC_ELT (pbbs, i, pbb)
- {
- FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
- if (pdr_write_p (pdr))
+ else if (pdr_write_p (pdr))
{
if (dump_file)
{
fprintf (dump_file, "Adding must write to depedence graph: ");
print_pdr (dump_file, pdr);
}
- res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+ isl_union_map *um
+ = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
+ must_writes = isl_union_map_union (must_writes, um);
if (dump_file)
{
fprintf (dump_file, "Must writes depedence graph: ");
- print_isl_union_map (dump_file, res);
+ print_isl_union_map (dump_file, must_writes);
}
}
- }
-
- return res;
-}
-
-/* Returns all the memory may writes in SCOP. */
-
-static isl_union_map *
-scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
-{
- int i, j;
- poly_bb_p pbb;
- poly_dr_p pdr;
- isl_space *space = isl_set_get_space (scop->param_context);
- isl_union_map *res = isl_union_map_empty (space);
-
- FOR_EACH_VEC_ELT (pbbs, i, pbb)
- {
- FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
- if (pdr_may_write_p (pdr))
+ else if (pdr_may_write_p (pdr))
{
if (dump_file)
{
fprintf (dump_file, "Adding may write to depedence graph: ");
print_pdr (dump_file, pdr);
}
- res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+ isl_union_map *um
+ = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
+ may_writes = isl_union_map_union (may_writes, um);
if (dump_file)
{
fprintf (dump_file, "May writes depedence graph: ");
- print_isl_union_map (dump_file, res);
+ print_isl_union_map (dump_file, may_writes);
}
}
+ }
}
-
- return res;
-}
-
-/* Returns all the original schedules in SCOP. */
-
-static isl_union_map *
-scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
-{
- int i;
- poly_bb_p pbb;
- isl_space *space = isl_set_get_space (scop->param_context);
- isl_union_map *res = isl_union_map_empty (space);
-
- FOR_EACH_VEC_ELT (pbbs, i, pbb)
- {
- res = isl_union_map_add_map
- (res, constrain_domain (isl_map_copy (pbb->schedule),
- isl_set_copy (pbb->domain)));
- }
-
- return res;
}
/* Helper function used on each MAP of a isl_union_map. Computes the
str.umap = isl_union_map_empty (isl_union_map_get_space (x));
isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
isl_union_map_free (x);
- return str.umap;
+ return isl_union_map_coalesce (str.umap);
}
/* Applies SCHEDULE to the in and out dimensions of the dependences
apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
__isl_keep isl_union_map *deps)
{
- isl_map *x;
- isl_union_map *ux, *trans;
-
- trans = isl_union_map_copy (schedule);
- trans = extend_schedule (trans);
- ux = isl_union_map_copy (deps);
+ isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
+ isl_union_map *ux = isl_union_map_copy (deps);
ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
ux = isl_union_map_apply_range (ux, trans);
- if (isl_union_map_is_empty (ux))
- {
- isl_union_map_free (ux);
- return NULL;
- }
- x = isl_map_from_union_map (ux);
+ ux = isl_union_map_coalesce (ux);
- return x;
+ if (!isl_union_map_is_empty (ux))
+ return isl_map_from_union_map (ux);
+
+ isl_union_map_free (ux);
+ return NULL;
}
/* Return true when DEPS is non empty and the intersection of LEX with
__isl_keep isl_union_map *deps,
int depth)
{
- bool res;
- int i;
- isl_space *space;
- isl_map *lex, *x;
- isl_constraint *ineq;
-
if (isl_union_map_is_empty (deps))
return false;
- x = apply_schedule_on_deps (schedule, deps);
+ isl_map *x = apply_schedule_on_deps (schedule, deps);
if (x == NULL)
return false;
- space = isl_map_get_space (x);
- space = isl_space_range (space);
- lex = isl_map_lex_le (space);
- space = isl_map_get_space (x);
- ineq = isl_inequality_alloc (isl_local_space_from_space (space));
- for (i = 0; i < depth - 1; i++)
+ isl_space *space = isl_map_get_space (x);
+ isl_map *lex = isl_map_lex_le (isl_space_range (space));
+ isl_constraint *ineq = isl_inequality_alloc
+ (isl_local_space_from_space (isl_map_get_space (x)));
+
+ for (int i = 0; i < depth - 1; i++)
lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
/* in + 1 <= out */
ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
ineq = isl_constraint_set_constant_si (ineq, -1);
lex = isl_map_add_constraint (lex, ineq);
+ lex = isl_map_coalesce (lex);
x = isl_map_intersect (x, lex);
- res = !isl_map_is_empty (x);
+ bool res = !isl_map_is_empty (x);
isl_map_free (x);
return res;
}
-/* Compute the original data dependences in SCOP for all the reads and
- writes in PBBS. */
+/* Compute the dependence relations for the SCOP:
+ RAW are read after write dependences,
+ WAR are write after read dependences,
+ WAW are write after write dependences. */
-static void
-compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
- isl_union_map **must_raw,
- isl_union_map **may_raw,
- isl_union_map **must_raw_no_source,
- isl_union_map **may_raw_no_source,
- isl_union_map **must_war,
- isl_union_map **may_war,
- isl_union_map **must_war_no_source,
- isl_union_map **may_war_no_source,
- isl_union_map **must_waw,
- isl_union_map **may_waw,
- isl_union_map **must_waw_no_source,
- isl_union_map **may_waw_no_source)
+void
+scop_get_dependences (scop_p scop)
{
- isl_union_map *reads = scop_get_reads (scop, pbbs);
- isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
- isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
- isl_union_map *all_writes = isl_union_map_union
- (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
- isl_space *space = isl_union_map_get_space (all_writes);
- isl_union_map *empty = isl_union_map_empty (space);
- isl_union_map *original = scop_get_original_schedule (scop, pbbs);
+ if (scop->dependence)
+ return;
+
+ isl_space *space = isl_set_get_space (scop->param_context);
+ isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
+ isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
+ isl_union_map *may_writes = isl_union_map_empty (space);
+ scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
if (dump_file)
{
print_isl_union_map (dump_file, must_writes);
fprintf (dump_file, " may_writes: ");
print_isl_union_map (dump_file, may_writes);
- fprintf (dump_file, " all_writes: ");
- print_isl_union_map (dump_file, all_writes);
fprintf (dump_file, ")\n");
}
- isl_union_map_compute_flow (isl_union_map_copy (reads),
- isl_union_map_copy (must_writes),
- isl_union_map_copy (may_writes),
- isl_union_map_copy (original),
- must_raw, may_raw, must_raw_no_source,
- may_raw_no_source);
- isl_union_map_compute_flow (isl_union_map_copy (all_writes),
- reads, empty,
- isl_union_map_copy (original),
- must_war, may_war, must_war_no_source,
- may_war_no_source);
- isl_union_map_compute_flow (all_writes, must_writes, may_writes,
- original,
- must_waw, may_waw, must_waw_no_source,
- may_waw_no_source);
-}
-
-isl_union_map *
-scop_get_dependences (scop_p scop)
-{
- if (scop->dependence)
- return scop->dependence;
-
- /* The original dependence relations:
- RAW are read after write dependences,
- WAR are write after read dependences,
- WAW are write after write dependences. */
- isl_union_map *must_raw = NULL, *may_raw = NULL, *must_raw_no_source = NULL,
- *may_raw_no_source = NULL, *must_war = NULL, *may_war = NULL,
- *must_war_no_source = NULL, *may_war_no_source = NULL, *must_waw = NULL,
- *may_waw = NULL, *must_waw_no_source = NULL, *may_waw_no_source = NULL;
-
- compute_deps (scop, scop->pbbs,
- &must_raw, &may_raw,
- &must_raw_no_source, &may_raw_no_source,
- &must_war, &may_war,
- &must_war_no_source, &may_war_no_source,
- &must_waw, &may_waw,
- &must_waw_no_source, &may_waw_no_source);
-
- isl_union_map *dependences = must_raw;
- dependences = isl_union_map_union (dependences, must_war);
- dependences = isl_union_map_union (dependences, must_waw);
- dependences = isl_union_map_union (dependences, may_raw);
- dependences = isl_union_map_union (dependences, may_war);
- dependences = isl_union_map_union (dependences, may_waw);
+ gcc_assert (scop->original_schedule);
+
+ isl_union_access_info *ai;
+ ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
+ ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
+ ai = isl_union_access_info_set_may_source (ai, may_writes);
+ ai = isl_union_access_info_set_schedule
+ (ai, isl_schedule_copy (scop->original_schedule));
+ isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
+ isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
+ isl_union_flow_free (flow);
+
+ ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
+ ai = isl_union_access_info_set_must_source (ai, must_writes);
+ ai = isl_union_access_info_set_may_source (ai, reads);
+ ai = isl_union_access_info_set_schedule
+ (ai, isl_schedule_copy (scop->original_schedule));
+ flow = isl_union_access_info_compute_flow (ai);
+
+ isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
+ isl_union_map *war = isl_union_flow_get_may_dependence (flow);
+ war = isl_union_map_subtract (war, isl_union_map_copy (waw));
+ isl_union_flow_free (flow);
+
+ raw = isl_union_map_coalesce (raw);
+ waw = isl_union_map_coalesce (waw);
+ war = isl_union_map_coalesce (war);
+
+ isl_union_map *dependences = raw;
+ dependences = isl_union_map_union (dependences, war);
+ dependences = isl_union_map_union (dependences, waw);
+ dependences = isl_union_map_coalesce (dependences);
if (dump_file)
{
fprintf (dump_file, ")\n");
}
- isl_union_map_free (must_raw_no_source);
- isl_union_map_free (may_raw_no_source);
- isl_union_map_free (must_war_no_source);
- isl_union_map_free (may_war_no_source);
- isl_union_map_free (must_waw_no_source);
- isl_union_map_free (may_waw_no_source);
-
scop->dependence = dependences;
- return dependences;
}
#endif /* HAVE_isl */
projects / thirdparty / gcc.git / blobdiff