isl_map.c

   1 #include <string.h>
   2 #include <strings.h>
   3 #include "isl_ctx.h"
   4 #include "isl_blk.h"
   5 #include "isl_dim.h"
   6 #include "isl_equalities.h"
   7 #include "isl_list.h"
   8 #include "isl_lp.h"
   9 #include "isl_seq.h"
  10 #include "isl_set.h"
  11 #include "isl_map.h"
  12 #include "isl_map_private.h"
  13 #include "isl_map_piplib.h"
  14 #include "isl_sample.h"
  15 #include "isl_vec.h"
  16
  17 /* Maps dst positions to src positions */
  18 struct isl_dim_map {
  19         unsigned len;
  20         int pos[1];
  21 };
  22
  23 static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
  24 {
  25         int i;
  26         struct isl_dim_map *dim_map;
  27         dim_map = isl_alloc(ctx, struct isl_dim_map,
  28                                 sizeof(struct isl_dim_map) + len * sizeof(int));
  29         if (!dim_map)
  30                 return NULL;
  31         dim_map->len = 1 + len;
  32         dim_map->pos[0] = 0;
  33         for (i = 0; i < len; ++i)
  34                 dim_map->pos[1 + i] = -1;
  35         return dim_map;
  36 }
  37
  38 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
  39 {
  40         switch (type) {
  41         case isl_dim_param:     return dim->nparam;
  42         case isl_dim_in:        return dim->n_in;
  43         case isl_dim_out:       return dim->n_out;
  44         }
  45 }
  46
  47 static unsigned pos(struct isl_dim *dim, enum isl_dim_type type)
  48 {
  49         switch (type) {
  50         case isl_dim_param:     return 1;
  51         case isl_dim_in:        return 1 + dim->nparam;
  52         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  53         }
  54 }
  55
  56 static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
  57                 enum isl_dim_type type, unsigned dst_pos)
  58 {
  59         int i;
  60         unsigned src_pos;
  61
  62         if (!dim_map || !dim)
  63                 return;
  64
  65         src_pos = pos(dim, type);
  66         for (i = 0; i < n(dim, type); ++i)
  67                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
  68 }
  69
  70 static void isl_dim_map_div(struct isl_dim_map *dim_map,
  71                 struct isl_basic_map *bmap, unsigned dst_pos)
  72 {
  73         int i;
  74         unsigned src_pos;
  75
  76         if (!dim_map || !bmap)
  77                 return;
  78
  79         src_pos = 1 + isl_dim_total(bmap->dim);
  80         for (i = 0; i < bmap->n_div; ++i)
  81                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
  82 }
  83
  84 static void isl_dim_map_dump(struct isl_dim_map *dim_map)
  85 {
  86         int i;
  87
  88         for (i = 0; i < dim_map->len; ++i)
  89                 fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
  90         fprintf(stderr, "\n");
  91 }
  92
  93 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
  94 {
  95         return bset->dim->n_out;
  96 }
  97
  98 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
  99 {
 100         return bset->dim->nparam;
 101 }
 102
 103 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 104 {
 105         return isl_dim_total(bset->dim) + bset->n_div;
 106 }
 107
 108 unsigned isl_set_n_dim(const struct isl_set *set)
 109 {
 110         return set->dim->n_out;
 111 }
 112
 113 unsigned isl_set_n_param(const struct isl_set *set)
 114 {
 115         return set->dim->nparam;
 116 }
 117
 118 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
 119 {
 120         return bmap->dim->n_in;
 121 }
 122
 123 unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
 124 {
 125         return bmap->dim->n_out;
 126 }
 127
 128 unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
 129 {
 130         return bmap->dim->nparam;
 131 }
 132
 133 unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
 134 {
 135         return bmap->n_div;
 136 }
 137
 138 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
 139 {
 140         return isl_dim_total(bmap->dim) + bmap->n_div;
 141 }
 142
 143 unsigned isl_map_n_in(const struct isl_map *map)
 144 {
 145         return map->dim->n_in;
 146 }
 147
 148 unsigned isl_map_n_out(const struct isl_map *map)
 149 {
 150         return map->dim->n_out;
 151 }
 152
 153 unsigned isl_map_n_param(const struct isl_map *map)
 154 {
 155         return map->dim->nparam;
 156 }
 157
 158 int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
 159 {
 160         return map->dim->n_in == set->dim->n_out &&
 161                map->dim->nparam == set->dim->nparam;
 162 }
 163
 164 int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
 165                 struct isl_basic_set *bset)
 166 {
 167         return bmap->dim->n_in == bset->dim->n_out &&
 168                bmap->dim->nparam == bset->dim->nparam;
 169 }
 170
 171 int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
 172                 struct isl_basic_set *bset)
 173 {
 174         return bmap->dim->n_out == bset->dim->n_out &&
 175                bmap->dim->nparam == bset->dim->nparam;
 176 }
 177
 178 static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 179                 struct isl_basic_map *bmap, unsigned extra,
 180                 unsigned n_eq, unsigned n_ineq)
 181 {
 182         int i;
 183         size_t row_size = 1 + isl_dim_total(bmap->dim) + extra;
 184
 185         bmap->block = isl_blk_alloc(ctx, (n_eq + n_ineq) * row_size);
 186         if (isl_blk_is_error(bmap->block)) {
 187                 free(bmap);
 188                 return NULL;
 189         }
 190
 191         bmap->eq = isl_alloc_array(ctx, isl_int *, n_eq + n_ineq);
 192         if (!bmap->eq) {
 193                 isl_blk_free(ctx, bmap->block);
 194                 free(bmap);
 195                 return NULL;
 196         }
 197
 198         if (extra == 0) {
 199                 bmap->block2 = isl_blk_empty();
 200                 bmap->div = NULL;
 201         } else {
 202                 bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
 203                 if (isl_blk_is_error(bmap->block2)) {
 204                         free(bmap->eq);
 205                         isl_blk_free(ctx, bmap->block);
 206                         free(bmap);
 207                         return NULL;
 208                 }
 209
 210                 bmap->div = isl_alloc_array(ctx, isl_int *, extra);
 211                 if (!bmap->div) {
 212                         isl_blk_free(ctx, bmap->block2);
 213                         free(bmap->eq);
 214                         isl_blk_free(ctx, bmap->block);
 215                         free(bmap);
 216                         return NULL;
 217                 }
 218         }
 219
 220         for (i = 0; i < n_eq + n_ineq; ++i)
 221                 bmap->eq[i] = bmap->block.data + i * row_size;
 222
 223         for (i = 0; i < extra; ++i)
 224                 bmap->div[i] = bmap->block2.data + i * (1 + row_size);
 225
 226         bmap->ctx = ctx;
 227         isl_ctx_ref(ctx);
 228         bmap->ref = 1;
 229         bmap->flags = 0;
 230         bmap->c_size = n_eq + n_ineq;
 231         bmap->ineq = bmap->eq + n_eq;
 232         bmap->extra = extra;
 233         bmap->n_eq = 0;
 234         bmap->n_ineq = 0;
 235         bmap->n_div = 0;
 236         bmap->sample = NULL;
 237
 238         return bmap;
 239 error:
 240         isl_basic_map_free(bmap);
 241         return NULL;
 242 }
 243
 244 struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
 245                 unsigned nparam, unsigned dim, unsigned extra,
 246                 unsigned n_eq, unsigned n_ineq)
 247 {
 248         struct isl_basic_map *bmap;
 249         bmap = isl_basic_map_alloc(ctx, nparam, 0, dim, extra, n_eq, n_ineq);
 250         return (struct isl_basic_set *)bmap;
 251 }
 252
 253 struct isl_basic_set *isl_basic_set_alloc_dim(struct isl_dim *dim,
 254                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 255 {
 256         struct isl_basic_map *bmap;
 257         if (!dim)
 258                 return NULL;
 259         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
 260         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 261         return (struct isl_basic_set *)bmap;
 262 }
 263
 264 struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_dim *dim,
 265                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 266 {
 267         struct isl_basic_map *bmap;
 268
 269         if (!dim)
 270                 return NULL;
 271         bmap = isl_alloc_type(dim->ctx, struct isl_basic_map);
 272         if (!bmap)
 273                 goto error;
 274         bmap->dim = dim;
 275
 276         return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
 277 error:
 278         isl_dim_free(dim);
 279         return NULL;
 280 }
 281
 282 struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
 283                 unsigned nparam, unsigned in, unsigned out, unsigned extra,
 284                 unsigned n_eq, unsigned n_ineq)
 285 {
 286         struct isl_basic_map *bmap;
 287         struct isl_dim *dim;
 288
 289         dim = isl_dim_alloc(ctx, nparam, in, out);
 290         if (!dim)
 291                 return NULL;
 292
 293         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 294         return bmap;
 295 }
 296
 297 static void dup_constraints(
 298                 struct isl_basic_map *dst, struct isl_basic_map *src)
 299 {
 300         int i;
 301         unsigned total = isl_basic_map_total_dim(src);
 302
 303         for (i = 0; i < src->n_eq; ++i) {
 304                 int j = isl_basic_map_alloc_equality(dst);
 305                 isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
 306         }
 307
 308         for (i = 0; i < src->n_ineq; ++i) {
 309                 int j = isl_basic_map_alloc_inequality(dst);
 310                 isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
 311         }
 312
 313         for (i = 0; i < src->n_div; ++i) {
 314                 int j = isl_basic_map_alloc_div(dst);
 315                 isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
 316         }
 317         F_SET(dst, ISL_BASIC_SET_FINAL);
 318 }
 319
 320 struct isl_basic_map *isl_basic_map_dup(struct isl_basic_map *bmap)
 321 {
 322         struct isl_basic_map *dup;
 323
 324         if (!bmap)
 325                 return NULL;
 326         dup = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
 327                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
 328         if (!dup)
 329                 return NULL;
 330         dup->flags = bmap->flags;
 331         dup_constraints(dup, bmap);
 332         dup->sample = isl_vec_copy(bmap->ctx, bmap->sample);
 333         return dup;
 334 }
 335
 336 struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
 337 {
 338         struct isl_basic_map *dup;
 339
 340         dup = isl_basic_map_dup((struct isl_basic_map *)bset);
 341         return (struct isl_basic_set *)dup;
 342 }
 343
 344 struct isl_basic_set *isl_basic_set_copy(struct isl_basic_set *bset)
 345 {
 346         if (!bset)
 347                 return NULL;
 348
 349         if (F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
 350                 bset->ref++;
 351                 return bset;
 352         }
 353         return isl_basic_set_dup(bset);
 354 }
 355
 356 struct isl_set *isl_set_copy(struct isl_set *set)
 357 {
 358         if (!set)
 359                 return NULL;
 360
 361         set->ref++;
 362         return set;
 363 }
 364
 365 struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
 366 {
 367         if (!bmap)
 368                 return NULL;
 369
 370         if (F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
 371                 bmap->ref++;
 372                 return bmap;
 373         }
 374         return isl_basic_map_dup(bmap);
 375 }
 376
 377 struct isl_map *isl_map_copy(struct isl_map *map)
 378 {
 379         if (!map)
 380                 return NULL;
 381
 382         map->ref++;
 383         return map;
 384 }
 385
 386 void isl_basic_map_free(struct isl_basic_map *bmap)
 387 {
 388         if (!bmap)
 389                 return;
 390
 391         if (--bmap->ref > 0)
 392                 return;
 393
 394         isl_ctx_deref(bmap->ctx);
 395         free(bmap->div);
 396         isl_blk_free(bmap->ctx, bmap->block2);
 397         free(bmap->eq);
 398         isl_blk_free(bmap->ctx, bmap->block);
 399         isl_vec_free(bmap->ctx, bmap->sample);
 400         isl_dim_free(bmap->dim);
 401         free(bmap);
 402 }
 403
 404 void isl_basic_set_free(struct isl_basic_set *bset)
 405 {
 406         isl_basic_map_free((struct isl_basic_map *)bset);
 407 }
 408
 409 int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
 410 {
 411         struct isl_ctx *ctx;
 412         if (!bmap)
 413                 return -1;
 414         ctx = bmap->ctx;
 415         isl_assert(ctx, bmap->n_eq + bmap->n_ineq < bmap->c_size, return -1);
 416         isl_assert(ctx, bmap->eq + bmap->n_eq <= bmap->ineq, return -1);
 417         if (bmap->eq + bmap->n_eq == bmap->ineq) {
 418                 isl_int *t;
 419                 int j = isl_basic_map_alloc_inequality(bmap);
 420                 if (j < 0)
 421                         return -1;
 422                 t = bmap->ineq[0];
 423                 bmap->ineq[0] = bmap->ineq[j];
 424                 bmap->ineq[j] = t;
 425                 bmap->n_ineq--;
 426                 bmap->ineq++;
 427         } else
 428                 isl_seq_clr(bmap->eq[bmap->n_eq] +
 429                       1 + isl_basic_map_total_dim(bmap),
 430                       bmap->extra - bmap->n_div);
 431         return bmap->n_eq++;
 432 }
 433
 434 int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
 435 {
 436         return isl_basic_map_alloc_equality((struct isl_basic_map *)bset);
 437 }
 438
 439 int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
 440 {
 441         if (!bmap)
 442                 return -1;
 443         isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
 444         bmap->n_eq -= n;
 445         return 0;
 446 }
 447
 448 int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
 449 {
 450         isl_int *t;
 451         if (!bmap)
 452                 return -1;
 453         isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
 454
 455         if (pos != bmap->n_eq - 1) {
 456                 t = bmap->eq[pos];
 457                 bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
 458                 bmap->eq[bmap->n_eq - 1] = t;
 459         }
 460         bmap->n_eq--;
 461         return 0;
 462 }
 463
 464 int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos)
 465 {
 466         return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos);
 467 }
 468
 469 void isl_basic_map_inequality_to_equality(
 470                 struct isl_basic_map *bmap, unsigned pos)
 471 {
 472         isl_int *t;
 473
 474         t = bmap->ineq[pos];
 475         bmap->ineq[pos] = bmap->ineq[0];
 476         bmap->ineq[0] = bmap->eq[bmap->n_eq];
 477         bmap->eq[bmap->n_eq] = t;
 478         bmap->n_eq++;
 479         bmap->n_ineq--;
 480         bmap->ineq++;
 481         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 482 }
 483
 484 int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap)
 485 {
 486         struct isl_ctx *ctx;
 487         if (!bmap)
 488                 return -1;
 489         ctx = bmap->ctx;
 490         isl_assert(ctx, (bmap->ineq - bmap->eq) + bmap->n_ineq < bmap->c_size,
 491                         return -1);
 492         F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
 493         F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 494         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 495         isl_seq_clr(bmap->ineq[bmap->n_ineq] +
 496                       1 + isl_basic_map_total_dim(bmap),
 497                       bmap->extra - bmap->n_div);
 498         return bmap->n_ineq++;
 499 }
 500
 501 int isl_basic_set_alloc_inequality(struct isl_basic_set *bset)
 502 {
 503         return isl_basic_map_alloc_inequality((struct isl_basic_map *)bset);
 504 }
 505
 506 int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
 507 {
 508         if (!bmap)
 509                 return -1;
 510         isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
 511         bmap->n_ineq -= n;
 512         return 0;
 513 }
 514
 515 int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
 516 {
 517         return isl_basic_map_free_inequality((struct isl_basic_map *)bset, n);
 518 }
 519
 520 int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
 521 {
 522         isl_int *t;
 523         if (!bmap)
 524                 return -1;
 525         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
 526
 527         if (pos != bmap->n_ineq - 1) {
 528                 t = bmap->ineq[pos];
 529                 bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 530                 bmap->ineq[bmap->n_ineq - 1] = t;
 531                 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 532         }
 533         bmap->n_ineq--;
 534         return 0;
 535 }
 536
 537 int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
 538 {
 539         return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos);
 540 }
 541
 542 int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
 543 {
 544         if (!bmap)
 545                 return -1;
 546         isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
 547         isl_seq_clr(bmap->div[bmap->n_div] +
 548                       1 + 1 + isl_basic_map_total_dim(bmap),
 549                       bmap->extra - bmap->n_div);
 550         return bmap->n_div++;
 551 }
 552
 553 int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
 554 {
 555         if (!bmap)
 556                 return -1;
 557         isl_assert(bmap->ctx, n <= bmap->n_div, return -1);
 558         bmap->n_div -= n;
 559         return 0;
 560 }
 561
 562 /* Copy constraint from src to dst, putting the vars of src at offset
 563  * dim_off in dst and the divs of src at offset div_off in dst.
 564  * If both sets are actually map, then dim_off applies to the input
 565  * variables.
 566  */
 567 static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
 568                             struct isl_basic_map *src_map, isl_int *src,
 569                             unsigned in_off, unsigned out_off, unsigned div_off)
 570 {
 571         unsigned src_nparam = isl_basic_map_n_param(src_map);
 572         unsigned dst_nparam = isl_basic_map_n_param(dst_map);
 573         unsigned src_in = isl_basic_map_n_in(src_map);
 574         unsigned dst_in = isl_basic_map_n_in(dst_map);
 575         unsigned src_out = isl_basic_map_n_out(src_map);
 576         unsigned dst_out = isl_basic_map_n_out(dst_map);
 577         isl_int_set(dst[0], src[0]);
 578         isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
 579         if (dst_nparam > src_nparam)
 580                 isl_seq_clr(dst+1+src_nparam,
 581                                 dst_nparam - src_nparam);
 582         isl_seq_clr(dst+1+dst_nparam, in_off);
 583         isl_seq_cpy(dst+1+dst_nparam+in_off,
 584                     src+1+src_nparam,
 585                     isl_min(dst_in-in_off, src_in));
 586         if (dst_in-in_off > src_in)
 587                 isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
 588                                 dst_in - in_off - src_in);
 589         isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
 590         isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
 591                     src+1+src_nparam+src_in,
 592                     isl_min(dst_out-out_off, src_out));
 593         if (dst_out-out_off > src_out)
 594                 isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
 595                                 dst_out - out_off - src_out);
 596         isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
 597         isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
 598                     src+1+src_nparam+src_in+src_out,
 599                     isl_min(dst_map->extra-div_off, src_map->n_div));
 600         if (dst_map->n_div-div_off > src_map->n_div)
 601                 isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
 602                                 div_off+src_map->n_div,
 603                                 dst_map->n_div - div_off - src_map->n_div);
 604 }
 605
 606 static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
 607                      struct isl_basic_map *src_map, isl_int *src,
 608                      unsigned in_off, unsigned out_off, unsigned div_off)
 609 {
 610         isl_int_set(dst[0], src[0]);
 611         copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
 612 }
 613
 614 static struct isl_basic_map *add_constraints(struct isl_basic_map *bmap1,
 615                 struct isl_basic_map *bmap2, unsigned i_pos, unsigned o_pos)
 616 {
 617         int i;
 618         unsigned div_off;
 619
 620         if (!bmap1 || !bmap2)
 621                 goto error;
 622
 623         div_off = bmap1->n_div;
 624
 625         for (i = 0; i < bmap2->n_eq; ++i) {
 626                 int i1 = isl_basic_map_alloc_equality(bmap1);
 627                 if (i1 < 0)
 628                         goto error;
 629                 copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
 630                                 i_pos, o_pos, div_off);
 631         }
 632
 633         for (i = 0; i < bmap2->n_ineq; ++i) {
 634                 int i1 = isl_basic_map_alloc_inequality(bmap1);
 635                 if (i1 < 0)
 636                         goto error;
 637                 copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
 638                                 i_pos, o_pos, div_off);
 639         }
 640
 641         for (i = 0; i < bmap2->n_div; ++i) {
 642                 int i1 = isl_basic_map_alloc_div(bmap1);
 643                 if (i1 < 0)
 644                         goto error;
 645                 copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
 646                          i_pos, o_pos, div_off);
 647         }
 648
 649         isl_basic_map_free(bmap2);
 650
 651         return bmap1;
 652
 653 error:
 654         isl_basic_map_free(bmap1);
 655         isl_basic_map_free(bmap2);
 656         return NULL;
 657 }
 658
 659 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
 660                                         struct isl_dim_map *dim_map)
 661 {
 662         int i;
 663
 664         for (i = 0; i < dim_map->len; ++i) {
 665                 if (dim_map->pos[i] < 0)
 666                         isl_int_set_si(dst[i], 0);
 667                 else
 668                         isl_int_set(dst[i], src[dim_map->pos[i]]);
 669         }
 670 }
 671
 672 static void copy_div_dim_map(isl_int *dst, isl_int *src,
 673                                         struct isl_dim_map *dim_map)
 674 {
 675         isl_int_set(dst[0], src[0]);
 676         copy_constraint_dim_map(dst+1, src+1, dim_map);
 677 }
 678
 679 static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst,
 680                 struct isl_basic_map *src, struct isl_dim_map *dim_map)
 681 {
 682         int i;
 683
 684         if (!src || !dst || !dim_map)
 685                 goto error;
 686
 687         for (i = 0; i < src->n_eq; ++i) {
 688                 int i1 = isl_basic_map_alloc_equality(dst);
 689                 if (i1 < 0)
 690                         goto error;
 691                 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
 692         }
 693
 694         for (i = 0; i < src->n_ineq; ++i) {
 695                 int i1 = isl_basic_map_alloc_inequality(dst);
 696                 if (i1 < 0)
 697                         goto error;
 698                 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
 699         }
 700
 701         for (i = 0; i < src->n_div; ++i) {
 702                 int i1 = isl_basic_map_alloc_div(dst);
 703                 if (i1 < 0)
 704                         goto error;
 705                 copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
 706         }
 707
 708         free(dim_map);
 709         isl_basic_map_free(src);
 710
 711         return dst;
 712 error:
 713         free(dim_map);
 714         isl_basic_map_free(src);
 715         isl_basic_map_free(dst);
 716         return NULL;
 717 }
 718
 719 static struct isl_basic_set *set_add_constraints(struct isl_basic_set *bset1,
 720                 struct isl_basic_set *bset2, unsigned pos)
 721 {
 722         return (struct isl_basic_set *)
 723                 add_constraints((struct isl_basic_map *)bset1,
 724                                 (struct isl_basic_map *)bset2, 0, pos);
 725 }
 726
 727 struct isl_basic_map *isl_basic_map_extend_dim(struct isl_basic_map *base,
 728                 struct isl_dim *dim, unsigned extra,
 729                 unsigned n_eq, unsigned n_ineq)
 730 {
 731         struct isl_basic_map *ext;
 732         unsigned flags;
 733         int dims_ok;
 734
 735         if (!dim)
 736                 goto error;
 737
 738         base = isl_basic_map_cow(base);
 739         if (!base)
 740                 goto error;
 741
 742         dims_ok = isl_dim_equal(base->dim, dim) &&
 743                   base->extra >= base->n_div + extra;
 744
 745         if (dims_ok && n_eq == 0 && n_ineq == 0) {
 746                 isl_dim_free(dim);
 747                 return base;
 748         }
 749
 750         isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
 751         isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
 752         isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
 753         extra += base->extra;
 754         n_eq += base->n_eq;
 755         n_ineq += base->n_ineq;
 756
 757         ext = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 758         dim = NULL;
 759         if (!ext)
 760                 goto error;
 761
 762         flags = base->flags;
 763         ext = add_constraints(ext, base, 0, 0);
 764         if (ext) {
 765                 ext->flags = flags;
 766                 F_CLR(ext, ISL_BASIC_SET_FINAL);
 767         }
 768
 769         return ext;
 770
 771 error:
 772         isl_dim_free(dim);
 773         isl_basic_map_free(base);
 774         return NULL;
 775 }
 776
 777 struct isl_basic_map *isl_basic_map_extend_constraints(
 778                 struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
 779 {
 780         if (!base)
 781                 return NULL;
 782         return isl_basic_map_extend_dim(base, isl_dim_copy(base->dim),
 783                                         0, n_eq, n_ineq);
 784 }
 785
 786 struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
 787                 unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
 788                 unsigned n_eq, unsigned n_ineq)
 789 {
 790         struct isl_basic_map *bmap;
 791         struct isl_dim *dim;
 792
 793         if (!base)
 794                 return NULL;
 795         dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out);
 796         if (!dim)
 797                 return NULL;
 798
 799         bmap = isl_basic_map_extend_dim(base, dim, extra, n_eq, n_ineq);
 800         return bmap;
 801 }
 802
 803 struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
 804                 unsigned nparam, unsigned dim, unsigned extra,
 805                 unsigned n_eq, unsigned n_ineq)
 806 {
 807         return (struct isl_basic_set *)
 808                 isl_basic_map_extend((struct isl_basic_map *)base,
 809                                         nparam, 0, dim, extra, n_eq, n_ineq);
 810 }
 811
 812 struct isl_basic_set *isl_basic_set_extend_constraints(
 813                 struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
 814 {
 815         return (struct isl_basic_set *)
 816                 isl_basic_map_extend_constraints((struct isl_basic_map *)base,
 817                                                     n_eq, n_ineq);
 818 }
 819
 820 struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset)
 821 {
 822         return (struct isl_basic_set *)
 823                 isl_basic_map_cow((struct isl_basic_map *)bset);
 824 }
 825
 826 struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
 827 {
 828         if (!bmap)
 829                 return NULL;
 830
 831         if (bmap->ref > 1) {
 832                 bmap->ref--;
 833                 bmap = isl_basic_map_dup(bmap);
 834         }
 835         F_CLR(bmap, ISL_BASIC_SET_FINAL);
 836         return bmap;
 837 }
 838
 839 struct isl_set *isl_set_cow(struct isl_set *set)
 840 {
 841         if (!set)
 842                 return NULL;
 843
 844         if (set->ref == 1)
 845                 return set;
 846         set->ref--;
 847         return isl_set_dup(set);
 848 }
 849
 850 struct isl_map *isl_map_cow(struct isl_map *map)
 851 {
 852         if (!map)
 853                 return NULL;
 854
 855         if (map->ref == 1)
 856                 return map;
 857         map->ref--;
 858         return isl_map_dup(map);
 859 }
 860
 861 static void swap_vars(struct isl_blk blk, isl_int *a,
 862                         unsigned a_len, unsigned b_len)
 863 {
 864         isl_seq_cpy(blk.data, a+a_len, b_len);
 865         isl_seq_cpy(blk.data+b_len, a, a_len);
 866         isl_seq_cpy(a, blk.data, b_len+a_len);
 867 }
 868
 869 struct isl_basic_set *isl_basic_set_swap_vars(
 870                 struct isl_basic_set *bset, unsigned n)
 871 {
 872         int i;
 873         struct isl_blk blk;
 874         unsigned dim;
 875         unsigned nparam;
 876
 877         if (!bset)
 878                 goto error;
 879
 880         nparam = isl_basic_set_n_param(bset);
 881         dim = isl_basic_set_n_dim(bset);
 882         isl_assert(bset->ctx, n <= dim, goto error);
 883
 884         if (n == dim)
 885                 return bset;
 886
 887         bset = isl_basic_set_cow(bset);
 888         if (!bset)
 889                 return NULL;
 890
 891         blk = isl_blk_alloc(bset->ctx, dim);
 892         if (isl_blk_is_error(blk))
 893                 goto error;
 894
 895         for (i = 0; i < bset->n_eq; ++i)
 896                 swap_vars(blk,
 897                           bset->eq[i]+1+nparam, n, dim - n);
 898
 899         for (i = 0; i < bset->n_ineq; ++i)
 900                 swap_vars(blk,
 901                           bset->ineq[i]+1+nparam, n, dim - n);
 902
 903         for (i = 0; i < bset->n_div; ++i)
 904                 swap_vars(blk,
 905                           bset->div[i]+1+1+nparam, n, dim - n);
 906
 907         isl_blk_free(bset->ctx, blk);
 908
 909         F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
 910         return bset;
 911
 912 error:
 913         isl_basic_set_free(bset);
 914         return NULL;
 915 }
 916
 917 struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n)
 918 {
 919         int i;
 920         set = isl_set_cow(set);
 921         if (!set)
 922                 return NULL;
 923
 924         for (i = 0; i < set->n; ++i) {
 925                 set->p[i] = isl_basic_set_swap_vars(set->p[i], n);
 926                 if (!set->p[i]) {
 927                         isl_set_free(set);
 928                         return NULL;
 929                 }
 930         }
 931         F_CLR(set, ISL_SET_NORMALIZED);
 932         return set;
 933 }
 934
 935 static void constraint_drop_vars(isl_int *c, unsigned n, unsigned rem)
 936 {
 937         isl_seq_cpy(c, c + n, rem);
 938         isl_seq_clr(c + rem, n);
 939 }
 940
 941 struct isl_basic_set *isl_basic_set_drop_dims(
 942                 struct isl_basic_set *bset, unsigned first, unsigned n)
 943 {
 944         int i;
 945
 946         if (!bset)
 947                 goto error;
 948
 949         isl_assert(bset->ctx, first + n <= bset->dim->n_out, goto error);
 950
 951         if (n == 0)
 952                 return bset;
 953
 954         bset = isl_basic_set_cow(bset);
 955         if (!bset)
 956                 return NULL;
 957
 958         for (i = 0; i < bset->n_eq; ++i)
 959                 constraint_drop_vars(bset->eq[i]+1+bset->dim->nparam+first, n,
 960                                      (bset->dim->n_out-first-n)+bset->extra);
 961
 962         for (i = 0; i < bset->n_ineq; ++i)
 963                 constraint_drop_vars(bset->ineq[i]+1+bset->dim->nparam+first, n,
 964                                      (bset->dim->n_out-first-n)+bset->extra);
 965
 966         for (i = 0; i < bset->n_div; ++i)
 967                 constraint_drop_vars(bset->div[i]+1+1+bset->dim->nparam+first, n,
 968                                      (bset->dim->n_out-first-n)+bset->extra);
 969
 970         bset->dim = isl_dim_drop_outputs(bset->dim, first, n);
 971         if (!bset->dim)
 972                 goto error;
 973         bset->extra += n;
 974
 975         F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
 976         bset = isl_basic_set_simplify(bset);
 977         return isl_basic_set_finalize(bset);
 978 error:
 979         isl_basic_set_free(bset);
 980         return NULL;
 981 }
 982
 983 static struct isl_set *isl_set_drop_dims(
 984                 struct isl_set *set, unsigned first, unsigned n)
 985 {
 986         int i;
 987
 988         if (!set)
 989                 goto error;
 990
 991         isl_assert(set->ctx, first + n <= set->dim->n_out, goto error);
 992
 993         if (n == 0)
 994                 return set;
 995         set = isl_set_cow(set);
 996         if (!set)
 997                 goto error;
 998         set->dim = isl_dim_drop_outputs(set->dim, first, n);
 999         if (!set->dim)
1000                 goto error;
1001
1002         for (i = 0; i < set->n; ++i) {
1003                 set->p[i] = isl_basic_set_drop_dims(set->p[i], first, n);
1004                 if (!set->p[i])
1005                         goto error;
1006         }
1007
1008         F_CLR(set, ISL_SET_NORMALIZED);
1009         return set;
1010 error:
1011         isl_set_free(set);
1012         return NULL;
1013 }
1014
1015 struct isl_basic_map *isl_basic_map_drop_inputs(
1016                 struct isl_basic_map *bmap, unsigned first, unsigned n)
1017 {
1018         int i;
1019         unsigned nparam;
1020         unsigned n_in;
1021         unsigned n_out;
1022
1023         if (!bmap)
1024                 goto error;
1025
1026         nparam = isl_basic_map_n_param(bmap);
1027         n_in = isl_basic_map_n_in(bmap);
1028         n_out = isl_basic_map_n_out(bmap);
1029         isl_assert(bmap->ctx, first + n <= n_in, goto error);
1030
1031         if (n == 0)
1032                 return bmap;
1033
1034         bmap = isl_basic_map_cow(bmap);
1035         if (!bmap)
1036                 return NULL;
1037
1038         for (i = 0; i < bmap->n_eq; ++i)
1039                 constraint_drop_vars(bmap->eq[i]+1+nparam+first, n,
1040                                  (n_in-first-n)+n_out+bmap->extra);
1041
1042         for (i = 0; i < bmap->n_ineq; ++i)
1043                 constraint_drop_vars(bmap->ineq[i]+1+nparam+first, n,
1044                                  (n_in-first-n)+n_out+bmap->extra);
1045
1046         for (i = 0; i < bmap->n_div; ++i)
1047                 constraint_drop_vars(bmap->div[i]+1+1+nparam+first, n,
1048                                  (n_in-first-n)+n_out+bmap->extra);
1049
1050         bmap->dim = isl_dim_drop_inputs(bmap->dim, first, n);
1051         if (!bmap->dim)
1052                 goto error;
1053         bmap->extra += n;
1054
1055         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1056         bmap = isl_basic_map_simplify(bmap);
1057         return isl_basic_map_finalize(bmap);
1058 error:
1059         isl_basic_map_free(bmap);
1060         return NULL;
1061 }
1062
1063 static struct isl_map *isl_map_drop_inputs(
1064                 struct isl_map *map, unsigned first, unsigned n)
1065 {
1066         int i;
1067
1068         if (!map)
1069                 goto error;
1070
1071         isl_assert(map->ctx, first + n <= map->dim->n_in, goto error);
1072
1073         if (n == 0)
1074                 return map;
1075         map = isl_map_cow(map);
1076         if (!map)
1077                 goto error;
1078         map->dim = isl_dim_drop_inputs(map->dim, first, n);
1079         if (!map->dim)
1080                 goto error;
1081
1082         for (i = 0; i < map->n; ++i) {
1083                 map->p[i] = isl_basic_map_drop_inputs(map->p[i], first, n);
1084                 if (!map->p[i])
1085                         goto error;
1086         }
1087         F_CLR(map, ISL_MAP_NORMALIZED);
1088
1089         return map;
1090 error:
1091         isl_map_free(map);
1092         return NULL;
1093 }
1094
1095 /*
1096  * We don't cow, as the div is assumed to be redundant.
1097  */
1098 static struct isl_basic_map *isl_basic_map_drop_div(
1099                 struct isl_basic_map *bmap, unsigned div)
1100 {
1101         int i;
1102         unsigned pos;
1103
1104         if (!bmap)
1105                 goto error;
1106
1107         pos = 1 + isl_dim_total(bmap->dim) + div;
1108
1109         isl_assert(bmap->ctx, div < bmap->n_div, goto error);
1110
1111         for (i = 0; i < bmap->n_eq; ++i)
1112                 constraint_drop_vars(bmap->eq[i]+pos, 1, bmap->extra-div-1);
1113
1114         for (i = 0; i < bmap->n_ineq; ++i) {
1115                 if (!isl_int_is_zero(bmap->ineq[i][pos])) {
1116                         isl_basic_map_drop_inequality(bmap, i);
1117                         --i;
1118                         continue;
1119                 }
1120                 constraint_drop_vars(bmap->ineq[i]+pos, 1, bmap->extra-div-1);
1121         }
1122
1123         for (i = 0; i < bmap->n_div; ++i)
1124                 constraint_drop_vars(bmap->div[i]+1+pos, 1, bmap->extra-div-1);
1125
1126         if (div != bmap->n_div - 1) {
1127                 int j;
1128                 isl_int *t = bmap->div[div];
1129
1130                 for (j = div; j < bmap->n_div - 1; ++j)
1131                         bmap->div[j] = bmap->div[j+1];
1132
1133                 bmap->div[bmap->n_div - 1] = t;
1134         }
1135         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1136         isl_basic_map_free_div(bmap, 1);
1137
1138         return bmap;
1139 error:
1140         isl_basic_map_free(bmap);
1141         return NULL;
1142 }
1143
1144 static void eliminate_div(struct isl_basic_map *bmap, isl_int *eq, unsigned div)
1145 {
1146         int i;
1147         unsigned pos = 1 + isl_dim_total(bmap->dim) + div;
1148         unsigned len;
1149         len = 1 + isl_basic_map_total_dim(bmap);
1150
1151         for (i = 0; i < bmap->n_eq; ++i)
1152                 if (bmap->eq[i] != eq)
1153                         isl_seq_elim(bmap->eq[i], eq, pos, len, NULL);
1154
1155         for (i = 0; i < bmap->n_ineq; ++i)
1156                 isl_seq_elim(bmap->ineq[i], eq, pos, len, NULL);
1157
1158         /* We need to be careful about circular definitions,
1159          * so for now we just remove the definitions of other divs that
1160          * depend on this div and (possibly) recompute them later.
1161          */
1162         for (i = 0; i < bmap->n_div; ++i)
1163                 if (!isl_int_is_zero(bmap->div[i][0]) &&
1164                     !isl_int_is_zero(bmap->div[i][1 + pos]))
1165                         isl_seq_clr(bmap->div[i], 1 + len);
1166
1167         isl_basic_map_drop_div(bmap, div);
1168 }
1169
1170 struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
1171 {
1172         int i = 0;
1173         unsigned total;
1174         if (!bmap)
1175                 goto error;
1176         total = isl_basic_map_total_dim(bmap);
1177         isl_basic_map_free_div(bmap, bmap->n_div);
1178         isl_basic_map_free_inequality(bmap, bmap->n_ineq);
1179         if (bmap->n_eq > 0)
1180                 isl_basic_map_free_equality(bmap, bmap->n_eq-1);
1181         else {
1182                 isl_basic_map_alloc_equality(bmap);
1183                 if (i < 0)
1184                         goto error;
1185         }
1186         isl_int_set_si(bmap->eq[i][0], 1);
1187         isl_seq_clr(bmap->eq[i]+1, total);
1188         F_SET(bmap, ISL_BASIC_MAP_EMPTY);
1189         return isl_basic_map_finalize(bmap);
1190 error:
1191         isl_basic_map_free(bmap);
1192         return NULL;
1193 }
1194
1195 struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset)
1196 {
1197         return (struct isl_basic_set *)
1198                 isl_basic_map_set_to_empty((struct isl_basic_map *)bset);
1199 }
1200
1201 static void swap_equality(struct isl_basic_map *bmap, int a, int b)
1202 {
1203         isl_int *t = bmap->eq[a];
1204         bmap->eq[a] = bmap->eq[b];
1205         bmap->eq[b] = t;
1206 }
1207
1208 static void swap_inequality(struct isl_basic_map *bmap, int a, int b)
1209 {
1210         if (a != b) {
1211                 isl_int *t = bmap->ineq[a];
1212                 bmap->ineq[a] = bmap->ineq[b];
1213                 bmap->ineq[b] = t;
1214         }
1215 }
1216
1217 static void set_swap_inequality(struct isl_basic_set *bset, int a, int b)
1218 {
1219         swap_inequality((struct isl_basic_map *)bset, a, b);
1220 }
1221
1222 static void swap_div(struct isl_basic_map *bmap, int a, int b)
1223 {
1224         int i;
1225         unsigned off = isl_dim_total(bmap->dim);
1226         isl_int *t = bmap->div[a];
1227         bmap->div[a] = bmap->div[b];
1228         bmap->div[b] = t;
1229
1230         for (i = 0; i < bmap->n_eq; ++i)
1231                 isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
1232
1233         for (i = 0; i < bmap->n_ineq; ++i)
1234                 isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
1235
1236         for (i = 0; i < bmap->n_div; ++i)
1237                 isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
1238         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1239 }
1240
1241 static void eliminate_var_using_equality(struct isl_basic_map *bmap,
1242         unsigned pos, isl_int *eq, int *progress)
1243 {
1244         unsigned total;
1245         int k;
1246
1247         total = isl_basic_map_total_dim(bmap);
1248         for (k = 0; k < bmap->n_eq; ++k) {
1249                 if (bmap->eq[k] == eq)
1250                         continue;
1251                 if (isl_int_is_zero(bmap->eq[k][1+pos]))
1252                         continue;
1253                 if (progress)
1254                         *progress = 1;
1255                 isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);
1256         }
1257
1258         for (k = 0; k < bmap->n_ineq; ++k) {
1259                 if (isl_int_is_zero(bmap->ineq[k][1+pos]))
1260                         continue;
1261                 if (progress)
1262                         *progress = 1;
1263                 isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);
1264                 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1265         }
1266
1267         for (k = 0; k < bmap->n_div; ++k) {
1268                 if (isl_int_is_zero(bmap->div[k][0]))
1269                         continue;
1270                 if (isl_int_is_zero(bmap->div[k][1+1+pos]))
1271                         continue;
1272                 if (progress)
1273                         *progress = 1;
1274                 isl_seq_elim(bmap->div[k]+1, eq,
1275                                 1+pos, 1+total, &bmap->div[k][0]);
1276                 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1277         }
1278 }
1279
1280
1281 struct isl_basic_map *isl_basic_map_gauss(
1282         struct isl_basic_map *bmap, int *progress)
1283 {
1284         int k;
1285         int done;
1286         int last_var;
1287         unsigned total_var;
1288         unsigned total;
1289
1290         if (!bmap)
1291                 return NULL;
1292
1293         total = isl_basic_map_total_dim(bmap);
1294         total_var = total - bmap->n_div;
1295
1296         last_var = total - 1;
1297         for (done = 0; done < bmap->n_eq; ++done) {
1298                 for (; last_var >= 0; --last_var) {
1299                         for (k = done; k < bmap->n_eq; ++k)
1300                                 if (!isl_int_is_zero(bmap->eq[k][1+last_var]))
1301                                         break;
1302                         if (k < bmap->n_eq)
1303                                 break;
1304                 }
1305                 if (last_var < 0)
1306                         break;
1307                 if (k != done)
1308                         swap_equality(bmap, k, done);
1309                 if (isl_int_is_neg(bmap->eq[done][1+last_var]))
1310                         isl_seq_neg(bmap->eq[done], bmap->eq[done], 1+total);
1311
1312                 eliminate_var_using_equality(bmap, last_var, bmap->eq[done],
1313                                                 progress);
1314
1315                 if (last_var >= total_var &&
1316                     isl_int_is_zero(bmap->div[last_var - total_var][0])) {
1317                         unsigned div = last_var - total_var;
1318                         isl_seq_neg(bmap->div[div]+1, bmap->eq[done], 1+total);
1319                         isl_int_set_si(bmap->div[div][1+1+last_var], 0);
1320                         isl_int_set(bmap->div[div][0],
1321                                     bmap->eq[done][1+last_var]);
1322                         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1323                 }
1324         }
1325         if (done == bmap->n_eq)
1326                 return bmap;
1327         for (k = done; k < bmap->n_eq; ++k) {
1328                 if (isl_int_is_zero(bmap->eq[k][0]))
1329                         continue;
1330                 return isl_basic_map_set_to_empty(bmap);
1331         }
1332         isl_basic_map_free_equality(bmap, bmap->n_eq-done);
1333         return bmap;
1334 }
1335
1336 struct isl_basic_set *isl_basic_set_gauss(
1337         struct isl_basic_set *bset, int *progress)
1338 {
1339         return (struct isl_basic_set*)isl_basic_map_gauss(
1340                         (struct isl_basic_map *)bset, progress);
1341 }
1342
1343 static unsigned int round_up(unsigned int v)
1344 {
1345         int old_v = v;
1346
1347         while (v) {
1348                 old_v = v;
1349                 v ^= v & -v;
1350         }
1351         return old_v << 1;
1352 }
1353
1354 static int hash_index(isl_int ***index, unsigned int size, int bits,
1355                         struct isl_basic_map *bmap, int k)
1356 {
1357         int h;
1358         unsigned total = isl_basic_map_total_dim(bmap);
1359         uint32_t hash = isl_seq_get_hash_bits(bmap->ineq[k]+1, total, bits);
1360         for (h = hash; index[h]; h = (h+1) % size)
1361                 if (&bmap->ineq[k] != index[h] &&
1362                     isl_seq_eq(bmap->ineq[k]+1, index[h][0]+1, total))
1363                         break;
1364         return h;
1365 }
1366
1367 static int set_hash_index(isl_int ***index, unsigned int size, int bits,
1368                           struct isl_basic_set *bset, int k)
1369 {
1370         return hash_index(index, size, bits, (struct isl_basic_map *)bset, k);
1371 }
1372
1373 static struct isl_basic_map *remove_duplicate_constraints(
1374         struct isl_basic_map *bmap, int *progress)
1375 {
1376         unsigned int size;
1377         isl_int ***index;
1378         int k, l, h;
1379         int bits;
1380         unsigned total = isl_basic_map_total_dim(bmap);
1381         isl_int sum;
1382
1383         if (bmap->n_ineq <= 1)
1384                 return bmap;
1385
1386         size = round_up(4 * (bmap->n_ineq+1) / 3 - 1);
1387         bits = ffs(size) - 1;
1388         index = isl_calloc_array(ctx, isl_int **, size);
1389         if (!index)
1390                 return bmap;
1391
1392         index[isl_seq_get_hash_bits(bmap->ineq[0]+1, total, bits)] = &bmap->ineq[0];
1393         for (k = 1; k < bmap->n_ineq; ++k) {
1394                 h = hash_index(index, size, bits, bmap, k);
1395                 if (!index[h]) {
1396                         index[h] = &bmap->ineq[k];
1397                         continue;
1398                 }
1399                 if (progress)
1400                         *progress = 1;
1401                 l = index[h] - &bmap->ineq[0];
1402                 if (isl_int_lt(bmap->ineq[k][0], bmap->ineq[l][0]))
1403                         swap_inequality(bmap, k, l);
1404                 isl_basic_map_drop_inequality(bmap, k);
1405                 --k;
1406         }
1407         isl_int_init(sum);
1408         for (k = 0; k < bmap->n_ineq-1; ++k) {
1409                 isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);
1410                 h = hash_index(index, size, bits, bmap, k);
1411                 isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);
1412                 if (!index[h])
1413                         continue;
1414                 l = index[h] - &bmap->ineq[0];
1415                 isl_int_add(sum, bmap->ineq[k][0], bmap->ineq[l][0]);
1416                 if (isl_int_is_pos(sum))
1417                         continue;
1418                 if (isl_int_is_zero(sum)) {
1419                         /* We need to break out of the loop after these
1420                          * changes since the contents of the hash
1421                          * will no longer be valid.
1422                          * Plus, we probably we want to regauss first.
1423                          */
1424                         isl_basic_map_drop_inequality(bmap, l);
1425                         isl_basic_map_inequality_to_equality(bmap, k);
1426                 } else
1427                         bmap = isl_basic_map_set_to_empty(bmap);
1428                 break;
1429         }
1430         isl_int_clear(sum);
1431
1432         free(index);
1433         return bmap;
1434 }
1435
1436 static void compute_elimination_index(struct isl_basic_map *bmap, int *elim)
1437 {
1438         int d, i;
1439         unsigned total;
1440
1441         total = isl_dim_total(bmap->dim);
1442         for (d = 0; d < total; ++d)
1443                 elim[d] = -1;
1444         for (d = total - 1, i = 0; d >= 0 && i < bmap->n_eq; ++i) {
1445                 for (; d >= 0; --d) {
1446                         if (isl_int_is_zero(bmap->eq[i][1+d]))
1447                                 continue;
1448                         elim[d] = i;
1449                         break;
1450                 }
1451         }
1452 }
1453
1454 static void set_compute_elimination_index(struct isl_basic_set *bset, int *elim)
1455 {
1456         return compute_elimination_index((struct isl_basic_map *)bset, elim);
1457 }
1458
1459 static int reduced_using_equalities(isl_int *dst, isl_int *src,
1460         struct isl_basic_map *bmap, int *elim)
1461 {
1462         int d, i;
1463         int copied = 0;
1464         unsigned total;
1465
1466         total = isl_dim_total(bmap->dim);
1467         for (d = total - 1; d >= 0; --d) {
1468                 if (isl_int_is_zero(src[1+d]))
1469                         continue;
1470                 if (elim[d] == -1)
1471                         continue;
1472                 if (!copied) {
1473                         isl_seq_cpy(dst, src, 1 + total);
1474                         copied = 1;
1475                 }
1476                 isl_seq_elim(dst, bmap->eq[elim[d]], 1 + d, 1 + total, NULL);
1477         }
1478         return copied;
1479 }
1480
1481 static int set_reduced_using_equalities(isl_int *dst, isl_int *src,
1482         struct isl_basic_set *bset, int *elim)
1483 {
1484         return reduced_using_equalities(dst, src,
1485                                         (struct isl_basic_map *)bset, elim);
1486 }
1487
1488 /* Quick check to see if two basic maps are disjoint.
1489  * In particular, we reduce the equalities and inequalities of
1490  * one basic map in the context of the equalities of the other
1491  * basic map and check if we get a contradiction.
1492  */
1493 int isl_basic_map_fast_is_disjoint(struct isl_basic_map *bmap1,
1494         struct isl_basic_map *bmap2)
1495 {
1496         struct isl_vec *v = NULL;
1497         int *elim = NULL;
1498         unsigned total;
1499         int d, i;
1500
1501         if (!bmap1 || !bmap2)
1502                 return -1;
1503         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
1504                         return -1);
1505         if (bmap1->n_div || bmap2->n_div)
1506                 return 0;
1507         if (!bmap1->n_eq && !bmap2->n_eq)
1508                 return 0;
1509
1510         total = isl_dim_total(bmap1->dim);
1511         if (total == 0)
1512                 return 0;
1513         v = isl_vec_alloc(bmap1->ctx, 1 + total);
1514         if (!v)
1515                 goto error;
1516         elim = isl_alloc_array(bmap1->ctx, int, total);
1517         if (!elim)
1518                 goto error;
1519         compute_elimination_index(bmap1, elim);
1520         for (i = 0; i < bmap2->n_eq; ++i) {
1521                 int reduced;
1522                 reduced = reduced_using_equalities(v->block.data, bmap2->eq[i],
1523                                                         bmap1, elim);
1524                 if (reduced && !isl_int_is_zero(v->block.data[0]) &&
1525                     isl_seq_first_non_zero(v->block.data + 1, total) == -1)
1526                         goto disjoint;
1527         }
1528         for (i = 0; i < bmap2->n_ineq; ++i) {
1529                 int reduced;
1530                 reduced = reduced_using_equalities(v->block.data,
1531                                                 bmap2->ineq[i], bmap1, elim);
1532                 if (reduced && isl_int_is_neg(v->block.data[0]) &&
1533                     isl_seq_first_non_zero(v->block.data + 1, total) == -1)
1534                         goto disjoint;
1535         }
1536         compute_elimination_index(bmap2, elim);
1537         for (i = 0; i < bmap1->n_ineq; ++i) {
1538                 int reduced;
1539                 reduced = reduced_using_equalities(v->block.data,
1540                                                 bmap1->ineq[i], bmap2, elim);
1541                 if (reduced && isl_int_is_neg(v->block.data[0]) &&
1542                     isl_seq_first_non_zero(v->block.data + 1, total) == -1)
1543                         goto disjoint;
1544         }
1545         isl_vec_free(bmap1->ctx, v);
1546         free(elim);
1547         return 0;
1548 disjoint:
1549         isl_vec_free(bmap1->ctx, v);
1550         free(elim);
1551         return 1;
1552 error:
1553         isl_vec_free(bmap1->ctx, v);
1554         free(elim);
1555         return -1;
1556 }
1557
1558 int isl_basic_set_fast_is_disjoint(struct isl_basic_set *bset1,
1559         struct isl_basic_set *bset2)
1560 {
1561         return isl_basic_map_fast_is_disjoint((struct isl_basic_map *)bset1,
1562                                               (struct isl_basic_map *)bset2);
1563 }
1564
1565 int isl_map_fast_is_disjoint(struct isl_map *map1, struct isl_map *map2)
1566 {
1567         int i, j;
1568
1569         if (!map1 || !map2)
1570                 return -1;
1571
1572         if (isl_map_fast_is_equal(map1, map2))
1573                 return 0;
1574
1575         for (i = 0; i < map1->n; ++i) {
1576                 for (j = 0; j < map2->n; ++j) {
1577                         int d = isl_basic_map_fast_is_disjoint(map1->p[i],
1578                                                                map2->p[j]);
1579                         if (d != 1)
1580                                 return d;
1581                 }
1582         }
1583         return 1;
1584 }
1585
1586 int isl_set_fast_is_disjoint(struct isl_set *set1, struct isl_set *set2)
1587 {
1588         return isl_map_fast_is_disjoint((struct isl_map *)set1,
1589                                         (struct isl_map *)set2);
1590 }
1591
1592 static struct isl_basic_map *remove_duplicate_divs(
1593         struct isl_basic_map *bmap, int *progress)
1594 {
1595         unsigned int size;
1596         int *index;
1597         int k, l, h;
1598         int bits;
1599         struct isl_blk eq;
1600         unsigned total_var = isl_dim_total(bmap->dim);
1601         unsigned total = total_var + bmap->n_div;
1602         struct isl_ctx *ctx;
1603
1604         if (bmap->n_div <= 1)
1605                 return bmap;
1606
1607         ctx = bmap->ctx;
1608         for (k = bmap->n_div - 1; k >= 0; --k)
1609                 if (!isl_int_is_zero(bmap->div[k][0]))
1610                         break;
1611         if (k <= 0)
1612                 return bmap;
1613
1614         size = round_up(4 * bmap->n_div / 3 - 1);
1615         bits = ffs(size) - 1;
1616         index = isl_calloc_array(ctx, int, size);
1617         if (!index)
1618                 return bmap;
1619         eq = isl_blk_alloc(ctx, 1+total);
1620         if (isl_blk_is_error(eq))
1621                 goto out;
1622
1623         isl_seq_clr(eq.data, 1+total);
1624         index[isl_seq_get_hash_bits(bmap->div[k], 2+total, bits)] = k + 1;
1625         for (--k; k >= 0; --k) {
1626                 uint32_t hash;
1627
1628                 if (isl_int_is_zero(bmap->div[k][0]))
1629                         continue;
1630
1631                 hash = isl_seq_get_hash_bits(bmap->div[k], 2+total, bits);
1632                 for (h = hash; index[h]; h = (h+1) % size)
1633                         if (isl_seq_eq(bmap->div[k],
1634                                        bmap->div[index[h]-1], 2+total))
1635                                 break;
1636                 if (index[h]) {
1637                         *progress = 1;
1638                         l = index[h] - 1;
1639                         isl_int_set_si(eq.data[1+total_var+k], -1);
1640                         isl_int_set_si(eq.data[1+total_var+l], 1);
1641                         eliminate_div(bmap, eq.data, l);
1642                         isl_int_set_si(eq.data[1+total_var+k], 0);
1643                         isl_int_set_si(eq.data[1+total_var+l], 0);
1644                 }
1645                 index[h] = k+1;
1646         }
1647
1648         isl_blk_free(ctx, eq);
1649 out:
1650         free(index);
1651         return bmap;
1652 }
1653
1654 /* Elimininate divs based on equalities
1655  */
1656 static struct isl_basic_map *eliminate_divs_eq(
1657                 struct isl_basic_map *bmap, int *progress)
1658 {
1659         int d;
1660         int i;
1661         int modified = 0;
1662         unsigned off;
1663
1664         if (!bmap)
1665                 return NULL;
1666
1667         off = 1 + isl_dim_total(bmap->dim);
1668
1669         for (d = bmap->n_div - 1; d >= 0 ; --d) {
1670                 for (i = 0; i < bmap->n_eq; ++i) {
1671                         if (!isl_int_is_one(bmap->eq[i][off + d]) &&
1672                             !isl_int_is_negone(bmap->eq[i][off + d]))
1673                                 continue;
1674                         modified = 1;
1675                         *progress = 1;
1676                         eliminate_div(bmap, bmap->eq[i], d);
1677                         isl_basic_map_drop_equality(bmap, i);
1678                         break;
1679                 }
1680         }
1681         if (modified)
1682                 return eliminate_divs_eq(bmap, progress);
1683         return bmap;
1684 }
1685
1686 static struct isl_basic_map *normalize_constraints(struct isl_basic_map *bmap)
1687 {
1688         int i;
1689         isl_int gcd;
1690         unsigned total = isl_basic_map_total_dim(bmap);
1691
1692         isl_int_init(gcd);
1693         for (i = bmap->n_eq - 1; i >= 0; --i) {
1694                 isl_seq_gcd(bmap->eq[i]+1, total, &gcd);
1695                 if (isl_int_is_zero(gcd)) {
1696                         if (!isl_int_is_zero(bmap->eq[i][0])) {
1697                                 bmap = isl_basic_map_set_to_empty(bmap);
1698                                 break;
1699                         }
1700                         isl_basic_map_drop_equality(bmap, i);
1701                         continue;
1702                 }
1703                 if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
1704                         isl_int_gcd(gcd, gcd, bmap->eq[i][0]);
1705                 if (isl_int_is_one(gcd))
1706                         continue;
1707                 if (!isl_int_is_divisible_by(bmap->eq[i][0], gcd)) {
1708                         bmap = isl_basic_map_set_to_empty(bmap);
1709                         break;
1710                 }
1711                 isl_seq_scale_down(bmap->eq[i], bmap->eq[i], gcd, 1+total);
1712         }
1713
1714         for (i = bmap->n_ineq - 1; i >= 0; --i) {
1715                 isl_seq_gcd(bmap->ineq[i]+1, total, &gcd);
1716                 if (isl_int_is_zero(gcd)) {
1717                         if (isl_int_is_neg(bmap->ineq[i][0])) {
1718                                 bmap = isl_basic_map_set_to_empty(bmap);
1719                                 break;
1720                         }
1721                         isl_basic_map_drop_inequality(bmap, i);
1722                         continue;
1723                 }
1724                 if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
1725                         isl_int_gcd(gcd, gcd, bmap->ineq[i][0]);
1726                 if (isl_int_is_one(gcd))
1727                         continue;
1728                 isl_int_fdiv_q(bmap->ineq[i][0], bmap->ineq[i][0], gcd);
1729                 isl_seq_scale_down(bmap->ineq[i]+1, bmap->ineq[i]+1, gcd, total);
1730         }
1731         isl_int_clear(gcd);
1732
1733         return bmap;
1734 }
1735
1736
1737 /* Eliminate the specified variables from the constraints using
1738  * Fourier-Motzkin.  The variables themselves are not removed.
1739  */
1740 struct isl_basic_map *isl_basic_map_eliminate_vars(
1741         struct isl_basic_map *bmap, int pos, unsigned n)
1742 {
1743         int d;
1744         int i, j, k;
1745         unsigned total;
1746
1747         if (n == 0)
1748                 return bmap;
1749         if (!bmap)
1750                 return NULL;
1751         total = isl_basic_map_total_dim(bmap);
1752
1753         bmap = isl_basic_map_cow(bmap);
1754         for (d = pos + n - 1; d >= pos; --d) {
1755                 int n_lower, n_upper;
1756                 if (!bmap)
1757                         return NULL;
1758                 for (i = 0; i < bmap->n_eq; ++i) {
1759                         if (isl_int_is_zero(bmap->eq[i][1+d]))
1760                                 continue;
1761                         eliminate_var_using_equality(bmap, d, bmap->eq[i], NULL);
1762                         isl_basic_map_drop_equality(bmap, i);
1763                         break;
1764                 }
1765                 if (i < bmap->n_eq)
1766                         continue;
1767                 n_lower = 0;
1768                 n_upper = 0;
1769                 for (i = 0; i < bmap->n_ineq; ++i) {
1770                         if (isl_int_is_pos(bmap->ineq[i][1+d]))
1771                                 n_lower++;
1772                         else if (isl_int_is_neg(bmap->ineq[i][1+d]))
1773                                 n_upper++;
1774                 }
1775                 bmap = isl_basic_map_extend_constraints(bmap,
1776                                 0, n_lower * n_upper);
1777                 for (i = bmap->n_ineq - 1; i >= 0; --i) {
1778                         int last;
1779                         if (isl_int_is_zero(bmap->ineq[i][1+d]))
1780                                 continue;
1781                         last = -1;
1782                         for (j = 0; j < i; ++j) {
1783                                 if (isl_int_is_zero(bmap->ineq[j][1+d]))
1784                                         continue;
1785                                 last = j;
1786                                 if (isl_int_sgn(bmap->ineq[i][1+d]) ==
1787                                     isl_int_sgn(bmap->ineq[j][1+d]))
1788                                         continue;
1789                                 k = isl_basic_map_alloc_inequality(bmap);
1790                                 if (k < 0)
1791                                         goto error;
1792                                 isl_seq_cpy(bmap->ineq[k], bmap->ineq[i],
1793                                                 1+total);
1794                                 isl_seq_elim(bmap->ineq[k], bmap->ineq[j],
1795                                                 1+d, 1+total, NULL);
1796                         }
1797                         isl_basic_map_drop_inequality(bmap, i);
1798                         i = last + 1;
1799                 }
1800                 if (n_lower > 0 && n_upper > 0) {
1801                         bmap = normalize_constraints(bmap);
1802                         bmap = remove_duplicate_constraints(bmap, NULL);
1803                         bmap = isl_basic_map_gauss(bmap, NULL);
1804                         bmap = isl_basic_map_convex_hull(bmap);
1805                         if (!bmap)
1806                                 goto error;
1807                         if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
1808                                 break;
1809                 }
1810         }
1811         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1812         return bmap;
1813 error:
1814         isl_basic_map_free(bmap);
1815         return NULL;
1816 }
1817
1818 struct isl_basic_set *isl_basic_set_eliminate_vars(
1819         struct isl_basic_set *bset, unsigned pos, unsigned n)
1820 {
1821         return (struct isl_basic_set *)isl_basic_map_eliminate_vars(
1822                         (struct isl_basic_map *)bset, pos, n);
1823 }
1824
1825 /* Eliminate the specified n dimensions starting at first from the
1826  * constraints using Fourier-Motzkin, The dimensions themselves
1827  * are not removed.
1828  */
1829 struct isl_set *isl_set_eliminate_dims(struct isl_set *set,
1830         unsigned first, unsigned n)
1831 {
1832         int i;
1833         unsigned nparam;
1834
1835         if (!set)
1836                 return NULL;
1837         if (n == 0)
1838                 return set;
1839
1840         set = isl_set_cow(set);
1841         if (!set)
1842                 return NULL;
1843         isl_assert(set->ctx, first+n <= isl_set_n_dim(set), goto error);
1844         nparam = isl_set_n_param(set);
1845
1846         for (i = 0; i < set->n; ++i) {
1847                 set->p[i] = isl_basic_set_eliminate_vars(set->p[i],
1848                                                             nparam + first, n);
1849                 if (!set->p[i])
1850                         goto error;
1851         }
1852         return set;
1853 error:
1854         isl_set_free(set);
1855         return NULL;
1856 }
1857
1858 /* Project out n dimensions starting at first using Fourier-Motzkin */
1859 struct isl_set *isl_set_remove_dims(struct isl_set *set,
1860         unsigned first, unsigned n)
1861 {
1862         set = isl_set_eliminate_dims(set, first, n);
1863         set = isl_set_drop_dims(set, first, n);
1864         return set;
1865 }
1866
1867 struct isl_basic_set *isl_basic_set_remove_divs(struct isl_basic_set *bset)
1868 {
1869         bset = isl_basic_set_eliminate_vars(bset, isl_dim_total(bset->dim),
1870                                                 bset->n_div);
1871         if (!bset)
1872                 return NULL;
1873         bset->n_div = 0;
1874         return bset;
1875 }
1876
1877 struct isl_set *isl_set_remove_divs(struct isl_set *set)
1878 {
1879         int i;
1880
1881         if (!set)
1882                 return NULL;
1883         if (set->n == 0)
1884                 return set;
1885
1886         set = isl_set_cow(set);
1887         if (!set)
1888                 return NULL;
1889
1890         for (i = 0; i < set->n; ++i) {
1891                 set->p[i] = isl_basic_set_remove_divs(set->p[i]);
1892                 if (!set->p[i])
1893                         goto error;
1894         }
1895         return set;
1896 error:
1897         isl_set_free(set);
1898         return NULL;
1899 }
1900
1901 /* Project out n inputs starting at first using Fourier-Motzkin */
1902 struct isl_map *isl_map_remove_inputs(struct isl_map *map,
1903         unsigned first, unsigned n)
1904 {
1905         int i;
1906         unsigned nparam;
1907
1908         if (n == 0)
1909                 return map;
1910
1911         map = isl_map_cow(map);
1912         if (!map)
1913                 return NULL;
1914         nparam = isl_map_n_param(map);
1915         isl_assert(map->ctx, first+n <= isl_map_n_in(map), goto error);
1916
1917         for (i = 0; i < map->n; ++i) {
1918                 map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
1919                                                             nparam + first, n);
1920                 if (!map->p[i])
1921                         goto error;
1922         }
1923         map = isl_map_drop_inputs(map, first, n);
1924         return map;
1925 error:
1926         isl_map_free(map);
1927         return NULL;
1928 }
1929
1930 /* Project out n dimensions starting at first using Fourier-Motzkin */
1931 struct isl_basic_set *isl_basic_set_remove_dims(struct isl_basic_set *bset,
1932         unsigned first, unsigned n)
1933 {
1934         unsigned nparam = isl_basic_set_n_param(bset);
1935         bset = isl_basic_set_eliminate_vars(bset, nparam + first, n);
1936         bset = isl_basic_set_drop_dims(bset, first, n);
1937         return bset;
1938 }
1939
1940 /* Elimininate divs based on inequalities
1941  */
1942 static struct isl_basic_map *eliminate_divs_ineq(
1943                 struct isl_basic_map *bmap, int *progress)
1944 {
1945         int d;
1946         int i;
1947         unsigned off;
1948         struct isl_ctx *ctx;
1949
1950         if (!bmap)
1951                 return NULL;
1952
1953         ctx = bmap->ctx;
1954         off = 1 + isl_dim_total(bmap->dim);
1955
1956         for (d = bmap->n_div - 1; d >= 0 ; --d) {
1957                 for (i = 0; i < bmap->n_eq; ++i)
1958                         if (!isl_int_is_zero(bmap->eq[i][off + d]))
1959                                 break;
1960                 if (i < bmap->n_eq)
1961                         continue;
1962                 for (i = 0; i < bmap->n_ineq; ++i)
1963                         if (isl_int_abs_gt(bmap->ineq[i][off + d], ctx->one))
1964                                 break;
1965                 if (i < bmap->n_ineq)
1966                         continue;
1967                 *progress = 1;
1968                 bmap = isl_basic_map_eliminate_vars(bmap, (off-1)+d, 1);
1969                 if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
1970                         break;
1971                 bmap = isl_basic_map_drop_div(bmap, d);
1972                 if (!bmap)
1973                         break;
1974         }
1975         return bmap;
1976 }
1977
1978 struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap)
1979 {
1980         int progress = 1;
1981         if (!bmap)
1982                 return NULL;
1983         while (progress) {
1984                 progress = 0;
1985                 bmap = normalize_constraints(bmap);
1986                 bmap = eliminate_divs_eq(bmap, &progress);
1987                 bmap = eliminate_divs_ineq(bmap, &progress);
1988                 bmap = isl_basic_map_gauss(bmap, &progress);
1989                 bmap = remove_duplicate_divs(bmap, &progress);
1990                 bmap = remove_duplicate_constraints(bmap, &progress);
1991         }
1992         return bmap;
1993 }
1994
1995 struct isl_basic_set *isl_basic_set_simplify(struct isl_basic_set *bset)
1996 {
1997         return (struct isl_basic_set *)
1998                 isl_basic_map_simplify((struct isl_basic_map *)bset);
1999 }
2000
2001 static void dump_term(struct isl_basic_map *bmap,
2002                         isl_int c, int pos, FILE *out)
2003 {
2004         const char *name;
2005         unsigned in = isl_basic_map_n_in(bmap);
2006         unsigned dim = in + isl_basic_map_n_out(bmap);
2007         unsigned nparam = isl_basic_map_n_param(bmap);
2008         if (!pos)
2009                 isl_int_print(out, c, 0);
2010         else {
2011                 if (!isl_int_is_one(c))
2012                         isl_int_print(out, c, 0);
2013                 if (pos < 1 + nparam) {
2014                         name = isl_dim_get_name(bmap->dim,
2015                                                 isl_dim_param, pos - 1);
2016                         if (name)
2017                                 fprintf(out, "%s", name);
2018                         else
2019                                 fprintf(out, "p%d", pos - 1);
2020                 } else if (pos < 1 + nparam + in)
2021                         fprintf(out, "i%d", pos - 1 - nparam);
2022                 else if (pos < 1 + nparam + dim)
2023                         fprintf(out, "o%d", pos - 1 - nparam - in);
2024                 else
2025                         fprintf(out, "e%d", pos - 1 - nparam - dim);
2026         }
2027 }
2028
2029 static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
2030                                 int sign, FILE *out)
2031 {
2032         int i;
2033         int first;
2034         unsigned len = 1 + isl_basic_map_total_dim(bmap);
2035         isl_int v;
2036
2037         isl_int_init(v);
2038         for (i = 0, first = 1; i < len; ++i) {
2039                 if (isl_int_sgn(c[i]) * sign <= 0)
2040                         continue;
2041                 if (!first)
2042                         fprintf(out, " + ");
2043                 first = 0;
2044                 isl_int_abs(v, c[i]);
2045                 dump_term(bmap, v, i, out);
2046         }
2047         isl_int_clear(v);
2048         if (first)
2049                 fprintf(out, "0");
2050 }
2051
2052 static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
2053                                 const char *op, FILE *out, int indent)
2054 {
2055         int i;
2056
2057         fprintf(out, "%*s", indent, "");
2058
2059         dump_constraint_sign(bmap, c, 1, out);
2060         fprintf(out, " %s ", op);
2061         dump_constraint_sign(bmap, c, -1, out);
2062
2063         fprintf(out, "\n");
2064
2065         for (i = bmap->n_div; i < bmap->extra; ++i) {
2066                 if (isl_int_is_zero(c[1+isl_dim_total(bmap->dim)+i]))
2067                         continue;
2068                 fprintf(out, "%*s", indent, "");
2069                 fprintf(out, "ERROR: unused div coefficient not zero\n");
2070                 abort();
2071         }
2072 }
2073
2074 static void dump_constraints(struct isl_basic_map *bmap,
2075                                 isl_int **c, unsigned n,
2076                                 const char *op, FILE *out, int indent)
2077 {
2078         int i;
2079
2080         for (i = 0; i < n; ++i)
2081                 dump_constraint(bmap, c[i], op, out, indent);
2082 }
2083
2084 static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
2085 {
2086         int j;
2087         int first = 1;
2088         unsigned total = isl_basic_map_total_dim(bmap);
2089
2090         for (j = 0; j < 1 + total; ++j) {
2091                 if (isl_int_is_zero(exp[j]))
2092                         continue;
2093                 if (!first && isl_int_is_pos(exp[j]))
2094                         fprintf(out, "+");
2095                 dump_term(bmap, exp[j], j, out);
2096                 first = 0;
2097         }
2098 }
2099
2100 static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
2101 {
2102         int i;
2103
2104         dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
2105         dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
2106
2107         for (i = 0; i < bmap->n_div; ++i) {
2108                 fprintf(out, "%*s", indent, "");
2109                 fprintf(out, "e%d = [(", i);
2110                 dump_affine(bmap, bmap->div[i]+1, out);
2111                 fprintf(out, ")/");
2112                 isl_int_print(out, bmap->div[i][0], 0);
2113                 fprintf(out, "]\n");
2114         }
2115 }
2116
2117 void isl_basic_set_dump(struct isl_basic_set *bset, FILE *out, int indent)
2118 {
2119         if (!bset) {
2120                 fprintf(out, "null basic set\n");
2121                 return;
2122         }
2123
2124         fprintf(out, "%*s", indent, "");
2125         fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
2126                         bset->ref, bset->dim->nparam, bset->dim->n_out,
2127                         bset->extra, bset->flags);
2128         dump((struct isl_basic_map *)bset, out, indent);
2129 }
2130
2131 void isl_basic_map_dump(struct isl_basic_map *bmap, FILE *out, int indent)
2132 {
2133         if (!bmap) {
2134                 fprintf(out, "null basic map\n");
2135                 return;
2136         }
2137
2138         fprintf(out, "%*s", indent, "");
2139         fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
2140                         "flags: %x, n_name: %d\n",
2141                 bmap->ref,
2142                 bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
2143                 bmap->extra, bmap->flags, bmap->dim->n_name);
2144         dump(bmap, out, indent);
2145 }
2146
2147 int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
2148 {
2149         unsigned total;
2150         if (!bmap)
2151                 return -1;
2152         total = isl_basic_map_total_dim(bmap);
2153         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
2154         isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
2155         isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
2156         F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2157         return 0;
2158 }
2159
2160 struct isl_set *isl_set_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
2161 {
2162         struct isl_set *set;
2163
2164         if (!dim)
2165                 return NULL;
2166         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
2167         isl_assert(dim->ctx, n >= 0, return NULL);
2168         set = isl_alloc(dim->ctx, struct isl_set,
2169                         sizeof(struct isl_set) +
2170                         n * sizeof(struct isl_basic_set *));
2171         if (!set)
2172                 goto error;
2173
2174         set->ctx = dim->ctx;
2175         isl_ctx_ref(set->ctx);
2176         set->ref = 1;
2177         set->size = n;
2178         set->n = 0;
2179         set->dim = dim;
2180         set->flags = flags;
2181         return set;
2182 error:
2183         isl_dim_free(dim);
2184         return NULL;
2185 }
2186
2187 struct isl_set *isl_set_alloc(struct isl_ctx *ctx,
2188                 unsigned nparam, unsigned dim, int n, unsigned flags)
2189 {
2190         struct isl_set *set;
2191         struct isl_dim *dims;
2192
2193         dims = isl_dim_alloc(ctx, nparam, 0, dim);
2194         if (!dims)
2195                 return NULL;
2196
2197         set = isl_set_alloc_dim(dims, n, flags);
2198         return set;
2199 }
2200
2201 struct isl_set *isl_set_dup(struct isl_set *set)
2202 {
2203         int i;
2204         struct isl_set *dup;
2205
2206         if (!set)
2207                 return NULL;
2208
2209         dup = isl_set_alloc_dim(isl_dim_copy(set->dim), set->n, set->flags);
2210         if (!dup)
2211                 return NULL;
2212         for (i = 0; i < set->n; ++i)
2213                 dup = isl_set_add(dup, isl_basic_set_copy(set->p[i]));
2214         return dup;
2215 }
2216
2217 struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset)
2218 {
2219         struct isl_set *set;
2220
2221         if (!bset)
2222                 return NULL;
2223
2224         set = isl_set_alloc_dim(isl_dim_copy(bset->dim), 1, ISL_MAP_DISJOINT);
2225         if (!set) {
2226                 isl_basic_set_free(bset);
2227                 return NULL;
2228         }
2229         return isl_set_add(set, bset);
2230 }
2231
2232 struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap)
2233 {
2234         struct isl_map *map;
2235
2236         if (!bmap)
2237                 return NULL;
2238
2239         map = isl_map_alloc_dim(isl_dim_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
2240         if (!map) {
2241                 isl_basic_map_free(bmap);
2242                 return NULL;
2243         }
2244         return isl_map_add(map, bmap);
2245 }
2246
2247 struct isl_set *isl_set_add(struct isl_set *set, struct isl_basic_set *bset)
2248 {
2249         if (!bset || !set)
2250                 goto error;
2251         isl_assert(set->ctx, isl_dim_equal(set->dim, bset->dim), goto error);
2252         isl_assert(set->ctx, set->n < set->size, goto error);
2253         set->p[set->n] = bset;
2254         set->n++;
2255         return set;
2256 error:
2257         if (set)
2258                 isl_set_free(set);
2259         if (bset)
2260                 isl_basic_set_free(bset);
2261         return NULL;
2262 }
2263
2264 void isl_set_free(struct isl_set *set)
2265 {
2266         int i;
2267
2268         if (!set)
2269                 return;
2270
2271         if (--set->ref > 0)
2272                 return;
2273
2274         isl_ctx_deref(set->ctx);
2275         for (i = 0; i < set->n; ++i)
2276                 isl_basic_set_free(set->p[i]);
2277         isl_dim_free(set->dim);
2278         free(set);
2279 }
2280
2281 void isl_set_dump(struct isl_set *set, FILE *out, int indent)
2282 {
2283         int i;
2284
2285         if (!set) {
2286                 fprintf(out, "null set\n");
2287                 return;
2288         }
2289
2290         fprintf(out, "%*s", indent, "");
2291         fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
2292                         set->ref, set->n, set->dim->nparam, set->dim->n_out,
2293                         set->flags);
2294         for (i = 0; i < set->n; ++i) {
2295                 fprintf(out, "%*s", indent, "");
2296                 fprintf(out, "basic set %d:\n", i);
2297                 isl_basic_set_dump(set->p[i], out, indent+4);
2298         }
2299 }
2300
2301 void isl_map_dump(struct isl_map *map, FILE *out, int indent)
2302 {
2303         int i;
2304
2305         if (!map) {
2306                 fprintf(out, "null map\n");
2307                 return;
2308         }
2309
2310         fprintf(out, "%*s", indent, "");
2311         fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
2312                      "flags: %x, n_name: %d\n",
2313                         map->ref, map->n, map->dim->nparam, map->dim->n_in,
2314                         map->dim->n_out, map->flags, map->dim->n_name);
2315         for (i = 0; i < map->n; ++i) {
2316                 fprintf(out, "%*s", indent, "");
2317                 fprintf(out, "basic map %d:\n", i);
2318                 isl_basic_map_dump(map->p[i], out, indent+4);
2319         }
2320 }
2321
2322 struct isl_basic_map *isl_basic_map_intersect_domain(
2323                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
2324 {
2325         struct isl_basic_map *bmap_domain;
2326         struct isl_dim *dim;
2327
2328         if (!bmap || !bset)
2329                 goto error;
2330
2331         isl_assert(set->ctx, isl_basic_map_compatible_domain(bmap, bset),
2332                     goto error);
2333
2334         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
2335                         bset->n_div, bset->n_eq, bset->n_ineq);
2336         if (!bmap)
2337                 goto error;
2338         dim = isl_dim_reverse(isl_dim_copy(bset->dim));
2339         bmap_domain = isl_basic_map_from_basic_set(bset, dim);
2340         bmap = add_constraints(bmap, bmap_domain, 0, 0);
2341
2342         bmap = isl_basic_map_simplify(bmap);
2343         return isl_basic_map_finalize(bmap);
2344 error:
2345         isl_basic_map_free(bmap);
2346         isl_basic_set_free(bset);
2347         return NULL;
2348 }
2349
2350 struct isl_basic_map *isl_basic_map_intersect_range(
2351                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
2352 {
2353         struct isl_basic_map *bmap_range;
2354
2355         if (!bmap || !bset)
2356                 goto error;
2357
2358         isl_assert(bset->ctx, isl_basic_map_compatible_range(bmap, bset),
2359                    goto error);
2360
2361         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
2362                         bset->n_div, bset->n_eq, bset->n_ineq);
2363         if (!bmap)
2364                 goto error;
2365         bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
2366         bmap = add_constraints(bmap, bmap_range, 0, 0);
2367
2368         bmap = isl_basic_map_simplify(bmap);
2369         return isl_basic_map_finalize(bmap);
2370 error:
2371         isl_basic_map_free(bmap);
2372         isl_basic_set_free(bset);
2373         return NULL;
2374 }
2375
2376 struct isl_basic_map *isl_basic_map_intersect(
2377                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2378 {
2379         if (!bmap1 || !bmap2)
2380                 goto error;
2381
2382         isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
2383
2384         bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
2385                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
2386         if (!bmap1)
2387                 goto error;
2388         bmap1 = add_constraints(bmap1, bmap2, 0, 0);
2389
2390         bmap1 = isl_basic_map_simplify(bmap1);
2391         return isl_basic_map_finalize(bmap1);
2392 error:
2393         isl_basic_map_free(bmap1);
2394         isl_basic_map_free(bmap2);
2395         return NULL;
2396 }
2397
2398 struct isl_basic_set *isl_basic_set_intersect(
2399                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
2400 {
2401         return (struct isl_basic_set *)
2402                 isl_basic_map_intersect(
2403                         (struct isl_basic_map *)bset1,
2404                         (struct isl_basic_map *)bset2);
2405 }
2406
2407 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
2408 {
2409         unsigned flags = 0;
2410         struct isl_map *result;
2411         int i, j;
2412
2413         if (!map1 || !map2)
2414                 goto error;
2415
2416         if (F_ISSET(map1, ISL_MAP_DISJOINT) &&
2417             F_ISSET(map2, ISL_MAP_DISJOINT))
2418                 FL_SET(flags, ISL_MAP_DISJOINT);
2419
2420         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2421                                 map1->n * map2->n, flags);
2422         if (!result)
2423                 goto error;
2424         for (i = 0; i < map1->n; ++i)
2425                 for (j = 0; j < map2->n; ++j) {
2426                         struct isl_basic_map *part;
2427                         part = isl_basic_map_intersect(
2428                                     isl_basic_map_copy(map1->p[i]),
2429                                     isl_basic_map_copy(map2->p[j]));
2430                         if (isl_basic_map_is_empty(part))
2431                                 isl_basic_map_free(part);
2432                         else
2433                                 result = isl_map_add(result, part);
2434                         if (!result)
2435                                 goto error;
2436                 }
2437         isl_map_free(map1);
2438         isl_map_free(map2);
2439         return result;
2440 error:
2441         isl_map_free(map1);
2442         isl_map_free(map2);
2443         return NULL;
2444 }
2445
2446 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
2447 {
2448         return (struct isl_set *)
2449                 isl_map_intersect((struct isl_map *)set1,
2450                                   (struct isl_map *)set2);
2451 }
2452
2453 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
2454 {
2455         struct isl_dim *dim;
2456         struct isl_basic_set *bset;
2457         unsigned in;
2458
2459         if (!bmap)
2460                 return NULL;
2461         bmap = isl_basic_map_cow(bmap);
2462         if (!bmap)
2463                 return NULL;
2464         dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
2465         in = isl_basic_map_n_in(bmap);
2466         bset = isl_basic_set_from_basic_map(bmap);
2467         bset = isl_basic_set_swap_vars(bset, in);
2468         return isl_basic_map_from_basic_set(bset, dim);
2469 }
2470
2471 /* Turn final n dimensions into existentially quantified variables.
2472  */
2473 struct isl_basic_set *isl_basic_set_project_out(
2474                 struct isl_basic_set *bset, unsigned n, unsigned flags)
2475 {
2476         int i;
2477         size_t row_size;
2478         isl_int **new_div;
2479         isl_int *old;
2480
2481         if (!bset)
2482                 return NULL;
2483
2484         isl_assert(bset->ctx, n <= isl_basic_set_n_dim(bset), goto error);
2485
2486         if (n == 0)
2487                 return bset;
2488
2489         bset = isl_basic_set_cow(bset);
2490
2491         row_size = 1 + isl_dim_total(bset->dim) + bset->extra;
2492         old = bset->block2.data;
2493         bset->block2 = isl_blk_extend(bset->ctx, bset->block2,
2494                                         (bset->extra + n) * (1 + row_size));
2495         if (!bset->block2.data)
2496                 goto error;
2497         new_div = isl_alloc_array(ctx, isl_int *, bset->extra + n);
2498         if (!new_div)
2499                 goto error;
2500         for (i = 0; i < n; ++i) {
2501                 new_div[i] = bset->block2.data +
2502                                 (bset->extra + i) * (1 + row_size);
2503                 isl_seq_clr(new_div[i], 1 + row_size);
2504         }
2505         for (i = 0; i < bset->extra; ++i)
2506                 new_div[n + i] = bset->block2.data + (bset->div[i] - old);
2507         free(bset->div);
2508         bset->div = new_div;
2509         bset->n_div += n;
2510         bset->extra += n;
2511         bset->dim = isl_dim_drop_outputs(bset->dim,
2512                                             isl_basic_set_n_dim(bset) - n, n);
2513         if (!bset->dim)
2514                 goto error;
2515         bset = isl_basic_set_simplify(bset);
2516         return isl_basic_set_finalize(bset);
2517 error:
2518         isl_basic_set_free(bset);
2519         return NULL;
2520 }
2521
2522 struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2523 {
2524         int i, j;
2525
2526         for (i = 0; i < n; ++i) {
2527                 j = isl_basic_map_alloc_div(bmap);
2528                 if (j < 0)
2529                         goto error;
2530                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2531         }
2532         return bmap;
2533 error:
2534         isl_basic_map_free(bmap);
2535         return NULL;
2536 }
2537
2538 struct isl_basic_map *isl_basic_map_apply_range(
2539                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2540 {
2541         struct isl_dim *dim_result = NULL;
2542         struct isl_basic_map *bmap;
2543         unsigned n_in, n_out, n, nparam, total, pos;
2544         struct isl_dim_map *dim_map1, *dim_map2;
2545
2546         if (!bmap1 || !bmap2)
2547                 goto error;
2548
2549         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2550                                   isl_dim_copy(bmap2->dim));
2551
2552         n_in = isl_basic_map_n_in(bmap1);
2553         n_out = isl_basic_map_n_out(bmap2);
2554         n = isl_basic_map_n_out(bmap1);
2555         nparam = isl_basic_map_n_param(bmap1);
2556
2557         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2558         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2559         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2560         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2561         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2562         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2563         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2564         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2565         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2566         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2567         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2568
2569         bmap = isl_basic_map_alloc_dim(dim_result,
2570                         bmap1->n_div + bmap2->n_div + n,
2571                         bmap1->n_eq + bmap2->n_eq,
2572                         bmap1->n_ineq + bmap2->n_ineq);
2573         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2574         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2575         bmap = add_divs(bmap, n);
2576         bmap = isl_basic_map_simplify(bmap);
2577         return isl_basic_map_finalize(bmap);
2578 error:
2579         isl_basic_map_free(bmap1);
2580         isl_basic_map_free(bmap2);
2581         return NULL;
2582 }
2583
2584 struct isl_basic_set *isl_basic_set_apply(
2585                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2586 {
2587         if (!bset || !bmap)
2588                 goto error;
2589
2590         isl_assert(set->ctx, isl_basic_map_compatible_domain(bmap, bset),
2591                     goto error);
2592
2593         return (struct isl_basic_set *)
2594                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2595 error:
2596         isl_basic_set_free(bset);
2597         isl_basic_map_free(bmap);
2598         return NULL;
2599 }
2600
2601 struct isl_basic_map *isl_basic_map_apply_domain(
2602                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2603 {
2604         if (!bmap1 || !bmap2)
2605                 goto error;
2606
2607         isl_assert(ctx,
2608             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2609         isl_assert(ctx,
2610             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2611             goto error);
2612
2613         bmap1 = isl_basic_map_reverse(bmap1);
2614         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2615         return isl_basic_map_reverse(bmap1);
2616 error:
2617         isl_basic_map_free(bmap1);
2618         isl_basic_map_free(bmap2);
2619         return NULL;
2620 }
2621
2622 static struct isl_basic_map *var_equal(struct isl_ctx *ctx,
2623                 struct isl_basic_map *bmap, unsigned pos)
2624 {
2625         int i;
2626         unsigned nparam;
2627         unsigned n_in;
2628
2629         i = isl_basic_map_alloc_equality(bmap);
2630         if (i < 0)
2631                 goto error;
2632         nparam = isl_basic_map_n_param(bmap);
2633         n_in = isl_basic_map_n_in(bmap);
2634         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2635         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2636         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2637         return isl_basic_map_finalize(bmap);
2638 error:
2639         isl_basic_map_free(bmap);
2640         return NULL;
2641 }
2642
2643 static struct isl_basic_map *var_more(struct isl_ctx *ctx,
2644                 struct isl_basic_map *bmap, unsigned pos)
2645 {
2646         int i;
2647         unsigned nparam;
2648         unsigned n_in;
2649
2650         i = isl_basic_map_alloc_inequality(bmap);
2651         if (i < 0)
2652                 goto error;
2653         nparam = isl_basic_map_n_param(bmap);
2654         n_in = isl_basic_map_n_in(bmap);
2655         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2656         isl_int_set_si(bmap->ineq[i][0], -1);
2657         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2658         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2659         return isl_basic_map_finalize(bmap);
2660 error:
2661         isl_basic_map_free(bmap);
2662         return NULL;
2663 }
2664
2665 static struct isl_basic_map *var_less(struct isl_ctx *ctx,
2666                 struct isl_basic_map *bmap, unsigned pos)
2667 {
2668         int i;
2669         unsigned nparam;
2670         unsigned n_in;
2671
2672         i = isl_basic_map_alloc_inequality(bmap);
2673         if (i < 0)
2674                 goto error;
2675         nparam = isl_basic_map_n_param(bmap);
2676         n_in = isl_basic_map_n_in(bmap);
2677         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2678         isl_int_set_si(bmap->ineq[i][0], -1);
2679         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2680         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2681         return isl_basic_map_finalize(bmap);
2682 error:
2683         isl_basic_map_free(bmap);
2684         return NULL;
2685 }
2686
2687 struct isl_basic_map *isl_basic_map_equal(struct isl_ctx *ctx,
2688                 unsigned nparam, unsigned in, unsigned out, unsigned n_equal)
2689 {
2690         int i;
2691         struct isl_basic_map *bmap;
2692         bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, n_equal, 0);
2693         if (!bmap)
2694                 return NULL;
2695         for (i = 0; i < n_equal && bmap; ++i)
2696                 bmap = var_equal(ctx, bmap, i);
2697         return isl_basic_map_finalize(bmap);
2698 }
2699
2700 struct isl_basic_map *isl_basic_map_less_at(struct isl_ctx *ctx,
2701                 unsigned nparam, unsigned in, unsigned out, unsigned pos)
2702 {
2703         int i;
2704         struct isl_basic_map *bmap;
2705         bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, pos, 1);
2706         if (!bmap)
2707                 return NULL;
2708         for (i = 0; i < pos && bmap; ++i)
2709                 bmap = var_equal(ctx, bmap, i);
2710         if (bmap)
2711                 bmap = var_less(ctx, bmap, pos);
2712         return isl_basic_map_finalize(bmap);
2713 }
2714
2715 struct isl_basic_map *isl_basic_map_more_at(struct isl_ctx *ctx,
2716                 unsigned nparam, unsigned in, unsigned out, unsigned pos)
2717 {
2718         int i;
2719         struct isl_basic_map *bmap;
2720         bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, pos, 1);
2721         if (!bmap)
2722                 return NULL;
2723         for (i = 0; i < pos && bmap; ++i)
2724                 bmap = var_equal(ctx, bmap, i);
2725         if (bmap)
2726                 bmap = var_more(ctx, bmap, pos);
2727         return isl_basic_map_finalize(bmap);
2728 }
2729
2730 struct isl_basic_map *isl_basic_map_from_basic_set(
2731                 struct isl_basic_set *bset, struct isl_dim *dim)
2732 {
2733         struct isl_basic_map *bmap;
2734
2735         bset = isl_basic_set_cow(bset);
2736         if (!bset || !dim)
2737                 goto error;
2738
2739         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
2740         isl_dim_free(bset->dim);
2741         bmap = (struct isl_basic_map *) bset;
2742         bmap->dim = dim;
2743         return isl_basic_map_finalize(bmap);
2744 error:
2745         isl_basic_set_free(bset);
2746         isl_dim_free(dim);
2747         return NULL;
2748 }
2749
2750 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
2751 {
2752         if (!bmap)
2753                 goto error;
2754         if (bmap->dim->n_in == 0)
2755                 return (struct isl_basic_set *)bmap;
2756         bmap = isl_basic_map_cow(bmap);
2757         if (!bmap)
2758                 goto error;
2759         bmap->dim = isl_dim_cow(bmap->dim);
2760         if (!bmap->dim)
2761                 goto error;
2762         bmap->dim->n_out += bmap->dim->n_in;
2763         bmap->dim->n_in = 0;
2764         bmap = isl_basic_map_finalize(bmap);
2765         return (struct isl_basic_set *)bmap;
2766 error:
2767         isl_basic_map_free(bmap);
2768         return NULL;
2769 }
2770
2771 /* For a div d = floor(f/m), add the constraints
2772  *
2773  *              f - m d >= 0
2774  *              -(f-(n-1)) + m d >= 0
2775  *
2776  * Note that the second constraint is the negation of
2777  *
2778  *              f - m d >= n
2779  */
2780 static int add_div_constraints(struct isl_basic_map *bmap, unsigned div)
2781 {
2782         int i, j;
2783         unsigned total = isl_basic_map_total_dim(bmap);
2784         unsigned div_pos = 1 + total - bmap->n_div + div;
2785
2786         i = isl_basic_map_alloc_inequality(bmap);
2787         if (i < 0)
2788                 return -1;
2789         isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total);
2790         isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]);
2791
2792         j = isl_basic_map_alloc_inequality(bmap);
2793         if (j < 0)
2794                 return -1;
2795         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
2796         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]);
2797         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
2798         return j;
2799 }
2800
2801 struct isl_basic_set *isl_basic_map_underlying_set(
2802                 struct isl_basic_map *bmap)
2803 {
2804         if (!bmap)
2805                 goto error;
2806         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
2807                 return (struct isl_basic_set *)bmap;
2808         bmap = isl_basic_map_cow(bmap);
2809         if (!bmap)
2810                 goto error;
2811         bmap->dim = isl_dim_cow(bmap->dim);
2812         if (!bmap->dim)
2813                 goto error;
2814         bmap->dim->n_out += bmap->dim->nparam + bmap->dim->n_in + bmap->n_div;
2815         bmap->dim->nparam = 0;
2816         bmap->dim->n_in = 0;
2817         bmap->extra -= bmap->n_div;
2818         bmap->n_div = 0;
2819         bmap = isl_basic_map_finalize(bmap);
2820         return (struct isl_basic_set *)bmap;
2821 error:
2822         return NULL;
2823 }
2824
2825 struct isl_basic_map *isl_basic_map_overlying_set(
2826         struct isl_basic_set *bset, struct isl_basic_map *like)
2827 {
2828         struct isl_basic_map *bmap;
2829         struct isl_ctx *ctx;
2830         unsigned total;
2831         int i, k;
2832
2833         if (!bset || !like)
2834                 goto error;
2835         ctx = bset->ctx;
2836         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
2837                         goto error);
2838         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
2839                 isl_basic_map_free(like);
2840                 return (struct isl_basic_map *)bset;
2841         }
2842         bset = isl_basic_set_cow(bset);
2843         if (!bset)
2844                 goto error;
2845         total = bset->dim->n_out + bset->extra;
2846         bmap = (struct isl_basic_map *)bset;
2847         isl_dim_free(bmap->dim);
2848         bmap->dim = isl_dim_copy(like->dim);
2849         if (!bmap->dim)
2850                 goto error;
2851         bmap->extra += like->n_div;
2852         if (bmap->extra) {
2853                 unsigned ltotal;
2854                 ltotal = total - bmap->extra + like->extra;
2855                 if (ltotal > total)
2856                         ltotal = total;
2857                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
2858                                         bmap->extra * (1 + 1 + total));
2859                 if (isl_blk_is_error(bmap->block2))
2860                         goto error;
2861                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
2862                                                 bmap->extra);
2863                 if (!bmap->div)
2864                         goto error;
2865                 bmap = isl_basic_map_extend_constraints(bmap,
2866                                                         0, 2 * like->n_div);
2867                 for (i = 0; i < like->n_div; ++i) {
2868                         k = isl_basic_map_alloc_div(bmap);
2869                         if (k < 0)
2870                                 goto error;
2871                         isl_seq_cpy(bmap->div[k], like->div[i], 1 + 1 + ltotal);
2872                         isl_seq_clr(bmap->div[k]+1+1+ltotal, total - ltotal);
2873                         if (add_div_constraints(bmap, k) < 0)
2874                                 goto error;
2875                 }
2876         }
2877         isl_basic_map_free(like);
2878         bmap = isl_basic_map_finalize(bmap);
2879         return bmap;
2880 error:
2881         isl_basic_map_free(like);
2882         isl_basic_set_free(bset);
2883         return NULL;
2884 }
2885
2886 struct isl_basic_set *isl_basic_set_from_underlying_set(
2887         struct isl_basic_set *bset, struct isl_basic_set *like)
2888 {
2889         return (struct isl_basic_set *)
2890                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
2891 }
2892
2893 struct isl_set *isl_set_from_underlying_set(
2894         struct isl_set *set, struct isl_basic_set *like)
2895 {
2896         int i;
2897
2898         if (!set || !like)
2899                 goto error;
2900         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
2901                     goto error);
2902         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
2903                 isl_basic_set_free(like);
2904                 return set;
2905         }
2906         set = isl_set_cow(set);
2907         if (!set)
2908                 goto error;
2909         for (i = 0; i < set->n; ++i) {
2910                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
2911                                                       isl_basic_set_copy(like));
2912                 if (!set->p[i])
2913                         goto error;
2914         }
2915         isl_dim_free(set->dim);
2916         set->dim = isl_dim_copy(like->dim);
2917         if (!set->dim)
2918                 goto error;
2919         isl_basic_set_free(like);
2920         return set;
2921 error:
2922         isl_basic_set_free(like);
2923         isl_set_free(set);
2924         return NULL;
2925 }
2926
2927 struct isl_set *isl_map_underlying_set(struct isl_map *map)
2928 {
2929         int i;
2930
2931         map = isl_map_align_divs(map);
2932         map = isl_map_cow(map);
2933         if (!map)
2934                 return NULL;
2935         map->dim = isl_dim_cow(map->dim);
2936         if (!map->dim)
2937                 goto error;
2938
2939         for (i = 0; i < map->n; ++i) {
2940                 map->p[i] = (struct isl_basic_map *)
2941                                 isl_basic_map_underlying_set(map->p[i]);
2942                 if (!map->p[i])
2943                         goto error;
2944         }
2945         if (map->n == 0)
2946                 map->dim->n_out += map->dim->nparam + map->dim->n_in;
2947         else
2948                 map->dim->n_out = map->p[0]->dim->n_out;
2949         map->dim->nparam = 0;
2950         map->dim->n_in = 0;
2951         return (struct isl_set *)map;
2952 error:
2953         isl_map_free(map);
2954         return NULL;
2955 }
2956
2957 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
2958 {
2959         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
2960 }
2961
2962 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
2963 {
2964         struct isl_basic_set *domain;
2965         unsigned n_out;
2966         if (!bmap)
2967                 return NULL;
2968         n_out = isl_basic_map_n_out(bmap);
2969         domain = isl_basic_set_from_basic_map(bmap);
2970         return isl_basic_set_project_out(domain, n_out, 0);
2971 }
2972
2973 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
2974 {
2975         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
2976 }
2977
2978 struct isl_set *isl_map_range(struct isl_map *map)
2979 {
2980         int i;
2981         struct isl_set *set;
2982
2983         if (!map)
2984                 goto error;
2985         map = isl_map_cow(map);
2986         if (!map)
2987                 goto error;
2988
2989         set = (struct isl_set *) map;
2990         if (set->dim->n_in != 0) {
2991                 set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
2992                 if (!set->dim)
2993                         goto error;
2994         }
2995         for (i = 0; i < map->n; ++i) {
2996                 set->p[i] = isl_basic_map_range(map->p[i]);
2997                 if (!set->p[i])
2998                         goto error;
2999         }
3000         F_CLR(set, ISL_MAP_DISJOINT);
3001         F_CLR(set, ISL_SET_NORMALIZED);
3002         return set;
3003 error:
3004         isl_map_free(map);
3005         return NULL;
3006 }
3007
3008 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3009 {
3010         int i;
3011         struct isl_map *map = NULL;
3012
3013         set = isl_set_cow(set);
3014         if (!set || !dim)
3015                 goto error;
3016         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3017         map = (struct isl_map *)set;
3018         for (i = 0; i < set->n; ++i) {
3019                 map->p[i] = isl_basic_map_from_basic_set(
3020                                 set->p[i], isl_dim_copy(dim));
3021                 if (!map->p[i])
3022                         goto error;
3023         }
3024         isl_dim_free(map->dim);
3025         map->dim = dim;
3026         return map;
3027 error:
3028         isl_dim_free(dim);
3029         isl_set_free(set);
3030         return NULL;
3031 }
3032
3033 struct isl_set *isl_set_from_map(struct isl_map *map)
3034 {
3035         int i;
3036         struct isl_set *set = NULL;
3037
3038         if (!map)
3039                 return NULL;
3040         map = isl_map_cow(map);
3041         if (!map)
3042                 return NULL;
3043         map->dim = isl_dim_cow(map->dim);
3044         if (!map->dim)
3045                 goto error;
3046         map->dim->n_out += map->dim->n_in;
3047         map->dim->n_in = 0;
3048         set = (struct isl_set *)map;
3049         for (i = 0; i < map->n; ++i) {
3050                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3051                 if (!set->p[i])
3052                         goto error;
3053         }
3054         return set;
3055 error:
3056         isl_map_free(map);
3057         return NULL;
3058 }
3059
3060 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3061 {
3062         struct isl_map *map;
3063
3064         if (!dim)
3065                 return NULL;
3066         isl_assert(dim->ctx, n >= 0, return NULL);
3067         map = isl_alloc(dim->ctx, struct isl_map,
3068                         sizeof(struct isl_map) +
3069                         n * sizeof(struct isl_basic_map *));
3070         if (!map)
3071                 goto error;
3072
3073         map->ctx = dim->ctx;
3074         isl_ctx_ref(map->ctx);
3075         map->ref = 1;
3076         map->size = n;
3077         map->n = 0;
3078         map->dim = dim;
3079         map->flags = flags;
3080         return map;
3081 error:
3082         isl_dim_free(dim);
3083         return NULL;
3084 }
3085
3086 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3087                 unsigned nparam, unsigned in, unsigned out, int n,
3088                 unsigned flags)
3089 {
3090         struct isl_map *map;
3091         struct isl_dim *dims;
3092
3093         dims = isl_dim_alloc(ctx, nparam, in, out);
3094         if (!dims)
3095                 return NULL;
3096
3097         map = isl_map_alloc_dim(dims, n, flags);
3098         return map;
3099 }
3100
3101 struct isl_basic_map *isl_basic_map_empty(struct isl_ctx *ctx,
3102                 unsigned nparam, unsigned in, unsigned out)
3103 {
3104         struct isl_basic_map *bmap;
3105         bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, 1, 0);
3106         bmap = isl_basic_map_set_to_empty(bmap);
3107         return bmap;
3108 }
3109
3110 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3111 {
3112         struct isl_basic_set *bset;
3113         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3114         bset = isl_basic_set_set_to_empty(bset);
3115         return bset;
3116 }
3117
3118 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3119 {
3120         struct isl_basic_map *bmap;
3121         if (!model)
3122                 return NULL;
3123         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3124         bmap = isl_basic_map_set_to_empty(bmap);
3125         return bmap;
3126 }
3127
3128 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3129 {
3130         struct isl_basic_map *bmap;
3131         if (!model)
3132                 return NULL;
3133         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3134         bmap = isl_basic_map_set_to_empty(bmap);
3135         return bmap;
3136 }
3137
3138 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3139 {
3140         struct isl_basic_set *bset;
3141         if (!model)
3142                 return NULL;
3143         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3144         bset = isl_basic_set_set_to_empty(bset);
3145         return bset;
3146 }
3147
3148 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3149 {
3150         struct isl_basic_map *bmap;
3151         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3152         return bmap;
3153 }
3154
3155 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3156 {
3157         struct isl_basic_set *bset;
3158         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3159         return bset;
3160 }
3161
3162 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3163 {
3164         if (!model)
3165                 return NULL;
3166         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3167 }
3168
3169 struct isl_map *isl_map_empty(struct isl_ctx *ctx,
3170                 unsigned nparam, unsigned in, unsigned out)
3171 {
3172         return isl_map_alloc(ctx, nparam, in, out, 0, ISL_MAP_DISJOINT);
3173 }
3174
3175 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3176 {
3177         if (!model)
3178                 return NULL;
3179         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3180 }
3181
3182 struct isl_set *isl_set_empty(struct isl_dim *dim)
3183 {
3184         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3185 }
3186
3187 struct isl_set *isl_set_empty_like(struct isl_set *model)
3188 {
3189         if (!model)
3190                 return NULL;
3191         return isl_set_empty(isl_dim_copy(model->dim));
3192 }
3193
3194 struct isl_map *isl_map_dup(struct isl_map *map)
3195 {
3196         int i;
3197         struct isl_map *dup;
3198
3199         if (!map)
3200                 return NULL;
3201         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3202         for (i = 0; i < map->n; ++i)
3203                 dup = isl_map_add(dup, isl_basic_map_copy(map->p[i]));
3204         return dup;
3205 }
3206
3207 struct isl_map *isl_map_add(struct isl_map *map, struct isl_basic_map *bmap)
3208 {
3209         if (!bmap || !map)
3210                 goto error;
3211         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3212         isl_assert(map->ctx, map->n < map->size, goto error);
3213         map->p[map->n] = bmap;
3214         map->n++;
3215         F_CLR(map, ISL_MAP_NORMALIZED);
3216         return map;
3217 error:
3218         if (map)
3219                 isl_map_free(map);
3220         if (bmap)
3221                 isl_basic_map_free(bmap);
3222         return NULL;
3223 }
3224
3225 void isl_map_free(struct isl_map *map)
3226 {
3227         int i;
3228
3229         if (!map)
3230                 return;
3231
3232         if (--map->ref > 0)
3233                 return;
3234
3235         isl_ctx_deref(map->ctx);
3236         for (i = 0; i < map->n; ++i)
3237                 isl_basic_map_free(map->p[i]);
3238         isl_dim_free(map->dim);
3239         free(map);
3240 }
3241
3242 struct isl_map *isl_map_extend(struct isl_map *base,
3243                 unsigned nparam, unsigned n_in, unsigned n_out)
3244 {
3245         int i;
3246
3247         base = isl_map_cow(base);
3248         if (!base)
3249                 return NULL;
3250
3251         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3252         if (!base->dim)
3253                 goto error;
3254         for (i = 0; i < base->n; ++i) {
3255                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3256                                 isl_dim_copy(base->dim), 0, 0, 0);
3257                 if (!base->p[i])
3258                         goto error;
3259         }
3260         return base;
3261 error:
3262         isl_map_free(base);
3263         return NULL;
3264 }
3265
3266 struct isl_set *isl_set_extend(struct isl_set *base,
3267                 unsigned nparam, unsigned dim)
3268 {
3269         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3270                                                         nparam, 0, dim);
3271 }
3272
3273 static struct isl_basic_map *isl_basic_map_fix_var(struct isl_basic_map *bmap,
3274                 unsigned var, int value)
3275 {
3276         int j;
3277
3278         bmap = isl_basic_map_cow(bmap);
3279         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3280         j = isl_basic_map_alloc_equality(bmap);
3281         if (j < 0)
3282                 goto error;
3283         isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3284         isl_int_set_si(bmap->eq[j][1 + var], -1);
3285         isl_int_set_si(bmap->eq[j][0], value);
3286         bmap = isl_basic_map_simplify(bmap);
3287         return isl_basic_map_finalize(bmap);
3288 error:
3289         isl_basic_map_free(bmap);
3290         return NULL;
3291 }
3292
3293 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3294                 unsigned input, int value)
3295 {
3296         if (!bmap)
3297                 return NULL;
3298         isl_assert(bmap->ctx, input < isl_basic_map_n_in(bmap), goto error);
3299         return isl_basic_map_fix_var(bmap, isl_basic_map_n_param(bmap) + input,
3300                                         value);
3301 error:
3302         isl_basic_map_free(bmap);
3303         return NULL;
3304 }
3305
3306 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3307                 unsigned dim, int value)
3308 {
3309         if (!bset)
3310                 return NULL;
3311         isl_assert(bset->ctx, dim < isl_basic_set_n_dim(bset), goto error);
3312         return (struct isl_basic_set *)
3313                 isl_basic_map_fix_var((struct isl_basic_map *)bset,
3314                                     isl_basic_set_n_param(bset) + dim, value);
3315 error:
3316         isl_basic_set_free(bset);
3317         return NULL;
3318 }
3319
3320 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3321                 unsigned input, int value)
3322 {
3323         int i;
3324
3325         map = isl_map_cow(map);
3326         if (!map)
3327                 return NULL;
3328
3329         isl_assert(ctx, input < isl_map_n_in(map), goto error);
3330         for (i = 0; i < map->n; ++i) {
3331                 map->p[i] = isl_basic_map_fix_input_si(map->p[i], input, value);
3332                 if (!map->p[i])
3333                         goto error;
3334         }
3335         F_CLR(map, ISL_MAP_NORMALIZED);
3336         return map;
3337 error:
3338         isl_map_free(map);
3339         return NULL;
3340 }
3341
3342 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3343 {
3344         int i;
3345
3346         set = isl_set_cow(set);
3347         if (!set)
3348                 return NULL;
3349
3350         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3351         for (i = 0; i < set->n; ++i) {
3352                 set->p[i] = isl_basic_set_fix_dim_si(set->p[i], dim, value);
3353                 if (!set->p[i])
3354                         goto error;
3355         }
3356         return set;
3357 error:
3358         isl_set_free(set);
3359         return NULL;
3360 }
3361
3362 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3363         unsigned dim, isl_int value)
3364 {
3365         int j;
3366         unsigned nparam;
3367
3368         bset = isl_basic_set_cow(bset);
3369         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3370         j = isl_basic_set_alloc_inequality(bset);
3371         if (j < 0)
3372                 goto error;
3373         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3374         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3375         isl_int_neg(bset->ineq[j][0], value);
3376         bset = isl_basic_set_simplify(bset);
3377         return isl_basic_set_finalize(bset);
3378 error:
3379         isl_basic_set_free(bset);
3380         return NULL;
3381 }
3382
3383 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3384                                         isl_int value)
3385 {
3386         int i;
3387
3388         set = isl_set_cow(set);
3389         if (!set)
3390                 return NULL;
3391
3392         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3393         for (i = 0; i < set->n; ++i) {
3394                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3395                 if (!set->p[i])
3396                         goto error;
3397         }
3398         return set;
3399 error:
3400         isl_set_free(set);
3401         return NULL;
3402 }
3403
3404 struct isl_map *isl_map_reverse(struct isl_map *map)
3405 {
3406         int i;
3407         unsigned t;
3408
3409         map = isl_map_cow(map);
3410         if (!map)
3411                 return NULL;
3412
3413         map->dim = isl_dim_reverse(map->dim);
3414         if (!map->dim)
3415                 goto error;
3416         for (i = 0; i < map->n; ++i) {
3417                 map->p[i] = isl_basic_map_reverse(map->p[i]);
3418                 if (!map->p[i])
3419                         goto error;
3420         }
3421         F_CLR(map, ISL_MAP_NORMALIZED);
3422         return map;
3423 error:
3424         isl_map_free(map);
3425         return NULL;
3426 }
3427
3428 struct isl_map *isl_basic_map_lexmax(
3429                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3430                 struct isl_set **empty)
3431 {
3432         return isl_pip_basic_map_lexmax(bmap, dom, empty);
3433 }
3434
3435 struct isl_map *isl_basic_map_lexmin(
3436                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3437                 struct isl_set **empty)
3438 {
3439         return isl_pip_basic_map_lexmin(bmap, dom, empty);
3440 }
3441
3442 struct isl_set *isl_basic_set_lexmin(struct isl_basic_set *bset)
3443 {
3444         struct isl_basic_map *bmap = NULL;
3445         struct isl_basic_set *dom = NULL;
3446         struct isl_map *min;
3447         struct isl_dim *param_dim;
3448
3449         if (!bset)
3450                 goto error;
3451         bmap = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
3452         if (!bmap)
3453                 goto error;
3454         param_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
3455         dom = isl_basic_set_universe(param_dim);
3456         if (!dom)
3457                 goto error;
3458         min = isl_basic_map_lexmin(bmap, dom, NULL);
3459         return isl_map_range(min);
3460 error:
3461         isl_basic_map_free(bmap);
3462         return NULL;
3463 }
3464
3465 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
3466 {
3467         if (!bmap)
3468                 return NULL;
3469         if (bmap->n_div == 0)
3470                 return isl_map_from_basic_map(bmap);
3471         return isl_pip_basic_map_compute_divs(bmap);
3472 }
3473
3474 struct isl_map *isl_map_compute_divs(struct isl_map *map)
3475 {
3476         int i;
3477         struct isl_map *res;
3478
3479         if (!map)
3480                 return NULL;
3481         if (map->n == 0)
3482                 return map;
3483         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
3484         for (i = 1 ; i < map->n; ++i) {
3485                 struct isl_map *r2;
3486                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
3487                 if (F_ISSET(map, ISL_MAP_DISJOINT))
3488                         res = isl_map_union_disjoint(res, r2);
3489                 else
3490                         res = isl_map_union(res, r2);
3491         }
3492         isl_map_free(map);
3493
3494         return res;
3495 }
3496
3497 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
3498 {
3499         return (struct isl_set *)
3500                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
3501 }
3502
3503 struct isl_set *isl_set_compute_divs(struct isl_set *set)
3504 {
3505         return (struct isl_set *)
3506                 isl_map_compute_divs((struct isl_map *)set);
3507 }
3508
3509 struct isl_set *isl_map_domain(struct isl_map *map)
3510 {
3511         int i;
3512         struct isl_set *set;
3513
3514         if (!map)
3515                 goto error;
3516
3517         map = isl_map_cow(map);
3518         if (!map)
3519                 return NULL;
3520
3521         set = (struct isl_set *)map;
3522         set->dim = isl_dim_domain(set->dim);
3523         if (!set->dim)
3524                 goto error;
3525         for (i = 0; i < map->n; ++i) {
3526                 set->p[i] = isl_basic_map_domain(map->p[i]);
3527                 if (!set->p[i])
3528                         goto error;
3529         }
3530         F_CLR(set, ISL_MAP_DISJOINT);
3531         F_CLR(set, ISL_SET_NORMALIZED);
3532         return set;
3533 error:
3534         isl_map_free(map);
3535         return NULL;
3536 }
3537
3538 struct isl_map *isl_map_union_disjoint(
3539                         struct isl_map *map1, struct isl_map *map2)
3540 {
3541         int i;
3542         unsigned flags = 0;
3543         struct isl_map *map = NULL;
3544
3545         if (!map1 || !map2)
3546                 goto error;
3547
3548         if (map1->n == 0) {
3549                 isl_map_free(map1);
3550                 return map2;
3551         }
3552         if (map2->n == 0) {
3553                 isl_map_free(map2);
3554                 return map1;
3555         }
3556
3557         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
3558
3559         if (F_ISSET(map1, ISL_MAP_DISJOINT) &&
3560             F_ISSET(map2, ISL_MAP_DISJOINT))
3561                 FL_SET(flags, ISL_MAP_DISJOINT);
3562
3563         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
3564                                 map1->n + map2->n, flags);
3565         if (!map)
3566                 goto error;
3567         for (i = 0; i < map1->n; ++i) {
3568                 map = isl_map_add(map,
3569                                   isl_basic_map_copy(map1->p[i]));
3570                 if (!map)
3571                         goto error;
3572         }
3573         for (i = 0; i < map2->n; ++i) {
3574                 map = isl_map_add(map,
3575                                   isl_basic_map_copy(map2->p[i]));
3576                 if (!map)
3577                         goto error;
3578         }
3579         isl_map_free(map1);
3580         isl_map_free(map2);
3581         return map;
3582 error:
3583         isl_map_free(map);
3584         isl_map_free(map1);
3585         isl_map_free(map2);
3586         return NULL;
3587 }
3588
3589 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
3590 {
3591         map1 = isl_map_union_disjoint(map1, map2);
3592         if (!map1)
3593                 return NULL;
3594         if (map1->n > 1)
3595                 F_CLR(map1, ISL_MAP_DISJOINT);
3596         return map1;
3597 }
3598
3599 struct isl_set *isl_set_union_disjoint(
3600                         struct isl_set *set1, struct isl_set *set2)
3601 {
3602         return (struct isl_set *)
3603                 isl_map_union_disjoint(
3604                         (struct isl_map *)set1, (struct isl_map *)set2);
3605 }
3606
3607 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
3608 {
3609         return (struct isl_set *)
3610                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
3611 }
3612
3613 struct isl_map *isl_map_intersect_range(
3614                 struct isl_map *map, struct isl_set *set)
3615 {
3616         unsigned flags = 0;
3617         struct isl_map *result;
3618         int i, j;
3619
3620         if (!map || !set)
3621                 goto error;
3622
3623         if (F_ISSET(map, ISL_MAP_DISJOINT) &&
3624             F_ISSET(set, ISL_MAP_DISJOINT))
3625                 FL_SET(flags, ISL_MAP_DISJOINT);
3626
3627         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
3628                                         map->n * set->n, flags);
3629         if (!result)
3630                 goto error;
3631         for (i = 0; i < map->n; ++i)
3632                 for (j = 0; j < set->n; ++j) {
3633                         result = isl_map_add(result,
3634                             isl_basic_map_intersect_range(
3635                                 isl_basic_map_copy(map->p[i]),
3636                                 isl_basic_set_copy(set->p[j])));
3637                         if (!result)
3638                                 goto error;
3639                 }
3640         isl_map_free(map);
3641         isl_set_free(set);
3642         return result;
3643 error:
3644         isl_map_free(map);
3645         isl_set_free(set);
3646         return NULL;
3647 }
3648
3649 struct isl_map *isl_map_intersect_domain(
3650                 struct isl_map *map, struct isl_set *set)
3651 {
3652         return isl_map_reverse(
3653                 isl_map_intersect_range(isl_map_reverse(map), set));
3654 }
3655
3656 struct isl_map *isl_map_apply_domain(
3657                 struct isl_map *map1, struct isl_map *map2)
3658 {
3659         if (!map1 || !map2)
3660                 goto error;
3661         map1 = isl_map_reverse(map1);
3662         map1 = isl_map_apply_range(map1, map2);
3663         return isl_map_reverse(map1);
3664 error:
3665         isl_map_free(map1);
3666         isl_map_free(map2);
3667         return NULL;
3668 }
3669
3670 struct isl_map *isl_map_apply_range(
3671                 struct isl_map *map1, struct isl_map *map2)
3672 {
3673         struct isl_dim *dim_result;
3674         struct isl_map *result;
3675         int i, j;
3676         unsigned nparam;
3677         unsigned n_in;
3678         unsigned n_out;
3679
3680         if (!map1 || !map2)
3681                 goto error;
3682
3683         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
3684                                   isl_dim_copy(map2->dim));
3685
3686         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
3687         if (!result)
3688                 goto error;
3689         for (i = 0; i < map1->n; ++i)
3690                 for (j = 0; j < map2->n; ++j) {
3691                         result = isl_map_add(result,
3692                             isl_basic_map_apply_range(
3693                                 isl_basic_map_copy(map1->p[i]),
3694                                 isl_basic_map_copy(map2->p[j])));
3695                         if (!result)
3696                                 goto error;
3697                 }
3698         isl_map_free(map1);
3699         isl_map_free(map2);
3700         if (result && result->n <= 1)
3701                 F_SET(result, ISL_MAP_DISJOINT);
3702         return result;
3703 error:
3704         isl_map_free(map1);
3705         isl_map_free(map2);
3706         return NULL;
3707 }
3708
3709 /*
3710  * returns range - domain
3711  */
3712 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
3713 {
3714         struct isl_basic_set *bset;
3715         unsigned dim;
3716         unsigned nparam;
3717         int i;
3718
3719         if (!bmap)
3720                 goto error;
3721         dim = isl_basic_map_n_in(bmap);
3722         nparam = isl_basic_map_n_param(bmap);
3723         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
3724         bset = isl_basic_set_from_basic_map(bmap);
3725         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
3726         bset = isl_basic_set_swap_vars(bset, 2*dim);
3727         for (i = 0; i < dim; ++i) {
3728                 int j = isl_basic_map_alloc_equality(
3729                                             (struct isl_basic_map *)bset);
3730                 if (j < 0)
3731                         goto error;
3732                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
3733                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
3734                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
3735                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
3736         }
3737         return isl_basic_set_project_out(bset, 2*dim, 0);
3738 error:
3739         isl_basic_map_free(bmap);
3740         return NULL;
3741 }
3742
3743 /*
3744  * returns range - domain
3745  */
3746 struct isl_set *isl_map_deltas(struct isl_map *map)
3747 {
3748         int i;
3749         struct isl_set *result;
3750
3751         if (!map)
3752                 return NULL;
3753
3754         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
3755         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
3756                                         isl_map_n_in(map), map->n, map->flags);
3757         if (!result)
3758                 goto error;
3759         for (i = 0; i < map->n; ++i)
3760                 result = isl_set_add(result,
3761                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
3762         isl_map_free(map);
3763         return result;
3764 error:
3765         isl_map_free(map);
3766         return NULL;
3767 }
3768
3769 /* If the only constraints a div d=floor(f/m)
3770  * appears in are its two defining constraints
3771  *
3772  *      f - m d >=0
3773  *      -(f - (m - 1)) + m d >= 0
3774  *
3775  * then it can safely be removed.
3776  */
3777 static int div_is_redundant(struct isl_basic_map *bmap, int div)
3778 {
3779         int i;
3780         unsigned pos = 1 + isl_dim_total(bmap->dim) + div;
3781
3782         for (i = 0; i < bmap->n_eq; ++i)
3783                 if (!isl_int_is_zero(bmap->eq[i][pos]))
3784                         return 0;
3785
3786         for (i = 0; i < bmap->n_ineq; ++i) {
3787                 if (isl_int_is_zero(bmap->ineq[i][pos]))
3788                         continue;
3789                 if (isl_int_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
3790                         int neg;
3791                         isl_int_sub(bmap->div[div][1],
3792                                         bmap->div[div][1], bmap->div[div][0]);
3793                         isl_int_add_ui(bmap->div[div][1], bmap->div[div][1], 1);
3794                         neg = isl_seq_is_neg(bmap->ineq[i], bmap->div[div]+1, pos);
3795                         isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);
3796                         isl_int_add(bmap->div[div][1],
3797                                         bmap->div[div][1], bmap->div[div][0]);
3798                         if (!neg)
3799                                 return 0;
3800                         if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
3801                                                     bmap->n_div-div-1) != -1)
3802                                 return 0;
3803                 } else if (isl_int_abs_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
3804                         if (!isl_seq_eq(bmap->ineq[i], bmap->div[div]+1, pos))
3805                                 return 0;
3806                         if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
3807                                                     bmap->n_div-div-1) != -1)
3808                                 return 0;
3809                 } else
3810                         return 0;
3811         }
3812
3813         for (i = 0; i < bmap->n_div; ++i)
3814                 if (!isl_int_is_zero(bmap->div[i][1+pos]))
3815                         return 0;
3816
3817         return 1;
3818 }
3819
3820 /*
3821  * Remove divs that don't occur in any of the constraints or other divs.
3822  * These can arise when dropping some of the variables in a quast
3823  * returned by piplib.
3824  */
3825 static struct isl_basic_map *remove_redundant_divs(struct isl_basic_map *bmap)
3826 {
3827         int i;
3828
3829         if (!bmap)
3830                 return NULL;
3831
3832         for (i = bmap->n_div-1; i >= 0; --i) {
3833                 if (!div_is_redundant(bmap, i))
3834                         continue;
3835                 bmap = isl_basic_map_drop_div(bmap, i);
3836         }
3837         return bmap;
3838 }
3839
3840 struct isl_basic_map *isl_basic_map_finalize(struct isl_basic_map *bmap)
3841 {
3842         bmap = remove_redundant_divs(bmap);
3843         if (!bmap)
3844                 return NULL;
3845         F_SET(bmap, ISL_BASIC_SET_FINAL);
3846         return bmap;
3847 }
3848
3849 struct isl_basic_set *isl_basic_set_finalize(struct isl_basic_set *bset)
3850 {
3851         return (struct isl_basic_set *)
3852                 isl_basic_map_finalize((struct isl_basic_map *)bset);
3853 }
3854
3855 struct isl_set *isl_set_finalize(struct isl_set *set)
3856 {
3857         int i;
3858
3859         if (!set)
3860                 return NULL;
3861         for (i = 0; i < set->n; ++i) {
3862                 set->p[i] = isl_basic_set_finalize(set->p[i]);
3863                 if (!set->p[i])
3864                         goto error;
3865         }
3866         return set;
3867 error:
3868         isl_set_free(set);
3869         return NULL;
3870 }
3871
3872 struct isl_map *isl_map_finalize(struct isl_map *map)
3873 {
3874         int i;
3875
3876         if (!map)
3877                 return NULL;
3878         for (i = 0; i < map->n; ++i) {
3879                 map->p[i] = isl_basic_map_finalize(map->p[i]);
3880                 if (!map->p[i])
3881                         goto error;
3882         }
3883         F_CLR(map, ISL_MAP_NORMALIZED);
3884         return map;
3885 error:
3886         isl_map_free(map);
3887         return NULL;
3888 }
3889
3890 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
3891 {
3892         struct isl_basic_map *bmap;
3893         unsigned nparam;
3894         unsigned dim;
3895         int i;
3896
3897         if (!dims)
3898                 return NULL;
3899
3900         nparam = dims->nparam;
3901         dim = dims->n_out;
3902         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
3903         if (!bmap)
3904                 goto error;
3905
3906         for (i = 0; i < dim; ++i) {
3907                 int j = isl_basic_map_alloc_equality(bmap);
3908                 if (j < 0)
3909                         goto error;
3910                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3911                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
3912                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
3913         }
3914         return isl_basic_map_finalize(bmap);
3915 error:
3916         isl_basic_map_free(bmap);
3917         return NULL;
3918 }
3919
3920 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
3921 {
3922         struct isl_dim *dim = isl_dim_map(set_dim);
3923         if (!dim)
3924                 return NULL;
3925         return basic_map_identity(dim);
3926 }
3927
3928 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
3929 {
3930         if (!model || !model->dim)
3931                 return NULL;
3932         isl_assert(model->ctx,
3933                         model->dim->n_in == model->dim->n_out, return NULL);
3934         return basic_map_identity(isl_dim_copy(model->dim));
3935 }
3936
3937 static struct isl_map *map_identity(struct isl_dim *dim)
3938 {
3939         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
3940         return isl_map_add(map, basic_map_identity(isl_dim_copy(dim)));
3941 }
3942
3943 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
3944 {
3945         struct isl_dim *dim = isl_dim_map(set_dim);
3946         if (!dim)
3947                 return NULL;
3948         return map_identity(dim);
3949 }
3950
3951 struct isl_map *isl_map_identity_like(struct isl_basic_map *model)
3952 {
3953         if (!model || !model->dim)
3954                 return NULL;
3955         isl_assert(model->ctx,
3956                         model->dim->n_in == model->dim->n_out, return NULL);
3957         return map_identity(isl_dim_copy(model->dim));
3958 }
3959
3960 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
3961 {
3962         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
3963 }
3964
3965 int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
3966 {
3967         return isl_map_is_subset(
3968                         (struct isl_map *)set1, (struct isl_map *)set2);
3969 }
3970
3971 int isl_basic_map_is_subset(
3972                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3973 {
3974         int is_subset;
3975         struct isl_map *map1;
3976         struct isl_map *map2;
3977
3978         if (!bmap1 || !bmap2)
3979                 return -1;
3980
3981         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
3982         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
3983
3984         is_subset = isl_map_is_subset(map1, map2);
3985
3986         isl_map_free(map1);
3987         isl_map_free(map2);
3988
3989         return is_subset;
3990 }
3991
3992 int isl_basic_map_is_equal(
3993                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3994 {
3995         int is_subset;
3996
3997         if (!bmap1 || !bmap2)
3998                 return -1;
3999         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4000         if (is_subset != 1)
4001                 return is_subset;
4002         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4003         return is_subset;
4004 }
4005
4006 int isl_basic_set_is_equal(
4007                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4008 {
4009         return isl_basic_map_is_equal(
4010                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4011 }
4012
4013 int isl_map_is_empty(struct isl_map *map)
4014 {
4015         int i;
4016         int is_empty;
4017
4018         if (!map)
4019                 return -1;
4020         for (i = 0; i < map->n; ++i) {
4021                 is_empty = isl_basic_map_is_empty(map->p[i]);
4022                 if (is_empty < 0)
4023                         return -1;
4024                 if (!is_empty)
4025                         return 0;
4026         }
4027         return 1;
4028 }
4029
4030 int isl_set_is_empty(struct isl_set *set)
4031 {
4032         return isl_map_is_empty((struct isl_map *)set);
4033 }
4034
4035 int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2)
4036 {
4037         int i;
4038         int is_subset = 0;
4039         struct isl_map *diff;
4040
4041         if (!map1 || !map2)
4042                 return -1;
4043
4044         if (isl_map_is_empty(map1))
4045                 return 1;
4046
4047         if (isl_map_is_empty(map2))
4048                 return 0;
4049
4050         diff = isl_map_subtract(isl_map_copy(map1), isl_map_copy(map2));
4051         if (!diff)
4052                 return -1;
4053
4054         is_subset = isl_map_is_empty(diff);
4055         isl_map_free(diff);
4056
4057         return is_subset;
4058 }
4059
4060 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4061 {
4062         int is_subset;
4063
4064         if (!map1 || !map2)
4065                 return -1;
4066         is_subset = isl_map_is_subset(map1, map2);
4067         if (is_subset != 1)
4068                 return is_subset;
4069         is_subset = isl_map_is_subset(map2, map1);
4070         return is_subset;
4071 }
4072
4073 int isl_basic_map_is_strict_subset(
4074                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4075 {
4076         int is_subset;
4077
4078         if (!bmap1 || !bmap2)
4079                 return -1;
4080         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4081         if (is_subset != 1)
4082                 return is_subset;
4083         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4084         if (is_subset == -1)
4085                 return is_subset;
4086         return !is_subset;
4087 }
4088
4089 static int basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
4090 {
4091         int i;
4092         unsigned total;
4093         isl_int s;
4094
4095         total = 1 + isl_basic_map_total_dim(bmap);
4096         if (total != vec->size)
4097                 return -1;
4098
4099         isl_int_init(s);
4100
4101         for (i = 0; i < bmap->n_eq; ++i) {
4102                 isl_seq_inner_product(vec->block.data, bmap->eq[i], total, &s);
4103                 if (!isl_int_is_zero(s)) {
4104                         isl_int_clear(s);
4105                         return 0;
4106                 }
4107         }
4108
4109         for (i = 0; i < bmap->n_ineq; ++i) {
4110                 isl_seq_inner_product(vec->block.data, bmap->ineq[i], total, &s);
4111                 if (isl_int_is_neg(s)) {
4112                         isl_int_clear(s);
4113                         return 0;
4114                 }
4115         }
4116
4117         isl_int_clear(s);
4118
4119         return 1;
4120 }
4121
4122 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4123 {
4124         if (!bmap)
4125                 return -1;
4126         return bmap->n_eq == 0 && bmap->n_ineq == 0;
4127 }
4128
4129 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4130 {
4131         struct isl_basic_set *bset = NULL;
4132         struct isl_vec *sample = NULL;
4133         int empty;
4134         unsigned total;
4135
4136         if (!bmap)
4137                 return -1;
4138
4139         if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4140                 return 1;
4141
4142         if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4143                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4144                 copy = isl_basic_map_convex_hull(copy);
4145                 empty = F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4146                 isl_basic_map_free(copy);
4147                 return empty;
4148         }
4149
4150         total = 1 + isl_basic_map_total_dim(bmap);
4151         if (bmap->sample && bmap->sample->size == total) {
4152                 int contains = basic_map_contains(bmap, bmap->sample);
4153                 if (contains < 0)
4154                         return -1;
4155                 if (contains)
4156                         return 0;
4157         }
4158         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4159         if (!bset)
4160                 return -1;
4161         sample = isl_basic_set_sample(bset);
4162         if (!sample)
4163                 return -1;
4164         empty = sample->size == 0;
4165         if (bmap->sample)
4166                 isl_vec_free(bmap->ctx, bmap->sample);
4167         bmap->sample = sample;
4168
4169         return empty;
4170 }
4171
4172 struct isl_map *isl_basic_map_union(
4173         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4174 {
4175         struct isl_map *map;
4176         if (!bmap1 || !bmap2)
4177                 return NULL;
4178
4179         isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
4180
4181         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
4182         if (!map)
4183                 goto error;
4184         map = isl_map_add(map, bmap1);
4185         map = isl_map_add(map, bmap2);
4186         return map;
4187 error:
4188         isl_basic_map_free(bmap1);
4189         isl_basic_map_free(bmap2);
4190         return NULL;
4191 }
4192
4193 struct isl_set *isl_basic_set_union(
4194                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4195 {
4196         return (struct isl_set *)isl_basic_map_union(
4197                                             (struct isl_basic_map *)bset1,
4198                                             (struct isl_basic_map *)bset2);
4199 }
4200
4201 /* Order divs such that any div only depends on previous divs */
4202 static struct isl_basic_map *order_divs(struct isl_basic_map *bmap)
4203 {
4204         int i;
4205         unsigned off = isl_dim_total(bmap->dim);
4206
4207         for (i = 0; i < bmap->n_div; ++i) {
4208                 int pos;
4209                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
4210                                                             bmap->n_div-i);
4211                 if (pos == -1)
4212                         continue;
4213                 swap_div(bmap, i, pos);
4214                 --i;
4215         }
4216         return bmap;
4217 }
4218
4219 static int find_div(struct isl_basic_map *dst,
4220                         struct isl_basic_map *src, unsigned div)
4221 {
4222         int i;
4223
4224         unsigned total = isl_basic_map_total_dim(src);
4225
4226         for (i = 0; i < dst->n_div; ++i)
4227                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total) &&
4228                     isl_seq_first_non_zero(dst->div[i]+1+1+total,
4229                                                 dst->n_div - src->n_div) == -1)
4230                         return i;
4231         return -1;
4232 }
4233
4234 struct isl_basic_map *isl_basic_map_align_divs(
4235                 struct isl_basic_map *dst, struct isl_basic_map *src)
4236 {
4237         int i;
4238         unsigned total = isl_basic_map_total_dim(src);
4239
4240         if (!dst || !src)
4241                 goto error;
4242
4243         if (src->n_div == 0)
4244                 return dst;
4245
4246         src = order_divs(src);
4247         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
4248                         src->n_div, 0, 2 * src->n_div);
4249         if (!dst)
4250                 return NULL;
4251         for (i = 0; i < src->n_div; ++i) {
4252                 int j = find_div(dst, src, i);
4253                 if (j < 0) {
4254                         j = isl_basic_map_alloc_div(dst);
4255                         if (j < 0)
4256                                 goto error;
4257                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
4258                         isl_seq_clr(dst->div[j]+1+1+total,
4259                                                     dst->n_div - src->n_div);
4260                         if (add_div_constraints(dst, j) < 0)
4261                                 goto error;
4262                 }
4263                 if (j != i)
4264                         swap_div(dst, i, j);
4265         }
4266         return dst;
4267 error:
4268         isl_basic_map_free(dst);
4269         return NULL;
4270 }
4271
4272 struct isl_basic_set *isl_basic_set_align_divs(
4273                 struct isl_basic_set *dst, struct isl_basic_set *src)
4274 {
4275         return (struct isl_basic_set *)isl_basic_map_align_divs(
4276                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
4277 }
4278
4279 struct isl_map *isl_map_align_divs(struct isl_map *map)
4280 {
4281         int i;
4282
4283         map = isl_map_compute_divs(map);
4284         map = isl_map_cow(map);
4285         if (!map)
4286                 return NULL;
4287
4288         for (i = 1; i < map->n; ++i)
4289                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
4290         for (i = 1; i < map->n; ++i)
4291                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
4292
4293         F_CLR(map, ISL_MAP_NORMALIZED);
4294         return map;
4295 }
4296
4297 static struct isl_map *add_cut_constraint(struct isl_map *dst,
4298                 struct isl_basic_map *src, isl_int *c,
4299                 unsigned len, int oppose)
4300 {
4301         struct isl_basic_map *copy = NULL;
4302         int is_empty;
4303         int k;
4304         unsigned total;
4305
4306         copy = isl_basic_map_copy(src);
4307         copy = isl_basic_map_cow(copy);
4308         if (!copy)
4309                 goto error;
4310         copy = isl_basic_map_extend_constraints(copy, 0, 1);
4311         k = isl_basic_map_alloc_inequality(copy);
4312         if (k < 0)
4313                 goto error;
4314         if (oppose)
4315                 isl_seq_neg(copy->ineq[k], c, len);
4316         else
4317                 isl_seq_cpy(copy->ineq[k], c, len);
4318         total = 1 + isl_basic_map_total_dim(copy);
4319         isl_seq_clr(copy->ineq[k]+len, total - len);
4320         isl_inequality_negate(copy, k);
4321         copy = isl_basic_map_simplify(copy);
4322         copy = isl_basic_map_finalize(copy);
4323         is_empty = isl_basic_map_is_empty(copy);
4324         if (is_empty < 0)
4325                 goto error;
4326         if (!is_empty)
4327                 dst = isl_map_add(dst, copy);
4328         else
4329                 isl_basic_map_free(copy);
4330         return dst;
4331 error:
4332         isl_basic_map_free(copy);
4333         isl_map_free(dst);
4334         return NULL;
4335 }
4336
4337 static struct isl_map *subtract(struct isl_map *map, struct isl_basic_map *bmap)
4338 {
4339         int i, j, k;
4340         unsigned flags = 0;
4341         struct isl_map *rest = NULL;
4342         unsigned max;
4343         unsigned total = isl_basic_map_total_dim(bmap);
4344
4345         assert(bmap);
4346
4347         if (!map)
4348                 goto error;
4349
4350         if (F_ISSET(map, ISL_MAP_DISJOINT))
4351                 FL_SET(flags, ISL_MAP_DISJOINT);
4352
4353         max = map->n * (2 * bmap->n_eq + bmap->n_ineq);
4354         rest = isl_map_alloc_dim(isl_dim_copy(map->dim), max, flags);
4355         if (!rest)
4356                 goto error;
4357
4358         for (i = 0; i < map->n; ++i) {
4359                 map->p[i] = isl_basic_map_align_divs(map->p[i], bmap);
4360                 if (!map->p[i])
4361                         goto error;
4362         }
4363
4364         for (j = 0; j < map->n; ++j)
4365                 map->p[j] = isl_basic_map_cow(map->p[j]);
4366
4367         for (i = 0; i < bmap->n_eq; ++i) {
4368                 for (j = 0; j < map->n; ++j) {
4369                         rest = add_cut_constraint(rest,
4370                                 map->p[j], bmap->eq[i], 1+total, 0);
4371                         if (!rest)
4372                                 goto error;
4373
4374                         rest = add_cut_constraint(rest,
4375                                 map->p[j], bmap->eq[i], 1+total, 1);
4376                         if (!rest)
4377                                 goto error;
4378
4379                         map->p[j] = isl_basic_map_extend_constraints(map->p[j],
4380                                 1, 0);
4381                         if (!map->p[j])
4382                                 goto error;
4383                         k = isl_basic_map_alloc_equality(map->p[j]);
4384                         if (k < 0)
4385                                 goto error;
4386                         isl_seq_cpy(map->p[j]->eq[k], bmap->eq[i], 1+total);
4387                         isl_seq_clr(map->p[j]->eq[k]+1+total,
4388                                         map->p[j]->n_div - bmap->n_div);
4389                 }
4390         }
4391
4392         for (i = 0; i < bmap->n_ineq; ++i) {
4393                 for (j = 0; j < map->n; ++j) {
4394                         rest = add_cut_constraint(rest,
4395                                 map->p[j], bmap->ineq[i], 1+total, 0);
4396                         if (!rest)
4397                                 goto error;
4398
4399                         map->p[j] = isl_basic_map_extend_constraints(map->p[j],
4400                                 0, 1);
4401                         if (!map->p[j])
4402                                 goto error;
4403                         k = isl_basic_map_alloc_inequality(map->p[j]);
4404                         if (k < 0)
4405                                 goto error;
4406                         isl_seq_cpy(map->p[j]->ineq[k], bmap->ineq[i], 1+total);
4407                         isl_seq_clr(map->p[j]->ineq[k]+1+total,
4408                                         map->p[j]->n_div - bmap->n_div);
4409                 }
4410         }
4411
4412         isl_map_free(map);
4413         return rest;
4414 error:
4415         isl_map_free(map);
4416         isl_map_free(rest);
4417         return NULL;
4418 }
4419
4420 struct isl_map *isl_map_subtract(struct isl_map *map1, struct isl_map *map2)
4421 {
4422         int i;
4423         if (!map1 || !map2)
4424                 goto error;
4425
4426         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4427
4428         if (isl_map_is_empty(map2)) {
4429                 isl_map_free(map2);
4430                 return map1;
4431         }
4432
4433         map1 = isl_map_compute_divs(map1);
4434         map2 = isl_map_compute_divs(map2);
4435         if (!map1 || !map2)
4436                 goto error;
4437
4438         for (i = 0; map1 && i < map2->n; ++i)
4439                 map1 = subtract(map1, map2->p[i]);
4440
4441         isl_map_free(map2);
4442         return map1;
4443 error:
4444         isl_map_free(map1);
4445         isl_map_free(map2);
4446         return NULL;
4447 }
4448
4449 struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2)
4450 {
4451         return (struct isl_set *)
4452                 isl_map_subtract(
4453                         (struct isl_map *)set1, (struct isl_map *)set2);
4454 }
4455
4456 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
4457 {
4458         if (!set || !map)
4459                 goto error;
4460         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
4461         map = isl_map_intersect_domain(map, set);
4462         set = isl_map_range(map);
4463         return set;
4464 error:
4465         isl_set_free(set);
4466         isl_map_free(map);
4467         return NULL;
4468 }
4469
4470 /* There is no need to cow as removing empty parts doesn't change
4471  * the meaning of the set.
4472  */
4473 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
4474 {
4475         int i;
4476
4477         if (!map)
4478                 return NULL;
4479
4480         for (i = map->n-1; i >= 0; --i) {
4481                 if (!F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
4482                         continue;
4483                 isl_basic_map_free(map->p[i]);
4484                 if (i != map->n-1) {
4485                         F_CLR(map, ISL_MAP_NORMALIZED);
4486                         map->p[i] = map->p[map->n-1];
4487                 }
4488                 map->n--;
4489         }
4490
4491         return map;
4492 }
4493
4494 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
4495 {
4496         return (struct isl_set *)
4497                 isl_map_remove_empty_parts((struct isl_map *)set);
4498 }
4499
4500 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
4501 {
4502         struct isl_basic_set *bset;
4503         if (!set || set->n == 0)
4504                 return NULL;
4505         bset = set->p[set->n-1];
4506         isl_assert(set->ctx, F_ISSET(bset, ISL_BASIC_SET_FINAL), return NULL);
4507         return isl_basic_set_copy(bset);
4508 }
4509
4510 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
4511                                                 struct isl_basic_set *bset)
4512 {
4513         int i;
4514
4515         if (!set || !bset)
4516                 goto error;
4517         for (i = set->n-1; i >= 0; --i) {
4518                 if (set->p[i] != bset)
4519                         continue;
4520                 set = isl_set_cow(set);
4521                 if (!set)
4522                         goto error;
4523                 isl_basic_set_free(set->p[i]);
4524                 if (i != set->n-1) {
4525                         F_CLR(set, ISL_SET_NORMALIZED);
4526                         set->p[i] = set->p[set->n-1];
4527                 }
4528                 set->n--;
4529                 return set;
4530         }
4531         isl_basic_set_free(bset);
4532         return set;
4533 error:
4534         isl_set_free(set);
4535         isl_basic_set_free(bset);
4536         return NULL;
4537 }
4538
4539 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
4540  * for any common value of the parameters and dimensions preceding dim
4541  * in both basic sets, the values of dimension pos in bset1 are
4542  * smaller or larger than those in bset2.
4543  *
4544  * Returns
4545  *       1 if bset1 follows bset2
4546  *      -1 if bset1 precedes bset2
4547  *       0 if bset1 and bset2 are incomparable
4548  *      -2 if some error occurred.
4549  */
4550 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
4551         struct isl_basic_set *bset2, int pos)
4552 {
4553         struct isl_dim *dims;
4554         struct isl_basic_map *bmap1 = NULL;
4555         struct isl_basic_map *bmap2 = NULL;
4556         struct isl_ctx *ctx;
4557         struct isl_vec *obj;
4558         unsigned total;
4559         unsigned nparam;
4560         unsigned dim1, dim2;
4561         isl_int num, den;
4562         enum isl_lp_result res;
4563         int cmp;
4564
4565         if (!bset1 || !bset2)
4566                 return -2;
4567
4568         nparam = isl_basic_set_n_param(bset1);
4569         dim1 = isl_basic_set_n_dim(bset1);
4570         dim2 = isl_basic_set_n_dim(bset2);
4571         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
4572         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
4573         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
4574         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
4575         if (!bmap1 || !bmap2)
4576                 goto error;
4577         bmap1 = isl_basic_map_extend(bmap1, nparam,
4578                         pos, (dim1 - pos) + (dim2 - pos),
4579                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
4580         if (!bmap1)
4581                 goto error;
4582         total = isl_basic_map_total_dim(bmap1);
4583         ctx = bmap1->ctx;
4584         obj = isl_vec_alloc(ctx, total);
4585         isl_seq_clr(obj->block.data, total);
4586         isl_int_set_si(obj->block.data[nparam+pos], 1);
4587         isl_int_set_si(obj->block.data[nparam+pos+(dim1-pos)], -1);
4588         if (!obj)
4589                 goto error;
4590         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
4591         isl_int_init(num);
4592         isl_int_init(den);
4593         res = isl_solve_lp(bmap1, 0, obj->block.data, ctx->one, &num, &den);
4594         if (res == isl_lp_empty)
4595                 cmp = 0;
4596         else if (res == isl_lp_ok && isl_int_is_pos(num))
4597                 cmp = 1;
4598         else if ((res == isl_lp_ok && isl_int_is_neg(num)) ||
4599                   res == isl_lp_unbounded)
4600                 cmp = -1;
4601         else
4602                 cmp = -2;
4603         isl_int_clear(num);
4604         isl_int_clear(den);
4605         isl_basic_map_free(bmap1);
4606         isl_vec_free(ctx, obj);
4607         return cmp;
4608 error:
4609         isl_basic_map_free(bmap1);
4610         isl_basic_map_free(bmap2);
4611         return -2;
4612 }
4613
4614 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
4615         unsigned pos, isl_int *val)
4616 {
4617         int i;
4618         int d;
4619         unsigned total;
4620
4621         if (!bmap)
4622                 return -1;
4623         total = isl_basic_map_total_dim(bmap);
4624         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
4625                 for (; d+1 > pos; --d)
4626                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
4627                                 break;
4628                 if (d != pos)
4629                         continue;
4630                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
4631                         return 0;
4632                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
4633                         return 0;
4634                 if (!isl_int_is_one(bmap->eq[i][1+d]))
4635                         return 0;
4636                 if (val)
4637                         isl_int_neg(*val, bmap->eq[i][0]);
4638                 return 1;
4639         }
4640         return 0;
4641 }
4642
4643 static int isl_map_fast_has_fixed_var(struct isl_map *map,
4644         unsigned pos, isl_int *val)
4645 {
4646         int i;
4647         isl_int v;
4648         isl_int tmp;
4649         int fixed;
4650
4651         if (!map)
4652                 return -1;
4653         if (map->n == 0)
4654                 return 0;
4655         if (map->n == 1)
4656                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
4657         isl_int_init(v);
4658         isl_int_init(tmp);
4659         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
4660         for (i = 1; fixed == 1 && i < map->n; ++i) {
4661                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
4662                 if (fixed == 1 && isl_int_ne(tmp, v))
4663                         fixed = 0;
4664         }
4665         if (val)
4666                 isl_int_set(*val, v);
4667         isl_int_clear(tmp);
4668         isl_int_clear(v);
4669         return fixed;
4670 }
4671
4672 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
4673         isl_int *val)
4674 {
4675         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
4676 }
4677
4678 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4679  * then return this fixed value in *val.
4680  */
4681 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
4682 {
4683         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
4684 }
4685
4686 /* Check if input variable in has fixed value and if so and if val is not NULL,
4687  * then return this fixed value in *val.
4688  */
4689 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
4690 {
4691         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
4692 }
4693
4694 /* Check if dimension dim has an (obvious) fixed lower bound and if so
4695  * and if val is not NULL, then return this lower bound in *val.
4696  */
4697 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
4698         unsigned dim, isl_int *val)
4699 {
4700         int i, i_eq = -1, i_ineq = -1;
4701         isl_int *c;
4702         unsigned total;
4703         unsigned nparam;
4704
4705         if (!bset)
4706                 return -1;
4707         total = isl_basic_set_total_dim(bset);
4708         nparam = isl_basic_set_n_param(bset);
4709         for (i = 0; i < bset->n_eq; ++i) {
4710                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
4711                         continue;
4712                 if (i_eq != -1)
4713                         return 0;
4714                 i_eq = i;
4715         }
4716         for (i = 0; i < bset->n_ineq; ++i) {
4717                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
4718                         continue;
4719                 if (i_eq != -1 || i_ineq != -1)
4720                         return 0;
4721                 i_ineq = i;
4722         }
4723         if (i_eq == -1 && i_ineq == -1)
4724                 return 0;
4725         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
4726         /* The coefficient should always be one due to normalization. */
4727         if (!isl_int_is_one(c[1+nparam+dim]))
4728                 return 0;
4729         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
4730                 return 0;
4731         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
4732                                         total - nparam - dim - 1) != -1)
4733                 return 0;
4734         if (val)
4735                 isl_int_neg(*val, c[0]);
4736         return 1;
4737 }
4738
4739 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
4740         unsigned dim, isl_int *val)
4741 {
4742         int i;
4743         isl_int v;
4744         isl_int tmp;
4745         int fixed;
4746
4747         if (!set)
4748                 return -1;
4749         if (set->n == 0)
4750                 return 0;
4751         if (set->n == 1)
4752                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4753                                                                 dim, val);
4754         isl_int_init(v);
4755         isl_int_init(tmp);
4756         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4757                                                                 dim, &v);
4758         for (i = 1; fixed == 1 && i < set->n; ++i) {
4759                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
4760                                                                 dim, &tmp);
4761                 if (fixed == 1 && isl_int_ne(tmp, v))
4762                         fixed = 0;
4763         }
4764         if (val)
4765                 isl_int_set(*val, v);
4766         isl_int_clear(tmp);
4767         isl_int_clear(v);
4768         return fixed;
4769 }
4770
4771 static struct isl_basic_set *isl_basic_set_reduce_using_equalities(
4772         struct isl_basic_set *bset, struct isl_basic_set *context)
4773 {
4774         int i;
4775         int *elim;
4776
4777         if (!bset || !context)
4778                 goto error;
4779
4780         bset = isl_basic_set_cow(bset);
4781         if (!bset)
4782                 goto error;
4783
4784         elim = isl_alloc_array(ctx, int, isl_basic_set_n_dim(bset));
4785         if (!elim)
4786                 goto error;
4787         set_compute_elimination_index(context, elim);
4788         for (i = 0; i < bset->n_eq; ++i)
4789                 set_reduced_using_equalities(bset->eq[i], bset->eq[i],
4790                                                         context, elim);
4791         for (i = 0; i < bset->n_ineq; ++i)
4792                 set_reduced_using_equalities(bset->ineq[i], bset->ineq[i],
4793                                                         context, elim);
4794         isl_basic_set_free(context);
4795         free(elim);
4796         bset = isl_basic_set_simplify(bset);
4797         bset = isl_basic_set_finalize(bset);
4798         return bset;
4799 error:
4800         isl_basic_set_free(bset);
4801         isl_basic_set_free(context);
4802         return NULL;
4803 }
4804
4805 static struct isl_basic_set *remove_shifted_constraints(
4806         struct isl_basic_set *bset, struct isl_basic_set *context)
4807 {
4808         unsigned int size;
4809         isl_int ***index;
4810         int bits;
4811         int k, h, l;
4812
4813         if (!bset)
4814                 return NULL;
4815
4816         size = round_up(4 * (context->n_ineq+1) / 3 - 1);
4817         bits = ffs(size) - 1;
4818         index = isl_calloc_array(ctx, isl_int **, size);
4819         if (!index)
4820                 return bset;
4821
4822         for (k = 0; k < context->n_ineq; ++k) {
4823                 h = set_hash_index(index, size, bits, context, k);
4824                 index[h] = &context->ineq[k];
4825         }
4826         for (k = 0; k < bset->n_ineq; ++k) {
4827                 h = set_hash_index(index, size, bits, bset, k);
4828                 if (!index[h])
4829                         continue;
4830                 l = index[h] - &context->ineq[0];
4831                 if (isl_int_lt(bset->ineq[k][0], context->ineq[l][0]))
4832                         continue;
4833                 bset = isl_basic_set_cow(bset);
4834                 if (!bset)
4835                         goto error;
4836                 isl_basic_set_drop_inequality(bset, k);
4837                 --k;
4838         }
4839         free(index);
4840         return bset;
4841 error:
4842         free(index);
4843         return bset;
4844 }
4845
4846 /* Remove all information from bset that is redundant in the context
4847  * of context.  In particular, equalities that are linear combinations
4848  * of those in context are removed.  Then the inequalities that are
4849  * redundant in the context of the equalities and inequalities of
4850  * context are removed.
4851  */
4852 static struct isl_basic_set *uset_gist(struct isl_basic_set *bset,
4853         struct isl_basic_set *context)
4854 {
4855         int i;
4856         isl_int opt;
4857         struct isl_basic_set *combined;
4858         struct isl_ctx *ctx;
4859
4860         if (!bset || !context)
4861                 goto error;
4862
4863         if (context->n_eq > 0) {
4864                 struct isl_mat *T;
4865                 struct isl_mat *T2;
4866                 struct isl_ctx *ctx = context->ctx;
4867                 struct isl_basic_set *reduced_context;
4868                 reduced_context = isl_basic_set_remove_equalities(
4869                                         isl_basic_set_copy(context), &T, &T2);
4870                 if (!reduced_context)
4871                         goto error;
4872                 bset = isl_basic_set_preimage(ctx, bset, T);
4873                 bset = uset_gist(bset, reduced_context);
4874                 bset = isl_basic_set_preimage(ctx, bset, T2);
4875                 bset = isl_basic_set_reduce_using_equalities(bset, context);
4876                 return bset;
4877         }
4878         if (!context->n_ineq)
4879                 goto done;
4880         bset = remove_shifted_constraints(bset, context);
4881         combined = isl_basic_set_extend_constraints(isl_basic_set_copy(bset),
4882                         context->n_eq, context->n_ineq);
4883         context = set_add_constraints(combined, context, 0);
4884         if (!context)
4885                 goto error;
4886         ctx = context->ctx;
4887         isl_int_init(opt);
4888         for (i = bset->n_ineq-1; i >= 0; --i) {
4889                 int redundant;
4890                 set_swap_inequality(context, i, context->n_ineq-1);
4891                 context->n_ineq--;
4892                 redundant = isl_basic_set_constraint_is_redundant(&context,
4893                                 context->ineq[context->n_ineq], &opt, NULL);
4894                 if (redundant == -1) {
4895                         isl_int_clear(opt);
4896                         goto error;
4897                 }
4898                 if (F_ISSET(context, ISL_BASIC_MAP_EMPTY)) {
4899                         bset = isl_basic_set_set_to_empty(bset);
4900                         break;
4901                 }
4902                 context->n_ineq++;
4903                 set_swap_inequality(context, i, context->n_ineq-1);
4904                 if (redundant) {
4905                         isl_basic_set_drop_inequality(context, i);
4906                         isl_basic_set_drop_inequality(bset, i);
4907                 }
4908         }
4909         isl_int_clear(opt);
4910 done:
4911         isl_basic_set_free(context);
4912         return bset;
4913 error:
4914         isl_basic_set_free(context);
4915         isl_basic_set_free(bset);
4916         return NULL;
4917 }
4918
4919 struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap,
4920         struct isl_basic_map *context)
4921 {
4922         struct isl_basic_set *bset;
4923
4924         if (!bmap || !context)
4925                 goto error;
4926
4927         context = isl_basic_map_align_divs(context, bmap);
4928         bmap = isl_basic_map_align_divs(bmap, context);
4929
4930         bset = uset_gist(isl_basic_map_underlying_set(isl_basic_map_copy(bmap)),
4931                          isl_basic_map_underlying_set(context));
4932
4933         return isl_basic_map_overlying_set(bset, bmap);
4934 error:
4935         isl_basic_map_free(bmap);
4936         isl_basic_map_free(context);
4937         return NULL;
4938 }
4939
4940 struct isl_map *isl_map_gist(struct isl_map *map, struct isl_basic_map *context)
4941 {
4942         int i;
4943
4944         map = isl_map_cow(map);
4945         if (!map || !context)
4946                 return NULL;
4947         isl_assert(map->ctx, isl_dim_equal(map->dim, context->dim), goto error);
4948         for (i = 0; i < map->n; ++i)
4949                 context = isl_basic_map_align_divs(context, map->p[i]);
4950         for (i = 0; i < map->n; ++i) {
4951                 map->p[i] = isl_basic_map_gist(map->p[i],
4952                                                 isl_basic_map_copy(context));
4953                 if (!map->p[i])
4954                         goto error;
4955         }
4956         isl_basic_map_free(context);
4957         F_CLR(map, ISL_MAP_NORMALIZED);
4958         return map;
4959 error:
4960         isl_map_free(map);
4961         isl_basic_map_free(context);
4962         return NULL;
4963 }
4964
4965 struct isl_basic_set *isl_basic_set_gist(struct isl_basic_set *bset,
4966                                                 struct isl_basic_set *context)
4967 {
4968         return (struct isl_basic_set *)isl_basic_map_gist(
4969                 (struct isl_basic_map *)bset, (struct isl_basic_map *)context);
4970 }
4971
4972 struct isl_set *isl_set_gist(struct isl_set *set, struct isl_basic_set *context)
4973 {
4974         return (struct isl_set *)isl_map_gist((struct isl_map *)set,
4975                                         (struct isl_basic_map *)context);
4976 }
4977
4978 struct constraint {
4979         unsigned        size;
4980         isl_int         *c;
4981 };
4982
4983 static int qsort_constraint_cmp(const void *p1, const void *p2)
4984 {
4985         const struct constraint *c1 = (const struct constraint *)p1;
4986         const struct constraint *c2 = (const struct constraint *)p2;
4987         unsigned size = isl_min(c1->size, c2->size);
4988         return isl_seq_cmp(c1->c, c2->c, size);
4989 }
4990
4991 static struct isl_basic_map *isl_basic_map_sort_constraints(
4992         struct isl_basic_map *bmap)
4993 {
4994         int i;
4995         struct constraint *c;
4996         unsigned total;
4997
4998         if (!bmap)
4999                 return NULL;
5000         total = isl_basic_map_total_dim(bmap);
5001         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5002         if (!c)
5003                 goto error;
5004         for (i = 0; i < bmap->n_ineq; ++i) {
5005                 c[i].size = total;
5006                 c[i].c = bmap->ineq[i];
5007         }
5008         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5009         for (i = 0; i < bmap->n_ineq; ++i)
5010                 bmap->ineq[i] = c[i].c;
5011         free(c);
5012         return bmap;
5013 error:
5014         isl_basic_map_free(bmap);
5015         return NULL;
5016 }
5017
5018 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5019 {
5020         if (!bmap)
5021                 return NULL;
5022         if (F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5023                 return bmap;
5024         bmap = isl_basic_map_convex_hull(bmap);
5025         bmap = isl_basic_map_sort_constraints(bmap);
5026         F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5027         return bmap;
5028 }
5029
5030 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5031 {
5032         return (struct isl_basic_set *)isl_basic_map_normalize(
5033                                                 (struct isl_basic_map *)bset);
5034 }
5035
5036 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5037         const struct isl_basic_map *bmap2)
5038 {
5039         int i, cmp;
5040         unsigned total;
5041
5042         if (bmap1 == bmap2)
5043                 return 0;
5044         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5045                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5046         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5047                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5048         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5049                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5050         if (F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5051             F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5052                 return 0;
5053         if (F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5054                 return 1;
5055         if (F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5056                 return -1;
5057         if (bmap1->n_eq != bmap2->n_eq)
5058                 return bmap1->n_eq - bmap2->n_eq;
5059         if (bmap1->n_ineq != bmap2->n_ineq)
5060                 return bmap1->n_ineq - bmap2->n_ineq;
5061         if (bmap1->n_div != bmap2->n_div)
5062                 return bmap1->n_div - bmap2->n_div;
5063         total = isl_basic_map_total_dim(bmap1);
5064         for (i = 0; i < bmap1->n_eq; ++i) {
5065                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5066                 if (cmp)
5067                         return cmp;
5068         }
5069         for (i = 0; i < bmap1->n_ineq; ++i) {
5070                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5071                 if (cmp)
5072                         return cmp;
5073         }
5074         for (i = 0; i < bmap1->n_div; ++i) {
5075                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5076                 if (cmp)
5077                         return cmp;
5078         }
5079         return 0;
5080 }
5081
5082 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5083         struct isl_basic_map *bmap2)
5084 {
5085         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5086 }
5087
5088 static int qsort_bmap_cmp(const void *p1, const void *p2)
5089 {
5090         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5091         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5092
5093         return isl_basic_map_fast_cmp(bmap1, bmap2);
5094 }
5095
5096 /* We normalize in place, but if anything goes wrong we need
5097  * to return NULL, so we need to make sure we don't change the
5098  * meaning of any possible other copies of map.
5099  */
5100 struct isl_map *isl_map_normalize(struct isl_map *map)
5101 {
5102         int i, j;
5103         struct isl_basic_map *bmap;
5104
5105         if (!map)
5106                 return NULL;
5107         if (F_ISSET(map, ISL_MAP_NORMALIZED))
5108                 return map;
5109         for (i = 0; i < map->n; ++i) {
5110                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5111                 if (!bmap)
5112                         goto error;
5113                 isl_basic_map_free(map->p[i]);
5114                 map->p[i] = bmap;
5115         }
5116         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5117         F_SET(map, ISL_MAP_NORMALIZED);
5118         map = isl_map_remove_empty_parts(map);
5119         if (!map)
5120                 return NULL;
5121         for (i = map->n - 1; i >= 1; --i) {
5122                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5123                         continue;
5124                 isl_basic_map_free(map->p[i-1]);
5125                 for (j = i; j < map->n; ++j)
5126                         map->p[j-1] = map->p[j];
5127                 map->n--;
5128         }
5129         return map;
5130 error:
5131         isl_map_free(map);
5132         return NULL;
5133
5134 }
5135
5136 struct isl_set *isl_set_normalize(struct isl_set *set)
5137 {
5138         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5139 }
5140
5141 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5142 {
5143         int i;
5144         int equal;
5145
5146         if (!map1 || !map2)
5147                 return -1;
5148
5149         if (map1 == map2)
5150                 return 1;
5151         if (!isl_dim_equal(map1->dim, map2->dim))
5152                 return 0;
5153
5154         map1 = isl_map_copy(map1);
5155         map2 = isl_map_copy(map2);
5156         map1 = isl_map_normalize(map1);
5157         map2 = isl_map_normalize(map2);
5158         if (!map1 || !map2)
5159                 goto error;
5160         equal = map1->n == map2->n;
5161         for (i = 0; equal && i < map1->n; ++i) {
5162                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5163                 if (equal < 0)
5164                         goto error;
5165         }
5166         isl_map_free(map1);
5167         isl_map_free(map2);
5168         return equal;
5169 error:
5170         isl_map_free(map1);
5171         isl_map_free(map2);
5172         return -1;
5173 }
5174
5175 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5176 {
5177         return isl_map_fast_is_equal((struct isl_map *)set1,
5178                                                 (struct isl_map *)set2);
5179 }
5180
5181 /* Return an interval that ranges from min to max (inclusive)
5182  */
5183 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5184         isl_int min, isl_int max)
5185 {
5186         int k;
5187         struct isl_basic_set *bset = NULL;
5188
5189         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5190         if (!bset)
5191                 goto error;
5192
5193         k = isl_basic_set_alloc_inequality(bset);
5194         if (k < 0)
5195                 goto error;
5196         isl_int_set_si(bset->ineq[k][1], 1);
5197         isl_int_neg(bset->ineq[k][0], min);
5198
5199         k = isl_basic_set_alloc_inequality(bset);
5200         if (k < 0)
5201                 goto error;
5202         isl_int_set_si(bset->ineq[k][1], -1);
5203         isl_int_set(bset->ineq[k][0], max);
5204
5205         return bset;
5206 error:
5207         isl_basic_set_free(bset);
5208         return NULL;
5209 }
5210
5211 /* Return the Cartesian product of the basic sets in list (in the given order).
5212  */
5213 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5214 {
5215         int i;
5216         unsigned dim;
5217         unsigned nparam;
5218         unsigned extra;
5219         unsigned n_eq;
5220         unsigned n_ineq;
5221         struct isl_basic_set *product = NULL;
5222
5223         if (!list)
5224                 goto error;
5225         isl_assert(list->ctx, list->n > 0, goto error);
5226         isl_assert(list->ctx, list->p[0], goto error);
5227         nparam = isl_basic_set_n_param(list->p[0]);
5228         dim = isl_basic_set_n_dim(list->p[0]);
5229         extra = list->p[0]->n_div;
5230         n_eq = list->p[0]->n_eq;
5231         n_ineq = list->p[0]->n_ineq;
5232         for (i = 1; i < list->n; ++i) {
5233                 isl_assert(list->ctx, list->p[i], goto error);
5234                 isl_assert(list->ctx,
5235                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5236                 dim += isl_basic_set_n_dim(list->p[i]);
5237                 extra += list->p[i]->n_div;
5238                 n_eq += list->p[i]->n_eq;
5239                 n_ineq += list->p[i]->n_ineq;
5240         }
5241         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5242                                         n_eq, n_ineq);
5243         if (!product)
5244                 goto error;
5245         dim = 0;
5246         for (i = 0; i < list->n; ++i) {
5247                 set_add_constraints(product,
5248                                         isl_basic_set_copy(list->p[i]), dim);
5249                 dim += isl_basic_set_n_dim(list->p[i]);
5250         }
5251         isl_basic_set_list_free(list);
5252         return product;
5253 error:
5254         isl_basic_set_free(product);
5255         isl_basic_set_list_free(list);
5256         return NULL;
5257 }
5258
5259 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5260 {
5261         int i;
5262         uint32_t hash;
5263         unsigned total;
5264
5265         if (!bset)
5266                 return 0;
5267         bset = isl_basic_set_copy(bset);
5268         bset = isl_basic_set_normalize(bset);
5269         if (!bset)
5270                 return 0;
5271         total = isl_basic_set_total_dim(bset);
5272         isl_hash_byte(hash, bset->n_eq & 0xFF);
5273         for (i = 0; i < bset->n_eq; ++i) {
5274                 uint32_t c_hash;
5275                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5276                 isl_hash_hash(hash, c_hash);
5277         }
5278         isl_hash_byte(hash, bset->n_ineq & 0xFF);
5279         for (i = 0; i < bset->n_ineq; ++i) {
5280                 uint32_t c_hash;
5281                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
5282                 isl_hash_hash(hash, c_hash);
5283         }
5284         isl_hash_byte(hash, bset->n_div & 0xFF);
5285         for (i = 0; i < bset->n_div; ++i) {
5286                 uint32_t c_hash;
5287                 if (isl_int_is_zero(bset->div[i][0]))
5288                         continue;
5289                 isl_hash_byte(hash, i & 0xFF);
5290                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
5291                 isl_hash_hash(hash, c_hash);
5292         }
5293         isl_basic_set_free(bset);
5294         return hash;
5295 }
5296
5297 uint32_t isl_set_get_hash(struct isl_set *set)
5298 {
5299         int i;
5300         uint32_t hash;
5301
5302         if (!set)
5303                 return 0;
5304         set = isl_set_copy(set);
5305         set = isl_set_normalize(set);
5306         if (!set)
5307                 return 0;
5308
5309         hash = isl_hash_init();
5310         for (i = 0; i < set->n; ++i) {
5311                 uint32_t bset_hash;
5312                 bset_hash = isl_basic_set_get_hash(set->p[i]);
5313                 isl_hash_hash(hash, bset_hash);
5314         }
5315
5316         isl_set_free(set);
5317
5318         return hash;
5319 }
5320
5321 /* Check if the value for dimension dim is completely determined
5322  * by the values of the other parameters and variables.
5323  * That is, check if dimension dim is involved in an equality.
5324  */
5325 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
5326 {
5327         int i;
5328         unsigned nparam;
5329
5330         if (!bset)
5331                 return -1;
5332         nparam = isl_basic_set_n_param(bset);
5333         for (i = 0; i < bset->n_eq; ++i)
5334                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
5335                         return 1;
5336         return 0;
5337 }
5338
5339 /* Check if the value for dimension dim is completely determined
5340  * by the values of the other parameters and variables.
5341  * That is, check if dimension dim is involved in an equality
5342  * for each of the subsets.
5343  */
5344 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
5345 {
5346         int i;
5347
5348         if (!set)
5349                 return -1;
5350         for (i = 0; i < set->n; ++i) {
5351                 int unique;
5352                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
5353                 if (unique != 1)
5354                         return unique;
5355         }
5356         return 1;
5357 }