/*
* Copyright 2010 INRIA Saclay
*
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
* 91893 Orsay, France
*/
+#include <isl_map_private.h>
#include <isl_morph.h>
#include <isl/seq.h>
-#include <isl_map_private.h>
#include <isl_mat_private.h>
-#include <isl_dim_private.h>
+#include <isl_space_private.h>
#include <isl_equalities.h>
__isl_give isl_morph *isl_morph_alloc(
free(morph);
}
-__isl_give isl_dim *isl_morph_get_ran_dim(__isl_keep isl_morph *morph)
+__isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph)
{
if (!morph)
return NULL;
- return isl_dim_copy(morph->ran->dim);
+ return isl_space_copy(morph->ran->dim);
}
unsigned isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
if (!morph)
return NULL;
- dom_offset = 1 + isl_dim_offset(morph->dom->dim, type);
+ dom_offset = 1 + isl_space_offset(morph->dom->dim, type);
morph->dom = isl_basic_set_remove_dims(morph->dom, type, first, n);
if (!morph)
return NULL;
- ran_offset = 1 + isl_dim_offset(morph->ran->dim, type);
+ ran_offset = 1 + isl_space_offset(morph->ran->dim, type);
morph->ran = isl_basic_set_remove_dims(morph->ran, type, first, n);
return NULL;
}
-void isl_morph_dump(__isl_take isl_morph *morph, FILE *out)
+/* Project domain of morph onto its parameter domain.
+ */
+__isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph)
+{
+ unsigned n;
+
+ morph = isl_morph_cow(morph);
+ if (!morph)
+ return NULL;
+ n = isl_basic_set_dim(morph->dom, isl_dim_set);
+ morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, n);
+ if (!morph)
+ return NULL;
+ morph->dom = isl_basic_set_params(morph->dom);
+ if (morph->dom)
+ return morph;
+
+ isl_morph_free(morph);
+ return NULL;
+}
+
+/* Project range of morph onto its parameter domain.
+ */
+__isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph)
+{
+ unsigned n;
+
+ morph = isl_morph_cow(morph);
+ if (!morph)
+ return NULL;
+ n = isl_basic_set_dim(morph->ran, isl_dim_set);
+ morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, n);
+ if (!morph)
+ return NULL;
+ morph->ran = isl_basic_set_params(morph->ran);
+ if (morph->ran)
+ return morph;
+
+ isl_morph_free(morph);
+ return NULL;
+}
+
+void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out)
{
if (!morph)
return;
isl_basic_set_print(morph->dom, out, 0, "", "", ISL_FORMAT_ISL);
isl_basic_set_print(morph->ran, out, 0, "", "", ISL_FORMAT_ISL);
- isl_mat_dump(morph->map, out, 4);
- isl_mat_dump(morph->inv, out, 4);
+ isl_mat_print_internal(morph->map, out, 4);
+ isl_mat_print_internal(morph->inv, out, 4);
+}
+
+void isl_morph_dump(__isl_take isl_morph *morph)
+{
+ isl_morph_print_internal(morph, stderr);
}
__isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset)
total = isl_basic_set_total_dim(bset);
id = isl_mat_identity(bset->ctx, 1 + total);
- universe = isl_basic_set_universe(isl_dim_copy(bset->dim));
+ universe = isl_basic_set_universe(isl_space_copy(bset->dim));
return isl_morph_alloc(universe, isl_basic_set_copy(universe),
id, isl_mat_copy(id));
total = isl_basic_set_total_dim(bset);
id = isl_mat_identity(bset->ctx, 1 + total);
- empty = isl_basic_set_empty(isl_dim_copy(bset->dim));
+ empty = isl_basic_set_empty(isl_space_copy(bset->dim));
return isl_morph_alloc(empty, isl_basic_set_copy(empty),
id, isl_mat_copy(id));
isl_assert(bset->ctx, bset->n_div == 0, return NULL);
total = isl_basic_set_total_dim(bset);
- eq = isl_basic_set_alloc_dim(isl_dim_copy(bset->dim), 0, n, 0);
+ eq = isl_basic_set_alloc_space(isl_space_copy(bset->dim), 0, n, 0);
if (!eq)
return NULL;
for (i = 0; i < n; ++i) {
return NULL;
}
-/* Given a basic set, exploit the equalties in the a basic set to construct
+/* Given a basic set, exploit the equalties in the basic set to construct
* a morphishm that maps the basic set to a lower-dimensional space.
* Specifically, the morphism reduces the number of dimensions of type "type".
*
unsigned ntype;
unsigned orest;
unsigned nrest;
- unsigned total;
int f_eq, n_eq;
- isl_dim *dim;
+ isl_space *dim;
isl_mat *H, *U, *Q, *C = NULL, *H1, *U1, *U2;
isl_basic_set *dom, *ran;
if (!bset)
return NULL;
- if (isl_basic_set_fast_is_empty(bset))
+ if (isl_basic_set_plain_is_empty(bset))
return isl_morph_empty(bset);
isl_assert(bset->ctx, bset->n_div == 0, return NULL);
- otype = 1 + isl_dim_offset(bset->dim, type);
+ otype = 1 + isl_space_offset(bset->dim, type);
ntype = isl_basic_set_dim(bset, type);
orest = otype + ntype;
nrest = isl_basic_set_total_dim(bset) - (orest - 1);
if (n_eq == 0)
return isl_morph_identity(bset);
- H = isl_mat_sub_alloc(bset->ctx, bset->eq, f_eq, n_eq, otype, ntype);
+ H = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, otype, ntype);
H = isl_mat_left_hermite(H, 0, &U, &Q);
if (!H || !U || !Q)
goto error;
isl_int_set_si(C->row[0][0], 1);
isl_seq_clr(C->row[0] + 1, otype - 1);
isl_mat_sub_neg(C->ctx, C->row + 1, bset->eq + f_eq, n_eq, 0, 0, otype);
- H1 = isl_mat_sub_alloc(H->ctx, H->row, 0, H->n_row, 0, H->n_row);
+ H1 = isl_mat_sub_alloc(H, 0, H->n_row, 0, H->n_row);
H1 = isl_mat_lin_to_aff(H1);
C = isl_mat_inverse_product(H1, C);
if (!C)
C = isl_mat_normalize(C);
}
- U1 = isl_mat_sub_alloc(U->ctx, U->row, 0, U->n_row, 0, n_eq);
+ U1 = isl_mat_sub_alloc(U, 0, U->n_row, 0, n_eq);
U1 = isl_mat_lin_to_aff(U1);
- U2 = isl_mat_sub_alloc(U->ctx, U->row, 0, U->n_row, n_eq, U->n_row - n_eq);
+ U2 = isl_mat_sub_alloc(U, 0, U->n_row, n_eq, U->n_row - n_eq);
U2 = isl_mat_lin_to_aff(U2);
isl_mat_free(U);
C = insert_parameter_rows(C, otype - 1);
C = isl_mat_diagonal(C, isl_mat_identity(bset->ctx, nrest));
- dim = isl_dim_copy(bset->dim);
- dim = isl_dim_drop(dim, type, 0, ntype);
- dim = isl_dim_add(dim, type, ntype - n_eq);
+ dim = isl_space_copy(bset->dim);
+ dim = isl_space_drop_dims(dim, type, 0, ntype);
+ dim = isl_space_add_dims(dim, type, ntype - n_eq);
ran = isl_basic_set_universe(dim);
dom = copy_equalities(bset, f_eq, n_eq);
* We basically just call isl_mat_parameter_compression with the right input
* and then extend the resulting matrix to include the variables.
*
+ * The implementation assumes that "bset" does not have any equalities
+ * that only involve the parameters and that isl_basic_set_gauss has
+ * been applied to "bset".
+ *
* Let the equalities be given as
*
* B(p) + A x = 0
if (!bset)
return NULL;
- if (isl_basic_set_fast_is_empty(bset))
+ if (isl_basic_set_plain_is_empty(bset))
return isl_morph_empty(bset);
if (bset->n_eq == 0)
return isl_morph_identity(bset);
nparam = isl_basic_set_dim(bset, isl_dim_param);
nvar = isl_basic_set_dim(bset, isl_dim_set);
- isl_assert(bset->ctx, n_eq <= nvar, return NULL);
+ if (isl_seq_first_non_zero(bset->eq[bset->n_eq - 1] + 1 + nparam,
+ nvar) == -1)
+ isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
+ "input not allowed to have parameter equalities",
+ return NULL);
+ if (n_eq > nvar)
+ isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
+ "input not gaussed", return NULL);
d = isl_vec_alloc(bset->ctx, n_eq);
- B = isl_mat_sub_alloc(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam);
- H = isl_mat_sub_alloc(bset->ctx, bset->eq, 0, n_eq, 1 + nparam, nvar);
+ B = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam);
+ H = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 1 + nparam, nvar);
H = isl_mat_left_hermite(H, 0, NULL, NULL);
H = isl_mat_drop_cols(H, n_eq, nvar - n_eq);
H = isl_mat_lin_to_aff(H);
H = isl_mat_right_inverse(H);
if (!H || !d)
goto error;
- isl_seq_set(d->el, H->row[0][0], d->size);
+ d = isl_vec_set(d, H->row[0][0]);
H = isl_mat_drop_rows(H, 0, 1);
H = isl_mat_drop_cols(H, 0, 1);
B = isl_mat_product(H, B);
inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar));
map = isl_mat_right_inverse(isl_mat_copy(inv));
- dom = isl_basic_set_universe(isl_dim_copy(bset->dim));
- ran = isl_basic_set_universe(isl_dim_copy(bset->dim));
+ dom = isl_basic_set_universe(isl_space_copy(bset->dim));
+ ran = isl_basic_set_universe(isl_space_copy(bset->dim));
return isl_morph_alloc(dom, ran, map, inv);
error:
div = isl_basic_set_alloc_div(bset);
if (div < 0)
goto error;
+ isl_int_set_si(bset->div[div][0], 0);
k = isl_basic_set_alloc_equality(bset);
if (k < 0)
goto error;
if (!morph || !bset)
goto error;
- isl_assert(bset->ctx, isl_dim_equal(bset->dim, morph->dom->dim),
+ isl_assert(bset->ctx, isl_space_is_equal(bset->dim, morph->dom->dim),
goto error);
max_stride = morph->inv->n_row - 1;
if (isl_int_is_one(morph->inv->row[0][0]))
max_stride = 0;
- res = isl_basic_set_alloc_dim(isl_dim_copy(morph->ran->dim),
+ res = isl_basic_set_alloc_space(isl_space_copy(morph->ran->dim),
bset->n_div + max_stride, bset->n_eq + max_stride, bset->n_ineq);
for (i = 0; i < bset->n_div; ++i)
if (isl_basic_set_alloc_div(res) < 0)
goto error;
- mat = isl_mat_sub_alloc(bset->ctx, bset->eq, 0, bset->n_eq,
+ mat = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
0, morph->inv->n_row);
mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
if (!mat)
}
isl_mat_free(mat);
- mat = isl_mat_sub_alloc(bset->ctx, bset->ineq, 0, bset->n_ineq,
+ mat = isl_mat_sub_alloc6(bset->ctx, bset->ineq, 0, bset->n_ineq,
0, morph->inv->n_row);
mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
if (!mat)
}
isl_mat_free(mat);
- mat = isl_mat_sub_alloc(bset->ctx, bset->div, 0, bset->n_div,
+ mat = isl_mat_sub_alloc6(bset->ctx, bset->div, 0, bset->n_div,
1, morph->inv->n_row);
mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
if (!mat)
res = add_strides(res, morph);
+ if (isl_basic_set_is_rational(bset))
+ res = isl_basic_set_set_rational(res);
+
res = isl_basic_set_simplify(res);
res = isl_basic_set_finalize(res);
if (!morph || !set)
goto error;
- isl_assert(set->ctx, isl_dim_equal(set->dim, morph->dom->dim), goto error);
+ isl_assert(set->ctx, isl_space_is_equal(set->dim, morph->dom->dim), goto error);
set = isl_set_cow(set);
if (!set)
goto error;
- isl_dim_free(set->dim);
- set->dim = isl_dim_copy(morph->ran->dim);
+ isl_space_free(set->dim);
+ set->dim = isl_space_copy(morph->ran->dim);
if (!set->dim)
goto error;
return morph;
}
+/* We detect all the equalities first to avoid implicit equalties
+ * being discovered during the computations. In particular,
+ * the compression on the variables could expose additional stride
+ * constraints on the parameters. This would result in existentially
+ * quantified variables after applying the resulting morph, which
+ * in turn could break invariants of the calling functions.
+ */
__isl_give isl_morph *isl_basic_set_full_compression(
__isl_keep isl_basic_set *bset)
{
isl_morph *morph, *morph2;
bset = isl_basic_set_copy(bset);
+ bset = isl_basic_set_detect_equalities(bset);
morph = isl_basic_set_variable_compression(bset, isl_dim_param);
bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
projects / platform / upstream / isl.git / blobdiff