X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=815437189cba44243b2df003b2ab1053fe37df08;hb=225c7e232df74cf93c7b0c1f945bbdf7581cc455;hp=a43f5af1f02e65e1591ec2a9c941d4de6c875cf4;hpb=c872d1883ffe12e392450c48e231eefc3f41a53f;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index a43f5af..8154371 100644 --- a/isl_map.c +++ b/isl_map.c @@ -690,6 +690,76 @@ int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset) return isl_basic_map_is_rational(bset); } +/* Does "bmap" contain any rational points? + * + * If "bmap" has an equality for each dimension, equating the dimension + * to an integer constant, then it has no rational points, even if it + * is marked as rational. + */ +int isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap) +{ + int has_rational = 1; + unsigned total; + + if (!bmap) + return -1; + if (isl_basic_map_plain_is_empty(bmap)) + return 0; + if (!isl_basic_map_is_rational(bmap)) + return 0; + bmap = isl_basic_map_copy(bmap); + bmap = isl_basic_map_implicit_equalities(bmap); + if (!bmap) + return -1; + total = isl_basic_map_total_dim(bmap); + if (bmap->n_eq == total) { + int i, j; + for (i = 0; i < bmap->n_eq; ++i) { + j = isl_seq_first_non_zero(bmap->eq[i] + 1, total); + if (j < 0) + break; + if (!isl_int_is_one(bmap->eq[i][1 + j]) && + !isl_int_is_negone(bmap->eq[i][1 + j])) + break; + j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1, + total - j - 1); + if (j >= 0) + break; + } + if (i == bmap->n_eq) + has_rational = 0; + } + isl_basic_map_free(bmap); + + return has_rational; +} + +/* Does "map" contain any rational points? + */ +int isl_map_has_rational(__isl_keep isl_map *map) +{ + int i; + int has_rational; + + if (!map) + return -1; + for (i = 0; i < map->n; ++i) { + has_rational = isl_basic_map_has_rational(map->p[i]); + if (has_rational < 0) + return -1; + if (has_rational) + return 1; + } + return 0; +} + +/* Does "set" contain any rational points? + */ +int isl_set_has_rational(__isl_keep isl_set *set) +{ + return isl_map_has_rational(set); +} + /* Is this basic set a parameter domain? */ int isl_basic_set_is_params(__isl_keep isl_basic_set *bset) @@ -2133,6 +2203,14 @@ __isl_give isl_basic_map *isl_basic_map_remove_unknown_divs( 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; @@ -2786,12 +2864,14 @@ static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1, 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; @@ -4180,6 +4260,11 @@ int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div) bmap->div[div]); } +int isl_basic_set_add_div_constraints(struct isl_basic_set *bset, unsigned div) +{ + return isl_basic_map_add_div_constraints(bset, div); +} + struct isl_basic_set *isl_basic_map_underlying_set( struct isl_basic_map *bmap) { @@ -5330,6 +5415,15 @@ __isl_give isl_basic_map *isl_basic_map_lower_bound_si( 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) { @@ -6427,12 +6521,23 @@ error: 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; @@ -6446,6 +6551,22 @@ static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1, 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) && @@ -6508,25 +6629,20 @@ struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2) 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; @@ -6538,20 +6654,31 @@ static __isl_give isl_map *map_intersect_range(__isl_take isl_map *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); @@ -6564,11 +6691,28 @@ __isl_give isl_map *isl_map_intersect_range(__isl_take isl_map *map, 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, @@ -7249,6 +7393,9 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap) 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); @@ -7464,7 +7611,7 @@ struct isl_basic_map *isl_basic_map_align_divs( struct isl_basic_map *dst, struct isl_basic_map *src) { int i; - unsigned total = isl_space_dim(src->dim, isl_dim_all); + unsigned total; if (!dst || !src) goto error; @@ -7481,6 +7628,7 @@ struct isl_basic_map *isl_basic_map_align_divs( src->n_div, 0, 2 * src->n_div); if (!dst) return NULL; + total = isl_space_dim(src->dim, isl_dim_all); for (i = 0; i < src->n_div; ++i) { int j = find_div(dst, src, i); if (j < 0) { @@ -8134,8 +8282,7 @@ int isl_basic_set_plain_cmp(const __isl_keep isl_basic_set *bset1, 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; @@ -10217,6 +10364,78 @@ error: 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. */ @@ -10458,6 +10677,37 @@ error: } /* 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, @@ -10559,6 +10809,10 @@ __isl_give isl_aff *isl_basic_set_get_div(__isl_keep isl_basic_set *bset, * are replaced by * * a f + d g + * + * We currently require that "subs" is an integral expression. + * Handling rational expressions may require us to add stride constraints + * as we do in isl_basic_set_preimage_multi_aff. */ __isl_give isl_basic_set *isl_basic_set_substitute( __isl_take isl_basic_set *bset, @@ -10582,6 +10836,9 @@ __isl_give isl_basic_set *isl_basic_set_substitute( if (isl_local_space_dim(subs->ls, isl_dim_div) != 0) isl_die(ctx, isl_error_unsupported, "cannot handle divs yet", goto error); + if (!isl_int_is_one(subs->v->el[0])) + isl_die(ctx, isl_error_invalid, + "can only substitute integer expressions", goto error); pos += isl_basic_set_offset(bset, type); @@ -10650,3 +10907,378 @@ error: isl_set_free(set); return NULL; } + +/* Check if the range of "ma" is compatible with "space". + * Return -1 if anything is wrong. + */ +static int check_space_compatible_range_multi_aff( + __isl_keep isl_space *space, __isl_keep isl_multi_aff *ma) +{ + int m; + isl_space *ma_space; + + ma_space = isl_multi_aff_get_space(ma); + m = isl_space_is_range_internal(space, ma_space); + isl_space_free(ma_space); + if (m >= 0 && !m) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "spaces don't match", return -1); + return m; +} + +/* Check if the range of "ma" is compatible with "bset". + * Return -1 if anything is wrong. + */ +static int check_basic_set_compatible_range_multi_aff( + __isl_keep isl_basic_set *bset, __isl_keep isl_multi_aff *ma) +{ + return check_space_compatible_range_multi_aff(bset->dim, ma); +} + +/* Copy the divs from "ma" to "bset", adding zeros for the coefficients + * of the other divs in "bset". + */ +static int set_ma_divs(__isl_keep isl_basic_set *bset, + __isl_keep isl_multi_aff *ma, int n_div) +{ + int i; + isl_local_space *ls; + + if (n_div == 0) + return 0; + + ls = isl_aff_get_domain_local_space(ma->p[0]); + if (!ls) + return -1; + + for (i = 0; i < n_div; ++i) { + isl_seq_cpy(bset->div[i], ls->div->row[i], ls->div->n_col); + isl_seq_clr(bset->div[i] + ls->div->n_col, bset->n_div - n_div); + if (isl_basic_set_add_div_constraints(bset, i) < 0) + goto error; + } + + isl_local_space_free(ls); + return 0; +error: + isl_local_space_free(ls); + return -1; +} + +/* How many stride constraints does "ma" enforce? + * That is, how many of the affine expressions have a denominator + * different from one? + */ +static int multi_aff_strides(__isl_keep isl_multi_aff *ma) +{ + int i; + int strides = 0; + + for (i = 0; i < ma->n; ++i) + if (!isl_int_is_one(ma->p[i]->v->el[0])) + strides++; + + return strides; +} + +/* For each affine expression in ma of the form + * + * x_i = (f_i y + h_i)/m_i + * + * with m_i different from one, add a constraint to "bset" + * of the form + * + * f_i y + h_i = m_i alpha_i + * + * with alpha_i an additional existentially quantified variable. + */ +static __isl_give isl_basic_set *add_ma_strides( + __isl_take isl_basic_set *bset, __isl_keep isl_multi_aff *ma) +{ + int i, k; + int div; + int total; + + total = isl_basic_set_total_dim(bset); + for (i = 0; i < ma->n; ++i) { + int len; + + if (isl_int_is_one(ma->p[i]->v->el[0])) + continue; + div = isl_basic_set_alloc_div(bset); + k = isl_basic_set_alloc_equality(bset); + if (div < 0 || k < 0) + goto error; + isl_int_set_si(bset->div[div][0], 0); + len = ma->p[i]->v->size; + isl_seq_cpy(bset->eq[k], ma->p[i]->v->el + 1, len - 1); + isl_seq_clr(bset->eq[k] + len - 1, 1 + total - (len - 1)); + isl_int_neg(bset->eq[k][1 + total], ma->p[i]->v->el[0]); + total++; + } + + return bset; +error: + isl_basic_set_free(bset); + return NULL; +} + +/* Compute the preimage of "bset" under the function represented by "ma". + * In other words, plug in "ma" in "bset". The result is a basic set + * that lives in the domain space of "ma". + * + * If bset is represented by + * + * A(p) + B x + C(divs) >= 0 + * + * and ma is represented by + * + * x = D(p) + F(y) + G(divs') + * + * then the result is + * + * A(p) + B D(p) + B F(y) + B G(divs') + C(divs) >= 0 + * + * The divs in the input set are similarly adjusted. + * In particular + * + * floor((a_i(p) + b_i x + c_i(divs))/n_i) + * + * becomes + * + * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i) + * + * If bset is not a rational set and if F(y) involves any denominators + * + * x_i = (f_i y + h_i)/m_i + * + * the additional constraints are added to ensure that we only + * map back integer points. That is we enforce + * + * f_i y + h_i = m_i alpha_i + * + * with alpha_i an additional existentially quantified variable. + * + * We first copy over the divs from "ma". + * Then we add the modified constraints and divs from "bset". + * Finally, we add the stride constraints, if needed. + */ +__isl_give isl_basic_set *isl_basic_set_preimage_multi_aff( + __isl_take isl_basic_set *bset, __isl_take isl_multi_aff *ma) +{ + int i, k; + isl_space *space; + isl_basic_set *res = NULL; + int n_div_bset, n_div_ma; + isl_int f, c1, c2, g; + int rational, strides; + + isl_int_init(f); + isl_int_init(c1); + isl_int_init(c2); + isl_int_init(g); + + ma = isl_multi_aff_align_divs(ma); + if (!bset || !ma) + goto error; + if (check_basic_set_compatible_range_multi_aff(bset, ma) < 0) + goto error; + + n_div_bset = isl_basic_set_dim(bset, isl_dim_div); + n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0; + + space = isl_space_domain(isl_multi_aff_get_space(ma)); + rational = isl_basic_set_is_rational(bset); + strides = rational ? 0 : multi_aff_strides(ma); + res = isl_basic_set_alloc_space(space, n_div_ma + n_div_bset + strides, + bset->n_eq + strides, bset->n_ineq + 2 * n_div_ma); + if (rational) + res = isl_basic_set_set_rational(res); + + for (i = 0; i < n_div_ma + n_div_bset; ++i) + if (isl_basic_set_alloc_div(res) < 0) + goto error; + + if (set_ma_divs(res, ma, n_div_ma) < 0) + goto error; + + for (i = 0; i < bset->n_eq; ++i) { + k = isl_basic_set_alloc_equality(res); + if (k < 0) + goto error; + isl_seq_preimage(res->eq[k], bset->eq[i], ma, n_div_ma, + n_div_bset, f, c1, c2, g, 0); + } + + for (i = 0; i < bset->n_ineq; ++i) { + k = isl_basic_set_alloc_inequality(res); + if (k < 0) + goto error; + isl_seq_preimage(res->ineq[k], bset->ineq[i], ma, n_div_ma, + n_div_bset, f, c1, c2, g, 0); + } + + for (i = 0; i < bset->n_div; ++i) { + if (isl_int_is_zero(bset->div[i][0])) { + isl_int_set_si(res->div[n_div_ma + i][0], 0); + continue; + } + isl_seq_preimage(res->div[n_div_ma + i], bset->div[i], + ma, n_div_ma, n_div_bset, f, c1, c2, g, 1); + } + + if (strides) + res = add_ma_strides(res, ma); + + isl_int_clear(f); + isl_int_clear(c1); + isl_int_clear(c2); + isl_int_clear(g); + isl_basic_set_free(bset); + isl_multi_aff_free(ma); + res = isl_basic_set_simplify(res); + return isl_basic_set_finalize(res); +error: + isl_int_clear(f); + isl_int_clear(c1); + isl_int_clear(c2); + isl_int_clear(g); + isl_basic_set_free(bset); + isl_multi_aff_free(ma); + isl_basic_set_free(res); + return NULL; +} + +/* Check if the range of "ma" is compatible with "set". + * Return -1 if anything is wrong. + */ +static int check_set_compatible_range_multi_aff( + __isl_keep isl_set *set, __isl_keep isl_multi_aff *ma) +{ + return check_space_compatible_range_multi_aff(set->dim, ma); +} + +/* Compute the preimage of "set" under the function represented by "ma". + * In other words, plug in "ma" in "set. The result is a set + * that lives in the domain space of "ma". + */ +static __isl_give isl_set *set_preimage_multi_aff(__isl_take isl_set *set, + __isl_take isl_multi_aff *ma) +{ + int i; + + set = isl_set_cow(set); + ma = isl_multi_aff_align_divs(ma); + if (!set || !ma) + goto error; + if (check_set_compatible_range_multi_aff(set, ma) < 0) + goto error; + + for (i = 0; i < set->n; ++i) { + set->p[i] = isl_basic_set_preimage_multi_aff(set->p[i], + isl_multi_aff_copy(ma)); + if (!set->p[i]) + goto error; + } + + isl_space_free(set->dim); + set->dim = isl_multi_aff_get_domain_space(ma); + if (!set->dim) + goto error; + + isl_multi_aff_free(ma); + if (set->n > 1) + ISL_F_CLR(set, ISL_MAP_DISJOINT); + ISL_F_CLR(set, ISL_SET_NORMALIZED); + return set; +error: + isl_multi_aff_free(ma); + isl_set_free(set); + return NULL; +} + +__isl_give isl_set *isl_set_preimage_multi_aff(__isl_take isl_set *set, + __isl_take isl_multi_aff *ma) +{ + if (!set || !ma) + goto error; + + if (isl_space_match(set->dim, isl_dim_param, ma->space, isl_dim_param)) + return set_preimage_multi_aff(set, ma); + + if (!isl_space_has_named_params(set->dim) || + !isl_space_has_named_params(ma->space)) + isl_die(set->ctx, isl_error_invalid, + "unaligned unnamed parameters", goto error); + set = isl_set_align_params(set, isl_multi_aff_get_space(ma)); + ma = isl_multi_aff_align_params(ma, isl_set_get_space(set)); + + return set_preimage_multi_aff(set, ma); +error: + isl_multi_aff_free(ma); + return isl_set_free(set); +} + +/* Compute the preimage of "set" under the function represented by "pma". + * In other words, plug in "pma" in "set. The result is a set + * that lives in the domain space of "pma". + */ +static __isl_give isl_set *set_preimage_pw_multi_aff(__isl_take isl_set *set, + __isl_take isl_pw_multi_aff *pma) +{ + int i; + isl_set *res; + + if (!pma) + goto error; + + if (pma->n == 0) { + isl_pw_multi_aff_free(pma); + res = isl_set_empty(isl_set_get_space(set)); + isl_set_free(set); + return res; + } + + res = isl_set_preimage_multi_aff(isl_set_copy(set), + isl_multi_aff_copy(pma->p[0].maff)); + res = isl_set_intersect(res, isl_set_copy(pma->p[0].set)); + + for (i = 1; i < pma->n; ++i) { + isl_set *res_i; + + res_i = isl_set_preimage_multi_aff(isl_set_copy(set), + isl_multi_aff_copy(pma->p[i].maff)); + res_i = isl_set_intersect(res_i, isl_set_copy(pma->p[i].set)); + res = isl_set_union(res, res_i); + } + + isl_pw_multi_aff_free(pma); + isl_set_free(set); + return res; +error: + isl_pw_multi_aff_free(pma); + isl_set_free(set); + return NULL; +} + +__isl_give isl_set *isl_set_preimage_pw_multi_aff(__isl_take isl_set *set, + __isl_take isl_pw_multi_aff *pma) +{ + if (!set || !pma) + goto error; + + if (isl_space_match(set->dim, isl_dim_param, pma->dim, isl_dim_param)) + return set_preimage_pw_multi_aff(set, pma); + + if (!isl_space_has_named_params(set->dim) || + !isl_space_has_named_params(pma->dim)) + isl_die(set->ctx, isl_error_invalid, + "unaligned unnamed parameters", goto error); + set = isl_set_align_params(set, isl_pw_multi_aff_get_space(pma)); + pma = isl_pw_multi_aff_align_params(pma, isl_set_get_space(set)); + + return set_preimage_pw_multi_aff(set, pma); +error: + isl_pw_multi_aff_free(pma); + return isl_set_free(set); +}