/* Data dependence analysis for Graphite.
- Copyright (C) 2009, 2010 Free Software Foundation, Inc.
+ Copyright (C) 2009, 2010, 2013 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 "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. When
- the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE
- and SINK are in dependence as described by DDP. */
-
-static poly_ddr_p
-new_poly_ddr (poly_dr_p source, poly_dr_p sink,
- ppl_Pointset_Powerset_C_Polyhedron_t ddp,
- bool original_scattering_p)
-{
- poly_ddr_p pddr = XNEW (struct poly_ddr);
-
- PDDR_SOURCE (pddr) = source;
- PDDR_SINK (pddr) = sink;
- PDDR_DDP (pddr) = ddp;
- PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
-
- if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
- PDDR_KIND (pddr) = no_dependence;
- else
- PDDR_KIND (pddr) = has_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. */
{
const struct poly_ddr *p = (const struct poly_ddr *) pddr;
- return (hashval_t) ((long) PDDR_SOURCE (p) + (long) PDDR_SINK (p));
+ return (hashval_t) ((intptr_t) PDDR_SOURCE (p) + (intptr_t) PDDR_SINK (p));
}
/* Returns true when PDDR has no dependence. */
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");
}
{
ppl_dimension_type *ds;
ppl_dimension_type access_dim;
- unsigned i, pos = 0;
+ unsigned i, pos;
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 = XNEWVEC (ppl_dimension_type, access_dim - 1);
+ gcc_assert (alias_dim < access_dim);
- ds[pos] = i;
- pos++;
- }
+ 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,
/* Builds scheduling inequality constraints: when DIRECTION is
1 builds a GE constraint,
0 builds an EQ constraint,
- -1 builds a LE 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 (graphite_dim_t dim,
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);
switch (direction)
{
- case -1:
- cstr = ppl_build_relation (dim, pos, pos + offset, 1,
+ case 1:
+ /* Builds "a + 1 <= b. */
+ cstr = ppl_build_relation (dim, a, b, 1,
PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
break;
case 0:
- cstr = ppl_build_relation (dim, pos, pos + offset, 0,
+ /* Builds "a = b. */
+ cstr = ppl_build_relation (dim, a, b, 0,
PPL_CONSTRAINT_TYPE_EQUAL);
break;
- case 1:
- cstr = ppl_build_relation (dim, pos, pos + offset, -1,
+ case -1:
+ /* Builds "a >= b + 1. */
+ cstr = ppl_build_relation (dim, a, b, -1,
PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
break;
lex = build_pairwise_scheduling (dim, 0, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ if (!ppl_powerset_is_empty (lex))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
+ if (ppl_powerset_is_empty (bag))
+ break;
+
lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ if (!ppl_powerset_is_empty (lex))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
relation, from PDR2 to PDR1. */
static ppl_Pointset_Powerset_C_Polyhedron_t
-dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
- int direction, bool original_scattering_p)
+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);
ppl_Pointset_Powerset_C_Polyhedron_t res;
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_delete_Pointset_Powerset_C_Polyhedron (idr2);
ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
- {
- ppl_Pointset_Powerset_C_Polyhedron_t lex =
- build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
+ 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);
- res = lex;
- }
+ ppl_delete_Pointset_Powerset_C_Polyhedron (res);
- return res;
+ return lex;
}
/* Build the dependence polyhedron for data references PDR1 and PDR2.
relation, from PDR2 to PDR1. */
static poly_ddr_p
-dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
- int 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;
- ppl_Pointset_Powerset_C_Polyhedron_t ddp;
+ bool may_alias;
/* Return the PDDR from the cache if it already has been computed. */
if (original_scattering_p)
return (poly_ddr_p) *x;
}
- 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)
- || !poly_drs_may_alias_p (pdr1, pdr2))
- ddp = NULL;
- else
- ddp = dependence_polyhedron_1 (pdr1, pdr2, 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;
- res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p);
+ 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)
- && poly_drs_may_alias_p (pdr1, 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;
}
+/* Free the data dependence relation 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);
+}
+
/* Return true when the data dependence relation between the data
references PDR1 belonging to PBB1 and PDR2 is part of a
reduction. */
poly_dr_p pdr;
FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr)
- if (PDR_TYPE (pdr) == PDR_WRITE)
- break;
+ if (PDR_TYPE (pdr) == PDR_WRITE
+ && same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2))
+ return true;
- return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
+ return false;
}
/* Return true when the data dependence relation between the data
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 = dependence_polyhedron (pdr1, pdr2, 1, true);
+ opddr = new_poly_ddr (pdr1, pdr2, 1, true);
if (PDDR_KIND (opddr) == unknown_dependence)
return false;
if (pddr_is_empty (opddr))
return true;
- tpddr = dependence_polyhedron (pdr1, pdr2, -1, false);
+ tpddr = new_poly_ddr (pdr1, pdr2, -1, false);
if (PDDR_KIND (tpddr) == unknown_dependence)
{
ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
- is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
+ is_empty_p = ppl_powerset_is_empty (po_temp);
ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
free_poly_ddr (tpddr);
{
ppl_Pointset_Powerset_C_Polyhedron_t po;
ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
- graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1));
- graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
+ 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 = dependence_polyhedron (pdr1, pdr2, 1, false);
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false);
+ graphite_dim_t pos;
if (PDDR_KIND (pddr) == unknown_dependence)
{
po = PDDR_DDP (pddr);
ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
- eqpp = build_pairwise_scheduling (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 false;
}
-/* Pretty print to FILE all the original data dependences of SCoP in
- DOT format. */
+/* 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_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_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)
- if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
- {
- 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)
+dot_deps_stmt_2 (FILE *file, scop_p scop, bool orig)
{
int i, j, k, l;
poly_bb_p pbb1, 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 = dependence_polyhedron (pdr1, pdr2, 1, false);
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig);
if (!pddr_is_empty (pddr))
{
- fprintf (file, "TS%d -> TS%d\n",
+ fprintf (file, orig ? "OS%d -> OS%d\n" : "TS%d -> TS%d\n",
pbb_index (pbb1), pbb_index (pbb2));
free_poly_ddr (pddr);
}
}
-
/* Pretty print to FILE all the data dependences of SCoP in DOT
format. */
{
fputs ("digraph all {\n", file);
- dot_original_deps_stmt_1 (file, scop);
- dot_transformed_deps_stmt_1 (file, scop);
+ dot_deps_stmt_2 (file, scop, true);
+ dot_deps_stmt_2 (file, scop, false);
fputs ("}\n\n", file);
}
-/* Pretty print to FILE all the original data dependences of SCoP in
- DOT format. */
+/* 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_original_deps (FILE *file, scop_p scop)
+dot_deps_2 (FILE *file, scop_p scop, bool orig)
{
int i, j, k, l;
poly_bb_p pbb1, pbb2;
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)
- if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
- 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_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 = dependence_polyhedron (pdr1, pdr2, 1, false);
+ {
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig);
if (!pddr_is_empty (pddr))
- fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
+ 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));
{
fputs ("digraph all {\n", file);
- dot_original_deps (file, scop);
- dot_transformed_deps (file, scop);
+ 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. */
-void
+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
- 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 &");
+ system ("dotty /tmp/scopdeps.dot &");
#else
dot_deps_stmt_1 (stderr, scop);
#endif
OSDN Git Service
