/* Returns a polyhedron of dimension DIM.
- Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET0
+ Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET
and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */
static ppl_Pointset_Powerset_C_Polyhedron_t
}
}
-/* Build the dependence polyhedron for data references PDR1 and PDR2. */
+/* Build the dependence polyhedron for data references PDR1 and PDR2.
+ The layout of the dependence polyhedron is:
+
+ T1|I1|T2|I2|S1|S2|G
+
+ with
+ | T1 and T2 the scattering dimensions for PDR1 and PDR2
+ | I1 and I2 the iteration domains
+ | S1 and S2 the subscripts
+ | G the global parameters. */
static poly_ddr_p
dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2,
graphite_dim_t gdim = scop_nb_params (scop);
graphite_dim_t dim1 = pdr_dim (pdr1);
graphite_dim_t dim2 = pdr_dim (pdr2);
- graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2;
+ graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim;
ppl_Pointset_Powerset_C_Polyhedron_t res;
ppl_Pointset_Powerset_C_Polyhedron_t id1, id2, isc1, isc2, idr1, idr2;
ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
+ ppl_Pointset_Powerset_C_Polyhedron_t context;
gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
+
+ ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+ (&context, SCOP_CONTEXT (scop));
+ ppl_insert_dimensions_pointset (context, 0, dim - gdim);
+
ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, s1);
ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, s2);
dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, context);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, id2);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (context);
ppl_delete_Pointset_Powerset_C_Polyhedron (id1);
ppl_delete_Pointset_Powerset_C_Polyhedron (id2);
ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2);
/* Returns the PDDR corresponding to the original schedule, or NULL if
- the dependence relation is empty or unknown (Can't judge dependency
- under polyhedral model. */
+ the dependence relation is empty or unknown (cannot judge dependency
+ under polyhedral model). */
static poly_ddr_p
pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
return pddr;
}
+/* Returns the PDDR corresponding to the transformed schedule, or NULL if
+ the dependence relation is empty or unknown (cannot judge dependency
+ under polyhedral model). */
+
+static poly_ddr_p
+pddr_transformed_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
+ poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ poly_ddr_p pddr;
+ ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
+ ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
+ ppl_Polyhedron_t st1 = PBB_ORIGINAL_SCATTERING (pbb1);
+ ppl_Polyhedron_t st2 = PBB_ORIGINAL_SCATTERING (pbb2);
+
+ if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
+ || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
+ || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
+ return NULL;
+
+ pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
+ true, false);
+ if (pddr_is_empty (pddr))
+ return NULL;
+
+ return pddr;
+}
+
+
+/* Return true when the data dependence relation between the data
+ references PDR1 belonging to PBB1 and PDR2 is part of a
+ reduction. */
+
+static inline bool
+reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ int i;
+ poly_dr_p pdr;
+
+ for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
+ if (PDR_TYPE (pdr) == PDR_WRITE)
+ break;
+
+ return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
+}
+
+/* Return true when the data dependence relation between the data
+ references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
+ part of a reduction. */
+
+static inline bool
+reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
+ poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ if (PBB_IS_REDUCTION (pbb1))
+ return reduction_dr_1 (pbb1, pdr1, pdr2);
+
+ if (PBB_IS_REDUCTION (pbb2))
+ return reduction_dr_1 (pbb2, pdr2, pdr1);
+
+ return false;
+}
+
/* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
functions. */
ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
+ if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
+ return true;
+
pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
if (!pddr)
return true;
part of a reduction. */
static inline bool
-reduction_ddr (poly_bb_p pbb1, poly_bb_p pbb2)
+reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
{
return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
}
if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
pbb_remove_duplicate_pdrs (pbb2);
- if (reduction_ddr (pbb1, pbb2))
+ if (reduction_ddr_p (pbb1, pbb2))
return true;
for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
return false;
}
-/* Pretty print to FILE all the data dependences of SCoP in DOT
- format. */
+/* Pretty print to FILE all the original data dependences of SCoP in
+ DOT format. */
static void
-dot_deps_1 (FILE *file, scop_p scop)
+dot_original_deps_stmt_1 (FILE *file, scop_p scop)
{
int i, j, k, l;
poly_bb_p pbb1, pbb2;
poly_dr_p pdr1, pdr2;
+ for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
+ for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
+ {
+ for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
+ for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
+ if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2))
+ {
+ fprintf (file, "OS%d -> OS%d\n",
+ pbb_index (pbb1), pbb_index (pbb2));
+ goto done;
+ }
+ done:;
+ }
+}
+
+/* Pretty print to FILE all the transformed data dependences of SCoP in
+ DOT format. */
+
+static void
+dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
+{
+ int i, j, k, l;
+ poly_bb_p pbb1, pbb2;
+ poly_dr_p pdr1, pdr2;
+
+ for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
+ for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
+ {
+ for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
+ for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
+ if (pddr_transformed_scattering (pbb1, pbb2, pdr1, pdr2))
+ {
+ fprintf (file, "TS%d -> TS%d\n",
+ pbb_index (pbb1), pbb_index (pbb2));
+ goto done;
+ }
+ done:;
+ }
+}
+
+
+/* Pretty print to FILE all the data dependences of SCoP in DOT
+ format. */
+
+static void
+dot_deps_stmt_1 (FILE *file, scop_p scop)
+{
fputs ("digraph all {\n", file);
+ dot_original_deps_stmt_1 (file, scop);
+ dot_transformed_deps_stmt_1 (file, scop);
+
+ fputs ("}\n\n", file);
+}
+
+/* Pretty print to FILE all the original data dependences of SCoP in
+ DOT format. */
+
+static void
+dot_original_deps (FILE *file, scop_p scop)
+{
+ int i, j, k, l;
+ poly_bb_p pbb1, pbb2;
+ poly_dr_p pdr1, pdr2;
+
for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
if (pddr_original_scattering (pbb1, pbb2, pdr1, pdr2))
- fprintf (file, "S%d_D%d -> S%d_D%d\n",
+ fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
pbb_index (pbb1), PDR_ID (pdr1),
pbb_index (pbb2), PDR_ID (pdr2));
+}
+
+/* Pretty print to FILE all the transformed data dependences of SCoP in
+ DOT format. */
+
+static void
+dot_transformed_deps (FILE *file, scop_p scop)
+{
+ int i, j, k, l;
+ poly_bb_p pbb1, pbb2;
+ poly_dr_p pdr1, pdr2;
+
+ for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
+ for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
+ for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
+ for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
+ if (pddr_transformed_scattering (pbb1, pbb2, pdr1, pdr2))
+ fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
+ pbb_index (pbb1), PDR_ID (pdr1),
+ pbb_index (pbb2), PDR_ID (pdr2));
+}
+
+/* Pretty print to FILE all the data dependences of SCoP in DOT
+ format. */
+
+static void
+dot_deps_1 (FILE *file, scop_p scop)
+{
+ fputs ("digraph all {\n", file);
+
+ dot_original_deps (file, scop);
+ dot_transformed_deps (file, scop);
fputs ("}\n\n", file);
}
#endif
}
+/* Display all the statement dependences in SCoP using dotty. */
+
+void
+dot_deps_stmt (scop_p scop)
+{
+ /* When debugging, enable the following code. This cannot be used
+ in production compilers because it calls "system". */
+#if 0
+ int x;
+ FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
+ gcc_assert (stream);
+
+ dot_deps_stmt_1 (stream, scop);
+ fclose (stream);
+
+ x = system ("dotty /tmp/scopdeps.dot");
+#else
+ dot_deps_stmt_1 (stderr, scop);
+#endif
+}
#endif
OSDN Git Service
