+
+/* 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_dim_total(r->dim) + 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(
+ __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_dim(qp, isl_dim_copy(r->dim));
+
+ isl_reordering_free(r);
+ return qp;
+error:
+ isl_qpolynomial_free(qp);
+ isl_reordering_free(r);
+ 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_dim *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_dim_total(dim);
+ bset = isl_basic_set_alloc_dim(isl_dim_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_dim_free(dim);
+ return isl_set_from_basic_set(bset);
+error:
+ isl_basic_set_free(bset);
+ isl_dim_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_dim(set), qp, div, v);
+ set = isl_set_intersect(set, slice);
+
+ if (!qp)
+ goto error;
+
+ total = isl_dim_total(qp->dim);
+
+ 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_dim_total(qp->dim);
+ 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_dim(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_dim *dim;
+ isl_qpolynomial *qp;
+
+ if (!bset)
+ return NULL;
+
+ bset = isl_basic_map_domain(isl_basic_map_from_range(bset));
+ dim = isl_basic_set_get_dim(bset);
+ if (cst < 0)
+ qp = isl_qpolynomial_infty(dim);
+ else if (cst == 0)
+ qp = isl_qpolynomial_zero(dim);
+ else
+ qp = isl_qpolynomial_one(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_dim *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)
+ goto error;
+ if (f->n_group == 0) {
+ isl_factorizer_free(f);
+ return fn(bset);
+ }
+
+ nparam = isl_basic_set_dim(bset, isl_dim_param);
+ nvar = isl_basic_set_dim(bset, isl_dim_set);
+
+ dim = isl_basic_set_get_dim(bset);
+ dim = isl_dim_domain(dim);
+ set = isl_set_universe(isl_dim_copy(dim));
+ qp = isl_qpolynomial_one(dim);
+ pwqp = isl_pw_qpolynomial_alloc(set, qp);
+
+ bset = isl_morph_basic_set(isl_morph_copy(f->morph), bset);
+
+ for (i = 0, n = 0; i < f->n_group; ++i) {
+ isl_basic_set *bset_i;
+ isl_pw_qpolynomial *pwqp_i;
+
+ bset_i = isl_basic_set_copy(bset);
+ bset_i = isl_basic_set_drop_constraints_involving(bset_i,
+ nparam + n + f->len[i], nvar - n - f->len[i]);
+ bset_i = isl_basic_set_drop_constraints_involving(bset_i,
+ nparam, n);
+ bset_i = isl_basic_set_drop(bset_i, isl_dim_set,
+ n + f->len[i], nvar - n - f->len[i]);
+ bset_i = isl_basic_set_drop(bset_i, isl_dim_set, 0, n);
+
+ pwqp_i = fn(bset_i);
+ pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp_i);
+
+ n += f->len[i];
+ }
+
+ isl_basic_set_free(bset);
+ isl_factorizer_free(f);
+
+ return pwqp;
+error:
+ isl_basic_set_free(bset);
+ return NULL;
+}
+
+/* Factor bset, call fn on each of the factors and return the product.
+ * The function is assumed to evaluate to zero on empty domains,
+ * to one on zero-dimensional domains and to infinity on unbounded domains
+ * and will not be called explicitly on zero-dimensional or unbounded domains.
+ *
+ * We first check for some special cases and remove all equalities.
+ * Then we hand over control to compressed_multiplicative_call.
+ */
+__isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call(
+ __isl_take isl_basic_set *bset,
+ __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset))
+{
+ int bounded;
+ isl_morph *morph;
+ isl_pw_qpolynomial *pwqp;
+ unsigned orig_nvar, final_nvar;
+
+ if (!bset)
+ return NULL;
+
+ if (isl_basic_set_fast_is_empty(bset))
+ return constant_on_domain(bset, 0);
+
+ orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
+
+ if (orig_nvar == 0)
+ return constant_on_domain(bset, 1);
+
+ bounded = isl_basic_set_is_bounded(bset);
+ if (bounded < 0)
+ goto error;
+ if (!bounded)
+ return constant_on_domain(bset, -1);
+
+ if (bset->n_eq == 0)
+ return compressed_multiplicative_call(bset, fn);
+
+ morph = isl_basic_set_full_compression(bset);
+ bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
+
+ final_nvar = isl_basic_set_dim(bset, isl_dim_set);
+
+ pwqp = compressed_multiplicative_call(bset, fn);
+
+ morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
+ morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
+ morph = isl_morph_inverse(morph);
+
+ pwqp = isl_pw_qpolynomial_morph(pwqp, morph);
+
+ return pwqp;
+error:
+ isl_basic_set_free(bset);
+ return NULL;
+}