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