isl_local_space.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_ctx_private.h>
  12 #include <isl_map_private.h>
  13 #include <isl_local_space_private.h>
  14 #include <isl_space_private.h>
  15 #include <isl_mat_private.h>
  16 #include <isl_aff_private.h>
  17 #include <isl/seq.h>
  18
  19 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
  20 {
  21         return ls ? ls->dim->ctx : NULL;
  22 }
  23
  24 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
  25         __isl_take isl_mat *div)
  26 {
  27         isl_ctx *ctx;
  28         isl_local_space *ls = NULL;
  29
  30         if (!dim)
  31                 goto error;
  32
  33         ctx = isl_space_get_ctx(dim);
  34         ls = isl_calloc_type(ctx, struct isl_local_space);
  35         if (!ls)
  36                 goto error;
  37
  38         ls->ref = 1;
  39         ls->dim = dim;
  40         ls->div = div;
  41
  42         return ls;
  43 error:
  44         isl_space_free(dim);
  45         isl_local_space_free(ls);
  46         return NULL;
  47 }
  48
  49 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
  50         unsigned n_div)
  51 {
  52         isl_ctx *ctx;
  53         isl_mat *div;
  54         unsigned total;
  55
  56         if (!dim)
  57                 return NULL;
  58
  59         total = isl_space_dim(dim, isl_dim_all);
  60
  61         ctx = isl_space_get_ctx(dim);
  62         div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
  63         return isl_local_space_alloc_div(dim, div);
  64 }
  65
  66 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
  67 {
  68         return isl_local_space_alloc(dim, 0);
  69 }
  70
  71 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
  72 {
  73         if (!ls)
  74                 return NULL;
  75
  76         ls->ref++;
  77         return ls;
  78 }
  79
  80 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
  81 {
  82         if (!ls)
  83                 return NULL;
  84
  85         return isl_local_space_alloc_div(isl_space_copy(ls->dim),
  86                                          isl_mat_copy(ls->div));
  87
  88 }
  89
  90 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
  91 {
  92         if (!ls)
  93                 return NULL;
  94
  95         if (ls->ref == 1)
  96                 return ls;
  97         ls->ref--;
  98         return isl_local_space_dup(ls);
  99 }
 100
 101 void *isl_local_space_free(__isl_take isl_local_space *ls)
 102 {
 103         if (!ls)
 104                 return NULL;
 105
 106         if (--ls->ref > 0)
 107                 return NULL;
 108
 109         isl_space_free(ls->dim);
 110         isl_mat_free(ls->div);
 111
 112         free(ls);
 113
 114         return NULL;
 115 }
 116
 117 /* Is the local space that of a set?
 118  */
 119 int isl_local_space_is_set(__isl_keep isl_local_space *ls)
 120 {
 121         return ls ? isl_space_is_set(ls->dim) : -1;
 122 }
 123
 124 /* Return true if the two local spaces are identical, with identical
 125  * expressions for the integer divisions.
 126  */
 127 int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
 128         __isl_keep isl_local_space *ls2)
 129 {
 130         int equal;
 131
 132         if (!ls1 || !ls2)
 133                 return -1;
 134
 135         equal = isl_space_is_equal(ls1->dim, ls2->dim);
 136         if (equal < 0 || !equal)
 137                 return equal;
 138
 139         if (!isl_local_space_divs_known(ls1))
 140                 return 0;
 141         if (!isl_local_space_divs_known(ls2))
 142                 return 0;
 143
 144         return isl_mat_is_equal(ls1->div, ls2->div);
 145 }
 146
 147 int isl_local_space_dim(__isl_keep isl_local_space *ls,
 148         enum isl_dim_type type)
 149 {
 150         if (!ls)
 151                 return 0;
 152         if (type == isl_dim_div)
 153                 return ls->div->n_row;
 154         if (type == isl_dim_all)
 155                 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
 156         return isl_space_dim(ls->dim, type);
 157 }
 158
 159 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
 160         enum isl_dim_type type)
 161 {
 162         isl_space *dim;
 163
 164         if (!ls)
 165                 return 0;
 166
 167         dim = ls->dim;
 168         switch (type) {
 169         case isl_dim_cst:       return 0;
 170         case isl_dim_param:     return 1;
 171         case isl_dim_in:        return 1 + dim->nparam;
 172         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 173         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 174         default:                return 0;
 175         }
 176 }
 177
 178 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
 179         enum isl_dim_type type, unsigned pos)
 180 {
 181         return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
 182 }
 183
 184 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
 185         int pos)
 186 {
 187         isl_aff *aff;
 188
 189         if (!ls)
 190                 return NULL;
 191
 192         if (pos < 0 || pos >= ls->div->n_row)
 193                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 194                         "index out of bounds", return NULL);
 195
 196         if (isl_int_is_zero(ls->div->row[pos][0]))
 197                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 198                         "expression of div unknown", return NULL);
 199
 200         aff = isl_aff_alloc(isl_local_space_copy(ls));
 201         if (!aff)
 202                 return NULL;
 203         isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
 204         return aff;
 205 }
 206
 207 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
 208 {
 209         if (!ls)
 210                 return NULL;
 211
 212         return isl_space_copy(ls->dim);
 213 }
 214
 215 __isl_give isl_local_space *isl_local_space_set_dim_name(
 216         __isl_take isl_local_space *ls,
 217         enum isl_dim_type type, unsigned pos, const char *s)
 218 {
 219         ls = isl_local_space_cow(ls);
 220         if (!ls)
 221                 return NULL;
 222         ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
 223         if (!ls->dim)
 224                 return isl_local_space_free(ls);
 225
 226         return ls;
 227 }
 228
 229 __isl_give isl_local_space *isl_local_space_set_dim_id(
 230         __isl_take isl_local_space *ls,
 231         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 232 {
 233         ls = isl_local_space_cow(ls);
 234         if (!ls)
 235                 return isl_id_free(id);
 236         ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
 237         if (!ls->dim)
 238                 return isl_local_space_free(ls);
 239
 240         return ls;
 241 }
 242
 243 __isl_give isl_local_space *isl_local_space_reset_space(
 244         __isl_take isl_local_space *ls, __isl_take isl_space *dim)
 245 {
 246         ls = isl_local_space_cow(ls);
 247         if (!ls || !dim)
 248                 goto error;
 249
 250         isl_space_free(ls->dim);
 251         ls->dim = dim;
 252
 253         return ls;
 254 error:
 255         isl_local_space_free(ls);
 256         isl_space_free(dim);
 257         return NULL;
 258 }
 259
 260 /* Reorder the columns of the given div definitions according to the
 261  * given reordering.
 262  * The order of the divs themselves is assumed not to change.
 263  */
 264 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
 265         __isl_take isl_reordering *r)
 266 {
 267         int i, j;
 268         isl_mat *mat;
 269         int extra;
 270
 271         if (!div || !r)
 272                 goto error;
 273
 274         extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
 275         mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
 276         if (!mat)
 277                 goto error;
 278
 279         for (i = 0; i < div->n_row; ++i) {
 280                 isl_seq_cpy(mat->row[i], div->row[i], 2);
 281                 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
 282                 for (j = 0; j < r->len; ++j)
 283                         isl_int_set(mat->row[i][2 + r->pos[j]],
 284                                     div->row[i][2 + j]);
 285         }
 286
 287         isl_reordering_free(r);
 288         isl_mat_free(div);
 289         return mat;
 290 error:
 291         isl_reordering_free(r);
 292         isl_mat_free(div);
 293         return NULL;
 294 }
 295
 296 /* Reorder the dimensions of "ls" according to the given reordering.
 297  * The reordering r is assumed to have been extended with the local
 298  * variables, leaving them in the same order.
 299  */
 300 __isl_give isl_local_space *isl_local_space_realign(
 301         __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
 302 {
 303         ls = isl_local_space_cow(ls);
 304         if (!ls || !r)
 305                 goto error;
 306
 307         ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
 308         if (!ls->div)
 309                 goto error;
 310
 311         ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
 312
 313         isl_reordering_free(r);
 314         return ls;
 315 error:
 316         isl_local_space_free(ls);
 317         isl_reordering_free(r);
 318         return NULL;
 319 }
 320
 321 __isl_give isl_local_space *isl_local_space_add_div(
 322         __isl_take isl_local_space *ls, __isl_take isl_vec *div)
 323 {
 324         ls = isl_local_space_cow(ls);
 325         if (!ls || !div)
 326                 goto error;
 327
 328         if (ls->div->n_col != div->size)
 329                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 330                         "incompatible dimensions", goto error);
 331
 332         ls->div = isl_mat_add_zero_cols(ls->div, 1);
 333         ls->div = isl_mat_add_rows(ls->div, 1);
 334         if (!ls->div)
 335                 goto error;
 336
 337         isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
 338         isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
 339
 340         isl_vec_free(div);
 341         return ls;
 342 error:
 343         isl_local_space_free(ls);
 344         isl_vec_free(div);
 345         return NULL;
 346 }
 347
 348 __isl_give isl_local_space *isl_local_space_replace_divs(
 349         __isl_take isl_local_space *ls, __isl_take isl_mat *div)
 350 {
 351         ls = isl_local_space_cow(ls);
 352
 353         if (!ls || !div)
 354                 goto error;
 355
 356         isl_mat_free(ls->div);
 357         ls->div = div;
 358         return ls;
 359 error:
 360         isl_mat_free(div);
 361         isl_local_space_free(ls);
 362         return NULL;
 363 }
 364
 365 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
 366  * defined by "exp".
 367  */
 368 static void expand_row(__isl_keep isl_mat *dst, int d,
 369         __isl_keep isl_mat *src, int s, int *exp)
 370 {
 371         int i;
 372         unsigned c = src->n_col - src->n_row;
 373
 374         isl_seq_cpy(dst->row[d], src->row[s], c);
 375         isl_seq_clr(dst->row[d] + c, dst->n_col - c);
 376
 377         for (i = 0; i < s; ++i)
 378                 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
 379 }
 380
 381 /* Compare (known) divs.
 382  * Return non-zero if at least one of the two divs is unknown.
 383  */
 384 static int cmp_row(__isl_keep isl_mat *div, int i, int j)
 385 {
 386         int li, lj;
 387
 388         if (isl_int_is_zero(div->row[j][0]))
 389                 return -1;
 390         if (isl_int_is_zero(div->row[i][0]))
 391                 return 1;
 392
 393         li = isl_seq_last_non_zero(div->row[i], div->n_col);
 394         lj = isl_seq_last_non_zero(div->row[j], div->n_col);
 395
 396         if (li != lj)
 397                 return li - lj;
 398
 399         return isl_seq_cmp(div->row[i], div->row[j], div->n_col);
 400 }
 401
 402 /* Combine the two lists of divs into a single list.
 403  * For each row i in div1, exp1[i] is set to the position of the corresponding
 404  * row in the result.  Similarly for div2 and exp2.
 405  * This function guarantees
 406  *      exp1[i] >= i
 407  *      exp1[i+1] > exp1[i]
 408  * For optimal merging, the two input list should have been sorted.
 409  */
 410 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
 411         __isl_keep isl_mat *div2, int *exp1, int *exp2)
 412 {
 413         int i, j, k;
 414         isl_mat *div = NULL;
 415         unsigned d = div1->n_col - div1->n_row;
 416
 417         div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
 418                                 d + div1->n_row + div2->n_row);
 419         if (!div)
 420                 return NULL;
 421
 422         for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
 423                 int cmp;
 424
 425                 expand_row(div, k, div1, i, exp1);
 426                 expand_row(div, k + 1, div2, j, exp2);
 427
 428                 cmp = cmp_row(div, k, k + 1);
 429                 if (cmp == 0) {
 430                         exp1[i++] = k;
 431                         exp2[j++] = k;
 432                 } else if (cmp < 0) {
 433                         exp1[i++] = k;
 434                 } else {
 435                         exp2[j++] = k;
 436                         isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
 437                 }
 438         }
 439         for (; i < div1->n_row; ++i, ++k) {
 440                 expand_row(div, k, div1, i, exp1);
 441                 exp1[i] = k;
 442         }
 443         for (; j < div2->n_row; ++j, ++k) {
 444                 expand_row(div, k, div2, j, exp2);
 445                 exp2[j] = k;
 446         }
 447
 448         div->n_row = k;
 449         div->n_col = d + k;
 450
 451         return div;
 452 }
 453
 454 /* Construct a local space that contains all the divs in either
 455  * "ls1" or "ls2".
 456  */
 457 __isl_give isl_local_space *isl_local_space_intersect(
 458         __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
 459 {
 460         isl_ctx *ctx;
 461         int *exp1 = NULL;
 462         int *exp2 = NULL;
 463         isl_mat *div;
 464
 465         if (!ls1 || !ls2)
 466                 goto error;
 467
 468         ctx = isl_local_space_get_ctx(ls1);
 469         if (!isl_space_is_equal(ls1->dim, ls2->dim))
 470                 isl_die(ctx, isl_error_invalid,
 471                         "spaces should be identical", goto error);
 472
 473         if (ls2->div->n_row == 0) {
 474                 isl_local_space_free(ls2);
 475                 return ls1;
 476         }
 477
 478         if (ls1->div->n_row == 0) {
 479                 isl_local_space_free(ls1);
 480                 return ls2;
 481         }
 482
 483         exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
 484         exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
 485         if (!exp1 || !exp2)
 486                 goto error;
 487
 488         div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
 489         if (!div)
 490                 goto error;
 491
 492         free(exp1);
 493         free(exp2);
 494         isl_local_space_free(ls2);
 495         isl_mat_free(ls1->div);
 496         ls1->div = div;
 497
 498         return ls1;
 499 error:
 500         free(exp1);
 501         free(exp2);
 502         isl_local_space_free(ls1);
 503         isl_local_space_free(ls2);
 504         return NULL;
 505 }
 506
 507 int isl_local_space_divs_known(__isl_keep isl_local_space *ls)
 508 {
 509         int i;
 510
 511         if (!ls)
 512                 return -1;
 513
 514         for (i = 0; i < ls->div->n_row; ++i)
 515                 if (isl_int_is_zero(ls->div->row[i][0]))
 516                         return 0;
 517
 518         return 1;
 519 }
 520
 521 __isl_give isl_local_space *isl_local_space_domain(
 522         __isl_take isl_local_space *ls)
 523 {
 524         ls = isl_local_space_drop_dims(ls, isl_dim_out,
 525                                         0, isl_local_space_dim(ls, isl_dim_out));
 526         ls = isl_local_space_cow(ls);
 527         if (!ls)
 528                 return NULL;
 529         ls->dim = isl_space_domain(ls->dim);
 530         if (!ls->dim)
 531                 return isl_local_space_free(ls);
 532         return ls;
 533 }
 534
 535 /* Construct a local space for a map that has the given local
 536  * space as domain and that has a zero-dimensional range.
 537  */
 538 __isl_give isl_local_space *isl_local_space_from_domain(
 539         __isl_take isl_local_space *ls)
 540 {
 541         ls = isl_local_space_cow(ls);
 542         if (!ls)
 543                 return NULL;
 544         ls->dim = isl_space_from_domain(ls->dim);
 545         if (!ls->dim)
 546                 return isl_local_space_free(ls);
 547         return ls;
 548 }
 549
 550 __isl_give isl_local_space *isl_local_space_add_dims(
 551         __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
 552 {
 553         int pos;
 554
 555         if (!ls)
 556                 return NULL;
 557         pos = isl_local_space_dim(ls, type);
 558         return isl_local_space_insert_dims(ls, type, pos, n);
 559 }
 560
 561 /* Remove common factor of non-constant terms and denominator.
 562  */
 563 static void normalize_div(__isl_keep isl_local_space *ls, int div)
 564 {
 565         isl_ctx *ctx = ls->div->ctx;
 566         unsigned total = ls->div->n_col - 2;
 567
 568         isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
 569         isl_int_gcd(ctx->normalize_gcd,
 570                     ctx->normalize_gcd, ls->div->row[div][0]);
 571         if (isl_int_is_one(ctx->normalize_gcd))
 572                 return;
 573
 574         isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
 575                             ctx->normalize_gcd, total);
 576         isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
 577                             ctx->normalize_gcd);
 578         isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
 579                             ctx->normalize_gcd);
 580 }
 581
 582 /* Exploit the equalities in "eq" to simplify the expressions of
 583  * the integer divisions in "ls".
 584  * The integer divisions in "ls" are assumed to appear as regular
 585  * dimensions in "eq".
 586  */
 587 __isl_give isl_local_space *isl_local_space_substitute_equalities(
 588         __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
 589 {
 590         int i, j, k;
 591         unsigned total;
 592         unsigned n_div;
 593
 594         ls = isl_local_space_cow(ls);
 595         if (!ls || !eq)
 596                 goto error;
 597
 598         total = isl_space_dim(eq->dim, isl_dim_all);
 599         if (isl_local_space_dim(ls, isl_dim_all) != total)
 600                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 601                         "dimensions don't match", goto error);
 602         total++;
 603         n_div = eq->n_div;
 604         for (i = 0; i < eq->n_eq; ++i) {
 605                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 606                 if (j < 0 || j == 0 || j >= total)
 607                         continue;
 608
 609                 for (k = 0; k < ls->div->n_row; ++k) {
 610                         if (isl_int_is_zero(ls->div->row[k][1 + j]))
 611                                 continue;
 612                         isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
 613                                         &ls->div->row[k][0]);
 614                         normalize_div(ls, k);
 615                 }
 616         }
 617
 618         isl_basic_set_free(eq);
 619         return ls;
 620 error:
 621         isl_basic_set_free(eq);
 622         isl_local_space_free(ls);
 623         return NULL;
 624 }
 625
 626 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
 627  * of "ls".
 628  *
 629  * Let i be the dimension to replace and let "subs" be of the form
 630  *
 631  *      f/d
 632  *
 633  * Any integer division with a non-zero coefficient for i,
 634  *
 635  *      floor((a i + g)/m)
 636  *
 637  * is replaced by
 638  *
 639  *      floor((a f + d g)/(m d))
 640  */
 641 __isl_give isl_local_space *isl_local_space_substitute(
 642         __isl_take isl_local_space *ls,
 643         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
 644 {
 645         int i;
 646         isl_int v;
 647
 648         ls = isl_local_space_cow(ls);
 649         if (!ls || !subs)
 650                 return isl_local_space_free(ls);
 651
 652         if (!isl_space_is_equal(ls->dim, subs->ls->dim))
 653                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 654                         "spaces don't match", return isl_local_space_free(ls));
 655         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
 656                 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
 657                         "cannot handle divs yet",
 658                         return isl_local_space_free(ls));
 659
 660         pos += isl_local_space_offset(ls, type);
 661
 662         isl_int_init(v);
 663         for (i = 0; i < ls->div->n_row; ++i) {
 664                 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
 665                         continue;
 666                 isl_int_set(v, ls->div->row[i][1 + pos]);
 667                 isl_int_set_si(ls->div->row[i][1 + pos], 0);
 668                 isl_seq_combine(ls->div->row[i] + 1,
 669                                 subs->v->el[0], ls->div->row[i] + 1,
 670                                 v, subs->v->el + 1, subs->v->size - 1);
 671                 isl_int_mul(ls->div->row[i][0],
 672                             ls->div->row[i][0], subs->v->el[0]);
 673                 normalize_div(ls, i);
 674         }
 675         isl_int_clear(v);
 676
 677         return ls;
 678 }
 679
 680 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
 681         enum isl_dim_type type)
 682 {
 683         if (!ls)
 684                 return -1;
 685         return isl_space_is_named_or_nested(ls->dim, type);
 686 }
 687
 688 __isl_give isl_local_space *isl_local_space_drop_dims(
 689         __isl_take isl_local_space *ls,
 690         enum isl_dim_type type, unsigned first, unsigned n)
 691 {
 692         isl_ctx *ctx;
 693
 694         if (!ls)
 695                 return NULL;
 696         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 697                 return ls;
 698
 699         ctx = isl_local_space_get_ctx(ls);
 700         if (first + n > isl_local_space_dim(ls, type))
 701                 isl_die(ctx, isl_error_invalid, "range out of bounds",
 702                         return isl_local_space_free(ls));
 703
 704         ls = isl_local_space_cow(ls);
 705         if (!ls)
 706                 return NULL;
 707
 708         if (type == isl_dim_div) {
 709                 ls->div = isl_mat_drop_rows(ls->div, first, n);
 710         } else {
 711                 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
 712                 if (!ls->dim)
 713                         return isl_local_space_free(ls);
 714         }
 715
 716         first += 1 + isl_local_space_offset(ls, type);
 717         ls->div = isl_mat_drop_cols(ls->div, first, n);
 718         if (!ls->div)
 719                 return isl_local_space_free(ls);
 720
 721         return ls;
 722 }
 723
 724 __isl_give isl_local_space *isl_local_space_insert_dims(
 725         __isl_take isl_local_space *ls,
 726         enum isl_dim_type type, unsigned first, unsigned n)
 727 {
 728         isl_ctx *ctx;
 729
 730         if (!ls)
 731                 return NULL;
 732         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 733                 return ls;
 734
 735         ctx = isl_local_space_get_ctx(ls);
 736         if (first > isl_local_space_dim(ls, type))
 737                 isl_die(ctx, isl_error_invalid, "position out of bounds",
 738                         return isl_local_space_free(ls));
 739
 740         ls = isl_local_space_cow(ls);
 741         if (!ls)
 742                 return NULL;
 743
 744         if (type == isl_dim_div) {
 745                 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
 746         } else {
 747                 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
 748                 if (!ls->dim)
 749                         return isl_local_space_free(ls);
 750         }
 751
 752         first += 1 + isl_local_space_offset(ls, type);
 753         ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
 754         if (!ls->div)
 755                 return isl_local_space_free(ls);
 756
 757         return ls;
 758 }
 759
 760 /* Check if the constraints pointed to by "constraint" is a div
 761  * constraint corresponding to div "div" in "ls".
 762  *
 763  * That is, if div = floor(f/m), then check if the constraint is
 764  *
 765  *              f - m d >= 0
 766  * or
 767  *              -(f-(m-1)) + m d >= 0
 768  */
 769 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
 770         isl_int *constraint, unsigned div)
 771 {
 772         unsigned pos;
 773
 774         if (!ls)
 775                 return -1;
 776
 777         if (isl_int_is_zero(ls->div->row[div][0]))
 778                 return 0;
 779
 780         pos = isl_local_space_offset(ls, isl_dim_div) + div;
 781
 782         if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
 783                 int neg;
 784                 isl_int_sub(ls->div->row[div][1],
 785                                 ls->div->row[div][1], ls->div->row[div][0]);
 786                 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 787                 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
 788                 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 789                 isl_int_add(ls->div->row[div][1],
 790                                 ls->div->row[div][1], ls->div->row[div][0]);
 791                 if (!neg)
 792                         return 0;
 793                 if (isl_seq_first_non_zero(constraint+pos+1,
 794                                             ls->div->n_row-div-1) != -1)
 795                         return 0;
 796         } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
 797                 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
 798                         return 0;
 799                 if (isl_seq_first_non_zero(constraint+pos+1,
 800                                             ls->div->n_row-div-1) != -1)
 801                         return 0;
 802         } else
 803                 return 0;
 804
 805         return 1;
 806 }
 807
 808 /*
 809  * Set active[i] to 1 if the dimension at position i is involved
 810  * in the linear expression l.
 811  */
 812 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
 813 {
 814         int i, j;
 815         isl_ctx *ctx;
 816         int *active = NULL;
 817         unsigned total;
 818         unsigned offset;
 819
 820         ctx = isl_local_space_get_ctx(ls);
 821         total = isl_local_space_dim(ls, isl_dim_all);
 822         active = isl_calloc_array(ctx, int, total);
 823         if (!active)
 824                 return NULL;
 825
 826         for (i = 0; i < total; ++i)
 827                 active[i] = !isl_int_is_zero(l[i]);
 828
 829         offset = isl_local_space_offset(ls, isl_dim_div) - 1;
 830         for (i = ls->div->n_row - 1; i >= 0; --i) {
 831                 if (!active[offset + i])
 832                         continue;
 833                 for (j = 0; j < total; ++j)
 834                         active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
 835         }
 836
 837         return active;
 838 }
 839
 840 /* Given a local space "ls" of a set, create a local space
 841  * for the lift of the set.  In particular, the result
 842  * is of the form [dim -> local[..]], with ls->div->n_row variables in the
 843  * range of the wrapped map.
 844  */
 845 __isl_give isl_local_space *isl_local_space_lift(
 846         __isl_take isl_local_space *ls)
 847 {
 848         ls = isl_local_space_cow(ls);
 849         if (!ls)
 850                 return NULL;
 851
 852         ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
 853         ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
 854         if (!ls->dim || !ls->div)
 855                 return isl_local_space_free(ls);
 856
 857         return ls;
 858 }
 859
 860 /* Construct a basic map that maps a set living in local space "ls"
 861  * to the corresponding lifted local space.
 862  */
 863 __isl_give isl_basic_map *isl_local_space_lifting(
 864         __isl_take isl_local_space *ls)
 865 {
 866         isl_basic_map *lifting;
 867         isl_basic_set *bset;
 868
 869         if (!ls)
 870                 return NULL;
 871         if (!isl_local_space_is_set(ls))
 872                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 873                         "lifting only defined on set spaces",
 874                         return isl_local_space_free(ls));
 875
 876         bset = isl_basic_set_from_local_space(ls);
 877         lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
 878         lifting = isl_basic_map_domain_map(lifting);
 879         lifting = isl_basic_map_reverse(lifting);
 880
 881         return lifting;
 882 }