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