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