+
+/* Compute the preimage of the affine expression "src" under "ma"
+ * and put the result in "dst". If "has_denom" is set (to one),
+ * then "src" and "dst" have an extra initial denominator.
+ * "n_div_ma" is the number of existentials in "ma"
+ * "n_div_bset" is the number of existentials in "src"
+ * The resulting "dst" (which is assumed to have been allocated by
+ * the caller) contains coefficients for both sets of existentials,
+ * first those in "ma" and then those in "src".
+ * f, c1, c2 and g are temporary objects that have been initialized
+ * by the caller.
+ *
+ * Let src represent the expression
+ *
+ * (a(p) + b x + c(divs))/d
+ *
+ * and let ma represent the expressions
+ *
+ * x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
+ *
+ * We start out with the following expression for dst:
+ *
+ * (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d
+ *
+ * with the multiplication factor f initially equal to 1.
+ * For each x_i that we substitute, we multiply the numerator
+ * (and denominator) of dst by c_1 = m_i and add the numerator
+ * of the x_i expression multiplied by c_2 = f b_i,
+ * after removing the common factors of c_1 and c_2.
+ * The multiplication factor f also needs to be multiplied by c_1
+ * for the next x_j, j > i.
+ */
+void isl_seq_preimage(isl_int *dst, isl_int *src,
+ __isl_keep isl_multi_aff *ma, int n_div_ma, int n_div_bset,
+ isl_int f, isl_int c1, isl_int c2, isl_int g, int has_denom)
+{
+ int i;
+ int n_param, n_in, n_out;
+ int o_div_bset;
+
+ n_param = isl_multi_aff_dim(ma, isl_dim_param);
+ n_in = isl_multi_aff_dim(ma, isl_dim_in);
+ n_out = isl_multi_aff_dim(ma, isl_dim_out);
+
+ o_div_bset = has_denom + 1 + n_param + n_in + n_div_ma;
+
+ isl_seq_cpy(dst, src, has_denom + 1 + n_param);
+ isl_seq_clr(dst + has_denom + 1 + n_param, n_in + n_div_ma);
+ isl_seq_cpy(dst + o_div_bset,
+ src + has_denom + 1 + n_param + n_out, n_div_bset);
+
+ isl_int_set_si(f, 1);
+
+ for (i = 0; i < n_out; ++i) {
+ if (isl_int_is_zero(src[has_denom + 1 + n_param + i]))
+ continue;
+ isl_int_set(c1, ma->p[i]->v->el[0]);
+ isl_int_mul(c2, f, src[has_denom + 1 + n_param + i]);
+ isl_int_gcd(g, c1, c2);
+ isl_int_divexact(c1, c1, g);
+ isl_int_divexact(c2, c2, g);
+
+ isl_int_mul(f, f, c1);
+ isl_seq_combine(dst + has_denom, c1, dst + has_denom,
+ c2, ma->p[i]->v->el + 1, ma->p[i]->v->size - 1);
+ isl_seq_scale(dst + o_div_bset,
+ dst + o_div_bset, c1, n_div_bset);
+ if (has_denom)
+ isl_int_mul(dst[0], dst[0], c1);
+ }
+}
+
+/* Extend the local space of "dst" to include the divs
+ * in the local space of "src".
+ */
+__isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
+ __isl_keep isl_aff *src)
+{
+ isl_ctx *ctx;
+ int *exp1 = NULL;
+ int *exp2 = NULL;
+ isl_mat *div;
+
+ if (!src || !dst)
+ return isl_aff_free(dst);
+
+ ctx = isl_aff_get_ctx(src);
+ if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
+ isl_die(ctx, isl_error_invalid,
+ "spaces don't match", goto error);
+
+ if (src->ls->div->n_row == 0)
+ return dst;
+
+ exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
+ exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
+ if (!exp1 || !exp2)
+ goto error;
+
+ div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
+ dst = isl_aff_expand_divs(dst, div, exp2);
+ free(exp1);
+ free(exp2);
+
+ return dst;
+error:
+ free(exp1);
+ free(exp2);
+ return isl_aff_free(dst);
+}
+
+/* Adjust the local spaces of the affine expressions in "maff"
+ * such that they all have the save divs.
+ */
+__isl_give isl_multi_aff *isl_multi_aff_align_divs(
+ __isl_take isl_multi_aff *maff)
+{
+ int i;
+
+ if (!maff)
+ return NULL;
+ if (maff->n == 0)
+ return maff;
+ maff = isl_multi_aff_cow(maff);
+ if (!maff)
+ return NULL;
+
+ for (i = 1; i < maff->n; ++i)
+ maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
+ for (i = 1; i < maff->n; ++i) {
+ maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
+ if (!maff->p[i])
+ return isl_multi_aff_free(maff);
+ }
+
+ return maff;
+}
+
+__isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
+{
+ aff = isl_aff_cow(aff);
+ if (!aff)
+ return NULL;
+
+ aff->ls = isl_local_space_lift(aff->ls);
+ if (!aff->ls)
+ return isl_aff_free(aff);
+
+ return aff;
+}
+
+/* Lift "maff" to a space with extra dimensions such that the result
+ * has no more existentially quantified variables.
+ * If "ls" is not NULL, then *ls is assigned the local space that lies
+ * at the basis of the lifting applied to "maff".
+ */
+__isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
+ __isl_give isl_local_space **ls)
+{
+ int i;
+ isl_space *space;
+ unsigned n_div;
+
+ if (ls)
+ *ls = NULL;
+
+ if (!maff)
+ return NULL;
+
+ if (maff->n == 0) {
+ if (ls) {
+ isl_space *space = isl_multi_aff_get_domain_space(maff);
+ *ls = isl_local_space_from_space(space);
+ if (!*ls)
+ return isl_multi_aff_free(maff);
+ }
+ return maff;
+ }
+
+ maff = isl_multi_aff_cow(maff);
+ maff = isl_multi_aff_align_divs(maff);
+ if (!maff)
+ return NULL;
+
+ n_div = isl_aff_dim(maff->p[0], isl_dim_div);
+ space = isl_multi_aff_get_space(maff);
+ space = isl_space_lift(isl_space_domain(space), n_div);
+ space = isl_space_extend_domain_with_range(space,
+ isl_multi_aff_get_space(maff));
+ if (!space)
+ return isl_multi_aff_free(maff);
+ isl_space_free(maff->space);
+ maff->space = space;
+
+ if (ls) {
+ *ls = isl_aff_get_domain_local_space(maff->p[0]);
+ if (!*ls)
+ return isl_multi_aff_free(maff);
+ }
+
+ for (i = 0; i < maff->n; ++i) {
+ maff->p[i] = isl_aff_lift(maff->p[i]);
+ if (!maff->p[i])
+ goto error;
+ }
+
+ return maff;
+error:
+ if (ls)
+ isl_local_space_free(*ls);
+ return isl_multi_aff_free(maff);
+}
+
+
+/* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
+ */
+__isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
+ __isl_keep isl_pw_multi_aff *pma, int pos)
+{
+ int i;
+ int n_out;
+ isl_space *space;
+ isl_pw_aff *pa;
+
+ if (!pma)
+ return NULL;
+
+ n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
+ if (pos < 0 || pos >= n_out)
+ isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
+ "index out of bounds", return NULL);
+
+ space = isl_pw_multi_aff_get_space(pma);
+ space = isl_space_drop_dims(space, isl_dim_out,
+ pos + 1, n_out - pos - 1);
+ space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
+
+ pa = isl_pw_aff_alloc_size(space, pma->n);
+ for (i = 0; i < pma->n; ++i) {
+ isl_aff *aff;
+ aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
+ pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
+ }
+
+ return pa;
+}
+
+/* Return an isl_pw_multi_aff with the given "set" as domain and
+ * an unnamed zero-dimensional range.
+ */
+__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
+ __isl_take isl_set *set)
+{
+ isl_multi_aff *ma;
+ isl_space *space;
+
+ space = isl_set_get_space(set);
+ space = isl_space_from_domain(space);
+ ma = isl_multi_aff_zero(space);
+ return isl_pw_multi_aff_alloc(set, ma);
+}
+
+/* Add an isl_pw_multi_aff with the given "set" as domain and
+ * an unnamed zero-dimensional range to *user.
+ */
+static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
+{
+ isl_union_pw_multi_aff **upma = user;
+ isl_pw_multi_aff *pma;
+
+ pma = isl_pw_multi_aff_from_domain(set);
+ *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
+
+ return 0;
+}
+
+/* Return an isl_union_pw_multi_aff with the given "uset" as domain and
+ * an unnamed zero-dimensional range.
+ */
+__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
+ __isl_take isl_union_set *uset)
+{
+ isl_space *space;
+ isl_union_pw_multi_aff *upma;
+
+ if (!uset)
+ return NULL;
+
+ space = isl_union_set_get_space(uset);
+ upma = isl_union_pw_multi_aff_empty(space);
+
+ if (isl_union_set_foreach_set(uset,
+ &add_pw_multi_aff_from_domain, &upma) < 0)
+ goto error;
+
+ isl_union_set_free(uset);
+ return upma;
+error:
+ isl_union_set_free(uset);
+ isl_union_pw_multi_aff_free(upma);
+ return NULL;
+}
+
+/* Convert "pma" to an isl_map and add it to *umap.
+ */
+static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
+{
+ isl_union_map **umap = user;
+ isl_map *map;
+
+ map = isl_map_from_pw_multi_aff(pma);
+ *umap = isl_union_map_add_map(*umap, map);
+
+ return 0;
+}
+
+/* Construct a union map mapping the domain of the union
+ * piecewise multi-affine expression to its range, with each dimension
+ * in the range equated to the corresponding affine expression on its cell.
+ */
+__isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
+ __isl_take isl_union_pw_multi_aff *upma)
+{
+ isl_space *space;
+ isl_union_map *umap;
+
+ if (!upma)
+ return NULL;
+
+ space = isl_union_pw_multi_aff_get_space(upma);
+ umap = isl_union_map_empty(space);
+
+ if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
+ &map_from_pw_multi_aff, &umap) < 0)
+ goto error;
+
+ isl_union_pw_multi_aff_free(upma);
+ return umap;
+error:
+ isl_union_pw_multi_aff_free(upma);
+ isl_union_map_free(umap);
+ return NULL;
+}
+
+/* Local data for bin_entry and the callback "fn".
+ */
+struct isl_union_pw_multi_aff_bin_data {
+ isl_union_pw_multi_aff *upma2;
+ isl_union_pw_multi_aff *res;
+ isl_pw_multi_aff *pma;
+ int (*fn)(void **entry, void *user);
+};
+
+/* Given an isl_pw_multi_aff from upma1, store it in data->pma
+ * and call data->fn for each isl_pw_multi_aff in data->upma2.
+ */
+static int bin_entry(void **entry, void *user)
+{
+ struct isl_union_pw_multi_aff_bin_data *data = user;
+ isl_pw_multi_aff *pma = *entry;
+
+ data->pma = pma;
+ if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
+ data->fn, data) < 0)
+ return -1;
+
+ return 0;
+}
+
+/* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
+ * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
+ * passed as user field) and the isl_pw_multi_aff from upma2 is available
+ * as *entry. The callback should adjust data->res if desired.
+ */
+static __isl_give isl_union_pw_multi_aff *bin_op(
+ __isl_take isl_union_pw_multi_aff *upma1,
+ __isl_take isl_union_pw_multi_aff *upma2,
+ int (*fn)(void **entry, void *user))
+{
+ isl_space *space;
+ struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
+
+ space = isl_union_pw_multi_aff_get_space(upma2);
+ upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
+ space = isl_union_pw_multi_aff_get_space(upma1);
+ upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
+
+ if (!upma1 || !upma2)
+ goto error;
+
+ data.upma2 = upma2;
+ data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
+ upma1->table.n);
+ if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
+ &bin_entry, &data) < 0)
+ goto error;
+
+ isl_union_pw_multi_aff_free(upma1);
+ isl_union_pw_multi_aff_free(upma2);
+ return data.res;
+error:
+ isl_union_pw_multi_aff_free(upma1);
+ isl_union_pw_multi_aff_free(upma2);
+ isl_union_pw_multi_aff_free(data.res);
+ return NULL;
+}
+
+/* Given two aligned isl_pw_multi_affs A -> B and C -> D,
+ * construct an isl_pw_multi_aff (A * C) -> [B -> D].
+ */
+static __isl_give isl_pw_multi_aff *pw_multi_aff_range_product(
+ __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
+{
+ isl_space *space;
+
+ space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
+ isl_pw_multi_aff_get_space(pma2));
+ return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
+ &isl_multi_aff_range_product);
+}
+
+/* Given two isl_pw_multi_affs A -> B and C -> D,
+ * construct an isl_pw_multi_aff (A * C) -> [B -> D].
+ */
+__isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_product(
+ __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
+{
+ return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
+ &pw_multi_aff_range_product);
+}
+
+/* Given two aligned isl_pw_multi_affs A -> B and C -> D,
+ * construct an isl_pw_multi_aff (A * C) -> (B, D).
+ */
+static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
+ __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
+{
+ isl_space *space;
+
+ space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
+ isl_pw_multi_aff_get_space(pma2));
+ space = isl_space_flatten_range(space);
+ return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
+ &isl_multi_aff_flat_range_product);
+}
+
+/* Given two isl_pw_multi_affs A -> B and C -> D,
+ * construct an isl_pw_multi_aff (A * C) -> (B, D).
+ */
+__isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
+ __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
+{
+ return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
+ &pw_multi_aff_flat_range_product);
+}
+
+/* If data->pma and *entry have the same domain space, then compute
+ * their flat range product and the result to data->res.
+ */
+static int flat_range_product_entry(void **entry, void *user)
+{
+ struct isl_union_pw_multi_aff_bin_data *data = user;
+ isl_pw_multi_aff *pma2 = *entry;
+
+ if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
+ pma2->dim, isl_dim_in))
+ return 0;
+
+ pma2 = isl_pw_multi_aff_flat_range_product(
+ isl_pw_multi_aff_copy(data->pma),
+ isl_pw_multi_aff_copy(pma2));
+
+ data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
+
+ return 0;
+}
+
+/* Given two isl_union_pw_multi_affs A -> B and C -> D,
+ * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
+ */
+__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
+ __isl_take isl_union_pw_multi_aff *upma1,
+ __isl_take isl_union_pw_multi_aff *upma2)
+{
+ return bin_op(upma1, upma2, &flat_range_product_entry);
+}
+
+/* Replace the affine expressions at position "pos" in "pma" by "pa".
+ * The parameters are assumed to have been aligned.
+ *
+ * The implementation essentially performs an isl_pw_*_on_shared_domain,
+ * except that it works on two different isl_pw_* types.
+ */
+static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff(
+ __isl_take isl_pw_multi_aff *pma, unsigned pos,
+ __isl_take isl_pw_aff *pa)
+{
+ int i, j, n;
+ isl_pw_multi_aff *res = NULL;
+
+ if (!pma || !pa)
+ goto error;
+
+ if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in))
+ isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
+ "domains don't match", goto error);
+ if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out))
+ isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
+ "index out of bounds", goto error);
+
+ n = pma->n * pa->n;
+ res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n);
+
+ for (i = 0; i < pma->n; ++i) {
+ for (j = 0; j < pa->n; ++j) {
+ isl_set *common;
+ isl_multi_aff *res_ij;
+ int empty;
+
+ common = isl_set_intersect(isl_set_copy(pma->p[i].set),
+ isl_set_copy(pa->p[j].set));
+ empty = isl_set_plain_is_empty(common);
+ if (empty < 0 || empty) {
+ isl_set_free(common);
+ if (empty < 0)
+ goto error;
+ continue;
+ }
+
+ res_ij = isl_multi_aff_set_aff(
+ isl_multi_aff_copy(pma->p[i].maff), pos,
+ isl_aff_copy(pa->p[j].aff));
+ res_ij = isl_multi_aff_gist(res_ij,
+ isl_set_copy(common));
+
+ res = isl_pw_multi_aff_add_piece(res, common, res_ij);
+ }
+ }
+
+ isl_pw_multi_aff_free(pma);
+ isl_pw_aff_free(pa);
+ return res;
+error:
+ isl_pw_multi_aff_free(pma);
+ isl_pw_aff_free(pa);
+ return isl_pw_multi_aff_free(res);
+}
+
+/* Replace the affine expressions at position "pos" in "pma" by "pa".
+ */
+__isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff(
+ __isl_take isl_pw_multi_aff *pma, unsigned pos,
+ __isl_take isl_pw_aff *pa)
+{
+ if (!pma || !pa)
+ goto error;
+ if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param))
+ return pw_multi_aff_set_pw_aff(pma, pos, pa);
+ if (!isl_space_has_named_params(pma->dim) ||
+ !isl_space_has_named_params(pa->dim))
+ isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
+ "unaligned unnamed parameters", goto error);
+ pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa));
+ pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma));
+ return pw_multi_aff_set_pw_aff(pma, pos, pa);
+error:
+ isl_pw_multi_aff_free(pma);
+ isl_pw_aff_free(pa);
+ return NULL;
+}
+
+#undef BASE
+#define BASE pw_aff
+
+#include <isl_multi_templ.c>