[PATCH 1/4] [graphite] add more coalescing to simplify constraints

[Sebastian Pop <s dot pop at samsung dot com>]

---
 gcc/graphite-dependences.c       | 63 ++++++++++++++++++----------------------
 gcc/graphite-isl-ast-to-gimple.c |  2 ++
 gcc/graphite-optimize-isl.c      | 12 ++++----
 gcc/graphite-sese-to-poly.c      | 28 ++++++++++++------
 4 files changed, 56 insertions(+), 49 deletions(-)

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 46869d7..ae08059 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -49,7 +49,7 @@ constrain_domain (isl_map *map, isl_set *s)
 
   s = isl_set_set_tuple_id (s, id);
   isl_space_free (d);
-  return isl_map_intersect_domain (map, s);
+  return isl_map_coalesce (isl_map_intersect_domain (map, s));
 }
 
 /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain.  */
@@ -59,8 +59,8 @@ add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
 {
   isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
 					isl_set_copy (pdr->subscript_sizes));
-  x = constrain_domain (x, isl_set_copy (pbb->domain));
-  return x;
+  x = isl_map_coalesce (x);
+  return constrain_domain (x, isl_set_copy (pbb->domain));
 }
 
 /* Returns all the memory reads in SCOP.  */
@@ -93,7 +93,7 @@ scop_get_reads (scop_p scop, vec<poly_bb_p> pbbs)
 	  }
     }
 
-  return res;
+  return isl_union_map_coalesce (res);
 }
 
 /* Returns all the memory must writes in SCOP.  */
@@ -126,7 +126,7 @@ scop_get_must_writes (scop_p scop, vec<poly_bb_p> pbbs)
 	  }
     }
 
-  return res;
+  return isl_union_map_coalesce (res);
 }
 
 /* Returns all the memory may writes in SCOP.  */
@@ -159,7 +159,7 @@ scop_get_may_writes (scop_p scop, vec<poly_bb_p> pbbs)
 	  }
     }
 
-  return res;
+  return isl_union_map_coalesce (res);
 }
 
 /* Returns all the original schedules in SCOP.  */
@@ -179,7 +179,7 @@ scop_get_original_schedule (scop_p scop, vec<poly_bb_p> pbbs)
 				isl_set_copy (pbb->domain)));
     }
 
-  return res;
+  return isl_union_map_coalesce (res);
 }
 
 /* Helper function used on each MAP of a isl_union_map.  Computes the
@@ -242,7 +242,7 @@ extend_schedule (__isl_take isl_union_map *x)
   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
   isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
   isl_union_map_free (x);
-  return str.umap;
+  return isl_union_map_coalesce (str.umap);
 }
 
 /* Applies SCHEDULE to the in and out dimensions of the dependences
@@ -252,22 +252,17 @@ static isl_map *
 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
 			__isl_keep isl_union_map *deps)
 {
-  isl_map *x;
-  isl_union_map *ux, *trans;
-
-  trans = isl_union_map_copy (schedule);
-  trans = extend_schedule (trans);
-  ux = isl_union_map_copy (deps);
+  isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
+  isl_union_map *ux = isl_union_map_copy (deps);
   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
   ux = isl_union_map_apply_range (ux, trans);
-  if (isl_union_map_is_empty (ux))
-    {
-      isl_union_map_free (ux);
-      return NULL;
-    }
-  x = isl_map_from_union_map (ux);
+  ux = isl_union_map_coalesce (ux);
+
+  if (!isl_union_map_is_empty (ux))
+    return isl_map_from_union_map (ux);
 
-  return x;
+  isl_union_map_free (ux);
+  return NULL;
 }
 
 /* Return true when DEPS is non empty and the intersection of LEX with
@@ -280,25 +275,19 @@ carries_deps (__isl_keep isl_union_map *schedule,
 	      __isl_keep isl_union_map *deps,
 	      int depth)
 {
-  bool res;
-  int i;
-  isl_space *space;
-  isl_map *lex, *x;
-  isl_constraint *ineq;
-
   if (isl_union_map_is_empty (deps))
     return false;
 
-  x = apply_schedule_on_deps (schedule, deps);
+  isl_map *x = apply_schedule_on_deps (schedule, deps);
   if (x == NULL)
     return false;
-  space = isl_map_get_space (x);
-  space = isl_space_range (space);
-  lex = isl_map_lex_le (space);
-  space = isl_map_get_space (x);
-  ineq = isl_inequality_alloc (isl_local_space_from_space (space));
 
-  for (i = 0; i < depth - 1; i++)
+  isl_space *space = isl_map_get_space (x);
+  isl_map *lex = isl_map_lex_le (isl_space_range (space));
+  isl_constraint *ineq = isl_inequality_alloc
+    (isl_local_space_from_space (isl_map_get_space (x)));
+
+  for (int i = 0; i < depth - 1; i++)
     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
 
   /* in + 1 <= out  */
@@ -306,8 +295,9 @@ carries_deps (__isl_keep isl_union_map *schedule,
   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
   ineq = isl_constraint_set_constant_si (ineq, -1);
   lex = isl_map_add_constraint (lex, ineq);
+  lex = isl_map_coalesce (lex);
   x = isl_map_intersect (x, lex);
-  res = !isl_map_is_empty (x);
+  bool res = !isl_map_is_empty (x);
 
   isl_map_free (x);
   return res;
@@ -336,6 +326,8 @@ compute_deps (scop_p scop, vec<poly_bb_p> 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);
+
   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);
@@ -416,6 +408,7 @@ scop_get_dependences (scop_p scop)
   dependences = isl_union_map_union (dependences, may_raw);
   dependences = isl_union_map_union (dependences, may_war);
   dependences = isl_union_map_union (dependences, may_waw);
+  dependences = isl_union_map_coalesce (dependences);
 
   if (dump_file)
     {
diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c
index 795232a..aaca9e9 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -3160,9 +3160,11 @@ translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop)
       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;
 }
diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c
index 9626e96..15dd5b0 100644
--- a/gcc/graphite-optimize-isl.c
+++ b/gcc/graphite-optimize-isl.c
@@ -241,6 +241,7 @@ get_schedule_for_band (isl_band *band, int *dimensions)
 			   PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
   tile_umap = isl_union_map_from_map (isl_map_from_basic_map (tile_map));
   tile_umap = isl_union_map_align_params (tile_umap, space);
+  tile_umap = isl_union_map_coalesce (tile_umap);
   *dimensions = 2 * *dimensions;
 
   return isl_union_map_apply_range (partial_schedule, tile_umap);
@@ -292,14 +293,14 @@ get_schedule_for_band_list (isl_band_list *band_list)
       isl_space_free (space);
     }
 
-  return schedule;
+  return isl_union_map_coalesce (schedule);
 }
 
 static isl_union_map *
 get_schedule_map (isl_schedule *schedule)
 {
-  isl_band_list *bandList = isl_schedule_get_band_forest (schedule);
-  isl_union_map *schedule_map = get_schedule_for_band_list (bandList);
+  isl_band_list *band_list = isl_schedule_get_band_forest (schedule);
+  isl_union_map *schedule_map = get_schedule_for_band_list (band_list);
   isl_band_list_free (bandList);
   return schedule_map;
 }
@@ -327,15 +328,16 @@ apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
       isl_union_map *stmt_band
 	= isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
 					  isl_union_set_from_set (domain));
+      stmt_band = isl_union_map_coalesce (stmt_band);
       isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
       isl_map_free (pbb->transformed);
-      pbb->transformed = stmt_schedule;
+      pbb->transformed = isl_map_coalesce (stmt_schedule);
       isl_union_map_free (stmt_band);
     }
 }
 
 static isl_union_set *
-scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
+scop_get_domains (scop_p scop)
 {
   int i;
   poly_bb_p pbb;
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 7992c28..6421e4e 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -143,6 +143,10 @@ build_pbb_scattering_polyhedrons (isl_aff *static_sched,
 	}
     }
 
+  /* 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);
 }
 
@@ -482,7 +486,7 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
   isl_constraint *c = isl_inequality_alloc
       (isl_local_space_from_space (isl_space_copy (space)));
   c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, 1);
-  inner = isl_set_add_constraint (inner, c);
+  inner = isl_set_coalesce (isl_set_add_constraint (inner, c));
 
   /* loop_i <= cst_nb_iters */
   if (TREE_CODE (nb_iters) == INTEGER_CST)
@@ -513,7 +517,8 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
 				   isl_set_dim (valid, isl_dim_set));
 
       if (valid)
-	scop->param_context = isl_set_intersect (scop->param_context, valid);
+	scop->param_context = isl_set_coalesce
+	  (isl_set_intersect (scop->param_context, valid));
 
       isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
       isl_aff *al = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls),
@@ -541,7 +546,8 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
 	  isl_set *x = isl_pw_aff_ge_set (approx, aff);
 	  x = isl_set_project_out (x, isl_dim_set, 0,
 				   isl_set_dim (x, isl_dim_set));
-	  scop->param_context = isl_set_intersect (scop->param_context, x);
+	  scop->param_context = isl_set_coalesce
+	    (isl_set_intersect (scop->param_context, x));
 
 	  isl_constraint *c = isl_inequality_alloc
 	      (isl_local_space_from_space (isl_space_copy (space)));
@@ -557,6 +563,7 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
   else
     gcc_unreachable ();
 
+  inner = isl_set_coalesce (inner);
   if (loop->inner
       && !build_loop_iteration_domains (scop, loop->inner, nb + 1,
 					isl_set_copy (inner), doms))
@@ -648,7 +655,7 @@ add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
 
   cond = isl_set_coalesce (cond);
   cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain));
-  pbb->domain = isl_set_intersect (pbb->domain, cond);
+  pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond));
   return true;
 }
 
@@ -749,7 +756,8 @@ add_param_constraints (scop_p scop, graphite_dim_t p)
       c = isl_constraint_set_constant_val (c, v);
       c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1);
 
-      scop->param_context = isl_set_add_constraint (scop->param_context, c);
+      scop->param_context = isl_set_coalesce
+	(isl_set_add_constraint (scop->param_context, c));
     }
 
   if (ub)
@@ -768,7 +776,8 @@ add_param_constraints (scop_p scop, graphite_dim_t p)
       c = isl_constraint_set_constant_val (c, v);
       c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1);
 
-      scop->param_context = isl_set_add_constraint (scop->param_context, c);
+      scop->param_context = isl_set_coalesce
+	(isl_set_add_constraint (scop->param_context, c));
     }
 }
 
@@ -911,7 +920,7 @@ pdr_add_memory_accesses (isl_map *acc, dr_info &dri)
       acc = set_index (acc, i + 1, aff);
     }
 
-  return acc;
+  return isl_map_coalesce (acc);
 }
 
 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
@@ -972,7 +981,8 @@ pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
       isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
       valid = isl_set_project_out (valid, isl_dim_set, 0,
 				   isl_set_dim (valid, isl_dim_set));
-      scop->param_context = isl_set_intersect (scop->param_context, valid);
+      scop->param_context = isl_set_coalesce
+	(isl_set_intersect (scop->param_context, valid));
 
       isl_aff *aff
 	= isl_aff_zero_on_domain (isl_local_space_from_space (space));
@@ -992,7 +1002,7 @@ pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
       subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
     }
 
-  return subscript_sizes;
+  return isl_set_coalesce (subscript_sizes);
 }
 
 /* Build data accesses for DRI.  */
-- 
1.9.1