continue;
ls = isl_local_space_copy(aff->ls);
ls = isl_local_space_substitute_seq(ls, isl_dim_div, i,
- aff->ls->div->row[i], len, i + 1);
+ aff->ls->div->row[i], len, i + 1, n - (i + 1));
vec = isl_vec_copy(aff->v);
vec = isl_vec_cow(vec);
if (!ls || !vec)
return isl_aff_free(aff);
}
+/* Look for any divs j that appear with a unit coefficient inside
+ * the definitions of other divs i and plug them into the definitions
+ * of the divs i.
+ *
+ * In particular, an expression of the form
+ *
+ * floor((f(..) + floor(g(..)/n))/m)
+ *
+ * is simplified to
+ *
+ * floor((n * f(..) + g(..))/(n * m))
+ *
+ * This simplification is correct because we can move the expression
+ * f(..) into the inner floor in the original expression to obtain
+ *
+ * floor(floor((n * f(..) + g(..))/n)/m)
+ *
+ * from which we can derive the simplified expression.
+ */
+static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff)
+{
+ int i, j, n;
+ int off;
+
+ if (!aff)
+ return NULL;
+
+ n = isl_local_space_dim(aff->ls, isl_dim_div);
+ off = isl_local_space_offset(aff->ls, isl_dim_div);
+ for (i = 1; i < n; ++i) {
+ for (j = 0; j < i; ++j) {
+ if (!isl_int_is_one(aff->ls->div->row[i][1 + off + j]))
+ continue;
+ aff->ls = isl_local_space_substitute_seq(aff->ls,
+ isl_dim_div, j, aff->ls->div->row[j],
+ aff->v->size, i, 1);
+ if (!aff->ls)
+ return isl_aff_free(aff);
+ }
+ }
+
+ return aff;
+}
+
/* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
*
* Even though this function is only called on isl_affs with a single
if (!aff->v)
return isl_aff_free(aff);
aff = plug_in_integral_divs(aff);
+ aff = plug_in_unit_divs(aff);
aff = sort_divs(aff);
aff = isl_aff_remove_unused_divs(aff);
return aff;
isl_int_set_si(aff->v->el[0], 1);
isl_int_set_si(aff->v->el[size], 1);
+ aff = isl_aff_normalize(aff);
+
return aff;
}
/* Given f, return ceil(f).
* If f is an integer expression, then just return f.
- * Otherwise, create a new div d = [-f] and return the expression -d.
+ * Otherwise, let f be the expression
+ *
+ * e/m
+ *
+ * then return
+ *
+ * floor((e + m - 1)/m)
*/
__isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
{
if (isl_int_is_one(aff->v->el[0]))
return aff;
- aff = isl_aff_neg(aff);
+ aff = isl_aff_cow(aff);
+ if (!aff)
+ return NULL;
+ aff->v = isl_vec_cow(aff->v);
+ if (!aff->v)
+ return isl_aff_free(aff);
+
+ isl_int_add(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
+ isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1);
aff = isl_aff_floor(aff);
- aff = isl_aff_neg(aff);
return aff;
}
aff->ls = isl_local_space_substitute_equalities(aff->ls,
isl_basic_set_copy(eq));
- if (!aff->ls)
+ aff->v = isl_vec_cow(aff->v);
+ if (!aff->ls || !aff->v)
goto error;
total = 1 + isl_space_dim(eq->dim, isl_dim_all);
goto error;
n_div = isl_local_space_dim(aff->ls, isl_dim_div);
if (n_div > 0)
- eq = isl_basic_set_add(eq, isl_dim_set, n_div);
+ eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div);
return isl_aff_substitute_equalities_lifted(aff, eq);
error:
isl_basic_set_free(eq);
__isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational(
__isl_take isl_pw_aff_list *list)
{
- int i;
+ int i, n;
if (!list)
return NULL;
if (list->n == 0)
return list;
- for (i = 0; i < list->n; ++i) {
+ n = list->n;
+ for (i = 0; i < n; ++i) {
isl_pw_aff *pa;
pa = isl_pw_aff_list_get_pw_aff(list, i);
return NULL;
}
+/* Given an affine expression
+ *
+ * [A -> B] -> f(A,B)
+ *
+ * construct an isl_multi_aff
+ *
+ * [A -> B] -> B'
+ *
+ * such that dimension "d" in B' is set to "aff" and the remaining
+ * dimensions are set equal to the corresponding dimensions in B.
+ * "n_in" is the dimension of the space A.
+ * "n_out" is the dimension of the space B.
+ *
+ * If "is_set" is set, then the affine expression is of the form
+ *
+ * [B] -> f(B)
+ *
+ * and we construct an isl_multi_aff
+ *
+ * B -> B'
+ */
+static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d,
+ unsigned n_in, unsigned n_out, int is_set)
+{
+ int i;
+ isl_multi_aff *ma;
+ isl_space *space, *space2;
+ isl_local_space *ls;
+
+ space = isl_aff_get_domain_space(aff);
+ ls = isl_local_space_from_space(isl_space_copy(space));
+ space2 = isl_space_copy(space);
+ if (!is_set)
+ space2 = isl_space_range(isl_space_unwrap(space2));
+ space = isl_space_map_from_domain_and_range(space, space2);
+ ma = isl_multi_aff_alloc(space);
+ ma = isl_multi_aff_set_aff(ma, d, aff);
+
+ for (i = 0; i < n_out; ++i) {
+ if (i == d)
+ continue;
+ aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
+ isl_dim_set, n_in + i);
+ ma = isl_multi_aff_set_aff(ma, i, aff);
+ }
+
+ isl_local_space_free(ls);
+
+ return ma;
+}
+
+/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
+ * taking into account that the dimension at position "d" can be written as
+ *
+ * x = m a + f(..) (1)
+ *
+ * where m is equal to "gcd".
+ * "i" is the index of the equality in "hull" that defines f(..).
+ * In particular, the equality is of the form
+ *
+ * f(..) - x + m g(existentials) = 0
+ *
+ * or
+ *
+ * -f(..) + x + m g(existentials) = 0
+ *
+ * We basically plug (1) into "map", resulting in a map with "a"
+ * in the range instead of "x". The corresponding isl_pw_multi_aff
+ * defining "a" is then plugged back into (1) to obtain a definition fro "x".
+ *
+ * Specifically, given the input map
+ *
+ * A -> B
+ *
+ * We first wrap it into a set
+ *
+ * [A -> B]
+ *
+ * and define (1) on top of the corresponding space, resulting in "aff".
+ * We use this to create an isl_multi_aff that maps the output position "d"
+ * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
+ * We plug this into the wrapped map, unwrap the result and compute the
+ * corresponding isl_pw_multi_aff.
+ * The result is an expression
+ *
+ * A -> T(A)
+ *
+ * We adjust that to
+ *
+ * A -> [A -> T(A)]
+ *
+ * so that we can plug that into "aff", after extending the latter to
+ * a mapping
+ *
+ * [A -> B] -> B'
+ *
+ *
+ * If "map" is actually a set, then there is no "A" space, meaning
+ * that we do not need to perform any wrapping, and that the result
+ * of the recursive call is of the form
+ *
+ * [T]
+ *
+ * which is plugged into a mapping of the form
+ *
+ * B -> B'
+ */
+static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride(
+ __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i,
+ isl_int gcd)
+{
+ isl_set *set;
+ isl_space *space;
+ isl_local_space *ls;
+ isl_aff *aff;
+ isl_multi_aff *ma;
+ isl_pw_multi_aff *pma, *id;
+ unsigned n_in;
+ unsigned o_out;
+ unsigned n_out;
+ int is_set;
+
+ is_set = isl_map_is_set(map);
+
+ n_in = isl_basic_map_dim(hull, isl_dim_in);
+ n_out = isl_basic_map_dim(hull, isl_dim_out);
+ o_out = isl_basic_map_offset(hull, isl_dim_out);
+
+ if (is_set)
+ set = map;
+ else
+ set = isl_map_wrap(map);
+ space = isl_space_map_from_set(isl_set_get_space(set));
+ ma = isl_multi_aff_identity(space);
+ ls = isl_local_space_from_space(isl_set_get_space(set));
+ aff = isl_aff_alloc(ls);
+ if (aff) {
+ isl_int_set_si(aff->v->el[0], 1);
+ if (isl_int_is_one(hull->eq[i][o_out + d]))
+ isl_seq_neg(aff->v->el + 1, hull->eq[i],
+ aff->v->size - 1);
+ else
+ isl_seq_cpy(aff->v->el + 1, hull->eq[i],
+ aff->v->size - 1);
+ isl_int_set(aff->v->el[1 + o_out + d], gcd);
+ }
+ ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff));
+ set = isl_set_preimage_multi_aff(set, ma);
+
+ ma = range_map(aff, d, n_in, n_out, is_set);
+
+ if (is_set)
+ map = set;
+ else
+ map = isl_set_unwrap(set);
+ pma = isl_pw_multi_aff_from_map(set);
+
+ if (!is_set) {
+ space = isl_pw_multi_aff_get_domain_space(pma);
+ space = isl_space_map_from_set(space);
+ id = isl_pw_multi_aff_identity(space);
+ pma = isl_pw_multi_aff_range_product(id, pma);
+ }
+ id = isl_pw_multi_aff_from_multi_aff(ma);
+ pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma);
+
+ isl_basic_map_free(hull);
+ return pma;
+}
+
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
*
* As a special case, we first check if all output dimensions are uniquely
* domain. If so, we extract the desired isl_pw_multi_aff directly
* from the affine hull of "map" and its domain.
*
- * Then we continue with pw_multi_aff_from_map_check_div for a further
+ * Otherwise, we check if any of the output dimensions is "strided".
+ * That is, we check if can be written as
+ *
+ * x = m a + f(..)
+ *
+ * with m greater than 1, a some combination of existentiall quantified
+ * variables and f and expression in the parameters and input dimensions.
+ * If so, we remove the stride in pw_multi_aff_from_map_stride.
+ *
+ * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
* special case.
*/
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
{
+ int i, j;
int sv;
isl_basic_map *hull;
+ unsigned n_out;
+ unsigned o_out;
+ unsigned n_div;
+ unsigned o_div;
+ isl_int gcd;
if (!map)
return NULL;
sv = isl_basic_map_plain_is_single_valued(hull);
if (sv >= 0 && sv)
return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
- isl_basic_map_free(hull);
if (sv < 0)
+ hull = isl_basic_map_free(hull);
+ if (!hull)
goto error;
+ n_div = isl_basic_map_dim(hull, isl_dim_div);
+ o_div = isl_basic_map_offset(hull, isl_dim_div);
+
+ if (n_div == 0) {
+ isl_basic_map_free(hull);
+ return pw_multi_aff_from_map_check_div(map);
+ }
+
+ isl_int_init(gcd);
+
+ n_out = isl_basic_map_dim(hull, isl_dim_out);
+ o_out = isl_basic_map_offset(hull, isl_dim_out);
+
+ for (i = 0; i < n_out; ++i) {
+ for (j = 0; j < hull->n_eq; ++j) {
+ isl_int *eq = hull->eq[j];
+ isl_pw_multi_aff *res;
+
+ if (!isl_int_is_one(eq[o_out + i]) &&
+ !isl_int_is_negone(eq[o_out + i]))
+ continue;
+ if (isl_seq_first_non_zero(eq + o_out, i) != -1)
+ continue;
+ if (isl_seq_first_non_zero(eq + o_out + i + 1,
+ n_out - (i + 1)) != -1)
+ continue;
+ isl_seq_gcd(eq + o_div, n_div, &gcd);
+ if (isl_int_is_zero(gcd))
+ continue;
+ if (isl_int_is_one(gcd))
+ continue;
+
+ res = pw_multi_aff_from_map_stride(map, hull,
+ i, j, gcd);
+ isl_int_clear(gcd);
+ return res;
+ }
+ }
+
+ isl_int_clear(gcd);
+ isl_basic_map_free(hull);
return pw_multi_aff_from_map_check_div(map);
error:
isl_map_free(map);
for (j = 0; j < subs->n; ++j) {
isl_set *common;
isl_multi_aff *res_ij;
+ int empty;
+
common = isl_set_intersect(
isl_set_copy(pma->p[i].set),
isl_set_copy(subs->p[j].set));
common = isl_set_substitute(common,
type, pos, subs->p[j].aff);
- if (isl_set_plain_is_empty(common)) {
+ empty = isl_set_plain_is_empty(common);
+ if (empty < 0 || empty) {
isl_set_free(common);
+ if (empty < 0)
+ goto error;
continue;
}
isl_pw_multi_aff_free(pma);
return res;
+error:
+ isl_pw_multi_aff_free(pma);
+ isl_pw_multi_aff_free(res);
+ return NULL;
}
/* Compute the preimage of the affine expression "src" under "ma"