[PATCH 12/15] new scop schedule.

[Sebastian Pop <spop@codeaurora.org>]

From: Sebastian Pop <s.pop@samsung.com>

	* graphite-dependences.c (scop_get_reads): Do not call
	isl_union_map_add_map that is undocumented isl functionality.
	(scop_get_must_writes): Same.
	(scop_get_may_writes): Same.
	(scop_get_original_schedule): Remove.
	(scop_get_dependences): Do not call isl_union_map_compute_flow that
	is deprecated in isl 0.15.  Instead, use isl_union_access_* interface.
	(compute_deps): Remove.
	* graphite-isl-ast-to-gimple.c (print_schedule_ast): New.
	(debug_schedule_ast): New.
	(translate_isl_ast_to_gimple::print_isl_ast_node): Removed.
	(translate_isl_ast_to_gimple::get_max_schedule_dimensions): Remove.
	(translate_isl_ast_to_gimple::extend_schedule): Remove.
	(translate_isl_ast_to_gimple::generate_isl_schedule): Remove.
	(translate_isl_ast_to_gimple::set_options): Remove.
	(translate_isl_ast_to_gimple::scop_to_isl_ast): Generate code
	from scop->transformed_schedule.
	(graphite_regenerate_ast_isl): Add more dump.
	* graphite-optimize-isl.c (optimize_isl): Set
	scop->transformed_schedule.  Check whether schedules are equal.
	(apply_poly_transforms): Move here.
	* graphite-poly.c (apply_poly_transforms): ... from here.
	(free_poly_bb): Static.
	(free_scop): Static.
	(pbb_number_of_iterations_at_time): Remove.
	(print_isl_ast): New.
	(debug_isl_ast): New.
	(debug_scop_pbb): New.
	* graphite-scop-detection.c (print_edge): Move.
        (print_sese): Move.
	* graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Remove.
	(build_scop_scattering): Remove.
	(create_pw_aff_from_tree): Assert instead of bailing out.
	(add_condition_to_pbb): Remove unused code, do not fail.
	(add_conditions_to_domain): Same.
	(add_conditions_to_constraints): Remove.
	(build_scop_context): New.
	(add_iter_domain_dimension): New.
	(build_iteration_domains): Initialize pbb->iterators.
	Call add_conditions_to_domain.
	(nested_in): New.
	(loop_at): New.
	(index_outermost_in_loop): New.
	(index_pbb_in_loop): New.
	(outermost_pbb_in): New.
	(add_in_sequence): New.
	(add_outer_projection): New.
	(outer_projection_mupa): New.
	(add_loop_schedule): New.
	(build_schedule_pbb): New.
	(build_schedule_loop): New.
	(embed_in_surrounding_loops): New.
	(build_schedule_loop_nest): New.
	(build_original_schedule): New.
	(build_poly_scop): Call build_original_schedule.
	* graphite.h (free_poly_dr): Remove.
	(struct poly_bb): Add iterators.  Remove schedule, transformed, saved.
        (free_poly_bb): Remove.
        (debug_loop_vec): Remove.
        (print_isl_ast): Declare.
        (debug_isl_ast): Declare.
        (scop_do_interchange): Remove.
        (scop_do_strip_mine): Remove.
        (scop_do_block): Remove.
        (flatten_all_loops): Remove.
        (optimize_isl): Remove.
        (pbb_number_of_iterations_at_time): Remove.
        (debug_scop_pbb): Declare.
        (print_schedule_ast): Declare.
        (debug_schedule_ast): Declare.
        (struct scop): Remove schedule.  Add original_schedule,
        transformed_schedule.
        (free_gimple_poly_bb): Remove.
        (print_generated_program): Remove.
        (debug_generated_program): Remove.
        (unify_scattering_dimensions): Remove.
	* sese.c (print_edge): ... here.
	(print_sese): ... here.
	(debug_edge): ... here.
	(debug_sese): ... here.
	* sese.h (print_edge): Declare.
        (print_sese): Declare.
        (dump_edge): Declare.
        (dump_sese): Declare.

gcc/testsuite

	* gcc.dg/graphite/block-0.c: Adjust pattern.
	* gcc.dg/graphite/block-1.c: Same.
	* gcc.dg/graphite/block-5.c: Same.
	* gcc.dg/graphite/block-6.c: Same.
	* gcc.dg/graphite/block-pr47654.c: Same.
	* gcc.dg/graphite/interchange-0.c: Same.
	* gcc.dg/graphite/interchange-10.c: Same.
	* gcc.dg/graphite/interchange-12.c: Same.
	* gcc.dg/graphite/interchange-14.c: Same.
	* gcc.dg/graphite/interchange-15.c: Same.
	* gcc.dg/graphite/interchange-5.c: Same.
	* gcc.dg/graphite/interchange-6.c: Same.
	* gcc.dg/graphite/interchange-8.c: Same.
	* gcc.dg/graphite/interchange-mvt.c: Same.
	* gcc.dg/graphite/pr35356-1.c: Same.
	* gcc.dg/graphite/scop-10.c (int toto): Same.
	* gcc.dg/graphite/uns-block-1.c: Same.
	* gcc.dg/graphite/uns-interchange-12.c: Same.
	* gcc.dg/graphite/uns-interchange-14.c: Same.
	* gcc.dg/graphite/uns-interchange-15.c: Same.
	* gcc.dg/graphite/uns-interchange-mvt.c: Same.
	* gfortran.dg/graphite/interchange-3.f90: Same.
	* gfortran.dg/graphite/pr14741.f90: Same.
---
 gcc/graphite-dependences.c                         | 169 +++----
 gcc/graphite-isl-ast-to-gimple.c                   | 232 ++-------
 gcc/graphite-optimize-isl.c                        |  83 +++-
 gcc/graphite-poly.c                                | 115 ++---
 gcc/graphite-scop-detection.c                      |  15 -
 gcc/graphite-sese-to-poly.c                        | 531 +++++++++++++--------
 gcc/graphite.h                                     |  41 +-
 gcc/sese.c                                         |  34 ++
 gcc/sese.h                                         |   7 +-
 gcc/testsuite/gcc.dg/graphite/block-0.c            |   2 +-
 gcc/testsuite/gcc.dg/graphite/block-1.c            |   2 +-
 gcc/testsuite/gcc.dg/graphite/block-5.c            |   3 +-
 gcc/testsuite/gcc.dg/graphite/block-6.c            |   2 +-
 gcc/testsuite/gcc.dg/graphite/block-pr47654.c      |   2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-0.c      |   2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-10.c     |   2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-12.c     |   3 +-
 gcc/testsuite/gcc.dg/graphite/interchange-14.c     |   3 +-
 gcc/testsuite/gcc.dg/graphite/interchange-15.c     |   2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-5.c      |   2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-6.c      |   2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-8.c      |   3 +-
 gcc/testsuite/gcc.dg/graphite/interchange-mvt.c    |   2 +-
 gcc/testsuite/gcc.dg/graphite/pr35356-1.c          |   3 +-
 gcc/testsuite/gcc.dg/graphite/scop-10.c            |   2 +-
 gcc/testsuite/gcc.dg/graphite/uns-block-1.c        |   2 +-
 gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c |   3 +-
 gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c |   3 +-
 gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c |   2 +-
 .../gcc.dg/graphite/uns-interchange-mvt.c          |   2 +-
 .../gfortran.dg/graphite/interchange-3.f90         |   2 +-
 gcc/testsuite/gfortran.dg/graphite/pr14741.f90     |   2 +-
 32 files changed, 613 insertions(+), 667 deletions(-)

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index ae08059..161e019 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -66,7 +66,7 @@ add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
 /* Returns all the memory reads in SCOP.  */
 
 static isl_union_map *
-scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
+scop_get_reads (scop_p scop)
 {
   int i, j;
   poly_bb_p pbb;
@@ -74,7 +74,7 @@ scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
   isl_space *space = isl_set_get_space (scop->param_context);
   isl_union_map *res = isl_union_map_empty (space);
 
-  FOR_EACH_VEC_ELT (pbbs, i, pbb)
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     {
       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 	if (pdr_read_p (pdr))
@@ -84,7 +84,9 @@ scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
 		fprintf (dump_file, "Adding read to depedence graph: ");
 		print_pdr (dump_file, pdr);
 	      }
-	    res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+	    isl_union_map *um
+	      = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
+	    res = isl_union_map_union (res, um);
 	    if (dump_file)
 	      {
 		fprintf (dump_file, "Reads depedence graph: ");
@@ -99,7 +101,7 @@ scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
 /* Returns all the memory must writes in SCOP.  */
 
 static isl_union_map *
-scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
+scop_get_must_writes (scop_p scop)
 {
   int i, j;
   poly_bb_p pbb;
@@ -107,7 +109,7 @@ scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
   isl_space *space = isl_set_get_space (scop->param_context);
   isl_union_map *res = isl_union_map_empty (space);
 
-  FOR_EACH_VEC_ELT (pbbs, i, pbb)
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     {
       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 	if (pdr_write_p (pdr))
@@ -117,7 +119,9 @@ scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
 		fprintf (dump_file, "Adding must write to depedence graph: ");
 		print_pdr (dump_file, pdr);
 	      }
-	    res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+	    isl_union_map *um
+	      = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
+	    res = isl_union_map_union (res, um);
 	    if (dump_file)
 	      {
 		fprintf (dump_file, "Must writes depedence graph: ");
@@ -132,7 +136,7 @@ scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
 /* Returns all the memory may writes in SCOP.  */
 
 static isl_union_map *
-scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
+scop_get_may_writes (scop_p scop)
 {
   int i, j;
   poly_bb_p pbb;
@@ -140,7 +144,7 @@ scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
   isl_space *space = isl_set_get_space (scop->param_context);
   isl_union_map *res = isl_union_map_empty (space);
 
-  FOR_EACH_VEC_ELT (pbbs, i, pbb)
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     {
       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr)
 	if (pdr_may_write_p (pdr))
@@ -150,7 +154,9 @@ scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
 		fprintf (dump_file, "Adding may write to depedence graph: ");
 		print_pdr (dump_file, pdr);
 	      }
-	    res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb));
+	    isl_union_map *um
+	      = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
+	    res = isl_union_map_union (res, um);
 	    if (dump_file)
 	      {
 		fprintf (dump_file, "May writes depedence graph: ");
@@ -162,26 +168,6 @@ scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
   return isl_union_map_coalesce (res);
 }
 
-/* Returns all the original schedules in SCOP.  */
-
-static isl_union_map *
-scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
-{
-  int i;
-  poly_bb_p pbb;
-  isl_space *space = isl_set_get_space (scop->param_context);
-  isl_union_map *res = isl_union_map_empty (space);
-
-  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 isl_union_map_coalesce (res);
-}
-
 /* Helper function used on each MAP of a isl_union_map.  Computes the
    maximal output dimension.  */
 
@@ -303,34 +289,20 @@ carries_deps (__isl_keep isl_union_map *schedule,
   return res;
 }
 
-/* Compute the original data dependences in SCOP for all the reads and
-   writes in PBBS.  */
-
-static 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)
+/* Compute the dependence relations for the SCOP:
+   RAW are read after write dependences,
+   WAR are write after read dependences,
+   WAW are write after write dependences.  */
+
+void
+scop_get_dependences (scop_p scop)
 {
-  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));
-  all_writes = isl_union_map_coalesce (all_writes);
+  if (scop->dependence)
+    return;
 
-  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);
+  isl_union_map *reads = scop_get_reads (scop);
+  isl_union_map *must_writes = scop_get_must_writes (scop);
+  isl_union_map *may_writes = scop_get_may_writes (scop);
 
   if (dump_file)
     {
@@ -357,57 +329,40 @@ compute_deps (scop_p scop, vec<poly_bb_p> pbbs,
       print_isl_union_map (dump_file, must_writes);
       fprintf (dump_file, "  may_writes: ");
       print_isl_union_map (dump_file, may_writes);
-      fprintf (dump_file, "  all_writes: ");
-      print_isl_union_map (dump_file, all_writes);
       fprintf (dump_file, ")\n");
     }
 
-  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);
-  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);
-  isl_union_map_compute_flow (all_writes, must_writes, may_writes,
-			      original,
-			      must_waw, may_waw, must_waw_no_source,
-			      may_waw_no_source);
-}
-
-isl_union_map *
-scop_get_dependences (scop_p scop)
-{
-  if (scop->dependence)
-    return scop->dependence;
-
-  /* The original dependence relations:
-     RAW are read after write dependences,
-     WAR are write after read dependences,
-     WAW are write after write dependences.  */
-  isl_union_map *must_raw = NULL, *may_raw = NULL, *must_raw_no_source = NULL,
-      *may_raw_no_source = NULL, *must_war = NULL, *may_war = NULL,
-      *must_war_no_source = NULL, *may_war_no_source = NULL, *must_waw = NULL,
-      *may_waw = NULL, *must_waw_no_source = NULL, *may_waw_no_source = NULL;
-
-  compute_deps (scop, scop->pbbs,
-		  &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);
-
-  isl_union_map *dependences = must_raw;
-  dependences = isl_union_map_union (dependences, must_war);
-  dependences = isl_union_map_union (dependences, must_waw);
-  dependences = isl_union_map_union (dependences, may_raw);
-  dependences = isl_union_map_union (dependences, may_war);
-  dependences = isl_union_map_union (dependences, may_waw);
+  gcc_assert (scop->original_schedule);
+
+  isl_union_access_info *ai;
+  ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
+  ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
+  ai = isl_union_access_info_set_may_source (ai, may_writes);
+  ai = isl_union_access_info_set_schedule
+    (ai, isl_schedule_copy (scop->original_schedule));
+  isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
+  isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
+  isl_union_flow_free (flow);
+
+  ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
+  ai = isl_union_access_info_set_must_source (ai, must_writes);
+  ai = isl_union_access_info_set_may_source (ai, reads);
+  ai = isl_union_access_info_set_schedule
+    (ai, isl_schedule_copy (scop->original_schedule));
+  flow = isl_union_access_info_compute_flow (ai);
+
+  isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
+  isl_union_map *war = isl_union_flow_get_may_dependence (flow);
+  war = isl_union_map_subtract (war, isl_union_map_copy (waw));
+  isl_union_flow_free (flow);
+
+  raw = isl_union_map_coalesce (raw);
+  waw = isl_union_map_coalesce (waw);
+  war = isl_union_map_coalesce (war);
+
+  isl_union_map *dependences = raw;
+  dependences = isl_union_map_union (dependences, war);
+  dependences = isl_union_map_union (dependences, waw);
   dependences = isl_union_map_coalesce (dependences);
 
   if (dump_file)
@@ -417,15 +372,7 @@ scop_get_dependences (scop_p scop)
       fprintf (dump_file, ")\n");
     }
 
-  isl_union_map_free (must_raw_no_source);
-  isl_union_map_free (may_raw_no_source);
-  isl_union_map_free (must_war_no_source);
-  isl_union_map_free (may_war_no_source);
-  isl_union_map_free (must_waw_no_source);
-  isl_union_map_free (may_waw_no_source);
-
   scop->dependence = dependences;
-  return dependences;
 }
 
 #endif /* HAVE_isl */
diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c
index a196419..2823d22 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -105,7 +105,7 @@ typedef std::map<isl_id *, tree> ivs_params;
 
 /* Free all memory allocated for isl's identifiers.  */
 
-void ivs_params_clear (ivs_params &ip)
+static void ivs_params_clear (ivs_params &ip)
 {
   std::map<isl_id *, tree>::iterator it;
   for (it = ip.begin ();
@@ -117,7 +117,7 @@ void ivs_params_clear (ivs_params &ip)
 
 /* Set the "separate" option for the schedule node.  */
 
-static __isl_give isl_schedule_node *
+static isl_schedule_node *
 set_separate_option (__isl_take isl_schedule_node *node, void *user)
 {
   if (user)
@@ -135,6 +135,26 @@ set_separate_option (__isl_take isl_schedule_node *node, void *user)
   return node;
 }
 
+/* Print SCHEDULE under an AST form on file F.  */
+
+void
+print_schedule_ast (FILE *f, __isl_keep isl_schedule *schedule, scop_p scop)
+{
+  isl_set *set = isl_set_params (isl_set_copy (scop->param_context));
+  isl_ast_build *context = isl_ast_build_from_context (set);
+  isl_ast_node *ast
+    = isl_ast_build_node_from_schedule (context, isl_schedule_copy (schedule));
+  isl_ast_build_free (context);
+  print_isl_ast (f, ast);
+  isl_ast_node_free (ast);
+}
+
+DEBUG_FUNCTION void
+debug_schedule_ast (__isl_keep isl_schedule *s, scop_p scop)
+{
+  print_schedule_ast (stderr, s, scop);
+}
+
 enum phi_node_kind
 {
   unknown_phi,
@@ -285,40 +305,13 @@ class translate_isl_ast_to_gimple
 
   void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip);
 
-  /* Get the maximal number of schedule dimensions in the scop SCOP.  */
-
-  int get_max_schedule_dimensions (scop_p scop);
-
   /* Generates a build, which specifies the constraints on the parameters.  */
 
   __isl_give isl_ast_build *generate_isl_context (scop_p scop);
 
-  /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
-
-     For schedules with different dimensionality, the isl AST generator can not
-     define an order and will just randomly choose an order.  The solution to
-     this problem is to extend all schedules to the maximal number of schedule
-     dimensions (using '0's for the remaining values).  */
-
-  __isl_give isl_map *extend_schedule (__isl_take isl_map *schedule,
-				       int nb_schedule_dims);
-
-  /* Generates a schedule, which specifies an order used to
-     visit elements in a domain.  */
-
-  __isl_give isl_union_map *generate_isl_schedule (scop_p scop);
-
-  /* Set the separate option for all dimensions.
-     This helps to reduce control overhead.  */
-
-  __isl_give isl_ast_build * set_options (__isl_take isl_ast_build *control,
-					  __isl_keep isl_union_map *schedule);
-
-  /* Generate isl AST from schedule of SCOP.  Also, collects IVS_PARAMS in
-     IP.  */
-
-  __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop, ivs_params &ip);
+  /* Generate isl AST from schedule of SCOP.  */
 
+  __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop);
 
   /* Return true if RENAME (defined in BB) is a valid use in NEW_BB.  The
      definition should flow into use, and the use should respect the loop-closed
@@ -474,11 +467,6 @@ class translate_isl_ast_to_gimple
   bool codegen_error_p () const
   { return codegen_error; }
 
-  /* Prints NODE to FILE.  */
-
-  void print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
-			   __isl_keep isl_ctx *ctx) const;
-
   /* Return true when OP is a constant tree.  */
 
   bool is_constant (tree op) const
@@ -1365,7 +1353,7 @@ is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb,
     {
       if (dump_file)
 	{
-	  fprintf (dump_file, "[codegen] rename not in loop closed ssa:");
+	  fprintf (dump_file, "[codegen] rename not in loop closed ssa: ");
 	  print_generic_expr (dump_file, rename, 0);
 	  fprintf (dump_file, "\n");
 	}
@@ -3052,20 +3040,6 @@ translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
     }
 }
 
-/* Prints NODE to FILE.  */
-
-void
-translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file,
-						 __isl_keep isl_ast_node *node,
-						 __isl_keep isl_ctx *ctx) const
-{
-  isl_printer *prn = isl_printer_to_file (ctx, file);
-  prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
-  prn = isl_printer_print_ast_node (prn, node);
-  prn = isl_printer_print_str (prn, "\n");
-  isl_printer_free (prn);
-}
-
 /* Add isl's parameter identifiers and corresponding trees to ivs_params.  */
 
 void
@@ -3094,83 +3068,6 @@ translate_isl_ast_to_gimple::generate_isl_context (scop_p scop)
   return isl_ast_build_from_context (context_isl);
 }
 
-/* Get the maximal number of schedule dimensions in the scop SCOP.  */
-
-int
-translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop)
-{
-  int i;
-  poly_bb_p pbb;
-  int schedule_dims = 0;
-
-  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
-    {
-      int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
-      if (pbb_schedule_dims > schedule_dims)
-	schedule_dims = pbb_schedule_dims;
-    }
-
-  return schedule_dims;
-}
-
-/* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
-
-   For schedules with different dimensionality, the isl AST generator can not
-   define an order and will just randomly choose an order.  The solution to this
-   problem is to extend all schedules to the maximal number of schedule
-   dimensions (using '0's for the remaining values).  */
-
-__isl_give isl_map *
-translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map *schedule,
-					      int nb_schedule_dims)
-{
-  int tmp_dims = isl_map_dim (schedule, isl_dim_out);
-  schedule =
-    isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
-  isl_val *zero =
-    isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
-  int i;
-  for (i = tmp_dims; i < nb_schedule_dims; i++)
-    {
-      schedule
-	= isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
-    }
-  isl_val_free (zero);
-  return schedule;
-}
-
-/* Generates a schedule, which specifies an order used to
-   visit elements in a domain.  */
-
-__isl_give isl_union_map *
-translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop)
-{
-  int nb_schedule_dims = get_max_schedule_dimensions (scop);
-  int i;
-  poly_bb_p pbb;
-  isl_union_map *schedule_isl =
-    isl_union_map_empty (isl_set_get_space (scop->param_context));
-
-  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
-    {
-      /* Dead code elimination: when the domain of a PBB is empty,
-	 don't generate code for the PBB.  */
-      if (isl_set_is_empty (pbb->domain))
-	continue;
-
-      isl_map *bb_schedule = isl_map_copy (pbb->transformed);
-      bb_schedule = isl_map_intersect_domain (bb_schedule,
-					      isl_set_copy (pbb->domain));
-      bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
-      bb_schedule = isl_map_coalesce (bb_schedule);
-      schedule_isl
-	= isl_union_map_union (schedule_isl,
-			       isl_union_map_from_map (bb_schedule));
-      schedule_isl = isl_union_map_coalesce (schedule_isl);
-    }
-  return schedule_isl;
-}
-
 /* This method is executed before the construction of a for node.  */
 __isl_give isl_id *
 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
@@ -3188,63 +3085,28 @@ ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
   return id;
 }
 
-/* Set the separate option for all dimensions.
-   This helps to reduce control overhead.  */
-
-__isl_give isl_ast_build *
-translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build *control,
-					  __isl_keep isl_union_map *schedule)
-{
-  isl_ctx *ctx = isl_union_map_get_ctx (schedule);
-  isl_space *range_space = isl_space_set_alloc (ctx, 0, 1);
-  range_space =
-    isl_space_set_tuple_name (range_space, isl_dim_set, "separate");
-  isl_union_set *range =
-    isl_union_set_from_set (isl_set_universe (range_space));
-  isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule));
-  domain = isl_union_set_universe (domain);
-  isl_union_map *options = isl_union_map_from_domain_and_range (domain, range);
-  return isl_ast_build_set_options (control, options);
-}
-
-/* Generate isl AST from schedule of SCOP.  Also, collects IVS_PARAMS in IP.  */
+/* Generate isl AST from schedule of SCOP.  */
 
 __isl_give isl_ast_node *
-translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop, ivs_params &ip)
+translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop)
 {
-  /* Generate loop upper bounds that consist of the current loop iterator, an
-     operator (< or <=) and an expression not involving the iterator.  If this
-     option is not set, then the current loop iterator may appear several times
-     in the upper bound.  See the isl manual for more details.  */
-  isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, true);
-
-  add_parameters_to_ivs_params (scop, ip);
+  gcc_assert (scop->transformed_schedule);
 
-  if (scop->schedule)
-    {
-      /* Set the separate option to reduce control flow overhead.  */
-      isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up
-	(scop->schedule, set_separate_option, NULL);
-      isl_ast_build *context_isl = generate_isl_context (scop);
-      isl_ast_node *ast_isl = isl_ast_build_node_from_schedule
-	(context_isl, schedule);
-      isl_ast_build_free (context_isl);
-      return ast_isl;
-    }
-
-  /* graphite-identity, or parallelize.  */
-  isl_union_map *schedule_isl = generate_isl_schedule (scop);
+  /* Set the separate option to reduce control flow overhead.  */
+  isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up
+    (isl_schedule_copy (scop->transformed_schedule), set_separate_option, NULL);
   isl_ast_build *context_isl = generate_isl_context (scop);
-  context_isl = set_options (context_isl, schedule_isl);
+
   if (flag_loop_parallelize_all)
     {
-      isl_union_map *dependence = scop_get_dependences (scop);
+      scop_get_dependences (scop);
       context_isl =
 	isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
-					   dependence);
+					   scop->dependence);
     }
-  isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule
-    (context_isl, schedule_isl);
+
+  isl_ast_node *ast_isl = isl_ast_build_node_from_schedule
+    (context_isl, schedule);
   isl_ast_build_free (context_isl);
   return ast_isl;
 }
@@ -3266,12 +3128,20 @@ graphite_regenerate_ast_isl (scop_p scop)
   ivs_params ip;
 
   timevar_push (TV_GRAPHITE_CODE_GEN);
-  root_node = t.scop_to_isl_ast (scop, ip);
+  t.add_parameters_to_ivs_params (scop, ip);
+  root_node = t.scop_to_isl_ast (scop);
 
-  if (dump_file && (dump_flags & TDF_DETAILS))
+  if (dump_file)
     {
-      fprintf (dump_file, "AST generated by isl: \n");
-      t.print_isl_ast_node (dump_file, root_node, scop->isl_context);
+      fprintf (dump_file, "[scheduler] original schedule:\n");
+      print_isl_schedule (dump_file, scop->original_schedule);
+      fprintf (dump_file, "[scheduler] isl transformed schedule:\n");
+      print_isl_schedule (dump_file, scop->transformed_schedule);
+
+      fprintf (dump_file, "[scheduler] original ast:\n");
+      print_schedule_ast (dump_file, scop->original_schedule, scop);
+      fprintf (dump_file, "[scheduler] AST generated by isl:\n");
+      print_isl_ast (dump_file, root_node);
     }
 
   recompute_all_dominators ();
@@ -3293,8 +3163,8 @@ graphite_regenerate_ast_isl (scop_p scop)
   if (t.codegen_error_p ())
     {
       if (dump_file)
-	fprintf (dump_file, "[codegen] unsuccessful,"
-		 " reverting back to the original code.\n");
+	fprintf (dump_file, "codegen error: "
+		 "reverting back to the original code.\n");
       set_ifsese_condition (if_region, integer_zero_node);
     }
   else
diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c
index 306f91c..f385c77 100644
--- a/gcc/graphite-optimize-isl.c
+++ b/gcc/graphite-optimize-isl.c
@@ -56,7 +56,7 @@ scop_get_domains (scop_p scop)
 /* Compute the schedule for SCOP based on its parameters, domain and set of
    constraints.  Then apply the schedule to SCOP.  */
 
-bool
+static bool
 optimize_isl (scop_p scop)
 {
   int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
@@ -66,57 +66,88 @@ optimize_isl (scop_p scop)
   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
 
   isl_union_set *domain = scop_get_domains (scop);
+
+  /* Simplify the dependences on the domain.  */
   scop_get_dependences (scop);
-  scop->dependence
-    = isl_union_map_gist_domain (scop->dependence, isl_union_set_copy (domain));
-  scop->dependence
-    = isl_union_map_gist_range (scop->dependence, isl_union_set_copy (domain));
-  isl_union_map *validity = isl_union_map_copy (scop->dependence);
+  isl_union_map *dependences
+    = isl_union_map_gist_domain (isl_union_map_copy (scop->dependence),
+				 isl_union_set_copy (domain));
+  isl_union_map *validity
+    = isl_union_map_gist_range (dependences, isl_union_set_copy (domain));
+
+  /* FIXME: proximity should not be validity.  */
   isl_union_map *proximity = isl_union_map_copy (validity);
 
-  isl_schedule_constraints *schedule_constraints;
-  schedule_constraints = isl_schedule_constraints_on_domain (domain);
-  schedule_constraints
-    = isl_schedule_constraints_set_proximity (schedule_constraints,
-                                             proximity);
-  schedule_constraints
-    = isl_schedule_constraints_set_validity (schedule_constraints,
-                                            isl_union_map_copy (validity));
-  schedule_constraints
-    = isl_schedule_constraints_set_coincidence (schedule_constraints,
-                                               validity);
+  isl_schedule_constraints *sc = isl_schedule_constraints_on_domain (domain);
+  sc = isl_schedule_constraints_set_proximity (sc, proximity);
+  sc = isl_schedule_constraints_set_validity (sc, isl_union_map_copy (validity));
+  sc = isl_schedule_constraints_set_coincidence (sc, validity);
 
   isl_options_set_schedule_serialize_sccs (scop->isl_context, 0);
   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
   isl_options_set_schedule_max_constant_term (scop->isl_context, 20);
   isl_options_set_schedule_max_coefficient (scop->isl_context, 20);
   isl_options_set_tile_scale_tile_loops (scop->isl_context, 0);
+  /* Generate loop upper bounds that consist of the current loop iterator, an
+     operator (< or <=) and an expression not involving the iterator.  If this
+     option is not set, then the current loop iterator may appear several times
+     in the upper bound.  See the isl manual for more details.  */
   isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1);
 
-  isl_schedule *schedule
-    = isl_schedule_constraints_compute_schedule (schedule_constraints);
+  scop->transformed_schedule = isl_schedule_constraints_compute_schedule (sc);
   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);
 
   isl_ctx_reset_operations (scop->isl_context);
   isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
-  if (!schedule || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
+  if (!scop->transformed_schedule
+      || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
     {
       if (dump_file && dump_flags)
 	fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n",
 		 max_operations);
-      if (schedule)
-	isl_schedule_free (schedule);
       return false;
     }
 
-  scop->schedule = schedule;
+  gcc_assert (scop->original_schedule);
+  isl_union_map *original = isl_schedule_get_map (scop->original_schedule);
+  isl_union_map *transformed = isl_schedule_get_map (scop->transformed_schedule);
+  bool same_schedule = isl_union_map_is_equal (original, transformed);
+  isl_union_map_free (original);
+  isl_union_map_free (transformed);
 
-  if (dump_file)
+  if (same_schedule)
     {
-      fprintf (dump_file, "isl end schedule:\n");
-      print_isl_schedule (dump_file, scop->schedule);
+      if (dump_file)
+	{
+	  fprintf (dump_file, "[scheduler] isl optimized schedule is "
+		   "identical to the original schedule.\n");
+	  print_schedule_ast (dump_file, scop->original_schedule, scop);
+	}
+      isl_schedule_free (scop->transformed_schedule);
+      scop->transformed_schedule = isl_schedule_copy (scop->original_schedule);
+      return false;
     }
 
   return true;
 }
+
+/* Apply graphite transformations to all the basic blocks of SCOP.  */
+
+bool
+apply_poly_transforms (scop_p scop)
+{
+  if (flag_loop_nest_optimize)
+    return optimize_isl (scop);
+
+  if (!flag_graphite_identity && !flag_loop_parallelize_all)
+    return false;
+
+  /* Generate code even if we did not apply any real transformation.
+     This also allows to check the performance for the identity
+     transformation: GIMPLE -> GRAPHITE -> GIMPLE.  */
+  gcc_assert (scop->original_schedule);
+  scop->transformed_schedule = isl_schedule_copy (scop->original_schedule);
+  return true;
+}
+
 #endif /* HAVE_isl */
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index de7515a..c1dd5ce 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -86,23 +86,6 @@ debug_iteration_domains (scop_p scop)
   print_iteration_domains (stderr, scop);
 }
 
-/* Apply graphite transformations to all the basic blocks of SCOP.  */
-
-bool
-apply_poly_transforms (scop_p scop)
-{
-  if (flag_loop_nest_optimize && optimize_isl (scop))
-    return true;
-
-  if (!flag_graphite_identity && !flag_loop_parallelize_all)
-    return false;
-
-  /* Generate code even if we did not apply any real transformation.
-     This also allows to check the performance for the identity
-     transformation: GIMPLE -> GRAPHITE -> GIMPLE.  */
-  return true;
-}
-
 /* Create a new polyhedral data reference and add it to PBB.  It is
    defined by its ACCESSES, its TYPE, and the number of subscripts
    NB_SUBSCRIPTS.  */
@@ -137,7 +120,7 @@ new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type,
 
 /* Free polyhedral data reference PDR.  */
 
-void
+static void
 free_poly_dr (poly_dr_p pdr)
 {
   isl_map_free (pdr->accesses);
@@ -153,9 +136,7 @@ new_poly_bb (scop_p scop, gimple_poly_bb_p black_box)
   poly_bb_p pbb = XNEW (struct poly_bb);
 
   pbb->domain = NULL;
-  pbb->schedule = NULL;
-  pbb->transformed = NULL;
-  pbb->saved = NULL;
+  pbb->iterators = NULL;
   PBB_SCOP (pbb) = scop;
   pbb_set_black_box (pbb, black_box);
   PBB_DRS (pbb).create (3);
@@ -166,16 +147,16 @@ new_poly_bb (scop_p scop, gimple_poly_bb_p black_box)
 
 /* Free polyhedral black box.  */
 
-void
+static void
 free_poly_bb (poly_bb_p pbb)
 {
   int i;
   poly_dr_p pdr;
 
   isl_set_free (pbb->domain);
-  isl_map_free (pbb->schedule);
-  isl_map_free (pbb->transformed);
-  isl_map_free (pbb->saved);
+  isl_set_free (pbb->iterators);
+  pbb->domain = NULL;
+  pbb->iterators = NULL;
 
   if (PBB_DRS (pbb).exists ())
     FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
@@ -246,7 +227,7 @@ new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs,
 
 /* Frees GBB.  */
 
-void
+static void
 free_gimple_poly_bb (gimple_poly_bb_p gbb)
 {
   free_data_refs (GBB_DATA_REFS (gbb));
@@ -277,7 +258,8 @@ new_scop (edge entry, edge exit)
   sese_info_p region = new_sese_info (entry, exit);
   scop_p s = XNEW (struct scop);
 
-  s->schedule = NULL;
+  s->original_schedule = NULL;
+  s->transformed_schedule = NULL;
   s->param_context = NULL;
   scop_set_region (s, region);
   s->pbbs.create (3);
@@ -305,7 +287,13 @@ free_scop (scop_p scop)
 
   isl_set_free (scop->param_context);
   isl_union_map_free (scop->dependence);
+  isl_schedule_free (scop->original_schedule);
+  isl_schedule_free (scop->transformed_schedule);
+
+  scop->param_context = NULL;
   scop->dependence = NULL;
+  scop->original_schedule = NULL;
+  scop->transformed_schedule = NULL;
   XDELETE (scop);
 }
 
@@ -530,7 +518,7 @@ debug_scop_params (scop_p scop)
 
 extern isl_ctx *the_isl_ctx;
 void
-print_isl_set (FILE *f, isl_set *set)
+print_isl_set (FILE *f, __isl_keep isl_set *set)
 {
   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
@@ -540,13 +528,13 @@ print_isl_set (FILE *f, isl_set *set)
 }
 
 DEBUG_FUNCTION void
-debug_isl_set (isl_set *set)
+debug_isl_set (__isl_keep isl_set *set)
 {
   print_isl_set (stderr, set);
 }
 
 void
-print_isl_map (FILE *f, isl_map *map)
+print_isl_map (FILE *f, __isl_keep isl_map *map)
 {
   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
@@ -556,13 +544,13 @@ print_isl_map (FILE *f, isl_map *map)
 }
 
 DEBUG_FUNCTION void
-debug_isl_map (isl_map *map)
+debug_isl_map (__isl_keep isl_map *map)
 {
   print_isl_map (stderr, map);
 }
 
 void
-print_isl_union_map (FILE *f, isl_union_map *map)
+print_isl_union_map (FILE *f, __isl_keep isl_union_map *map)
 {
   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
@@ -579,7 +567,7 @@ debug_isl_union_map (isl_union_map *map)
 
 
 void
-print_isl_aff (FILE *f, isl_aff *aff)
+print_isl_aff (FILE *f, __isl_keep isl_aff *aff)
 {
   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
   p = isl_printer_print_aff (p, aff);
@@ -588,13 +576,13 @@ print_isl_aff (FILE *f, isl_aff *aff)
 }
 
 DEBUG_FUNCTION void
-debug_isl_aff (isl_aff *aff)
+debug_isl_aff (__isl_keep isl_aff *aff)
 {
   print_isl_aff (stderr, aff);
 }
 
 void
-print_isl_constraint (FILE *f, isl_constraint *c)
+print_isl_constraint (FILE *f, __isl_keep isl_constraint *c)
 {
   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
   p = isl_printer_print_constraint (p, c);
@@ -603,13 +591,13 @@ print_isl_constraint (FILE *f, isl_constraint *c)
 }
 
 DEBUG_FUNCTION void
-debug_isl_constraint (isl_constraint *c)
+debug_isl_constraint (__isl_keep isl_constraint *c)
 {
   print_isl_constraint (stderr, c);
 }
 
 void
-print_isl_schedule (FILE *f, isl_schedule *s)
+print_isl_schedule (FILE *f, __isl_keep isl_schedule *s)
 {
   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
@@ -624,41 +612,26 @@ debug_isl_schedule (isl_schedule *s)
   print_isl_schedule (stderr, s);
 }
 
-/* Returns the number of iterations RES of the loop around PBB at
-   time(scattering) dimension TIME_DEPTH.  */
-
 void
-pbb_number_of_iterations_at_time (poly_bb_p pbb,
-				  graphite_dim_t time_depth,
-				  mpz_t res)
-{
-  isl_set *transdomain;
-  isl_space *dc;
-  isl_aff *aff;
-  isl_val *isllb, *islub;
-
-  /* Map the iteration domain through the current scatter, and work
-     on the resulting set.  */
-  transdomain = isl_set_apply (isl_set_copy (pbb->domain),
-			       isl_map_copy (pbb->transformed));
-
-  /* Select the time_depth' dimension via an affine expression.  */
-  dc = isl_set_get_space (transdomain);
-  aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
-  aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1);
-
-  /* And find the min/max for that function.  */
-  /* XXX isl check results?  */
-  isllb = isl_set_min_val (transdomain, aff);
-  islub = isl_set_max_val (transdomain, aff);
-
-  islub = isl_val_sub (islub, isllb);
-  islub = isl_val_add_ui (islub, 1);
-  isl_val_get_num_gmp (islub, res);
-
-  isl_val_free (islub);
-  isl_aff_free (aff);
-  isl_set_free (transdomain);
+print_isl_ast (FILE *file, __isl_keep isl_ast_node *n)
+{
+  isl_printer *prn = isl_printer_to_file (the_isl_ctx, file);
+  prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
+  prn = isl_printer_print_ast_node (prn, n);
+  prn = isl_printer_print_str (prn, "\n");
+  isl_printer_free (prn);
+}
+
+DEBUG_FUNCTION void
+debug_isl_ast (isl_ast_node *n)
+{
+  print_isl_ast (stderr, n);
+}
+
+DEBUG_FUNCTION void
+debug_scop_pbb (scop_p scop, int i)
+{
+  debug_pbb (scop->pbbs[i]);
 }
 
 #endif  /* HAVE_isl */
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index f035e0d..8dfb20a 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -522,21 +522,6 @@ public:
 
   static edge get_nearest_pdom_with_single_exit (basic_block dom);
 
-
-  /* Pretty printers.  */
-
-  static void print_edge (FILE *file, const_edge e)
-  {
-    fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
-  }
-
-  static void print_sese (FILE *file, sese_l s)
-  {
-    fprintf (file, "(entry_"); print_edge (file, s.entry);
-    fprintf (file, ", exit_"); print_edge (file, s.exit);
-    fprintf (file, ")\n");
-  }
-
   /* Merge scops at same loop depth and returns the new sese.
      Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index abf18a7..885e0b7 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -77,151 +77,6 @@ isl_id_for_pbb (scop_p s, poly_bb_p pbb)
   return isl_id_alloc (s->isl_context, name, pbb);
 }
 
-/* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
-   We generate SCATTERING_DIMENSIONS scattering dimensions.
-
-   The scattering polyhedron consists of these dimensions: scattering,
-   loop_iterators, parameters.
-
-   Example:
-
-   | scattering_dimensions = 5
-   | nb_iterators = 1
-   | scop_nb_params = 2
-   |
-   | Schedule:
-   |   i
-   | 4 5
-   |
-   | Scattering polyhedron:
-   |
-   | scattering: {s1, s2, s3, s4, s5}
-   | loop_iterators: {i}
-   | parameters: {p1, p2}
-   |
-   | s1  s2  s3  s4  s5  i   p1  p2  1
-   | 1   0   0   0   0   0   0   0  -4  = 0
-   | 0   1   0   0   0  -1   0   0   0  = 0
-   | 0   0   1   0   0   0   0   0  -5  = 0  */
-
-static void
-build_pbb_scattering_polyhedrons (isl_aff *static_sched,
-				  poly_bb_p pbb)
-{
-  isl_val *val;
-
-  int scattering_dimensions = isl_set_dim (pbb->domain, isl_dim_set) * 2 + 1;
-
-  isl_space *dc = isl_set_get_space (pbb->domain);
-  isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc),
-				      isl_dim_out, scattering_dimensions);
-  pbb->schedule = isl_map_universe (dm);
-
-  for (int i = 0; i < scattering_dimensions; i++)
-    {
-      /* Textual order inside this loop.  */
-      if ((i % 2) == 0)
-	{
-	  isl_constraint *c = isl_equality_alloc
-	      (isl_local_space_from_space (isl_map_get_space (pbb->schedule)));
-
-	  val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, i / 2);
-	  gcc_assert (val && isl_val_is_int (val));
-
-	  val = isl_val_neg (val);
-	  c = isl_constraint_set_constant_val (c, val);
-	  c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
-	  pbb->schedule = isl_map_add_constraint (pbb->schedule, c);
-	}
-
-      /* Iterations of this loop.  */
-      else /* if ((i % 2) == 1) */
-	{
-	  int loop = (i - 1) / 2;
-	  pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, loop,
-					  isl_dim_out, i);
-	}
-    }
-
-  /* Simplify the original schedule.  */
-  pbb->schedule = isl_map_coalesce (pbb->schedule);
-
-  /* At the beginning, set the transformed schedule to the original.  */
-  pbb->transformed = isl_map_copy (pbb->schedule);
-}
-
-/* Build for BB the static schedule.
-
-   The static schedule is a Dewey numbering of the abstract syntax
-   tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
-
-   The following example informally defines the static schedule:
-
-   A
-   for (i: ...)
-     {
-       for (j: ...)
-         {
-           B
-           C
-         }
-
-       for (k: ...)
-         {
-           D
-           E
-         }
-     }
-   F
-
-   Static schedules for A to F:
-
-     DEPTH
-     0 1 2
-   A 0
-   B 1 0 0
-   C 1 0 1
-   D 1 1 0
-   E 1 1 1
-   F 2
-*/
-
-static void
-build_scop_scattering (scop_p scop)
-{
-  gimple_poly_bb_p previous_gbb = NULL;
-  isl_space *dc = isl_set_get_space (scop->param_context);
-  isl_aff *static_sched;
-
-  dc = isl_space_add_dims (dc, isl_dim_set, number_of_loops (cfun));
-  static_sched = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
-
-  /* We have to start schedules at 0 on the first component and
-     because we cannot compare_prefix_loops against a previous loop,
-     prefix will be equal to zero, and that index will be
-     incremented before copying.  */
-  static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, 0, -1);
-
-  int i;
-  poly_bb_p pbb;
-  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
-    {
-      gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
-      int prefix = 0;
-
-      if (previous_gbb)
-	prefix = nb_common_loops (scop->scop_info->region, previous_gbb, gbb);
-
-      previous_gbb = gbb;
-
-      static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in,
-						 prefix, 1);
-      build_pbb_scattering_polyhedrons (static_sched, pbb);
-    }
-
-  isl_aff_free (static_sched);
-}
-
 static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space);
 
 /* Extract an affine expression from the chain of recurrence E.  */
@@ -440,10 +295,7 @@ create_pw_aff_from_tree (poly_bb_p pbb, tree t)
 
   t = scalar_evolution_in_region (scop->scop_info->region, pbb_loop (pbb), t);
 
-  /* Bail out as we do not know the scev.  */
-  if (chrec_contains_undetermined (t))
-    return NULL;
-
+  gcc_assert (!chrec_contains_undetermined (t));
   gcc_assert (!automatically_generated_chrec_p (t));
 
   return extract_affine (scop, t, isl_set_get_space (pbb->domain));
@@ -453,19 +305,11 @@ create_pw_aff_from_tree (poly_bb_p pbb, tree t)
    operator.  This allows us to invert the condition or to handle
    inequalities.  */
 
-static bool
+static void
 add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
 {
   isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, gimple_cond_lhs (stmt));
-  if (!lhs)
-    return false;
-
   isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, gimple_cond_rhs (stmt));
-  if (!rhs)
-    {
-      isl_pw_aff_free (lhs);
-      return false;
-    }
 
   isl_set *cond;
   switch (code)
@@ -495,20 +339,17 @@ add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
 	break;
 
       default:
-	isl_pw_aff_free (lhs);
-	isl_pw_aff_free (rhs);
-	return true;
+	gcc_unreachable ();
     }
 
   cond = isl_set_coalesce (cond);
   cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain));
   pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond));
-  return true;
 }
 
 /* Add conditions to the domain of PBB.  */
 
-static bool
+static void
 add_conditions_to_domain (poly_bb_p pbb)
 {
   unsigned int i;
@@ -516,7 +357,7 @@ add_conditions_to_domain (poly_bb_p pbb)
   gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
 
   if (GBB_CONDITIONS (gbb).is_empty ())
-    return true;
+    return;
 
   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
     switch (gimple_code (stmt))
@@ -534,36 +375,14 @@ add_conditions_to_domain (poly_bb_p pbb)
 	    if (!GBB_CONDITION_CASES (gbb)[i])
 	      code = invert_tree_comparison (code, false);
 
-	    if (!add_condition_to_pbb (pbb, cond_stmt, code))
-	      return false;
+	    add_condition_to_pbb (pbb, cond_stmt, code);
 	    break;
 	  }
 
-      case GIMPLE_SWITCH:
-	/* Switch statements are not supported right now - fall through.  */
-
       default:
 	gcc_unreachable ();
 	break;
       }
-
-  return true;
-}
-
-/* Traverses all the GBBs of the SCOP and add their constraints to the
-   iteration domains.  */
-
-static bool
-add_conditions_to_constraints (scop_p scop)
-{
-  int i;
-  poly_bb_p pbb;
-
-  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
-    if (!add_conditions_to_domain (pbb))
-      return false;
-
-  return true;
 }
 
 /* Add constraints on the possible values of parameter P from the type
@@ -628,6 +447,29 @@ add_param_constraints (scop_p scop, graphite_dim_t p)
     }
 }
 
+/* Assign dimension for each parameter in SCOP and add constraints for the
+   parameters.  */
+
+static void
+build_scop_context (scop_p scop)
+{
+  sese_info_p region = scop->scop_info;
+  unsigned nbp = sese_nb_params (region);
+  isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0);
+
+  unsigned i;
+  tree e;
+  FOR_EACH_VEC_ELT (region->params, i, e)
+    space = isl_space_set_dim_id (space, isl_dim_param, i,
+                                  isl_id_for_ssa_name (scop, e));
+
+  scop->param_context = isl_set_universe (space);
+
+  graphite_dim_t p;
+  for (p = 0; p < nbp; p++)
+    add_param_constraints (scop, p);
+}
+
 /* Add a constrain to the ACCESSES polyhedron for the alias set of
    data reference DR.  ACCESSP_NB_DIMS is the dimension of the
    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
@@ -898,6 +740,19 @@ build_scop_drs (scop_p scop)
     build_poly_sr (pbb);
 }
 
+/* Add to the iteration DOMAIN one extra dimension for LOOP->num.  */
+
+static isl_set *
+add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop)
+{
+  int loop_index = isl_set_dim (domain, isl_dim_set);
+  domain = isl_set_add_dims (domain, isl_dim_set, 1);
+  char name[50];
+  snprintf (name, sizeof(name), "i%d", loop->num);
+  isl_id *label = isl_id_alloc (scop->isl_context, name, NULL);
+  return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label);
+}
+
 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT.  */
 
 static isl_set *
@@ -919,7 +774,7 @@ add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
   if (dump_file)
     fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the "
 	     "domain for loop_%d.\n", loop->num);
-  domain = isl_set_add_dims (domain, isl_dim_set, 1);
+  domain = add_iter_domain_dimension (domain, loop, scop);
   isl_space *space = isl_set_get_space (domain);
 
   /* 0 <= loop_i */
@@ -1014,8 +869,8 @@ add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
 /* Builds the original iteration domains for each pbb in the SCOP.  */
 
 static int
-build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index,
-			 loop_p context_loop)
+build_iteration_domains (scop_p scop, __isl_keep isl_set *context,
+			 int index, loop_p context_loop)
 {
   loop_p current = pbb_loop (scop->pbbs[index]);
   isl_set *domain = isl_set_copy (context);
@@ -1029,9 +884,12 @@ build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index,
       loop_p loop = pbb_loop (pbb);
       if (current == loop)
 	{
+	  pbb->iterators = isl_set_copy (domain);
 	  pbb->domain = isl_set_copy (domain);
 	  pbb->domain = isl_set_set_tuple_id (pbb->domain,
 					      isl_id_for_pbb (scop, pbb));
+	  add_conditions_to_domain (pbb);
+
 	  if (dump_file)
 	    {
 	      fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ",
@@ -1061,28 +919,283 @@ build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index,
   return i;
 }
 
+/* Return true when loop A is nested in loop B.  */
 
-/* Assign dimension for each parameter in SCOP and add constraints for the
-   parameters.  */
+static bool
+nested_in (loop_p a, loop_p b)
+{
+  return b == find_common_loop (a, b);
+}
 
-static void
-build_scop_context (scop_p scop)
+/* Return the loop at a specific SCOP->pbbs[*INDEX].  */
+static loop_p
+loop_at (scop_p scop, int *index)
 {
-  sese_info_p region = scop->scop_info;
-  unsigned nbp = sese_nb_params (region);
-  isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0);
+  return pbb_loop (scop->pbbs[*index]);
+}
 
-  unsigned i;
-  tree e;
-  FOR_EACH_VEC_ELT (region->params, i, e)
-    space = isl_space_set_dim_id (space, isl_dim_param, i,
-                                  isl_id_for_ssa_name (scop, e));
+/* Return the index of any pbb belonging to loop or a subloop of A.  */
 
-  scop->param_context = isl_set_universe (space);
+static int
+index_outermost_in_loop (loop_p a, scop_p scop)
+{
+  int i, outermost = -1;
+  int last_depth = -1;
+  poly_bb_p pbb;
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
+    if (nested_in (pbb_loop (pbb), a)
+	&& (last_depth == -1
+	    || last_depth > (int) loop_depth (pbb_loop (pbb))))
+      {
+	outermost = i;
+	last_depth = loop_depth (pbb_loop (pbb));
+      }
+  return outermost;
+}
 
-  graphite_dim_t p;
-  for (p = 0; p < nbp; p++)
-    add_param_constraints (scop, p);
+/* Return the index of any pbb belonging to loop or a subloop of A.  */
+
+static int
+index_pbb_in_loop (loop_p a, scop_p scop)
+{
+  int i;
+  poly_bb_p pbb;
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
+    if (pbb_loop (pbb) == a)
+      return i;
+  return -1;
+}
+
+static poly_bb_p
+outermost_pbb_in (loop_p loop, scop_p scop)
+{
+  int x = index_pbb_in_loop (loop, scop);
+  if (x == -1)
+    x = index_outermost_in_loop (loop, scop);
+  return scop->pbbs[x];
+}
+
+static isl_schedule *
+add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b)
+{
+  gcc_assert (a || b);
+
+  if (!a)
+    return b;
+
+  if (!b)
+    return a;
+
+  return isl_schedule_sequence (a, b);
+}
+
+struct map_to_dimension_data {
+  int n;
+  isl_union_pw_multi_aff *res;
+};
+
+/* Create a function that maps the elements of SET to its N-th dimension and add
+   it to USER->res.  */
+
+static isl_stat
+add_outer_projection (__isl_take isl_set *set, void *user)
+{
+  struct map_to_dimension_data *data = (struct map_to_dimension_data *) user;
+  int dim = isl_set_dim (set, isl_dim_set);
+  isl_space *space = isl_set_get_space (set);
+
+  gcc_assert (dim >= data->n);
+  isl_pw_multi_aff *pma
+    = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n,
+					dim - data->n);
+  data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma);
+
+  isl_set_free (set);
+  return isl_stat_ok;
+}
+
+/* Return SET in which all inner dimensions above N are removed.  */
+
+static isl_multi_union_pw_aff *
+outer_projection_mupa (__isl_take isl_union_set *set, int n)
+{
+  gcc_assert (n >= 0);
+  gcc_assert (set);
+  gcc_assert (!isl_union_set_is_empty (set));
+
+  isl_space *space = isl_union_set_get_space (set);
+  isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space);
+
+  struct map_to_dimension_data data = {n, pwaff};
+
+  if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0)
+    data.res = isl_union_pw_multi_aff_free (data.res);
+
+  isl_union_set_free (set);
+  return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res);
+}
+
+/* Embed SCHEDULE in the constraints of the LOOP domain.  */
+
+static isl_schedule *
+add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop,
+		   scop_p scop)
+{
+  poly_bb_p pbb = outermost_pbb_in (loop, scop);
+  isl_set *iterators = pbb->iterators;
+
+  int empty = isl_set_is_empty (iterators);
+  if (empty < 0 || empty)
+    return empty < 0 ? isl_schedule_free (schedule) : schedule;
+
+  isl_space *space = isl_set_get_space (iterators);
+  int loop_index = isl_space_dim (space, isl_dim_set) - 1;
+
+  loop_p ploop = pbb_loop (pbb);
+  while (loop != ploop)
+    {
+      --loop_index;
+      ploop = loop_outer (ploop);
+    }
+
+  isl_local_space *ls = isl_local_space_from_space (space);
+  isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index);
+  isl_multi_aff *prefix = isl_multi_aff_from_aff (aff);
+  char name[50];
+  snprintf (name, sizeof(name), "L_%d", loop->num);
+  isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule),
+				name, NULL);
+  prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label);
+
+  int n = isl_multi_aff_dim (prefix, isl_dim_in);
+  isl_union_set *domain = isl_schedule_get_domain (schedule);
+  isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n);
+  mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix);
+  return isl_schedule_insert_partial_schedule (schedule, mupa);
+}
+
+/* Build schedule for the pbb at INDEX.  */
+
+static isl_schedule *
+build_schedule_pbb (scop_p scop, int *index)
+{
+  poly_bb_p pbb = scop->pbbs[*index];
+  ++*index;
+  isl_set *domain = isl_set_copy (pbb->domain);
+  isl_union_set *ud = isl_union_set_from_set (domain);
+  return isl_schedule_from_domain (ud);
+}
+
+static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p);
+
+/* Build the schedule of the loop containing the SCOP pbb at INDEX.  */
+
+static isl_schedule *
+build_schedule_loop (scop_p scop, int *index)
+{
+  int max = scop->pbbs.length ();
+  gcc_assert (*index < max);
+  loop_p loop = loop_at (scop, index);
+
+  isl_schedule *s = NULL;
+  while (nested_in (loop_at (scop, index), loop))
+    {
+      if (loop == loop_at (scop, index))
+	s = add_in_sequence (s, build_schedule_pbb (scop, index));
+      else
+	s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop));
+
+      if (*index == max)
+	break;
+    }
+
+  return add_loop_schedule (s, loop, scop);
+}
+
+/* S is the schedule of the loop LOOP.  Embed the schedule S in all outer loops.
+   When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
+   SCOP surrounding LOOP.  When CONTEXT_LOOP is non null, only embed S in the
+   maximal loop nest contained within CONTEXT_LOOP.  */
+
+static isl_schedule *
+embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop,
+			    loop_p loop, int *index, loop_p context_loop)
+{
+  loop_p outer = loop_outer (loop);
+  sese_l region = scop->scop_info->region;
+  if (context_loop == outer
+      || !loop_in_sese_p (outer, region))
+    return s;
+
+  int max = scop->pbbs.length ();
+  if (*index == max
+      || (context_loop && !nested_in (loop_at (scop, index), context_loop))
+      || (!context_loop
+	  && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)),
+			      region)))
+    return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop),
+				       scop, outer, index, context_loop);
+
+  bool a_pbb;
+  while ((a_pbb = (outer == loop_at (scop, index)))
+	 || nested_in (loop_at (scop, index), outer))
+    {
+      if (a_pbb)
+	s = add_in_sequence (s, build_schedule_pbb (scop, index));
+      else
+	s = add_in_sequence (s, build_schedule_loop (scop, index));
+
+      if (*index == max)
+	break;
+    }
+
+  /* We reached the end of the OUTER loop: embed S in OUTER.  */
+  return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop,
+				     outer, index, context_loop);
+}
+
+/* Build schedule for the full loop nest containing the pbb at INDEX.  When
+   CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
+   surrounding the pbb.  When CONTEXT_LOOP is non null, only build the maximal loop
+   nest contained within CONTEXT_LOOP.  */
+
+static isl_schedule *
+build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop)
+{
+  gcc_assert (*index != (int) scop->pbbs.length ());
+
+  loop_p loop = loop_at (scop, index);
+  isl_schedule *s = build_schedule_loop (scop, index);
+  return embed_in_surrounding_loops (s, scop, loop, index, context_loop);
+}
+
+/* Build the schedule of the SCOP.  */
+
+static bool
+build_original_schedule (scop_p scop)
+{
+  int i = 0;
+  int n = scop->pbbs.length ();
+  while (i < n)
+    {
+      poly_bb_p pbb = scop->pbbs[i];
+      isl_schedule *s = NULL;
+      if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region))
+	s = build_schedule_pbb (scop, &i);
+      else
+	s = build_schedule_loop_nest (scop, &i, NULL);
+
+      scop->original_schedule = add_in_sequence (scop->original_schedule, s);
+    }
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "[sese-to-poly] original schedule:\n");
+      print_isl_schedule (dump_file, scop->original_schedule);
+    }
+  if (!scop->original_schedule)
+    return false;
+  return true;
 }
 
 /* Builds the polyhedral representation for a SESE region.  */
@@ -1097,11 +1210,7 @@ build_poly_scop (scop_p scop)
   while (i < n)
     i = build_iteration_domains (scop, scop->param_context, i, NULL);
 
-  if (!add_conditions_to_constraints (scop))
-    return false;
-
   build_scop_drs (scop);
-  build_scop_scattering (scop);
-  return true;
+  return build_original_schedule (scop);
 }
 #endif  /* HAVE_isl */
diff --git a/gcc/graphite.h b/gcc/graphite.h
index 7f8a273..7bafd09 100644
--- a/gcc/graphite.h
+++ b/gcc/graphite.h
@@ -200,7 +200,6 @@ struct poly_dr
 
 void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
 		  isl_map *, isl_set *);
-void free_poly_dr (poly_dr_p);
 void debug_pdr (poly_dr_p);
 void print_pdr (FILE *, poly_dr_p);
 
@@ -259,19 +258,11 @@ struct poly_bb
      The number of variables in the DOMAIN may change and is not
      related to the number of loops in the original code.  */
   isl_set *domain;
+  isl_set *iterators;
 
   /* The data references we access.  */
   vec<poly_dr_p> drs;
 
-  /* The original scattering.  */
-  isl_map *schedule;
-
-  /* The transformed scattering.  */
-  isl_map *transformed;
-
-  /* A copy of the transformed scattering.  */
-  isl_map *saved;
-
   /* The last basic block generated for this pbb.  */
   basic_block new_bb;
 };
@@ -281,8 +272,6 @@ struct poly_bb
 #define PBB_DRS(PBB) (PBB->drs)
 
 extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p);
-extern void free_poly_bb (poly_bb_p);
-extern void debug_loop_vec (poly_bb_p);
 extern void print_pbb_domain (FILE *, poly_bb_p);
 extern void print_pbb (FILE *, poly_bb_p);
 extern void print_scop_context (FILE *, scop_p);
@@ -306,18 +295,17 @@ extern void print_isl_aff (FILE *, isl_aff *);
 extern void print_isl_constraint (FILE *, isl_constraint *);
 extern void print_isl_schedule (FILE *, isl_schedule *);
 extern void debug_isl_schedule (isl_schedule *);
+extern void print_isl_ast (FILE *, isl_ast_node *);
+extern void debug_isl_ast (isl_ast_node *);
 extern void debug_isl_set (isl_set *);
 extern void debug_isl_map (isl_map *);
 extern void debug_isl_union_map (isl_union_map *);
 extern void debug_isl_aff (isl_aff *);
 extern void debug_isl_constraint (isl_constraint *);
-extern int scop_do_interchange (scop_p);
-extern int scop_do_strip_mine (scop_p, int);
-extern bool scop_do_block (scop_p);
-extern bool flatten_all_loops (scop_p);
-extern bool optimize_isl (scop_p);
-extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
 extern void debug_gmp_value (mpz_t);
+extern void debug_scop_pbb (scop_p scop, int i);
+extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p);
+extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p);
 
 /* The basic block of the PBB.  */
 
@@ -417,8 +405,11 @@ struct scop
   /* The context used internally by isl.  */
   isl_ctx *isl_context;
 
-  /* SCoP final schedule.  */
-  isl_schedule *schedule;
+  /* SCoP original schedule.  */
+  isl_schedule *original_schedule;
+
+  /* SCoP transformed schedule.  */
+  isl_schedule *transformed_schedule;
 
   /* The data dependence relation among the data references in this scop.  */
   isl_union_map *dependence;
@@ -428,10 +419,6 @@ extern scop_p new_scop (edge, edge);
 extern void free_scop (scop_p);
 extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
 					    vec<scalar_use>, vec<tree>);
-extern void free_gimple_poly_bb (gimple_poly_bb_p);
-extern void print_generated_program (FILE *, scop_p);
-extern void debug_generated_program (scop_p);
-extern int unify_scattering_dimensions (scop_p);
 extern bool apply_poly_transforms (scop_p);
 
 /* Set the region of SCOP to REGION.  */
@@ -458,9 +445,6 @@ scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
   scop->nb_params = nb_params;
 }
 
-isl_union_map *
-scop_get_dependences (scop_p scop);
-
 bool
 carries_deps (__isl_keep isl_union_map *schedule,
 	      __isl_keep isl_union_map *deps,
@@ -468,9 +452,10 @@ carries_deps (__isl_keep isl_union_map *schedule,
 
 extern bool build_poly_scop (scop_p);
 extern bool graphite_regenerate_ast_isl (scop_p);
-
+extern void scop_get_dependences (scop_p scop);
 extern void build_scops (vec<scop_p> *);
 extern void dot_all_sese (FILE *, vec<sese_l> &);
 extern void dot_sese (sese_l &);
 extern void dot_cfg ();
+
 #endif
diff --git a/gcc/sese.c b/gcc/sese.c
index 2ecff7d..9ea46c7f 100644
--- a/gcc/sese.c
+++ b/gcc/sese.c
@@ -581,3 +581,37 @@ scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
 
   return instantiate_scev (before, loop, t);
 }
+
+/* Pretty print edge E to FILE.  */
+
+void
+print_edge (FILE *file, const_edge e)
+{
+  fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
+}
+
+/* Pretty print sese S to FILE.  */
+
+void
+print_sese (FILE *file, const sese_l &s)
+{
+  fprintf (file, "(entry_"); print_edge (file, s.entry);
+  fprintf (file, ", exit_"); print_edge (file, s.exit);
+  fprintf (file, ")\n");
+}
+
+/* Pretty print edge E to STDERR.  */
+
+DEBUG_FUNCTION void
+debug_edge (const_edge e)
+{
+  print_edge (stderr, e);
+}
+
+/* Pretty print sese S to STDERR.  */
+
+DEBUG_FUNCTION void
+debug_sese (const sese_l &s)
+{
+  print_sese (stderr, s);
+}
diff --git a/gcc/sese.h b/gcc/sese.h
index f481524..e70ebd1 100644
--- a/gcc/sese.h
+++ b/gcc/sese.h
@@ -42,6 +42,11 @@ struct sese_l
   edge exit;
 };
 
+void print_edge (FILE *file, const_edge e);
+void print_sese (FILE *file, const sese_l &s);
+void dump_edge (const_edge e);
+void dump_sese (const sese_l &);
+
 /* Get the entry of an sese S.  */
 
 static inline basic_block
@@ -203,7 +208,7 @@ loop_in_sese_p (struct loop *loop, const sese_l &region)
     loop_2 is completely contained -> depth 1  */
 
 static inline unsigned int
-sese_loop_depth (sese_l &region, loop_p loop)
+sese_loop_depth (const sese_l &region, loop_p loop)
 {
   unsigned int depth = 0;
 
diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c
index 0a278f8..4baf79c 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-0.c
@@ -42,4 +42,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-1.c b/gcc/testsuite/gcc.dg/graphite/block-1.c
index 2758404..03a5f83 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-1.c
@@ -45,4 +45,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-5.c b/gcc/testsuite/gcc.dg/graphite/block-5.c
index 28a0192..95f08c7 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-5.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-5.c
@@ -54,4 +54,5 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-6.c b/gcc/testsuite/gcc.dg/graphite/block-6.c
index 8902a17..0418a34 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-6.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-6.c
@@ -49,4 +49,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c
index 2027a3f..c4ffca3 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c
@@ -21,4 +21,4 @@ main ()
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-0.c b/gcc/testsuite/gcc.dg/graphite/interchange-0.c
index f655e84..3f398ca 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-0.c
@@ -46,4 +46,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-10.c b/gcc/testsuite/gcc.dg/graphite/interchange-10.c
index 825aafd..4f6be65 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-10.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-10.c
@@ -46,4 +46,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-12.c b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
index 7cdbabe..0012d56 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-12.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
@@ -53,4 +53,5 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
index 617659c..917e679 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-14.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
@@ -54,4 +54,5 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-15.c b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
index 3696f41..8e147ad 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-15.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
@@ -48,4 +48,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-5.c b/gcc/testsuite/gcc.dg/graphite/interchange-5.c
index 4410a17..e578e17 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-5.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-5.c
@@ -46,4 +46,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-6.c b/gcc/testsuite/gcc.dg/graphite/interchange-6.c
index c4500cb..9760ed3 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-6.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-6.c
@@ -47,4 +47,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-8.c b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
index 9df7258..c623a32 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
@@ -82,4 +82,5 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "codegen error: reverting back to the original code" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
index b43131c..ec6a983 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
@@ -58,4 +58,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c
index 89e6994..1c13a69 100644
--- a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c
@@ -34,4 +34,5 @@ if (n >= k + 1 && k >= 0) {
 
 */
 
-/* { dg-final { scan-tree-dump-times "if \\\(P_9 >= P_10 \\\+ 1 && P_10 >= 0\\\) \\\{" 1 "graphite" } } */
+/* { dg-final { scan-tree-dump-times "if \\\(P_9 >= P_10 \\\+ 1 && P_10 >= 0\\\) \\\{" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/scop-10.c b/gcc/testsuite/gcc.dg/graphite/scop-10.c
index 39ed5d7..ac2c7f9 100644
--- a/gcc/testsuite/gcc.dg/graphite/scop-10.c
+++ b/gcc/testsuite/gcc.dg/graphite/scop-10.c
@@ -17,7 +17,7 @@ int toto()
 	    b[i+j] = b[i+j-1] + 2;
 	  a[i][i] = 2;
 	}
-
+      
       for (k = 1; k < 100; k++)
         b[i+k] = b[i+k-5] + 2;
     }
diff --git a/gcc/testsuite/gcc.dg/graphite/uns-block-1.c b/gcc/testsuite/gcc.dg/graphite/uns-block-1.c
index 5b61eea..19f358d 100644
--- a/gcc/testsuite/gcc.dg/graphite/uns-block-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/uns-block-1.c
@@ -45,4 +45,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c
index a53c98e..2b957f5 100644
--- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c
+++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c
@@ -54,4 +54,5 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c
index 1e180c6..960e7ae 100644
--- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c
+++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c
@@ -55,4 +55,5 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c
index adac7d4..5c5597f 100644
--- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c
+++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c
@@ -49,4 +49,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c
index 04f5b7d..153fc8e 100644
--- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c
+++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c
@@ -59,4 +59,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */
+/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */
diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 b/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90
index a66ddfd..192c5b2 100644
--- a/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90
+++ b/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90
@@ -24,4 +24,4 @@ Program FOO
 
 end Program FOO
 
-! { dg-final { scan-tree-dump-times "unsuccessful, reverting back to the original code." "1" "graphite" } }
+! { dg-final { scan-tree-dump-times "codegen error: reverting back to the original code" "1" "graphite" } }
diff --git a/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 b/gcc/testsuite/gfortran.dg/graphite/pr14741.f90
index 50c2e79..057e57e 100644
--- a/gcc/testsuite/gfortran.dg/graphite/pr14741.f90
+++ b/gcc/testsuite/gfortran.dg/graphite/pr14741.f90
@@ -24,4 +24,4 @@ SUBROUTINE mult(A,B,C,N)
   ENDDO
 END SUBROUTINE mult
 
-! { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } }
+! { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } }
-- 
2.5.0