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