--- a/gcc/graphite-dependences.c	Fri Feb 12 23:41:23 2010 +0900
+++ b/gcc/graphite-dependences.c	Mon May 24 12:47:05 2010 +0900
@@ -1,5 +1,5 @@
 /* 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>.
 
@@ -51,20 +51,26 @@
 #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).  */
+   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)
+	      ppl_Pointset_Powerset_C_Polyhedron_t ddp,
+	      bool original_scattering_p)
 {
-  poly_ddr_p pddr;
+  poly_ddr_p pddr = XNEW (struct poly_ddr);
 
-  pddr = XNEW (struct poly_ddr);
   PDDR_SOURCE (pddr) = source;
   PDDR_SINK (pddr) = sink;
   PDDR_DDP (pddr) = ddp;
-  PDDR_KIND (pddr) = unknown_dependence;
+  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;
 }
@@ -106,624 +112,102 @@
 static bool
 pddr_is_empty (poly_ddr_p pddr)
 {
-  if (PDDR_KIND (pddr) != unknown_dependence)
-    return PDDR_KIND (pddr) == no_dependence ? true : false;
-
-  if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PDDR_DDP (pddr)))
-    {
-      PDDR_KIND (pddr) = no_dependence;
-      return true;
-    }
-
-  PDDR_KIND (pddr) = has_dependence;
-  return false;
-}
-
-/* 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"
-
-   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".  */
-
-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)
-{
-  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);
+  if (!pddr)
+    return true;
 
-  /* First mapping: move 'g' vector to right position.  */
-  for (i = 0; i < cut0; i++)
-    map[i] = i;
-
-  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);
-
-  return res;
-}
-
-/* Builds a constraints of the form "POS1 - POS2 CSTR_TYPE C" */
+  gcc_assert (PDDR_KIND (pddr) != unknown_dependence);
 
-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;
+  return PDDR_KIND (pddr) == no_dependence ? true : false;
 }
 
-/* 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_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++)
-    {
-      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);
-    }
-
-  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.  */
-
-static ppl_Pointset_Powerset_C_Polyhedron_t
-build_pairwise_scheduling_equality (graphite_dim_t dim,
-		                    graphite_dim_t pos, graphite_dim_t offset)
-{
-  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);
-
-  cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
-				    PPL_CONSTRAINT_TYPE_EQUAL);
-  ppl_Polyhedron_add_constraint (equalities, cstr);
-  ppl_delete_Constraint (cstr);
-
-  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
-  ppl_delete_Polyhedron (equalities);
-  return res;
-}
-
-/* Builds scheduling inequality constraints.  */
-
-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)
-{
-  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);
-
-  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_Polyhedron_add_constraint (equalities, cstr);
-  ppl_delete_Constraint (cstr);
-
-  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
-  ppl_delete_Polyhedron (equalities);
-  return res;
-}
-
-/* Returns true when adding the lexicographical constraints at level I
-   to the RES dependence polyhedron returns an empty polyhedron.  */
-
-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;
-
-  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;
-}
-
-/* Build the precedence constraints for the lexicographical comparison
-   of time vectors RES following the lexicographical order.  */
-
-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 (lexicographically_gt_p (*res, dim, offset, direction, 0))
-    return;
-
-  for (i = 0; i < tdim1 - 1; i++)
-    {
-      ppl_Pointset_Powerset_C_Polyhedron_t sceq;
-
-      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);
-    }
-}
-
-/* Build the dependence polyhedron for data references PDR1 and PDR2.
-   The layout of the dependence polyhedron is:
+/* 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 PDR1 and PDR2
+   | 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 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 void
+print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr)
 {
-  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 - 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 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);
+  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);
 
-  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, 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, 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);
+  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));
 
-  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);
-}
-
-/* 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;
-
-  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;
-    }
+  fprintf (file, "#  eq");
 
-  res = dependence_polyhedron_1 (pbb1, pbb2, d1, d2, pdr1, pdr2,
-                                 s1, s2, direction, original_scattering_p);
-
-  if (original_scattering_p)
-    *x = res;
-
-  return res;
-}
-
-static bool
-poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2);
-
-/* Returns the PDDR corresponding to the original schedule, or NULL if
-   the dependence relation is empty or unknown (cannot judge dependency
-   under polyhedral model).  */
+  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);
 
-static poly_ddr_p
-pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
-			  poly_dr_p pdr1, poly_dr_p pdr2)
-{
-  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_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))
-    return NULL;
-
-  pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2,
-				true, true);
-  if (pddr_is_empty (pddr))
-    return NULL;
-
-  return pddr;
+  fprintf (file, "    cst\n");
 }
 
-/* Returns the PDDR corresponding to the transformed schedule, or NULL if
-   the dependence relation is empty or unknown (cannot judge dependency
-   under polyhedral model).  */
+/* Prints to FILE the poly_ddr_p PDDR.  */
 
-static poly_ddr_p
-pddr_transformed_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
-			     poly_dr_p pdr1, poly_dr_p pdr2)
+void
+print_pddr (FILE *file, poly_ddr_p pddr)
 {
-  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 st1 = PBB_ORIGINAL_SCATTERING (pbb1);
-  ppl_Polyhedron_t st2 = PBB_ORIGINAL_SCATTERING (pbb2);
+  fprintf (file, "pddr (kind: ");
 
-  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))
-    return NULL;
-
-  pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, st1, st2,
-				true, false);
-  if (pddr_is_empty (pddr))
-    return NULL;
-
-  return pddr;
-}
-
+  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");
 
-/* Return true when the data dependence relation between the data
-   references PDR1 belonging to PBB1 and PDR2 is part of a
-   reduction.  */
+  fprintf (file, "\n  source ");
+  print_pdr (file, PDDR_SOURCE (pddr), 2);
 
-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 (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
-    if (PDR_TYPE (pdr) == PDR_WRITE)
-      break;
+  fprintf (file, "\n  sink ");
+  print_pdr (file, PDDR_SINK (pddr), 2);
 
-  return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
-}
-
-/* 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.  */
+  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));
+      fprintf (file, ")\n");
+    }
 
-static inline bool
-reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
-		poly_dr_p pdr1, poly_dr_p pdr2)
-{
-  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;
+  fprintf (file, ")\n");
 }
 
-/* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
-   and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
-   functions.  */
-
-static bool
-graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
-			     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_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);
-
-  if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
-    return true;
-
-  pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
-  if (!pddr)
-    return true;
-
-  po = PDDR_DDP (pddr);
-
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "\nloop carries dependency.\n");
+/* Prints to STDERR the poly_ddr_p PDDR.  */
 
-  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);
-
-  ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
-  free_poly_ddr (pddr);
-
-  return is_empty_p;
+void
+debug_pddr (poly_ddr_p pddr)
+{
+  print_pddr (stderr, pddr);
 }
 
-/* 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.  */
-
-static bool
-graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
-{
-  int i, j;
-  poly_dr_p pdr1, pdr2;
-
-  if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
-    pbb_remove_duplicate_pdrs (pbb1);
-
-  if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
-    pbb_remove_duplicate_pdrs (pbb2);
-
-  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++)
-      if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
-	return false;
-
-  return true;
-}
-
-/* Iterates over the SCOP and detect whether the transformed schedule
-   is correct.  */
-
-bool
-graphite_legal_transform (scop_p scop)
-{
-  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;
-}
 
 /* Remove all the dimensions except alias information at dimension
    ALIAS_DIM.  */
@@ -785,6 +269,491 @@
   return !empty_p;
 }
 
+/* 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".  */
+
+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)
+{
+  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;
+
+  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);
+
+  return res;
+}
+
+/* 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 eqs;
+  ppl_Pointset_Powerset_C_Polyhedron_t res;
+  graphite_dim_t i;
+
+  ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0);
+
+  for (i = 0; i < nb_subscripts; i++)
+    {
+      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_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs);
+  ppl_delete_Polyhedron (eqs);
+  return res;
+}
+
+/* Builds scheduling inequality constraints: when DIRECTION is
+   1 builds a GE constraint,
+   0 builds an EQ constraint,
+   -1 builds a LE constraint.  */
+
+static ppl_Pointset_Powerset_C_Polyhedron_t
+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;
+
+  ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
+
+  switch (direction)
+    {
+    case -1:
+      cstr = ppl_build_relation (dim, pos, pos + offset, 1,
+				 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
+      break;
+
+    case 0:
+      cstr = ppl_build_relation (dim, pos, pos + offset, 0,
+				 PPL_CONSTRAINT_TYPE_EQUAL);
+      break;
+
+    case 1:
+      cstr = ppl_build_relation (dim, pos, pos + offset, -1,
+				 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  ppl_Polyhedron_add_constraint (equalities, cstr);
+  ppl_delete_Constraint (cstr);
+
+  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
+  ppl_delete_Polyhedron (equalities);
+  return 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 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_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;
+
+  ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
+
+  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))
+    ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
+
+  ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
+
+  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);
+
+      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);
+    }
+
+  return res;
+}
+
+/* Build the dependence polyhedron for data references PDR1 and PDR2.
+   The layout of the dependence polyhedron is:
+
+   T1|I1|T2|I2|S1|S2|G
+
+   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.
+
+   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
+dependence_polyhedron_1 (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 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 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 idr1, idr2;
+  ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
+
+  gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
+
+  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);
+  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, 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 (sc1);
+  ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
+  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))
+    {
+      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;
+}
+
+/* Build the dependence polyhedron for data references PDR1 and PDR2.
+   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_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;
+
+  /* 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 (scop),
+                          &tmp, INSERT);
+
+      if (x && *x)
+	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 = 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;
+
+  return res;
+}
+
+/* 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 (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
+    if (PDR_TYPE (pdr) == PDR_WRITE)
+      break;
+
+  return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
+}
+
+/* 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);
+
+  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
+   and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
+   functions.  */
+
+static bool
+graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
+{
+  ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
+  graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
+  ppl_Pointset_Powerset_C_Polyhedron_t po_temp;
+  ppl_dimension_type pdim;
+  bool is_empty_p;
+  poly_ddr_p opddr, tpddr;
+  poly_bb_p pbb1, pbb2;
+
+  if (reduction_dr_p (pdr1, pdr2))
+    return true;
+
+  /* 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 = dependence_polyhedron (pdr1, pdr2, 1, true);
+
+  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 = 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);
+      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);
+
+  /* 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);
+  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 (po_temp, pt);
+  is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
+
+  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.  */
+
+static bool
+graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
+{
+  int i, j;
+  poly_dr_p pdr1, pdr2;
+
+  if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
+    pbb_remove_duplicate_pdrs (pbb1);
+
+  if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
+    pbb_remove_duplicate_pdrs (pbb2);
+
+  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++)
+      if (!graphite_legal_transform_dr (pdr1, pdr2))
+	return false;
+
+  return true;
+}
+
+/* Iterates over the SCOP and detect whether the transformed schedule
+   is correct.  */
+
+bool
+graphite_legal_transform (scop_p scop)
+{
+  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;
+}
+
 /* Returns TRUE when the dependence polyhedron between PDR1 and
    PDR2 represents a loop carried dependence at level LEVEL.  */
 
@@ -792,46 +761,36 @@
 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);
+  graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1));
+  graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
   ppl_dimension_type dim;
   bool empty_p;
-  poly_ddr_p pddr;
-  int obj_base_set1 = PDR_BASE_OBJECT_SET (pdr1);
-  int obj_base_set2 = PDR_BASE_OBJECT_SET (pdr2);
-
-  if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
-      || !poly_drs_may_alias_p (pdr1, pdr2))
-    return false;
+  poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
 
-  if (obj_base_set1 != obj_base_set2)
-    return true;
-
-  if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2))
-    return false;
-
-  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);
+  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);
 
   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
+  free_poly_ddr (pddr);
+
   return !empty_p;
 }
 
@@ -872,7 +831,7 @@
       {
 	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))
+	    if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
 	      {
 		fprintf (file, "OS%d -> OS%d\n",
 			 pbb_index (pbb1), pbb_index (pbb2));
@@ -897,12 +856,20 @@
       {
 	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_transformed_scattering (pbb1, pbb2, pdr1, pdr2))
-	      {
-		fprintf (file, "TS%d -> TS%d\n",
-			 pbb_index (pbb1), pbb_index (pbb2));
-		goto done;
-	      }
+	    {
+	      poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
+
+	      if (!pddr_is_empty (pddr))
+		{
+		  fprintf (file, "TS%d -> TS%d\n",
+			   pbb_index (pbb1), pbb_index (pbb2));
+
+		  free_poly_ddr (pddr);
+		  goto done;
+		}
+
+	      free_poly_ddr (pddr);
+	    }
       done:;
       }
 }
@@ -936,7 +903,7 @@
     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))
+	  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));
@@ -956,10 +923,16 @@
     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_transformed_scattering (pbb1, pbb2, pdr1, pdr2))
-	    fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
-		     pbb_index (pbb1), PDR_ID (pdr1),
-		     pbb_index (pbb2), PDR_ID (pdr2));
+	  {
+	    poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
+
+	    if (!pddr_is_empty (pddr))
+	      fprintf (file, "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