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_set *isl_set_universe(struct isl_dim *dim)
3195 {
3196         struct isl_set *set;
3197         if (!dim)
3198                 return NULL;
3199         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3200         set = isl_set_add(set, isl_basic_set_universe(dim));
3201         return set;
3202 }
3203
3204 struct isl_map *isl_map_dup(struct isl_map *map)
3205 {
3206         int i;
3207         struct isl_map *dup;
3208
3209         if (!map)
3210                 return NULL;
3211         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3212         for (i = 0; i < map->n; ++i)
3213                 dup = isl_map_add(dup, isl_basic_map_copy(map->p[i]));
3214         return dup;
3215 }
3216
3217 struct isl_map *isl_map_add(struct isl_map *map, struct isl_basic_map *bmap)
3218 {
3219         if (!bmap || !map)
3220                 goto error;
3221         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3222         isl_assert(map->ctx, map->n < map->size, goto error);
3223         map->p[map->n] = bmap;
3224         map->n++;
3225         F_CLR(map, ISL_MAP_NORMALIZED);
3226         return map;
3227 error:
3228         if (map)
3229                 isl_map_free(map);
3230         if (bmap)
3231                 isl_basic_map_free(bmap);
3232         return NULL;
3233 }
3234
3235 void isl_map_free(struct isl_map *map)
3236 {
3237         int i;
3238
3239         if (!map)
3240                 return;
3241
3242         if (--map->ref > 0)
3243                 return;
3244
3245         isl_ctx_deref(map->ctx);
3246         for (i = 0; i < map->n; ++i)
3247                 isl_basic_map_free(map->p[i]);
3248         isl_dim_free(map->dim);
3249         free(map);
3250 }
3251
3252 struct isl_map *isl_map_extend(struct isl_map *base,
3253                 unsigned nparam, unsigned n_in, unsigned n_out)
3254 {
3255         int i;
3256
3257         base = isl_map_cow(base);
3258         if (!base)
3259                 return NULL;
3260
3261         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3262         if (!base->dim)
3263                 goto error;
3264         for (i = 0; i < base->n; ++i) {
3265                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3266                                 isl_dim_copy(base->dim), 0, 0, 0);
3267                 if (!base->p[i])
3268                         goto error;
3269         }
3270         return base;
3271 error:
3272         isl_map_free(base);
3273         return NULL;
3274 }
3275
3276 struct isl_set *isl_set_extend(struct isl_set *base,
3277                 unsigned nparam, unsigned dim)
3278 {
3279         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3280                                                         nparam, 0, dim);
3281 }
3282
3283 static struct isl_basic_map *isl_basic_map_fix_var(struct isl_basic_map *bmap,
3284                 unsigned var, int value)
3285 {
3286         int j;
3287
3288         bmap = isl_basic_map_cow(bmap);
3289         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3290         j = isl_basic_map_alloc_equality(bmap);
3291         if (j < 0)
3292                 goto error;
3293         isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3294         isl_int_set_si(bmap->eq[j][1 + var], -1);
3295         isl_int_set_si(bmap->eq[j][0], value);
3296         bmap = isl_basic_map_simplify(bmap);
3297         return isl_basic_map_finalize(bmap);
3298 error:
3299         isl_basic_map_free(bmap);
3300         return NULL;
3301 }
3302
3303 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3304                 unsigned input, int value)
3305 {
3306         if (!bmap)
3307                 return NULL;
3308         isl_assert(bmap->ctx, input < isl_basic_map_n_in(bmap), goto error);
3309         return isl_basic_map_fix_var(bmap, isl_basic_map_n_param(bmap) + input,
3310                                         value);
3311 error:
3312         isl_basic_map_free(bmap);
3313         return NULL;
3314 }
3315
3316 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3317                 unsigned dim, int value)
3318 {
3319         if (!bset)
3320                 return NULL;
3321         isl_assert(bset->ctx, dim < isl_basic_set_n_dim(bset), goto error);
3322         return (struct isl_basic_set *)
3323                 isl_basic_map_fix_var((struct isl_basic_map *)bset,
3324                                     isl_basic_set_n_param(bset) + dim, value);
3325 error:
3326         isl_basic_set_free(bset);
3327         return NULL;
3328 }
3329
3330 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3331                 unsigned input, int value)
3332 {
3333         int i;
3334
3335         map = isl_map_cow(map);
3336         if (!map)
3337                 return NULL;
3338
3339         isl_assert(ctx, input < isl_map_n_in(map), goto error);
3340         for (i = 0; i < map->n; ++i) {
3341                 map->p[i] = isl_basic_map_fix_input_si(map->p[i], input, value);
3342                 if (!map->p[i])
3343                         goto error;
3344         }
3345         F_CLR(map, ISL_MAP_NORMALIZED);
3346         return map;
3347 error:
3348         isl_map_free(map);
3349         return NULL;
3350 }
3351
3352 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3353 {
3354         int i;
3355
3356         set = isl_set_cow(set);
3357         if (!set)
3358                 return NULL;
3359
3360         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3361         for (i = 0; i < set->n; ++i) {
3362                 set->p[i] = isl_basic_set_fix_dim_si(set->p[i], dim, value);
3363                 if (!set->p[i])
3364                         goto error;
3365         }
3366         return set;
3367 error:
3368         isl_set_free(set);
3369         return NULL;
3370 }
3371
3372 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3373         unsigned dim, isl_int value)
3374 {
3375         int j;
3376         unsigned nparam;
3377
3378         bset = isl_basic_set_cow(bset);
3379         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3380         j = isl_basic_set_alloc_inequality(bset);
3381         if (j < 0)
3382                 goto error;
3383         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3384         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3385         isl_int_neg(bset->ineq[j][0], value);
3386         bset = isl_basic_set_simplify(bset);
3387         return isl_basic_set_finalize(bset);
3388 error:
3389         isl_basic_set_free(bset);
3390         return NULL;
3391 }
3392
3393 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3394                                         isl_int value)
3395 {
3396         int i;
3397
3398         set = isl_set_cow(set);
3399         if (!set)
3400                 return NULL;
3401
3402         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3403         for (i = 0; i < set->n; ++i) {
3404                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3405                 if (!set->p[i])
3406                         goto error;
3407         }
3408         return set;
3409 error:
3410         isl_set_free(set);
3411         return NULL;
3412 }
3413
3414 struct isl_map *isl_map_reverse(struct isl_map *map)
3415 {
3416         int i;
3417         unsigned t;
3418
3419         map = isl_map_cow(map);
3420         if (!map)
3421                 return NULL;
3422
3423         map->dim = isl_dim_reverse(map->dim);
3424         if (!map->dim)
3425                 goto error;
3426         for (i = 0; i < map->n; ++i) {
3427                 map->p[i] = isl_basic_map_reverse(map->p[i]);
3428                 if (!map->p[i])
3429                         goto error;
3430         }
3431         F_CLR(map, ISL_MAP_NORMALIZED);
3432         return map;
3433 error:
3434         isl_map_free(map);
3435         return NULL;
3436 }
3437
3438 struct isl_map *isl_basic_map_lexmax(
3439                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3440                 struct isl_set **empty)
3441 {
3442         return isl_pip_basic_map_lexmax(bmap, dom, empty);
3443 }
3444
3445 struct isl_map *isl_basic_map_lexmin(
3446                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3447                 struct isl_set **empty)
3448 {
3449         return isl_pip_basic_map_lexmin(bmap, dom, empty);
3450 }
3451
3452 struct isl_set *isl_basic_set_lexmin(struct isl_basic_set *bset)
3453 {
3454         struct isl_basic_map *bmap = NULL;
3455         struct isl_basic_set *dom = NULL;
3456         struct isl_map *min;
3457         struct isl_dim *param_dim;
3458
3459         if (!bset)
3460                 goto error;
3461         bmap = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
3462         if (!bmap)
3463                 goto error;
3464         param_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
3465         dom = isl_basic_set_universe(param_dim);
3466         if (!dom)
3467                 goto error;
3468         min = isl_basic_map_lexmin(bmap, dom, NULL);
3469         return isl_map_range(min);
3470 error:
3471         isl_basic_map_free(bmap);
3472         return NULL;
3473 }
3474
3475 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
3476 {
3477         if (!bmap)
3478                 return NULL;
3479         if (bmap->n_div == 0)
3480                 return isl_map_from_basic_map(bmap);
3481         return isl_pip_basic_map_compute_divs(bmap);
3482 }
3483
3484 struct isl_map *isl_map_compute_divs(struct isl_map *map)
3485 {
3486         int i;
3487         struct isl_map *res;
3488
3489         if (!map)
3490                 return NULL;
3491         if (map->n == 0)
3492                 return map;
3493         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
3494         for (i = 1 ; i < map->n; ++i) {
3495                 struct isl_map *r2;
3496                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
3497                 if (F_ISSET(map, ISL_MAP_DISJOINT))
3498                         res = isl_map_union_disjoint(res, r2);
3499                 else
3500                         res = isl_map_union(res, r2);
3501         }
3502         isl_map_free(map);
3503
3504         return res;
3505 }
3506
3507 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
3508 {
3509         return (struct isl_set *)
3510                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
3511 }
3512
3513 struct isl_set *isl_set_compute_divs(struct isl_set *set)
3514 {
3515         return (struct isl_set *)
3516                 isl_map_compute_divs((struct isl_map *)set);
3517 }
3518
3519 struct isl_set *isl_map_domain(struct isl_map *map)
3520 {
3521         int i;
3522         struct isl_set *set;
3523
3524         if (!map)
3525                 goto error;
3526
3527         map = isl_map_cow(map);
3528         if (!map)
3529                 return NULL;
3530
3531         set = (struct isl_set *)map;
3532         set->dim = isl_dim_domain(set->dim);
3533         if (!set->dim)
3534                 goto error;
3535         for (i = 0; i < map->n; ++i) {
3536                 set->p[i] = isl_basic_map_domain(map->p[i]);
3537                 if (!set->p[i])
3538                         goto error;
3539         }
3540         F_CLR(set, ISL_MAP_DISJOINT);
3541         F_CLR(set, ISL_SET_NORMALIZED);
3542         return set;
3543 error:
3544         isl_map_free(map);
3545         return NULL;
3546 }
3547
3548 struct isl_map *isl_map_union_disjoint(
3549                         struct isl_map *map1, struct isl_map *map2)
3550 {
3551         int i;
3552         unsigned flags = 0;
3553         struct isl_map *map = NULL;
3554
3555         if (!map1 || !map2)
3556                 goto error;
3557
3558         if (map1->n == 0) {
3559                 isl_map_free(map1);
3560                 return map2;
3561         }
3562         if (map2->n == 0) {
3563                 isl_map_free(map2);
3564                 return map1;
3565         }
3566
3567         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
3568
3569         if (F_ISSET(map1, ISL_MAP_DISJOINT) &&
3570             F_ISSET(map2, ISL_MAP_DISJOINT))
3571                 FL_SET(flags, ISL_MAP_DISJOINT);
3572
3573         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
3574                                 map1->n + map2->n, flags);
3575         if (!map)
3576                 goto error;
3577         for (i = 0; i < map1->n; ++i) {
3578                 map = isl_map_add(map,
3579                                   isl_basic_map_copy(map1->p[i]));
3580                 if (!map)
3581                         goto error;
3582         }
3583         for (i = 0; i < map2->n; ++i) {
3584                 map = isl_map_add(map,
3585                                   isl_basic_map_copy(map2->p[i]));
3586                 if (!map)
3587                         goto error;
3588         }
3589         isl_map_free(map1);
3590         isl_map_free(map2);
3591         return map;
3592 error:
3593         isl_map_free(map);
3594         isl_map_free(map1);
3595         isl_map_free(map2);
3596         return NULL;
3597 }
3598
3599 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
3600 {
3601         map1 = isl_map_union_disjoint(map1, map2);
3602         if (!map1)
3603                 return NULL;
3604         if (map1->n > 1)
3605                 F_CLR(map1, ISL_MAP_DISJOINT);
3606         return map1;
3607 }
3608
3609 struct isl_set *isl_set_union_disjoint(
3610                         struct isl_set *set1, struct isl_set *set2)
3611 {
3612         return (struct isl_set *)
3613                 isl_map_union_disjoint(
3614                         (struct isl_map *)set1, (struct isl_map *)set2);
3615 }
3616
3617 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
3618 {
3619         return (struct isl_set *)
3620                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
3621 }
3622
3623 struct isl_map *isl_map_intersect_range(
3624                 struct isl_map *map, struct isl_set *set)
3625 {
3626         unsigned flags = 0;
3627         struct isl_map *result;
3628         int i, j;
3629
3630         if (!map || !set)
3631                 goto error;
3632
3633         if (F_ISSET(map, ISL_MAP_DISJOINT) &&
3634             F_ISSET(set, ISL_MAP_DISJOINT))
3635                 FL_SET(flags, ISL_MAP_DISJOINT);
3636
3637         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
3638                                         map->n * set->n, flags);
3639         if (!result)
3640                 goto error;
3641         for (i = 0; i < map->n; ++i)
3642                 for (j = 0; j < set->n; ++j) {
3643                         result = isl_map_add(result,
3644                             isl_basic_map_intersect_range(
3645                                 isl_basic_map_copy(map->p[i]),
3646                                 isl_basic_set_copy(set->p[j])));
3647                         if (!result)
3648                                 goto error;
3649                 }
3650         isl_map_free(map);
3651         isl_set_free(set);
3652         return result;
3653 error:
3654         isl_map_free(map);
3655         isl_set_free(set);
3656         return NULL;
3657 }
3658
3659 struct isl_map *isl_map_intersect_domain(
3660                 struct isl_map *map, struct isl_set *set)
3661 {
3662         return isl_map_reverse(
3663                 isl_map_intersect_range(isl_map_reverse(map), set));
3664 }
3665
3666 struct isl_map *isl_map_apply_domain(
3667                 struct isl_map *map1, struct isl_map *map2)
3668 {
3669         if (!map1 || !map2)
3670                 goto error;
3671         map1 = isl_map_reverse(map1);
3672         map1 = isl_map_apply_range(map1, map2);
3673         return isl_map_reverse(map1);
3674 error:
3675         isl_map_free(map1);
3676         isl_map_free(map2);
3677         return NULL;
3678 }
3679
3680 struct isl_map *isl_map_apply_range(
3681                 struct isl_map *map1, struct isl_map *map2)
3682 {
3683         struct isl_dim *dim_result;
3684         struct isl_map *result;
3685         int i, j;
3686         unsigned nparam;
3687         unsigned n_in;
3688         unsigned n_out;
3689
3690         if (!map1 || !map2)
3691                 goto error;
3692
3693         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
3694                                   isl_dim_copy(map2->dim));
3695
3696         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
3697         if (!result)
3698                 goto error;
3699         for (i = 0; i < map1->n; ++i)
3700                 for (j = 0; j < map2->n; ++j) {
3701                         result = isl_map_add(result,
3702                             isl_basic_map_apply_range(
3703                                 isl_basic_map_copy(map1->p[i]),
3704                                 isl_basic_map_copy(map2->p[j])));
3705                         if (!result)
3706                                 goto error;
3707                 }
3708         isl_map_free(map1);
3709         isl_map_free(map2);
3710         if (result && result->n <= 1)
3711                 F_SET(result, ISL_MAP_DISJOINT);
3712         return result;
3713 error:
3714         isl_map_free(map1);
3715         isl_map_free(map2);
3716         return NULL;
3717 }
3718
3719 /*
3720  * returns range - domain
3721  */
3722 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
3723 {
3724         struct isl_basic_set *bset;
3725         unsigned dim;
3726         unsigned nparam;
3727         int i;
3728
3729         if (!bmap)
3730                 goto error;
3731         dim = isl_basic_map_n_in(bmap);
3732         nparam = isl_basic_map_n_param(bmap);
3733         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
3734         bset = isl_basic_set_from_basic_map(bmap);
3735         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
3736         bset = isl_basic_set_swap_vars(bset, 2*dim);
3737         for (i = 0; i < dim; ++i) {
3738                 int j = isl_basic_map_alloc_equality(
3739                                             (struct isl_basic_map *)bset);
3740                 if (j < 0)
3741                         goto error;
3742                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
3743                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
3744                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
3745                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
3746         }
3747         return isl_basic_set_project_out(bset, 2*dim, 0);
3748 error:
3749         isl_basic_map_free(bmap);
3750         return NULL;
3751 }
3752
3753 /*
3754  * returns range - domain
3755  */
3756 struct isl_set *isl_map_deltas(struct isl_map *map)
3757 {
3758         int i;
3759         struct isl_set *result;
3760
3761         if (!map)
3762                 return NULL;
3763
3764         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
3765         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
3766                                         isl_map_n_in(map), map->n, map->flags);
3767         if (!result)
3768                 goto error;
3769         for (i = 0; i < map->n; ++i)
3770                 result = isl_set_add(result,
3771                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
3772         isl_map_free(map);
3773         return result;
3774 error:
3775         isl_map_free(map);
3776         return NULL;
3777 }
3778
3779 /* If the only constraints a div d=floor(f/m)
3780  * appears in are its two defining constraints
3781  *
3782  *      f - m d >=0
3783  *      -(f - (m - 1)) + m d >= 0
3784  *
3785  * then it can safely be removed.
3786  */
3787 static int div_is_redundant(struct isl_basic_map *bmap, int div)
3788 {
3789         int i;
3790         unsigned pos = 1 + isl_dim_total(bmap->dim) + div;
3791
3792         for (i = 0; i < bmap->n_eq; ++i)
3793                 if (!isl_int_is_zero(bmap->eq[i][pos]))
3794                         return 0;
3795
3796         for (i = 0; i < bmap->n_ineq; ++i) {
3797                 if (isl_int_is_zero(bmap->ineq[i][pos]))
3798                         continue;
3799                 if (isl_int_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
3800                         int neg;
3801                         isl_int_sub(bmap->div[div][1],
3802                                         bmap->div[div][1], bmap->div[div][0]);
3803                         isl_int_add_ui(bmap->div[div][1], bmap->div[div][1], 1);
3804                         neg = isl_seq_is_neg(bmap->ineq[i], bmap->div[div]+1, pos);
3805                         isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);
3806                         isl_int_add(bmap->div[div][1],
3807                                         bmap->div[div][1], bmap->div[div][0]);
3808                         if (!neg)
3809                                 return 0;
3810                         if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
3811                                                     bmap->n_div-div-1) != -1)
3812                                 return 0;
3813                 } else if (isl_int_abs_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
3814                         if (!isl_seq_eq(bmap->ineq[i], bmap->div[div]+1, pos))
3815                                 return 0;
3816                         if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
3817                                                     bmap->n_div-div-1) != -1)
3818                                 return 0;
3819                 } else
3820                         return 0;
3821         }
3822
3823         for (i = 0; i < bmap->n_div; ++i)
3824                 if (!isl_int_is_zero(bmap->div[i][1+pos]))
3825                         return 0;
3826
3827         return 1;
3828 }
3829
3830 /*
3831  * Remove divs that don't occur in any of the constraints or other divs.
3832  * These can arise when dropping some of the variables in a quast
3833  * returned by piplib.
3834  */
3835 static struct isl_basic_map *remove_redundant_divs(struct isl_basic_map *bmap)
3836 {
3837         int i;
3838
3839         if (!bmap)
3840                 return NULL;
3841
3842         for (i = bmap->n_div-1; i >= 0; --i) {
3843                 if (!div_is_redundant(bmap, i))
3844                         continue;
3845                 bmap = isl_basic_map_drop_div(bmap, i);
3846         }
3847         return bmap;
3848 }
3849
3850 struct isl_basic_map *isl_basic_map_finalize(struct isl_basic_map *bmap)
3851 {
3852         bmap = remove_redundant_divs(bmap);
3853         if (!bmap)
3854                 return NULL;
3855         F_SET(bmap, ISL_BASIC_SET_FINAL);
3856         return bmap;
3857 }
3858
3859 struct isl_basic_set *isl_basic_set_finalize(struct isl_basic_set *bset)
3860 {
3861         return (struct isl_basic_set *)
3862                 isl_basic_map_finalize((struct isl_basic_map *)bset);
3863 }
3864
3865 struct isl_set *isl_set_finalize(struct isl_set *set)
3866 {
3867         int i;
3868
3869         if (!set)
3870                 return NULL;
3871         for (i = 0; i < set->n; ++i) {
3872                 set->p[i] = isl_basic_set_finalize(set->p[i]);
3873                 if (!set->p[i])
3874                         goto error;
3875         }
3876         return set;
3877 error:
3878         isl_set_free(set);
3879         return NULL;
3880 }
3881
3882 struct isl_map *isl_map_finalize(struct isl_map *map)
3883 {
3884         int i;
3885
3886         if (!map)
3887                 return NULL;
3888         for (i = 0; i < map->n; ++i) {
3889                 map->p[i] = isl_basic_map_finalize(map->p[i]);
3890                 if (!map->p[i])
3891                         goto error;
3892         }
3893         F_CLR(map, ISL_MAP_NORMALIZED);
3894         return map;
3895 error:
3896         isl_map_free(map);
3897         return NULL;
3898 }
3899
3900 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
3901 {
3902         struct isl_basic_map *bmap;
3903         unsigned nparam;
3904         unsigned dim;
3905         int i;
3906
3907         if (!dims)
3908                 return NULL;
3909
3910         nparam = dims->nparam;
3911         dim = dims->n_out;
3912         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
3913         if (!bmap)
3914                 goto error;
3915
3916         for (i = 0; i < dim; ++i) {
3917                 int j = isl_basic_map_alloc_equality(bmap);
3918                 if (j < 0)
3919                         goto error;
3920                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3921                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
3922                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
3923         }
3924         return isl_basic_map_finalize(bmap);
3925 error:
3926         isl_basic_map_free(bmap);
3927         return NULL;
3928 }
3929
3930 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
3931 {
3932         struct isl_dim *dim = isl_dim_map(set_dim);
3933         if (!dim)
3934                 return NULL;
3935         return basic_map_identity(dim);
3936 }
3937
3938 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
3939 {
3940         if (!model || !model->dim)
3941                 return NULL;
3942         isl_assert(model->ctx,
3943                         model->dim->n_in == model->dim->n_out, return NULL);
3944         return basic_map_identity(isl_dim_copy(model->dim));
3945 }
3946
3947 static struct isl_map *map_identity(struct isl_dim *dim)
3948 {
3949         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
3950         return isl_map_add(map, basic_map_identity(isl_dim_copy(dim)));
3951 }
3952
3953 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
3954 {
3955         struct isl_dim *dim = isl_dim_map(set_dim);
3956         if (!dim)
3957                 return NULL;
3958         return map_identity(dim);
3959 }
3960
3961 struct isl_map *isl_map_identity_like(struct isl_basic_map *model)
3962 {
3963         if (!model || !model->dim)
3964                 return NULL;
3965         isl_assert(model->ctx,
3966                         model->dim->n_in == model->dim->n_out, return NULL);
3967         return map_identity(isl_dim_copy(model->dim));
3968 }
3969
3970 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
3971 {
3972         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
3973 }
3974
3975 int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
3976 {
3977         return isl_map_is_subset(
3978                         (struct isl_map *)set1, (struct isl_map *)set2);
3979 }
3980
3981 int isl_basic_map_is_subset(
3982                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3983 {
3984         int is_subset;
3985         struct isl_map *map1;
3986         struct isl_map *map2;
3987
3988         if (!bmap1 || !bmap2)
3989                 return -1;
3990
3991         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
3992         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
3993
3994         is_subset = isl_map_is_subset(map1, map2);
3995
3996         isl_map_free(map1);
3997         isl_map_free(map2);
3998
3999         return is_subset;
4000 }
4001
4002 int isl_basic_map_is_equal(
4003                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4004 {
4005         int is_subset;
4006
4007         if (!bmap1 || !bmap2)
4008                 return -1;
4009         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4010         if (is_subset != 1)
4011                 return is_subset;
4012         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4013         return is_subset;
4014 }
4015
4016 int isl_basic_set_is_equal(
4017                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4018 {
4019         return isl_basic_map_is_equal(
4020                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4021 }
4022
4023 int isl_map_is_empty(struct isl_map *map)
4024 {
4025         int i;
4026         int is_empty;
4027
4028         if (!map)
4029                 return -1;
4030         for (i = 0; i < map->n; ++i) {
4031                 is_empty = isl_basic_map_is_empty(map->p[i]);
4032                 if (is_empty < 0)
4033                         return -1;
4034                 if (!is_empty)
4035                         return 0;
4036         }
4037         return 1;
4038 }
4039
4040 int isl_set_is_empty(struct isl_set *set)
4041 {
4042         return isl_map_is_empty((struct isl_map *)set);
4043 }
4044
4045 int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2)
4046 {
4047         int i;
4048         int is_subset = 0;
4049         struct isl_map *diff;
4050
4051         if (!map1 || !map2)
4052                 return -1;
4053
4054         if (isl_map_is_empty(map1))
4055                 return 1;
4056
4057         if (isl_map_is_empty(map2))
4058                 return 0;
4059
4060         diff = isl_map_subtract(isl_map_copy(map1), isl_map_copy(map2));
4061         if (!diff)
4062                 return -1;
4063
4064         is_subset = isl_map_is_empty(diff);
4065         isl_map_free(diff);
4066
4067         return is_subset;
4068 }
4069
4070 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4071 {
4072         int is_subset;
4073
4074         if (!map1 || !map2)
4075                 return -1;
4076         is_subset = isl_map_is_subset(map1, map2);
4077         if (is_subset != 1)
4078                 return is_subset;
4079         is_subset = isl_map_is_subset(map2, map1);
4080         return is_subset;
4081 }
4082
4083 int isl_basic_map_is_strict_subset(
4084                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4085 {
4086         int is_subset;
4087
4088         if (!bmap1 || !bmap2)
4089                 return -1;
4090         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4091         if (is_subset != 1)
4092                 return is_subset;
4093         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4094         if (is_subset == -1)
4095                 return is_subset;
4096         return !is_subset;
4097 }
4098
4099 static int basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
4100 {
4101         int i;
4102         unsigned total;
4103         isl_int s;
4104
4105         total = 1 + isl_basic_map_total_dim(bmap);
4106         if (total != vec->size)
4107                 return -1;
4108
4109         isl_int_init(s);
4110
4111         for (i = 0; i < bmap->n_eq; ++i) {
4112                 isl_seq_inner_product(vec->block.data, bmap->eq[i], total, &s);
4113                 if (!isl_int_is_zero(s)) {
4114                         isl_int_clear(s);
4115                         return 0;
4116                 }
4117         }
4118
4119         for (i = 0; i < bmap->n_ineq; ++i) {
4120                 isl_seq_inner_product(vec->block.data, bmap->ineq[i], total, &s);
4121                 if (isl_int_is_neg(s)) {
4122                         isl_int_clear(s);
4123                         return 0;
4124                 }
4125         }
4126
4127         isl_int_clear(s);
4128
4129         return 1;
4130 }
4131
4132 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4133 {
4134         if (!bmap)
4135                 return -1;
4136         return bmap->n_eq == 0 && bmap->n_ineq == 0;
4137 }
4138
4139 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4140 {
4141         struct isl_basic_set *bset = NULL;
4142         struct isl_vec *sample = NULL;
4143         int empty;
4144         unsigned total;
4145
4146         if (!bmap)
4147                 return -1;
4148
4149         if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4150                 return 1;
4151
4152         if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4153                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4154                 copy = isl_basic_map_convex_hull(copy);
4155                 empty = F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4156                 isl_basic_map_free(copy);
4157                 return empty;
4158         }
4159
4160         total = 1 + isl_basic_map_total_dim(bmap);
4161         if (bmap->sample && bmap->sample->size == total) {
4162                 int contains = basic_map_contains(bmap, bmap->sample);
4163                 if (contains < 0)
4164                         return -1;
4165                 if (contains)
4166                         return 0;
4167         }
4168         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4169         if (!bset)
4170                 return -1;
4171         sample = isl_basic_set_sample(bset);
4172         if (!sample)
4173                 return -1;
4174         empty = sample->size == 0;
4175         if (bmap->sample)
4176                 isl_vec_free(bmap->ctx, bmap->sample);
4177         bmap->sample = sample;
4178
4179         return empty;
4180 }
4181
4182 struct isl_map *isl_basic_map_union(
4183         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4184 {
4185         struct isl_map *map;
4186         if (!bmap1 || !bmap2)
4187                 return NULL;
4188
4189         isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
4190
4191         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
4192         if (!map)
4193                 goto error;
4194         map = isl_map_add(map, bmap1);
4195         map = isl_map_add(map, bmap2);
4196         return map;
4197 error:
4198         isl_basic_map_free(bmap1);
4199         isl_basic_map_free(bmap2);
4200         return NULL;
4201 }
4202
4203 struct isl_set *isl_basic_set_union(
4204                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4205 {
4206         return (struct isl_set *)isl_basic_map_union(
4207                                             (struct isl_basic_map *)bset1,
4208                                             (struct isl_basic_map *)bset2);
4209 }
4210
4211 /* Order divs such that any div only depends on previous divs */
4212 static struct isl_basic_map *order_divs(struct isl_basic_map *bmap)
4213 {
4214         int i;
4215         unsigned off = isl_dim_total(bmap->dim);
4216
4217         for (i = 0; i < bmap->n_div; ++i) {
4218                 int pos;
4219                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
4220                                                             bmap->n_div-i);
4221                 if (pos == -1)
4222                         continue;
4223                 swap_div(bmap, i, pos);
4224                 --i;
4225         }
4226         return bmap;
4227 }
4228
4229 static int find_div(struct isl_basic_map *dst,
4230                         struct isl_basic_map *src, unsigned div)
4231 {
4232         int i;
4233
4234         unsigned total = isl_basic_map_total_dim(src);
4235
4236         for (i = 0; i < dst->n_div; ++i)
4237                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total) &&
4238                     isl_seq_first_non_zero(dst->div[i]+1+1+total,
4239                                                 dst->n_div - src->n_div) == -1)
4240                         return i;
4241         return -1;
4242 }
4243
4244 struct isl_basic_map *isl_basic_map_align_divs(
4245                 struct isl_basic_map *dst, struct isl_basic_map *src)
4246 {
4247         int i;
4248         unsigned total = isl_basic_map_total_dim(src);
4249
4250         if (!dst || !src)
4251                 goto error;
4252
4253         if (src->n_div == 0)
4254                 return dst;
4255
4256         src = order_divs(src);
4257         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
4258                         src->n_div, 0, 2 * src->n_div);
4259         if (!dst)
4260                 return NULL;
4261         for (i = 0; i < src->n_div; ++i) {
4262                 int j = find_div(dst, src, i);
4263                 if (j < 0) {
4264                         j = isl_basic_map_alloc_div(dst);
4265                         if (j < 0)
4266                                 goto error;
4267                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
4268                         isl_seq_clr(dst->div[j]+1+1+total,
4269                                                     dst->n_div - src->n_div);
4270                         if (add_div_constraints(dst, j) < 0)
4271                                 goto error;
4272                 }
4273                 if (j != i)
4274                         swap_div(dst, i, j);
4275         }
4276         return dst;
4277 error:
4278         isl_basic_map_free(dst);
4279         return NULL;
4280 }
4281
4282 struct isl_basic_set *isl_basic_set_align_divs(
4283                 struct isl_basic_set *dst, struct isl_basic_set *src)
4284 {
4285         return (struct isl_basic_set *)isl_basic_map_align_divs(
4286                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
4287 }
4288
4289 struct isl_map *isl_map_align_divs(struct isl_map *map)
4290 {
4291         int i;
4292
4293         map = isl_map_compute_divs(map);
4294         map = isl_map_cow(map);
4295         if (!map)
4296                 return NULL;
4297
4298         for (i = 1; i < map->n; ++i)
4299                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
4300         for (i = 1; i < map->n; ++i)
4301                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
4302
4303         F_CLR(map, ISL_MAP_NORMALIZED);
4304         return map;
4305 }
4306
4307 static struct isl_map *add_cut_constraint(struct isl_map *dst,
4308                 struct isl_basic_map *src, isl_int *c,
4309                 unsigned len, int oppose)
4310 {
4311         struct isl_basic_map *copy = NULL;
4312         int is_empty;
4313         int k;
4314         unsigned total;
4315
4316         copy = isl_basic_map_copy(src);
4317         copy = isl_basic_map_cow(copy);
4318         if (!copy)
4319                 goto error;
4320         copy = isl_basic_map_extend_constraints(copy, 0, 1);
4321         k = isl_basic_map_alloc_inequality(copy);
4322         if (k < 0)
4323                 goto error;
4324         if (oppose)
4325                 isl_seq_neg(copy->ineq[k], c, len);
4326         else
4327                 isl_seq_cpy(copy->ineq[k], c, len);
4328         total = 1 + isl_basic_map_total_dim(copy);
4329         isl_seq_clr(copy->ineq[k]+len, total - len);
4330         isl_inequality_negate(copy, k);
4331         copy = isl_basic_map_simplify(copy);
4332         copy = isl_basic_map_finalize(copy);
4333         is_empty = isl_basic_map_is_empty(copy);
4334         if (is_empty < 0)
4335                 goto error;
4336         if (!is_empty)
4337                 dst = isl_map_add(dst, copy);
4338         else
4339                 isl_basic_map_free(copy);
4340         return dst;
4341 error:
4342         isl_basic_map_free(copy);
4343         isl_map_free(dst);
4344         return NULL;
4345 }
4346
4347 static struct isl_map *subtract(struct isl_map *map, struct isl_basic_map *bmap)
4348 {
4349         int i, j, k;
4350         unsigned flags = 0;
4351         struct isl_map *rest = NULL;
4352         unsigned max;
4353         unsigned total = isl_basic_map_total_dim(bmap);
4354
4355         assert(bmap);
4356
4357         if (!map)
4358                 goto error;
4359
4360         if (F_ISSET(map, ISL_MAP_DISJOINT))
4361                 FL_SET(flags, ISL_MAP_DISJOINT);
4362
4363         max = map->n * (2 * bmap->n_eq + bmap->n_ineq);
4364         rest = isl_map_alloc_dim(isl_dim_copy(map->dim), max, flags);
4365         if (!rest)
4366                 goto error;
4367
4368         for (i = 0; i < map->n; ++i) {
4369                 map->p[i] = isl_basic_map_align_divs(map->p[i], bmap);
4370                 if (!map->p[i])
4371                         goto error;
4372         }
4373
4374         for (j = 0; j < map->n; ++j)
4375                 map->p[j] = isl_basic_map_cow(map->p[j]);
4376
4377         for (i = 0; i < bmap->n_eq; ++i) {
4378                 for (j = 0; j < map->n; ++j) {
4379                         rest = add_cut_constraint(rest,
4380                                 map->p[j], bmap->eq[i], 1+total, 0);
4381                         if (!rest)
4382                                 goto error;
4383
4384                         rest = add_cut_constraint(rest,
4385                                 map->p[j], bmap->eq[i], 1+total, 1);
4386                         if (!rest)
4387                                 goto error;
4388
4389                         map->p[j] = isl_basic_map_extend_constraints(map->p[j],
4390                                 1, 0);
4391                         if (!map->p[j])
4392                                 goto error;
4393                         k = isl_basic_map_alloc_equality(map->p[j]);
4394                         if (k < 0)
4395                                 goto error;
4396                         isl_seq_cpy(map->p[j]->eq[k], bmap->eq[i], 1+total);
4397                         isl_seq_clr(map->p[j]->eq[k]+1+total,
4398                                         map->p[j]->n_div - bmap->n_div);
4399                 }
4400         }
4401
4402         for (i = 0; i < bmap->n_ineq; ++i) {
4403                 for (j = 0; j < map->n; ++j) {
4404                         rest = add_cut_constraint(rest,
4405                                 map->p[j], bmap->ineq[i], 1+total, 0);
4406                         if (!rest)
4407                                 goto error;
4408
4409                         map->p[j] = isl_basic_map_extend_constraints(map->p[j],
4410                                 0, 1);
4411                         if (!map->p[j])
4412                                 goto error;
4413                         k = isl_basic_map_alloc_inequality(map->p[j]);
4414                         if (k < 0)
4415                                 goto error;
4416                         isl_seq_cpy(map->p[j]->ineq[k], bmap->ineq[i], 1+total);
4417                         isl_seq_clr(map->p[j]->ineq[k]+1+total,
4418                                         map->p[j]->n_div - bmap->n_div);
4419                 }
4420         }
4421
4422         isl_map_free(map);
4423         return rest;
4424 error:
4425         isl_map_free(map);
4426         isl_map_free(rest);
4427         return NULL;
4428 }
4429
4430 struct isl_map *isl_map_subtract(struct isl_map *map1, struct isl_map *map2)
4431 {
4432         int i;
4433         if (!map1 || !map2)
4434                 goto error;
4435
4436         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4437
4438         if (isl_map_is_empty(map2)) {
4439                 isl_map_free(map2);
4440                 return map1;
4441         }
4442
4443         map1 = isl_map_compute_divs(map1);
4444         map2 = isl_map_compute_divs(map2);
4445         if (!map1 || !map2)
4446                 goto error;
4447
4448         for (i = 0; map1 && i < map2->n; ++i)
4449                 map1 = subtract(map1, map2->p[i]);
4450
4451         isl_map_free(map2);
4452         return map1;
4453 error:
4454         isl_map_free(map1);
4455         isl_map_free(map2);
4456         return NULL;
4457 }
4458
4459 struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2)
4460 {
4461         return (struct isl_set *)
4462                 isl_map_subtract(
4463                         (struct isl_map *)set1, (struct isl_map *)set2);
4464 }
4465
4466 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
4467 {
4468         if (!set || !map)
4469                 goto error;
4470         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
4471         map = isl_map_intersect_domain(map, set);
4472         set = isl_map_range(map);
4473         return set;
4474 error:
4475         isl_set_free(set);
4476         isl_map_free(map);
4477         return NULL;
4478 }
4479
4480 /* There is no need to cow as removing empty parts doesn't change
4481  * the meaning of the set.
4482  */
4483 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
4484 {
4485         int i;
4486
4487         if (!map)
4488                 return NULL;
4489
4490         for (i = map->n-1; i >= 0; --i) {
4491                 if (!F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
4492                         continue;
4493                 isl_basic_map_free(map->p[i]);
4494                 if (i != map->n-1) {
4495                         F_CLR(map, ISL_MAP_NORMALIZED);
4496                         map->p[i] = map->p[map->n-1];
4497                 }
4498                 map->n--;
4499         }
4500
4501         return map;
4502 }
4503
4504 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
4505 {
4506         return (struct isl_set *)
4507                 isl_map_remove_empty_parts((struct isl_map *)set);
4508 }
4509
4510 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
4511 {
4512         struct isl_basic_set *bset;
4513         if (!set || set->n == 0)
4514                 return NULL;
4515         bset = set->p[set->n-1];
4516         isl_assert(set->ctx, F_ISSET(bset, ISL_BASIC_SET_FINAL), return NULL);
4517         return isl_basic_set_copy(bset);
4518 }
4519
4520 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
4521                                                 struct isl_basic_set *bset)
4522 {
4523         int i;
4524
4525         if (!set || !bset)
4526                 goto error;
4527         for (i = set->n-1; i >= 0; --i) {
4528                 if (set->p[i] != bset)
4529                         continue;
4530                 set = isl_set_cow(set);
4531                 if (!set)
4532                         goto error;
4533                 isl_basic_set_free(set->p[i]);
4534                 if (i != set->n-1) {
4535                         F_CLR(set, ISL_SET_NORMALIZED);
4536                         set->p[i] = set->p[set->n-1];
4537                 }
4538                 set->n--;
4539                 return set;
4540         }
4541         isl_basic_set_free(bset);
4542         return set;
4543 error:
4544         isl_set_free(set);
4545         isl_basic_set_free(bset);
4546         return NULL;
4547 }
4548
4549 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
4550  * for any common value of the parameters and dimensions preceding dim
4551  * in both basic sets, the values of dimension pos in bset1 are
4552  * smaller or larger than those in bset2.
4553  *
4554  * Returns
4555  *       1 if bset1 follows bset2
4556  *      -1 if bset1 precedes bset2
4557  *       0 if bset1 and bset2 are incomparable
4558  *      -2 if some error occurred.
4559  */
4560 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
4561         struct isl_basic_set *bset2, int pos)
4562 {
4563         struct isl_dim *dims;
4564         struct isl_basic_map *bmap1 = NULL;
4565         struct isl_basic_map *bmap2 = NULL;
4566         struct isl_ctx *ctx;
4567         struct isl_vec *obj;
4568         unsigned total;
4569         unsigned nparam;
4570         unsigned dim1, dim2;
4571         isl_int num, den;
4572         enum isl_lp_result res;
4573         int cmp;
4574
4575         if (!bset1 || !bset2)
4576                 return -2;
4577
4578         nparam = isl_basic_set_n_param(bset1);
4579         dim1 = isl_basic_set_n_dim(bset1);
4580         dim2 = isl_basic_set_n_dim(bset2);
4581         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
4582         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
4583         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
4584         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
4585         if (!bmap1 || !bmap2)
4586                 goto error;
4587         bmap1 = isl_basic_map_extend(bmap1, nparam,
4588                         pos, (dim1 - pos) + (dim2 - pos),
4589                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
4590         if (!bmap1)
4591                 goto error;
4592         total = isl_basic_map_total_dim(bmap1);
4593         ctx = bmap1->ctx;
4594         obj = isl_vec_alloc(ctx, total);
4595         isl_seq_clr(obj->block.data, total);
4596         isl_int_set_si(obj->block.data[nparam+pos], 1);
4597         isl_int_set_si(obj->block.data[nparam+pos+(dim1-pos)], -1);
4598         if (!obj)
4599                 goto error;
4600         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
4601         isl_int_init(num);
4602         isl_int_init(den);
4603         res = isl_solve_lp(bmap1, 0, obj->block.data, ctx->one, &num, &den);
4604         if (res == isl_lp_empty)
4605                 cmp = 0;
4606         else if (res == isl_lp_ok && isl_int_is_pos(num))
4607                 cmp = 1;
4608         else if ((res == isl_lp_ok && isl_int_is_neg(num)) ||
4609                   res == isl_lp_unbounded)
4610                 cmp = -1;
4611         else
4612                 cmp = -2;
4613         isl_int_clear(num);
4614         isl_int_clear(den);
4615         isl_basic_map_free(bmap1);
4616         isl_vec_free(ctx, obj);
4617         return cmp;
4618 error:
4619         isl_basic_map_free(bmap1);
4620         isl_basic_map_free(bmap2);
4621         return -2;
4622 }
4623
4624 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
4625         unsigned pos, isl_int *val)
4626 {
4627         int i;
4628         int d;
4629         unsigned total;
4630
4631         if (!bmap)
4632                 return -1;
4633         total = isl_basic_map_total_dim(bmap);
4634         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
4635                 for (; d+1 > pos; --d)
4636                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
4637                                 break;
4638                 if (d != pos)
4639                         continue;
4640                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
4641                         return 0;
4642                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
4643                         return 0;
4644                 if (!isl_int_is_one(bmap->eq[i][1+d]))
4645                         return 0;
4646                 if (val)
4647                         isl_int_neg(*val, bmap->eq[i][0]);
4648                 return 1;
4649         }
4650         return 0;
4651 }
4652
4653 static int isl_map_fast_has_fixed_var(struct isl_map *map,
4654         unsigned pos, isl_int *val)
4655 {
4656         int i;
4657         isl_int v;
4658         isl_int tmp;
4659         int fixed;
4660
4661         if (!map)
4662                 return -1;
4663         if (map->n == 0)
4664                 return 0;
4665         if (map->n == 1)
4666                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
4667         isl_int_init(v);
4668         isl_int_init(tmp);
4669         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
4670         for (i = 1; fixed == 1 && i < map->n; ++i) {
4671                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
4672                 if (fixed == 1 && isl_int_ne(tmp, v))
4673                         fixed = 0;
4674         }
4675         if (val)
4676                 isl_int_set(*val, v);
4677         isl_int_clear(tmp);
4678         isl_int_clear(v);
4679         return fixed;
4680 }
4681
4682 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
4683         isl_int *val)
4684 {
4685         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
4686 }
4687
4688 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4689  * then return this fixed value in *val.
4690  */
4691 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
4692 {
4693         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
4694 }
4695
4696 /* Check if input variable in has fixed value and if so and if val is not NULL,
4697  * then return this fixed value in *val.
4698  */
4699 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
4700 {
4701         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
4702 }
4703
4704 /* Check if dimension dim has an (obvious) fixed lower bound and if so
4705  * and if val is not NULL, then return this lower bound in *val.
4706  */
4707 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
4708         unsigned dim, isl_int *val)
4709 {
4710         int i, i_eq = -1, i_ineq = -1;
4711         isl_int *c;
4712         unsigned total;
4713         unsigned nparam;
4714
4715         if (!bset)
4716                 return -1;
4717         total = isl_basic_set_total_dim(bset);
4718         nparam = isl_basic_set_n_param(bset);
4719         for (i = 0; i < bset->n_eq; ++i) {
4720                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
4721                         continue;
4722                 if (i_eq != -1)
4723                         return 0;
4724                 i_eq = i;
4725         }
4726         for (i = 0; i < bset->n_ineq; ++i) {
4727                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
4728                         continue;
4729                 if (i_eq != -1 || i_ineq != -1)
4730                         return 0;
4731                 i_ineq = i;
4732         }
4733         if (i_eq == -1 && i_ineq == -1)
4734                 return 0;
4735         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
4736         /* The coefficient should always be one due to normalization. */
4737         if (!isl_int_is_one(c[1+nparam+dim]))
4738                 return 0;
4739         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
4740                 return 0;
4741         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
4742                                         total - nparam - dim - 1) != -1)
4743                 return 0;
4744         if (val)
4745                 isl_int_neg(*val, c[0]);
4746         return 1;
4747 }
4748
4749 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
4750         unsigned dim, isl_int *val)
4751 {
4752         int i;
4753         isl_int v;
4754         isl_int tmp;
4755         int fixed;
4756
4757         if (!set)
4758                 return -1;
4759         if (set->n == 0)
4760                 return 0;
4761         if (set->n == 1)
4762                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4763                                                                 dim, val);
4764         isl_int_init(v);
4765         isl_int_init(tmp);
4766         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4767                                                                 dim, &v);
4768         for (i = 1; fixed == 1 && i < set->n; ++i) {
4769                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
4770                                                                 dim, &tmp);
4771                 if (fixed == 1 && isl_int_ne(tmp, v))
4772                         fixed = 0;
4773         }
4774         if (val)
4775                 isl_int_set(*val, v);
4776         isl_int_clear(tmp);
4777         isl_int_clear(v);
4778         return fixed;
4779 }
4780
4781 static struct isl_basic_set *isl_basic_set_reduce_using_equalities(
4782         struct isl_basic_set *bset, struct isl_basic_set *context)
4783 {
4784         int i;
4785         int *elim;
4786
4787         if (!bset || !context)
4788                 goto error;
4789
4790         bset = isl_basic_set_cow(bset);
4791         if (!bset)
4792                 goto error;
4793
4794         elim = isl_alloc_array(ctx, int, isl_basic_set_n_dim(bset));
4795         if (!elim)
4796                 goto error;
4797         set_compute_elimination_index(context, elim);
4798         for (i = 0; i < bset->n_eq; ++i)
4799                 set_reduced_using_equalities(bset->eq[i], bset->eq[i],
4800                                                         context, elim);
4801         for (i = 0; i < bset->n_ineq; ++i)
4802                 set_reduced_using_equalities(bset->ineq[i], bset->ineq[i],
4803                                                         context, elim);
4804         isl_basic_set_free(context);
4805         free(elim);
4806         bset = isl_basic_set_simplify(bset);
4807         bset = isl_basic_set_finalize(bset);
4808         return bset;
4809 error:
4810         isl_basic_set_free(bset);
4811         isl_basic_set_free(context);
4812         return NULL;
4813 }
4814
4815 static struct isl_basic_set *remove_shifted_constraints(
4816         struct isl_basic_set *bset, struct isl_basic_set *context)
4817 {
4818         unsigned int size;
4819         isl_int ***index;
4820         int bits;
4821         int k, h, l;
4822
4823         if (!bset)
4824                 return NULL;
4825
4826         size = round_up(4 * (context->n_ineq+1) / 3 - 1);
4827         bits = ffs(size) - 1;
4828         index = isl_calloc_array(ctx, isl_int **, size);
4829         if (!index)
4830                 return bset;
4831
4832         for (k = 0; k < context->n_ineq; ++k) {
4833                 h = set_hash_index(index, size, bits, context, k);
4834                 index[h] = &context->ineq[k];
4835         }
4836         for (k = 0; k < bset->n_ineq; ++k) {
4837                 h = set_hash_index(index, size, bits, bset, k);
4838                 if (!index[h])
4839                         continue;
4840                 l = index[h] - &context->ineq[0];
4841                 if (isl_int_lt(bset->ineq[k][0], context->ineq[l][0]))
4842                         continue;
4843                 bset = isl_basic_set_cow(bset);
4844                 if (!bset)
4845                         goto error;
4846                 isl_basic_set_drop_inequality(bset, k);
4847                 --k;
4848         }
4849         free(index);
4850         return bset;
4851 error:
4852         free(index);
4853         return bset;
4854 }
4855
4856 /* Remove all information from bset that is redundant in the context
4857  * of context.  In particular, equalities that are linear combinations
4858  * of those in context are removed.  Then the inequalities that are
4859  * redundant in the context of the equalities and inequalities of
4860  * context are removed.
4861  */
4862 static struct isl_basic_set *uset_gist(struct isl_basic_set *bset,
4863         struct isl_basic_set *context)
4864 {
4865         int i;
4866         isl_int opt;
4867         struct isl_basic_set *combined;
4868         struct isl_ctx *ctx;
4869
4870         if (!bset || !context)
4871                 goto error;
4872
4873         if (context->n_eq > 0) {
4874                 struct isl_mat *T;
4875                 struct isl_mat *T2;
4876                 struct isl_ctx *ctx = context->ctx;
4877                 struct isl_basic_set *reduced_context;
4878                 reduced_context = isl_basic_set_remove_equalities(
4879                                         isl_basic_set_copy(context), &T, &T2);
4880                 if (!reduced_context)
4881                         goto error;
4882                 bset = isl_basic_set_preimage(ctx, bset, T);
4883                 bset = uset_gist(bset, reduced_context);
4884                 bset = isl_basic_set_preimage(ctx, bset, T2);
4885                 bset = isl_basic_set_reduce_using_equalities(bset, context);
4886                 return bset;
4887         }
4888         if (!context->n_ineq)
4889                 goto done;
4890         bset = remove_shifted_constraints(bset, context);
4891         combined = isl_basic_set_extend_constraints(isl_basic_set_copy(bset),
4892                         context->n_eq, context->n_ineq);
4893         context = set_add_constraints(combined, context, 0);
4894         if (!context)
4895                 goto error;
4896         ctx = context->ctx;
4897         isl_int_init(opt);
4898         for (i = bset->n_ineq-1; i >= 0; --i) {
4899                 int redundant;
4900                 set_swap_inequality(context, i, context->n_ineq-1);
4901                 context->n_ineq--;
4902                 redundant = isl_basic_set_constraint_is_redundant(&context,
4903                                 context->ineq[context->n_ineq], &opt, NULL);
4904                 if (redundant == -1) {
4905                         isl_int_clear(opt);
4906                         goto error;
4907                 }
4908                 if (F_ISSET(context, ISL_BASIC_MAP_EMPTY)) {
4909                         bset = isl_basic_set_set_to_empty(bset);
4910                         break;
4911                 }
4912                 context->n_ineq++;
4913                 set_swap_inequality(context, i, context->n_ineq-1);
4914                 if (redundant) {
4915                         isl_basic_set_drop_inequality(context, i);
4916                         isl_basic_set_drop_inequality(bset, i);
4917                 }
4918         }
4919         isl_int_clear(opt);
4920 done:
4921         isl_basic_set_free(context);
4922         return bset;
4923 error:
4924         isl_basic_set_free(context);
4925         isl_basic_set_free(bset);
4926         return NULL;
4927 }
4928
4929 struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap,
4930         struct isl_basic_map *context)
4931 {
4932         struct isl_basic_set *bset;
4933
4934         if (!bmap || !context)
4935                 goto error;
4936
4937         context = isl_basic_map_align_divs(context, bmap);
4938         bmap = isl_basic_map_align_divs(bmap, context);
4939
4940         bset = uset_gist(isl_basic_map_underlying_set(isl_basic_map_copy(bmap)),
4941                          isl_basic_map_underlying_set(context));
4942
4943         return isl_basic_map_overlying_set(bset, bmap);
4944 error:
4945         isl_basic_map_free(bmap);
4946         isl_basic_map_free(context);
4947         return NULL;
4948 }
4949
4950 struct isl_map *isl_map_gist(struct isl_map *map, struct isl_basic_map *context)
4951 {
4952         int i;
4953
4954         map = isl_map_cow(map);
4955         if (!map || !context)
4956                 return NULL;
4957         isl_assert(map->ctx, isl_dim_equal(map->dim, context->dim), goto error);
4958         for (i = 0; i < map->n; ++i)
4959                 context = isl_basic_map_align_divs(context, map->p[i]);
4960         for (i = 0; i < map->n; ++i) {
4961                 map->p[i] = isl_basic_map_gist(map->p[i],
4962                                                 isl_basic_map_copy(context));
4963                 if (!map->p[i])
4964                         goto error;
4965         }
4966         isl_basic_map_free(context);
4967         F_CLR(map, ISL_MAP_NORMALIZED);
4968         return map;
4969 error:
4970         isl_map_free(map);
4971         isl_basic_map_free(context);
4972         return NULL;
4973 }
4974
4975 struct isl_basic_set *isl_basic_set_gist(struct isl_basic_set *bset,
4976                                                 struct isl_basic_set *context)
4977 {
4978         return (struct isl_basic_set *)isl_basic_map_gist(
4979                 (struct isl_basic_map *)bset, (struct isl_basic_map *)context);
4980 }
4981
4982 struct isl_set *isl_set_gist(struct isl_set *set, struct isl_basic_set *context)
4983 {
4984         return (struct isl_set *)isl_map_gist((struct isl_map *)set,
4985                                         (struct isl_basic_map *)context);
4986 }
4987
4988 struct constraint {
4989         unsigned        size;
4990         isl_int         *c;
4991 };
4992
4993 static int qsort_constraint_cmp(const void *p1, const void *p2)
4994 {
4995         const struct constraint *c1 = (const struct constraint *)p1;
4996         const struct constraint *c2 = (const struct constraint *)p2;
4997         unsigned size = isl_min(c1->size, c2->size);
4998         return isl_seq_cmp(c1->c, c2->c, size);
4999 }
5000
5001 static struct isl_basic_map *isl_basic_map_sort_constraints(
5002         struct isl_basic_map *bmap)
5003 {
5004         int i;
5005         struct constraint *c;
5006         unsigned total;
5007
5008         if (!bmap)
5009                 return NULL;
5010         total = isl_basic_map_total_dim(bmap);
5011         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5012         if (!c)
5013                 goto error;
5014         for (i = 0; i < bmap->n_ineq; ++i) {
5015                 c[i].size = total;
5016                 c[i].c = bmap->ineq[i];
5017         }
5018         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5019         for (i = 0; i < bmap->n_ineq; ++i)
5020                 bmap->ineq[i] = c[i].c;
5021         free(c);
5022         return bmap;
5023 error:
5024         isl_basic_map_free(bmap);
5025         return NULL;
5026 }
5027
5028 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5029 {
5030         if (!bmap)
5031                 return NULL;
5032         if (F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5033                 return bmap;
5034         bmap = isl_basic_map_convex_hull(bmap);
5035         bmap = isl_basic_map_sort_constraints(bmap);
5036         F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5037         return bmap;
5038 }
5039
5040 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5041 {
5042         return (struct isl_basic_set *)isl_basic_map_normalize(
5043                                                 (struct isl_basic_map *)bset);
5044 }
5045
5046 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5047         const struct isl_basic_map *bmap2)
5048 {
5049         int i, cmp;
5050         unsigned total;
5051
5052         if (bmap1 == bmap2)
5053                 return 0;
5054         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5055                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5056         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5057                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5058         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5059                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5060         if (F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5061             F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5062                 return 0;
5063         if (F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5064                 return 1;
5065         if (F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5066                 return -1;
5067         if (bmap1->n_eq != bmap2->n_eq)
5068                 return bmap1->n_eq - bmap2->n_eq;
5069         if (bmap1->n_ineq != bmap2->n_ineq)
5070                 return bmap1->n_ineq - bmap2->n_ineq;
5071         if (bmap1->n_div != bmap2->n_div)
5072                 return bmap1->n_div - bmap2->n_div;
5073         total = isl_basic_map_total_dim(bmap1);
5074         for (i = 0; i < bmap1->n_eq; ++i) {
5075                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5076                 if (cmp)
5077                         return cmp;
5078         }
5079         for (i = 0; i < bmap1->n_ineq; ++i) {
5080                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5081                 if (cmp)
5082                         return cmp;
5083         }
5084         for (i = 0; i < bmap1->n_div; ++i) {
5085                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5086                 if (cmp)
5087                         return cmp;
5088         }
5089         return 0;
5090 }
5091
5092 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5093         struct isl_basic_map *bmap2)
5094 {
5095         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5096 }
5097
5098 static int qsort_bmap_cmp(const void *p1, const void *p2)
5099 {
5100         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5101         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5102
5103         return isl_basic_map_fast_cmp(bmap1, bmap2);
5104 }
5105
5106 /* We normalize in place, but if anything goes wrong we need
5107  * to return NULL, so we need to make sure we don't change the
5108  * meaning of any possible other copies of map.
5109  */
5110 struct isl_map *isl_map_normalize(struct isl_map *map)
5111 {
5112         int i, j;
5113         struct isl_basic_map *bmap;
5114
5115         if (!map)
5116                 return NULL;
5117         if (F_ISSET(map, ISL_MAP_NORMALIZED))
5118                 return map;
5119         for (i = 0; i < map->n; ++i) {
5120                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5121                 if (!bmap)
5122                         goto error;
5123                 isl_basic_map_free(map->p[i]);
5124                 map->p[i] = bmap;
5125         }
5126         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5127         F_SET(map, ISL_MAP_NORMALIZED);
5128         map = isl_map_remove_empty_parts(map);
5129         if (!map)
5130                 return NULL;
5131         for (i = map->n - 1; i >= 1; --i) {
5132                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5133                         continue;
5134                 isl_basic_map_free(map->p[i-1]);
5135                 for (j = i; j < map->n; ++j)
5136                         map->p[j-1] = map->p[j];
5137                 map->n--;
5138         }
5139         return map;
5140 error:
5141         isl_map_free(map);
5142         return NULL;
5143
5144 }
5145
5146 struct isl_set *isl_set_normalize(struct isl_set *set)
5147 {
5148         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5149 }
5150
5151 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5152 {
5153         int i;
5154         int equal;
5155
5156         if (!map1 || !map2)
5157                 return -1;
5158
5159         if (map1 == map2)
5160                 return 1;
5161         if (!isl_dim_equal(map1->dim, map2->dim))
5162                 return 0;
5163
5164         map1 = isl_map_copy(map1);
5165         map2 = isl_map_copy(map2);
5166         map1 = isl_map_normalize(map1);
5167         map2 = isl_map_normalize(map2);
5168         if (!map1 || !map2)
5169                 goto error;
5170         equal = map1->n == map2->n;
5171         for (i = 0; equal && i < map1->n; ++i) {
5172                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5173                 if (equal < 0)
5174                         goto error;
5175         }
5176         isl_map_free(map1);
5177         isl_map_free(map2);
5178         return equal;
5179 error:
5180         isl_map_free(map1);
5181         isl_map_free(map2);
5182         return -1;
5183 }
5184
5185 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5186 {
5187         return isl_map_fast_is_equal((struct isl_map *)set1,
5188                                                 (struct isl_map *)set2);
5189 }
5190
5191 /* Return an interval that ranges from min to max (inclusive)
5192  */
5193 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5194         isl_int min, isl_int max)
5195 {
5196         int k;
5197         struct isl_basic_set *bset = NULL;
5198
5199         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5200         if (!bset)
5201                 goto error;
5202
5203         k = isl_basic_set_alloc_inequality(bset);
5204         if (k < 0)
5205                 goto error;
5206         isl_int_set_si(bset->ineq[k][1], 1);
5207         isl_int_neg(bset->ineq[k][0], min);
5208
5209         k = isl_basic_set_alloc_inequality(bset);
5210         if (k < 0)
5211                 goto error;
5212         isl_int_set_si(bset->ineq[k][1], -1);
5213         isl_int_set(bset->ineq[k][0], max);
5214
5215         return bset;
5216 error:
5217         isl_basic_set_free(bset);
5218         return NULL;
5219 }
5220
5221 /* Return the Cartesian product of the basic sets in list (in the given order).
5222  */
5223 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5224 {
5225         int i;
5226         unsigned dim;
5227         unsigned nparam;
5228         unsigned extra;
5229         unsigned n_eq;
5230         unsigned n_ineq;
5231         struct isl_basic_set *product = NULL;
5232
5233         if (!list)
5234                 goto error;
5235         isl_assert(list->ctx, list->n > 0, goto error);
5236         isl_assert(list->ctx, list->p[0], goto error);
5237         nparam = isl_basic_set_n_param(list->p[0]);
5238         dim = isl_basic_set_n_dim(list->p[0]);
5239         extra = list->p[0]->n_div;
5240         n_eq = list->p[0]->n_eq;
5241         n_ineq = list->p[0]->n_ineq;
5242         for (i = 1; i < list->n; ++i) {
5243                 isl_assert(list->ctx, list->p[i], goto error);
5244                 isl_assert(list->ctx,
5245                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5246                 dim += isl_basic_set_n_dim(list->p[i]);
5247                 extra += list->p[i]->n_div;
5248                 n_eq += list->p[i]->n_eq;
5249                 n_ineq += list->p[i]->n_ineq;
5250         }
5251         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5252                                         n_eq, n_ineq);
5253         if (!product)
5254                 goto error;
5255         dim = 0;
5256         for (i = 0; i < list->n; ++i) {
5257                 set_add_constraints(product,
5258                                         isl_basic_set_copy(list->p[i]), dim);
5259                 dim += isl_basic_set_n_dim(list->p[i]);
5260         }
5261         isl_basic_set_list_free(list);
5262         return product;
5263 error:
5264         isl_basic_set_free(product);
5265         isl_basic_set_list_free(list);
5266         return NULL;
5267 }
5268
5269 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5270 {
5271         int i;
5272         uint32_t hash;
5273         unsigned total;
5274
5275         if (!bset)
5276                 return 0;
5277         bset = isl_basic_set_copy(bset);
5278         bset = isl_basic_set_normalize(bset);
5279         if (!bset)
5280                 return 0;
5281         total = isl_basic_set_total_dim(bset);
5282         isl_hash_byte(hash, bset->n_eq & 0xFF);
5283         for (i = 0; i < bset->n_eq; ++i) {
5284                 uint32_t c_hash;
5285                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5286                 isl_hash_hash(hash, c_hash);
5287         }
5288         isl_hash_byte(hash, bset->n_ineq & 0xFF);
5289         for (i = 0; i < bset->n_ineq; ++i) {
5290                 uint32_t c_hash;
5291                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
5292                 isl_hash_hash(hash, c_hash);
5293         }
5294         isl_hash_byte(hash, bset->n_div & 0xFF);
5295         for (i = 0; i < bset->n_div; ++i) {
5296                 uint32_t c_hash;
5297                 if (isl_int_is_zero(bset->div[i][0]))
5298                         continue;
5299                 isl_hash_byte(hash, i & 0xFF);
5300                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
5301                 isl_hash_hash(hash, c_hash);
5302         }
5303         isl_basic_set_free(bset);
5304         return hash;
5305 }
5306
5307 uint32_t isl_set_get_hash(struct isl_set *set)
5308 {
5309         int i;
5310         uint32_t hash;
5311
5312         if (!set)
5313                 return 0;
5314         set = isl_set_copy(set);
5315         set = isl_set_normalize(set);
5316         if (!set)
5317                 return 0;
5318
5319         hash = isl_hash_init();
5320         for (i = 0; i < set->n; ++i) {
5321                 uint32_t bset_hash;
5322                 bset_hash = isl_basic_set_get_hash(set->p[i]);
5323                 isl_hash_hash(hash, bset_hash);
5324         }
5325
5326         isl_set_free(set);
5327
5328         return hash;
5329 }
5330
5331 /* Check if the value for dimension dim is completely determined
5332  * by the values of the other parameters and variables.
5333  * That is, check if dimension dim is involved in an equality.
5334  */
5335 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
5336 {
5337         int i;
5338         unsigned nparam;
5339
5340         if (!bset)
5341                 return -1;
5342         nparam = isl_basic_set_n_param(bset);
5343         for (i = 0; i < bset->n_eq; ++i)
5344                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
5345                         return 1;
5346         return 0;
5347 }
5348
5349 /* Check if the value for dimension dim is completely determined
5350  * by the values of the other parameters and variables.
5351  * That is, check if dimension dim is involved in an equality
5352  * for each of the subsets.
5353  */
5354 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
5355 {
5356         int i;
5357
5358         if (!set)
5359                 return -1;
5360         for (i = 0; i < set->n; ++i) {
5361                 int unique;
5362                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
5363                 if (unique != 1)
5364                         return unique;
5365         }
5366         return 1;
5367 }