* Copyright 2010 INRIA Saclay
* Copyright 2012 Ecole Normale Superieure
*
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, K.U.Leuven, Departement
* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
return NULL;
}
+/* Does the input or output tuple have a name?
+ */
+int isl_map_has_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type)
+{
+ return map ? isl_space_has_tuple_name(map->dim, type) : -1;
+}
+
const char *isl_map_get_tuple_name(__isl_keep isl_map *map,
enum isl_dim_type type)
{
return map;
}
-void isl_basic_map_free(struct isl_basic_map *bmap)
+void *isl_basic_map_free(__isl_take isl_basic_map *bmap)
{
if (!bmap)
- return;
+ return NULL;
if (--bmap->ref > 0)
- return;
+ return NULL;
isl_ctx_deref(bmap->ctx);
free(bmap->div);
isl_vec_free(bmap->sample);
isl_space_free(bmap->dim);
free(bmap);
+
+ return NULL;
}
-void isl_basic_set_free(struct isl_basic_set *bset)
+void *isl_basic_set_free(struct isl_basic_set *bset)
{
- isl_basic_map_free((struct isl_basic_map *)bset);
+ return isl_basic_map_free((struct isl_basic_map *)bset);
}
static int room_for_con(struct isl_basic_map *bmap, unsigned n)
return NULL;
}
+__isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_basic_map_remove_divs_involving_dims(bset, type, first, n);
+}
+
__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map,
enum isl_dim_type type, unsigned first, unsigned n)
{
if (!map1 || !map2)
goto error;
- if (isl_map_plain_is_empty(map1) &&
+ if ((isl_map_plain_is_empty(map1) ||
+ isl_map_plain_is_universe(map2)) &&
isl_space_is_equal(map1->dim, map2->dim)) {
isl_map_free(map2);
return map1;
}
- if (isl_map_plain_is_empty(map2) &&
+ if ((isl_map_plain_is_empty(map2) ||
+ isl_map_plain_is_universe(map1)) &&
isl_space_is_equal(map1->dim, map2->dim)) {
isl_map_free(map1);
return map2;
part = isl_basic_map_intersect(
isl_basic_map_copy(map1->p[i]),
isl_basic_map_copy(map2->p[j]));
- if (isl_basic_map_is_empty(part))
- isl_basic_map_free(part);
- else
- result = isl_map_add_basic_map(result, part);
+ if (isl_basic_map_is_empty(part) < 0)
+ goto error;
+ result = isl_map_add_basic_map(result, part);
if (!result)
goto error;
}
return bmap;
}
-__isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap,
- enum isl_dim_type type, unsigned pos, unsigned n)
+__isl_give isl_basic_map *isl_basic_map_insert_dims(
+ __isl_take isl_basic_map *bmap, enum isl_dim_type type,
+ unsigned pos, unsigned n)
{
isl_space *res_dim;
struct isl_basic_map *res;
return isl_basic_map_finalize(res);
}
+__isl_give isl_basic_set *isl_basic_set_insert_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned pos, unsigned n)
+{
+ return isl_basic_map_insert_dims(bset, type, pos, n);
+}
+
__isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
enum isl_dim_type type, unsigned n)
{
if (!bmap)
return NULL;
- return isl_basic_map_insert(bmap, type,
+ return isl_basic_map_insert_dims(bmap, type,
isl_basic_map_dim(bmap, type), n);
}
goto error;
for (i = 0; i < map->n; ++i) {
- map->p[i] = isl_basic_map_insert(map->p[i], type, pos, n);
+ map->p[i] = isl_basic_map_insert_dims(map->p[i], type, pos, n);
if (!map->p[i])
goto error;
}
return NULL;
}
-void isl_map_free(struct isl_map *map)
+void *isl_map_free(struct isl_map *map)
{
int i;
if (!map)
- return;
+ return NULL;
if (--map->ref > 0)
- return;
+ return NULL;
isl_ctx_deref(map->ctx);
for (i = 0; i < map->n; ++i)
isl_basic_map_free(map->p[i]);
isl_space_free(map->dim);
free(map);
+
+ return NULL;
}
struct isl_map *isl_map_extend(struct isl_map *base,
return basic_map_bound_si(bmap, type, pos, value, 0);
}
+/* Constrain the values of the given dimension to be no greater than "value".
+ */
+__isl_give isl_basic_map *isl_basic_map_upper_bound_si(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned pos, int value)
+{
+ return basic_map_bound_si(bmap, type, pos, value, 1);
+}
+
struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
unsigned dim, isl_int value)
{
return isl_basic_map_lexopt_pw_multi_aff(bmap, 0);
}
-/* Given a basic map "bmap", compute the lexicographically minimal
- * (or maximal) image element for each domain element in dom.
+#undef TYPE
+#define TYPE isl_pw_multi_aff
+#undef SUFFIX
+#define SUFFIX _pw_multi_aff
+#undef EMPTY
+#define EMPTY isl_pw_multi_aff_empty
+#undef ADD
+#define ADD isl_pw_multi_aff_union_add
+#include "isl_map_lexopt_templ.c"
+
+/* Given a map "map", compute the lexicographically minimal
+ * (or maximal) image element for each domain element in dom,
+ * in the form of an isl_pw_multi_aff.
* Set *empty to those elements in dom that do not have an image element.
*
- * We first make sure the basic sets in dom are disjoint and then
- * simply collect the results over each of the basic sets separately.
- * We could probably improve the efficiency a bit by moving the union
- * domain down into the parametric integer programming.
+ * We first compute the lexicographically minimal or maximal element
+ * in the first basic map. This results in a partial solution "res"
+ * and a subset "todo" of dom that still need to be handled.
+ * We then consider each of the remaining maps in "map" and successively
+ * update both "res" and "todo".
*/
-static __isl_give isl_map *basic_map_partial_lexopt(
- __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
- __isl_give isl_set **empty, int max)
+static __isl_give isl_pw_multi_aff *isl_map_partial_lexopt_aligned_pw_multi_aff(
+ __isl_take isl_map *map, __isl_take isl_set *dom,
+ __isl_give isl_set **empty, int max)
{
int i;
- struct isl_map *res;
+ isl_pw_multi_aff *res;
+ isl_set *todo;
- dom = isl_set_make_disjoint(dom);
- if (!dom)
+ if (!map || !dom)
goto error;
- if (isl_set_plain_is_empty(dom)) {
- res = isl_map_empty_like_basic_map(bmap);
- *empty = isl_set_empty_like(dom);
- isl_set_free(dom);
- isl_basic_map_free(bmap);
- return res;
+ if (isl_map_plain_is_empty(map)) {
+ if (empty)
+ *empty = dom;
+ else
+ isl_set_free(dom);
+ return isl_pw_multi_aff_from_map(map);
}
- res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
- isl_basic_set_copy(dom->p[0]), empty, max);
-
- for (i = 1; i < dom->n; ++i) {
- struct isl_map *res_i;
- struct isl_set *empty_i;
+ res = basic_map_partial_lexopt_pw_multi_aff(
+ isl_basic_map_copy(map->p[0]),
+ isl_set_copy(dom), &todo, max);
+
+ for (i = 1; i < map->n; ++i) {
+ isl_pw_multi_aff *res_i;
+ isl_set *todo_i;
- res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
- isl_basic_set_copy(dom->p[i]), &empty_i, max);
+ res_i = basic_map_partial_lexopt_pw_multi_aff(
+ isl_basic_map_copy(map->p[i]),
+ isl_set_copy(dom), &todo_i, max);
- res = isl_map_union_disjoint(res, res_i);
- *empty = isl_set_union_disjoint(*empty, empty_i);
+ if (max)
+ res = isl_pw_multi_aff_union_lexmax(res, res_i);
+ else
+ res = isl_pw_multi_aff_union_lexmin(res, res_i);
+
+ todo = isl_set_intersect(todo, todo_i);
}
isl_set_free(dom);
- isl_basic_map_free(bmap);
+ isl_map_free(map);
+
+ if (empty)
+ *empty = todo;
+ else
+ isl_set_free(todo);
+
return res;
error:
- *empty = NULL;
+ if (empty)
+ *empty = NULL;
isl_set_free(dom);
- isl_basic_map_free(bmap);
+ isl_map_free(map);
return NULL;
}
+#undef TYPE
+#define TYPE isl_map
+#undef SUFFIX
+#define SUFFIX
+#undef EMPTY
+#define EMPTY isl_map_empty
+#undef ADD
+#define ADD isl_map_union_disjoint
+#include "isl_map_lexopt_templ.c"
+
/* Given a map "map", compute the lexicographically minimal
* (or maximal) image element for each domain element in dom.
* Set *empty to those elements in dom that do not have an image element.
* in the first basic map. This results in a partial solution "res"
* and a subset "todo" of dom that still need to be handled.
* We then consider each of the remaining maps in "map" and successively
- * improve both "res" and "todo".
+ * update both "res" and "todo".
*
* Let res^k and todo^k be the results after k steps and let i = k + 1.
* Assume we are computing the lexicographical maximum.
return NULL;
}
-/* Given a map "map", compute the lexicographically minimal
- * (or maximal) image element for each domain element in dom.
- * Set *empty to those elements in dom that do not have an image element.
- *
- * Align parameters if needed and then call isl_map_partial_lexopt_aligned.
- */
-static __isl_give isl_map *isl_map_partial_lexopt(
- __isl_take isl_map *map, __isl_take isl_set *dom,
- __isl_give isl_set **empty, int max)
-{
- if (!map || !dom)
- goto error;
- if (isl_space_match(map->dim, isl_dim_param, dom->dim, isl_dim_param))
- return isl_map_partial_lexopt_aligned(map, dom, empty, max);
- if (!isl_space_has_named_params(map->dim) ||
- !isl_space_has_named_params(dom->dim))
- isl_die(map->ctx, isl_error_invalid,
- "unaligned unnamed parameters", goto error);
- map = isl_map_align_params(map, isl_map_get_space(dom));
- dom = isl_map_align_params(dom, isl_map_get_space(map));
- return isl_map_partial_lexopt_aligned(map, dom, empty, max);
-error:
- if (empty)
- *empty = NULL;
- isl_set_free(dom);
- isl_map_free(map);
- return NULL;
-}
-
__isl_give isl_map *isl_map_partial_lexmax(
__isl_take isl_map *map, __isl_take isl_set *dom,
__isl_give isl_set **empty)
return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
}
-__isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
-{
- struct isl_set *dom = NULL;
- isl_space *dom_dim;
-
- if (!map)
- goto error;
- dom_dim = isl_space_domain(isl_space_copy(map->dim));
- dom = isl_set_universe(dom_dim);
- return isl_map_partial_lexopt(map, dom, NULL, max);
-error:
- isl_map_free(map);
- return NULL;
-}
-
-__isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
-{
- return isl_map_lexopt(map, 0);
-}
-
-__isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
-{
- return isl_map_lexopt(map, 1);
-}
-
__isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
{
return (isl_set *)isl_map_lexmin((isl_map *)set);
isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
}
-static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map,
- __isl_take isl_set *set)
+/* Apply "fn" to pairs of elements from "map" and "set" and collect
+ * the results.
+ *
+ * "map" and "set" are assumed to be compatible and non-NULL.
+ */
+static __isl_give isl_map *map_intersect_set(__isl_take isl_map *map,
+ __isl_take isl_set *set,
+ __isl_give isl_basic_map *fn(__isl_take isl_basic_map *bmap,
+ __isl_take isl_basic_set *bset))
{
unsigned flags = 0;
struct isl_map *result;
int i, j;
- if (!map || !set)
- goto error;
-
- if (!isl_space_match(map->dim, isl_dim_param, set->dim, isl_dim_param))
- isl_die(set->ctx, isl_error_invalid,
- "parameters don't match", goto error);
-
- if (isl_space_dim(set->dim, isl_dim_set) != 0 &&
- !isl_map_compatible_range(map, set))
- isl_die(set->ctx, isl_error_invalid,
- "incompatible spaces", goto error);
-
if (isl_set_plain_is_universe(set)) {
isl_set_free(set);
return map;
result = isl_map_alloc_space(isl_space_copy(map->dim),
map->n * set->n, flags);
- if (!result)
- goto error;
- for (i = 0; i < map->n; ++i)
+ for (i = 0; result && i < map->n; ++i)
for (j = 0; j < set->n; ++j) {
result = isl_map_add_basic_map(result,
- isl_basic_map_intersect_range(
- isl_basic_map_copy(map->p[i]),
- isl_basic_set_copy(set->p[j])));
+ fn(isl_basic_map_copy(map->p[i]),
+ isl_basic_set_copy(set->p[j])));
if (!result)
- goto error;
+ break;
}
+
isl_map_free(map);
isl_set_free(set);
return result;
+}
+
+static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map,
+ __isl_take isl_set *set)
+{
+ if (!map || !set)
+ goto error;
+
+ if (!isl_map_compatible_range(map, set))
+ isl_die(set->ctx, isl_error_invalid,
+ "incompatible spaces", goto error);
+
+ return map_intersect_set(map, set, &isl_basic_map_intersect_range);
error:
isl_map_free(map);
isl_set_free(set);
return isl_map_align_params_map_map_and(map, set, &map_intersect_range);
}
-struct isl_map *isl_map_intersect_domain(
- struct isl_map *map, struct isl_set *set)
+static __isl_give isl_map *map_intersect_domain(__isl_take isl_map *map,
+ __isl_take isl_set *set)
+{
+ if (!map || !set)
+ goto error;
+
+ if (!isl_map_compatible_domain(map, set))
+ isl_die(set->ctx, isl_error_invalid,
+ "incompatible spaces", goto error);
+
+ return map_intersect_set(map, set, &isl_basic_map_intersect_domain);
+error:
+ isl_map_free(map);
+ isl_set_free(set);
+ return NULL;
+}
+
+__isl_give isl_map *isl_map_intersect_domain(__isl_take isl_map *map,
+ __isl_take isl_set *set)
{
- return isl_map_reverse(
- isl_map_intersect_range(isl_map_reverse(map), set));
+ return isl_map_align_params_map_map_and(map, set,
+ &map_intersect_domain);
}
static __isl_give isl_map *map_apply_domain(__isl_take isl_map *map1,
return NULL;
}
-__isl_give struct isl_basic_map *basic_map_identity(__isl_take isl_space *dims)
+static __isl_give isl_basic_map *basic_map_identity(__isl_take isl_space *dims)
{
struct isl_basic_map *bmap;
unsigned nparam;
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
return 1;
+ if (isl_basic_map_is_universe(bmap))
+ return 0;
+
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
struct isl_basic_map *copy = isl_basic_map_copy(bmap);
copy = isl_basic_map_remove_redundancies(copy);
return isl_map_dim_is_bounded((isl_map *)set, type, pos);
}
-static int has_bound(__isl_keep isl_map *map,
+static int has_any_bound(__isl_keep isl_map *map,
enum isl_dim_type type, unsigned pos,
int (*fn)(__isl_keep isl_basic_map *bmap,
enum isl_dim_type type, unsigned pos))
/* Return 1 if the specified dim is involved in any lower bound.
*/
-int isl_set_dim_has_lower_bound(__isl_keep isl_set *set,
+int isl_set_dim_has_any_lower_bound(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned pos)
{
- return has_bound(set, type, pos, &isl_basic_map_dim_has_lower_bound);
+ return has_any_bound(set, type, pos,
+ &isl_basic_map_dim_has_lower_bound);
}
/* Return 1 if the specified dim is involved in any upper bound.
*/
-int isl_set_dim_has_upper_bound(__isl_keep isl_set *set,
+int isl_set_dim_has_any_upper_bound(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned pos)
{
- return has_bound(set, type, pos, &isl_basic_map_dim_has_upper_bound);
+ return has_any_bound(set, type, pos,
+ &isl_basic_map_dim_has_upper_bound);
}
/* For each of the "n" variables starting at "first", determine
return NULL;
}
+/* Can we apply isl_basic_map_uncurry to "bmap"?
+ * That is, does it have a nested relation in its domain?
+ */
+int isl_basic_map_can_uncurry(__isl_keep isl_basic_map *bmap)
+{
+ if (!bmap)
+ return -1;
+
+ return isl_space_can_uncurry(bmap->dim);
+}
+
+/* Can we apply isl_map_uncurry to "map"?
+ * That is, does it have a nested relation in its domain?
+ */
+int isl_map_can_uncurry(__isl_keep isl_map *map)
+{
+ if (!map)
+ return -1;
+
+ return isl_space_can_uncurry(map->dim);
+}
+
+/* Given a basic map A -> (B -> C), return the corresponding basic map
+ * (A -> B) -> C.
+ */
+__isl_give isl_basic_map *isl_basic_map_uncurry(__isl_take isl_basic_map *bmap)
+{
+
+ if (!bmap)
+ return NULL;
+
+ if (!isl_basic_map_can_uncurry(bmap))
+ isl_die(bmap->ctx, isl_error_invalid,
+ "basic map cannot be uncurried",
+ return isl_basic_map_free(bmap));
+ bmap->dim = isl_space_uncurry(bmap->dim);
+ if (!bmap->dim)
+ return isl_basic_map_free(bmap);
+ return bmap;
+}
+
+/* Given a map A -> (B -> C), return the corresponding map
+ * (A -> B) -> C.
+ */
+__isl_give isl_map *isl_map_uncurry(__isl_take isl_map *map)
+{
+ int i;
+
+ if (!map)
+ return NULL;
+
+ if (!isl_map_can_uncurry(map))
+ isl_die(map->ctx, isl_error_invalid, "map cannot be uncurried",
+ return isl_map_free(map));
+
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_uncurry(map->p[i]);
+ if (!map->p[i])
+ return isl_map_free(map);
+ }
+
+ map->dim = isl_space_uncurry(map->dim);
+ if (!map->dim)
+ return isl_map_free(map);
+
+ return map;
+}
+
/* Construct a basic map mapping the domain of the affine expression
* to a one-dimensional range prescribed by the affine expression.
*/
}
/* Add a constraint imposing that the value of the first dimension is
+ * greater than or equal to that of the second.
+ */
+__isl_give isl_basic_map *isl_basic_map_order_ge(__isl_take isl_basic_map *bmap,
+ enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
+{
+ isl_constraint *c;
+ isl_local_space *ls;
+
+ if (!bmap)
+ return NULL;
+
+ if (pos1 >= isl_basic_map_dim(bmap, type1))
+ isl_die(bmap->ctx, isl_error_invalid,
+ "index out of bounds", return isl_basic_map_free(bmap));
+ if (pos2 >= isl_basic_map_dim(bmap, type2))
+ isl_die(bmap->ctx, isl_error_invalid,
+ "index out of bounds", return isl_basic_map_free(bmap));
+
+ if (type1 == type2 && pos1 == pos2)
+ return bmap;
+
+ ls = isl_local_space_from_space(isl_basic_map_get_space(bmap));
+ c = isl_inequality_alloc(ls);
+ c = isl_constraint_set_coefficient_si(c, type1, pos1, 1);
+ c = isl_constraint_set_coefficient_si(c, type2, pos2, -1);
+ bmap = isl_basic_map_add_constraint(bmap, c);
+
+ return bmap;
+}
+
+/* Add a constraint imposing that the value of the first dimension is
* greater than that of the second.
*/
__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map,