diff --git a/isl_map_simplify.c b/isl_map_simplify.c
--- a/isl_map_simplify.c
+++ b/isl_map_simplify.c
* Copyright 2012-2013 Ecole Normale Superieure
* Copyright 2014-2015 INRIA Rocquencourt
* Copyright 2016 Sven Verdoolaege
+ * Copyright 2021,2023 Cerebras Systems
*
* Use of this software is governed by the MIT license
*
* and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
* B.P. 105 - 78153 Le Chesnay, France
+ * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA
*/
#include <isl_ctx_private.h>
#include <set_to_map.c>
#include <set_from_map.c>
-static void swap_equality(struct isl_basic_map *bmap, int a, int b)
+/* Mark "bmap" as having one or more inequality constraints modified.
+ * If "equivalent" is set, then this modification was done based
+ * on an equality constraint already available in "bmap".
+ *
+ * Any modification may result in the constraints no longer being sorted and
+ * may also undo the effect of reduce_coefficients.
+ *
+ * A modification that uses extra information may also result
+ * in the modified constraint(s) becoming redundant or
+ * turning into an implicit equality constraint.
+ */
+static __isl_give isl_basic_map *isl_basic_map_modify_inequality(
+ __isl_take isl_basic_map *bmap, int equivalent)
+{
+ if (!bmap)
+ return NULL;
+ ISL_F_CLR(bmap, ISL_BASIC_MAP_SORTED);
+ ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
+ if (equivalent)
+ return bmap;
+ ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
+ ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
+ return bmap;
+}
+
+static void swap_equality(__isl_keep isl_basic_map *bmap, int a, int b)
{
isl_int *t = bmap->eq[a];
bmap->eq[a] = bmap->eq[b];
bmap->eq[b] = t;
}
-static void swap_inequality(struct isl_basic_map *bmap, int a, int b)
+static void swap_inequality(__isl_keep isl_basic_map *bmap, int a, int b)
{
if (a != b) {
isl_int *t = bmap->ineq[a];
}
}
+/* Scale down the inequality constraint "ineq" of length "len"
+ * by a factor of "f".
+ * All the coefficients, except the constant term,
+ * are assumed to be multiples of "f".
+ *
+ * If the factor is 0 or 1, then no scaling needs to be performed.
+ *
+ * If scaling is performed then take into account that the constraint
+ * is modified (not simply based on an equality constraint).
+ */
+static __isl_give isl_basic_map *scale_down_inequality(
+ __isl_take isl_basic_map *bmap, int ineq, isl_int f, unsigned len)
+{
+ if (!bmap)
+ return NULL;
+
+ if (isl_int_is_zero(f) || isl_int_is_one(f))
+ return bmap;
+
+ isl_int_fdiv_q(bmap->ineq[ineq][0], bmap->ineq[ineq][0], f);
+ isl_seq_scale_down(bmap->ineq[ineq] + 1, bmap->ineq[ineq] + 1, f, len);
+
+ bmap = isl_basic_map_modify_inequality(bmap, 0);
+
+ return bmap;
+}
+
__isl_give isl_basic_map *isl_basic_map_normalize_constraints(
__isl_take isl_basic_map *bmap)
{
int i;
isl_int gcd;
- unsigned total = isl_basic_map_total_dim(bmap);
+ isl_size total = isl_basic_map_dim(bmap, isl_dim_all);
- if (!bmap)
- return NULL;
+ if (total < 0)
+ return isl_basic_map_free(bmap);
isl_int_init(gcd);
for (i = bmap->n_eq - 1; i >= 0; --i) {
bmap = isl_basic_map_set_to_empty(bmap);
break;
}
- isl_basic_map_drop_equality(bmap, i);
+ if (isl_basic_map_drop_equality(bmap, i) < 0)
+ goto error;
continue;
}
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
bmap = isl_basic_map_set_to_empty(bmap);
break;
}
- isl_basic_map_drop_inequality(bmap, i);
+ if (isl_basic_map_drop_inequality(bmap, i) < 0)
+ goto error;
continue;
}
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
isl_int_gcd(gcd, gcd, bmap->ineq[i][0]);
- if (isl_int_is_one(gcd))
- continue;
- isl_int_fdiv_q(bmap->ineq[i][0], bmap->ineq[i][0], gcd);
- isl_seq_scale_down(bmap->ineq[i]+1, bmap->ineq[i]+1, gcd, total);
+ bmap = scale_down_inequality(bmap, i, gcd, total);
+ if (!bmap)
+ goto error;
}
isl_int_clear(gcd);
return bmap;
+error:
+ isl_int_clear(gcd);
+ isl_basic_map_free(bmap);
+ return NULL;
}
__isl_give isl_basic_set *isl_basic_set_normalize_constraints(
__isl_take isl_basic_map *bmap, int div)
{
int i;
- unsigned total = 1 + isl_basic_map_total_dim(bmap);
+ isl_size total;
- for (i = 0; i < total; ++i) {
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_basic_map_free(bmap);
+ for (i = 0; i < 1 + total; ++i) {
isl_bool reduce;
reduce = needs_reduction(bmap, div, i);
* 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 void normalize_div_expression(__isl_keep isl_basic_map *bmap, int div)
+static __isl_give isl_basic_map *normalize_div_expression(
+ __isl_take isl_basic_map *bmap, int div)
{
- unsigned total = isl_basic_map_total_dim(bmap);
+ isl_size total = isl_basic_map_dim(bmap, isl_dim_all);
isl_ctx *ctx = bmap->ctx;
+ if (total < 0)
+ return isl_basic_map_free(bmap);
if (isl_int_is_zero(bmap->div[div][0]))
- return;
+ return bmap;
isl_seq_gcd(bmap->div[div] + 2, total, &ctx->normalize_gcd);
isl_int_gcd(ctx->normalize_gcd, ctx->normalize_gcd, bmap->div[div][0]);
if (isl_int_is_one(ctx->normalize_gcd))
- return;
+ return bmap;
isl_int_fdiv_q(bmap->div[div][1], bmap->div[div][1],
ctx->normalize_gcd);
isl_int_divexact(bmap->div[div][0], bmap->div[div][0],
ctx->normalize_gcd);
isl_seq_scale_down(bmap->div[div] + 2, bmap->div[div] + 2,
ctx->normalize_gcd, total);
+
+ return bmap;
}
/* Remove any common factor in numerator and denominator of a div expression,
return bmap;
for (i = 0; i < bmap->n_div; ++i)
- normalize_div_expression(bmap, i);
+ bmap = normalize_div_expression(bmap, i);
return bmap;
}
-/* Assumes divs have been ordered if keep_divs is set.
+/* Some progress has been made.
+ * Set *progress if "progress" is not NULL.
*/
-static void eliminate_var_using_equality(struct isl_basic_map *bmap,
- unsigned pos, isl_int *eq, int keep_divs, int *progress)
+static void mark_progress(int *progress)
{
- unsigned total;
- unsigned space_total;
+ if (progress)
+ *progress = 1;
+}
+
+/* Eliminate the variable at position "pos" from the constraints of "bmap"
+ * using the equality constraint "eq".
+ * If "keep_divs" is set, then try and preserve
+ * the integer division expressions. In this case, these expressions
+ * are assumed to have been ordered.
+ * If "equivalent" is set, then the elimination is performed
+ * using an equality constraint of "bmap", meaning that the meaning
+ * of the constraints is preserved.
+ */
+static __isl_give isl_basic_map *eliminate_var_using_equality(
+ __isl_take isl_basic_map *bmap,
+ unsigned pos, isl_int *eq, int keep_divs, int equivalent, int *progress)
+{
+ isl_size total;
+ isl_size v_div;
int k;
int last_div;
+ isl_ctx *ctx;
- total = isl_basic_map_total_dim(bmap);
- space_total = isl_space_dim(bmap->dim, isl_dim_all);
- last_div = isl_seq_last_non_zero(eq + 1 + space_total, bmap->n_div);
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (total < 0 || v_div < 0)
+ return isl_basic_map_free(bmap);
+ ctx = isl_basic_map_get_ctx(bmap);
+ last_div = isl_seq_last_non_zero(eq + 1 + v_div, 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;
+ mark_progress(progress);
isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);
- isl_seq_normalize(bmap->ctx, bmap->eq[k], 1 + total);
+ isl_seq_normalize(ctx, bmap->eq[k], 1 + total);
}
for (k = 0; k < bmap->n_ineq; ++k) {
if (isl_int_is_zero(bmap->ineq[k][1+pos]))
continue;
- if (progress)
- *progress = 1;
+ mark_progress(progress);
isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);
- isl_seq_normalize(bmap->ctx, bmap->ineq[k], 1 + total);
- ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
+ isl_seq_gcd(bmap->ineq[k], 1 + total, &ctx->normalize_gcd);
+ bmap = scale_down_inequality(bmap, k, ctx->normalize_gcd,
+ total);
+ bmap = isl_basic_map_modify_inequality(bmap, equivalent);
+ if (!bmap)
+ return NULL;
}
for (k = 0; k < bmap->n_div; ++k) {
continue;
if (isl_int_is_zero(bmap->div[k][1+1+pos]))
continue;
- if (progress)
- *progress = 1;
+ mark_progress(progress);
/* 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 (last_div == -1 || (keep_divs && last_div < k)) {
isl_seq_elim(bmap->div[k]+1, eq,
1+pos, 1+total, &bmap->div[k][0]);
- normalize_div_expression(bmap, k);
+ bmap = normalize_div_expression(bmap, k);
+ if (!bmap)
+ return NULL;
} else
isl_seq_clr(bmap->div[k], 1 + total);
- ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
}
+
+ return bmap;
}
-/* Assumes divs have been ordered if keep_divs is set.
+/* Eliminate and remove the local variable at position "pos" of "bmap"
+ * using the equality constraint "eq".
+ * If "keep_divs" is set, then try and preserve
+ * the integer division expressions. In this case, these expressions
+ * are assumed to have been ordered.
+ * If "equivalent" is set, then the elimination is performed
+ * using an equality constraint of "bmap", meaning that the meaning
+ * of the constraints is preserved.
*/
static __isl_give isl_basic_map *eliminate_div(__isl_take isl_basic_map *bmap,
- isl_int *eq, unsigned div, int keep_divs)
+ isl_int *eq, unsigned div, int keep_divs, int equivalent)
{
- unsigned pos = isl_space_dim(bmap->dim, isl_dim_all) + div;
+ isl_size v_div;
+ unsigned pos;
- eliminate_var_using_equality(bmap, pos, eq, keep_divs, NULL);
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return isl_basic_map_free(bmap);
+ pos = v_div + div;
+ bmap = eliminate_var_using_equality(bmap, pos, eq, keep_divs,
+ equivalent, NULL);
bmap = isl_basic_map_drop_div(bmap, div);
@@ -362,10 +467,15 @@ static isl_bool ok_to_eliminate_div(__isl_keep isl_basic_map *bmap, isl_int *eq,
{
int k;
int last_div;
- unsigned space_total = isl_space_dim(bmap->dim, isl_dim_all);
- unsigned pos = space_total + div;
+ isl_size v_div;
+ unsigned pos;
+
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return isl_bool_error;
+ pos = v_div + div;
- last_div = isl_seq_last_non_zero(eq + 1 + space_total, bmap->n_div);
+ last_div = isl_seq_last_non_zero(eq + 1 + v_div, bmap->n_div);
if (last_div < 0 || last_div <= div)
return isl_bool_true;
if (!bmap)
return NULL;
- off = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+ off = isl_basic_map_offset(bmap, isl_dim_div);
for (d = bmap->n_div - 1; d >= 0 ; --d) {
for (i = 0; i < bmap->n_eq; ++i) {
if (!ok)
continue;
modified = 1;
- *progress = 1;
- bmap = eliminate_div(bmap, bmap->eq[i], d, 1);
+ mark_progress(progress);
+ bmap = eliminate_div(bmap, bmap->eq[i], d, 1, 1);
if (isl_basic_map_drop_equality(bmap, i) < 0)
return isl_basic_map_free(bmap);
break;
return NULL;
ctx = bmap->ctx;
- off = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+ off = isl_basic_map_offset(bmap, isl_dim_div);
for (d = bmap->n_div - 1; d >= 0 ; --d) {
for (i = 0; i < bmap->n_eq; ++i)
break;
if (i < bmap->n_ineq)
continue;
- *progress = 1;
+ mark_progress(progress);
bmap = isl_basic_map_eliminate_vars(bmap, (off-1)+d, 1);
if (!bmap || ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
break;
static __isl_give isl_basic_map *set_div_from_eq(__isl_take isl_basic_map *bmap,
int div, int eq, int *progress)
{
- unsigned total, o_div;
+ isl_size total;
+ unsigned o_div;
isl_bool involves;
if (!bmap)
@@ -530,13 +641,13 @@ static __isl_give isl_basic_map *set_div_from_eq(__isl_take isl_basic_map *bmap,
return bmap;
total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_basic_map_free(bmap);
o_div = isl_basic_map_offset(bmap, isl_dim_div);
isl_seq_neg(bmap->div[div] + 1, bmap->eq[eq], 1 + total);
isl_int_set_si(bmap->div[div][1 + o_div + div], 0);
isl_int_set(bmap->div[div][0], bmap->eq[eq][o_div + div]);
- if (progress)
- *progress = 1;
- ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
+ mark_progress(progress);
return bmap;
}
@@ -548,7 +659,7 @@ static __isl_give isl_basic_map *set_div_from_eq(__isl_take isl_basic_map *bmap,
* from all constraints.
*
* If "progress" is not NULL, then it gets set if the elimination
- * result in any changes.
+ * results in any changes.
* The elimination process may result in some equality constraints
* getting interchanged or removed.
* If "swap" or "drop" are not NULL, then they get called when
@@ -569,16 +680,16 @@ __isl_give isl_basic_map *isl_basic_map_gauss5(__isl_take isl_basic_map *bmap,
int done;
int last_var;
unsigned total_var;
- unsigned total;
+ isl_size total;
unsigned n_drop;
if (!swap && !drop)
bmap = isl_basic_map_order_divs(bmap);
- if (!bmap)
- return NULL;
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_basic_map_free(bmap);
- total = isl_basic_map_total_dim(bmap);
total_var = total - bmap->n_div;
last_var = total - 1;
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], 1,
- progress);
+ bmap = eliminate_var_using_equality(bmap, last_var,
+ bmap->eq[done], 1, 1, progress);
if (last_var >= total_var)
bmap = set_div_from_eq(bmap, last_var - total_var,
return isl_basic_map_set_to_empty(bmap);
}
n_drop = bmap->n_eq - done;
- isl_basic_map_free_equality(bmap, n_drop);
+ bmap = isl_basic_map_free_equality(bmap, n_drop);
if (drop && drop(n_drop, user) < 0)
return isl_basic_map_free(bmap);
return bmap;
unsigned int size;
int bits;
isl_int ***index;
- unsigned total;
+ isl_size total;
};
/* Fill in the "ci" data structure for holding the inequalities of "bmap".
ci->index = NULL;
if (!bmap)
return isl_stat_error;
- ci->total = isl_basic_set_total_dim(bmap);
+ ci->total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (ci->total < 0)
+ return isl_stat_error;
if (bmap->n_ineq == 0)
return isl_stat_ok;
ci->size = round_up(4 * (bmap->n_ineq + 1) / 3 - 1);
int k, l, h;
int bits;
struct isl_blk eq;
- unsigned total_var;
+ isl_size v_div;
unsigned total;
struct isl_ctx *ctx;
if (!bmap || bmap->n_div <= 1)
return bmap;
- total_var = isl_space_dim(bmap->dim, isl_dim_all);
- total = total_var + bmap->n_div;
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return isl_basic_map_free(bmap);
+ total = v_div + bmap->n_div;
ctx = bmap->ctx;
for (k = bmap->n_div - 1; k >= 0; --k)
bmap->div[index[h]-1], 2+total))
break;
if (index[h]) {
- *progress = 1;
+ mark_progress(progress);
l = index[h] - 1;
elim_for[l] = k + 1;
}
if (!elim_for[l])
continue;
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);
- bmap = eliminate_div(bmap, eq.data, l, 1);
+ isl_int_set_si(eq.data[1 + v_div + k], -1);
+ isl_int_set_si(eq.data[1 + v_div + l], 1);
+ bmap = eliminate_div(bmap, eq.data, l, 1, 0);
if (!bmap)
break;
- isl_int_set_si(eq.data[1+total_var+k], 0);
- isl_int_set_si(eq.data[1+total_var+l], 0);
+ isl_int_set_si(eq.data[1 + v_div + k], 0);
+ isl_int_set_si(eq.data[1 + v_div + l], 0);
}
isl_blk_free(ctx, eq);
return bmap;
}
-static int n_pure_div_eq(struct isl_basic_map *bmap)
+/* Is the local variable at position "div" of "bmap"
+ * an integral integer division?
+ */
+static isl_bool is_known_integral_div(__isl_keep isl_basic_map *bmap, int div)
+{
+ isl_bool unknown;
+
+ unknown = isl_basic_map_div_is_marked_unknown(bmap, div);
+ if (unknown < 0 || unknown)
+ return isl_bool_not(unknown);
+ return isl_basic_map_div_is_integral(bmap, div);
+}
+
+/* Eliminate local variable "div" from "bmap", given
+ * that it represents an integer division with denominator 1.
+ *
+ * Construct an equality constraint that equates the local variable
+ * to the argument of the integer division and use that to eliminate
+ * the local variable.
+ */
+static __isl_give isl_basic_map *eliminate_integral_div(
+ __isl_take isl_basic_map *bmap, int div)
+{
+ isl_size total, v_div;
+ isl_vec *v;
+
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (v_div < 0 || total < 0)
+ return isl_basic_map_free(bmap);
+ v = isl_vec_alloc(isl_basic_map_get_ctx(bmap), 1 + total);
+ if (!v)
+ return isl_basic_map_free(bmap);
+ isl_seq_cpy(v->el, bmap->div[div] + 1, 1 + total);
+ isl_int_set_si(v->el[1 + v_div + div], -1);
+ bmap = eliminate_div(bmap, v->el, div, 1, 0);
+ isl_vec_free(v);
+
+ return bmap;
+}
+
+/* Eliminate all integer divisions with denominator 1.
+ */
+static __isl_give isl_basic_map *eliminate_integral_divs(
+ __isl_take isl_basic_map *bmap, int *progress)
+{
+ int i;
+ isl_size n_div;
+
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_basic_map_free(bmap);
+
+ for (i = 0; i < n_div; ++i) {
+ isl_bool eliminate;
+
+ eliminate = is_known_integral_div(bmap, i);
+ if (eliminate < 0)
+ return isl_basic_map_free(bmap);
+ if (!eliminate)
+ continue;
+
+ bmap = eliminate_integral_div(bmap, i);
+ mark_progress(progress);
+ i--;
+ n_div--;
+ }
+
+ return bmap;
+}
+
+static int n_pure_div_eq(__isl_keep isl_basic_map *bmap)
{
int i, j;
- unsigned total;
+ isl_size v_div;
- total = isl_space_dim(bmap->dim, isl_dim_all);
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return -1;
for (i = 0, j = bmap->n_div-1; i < bmap->n_eq; ++i) {
- while (j >= 0 && isl_int_is_zero(bmap->eq[i][1 + total + j]))
+ while (j >= 0 && isl_int_is_zero(bmap->eq[i][1 + v_div + j]))
--j;
if (j < 0)
break;
- if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total, j) != -1)
+ if (isl_seq_any_non_zero(bmap->eq[i] + 1 + v_div, j))
return 0;
}
return i;
@@ -926,7 +1114,7 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
int *progress)
{
int i, j, k;
- int total;
+ isl_size v_div;
int div_eq;
struct isl_mat *B;
struct isl_vec *d;
@@ -949,14 +1137,16 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS))
return bmap;
- total = isl_space_dim(bmap->dim, isl_dim_all);
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
div_eq = n_pure_div_eq(bmap);
+ if (v_div < 0 || div_eq < 0)
+ return isl_basic_map_free(bmap);
if (div_eq == 0)
return bmap;
if (div_eq < bmap->n_eq) {
B = isl_mat_sub_alloc6(bmap->ctx, bmap->eq, div_eq,
- bmap->n_eq - div_eq, 0, 1 + total);
+ bmap->n_eq - div_eq, 0, 1 + v_div);
C = isl_mat_variable_compression(B, &C2);
if (!C || !C2)
goto error;
@@ -972,11 +1162,11 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
if (!d)
goto error;
for (i = 0, j = bmap->n_div-1; i < div_eq; ++i) {
- while (j >= 0 && isl_int_is_zero(bmap->eq[i][1 + total + j]))
+ while (j >= 0 && isl_int_is_zero(bmap->eq[i][1 + v_div + j]))
--j;
- isl_int_set(d->block.data[i], bmap->eq[i][1 + total + j]);
+ isl_int_set(d->block.data[i], bmap->eq[i][1 + v_div + j]);
}
- B = isl_mat_sub_alloc6(bmap->ctx, bmap->eq, 0, div_eq, 0, 1 + total);
+ B = isl_mat_sub_alloc6(bmap->ctx, bmap->eq, 0, div_eq, 0, 1 + v_div);
if (C) {
B = isl_mat_product(B, C);
@@ -1007,11 +1197,12 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
dropped = 0;
for (j = bmap->n_div - 1; j >= 0; --j) {
for (i = 0; i < bmap->n_eq; ++i)
- if (!isl_int_is_zero(bmap->eq[i][1 + total + j]))
+ if (!isl_int_is_zero(bmap->eq[i][1 + v_div + j]))
break;
if (i < bmap->n_eq) {
bmap = isl_basic_map_drop_div(bmap, j);
- isl_basic_map_drop_equality(bmap, i);
+ if (isl_basic_map_drop_equality(bmap, i) < 0)
+ goto error;
++dropped;
}
}
@@ -1024,8 +1215,7 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
needed++;
}
if (needed > dropped) {
- bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
- needed, needed, 0);
+ bmap = isl_basic_map_extend(bmap, needed, needed, 0);
if (!bmap)
goto error;
}
@@ -1033,11 +1223,11 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
if (isl_int_is_one(T->row[i][i]))
continue;
k = isl_basic_map_alloc_div(bmap);
- pos[i] = 1 + total + k;
- isl_seq_clr(bmap->div[k] + 1, 1 + total + bmap->n_div);
+ pos[i] = 1 + v_div + k;
+ isl_seq_clr(bmap->div[k] + 1, 1 + v_div + bmap->n_div);
isl_int_set(bmap->div[k][0], T->row[i][i]);
if (C2)
- isl_seq_cpy(bmap->div[k] + 1, C2->row[i], 1 + total);
+ isl_seq_cpy(bmap->div[k] + 1, C2->row[i], 1 + v_div);
else
isl_int_set_si(bmap->div[k][1 + i], 1);
for (j = 0; j < i; ++j) {
@@ -1045,21 +1235,20 @@ static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,
continue;
if (pos[j] < T->n_row && C2)
isl_seq_submul(bmap->div[k] + 1, T->row[i][j],
- C2->row[pos[j]], 1 + total);
+ C2->row[pos[j]], 1 + v_div);
else
isl_int_neg(bmap->div[k][1 + pos[j]],
T->row[i][j]);
}
j = isl_basic_map_alloc_equality(bmap);
- isl_seq_neg(bmap->eq[j], bmap->div[k]+1, 1+total+bmap->n_div);
+ isl_seq_neg(bmap->eq[j], bmap->div[k]+1, 1+v_div+bmap->n_div);
isl_int_set(bmap->eq[j][pos[i]], bmap->div[k][0]);
}
free(pos);
isl_mat_free(C2);
isl_mat_free(T);
- if (progress)
- *progress = 1;
+ mark_progress(progress);
done:
ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
isl_mat_free(C);
isl_mat_free(C2);
isl_mat_free(T);
- return bmap;
+ isl_basic_map_free(bmap);
+ return NULL;
}
static __isl_give isl_basic_map *set_div_from_lower_bound(
__isl_take isl_basic_map *bmap, int div, int ineq)
{
- unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+ unsigned total = isl_basic_map_offset(bmap, isl_dim_div);
isl_seq_neg(bmap->div[div] + 1, bmap->ineq[ineq], total + bmap->n_div);
isl_int_set(bmap->div[div][0], bmap->ineq[ineq][total + div]);
int div, int ineq)
{
int j;
- unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+ unsigned total = isl_basic_map_offset(bmap, isl_dim_div);
/* Not defined in terms of unknown divs */
for (j = 0; j < bmap->n_div; ++j) {
static isl_bool better_div_constraint(__isl_keep isl_basic_map *bmap,
int div, int ineq)
{
- unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+ unsigned total = isl_basic_map_offset(bmap, isl_dim_div);
+ isl_size n_div = isl_basic_map_dim(bmap, isl_dim_div);
int last_div;
int last_ineq;
+ if (n_div < 0)
+ return isl_bool_error;
if (isl_int_is_zero(bmap->div[div][0]))
return isl_bool_true;
- if (isl_seq_last_non_zero(bmap->ineq[ineq] + total + div + 1,
- bmap->n_div - (div + 1)) >= 0)
+ if (isl_seq_any_non_zero(bmap->ineq[ineq] + total + div + 1,
+ n_div - (div + 1)))
return isl_bool_false;
last_ineq = isl_seq_last_non_zero(bmap->ineq[ineq], total + div);
- last_div = isl_seq_last_non_zero(bmap->div[div] + 1,
- total + bmap->n_div);
+ last_div = isl_seq_last_non_zero(bmap->div[div] + 1, total + n_div);
return last_ineq < last_div;
}
+/* Is the sequence of "len" coefficients "ineq" equal to "res"
+ * plus some non-trivial coefficients that are all a multiple of some number
+ * greater than "sum"?
+ * If so, this factor is stored in "gcd".
+ *
+ * The current implementation requires the coefficients
+ * in "res" to appear directly in "ineq", so that "gcd"
+ * is the gcd of the remaining coefficients.
+ * The same assumption is used in has_nested_unit_div.
+ */
+static int is_residue(isl_int *res, isl_int *ineq, isl_int sum, unsigned len,
+ isl_int *gcd)
+{
+ int j;
+
+ isl_int_set_si(*gcd, 0);
+ for (j = 0; j < len; ++j) {
+ if (!isl_int_is_zero(res[1 + j])) {
+ if (isl_int_eq(res[1 + j], ineq[1 + j]))
+ continue;
+ return 0;
+ }
+ if (!isl_int_is_zero(ineq[1 + j])) {
+ isl_int_gcd(*gcd, *gcd, ineq[1 + j]);
+ if (isl_int_le(*gcd, sum))
+ return 0;
+ }
+ }
+
+ return !isl_int_is_zero(*gcd);
+}
+
+/* Is
+ *
+ * (cst - cst2) mod n + sum
+ *
+ * greater than or equal to n?
+ */
+static int residue_exceeded(isl_int cst, isl_int cst2, isl_int n, isl_int sum)
+{
+ int exceeded;
+ isl_int t;
+
+ isl_int_init(t);
+ isl_int_sub(t, cst, cst2);
+ isl_int_fdiv_r(t, t, n);
+ isl_int_add(t, t, sum);
+ exceeded = isl_int_ge(t, n);
+ isl_int_clear(t);
+
+ return exceeded;
+}
+
+/* Given two constraints "k" and "l" that are opposite to each other,
+ * except for the constant term, with "sum" the sum of these constant terms,
+ * check if they can be used to simplify any integer division expression.
+ *
+ * In particular, let "k" and "l" be of the form
+ *
+ * f(x) >= 0
+ * -f(x) + c >= 0
+ *
+ * That is,
+ *
+ * 0 <= f(x) <= c
+ *
+ * Note that the same constraint holds for "k" and "l" interchanged, i.e.,
+ *
+ * 0 <= -f(x) + c <= c
+ *
+ * That is, the reasoning below holds for both "f(x)" and "-f(x) + c".
+ *
+ * If there is an integer division definition of the form
+ *
+ * floor((f(x) + n h(x) + c')/(n * m))
+ *
+ * with
+ *
+ * c' % n < n - c
+ *
+ * then it is equal to
+ *
+ * floor((h(x) + floor(c'/n))/m)
+ *
+ * because
+ *
+ * floor((f(x) + n h(x) + c')/(n * m))
+ * = floor((f(x) + c' % n + n (h(x) + floor(c'/n)))/(n * m))
+ *
+ * and
+ *
+ * 0 <= f(x) + c' % n < n
+ *
+ * Note that h(x) may be equal to zero, in which case the denominator
+ * of the integer division can be used as n (and m = 1).
+ */
+static __isl_give isl_basic_map *check_for_residues_in_divs(
+ __isl_take isl_basic_map *bmap, int k, int l, isl_int sum,
+ int *progress)
+{
+ int i;
+ int p;
+ isl_ctx *ctx;
+ isl_size n_div, total;
+
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (n_div < 0 || total < 0)
+ return isl_basic_map_free(bmap);
+
+ ctx = isl_basic_map_get_ctx(bmap);
+ p = isl_seq_last_non_zero(bmap->ineq[k] + 1, total);
+ for (i = 0; i < n_div; ++i) {
+ int c;
+ isl_bool unknown;
+
+ unknown = isl_basic_map_div_is_marked_unknown(bmap, i);
+ if (unknown < 0)
+ return isl_basic_map_free(bmap);
+ if (unknown)
+ continue;
+ if (isl_int_le(bmap->div[i][0], sum))
+ continue;
+ if (isl_int_eq(bmap->div[i][2 + p], bmap->ineq[k][1 + p]))
+ c = k;
+ else if (isl_int_eq(bmap->div[i][2 + p], bmap->ineq[l][1 + p]))
+ c = l;
+ else
+ continue;
+
+ if (isl_seq_eq(bmap->div[i] + 2, bmap->ineq[c] + 1, total))
+ isl_int_set(ctx->normalize_gcd, bmap->div[i][0]);
+ else if (!is_residue(bmap->ineq[c], bmap->div[i] + 1, sum,
+ total, &ctx->normalize_gcd))
+ continue;
+
+ if (residue_exceeded(bmap->div[i][1], bmap->ineq[c][0],
+ ctx->normalize_gcd, sum))
+ continue;
+
+ if (!isl_int_is_divisible_by(bmap->div[i][0],
+ ctx->normalize_gcd))
+ continue;
+
+ isl_seq_sub(bmap->div[i] + 1, bmap->ineq[c], 1 + total);
+ mark_progress(progress);
+ }
+
+ return bmap;
+}
+
+/* Is inequality "ineq" of "bmap" a constraint defining an integer division?
+ * "v_div" is the position of the first local variable.
+ * "n_div" is the number of local variables.
+ *
+ * A constraint defining an integer division must involve some local variable
+ * and could only possibly define the last local variable involved since
+ * it can only be defined in terms of earlier variables.
+ */
+static isl_bool is_div_constraint(__isl_keep isl_basic_map *bmap, int ineq,
+ unsigned v_div, unsigned n_div)
+{
+ int last;
+
+ last = isl_seq_last_non_zero(bmap->ineq[ineq] + 1 + v_div, n_div);
+ if (last < 0)
+ return isl_bool_false;
+ return isl_basic_map_is_div_constraint(bmap, bmap->ineq[ineq], last);
+}
+
+/* Does the inequality constraint "ineq" of "bmap" involve nested integer
+ * divisions with unit coefficient after removing the coefficients
+ * of inequality constraint "base"?
+ * "v_div" is the position of the first local variable.
+ * "n_div" is the number of local variables.
+ * "n" is the factor with which the constraint will be scaled down.
+ *
+ * Use the same simplifying assumption as "is_residue" that
+ * the coefficients in "base" appear directly in "ineq".
+ * Look for an integer division involving nested integer divisions
+ * that does not appear in "base" and does appear in "ineq"
+ * with a coefficient equal to "n" (up to a change of sign).
+ */
+static isl_bool has_nested_unit_div(__isl_keep isl_basic_map *bmap,
+ int base, int ineq, unsigned v_div, unsigned n_div, isl_int n)
+{
+ int j;
+
+ for (j = 0; j < n_div; ++j) {
+ isl_bool nested;
+
+ if (!isl_int_is_zero(bmap->ineq[base][1 + v_div + j]))
+ continue;
+ if (!isl_int_abs_eq(bmap->ineq[ineq][1 + v_div + j], n))
+ continue;
+ nested = isl_basic_map_div_expr_involves_vars(bmap, j,
+ v_div, n_div);
+ if (nested < 0 || nested)
+ return nested;
+ }
+
+ return isl_bool_false;
+}
+
+/* Given two constraints "k" and "l" that are opposite to each other,
+ * except for the constant term, with "sum" the sum of these constant terms,
+ * check if they can be used to simplify other constraints.
+ * Only do this for integer basic maps.
+ *
+ * In particular, let "k" and "l" be of the form
+ *
+ * f(x) >= 0
+ * -f(x) + c >= 0
+ *
+ * That is,
+ *
+ * 0 <= f(x) <= c
+ *
+ * Note that the same constraint holds for "k" and "l" interchanged, i.e.,
+ *
+ * 0 <= -f(x) + c <= c
+ *
+ * That is, the reasoning below holds for both "f(x)" and "-f(x) + c".
+ *
+ * If there is some other constraint
+ *
+ * g(x) >= 0
+ *
+ * such that
+ *
+ * g(x) - f(x) = n h(x) + c'
+ *
+ * with
+ *
+ * 0 <= c' < n - c
+ *
+ * in particular, for the constant term,
+ *
+ * (g(x) - f(x)) mod n + c < n
+ *
+ * then this other constraint is equivalent to
+ *
+ * h(x) >= 0
+ *
+ * (given "k" and "l") since
+ *
+ * 0 <= f(x) + c' < n
+ *
+ * Note that the constraint does not necessarily need to be scaled down here
+ * since it would otherwise also be scaled down
+ * by isl_basic_map_normalize_constraints, but since the scaling factor
+ * is already known here, it might as well be done immediately.
+ * Also note that the current implementation only checks for constraints
+ * where the coefficients of f(x) appear directly in g(x), while it would
+ * be sufficient for the differences with the corresponding coefficients
+ * in g(x) to be multiples of n.
+ *
+ * Similarly, if there is an integer division definition of the form
+ *
+ * floor((f(x) + n h(x) + c')/(n * m))
+ *
+ * with
+ *
+ * c' % n < n - c
+ *
+ * then it is equal to
+ *
+ * floor((h(x) + floor(c'/n))/m)
+ *
+ *
+ * Do not apply any simplification to constraint(s) defining integer divisions.
+ * Such constraints would first be simplified to be of the form
+ *
+ * e + c'' >= 0
+ *
+ * and then the integer division definition would be plugged into
+ * this constraint, resulting in the original constraint and
+ * causing an infinite loop.
+ * Simplifying the integer division definitions as well mitigates
+ * some (possibly all) of this effect, but it is too fragile to rely on
+ * for avoiding infinite loops.
+ *
+ * If any nested integer divisions are involved, then a similar effect
+ * may be obtained even on constraints that do not (obviously)
+ * define an integer division through multiple steps of such substitutions.
+ * Any constraint that would result in an integer division with nested
+ * integer divisions and a unit coefficient is therefore also left untouched.
+ */
+static __isl_give isl_basic_map *check_for_residues(
+ __isl_take isl_basic_map *bmap, int k, int l, isl_int sum,
+ int *progress)
+{
+ int i;
+ int p;
+ isl_ctx *ctx;
+ isl_bool rat;
+ isl_size n_ineq, total, v_div, n_div;
+
+ rat = isl_basic_map_is_rational(bmap);
+ n_ineq = isl_basic_map_n_inequality(bmap);
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (rat < 0 || n_ineq < 0 || total < 0 || v_div < 0 || n_div < 0)
+ return isl_basic_map_free(bmap);
+ if (rat)
+ return bmap;
+
+ bmap = check_for_residues_in_divs(bmap, k, l, sum, progress);
+ if (!bmap)
+ return bmap;
+
+ ctx = isl_basic_map_get_ctx(bmap);
+ p = isl_seq_last_non_zero(bmap->ineq[k] + 1, total);
+ for (i = 0; i < n_ineq; ++i) {
+ isl_bool skip;
+ int c;
+
+ if (i == k || i == l)
+ continue;
+ if (isl_int_is_zero(bmap->ineq[i][1 + p]))
+ continue;
+ skip = is_div_constraint(bmap, i, v_div, n_div);
+ if (skip < 0)
+ return isl_basic_map_free(bmap);
+ if (skip)
+ continue;
+ if (isl_int_eq(bmap->ineq[i][1 + p], bmap->ineq[k][1 + p]))
+ c = k;
+ else if (isl_int_eq(bmap->ineq[i][1 + p], bmap->ineq[l][1 + p]))
+ c = l;
+ else
+ continue;
+
+ if (!is_residue(bmap->ineq[c], bmap->ineq[i], sum, total,
+ &ctx->normalize_gcd))
+ continue;
+
+ skip = has_nested_unit_div(bmap, c, i, v_div, n_div,
+ ctx->normalize_gcd);
+ if (skip < 0)
+ return isl_basic_map_free(bmap);
+ if (skip)
+ continue;
+ if (residue_exceeded(bmap->ineq[i][0], bmap->ineq[c][0],
+ ctx->normalize_gcd, sum))
+ continue;
+
+ isl_seq_sub(bmap->ineq[i], bmap->ineq[c], 1 + total);
+ bmap = scale_down_inequality(bmap, i, ctx->normalize_gcd,
+ total);
+ if (!bmap)
+ return NULL;
+ mark_progress(progress);
+ }
+
+ return bmap;
+}
+
/* Given two constraints "k" and "l" that are opposite to each other,
* except for the constant term, check if we can use them
* to obtain an expression for one of the hitherto unknown divs or
* a "better" expression for a div for which we already have an expression.
* "sum" is the sum of the constant terms of the constraints.
* If this sum is strictly smaller than the coefficient of one
- * of the divs, then this pair can be used define the div.
+ * of the divs, then this pair can be used to define the div.
* To avoid the introduction of circular definitions of divs, we
* do not use the pair if the resulting expression would refer to
* any other undefined divs or if any known div is defined in
int *progress)
{
int i;
- unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+ unsigned total = isl_basic_map_offset(bmap, isl_dim_div);
for (i = 0; i < bmap->n_div; ++i) {
isl_bool set_div;
bmap = set_div_from_lower_bound(bmap, i, k);
else
bmap = set_div_from_lower_bound(bmap, i, l);
- if (progress)
- *progress = 1;
+ mark_progress(progress);
break;
}
return bmap;
}
+/* Look for pairs of constraints that have equal or opposite coefficients.
+ * For each pair of constraints with equal coefficients, only keep
+ * the one which imposes the most stringent constraint, i.e.,
+ * the one with the smallest constant term.
+ * For each pair of constraints with opposite coefficients,
+ * consider the sum of the constant terms.
+ * If the sum is smaller than zero, then the constraints conflict.
+ * If the sum is equal to zero, then the constraints form
+ * an equality constraint.
+ * If the sum is greater than zero, then check whether this pair
+ * can be used to simplify any other constraints and/or,
+ * if "detect_divs" is set, whether a (better) integer division definition
+ * can be read off from the pair.
+ */
__isl_give isl_basic_map *isl_basic_map_remove_duplicate_constraints(
__isl_take isl_basic_map *bmap, int *progress, int detect_divs)
{
struct isl_constraint_index ci;
int k, l, h;
- unsigned total = isl_basic_map_total_dim(bmap);
+ isl_size total = isl_basic_map_dim(bmap, isl_dim_all);
isl_int sum;
- if (!bmap || bmap->n_ineq <= 1)
+ if (total < 0 || bmap->n_ineq <= 1)
return bmap;
if (create_constraint_index(&ci, bmap) < 0)
ci.index[h] = &bmap->ineq[k];
continue;
}
- if (progress)
- *progress = 1;
l = ci.index[h] - &bmap->ineq[0];
if (isl_int_lt(bmap->ineq[k][0], bmap->ineq[l][0]))
swap_inequality(bmap, k, l);
--k;
}
isl_int_init(sum);
- for (k = 0; k < bmap->n_ineq-1; ++k) {
+ for (k = 0; bmap && k < bmap->n_ineq-1; ++k) {
isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);
h = hash_index(&ci, bmap, k);
isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);
l = ci.index[h] - &bmap->ineq[0];
isl_int_add(sum, bmap->ineq[k][0], bmap->ineq[l][0]);
if (isl_int_is_pos(sum)) {
+ int residue = 0;
+
+ bmap = check_for_residues(bmap, k, l, sum, &residue);
if (detect_divs)
bmap = check_for_div_constraints(bmap, k, l,
sum, progress);
- continue;
+ if (!residue)
+ continue;
+ mark_progress(progress);
+ break;
}
if (isl_int_is_zero(sum)) {
/* We need to break out of the loop after these
* will no longer be valid.
* Plus, we probably we want to regauss first.
*/
- if (progress)
- *progress = 1;
+ mark_progress(progress);
isl_basic_map_drop_inequality(bmap, l);
isl_basic_map_inequality_to_equality(bmap, k);
} else
duplicate = 0;
bmap = isl_basic_map_remove_duplicate_constraints(bmap,
&duplicate, 0);
- if (progress && duplicate)
- *progress = 1;
+ if (duplicate)
+ mark_progress(progress);
} while (duplicate);
return bmap;
}
-/* Eliminate knowns divs from constraints where they appear with
- * a (positive or negative) unit coefficient.
+/* Given a known integer division "div" that is not integral
+ * (with denominator 1), eliminate it from the constraints in "bmap"
+ * where it appears with a (positive or negative) unit coefficient.
+ * If "progress" is not NULL, then it gets set if the elimination
+ * results in any changes.
*
* That is, replace
*
* being modified by this function. The modified constraint may
* no longer imply this div constraint, so we add it back to make
* sure we do not lose any information.
- *
- * We skip integral divs, i.e., those with denominator 1, as we would
- * risk eliminating the div from the div constraints. We do not need
- * to handle those divs here anyway since the div constraints will turn
- * out to form an equality and this equality can then be used to eliminate
- * the div from all constraints.
*/
-static __isl_give isl_basic_map *eliminate_unit_divs(
- __isl_take isl_basic_map *bmap, int *progress)
+static __isl_give isl_basic_map *eliminate_unit_div(
+ __isl_take isl_basic_map *bmap, int div, int *progress)
{
- int i, j;
+ int j;
+ isl_size v_div, dim;
isl_ctx *ctx;
- unsigned total;
- if (!bmap)
- return NULL;
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ dim = isl_basic_map_dim(bmap, isl_dim_all);
+ if (v_div < 0 || dim < 0)
+ return isl_basic_map_free(bmap);
ctx = isl_basic_map_get_ctx(bmap);
- total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
- for (i = 0; i < bmap->n_div; ++i) {
- if (isl_int_is_zero(bmap->div[i][0]))
- continue;
- if (isl_int_is_one(bmap->div[i][0]))
+ for (j = 0; j < bmap->n_ineq; ++j) {
+ int s;
+
+ if (!isl_int_is_one(bmap->ineq[j][1 + v_div + div]) &&
+ !isl_int_is_negone(bmap->ineq[j][1 + v_div + div]))
continue;
- for (j = 0; j < bmap->n_ineq; ++j) {
- int s;
- if (!isl_int_is_one(bmap->ineq[j][total + i]) &&
- !isl_int_is_negone(bmap->ineq[j][total + i]))
- continue;
+ mark_progress(progress);
- *progress = 1;
+ s = isl_int_sgn(bmap->ineq[j][1 + v_div + div]);
+ isl_int_set_si(bmap->ineq[j][1 + v_div + div], 0);
+ if (s < 0)
+ isl_seq_combine(bmap->ineq[j],
+ ctx->negone, bmap->div[div] + 1,
+ bmap->div[div][0], bmap->ineq[j], 1 + dim);
+ else
+ isl_seq_combine(bmap->ineq[j],
+ ctx->one, bmap->div[div] + 1,
+ bmap->div[div][0], bmap->ineq[j], 1 + dim);
+ if (s < 0) {
+ isl_int_add(bmap->ineq[j][0],
+ bmap->ineq[j][0], bmap->div[div][0]);
+ isl_int_sub_ui(bmap->ineq[j][0],
+ bmap->ineq[j][0], 1);
+ }
- s = isl_int_sgn(bmap->ineq[j][total + i]);
- isl_int_set_si(bmap->ineq[j][total + i], 0);
- if (s < 0)
- isl_seq_combine(bmap->ineq[j],
- ctx->negone, bmap->div[i] + 1,
- bmap->div[i][0], bmap->ineq[j],
- total + bmap->n_div);
- else
- isl_seq_combine(bmap->ineq[j],
- ctx->one, bmap->div[i] + 1,
- bmap->div[i][0], bmap->ineq[j],
- total + bmap->n_div);
- if (s < 0) {
- isl_int_add(bmap->ineq[j][0],
- bmap->ineq[j][0], bmap->div[i][0]);
- isl_int_sub_ui(bmap->ineq[j][0],
- bmap->ineq[j][0], 1);
- }
+ bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
+ bmap = isl_basic_map_add_div_constraint(bmap, div, s);
+ if (!bmap)
+ return NULL;
+ }
- bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
- if (isl_basic_map_add_div_constraint(bmap, i, s) < 0)
- return isl_basic_map_free(bmap);
- }
+ return bmap;
+}
+
+/* Eliminate selected known divs from constraints where they appear with
+ * a (positive or negative) unit coefficient.
+ * In particular, only handle those for which "select" returns isl_bool_true.
+ * If "progress" is not NULL, then it gets set if the elimination
+ * results in any changes.
+ *
+ * We skip integral divs, i.e., those with denominator 1, as we would
+ * risk eliminating the div from the div constraints.
+ * They are eliminated in eliminate_integral_divs instead.
+ */
+static __isl_give isl_basic_map *eliminate_selected_unit_divs(
+ __isl_take isl_basic_map *bmap,
+ isl_bool (*select)(__isl_keep isl_basic_map *bmap, int div),
+ int *progress)
+{
+ int i;
+ isl_size n_div;
+
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_basic_map_free(bmap);
+
+ for (i = 0; i < n_div; ++i) {
+ isl_bool skip;
+ isl_bool selected;
+
+ skip = isl_basic_map_div_is_marked_unknown(bmap, i);
+ if (skip >= 0 && !skip)
+ skip = isl_basic_map_div_is_integral(bmap, i);
+ if (skip < 0)
+ return isl_basic_map_free(bmap);
+ if (skip)
+ continue;
+ selected = select(bmap, i);
+ if (selected < 0)
+ return isl_basic_map_free(bmap);
+ if (!selected)
+ continue;
+ bmap = eliminate_unit_div(bmap, i, progress);
+ if (!bmap)
+ return NULL;
}
return bmap;
}
+/* eliminate_selected_unit_divs callback that selects every
+ * integer division.
+ */
+static isl_bool is_any_div(__isl_keep isl_basic_map *bmap, int div)
+{
+ return isl_bool_true;
+}
+
+/* Eliminate known divs from constraints where they appear with
+ * a (positive or negative) unit coefficient.
+ * If "progress" is not NULL, then it gets set if the elimination
+ * results in any changes.
+ */
+static __isl_give isl_basic_map *eliminate_unit_divs(
+ __isl_take isl_basic_map *bmap, int *progress)
+{
+ return eliminate_selected_unit_divs(bmap, &is_any_div, progress);
+}
+
+/* eliminate_selected_unit_divs callback that selects
+ * integer divisions that only appear with
+ * a (positive or negative) unit coefficient
+ * (outside their div constraints).
+ */
+static isl_bool is_pure_unit_div(__isl_keep isl_basic_map *bmap, int div)
+{
+ int i;
+ isl_size v_div, n_ineq;
+
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ n_ineq = isl_basic_map_n_inequality(bmap);
+ if (v_div < 0 || n_ineq < 0)
+ return isl_bool_error;
+
+ for (i = 0; i < n_ineq; ++i) {
+ isl_bool skip;
+
+ if (isl_int_is_zero(bmap->ineq[i][1 + v_div + div]))
+ continue;
+ skip = isl_basic_map_is_div_constraint(bmap,
+ bmap->ineq[i], div);
+ if (skip < 0)
+ return isl_bool_error;
+ if (skip)
+ continue;
+ if (!isl_int_is_one(bmap->ineq[i][1 + v_div + div]) &&
+ !isl_int_is_negone(bmap->ineq[i][1 + v_div + div]))
+ return isl_bool_false;
+ }
+
+ return isl_bool_true;
+}
+
+/* Eliminate known divs from constraints where they appear with
+ * a (positive or negative) unit coefficient,
+ * but only if they do not appear in any other constraints
+ * (other than the div constraints).
+ */
+__isl_give isl_basic_map *isl_basic_map_eliminate_pure_unit_divs(
+ __isl_take isl_basic_map *bmap)
+{
+ return eliminate_selected_unit_divs(bmap, &is_pure_unit_div, NULL);
+}
+
__isl_give isl_basic_map *isl_basic_map_simplify(__isl_take isl_basic_map *bmap)
{
int progress = 1;
@@ -1394,18 +2062,18 @@ __isl_give isl_basic_map *isl_basic_map_simplify(__isl_take isl_basic_map *bmap)
bmap = eliminate_unit_divs(bmap, &progress);
bmap = eliminate_divs_eq(bmap, &progress);
bmap = eliminate_divs_ineq(bmap, &progress);
+ bmap = eliminate_integral_divs(bmap, &progress);
bmap = isl_basic_map_gauss(bmap, &progress);
/* requires equalities in normal form */
bmap = normalize_divs(bmap, &progress);
bmap = isl_basic_map_remove_duplicate_constraints(bmap,
&progress, 1);
- if (bmap && progress)
- ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
}
return bmap;
}
-struct isl_basic_set *isl_basic_set_simplify(struct isl_basic_set *bset)
+__isl_give isl_basic_set *isl_basic_set_simplify(
+ __isl_take isl_basic_set *bset)
{
return bset_from_bmap(isl_basic_map_simplify(bset_to_bmap(bset)));
}
if (!bmap)
return isl_bool_error;
- pos = 1 + isl_space_dim(bmap->dim, isl_dim_all) + div;
+ pos = isl_basic_map_offset(bmap, isl_dim_div) + div;
if (isl_int_eq(constraint[pos], bmap->div[div][0])) {
int neg;
bmap->div[div][1], bmap->div[div][0]);
if (!neg)
return isl_bool_false;
- if (isl_seq_first_non_zero(constraint+pos+1,
- bmap->n_div-div-1) != -1)
+ if (isl_seq_any_non_zero(constraint+pos+1,
+ bmap->n_div-div-1))
return isl_bool_false;
} else if (isl_int_abs_eq(constraint[pos], bmap->div[div][0])) {
if (!isl_seq_eq(constraint, bmap->div[div]+1, pos))
return isl_bool_false;
- if (isl_seq_first_non_zero(constraint+pos+1,
- bmap->n_div-div-1) != -1)
+ if (isl_seq_any_non_zero(constraint+pos+1,
+ bmap->n_div-div-1))
return isl_bool_false;
} else
return isl_bool_false;
return isl_bool_true;
}
-isl_bool 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
*
static isl_bool div_is_redundant(__isl_keep isl_basic_map *bmap, int div)
{
int i;
- unsigned pos = 1 + isl_space_dim(bmap->dim, isl_dim_all) + div;
+ isl_bool involves;
+ isl_size v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ unsigned pos = 1 + v_div + div;
+
+ if (v_div < 0)
+ return isl_bool_error;
for (i = 0; i < bmap->n_eq; ++i)
if (!isl_int_is_zero(bmap->eq[i][pos]))
return red;
}
- 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+pos]))
- return isl_bool_false;
- }
+ involves = isl_basic_map_any_div_involves_vars(bmap, v_div + div, 1);
+ if (involves < 0 || involves)
+ return isl_bool_not(involves);
return isl_bool_true;
}
__isl_take isl_basic_map *bmap)
{
int i;
+ isl_size v_div;
- if (!bmap)
- return NULL;
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return isl_basic_map_free(bmap);
for (i = bmap->n_div-1; i >= 0; --i) {
isl_bool redundant;
return isl_basic_map_free(bmap);
if (!redundant)
continue;
+ bmap = isl_basic_map_drop_constraints_involving(bmap,
+ v_div + i, 1);
bmap = isl_basic_map_drop_div(bmap, i);
}
return bmap;
@@ -1540,7 +2207,8 @@ __isl_give isl_basic_map *isl_basic_map_finalize(__isl_take isl_basic_map *bmap)
return bmap;
}
-struct isl_basic_set *isl_basic_set_finalize(struct isl_basic_set *bset)
+__isl_give isl_basic_set *isl_basic_set_finalize(
+ __isl_take isl_basic_set *bset)
{
return bset_from_bmap(isl_basic_map_finalize(bset_to_bmap(bset)));
}
{
int d;
int i, j, k;
- unsigned total;
+ isl_size total;
int need_gauss = 0;
if (n == 0)
return bmap;
- if (!bmap)
- return NULL;
- total = isl_basic_map_total_dim(bmap);
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_basic_map_free(bmap);
bmap = isl_basic_map_cow(bmap);
for (d = pos + n - 1; d >= 0 && d >= pos; --d)
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], 0, NULL);
- isl_basic_map_drop_equality(bmap, i);
+ bmap = eliminate_var_using_equality(bmap, d,
+ bmap->eq[i], 0, 1, NULL);
+ if (isl_basic_map_drop_equality(bmap, i) < 0)
+ return isl_basic_map_free(bmap);
need_gauss = 1;
break;
}
break;
}
}
- ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
if (need_gauss)
bmap = isl_basic_map_gauss(bmap, NULL);
return bmap;
return NULL;
}
-struct isl_basic_set *isl_basic_set_eliminate_vars(
- struct isl_basic_set *bset, unsigned pos, unsigned n)
+__isl_give isl_basic_set *isl_basic_set_eliminate_vars(
+ __isl_take isl_basic_set *bset, unsigned pos, unsigned n)
{
return bset_from_bmap(isl_basic_map_eliminate_vars(bset_to_bmap(bset),
pos, n));
if (n == 0)
return bmap;
- 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);
+ if (isl_basic_map_check_range(bmap, type, first, n) < 0)
+ return isl_basic_map_free(bmap);
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
first += isl_basic_map_offset(bmap, type) - 1;
bmap = isl_basic_map_insert_dims(bmap, type, first, n);
bmap = isl_basic_map_reset_space(bmap, space);
return bmap;
-error:
- isl_basic_map_free(bmap);
- return NULL;
}
__isl_give isl_basic_set *isl_basic_set_eliminate(
* Therefore, start over after calling
* isl_basic_map_drop_constraints_involving_dims.
*/
-__isl_give isl_basic_map *isl_basic_map_drop_constraint_involving_unknown_divs(
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_unknown_divs(
__isl_take isl_basic_map *bmap)
{
isl_bool known;
- int i, n_div, o_div;
+ isl_size n_div;
+ int i, o_div;
known = isl_basic_map_divs_known(bmap);
if (known < 0)
@@ -1740,6 +2406,8 @@ __isl_give isl_basic_map *isl_basic_map_drop_constraint_involving_unknown_divs(
return bmap;
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_basic_map_free(bmap);
o_div = isl_basic_map_offset(bmap, isl_dim_div) - 1;
for (i = 0; i < n_div; ++i) {
@@ -1751,22 +2419,35 @@ __isl_give isl_basic_map *isl_basic_map_drop_constraint_involving_unknown_divs(
bmap = remove_dependent_vars(bmap, o_div + i);
bmap = isl_basic_map_drop_constraints_involving_dims(bmap,
isl_dim_div, i, 1);
- if (!bmap)
- return NULL;
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_basic_map_free(bmap);
i = -1;
}
return bmap;
}
+/* Remove all constraints from "bset" that reference any unknown local
+ * variables (directly or indirectly).
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_unknown_divs(
+ __isl_take isl_basic_set *bset)
+{
+ isl_basic_map *bmap;
+
+ bmap = bset_to_bmap(bset);
+ bmap = isl_basic_map_drop_constraints_involving_unknown_divs(bmap);
+ return bset_from_bmap(bmap);
+}
+
/* Remove all constraints from "map" that reference any unknown local
* variables (directly or indirectly).
*
* Since constraints may get dropped from the basic maps,
* they may no longer be disjoint from each other.
*/
-__isl_give isl_map *isl_map_drop_constraint_involving_unknown_divs(
+__isl_give isl_map *isl_map_drop_constraints_involving_unknown_divs(
__isl_take isl_map *map)
{
int i;
for (i = 0; i < map->n; ++i) {
map->p[i] =
- isl_basic_map_drop_constraint_involving_unknown_divs(
+ isl_basic_map_drop_constraints_involving_unknown_divs(
map->p[i]);
if (!map->p[i])
return isl_map_free(map);
/* Don't assume equalities are in order, because align_divs
* may have changed the order of the divs.
*/
-static void compute_elimination_index(__isl_keep isl_basic_map *bmap, int *elim)
+static void compute_elimination_index(__isl_keep isl_basic_map *bmap, int *elim,
+ unsigned len)
{
int d, i;
- unsigned total;
- total = isl_space_dim(bmap->dim, isl_dim_all);
- for (d = 0; d < total; ++d)
+ for (d = 0; d < len; ++d)
elim[d] = -1;
for (i = 0; i < bmap->n_eq; ++i) {
- for (d = total - 1; d >= 0; --d) {
+ for (d = len - 1; d >= 0; --d) {
if (isl_int_is_zero(bmap->eq[i][1+d]))
continue;
elim[d] = i;
@@ -1818,19 +2498,17 @@ static void compute_elimination_index(__isl_keep isl_basic_map *bmap, int *elim)
}
static void set_compute_elimination_index(__isl_keep isl_basic_set *bset,
- int *elim)
+ int *elim, unsigned len)
{
- compute_elimination_index(bset_to_bmap(bset), elim);
+ compute_elimination_index(bset_to_bmap(bset), elim, len);
}
static int reduced_using_equalities(isl_int *dst, isl_int *src,
- __isl_keep isl_basic_map *bmap, int *elim)
+ __isl_keep isl_basic_map *bmap, int *elim, unsigned total)
{
int d;
int copied = 0;
- unsigned total;
- total = isl_space_dim(bmap->dim, isl_dim_all);
for (d = total - 1; d >= 0; --d) {
if (isl_int_is_zero(src[1+d]))
continue;
}
static int set_reduced_using_equalities(isl_int *dst, isl_int *src,
- __isl_keep isl_basic_set *bset, int *elim)
+ __isl_keep isl_basic_set *bset, int *elim, unsigned total)
{
return reduced_using_equalities(dst, src,
- bset_to_bmap(bset), elim);
+ bset_to_bmap(bset), elim, total);
}
static __isl_give isl_basic_set *isl_basic_set_reduce_using_equalities(
{
int i;
int *elim;
+ isl_size dim;
if (!bset || !context)
goto error;
}
bset = isl_basic_set_cow(bset);
- if (!bset)
+ dim = isl_basic_set_dim(bset, isl_dim_set);
+ if (dim < 0)
goto error;
- elim = isl_alloc_array(bset->ctx, int, isl_basic_set_n_dim(bset));
+ elim = isl_alloc_array(bset->ctx, int, dim);
if (!elim)
goto error;
- set_compute_elimination_index(context, elim);
+ set_compute_elimination_index(context, elim, dim);
for (i = 0; i < bset->n_eq; ++i)
set_reduced_using_equalities(bset->eq[i], bset->eq[i],
- context, elim);
+ context, elim, dim);
for (i = 0; i < bset->n_ineq; ++i)
set_reduced_using_equalities(bset->ineq[i], bset->ineq[i],
- context, elim);
+ context, elim, dim);
isl_basic_set_free(context);
free(elim);
bset = isl_basic_set_simplify(bset);
__isl_keep isl_basic_set *context, int *row)
{
struct isl_constraint_index ci;
- int n_ineq;
+ isl_size n_ineq, cols;
unsigned total;
int k;
return isl_stat_error;
n_ineq = isl_mat_rows(ineq);
- total = isl_mat_cols(ineq) - 1;
+ cols = isl_mat_cols(ineq);
+ if (n_ineq < 0 || cols < 0)
+ return isl_stat_error;
+ total = cols - 1;
for (k = 0; k < n_ineq; ++k) {
int l;
isl_bool redundant;
return bmap;
}
- context = isl_basic_map_align_divs(context, bmap);
+ context = isl_basic_map_drop_constraints_involving_unknown_divs(
+ context);
+ context = isl_basic_map_remove_unknown_divs(context);
+
+ context = isl_basic_map_order_divs(context);
bmap = isl_basic_map_align_divs(bmap, context);
+ context = isl_basic_map_align_divs(context, bmap);
bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
bset_context = isl_basic_map_underlying_set(context);
static __isl_give isl_basic_map *drop_unrelated_constraints(
__isl_take isl_basic_map *bmap, int *relevant)
{
- int i, dim;
+ int i;
+ isl_size dim;
dim = isl_basic_map_dim(bmap, isl_dim_all);
+ if (dim < 0)
+ return isl_basic_map_free(bmap);
for (i = 0; i < dim; ++i)
if (!relevant[i])
break;
static int *alloc_groups(__isl_keep isl_basic_set *context)
{
isl_ctx *ctx;
- int dim;
+ isl_size dim;
dim = isl_basic_set_dim(context, isl_dim_set);
+ if (dim < 0)
+ return NULL;
ctx = isl_basic_set_get_ctx(context);
return isl_calloc_array(ctx, int, dim);
}
__isl_give isl_basic_map *isl_basic_map_drop_unrelated_constraints(
__isl_take isl_basic_map *bmap, __isl_take int *group)
{
- int dim;
+ isl_size dim;
int i;
int last;
- if (!bmap)
- return NULL;
-
dim = isl_basic_map_dim(bmap, isl_dim_all);
+ if (dim < 0)
+ goto error;
last = -1;
for (i = 0; i < dim; ++i)
free(group);
return bmap;
+error:
+ free(group);
+ isl_basic_map_free(bmap);
+ return NULL;
}
/* Drop constraints from "context" that are irrelevant for computing
__isl_take isl_basic_set *context, __isl_keep isl_basic_set *bset)
{
int *group;
- int dim;
+ isl_size dim;
int i, j;
- if (!context || !bset)
+ dim = isl_basic_set_dim(bset, isl_dim_set);
+ if (!context || dim < 0)
return isl_basic_set_free(context);
group = alloc_groups(context);
if (!group)
return isl_basic_set_free(context);
- dim = isl_basic_set_dim(bset, isl_dim_set);
for (i = 0; i < dim; ++i) {
for (j = 0; j < bset->n_eq; ++j)
if (!isl_int_is_zero(bset->eq[j][1 + i]))
__isl_take isl_basic_set *context, __isl_keep isl_mat *ineq, int *row)
{
int *group;
- int dim;
- int i, j, n;
+ isl_size dim;
+ int i, j;
+ isl_size n;
- if (!context || !ineq)
+ dim = isl_basic_set_dim(context, isl_dim_set);
+ n = isl_mat_rows(ineq);
+ if (dim < 0 || n < 0)
return isl_basic_set_free(context);
group = alloc_groups(context);
if (!group)
return isl_basic_set_free(context);
- dim = isl_basic_set_dim(context, isl_dim_set);
- n = isl_mat_rows(ineq);
for (i = 0; i < dim; ++i) {
for (j = 0; j < n; ++j) {
if (row[j] < 0)
@@ -2431,8 +3128,7 @@ static __isl_give isl_basic_set *uset_gist_full(__isl_take isl_basic_set *bset,
if (tab->con[n_eq + r].is_redundant)
continue;
test = isl_basic_set_dup(combined);
- if (isl_inequality_negate(test, r) < 0)
- test = isl_basic_set_free(test);
+ test = isl_inequality_negate(test, r);
test = isl_basic_set_update_from_tab(test, tab);
is_empty = isl_basic_set_is_empty(test);
isl_basic_set_free(test);
*/
static __isl_give isl_mat *extract_ineq(__isl_keep isl_basic_set *bset)
{
- unsigned total;
+ isl_size total;
isl_ctx *ctx;
isl_mat *ineq;
- if (!bset)
+ total = isl_basic_set_dim(bset, isl_dim_all);
+ if (total < 0)
return NULL;
ctx = isl_basic_set_get_ctx(bset);
- total = isl_basic_set_total_dim(bset);
ineq = isl_mat_sub_alloc6(ctx, bset->ineq, 0, bset->n_ineq,
0, 1 + total);
return uset_gist_full(bset, ineq, context);
}
+/* Replace "bset" by an empty basic set in the same space.
+ */
+static __isl_give isl_basic_set *replace_by_empty(
+ __isl_take isl_basic_set *bset)
+{
+ isl_space *space;
+
+ space = isl_basic_set_get_space(bset);
+ isl_basic_set_free(bset);
+ return isl_basic_set_empty(space);
+}
+
/* Remove all information from "bset" that is redundant in the context
* of "context", for the case where the combined equalities of
* "bset" and "context" allow for a compression that can be obtained
* by preapplication of "T".
+ * If the compression of "context" is empty, meaning that "bset" and
+ * "context" do not intersect, then return the empty set.
*
* "bset" itself is not transformed by "T". Instead, the inequalities
* are extracted from "bset" and those are transformed by "T".
{
isl_ctx *ctx;
isl_mat *ineq;
- int i, n_row, n_col;
+ int i;
+ isl_size n_row, n_col;
isl_int rem;
ineq = extract_ineq(bset);
if (isl_basic_set_plain_is_empty(context)) {
isl_mat_free(ineq);
isl_basic_set_free(context);
- return isl_basic_set_set_to_empty(bset);
+ return replace_by_empty(bset);
}
ctx = isl_mat_get_ctx(ineq);
n_row = isl_mat_rows(ineq);
n_col = isl_mat_cols(ineq);
+ if (n_row < 0 || n_col < 0)
+ goto error;
isl_int_init(rem);
for (i = 0; i < n_row; ++i) {
isl_seq_gcd(ineq->row[i] + 1, n_col - 1, &ctx->normalize_gcd);
static __isl_give isl_basic_set *project_onto_involved(
__isl_take isl_basic_set *bset, __isl_keep isl_basic_set *template)
{
- int i, n;
-
- if (!bset || !template)
- return isl_basic_set_free(bset);
+ int i;
+ isl_size n;
n = isl_basic_set_dim(template, isl_dim_set);
+ if (n < 0 || !template)
+ return isl_basic_set_free(bset);
for (i = 0; i < n; ++i) {
isl_bool involved;
* compute the gist inside this intersection and then reduce
* the constraints with respect to the equalities of the context
* that only involve variables already involved in the input.
+ * If the intersection of the affine hulls turns out to be empty,
+ * then return the empty set.
*
* If two constraints are mutually redundant, then uset_gist_full
* will remove the second of those constraints. We therefore first
isl_mat *T;
isl_basic_set *aff;
isl_basic_set *aff_context;
- unsigned total;
+ isl_size total;
- if (!bset || !context)
+ total = isl_basic_set_dim(bset, isl_dim_all);
+ if (total < 0 || !context)
goto error;
context = drop_irrelevant_constraints(context, bset);
isl_basic_set_free(aff);
return uset_gist_uncompressed(bset, context);
}
- total = isl_basic_set_total_dim(bset);
eq = isl_mat_sub_alloc6(bset->ctx, aff->eq, 0, aff->n_eq, 0, 1 + total);
eq = isl_mat_cow(eq);
T = isl_mat_variable_compression(eq, NULL);
if (T && T->n_col == 0) {
isl_mat_free(T);
isl_basic_set_free(context);
- return isl_basic_set_set_to_empty(bset);
+ return replace_by_empty(bset);
}
aff_context = isl_basic_set_affine_hull(isl_basic_set_copy(context));
static int n_div_eq(__isl_keep isl_basic_map *bmap)
{
int i;
- int total, n_div;
+ isl_size total, n_div;
if (!bmap)
return -1;
total = isl_basic_map_dim(bmap, isl_dim_all);
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (total < 0 || n_div < 0)
+ return -1;
total -= n_div;
for (i = 0; i < bmap->n_eq; ++i)
- if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total,
- n_div) == -1)
+ if (!isl_seq_any_non_zero(bmap->eq[i] + 1 + total, n_div))
return i;
return bmap->n_eq;
__isl_take isl_space *space, __isl_take isl_mat *eq)
{
int i, k;
+ isl_size total;
isl_basic_map *bmap = NULL;
- if (!space || !eq)
+ total = isl_space_dim(space, isl_dim_all);
+ if (total < 0 || !eq)
goto error;
- if (1 + isl_space_dim(space, isl_dim_all) != eq->n_col)
+ if (1 + total != eq->n_col)
isl_die(isl_space_get_ctx(space), isl_error_internal,
"unexpected number of columns", goto error);
__isl_keep isl_basic_map *bmap, int bmap_n_eq,
__isl_keep isl_basic_map *context, int context_n_eq)
{
- int total, n_div;
+ isl_size total, n_div;
isl_ctx *ctx;
isl_mat *A, *B, *T, *V;
total = isl_basic_map_dim(context, isl_dim_all);
n_div = isl_basic_map_dim(context, isl_dim_div);
+ if (total < 0 || n_div < 0)
+ return NULL;
total -= n_div;
ctx = isl_basic_map_get_ctx(bmap);
T = isl_mat_product(V, T);
n_div = isl_basic_map_dim(bmap, isl_dim_div);
- T = isl_mat_diagonal(T, isl_mat_identity(ctx, n_div));
+ if (n_div < 0)
+ T = isl_mat_free(T);
+ else
+ T = isl_mat_diagonal(T, isl_mat_identity(ctx, n_div));
A = isl_mat_sub_alloc6(ctx, bmap->eq,
0, bmap_n_eq, 0, 1 + total + n_div);
__isl_take isl_basic_map *bmap, int n, __isl_keep isl_mat *A)
{
int i;
- int total, n_div;
+ isl_size total, n_div;
int any = 0;
isl_int gcd;
- if (!bmap || !A)
- return isl_basic_map_free(bmap);
-
total = isl_basic_map_dim(bmap, isl_dim_all);
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (total < 0 || n_div < 0 || !A)
+ return isl_basic_map_free(bmap);
total -= n_div;
isl_int_init(gcd);
isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,
"equality constraints modified unexpectedly",
goto error);
- if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total + div + 1,
- n_div - div - 1) != -1)
+ if (isl_seq_any_non_zero(bmap->eq[i] + 1 + total + div + 1,
+ n_div - div - 1))
continue;
if (isl_mat_row_gcd(A, i, &gcd) < 0)
goto error;
{
isl_basic_set *bset, *eq;
isl_basic_map *eq_bmap;
- unsigned total, n_div, extra, n_eq, n_ineq;
+ isl_size total, n_div, n_div_bmap;
+ unsigned extra, n_eq, n_ineq;
if (!bmap || !context)
goto error;
@@ -3094,13 +3817,15 @@ __isl_give isl_basic_map *isl_basic_map_gist(__isl_take isl_basic_map *bmap,
bmap = isl_basic_map_remove_redundancies(bmap);
context = isl_basic_map_remove_redundancies(context);
+ bmap = isl_basic_map_order_divs(bmap);
context = isl_basic_map_align_divs(context, bmap);
- if (!context)
- goto error;
n_div = isl_basic_map_dim(context, isl_dim_div);
total = isl_basic_map_dim(bmap, isl_dim_all);
- extra = n_div - isl_basic_map_dim(bmap, isl_dim_div);
+ n_div_bmap = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0 || total < 0 || n_div_bmap < 0)
+ goto error;
+ extra = n_div - n_div_bmap;
bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
bset = isl_basic_set_add_dims(bset, isl_dim_set, extra);
n_ineq = bset->n_ineq;
eq = isl_basic_set_copy(bset);
eq = isl_basic_set_cow(eq);
- if (isl_basic_set_free_inequality(eq, n_ineq) < 0)
- eq = isl_basic_set_free(eq);
- if (isl_basic_set_free_equality(bset, n_eq) < 0)
- bset = isl_basic_set_free(bset);
+ eq = isl_basic_set_free_inequality(eq, n_ineq);
+ bset = isl_basic_set_free_equality(bset, n_eq);
eq_bmap = isl_basic_map_overlying_set(eq, isl_basic_map_copy(bmap));
eq_bmap = gist_strides(eq_bmap, context);
context = isl_basic_map_remove_redundancies(context);
map = isl_map_cow(map);
- if (!map || !context)
+ if (isl_map_basic_map_check_equal_space(map, context) < 0)
goto error;
- isl_assert(map->ctx, isl_space_is_equal(map->dim, context->dim), goto error);
map = isl_map_compute_divs(map);
if (!map)
goto error;
__isl_take isl_basic_map *bmap, __isl_keep isl_basic_map *context)
{
int i1, i2;
- unsigned total, extra;
+ isl_size total, bmap_total;
+ unsigned extra;
- if (!bmap || !context)
+ total = isl_basic_map_dim(context, isl_dim_all);
+ bmap_total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0 || bmap_total < 0)
return isl_basic_map_free(bmap);
- total = isl_basic_map_total_dim(context);
- extra = isl_basic_map_total_dim(bmap) - total;
+ extra = bmap_total - total;
i1 = bmap->n_ineq - 1;
i2 = context->n_ineq - 1;
while (bmap && i1 >= 0 && i2 >= 0) {
int cmp;
- if (isl_seq_first_non_zero(bmap->ineq[i1] + 1 + total,
- extra) != -1) {
+ if (isl_seq_any_non_zero(bmap->ineq[i1] + 1 + total, extra)) {
--i1;
continue;
}
__isl_take isl_basic_map *bmap, __isl_keep isl_basic_map *context)
{
int i1, i2;
- unsigned total, extra;
+ isl_size total, bmap_total;
+ unsigned extra;
- if (!bmap || !context)
+ total = isl_basic_map_dim(context, isl_dim_all);
+ bmap_total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0 || bmap_total < 0)
return isl_basic_map_free(bmap);
- total = isl_basic_map_total_dim(context);
- extra = isl_basic_map_total_dim(bmap) - total;
+ extra = bmap_total - total;
i1 = bmap->n_eq - 1;
i2 = context->n_eq - 1;
while (bmap && i1 >= 0 && i2 >= 0) {
int last1, last2;
- if (isl_seq_first_non_zero(bmap->eq[i1] + 1 + total,
- extra) != -1)
+ if (isl_seq_any_non_zero(bmap->eq[i1] + 1 + total, extra))
break;
last1 = isl_seq_last_non_zero(bmap->eq[i1] + 1, total);
last2 = isl_seq_last_non_zero(context->eq[i2] + 1, total);
isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
"context has unknown divs", goto error);
+ context = isl_basic_map_order_divs(context);
bmap = isl_basic_map_align_divs(bmap, context);
bmap = isl_basic_map_gauss(bmap, NULL);
bmap = isl_basic_map_sort_constraints(bmap);
* for the context. These can then be used to simplify away
* the corresponding constraints in "map".
*/
-static __isl_give isl_map *map_gist(__isl_take isl_map *map,
+__isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
__isl_take isl_map *context)
{
int equal;
int is_universe;
- int single_disjunct_map, single_disjunct_context;
+ isl_size n_disjunct_map, n_disjunct_context;
isl_bool subset;
isl_basic_map *hull;
return map;
}
+ isl_map_align_params_bin(&map, &context);
equal = isl_map_plain_is_equal(map, context);
if (equal < 0)
goto error;
if (equal)
return replace_by_universe(map, context);
- single_disjunct_map = isl_map_n_basic_map(map) == 1;
- single_disjunct_context = isl_map_n_basic_map(context) == 1;
- if (!single_disjunct_map || !single_disjunct_context) {
+ n_disjunct_map = isl_map_n_basic_map(map);
+ n_disjunct_context = isl_map_n_basic_map(context);
+ if (n_disjunct_map < 0 || n_disjunct_context < 0)
+ goto error;
+ if (n_disjunct_map != 1 || n_disjunct_context != 1) {
subset = isl_map_is_subset(context, map);
if (subset < 0)
goto error;
context = isl_map_compute_divs(context);
if (!context)
goto error;
- if (single_disjunct_context) {
+ if (n_disjunct_context == 1) {
hull = isl_map_simple_hull(context);
} else {
isl_ctx *ctx;
return NULL;
}
-__isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
- __isl_take isl_map *context)
-{
- return isl_map_align_params_map_map_and(map, context, &map_gist);
-}
-
-struct isl_basic_set *isl_basic_set_gist(struct isl_basic_set *bset,
- struct isl_basic_set *context)
+__isl_give isl_basic_set *isl_basic_set_gist(__isl_take isl_basic_set *bset,
+ __isl_take isl_basic_set *context)
{
return bset_from_bmap(isl_basic_map_gist(bset_to_bmap(bset),
bset_to_bmap(context)));
{
struct isl_vec *v = NULL;
int *elim = NULL;
- unsigned total;
+ isl_size total;
int i;
- if (!bmap1 || !bmap2)
+ if (isl_basic_map_check_equal_space(bmap1, bmap2) < 0)
return isl_bool_error;
- isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim),
- return isl_bool_error);
if (bmap1->n_div || bmap2->n_div)
return isl_bool_false;
if (!bmap1->n_eq && !bmap2->n_eq)
return isl_bool_false;
total = isl_space_dim(bmap1->dim, isl_dim_all);
+ if (total < 0)
+ return isl_bool_error;
if (total == 0)
return isl_bool_false;
v = isl_vec_alloc(bmap1->ctx, 1 + total);
elim = isl_alloc_array(bmap1->ctx, int, total);
if (!elim)
goto error;
- compute_elimination_index(bmap1, elim);
+ compute_elimination_index(bmap1, elim, total);
for (i = 0; i < bmap2->n_eq; ++i) {
int reduced;
reduced = reduced_using_equalities(v->block.data, bmap2->eq[i],
- bmap1, elim);
+ bmap1, elim, total);
if (reduced && !isl_int_is_zero(v->block.data[0]) &&
- isl_seq_first_non_zero(v->block.data + 1, total) == -1)
+ !isl_seq_any_non_zero(v->block.data + 1, total))
goto disjoint;
}
for (i = 0; i < bmap2->n_ineq; ++i) {
int reduced;
reduced = reduced_using_equalities(v->block.data,
- bmap2->ineq[i], bmap1, elim);
+ bmap2->ineq[i], bmap1, elim, total);
if (reduced && isl_int_is_neg(v->block.data[0]) &&
- isl_seq_first_non_zero(v->block.data + 1, total) == -1)
+ !isl_seq_any_non_zero(v->block.data + 1, total))
goto disjoint;
}
- compute_elimination_index(bmap2, elim);
+ compute_elimination_index(bmap2, elim, total);
for (i = 0; i < bmap1->n_ineq; ++i) {
int reduced;
reduced = reduced_using_equalities(v->block.data,
- bmap1->ineq[i], bmap2, elim);
+ bmap1->ineq[i], bmap2, elim, total);
if (reduced && isl_int_is_neg(v->block.data[0]) &&
- isl_seq_first_non_zero(v->block.data + 1, total) == -1)
+ !isl_seq_any_non_zero(v->block.data + 1, total))
goto disjoint;
}
isl_vec_free(v);
if (disjoint < 0 || disjoint)
return disjoint;
- match = isl_space_tuple_is_equal(map1->dim, isl_dim_in,
- map2->dim, isl_dim_in);
+ match = isl_map_tuple_is_equal(map1, isl_dim_in, map2, isl_dim_in);
if (match < 0 || !match)
return match < 0 ? isl_bool_error : isl_bool_true;
- match = isl_space_tuple_is_equal(map1->dim, isl_dim_out,
- map2->dim, isl_dim_out);
+ match = isl_map_tuple_is_equal(map1, isl_dim_out, map2, isl_dim_out);
if (match < 0 || !match)
return match < 0 ? isl_bool_error : isl_bool_true;
@@ -3820,11 +4540,11 @@ isl_bool isl_map_is_disjoint(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
intersect = isl_map_plain_is_universe(map1);
if (intersect < 0 || intersect)
- return intersect < 0 ? isl_bool_error : isl_bool_false;
+ return isl_bool_not(intersect);
intersect = isl_map_plain_is_universe(map2);
if (intersect < 0 || intersect)
- return intersect < 0 ? isl_bool_error : isl_bool_false;
+ return isl_bool_not(intersect);
intersect = isl_map_plain_is_equal(map1, map2);
if (intersect < 0 || intersect)
intersect = isl_basic_map_plain_is_universe(bmap1);
if (intersect < 0 || intersect)
- return intersect < 0 ? isl_bool_error : isl_bool_false;
+ return isl_bool_not(intersect);
intersect = isl_basic_map_plain_is_universe(bmap2);
if (intersect < 0 || intersect)
- return intersect < 0 ? isl_bool_error : isl_bool_false;
+ return isl_bool_not(intersect);
test = isl_basic_map_intersect(isl_basic_map_copy(bmap1),
isl_basic_map_copy(bmap2));
return isl_int_is_zero(v) || isl_int_is_one(v) || isl_int_is_negone(v);
}
+/* Are the "n" coefficients starting at "first" of inequality constraints
+ * "i" and "j" of "bmap" opposite to each other?
+ */
+static int is_opposite_part(__isl_keep isl_basic_map *bmap, int i, int j,
+ int first, int n)
+{
+ return isl_seq_is_neg(bmap->ineq[i] + first, bmap->ineq[j] + first, n);
+}
+
+/* Are inequality constraints "i" and "j" of "bmap" opposite to each other,
+ * apart from the constant term?
+ */
+static isl_bool is_opposite(__isl_keep isl_basic_map *bmap, int i, int j)
+{
+ isl_size total;
+
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_bool_error;
+ return is_opposite_part(bmap, i, j, 1, total);
+}
+
/* Check if we can combine a given div with lower bound l and upper
* bound u with some other div and if so return that other div.
- * Otherwise return -1.
+ * Otherwise, return a position beyond the integer divisions.
+ * Return isl_size_error on error.
*
* We first check that
* - the bounds are opposites of each other (except for the constant
* If so, we return b so that "a + m b" can be replaced by
* a single div "c = a + m b".
*/
-static int div_find_coalesce(struct isl_basic_map *bmap, int *pairs,
+static isl_size div_find_coalesce(__isl_keep isl_basic_map *bmap, int *pairs,
unsigned div, unsigned l, unsigned u)
{
int i, j;
- unsigned dim;
- int coalesce = -1;
-
- if (bmap->n_div <= 1)
- return -1;
- dim = isl_space_dim(bmap->dim, isl_dim_all);
- if (isl_seq_first_non_zero(bmap->ineq[l] + 1 + dim, div) != -1)
- return -1;
- if (isl_seq_first_non_zero(bmap->ineq[l] + 1 + dim + div + 1,
- bmap->n_div - div - 1) != -1)
- return -1;
- if (!isl_seq_is_neg(bmap->ineq[l] + 1, bmap->ineq[u] + 1,
- dim + bmap->n_div))
- return -1;
+ isl_size n_div;
+ isl_size v_div;
+ isl_size coalesce;
+ isl_bool involves, opp;
- 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 + dim + div]))
- return -1;
- }
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div <= 1)
+ return n_div;
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return isl_size_error;
+ if (isl_seq_any_non_zero(bmap->ineq[l] + 1 + v_div, div))
+ return n_div;
+ if (isl_seq_any_non_zero(bmap->ineq[l] + 1 + v_div + div + 1,
+ n_div - div - 1))
+ return n_div;
+ opp = is_opposite(bmap, l, u);
+ if (opp < 0 || !opp)
+ return opp < 0 ? isl_size_error : n_div;
+
+ involves = isl_basic_map_any_div_involves_vars(bmap, v_div + div, 1);
+ if (involves < 0 || involves)
+ return involves < 0 ? isl_size_error : n_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])) {
bmap = isl_basic_map_copy(bmap);
bmap = isl_basic_map_set_to_empty(bmap);
isl_basic_map_free(bmap);
- return -1;
+ return n_div;
}
isl_int_add_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
- for (i = 0; i < bmap->n_div; ++i) {
+ coalesce = n_div;
+ for (i = 0; i < n_div; ++i) {
if (i == div)
continue;
if (!pairs[i])
continue;
- for (j = 0; j < bmap->n_div; ++j) {
- if (isl_int_is_zero(bmap->div[j][0]))
- continue;
- if (!isl_int_is_zero(bmap->div[j][1 + 1 + dim + i]))
- break;
- }
- if (j < bmap->n_div)
+ involves = isl_basic_map_any_div_involves_vars(bmap,
+ v_div + i, 1);
+ if (involves < 0)
+ goto error;
+ if (involves)
continue;
for (j = 0; j < bmap->n_ineq; ++j) {
int valid;
if (j == l || j == u)
continue;
- if (isl_int_is_zero(bmap->ineq[j][1 + dim + div])) {
- if (is_zero_or_one(bmap->ineq[j][1 + dim + i]))
+ if (isl_int_is_zero(bmap->ineq[j][1 + v_div + div])) {
+ if (is_zero_or_one(bmap->ineq[j][1 + v_div + i]))
continue;
break;
}
- if (isl_int_is_zero(bmap->ineq[j][1 + dim + i]))
+ if (isl_int_is_zero(bmap->ineq[j][1 + v_div + i]))
break;
- isl_int_mul(bmap->ineq[j][1 + dim + div],
- bmap->ineq[j][1 + dim + div],
+ isl_int_mul(bmap->ineq[j][1 + v_div + div],
+ bmap->ineq[j][1 + v_div + div],
bmap->ineq[l][0]);
- valid = isl_int_eq(bmap->ineq[j][1 + dim + div],
- bmap->ineq[j][1 + dim + i]);
- isl_int_divexact(bmap->ineq[j][1 + dim + div],
- bmap->ineq[j][1 + dim + div],
+ valid = isl_int_eq(bmap->ineq[j][1 + v_div + div],
+ bmap->ineq[j][1 + v_div + i]);
+ isl_int_divexact(bmap->ineq[j][1 + v_div + div],
+ bmap->ineq[j][1 + v_div + div],
bmap->ineq[l][0]);
if (!valid)
break;
coalesce = i;
break;
}
+ if (0)
+error: coalesce = isl_size_error;
isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
isl_int_sub(bmap->ineq[l][0], bmap->ineq[l][0], bmap->ineq[u][0]);
return coalesce;
static isl_bool int_between_bounds(__isl_keep isl_basic_map *bmap, int i,
int l, int u, struct test_ineq_data *data)
{
- unsigned offset, n_div;
+ unsigned offset;
+ isl_size n_div;
+
offset = isl_basic_map_offset(bmap, isl_dim_div);
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_bool_error;
isl_int_gcd(data->g,
bmap->ineq[l][offset + i], bmap->ineq[u][offset + i]);
{
isl_ctx *ctx;
struct test_ineq_data data = { NULL, NULL };
- unsigned off, n_div;
+ unsigned off;
+ isl_size n_div;
int remove = -1;
isl_int_init(data.g);
isl_int_init(data.fl);
isl_int_init(data.fu);
- if (!bmap)
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
goto error;
ctx = isl_basic_map_get_ctx(bmap);
off = isl_basic_map_offset(bmap, isl_dim_div);
- n_div = isl_basic_map_dim(bmap, isl_dim_div);
data.v = isl_vec_alloc(ctx, off + n_div);
if (!data.v)
goto error;
@@ -4305,13 +5056,16 @@ static __isl_give isl_basic_map *coalesce_divs(__isl_take isl_basic_map *bmap,
{
isl_ctx *ctx;
isl_int m;
- unsigned dim, total;
+ isl_size v_div;
+ unsigned total;
int i;
ctx = isl_basic_map_get_ctx(bmap);
- dim = isl_space_dim(bmap->dim, isl_dim_all);
- total = 1 + dim + bmap->n_div;
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (v_div < 0)
+ return isl_basic_map_free(bmap);
+ total = 1 + v_div + bmap->n_div;
isl_int_init(m);
isl_int_add(m, bmap->ineq[l][0], bmap->ineq[u][0]);
@@ -4320,19 +5074,19 @@ static __isl_give isl_basic_map *coalesce_divs(__isl_take isl_basic_map *bmap,
for (i = 0; i < bmap->n_ineq; ++i) {
if (i == l || i == u)
continue;
- if (isl_int_is_zero(bmap->ineq[i][1 + dim + div2]))
+ if (isl_int_is_zero(bmap->ineq[i][1 + v_div + div2]))
continue;
- if (isl_int_is_zero(bmap->ineq[i][1 + dim + div1])) {
- if (isl_int_is_pos(bmap->ineq[i][1 + dim + div2]))
+ if (isl_int_is_zero(bmap->ineq[i][1 + v_div + div1])) {
+ if (isl_int_is_pos(bmap->ineq[i][1 + v_div + div2]))
isl_seq_combine(bmap->ineq[i], m, bmap->ineq[i],
ctx->one, bmap->ineq[l], total);
else
isl_seq_combine(bmap->ineq[i], m, bmap->ineq[i],
ctx->one, bmap->ineq[u], total);
}
- isl_int_set(bmap->ineq[i][1 + dim + div2],
- bmap->ineq[i][1 + dim + div1]);
- isl_int_set_si(bmap->ineq[i][1 + dim + div1], 0);
+ isl_int_set(bmap->ineq[i][1 + v_div + div2],
+ bmap->ineq[i][1 + v_div + div1]);
+ isl_int_set_si(bmap->ineq[i][1 + v_div + div1], 0);
}
isl_int_clear(m);
__isl_take isl_basic_map *bmap, int *pairs, int n)
{
int i, l, u;
- unsigned dim;
+ isl_size v_div;
+ isl_size n_div;
- dim = isl_space_dim(bmap->dim, isl_dim_all);
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (v_div < 0 || n_div < 0)
+ return isl_basic_map_free(bmap);
- for (i = 0; i < bmap->n_div; ++i) {
+ for (i = 0; i < n_div; ++i) {
if (!pairs[i])
continue;
for (l = 0; l < bmap->n_ineq; ++l) {
- if (!isl_int_is_one(bmap->ineq[l][1 + dim + i]))
+ if (!isl_int_is_one(bmap->ineq[l][1 + v_div + i]))
continue;
for (u = 0; u < bmap->n_ineq; ++u) {
int c;
- if (!isl_int_is_negone(bmap->ineq[u][1+dim+i]))
+ if (!isl_int_is_negone(bmap->ineq[u][1+v_div+i]))
continue;
c = div_find_coalesce(bmap, pairs, i, l, u);
if (c < 0)
+ goto error;
+ if (c >= n_div)
continue;
free(pairs);
bmap = coalesce_divs(bmap, i, c, l, u);
}
return drop_more_redundant_divs(bmap, pairs, n);
+error:
+ free(pairs);
+ isl_basic_map_free(bmap);
+ return NULL;
}
/* Are the "n" coefficients starting at "first" of inequality constraints
return isl_seq_eq(bmap->ineq[i] + first, bmap->ineq[j] + first, n);
}
-/* Are the "n" coefficients starting at "first" of inequality constraints
- * "i" and "j" of "bmap" opposite to each other?
- */
-static int is_opposite_part(__isl_keep isl_basic_map *bmap, int i, int j,
- int first, int n)
-{
- return isl_seq_is_neg(bmap->ineq[i] + first, bmap->ineq[j] + first, n);
-}
-
-/* Are inequality constraints "i" and "j" of "bmap" opposite to each other,
- * apart from the constant term?
- */
-static isl_bool is_opposite(__isl_keep isl_basic_map *bmap, int i, int j)
-{
- unsigned total;
-
- total = isl_basic_map_dim(bmap, isl_dim_all);
- return is_opposite_part(bmap, i, j, 1, total);
-}
-
/* Are inequality constraints "i" and "j" of "bmap" equal to each other,
* apart from the constant term and the coefficient at position "pos"?
*/
-static int is_parallel_except(__isl_keep isl_basic_map *bmap, int i, int j,
+static isl_bool is_parallel_except(__isl_keep isl_basic_map *bmap, int i, int j,
int pos)
{
- unsigned total;
+ isl_size total;
total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_bool_error;
return is_parallel_part(bmap, i, j, 1, pos - 1) &&
is_parallel_part(bmap, i, j, pos + 1, total - pos);
}
/* Are inequality constraints "i" and "j" of "bmap" opposite to each other,
* apart from the constant term and the coefficient at position "pos"?
*/
-static int is_opposite_except(__isl_keep isl_basic_map *bmap, int i, int j,
+static isl_bool is_opposite_except(__isl_keep isl_basic_map *bmap, int i, int j,
int pos)
{
- unsigned total;
+ isl_size total;
total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_bool_error;
return is_opposite_part(bmap, i, j, 1, pos - 1) &&
is_opposite_part(bmap, i, j, pos + 1, total - pos);
}
int div)
{
int i;
- unsigned n_div, o_div;
+ isl_size n_div;
+ unsigned o_div;
isl_bool known;
known = isl_basic_map_div_is_known(bmap, div);
if (known < 0 || known)
return isl_bool_not(known);
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_bool_error;
if (n_div == 1)
return isl_bool_true;
o_div = isl_basic_map_offset(bmap, isl_dim_div);
* ceil((-c1 - c)/n) = ceil((c0 - c)/n)
*
* If so, return the index of inequality f(x) + c0 >= 0.
- * Otherwise, return -1.
+ * Otherwise, return bmap->n_ineq.
+ * Return -1 on error.
*/
static int lower_bound_is_cst(__isl_keep isl_basic_map *bmap, int div, int ineq)
{
@@ -4627,23 +5379,32 @@ static int lower_bound_is_cst(__isl_keep isl_basic_map *bmap, int div, int ineq)
o_div = isl_basic_map_offset(bmap, isl_dim_div);
for (i = 0; i < bmap->n_ineq && (lower < 0 || upper < 0); ++i) {
+ isl_bool par, opp;
+
if (i == ineq)
continue;
if (!isl_int_is_zero(bmap->ineq[i][o_div + div]))
continue;
- if (lower < 0 &&
- is_parallel_except(bmap, ineq, i, o_div + div)) {
+ par = isl_bool_false;
+ if (lower < 0)
+ par = is_parallel_except(bmap, ineq, i, o_div + div);
+ if (par < 0)
+ return -1;
+ if (par) {
lower = i;
continue;
}
- if (upper < 0 &&
- is_opposite_except(bmap, ineq, i, o_div + div)) {
+ opp = isl_bool_false;
+ if (upper < 0)
+ opp = is_opposite_except(bmap, ineq, i, o_div + div);
+ if (opp < 0)
+ return -1;
+ if (opp)
upper = i;
- }
}
if (lower < 0 || upper < 0)
- return -1;
+ return bmap->n_ineq;
isl_int_init(l);
isl_int_init(u);
@@ -4656,7 +5417,7 @@ static int lower_bound_is_cst(__isl_keep isl_basic_map *bmap, int div, int ineq)
isl_int_clear(l);
isl_int_clear(u);
- return equal ? lower : -1;
+ return equal ? lower : bmap->n_ineq;
}
/* Given a lower bound constraint "ineq" on the existentially quantified
@@ -4696,6 +5457,33 @@ static __isl_give isl_basic_map *fix_cst_lower(__isl_take isl_basic_map *bmap,
return isl_basic_map_drop_redundant_divs(bmap);
}
+/* Do any of the integer divisions of "bmap" involve integer division "div"?
+ *
+ * The integer division "div" could only ever appear in any later
+ * integer division (with an explicit representation).
+ */
+static isl_bool any_div_involves_div(__isl_keep isl_basic_map *bmap, int div)
+{
+ int i;
+ isl_size v_div, n_div;
+
+ v_div = isl_basic_map_var_offset(bmap, isl_dim_div);
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (v_div < 0 || n_div < 0)
+ return isl_bool_error;
+
+ for (i = div + 1; i < n_div; ++i) {
+ isl_bool involves;
+
+ involves = isl_basic_map_div_expr_involves_vars(bmap, i,
+ v_div + div, 1);
+ if (involves < 0 || involves)
+ return involves;
+ }
+
+ return isl_bool_false;
+}
+
/* Remove divs that are not strictly needed based on the inequality
* constraints.
* In particular, if a div only occurs positively (or negatively)
__isl_take isl_basic_map *bmap)
{
int i, j;
- unsigned off;
+ isl_size off;
int *pairs = NULL;
int n = 0;
+ isl_size n_ineq;
if (!bmap)
goto error;
if (bmap->n_div == 0)
return bmap;
- off = isl_space_dim(bmap->dim, isl_dim_all);
+ off = isl_basic_map_var_offset(bmap, isl_dim_div);
+ if (off < 0)
+ return isl_basic_map_free(bmap);
pairs = isl_calloc_array(bmap->ctx, int, bmap->n_div);
if (!pairs)
goto error;
+ n_ineq = isl_basic_map_n_inequality(bmap);
+ if (n_ineq < 0)
+ goto error;
for (i = 0; i < bmap->n_div; ++i) {
int pos, neg;
int last_pos, last_neg;
int redundant;
int defined;
- isl_bool opp, set_div;
+ isl_bool involves, opp, set_div;
defined = !isl_int_is_zero(bmap->div[i][0]);
- for (j = i; j < bmap->n_div; ++j)
- if (!isl_int_is_zero(bmap->div[j][1 + 1 + off + i]))
- break;
- if (j < bmap->n_div)
+ involves = any_div_involves_div(bmap, i);
+ if (involves < 0)
+ goto error;
+ if (involves)
continue;
for (j = 0; j < bmap->n_eq; ++j)
if (!isl_int_is_zero(bmap->eq[j][1 + off + i]))
return set_eq_and_try_again(bmap, last_pos,
pairs);
lower = lower_bound_is_cst(bmap, i, last_pos);
- if (lower >= 0)
+ if (lower < 0)
+ goto error;
+ if (lower < n_ineq)
return fix_cst_lower(bmap, i, last_pos, lower,
pairs);
continue;
*/
static isl_stat preimage(isl_int *c, __isl_keep isl_mat *T)
{
- int n;
+ isl_size n;
isl_ctx *ctx;
isl_vec *v;
- if (!T)
- return isl_stat_error;
n = isl_mat_rows(T);
- if (isl_seq_first_non_zero(c, n) == -1)
+ if (n < 0)
+ return isl_stat_error;
+ if (!isl_seq_any_non_zero(c, n))
return isl_stat_ok;
ctx = isl_mat_get_ctx(T);
v = isl_vec_alloc(ctx, n);
__isl_take isl_basic_map *bmap, unsigned pos, __isl_take isl_mat *T)
{
int i;
- unsigned n, total;
+ isl_size n_row, n_col;
bmap = isl_basic_map_cow(bmap);
- if (!bmap || !T)
+ n_row = isl_mat_rows(T);
+ n_col = isl_mat_cols(T);
+ if (!bmap || n_row < 0 || n_col < 0)
goto error;
- n = isl_mat_cols(T);
- if (n != isl_mat_rows(T))
+ if (n_col != n_row)
isl_die(isl_mat_get_ctx(T), isl_error_invalid,
"expecting square matrix", goto error);
- total = isl_basic_map_dim(bmap, isl_dim_all);
- if (pos + n > total || pos + n < pos)
- isl_die(isl_mat_get_ctx(T), isl_error_invalid,
- "invalid range", goto error);
+ if (isl_basic_map_check_range(bmap, isl_dim_all, pos, n_col) < 0)
+ goto error;
for (i = 0; i < bmap->n_eq; ++i)
if (preimage(bmap->eq[i] + 1 + pos, T) < 0)
{
int first;
int i;
- unsigned o_div, n_div;
+ unsigned o_div;
+ isl_size n_div;
int l;
isl_ctx *ctx;
isl_mat *T;
o_div = isl_basic_map_offset(bmap, isl_dim_div);
n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ if (n_div < 0)
+ return isl_basic_map_free(bmap);
for (i = 0; i < bmap->n_eq; ++i) {
l = isl_seq_first_non_zero(bmap->eq[i] + o_div + first,
if (l < 0)
continue;
l += first;
- if (isl_seq_first_non_zero(bmap->eq[i] + o_div + l + 1,
- n_div - (l + 1)) == -1)
+ if (!isl_seq_any_non_zero(bmap->eq[i] + o_div + l + 1,
+ n_div - (l + 1)))
continue;
break;
}
/* Does "bmap" satisfy any equality that involves more than 2 variables
* and/or has coefficients different from -1 and 1?
*/
-static int has_multiple_var_equality(__isl_keep isl_basic_map *bmap)
+static isl_bool has_multiple_var_equality(__isl_keep isl_basic_map *bmap)
{
int i;
- unsigned total;
+ isl_size total;
total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_bool_error;
for (i = 0; i < bmap->n_eq; ++i) {
int j, k;
continue;
if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
!isl_int_is_negone(bmap->eq[i][1 + j]))
- return 1;
+ return isl_bool_true;
j += 1;
k = isl_seq_first_non_zero(bmap->eq[i] + 1 + j, total - j);
j += k;
if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
!isl_int_is_negone(bmap->eq[i][1 + j]))
- return 1;
+ return isl_bool_true;
j += 1;
- k = isl_seq_first_non_zero(bmap->eq[i] + 1 + j, total - j);
- if (k >= 0)
- return 1;
+ if (isl_seq_any_non_zero(bmap->eq[i] + 1 + j, total - j))
+ return isl_bool_true;
}
- return 0;
+ return isl_bool_false;
}
/* Remove any common factor g from the constraint coefficients in "v".
return v;
}
+/* Internal representation used by isl_basic_map_reduce_coefficients.
+ *
+ * "total" is the total dimensionality of the original basic map.
+ * "v" is a temporary vector of size 1 + total that can be used
+ * to store constraint coefficients.
+ * "T" is the variable compression.
+ * "T2" is the inverse transformation.
+ * "tightened" is set if any constant term got tightened
+ * while reducing the coefficients.
+ */
+struct isl_reduce_coefficients_data {
+ isl_size total;
+ isl_vec *v;
+ isl_mat *T;
+ isl_mat *T2;
+ int tightened;
+};
+
+/* Free all memory allocated in "data".
+ */
+static void isl_reduce_coefficients_data_clear(
+ struct isl_reduce_coefficients_data *data)
+{
+ data->T = isl_mat_free(data->T);
+ data->T2 = isl_mat_free(data->T2);
+ data->v = isl_vec_free(data->v);
+}
+
+/* Initialize "data" for "bmap", freeing all allocated memory
+ * if anything goes wrong.
+ *
+ * In particular, construct a variable compression
+ * from the equality constraints of "bmap" and
+ * allocate a temporary vector.
+ */
+static isl_stat isl_reduce_coefficients_data_init(
+ __isl_keep isl_basic_map *bmap,
+ struct isl_reduce_coefficients_data *data)
+{
+ isl_ctx *ctx;
+ isl_mat *eq;
+
+ data->v = NULL;
+ data->T = NULL;
+ data->T2 = NULL;
+ data->tightened = 0;
+
+ data->total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (data->total < 0)
+ return isl_stat_error;
+ ctx = isl_basic_map_get_ctx(bmap);
+ data->v = isl_vec_alloc(ctx, 1 + data->total);
+ if (!data->v)
+ return isl_stat_error;
+
+ eq = isl_mat_sub_alloc6(ctx, bmap->eq, 0, bmap->n_eq,
+ 0, 1 + data->total);
+ data->T = isl_mat_variable_compression(eq, &data->T2);
+ if (!data->T || !data->T2)
+ goto error;
+
+ return isl_stat_ok;
+error:
+ isl_reduce_coefficients_data_clear(data);
+ return isl_stat_error;
+}
+
+/* Reduce the coefficients of "bmap" by applying the variable compression
+ * in "data".
+ * In particular, apply the variable compression to each constraint,
+ * factor out any common factor in the non-constant coefficients and
+ * then apply the inverse of the compression.
+ *
+ * Only apply the reduction on a single copy of the basic map
+ * since the reduction may leave the result in an inconsistent state.
+ * In particular, the constraints may not be gaussed.
+ */
+static __isl_give isl_basic_map *reduce_coefficients(
+ __isl_take isl_basic_map *bmap,
+ struct isl_reduce_coefficients_data *data)
+{
+ int i;
+ isl_size total;
+
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+ if (total < 0)
+ return isl_basic_map_free(bmap);
+ if (total != data->total)
+ isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,
+ "total dimensionality changed unexpectedly",
+ return isl_basic_map_free(bmap));
+
+ bmap = isl_basic_map_cow(bmap);
+ if (!bmap)
+ return NULL;
+
+ for (i = 0; i < bmap->n_ineq; ++i) {
+ isl_seq_cpy(data->v->el, bmap->ineq[i], 1 + data->total);
+ data->v = isl_vec_mat_product(data->v, isl_mat_copy(data->T));
+ data->v = normalize_constraint(data->v, &data->tightened);
+ data->v = isl_vec_mat_product(data->v, isl_mat_copy(data->T2));
+ if (!data->v)
+ return isl_basic_map_free(bmap);
+ isl_seq_cpy(bmap->ineq[i], data->v->el, 1 + data->total);
+ }
+
+ ISL_F_SET(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
+
+ return bmap;
+}
+
/* If "bmap" is an integer set that satisfies any equality involving
* more than 2 variables and/or has coefficients different from -1 and 1,
* then use variable compression to reduce the coefficients by removing
* We therefore call isl_basic_map_detect_inequality_pairs,
* which checks for such pairs of inequalities as well as eliminate_divs_eq
* and isl_basic_map_gauss if such a pair was found.
+ * This call to isl_basic_map_gauss may undo much of the effect
+ * of the reduction on which isl_map_coalesce depends.
+ * In particular, constraints in terms of (compressed) local variables
+ * get reformulated in terms of the set variables again.
+ * The reduction is therefore applied again afterwards.
+ * This has to be done before the call to eliminate_divs_eq, however,
+ * since that may remove some local variables, while
+ * the data used during the reduction is formulated in terms
+ * of the original variables.
*
* Tightening may also result in some other constraints becoming
* (rationally) redundant with respect to the tightened constraint
__isl_give isl_basic_map *isl_basic_map_reduce_coefficients(
__isl_take isl_basic_map *bmap)
{
- unsigned total;
- isl_ctx *ctx;
- isl_vec *v;
- isl_mat *eq, *T, *T2;
- int i;
- int tightened;
+ struct isl_reduce_coefficients_data data;
+ isl_bool multi;
if (!bmap)
return NULL;
return bmap;
if (bmap->n_eq == 0)
return bmap;
- if (!has_multiple_var_equality(bmap))
+ multi = has_multiple_var_equality(bmap);
+ if (multi < 0)
+ return isl_basic_map_free(bmap);
+ if (!multi)
return bmap;
- total = isl_basic_map_dim(bmap, isl_dim_all);
- ctx = isl_basic_map_get_ctx(bmap);
- v = isl_vec_alloc(ctx, 1 + total);
- if (!v)
+ if (isl_reduce_coefficients_data_init(bmap, &data) < 0)
return isl_basic_map_free(bmap);
- eq = isl_mat_sub_alloc6(ctx, bmap->eq, 0, bmap->n_eq, 0, 1 + total);
- T = isl_mat_variable_compression(eq, &T2);
- if (!T || !T2)
- goto error;
- if (T->n_col == 0) {
- isl_mat_free(T);
- isl_mat_free(T2);
- isl_vec_free(v);
+ if (data.T->n_col == 0) {
+ isl_reduce_coefficients_data_clear(&data);
return isl_basic_map_set_to_empty(bmap);
}
- bmap = isl_basic_map_cow(bmap);
+ bmap = reduce_coefficients(bmap, &data);
if (!bmap)
goto error;
- tightened = 0;
- for (i = 0; i < bmap->n_ineq; ++i) {
- isl_seq_cpy(v->el, bmap->ineq[i], 1 + total);
- v = isl_vec_mat_product(v, isl_mat_copy(T));
- v = normalize_constraint(v, &tightened);
- v = isl_vec_mat_product(v, isl_mat_copy(T2));
- if (!v)
- goto error;
- isl_seq_cpy(bmap->ineq[i], v->el, 1 + total);
- }
-
- isl_mat_free(T);
- isl_mat_free(T2);
- isl_vec_free(v);
-
- ISL_F_SET(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
-
- if (tightened) {
+ if (data.tightened) {
int progress = 0;
ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
bmap = isl_basic_map_detect_inequality_pairs(bmap, &progress);
if (progress) {
- bmap = eliminate_divs_eq(bmap, &progress);
bmap = isl_basic_map_gauss(bmap, NULL);
+ bmap = reduce_coefficients(bmap, &data);
+ bmap = eliminate_divs_eq(bmap, &progress);
}
}
+ isl_reduce_coefficients_data_clear(&data);
+
return bmap;
error:
- isl_mat_free(T);
- isl_mat_free(T2);
- isl_vec_free(v);
+ isl_reduce_coefficients_data_clear(&data);
return isl_basic_map_free(bmap);
}
__isl_take isl_basic_map *bmap, int div, int pos, isl_int shift)
{
int i;
- unsigned total;
+ isl_size total, n_div;
if (isl_int_is_zero(shift))
return bmap;
- if (!bmap)
- return NULL;
-
total = isl_basic_map_dim(bmap, isl_dim_all);
- total -= isl_basic_map_dim(bmap, isl_dim_div);
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ total -= n_div;
+ if (total < 0 || n_div < 0)
+ return isl_basic_map_free(bmap);
isl_int_addmul(bmap->div[div][1 + pos], shift, bmap->div[div][0]);