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 __isl_give isl_local_space *isl_local_space_range(
 536         __isl_take isl_local_space *ls)
 537 {
 538         ls = isl_local_space_drop_dims(ls, isl_dim_in,
 539                                         0, isl_local_space_dim(ls, isl_dim_in));
 540         ls = isl_local_space_cow(ls);
 541         if (!ls)
 542                 return NULL;
 543
 544         ls->dim = isl_space_range(ls->dim);
 545         if (!ls->dim)
 546                 return isl_local_space_free(ls);
 547         return ls;
 548 }
 549
 550 /* Construct a local space for a map that has the given local
 551  * space as domain and that has a zero-dimensional range.
 552  */
 553 __isl_give isl_local_space *isl_local_space_from_domain(
 554         __isl_take isl_local_space *ls)
 555 {
 556         ls = isl_local_space_cow(ls);
 557         if (!ls)
 558                 return NULL;
 559         ls->dim = isl_space_from_domain(ls->dim);
 560         if (!ls->dim)
 561                 return isl_local_space_free(ls);
 562         return ls;
 563 }
 564
 565 __isl_give isl_local_space *isl_local_space_add_dims(
 566         __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
 567 {
 568         int pos;
 569
 570         if (!ls)
 571                 return NULL;
 572         pos = isl_local_space_dim(ls, type);
 573         return isl_local_space_insert_dims(ls, type, pos, n);
 574 }
 575
 576 /* Remove common factor of non-constant terms and denominator.
 577  */
 578 static void normalize_div(__isl_keep isl_local_space *ls, int div)
 579 {
 580         isl_ctx *ctx = ls->div->ctx;
 581         unsigned total = ls->div->n_col - 2;
 582
 583         isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
 584         isl_int_gcd(ctx->normalize_gcd,
 585                     ctx->normalize_gcd, ls->div->row[div][0]);
 586         if (isl_int_is_one(ctx->normalize_gcd))
 587                 return;
 588
 589         isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
 590                             ctx->normalize_gcd, total);
 591         isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
 592                             ctx->normalize_gcd);
 593         isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
 594                             ctx->normalize_gcd);
 595 }
 596
 597 /* Exploit the equalities in "eq" to simplify the expressions of
 598  * the integer divisions in "ls".
 599  * The integer divisions in "ls" are assumed to appear as regular
 600  * dimensions in "eq".
 601  */
 602 __isl_give isl_local_space *isl_local_space_substitute_equalities(
 603         __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
 604 {
 605         int i, j, k;
 606         unsigned total;
 607         unsigned n_div;
 608
 609         ls = isl_local_space_cow(ls);
 610         if (!ls || !eq)
 611                 goto error;
 612
 613         total = isl_space_dim(eq->dim, isl_dim_all);
 614         if (isl_local_space_dim(ls, isl_dim_all) != total)
 615                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 616                         "dimensions don't match", goto error);
 617         total++;
 618         n_div = eq->n_div;
 619         for (i = 0; i < eq->n_eq; ++i) {
 620                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 621                 if (j < 0 || j == 0 || j >= total)
 622                         continue;
 623
 624                 for (k = 0; k < ls->div->n_row; ++k) {
 625                         if (isl_int_is_zero(ls->div->row[k][1 + j]))
 626                                 continue;
 627                         isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
 628                                         &ls->div->row[k][0]);
 629                         normalize_div(ls, k);
 630                 }
 631         }
 632
 633         isl_basic_set_free(eq);
 634         return ls;
 635 error:
 636         isl_basic_set_free(eq);
 637         isl_local_space_free(ls);
 638         return NULL;
 639 }
 640
 641 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
 642  * of "ls".
 643  *
 644  * Let i be the dimension to replace and let "subs" be of the form
 645  *
 646  *      f/d
 647  *
 648  * Any integer division with a non-zero coefficient for i,
 649  *
 650  *      floor((a i + g)/m)
 651  *
 652  * is replaced by
 653  *
 654  *      floor((a f + d g)/(m d))
 655  */
 656 __isl_give isl_local_space *isl_local_space_substitute(
 657         __isl_take isl_local_space *ls,
 658         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
 659 {
 660         int i;
 661         isl_int v;
 662
 663         ls = isl_local_space_cow(ls);
 664         if (!ls || !subs)
 665                 return isl_local_space_free(ls);
 666
 667         if (!isl_space_is_equal(ls->dim, subs->ls->dim))
 668                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 669                         "spaces don't match", return isl_local_space_free(ls));
 670         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
 671                 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
 672                         "cannot handle divs yet",
 673                         return isl_local_space_free(ls));
 674
 675         pos += isl_local_space_offset(ls, type);
 676
 677         isl_int_init(v);
 678         for (i = 0; i < ls->div->n_row; ++i) {
 679                 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
 680                         continue;
 681                 isl_int_set(v, ls->div->row[i][1 + pos]);
 682                 isl_int_set_si(ls->div->row[i][1 + pos], 0);
 683                 isl_seq_combine(ls->div->row[i] + 1,
 684                                 subs->v->el[0], ls->div->row[i] + 1,
 685                                 v, subs->v->el + 1, subs->v->size - 1);
 686                 isl_int_mul(ls->div->row[i][0],
 687                             ls->div->row[i][0], subs->v->el[0]);
 688                 normalize_div(ls, i);
 689         }
 690         isl_int_clear(v);
 691
 692         return ls;
 693 }
 694
 695 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
 696         enum isl_dim_type type)
 697 {
 698         if (!ls)
 699                 return -1;
 700         return isl_space_is_named_or_nested(ls->dim, type);
 701 }
 702
 703 __isl_give isl_local_space *isl_local_space_drop_dims(
 704         __isl_take isl_local_space *ls,
 705         enum isl_dim_type type, unsigned first, unsigned n)
 706 {
 707         isl_ctx *ctx;
 708
 709         if (!ls)
 710                 return NULL;
 711         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 712                 return ls;
 713
 714         ctx = isl_local_space_get_ctx(ls);
 715         if (first + n > isl_local_space_dim(ls, type))
 716                 isl_die(ctx, isl_error_invalid, "range out of bounds",
 717                         return isl_local_space_free(ls));
 718
 719         ls = isl_local_space_cow(ls);
 720         if (!ls)
 721                 return NULL;
 722
 723         if (type == isl_dim_div) {
 724                 ls->div = isl_mat_drop_rows(ls->div, first, n);
 725         } else {
 726                 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
 727                 if (!ls->dim)
 728                         return isl_local_space_free(ls);
 729         }
 730
 731         first += 1 + isl_local_space_offset(ls, type);
 732         ls->div = isl_mat_drop_cols(ls->div, first, n);
 733         if (!ls->div)
 734                 return isl_local_space_free(ls);
 735
 736         return ls;
 737 }
 738
 739 __isl_give isl_local_space *isl_local_space_insert_dims(
 740         __isl_take isl_local_space *ls,
 741         enum isl_dim_type type, unsigned first, unsigned n)
 742 {
 743         isl_ctx *ctx;
 744
 745         if (!ls)
 746                 return NULL;
 747         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 748                 return ls;
 749
 750         ctx = isl_local_space_get_ctx(ls);
 751         if (first > isl_local_space_dim(ls, type))
 752                 isl_die(ctx, isl_error_invalid, "position out of bounds",
 753                         return isl_local_space_free(ls));
 754
 755         ls = isl_local_space_cow(ls);
 756         if (!ls)
 757                 return NULL;
 758
 759         if (type == isl_dim_div) {
 760                 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
 761         } else {
 762                 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
 763                 if (!ls->dim)
 764                         return isl_local_space_free(ls);
 765         }
 766
 767         first += 1 + isl_local_space_offset(ls, type);
 768         ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
 769         if (!ls->div)
 770                 return isl_local_space_free(ls);
 771
 772         return ls;
 773 }
 774
 775 /* Check if the constraints pointed to by "constraint" is a div
 776  * constraint corresponding to div "div" in "ls".
 777  *
 778  * That is, if div = floor(f/m), then check if the constraint is
 779  *
 780  *              f - m d >= 0
 781  * or
 782  *              -(f-(m-1)) + m d >= 0
 783  */
 784 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
 785         isl_int *constraint, unsigned div)
 786 {
 787         unsigned pos;
 788
 789         if (!ls)
 790                 return -1;
 791
 792         if (isl_int_is_zero(ls->div->row[div][0]))
 793                 return 0;
 794
 795         pos = isl_local_space_offset(ls, isl_dim_div) + div;
 796
 797         if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
 798                 int neg;
 799                 isl_int_sub(ls->div->row[div][1],
 800                                 ls->div->row[div][1], ls->div->row[div][0]);
 801                 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 802                 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
 803                 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 804                 isl_int_add(ls->div->row[div][1],
 805                                 ls->div->row[div][1], ls->div->row[div][0]);
 806                 if (!neg)
 807                         return 0;
 808                 if (isl_seq_first_non_zero(constraint+pos+1,
 809                                             ls->div->n_row-div-1) != -1)
 810                         return 0;
 811         } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
 812                 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
 813                         return 0;
 814                 if (isl_seq_first_non_zero(constraint+pos+1,
 815                                             ls->div->n_row-div-1) != -1)
 816                         return 0;
 817         } else
 818                 return 0;
 819
 820         return 1;
 821 }
 822
 823 /*
 824  * Set active[i] to 1 if the dimension at position i is involved
 825  * in the linear expression l.
 826  */
 827 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
 828 {
 829         int i, j;
 830         isl_ctx *ctx;
 831         int *active = NULL;
 832         unsigned total;
 833         unsigned offset;
 834
 835         ctx = isl_local_space_get_ctx(ls);
 836         total = isl_local_space_dim(ls, isl_dim_all);
 837         active = isl_calloc_array(ctx, int, total);
 838         if (!active)
 839                 return NULL;
 840
 841         for (i = 0; i < total; ++i)
 842                 active[i] = !isl_int_is_zero(l[i]);
 843
 844         offset = isl_local_space_offset(ls, isl_dim_div) - 1;
 845         for (i = ls->div->n_row - 1; i >= 0; --i) {
 846                 if (!active[offset + i])
 847                         continue;
 848                 for (j = 0; j < total; ++j)
 849                         active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
 850         }
 851
 852         return active;
 853 }
 854
 855 /* Given a local space "ls" of a set, create a local space
 856  * for the lift of the set.  In particular, the result
 857  * is of the form [dim -> local[..]], with ls->div->n_row variables in the
 858  * range of the wrapped map.
 859  */
 860 __isl_give isl_local_space *isl_local_space_lift(
 861         __isl_take isl_local_space *ls)
 862 {
 863         ls = isl_local_space_cow(ls);
 864         if (!ls)
 865                 return NULL;
 866
 867         ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
 868         ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
 869         if (!ls->dim || !ls->div)
 870                 return isl_local_space_free(ls);
 871
 872         return ls;
 873 }
 874
 875 /* Construct a basic map that maps a set living in local space "ls"
 876  * to the corresponding lifted local space.
 877  */
 878 __isl_give isl_basic_map *isl_local_space_lifting(
 879         __isl_take isl_local_space *ls)
 880 {
 881         isl_basic_map *lifting;
 882         isl_basic_set *bset;
 883
 884         if (!ls)
 885                 return NULL;
 886         if (!isl_local_space_is_set(ls))
 887                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 888                         "lifting only defined on set spaces",
 889                         return isl_local_space_free(ls));
 890
 891         bset = isl_basic_set_from_local_space(ls);
 892         lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
 893         lifting = isl_basic_map_domain_map(lifting);
 894         lifting = isl_basic_map_reverse(lifting);
 895
 896         return lifting;
 897 }