+/*
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * 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
+ */
+
#include "isl_equalities.h"
#include "isl_map.h"
#include "isl_map_private.h"
+#include "isl_seq.h"
#include "isl_tab.h"
static void swap_equality(struct isl_basic_map *bmap, int a, int b)
return NULL;
}
+struct isl_set *isl_set_drop(struct isl_set *set,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return (isl_set *)isl_map_drop((isl_map *)set, type, first, n);
+}
+
struct isl_map *isl_map_drop_inputs(
struct isl_map *map, unsigned first, unsigned n)
{
struct isl_basic_set *isl_basic_set_normalize_constraints(
struct isl_basic_set *bset)
{
- (struct isl_basic_set *)isl_basic_map_normalize_constraints(
+ return (struct isl_basic_set *)isl_basic_map_normalize_constraints(
(struct isl_basic_map *)bset);
}
-static void eliminate_div(struct isl_basic_map *bmap, isl_int *eq, unsigned div)
+/* Assumes divs have been ordered if keep_divs is set.
+ */
+static void eliminate_var_using_equality(struct isl_basic_map *bmap,
+ unsigned pos, isl_int *eq, int keep_divs, int *progress)
{
- int i;
- unsigned pos = 1 + isl_dim_total(bmap->dim) + div;
- unsigned len;
- len = 1 + isl_basic_map_total_dim(bmap);
+ unsigned total;
+ int k;
+ int last_div;
- for (i = 0; i < bmap->n_eq; ++i)
- if (bmap->eq[i] != eq)
- isl_seq_elim(bmap->eq[i], eq, pos, len, NULL);
+ total = isl_basic_map_total_dim(bmap);
+ last_div = isl_seq_last_non_zero(eq + 1 + isl_dim_total(bmap->dim),
+ bmap->n_div);
+ for (k = 0; k < bmap->n_eq; ++k) {
+ if (bmap->eq[k] == eq)
+ continue;
+ if (isl_int_is_zero(bmap->eq[k][1+pos]))
+ continue;
+ if (progress)
+ *progress = 1;
+ isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);
+ }
- for (i = 0; i < bmap->n_ineq; ++i)
- isl_seq_elim(bmap->ineq[i], eq, pos, len, NULL);
+ for (k = 0; k < bmap->n_ineq; ++k) {
+ if (isl_int_is_zero(bmap->ineq[k][1+pos]))
+ continue;
+ if (progress)
+ *progress = 1;
+ isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);
+ ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
+ }
- /* We need to be careful about circular definitions,
- * so for now we just remove the definitions of other divs that
- * depend on this div and (possibly) recompute them later.
- */
- for (i = 0; i < bmap->n_div; ++i)
- if (!isl_int_is_zero(bmap->div[i][0]) &&
- !isl_int_is_zero(bmap->div[i][1 + pos]))
- isl_seq_clr(bmap->div[i], 1 + len);
+ for (k = 0; k < bmap->n_div; ++k) {
+ if (isl_int_is_zero(bmap->div[k][0]))
+ continue;
+ if (isl_int_is_zero(bmap->div[k][1+1+pos]))
+ continue;
+ if (progress)
+ *progress = 1;
+ /* We need to be careful about circular definitions,
+ * so for now we just remove the definition of div k
+ * if the equality contains any divs.
+ * If keep_divs is set, then the divs have been ordered
+ * and we can keep the definition as long as the result
+ * is still ordered.
+ */
+ if (last_div == -1 || (keep_divs && last_div < k))
+ isl_seq_elim(bmap->div[k]+1, eq,
+ 1+pos, 1+total, &bmap->div[k][0]);
+ else
+ isl_seq_clr(bmap->div[k], 1 + total);
+ ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
+ }
+}
+
+/* Assumes divs have been ordered if keep_divs is set.
+ */
+static void eliminate_div(struct isl_basic_map *bmap, isl_int *eq,
+ unsigned div, int keep_divs)
+{
+ unsigned pos = isl_dim_total(bmap->dim) + div;
+
+ eliminate_var_using_equality(bmap, pos, eq, keep_divs, NULL);
isl_basic_map_drop_div(bmap, div);
}
int modified = 0;
unsigned off;
+ bmap = isl_basic_map_order_divs(bmap);
+
if (!bmap)
return NULL;
continue;
modified = 1;
*progress = 1;
- eliminate_div(bmap, bmap->eq[i], d);
+ eliminate_div(bmap, bmap->eq[i], d, 1);
isl_basic_map_drop_equality(bmap, i);
break;
}
return bmap;
}
-static void eliminate_var_using_equality(struct isl_basic_map *bmap,
- unsigned pos, isl_int *eq, int *progress)
-{
- unsigned total;
- int k;
- int contains_divs;
-
- total = isl_basic_map_total_dim(bmap);
- contains_divs =
- isl_seq_first_non_zero(eq + 1 + isl_dim_total(bmap->dim),
- bmap->n_div) != -1;
- for (k = 0; k < bmap->n_eq; ++k) {
- if (bmap->eq[k] == eq)
- continue;
- if (isl_int_is_zero(bmap->eq[k][1+pos]))
- continue;
- if (progress)
- *progress = 1;
- isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);
- }
-
- for (k = 0; k < bmap->n_ineq; ++k) {
- if (isl_int_is_zero(bmap->ineq[k][1+pos]))
- continue;
- if (progress)
- *progress = 1;
- isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);
- ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
- }
-
- for (k = 0; k < bmap->n_div; ++k) {
- if (isl_int_is_zero(bmap->div[k][0]))
- continue;
- if (isl_int_is_zero(bmap->div[k][1+1+pos]))
- continue;
- if (progress)
- *progress = 1;
- /* We need to be careful about circular definitions,
- * so for now we just remove the definition of div k
- * if the equality contains any divs.
- */
- if (contains_divs)
- isl_seq_clr(bmap->div[k], 1 + total);
- else
- isl_seq_elim(bmap->div[k]+1, eq,
- 1+pos, 1+total, &bmap->div[k][0]);
- ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
- }
-}
-
struct isl_basic_map *isl_basic_map_gauss(
struct isl_basic_map *bmap, int *progress)
{
unsigned total_var;
unsigned total;
+ bmap = isl_basic_map_order_divs(bmap);
+
if (!bmap)
return NULL;
if (isl_int_is_neg(bmap->eq[done][1+last_var]))
isl_seq_neg(bmap->eq[done], bmap->eq[done], 1+total);
- eliminate_var_using_equality(bmap, last_var, bmap->eq[done],
+ eliminate_var_using_equality(bmap, last_var, bmap->eq[done], 1,
progress);
if (last_var >= total_var &&
k = elim_for[l] - 1;
isl_int_set_si(eq.data[1+total_var+k], -1);
isl_int_set_si(eq.data[1+total_var+l], 1);
- eliminate_div(bmap, eq.data, l);
+ eliminate_div(bmap, eq.data, l, 0);
isl_int_set_si(eq.data[1+total_var+k], 0);
isl_int_set_si(eq.data[1+total_var+l], 0);
}
static struct isl_basic_map *check_for_div_constraints(
struct isl_basic_map *bmap, int k, int l, isl_int sum, int *progress)
{
- int i, j;
+ int i;
unsigned total = 1 + isl_dim_total(bmap->dim);
for (i = 0; i < bmap->n_div; ++i) {
* will no longer be valid.
* Plus, we probably we want to regauss first.
*/
+ if (progress)
+ *progress = 1;
isl_basic_map_drop_inequality(bmap, l);
isl_basic_map_inequality_to_equality(bmap, k);
} else
}
-/* Remove any div that is defined in terms of the given variable.
+/* Remove definition of any div that is defined in terms of the given variable.
+ * The div itself is not removed. Functions such as
+ * eliminate_divs_ineq depend on the other divs remaining in place.
*/
static struct isl_basic_map *remove_dependent_vars(struct isl_basic_map *bmap,
int pos)
{
int i;
- unsigned dim = isl_dim_total(bmap->dim);
for (i = 0; i < bmap->n_div; ++i) {
if (isl_int_is_zero(bmap->div[i][0]))
continue;
if (isl_int_is_zero(bmap->div[i][1+1+pos]))
continue;
- bmap = isl_basic_map_eliminate_vars(bmap, dim + i, 1);
- if (!bmap)
- return NULL;
+ isl_int_set_si(bmap->div[i][0], 0);
}
return bmap;
}
for (i = 0; i < bmap->n_eq; ++i) {
if (isl_int_is_zero(bmap->eq[i][1+d]))
continue;
- eliminate_var_using_equality(bmap, d, bmap->eq[i], NULL);
+ eliminate_var_using_equality(bmap, d, bmap->eq[i], 0, NULL);
isl_basic_map_drop_equality(bmap, i);
break;
}
static void set_compute_elimination_index(struct isl_basic_set *bset, int *elim)
{
- return compute_elimination_index((struct isl_basic_map *)bset, elim);
+ compute_elimination_index((struct isl_basic_map *)bset, elim);
}
static int reduced_using_equalities(isl_int *dst, isl_int *src,
struct isl_basic_map *bmap, int *elim)
{
- int d, i;
+ int d;
int copied = 0;
unsigned total;
bset = remove_shifted_constraints(bset, context);
if (!bset->n_ineq)
goto done;
- isl_basic_set_free_equality(context, context->n_eq);
context_ineq = context->n_ineq;
combined = isl_basic_set_cow(isl_basic_set_copy(context));
+ if (isl_basic_set_free_equality(combined, context->n_eq) < 0)
+ goto error;
combined = isl_basic_set_extend_constraints(combined,
bset->n_eq, bset->n_ineq);
tab = isl_tab_from_basic_set(combined);
if (!tab)
goto error;
for (i = 0; i < context_ineq; ++i)
- tab->con[i].frozen = 1;
+ if (isl_tab_freeze_constraint(tab, i) < 0)
+ goto error;
tab = isl_tab_extend(tab, bset->n_ineq);
if (!tab)
goto error;
for (i = 0; i < bset->n_ineq; ++i)
- tab = isl_tab_add_ineq(tab, bset->ineq[i]);
+ if (isl_tab_add_ineq(tab, bset->ineq[i]) < 0)
+ goto error;
bset = isl_basic_set_add_constraints(combined, bset, 0);
- tab = isl_tab_detect_equalities(tab);
- tab = isl_tab_detect_redundant(tab);
- if (!tab)
+ tab = isl_tab_detect_implicit_equalities(tab);
+ if (isl_tab_detect_redundant(tab) < 0) {
+ isl_tab_free(tab);
goto error2;
+ }
for (i = 0; i < context_ineq; ++i) {
tab->con[i].is_zero = 0;
tab->con[i].is_redundant = 1;
struct isl_vec *v = NULL;
int *elim = NULL;
unsigned total;
- int d, i;
+ int i;
if (!bmap1 || !bmap2)
return -1;
* Otherwise return -1.
*
* We first check that
- * - the bounds are opposites of each other (expect for the constant
- * term
+ * - the bounds are opposites of each other (except for the constant
+ * term)
* - the bounds do not reference any other div
* - no div is defined in terms of this div
*
}
isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0], bmap->ineq[u][0]);
+ if (isl_int_is_neg(bmap->ineq[l][0])) {
+ isl_int_sub(bmap->ineq[l][0],
+ bmap->ineq[l][0], bmap->ineq[u][0]);
+ bmap = isl_basic_map_copy(bmap);
+ bmap = isl_basic_map_set_to_empty(bmap);
+ isl_basic_map_free(bmap);
+ return -1;
+ }
isl_int_add_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
for (i = 0; i < bmap->n_div; ++i) {
if (i == div)
}
}
+ if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
+ return bmap;
+
return drop_more_redundant_divs(bmap, pairs, n);
}
int pos, neg;
int last_pos, last_neg;
int redundant;
+ int defined;
- if (!isl_int_is_zero(bmap->div[i][0]))
- continue;
+ defined = !isl_int_is_zero(bmap->div[i][0]);
for (j = 0; j < bmap->n_eq; ++j)
if (!isl_int_is_zero(bmap->eq[j][1 + off + i]))
break;
isl_int_sub(bmap->ineq[last_pos][0],
bmap->ineq[last_pos][0], bmap->ineq[last_neg][0]);
if (!redundant) {
- if (!ok_to_set_div_from_bound(bmap, i, last_pos)) {
+ if (defined ||
+ !ok_to_set_div_from_bound(bmap, i, last_pos)) {
pairs[i] = 0;
--n;
continue;
isl_basic_map_free(bmap);
return NULL;
}
+
+struct isl_basic_set *isl_basic_set_drop_redundant_divs(
+ struct isl_basic_set *bset)
+{
+ return (struct isl_basic_set *)
+ isl_basic_map_drop_redundant_divs((struct isl_basic_map *)bset);
+}
+
+struct isl_map *isl_map_drop_redundant_divs(struct isl_map *map)
+{
+ int i;
+
+ if (!map)
+ return NULL;
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_drop_redundant_divs(map->p[i]);
+ if (!map->p[i])
+ goto error;
+ }
+ ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+ return map;
+error:
+ isl_map_free(map);
+ return NULL;
+}
+
+struct isl_set *isl_set_drop_redundant_divs(struct isl_set *set)
+{
+ return (struct isl_set *)
+ isl_map_drop_redundant_divs((struct isl_map *)set);
+}
projects / platform / upstream / isl.git / blobdiff