X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=926d6e16c14c8045e159c97268530328371d664f;hb=375839697529f1dd2ec13f3f692989c962d7995e;hp=d2a518c2c07ee1088c38d32a618a9a3e617f0508;hpb=6fb54548c5d0586c306e61f294ed0f93167a18fa;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index d2a518c..926d6e1 100644 --- a/isl_map.c +++ b/isl_map.c @@ -30,6 +30,7 @@ #include #include #include +#include static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type) { @@ -121,6 +122,8 @@ unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset) unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset) { + if (!bset) + return 0; return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div; } @@ -254,25 +257,42 @@ __isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset) return isl_space_copy(bset->dim); } -__isl_give isl_local_space *isl_basic_map_get_local_space( - __isl_keep isl_basic_map *bmap) +/* Extract the divs in "bmap" as a matrix. + */ +__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap) { int i; - isl_local_space *ls; + isl_ctx *ctx; + isl_mat *div; unsigned total; + unsigned cols; if (!bmap) return NULL; - total = isl_basic_map_total_dim(bmap); - ls = isl_local_space_alloc(isl_space_copy(bmap->dim), bmap->n_div); - if (!ls) + ctx = isl_basic_map_get_ctx(bmap); + total = isl_space_dim(bmap->dim, isl_dim_all); + cols = 1 + 1 + total + bmap->n_div; + div = isl_mat_alloc(ctx, bmap->n_div, cols); + if (!div) return NULL; for (i = 0; i < bmap->n_div; ++i) - isl_seq_cpy(ls->div->row[i], bmap->div[i], 2 + total); + isl_seq_cpy(div->row[i], bmap->div[i], cols); - return ls; + return div; +} + +__isl_give isl_local_space *isl_basic_map_get_local_space( + __isl_keep isl_basic_map *bmap) +{ + isl_mat *div; + + if (!bmap) + return NULL; + + div = isl_basic_map_get_divs(bmap); + return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div); } __isl_give isl_local_space *isl_basic_set_get_local_space( @@ -488,10 +508,19 @@ const char *isl_set_get_dim_name(__isl_keep isl_set *set, return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL; } +/* Does the given dimension have a name? + */ +int isl_set_has_dim_name(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned pos) +{ + return set ? isl_space_has_dim_name(set->dim, type, pos) : -1; +} + __isl_give isl_basic_map *isl_basic_map_set_dim_name( __isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, const char *s) { + bmap = isl_basic_map_cow(bmap); if (!bmap) return NULL; bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s); @@ -508,6 +537,7 @@ __isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map, { int i; + map = isl_map_cow(map); if (!map) return NULL; @@ -611,6 +641,12 @@ int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type, return isl_space_find_dim_by_name(map->dim, type, name); } +int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type, + const char *name) +{ + return isl_map_find_dim_by_name(set, type, name); +} + int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap) { if (!bmap) @@ -909,7 +945,7 @@ error: return NULL; } -static int align_params_map_map_and_test(__isl_keep isl_map *map1, +int isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1, __isl_keep isl_map *map2, int (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2)) { @@ -1560,11 +1596,9 @@ __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, map = isl_map_cow(map); if (!map) return NULL; - isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error); - first += pos(map->dim, type) - 1; - + for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_eliminate_vars(map->p[i], first, n); + map->p[i] = isl_basic_map_eliminate(map->p[i], type, first, n); if (!map->p[i]) goto error; } @@ -1752,6 +1786,12 @@ __isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set, type, first, n); } +/* Does the desciption of "bmap" depend on the specified dimensions? + * We also check whether the dimensions appear in any of the div definitions. + * In principle there is no need for this check. If the dimensions appear + * in a div definition, they also appear in the defining constraints of that + * div. + */ int isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap, enum isl_dim_type type, unsigned first, unsigned n) { @@ -1771,6 +1811,12 @@ int isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap, for (i = 0; i < bmap->n_ineq; ++i) if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0) return 1; + for (i = 0; i < bmap->n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) + continue; + if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0) + return 1; + } return 0; } @@ -1844,6 +1890,9 @@ __isl_give isl_basic_map *isl_basic_map_remove_unknown_divs( if (!div_is_unknown(bmap, i)) continue; bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1); + if (!bmap) + return NULL; + i = bmap->n_div; } return bmap; @@ -2429,6 +2478,12 @@ struct isl_basic_set *isl_basic_set_intersect( (struct isl_basic_map *)bset2); } +__isl_give isl_basic_set *isl_basic_set_intersect_params( + __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) +{ + return isl_basic_set_intersect(bset1, bset2); +} + /* Special case of isl_map_intersect, where both map1 and map2 * are convex, without any divs and such that either map1 or map2 * contains a single constraint. This constraint is then simply @@ -2481,7 +2536,10 @@ error: return NULL; } -static __isl_give isl_map *map_intersect(__isl_take isl_map *map1, +/* map2 may be either a parameter domain or a map living in the same + * space as map1. + */ +static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1, __isl_take isl_map *map2) { unsigned flags = 0; @@ -2508,13 +2566,6 @@ static __isl_give isl_map *map_intersect(__isl_take isl_map *map1, (map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 || map2->p[0]->n_eq + map2->p[0]->n_ineq == 1)) return map_intersect_add_constraint(map1, map2); - if (isl_map_is_params(map1) && !isl_map_is_params(map2)) - return isl_map_intersect(map2, map1); - if (isl_space_dim(map1->dim, isl_dim_all) == - isl_space_dim(map1->dim, isl_dim_param) && - isl_space_dim(map2->dim, isl_dim_all) != - isl_space_dim(map2->dim, isl_dim_param)) - return isl_map_intersect(map2, map1); if (isl_space_dim(map2->dim, isl_dim_all) != isl_space_dim(map2->dim, isl_dim_param)) @@ -2551,6 +2602,21 @@ error: return NULL; } +static __isl_give isl_map *map_intersect(__isl_take isl_map *map1, + __isl_take isl_map *map2) +{ + if (!map1 || !map2) + goto error; + if (!isl_space_is_equal(map1->dim, map2->dim)) + isl_die(isl_map_get_ctx(map1), isl_error_invalid, + "spaces don't match", goto error); + return map_intersect_internal(map1, map2); +error: + isl_map_free(map1); + isl_map_free(map2); + return NULL; +} + __isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1, __isl_take isl_map *map2) { @@ -2564,13 +2630,13 @@ struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2) (struct isl_map *)set2); } -/* The current implementation of isl_map_intersect accepts intersections - * with parameter domains, so we can just call that for now. +/* map_intersect_internal accepts intersections + * with parameter domains, so we can just call that function. */ static __isl_give isl_map *map_intersect_params(__isl_take isl_map *map, __isl_take isl_set *params) { - return isl_map_intersect(map, params); + return map_intersect_internal(map, params); } __isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map1, @@ -2655,6 +2721,10 @@ __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, bmap->n_div, bmap->n_eq, bmap->n_ineq); if (isl_basic_map_is_rational(bmap)) res = isl_basic_map_set_rational(res); + if (isl_basic_map_plain_is_empty(bmap)) { + isl_basic_map_free(bmap); + return isl_basic_map_set_to_empty(res); + } res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); return isl_basic_map_finalize(res); } @@ -2685,7 +2755,7 @@ static __isl_give isl_map *map_space_reset(__isl_take isl_map *map, { isl_space *space; - if (!isl_space_is_named_or_nested(map->dim, type)) + if (!map || !isl_space_is_named_or_nested(map->dim, type)) return map; space = isl_map_get_space(map); @@ -2959,7 +3029,7 @@ __isl_give isl_basic_map *isl_basic_map_project_out( isl_int *old; if (n == 0) - return bmap; + return basic_map_space_reset(bmap, type); if (!bmap) return NULL; @@ -3029,7 +3099,7 @@ __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map, return NULL; if (n == 0) - return map; + return map_space_reset(map, type); isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error); @@ -4494,7 +4564,9 @@ __isl_give isl_map *isl_map_alloc_space(__isl_take isl_space *dim, int n, if (!dim) return NULL; - isl_assert(dim->ctx, n >= 0, return NULL); + if (n < 0) + isl_die(dim->ctx, isl_error_internal, + "negative number of basic maps", goto error); map = isl_alloc(dim->ctx, struct isl_map, sizeof(struct isl_map) + (n - 1) * sizeof(struct isl_basic_map *)); @@ -4887,6 +4959,25 @@ struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset, isl_dim_set, dim, value); } +static int remove_if_empty(__isl_keep isl_map *map, int i) +{ + int empty = isl_basic_map_plain_is_empty(map->p[i]); + + if (empty < 0) + return -1; + if (!empty) + return 0; + + isl_basic_map_free(map->p[i]); + if (i != map->n - 1) { + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + map->p[i] = map->p[map->n - 1]; + } + map->n--; + + return 0; +} + struct isl_map *isl_map_fix_si(struct isl_map *map, enum isl_dim_type type, unsigned pos, int value) { @@ -4897,9 +4988,9 @@ struct isl_map *isl_map_fix_si(struct isl_map *map, return NULL; isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error); - for (i = 0; i < map->n; ++i) { + for (i = map->n - 1; i >= 0; --i) { map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value); - if (!map->p[i]) + if (remove_if_empty(map, i) < 0) goto error; } ISL_F_CLR(map, ISL_MAP_NORMALIZED); @@ -4956,9 +5047,9 @@ struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value) isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value); } -__isl_give isl_basic_map *isl_basic_map_lower_bound_si( - __isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned pos, int value) +static __isl_give isl_basic_map *basic_map_bound_si( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, int value, int upper) { int j; @@ -4972,8 +5063,13 @@ __isl_give isl_basic_map *isl_basic_map_lower_bound_si( if (j < 0) goto error; isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap)); - isl_int_set_si(bmap->ineq[j][pos], 1); - isl_int_set_si(bmap->ineq[j][0], -value); + if (upper) { + isl_int_set_si(bmap->ineq[j][pos], -1); + isl_int_set_si(bmap->ineq[j][0], value); + } else { + isl_int_set_si(bmap->ineq[j][pos], 1); + isl_int_set_si(bmap->ineq[j][0], -value); + } bmap = isl_basic_map_simplify(bmap); return isl_basic_map_finalize(bmap); error: @@ -4981,6 +5077,13 @@ error: return NULL; } +__isl_give isl_basic_map *isl_basic_map_lower_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, 0); +} + struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset, unsigned dim, isl_int value) { @@ -5001,8 +5104,8 @@ error: return NULL; } -__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, - enum isl_dim_type type, unsigned pos, int value) +static __isl_give isl_map *map_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value, int upper) { int i; @@ -5012,8 +5115,8 @@ __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error); for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_lower_bound_si(map->p[i], - type, pos, value); + map->p[i] = basic_map_bound_si(map->p[i], + type, pos, value, upper); if (!map->p[i]) goto error; } @@ -5024,6 +5127,18 @@ error: return NULL; } +__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value) +{ + return map_bound_si(map, type, pos, value, 0); +} + +__isl_give isl_map *isl_map_upper_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value) +{ + return map_bound_si(map, type, pos, value, 1); +} + __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set, enum isl_dim_type type, unsigned pos, int value) { @@ -5031,6 +5146,98 @@ __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set, isl_map_lower_bound_si((struct isl_map *)set, type, pos, value); } +__isl_give isl_set *isl_set_upper_bound_si(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, int value) +{ + return isl_map_upper_bound_si(set, type, pos, value); +} + +/* Bound the given variable of "bmap" from below (or above is "upper" + * is set) to "value". + */ +static __isl_give isl_basic_map *basic_map_bound( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, isl_int value, int upper) +{ + int j; + + if (!bmap) + return NULL; + if (pos >= isl_basic_map_dim(bmap, type)) + isl_die(bmap->ctx, isl_error_invalid, + "index out of bounds", goto error); + pos += isl_basic_map_offset(bmap, type); + bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_extend_constraints(bmap, 0, 1); + j = isl_basic_map_alloc_inequality(bmap); + if (j < 0) + goto error; + isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap)); + if (upper) { + isl_int_set_si(bmap->ineq[j][pos], -1); + isl_int_set(bmap->ineq[j][0], value); + } else { + isl_int_set_si(bmap->ineq[j][pos], 1); + isl_int_neg(bmap->ineq[j][0], value); + } + bmap = isl_basic_map_simplify(bmap); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* Bound the given variable of "map" from below (or above is "upper" + * is set) to "value". + */ +static __isl_give isl_map *map_bound(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value, int upper) +{ + int i; + + map = isl_map_cow(map); + if (!map) + return NULL; + + if (pos >= isl_map_dim(map, type)) + isl_die(map->ctx, isl_error_invalid, + "index out of bounds", goto error); + for (i = map->n - 1; i >= 0; --i) { + map->p[i] = basic_map_bound(map->p[i], type, pos, value, upper); + if (remove_if_empty(map, i) < 0) + goto error; + } + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + return map; +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_map *isl_map_lower_bound(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return map_bound(map, type, pos, value, 0); +} + +__isl_give isl_map *isl_map_upper_bound(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return map_bound(map, type, pos, value, 1); +} + +__isl_give isl_set *isl_set_lower_bound(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return isl_map_lower_bound(set, type, pos, value); +} + +__isl_give isl_set *isl_set_upper_bound(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return isl_map_upper_bound(set, type, pos, value); +} + struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim, isl_int value) { @@ -6623,6 +6830,12 @@ int isl_basic_map_is_subset( return is_subset; } +int isl_basic_set_is_subset(__isl_keep isl_basic_set *bset1, + __isl_keep isl_basic_set *bset2) +{ + return isl_basic_map_is_subset(bset1, bset2); +} + int isl_basic_map_is_equal( struct isl_basic_map *bmap1, struct isl_basic_map *bmap2) { @@ -6717,7 +6930,7 @@ static int map_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2) int isl_map_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2) { - return align_params_map_map_and_test(map1, map2, &map_is_equal); + return isl_map_align_params_map_map_and_test(map1, map2, &map_is_equal); } int isl_basic_map_is_strict_subset( @@ -6876,7 +7089,7 @@ struct isl_map *isl_basic_map_union( { struct isl_map *map; if (!bmap1 || !bmap2) - return NULL; + goto error; isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim), goto error); @@ -7126,16 +7339,8 @@ struct isl_map *isl_map_remove_empty_parts(struct isl_map *map) if (!map) return NULL; - for (i = map->n-1; i >= 0; --i) { - if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY)) - continue; - isl_basic_map_free(map->p[i]); - if (i != map->n-1) { - ISL_F_CLR(map, ISL_MAP_NORMALIZED); - map->p[i] = map->p[map->n-1]; - } - map->n--; - } + for (i = map->n - 1; i >= 0; --i) + remove_if_empty(map, i); return map; } @@ -8659,7 +8864,7 @@ int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset, return -1; bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset)); - tab = isl_tab_from_basic_set(bset); + tab = isl_tab_from_basic_set(bset, 0); if (!bound || !tab) goto error; @@ -9262,14 +9467,21 @@ __isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap, __isl_take isl_space *dim, __isl_take struct isl_dim_map *dim_map) { isl_basic_map *res; + unsigned flags; bmap = isl_basic_map_cow(bmap); if (!bmap || !dim || !dim_map) goto error; + flags = bmap->flags; + ISL_FL_CLR(flags, ISL_BASIC_MAP_FINAL); + ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED); + ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED_DIVS); res = isl_basic_map_alloc_space(dim, bmap->n_div, bmap->n_eq, bmap->n_ineq); res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); + if (res) + res->flags = flags; res = isl_basic_map_finalize(res); return res; error: @@ -9923,14 +10135,8 @@ __isl_give isl_set *isl_set_substitute(__isl_take isl_set *set, for (i = set->n - 1; i >= 0; --i) { set->p[i] = isl_basic_set_substitute(set->p[i], type, pos, subs); - if (!set->p[i]) + if (remove_if_empty(set, i) < 0) goto error; - if (isl_basic_set_plain_is_empty(set->p[i])) { - isl_basic_set_free(set->p[i]); - if (i != set->n - 1) - set->p[i] = set->p[set->n - 1]; - set->n--; - } } return set;