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