isl_local_space.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2012-2014 Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   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, France
  10  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  11  */
  12
  13 #include <isl_ctx_private.h>
  14 #include <isl_map_private.h>
  15 #include <isl_local_space_private.h>
  16 #include <isl_space_private.h>
  17 #include <isl_mat_private.h>
  18 #include <isl_aff_private.h>
  19 #include <isl_vec_private.h>
  20 #include <isl_seq.h>
  21 #include <isl_local.h>
  22
  23 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
  24 {
  25         return ls ? ls->dim->ctx : NULL;
  26 }
  27
  28 /* Return a hash value that digests "ls".
  29  */
  30 uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls)
  31 {
  32         uint32_t hash, space_hash, div_hash;
  33
  34         if (!ls)
  35                 return 0;
  36
  37         hash = isl_hash_init();
  38         space_hash = isl_space_get_hash(ls->dim);
  39         isl_hash_hash(hash, space_hash);
  40         div_hash = isl_mat_get_hash(ls->div);
  41         isl_hash_hash(hash, div_hash);
  42
  43         return hash;
  44 }
  45
  46 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
  47         __isl_take isl_mat *div)
  48 {
  49         isl_ctx *ctx;
  50         isl_local_space *ls = NULL;
  51
  52         if (!dim || !div)
  53                 goto error;
  54
  55         ctx = isl_space_get_ctx(dim);
  56         ls = isl_calloc_type(ctx, struct isl_local_space);
  57         if (!ls)
  58                 goto error;
  59
  60         ls->ref = 1;
  61         ls->dim = dim;
  62         ls->div = div;
  63
  64         return ls;
  65 error:
  66         isl_mat_free(div);
  67         isl_space_free(dim);
  68         isl_local_space_free(ls);
  69         return NULL;
  70 }
  71
  72 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
  73         unsigned n_div)
  74 {
  75         isl_ctx *ctx;
  76         isl_mat *div;
  77         unsigned total;
  78
  79         if (!dim)
  80                 return NULL;
  81
  82         total = isl_space_dim(dim, isl_dim_all);
  83
  84         ctx = isl_space_get_ctx(dim);
  85         div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
  86         return isl_local_space_alloc_div(dim, div);
  87 }
  88
  89 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
  90 {
  91         return isl_local_space_alloc(dim, 0);
  92 }
  93
  94 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
  95 {
  96         if (!ls)
  97                 return NULL;
  98
  99         ls->ref++;
 100         return ls;
 101 }
 102
 103 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
 104 {
 105         if (!ls)
 106                 return NULL;
 107
 108         return isl_local_space_alloc_div(isl_space_copy(ls->dim),
 109                                          isl_mat_copy(ls->div));
 110
 111 }
 112
 113 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
 114 {
 115         if (!ls)
 116                 return NULL;
 117
 118         if (ls->ref == 1)
 119                 return ls;
 120         ls->ref--;
 121         return isl_local_space_dup(ls);
 122 }
 123
 124 __isl_null isl_local_space *isl_local_space_free(
 125         __isl_take isl_local_space *ls)
 126 {
 127         if (!ls)
 128                 return NULL;
 129
 130         if (--ls->ref > 0)
 131                 return NULL;
 132
 133         isl_space_free(ls->dim);
 134         isl_mat_free(ls->div);
 135
 136         free(ls);
 137
 138         return NULL;
 139 }
 140
 141 /* Is the local space that of a parameter domain?
 142  */
 143 isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls)
 144 {
 145         if (!ls)
 146                 return isl_bool_error;
 147         return isl_space_is_params(ls->dim);
 148 }
 149
 150 /* Is the local space that of a set?
 151  */
 152 isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls)
 153 {
 154         return ls ? isl_space_is_set(ls->dim) : isl_bool_error;
 155 }
 156
 157 /* Return true if the two local spaces are identical, with identical
 158  * expressions for the integer divisions.
 159  */
 160 isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
 161         __isl_keep isl_local_space *ls2)
 162 {
 163         isl_bool equal;
 164
 165         if (!ls1 || !ls2)
 166                 return isl_bool_error;
 167
 168         equal = isl_space_is_equal(ls1->dim, ls2->dim);
 169         if (equal < 0 || !equal)
 170                 return equal;
 171
 172         if (!isl_local_space_divs_known(ls1))
 173                 return isl_bool_false;
 174         if (!isl_local_space_divs_known(ls2))
 175                 return isl_bool_false;
 176
 177         return isl_mat_is_equal(ls1->div, ls2->div);
 178 }
 179
 180 /* Compare two isl_local_spaces.
 181  *
 182  * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
 183  * than "ls2" and 0 if they are equal.
 184  */
 185 int isl_local_space_cmp(__isl_keep isl_local_space *ls1,
 186         __isl_keep isl_local_space *ls2)
 187 {
 188         int cmp;
 189
 190         if (ls1 == ls2)
 191                 return 0;
 192         if (!ls1)
 193                 return -1;
 194         if (!ls2)
 195                 return 1;
 196
 197         cmp = isl_space_cmp(ls1->dim, ls2->dim);
 198         if (cmp != 0)
 199                 return cmp;
 200
 201         return isl_local_cmp(ls1->div, ls2->div);
 202 }
 203
 204 int isl_local_space_dim(__isl_keep isl_local_space *ls,
 205         enum isl_dim_type type)
 206 {
 207         if (!ls)
 208                 return 0;
 209         if (type == isl_dim_div)
 210                 return ls->div->n_row;
 211         if (type == isl_dim_all)
 212                 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
 213         return isl_space_dim(ls->dim, type);
 214 }
 215
 216 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
 217         enum isl_dim_type type)
 218 {
 219         isl_space *dim;
 220
 221         if (!ls)
 222                 return 0;
 223
 224         dim = ls->dim;
 225         switch (type) {
 226         case isl_dim_cst:       return 0;
 227         case isl_dim_param:     return 1;
 228         case isl_dim_in:        return 1 + dim->nparam;
 229         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 230         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 231         default:                return 0;
 232         }
 233 }
 234
 235 /* Return the position of the dimension of the given type and name
 236  * in "ls".
 237  * Return -1 if no such dimension can be found.
 238  */
 239 int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls,
 240         enum isl_dim_type type, const char *name)
 241 {
 242         if (!ls)
 243                 return -1;
 244         if (type == isl_dim_div)
 245                 return -1;
 246         return isl_space_find_dim_by_name(ls->dim, type, name);
 247 }
 248
 249 /* Does the given dimension have a name?
 250  */
 251 isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
 252         enum isl_dim_type type, unsigned pos)
 253 {
 254         return ls ? isl_space_has_dim_name(ls->dim, type, pos) : isl_bool_error;
 255 }
 256
 257 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
 258         enum isl_dim_type type, unsigned pos)
 259 {
 260         return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
 261 }
 262
 263 isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
 264         enum isl_dim_type type, unsigned pos)
 265 {
 266         return ls ? isl_space_has_dim_id(ls->dim, type, pos) : isl_bool_error;
 267 }
 268
 269 __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
 270         enum isl_dim_type type, unsigned pos)
 271 {
 272         return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
 273 }
 274
 275 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
 276         int pos)
 277 {
 278         isl_aff *aff;
 279
 280         if (!ls)
 281                 return NULL;
 282
 283         if (pos < 0 || pos >= ls->div->n_row)
 284                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 285                         "index out of bounds", return NULL);
 286
 287         if (isl_int_is_zero(ls->div->row[pos][0]))
 288                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 289                         "expression of div unknown", return NULL);
 290         if (!isl_local_space_is_set(ls))
 291                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 292                         "cannot represent divs of map spaces", return NULL);
 293
 294         aff = isl_aff_alloc(isl_local_space_copy(ls));
 295         if (!aff)
 296                 return NULL;
 297         isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
 298         return aff;
 299 }
 300
 301 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
 302 {
 303         if (!ls)
 304                 return NULL;
 305
 306         return isl_space_copy(ls->dim);
 307 }
 308
 309 /* Replace the identifier of the tuple of type "type" by "id".
 310  */
 311 __isl_give isl_local_space *isl_local_space_set_tuple_id(
 312         __isl_take isl_local_space *ls,
 313         enum isl_dim_type type, __isl_take isl_id *id)
 314 {
 315         ls = isl_local_space_cow(ls);
 316         if (!ls)
 317                 goto error;
 318         ls->dim = isl_space_set_tuple_id(ls->dim, type, id);
 319         if (!ls->dim)
 320                 return isl_local_space_free(ls);
 321         return ls;
 322 error:
 323         isl_id_free(id);
 324         return NULL;
 325 }
 326
 327 __isl_give isl_local_space *isl_local_space_set_dim_name(
 328         __isl_take isl_local_space *ls,
 329         enum isl_dim_type type, unsigned pos, const char *s)
 330 {
 331         ls = isl_local_space_cow(ls);
 332         if (!ls)
 333                 return NULL;
 334         ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
 335         if (!ls->dim)
 336                 return isl_local_space_free(ls);
 337
 338         return ls;
 339 }
 340
 341 __isl_give isl_local_space *isl_local_space_set_dim_id(
 342         __isl_take isl_local_space *ls,
 343         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 344 {
 345         ls = isl_local_space_cow(ls);
 346         if (!ls)
 347                 goto error;
 348         ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
 349         if (!ls->dim)
 350                 return isl_local_space_free(ls);
 351
 352         return ls;
 353 error:
 354         isl_id_free(id);
 355         return NULL;
 356 }
 357
 358 __isl_give isl_local_space *isl_local_space_reset_space(
 359         __isl_take isl_local_space *ls, __isl_take isl_space *dim)
 360 {
 361         ls = isl_local_space_cow(ls);
 362         if (!ls || !dim)
 363                 goto error;
 364
 365         isl_space_free(ls->dim);
 366         ls->dim = dim;
 367
 368         return ls;
 369 error:
 370         isl_local_space_free(ls);
 371         isl_space_free(dim);
 372         return NULL;
 373 }
 374
 375 /* Reorder the columns of the given div definitions according to the
 376  * given reordering.
 377  * The order of the divs themselves is assumed not to change.
 378  */
 379 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
 380         __isl_take isl_reordering *r)
 381 {
 382         int i, j;
 383         isl_mat *mat;
 384         int extra;
 385
 386         if (!div || !r)
 387                 goto error;
 388
 389         extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
 390         mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
 391         if (!mat)
 392                 goto error;
 393
 394         for (i = 0; i < div->n_row; ++i) {
 395                 isl_seq_cpy(mat->row[i], div->row[i], 2);
 396                 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
 397                 for (j = 0; j < r->len; ++j)
 398                         isl_int_set(mat->row[i][2 + r->pos[j]],
 399                                     div->row[i][2 + j]);
 400         }
 401
 402         isl_reordering_free(r);
 403         isl_mat_free(div);
 404         return mat;
 405 error:
 406         isl_reordering_free(r);
 407         isl_mat_free(div);
 408         return NULL;
 409 }
 410
 411 /* Reorder the dimensions of "ls" according to the given reordering.
 412  * The reordering r is assumed to have been extended with the local
 413  * variables, leaving them in the same order.
 414  */
 415 __isl_give isl_local_space *isl_local_space_realign(
 416         __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
 417 {
 418         ls = isl_local_space_cow(ls);
 419         if (!ls || !r)
 420                 goto error;
 421
 422         ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
 423         if (!ls->div)
 424                 goto error;
 425
 426         ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
 427
 428         isl_reordering_free(r);
 429         return ls;
 430 error:
 431         isl_local_space_free(ls);
 432         isl_reordering_free(r);
 433         return NULL;
 434 }
 435
 436 __isl_give isl_local_space *isl_local_space_add_div(
 437         __isl_take isl_local_space *ls, __isl_take isl_vec *div)
 438 {
 439         ls = isl_local_space_cow(ls);
 440         if (!ls || !div)
 441                 goto error;
 442
 443         if (ls->div->n_col != div->size)
 444                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 445                         "incompatible dimensions", goto error);
 446
 447         ls->div = isl_mat_add_zero_cols(ls->div, 1);
 448         ls->div = isl_mat_add_rows(ls->div, 1);
 449         if (!ls->div)
 450                 goto error;
 451
 452         isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
 453         isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
 454
 455         isl_vec_free(div);
 456         return ls;
 457 error:
 458         isl_local_space_free(ls);
 459         isl_vec_free(div);
 460         return NULL;
 461 }
 462
 463 __isl_give isl_local_space *isl_local_space_replace_divs(
 464         __isl_take isl_local_space *ls, __isl_take isl_mat *div)
 465 {
 466         ls = isl_local_space_cow(ls);
 467
 468         if (!ls || !div)
 469                 goto error;
 470
 471         isl_mat_free(ls->div);
 472         ls->div = div;
 473         return ls;
 474 error:
 475         isl_mat_free(div);
 476         isl_local_space_free(ls);
 477         return NULL;
 478 }
 479
 480 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
 481  * defined by "exp".
 482  */
 483 static void expand_row(__isl_keep isl_mat *dst, int d,
 484         __isl_keep isl_mat *src, int s, int *exp)
 485 {
 486         int i;
 487         unsigned c = src->n_col - src->n_row;
 488
 489         isl_seq_cpy(dst->row[d], src->row[s], c);
 490         isl_seq_clr(dst->row[d] + c, dst->n_col - c);
 491
 492         for (i = 0; i < s; ++i)
 493                 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
 494 }
 495
 496 /* Compare (known) divs.
 497  * Return non-zero if at least one of the two divs is unknown.
 498  * In particular, if both divs are unknown, we respect their
 499  * current order.  Otherwise, we sort the known div after the unknown
 500  * div only if the known div depends on the unknown div.
 501  */
 502 static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
 503         unsigned n_row, unsigned n_col)
 504 {
 505         int li, lj;
 506         int unknown_i, unknown_j;
 507
 508         unknown_i = isl_int_is_zero(row_i[0]);
 509         unknown_j = isl_int_is_zero(row_j[0]);
 510
 511         if (unknown_i && unknown_j)
 512                 return i - j;
 513
 514         if (unknown_i)
 515                 li = n_col - n_row + i;
 516         else
 517                 li = isl_seq_last_non_zero(row_i, n_col);
 518         if (unknown_j)
 519                 lj = n_col - n_row + j;
 520         else
 521                 lj = isl_seq_last_non_zero(row_j, n_col);
 522
 523         if (li != lj)
 524                 return li - lj;
 525
 526         return isl_seq_cmp(row_i, row_j, n_col);
 527 }
 528
 529 /* Call cmp_row for divs in a matrix.
 530  */
 531 int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
 532 {
 533         return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
 534 }
 535
 536 /* Call cmp_row for divs in a basic map.
 537  */
 538 static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
 539         unsigned total)
 540 {
 541         return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
 542 }
 543
 544 /* Sort the divs in "bmap".
 545  *
 546  * We first make sure divs are placed after divs on which they depend.
 547  * Then we perform a simple insertion sort based on the same ordering
 548  * that is used in isl_merge_divs.
 549  */
 550 __isl_give isl_basic_map *isl_basic_map_sort_divs(
 551         __isl_take isl_basic_map *bmap)
 552 {
 553         int i, j;
 554         unsigned total;
 555
 556         bmap = isl_basic_map_order_divs(bmap);
 557         if (!bmap)
 558                 return NULL;
 559         if (bmap->n_div <= 1)
 560                 return bmap;
 561
 562         total = 2 + isl_basic_map_total_dim(bmap);
 563         for (i = 1; i < bmap->n_div; ++i) {
 564                 for (j = i - 1; j >= 0; --j) {
 565                         if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
 566                                 break;
 567                         isl_basic_map_swap_div(bmap, j, j + 1);
 568                 }
 569         }
 570
 571         return bmap;
 572 }
 573
 574 /* Sort the divs in the basic maps of "map".
 575  */
 576 __isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
 577 {
 578         return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
 579 }
 580
 581 /* Combine the two lists of divs into a single list.
 582  * For each row i in div1, exp1[i] is set to the position of the corresponding
 583  * row in the result.  Similarly for div2 and exp2.
 584  * This function guarantees
 585  *      exp1[i] >= i
 586  *      exp1[i+1] > exp1[i]
 587  * For optimal merging, the two input list should have been sorted.
 588  */
 589 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
 590         __isl_keep isl_mat *div2, int *exp1, int *exp2)
 591 {
 592         int i, j, k;
 593         isl_mat *div = NULL;
 594         unsigned d;
 595
 596         if (!div1 || !div2)
 597                 return NULL;
 598
 599         d = div1->n_col - div1->n_row;
 600         div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
 601                                 d + div1->n_row + div2->n_row);
 602         if (!div)
 603                 return NULL;
 604
 605         for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
 606                 int cmp;
 607
 608                 expand_row(div, k, div1, i, exp1);
 609                 expand_row(div, k + 1, div2, j, exp2);
 610
 611                 cmp = isl_mat_cmp_div(div, k, k + 1);
 612                 if (cmp == 0) {
 613                         exp1[i++] = k;
 614                         exp2[j++] = k;
 615                 } else if (cmp < 0) {
 616                         exp1[i++] = k;
 617                 } else {
 618                         exp2[j++] = k;
 619                         isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
 620                 }
 621         }
 622         for (; i < div1->n_row; ++i, ++k) {
 623                 expand_row(div, k, div1, i, exp1);
 624                 exp1[i] = k;
 625         }
 626         for (; j < div2->n_row; ++j, ++k) {
 627                 expand_row(div, k, div2, j, exp2);
 628                 exp2[j] = k;
 629         }
 630
 631         div->n_row = k;
 632         div->n_col = d + k;
 633
 634         return div;
 635 }
 636
 637 /* Swap divs "a" and "b" in "ls".
 638  */
 639 __isl_give isl_local_space *isl_local_space_swap_div(
 640         __isl_take isl_local_space *ls, int a, int b)
 641 {
 642         int offset;
 643
 644         ls = isl_local_space_cow(ls);
 645         if (!ls)
 646                 return NULL;
 647         if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
 648                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 649                         "index out of bounds", return isl_local_space_free(ls));
 650         offset = ls->div->n_col - ls->div->n_row;
 651         ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
 652         ls->div = isl_mat_swap_rows(ls->div, a, b);
 653         if (!ls->div)
 654                 return isl_local_space_free(ls);
 655         return ls;
 656 }
 657
 658 /* Construct a local space that contains all the divs in either
 659  * "ls1" or "ls2".
 660  */
 661 __isl_give isl_local_space *isl_local_space_intersect(
 662         __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
 663 {
 664         isl_ctx *ctx;
 665         int *exp1 = NULL;
 666         int *exp2 = NULL;
 667         isl_mat *div;
 668         int equal;
 669
 670         if (!ls1 || !ls2)
 671                 goto error;
 672
 673         ctx = isl_local_space_get_ctx(ls1);
 674         if (!isl_space_is_equal(ls1->dim, ls2->dim))
 675                 isl_die(ctx, isl_error_invalid,
 676                         "spaces should be identical", goto error);
 677
 678         if (ls2->div->n_row == 0) {
 679                 isl_local_space_free(ls2);
 680                 return ls1;
 681         }
 682
 683         if (ls1->div->n_row == 0) {
 684                 isl_local_space_free(ls1);
 685                 return ls2;
 686         }
 687
 688         exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
 689         exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
 690         if (!exp1 || !exp2)
 691                 goto error;
 692
 693         div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
 694         if (!div)
 695                 goto error;
 696
 697         equal = isl_mat_is_equal(ls1->div, div);
 698         if (equal < 0)
 699                 goto error;
 700         if (!equal)
 701                 ls1 = isl_local_space_cow(ls1);
 702         if (!ls1)
 703                 goto error;
 704
 705         free(exp1);
 706         free(exp2);
 707         isl_local_space_free(ls2);
 708         isl_mat_free(ls1->div);
 709         ls1->div = div;
 710
 711         return ls1;
 712 error:
 713         free(exp1);
 714         free(exp2);
 715         isl_local_space_free(ls1);
 716         isl_local_space_free(ls2);
 717         return NULL;
 718 }
 719
 720 /* Does "ls" have an explicit representation for div "div"?
 721  */
 722 isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
 723 {
 724         if (!ls)
 725                 return isl_bool_error;
 726         return isl_local_div_is_known(ls->div, div);
 727 }
 728
 729 /* Does "ls" have an explicit representation for all local variables?
 730  */
 731 isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
 732 {
 733         int i;
 734
 735         if (!ls)
 736                 return isl_bool_error;
 737
 738         for (i = 0; i < ls->div->n_row; ++i) {
 739                 isl_bool known = isl_local_space_div_is_known(ls, i);
 740                 if (known < 0 || !known)
 741                         return known;
 742         }
 743
 744         return isl_bool_true;
 745 }
 746
 747 __isl_give isl_local_space *isl_local_space_domain(
 748         __isl_take isl_local_space *ls)
 749 {
 750         ls = isl_local_space_drop_dims(ls, isl_dim_out,
 751                                         0, isl_local_space_dim(ls, isl_dim_out));
 752         ls = isl_local_space_cow(ls);
 753         if (!ls)
 754                 return NULL;
 755         ls->dim = isl_space_domain(ls->dim);
 756         if (!ls->dim)
 757                 return isl_local_space_free(ls);
 758         return ls;
 759 }
 760
 761 __isl_give isl_local_space *isl_local_space_range(
 762         __isl_take isl_local_space *ls)
 763 {
 764         ls = isl_local_space_drop_dims(ls, isl_dim_in,
 765                                         0, isl_local_space_dim(ls, isl_dim_in));
 766         ls = isl_local_space_cow(ls);
 767         if (!ls)
 768                 return NULL;
 769
 770         ls->dim = isl_space_range(ls->dim);
 771         if (!ls->dim)
 772                 return isl_local_space_free(ls);
 773         return ls;
 774 }
 775
 776 /* Construct a local space for a map that has the given local
 777  * space as domain and that has a zero-dimensional range.
 778  */
 779 __isl_give isl_local_space *isl_local_space_from_domain(
 780         __isl_take isl_local_space *ls)
 781 {
 782         ls = isl_local_space_cow(ls);
 783         if (!ls)
 784                 return NULL;
 785         ls->dim = isl_space_from_domain(ls->dim);
 786         if (!ls->dim)
 787                 return isl_local_space_free(ls);
 788         return ls;
 789 }
 790
 791 __isl_give isl_local_space *isl_local_space_add_dims(
 792         __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
 793 {
 794         int pos;
 795
 796         if (!ls)
 797                 return NULL;
 798         pos = isl_local_space_dim(ls, type);
 799         return isl_local_space_insert_dims(ls, type, pos, n);
 800 }
 801
 802 /* Remove common factor of non-constant terms and denominator.
 803  */
 804 static void normalize_div(__isl_keep isl_local_space *ls, int div)
 805 {
 806         isl_ctx *ctx = ls->div->ctx;
 807         unsigned total = ls->div->n_col - 2;
 808
 809         isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
 810         isl_int_gcd(ctx->normalize_gcd,
 811                     ctx->normalize_gcd, ls->div->row[div][0]);
 812         if (isl_int_is_one(ctx->normalize_gcd))
 813                 return;
 814
 815         isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
 816                             ctx->normalize_gcd, total);
 817         isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
 818                             ctx->normalize_gcd);
 819         isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
 820                             ctx->normalize_gcd);
 821 }
 822
 823 /* Exploit the equalities in "eq" to simplify the expressions of
 824  * the integer divisions in "ls".
 825  * The integer divisions in "ls" are assumed to appear as regular
 826  * dimensions in "eq".
 827  */
 828 __isl_give isl_local_space *isl_local_space_substitute_equalities(
 829         __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
 830 {
 831         int i, j, k;
 832         unsigned total;
 833         unsigned n_div;
 834
 835         if (!ls || !eq)
 836                 goto error;
 837
 838         total = isl_space_dim(eq->dim, isl_dim_all);
 839         if (isl_local_space_dim(ls, isl_dim_all) != total)
 840                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 841                         "spaces don't match", goto error);
 842         total++;
 843         n_div = eq->n_div;
 844         for (i = 0; i < eq->n_eq; ++i) {
 845                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 846                 if (j < 0 || j == 0 || j >= total)
 847                         continue;
 848
 849                 for (k = 0; k < ls->div->n_row; ++k) {
 850                         if (isl_int_is_zero(ls->div->row[k][1 + j]))
 851                                 continue;
 852                         ls = isl_local_space_cow(ls);
 853                         if (!ls)
 854                                 goto error;
 855                         ls->div = isl_mat_cow(ls->div);
 856                         if (!ls->div)
 857                                 goto error;
 858                         isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
 859                                         &ls->div->row[k][0]);
 860                         normalize_div(ls, k);
 861                 }
 862         }
 863
 864         isl_basic_set_free(eq);
 865         return ls;
 866 error:
 867         isl_basic_set_free(eq);
 868         isl_local_space_free(ls);
 869         return NULL;
 870 }
 871
 872 /* Plug in the affine expressions "subs" of length "subs_len" (including
 873  * the denominator and the constant term) into the variable at position "pos"
 874  * of the "n" div expressions starting at "first".
 875  *
 876  * Let i be the dimension to replace and let "subs" be of the form
 877  *
 878  *      f/d
 879  *
 880  * Any integer division starting at "first" with a non-zero coefficient for i,
 881  *
 882  *      floor((a i + g)/m)
 883  *
 884  * is replaced by
 885  *
 886  *      floor((a f + d g)/(m d))
 887  */
 888 __isl_give isl_local_space *isl_local_space_substitute_seq(
 889         __isl_take isl_local_space *ls,
 890         enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
 891         int first, int n)
 892 {
 893         int i;
 894         isl_int v;
 895
 896         if (n == 0)
 897                 return ls;
 898         ls = isl_local_space_cow(ls);
 899         if (!ls)
 900                 return NULL;
 901         ls->div = isl_mat_cow(ls->div);
 902         if (!ls->div)
 903                 return isl_local_space_free(ls);
 904
 905         if (first + n > ls->div->n_row)
 906                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 907                         "index out of bounds", return isl_local_space_free(ls));
 908
 909         pos += isl_local_space_offset(ls, type);
 910
 911         isl_int_init(v);
 912         for (i = first; i < first + n; ++i) {
 913                 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
 914                         continue;
 915                 isl_seq_substitute(ls->div->row[i], pos, subs,
 916                         ls->div->n_col, subs_len, v);
 917                 normalize_div(ls, i);
 918         }
 919         isl_int_clear(v);
 920
 921         return ls;
 922 }
 923
 924 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
 925  * of "ls".
 926  *
 927  * Let i be the dimension to replace and let "subs" be of the form
 928  *
 929  *      f/d
 930  *
 931  * Any integer division with a non-zero coefficient for i,
 932  *
 933  *      floor((a i + g)/m)
 934  *
 935  * is replaced by
 936  *
 937  *      floor((a f + d g)/(m d))
 938  */
 939 __isl_give isl_local_space *isl_local_space_substitute(
 940         __isl_take isl_local_space *ls,
 941         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
 942 {
 943         ls = isl_local_space_cow(ls);
 944         if (!ls || !subs)
 945                 return isl_local_space_free(ls);
 946
 947         if (!isl_space_is_equal(ls->dim, subs->ls->dim))
 948                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 949                         "spaces don't match", return isl_local_space_free(ls));
 950         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
 951                 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
 952                         "cannot handle divs yet",
 953                         return isl_local_space_free(ls));
 954
 955         return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
 956                                             subs->v->size, 0, ls->div->n_row);
 957 }
 958
 959 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
 960         enum isl_dim_type type)
 961 {
 962         if (!ls)
 963                 return -1;
 964         return isl_space_is_named_or_nested(ls->dim, type);
 965 }
 966
 967 __isl_give isl_local_space *isl_local_space_drop_dims(
 968         __isl_take isl_local_space *ls,
 969         enum isl_dim_type type, unsigned first, unsigned n)
 970 {
 971         isl_ctx *ctx;
 972
 973         if (!ls)
 974                 return NULL;
 975         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 976                 return ls;
 977
 978         ctx = isl_local_space_get_ctx(ls);
 979         if (first + n > isl_local_space_dim(ls, type))
 980                 isl_die(ctx, isl_error_invalid, "range out of bounds",
 981                         return isl_local_space_free(ls));
 982
 983         ls = isl_local_space_cow(ls);
 984         if (!ls)
 985                 return NULL;
 986
 987         if (type == isl_dim_div) {
 988                 ls->div = isl_mat_drop_rows(ls->div, first, n);
 989         } else {
 990                 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
 991                 if (!ls->dim)
 992                         return isl_local_space_free(ls);
 993         }
 994
 995         first += 1 + isl_local_space_offset(ls, type);
 996         ls->div = isl_mat_drop_cols(ls->div, first, n);
 997         if (!ls->div)
 998                 return isl_local_space_free(ls);
 999
1000         return ls;
1001 }
1002
1003 __isl_give isl_local_space *isl_local_space_insert_dims(
1004         __isl_take isl_local_space *ls,
1005         enum isl_dim_type type, unsigned first, unsigned n)
1006 {
1007         isl_ctx *ctx;
1008
1009         if (!ls)
1010                 return NULL;
1011         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
1012                 return ls;
1013
1014         ctx = isl_local_space_get_ctx(ls);
1015         if (first > isl_local_space_dim(ls, type))
1016                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1017                         return isl_local_space_free(ls));
1018
1019         ls = isl_local_space_cow(ls);
1020         if (!ls)
1021                 return NULL;
1022
1023         if (type == isl_dim_div) {
1024                 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
1025         } else {
1026                 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
1027                 if (!ls->dim)
1028                         return isl_local_space_free(ls);
1029         }
1030
1031         first += 1 + isl_local_space_offset(ls, type);
1032         ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
1033         if (!ls->div)
1034                 return isl_local_space_free(ls);
1035
1036         return ls;
1037 }
1038
1039 /* Check if the constraints pointed to by "constraint" is a div
1040  * constraint corresponding to div "div" in "ls".
1041  *
1042  * That is, if div = floor(f/m), then check if the constraint is
1043  *
1044  *              f - m d >= 0
1045  * or
1046  *              -(f-(m-1)) + m d >= 0
1047  */
1048 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1049         isl_int *constraint, unsigned div)
1050 {
1051         unsigned pos;
1052
1053         if (!ls)
1054                 return -1;
1055
1056         if (isl_int_is_zero(ls->div->row[div][0]))
1057                 return 0;
1058
1059         pos = isl_local_space_offset(ls, isl_dim_div) + div;
1060
1061         if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
1062                 int neg;
1063                 isl_int_sub(ls->div->row[div][1],
1064                                 ls->div->row[div][1], ls->div->row[div][0]);
1065                 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1066                 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
1067                 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1068                 isl_int_add(ls->div->row[div][1],
1069                                 ls->div->row[div][1], ls->div->row[div][0]);
1070                 if (!neg)
1071                         return 0;
1072                 if (isl_seq_first_non_zero(constraint+pos+1,
1073                                             ls->div->n_row-div-1) != -1)
1074                         return 0;
1075         } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
1076                 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
1077                         return 0;
1078                 if (isl_seq_first_non_zero(constraint+pos+1,
1079                                             ls->div->n_row-div-1) != -1)
1080                         return 0;
1081         } else
1082                 return 0;
1083
1084         return 1;
1085 }
1086
1087 /*
1088  * Set active[i] to 1 if the dimension at position i is involved
1089  * in the linear expression l.
1090  */
1091 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1092 {
1093         int i, j;
1094         isl_ctx *ctx;
1095         int *active = NULL;
1096         unsigned total;
1097         unsigned offset;
1098
1099         ctx = isl_local_space_get_ctx(ls);
1100         total = isl_local_space_dim(ls, isl_dim_all);
1101         active = isl_calloc_array(ctx, int, total);
1102         if (total && !active)
1103                 return NULL;
1104
1105         for (i = 0; i < total; ++i)
1106                 active[i] = !isl_int_is_zero(l[i]);
1107
1108         offset = isl_local_space_offset(ls, isl_dim_div) - 1;
1109         for (i = ls->div->n_row - 1; i >= 0; --i) {
1110                 if (!active[offset + i])
1111                         continue;
1112                 for (j = 0; j < total; ++j)
1113                         active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
1114         }
1115
1116         return active;
1117 }
1118
1119 /* Given a local space "ls" of a set, create a local space
1120  * for the lift of the set.  In particular, the result
1121  * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1122  * range of the wrapped map.
1123  */
1124 __isl_give isl_local_space *isl_local_space_lift(
1125         __isl_take isl_local_space *ls)
1126 {
1127         ls = isl_local_space_cow(ls);
1128         if (!ls)
1129                 return NULL;
1130
1131         ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1132         ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1133         if (!ls->dim || !ls->div)
1134                 return isl_local_space_free(ls);
1135
1136         return ls;
1137 }
1138
1139 /* Construct a basic map that maps a set living in local space "ls"
1140  * to the corresponding lifted local space.
1141  */
1142 __isl_give isl_basic_map *isl_local_space_lifting(
1143         __isl_take isl_local_space *ls)
1144 {
1145         isl_basic_map *lifting;
1146         isl_basic_set *bset;
1147
1148         if (!ls)
1149                 return NULL;
1150         if (!isl_local_space_is_set(ls))
1151                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1152                         "lifting only defined on set spaces", goto error);
1153
1154         bset = isl_basic_set_from_local_space(ls);
1155         lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1156         lifting = isl_basic_map_domain_map(lifting);
1157         lifting = isl_basic_map_reverse(lifting);
1158
1159         return lifting;
1160 error:
1161         isl_local_space_free(ls);
1162         return NULL;
1163 }
1164
1165 /* Compute the preimage of "ls" under the function represented by "ma".
1166  * In other words, plug in "ma" in "ls".  The result is a local space
1167  * that is part of the domain space of "ma".
1168  *
1169  * If the divs in "ls" are represented as
1170  *
1171  *      floor((a_i(p) + b_i x + c_i(divs))/n_i)
1172  *
1173  * and ma is represented by
1174  *
1175  *      x = D(p) + F(y) + G(divs')
1176  *
1177  * then the resulting divs are
1178  *
1179  *      floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1180  *
1181  * We first copy over the divs from "ma" and then
1182  * we add the modified divs from "ls".
1183  */
1184 __isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1185         __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1186 {
1187         int i;
1188         isl_space *space;
1189         isl_local_space *res = NULL;
1190         int n_div_ls, n_div_ma;
1191         isl_int f, c1, c2, g;
1192
1193         ma = isl_multi_aff_align_divs(ma);
1194         if (!ls || !ma)
1195                 goto error;
1196         if (!isl_space_is_range_internal(ls->dim, ma->space))
1197                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1198                         "spaces don't match", goto error);
1199
1200         n_div_ls = isl_local_space_dim(ls, isl_dim_div);
1201         n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
1202
1203         space = isl_space_domain(isl_multi_aff_get_space(ma));
1204         res = isl_local_space_alloc(space, n_div_ma + n_div_ls);
1205         if (!res)
1206                 goto error;
1207
1208         if (n_div_ma) {
1209                 isl_mat_free(res->div);
1210                 res->div = isl_mat_copy(ma->p[0]->ls->div);
1211                 res->div = isl_mat_add_zero_cols(res->div, n_div_ls);
1212                 res->div = isl_mat_add_rows(res->div, n_div_ls);
1213                 if (!res->div)
1214                         goto error;
1215         }
1216
1217         isl_int_init(f);
1218         isl_int_init(c1);
1219         isl_int_init(c2);
1220         isl_int_init(g);
1221
1222         for (i = 0; i < ls->div->n_row; ++i) {
1223                 if (isl_int_is_zero(ls->div->row[i][0])) {
1224                         isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1225                         continue;
1226                 }
1227                 isl_seq_preimage(res->div->row[n_div_ma + i], ls->div->row[i],
1228                                 ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1);
1229                 normalize_div(res, n_div_ma + i);
1230         }
1231
1232         isl_int_clear(f);
1233         isl_int_clear(c1);
1234         isl_int_clear(c2);
1235         isl_int_clear(g);
1236
1237         isl_local_space_free(ls);
1238         isl_multi_aff_free(ma);
1239         return res;
1240 error:
1241         isl_local_space_free(ls);
1242         isl_multi_aff_free(ma);
1243         isl_local_space_free(res);
1244         return NULL;
1245 }
1246
1247 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1248  * to dimensions of "dst_type" at "dst_pos".
1249  *
1250  * Moving to/from local dimensions is not allowed.
1251  * We currently assume that the dimension type changes.
1252  */
1253 __isl_give isl_local_space *isl_local_space_move_dims(
1254         __isl_take isl_local_space *ls,
1255         enum isl_dim_type dst_type, unsigned dst_pos,
1256         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1257 {
1258         unsigned g_dst_pos;
1259         unsigned g_src_pos;
1260
1261         if (!ls)
1262                 return NULL;
1263         if (n == 0 &&
1264             !isl_local_space_is_named_or_nested(ls, src_type) &&
1265             !isl_local_space_is_named_or_nested(ls, dst_type))
1266                 return ls;
1267
1268         if (src_pos + n > isl_local_space_dim(ls, src_type))
1269                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1270                         "range out of bounds", return isl_local_space_free(ls));
1271         if (dst_pos > isl_local_space_dim(ls, dst_type))
1272                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1273                         "position out of bounds",
1274                         return isl_local_space_free(ls));
1275         if (src_type == isl_dim_div)
1276                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1277                         "cannot move divs", return isl_local_space_free(ls));
1278         if (dst_type == isl_dim_div)
1279                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1280                         "cannot move to divs", return isl_local_space_free(ls));
1281         if (dst_type == src_type && dst_pos == src_pos)
1282                 return ls;
1283         if (dst_type == src_type)
1284                 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1285                         "moving dims within the same type not supported",
1286                         return isl_local_space_free(ls));
1287
1288         ls = isl_local_space_cow(ls);
1289         if (!ls)
1290                 return NULL;
1291
1292         g_src_pos = 1 + isl_local_space_offset(ls, src_type) + src_pos;
1293         g_dst_pos = 1 + isl_local_space_offset(ls, dst_type) + dst_pos;
1294         if (dst_type > src_type)
1295                 g_dst_pos -= n;
1296         ls->div = isl_mat_move_cols(ls->div, g_dst_pos, g_src_pos, n);
1297         if (!ls->div)
1298                 return isl_local_space_free(ls);
1299         ls->dim = isl_space_move_dims(ls->dim, dst_type, dst_pos,
1300                                         src_type, src_pos, n);
1301         if (!ls->dim)
1302                 return isl_local_space_free(ls);
1303
1304         return ls;
1305 }
1306
1307 /* Remove any internal structure of the domain of "ls".
1308  * If there is any such internal structure in the input,
1309  * then the name of the corresponding space is also removed.
1310  */
1311 __isl_give isl_local_space *isl_local_space_flatten_domain(
1312         __isl_take isl_local_space *ls)
1313 {
1314         if (!ls)
1315                 return NULL;
1316
1317         if (!ls->dim->nested[0])
1318                 return ls;
1319
1320         ls = isl_local_space_cow(ls);
1321         if (!ls)
1322                 return NULL;
1323
1324         ls->dim = isl_space_flatten_domain(ls->dim);
1325         if (!ls->dim)
1326                 return isl_local_space_free(ls);
1327
1328         return ls;
1329 }
1330
1331 /* Remove any internal structure of the range of "ls".
1332  * If there is any such internal structure in the input,
1333  * then the name of the corresponding space is also removed.
1334  */
1335 __isl_give isl_local_space *isl_local_space_flatten_range(
1336         __isl_take isl_local_space *ls)
1337 {
1338         if (!ls)
1339                 return NULL;
1340
1341         if (!ls->dim->nested[1])
1342                 return ls;
1343
1344         ls = isl_local_space_cow(ls);
1345         if (!ls)
1346                 return NULL;
1347
1348         ls->dim = isl_space_flatten_range(ls->dim);
1349         if (!ls->dim)
1350                 return isl_local_space_free(ls);
1351
1352         return ls;
1353 }
1354
1355 /* Given the local space "ls" of a map, return the local space of a set
1356  * that lives in a space that wraps the space of "ls" and that has
1357  * the same divs.
1358  */
1359 __isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)
1360 {
1361         ls = isl_local_space_cow(ls);
1362         if (!ls)
1363                 return NULL;
1364
1365         ls->dim = isl_space_wrap(ls->dim);
1366         if (!ls->dim)
1367                 return isl_local_space_free(ls);
1368
1369         return ls;
1370 }