+/* Replace all integer divisions [e/d] that turn out to not actually be integer
+ * divisions because d is equal to 1 by their definition, i.e., e.
+ */
+static __isl_give isl_qpolynomial *substitute_non_divs(
+ __isl_take isl_qpolynomial *qp)
+{
+ int i, j;
+ int total;
+ struct isl_upoly *s;
+
+ if (!qp)
+ return NULL;
+
+ total = isl_space_dim(qp->dim, isl_dim_all);
+ for (i = 0; qp && i < qp->div->n_row; ++i) {
+ if (!isl_int_is_one(qp->div->row[i][0]))
+ continue;
+ for (j = i + 1; j < qp->div->n_row; ++j) {
+ if (isl_int_is_zero(qp->div->row[j][2 + total + i]))
+ continue;
+ isl_seq_combine(qp->div->row[j] + 1,
+ qp->div->ctx->one, qp->div->row[j] + 1,
+ qp->div->row[j][2 + total + i],
+ qp->div->row[i] + 1, 1 + total + i);
+ isl_int_set_si(qp->div->row[j][2 + total + i], 0);
+ normalize_div(qp, j);
+ }
+ s = isl_upoly_from_affine(qp->dim->ctx, qp->div->row[i] + 1,
+ qp->div->row[i][0], qp->div->n_col - 1);
+ qp = substitute_div(qp, i, s);
+ --i;
+ }
+
+ return qp;
+}
+
+/* Reduce the coefficients of div "div" to lie in the interval [0, d-1],
+ * with d the denominator. When replacing the coefficient e of x by
+ * d * frac(e/d) = e - d * floor(e/d), we are subtracting d * floor(e/d) * x
+ * inside the division, so we need to add floor(e/d) * x outside.
+ * That is, we replace q by q' + floor(e/d) * x and we therefore need
+ * to adjust the coefficient of x in each later div that depends on the
+ * current div "div" and also in the affine expression "aff"
+ * (if it too depends on "div").
+ */
+static void reduce_div(__isl_keep isl_qpolynomial *qp, int div,
+ __isl_keep isl_vec *aff)
+{
+ int i, j;
+ isl_int v;
+ unsigned total = qp->div->n_col - qp->div->n_row - 2;
+
+ isl_int_init(v);
+ for (i = 0; i < 1 + total + div; ++i) {
+ if (isl_int_is_nonneg(qp->div->row[div][1 + i]) &&
+ isl_int_lt(qp->div->row[div][1 + i], qp->div->row[div][0]))
+ continue;
+ isl_int_fdiv_q(v, qp->div->row[div][1 + i], qp->div->row[div][0]);
+ isl_int_fdiv_r(qp->div->row[div][1 + i],
+ qp->div->row[div][1 + i], qp->div->row[div][0]);
+ if (!isl_int_is_zero(aff->el[1 + total + div]))
+ isl_int_addmul(aff->el[i], v, aff->el[1 + total + div]);
+ for (j = div + 1; j < qp->div->n_row; ++j) {
+ if (isl_int_is_zero(qp->div->row[j][2 + total + div]))
+ continue;
+ isl_int_addmul(qp->div->row[j][1 + i],
+ v, qp->div->row[j][2 + total + div]);
+ }
+ }
+ isl_int_clear(v);
+}
+
+/* Check if the last non-zero coefficient is bigger that half of the
+ * denominator. If so, we will invert the div to further reduce the number
+ * of distinct divs that may appear.
+ * If the last non-zero coefficient is exactly half the denominator,
+ * then we continue looking for earlier coefficients that are bigger
+ * than half the denominator.
+ */
+static int needs_invert(__isl_keep isl_mat *div, int row)