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"
return res;
}
-/* Add to a non empty polyhedron RES the precedence constraints for
- the lexicographical comparison of time vectors in RES following the
- lexicographical order. DIM is the dimension of the polyhedron RES.
+/* 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 RES polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
+ 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 void
-build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t *res,
+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,
int direction)
{
graphite_dim_t i;
+ ppl_Pointset_Powerset_C_Polyhedron_t res, lex;
- for (i = 0; i < tdim - 1; i+=2)
- {
- ppl_Pointset_Powerset_C_Polyhedron_t ineq;
- bool empty_p;
+ ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
- /* Identify the static schedule dimensions. */
- ineq = build_pairwise_scheduling (dim, i, offset, 0);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (ineq, *res);
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (ineq);
+ lex = build_pairwise_scheduling (dim, 0, offset, direction);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (empty_p)
- {
- /* Add the lexicographical dynamic schedule dimension. */
- if (i > 0)
- ineq = build_pairwise_scheduling (dim, i - 1, offset, direction);
+ if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
- return;
- }
+ ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, ineq);
- ppl_delete_Pointset_Powerset_C_Polyhedron (ineq);
+ for (i = 0; i < tdim - 1; i++)
+ {
+ ppl_Pointset_Powerset_C_Polyhedron_t sceq;
+
+ sceq = build_pairwise_scheduling (dim, i, offset, 0);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
+
+ lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
+ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- /* Identify the dynamic schedule dimensions. */
- ineq = build_pairwise_scheduling (dim, i + 1, offset, 0);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, ineq);
- ppl_delete_Pointset_Powerset_C_Polyhedron (ineq);
+ if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
+
+ ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
}
- /* There is no dependence. */
- ppl_delete_Pointset_Powerset_C_Polyhedron (*res);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res, dim, 1);
+ return res;
}
/* Build the dependence polyhedron for data references PDR1 and PDR2.
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))
- build_lexicographical_constraint (&res, dim, MIN (tdim1, tdim2),
- tdim1 + ddim1, direction);
+ {
+ ppl_Pointset_Powerset_C_Polyhedron_t lex =
+ build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
+ tdim1 + ddim1, direction);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (res);
+ res = lex;
+ }
return res;
}
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;
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);
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);