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