/* Data dependence analysis for Graphite.
- Copyright (C) 2009 Free Software Foundation, Inc.
+ Copyright (C) 2009-2013 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@amd.com> and
Konrad Trifunovic <konrad.trifunovic@inria.fr>.
<http://www.gnu.org/licenses/>. */
#include "config.h"
+
+#ifdef HAVE_cloog
+#include <isl/set.h>
+#include <isl/map.h>
+#include <isl/union_map.h>
+#include <isl/flow.h>
+#include <isl/constraint.h>
+#include <cloog/cloog.h>
+#include <cloog/isl/domain.h>
+#endif
+
#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 "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "tree-ssa-loop.h"
+#include "tree-pass.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"
+#include "graphite-htab.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). */
+/* Add the constraints from the set S to the domain of MAP. */
-static poly_ddr_p
-new_poly_ddr (poly_dr_p source, poly_dr_p sink,
- ppl_Pointset_Powerset_C_Polyhedron_t ddp)
+static isl_map *
+constrain_domain (isl_map *map, isl_set *s)
{
- poly_ddr_p pddr;
+ isl_space *d = isl_map_get_space (map);
+ isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
- pddr = XNEW (struct poly_ddr);
- PDDR_SOURCE (pddr) = source;
- PDDR_SINK (pddr) = sink;
- PDDR_DDP (pddr) = ddp;
- PDDR_KIND (pddr) = unknown_dependence;
-
- return pddr;
+ s = isl_set_set_tuple_id (s, id);
+ isl_space_free (d);
+ return isl_map_intersect_domain (map, s);
}
-/* Free the poly_ddr_p P. */
+/* Constrain pdr->accesses with pdr->extent and pbb->domain. */
-void
-free_poly_ddr (void *p)
+static isl_map *
+add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
{
- poly_ddr_p pddr = (poly_ddr_p) p;
- ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
- free (pddr);
+ isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
+ isl_set_copy (pdr->extent));
+ x = constrain_domain (x, isl_set_copy (pbb->domain));
+ return x;
}
-/* Comparison function for poly_ddr hash table. */
+/* Returns all the memory reads in SCOP. */
-int
-eq_poly_ddr_p (const void *pddr1, const void *pddr2)
+static isl_union_map *
+scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
{
- const struct poly_ddr *p1 = (const struct poly_ddr *) pddr1;
- const struct poly_ddr *p2 = (const struct poly_ddr *) pddr2;
-
- return (PDDR_SOURCE (p1) == PDDR_SOURCE (p2)
- && PDDR_SINK (p1) == PDDR_SINK (p2));
-}
-
-/* Hash function for poly_ddr hashtable. */
+ int i, j;
+ poly_bb_p pbb;
+ poly_dr_p pdr;
+ isl_space *space = isl_set_get_space (scop->context);
+ isl_union_map *res = isl_union_map_empty (space);
-hashval_t
-hash_poly_ddr_p (const void *pddr)
-{
- const struct poly_ddr *p = (const struct poly_ddr *) pddr;
+ FOR_EACH_VEC_ELT (pbbs, i, pbb)
+ {
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ if (pdr_read_p (pdr))
+ res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+ }
- return (hashval_t) ((long) PDDR_SOURCE (p) + (long) PDDR_SINK (p));
+ return res;
}
-/* Returns true when PDDR has no dependence. */
+/* Returns all the memory must writes in SCOP. */
-static bool
-pddr_is_empty (poly_ddr_p pddr)
+static isl_union_map *
+scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
{
- if (PDDR_KIND (pddr) != unknown_dependence)
- return PDDR_KIND (pddr) == no_dependence ? true : false;
+ int i, j;
+ poly_bb_p pbb;
+ poly_dr_p pdr;
+ isl_space *space = isl_set_get_space (scop->context);
+ isl_union_map *res = isl_union_map_empty (space);
- if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PDDR_DDP (pddr)))
+ FOR_EACH_VEC_ELT (pbbs, i, pbb)
{
- PDDR_KIND (pddr) = no_dependence;
- return true;
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ if (pdr_write_p (pdr))
+ res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
}
- PDDR_KIND (pddr) = has_dependence;
- return false;
+ return res;
}
-/* Returns a polyhedron of dimension DIM.
-
- Maps the dimensions [0, ..., cut - 1] of polyhedron P to OFFSET0
- and the dimensions [cut, ..., nb_dim] to DIM - GDIM. */
+/* Returns all the memory may writes in SCOP. */
-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)
+static isl_union_map *
+scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
{
- ppl_Pointset_Powerset_C_Polyhedron_t res;
+ int i, j;
+ poly_bb_p pbb;
+ poly_dr_p pdr;
+ isl_space *space = isl_set_get_space (scop->context);
+ isl_union_map *res = isl_union_map_empty (space);
- 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);
+ FOR_EACH_VEC_ELT (pbbs, i, pbb)
+ {
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ if (pdr_may_write_p (pdr))
+ res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+ }
return res;
}
-/* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
- transformed into "a CUT0 c CUT1' b"
-
- Add NB0 zeros before "a": "00...0 a CUT0 c CUT1' b"
- Add NB1 zeros between "a" and "c": "00...0 a 00...0 c CUT1' b"
- Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
- "00...0 a 00...0 c 00...0 b". */
+/* Returns all the original schedules in SCOP. */
-static ppl_Pointset_Powerset_C_Polyhedron_t
-map_dr_into_dep_poly (graphite_dim_t dim,
- ppl_Pointset_Powerset_C_Polyhedron_t dr,
- graphite_dim_t cut0, graphite_dim_t cut1,
- graphite_dim_t nb0, graphite_dim_t nb1)
+static isl_union_map *
+scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
{
- ppl_dimension_type pdim;
- ppl_dimension_type *map;
- ppl_Pointset_Powerset_C_Polyhedron_t res;
- ppl_dimension_type i;
-
- ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
- (&res, dr);
- ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim);
-
- map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim);
-
- /* First mapping: move 'g' vector to right position. */
- for (i = 0; i < cut0; i++)
- map[i] = i;
+ int i;
+ poly_bb_p pbb;
+ isl_space *space = isl_set_get_space (scop->context);
+ isl_union_map *res = isl_union_map_empty (space);
- for (i = cut0; i < cut1; i++)
- map[i] = pdim - cut1 + i;
-
- for (i = cut1; i < pdim; i++)
- map[i] = cut0 + i - cut1;
-
- ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim);
- free (map);
-
- /* After swapping 's' and 'g' vectors, we have to update a new cut. */
- cut1 = pdim - cut1 + cut0;
-
- ppl_insert_dimensions_pointset (res, 0, nb0);
- ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1);
- ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1,
- dim - nb0 - nb1 - pdim);
+ FOR_EACH_VEC_ELT (pbbs, i, pbb)
+ {
+ res = isl_union_map_add_map
+ (res, constrain_domain (isl_map_copy (pbb->schedule),
+ isl_set_copy (pbb->domain)));
+ }
return res;
}
-/* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
+/* Returns all the transformed schedules in SCOP. */
-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)
+static isl_union_map *
+scop_get_transformed_schedule (scop_p scop, vec<poly_bb_p> pbbs)
{
- 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. */
+ int i;
+ poly_bb_p pbb;
+ isl_space *space = isl_set_get_space (scop->context);
+ isl_union_map *res = isl_union_map_empty (space);
-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_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 (&subscript_equalities, dim, 0);
- for (i = 0; i < nb_subscripts; i++)
+ FOR_EACH_VEC_ELT (pbbs, i, pbb)
{
- 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_delete_Constraint (cstr);
- ppl_delete_Coefficient (coef);
+ res = isl_union_map_add_map
+ (res, constrain_domain (isl_map_copy (pbb->transformed),
+ isl_set_copy (pbb->domain)));
}
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
- (&res, subscript_equalities);
- value_clear (v);
- value_clear (v_op);
- ppl_delete_Polyhedron (subscript_equalities);
-
return res;
}
-/* Builds scheduling equality constraints. */
+/* Helper function used on each MAP of a isl_union_map. Computes the
+ maximal output dimension. */
-static ppl_Pointset_Powerset_C_Polyhedron_t
-build_pairwise_scheduling_equality (graphite_dim_t dim,
- graphite_dim_t pos, graphite_dim_t offset)
+static int
+max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
{
- 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);
+ int global_max = *((int *) user);
+ isl_space *space = isl_map_get_space (map);
+ int nb_out = isl_space_dim (space, isl_dim_out);
- cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
- PPL_CONSTRAINT_TYPE_EQUAL);
- ppl_Polyhedron_add_constraint (equalities, cstr);
- ppl_delete_Constraint (cstr);
+ if (global_max < nb_out)
+ *((int *) user) = nb_out;
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
- ppl_delete_Polyhedron (equalities);
- return res;
+ isl_map_free (map);
+ isl_space_free (space);
+ return 0;
}
-/* Builds scheduling inequality constraints. */
+/* Extends the output dimension of MAP to MAX dimensions. */
-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)
+static __isl_give isl_map *
+extend_map (__isl_take isl_map *map, int max)
{
- 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);
+ isl_space *space = isl_map_get_space (map);
+ int n = isl_space_dim (space, isl_dim_out);
- 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);
+ isl_space_free (space);
+ return isl_map_add_dims (map, isl_dim_out, max - n);
+}
- ppl_Polyhedron_add_constraint (equalities, cstr);
- ppl_delete_Constraint (cstr);
+/* Structure used to pass parameters to extend_schedule_1. */
- ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
- ppl_delete_Polyhedron (equalities);
- return res;
-}
+struct extend_schedule_str {
+ int max;
+ isl_union_map *umap;
+};
-/* Returns true when adding the lexicographical constraints at level I
- to the RES dependence polyhedron returns an empty polyhedron. */
+/* Helper function for extend_schedule. */
-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)
+static int
+extend_schedule_1 (__isl_take isl_map *map, void *user)
{
- ppl_Pointset_Powerset_C_Polyhedron_t ineq;
- bool empty_p;
-
- 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);
-
- return !empty_p;
+ struct extend_schedule_str *str = (struct extend_schedule_str *) user;
+ str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
+ return 0;
}
-/* Build the precedence constraints for the lexicographical comparison
- of time vectors RES following the lexicographical order. */
+/* Return a relation that has uniform output dimensions. */
-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)
+__isl_give isl_union_map *
+extend_schedule (__isl_take isl_union_map *x)
{
- graphite_dim_t i;
+ int max = 0;
+ int res;
+ struct extend_schedule_str str;
- if (lexicographically_gt_p (*res, dim, offset, direction, 0))
- return;
+ res = isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
+ gcc_assert (res == 0);
- for (i = 0; i < tdim1 - 1; i++)
- {
- ppl_Pointset_Powerset_C_Polyhedron_t sceq;
+ str.max = max;
+ str.umap = isl_union_map_empty (isl_union_map_get_space (x));
+ res = isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
+ gcc_assert (res == 0);
- sceq = build_pairwise_scheduling_equality (dim, i, offset);
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, sceq);
- ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
-
- if (lexicographically_gt_p (*res, dim, offset, direction, i + 1))
- return;
- }
-
- if (i == tdim1 - 1)
- {
- ppl_delete_Pointset_Powerset_C_Polyhedron (*res);
- ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (res, dim, 1);
- }
+ isl_union_map_free (x);
+ return str.umap;
}
-/* Build the dependence polyhedron for data references PDR1 and PDR2. */
+/* Applies SCHEDULE to the in and out dimensions of the dependences
+ DEPS and return the resulting relation. */
-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 isl_map *
+apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
+ __isl_keep isl_union_map *deps)
{
- 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 tdim2 = original_scattering_p ?
- pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (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 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;
- 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;
-
- 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);
-
- idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
- tdim1, tdim2 + ddim2);
- idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
- tdim1 + ddim1 + tdim2, sdim1);
-
- /* Now add the subscript equalities. */
- 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, 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);
-
- return new_poly_ddr (pdr1, pdr2, res);
-}
+ isl_map *x;
+ isl_union_map *ux, *trans;
-/* Build the dependence polyhedron for data references PDR1 and PDR2.
- If possible use already cached information. */
-
-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)
-{
- PTR *x = NULL;
- poly_ddr_p res;
+ trans = isl_union_map_copy (schedule);
+ trans = extend_schedule (trans);
+ ux = isl_union_map_copy (deps);
+ ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
+ ux = isl_union_map_apply_range (ux, trans);
+ x = isl_map_from_union_map (ux);
- if (original_scattering_p)
- {
- struct poly_ddr tmp;
-
- tmp.source = pdr1;
- tmp.sink = pdr2;
- x = htab_find_slot (SCOP_ORIGINAL_PDDRS (PBB_SCOP (pbb1)),
- &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);
-
- if (original_scattering_p)
- *x = res;
-
- return res;
+ return x;
}
-/* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
- and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
- functions. */
+/* Return true when SCHEDULE does not violate the data DEPS: that is
+ when the intersection of LEX with the DEPS transformed by SCHEDULE
+ is empty. LEX is the relation in which the outputs occur before
+ the inputs. */
static bool
-graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
- poly_dr_p pdr1, poly_dr_p pdr2)
+no_violations (__isl_keep isl_union_map *schedule,
+ __isl_keep isl_union_map *deps)
{
- 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_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);
- ppl_Polyhedron_t so1 = PBB_ORIGINAL_SCATTERING (pbb1);
- ppl_Polyhedron_t so2 = PBB_ORIGINAL_SCATTERING (pbb2);
- graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
- graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
-
- if (sdim1 != sdim2)
- return true;
+ bool res;
+ isl_space *space;
+ isl_map *lex, *x;
- pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
- true, true);
- if (pddr_is_empty (pddr))
+ if (isl_union_map_is_empty (deps))
return true;
- po = PDDR_DDP (pddr);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nloop carries dependency.\n");
-
- st1 = PBB_TRANSFORMED_SCATTERING (pbb1);
- st2 = PBB_TRANSFORMED_SCATTERING (pbb2);
- 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 (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);
+ x = apply_schedule_on_deps (schedule, deps);
+ space = isl_map_get_space (x);
+ space = isl_space_range (space);
+ lex = isl_map_lex_ge (space);
+ x = isl_map_intersect (x, lex);
+ res = isl_map_is_empty (x);
- ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
- free_poly_ddr (pddr);
-
- return is_empty_p;
+ isl_map_free (x);
+ return res;
}
-/* Iterates over the data references of PBB1 and PBB2 and detect
- whether the transformed schedule is correct. */
+/* Return true when DEPS is non empty and the intersection of LEX with
+ the DEPS transformed by SCHEDULE is non empty. LEX is the relation
+ in which all the inputs before DEPTH occur at the same time as the
+ output, and the input at DEPTH occurs before output. */
static bool
-graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
+carries_deps (__isl_keep isl_union_map *schedule,
+ __isl_keep isl_union_map *deps,
+ int depth)
{
- int i, j;
- poly_dr_p pdr1, pdr2;
+ bool res;
+ int i;
+ isl_space *space;
+ isl_map *lex, *x;
+ isl_constraint *ineq;
- 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))
- return false;
+ if (isl_union_map_is_empty (deps))
+ return false;
- return true;
+ x = apply_schedule_on_deps (schedule, deps);
+ space = isl_map_get_space (x);
+ space = isl_space_range (space);
+ lex = isl_map_lex_le (space);
+ space = isl_map_get_space (x);
+ ineq = isl_inequality_alloc (isl_local_space_from_space (space));
+
+ for (i = 0; i < depth - 1; i++)
+ lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
+
+ /* in + 1 <= out */
+ ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
+ ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
+ ineq = isl_constraint_set_constant_si (ineq, -1);
+ lex = isl_map_add_constraint (lex, ineq);
+ x = isl_map_intersect (x, lex);
+ res = !isl_map_is_empty (x);
+
+ isl_map_free (x);
+ return res;
}
-/* Iterates over the SCOP and detect whether the transformed schedule
- is correct. */
+/* Subtract from the RAW, WAR, and WAW dependences those relations
+ that have been marked as belonging to an associative commutative
+ reduction. */
-bool
-graphite_legal_transform (scop_p scop)
+static void
+subtract_commutative_associative_deps (scop_p scop,
+ vec<poly_bb_p> pbbs,
+ isl_union_map *original,
+ isl_union_map **must_raw,
+ isl_union_map **may_raw,
+ isl_union_map **must_raw_no_source,
+ isl_union_map **may_raw_no_source,
+ isl_union_map **must_war,
+ isl_union_map **may_war,
+ isl_union_map **must_war_no_source,
+ isl_union_map **may_war_no_source,
+ isl_union_map **must_waw,
+ isl_union_map **may_waw,
+ isl_union_map **must_waw_no_source,
+ isl_union_map **may_waw_no_source)
{
int i, j;
- poly_bb_p pbb1, pbb2;
-
- 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++)
- if (!graphite_legal_transform_bb (pbb1, pbb2))
- {
- timevar_pop (TV_GRAPHITE_DATA_DEPS);
- return false;
- }
-
- timevar_pop (TV_GRAPHITE_DATA_DEPS);
- return true;
+ poly_bb_p pbb;
+ poly_dr_p pdr;
+ isl_space *space = isl_set_get_space (scop->context);
+
+ FOR_EACH_VEC_ELT (pbbs, i, pbb)
+ if (PBB_IS_REDUCTION (pbb))
+ {
+ int res;
+ isl_union_map *r = isl_union_map_empty (isl_space_copy (space));
+ isl_union_map *must_w = isl_union_map_empty (isl_space_copy (space));
+ isl_union_map *may_w = isl_union_map_empty (isl_space_copy (space));
+ isl_union_map *all_w;
+ isl_union_map *empty;
+ isl_union_map *x_must_raw;
+ isl_union_map *x_may_raw;
+ isl_union_map *x_must_raw_no_source;
+ isl_union_map *x_may_raw_no_source;
+ isl_union_map *x_must_war;
+ isl_union_map *x_may_war;
+ isl_union_map *x_must_war_no_source;
+ isl_union_map *x_may_war_no_source;
+ isl_union_map *x_must_waw;
+ isl_union_map *x_may_waw;
+ isl_union_map *x_must_waw_no_source;
+ isl_union_map *x_may_waw_no_source;
+
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ if (pdr_read_p (pdr))
+ r = isl_union_map_add_map (r, add_pdr_constraints (pdr, pbb));
+
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ if (pdr_write_p (pdr))
+ must_w = isl_union_map_add_map (must_w,
+ add_pdr_constraints (pdr, pbb));
+
+ FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
+ if (pdr_may_write_p (pdr))
+ may_w = isl_union_map_add_map (may_w,
+ add_pdr_constraints (pdr, pbb));
+
+ all_w = isl_union_map_union
+ (isl_union_map_copy (must_w), isl_union_map_copy (may_w));
+ empty = isl_union_map_empty (isl_union_map_get_space (all_w));
+
+ res = isl_union_map_compute_flow (isl_union_map_copy (r),
+ isl_union_map_copy (must_w),
+ isl_union_map_copy (may_w),
+ isl_union_map_copy (original),
+ &x_must_raw, &x_may_raw,
+ &x_must_raw_no_source,
+ &x_may_raw_no_source);
+ gcc_assert (res == 0);
+ res = isl_union_map_compute_flow (isl_union_map_copy (all_w),
+ r, empty,
+ isl_union_map_copy (original),
+ &x_must_war, &x_may_war,
+ &x_must_war_no_source,
+ &x_may_war_no_source);
+ gcc_assert (res == 0);
+ res = isl_union_map_compute_flow (all_w, must_w, may_w,
+ isl_union_map_copy (original),
+ &x_must_waw, &x_may_waw,
+ &x_must_waw_no_source,
+ &x_may_waw_no_source);
+ gcc_assert (res == 0);
+
+ *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
+ *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
+ *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
+ x_must_raw_no_source);
+ *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
+ x_may_raw_no_source);
+ *must_war = isl_union_map_subtract (*must_war, x_must_war);
+ *may_war = isl_union_map_subtract (*may_war, x_may_war);
+ *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
+ x_must_war_no_source);
+ *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
+ x_may_war_no_source);
+ *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
+ *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
+ *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
+ x_must_waw_no_source);
+ *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
+ x_may_waw_no_source);
+ }
+
+ isl_union_map_free (original);
+ isl_space_free (space);
}
-/* Remove all the dimensions except alias information at dimension
- ALIAS_DIM. */
+/* Compute the original data dependences in SCOP for all the reads and
+ writes in PBBS. */
-static void
-build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
- ppl_dimension_type alias_dim)
+void
+compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
+ isl_union_map **must_raw,
+ isl_union_map **may_raw,
+ isl_union_map **must_raw_no_source,
+ isl_union_map **may_raw_no_source,
+ isl_union_map **must_war,
+ isl_union_map **may_war,
+ isl_union_map **must_war_no_source,
+ isl_union_map **may_war_no_source,
+ isl_union_map **must_waw,
+ isl_union_map **may_waw,
+ isl_union_map **must_waw_no_source,
+ isl_union_map **may_waw_no_source)
{
- 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);
+ isl_union_map *reads = scop_get_reads (scop, pbbs);
+ isl_union_map *must_writes = scop_get_must_writes (scop, pbbs);
+ isl_union_map *may_writes = scop_get_may_writes (scop, pbbs);
+ isl_union_map *all_writes = isl_union_map_union
+ (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes));
+ isl_space *space = isl_union_map_get_space (all_writes);
+ isl_union_map *empty = isl_union_map_empty (space);
+ isl_union_map *original = scop_get_original_schedule (scop, pbbs);
+ int res;
+
+ res = isl_union_map_compute_flow (isl_union_map_copy (reads),
+ isl_union_map_copy (must_writes),
+ isl_union_map_copy (may_writes),
+ isl_union_map_copy (original),
+ must_raw, may_raw, must_raw_no_source,
+ may_raw_no_source);
+ gcc_assert (res == 0);
+ res = isl_union_map_compute_flow (isl_union_map_copy (all_writes),
+ reads, empty,
+ isl_union_map_copy (original),
+ must_war, may_war, must_war_no_source,
+ may_war_no_source);
+ gcc_assert (res == 0);
+ res = isl_union_map_compute_flow (all_writes, must_writes, may_writes,
+ isl_union_map_copy (original),
+ must_waw, may_waw, must_waw_no_source,
+ may_waw_no_source);
+ gcc_assert (res == 0);
+
+ subtract_commutative_associative_deps
+ (scop, pbbs, original,
+ must_raw, may_raw, must_raw_no_source, may_raw_no_source,
+ must_war, may_war, must_war_no_source, may_war_no_source,
+ must_waw, may_waw, must_waw_no_source, may_waw_no_source);
}
-/* Return true when PDR1 and PDR2 may alias. */
+/* Given a TRANSFORM, check whether it respects the original
+ dependences in SCOP. Returns true when TRANSFORM is a safe
+ transformation. */
static bool
-poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
+transform_is_safe (scop_p scop, isl_union_map *transform)
{
- 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);
+ bool res;
+
+ if (!scop->must_raw)
+ compute_deps (scop, SCOP_BBS (scop),
+ &scop->must_raw, &scop->may_raw,
+ &scop->must_raw_no_source, &scop->may_raw_no_source,
+ &scop->must_war, &scop->may_war,
+ &scop->must_war_no_source, &scop->may_war_no_source,
+ &scop->must_waw, &scop->may_waw,
+ &scop->must_waw_no_source, &scop->may_waw_no_source);
+
+ res = (no_violations (transform, scop->must_raw)
+ && no_violations (transform, scop->may_raw)
+ && no_violations (transform, scop->must_war)
+ && no_violations (transform, scop->may_war)
+ && no_violations (transform, scop->must_waw)
+ && no_violations (transform, scop->may_waw));
+
+ isl_union_map_free (transform);
+ return res;
+}
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
- (alias_powerset1, alias_powerset2);
+/* Return true when the SCOP transformed schedule is correct. */
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
+bool
+graphite_legal_transform (scop_p scop)
+{
+ int res;
+ isl_union_map *transform;
- ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
- ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
+ timevar_push (TV_GRAPHITE_DATA_DEPS);
+ transform = scop_get_transformed_schedule (scop, SCOP_BBS (scop));
+ res = transform_is_safe (scop, transform);
+ timevar_pop (TV_GRAPHITE_DATA_DEPS);
- return !empty_p;
+ return res;
}
-/* Returns TRUE when the dependence polyhedron between PDR1 and
- PDR2 represents a loop carried dependence at level LEVEL. */
+/* Return true when the loop at DEPTH carries dependences. BODY is
+ the body of the loop. */
static bool
-graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
- int level)
+loop_level_carries_dependences (scop_p scop, vec<poly_bb_p> body,
+ int depth)
{
- 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 sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
- graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
- graphite_dim_t tdim1 = pbb_nb_scattering_transform (pbb1);
- graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
- ppl_dimension_type dim;
- bool empty_p;
- poly_ddr_p pddr;
-
- if ((PDR_TYPE (pdr1) == PDR_READ && PDR_TYPE (pdr2) == PDR_READ)
- || !poly_drs_may_alias_p (pdr1, pdr2))
- return false;
-
- if (sdim1 != sdim2)
- return true;
-
- pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
- true, false);
-
- if (pddr_is_empty (pddr))
- {
- ppl_delete_Pointset_Powerset_C_Polyhedron (po);
- 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);
-
- ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
-
- ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
- return !empty_p;
+ isl_union_map *transform = scop_get_transformed_schedule (scop, body);
+ isl_union_map *must_raw, *may_raw;
+ isl_union_map *must_war, *may_war;
+ isl_union_map *must_waw, *may_waw;
+ int res;
+
+ compute_deps (scop, body,
+ &must_raw, &may_raw, NULL, NULL,
+ &must_war, &may_war, NULL, NULL,
+ &must_waw, &may_waw, NULL, NULL);
+
+ res = (carries_deps (transform, must_raw, depth)
+ || carries_deps (transform, may_raw, depth)
+ || carries_deps (transform, must_war, depth)
+ || carries_deps (transform, may_war, depth)
+ || carries_deps (transform, must_waw, depth)
+ || carries_deps (transform, may_waw, depth));
+
+ isl_union_map_free (transform);
+ isl_union_map_free (must_raw);
+ isl_union_map_free (may_raw);
+ isl_union_map_free (must_war);
+ isl_union_map_free (may_war);
+ isl_union_map_free (must_waw);
+ isl_union_map_free (may_waw);
+ return res;
}
-/* Check data dependency between PBB1 and PBB2 at level LEVEL. */
+/* Returns true when the loop L at level DEPTH is parallel.
+ BB_PBB_MAPPING is a map between a basic_block and its related
+ poly_bb_p. */
bool
-dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
+loop_is_parallel_p (loop_p loop, bb_pbb_htab_type bb_pbb_mapping, int depth)
{
- int i, j;
- poly_dr_p pdr1, pdr2;
+ bool dependences;
+ scop_p scop;
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++)
- if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
- {
- timevar_pop (TV_GRAPHITE_DATA_DEPS);
- return true;
- }
-
+ stack_vec<poly_bb_p, 3> body;
+ scop = get_loop_body_pbbs (loop, bb_pbb_mapping, &body);
+ dependences = loop_level_carries_dependences (scop, body, depth);
timevar_pop (TV_GRAPHITE_DATA_DEPS);
- return false;
+
+ return !dependences;
}
#endif
git://gcc.gnu.org / gcc.git / blobdiff