* 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 bmap;
}
+/* Remove all divs that are unknown or defined in terms of unknown divs.
+ */
+__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs(
+ __isl_take isl_basic_set *bset)
+{
+ return isl_basic_map_remove_unknown_divs(bset);
+}
+
__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
{
int i;
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 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 NULL;
}
+/* Return the union of "map1" and "map2", where we assume for now that
+ * "map1" and "map2" are disjoint. Note that the basic maps inside
+ * "map1" or "map2" may not be disjoint from each other.
+ * Also note that this function is also called from isl_map_union,
+ * which takes care of handling the situation where "map1" and "map2"
+ * may not be disjoint.
+ *
+ * If one of the inputs is empty, we can simply return the other input.
+ * Similarly, if one of the inputs is universal, then it is equal to the union.
+ */
static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1,
__isl_take isl_map *map2)
{
int i;
unsigned flags = 0;
struct isl_map *map = NULL;
+ int is_universe;
if (!map1 || !map2)
goto error;
return map1;
}
+ is_universe = isl_map_plain_is_universe(map1);
+ if (is_universe < 0)
+ goto error;
+ if (is_universe) {
+ isl_map_free(map2);
+ return map1;
+ }
+
+ is_universe = isl_map_plain_is_universe(map2);
+ if (is_universe < 0)
+ goto error;
+ if (is_universe) {
+ isl_map_free(map1);
+ return map2;
+ }
+
isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
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)
{
- return isl_map_reverse(
- isl_map_intersect_range(isl_map_reverse(map), 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_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_basic_map_plain_cmp(bset1, bset2);
}
-int isl_set_plain_cmp(const __isl_keep isl_set *set1,
- const __isl_keep isl_set *set2)
+int isl_set_plain_cmp(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
{
int i, cmp;
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,