static struct isl_basic_set *uset_convex_hull_wrap(struct isl_set *set);
-static swap_ineq(struct isl_basic_map *bmap, unsigned i, unsigned j)
+static void swap_ineq(struct isl_basic_map *bmap, unsigned i, unsigned j)
{
isl_int *t;
}
}
+/* Return 1 if constraint c is redundant with respect to the constraints
+ * in bmap. If c is a lower [upper] bound in some variable and bmap
+ * does not have a lower [upper] bound in that variable, then c cannot
+ * be redundant and we do not need solve any lp.
+ */
+int isl_basic_map_constraint_is_redundant(struct isl_basic_map **bmap,
+ isl_int *c, isl_int *opt_n, isl_int *opt_d)
+{
+ enum isl_lp_result res;
+ unsigned total;
+ int i, j;
+
+ if (!bmap)
+ return -1;
+
+ total = (*bmap)->nparam + (*bmap)->n_in + (*bmap)->n_out + (*bmap)->n_div;
+ for (i = 0; i < total; ++i) {
+ int sign;
+ if (isl_int_is_zero(c[1+i]))
+ continue;
+ sign = isl_int_sgn(c[1+i]);
+ for (j = 0; j < (*bmap)->n_ineq; ++j)
+ if (sign == isl_int_sgn((*bmap)->ineq[j][1+i]))
+ break;
+ if (j == (*bmap)->n_ineq)
+ break;
+ }
+ if (i < total)
+ return 0;
+
+ res = isl_solve_lp(*bmap, 0, c+1, (*bmap)->ctx->one, opt_n, opt_d);
+ if (res == isl_lp_unbounded)
+ return 0;
+ if (res == isl_lp_error)
+ return -1;
+ if (res == isl_lp_empty) {
+ *bmap = isl_basic_map_set_to_empty(*bmap);
+ return 0;
+ }
+ if (opt_d)
+ isl_int_addmul(*opt_n, *opt_d, c[0]);
+ else
+ isl_int_add(*opt_n, *opt_n, c[0]);
+ return !isl_int_is_neg(*opt_n);
+}
+
+int isl_basic_set_constraint_is_redundant(struct isl_basic_set **bset,
+ isl_int *c, isl_int *opt_n, isl_int *opt_d)
+{
+ return isl_basic_map_constraint_is_redundant(
+ (struct isl_basic_map **)bset, c, opt_n, opt_d);
+}
+
/* Compute the convex hull of a basic map, by removing the redundant
* constraints. If the minimal value along the normal of a constraint
* is the same if the constraint is removed, then the constraint is redundant.
isl_int_init(opt_n);
isl_int_init(opt_d);
for (i = bmap->n_ineq-1; i >= 0; --i) {
- enum isl_lp_result res;
+ int redundant;
swap_ineq(bmap, i, bmap->n_ineq-1);
bmap->n_ineq--;
- res = isl_solve_lp(bmap, 0,
- bmap->ineq[bmap->n_ineq]+1, ctx->one, &opt_n, &opt_d);
- bmap->n_ineq++;
- swap_ineq(bmap, i, bmap->n_ineq-1);
- if (res == isl_lp_unbounded)
- continue;
- if (res == isl_lp_error)
+ redundant = isl_basic_map_constraint_is_redundant(&bmap,
+ bmap->ineq[bmap->n_ineq], &opt_n, &opt_d);
+ if (redundant == -1)
goto error;
- if (res == isl_lp_empty) {
- bmap = isl_basic_map_set_to_empty(bmap);
+ if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
break;
- }
- isl_int_addmul(opt_n, opt_d, bmap->ineq[i][0]);
- if (!isl_int_is_neg(opt_n))
+ bmap->n_ineq++;
+ swap_ineq(bmap, i, bmap->n_ineq-1);
+ if (redundant)
isl_basic_map_drop_inequality(bmap, i);
}
isl_int_clear(opt_n);
isl_basic_map_convex_hull((struct isl_basic_map *)bset);
}
+/* Check if the set set is bound in the direction of the affine
+ * constraint c and if so, set the constant term such that the
+ * resulting constraint is a bounding constraint for the set.
+ */
static int uset_is_bound(struct isl_ctx *ctx, struct isl_set *set,
isl_int *c, unsigned len)
{
return (struct isl_basic_set *)
isl_map_convex_hull((struct isl_map *)set);
}
+
+/* Compute a superset of the convex hull of map that is described
+ * by only translates of the constraints in the constituents of map.
+ */
+struct isl_basic_map *isl_map_simple_hull(struct isl_map *map)
+{
+ struct isl_set *set = NULL;
+ struct isl_basic_map *hull;
+ struct isl_basic_set *bset = NULL;
+ int i, j;
+ unsigned n_ineq;
+
+ if (map->n == 0) {
+ hull = isl_basic_map_empty(map->ctx,
+ map->nparam, map->n_in, map->n_out);
+ isl_map_free(map);
+ return hull;
+ }
+ if (map->n == 1) {
+ hull = isl_basic_map_copy(map->p[0]);
+ isl_map_free(map);
+ return hull;
+ }
+
+ n_ineq = 0;
+ for (i = 0; i < map->n; ++i) {
+ if (!map->p[i])
+ goto error;
+ n_ineq += map->p[i]->n_ineq;
+ }
+
+ set = isl_map_underlying_set(isl_map_copy(map));
+ if (!set)
+ goto error;
+
+ bset = isl_set_affine_hull(isl_set_copy(set));
+ if (!bset)
+ goto error;
+ bset = isl_basic_set_extend(bset, 0, bset->dim, 0, 0, n_ineq);
+ if (!bset)
+ goto error;
+
+ for (i = 0; i < set->n; ++i) {
+ for (j = 0; j < set->p[i]->n_ineq; ++j) {
+ int k;
+ int is_bound;
+
+ k = isl_basic_set_alloc_inequality(bset);
+ if (k < 0)
+ goto error;
+ isl_seq_cpy(bset->ineq[k], set->p[i]->ineq[j],
+ 1 + bset->dim);
+ is_bound = uset_is_bound(set->ctx, set, bset->ineq[k],
+ 1 + bset->dim);
+ if (is_bound < 0)
+ goto error;
+ if (!is_bound)
+ isl_basic_set_free_inequality(bset, 1);
+ }
+ }
+
+ bset = isl_basic_set_simplify(bset);
+ bset = isl_basic_set_finalize(bset);
+ bset = isl_basic_set_convex_hull(bset);
+
+ hull = isl_basic_map_overlying_set(bset, isl_basic_map_copy(map->p[0]));
+
+ isl_set_free(set);
+ isl_map_free(map);
+ return hull;
+error:
+ isl_basic_set_free(bset);
+ isl_set_free(set);
+ isl_map_free(map);
+ return NULL;
+}
+
+struct isl_basic_set *isl_set_simple_hull(struct isl_set *set)
+{
+ return (struct isl_basic_set *)
+ isl_map_simple_hull((struct isl_map *)set);
+}
projects / platform / upstream / isl.git / blobdiff