/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
*
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, K.U.Leuven, Departement
* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
return NULL;
}
+/* Drop all constraints in bmap that involve any of the dimensions
+ * first to first+n-1.
+ */
+static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
+ __isl_take isl_basic_map *bmap, unsigned first, unsigned n)
+{
+ int i;
+
+ if (n == 0)
+ return bmap;
+
+ bmap = isl_basic_map_cow(bmap);
+
+ if (!bmap)
+ return NULL;
+
+ for (i = bmap->n_eq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
+ continue;
+ isl_basic_map_drop_equality(bmap, i);
+ }
+
+ for (i = bmap->n_ineq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
+ continue;
+ isl_basic_map_drop_inequality(bmap, i);
+ }
+
+ return bmap;
+}
+
/* Drop all constraints in bset that involve any of the dimensions
* first to first+n-1.
*/
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
__isl_take isl_basic_set *bset, unsigned first, unsigned n)
{
+ return isl_basic_map_drop_constraints_involving(bset, first, n);
+}
+
+/* Drop all constraints in bmap that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
int i;
+ unsigned dim;
if (n == 0)
- return bset;
+ return isl_basic_map_set_to_empty(bmap);
+ bmap = isl_basic_map_cow(bmap);
+ if (!bmap)
+ return NULL;
- bset = isl_basic_set_cow(bset);
+ dim = isl_basic_map_dim(bmap, type);
+ if (first + n > dim || first + n < first)
+ isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
+ "index out of bounds", return isl_basic_map_free(bmap));
- if (!bset)
- return NULL;
+ first += isl_basic_map_offset(bmap, type) - 1;
- for (i = bset->n_eq - 1; i >= 0; --i) {
- if (isl_seq_first_non_zero(bset->eq[i] + 1 + first, n) == -1)
+ for (i = bmap->n_eq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
continue;
- isl_basic_set_drop_equality(bset, i);
+ isl_basic_map_drop_equality(bmap, i);
}
- for (i = bset->n_ineq - 1; i >= 0; --i) {
- if (isl_seq_first_non_zero(bset->ineq[i] + 1 + first, n) == -1)
+ for (i = bmap->n_ineq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
continue;
- isl_basic_set_drop_inequality(bset, i);
+ isl_basic_map_drop_inequality(bmap, i);
}
- return bset;
+ return bmap;
+}
+
+/* Drop all constraints in bset that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_basic_map_drop_constraints_not_involving_dims(bset,
+ type, first, n);
+}
+
+/* Drop all constraints in bmap that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ unsigned dim;
+
+ if (!bmap)
+ return NULL;
+ if (n == 0)
+ return bmap;
+
+ dim = isl_basic_map_dim(bmap, type);
+ if (first + n > dim || first + n < first)
+ isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
+ "index out of bounds", return isl_basic_map_free(bmap));
+
+ bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
+ first += isl_basic_map_offset(bmap, type) - 1;
+ return isl_basic_map_drop_constraints_involving(bmap, first, n);
+}
+
+/* Drop all constraints in bset that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_basic_map_drop_constraints_involving_dims(bset,
+ type, first, n);
+}
+
+/* Drop all constraints in map that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_map *isl_map_drop_constraints_involving_dims(
+ __isl_take isl_map *map,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ int i;
+ unsigned dim;
+
+ if (!map)
+ return NULL;
+ if (n == 0)
+ return map;
+
+ dim = isl_map_dim(map, type);
+ if (first + n > dim || first + n < first)
+ isl_die(isl_map_get_ctx(map), isl_error_invalid,
+ "index out of bounds", return isl_map_free(map));
+
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_drop_constraints_involving_dims(
+ map->p[i], type, first, n);
+ if (!map->p[i])
+ return isl_map_free(map);
+ }
+
+ return map;
+}
+
+/* Drop all constraints in set that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_set *isl_set_drop_constraints_involving_dims(
+ __isl_take isl_set *set,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_map_drop_constraints_involving_dims(set, type, first, n);
}
/* Construct an initial underapproximatino of the hull of "bset"
{
int j;
struct isl_vec *sample;
- struct isl_basic_set *hull;
+ struct isl_basic_set *hull = NULL;
struct isl_tab_undo *snap;
if (!tab || !tab_cone)
return tab;
error:
+ isl_basic_set_free(hull);
isl_tab_free(tab);
return NULL;
}
hull = uset_affine_hull_bounded(bset);
- if (!hull)
+ if (!hull) {
+ isl_mat_free(Q);
isl_mat_free(U);
- else {
+ } else {
struct isl_vec *sample = isl_vec_copy(hull->sample);
U = isl_mat_drop_cols(U, 1 + total - cone_dim, cone_dim);
if (sample && sample->size > 0)
return hull;
error:
+ isl_mat_free(T1);
isl_mat_free(T2);
isl_basic_set_free(bset);
isl_basic_set_free(hull);
isl_basic_map_detect_equalities((isl_basic_map *)bset);
}
-__isl_give isl_map *isl_map_inline_foreach_basic_map(__isl_take isl_map *map,
- __isl_give isl_basic_map *(*fn)(__isl_take isl_basic_map *bmap))
-{
- struct isl_basic_map *bmap;
- int i;
-
- if (!map)
- return NULL;
-
- for (i = 0; i < map->n; ++i) {
- bmap = isl_basic_map_copy(map->p[i]);
- bmap = fn(bmap);
- if (!bmap)
- goto error;
- isl_basic_map_free(map->p[i]);
- map->p[i] = bmap;
- }
-
- return map;
-error:
- isl_map_free(map);
- return NULL;
-}
-
__isl_give isl_map *isl_map_detect_equalities(__isl_take isl_map *map)
{
return isl_map_inline_foreach_basic_map(map,
isl_basic_map_affine_hull((struct isl_basic_map *)bset);
}
-struct isl_basic_map *isl_map_affine_hull(struct isl_map *map)
+/* Compute the affine hull of each basic map in "map" separately
+ * and call isl_basic_map_gauss on the result.
+ */
+static __isl_give isl_map *isl_map_local_affine_hull(__isl_take isl_map *map)
{
int i;
+
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_affine_hull(map->p[i]);
+ map->p[i] = isl_basic_map_gauss(map->p[i], NULL);
+ if (!map->p[i])
+ return isl_map_free(map);
+ }
+
+ return map;
+}
+
+static __isl_give isl_set *isl_set_local_affine_hull(__isl_take isl_set *set)
+{
+ return isl_map_local_affine_hull(set);
+}
+
+/* Compute the affine hull of "map".
+ *
+ * We first compute the affine hull of each basic map separately.
+ * Then we align the divs and recompute the affine hulls of the basic
+ * maps since some of them may now have extra divs.
+ * In order to avoid performing parametric integer programming to
+ * compute explicit expressions for the divs, possible leading to
+ * an explosion in the number of basic maps, we first drop all unknown
+ * divs before aligning the divs. Note that the divs determined
+ * by an equality will be known since we call isl_basic_set_gauss
+ * from isl_map_local_affine_hull. Calling gauss is also needed
+ * because affine_hull assumes its input has been gaussed, while
+ * isl_map_affine_hull may be called on input that has not been gaussed,
+ * in particular from initial_facet_constraint.
+ * Similarly, align_divs may reorder some divs so that we need to
+ * gauss the result again.
+ * Finally, we combine the individual affine hulls into a single
+ * affine hull.
+ */
+__isl_give isl_basic_map *isl_map_affine_hull(__isl_take isl_map *map)
+{
struct isl_basic_map *model = NULL;
struct isl_basic_map *hull = NULL;
struct isl_set *set;
+ isl_basic_set *bset;
map = isl_map_detect_equalities(map);
+ map = isl_map_local_affine_hull(map);
+ map = isl_map_remove_empty_parts(map);
+ map = isl_map_remove_unknown_divs(map);
map = isl_map_align_divs(map);
if (!map)
model = isl_basic_map_copy(map->p[0]);
set = isl_map_underlying_set(map);
set = isl_set_cow(set);
+ set = isl_set_local_affine_hull(set);
if (!set)
goto error;
- for (i = 0; i < set->n; ++i) {
- set->p[i] = isl_basic_set_cow(set->p[i]);
- set->p[i] = isl_basic_set_affine_hull(set->p[i]);
- set->p[i] = isl_basic_set_gauss(set->p[i], NULL);
- if (!set->p[i])
- goto error;
- }
- set = isl_set_remove_empty_parts(set);
- if (set->n == 0) {
- hull = isl_basic_map_empty_like(model);
- isl_basic_map_free(model);
- } else {
- struct isl_basic_set *bset;
- while (set->n > 1) {
- set->p[0] = affine_hull(set->p[0], set->p[--set->n]);
- if (!set->p[0])
- goto error;
- }
- bset = isl_basic_set_copy(set->p[0]);
- hull = isl_basic_map_overlying_set(bset, model);
- }
+ while (set->n > 1)
+ set->p[0] = affine_hull(set->p[0], set->p[--set->n]);
+
+ bset = isl_basic_set_copy(set->p[0]);
+ hull = isl_basic_map_overlying_set(bset, model);
isl_set_free(set);
hull = isl_basic_map_simplify(hull);
return isl_basic_map_finalize(hull);
projects / platform / upstream / isl.git / blobdiff