/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
+ * Copyright 2012 Ecole Normale Superieure
*
* Use of this software is governed by the GNU LGPLv2.1 license
*
* Written by Sven Verdoolaege, K.U.Leuven, Departement
* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
+ * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
*/
#include <strings.h>
(struct isl_basic_map *)bset);
}
+/* Remove any common factor in numerator and denominator of a div expression,
+ * not taking into account the constant term.
+ * That is, look for any div of the form
+ *
+ * floor((a + m f(x))/(m d))
+ *
+ * and replace it by
+ *
+ * floor((floor(a/m) + f(x))/d)
+ *
+ * The difference {a/m}/d in the argument satisfies 0 <= {a/m}/d < 1/d
+ * and can therefore not influence the result of the floor.
+ */
+static __isl_give isl_basic_map *normalize_div_expressions(
+ __isl_take isl_basic_map *bmap)
+{
+ int i;
+ isl_int gcd;
+ unsigned total = isl_basic_map_total_dim(bmap);
+
+ if (!bmap)
+ return NULL;
+ if (bmap->n_div == 0)
+ return bmap;
+
+ isl_int_init(gcd);
+ for (i = 0; i < bmap->n_div; ++i) {
+ if (isl_int_is_zero(bmap->div[i][0]))
+ continue;
+ isl_seq_gcd(bmap->div[i] + 2, total, &gcd);
+ isl_int_gcd(gcd, gcd, bmap->div[i][0]);
+ if (isl_int_is_one(gcd))
+ continue;
+ isl_int_fdiv_q(bmap->div[i][1], bmap->div[i][1], gcd);
+ isl_int_divexact(bmap->div[i][0], bmap->div[i][0], gcd);
+ isl_seq_scale_down(bmap->div[i] + 2, bmap->div[i] + 2, gcd,
+ total);
+ }
+ isl_int_clear(gcd);
+
+ return bmap;
+}
+
/* Assumes divs have been ordered if keep_divs is set.
*/
static void eliminate_var_using_equality(struct isl_basic_map *bmap,
while (progress) {
progress = 0;
bmap = isl_basic_map_normalize_constraints(bmap);
+ bmap = normalize_div_expressions(bmap);
bmap = remove_duplicate_divs(bmap, &progress);
bmap = eliminate_divs_eq(bmap, &progress);
bmap = eliminate_divs_ineq(bmap, &progress);
return 1;
}
+int isl_basic_set_is_div_constraint(__isl_keep isl_basic_set *bset,
+ isl_int *constraint, unsigned div)
+{
+ return isl_basic_map_is_div_constraint(bset, constraint, div);
+}
+
/* If the only constraints a div d=floor(f/m)
* appears in are its two defining constraints
}
/* Eliminate the specified n dimensions starting at first from the
- * constraints using Fourier-Motzkin. The dimensions themselves
- * are not removed.
+ * constraints, without removing the dimensions from the space.
+ * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
+ * Otherwise, they are projected out and the original space is restored.
*/
__isl_give isl_basic_map *isl_basic_map_eliminate(
__isl_take isl_basic_map *bmap,
enum isl_dim_type type, unsigned first, unsigned n)
{
+ isl_space *space;
+
if (!bmap)
return NULL;
if (n == 0)
return bmap;
- if (first + n > isl_basic_map_dim(bmap, type))
+ if (first + n > isl_basic_map_dim(bmap, type) || first + n < first)
isl_die(bmap->ctx, isl_error_invalid,
"index out of bounds", goto error);
- first += isl_basic_map_offset(bmap, type) - 1;
- bmap = isl_basic_map_eliminate_vars(bmap, first, n);
- return isl_basic_map_finalize(bmap);
+ if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
+ first += isl_basic_map_offset(bmap, type) - 1;
+ bmap = isl_basic_map_eliminate_vars(bmap, first, n);
+ return isl_basic_map_finalize(bmap);
+ }
+
+ space = isl_basic_map_get_space(bmap);
+ bmap = isl_basic_map_project_out(bmap, type, first, n);
+ bmap = isl_basic_map_insert(bmap, type, first, n);
+ bmap = isl_basic_map_reset_space(bmap, space);
+ return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
context_ineq = context->n_ineq;
combined = isl_basic_set_cow(isl_basic_set_copy(context));
combined = isl_basic_set_extend_constraints(combined, 0, bset->n_ineq);
- tab = isl_tab_from_basic_set(combined);
+ tab = isl_tab_from_basic_set(combined, 0);
for (i = 0; i < context_ineq; ++i)
if (isl_tab_freeze_constraint(tab, i) < 0)
goto error;
return bmap;
}
if (isl_basic_map_plain_is_empty(context)) {
- isl_space *dim = isl_space_copy(bmap->dim);
- isl_basic_map_free(context);
isl_basic_map_free(bmap);
- return isl_basic_map_universe(dim);
+ return context;
}
if (isl_basic_map_plain_is_empty(bmap)) {
isl_basic_map_free(context);
goto error;;
if (isl_basic_map_plain_is_empty(context)) {
- isl_space *dim = isl_space_copy(map->dim);
- isl_basic_map_free(context);
isl_map_free(map);
- return isl_map_universe(dim);
+ return isl_map_from_basic_map(context);
}
context = isl_basic_map_remove_redundancies(context);
(struct isl_basic_map *)context);
}
+__isl_give isl_set *isl_set_gist_params_basic_set(__isl_take isl_set *set,
+ __isl_take isl_basic_set *context)
+{
+ isl_space *space = isl_set_get_space(set);
+ isl_basic_set *dom_context = isl_basic_set_universe(space);
+ dom_context = isl_basic_set_intersect_params(dom_context, context);
+ return isl_set_gist_basic_set(set, dom_context);
+}
+
__isl_give isl_set *isl_set_gist(__isl_take isl_set *set,
__isl_take isl_set *context)
{
(struct isl_map *)context);
}
+__isl_give isl_map *isl_map_gist_domain(__isl_take isl_map *map,
+ __isl_take isl_set *context)
+{
+ isl_map *map_context = isl_map_universe(isl_map_get_space(map));
+ map_context = isl_map_intersect_domain(map_context, context);
+ return isl_map_gist(map, map_context);
+}
+
+__isl_give isl_map *isl_map_gist_range(__isl_take isl_map *map,
+ __isl_take isl_set *context)
+{
+ isl_map *map_context = isl_map_universe(isl_map_get_space(map));
+ map_context = isl_map_intersect_range(map_context, context);
+ return isl_map_gist(map, map_context);
+}
+
__isl_give isl_map *isl_map_gist_params(__isl_take isl_map *map,
__isl_take isl_set *context)
{
if (!vec)
goto error;
- tab = isl_tab_from_basic_map(bmap);
+ tab = isl_tab_from_basic_map(bmap, 0);
while (n > 0) {
int i, l, u;