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