isl_map_transitive_closure, omega-like: only use ?-closure if result is exact

1 files changed, 40 insertions, 33 deletions

diff --git a/isl_transitive_closure.c b/isl_transitive_closure.c
index 78cb1937..fa12dbf5 100644
--- a/isl_transitive_closure.c
+++ b/isl_transitive_closure.c
@@ -2278,6 +2278,19 @@ error:
 	return -1;
 }
 
+static __isl_give isl_map *box_closure_with_check(__isl_take isl_map *map,
+	int *exact)
+{
+	isl_map *app;
+
+	app = box_closure(isl_map_copy(map));
+	if (exact)
+		*exact = check_exactness_omega(map, app);
+
+	isl_map_free(map);
+	return app;
+}
+
 /* Compute an overapproximation of the transitive closure of "map"
  * using a variation of the algorithm from
  * "Transitive Closure of Infinite Graphs and its Applications"
@@ -2296,18 +2309,17 @@ error:
  *
  * If not, we simply call box_closure on the whole map.
  */
-static __isl_give isl_map *compute_closure_omega(__isl_take isl_map *map)
+static __isl_give isl_map *transitive_closure_omega(__isl_take isl_map *map,
+	int *exact)
 {
 	int i, j;
+	int exact_i;
+	isl_map *app;
 
 	if (!map)
 		return NULL;
 	if (map->n == 1)
-		return box_closure(map);
-
-	map = isl_map_cow(map);
-	if (!map)
-		goto error;
+		return box_closure_with_check(map, exact);
 
 	for (i = 0; i < map->n; ++i) {
 		int ok;
@@ -2318,42 +2330,37 @@ static __isl_give isl_map *compute_closure_omega(__isl_take isl_map *map)
 		if (!ok)
 			continue;
 
-		isl_basic_map_free(map->p[i]);
-		if (i != map->n - 1)
-			map->p[i] = map->p[map->n - 1];
-		map->n--;
+		app = isl_map_alloc_dim(isl_map_get_dim(map), map->n - 1, 0);
+
+		for (j = 0; j < map->n; ++j) {
+			if (j == i)
+				continue;
+			app = isl_map_add_basic_map(app,
+						isl_basic_map_copy(map->p[j]));
+		}
 
-		map = isl_map_apply_range(isl_map_copy(qc), map);
-		map = isl_map_apply_range(map, qc);
+		app = isl_map_apply_range(isl_map_copy(qc), app);
+		app = isl_map_apply_range(app, qc);
 
-		return isl_map_union(tc, compute_closure_omega(map));
+		app = isl_map_union(tc, transitive_closure_omega(app, NULL));
+		exact_i = check_exactness_omega(map, app);
+		if (exact_i == 1) {
+			if (exact)
+				*exact = exact_i;
+			isl_map_free(map);
+			return app;
+		}
+		isl_map_free(app);
+		if (exact_i < 0)
+			goto error;
 	}
 
-	return box_closure(map);
+	return box_closure_with_check(map, exact);
 error:
 	isl_map_free(map);
 	return NULL;
 }
 
-/* Compute an overapproximation of the transitive closure of "map"
- * using a variation of the algorithm from
- * "Transitive Closure of Infinite Graphs and its Applications"
- * by Kelly et al. and check whether the result is definitely exact.
- */
-static __isl_give isl_map *transitive_closure_omega(__isl_take isl_map *map,
-	int *exact)
-{
-	isl_map *app;
-
-	app = compute_closure_omega(isl_map_copy(map));
-
-	if (exact)
-		*exact = check_exactness_omega(map, app);
-
-	isl_map_free(map);
-	return app;
-}
-
 /* Compute the transitive closure  of "map", or an overapproximation.
  * If the result is exact, then *exact is set to 1.
  * Simply use map_power to compute the powers of map, but tell