+ if (!qp || !dim)
+ goto error;
+
+ if (isl_space_is_equal(qp->dim, dim)) {
+ isl_space_free(dim);
+ return qp;
+ }
+
+ qp = isl_qpolynomial_cow(qp);
+ if (!qp)
+ goto error;
+
+ extra = isl_space_dim(dim, isl_dim_set) -
+ isl_space_dim(qp->dim, isl_dim_set);
+ total = isl_space_dim(qp->dim, isl_dim_all);
+ if (qp->div->n_row) {
+ int *exp;
+
+ exp = isl_alloc_array(qp->div->ctx, int, qp->div->n_row);
+ if (!exp)
+ goto error;
+ for (i = 0; i < qp->div->n_row; ++i)
+ exp[i] = extra + i;
+ qp->upoly = expand(qp->upoly, exp, total);
+ free(exp);
+ if (!qp->upoly)
+ goto error;
+ }
+ qp->div = isl_mat_insert_cols(qp->div, 2 + total, extra);
+ if (!qp->div)
+ goto error;
+ for (i = 0; i < qp->div->n_row; ++i)
+ isl_seq_clr(qp->div->row[i] + 2 + total, extra);
+
+ isl_space_free(qp->dim);
+ qp->dim = dim;
+
+ return qp;
+error:
+ isl_space_free(dim);
+ isl_qpolynomial_free(qp);
+ return NULL;
+}
+
+/* For each parameter or variable that does not appear in qp,
+ * first eliminate the variable from all constraints and then set it to zero.
+ */
+static __isl_give isl_set *fix_inactive(__isl_take isl_set *set,
+ __isl_keep isl_qpolynomial *qp)
+{
+ int *active = NULL;
+ int i;
+ int d;
+ unsigned nparam;
+ unsigned nvar;
+
+ if (!set || !qp)
+ goto error;
+
+ d = isl_space_dim(set->dim, isl_dim_all);
+ active = isl_calloc_array(set->ctx, int, d);
+ if (set_active(qp, active) < 0)
+ goto error;
+
+ for (i = 0; i < d; ++i)
+ if (!active[i])
+ break;
+
+ if (i == d) {
+ free(active);
+ return set;
+ }
+
+ nparam = isl_space_dim(set->dim, isl_dim_param);
+ nvar = isl_space_dim(set->dim, isl_dim_set);
+ for (i = 0; i < nparam; ++i) {
+ if (active[i])
+ continue;
+ set = isl_set_eliminate(set, isl_dim_param, i, 1);
+ set = isl_set_fix_si(set, isl_dim_param, i, 0);
+ }
+ for (i = 0; i < nvar; ++i) {
+ if (active[nparam + i])
+ continue;
+ set = isl_set_eliminate(set, isl_dim_set, i, 1);
+ set = isl_set_fix_si(set, isl_dim_set, i, 0);
+ }
+
+ free(active);
+
+ return set;
+error:
+ free(active);
+ isl_set_free(set);
+ return NULL;
+}
+
+struct isl_opt_data {
+ isl_qpolynomial *qp;
+ int first;
+ isl_qpolynomial *opt;
+ int max;
+};
+
+static int opt_fn(__isl_take isl_point *pnt, void *user)
+{
+ struct isl_opt_data *data = (struct isl_opt_data *)user;
+ isl_qpolynomial *val;
+
+ val = isl_qpolynomial_eval(isl_qpolynomial_copy(data->qp), pnt);
+ if (data->first) {
+ data->first = 0;
+ data->opt = val;
+ } else if (data->max) {
+ data->opt = isl_qpolynomial_max_cst(data->opt, val);
+ } else {
+ data->opt = isl_qpolynomial_min_cst(data->opt, val);
+ }
+
+ return 0;
+}
+
+__isl_give isl_qpolynomial *isl_qpolynomial_opt_on_domain(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_set *set, int max)
+{
+ struct isl_opt_data data = { NULL, 1, NULL, max };
+
+ if (!set || !qp)
+ goto error;
+
+ if (isl_upoly_is_cst(qp->upoly)) {
+ isl_set_free(set);
+ return qp;
+ }
+
+ set = fix_inactive(set, qp);
+
+ data.qp = qp;
+ if (isl_set_foreach_point(set, opt_fn, &data) < 0)
+ goto error;
+
+ if (data.first) {
+ isl_space *space = isl_qpolynomial_get_domain_space(qp);
+ data.opt = isl_qpolynomial_zero_on_domain(space);
+ }
+
+ isl_set_free(set);
+ isl_qpolynomial_free(qp);
+ return data.opt;
+error:
+ isl_set_free(set);
+ isl_qpolynomial_free(qp);
+ isl_qpolynomial_free(data.opt);
+ return NULL;
+}
+
+__isl_give isl_qpolynomial *isl_qpolynomial_morph_domain(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_morph *morph)
+{
+ int i;
+ int n_sub;
+ isl_ctx *ctx;
+ struct isl_upoly **subs;
+ isl_mat *mat, *diag;
+
+ qp = isl_qpolynomial_cow(qp);
+ if (!qp || !morph)
+ goto error;
+
+ ctx = qp->dim->ctx;
+ isl_assert(ctx, isl_space_is_equal(qp->dim, morph->dom->dim), goto error);
+
+ n_sub = morph->inv->n_row - 1;
+ if (morph->inv->n_row != morph->inv->n_col)
+ n_sub += qp->div->n_row;
+ subs = isl_calloc_array(ctx, struct isl_upoly *, n_sub);
+ if (!subs)
+ goto error;
+
+ for (i = 0; 1 + i < morph->inv->n_row; ++i)
+ subs[i] = isl_upoly_from_affine(ctx, morph->inv->row[1 + i],
+ morph->inv->row[0][0], morph->inv->n_col);
+ if (morph->inv->n_row != morph->inv->n_col)
+ for (i = 0; i < qp->div->n_row; ++i)
+ subs[morph->inv->n_row - 1 + i] =
+ isl_upoly_var_pow(ctx, morph->inv->n_col - 1 + i, 1);
+
+ qp->upoly = isl_upoly_subs(qp->upoly, 0, n_sub, subs);
+
+ for (i = 0; i < n_sub; ++i)
+ isl_upoly_free(subs[i]);
+ free(subs);
+
+ diag = isl_mat_diag(ctx, 1, morph->inv->row[0][0]);
+ mat = isl_mat_diagonal(diag, isl_mat_copy(morph->inv));
+ diag = isl_mat_diag(ctx, qp->div->n_row, morph->inv->row[0][0]);
+ mat = isl_mat_diagonal(mat, diag);
+ qp->div = isl_mat_product(qp->div, mat);
+ isl_space_free(qp->dim);
+ qp->dim = isl_space_copy(morph->ran->dim);
+
+ if (!qp->upoly || !qp->div || !qp->dim)
+ goto error;
+
+ isl_morph_free(morph);
+
+ return qp;
+error:
+ isl_qpolynomial_free(qp);
+ isl_morph_free(morph);
+ return NULL;
+}
+
+static int neg_entry(void **entry, void *user)
+{
+ isl_pw_qpolynomial **pwqp = (isl_pw_qpolynomial **)entry;
+
+ *pwqp = isl_pw_qpolynomial_neg(*pwqp);
+
+ return *pwqp ? 0 : -1;
+}
+
+__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_neg(
+ __isl_take isl_union_pw_qpolynomial *upwqp)
+{
+ upwqp = isl_union_pw_qpolynomial_cow(upwqp);
+ if (!upwqp)
+ return NULL;
+
+ if (isl_hash_table_foreach(upwqp->dim->ctx, &upwqp->table,
+ &neg_entry, NULL) < 0)
+ goto error;
+
+ return upwqp;
+error:
+ isl_union_pw_qpolynomial_free(upwqp);
+ return NULL;
+}
+
+__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
+ __isl_take isl_union_pw_qpolynomial *upwqp1,
+ __isl_take isl_union_pw_qpolynomial *upwqp2)
+{
+ return match_bin_op(upwqp1, upwqp2, &isl_pw_qpolynomial_mul);
+}
+
+/* Reorder the columns of the given div definitions according to the
+ * given reordering.
+ */
+static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
+ __isl_take isl_reordering *r)
+{
+ int i, j;
+ isl_mat *mat;
+ int extra;
+
+ if (!div || !r)
+ goto error;
+
+ extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
+ mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
+ if (!mat)
+ goto error;
+
+ for (i = 0; i < div->n_row; ++i) {
+ isl_seq_cpy(mat->row[i], div->row[i], 2);
+ isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
+ for (j = 0; j < r->len; ++j)
+ isl_int_set(mat->row[i][2 + r->pos[j]],
+ div->row[i][2 + j]);
+ }
+
+ isl_reordering_free(r);
+ isl_mat_free(div);
+ return mat;
+error:
+ isl_reordering_free(r);
+ isl_mat_free(div);
+ return NULL;
+}
+
+/* Reorder the dimension of "qp" according to the given reordering.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r)
+{
+ qp = isl_qpolynomial_cow(qp);
+ if (!qp)
+ goto error;
+
+ r = isl_reordering_extend(r, qp->div->n_row);
+ if (!r)
+ goto error;
+
+ qp->div = reorder_divs(qp->div, isl_reordering_copy(r));
+ if (!qp->div)
+ goto error;
+
+ qp->upoly = reorder(qp->upoly, r->pos);
+ if (!qp->upoly)
+ goto error;
+
+ qp = isl_qpolynomial_reset_domain_space(qp, isl_space_copy(r->dim));
+
+ isl_reordering_free(r);
+ return qp;
+error:
+ isl_qpolynomial_free(qp);
+ isl_reordering_free(r);
+ return NULL;
+}
+
+__isl_give isl_qpolynomial *isl_qpolynomial_align_params(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_space *model)
+{
+ if (!qp || !model)
+ goto error;
+
+ if (!isl_space_match(qp->dim, isl_dim_param, model, isl_dim_param)) {
+ isl_reordering *exp;
+
+ model = isl_space_drop_dims(model, isl_dim_in,
+ 0, isl_space_dim(model, isl_dim_in));
+ model = isl_space_drop_dims(model, isl_dim_out,
+ 0, isl_space_dim(model, isl_dim_out));
+ exp = isl_parameter_alignment_reordering(qp->dim, model);
+ exp = isl_reordering_extend_space(exp,
+ isl_qpolynomial_get_domain_space(qp));
+ qp = isl_qpolynomial_realign_domain(qp, exp);
+ }
+
+ isl_space_free(model);
+ return qp;
+error:
+ isl_space_free(model);
+ isl_qpolynomial_free(qp);
+ return NULL;
+}
+
+struct isl_split_periods_data {
+ int max_periods;
+ isl_pw_qpolynomial *res;
+};
+
+/* Create a slice where the integer division "div" has the fixed value "v".
+ * In particular, if "div" refers to floor(f/m), then create a slice
+ *
+ * m v <= f <= m v + (m - 1)
+ *
+ * or
+ *
+ * f - m v >= 0
+ * -f + m v + (m - 1) >= 0
+ */
+static __isl_give isl_set *set_div_slice(__isl_take isl_space *dim,
+ __isl_keep isl_qpolynomial *qp, int div, isl_int v)
+{
+ int total;
+ isl_basic_set *bset = NULL;
+ int k;
+
+ if (!dim || !qp)
+ goto error;
+
+ total = isl_space_dim(dim, isl_dim_all);
+ bset = isl_basic_set_alloc_space(isl_space_copy(dim), 0, 0, 2);
+
+ k = isl_basic_set_alloc_inequality(bset);
+ if (k < 0)
+ goto error;
+ isl_seq_cpy(bset->ineq[k], qp->div->row[div] + 1, 1 + total);
+ isl_int_submul(bset->ineq[k][0], v, qp->div->row[div][0]);
+
+ k = isl_basic_set_alloc_inequality(bset);
+ if (k < 0)
+ goto error;
+ isl_seq_neg(bset->ineq[k], qp->div->row[div] + 1, 1 + total);
+ isl_int_addmul(bset->ineq[k][0], v, qp->div->row[div][0]);
+ isl_int_add(bset->ineq[k][0], bset->ineq[k][0], qp->div->row[div][0]);
+ isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
+
+ isl_space_free(dim);
+ return isl_set_from_basic_set(bset);
+error:
+ isl_basic_set_free(bset);
+ isl_space_free(dim);
+ return NULL;
+}
+
+static int split_periods(__isl_take isl_set *set,
+ __isl_take isl_qpolynomial *qp, void *user);
+
+/* Create a slice of the domain "set" such that integer division "div"
+ * has the fixed value "v" and add the results to data->res,
+ * replacing the integer division by "v" in "qp".
+ */
+static int set_div(__isl_take isl_set *set,
+ __isl_take isl_qpolynomial *qp, int div, isl_int v,
+ struct isl_split_periods_data *data)
+{
+ int i;
+ int total;
+ isl_set *slice;
+ struct isl_upoly *cst;
+
+ slice = set_div_slice(isl_set_get_space(set), qp, div, v);
+ set = isl_set_intersect(set, slice);
+
+ if (!qp)
+ goto error;
+
+ total = isl_space_dim(qp->dim, isl_dim_all);
+
+ for (i = div + 1; i < qp->div->n_row; ++i) {
+ if (isl_int_is_zero(qp->div->row[i][2 + total + div]))
+ continue;
+ isl_int_addmul(qp->div->row[i][1],
+ qp->div->row[i][2 + total + div], v);
+ isl_int_set_si(qp->div->row[i][2 + total + div], 0);
+ }
+
+ cst = isl_upoly_rat_cst(qp->dim->ctx, v, qp->dim->ctx->one);
+ qp = substitute_div(qp, div, cst);
+
+ return split_periods(set, qp, data);
+error:
+ isl_set_free(set);
+ isl_qpolynomial_free(qp);
+ return -1;
+}
+
+/* Split the domain "set" such that integer division "div"
+ * has a fixed value (ranging from "min" to "max") on each slice
+ * and add the results to data->res.
+ */
+static int split_div(__isl_take isl_set *set,
+ __isl_take isl_qpolynomial *qp, int div, isl_int min, isl_int max,
+ struct isl_split_periods_data *data)
+{
+ for (; isl_int_le(min, max); isl_int_add_ui(min, min, 1)) {
+ isl_set *set_i = isl_set_copy(set);
+ isl_qpolynomial *qp_i = isl_qpolynomial_copy(qp);
+
+ if (set_div(set_i, qp_i, div, min, data) < 0)
+ goto error;
+ }
+ isl_set_free(set);
+ isl_qpolynomial_free(qp);
+ return 0;
+error:
+ isl_set_free(set);
+ isl_qpolynomial_free(qp);
+ return -1;
+}
+
+/* If "qp" refers to any integer division
+ * that can only attain "max_periods" distinct values on "set"
+ * then split the domain along those distinct values.
+ * Add the results (or the original if no splitting occurs)
+ * to data->res.
+ */
+static int split_periods(__isl_take isl_set *set,
+ __isl_take isl_qpolynomial *qp, void *user)
+{
+ int i;
+ isl_pw_qpolynomial *pwqp;
+ struct isl_split_periods_data *data;
+ isl_int min, max;
+ int total;
+ int r = 0;
+
+ data = (struct isl_split_periods_data *)user;
+
+ if (!set || !qp)
+ goto error;
+
+ if (qp->div->n_row == 0) {
+ pwqp = isl_pw_qpolynomial_alloc(set, qp);
+ data->res = isl_pw_qpolynomial_add_disjoint(data->res, pwqp);
+ return 0;
+ }
+
+ isl_int_init(min);
+ isl_int_init(max);
+ total = isl_space_dim(qp->dim, isl_dim_all);
+ for (i = 0; i < qp->div->n_row; ++i) {
+ enum isl_lp_result lp_res;
+
+ if (isl_seq_first_non_zero(qp->div->row[i] + 2 + total,
+ qp->div->n_row) != -1)
+ continue;
+
+ lp_res = isl_set_solve_lp(set, 0, qp->div->row[i] + 1,
+ set->ctx->one, &min, NULL, NULL);
+ if (lp_res == isl_lp_error)
+ goto error2;
+ if (lp_res == isl_lp_unbounded || lp_res == isl_lp_empty)
+ continue;
+ isl_int_fdiv_q(min, min, qp->div->row[i][0]);
+
+ lp_res = isl_set_solve_lp(set, 1, qp->div->row[i] + 1,
+ set->ctx->one, &max, NULL, NULL);
+ if (lp_res == isl_lp_error)
+ goto error2;
+ if (lp_res == isl_lp_unbounded || lp_res == isl_lp_empty)
+ continue;
+ isl_int_fdiv_q(max, max, qp->div->row[i][0]);
+
+ isl_int_sub(max, max, min);
+ if (isl_int_cmp_si(max, data->max_periods) < 0) {
+ isl_int_add(max, max, min);
+ break;
+ }
+ }
+
+ if (i < qp->div->n_row) {
+ r = split_div(set, qp, i, min, max, data);
+ } else {
+ pwqp = isl_pw_qpolynomial_alloc(set, qp);
+ data->res = isl_pw_qpolynomial_add_disjoint(data->res, pwqp);
+ }
+
+ isl_int_clear(max);
+ isl_int_clear(min);
+
+ return r;
+error2:
+ isl_int_clear(max);
+ isl_int_clear(min);
+error:
+ isl_set_free(set);
+ isl_qpolynomial_free(qp);
+ return -1;
+}
+
+/* If any quasi-polynomial in pwqp refers to any integer division
+ * that can only attain "max_periods" distinct values on its domain
+ * then split the domain along those distinct values.
+ */
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_split_periods(
+ __isl_take isl_pw_qpolynomial *pwqp, int max_periods)
+{
+ struct isl_split_periods_data data;
+
+ data.max_periods = max_periods;
+ data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
+
+ if (isl_pw_qpolynomial_foreach_piece(pwqp, &split_periods, &data) < 0)
+ goto error;
+
+ isl_pw_qpolynomial_free(pwqp);
+
+ return data.res;
+error:
+ isl_pw_qpolynomial_free(data.res);
+ isl_pw_qpolynomial_free(pwqp);
+ return NULL;
+}
+
+/* Construct a piecewise quasipolynomial that is constant on the given
+ * domain. In particular, it is
+ * 0 if cst == 0
+ * 1 if cst == 1
+ * infinity if cst == -1
+ */
+static __isl_give isl_pw_qpolynomial *constant_on_domain(
+ __isl_take isl_basic_set *bset, int cst)
+{
+ isl_space *dim;
+ isl_qpolynomial *qp;
+
+ if (!bset)
+ return NULL;
+
+ bset = isl_basic_set_params(bset);
+ dim = isl_basic_set_get_space(bset);
+ if (cst < 0)
+ qp = isl_qpolynomial_infty_on_domain(dim);
+ else if (cst == 0)
+ qp = isl_qpolynomial_zero_on_domain(dim);
+ else
+ qp = isl_qpolynomial_one_on_domain(dim);
+ return isl_pw_qpolynomial_alloc(isl_set_from_basic_set(bset), qp);
+}
+
+/* Factor bset, call fn on each of the factors and return the product.
+ *
+ * If no factors can be found, simply call fn on the input.
+ * Otherwise, construct the factors based on the factorizer,
+ * call fn on each factor and compute the product.
+ */
+static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call(
+ __isl_take isl_basic_set *bset,
+ __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset))
+{
+ int i, n;
+ isl_space *dim;
+ isl_set *set;
+ isl_factorizer *f;
+ isl_qpolynomial *qp;
+ isl_pw_qpolynomial *pwqp;
+ unsigned nparam;
+ unsigned nvar;
+
+ f = isl_basic_set_factorizer(bset);
+ if (!f)