isl_map_coalesce: avoid dropping constraints redundant wrt implicit equalities

isl_map_coalesce first detects implicit equalities in the basic maps.
If two basic maps can indeed be coalesced, then fuse() would
only add this constraint to the fused basic map as an inequality.
Other constraints that imply that this constraint is actually an equality
are redundant with respect to the equality and would not get copied
inside fuse() either.  The end result is that we would lose information.

In principle, we could just modify fuse() to add the implicit equalities
to the fused basic map as equalities, but it seems more prudent to
turn them into explicit equalities from the start.

Reported-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

1 files changed, 15 insertions, 0 deletions

diff --git a/isl_coalesce.c b/isl_coalesce.c
index c68ce20c..c2c3bb44 100644
--- a/isl_coalesce.c
+++ b/isl_coalesce.c
@@ -1533,6 +1533,16 @@ error:
 /* For each pair of basic maps in the map, check if the union of the two
  * can be represented by a single basic map.
  * If so, replace the pair by the single basic map and start over.
+ *
+ * Since we are constructing the tableaus of the basic maps anyway,
+ * we exploit them to detect implicit equalities and redundant constraints.
+ * This also helps the coalescing as it can ignore the redundant constraints.
+ * In order to avoid confusion, we make all implicit equalities explicit
+ * in the basic maps.  We don't call isl_basic_map_gauss, though,
+ * as that may affect the number of constraints.
+ * This means that we have to call isl_basic_map_gauss at the end
+ * of the computation to ensure that the basic maps are not left
+ * in an unexpected state.
  */
 struct isl_map *isl_map_coalesce(struct isl_map *map)
 {
@@ -1562,6 +1572,10 @@ struct isl_map *isl_map_coalesce(struct isl_map *map)
 		if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT))
 			if (isl_tab_detect_implicit_equalities(tabs[i]) < 0)
 				goto error;
+		map->p[i] = isl_tab_make_equalities_explicit(tabs[i],
+								map->p[i]);
+		if (!map->p[i])
+			goto error;
 		if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT))
 			if (isl_tab_detect_redundant(tabs[i]) < 0)
 				goto error;
@@ -1576,6 +1590,7 @@ struct isl_map *isl_map_coalesce(struct isl_map *map)
 		for (i = 0; i < map->n; ++i) {
 			map->p[i] = isl_basic_map_update_from_tab(map->p[i],
 								    tabs[i]);
+			map->p[i] = isl_basic_map_gauss(map->p[i], NULL);
 			map->p[i] = isl_basic_map_finalize(map->p[i]);
 			if (!map->p[i])
 				goto error;