/* Data dependence analysis for Graphite.
- Copyright (C) 2009 Free Software Foundation, Inc.
+ Copyright (C) 2009, 2010 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@amd.com> and
Konrad Trifunovic <konrad.trifunovic@inria.fr>.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "tree.h"
-#include "rtl.h"
-#include "basic-block.h"
-#include "diagnostic.h"
#include "tree-flow.h"
-#include "toplev.h"
#include "tree-dump.h"
-#include "timevar.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
-#include "tree-pass.h"
-#include "domwalk.h"
-#include "pointer-set.h"
-#include "gimple.h"
+#include "sese.h"
#ifdef HAVE_cloog
-#include "cloog/cloog.h"
#include "ppl_c.h"
-#include "sese.h"
#include "graphite-ppl.h"
-#include "graphite.h"
#include "graphite-poly.h"
#include "graphite-dependences.h"
-
-/* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is
- the source data reference, SINK is the sink data reference. SOURCE
- and SINK define an edge in the Data Dependence Graph (DDG). */
-
-static poly_ddr_p
-new_poly_ddr (poly_dr_p source, poly_dr_p sink,
- ppl_Pointset_Powerset_C_Polyhedron_t ddp)
-{
- poly_ddr_p pddr;
-
- pddr = XNEW (struct poly_ddr);
- PDDR_SOURCE (pddr) = source;
- PDDR_SINK (pddr) = sink;
- PDDR_DDP (pddr) = ddp;
- PDDR_KIND (pddr) = unknown_dependence;
-
- return pddr;
-}
-
-/* Free the poly_ddr_p P. */
-
-void
-free_poly_ddr (void *p)
-{
- poly_ddr_p pddr = (poly_ddr_p) p;
- ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
- free (pddr);
-}
+#include "graphite-cloog-util.h"
/* Comparison function for poly_ddr hash table. */
static bool
pddr_is_empty (poly_ddr_p pddr)
{
- if (PDDR_KIND (pddr) != unknown_dependence)
- return PDDR_KIND (pddr) == no_dependence ? true : false;
+ if (!pddr)
+ return true;
+
+ gcc_assert (PDDR_KIND (pddr) != unknown_dependence);
+
+ return PDDR_KIND (pddr) == no_dependence ? true : false;
+}
+
+/* Prints to FILE the layout of the dependence polyhedron of PDDR:
+
+ T1|I1|T2|I2|S1|S2|G
+
+ with
+ | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
+ | I1 and I2 the iteration domains
+ | S1 and S2 the subscripts
+ | G the global parameters. */
+
+static void
+print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr)
+{
+ poly_dr_p pdr1 = PDDR_SOURCE (pddr);
+ poly_dr_p pdr2 = PDDR_SINK (pddr);
+ poly_bb_p pbb1 = PDR_PBB (pdr1);
+ poly_bb_p pbb2 = PDR_PBB (pdr2);
+
+ graphite_dim_t i;
+ graphite_dim_t tdim1 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
+ pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
+ graphite_dim_t tdim2 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
+ pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
+ graphite_dim_t idim1 = pbb_dim_iter_domain (pbb1);
+ graphite_dim_t idim2 = pbb_dim_iter_domain (pbb2);
+ graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
+ graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
+ graphite_dim_t gdim = scop_nb_params (PBB_SCOP (pbb1));
+
+ fprintf (file, "# eq");
+
+ for (i = 0; i < tdim1; i++)
+ fprintf (file, " t1_%d", (int) i);
+ for (i = 0; i < idim1; i++)
+ fprintf (file, " i1_%d", (int) i);
+ for (i = 0; i < tdim2; i++)
+ fprintf (file, " t2_%d", (int) i);
+ for (i = 0; i < idim2; i++)
+ fprintf (file, " i2_%d", (int) i);
+ for (i = 0; i < sdim1; i++)
+ fprintf (file, " s1_%d", (int) i);
+ for (i = 0; i < sdim2; i++)
+ fprintf (file, " s2_%d", (int) i);
+ for (i = 0; i < gdim; i++)
+ fprintf (file, " g_%d", (int) i);
+
+ fprintf (file, " cst\n");
+}
+
+/* Prints to FILE the poly_ddr_p PDDR. */
+
+void
+print_pddr (FILE *file, poly_ddr_p pddr)
+{
+ fprintf (file, "pddr (kind: ");
+
+ if (PDDR_KIND (pddr) == unknown_dependence)
+ fprintf (file, "unknown_dependence");
+ else if (PDDR_KIND (pddr) == no_dependence)
+ fprintf (file, "no_dependence");
+ else if (PDDR_KIND (pddr) == has_dependence)
+ fprintf (file, "has_dependence");
- if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PDDR_DDP (pddr)))
+ fprintf (file, "\n source ");
+ print_pdr (file, PDDR_SOURCE (pddr), 2);
+
+ fprintf (file, "\n sink ");
+ print_pdr (file, PDDR_SINK (pddr), 2);
+
+ if (PDDR_KIND (pddr) == has_dependence)
{
- PDDR_KIND (pddr) = no_dependence;
- return true;
+ fprintf (file, "\n dependence polyhedron (\n");
+ print_dependence_polyhedron_layout (file, pddr);
+ ppl_print_powerset_matrix (file, PDDR_DDP (pddr));
+ ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file, PDDR_DDP (pddr));
+ fprintf (file, ")\n");
}
- PDDR_KIND (pddr) = has_dependence;
- return false;
+ fprintf (file, ")\n");
}
-/* Returns a polyhedron of dimension DIM.
+/* Prints to STDERR the poly_ddr_p PDDR. */
- Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET0
- and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */
+DEBUG_FUNCTION void
+debug_pddr (poly_ddr_p pddr)
+{
+ print_pddr (stderr, pddr);
+}
-static ppl_Pointset_Powerset_C_Polyhedron_t
-map_into_dep_poly (graphite_dim_t dim, graphite_dim_t gdim,
- ppl_Pointset_Powerset_C_Polyhedron_t p,
- graphite_dim_t cut,
- graphite_dim_t offset)
+
+/* Remove all the dimensions except alias information at dimension
+ ALIAS_DIM. */
+
+static void
+build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
+ ppl_dimension_type alias_dim)
{
- ppl_Pointset_Powerset_C_Polyhedron_t res;
+ ppl_dimension_type *ds;
+ ppl_dimension_type access_dim;
+ unsigned i, pos;
+
+ ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
+ &access_dim);
+ ds = XNEWVEC (ppl_dimension_type, access_dim - 1);
+ gcc_assert (alias_dim < access_dim);
+
+ for (pos = 0, i = 0; i < access_dim; i++)
+ if (i != alias_dim)
+ ds[pos++] = i;
+
+ ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
+ ds,
+ access_dim - 1);
+ free (ds);
+}
+
+/* Return true when PDR1 and PDR2 may alias. */
+
+static bool
+poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
+ ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
+ ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
+ ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
+ ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
+ int empty_p;
ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
- (&res, p);
- ppl_insert_dimensions_pointset (res, 0, offset);
- ppl_insert_dimensions_pointset (res, offset + cut,
- dim - offset - cut - gdim);
+ (&alias_powerset1, accesses1);
+ ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+ (&alias_powerset2, accesses2);
- return res;
+ build_alias_set_powerset (alias_powerset1, alias_dim1);
+ build_alias_set_powerset (alias_powerset2, alias_dim2);
+
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
+ (alias_powerset1, alias_powerset2);
+
+ empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
+
+ ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
+
+ return !empty_p;
}
/* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
return res;
}
-/* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
-
-static ppl_Constraint_t
-build_pairwise_constraint (graphite_dim_t dim,
- graphite_dim_t pos1, graphite_dim_t pos2,
- int c, enum ppl_enum_Constraint_Type cstr_type)
-{
- ppl_Linear_Expression_t expr;
- ppl_Constraint_t cstr;
- ppl_Coefficient_t coef;
- Value v, v_op, v_c;
-
- value_init (v);
- value_init (v_op);
- value_init (v_c);
-
- value_set_si (v, 1);
- value_set_si (v_op, -1);
- value_set_si (v_c, c);
-
- ppl_new_Coefficient (&coef);
- ppl_new_Linear_Expression_with_dimension (&expr, dim);
-
- ppl_assign_Coefficient_from_mpz_t (coef, v);
- ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef);
- ppl_assign_Coefficient_from_mpz_t (coef, v_op);
- ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef);
- ppl_assign_Coefficient_from_mpz_t (coef, v_c);
- ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
-
- ppl_new_Constraint (&cstr, expr, cstr_type);
-
- ppl_delete_Linear_Expression (expr);
- ppl_delete_Coefficient (coef);
- value_clear (v);
- value_clear (v_op);
- value_clear (v_c);
-
- return cstr;
-}
-
/* Builds subscript equality constraints. */
static ppl_Pointset_Powerset_C_Polyhedron_t
dr_equality_constraints (graphite_dim_t dim,
graphite_dim_t pos, graphite_dim_t nb_subscripts)
{
- ppl_Polyhedron_t subscript_equalities;
+ ppl_Polyhedron_t eqs;
ppl_Pointset_Powerset_C_Polyhedron_t res;
- Value v, v_op;
graphite_dim_t i;
- value_init (v);
- value_init (v_op);
- value_set_si (v, 1);
- value_set_si (v_op, -1);
+ ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0);
- ppl_new_C_Polyhedron_from_space_dimension (&subscript_equalities, dim, 0);
for (i = 0; i < nb_subscripts; i++)
{
- ppl_Linear_Expression_t expr;
- ppl_Constraint_t cstr;
- ppl_Coefficient_t coef;
-
- ppl_new_Coefficient (&coef);
- ppl_new_Linear_Expression_with_dimension (&expr, dim);
-
- ppl_assign_Coefficient_from_mpz_t (coef, v);
- ppl_Linear_Expression_add_to_coefficient (expr, pos + i, coef);
- ppl_assign_Coefficient_from_mpz_t (coef, v_op);
- ppl_Linear_Expression_add_to_coefficient (expr, pos + i + nb_subscripts,
- coef);
-
- ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
- ppl_Polyhedron_add_constraint (subscript_equalities, cstr);
-
- ppl_delete_Linear_Expression (expr);
+ ppl_Constraint_t cstr
+ = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts,
+ 0, PPL_CONSTRAINT_TYPE_EQUAL);
+ ppl_Polyhedron_add_constraint (eqs, cstr);
ppl_delete_Constraint (cstr);
- ppl_delete_Coefficient (coef);
}
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
- (&res, subscript_equalities);
- value_clear (v);
- value_clear (v_op);
- ppl_delete_Polyhedron (subscript_equalities);
-
+ ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs);
+ ppl_delete_Polyhedron (eqs);
return res;
}
-/* Builds scheduling equality constraints. */
+/* Builds scheduling inequality constraints: when DIRECTION is
+ 1 builds a GE constraint,
+ 0 builds an EQ constraint,
+ -1 builds a LE constraint.
+ DIM is the dimension of the scheduling space.
+ POS and POS + OFFSET are the dimensions that are related. */
static ppl_Pointset_Powerset_C_Polyhedron_t
-build_pairwise_scheduling_equality (graphite_dim_t dim,
- graphite_dim_t pos, graphite_dim_t offset)
+build_pairwise_scheduling (graphite_dim_t dim,
+ graphite_dim_t pos,
+ graphite_dim_t offset,
+ int direction)
{
ppl_Pointset_Powerset_C_Polyhedron_t res;
ppl_Polyhedron_t equalities;
ppl_Constraint_t cstr;
+ graphite_dim_t a = pos;
+ graphite_dim_t b = pos + offset;
ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
- cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
- PPL_CONSTRAINT_TYPE_EQUAL);
+ switch (direction)
+ {
+ case 1:
+ /* Builds "a + 1 <= b. */
+ cstr = ppl_build_relation (dim, a, b, 1,
+ PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
+ break;
+
+ case 0:
+ /* Builds "a = b. */
+ cstr = ppl_build_relation (dim, a, b, 0,
+ PPL_CONSTRAINT_TYPE_EQUAL);
+ break;
+
+ case -1:
+ /* Builds "a >= b + 1. */
+ cstr = ppl_build_relation (dim, a, b, -1,
+ PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
ppl_Polyhedron_add_constraint (equalities, cstr);
ppl_delete_Constraint (cstr);
return res;
}
-/* Builds scheduling inequality constraints. */
+/* Add to a non empty polyhedron BAG the precedence constraints for
+ the lexicographical comparison of time vectors in BAG following the
+ lexicographical order. DIM is the dimension of the polyhedron BAG.
+ TDIM is the number of loops common to the two statements that are
+ compared lexicographically, i.e. the number of loops containing
+ both statements. OFFSET is the number of dimensions needed to
+ represent the first statement, i.e. dimT1 + dimI1 in the layout of
+ the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
+ 1, compute the direct dependence from PDR1 to PDR2, and when
+ DIRECTION is -1, compute the reversed dependence relation, from
+ PDR2 to PDR1. */
static ppl_Pointset_Powerset_C_Polyhedron_t
-build_pairwise_scheduling_inequality (graphite_dim_t dim,
- graphite_dim_t pos,
- graphite_dim_t offset,
- bool direction)
+build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
+ graphite_dim_t dim,
+ graphite_dim_t tdim,
+ graphite_dim_t offset,
+ int direction)
{
- ppl_Pointset_Powerset_C_Polyhedron_t res;
- ppl_Polyhedron_t equalities;
- ppl_Constraint_t cstr;
-
- ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
+ graphite_dim_t i;
+ ppl_Pointset_Powerset_C_Polyhedron_t res, lex;
- if (direction)
- cstr = build_pairwise_constraint (dim, pos, pos + offset, -1,
- PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
- else
- cstr = build_pairwise_constraint (dim, pos, pos + offset, 1,
- PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
+ ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
- ppl_Polyhedron_add_constraint (equalities, cstr);
- ppl_delete_Constraint (cstr);
+ lex = build_pairwise_scheduling (dim, 0, offset, direction);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
- ppl_delete_Polyhedron (equalities);
- return res;
-}
+ if (!ppl_powerset_is_empty (lex))
+ ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
-/* Returns true when adding the lexicographical constraints at level I
- to the RES dependence polyhedron returns an empty polyhedron. */
+ ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
-static bool
-lexicographically_gt_p (ppl_Pointset_Powerset_C_Polyhedron_t res,
- graphite_dim_t dim,
- graphite_dim_t offset,
- bool direction, graphite_dim_t i)
-{
- ppl_Pointset_Powerset_C_Polyhedron_t ineq;
- bool empty_p;
+ for (i = 0; i < tdim - 1; i++)
+ {
+ ppl_Pointset_Powerset_C_Polyhedron_t sceq;
- ineq = build_pairwise_scheduling_inequality (dim, i, offset,
- direction);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq, res);
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq);
- if (!empty_p)
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, ineq);
- ppl_delete_Pointset_Powerset_C_Polyhedron (ineq);
+ sceq = build_pairwise_scheduling (dim, i, offset, 0);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
- return !empty_p;
-}
+ if (ppl_powerset_is_empty (bag))
+ break;
-/* Build the precedence constraints for the lexicographical comparison
- of time vectors RES following the lexicographical order. */
+ lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
-static void
-build_lexicographically_gt_constraint (ppl_Pointset_Powerset_C_Polyhedron_t *res,
- graphite_dim_t dim,
- graphite_dim_t tdim1,
- graphite_dim_t offset,
- bool direction)
-{
- graphite_dim_t i;
+ if (!ppl_powerset_is_empty (lex))
+ ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
- if (lexicographically_gt_p (*res, dim, offset, direction, 0))
- return;
+ ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
+ }
- for (i = 0; i < tdim1 - 1; i++)
- {
- ppl_Pointset_Powerset_C_Polyhedron_t sceq;
+ return res;
+}
- sceq = build_pairwise_scheduling_equality (dim, i, offset);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, sceq);
- ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
+/* Build the dependence polyhedron for data references PDR1 and PDR2.
+ The layout of the dependence polyhedron is:
- if (lexicographically_gt_p (*res, dim, offset, direction, i + 1))
- return;
- }
+ T1|I1|T2|I2|S1|S2|G
- if (i == tdim1 - 1)
- {
- ppl_delete_Pointset_Powerset_C_Polyhedron (*res);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res, dim, 1);
- }
-}
+ 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.
-/* Build the dependence polyhedron for data references PDR1 and PDR2. */
+ When DIRECTION is set to 1, compute the direct dependence from PDR1
+ to PDR2, and when DIRECTION is -1, compute the reversed dependence
+ relation, from PDR2 to PDR1. */
-static poly_ddr_p
-dependence_polyhedron_1 (poly_bb_p pbb1, poly_bb_p pbb2,
- ppl_Pointset_Powerset_C_Polyhedron_t d1,
- ppl_Pointset_Powerset_C_Polyhedron_t d2,
- poly_dr_p pdr1, poly_dr_p pdr2,
- ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
- bool direction,
- bool original_scattering_p)
+static ppl_Pointset_Powerset_C_Polyhedron_t
+dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
+ int direction, bool original_scattering_p)
{
+ poly_bb_p pbb1 = PDR_PBB (pdr1);
+ poly_bb_p pbb2 = PDR_PBB (pdr2);
scop_p scop = PBB_SCOP (pbb1);
graphite_dim_t tdim1 = original_scattering_p ?
pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
+ graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
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 idr1, idr2;
ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
+ ppl_Pointset_Powerset_C_Polyhedron_t lex;
gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, s1);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, s2);
- id1 = map_into_dep_poly (dim, gdim, d1, ddim1, tdim1);
- id2 = map_into_dep_poly (dim, gdim, d2, ddim2, tdim1 + ddim1 + tdim2);
- isc1 = map_into_dep_poly (dim, gdim, sc1, ddim1 + tdim1, 0);
- isc2 = map_into_dep_poly (dim, gdim, sc2, ddim2 + tdim2, tdim1 + ddim1);
+ combine_context_id_scat (&sc1, pbb1, original_scattering_p);
+ combine_context_id_scat (&sc2, pbb2, original_scattering_p);
+
+ ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1,
+ tdim2 + ddim2 + sdim1 + sdim2);
+
+ ppl_insert_dimensions_pointset (sc2, 0, tdim1 + ddim1);
+ ppl_insert_dimensions_pointset (sc2, tdim1 + ddim1 + tdim2 + ddim2,
+ sdim1 + sdim2);
idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
tdim1, tdim2 + ddim2);
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, 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, isc2);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc1);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc2);
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 (id1);
- ppl_delete_Pointset_Powerset_C_Polyhedron (id2);
ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
- ppl_delete_Pointset_Powerset_C_Polyhedron (isc1);
- ppl_delete_Pointset_Powerset_C_Polyhedron (isc2);
ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
- build_lexicographically_gt_constraint (&res, dim, MIN (tdim1, tdim2),
- tdim1 + ddim1, direction);
+ if (ppl_powerset_is_empty (res))
+ return NULL;
+
+ lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
+ tdim1 + ddim1, direction);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (res);
- return new_poly_ddr (pdr1, pdr2, res);
+ return lex;
}
/* Build the dependence polyhedron for data references PDR1 and PDR2.
- If possible use already cached information. */
+ If possible use already cached information.
+
+ When DIRECTION is set to 1, compute the direct dependence from PDR1
+ to PDR2, and when DIRECTION is -1, compute the reversed dependence
+ relation, from PDR2 to PDR1. */
static poly_ddr_p
-dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2,
- ppl_Pointset_Powerset_C_Polyhedron_t d1,
- ppl_Pointset_Powerset_C_Polyhedron_t d2,
- poly_dr_p pdr1, poly_dr_p pdr2,
- ppl_Polyhedron_t s1, ppl_Polyhedron_t s2,
- bool direction,
- bool original_scattering_p)
+new_poly_ddr (poly_dr_p pdr1, poly_dr_p pdr2,
+ int direction, bool original_scattering_p)
{
PTR *x = NULL;
poly_ddr_p res;
+ bool may_alias;
+ /* Return the PDDR from the cache if it already has been computed. */
if (original_scattering_p)
{
struct poly_ddr tmp;
+ scop_p scop = PBB_SCOP (PDR_PBB (pdr1));
tmp.source = pdr1;
tmp.sink = pdr2;
- x = htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1)),
+ x = htab_find_slot (SCOP_ORIGINAL_PDDRS (scop),
&tmp, INSERT);
if (x && *x)
return (poly_ddr_p) *x;
}
- res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2,
- s1, s2, direction, original_scattering_p);
+ res = XNEW (struct poly_ddr);
+ PDDR_SOURCE (res) = pdr1;
+ PDDR_SINK (res) = pdr2;
+ PDDR_DDP (res) = NULL;
+ PDDR_ORIGINAL_SCATTERING_P (res) = original_scattering_p;
+ PDDR_KIND (res) = unknown_dependence;
+
+ may_alias = poly_drs_may_alias_p (pdr1, pdr2);
+
+ if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
+ && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
+ && may_alias)
+ PDDR_KIND (res) = unknown_dependence;
+
+ else if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
+ && same_pdr_p (pdr1, pdr2)
+ && may_alias)
+ {
+ PDDR_DDP (res) = dependence_polyhedron (pdr1, pdr2, direction,
+ original_scattering_p);
+ if (PDDR_DDP (res))
+ PDDR_KIND (res) = has_dependence;
+ else
+ PDDR_KIND (res) = no_dependence;
+ }
+ else
+ PDDR_KIND (res) = no_dependence;
if (original_scattering_p)
*x = res;
return res;
}
-/* Returns the PDDR corresponding to the original schedule, or NULL if
- the dependence relation is empty. */
+/* Free the data dependence relation poly_ddr_p P. */
-static poly_ddr_p
-pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
- poly_dr_p pdr1, poly_dr_p pdr2)
+void
+free_poly_ddr (void *p)
{
- 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 so1 = PBB_ORIGINAL_SCATTERING (pbb1);
- ppl_Polyhedron_t so2 = PBB_ORIGINAL_SCATTERING (pbb2);
-
- if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
- || (pdr_read_p (pdr1) && pdr_read_p (pdr2)))
- return NULL;
+ poly_ddr_p pddr = (poly_ddr_p) p;
+ ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
+ free (pddr);
+}
- pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
- true, true);
- if (pddr_is_empty (pddr))
- return NULL;
+/* 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_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr)
+ if (PDR_TYPE (pdr) == PDR_WRITE
+ && same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2))
+ return true;
+
+ return false;
+}
+
+/* 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_dr_p pdr1, poly_dr_p pdr2)
+{
+ poly_bb_p pbb1 = PDR_PBB (pdr1);
+ poly_bb_p pbb2 = PDR_PBB (pdr2);
- return pddr;
+ 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
functions. */
static bool
-graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
- poly_dr_p pdr1, poly_dr_p pdr2)
+graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
{
- ppl_Polyhedron_t st1, st2;
ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
- ppl_Pointset_Powerset_C_Polyhedron_t temp;
+ ppl_Pointset_Powerset_C_Polyhedron_t po_temp;
ppl_dimension_type pdim;
bool is_empty_p;
- poly_ddr_p pddr;
- ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
- ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
+ poly_ddr_p opddr, tpddr;
+ poly_bb_p pbb1, pbb2;
- pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
- if (!pddr)
+ if (reduction_dr_p (pdr1, pdr2))
return true;
- po = PDDR_DDP (pddr);
+ /* We build the reverse dependence relation for the transformed
+ scattering, such that when we intersect it with the original PO,
+ we get an empty intersection when the transform is legal:
+ i.e. the transform should reverse no dependences, and so PT, the
+ reversed transformed PDDR, should have no constraint from PO. */
+ opddr = new_poly_ddr (pdr1, pdr2, 1, true);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nloop carries dependency.\n");
+ if (PDDR_KIND (opddr) == unknown_dependence)
+ return false;
+
+ /* There are no dependences between PDR1 and PDR2 in the original
+ version of the program, or after the transform, so the
+ transform is legal. */
+ if (pddr_is_empty (opddr))
+ return true;
+
+ tpddr = new_poly_ddr (pdr1, pdr2, -1, false);
+
+ if (PDDR_KIND (tpddr) == unknown_dependence)
+ {
+ free_poly_ddr (tpddr);
+ return false;
+ }
+
+ if (pddr_is_empty (tpddr))
+ {
+ free_poly_ddr (tpddr);
+ return true;
+ }
+
+ po = PDDR_DDP (opddr);
+ pt = PDDR_DDP (tpddr);
+
+ /* Copy PO into PO_TEMP, such that PO is not destroyed. PO is
+ stored in a cache and should not be modified or freed. */
+ ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
+ ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp,
+ pdim, 0);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, po);
- st1 = PBB_TRANSFORMED_SCATTERING (pbb1);
- st2 = PBB_TRANSFORMED_SCATTERING (pbb2);
+ /* Extend PO and PT to have the same dimensions. */
+ pbb1 = PDR_PBB (pdr1);
+ pbb2 = PDR_PBB (pdr2);
ddim1 = pbb_dim_iter_domain (pbb1);
otdim1 = pbb_nb_scattering_orig (pbb1);
otdim2 = pbb_nb_scattering_orig (pbb2);
ttdim1 = pbb_nb_scattering_transform (pbb1);
ttdim2 = pbb_nb_scattering_transform (pbb2);
-
- /* Copy the PO polyhedron into the TEMP, so it is not destroyed.
- Keep in mind, that PO polyhedron might be restored from the cache
- and should not be modified! */
- ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&temp, pdim, 0);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, po);
-
- pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
- false, false);
- pt = PDDR_DDP (pddr);
-
- /* Extend PO and PT to have the same dimensions. */
- ppl_insert_dimensions_pointset (temp, otdim1, ttdim1);
- ppl_insert_dimensions_pointset (temp, otdim1 + ttdim1 + ddim1 + otdim2, ttdim2);
+ ppl_insert_dimensions_pointset (po_temp, otdim1, ttdim1);
+ ppl_insert_dimensions_pointset (po_temp, otdim1 + ttdim1 + ddim1 + otdim2,
+ ttdim2);
ppl_insert_dimensions_pointset (pt, 0, otdim1);
ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (temp, pt);
- is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
+ is_empty_p = ppl_powerset_is_empty (po_temp);
- ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
- free_poly_ddr (pddr);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
+ free_poly_ddr (tpddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nloop carries dependency.\n");
return is_empty_p;
}
+/* Return true when the data dependence relation for PBB1 and PBB2 is
+ part of a reduction. */
+
+static inline bool
+reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
+{
+ return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
+}
+
/* Iterates over the data references of PBB1 and PBB2 and detect
whether the transformed schedule is correct. */
if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
pbb_remove_duplicate_pdrs (pbb2);
- for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
- for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
- if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
+ if (reduction_ddr_p (pbb1, pbb2))
+ return true;
+
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2)
+ if (!graphite_legal_transform_dr (pdr1, pdr2))
return false;
return true;
timevar_push (TV_GRAPHITE_DATA_DEPS);
- 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_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))
{
timevar_pop (TV_GRAPHITE_DATA_DEPS);
return true;
}
-/* Remove all the dimensions except alias information at dimension
- ALIAS_DIM. */
-
-static void
-build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
- ppl_dimension_type alias_dim)
-{
- ppl_dimension_type *ds;
- ppl_dimension_type access_dim;
- unsigned i, pos = 0;
-
- ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
- &access_dim);
- ds = XNEWVEC (ppl_dimension_type, access_dim-1);
- for (i = 0; i < access_dim; i++)
- {
- if (i == alias_dim)
- continue;
-
- ds[pos] = i;
- pos++;
- }
-
- ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
- ds,
- access_dim - 1);
- free (ds);
-}
-
-/* Return true when PDR1 and PDR2 may alias. */
-
-static bool
-poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
-{
- ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
- ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
- ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
- ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
- ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
- int empty_p;
-
- ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
- (&alias_powerset1, accesses1);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
- (&alias_powerset2, accesses2);
-
- build_alias_set_powerset (alias_powerset1, alias_dim1);
- build_alias_set_powerset (alias_powerset2, alias_dim2);
-
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
- (alias_powerset1, alias_powerset2);
-
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
-
- ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
- ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
-
- return !empty_p;
-}
-
/* Returns TRUE when the dependence polyhedron between PDR1 and
PDR2 represents a loop carried dependence at level LEVEL. */
graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
int level)
{
- poly_bb_p pbb1 = PDR_PBB (pdr1);
- poly_bb_p pbb2 = PDR_PBB (pdr2);
- ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
- ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
- ppl_Polyhedron_t so1 = PBB_TRANSFORMED_SCATTERING (pbb1);
- ppl_Polyhedron_t so2 = PBB_TRANSFORMED_SCATTERING (pbb2);
ppl_Pointset_Powerset_C_Polyhedron_t po;
ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
- graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
- graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
+ poly_bb_p pbb = PDR_PBB (pdr1);
+ graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb);
+ graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb);
ppl_dimension_type dim;
bool empty_p;
- poly_ddr_p pddr;
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false);
+ graphite_dim_t pos;
- if ((PDR_TYPE (pdr1) == PDR_READ && PDR_TYPE (pdr2) == PDR_READ)
- || !poly_drs_may_alias_p (pdr1, pdr2))
- return false;
-
- if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
- return true;
-
- pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
- true, false);
+ if (PDDR_KIND (pddr) == unknown_dependence)
+ {
+ free_poly_ddr (pddr);
+ return true;
+ }
if (pddr_is_empty (pddr))
- return false;
+ {
+ free_poly_ddr (pddr);
+ return false;
+ }
po = PDDR_DDP (pddr);
ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
- eqpp = build_pairwise_scheduling_inequality (dim, level, tdim1 + ddim1, 1);
+ pos = psct_dynamic_dim (pbb, level);
+ eqpp = build_pairwise_scheduling (dim, pos, tdim1 + ddim1, 1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
+ empty_p = ppl_powerset_is_empty (eqpp);
ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
+ free_poly_ddr (pddr);
+
return !empty_p;
}
timevar_push (TV_GRAPHITE_DATA_DEPS);
- for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
- for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2)
if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
{
timevar_pop (TV_GRAPHITE_DATA_DEPS);
return false;
}
+/* When ORIG is true, pretty print to FILE all the original data
+ dependences of SCoP in DOT format, otherwise print the transformed
+ data deps. */
+
+static void
+dot_deps_stmt_2 (FILE *file, scop_p scop, bool orig)
+{
+ int i, j, k, l;
+ poly_bb_p pbb1, pbb2;
+ poly_dr_p pdr1, pdr2;
+
+ FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
+ FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
+ {
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2)
+ {
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig);
+
+ if (!pddr_is_empty (pddr))
+ {
+ fprintf (file, orig ? "OS%d -> OS%d\n" : "TS%d -> TS%d\n",
+ pbb_index (pbb1), pbb_index (pbb2));
+
+ free_poly_ddr (pddr);
+ goto done;
+ }
+
+ free_poly_ddr (pddr);
+ }
+ done:;
+ }
+}
+
/* Pretty print to FILE all the data dependences of SCoP in DOT
format. */
static void
-dot_deps_1 (FILE *file, scop_p scop)
+dot_deps_stmt_1 (FILE *file, scop_p scop)
+{
+ fputs ("digraph all {\n", file);
+
+ dot_deps_stmt_2 (file, scop, true);
+ dot_deps_stmt_2 (file, scop, false);
+
+ fputs ("}\n\n", file);
+}
+
+/* When ORIG is true, pretty print to FILE all the original data
+ dependences of SCoP in DOT format, otherwise print the transformed
+ data deps. */
+
+static void
+dot_deps_2 (FILE *file, scop_p scop, bool orig)
{
int i, j, k, l;
poly_bb_p pbb1, pbb2;
poly_dr_p pdr1, pdr2;
+ FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
+ FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2)
+ {
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig);
+
+ if (!pddr_is_empty (pddr))
+ fprintf (file, orig
+ ? "OS%d_D%d -> OS%d_D%d\n" : "TS%d_D%d -> TS%d_D%d\n",
+ pbb_index (pbb1), PDR_ID (pdr1),
+ pbb_index (pbb2), PDR_ID (pdr2));
+
+ free_poly_ddr (pddr);
+ }
+}
+
+/* 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);
- 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",
- pbb_index (pbb1), PDR_ID (pdr1),
- pbb_index (pbb2), PDR_ID (pdr2));
+ dot_deps_2 (file, scop, true);
+ dot_deps_2 (file, scop, false);
fputs ("}\n\n", file);
}
/* Display all the data dependences in SCoP using dotty. */
-void
+DEBUG_FUNCTION void
dot_deps (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_1 (stream, scop);
fclose (stream);
- x = system ("dotty /tmp/scopdeps.dot");
+ system ("dotty /tmp/scopdeps.dot &");
#else
dot_deps_1 (stderr, scop);
#endif
}
+/* Display all the statement dependences in SCoP using dotty. */
+
+DEBUG_FUNCTION 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
+ FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
+ gcc_assert (stream);
+
+ dot_deps_stmt_1 (stream, scop);
+ fclose (stream);
+
+ system ("dotty /tmp/scopdeps.dot &");
+#else
+ dot_deps_stmt_1 (stderr, scop);
+#endif
+}
#endif