+/* Project the domain of the quasi-polynomial onto its parameter space.
+ * The quasi-polynomial may not involve any of the domain dimensions.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_project_domain_on_params(
+ __isl_take isl_qpolynomial *qp)
+{
+ isl_space *space;
+ unsigned n;
+ int involves;
+
+ n = isl_qpolynomial_dim(qp, isl_dim_in);
+ involves = isl_qpolynomial_involves_dims(qp, isl_dim_in, 0, n);
+ if (involves < 0)
+ return isl_qpolynomial_free(qp);
+ if (involves)
+ isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,
+ "polynomial involves some of the domain dimensions",
+ return isl_qpolynomial_free(qp));
+ qp = isl_qpolynomial_drop_dims(qp, isl_dim_in, 0, n);
+ space = isl_qpolynomial_get_domain_space(qp);
+ space = isl_space_params(space);
+ qp = isl_qpolynomial_reset_domain_space(qp, space);
+ return qp;
+}
+
+static __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities_lifted(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq)
+{
+ int i, j, k;
+ isl_int denom;
+ unsigned total;
+ unsigned n_div;
+ struct isl_upoly *up;
+
+ if (!eq)
+ goto error;
+ if (eq->n_eq == 0) {
+ isl_basic_set_free(eq);
+ return qp;
+ }
+
+ qp = isl_qpolynomial_cow(qp);
+ if (!qp)
+ goto error;
+ qp->div = isl_mat_cow(qp->div);
+ if (!qp->div)
+ goto error;
+
+ total = 1 + isl_space_dim(eq->dim, isl_dim_all);
+ n_div = eq->n_div;
+ isl_int_init(denom);
+ for (i = 0; i < eq->n_eq; ++i) {
+ j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
+ if (j < 0 || j == 0 || j >= total)
+ continue;
+
+ for (k = 0; k < qp->div->n_row; ++k) {
+ if (isl_int_is_zero(qp->div->row[k][1 + j]))
+ continue;
+ isl_seq_elim(qp->div->row[k] + 1, eq->eq[i], j, total,
+ &qp->div->row[k][0]);
+ normalize_div(qp, k);
+ }
+
+ if (isl_int_is_pos(eq->eq[i][j]))
+ isl_seq_neg(eq->eq[i], eq->eq[i], total);
+ isl_int_abs(denom, eq->eq[i][j]);
+ isl_int_set_si(eq->eq[i][j], 0);
+
+ up = isl_upoly_from_affine(qp->dim->ctx,
+ eq->eq[i], denom, total);
+ qp->upoly = isl_upoly_subs(qp->upoly, j - 1, 1, &up);
+ isl_upoly_free(up);
+ }
+ isl_int_clear(denom);
+
+ if (!qp->upoly)
+ goto error;
+
+ isl_basic_set_free(eq);
+
+ qp = substitute_non_divs(qp);
+ qp = sort_divs(qp);
+
+ return qp;
+error:
+ isl_basic_set_free(eq);
+ isl_qpolynomial_free(qp);
+ return NULL;
+}
+
+/* Exploit the equalities in "eq" to simplify the quasi-polynomial.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq)
+{
+ if (!qp || !eq)
+ goto error;
+ if (qp->div->n_row > 0)
+ eq = isl_basic_set_add_dims(eq, isl_dim_set, qp->div->n_row);
+ return isl_qpolynomial_substitute_equalities_lifted(qp, eq);
+error:
+ isl_basic_set_free(eq);
+ isl_qpolynomial_free(qp);
+ return NULL;
+}
+
+static __isl_give isl_basic_set *add_div_constraints(
+ __isl_take isl_basic_set *bset, __isl_take isl_mat *div)
+{
+ int i;
+ unsigned total;
+
+ if (!bset || !div)
+ goto error;
+
+ bset = isl_basic_set_extend_constraints(bset, 0, 2 * div->n_row);
+ if (!bset)
+ goto error;
+ total = isl_basic_set_total_dim(bset);
+ for (i = 0; i < div->n_row; ++i)
+ if (isl_basic_set_add_div_constraints_var(bset,
+ total - div->n_row + i, div->row[i]) < 0)
+ goto error;
+
+ isl_mat_free(div);
+ return bset;
+error:
+ isl_mat_free(div);
+ isl_basic_set_free(bset);
+ return NULL;
+}
+
+/* Look for equalities among the variables shared by context and qp
+ * and the integer divisions of qp, if any.
+ * The equalities are then used to eliminate variables and/or integer
+ * divisions from qp.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_gist(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_set *context)
+{
+ isl_basic_set *aff;
+
+ if (!qp)
+ goto error;
+ if (qp->div->n_row > 0) {
+ isl_basic_set *bset;
+ context = isl_set_add_dims(context, isl_dim_set,
+ qp->div->n_row);
+ bset = isl_basic_set_universe(isl_set_get_space(context));
+ bset = add_div_constraints(bset, isl_mat_copy(qp->div));
+ context = isl_set_intersect(context,
+ isl_set_from_basic_set(bset));
+ }
+
+ aff = isl_set_affine_hull(context);
+ return isl_qpolynomial_substitute_equalities_lifted(qp, aff);
+error:
+ isl_qpolynomial_free(qp);
+ isl_set_free(context);
+ return NULL;
+}
+
+__isl_give isl_qpolynomial *isl_qpolynomial_gist_params(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_set *context)
+{
+ isl_space *space = isl_qpolynomial_get_domain_space(qp);
+ isl_set *dom_context = isl_set_universe(space);
+ dom_context = isl_set_intersect_params(dom_context, context);
+ return isl_qpolynomial_gist(qp, dom_context);
+}
+
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
+ __isl_take isl_qpolynomial *qp)
+{
+ isl_set *dom;
+
+ if (!qp)
+ return NULL;
+ if (isl_qpolynomial_is_zero(qp)) {
+ isl_space *dim = isl_qpolynomial_get_space(qp);
+ isl_qpolynomial_free(qp);
+ return isl_pw_qpolynomial_zero(dim);
+ }
+
+ dom = isl_set_universe(isl_qpolynomial_get_domain_space(qp));
+ return isl_pw_qpolynomial_alloc(dom, qp);
+}
+