diff --git a/isl_convex_hull.c b/isl_convex_hull.c
--- a/isl_convex_hull.c
+++ b/isl_convex_hull.c
if (!facet || !hull_facet)
goto error;
hull = isl_basic_set_cow(hull);
- hull = isl_basic_set_extend_space(hull,
- isl_space_copy(hull->dim), 0, 0, facet->n_ineq);
+ hull = isl_basic_set_extend(hull, 0, 0, facet->n_ineq);
if (!hull)
goto error;
for (j = 0; j < facet->n_ineq; ++j) {
static __isl_give isl_basic_set *valid_direction_lp(
__isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
{
- isl_space *dim;
+ isl_space *space;
struct isl_basic_set *lp;
unsigned d;
int n;
d = 1 + total;
n = 2 +
2 * bset1->n_eq + bset1->n_ineq + 2 * bset2->n_eq + bset2->n_ineq;
- dim = isl_space_set_alloc(bset1->ctx, 0, n);
- lp = isl_basic_set_alloc_space(dim, 0, d, n);
+ space = isl_space_set_alloc(bset1->ctx, 0, n);
+ lp = isl_basic_set_alloc_space(space, 0, d, n);
if (!lp)
goto error;
for (i = 0; i < n; ++i) {
int ineq;
};
-static int max_constraint_equal(const void *entry, const void *val)
+static isl_bool max_constraint_equal(const void *entry, const void *val)
{
struct max_constraint *a = (struct max_constraint *)entry;
isl_int *b = (isl_int *)val;
- return isl_seq_eq(a->c->row[0] + 1, b, a->c->n_col - 1);
+ return isl_bool_ok(isl_seq_eq(a->c->row[0] + 1, b, a->c->n_col - 1));
}
-static void update_constraint(struct isl_ctx *ctx, struct isl_hash_table *table,
+static isl_stat update_constraint(struct isl_ctx *ctx,
+ struct isl_hash_table *table,
isl_int *con, unsigned len, int n, int ineq)
{
struct isl_hash_table_entry *entry;
@@ -1538,30 +1538,34 @@ static void update_constraint(struct isl_ctx *ctx, struct isl_hash_table *table,
entry = isl_hash_table_find(ctx, table, c_hash, max_constraint_equal,
con + 1, 0);
if (!entry)
- return;
+ return isl_stat_error;
+ if (entry == isl_hash_table_entry_none)
+ return isl_stat_ok;
c = entry->data;
if (c->count < n) {
isl_hash_table_remove(ctx, table, entry);
- return;
+ return isl_stat_ok;
}
c->count++;
if (isl_int_gt(c->c->row[0][0], con[0]))
- return;
+ return isl_stat_ok;
if (isl_int_eq(c->c->row[0][0], con[0])) {
if (ineq)
c->ineq = ineq;
- return;
+ return isl_stat_ok;
}
c->c = isl_mat_cow(c->c);
isl_int_set(c->c->row[0][0], con[0]);
c->ineq = ineq;
+
+ return isl_stat_ok;
}
/* Check whether the constraint hash table "table" contains the constraint
* "con".
*/
-static int has_constraint(struct isl_ctx *ctx, struct isl_hash_table *table,
- isl_int *con, unsigned len, int n)
+static isl_bool has_constraint(struct isl_ctx *ctx,
+ struct isl_hash_table *table, isl_int *con, unsigned len, int n)
{
struct isl_hash_table_entry *entry;
struct max_constraint *c;
@@ -1571,14 +1575,34 @@ static int has_constraint(struct isl_ctx *ctx, struct isl_hash_table *table,
entry = isl_hash_table_find(ctx, table, c_hash, max_constraint_equal,
con + 1, 0);
if (!entry)
- return 0;
+ return isl_bool_error;
+ if (entry == isl_hash_table_entry_none)
+ return isl_bool_false;
c = entry->data;
if (c->count < n)
- return 0;
- return isl_int_eq(c->c->row[0][0], con[0]);
+ return isl_bool_false;
+ return isl_bool_ok(isl_int_eq(c->c->row[0][0], con[0]));
+}
+
+/* Are the constraints of "bset" known to be facets?
+ * If there are any equality constraints, then they are not.
+ * If there may be redundant constraints, then those
+ * redundant constraints are not facets.
+ */
+static isl_bool has_facets(__isl_keep isl_basic_set *bset)
+{
+ isl_size n_eq;
+
+ n_eq = isl_basic_set_n_equality(bset);
+ if (n_eq < 0)
+ return isl_bool_error;
+ if (n_eq != 0)
+ return isl_bool_false;
+ return ISL_F_ISSET(bset, ISL_BASIC_SET_NO_REDUNDANT);
}
/* Check for inequality constraints of a basic set without equalities
+ * or redundant constraints
* such that the same or more stringent copies of the constraint appear
* in all of the basic sets. Such constraints are necessarily facet
* constraints of the convex hull.
*is_hull = 0;
- for (i = 0; i < set->n; ++i)
- if (set->p[i]->n_eq == 0)
+ for (i = 0; i < set->n; ++i) {
+ isl_bool facets = has_facets(set->p[i]);
+ if (facets < 0)
+ return isl_basic_set_free(hull);
+ if (facets)
break;
+ }
if (i >= set->n)
return hull;
min_constraints = set->p[i]->n_ineq;
best = i;
for (i = best + 1; i < set->n; ++i) {
- if (set->p[i]->n_eq != 0)
+ isl_bool facets = has_facets(set->p[i]);
+ if (facets < 0)
+ return isl_basic_set_free(hull);
+ if (!facets)
continue;
if (set->p[i]->n_ineq >= min_constraints)
continue;
isl_int *eq = set->p[s]->eq[i];
for (j = 0; j < 2; ++j) {
isl_seq_neg(eq, eq, 1 + total);
- update_constraint(hull->ctx, table,
- eq, total, n, 0);
+ if (update_constraint(hull->ctx, table,
+ eq, total, n, 0) < 0)
+ goto error;
}
}
for (i = 0; i < set->p[s]->n_ineq; ++i) {
isl_int *ineq = set->p[s]->ineq[i];
- update_constraint(hull->ctx, table, ineq, total, n,
- set->p[s]->n_eq == 0);
+ if (update_constraint(hull->ctx, table, ineq, total, n,
+ set->p[s]->n_eq == 0) < 0)
+ goto error;
}
++n;
}
if (set->p[s]->n_ineq != hull->n_ineq)
continue;
for (i = 0; i < set->p[s]->n_ineq; ++i) {
+ isl_bool has;
isl_int *ineq = set->p[s]->ineq[i];
- if (!has_constraint(hull->ctx, table, ineq, total, n))
+ has = has_constraint(hull->ctx, table, ineq, total, n);
+ if (has < 0)
+ goto error;
+ if (!has)
break;
}
if (i == set->p[s]->n_ineq)
return NULL;
}
-struct isl_basic_set *isl_set_convex_hull(struct isl_set *set)
+__isl_give isl_basic_set *isl_set_convex_hull(__isl_take isl_set *set)
{
return bset_from_bmap(isl_map_convex_hull(set_to_map(set)));
}
isl_int *p;
};
-static int has_ineq(const void *entry, const void *val)
+static isl_bool has_ineq(const void *entry, const void *val)
{
isl_int *row = (isl_int *)entry;
struct ineq_cmp_data *v = (struct ineq_cmp_data *)val;
- return isl_seq_eq(row + 1, v->p + 1, v->len) ||
- isl_seq_is_neg(row + 1, v->p + 1, v->len);
+ return isl_bool_ok(isl_seq_eq(row + 1, v->p + 1, v->len) ||
+ isl_seq_is_neg(row + 1, v->p + 1, v->len));
}
static int hash_ineq(struct isl_ctx *ctx, struct isl_hash_table *table,
* least its constant term) may need to be temporarily negated to get
* the actually hashed constraint.
*/
-static void set_max_constant_term(struct sh_data *data, __isl_keep isl_set *set,
+static isl_stat set_max_constant_term(struct sh_data *data,
+ __isl_keep isl_set *set,
int i, isl_int *ineq, uint32_t c_hash, struct ineq_cmp_data *v)
{
int j;
@@ -2141,6 +2179,8 @@ static void set_max_constant_term(struct sh_data *data, __isl_keep isl_set *set,
entry = isl_hash_table_find(ctx, data->p[j].table,
c_hash, &has_ineq, v, 0);
if (!entry)
+ return isl_stat_error;
+ if (entry == isl_hash_table_entry_none)
continue;
ineq_j = entry->data;
@@ -2152,6 +2192,8 @@ static void set_max_constant_term(struct sh_data *data, __isl_keep isl_set *set,
if (neg)
isl_int_neg(ineq_j[0], ineq_j[0]);
}
+
+ return isl_stat_ok;
}
/* Check if inequality "ineq" from basic set "i" is or can be relaxed to
entry = isl_hash_table_find(hull->ctx, data->hull_table, c_hash,
has_ineq, &v, 0);
- if (entry)
+ if (!entry)
+ return isl_basic_set_free(hull);
+ if (entry != isl_hash_table_entry_none)
return hull;
for (j = 0; j < i; ++j) {
entry = isl_hash_table_find(hull->ctx, data->p[j].table,
c_hash, has_ineq, &v, 0);
- if (entry)
+ if (!entry)
+ return isl_basic_set_free(hull);
+ if (entry != isl_hash_table_entry_none)
break;
}
if (j < i)
goto error;
isl_seq_cpy(hull->ineq[k], ineq, 1 + v.len);
- set_max_constant_term(data, set, i, hull->ineq[k], c_hash, &v);
+ if (set_max_constant_term(data, set, i, hull->ineq[k], c_hash, &v) < 0)
+ goto error;
for (j = 0; j < i; ++j) {
int bound;
bound = is_bound(data, set, j, hull->ineq[k], shift);
int bound;
entry = isl_hash_table_find(hull->ctx, data->p[j].table,
c_hash, has_ineq, &v, 0);
- if (entry)
+ if (!entry)
+ return isl_basic_set_free(hull);
+ if (entry != isl_hash_table_entry_none)
continue;
bound = is_bound(data, set, j, hull->ineq[k], shift);
if (bound < 0)
return map_simple_hull(map, 1);
}
-struct isl_basic_set *isl_set_simple_hull(struct isl_set *set)
+__isl_give isl_basic_set *isl_set_simple_hull(__isl_take isl_set *set)
{
return bset_from_bmap(isl_map_simple_hull(set_to_map(set)));
}
__isl_give isl_basic_map *isl_basic_map_plain_unshifted_simple_hull(
__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{
- bmap1 = isl_basic_map_drop_constraint_involving_unknown_divs(bmap1);
- bmap2 = isl_basic_map_drop_constraint_involving_unknown_divs(bmap2);
+ if (isl_basic_map_check_equal_space(bmap1, bmap2) < 0)
+ goto error;
+
+ bmap1 = isl_basic_map_drop_constraints_involving_unknown_divs(bmap1);
+ bmap2 = isl_basic_map_drop_constraints_involving_unknown_divs(bmap2);
+ bmap1 = isl_basic_map_order_divs(bmap1);
bmap2 = isl_basic_map_align_divs(bmap2, bmap1);
bmap1 = isl_basic_map_align_divs(bmap1, bmap2);
- bmap1 = isl_basic_map_gauss(bmap1, NULL);
- bmap2 = isl_basic_map_gauss(bmap2, NULL);
bmap1 = isl_basic_map_sort_constraints(bmap1);
bmap2 = isl_basic_map_sort_constraints(bmap2);
isl_basic_map_free(bmap2);
bmap1 = isl_basic_map_finalize(bmap1);
return bmap1;
+error:
+ isl_basic_map_free(bmap1);
+ isl_basic_map_free(bmap2);
+ return NULL;
}
/* Compute a superset of the convex hull of "map" that is described
return NULL;
if (map->n <= 1)
return map_simple_hull_trivial(map);
- map = isl_map_drop_constraint_involving_unknown_divs(map);
+ map = isl_map_drop_constraints_involving_unknown_divs(map);
hull = isl_basic_map_copy(map->p[0]);
for (i = 1; i < map->n; ++i) {
isl_basic_map *bmap_i;
entry = isl_hash_table_find(ctx, data->p[i].table,
c_hash, &has_ineq, &v, 0);
- if (entry) {
+ if (!entry)
+ return isl_basic_set_free(hull);
+ if (entry != isl_hash_table_entry_none) {
isl_int *ineq_i = entry->data;
int neg, more_relaxed;