+/* 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);
+ }
+}
+
+/* Compute the pullback of "aff" by the function represented by "ma".
+ * In other words, plug in "ma" in "aff". The result is an affine expression
+ * defined over the domain space of "ma".
+ *
+ * If "aff" is represented by
+ *
+ * (a(p) + b x + c(divs))/d
+ *
+ * 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))/d
+ *
+ * The divs in the local space of the input are similarly adjusted
+ * through a call to isl_local_space_preimage_multi_aff.
+ */
+__isl_give isl_aff *isl_aff_pullback_multi_aff(__isl_take isl_aff *aff,
+ __isl_take isl_multi_aff *ma)
+{
+ isl_aff *res = NULL;
+ isl_local_space *ls;
+ int n_div_aff, n_div_ma;
+ isl_int f, c1, c2, g;
+
+ ma = isl_multi_aff_align_divs(ma);
+ if (!aff || !ma)
+ goto error;
+
+ n_div_aff = isl_aff_dim(aff, isl_dim_div);
+ n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
+
+ ls = isl_aff_get_domain_local_space(aff);
+ ls = isl_local_space_preimage_multi_aff(ls, isl_multi_aff_copy(ma));
+ res = isl_aff_alloc(ls);
+ if (!res)
+ goto error;
+
+ isl_int_init(f);
+ isl_int_init(c1);
+ isl_int_init(c2);
+ isl_int_init(g);
+
+ isl_seq_preimage(res->v->el, aff->v->el, ma, n_div_ma, n_div_aff,
+ f, c1, c2, g, 1);
+
+ isl_int_clear(f);
+ isl_int_clear(c1);
+ isl_int_clear(c2);
+ isl_int_clear(g);
+
+ isl_aff_free(aff);
+ isl_multi_aff_free(ma);
+ res = isl_aff_normalize(res);
+ return res;
+error:
+ isl_aff_free(aff);
+ isl_multi_aff_free(ma);
+ isl_aff_free(res);
+ return NULL;
+}
+
+/* Compute the pullback of "ma1" by the function represented by "ma2".
+ * In other words, plug in "ma2" in "ma1".
+ */
+__isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff(
+ __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
+{
+ int i;
+ isl_space *space = NULL;
+
+ ma2 = isl_multi_aff_align_divs(ma2);
+ ma1 = isl_multi_aff_cow(ma1);
+ if (!ma1 || !ma2)
+ goto error;
+
+ space = isl_space_join(isl_multi_aff_get_space(ma2),
+ isl_multi_aff_get_space(ma1));
+
+ for (i = 0; i < ma1->n; ++i) {
+ ma1->p[i] = isl_aff_pullback_multi_aff(ma1->p[i],
+ isl_multi_aff_copy(ma2));
+ if (!ma1->p[i])
+ goto error;
+ }
+
+ ma1 = isl_multi_aff_reset_space(ma1, space);
+ isl_multi_aff_free(ma2);
+ return ma1;
+error:
+ isl_space_free(space);
+ isl_multi_aff_free(ma2);
+ isl_multi_aff_free(ma1);
+ return NULL;
+}
+