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