return isl_basic_map_is_rational(bset);
}
+/* Does "bmap" contain any rational points?
+ *
+ * If "bmap" has an equality for each dimension, equating the dimension
+ * to an integer constant, then it has no rational points, even if it
+ * is marked as rational.
+ */
+int isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap)
+{
+ int has_rational = 1;
+ unsigned total;
+
+ if (!bmap)
+ return -1;
+ if (isl_basic_map_plain_is_empty(bmap))
+ return 0;
+ if (!isl_basic_map_is_rational(bmap))
+ return 0;
+ bmap = isl_basic_map_copy(bmap);
+ bmap = isl_basic_map_implicit_equalities(bmap);
+ if (!bmap)
+ return -1;
+ total = isl_basic_map_total_dim(bmap);
+ if (bmap->n_eq == total) {
+ int i, j;
+ for (i = 0; i < bmap->n_eq; ++i) {
+ j = isl_seq_first_non_zero(bmap->eq[i] + 1, total);
+ if (j < 0)
+ break;
+ if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
+ !isl_int_is_negone(bmap->eq[i][1 + j]))
+ break;
+ j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1,
+ total - j - 1);
+ if (j >= 0)
+ break;
+ }
+ if (i == bmap->n_eq)
+ has_rational = 0;
+ }
+ isl_basic_map_free(bmap);
+
+ return has_rational;
+}
+
+/* Does "map" contain any rational points?
+ */
+int isl_map_has_rational(__isl_keep isl_map *map)
+{
+ int i;
+ int has_rational;
+
+ if (!map)
+ return -1;
+ for (i = 0; i < map->n; ++i) {
+ has_rational = isl_basic_map_has_rational(map->p[i]);
+ if (has_rational < 0)
+ return -1;
+ if (has_rational)
+ return 1;
+ }
+ return 0;
+}
+
+/* Does "set" contain any rational points?
+ */
+int isl_set_has_rational(__isl_keep isl_set *set)
+{
+ return isl_map_has_rational(set);
+}
+
/* Is this basic set a parameter domain?
*/
int isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
bmap->div[div]);
}
+int isl_basic_set_add_div_constraints(struct isl_basic_set *bset, unsigned div)
+{
+ return isl_basic_map_add_div_constraints(bset, div);
+}
+
struct isl_basic_set *isl_basic_map_underlying_set(
struct isl_basic_map *bmap)
{
return NULL;
}
+/* Return the union of "map1" and "map2", where we assume for now that
+ * "map1" and "map2" are disjoint. Note that the basic maps inside
+ * "map1" or "map2" may not be disjoint from each other.
+ * Also note that this function is also called from isl_map_union,
+ * which takes care of handling the situation where "map1" and "map2"
+ * may not be disjoint.
+ *
+ * If one of the inputs is empty, we can simply return the other input.
+ * Similarly, if one of the inputs is universal, then it is equal to the union.
+ */
static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1,
__isl_take isl_map *map2)
{
int i;
unsigned flags = 0;
struct isl_map *map = NULL;
+ int is_universe;
if (!map1 || !map2)
goto error;
return map1;
}
+ is_universe = isl_map_plain_is_universe(map1);
+ if (is_universe < 0)
+ goto error;
+ if (is_universe) {
+ isl_map_free(map2);
+ return map1;
+ }
+
+ is_universe = isl_map_plain_is_universe(map2);
+ if (is_universe < 0)
+ goto error;
+ if (is_universe) {
+ isl_map_free(map1);
+ return map2;
+ }
+
isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
struct isl_basic_map *dst, struct isl_basic_map *src)
{
int i;
- unsigned total = isl_space_dim(src->dim, isl_dim_all);
+ unsigned total;
if (!dst || !src)
goto error;
src->n_div, 0, 2 * src->n_div);
if (!dst)
return NULL;
+ total = isl_space_dim(src->dim, isl_dim_all);
for (i = 0; i < src->n_div; ++i) {
int j = find_div(dst, src, i);
if (j < 0) {
isl_set_free(set);
return NULL;
}
+
+/* Check if the range of "ma" is compatible with "space".
+ * Return -1 if anything is wrong.
+ */
+static int check_space_compatible_range_multi_aff(
+ __isl_keep isl_space *space, __isl_keep isl_multi_aff *ma)
+{
+ int m;
+ isl_space *ma_space;
+
+ ma_space = isl_multi_aff_get_space(ma);
+ m = isl_space_is_range_internal(space, ma_space);
+ isl_space_free(ma_space);
+ if (m >= 0 && !m)
+ isl_die(isl_space_get_ctx(space), isl_error_invalid,
+ "spaces don't match", return -1);
+ return m;
+}
+
+/* Check if the range of "ma" is compatible with "bset".
+ * Return -1 if anything is wrong.
+ */
+static int check_basic_set_compatible_range_multi_aff(
+ __isl_keep isl_basic_set *bset, __isl_keep isl_multi_aff *ma)
+{
+ return check_space_compatible_range_multi_aff(bset->dim, ma);
+}
+
+/* Copy the divs from "ma" to "bset", adding zeros for the coefficients
+ * of the other divs in "bset".
+ */
+static int set_ma_divs(__isl_keep isl_basic_set *bset,
+ __isl_keep isl_multi_aff *ma, int n_div)
+{
+ int i;
+ isl_local_space *ls;
+
+ if (n_div == 0)
+ return 0;
+
+ ls = isl_aff_get_domain_local_space(ma->p[0]);
+ if (!ls)
+ return -1;
+
+ for (i = 0; i < n_div; ++i) {
+ isl_seq_cpy(bset->div[i], ls->div->row[i], ls->div->n_col);
+ isl_seq_clr(bset->div[i] + ls->div->n_col, bset->n_div - n_div);
+ if (isl_basic_set_add_div_constraints(bset, i) < 0)
+ goto error;
+ }
+
+ isl_local_space_free(ls);
+ return 0;
+error:
+ isl_local_space_free(ls);
+ return -1;
+}
+
+/* How many stride constraints does "ma" enforce?
+ * That is, how many of the affine expressions have a denominator
+ * different from one?
+ */
+static int multi_aff_strides(__isl_keep isl_multi_aff *ma)
+{
+ int i;
+ int strides = 0;
+
+ for (i = 0; i < ma->n; ++i)
+ if (!isl_int_is_one(ma->p[i]->v->el[0]))
+ strides++;
+
+ return strides;
+}
+
+/* For each affine expression in ma of the form
+ *
+ * x_i = (f_i y + h_i)/m_i
+ *
+ * with m_i different from one, add a constraint to "bset"
+ * of the form
+ *
+ * f_i y + h_i = m_i alpha_i
+ *
+ * with alpha_i an additional existentially quantified variable.
+ */
+static __isl_give isl_basic_set *add_ma_strides(
+ __isl_take isl_basic_set *bset, __isl_keep isl_multi_aff *ma)
+{
+ int i, k;
+ int div;
+ int total;
+
+ total = isl_basic_set_total_dim(bset);
+ for (i = 0; i < ma->n; ++i) {
+ int len;
+
+ if (isl_int_is_one(ma->p[i]->v->el[0]))
+ continue;
+ div = isl_basic_set_alloc_div(bset);
+ k = isl_basic_set_alloc_equality(bset);
+ if (div < 0 || k < 0)
+ goto error;
+ isl_int_set_si(bset->div[div][0], 0);
+ len = ma->p[i]->v->size;
+ isl_seq_cpy(bset->eq[k], ma->p[i]->v->el + 1, len - 1);
+ isl_seq_clr(bset->eq[k] + len - 1, 1 + total - (len - 1));
+ isl_int_neg(bset->eq[k][1 + total], ma->p[i]->v->el[0]);
+ total++;
+ }
+
+ return bset;
+error:
+ isl_basic_set_free(bset);
+ return NULL;
+}
+
+/* Compute the preimage of "bset" under the function represented by "ma".
+ * In other words, plug in "ma" in "bset". The result is a basic set
+ * that lives in the domain space of "ma".
+ *
+ * If bset is represented by
+ *
+ * A(p) + B x + C(divs) >= 0
+ *
+ * and ma is represented by
+ *
+ * x = D(p) + F(y) + G(divs')
+ *
+ * then the result is
+ *
+ * A(p) + B D(p) + B F(y) + B G(divs') + C(divs) >= 0
+ *
+ * The divs in the input set are similarly adjusted.
+ * In particular
+ *
+ * floor((a_i(p) + b_i x + c_i(divs))/n_i)
+ *
+ * becomes
+ *
+ * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
+ *
+ * If bset is not a rational set and if F(y) involves any denominators
+ *
+ * x_i = (f_i y + h_i)/m_i
+ *
+ * the additional constraints are added to ensure that we only
+ * map back integer points. That is we enforce
+ *
+ * f_i y + h_i = m_i alpha_i
+ *
+ * with alpha_i an additional existentially quantified variable.
+ *
+ * We first copy over the divs from "ma".
+ * Then we add the modified constraints and divs from "bset".
+ * Finally, we add the stride constraints, if needed.
+ */
+__isl_give isl_basic_set *isl_basic_set_preimage_multi_aff(
+ __isl_take isl_basic_set *bset, __isl_take isl_multi_aff *ma)
+{
+ int i, k;
+ isl_space *space;
+ isl_basic_set *res = NULL;
+ int n_div_bset, n_div_ma;
+ isl_int f, c1, c2, g;
+ int rational, strides;
+
+ isl_int_init(f);
+ isl_int_init(c1);
+ isl_int_init(c2);
+ isl_int_init(g);
+
+ ma = isl_multi_aff_align_divs(ma);
+ if (!bset || !ma)
+ goto error;
+ if (check_basic_set_compatible_range_multi_aff(bset, ma) < 0)
+ goto error;
+
+ n_div_bset = isl_basic_set_dim(bset, isl_dim_div);
+ n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
+
+ space = isl_space_domain(isl_multi_aff_get_space(ma));
+ rational = isl_basic_set_is_rational(bset);
+ strides = rational ? 0 : multi_aff_strides(ma);
+ res = isl_basic_set_alloc_space(space, n_div_ma + n_div_bset + strides,
+ bset->n_eq + strides, bset->n_ineq + 2 * n_div_ma);
+ if (rational)
+ res = isl_basic_set_set_rational(res);
+
+ for (i = 0; i < n_div_ma + n_div_bset; ++i)
+ if (isl_basic_set_alloc_div(res) < 0)
+ goto error;
+
+ if (set_ma_divs(res, ma, n_div_ma) < 0)
+ goto error;
+
+ for (i = 0; i < bset->n_eq; ++i) {
+ k = isl_basic_set_alloc_equality(res);
+ if (k < 0)
+ goto error;
+ isl_seq_preimage(res->eq[k], bset->eq[i], ma, n_div_ma,
+ n_div_bset, f, c1, c2, g, 0);
+ }
+
+ for (i = 0; i < bset->n_ineq; ++i) {
+ k = isl_basic_set_alloc_inequality(res);
+ if (k < 0)
+ goto error;
+ isl_seq_preimage(res->ineq[k], bset->ineq[i], ma, n_div_ma,
+ n_div_bset, f, c1, c2, g, 0);
+ }
+
+ for (i = 0; i < bset->n_div; ++i) {
+ if (isl_int_is_zero(bset->div[i][0])) {
+ isl_int_set_si(res->div[n_div_ma + i][0], 0);
+ continue;
+ }
+ isl_seq_preimage(res->div[n_div_ma + i], bset->div[i],
+ ma, n_div_ma, n_div_bset, f, c1, c2, g, 1);
+ }
+
+ if (strides)
+ res = add_ma_strides(res, ma);
+
+ isl_int_clear(f);
+ isl_int_clear(c1);
+ isl_int_clear(c2);
+ isl_int_clear(g);
+ isl_basic_set_free(bset);
+ isl_multi_aff_free(ma);
+ res = isl_basic_set_simplify(res);
+ return isl_basic_set_finalize(res);
+error:
+ isl_int_clear(f);
+ isl_int_clear(c1);
+ isl_int_clear(c2);
+ isl_int_clear(g);
+ isl_basic_set_free(bset);
+ isl_multi_aff_free(ma);
+ isl_basic_set_free(res);
+ return NULL;
+}
+
+/* Check if the range of "ma" is compatible with "set".
+ * Return -1 if anything is wrong.
+ */
+static int check_set_compatible_range_multi_aff(
+ __isl_keep isl_set *set, __isl_keep isl_multi_aff *ma)
+{
+ return check_space_compatible_range_multi_aff(set->dim, ma);
+}
+
+/* Compute the preimage of "set" under the function represented by "ma".
+ * In other words, plug in "ma" in "set. The result is a set
+ * that lives in the domain space of "ma".
+ */
+static __isl_give isl_set *set_preimage_multi_aff(__isl_take isl_set *set,
+ __isl_take isl_multi_aff *ma)
+{
+ int i;
+
+ set = isl_set_cow(set);
+ ma = isl_multi_aff_align_divs(ma);
+ if (!set || !ma)
+ goto error;
+ if (check_set_compatible_range_multi_aff(set, ma) < 0)
+ goto error;
+
+ for (i = 0; i < set->n; ++i) {
+ set->p[i] = isl_basic_set_preimage_multi_aff(set->p[i],
+ isl_multi_aff_copy(ma));
+ if (!set->p[i])
+ goto error;
+ }
+
+ isl_space_free(set->dim);
+ set->dim = isl_multi_aff_get_domain_space(ma);
+ if (!set->dim)
+ goto error;
+
+ isl_multi_aff_free(ma);
+ if (set->n > 1)
+ ISL_F_CLR(set, ISL_MAP_DISJOINT);
+ ISL_F_CLR(set, ISL_SET_NORMALIZED);
+ return set;
+error:
+ isl_multi_aff_free(ma);
+ isl_set_free(set);
+ return NULL;
+}
+
+__isl_give isl_set *isl_set_preimage_multi_aff(__isl_take isl_set *set,
+ __isl_take isl_multi_aff *ma)
+{
+ if (!set || !ma)
+ goto error;
+
+ if (isl_space_match(set->dim, isl_dim_param, ma->space, isl_dim_param))
+ return set_preimage_multi_aff(set, ma);
+
+ if (!isl_space_has_named_params(set->dim) ||
+ !isl_space_has_named_params(ma->space))
+ isl_die(set->ctx, isl_error_invalid,
+ "unaligned unnamed parameters", goto error);
+ set = isl_set_align_params(set, isl_multi_aff_get_space(ma));
+ ma = isl_multi_aff_align_params(ma, isl_set_get_space(set));
+
+ return set_preimage_multi_aff(set, ma);
+error:
+ isl_multi_aff_free(ma);
+ return isl_set_free(set);
+}
+
+/* Compute the preimage of "set" under the function represented by "pma".
+ * In other words, plug in "pma" in "set. The result is a set
+ * that lives in the domain space of "pma".
+ */
+static __isl_give isl_set *set_preimage_pw_multi_aff(__isl_take isl_set *set,
+ __isl_take isl_pw_multi_aff *pma)
+{
+ int i;
+ isl_set *res;
+
+ if (!pma)
+ goto error;
+
+ if (pma->n == 0) {
+ isl_pw_multi_aff_free(pma);
+ res = isl_set_empty(isl_set_get_space(set));
+ isl_set_free(set);
+ return res;
+ }
+
+ res = isl_set_preimage_multi_aff(isl_set_copy(set),
+ isl_multi_aff_copy(pma->p[0].maff));
+ res = isl_set_intersect(res, isl_set_copy(pma->p[0].set));
+
+ for (i = 1; i < pma->n; ++i) {
+ isl_set *res_i;
+
+ res_i = isl_set_preimage_multi_aff(isl_set_copy(set),
+ isl_multi_aff_copy(pma->p[i].maff));
+ res_i = isl_set_intersect(res_i, isl_set_copy(pma->p[i].set));
+ res = isl_set_union(res, res_i);
+ }
+
+ isl_pw_multi_aff_free(pma);
+ isl_set_free(set);
+ return res;
+error:
+ isl_pw_multi_aff_free(pma);
+ isl_set_free(set);
+ return NULL;
+}
+
+__isl_give isl_set *isl_set_preimage_pw_multi_aff(__isl_take isl_set *set,
+ __isl_take isl_pw_multi_aff *pma)
+{
+ if (!set || !pma)
+ goto error;
+
+ if (isl_space_match(set->dim, isl_dim_param, pma->dim, isl_dim_param))
+ return set_preimage_pw_multi_aff(set, pma);
+
+ if (!isl_space_has_named_params(set->dim) ||
+ !isl_space_has_named_params(pma->dim))
+ isl_die(set->ctx, isl_error_invalid,
+ "unaligned unnamed parameters", goto error);
+ set = isl_set_align_params(set, isl_pw_multi_aff_get_space(pma));
+ pma = isl_pw_multi_aff_align_params(pma, isl_set_get_space(set));
+
+ return set_preimage_pw_multi_aff(set, pma);
+error:
+ isl_pw_multi_aff_free(pma);
+ return isl_set_free(set);
+}
projects / platform / upstream / isl.git / blobdiff