isl_local_space.c

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