/* 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"
PDDR_DDP (pddr) = ddp;
PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
- if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
+ if (!ddp
+ || ppl_powerset_is_empty (ddp,
+ scop_nb_params (PBB_SCOP (PDR_PBB (source)))))
PDDR_KIND (pddr) = no_dependence;
else
PDDR_KIND (pddr) = has_dependence;
fprintf (file, "has_dependence");
fprintf (file, "\n source ");
- print_pdr (file, PDDR_SOURCE (pddr));
+ print_pdr (file, PDDR_SOURCE (pddr), 2);
fprintf (file, "\n sink ");
- print_pdr (file, PDDR_SINK (pddr));
+ print_pdr (file, PDDR_SINK (pddr), 2);
if (PDDR_KIND (pddr) == has_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");
}
/* Prints to STDERR the poly_ddr_p PDDR. */
-void
+DEBUG_FUNCTION void
debug_pddr (poly_ddr_p pddr)
{
print_pddr (stderr, pddr);
return !empty_p;
}
-/* Returns a polyhedron of dimension DIM.
-
- 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
-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)
-{
- ppl_Pointset_Powerset_C_Polyhedron_t res;
-
- 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);
-
- return res;
-}
-
/* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
transformed into "a CUT0 c CUT1' b"
/* 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;
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. */
+ PDR2 to PDR1. GDIM is the number of parameters in the scop. */
static ppl_Pointset_Powerset_C_Polyhedron_t
build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
graphite_dim_t dim,
graphite_dim_t tdim,
graphite_dim_t offset,
+ graphite_dim_t gdim,
int direction)
{
graphite_dim_t i;
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, gdim))
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, gdim))
+ 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, gdim))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
poly_bb_p pbb1 = PDR_PBB (pdr1);
poly_bb_p pbb2 = PDR_PBB (pdr2);
scop_p scop = PBB_SCOP (pbb1);
- ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
- ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
graphite_dim_t tdim1 = original_scattering_p ?
pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
graphite_dim_t tdim2 = original_scattering_p ?
pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
- ppl_Polyhedron_t scat1 = original_scattering_p ?
- PBB_ORIGINAL_SCATTERING (pbb1) : PBB_TRANSFORMED_SCATTERING (pbb1);
- ppl_Polyhedron_t scat2 = original_scattering_p ?
- PBB_ORIGINAL_SCATTERING (pbb2) : PBB_TRANSFORMED_SCATTERING (pbb2);
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 - 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 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);
+ combine_context_id_scat (&sc1, pbb1, original_scattering_p);
+ combine_context_id_scat (&sc2, pbb2, original_scattering_p);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc1, scat1);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sc2, scat2);
+ ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1,
+ tdim2 + ddim2 + sdim1 + sdim2);
- 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);
+ 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, 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, 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 (context);
- 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))
+ if (!ppl_powerset_is_empty (res, gdim))
{
ppl_Pointset_Powerset_C_Polyhedron_t lex =
build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
- tdim1 + ddim1, direction);
+ tdim1 + ddim1, gdim, direction);
ppl_delete_Pointset_Powerset_C_Polyhedron (res);
res = lex;
}
res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p);
+ 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))
+ PDDR_KIND (res) = unknown_dependence;
+
if (original_scattering_p)
*x = res;
int i;
poly_dr_p pdr;
- for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
+ FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr)
if (PDR_TYPE (pdr) == PDR_WRITE)
break;
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);
- tpddr = dependence_polyhedron (pdr1, pdr2, -1, false);
+
+ 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
if (pddr_is_empty (opddr))
return true;
+ tpddr = dependence_polyhedron (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);
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,
+ scop_nb_params (PBB_SCOP (pbb1)));
ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
free_poly_ddr (tpddr);
if (reduction_ddr_p (pbb1, pbb2))
return true;
- 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_legal_transform_dr (pdr1, pdr2))
return false;
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);
bool empty_p;
poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
+ if (PDDR_KIND (pddr) == unknown_dependence)
+ {
+ free_poly_ddr (pddr);
+ return true;
+ }
+
if (pddr_is_empty (pddr))
{
free_poly_ddr (pddr);
eqpp = build_pairwise_scheduling (dim, level, 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, scop_nb_params (PBB_SCOP (PDR_PBB (pdr1))));
ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
free_poly_ddr (pddr);
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);
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_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
+ FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
{
- 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++)
+ 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",
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_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
+ FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
{
- 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++)
+ 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_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++)
+ 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_D%d -> OS%d_D%d\n",
pbb_index (pbb1), PDR_ID (pdr1),
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++)
+ 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);
/* 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
