*/
#include <stdlib.h>
+#include <isl_ctx_private.h>
+#include <isl_map_private.h>
#include <isl_factorization.h>
#include <isl/lp.h>
#include <isl/seq.h>
#include <isl_polynomial_private.h>
#include <isl_point_private.h>
#include <isl_dim_private.h>
-#include <isl_map_private.h>
+#include <isl_div_private.h>
#include <isl_mat_private.h>
#include <isl_range.h>
+#include <isl_local_space_private.h>
+#include <isl_aff_private.h>
+#include <isl_config.h>
static unsigned pos(__isl_keep isl_dim *dim, enum isl_dim_type type)
{
isl_assert(ctx, size >= 0, return NULL);
rec = isl_calloc(ctx, struct isl_upoly_rec,
sizeof(struct isl_upoly_rec) +
- (size - 1) * sizeof(struct isl_upoly *));
+ size * sizeof(struct isl_upoly *));
if (!rec)
return NULL;
__isl_give struct isl_upoly *isl_upoly_dup(__isl_keep struct isl_upoly *up)
{
- struct isl_upoly *dup;
-
if (!up)
return NULL;
{
struct isl_upoly_rec *rec1;
struct isl_upoly_rec *rec2;
- struct isl_upoly_rec *res;
+ struct isl_upoly_rec *res = NULL;
int i, j;
int size;
__isl_give struct isl_upoly *isl_upoly_var_pow(isl_ctx *ctx, int pos, int power)
{
int i;
- struct isl_upoly *up;
struct isl_upoly_rec *rec;
struct isl_upoly_cst *cst;
return equal;
}
-static void expand_row(__isl_keep isl_mat *dst, int d,
- __isl_keep isl_mat *src, int s, int *exp)
-{
- int i;
- unsigned c = src->n_col - src->n_row;
-
- isl_seq_cpy(dst->row[d], src->row[s], c);
- isl_seq_clr(dst->row[d] + c, dst->n_col - c);
-
- for (i = 0; i < s; ++i)
- isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
-}
-
static int cmp_row(__isl_keep isl_mat *div, int i, int j)
{
int li, lj;
return NULL;
}
-static __isl_give isl_mat *merge_divs(__isl_keep isl_mat *div1,
- __isl_keep isl_mat *div2, int *exp1, int *exp2)
-{
- int i, j, k;
- isl_mat *div = NULL;
- unsigned d = div1->n_col - div1->n_row;
-
- div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
- d + div1->n_row + div2->n_row);
- if (!div)
- return NULL;
-
- for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
- int cmp;
-
- expand_row(div, k, div1, i, exp1);
- expand_row(div, k + 1, div2, j, exp2);
-
- cmp = cmp_row(div, k, k + 1);
- if (cmp == 0) {
- exp1[i++] = k;
- exp2[j++] = k;
- } else if (cmp < 0) {
- exp1[i++] = k;
- } else {
- exp2[j++] = k;
- isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
- }
- }
- for (; i < div1->n_row; ++i, ++k) {
- expand_row(div, k, div1, i, exp1);
- exp1[i] = k;
- }
- for (; j < div2->n_row; ++j, ++k) {
- expand_row(div, k, div2, j, exp2);
- exp2[j] = k;
- }
-
- div->n_row = k;
- div->n_col = d + k;
-
- return div;
-}
-
static __isl_give struct isl_upoly *expand(__isl_take struct isl_upoly *up,
int *exp, int first)
{
if (!exp1 || !exp2)
goto error;
- div = merge_divs(qp1->div, qp2->div, exp1, exp2);
+ div = isl_merge_divs(qp1->div, qp2->div, exp1, exp2);
if (!div)
goto error;
__isl_give isl_qpolynomial *isl_qpolynomial_zero(__isl_take isl_dim *dim)
{
+ if (!dim)
+ return NULL;
return isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
}
__isl_give isl_qpolynomial *isl_qpolynomial_one(__isl_take isl_dim *dim)
{
+ if (!dim)
+ return NULL;
return isl_qpolynomial_alloc(dim, 0, isl_upoly_one(dim->ctx));
}
__isl_give isl_qpolynomial *isl_qpolynomial_infty(__isl_take isl_dim *dim)
{
+ if (!dim)
+ return NULL;
return isl_qpolynomial_alloc(dim, 0, isl_upoly_infty(dim->ctx));
}
__isl_give isl_qpolynomial *isl_qpolynomial_neginfty(__isl_take isl_dim *dim)
{
+ if (!dim)
+ return NULL;
return isl_qpolynomial_alloc(dim, 0, isl_upoly_neginfty(dim->ctx));
}
__isl_give isl_qpolynomial *isl_qpolynomial_nan(__isl_take isl_dim *dim)
{
+ if (!dim)
+ return NULL;
return isl_qpolynomial_alloc(dim, 0, isl_upoly_nan(dim->ctx));
}
struct isl_qpolynomial *qp;
struct isl_upoly_cst *cst;
+ if (!dim)
+ return NULL;
+
qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
if (!qp)
return NULL;
if (!qp)
return NULL;
- isl_assert(qp->div->ctx, qp->div->n_row == 0, return NULL);
d = isl_dim_total(qp->dim);
- aff = isl_vec_alloc(qp->div->ctx, 2 + d);
+ aff = isl_vec_alloc(qp->div->ctx, 2 + d + qp->div->n_row);
if (!aff)
return NULL;
- isl_seq_clr(aff->el + 1, 1 + d);
+ isl_seq_clr(aff->el + 1, 1 + d + qp->div->n_row);
isl_int_set_si(aff->el[0], 1);
if (isl_upoly_update_affine(qp->upoly, aff) < 0)
*
* After the reduction, some divs may have become redundant or identical,
* so we call substitute_non_divs and sort_divs. If these functions
- * eliminate divs of merge * two or more divs into one, the coefficients
+ * eliminate divs or merge two or more divs into one, the coefficients
* of the enclosing divs may have to be reduced again, so we call
* ourselves recursively if the number of divs decreases.
*/
static __isl_give isl_qpolynomial *reduce_divs(__isl_take isl_qpolynomial *qp)
{
- int i, j;
+ int i;
isl_vec *aff = NULL;
struct isl_upoly *s;
unsigned n_div;
isl_assert(qp->dim->ctx, type == isl_dim_param ||
type == isl_dim_set, return -1);
- active = isl_calloc_array(set->ctx, int, isl_dim_total(qp->dim));
+ active = isl_calloc_array(qp->dim->ctx, int, isl_dim_total(qp->dim));
if (set_active(qp, active) < 0)
goto error;
return -1;
}
+/* Remove divs that do not appear in the quasi-polynomial, nor in any
+ * of the divs that do appear in the quasi-polynomial.
+ */
+static __isl_give isl_qpolynomial *remove_redundant_divs(
+ __isl_take isl_qpolynomial *qp)
+{
+ int i, j;
+ int d;
+ int len;
+ int skip;
+ int *active = NULL;
+ int *reordering = NULL;
+ int redundant = 0;
+ int n_div;
+ isl_ctx *ctx;
+
+ if (!qp)
+ return NULL;
+ if (qp->div->n_row == 0)
+ return qp;
+
+ d = isl_dim_total(qp->dim);
+ len = qp->div->n_col - 2;
+ ctx = isl_qpolynomial_get_ctx(qp);
+ active = isl_calloc_array(ctx, int, len);
+ if (!active)
+ goto error;
+
+ if (up_set_active(qp->upoly, active, len) < 0)
+ goto error;
+
+ for (i = qp->div->n_row - 1; i >= 0; --i) {
+ if (!active[d + i]) {
+ redundant = 1;
+ continue;
+ }
+ for (j = 0; j < i; ++j) {
+ if (isl_int_is_zero(qp->div->row[i][2 + d + j]))
+ continue;
+ active[d + j] = 1;
+ break;
+ }
+ }
+
+ if (!redundant) {
+ free(active);
+ return qp;
+ }
+
+ reordering = isl_alloc_array(qp->div->ctx, int, len);
+ if (!reordering)
+ goto error;
+
+ for (i = 0; i < d; ++i)
+ reordering[i] = i;
+
+ skip = 0;
+ n_div = qp->div->n_row;
+ for (i = 0; i < n_div; ++i) {
+ if (!active[d + i]) {
+ qp->div = isl_mat_drop_rows(qp->div, i - skip, 1);
+ qp->div = isl_mat_drop_cols(qp->div,
+ 2 + d + i - skip, 1);
+ skip++;
+ }
+ reordering[d + i] = d + i - skip;
+ }
+
+ qp->upoly = reorder(qp->upoly, reordering);
+
+ if (!qp->upoly || !qp->div)
+ goto error;
+
+ free(active);
+ free(reordering);
+
+ return qp;
+error:
+ free(active);
+ free(reordering);
+ isl_qpolynomial_free(qp);
+ return NULL;
+}
+
__isl_give struct isl_upoly *isl_upoly_drop(__isl_take struct isl_upoly *up,
unsigned first, unsigned n)
{
if (pwqp->n != -1)
return 0;
- if (!isl_set_fast_is_universe(pwqp->p[0].set))
+ if (!isl_set_plain_is_universe(pwqp->p[0].set))
return 0;
return isl_qpolynomial_is_one(pwqp->p[0].qp);
{
int i, j, n;
struct isl_pw_qpolynomial *res;
- isl_set *set;
if (!pwqp1 || !pwqp2)
goto error;
struct isl_qpolynomial *prod;
common = isl_set_intersect(isl_set_copy(pwqp1->p[i].set),
isl_set_copy(pwqp2->p[j].set));
- if (isl_set_fast_is_empty(common)) {
+ if (isl_set_plain_is_empty(common)) {
isl_set_free(common);
continue;
}
return isl_qpolynomial_alloc(dim, 0, up);
}
+__isl_give isl_qpolynomial *isl_qpolynomial_from_aff(__isl_take isl_aff *aff)
+{
+ isl_ctx *ctx;
+ struct isl_upoly *up;
+ isl_qpolynomial *qp;
+
+ if (!aff)
+ return NULL;
+
+ ctx = isl_aff_get_ctx(aff);
+ up = isl_upoly_from_affine(ctx, aff->v->el + 1, aff->v->el[0],
+ aff->v->size - 1);
+
+ qp = isl_qpolynomial_alloc(isl_aff_get_dim(aff),
+ aff->ls->div->n_row, up);
+ if (!qp)
+ goto error;
+
+ isl_mat_free(qp->div);
+ qp->div = isl_mat_copy(aff->ls->div);
+ qp->div = isl_mat_cow(qp->div);
+ if (!qp->div)
+ goto error;
+
+ isl_aff_free(aff);
+ qp = reduce_divs(qp);
+ qp = remove_redundant_divs(qp);
+ return qp;
+error:
+ isl_aff_free(aff);
+ return NULL;
+}
+
__isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
__isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
{
int i;
int n_sub;
isl_ctx *ctx;
- struct isl_upoly *up;
- unsigned n_div;
struct isl_upoly **subs;
isl_mat *mat;
return NULL;
}
+__isl_give isl_qpolynomial *isl_qpolynomial_align_params(
+ __isl_take isl_qpolynomial *qp, __isl_take isl_dim *model)
+{
+ if (!qp || !model)
+ goto error;
+
+ if (!isl_dim_match(qp->dim, isl_dim_param, model, isl_dim_param)) {
+ isl_reordering *exp;
+
+ model = isl_dim_drop(model, isl_dim_in,
+ 0, isl_dim_size(model, isl_dim_in));
+ model = isl_dim_drop(model, isl_dim_out,
+ 0, isl_dim_size(model, isl_dim_out));
+ exp = isl_parameter_alignment_reordering(qp->dim, model);
+ exp = isl_reordering_extend_dim(exp,
+ isl_qpolynomial_get_dim(qp));
+ qp = isl_qpolynomial_realign(qp, exp);
+ }
+
+ isl_dim_free(model);
+ return qp;
+error:
+ isl_dim_free(model);
+ isl_qpolynomial_free(qp);
+ return NULL;
+}
+
struct isl_split_periods_data {
int max_periods;
isl_pw_qpolynomial *res;
if (!bset)
return NULL;
- if (isl_basic_set_fast_is_empty(bset))
+ if (isl_basic_set_plain_is_empty(bset))
return constant_on_domain(bset, 0);
orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
isl_union_pw_qpolynomial_free(upwqp);
return NULL;
}
+
+__isl_give isl_basic_map *isl_basic_map_from_qpolynomial(
+ __isl_take isl_qpolynomial *qp)
+{
+ int i, k;
+ isl_dim *dim;
+ isl_vec *aff = NULL;
+ isl_basic_map *bmap = NULL;
+ unsigned pos;
+ unsigned n_div;
+
+ if (!qp)
+ return NULL;
+ if (!isl_upoly_is_affine(qp->upoly))
+ isl_die(qp->dim->ctx, isl_error_invalid,
+ "input quasi-polynomial not affine", goto error);
+ aff = isl_qpolynomial_extract_affine(qp);
+ if (!aff)
+ goto error;
+ dim = isl_qpolynomial_get_dim(qp);
+ dim = isl_dim_from_domain(dim);
+ pos = 1 + isl_dim_offset(dim, isl_dim_out);
+ dim = isl_dim_add(dim, isl_dim_out, 1);
+ n_div = qp->div->n_row;
+ bmap = isl_basic_map_alloc_dim(dim, n_div, 1, 2 * n_div);
+
+ for (i = 0; i < n_div; ++i) {
+ k = isl_basic_map_alloc_div(bmap);
+ if (k < 0)
+ goto error;
+ isl_seq_cpy(bmap->div[k], qp->div->row[i], qp->div->n_col);
+ isl_int_set_si(bmap->div[k][qp->div->n_col], 0);
+ if (isl_basic_map_add_div_constraints(bmap, k) < 0)
+ goto error;
+ }
+ k = isl_basic_map_alloc_equality(bmap);
+ if (k < 0)
+ goto error;
+ isl_int_neg(bmap->eq[k][pos], aff->el[0]);
+ isl_seq_cpy(bmap->eq[k], aff->el + 1, pos);
+ isl_seq_cpy(bmap->eq[k] + pos + 1, aff->el + 1 + pos, n_div);
+
+ isl_vec_free(aff);
+ isl_qpolynomial_free(qp);
+ bmap = isl_basic_map_finalize(bmap);
+ return bmap;
+error:
+ isl_vec_free(aff);
+ isl_qpolynomial_free(qp);
+ isl_basic_map_free(bmap);
+ return NULL;
+}