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