isl_map.c

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