/*
* Copyright 2011 INRIA Saclay
* Copyright 2011 Sven Verdoolaege
- * Copyright 2012 Ecole Normale Superieure
+ * Copyright 2012-2013 Ecole Normale Superieure
*
* Use of this software is governed by the MIT license
*
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;
}
if (!aff->v)
return isl_aff_free(aff);
+ if (isl_int_is_pos(f) && isl_int_is_divisible_by(aff->v->el[0], f)) {
+ isl_int_divexact(aff->v->el[0], aff->v->el[0], f);
+ return aff;
+ }
+
isl_int_init(gcd);
isl_int_gcd(gcd, aff->v->el[0], f);
isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
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);
__isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
__isl_take isl_multi_aff *maff2)
{
- int i;
- isl_ctx *ctx;
-
- maff1 = isl_multi_aff_cow(maff1);
- if (!maff1 || !maff2)
- goto error;
-
- ctx = isl_multi_aff_get_ctx(maff1);
- if (!isl_space_is_equal(maff1->space, maff2->space))
- isl_die(ctx, isl_error_invalid,
- "spaces don't match", goto error);
-
- for (i = 0; i < maff1->n; ++i) {
- maff1->p[i] = isl_aff_add(maff1->p[i],
- isl_aff_copy(maff2->p[i]));
- if (!maff1->p[i])
- goto error;
- }
+ return isl_multi_aff_bin_op(maff1, maff2, &isl_aff_add);
+}
- isl_multi_aff_free(maff2);
- return maff1;
-error:
- isl_multi_aff_free(maff1);
- isl_multi_aff_free(maff2);
- return NULL;
+/* Subtract "ma2" from "ma1" and return the result.
+ */
+__isl_give isl_multi_aff *isl_multi_aff_sub(__isl_take isl_multi_aff *ma1,
+ __isl_take isl_multi_aff *ma2)
+{
+ return isl_multi_aff_bin_op(ma1, ma2, &isl_aff_sub);
}
/* Given two multi-affine expressions A -> B and C -> D,
&pw_multi_aff_add);
}
+static __isl_give isl_pw_multi_aff *pw_multi_aff_sub(
+ __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
+{
+ return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
+ &isl_multi_aff_sub);
+}
+
+/* Subtract "pma2" from "pma1" and return the result.
+ */
+__isl_give isl_pw_multi_aff *isl_pw_multi_aff_sub(
+ __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
+{
+ return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
+ &pw_multi_aff_sub);
+}
+
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
{
return isl_pw_multi_aff_from_map(set);
}
+/* Convert "map" into an isl_pw_multi_aff (if possible) and
+ * add it to *user.
+ */
+static int pw_multi_aff_from_map(__isl_take isl_map *map, void *user)
+{
+ isl_union_pw_multi_aff **upma = user;
+ isl_pw_multi_aff *pma;
+
+ pma = isl_pw_multi_aff_from_map(map);
+ *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
+
+ return *upma ? 0 : -1;
+}
+
+/* Try and create an isl_union_pw_multi_aff that is equivalent
+ * to the given isl_union_map.
+ * The isl_union_map is required to be single-valued in each space.
+ * Otherwise, an error is produced.
+ */
+__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_union_map(
+ __isl_take isl_union_map *umap)
+{
+ isl_space *space;
+ isl_union_pw_multi_aff *upma;
+
+ space = isl_union_map_get_space(umap);
+ upma = isl_union_pw_multi_aff_empty(space);
+ if (isl_union_map_foreach_map(umap, &pw_multi_aff_from_map, &upma) < 0)
+ upma = isl_union_pw_multi_aff_free(upma);
+ isl_union_map_free(umap);
+
+ return upma;
+}
+
+/* Try and create an isl_union_pw_multi_aff that is equivalent
+ * to the given isl_union_set.
+ * The isl_union_set is required to be a singleton in each space.
+ * Otherwise, an error is produced.
+ */
+__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_union_set(
+ __isl_take isl_union_set *uset)
+{
+ return isl_union_pw_multi_aff_from_union_map(uset);
+}
+
/* Return the piecewise affine expression "set ? 1 : 0".
*/
__isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
#define BASE pw_aff
#include <isl_multi_templ.c>
+
+/* Scale the first elements of "ma" by the corresponding elements of "vec".
+ */
+__isl_give isl_multi_aff *isl_multi_aff_scale_vec(__isl_take isl_multi_aff *ma,
+ __isl_take isl_vec *vec)
+{
+ int i, n;
+ isl_int v;
+
+ if (!ma || !vec)
+ goto error;
+
+ n = isl_multi_aff_dim(ma, isl_dim_out);
+ if (isl_vec_size(vec) < n)
+ n = isl_vec_size(vec);
+
+ isl_int_init(v);
+ for (i = 0; i < n; ++i) {
+ isl_aff *aff;
+
+ isl_vec_get_element(vec, i, &v);
+
+ aff = isl_multi_aff_get_aff(ma, i);
+ aff = isl_aff_scale(aff, v);
+ ma = isl_multi_aff_set_aff(ma, i, aff);
+ }
+ isl_int_clear(v);
+
+ isl_vec_free(vec);
+ return ma;
+error:
+ isl_vec_free(vec);
+ isl_multi_aff_free(ma);
+ return NULL;
+}
+
+/* Scale the first elements of "pma" by the corresponding elements of "vec".
+ */
+__isl_give isl_pw_multi_aff *isl_pw_multi_aff_scale_vec(
+ __isl_take isl_pw_multi_aff *pma, __isl_take isl_vec *v)
+{
+ int i;
+
+ pma = isl_pw_multi_aff_cow(pma);
+ if (!pma || !v)
+ goto error;
+
+ for (i = 0; i < pma->n; ++i) {
+ pma->p[i].maff = isl_multi_aff_scale_vec(pma->p[i].maff,
+ isl_vec_copy(v));
+ if (!pma->p[i].maff)
+ goto error;
+ }
+
+ isl_vec_free(v);
+ return pma;
+error:
+ isl_vec_free(v);
+ isl_pw_multi_aff_free(pma);
+ return NULL;
+}
+
+/* This function is called for each entry of an isl_union_pw_multi_aff.
+ * Replace the entry by the result of applying isl_pw_multi_aff_scale_vec
+ * to the original entry with the isl_vec in "user" as extra argument.
+ */
+static int union_pw_multi_aff_scale_vec_entry(void **entry, void *user)
+{
+ isl_pw_multi_aff **pma = (isl_pw_multi_aff **) entry;
+ isl_vec *v = user;
+
+ *pma = isl_pw_multi_aff_scale_vec(*pma, isl_vec_copy(v));
+ if (!*pma)
+ return -1;
+
+ return 0;
+}
+
+/* Scale the first elements of "upma" by the corresponding elements of "vec".
+ */
+__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_scale_vec(
+ __isl_take isl_union_pw_multi_aff *upma, __isl_take isl_vec *v)
+{
+ upma = isl_union_pw_multi_aff_cow(upma);
+ if (!upma || !v)
+ goto error;
+
+ if (isl_hash_table_foreach(upma->dim->ctx, &upma->table,
+ &union_pw_multi_aff_scale_vec_entry, v) < 0)
+ goto error;
+
+ isl_vec_free(v);
+ return upma;
+error:
+ isl_vec_free(v);
+ isl_union_pw_multi_aff_free(upma);
+ return NULL;
+}