1789 lines · c
1/*2 * Copyright 2011 INRIA Saclay3 * Copyright 2012-2014 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,9 * 91893 Orsay, France10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France11 */12 13#include <isl_ctx_private.h>14#include <isl/id.h>15#include <isl_map_private.h>16#include <isl_local_space_private.h>17#include <isl_space_private.h>18#include <isl_mat_private.h>19#include <isl_aff_private.h>20#include <isl_vec_private.h>21#include <isl_point_private.h>22#include <isl_seq.h>23#include <isl_local.h>24 25isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)26{27 return ls ? ls->dim->ctx : NULL;28}29 30/* Return a hash value that digests "ls".31 */32uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls)33{34 uint32_t hash, space_hash, div_hash;35 36 if (!ls)37 return 0;38 39 hash = isl_hash_init();40 space_hash = isl_space_get_full_hash(isl_local_space_peek_space(ls));41 isl_hash_hash(hash, space_hash);42 div_hash = isl_mat_get_hash(ls->div);43 isl_hash_hash(hash, div_hash);44 45 return hash;46}47 48__isl_give isl_local_space *isl_local_space_alloc_div(49 __isl_take isl_space *space, __isl_take isl_mat *div)50{51 isl_ctx *ctx;52 isl_local_space *ls = NULL;53 54 if (!space || !div)55 goto error;56 57 ctx = isl_space_get_ctx(space);58 ls = isl_calloc_type(ctx, struct isl_local_space);59 if (!ls)60 goto error;61 62 ls->ref = 1;63 ls->dim = space;64 ls->div = div;65 66 return ls;67error:68 isl_mat_free(div);69 isl_space_free(space);70 isl_local_space_free(ls);71 return NULL;72}73 74__isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *space,75 unsigned n_div)76{77 isl_ctx *ctx;78 isl_mat *div;79 isl_size total;80 81 if (!space)82 return NULL;83 84 total = isl_space_dim(space, isl_dim_all);85 if (total < 0)86 return isl_local_space_from_space(isl_space_free(space));87 88 ctx = isl_space_get_ctx(space);89 div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);90 return isl_local_space_alloc_div(space, div);91}92 93__isl_give isl_local_space *isl_local_space_from_space(94 __isl_take isl_space *space)95{96 return isl_local_space_alloc(space, 0);97}98 99__isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)100{101 if (!ls)102 return NULL;103 104 ls->ref++;105 return ls;106}107 108__isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)109{110 if (!ls)111 return NULL;112 113 return isl_local_space_alloc_div(isl_space_copy(ls->dim),114 isl_mat_copy(ls->div));115 116}117 118__isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)119{120 if (!ls)121 return NULL;122 123 if (ls->ref == 1)124 return ls;125 ls->ref--;126 return isl_local_space_dup(ls);127}128 129__isl_null isl_local_space *isl_local_space_free(130 __isl_take isl_local_space *ls)131{132 if (!ls)133 return NULL;134 135 if (--ls->ref > 0)136 return NULL;137 138 isl_space_free(ls->dim);139 isl_mat_free(ls->div);140 141 free(ls);142 143 return NULL;144}145 146/* Is the local space that of a parameter domain?147 */148isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls)149{150 if (!ls)151 return isl_bool_error;152 return isl_space_is_params(ls->dim);153}154 155/* Is the local space that of a set?156 */157isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls)158{159 return ls ? isl_space_is_set(ls->dim) : isl_bool_error;160}161 162#undef TYPE163#define TYPE isl_local_space164 165#include "isl_type_has_equal_space_bin_templ.c"166#include "isl_type_has_space_templ.c"167 168/* Check that the space of "ls" is equal to "space".169 */170static isl_stat isl_local_space_check_has_space(__isl_keep isl_local_space *ls,171 __isl_keep isl_space *space)172{173 isl_bool ok;174 175 ok = isl_local_space_has_space(ls, space);176 if (ok < 0)177 return isl_stat_error;178 if (!ok)179 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,180 "spaces don't match", return isl_stat_error);181 return isl_stat_ok;182}183 184/* Return true if the two local spaces are identical, with identical185 * expressions for the integer divisions.186 */187isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1,188 __isl_keep isl_local_space *ls2)189{190 isl_bool equal;191 192 equal = isl_local_space_has_equal_space(ls1, ls2);193 if (equal < 0 || !equal)194 return equal;195 196 if (!isl_local_space_divs_known(ls1))197 return isl_bool_false;198 if (!isl_local_space_divs_known(ls2))199 return isl_bool_false;200 201 return isl_mat_is_equal(ls1->div, ls2->div);202}203 204/* Compare two isl_local_spaces.205 *206 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"207 * than "ls2" and 0 if they are equal.208 */209int isl_local_space_cmp(__isl_keep isl_local_space *ls1,210 __isl_keep isl_local_space *ls2)211{212 int cmp;213 214 if (ls1 == ls2)215 return 0;216 if (!ls1)217 return -1;218 if (!ls2)219 return 1;220 221 cmp = isl_space_cmp(ls1->dim, ls2->dim);222 if (cmp != 0)223 return cmp;224 225 return isl_local_cmp(ls1->div, ls2->div);226}227 228isl_size isl_local_space_dim(__isl_keep isl_local_space *ls,229 enum isl_dim_type type)230{231 if (!ls)232 return isl_size_error;233 if (type == isl_dim_div)234 return ls->div->n_row;235 if (type == isl_dim_all) {236 isl_size dim = isl_space_dim(ls->dim, isl_dim_all);237 if (dim < 0)238 return isl_size_error;239 return dim + ls->div->n_row;240 }241 return isl_space_dim(ls->dim, type);242}243 244#undef TYPE245#define TYPE isl_local_space246#include "check_type_range_templ.c"247 248/* Return the position of the variables of the given type249 * within the sequence of variables of "ls".250 */251isl_size isl_local_space_var_offset(__isl_keep isl_local_space *ls,252 enum isl_dim_type type)253{254 isl_space *space;255 256 space = isl_local_space_peek_space(ls);257 if (space < 0)258 return isl_size_error;259 switch (type) {260 case isl_dim_param:261 case isl_dim_in:262 case isl_dim_out: return isl_space_offset(space, type);263 case isl_dim_div: return isl_space_dim(space, isl_dim_all);264 case isl_dim_cst:265 default:266 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,267 "invalid dimension type", return isl_size_error);268 }269}270 271/* Return the position of the coefficients of the variables of the given type272 * within the sequence of coefficients of "ls".273 */274unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,275 enum isl_dim_type type)276{277 if (!ls)278 return 0;279 280 switch (type) {281 case isl_dim_cst: return 0;282 case isl_dim_param:283 case isl_dim_in:284 case isl_dim_out:285 case isl_dim_div: return 1 + isl_local_space_var_offset(ls, type);286 default: return 0;287 }288}289 290/* Return the position of the dimension of the given type and name291 * in "ls".292 * Return -1 if no such dimension can be found.293 */294int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls,295 enum isl_dim_type type, const char *name)296{297 if (!ls)298 return -1;299 if (type == isl_dim_div)300 return -1;301 return isl_space_find_dim_by_name(ls->dim, type, name);302}303 304/* Does the given dimension have a name?305 */306isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,307 enum isl_dim_type type, unsigned pos)308{309 return ls ? isl_space_has_dim_name(ls->dim, type, pos) : isl_bool_error;310}311 312const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,313 enum isl_dim_type type, unsigned pos)314{315 return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;316}317 318isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,319 enum isl_dim_type type, unsigned pos)320{321 return ls ? isl_space_has_dim_id(ls->dim, type, pos) : isl_bool_error;322}323 324__isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,325 enum isl_dim_type type, unsigned pos)326{327 return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;328}329 330/* Return the argument of the integer division at position "pos" in "ls".331 * All local variables in "ls" are known to have a (complete) explicit332 * representation.333 */334static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos)335{336 isl_aff *aff;337 338 aff = isl_aff_alloc(isl_local_space_copy(ls));339 if (!aff)340 return NULL;341 isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);342 return aff;343}344 345/* Return the argument of the integer division at position "pos" in "ls".346 * The integer division at that position is known to have a complete347 * explicit representation, but some of the others do not.348 * Remove them first because the domain of an isl_aff349 * is not allowed to have unknown local variables.350 */351static __isl_give isl_aff *drop_unknown_divs_and_extract_div(352 __isl_keep isl_local_space *ls, int pos)353{354 int i;355 isl_size n;356 isl_bool unknown;357 isl_aff *aff;358 359 n = isl_local_space_dim(ls, isl_dim_div);360 if (n < 0)361 return NULL;362 ls = isl_local_space_copy(ls);363 for (i = n - 1; i >= 0; --i) {364 unknown = isl_local_space_div_is_marked_unknown(ls, i);365 if (unknown < 0)366 ls = isl_local_space_free(ls);367 else if (!unknown)368 continue;369 ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1);370 if (pos > i)371 --pos;372 }373 aff = extract_div(ls, pos);374 isl_local_space_free(ls);375 return aff;376}377 378/* Return the argument of the integer division at position "pos" in "ls".379 * The integer division is assumed to have a complete explicit380 * representation. If some of the other integer divisions381 * do not have an explicit representation, then they need382 * to be removed first because the domain of an isl_aff383 * is not allowed to have unknown local variables.384 */385__isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,386 int pos)387{388 isl_bool known;389 390 if (!ls)391 return NULL;392 393 if (pos < 0 || pos >= ls->div->n_row)394 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,395 "index out of bounds", return NULL);396 397 known = isl_local_space_div_is_known(ls, pos);398 if (known < 0)399 return NULL;400 if (!known)401 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,402 "expression of div unknown", return NULL);403 if (!isl_local_space_is_set(ls))404 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,405 "cannot represent divs of map spaces", return NULL);406 407 known = isl_local_space_divs_known(ls);408 if (known < 0)409 return NULL;410 if (known)411 return extract_div(ls, pos);412 else413 return drop_unknown_divs_and_extract_div(ls, pos);414}415 416/* Return the space of "ls".417 */418__isl_keep isl_space *isl_local_space_peek_space(__isl_keep isl_local_space *ls)419{420 if (!ls)421 return NULL;422 423 return ls->dim;424}425 426__isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)427{428 return isl_space_copy(isl_local_space_peek_space(ls));429}430 431/* Return the space of "ls".432 * This may be either a copy or the space itself433 * if there is only one reference to "ls".434 * This allows the space to be modified inplace435 * if both the local space and its space have only a single reference.436 * The caller is not allowed to modify "ls" between this call and437 * a subsequent call to isl_local_space_restore_space.438 * The only exception is that isl_local_space_free can be called instead.439 */440__isl_give isl_space *isl_local_space_take_space(__isl_keep isl_local_space *ls)441{442 isl_space *space;443 444 if (!ls)445 return NULL;446 if (ls->ref != 1)447 return isl_local_space_get_space(ls);448 space = ls->dim;449 ls->dim = NULL;450 return space;451}452 453/* Set the space of "ls" to "space", where the space of "ls" may be missing454 * due to a preceding call to isl_local_space_take_space.455 * However, in this case, "ls" only has a single reference and456 * then the call to isl_local_space_cow has no effect.457 */458__isl_give isl_local_space *isl_local_space_restore_space(459 __isl_take isl_local_space *ls, __isl_take isl_space *space)460{461 if (!ls || !space)462 goto error;463 464 if (ls->dim == space) {465 isl_space_free(space);466 return ls;467 }468 469 ls = isl_local_space_cow(ls);470 if (!ls)471 goto error;472 isl_space_free(ls->dim);473 ls->dim = space;474 475 return ls;476error:477 isl_local_space_free(ls);478 isl_space_free(space);479 return NULL;480}481 482/* Return the local variables of "ls".483 */484__isl_keep isl_local *isl_local_space_peek_local(__isl_keep isl_local_space *ls)485{486 return ls ? ls->div : NULL;487}488 489/* Return a copy of the local variables of "ls".490 */491__isl_keep isl_local *isl_local_space_get_local(__isl_keep isl_local_space *ls)492{493 return isl_local_copy(isl_local_space_peek_local(ls));494}495 496/* Return the local variables of "ls".497 * This may be either a copy or the local variables itself498 * if there is only one reference to "ls".499 * This allows the local variables to be modified inplace500 * if both the local space and its local variables have only a single reference.501 * The caller is not allowed to modify "ls" between this call and502 * the subsequent call to isl_local_space_restore_local.503 * The only exception is that isl_local_space_free can be called instead.504 */505static __isl_give isl_local *isl_local_space_take_local(506 __isl_keep isl_local_space *ls)507{508 isl_local *local;509 510 if (!ls)511 return NULL;512 if (ls->ref != 1)513 return isl_local_space_get_local(ls);514 local = ls->div;515 ls->div = NULL;516 return local;517}518 519/* Set the local variables of "ls" to "local",520 * where the local variables of "ls" may be missing521 * due to a preceding call to isl_local_space_take_local.522 * However, in this case, "ls" only has a single reference and523 * then the call to isl_local_space_cow has no effect.524 */525static __isl_give isl_local_space *isl_local_space_restore_local(526 __isl_take isl_local_space *ls, __isl_take isl_local *local)527{528 if (!ls || !local)529 goto error;530 531 if (ls->div == local) {532 isl_local_free(local);533 return ls;534 }535 536 ls = isl_local_space_cow(ls);537 if (!ls)538 goto error;539 isl_local_free(ls->div);540 ls->div = local;541 542 return ls;543error:544 isl_local_space_free(ls);545 isl_local_free(local);546 return NULL;547}548 549/* Replace the identifier of the tuple of type "type" by "id".550 */551__isl_give isl_local_space *isl_local_space_set_tuple_id(552 __isl_take isl_local_space *ls,553 enum isl_dim_type type, __isl_take isl_id *id)554{555 ls = isl_local_space_cow(ls);556 if (!ls)557 goto error;558 ls->dim = isl_space_set_tuple_id(ls->dim, type, id);559 if (!ls->dim)560 return isl_local_space_free(ls);561 return ls;562error:563 isl_id_free(id);564 return NULL;565}566 567__isl_give isl_local_space *isl_local_space_set_dim_name(568 __isl_take isl_local_space *ls,569 enum isl_dim_type type, unsigned pos, const char *s)570{571 ls = isl_local_space_cow(ls);572 if (!ls)573 return NULL;574 ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);575 if (!ls->dim)576 return isl_local_space_free(ls);577 578 return ls;579}580 581__isl_give isl_local_space *isl_local_space_set_dim_id(582 __isl_take isl_local_space *ls,583 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)584{585 ls = isl_local_space_cow(ls);586 if (!ls)587 goto error;588 ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);589 if (!ls->dim)590 return isl_local_space_free(ls);591 592 return ls;593error:594 isl_id_free(id);595 return NULL;596}597 598/* Construct a zero-dimensional local space with the given parameter domain.599 */600__isl_give isl_local_space *isl_local_space_set_from_params(601 __isl_take isl_local_space *ls)602{603 isl_space *space;604 605 space = isl_local_space_take_space(ls);606 space = isl_space_set_from_params(space);607 ls = isl_local_space_restore_space(ls, space);608 609 return ls;610}611 612__isl_give isl_local_space *isl_local_space_reset_space(613 __isl_take isl_local_space *ls, __isl_take isl_space *space)614{615 ls = isl_local_space_cow(ls);616 if (!ls || !space)617 goto error;618 619 isl_space_free(ls->dim);620 ls->dim = space;621 622 return ls;623error:624 isl_local_space_free(ls);625 isl_space_free(space);626 return NULL;627}628 629/* Reorder the dimensions of "ls" according to the given reordering.630 * The reordering r is assumed to have been extended with the local631 * variables, leaving them in the same order.632 */633__isl_give isl_local_space *isl_local_space_realign(634 __isl_take isl_local_space *ls, __isl_take isl_reordering *r)635{636 isl_local *local;637 638 local = isl_local_space_take_local(ls);639 local = isl_local_reorder(local, isl_reordering_copy(r));640 ls = isl_local_space_restore_local(ls, local);641 642 ls = isl_local_space_reset_space(ls, isl_reordering_get_space(r));643 644 isl_reordering_free(r);645 return ls;646}647 648__isl_give isl_local_space *isl_local_space_add_div(649 __isl_take isl_local_space *ls, __isl_take isl_vec *div)650{651 ls = isl_local_space_cow(ls);652 if (!ls || !div)653 goto error;654 655 if (ls->div->n_col != div->size)656 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,657 "incompatible dimensions", goto error);658 659 ls->div = isl_mat_add_zero_cols(ls->div, 1);660 ls->div = isl_mat_add_rows(ls->div, 1);661 if (!ls->div)662 goto error;663 664 isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);665 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);666 667 isl_vec_free(div);668 return ls;669error:670 isl_local_space_free(ls);671 isl_vec_free(div);672 return NULL;673}674 675__isl_give isl_local_space *isl_local_space_replace_divs(676 __isl_take isl_local_space *ls, __isl_take isl_mat *div)677{678 ls = isl_local_space_cow(ls);679 680 if (!ls || !div)681 goto error;682 683 isl_mat_free(ls->div);684 ls->div = div;685 return ls;686error:687 isl_mat_free(div);688 isl_local_space_free(ls);689 return NULL;690}691 692/* Copy row "s" of "src" to row "d" of "dst", applying the expansion693 * defined by "exp".694 */695static void expand_row(__isl_keep isl_mat *dst, int d,696 __isl_keep isl_mat *src, int s, int *exp)697{698 int i;699 unsigned c = src->n_col - src->n_row;700 701 isl_seq_cpy(dst->row[d], src->row[s], c);702 isl_seq_clr(dst->row[d] + c, dst->n_col - c);703 704 for (i = 0; i < s; ++i)705 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);706}707 708/* Compare (known) divs.709 * Return non-zero if at least one of the two divs is unknown.710 * In particular, if both divs are unknown, we respect their711 * current order. Otherwise, we sort the known div after the unknown712 * div only if the known div depends on the unknown div.713 */714static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,715 unsigned n_row, unsigned n_col)716{717 int li, lj;718 int unknown_i, unknown_j;719 720 unknown_i = isl_int_is_zero(row_i[0]);721 unknown_j = isl_int_is_zero(row_j[0]);722 723 if (unknown_i && unknown_j)724 return i - j;725 726 if (unknown_i)727 li = n_col - n_row + i;728 else729 li = isl_seq_last_non_zero(row_i, n_col);730 if (unknown_j)731 lj = n_col - n_row + j;732 else733 lj = isl_seq_last_non_zero(row_j, n_col);734 735 if (li != lj)736 return li - lj;737 738 return isl_seq_cmp(row_i, row_j, n_col);739}740 741/* Call cmp_row for divs in a matrix.742 */743int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)744{745 return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);746}747 748/* Call cmp_row for divs in a basic map.749 */750static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,751 unsigned total)752{753 return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);754}755 756/* Sort the divs in "bmap".757 *758 * We first make sure divs are placed after divs on which they depend.759 * Then we perform a simple insertion sort based on the same ordering760 * that is used in isl_merge_divs.761 */762__isl_give isl_basic_map *isl_basic_map_sort_divs(763 __isl_take isl_basic_map *bmap)764{765 int i, j;766 isl_size total;767 768 bmap = isl_basic_map_order_divs(bmap);769 if (!bmap)770 return NULL;771 if (bmap->n_div <= 1)772 return bmap;773 774 total = isl_basic_map_dim(bmap, isl_dim_all);775 if (total < 0)776 return isl_basic_map_free(bmap);777 for (i = 1; i < bmap->n_div; ++i) {778 for (j = i - 1; j >= 0; --j) {779 if (bmap_cmp_row(bmap, j, j + 1, 2 + total) <= 0)780 break;781 bmap = isl_basic_map_swap_div(bmap, j, j + 1);782 if (!bmap)783 return NULL;784 }785 }786 787 return bmap;788}789 790/* Sort the divs in the basic maps of "map".791 */792__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)793{794 return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);795}796 797/* Combine the two lists of divs into a single list.798 * For each row i in div1, exp1[i] is set to the position of the corresponding799 * row in the result. Similarly for div2 and exp2.800 * This function guarantees801 * exp1[i] >= i802 * exp1[i+1] > exp1[i]803 * For optimal merging, the two input list should have been sorted.804 */805__isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,806 __isl_keep isl_mat *div2, int *exp1, int *exp2)807{808 int i, j, k;809 isl_mat *div = NULL;810 unsigned d;811 812 if (!div1 || !div2)813 return NULL;814 815 d = div1->n_col - div1->n_row;816 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,817 d + div1->n_row + div2->n_row);818 if (!div)819 return NULL;820 821 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {822 int cmp;823 824 expand_row(div, k, div1, i, exp1);825 expand_row(div, k + 1, div2, j, exp2);826 827 cmp = isl_mat_cmp_div(div, k, k + 1);828 if (cmp == 0) {829 exp1[i++] = k;830 exp2[j++] = k;831 } else if (cmp < 0) {832 exp1[i++] = k;833 } else {834 exp2[j++] = k;835 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);836 }837 }838 for (; i < div1->n_row; ++i, ++k) {839 expand_row(div, k, div1, i, exp1);840 exp1[i] = k;841 }842 for (; j < div2->n_row; ++j, ++k) {843 expand_row(div, k, div2, j, exp2);844 exp2[j] = k;845 }846 847 div->n_row = k;848 div->n_col = d + k;849 850 return div;851}852 853/* Swap divs "a" and "b" in "ls".854 */855__isl_give isl_local_space *isl_local_space_swap_div(856 __isl_take isl_local_space *ls, int a, int b)857{858 int offset;859 860 ls = isl_local_space_cow(ls);861 if (!ls)862 return NULL;863 if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)864 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,865 "index out of bounds", return isl_local_space_free(ls));866 offset = ls->div->n_col - ls->div->n_row;867 ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);868 ls->div = isl_mat_swap_rows(ls->div, a, b);869 if (!ls->div)870 return isl_local_space_free(ls);871 return ls;872}873 874/* Construct a local space that contains all the divs in either875 * "ls1" or "ls2".876 */877__isl_give isl_local_space *isl_local_space_intersect(878 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)879{880 isl_ctx *ctx;881 int *exp1 = NULL;882 int *exp2 = NULL;883 isl_mat *div = NULL;884 isl_bool equal;885 886 if (!ls1 || !ls2)887 goto error;888 889 ctx = isl_local_space_get_ctx(ls1);890 if (!isl_space_is_equal(ls1->dim, ls2->dim))891 isl_die(ctx, isl_error_invalid,892 "spaces should be identical", goto error);893 894 if (ls2->div->n_row == 0) {895 isl_local_space_free(ls2);896 return ls1;897 }898 899 if (ls1->div->n_row == 0) {900 isl_local_space_free(ls1);901 return ls2;902 }903 904 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);905 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);906 if (!exp1 || !exp2)907 goto error;908 909 div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);910 if (!div)911 goto error;912 913 equal = isl_mat_is_equal(ls1->div, div);914 if (equal < 0)915 goto error;916 if (!equal)917 ls1 = isl_local_space_cow(ls1);918 if (!ls1)919 goto error;920 921 free(exp1);922 free(exp2);923 isl_local_space_free(ls2);924 isl_mat_free(ls1->div);925 ls1->div = div;926 927 return ls1;928error:929 free(exp1);930 free(exp2);931 isl_mat_free(div);932 isl_local_space_free(ls1);933 isl_local_space_free(ls2);934 return NULL;935}936 937/* Is the local variable "div" of "ls" marked as not having938 * an explicit representation?939 * Note that even if this variable is not marked in this way and therefore940 * does have an explicit representation, this representation may still941 * depend (indirectly) on other local variables that do not942 * have an explicit representation.943 */944isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,945 int div)946{947 if (!ls)948 return isl_bool_error;949 return isl_local_div_is_marked_unknown(ls->div, div);950}951 952/* Does "ls" have a complete explicit representation for div "div"?953 */954isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)955{956 if (!ls)957 return isl_bool_error;958 return isl_local_div_is_known(ls->div, div);959}960 961/* Does "ls" have an explicit representation for all local variables?962 */963isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)964{965 if (!ls)966 return isl_bool_error;967 return isl_local_divs_known(ls->div);968}969 970__isl_give isl_local_space *isl_local_space_domain(971 __isl_take isl_local_space *ls)972{973 isl_size n_out;974 975 n_out = isl_local_space_dim(ls, isl_dim_out);976 if (n_out < 0)977 return isl_local_space_free(ls);978 ls = isl_local_space_drop_dims(ls, isl_dim_out, 0, n_out);979 ls = isl_local_space_cow(ls);980 if (!ls)981 return NULL;982 ls->dim = isl_space_domain(ls->dim);983 if (!ls->dim)984 return isl_local_space_free(ls);985 return ls;986}987 988__isl_give isl_local_space *isl_local_space_range(989 __isl_take isl_local_space *ls)990{991 isl_size n_in;992 993 n_in = isl_local_space_dim(ls, isl_dim_in);994 if (n_in < 0)995 return isl_local_space_free(ls);996 ls = isl_local_space_drop_dims(ls, isl_dim_in, 0, n_in);997 ls = isl_local_space_cow(ls);998 if (!ls)999 return NULL;1000 1001 ls->dim = isl_space_range(ls->dim);1002 if (!ls->dim)1003 return isl_local_space_free(ls);1004 return ls;1005}1006 1007/* Construct a local space for a map that has the given local1008 * space as domain and that has a zero-dimensional range.1009 */1010__isl_give isl_local_space *isl_local_space_from_domain(1011 __isl_take isl_local_space *ls)1012{1013 ls = isl_local_space_cow(ls);1014 if (!ls)1015 return NULL;1016 ls->dim = isl_space_from_domain(ls->dim);1017 if (!ls->dim)1018 return isl_local_space_free(ls);1019 return ls;1020}1021 1022__isl_give isl_local_space *isl_local_space_add_dims(1023 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)1024{1025 isl_size pos;1026 1027 pos = isl_local_space_dim(ls, type);1028 if (pos < 0)1029 return isl_local_space_free(ls);1030 return isl_local_space_insert_dims(ls, type, pos, n);1031}1032 1033/* Lift the basic set "bset", living in the space of "ls"1034 * to live in a space with extra coordinates corresponding1035 * to the local variables of "ls".1036 */1037__isl_give isl_basic_set *isl_local_space_lift_basic_set(1038 __isl_take isl_local_space *ls, __isl_take isl_basic_set *bset)1039{1040 isl_size n_local;1041 isl_space *space;1042 isl_basic_set *ls_bset;1043 1044 n_local = isl_local_space_dim(ls, isl_dim_div);1045 space = isl_basic_set_peek_space(bset);1046 if (n_local < 0 ||1047 isl_local_space_check_has_space(ls, space) < 0)1048 goto error;1049 1050 if (n_local == 0) {1051 isl_local_space_free(ls);1052 return bset;1053 }1054 1055 bset = isl_basic_set_add_dims(bset, isl_dim_set, n_local);1056 ls_bset = isl_basic_set_from_local_space(ls);1057 ls_bset = isl_basic_set_lift(ls_bset);1058 ls_bset = isl_basic_set_flatten(ls_bset);1059 bset = isl_basic_set_intersect(bset, ls_bset);1060 1061 return bset;1062error:1063 isl_local_space_free(ls);1064 isl_basic_set_free(bset);1065 return NULL;1066}1067 1068/* Lift the set "set", living in the space of "ls"1069 * to live in a space with extra coordinates corresponding1070 * to the local variables of "ls".1071 */1072__isl_give isl_set *isl_local_space_lift_set(__isl_take isl_local_space *ls,1073 __isl_take isl_set *set)1074{1075 isl_size n_local;1076 isl_basic_set *bset;1077 1078 n_local = isl_local_space_dim(ls, isl_dim_div);1079 if (n_local < 0 ||1080 isl_local_space_check_has_space(ls, isl_set_peek_space(set)) < 0)1081 goto error;1082 1083 if (n_local == 0) {1084 isl_local_space_free(ls);1085 return set;1086 }1087 1088 set = isl_set_add_dims(set, isl_dim_set, n_local);1089 bset = isl_basic_set_from_local_space(ls);1090 bset = isl_basic_set_lift(bset);1091 bset = isl_basic_set_flatten(bset);1092 set = isl_set_intersect(set, isl_set_from_basic_set(bset));1093 1094 return set;1095error:1096 isl_local_space_free(ls);1097 isl_set_free(set);1098 return NULL;1099}1100 1101/* Remove common factor of non-constant terms and denominator.1102 */1103static __isl_give isl_local_space *normalize_div(1104 __isl_take isl_local_space *ls, int div)1105{1106 isl_ctx *ctx = ls->div->ctx;1107 unsigned total = ls->div->n_col - 2;1108 1109 isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);1110 isl_int_gcd(ctx->normalize_gcd,1111 ctx->normalize_gcd, ls->div->row[div][0]);1112 if (isl_int_is_one(ctx->normalize_gcd))1113 return ls;1114 1115 isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,1116 ctx->normalize_gcd, total);1117 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],1118 ctx->normalize_gcd);1119 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],1120 ctx->normalize_gcd);1121 1122 return ls;1123}1124 1125/* Exploit the equalities in "eq" to simplify the expressions of1126 * the integer divisions in "ls".1127 * The integer divisions in "ls" are assumed to appear as regular1128 * dimensions in "eq".1129 */1130__isl_give isl_local_space *isl_local_space_substitute_equalities(1131 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)1132{1133 int i, j, k;1134 isl_size total, dim;1135 unsigned n_div;1136 1137 if (!ls || !eq)1138 goto error;1139 1140 total = isl_space_dim(eq->dim, isl_dim_all);1141 dim = isl_local_space_dim(ls, isl_dim_all);1142 if (dim < 0 || total < 0)1143 goto error;1144 if (dim != total)1145 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1146 "spaces don't match", goto error);1147 total++;1148 n_div = eq->n_div;1149 for (i = 0; i < eq->n_eq; ++i) {1150 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);1151 if (j < 0 || j == 0 || j >= total)1152 continue;1153 1154 for (k = 0; k < ls->div->n_row; ++k) {1155 if (isl_int_is_zero(ls->div->row[k][1 + j]))1156 continue;1157 ls = isl_local_space_cow(ls);1158 if (!ls)1159 goto error;1160 ls->div = isl_mat_cow(ls->div);1161 if (!ls->div)1162 goto error;1163 isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,1164 &ls->div->row[k][0]);1165 ls = normalize_div(ls, k);1166 if (!ls)1167 goto error;1168 }1169 }1170 1171 isl_basic_set_free(eq);1172 return ls;1173error:1174 isl_basic_set_free(eq);1175 isl_local_space_free(ls);1176 return NULL;1177}1178 1179/* Plug in the affine expressions "subs" of length "subs_len" (including1180 * the denominator and the constant term) into the variable at position "pos"1181 * of the "n" div expressions starting at "first".1182 *1183 * Let i be the dimension to replace and let "subs" be of the form1184 *1185 * f/d1186 *1187 * Any integer division starting at "first" with a non-zero coefficient for i,1188 *1189 * floor((a i + g)/m)1190 *1191 * is replaced by1192 *1193 * floor((a f + d g)/(m d))1194 */1195__isl_give isl_local_space *isl_local_space_substitute_seq(1196 __isl_take isl_local_space *ls,1197 enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,1198 int first, int n)1199{1200 int i;1201 isl_int v;1202 1203 if (n == 0)1204 return ls;1205 ls = isl_local_space_cow(ls);1206 if (!ls)1207 return NULL;1208 ls->div = isl_mat_cow(ls->div);1209 if (!ls->div)1210 return isl_local_space_free(ls);1211 1212 if (first + n > ls->div->n_row)1213 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1214 "index out of bounds", return isl_local_space_free(ls));1215 1216 pos += isl_local_space_offset(ls, type);1217 1218 isl_int_init(v);1219 for (i = first; i < first + n; ++i) {1220 if (isl_int_is_zero(ls->div->row[i][1 + pos]))1221 continue;1222 isl_seq_substitute(ls->div->row[i], pos, subs,1223 ls->div->n_col, subs_len, v);1224 ls = normalize_div(ls, i);1225 if (!ls)1226 break;1227 }1228 isl_int_clear(v);1229 1230 return ls;1231}1232 1233/* Plug in "subs" for dimension "type", "pos" in the integer divisions1234 * of "ls".1235 *1236 * Let i be the dimension to replace and let "subs" be of the form1237 *1238 * f/d1239 *1240 * Any integer division with a non-zero coefficient for i,1241 *1242 * floor((a i + g)/m)1243 *1244 * is replaced by1245 *1246 * floor((a f + d g)/(m d))1247 */1248__isl_give isl_local_space *isl_local_space_substitute(1249 __isl_take isl_local_space *ls,1250 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)1251{1252 isl_size n_div;1253 1254 ls = isl_local_space_cow(ls);1255 if (!ls || !subs)1256 return isl_local_space_free(ls);1257 1258 if (!isl_space_is_equal(ls->dim, subs->ls->dim))1259 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1260 "spaces don't match", return isl_local_space_free(ls));1261 n_div = isl_local_space_dim(subs->ls, isl_dim_div);1262 if (n_div < 0)1263 return isl_local_space_free(ls);1264 if (n_div != 0)1265 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,1266 "cannot handle divs yet",1267 return isl_local_space_free(ls));1268 1269 return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,1270 subs->v->size, 0, ls->div->n_row);1271}1272 1273isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,1274 enum isl_dim_type type)1275{1276 if (!ls)1277 return isl_bool_error;1278 return isl_space_is_named_or_nested(ls->dim, type);1279}1280 1281__isl_give isl_local_space *isl_local_space_drop_dims(1282 __isl_take isl_local_space *ls,1283 enum isl_dim_type type, unsigned first, unsigned n)1284{1285 if (!ls)1286 return NULL;1287 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))1288 return ls;1289 1290 if (isl_local_space_check_range(ls, type, first, n) < 0)1291 return isl_local_space_free(ls);1292 1293 ls = isl_local_space_cow(ls);1294 if (!ls)1295 return NULL;1296 1297 if (type == isl_dim_div) {1298 ls->div = isl_mat_drop_rows(ls->div, first, n);1299 } else {1300 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);1301 if (!ls->dim)1302 return isl_local_space_free(ls);1303 }1304 1305 first += 1 + isl_local_space_offset(ls, type);1306 ls->div = isl_mat_drop_cols(ls->div, first, n);1307 if (!ls->div)1308 return isl_local_space_free(ls);1309 1310 return ls;1311}1312 1313__isl_give isl_local_space *isl_local_space_insert_dims(1314 __isl_take isl_local_space *ls,1315 enum isl_dim_type type, unsigned first, unsigned n)1316{1317 if (!ls)1318 return NULL;1319 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))1320 return ls;1321 1322 if (isl_local_space_check_range(ls, type, first, 0) < 0)1323 return isl_local_space_free(ls);1324 1325 ls = isl_local_space_cow(ls);1326 if (!ls)1327 return NULL;1328 1329 if (type == isl_dim_div) {1330 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);1331 } else {1332 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);1333 if (!ls->dim)1334 return isl_local_space_free(ls);1335 }1336 1337 first += 1 + isl_local_space_offset(ls, type);1338 ls->div = isl_mat_insert_zero_cols(ls->div, first, n);1339 if (!ls->div)1340 return isl_local_space_free(ls);1341 1342 return ls;1343}1344 1345/* Does the linear part of "constraint" correspond to1346 * integer division "div" in "ls"?1347 *1348 * That is, given div = floor((c + f)/m), is the constraint of the form1349 *1350 * f - m d + c' >= 0 [sign = 1]1351 * or1352 * -f + m d + c'' >= 0 [sign = -1]1353 * ?1354 * If so, set *sign to the corresponding value.1355 */1356static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls,1357 isl_int *constraint, unsigned div, int *sign)1358{1359 isl_bool unknown;1360 unsigned pos;1361 1362 unknown = isl_local_space_div_is_marked_unknown(ls, div);1363 if (unknown < 0)1364 return isl_bool_error;1365 if (unknown)1366 return isl_bool_false;1367 1368 pos = isl_local_space_offset(ls, isl_dim_div) + div;1369 1370 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {1371 *sign = -1;1372 if (!isl_seq_is_neg(constraint + 1,1373 ls->div->row[div] + 2, pos - 1))1374 return isl_bool_false;1375 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {1376 *sign = 1;1377 if (!isl_seq_eq(constraint + 1, ls->div->row[div] + 2, pos - 1))1378 return isl_bool_false;1379 } else {1380 return isl_bool_false;1381 }1382 if (isl_seq_first_non_zero(constraint + pos + 1,1383 ls->div->n_row - div - 1) != -1)1384 return isl_bool_false;1385 return isl_bool_true;1386}1387 1388/* Check if the constraints pointed to by "constraint" is a div1389 * constraint corresponding to div "div" in "ls".1390 *1391 * That is, if div = floor(f/m), then check if the constraint is1392 *1393 * f - m d >= 01394 * or1395 * -(f-(m-1)) + m d >= 01396 *1397 * First check if the linear part is of the right form and1398 * then check the constant term.1399 */1400isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,1401 isl_int *constraint, unsigned div)1402{1403 int sign;1404 isl_bool linear;1405 1406 linear = is_linear_div_constraint(ls, constraint, div, &sign);1407 if (linear < 0 || !linear)1408 return linear;1409 1410 if (sign < 0) {1411 int neg;1412 isl_int_sub(ls->div->row[div][1],1413 ls->div->row[div][1], ls->div->row[div][0]);1414 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);1415 neg = isl_seq_is_neg(constraint, ls->div->row[div] + 1, 1);1416 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);1417 isl_int_add(ls->div->row[div][1],1418 ls->div->row[div][1], ls->div->row[div][0]);1419 if (!neg)1420 return isl_bool_false;1421 } else {1422 if (!isl_int_eq(constraint[0], ls->div->row[div][1]))1423 return isl_bool_false;1424 }1425 1426 return isl_bool_true;1427}1428 1429/* Is the constraint pointed to by "constraint" one1430 * of an equality that corresponds to integer division "div" in "ls"?1431 *1432 * That is, given an integer division of the form1433 *1434 * a = floor((f + c)/m)1435 *1436 * is the equality of the form1437 *1438 * -f + m d + c' = 01439 * ?1440 * Note that the constant term is not checked explicitly, but given1441 * that this is a valid equality constraint, the constant c' necessarily1442 * has a value close to -c.1443 */1444isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls,1445 isl_int *constraint, unsigned div)1446{1447 int sign;1448 isl_bool linear;1449 1450 linear = is_linear_div_constraint(ls, constraint, div, &sign);1451 if (linear < 0 || !linear)1452 return linear;1453 1454 return isl_bool_ok(sign < 0);1455}1456 1457/*1458 * Set active[i] to 1 if the dimension at position i is involved1459 * in the linear expression l.1460 */1461int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)1462{1463 int i, j;1464 isl_ctx *ctx;1465 int *active = NULL;1466 isl_size total;1467 unsigned offset;1468 1469 ctx = isl_local_space_get_ctx(ls);1470 total = isl_local_space_dim(ls, isl_dim_all);1471 if (total < 0)1472 return NULL;1473 active = isl_calloc_array(ctx, int, total);1474 if (total && !active)1475 return NULL;1476 1477 for (i = 0; i < total; ++i)1478 active[i] = !isl_int_is_zero(l[i]);1479 1480 offset = isl_local_space_offset(ls, isl_dim_div) - 1;1481 for (i = ls->div->n_row - 1; i >= 0; --i) {1482 if (!active[offset + i])1483 continue;1484 for (j = 0; j < total; ++j)1485 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);1486 }1487 1488 return active;1489}1490 1491/* Given a local space "ls" of a set, create a local space1492 * for the lift of the set. In particular, the result1493 * is of the form [dim -> local[..]], with ls->div->n_row variables in the1494 * range of the wrapped map.1495 */1496__isl_give isl_local_space *isl_local_space_lift(1497 __isl_take isl_local_space *ls)1498{1499 ls = isl_local_space_cow(ls);1500 if (!ls)1501 return NULL;1502 1503 ls->dim = isl_space_lift(ls->dim, ls->div->n_row);1504 ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);1505 if (!ls->dim || !ls->div)1506 return isl_local_space_free(ls);1507 1508 return ls;1509}1510 1511/* Construct a basic map that maps a set living in local space "ls"1512 * to the corresponding lifted local space.1513 */1514__isl_give isl_basic_map *isl_local_space_lifting(1515 __isl_take isl_local_space *ls)1516{1517 isl_basic_map *lifting;1518 isl_basic_set *bset;1519 1520 if (!ls)1521 return NULL;1522 if (!isl_local_space_is_set(ls))1523 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1524 "lifting only defined on set spaces", goto error);1525 1526 bset = isl_basic_set_from_local_space(ls);1527 lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));1528 lifting = isl_basic_map_domain_map(lifting);1529 lifting = isl_basic_map_reverse(lifting);1530 1531 return lifting;1532error:1533 isl_local_space_free(ls);1534 return NULL;1535}1536 1537/* Compute the preimage of "ls" under the function represented by "ma".1538 * In other words, plug in "ma" in "ls". The result is a local space1539 * that is part of the domain space of "ma".1540 *1541 * If the divs in "ls" are represented as1542 *1543 * floor((a_i(p) + b_i x + c_i(divs))/n_i)1544 *1545 * and ma is represented by1546 *1547 * x = D(p) + F(y) + G(divs')1548 *1549 * then the resulting divs are1550 *1551 * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)1552 *1553 * We first copy over the divs from "ma" and then1554 * we add the modified divs from "ls".1555 */1556__isl_give isl_local_space *isl_local_space_preimage_multi_aff(1557 __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)1558{1559 int i;1560 isl_space *space;1561 isl_local_space *res = NULL;1562 isl_size n_div_ls, n_div_ma;1563 isl_int f, c1, c2, g;1564 1565 ma = isl_multi_aff_align_divs(ma);1566 if (!ls || !ma)1567 goto error;1568 if (!isl_space_is_range_internal(ls->dim, ma->space))1569 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1570 "spaces don't match", goto error);1571 1572 n_div_ls = isl_local_space_dim(ls, isl_dim_div);1573 n_div_ma = ma->n ? isl_aff_dim(ma->u.p[0], isl_dim_div) : 0;1574 if (n_div_ls < 0 || n_div_ma < 0)1575 goto error;1576 1577 space = isl_space_domain(isl_multi_aff_get_space(ma));1578 res = isl_local_space_alloc(space, n_div_ma + n_div_ls);1579 if (!res)1580 goto error;1581 1582 if (n_div_ma) {1583 isl_mat_free(res->div);1584 res->div = isl_mat_copy(ma->u.p[0]->ls->div);1585 res->div = isl_mat_add_zero_cols(res->div, n_div_ls);1586 res->div = isl_mat_add_rows(res->div, n_div_ls);1587 if (!res->div)1588 goto error;1589 }1590 1591 isl_int_init(f);1592 isl_int_init(c1);1593 isl_int_init(c2);1594 isl_int_init(g);1595 1596 for (i = 0; i < ls->div->n_row; ++i) {1597 if (isl_int_is_zero(ls->div->row[i][0])) {1598 isl_int_set_si(res->div->row[n_div_ma + i][0], 0);1599 continue;1600 }1601 if (isl_seq_preimage(res->div->row[n_div_ma + i],1602 ls->div->row[i],1603 ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1) < 0)1604 res = isl_local_space_free(res);1605 res = normalize_div(res, n_div_ma + i);1606 if (!res)1607 break;1608 }1609 1610 isl_int_clear(f);1611 isl_int_clear(c1);1612 isl_int_clear(c2);1613 isl_int_clear(g);1614 1615 isl_local_space_free(ls);1616 isl_multi_aff_free(ma);1617 return res;1618error:1619 isl_local_space_free(ls);1620 isl_multi_aff_free(ma);1621 isl_local_space_free(res);1622 return NULL;1623}1624 1625/* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"1626 * to dimensions of "dst_type" at "dst_pos".1627 *1628 * Moving to/from local dimensions is not allowed.1629 * We currently assume that the dimension type changes.1630 */1631__isl_give isl_local_space *isl_local_space_move_dims(1632 __isl_take isl_local_space *ls,1633 enum isl_dim_type dst_type, unsigned dst_pos,1634 enum isl_dim_type src_type, unsigned src_pos, unsigned n)1635{1636 isl_space *space;1637 isl_local *local;1638 isl_size v_src, v_dst;1639 unsigned g_dst_pos;1640 unsigned g_src_pos;1641 1642 if (!ls)1643 return NULL;1644 if (n == 0 &&1645 !isl_local_space_is_named_or_nested(ls, src_type) &&1646 !isl_local_space_is_named_or_nested(ls, dst_type))1647 return ls;1648 1649 if (isl_local_space_check_range(ls, src_type, src_pos, n) < 0)1650 return isl_local_space_free(ls);1651 if (isl_local_space_check_range(ls, dst_type, dst_pos, 0) < 0)1652 return isl_local_space_free(ls);1653 if (src_type == isl_dim_div)1654 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1655 "cannot move divs", return isl_local_space_free(ls));1656 if (dst_type == isl_dim_div)1657 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,1658 "cannot move to divs", return isl_local_space_free(ls));1659 if (dst_type == src_type && dst_pos == src_pos)1660 return ls;1661 if (dst_type == src_type)1662 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,1663 "moving dims within the same type not supported",1664 return isl_local_space_free(ls));1665 1666 v_src = isl_local_space_var_offset(ls, src_type);1667 v_dst = isl_local_space_var_offset(ls, dst_type);1668 if (v_src < 0 || v_dst < 0)1669 return isl_local_space_free(ls);1670 g_src_pos = v_src + src_pos;1671 g_dst_pos = v_dst + dst_pos;1672 if (dst_type > src_type)1673 g_dst_pos -= n;1674 1675 local = isl_local_space_take_local(ls);1676 local = isl_local_move_vars(local, g_dst_pos, g_src_pos, n);1677 ls = isl_local_space_restore_local(ls, local);1678 1679 space = isl_local_space_take_space(ls);1680 space = isl_space_move_dims(space, dst_type, dst_pos,1681 src_type, src_pos, n);1682 ls = isl_local_space_restore_space(ls, space);1683 1684 return ls;1685}1686 1687/* Remove any internal structure of the domain of "ls".1688 * If there is any such internal structure in the input,1689 * then the name of the corresponding space is also removed.1690 */1691__isl_give isl_local_space *isl_local_space_flatten_domain(1692 __isl_take isl_local_space *ls)1693{1694 if (!ls)1695 return NULL;1696 1697 if (!ls->dim->nested[0])1698 return ls;1699 1700 ls = isl_local_space_cow(ls);1701 if (!ls)1702 return NULL;1703 1704 ls->dim = isl_space_flatten_domain(ls->dim);1705 if (!ls->dim)1706 return isl_local_space_free(ls);1707 1708 return ls;1709}1710 1711/* Remove any internal structure of the range of "ls".1712 * If there is any such internal structure in the input,1713 * then the name of the corresponding space is also removed.1714 */1715__isl_give isl_local_space *isl_local_space_flatten_range(1716 __isl_take isl_local_space *ls)1717{1718 if (!ls)1719 return NULL;1720 1721 if (!ls->dim->nested[1])1722 return ls;1723 1724 ls = isl_local_space_cow(ls);1725 if (!ls)1726 return NULL;1727 1728 ls->dim = isl_space_flatten_range(ls->dim);1729 if (!ls->dim)1730 return isl_local_space_free(ls);1731 1732 return ls;1733}1734 1735/* Given the local space "ls" of a map, return the local space of a set1736 * that lives in a space that wraps the space of "ls" and that has1737 * the same divs.1738 */1739__isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)1740{1741 ls = isl_local_space_cow(ls);1742 if (!ls)1743 return NULL;1744 1745 ls->dim = isl_space_wrap(ls->dim);1746 if (!ls->dim)1747 return isl_local_space_free(ls);1748 1749 return ls;1750}1751 1752/* Lift the point "pnt", living in the (set) space of "ls"1753 * to live in a space with extra coordinates corresponding1754 * to the local variables of "ls".1755 */1756__isl_give isl_point *isl_local_space_lift_point(__isl_take isl_local_space *ls,1757 __isl_take isl_point *pnt)1758{1759 isl_size n_local;1760 isl_space *space;1761 isl_local *local;1762 isl_vec *vec;1763 1764 if (isl_local_space_check_has_space(ls, isl_point_peek_space(pnt)) < 0)1765 goto error;1766 1767 local = isl_local_space_peek_local(ls);1768 n_local = isl_local_space_dim(ls, isl_dim_div);1769 if (n_local < 0)1770 goto error;1771 1772 space = isl_point_take_space(pnt);1773 vec = isl_point_take_vec(pnt);1774 1775 space = isl_space_lift(space, n_local);1776 vec = isl_local_extend_point_vec(local, vec);1777 1778 pnt = isl_point_restore_vec(pnt, vec);1779 pnt = isl_point_restore_space(pnt, space);1780 1781 isl_local_space_free(ls);1782 1783 return pnt;1784error:1785 isl_local_space_free(ls);1786 isl_point_free(pnt);1787 return NULL;1788}1789