isl_map.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  11  */
  12
  13 #include <string.h>
  14 #include <strings.h>
  15 #include "isl_ctx.h"
  16 #include "isl_blk.h"
  17 #include "isl_dim.h"
  18 #include "isl_equalities.h"
  19 #include "isl_list.h"
  20 #include "isl_lp.h"
  21 #include "isl_seq.h"
  22 #include "isl_set.h"
  23 #include "isl_map.h"
  24 #include "isl_map_private.h"
  25 #include "isl_map_piplib.h"
  26 #include "isl_sample.h"
  27 #include "isl_tab.h"
  28 #include "isl_vec.h"
  29
  30 /* Maps dst positions to src positions */
  31 struct isl_dim_map {
  32         unsigned len;
  33         int pos[1];
  34 };
  35
  36 static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
  37 {
  38         int i;
  39         struct isl_dim_map *dim_map;
  40         dim_map = isl_alloc(ctx, struct isl_dim_map,
  41                                 sizeof(struct isl_dim_map) + len * sizeof(int));
  42         if (!dim_map)
  43                 return NULL;
  44         dim_map->len = 1 + len;
  45         dim_map->pos[0] = 0;
  46         for (i = 0; i < len; ++i)
  47                 dim_map->pos[1 + i] = -1;
  48         return dim_map;
  49 }
  50
  51 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
  52 {
  53         switch (type) {
  54         case isl_dim_param:     return dim->nparam;
  55         case isl_dim_in:        return dim->n_in;
  56         case isl_dim_out:       return dim->n_out;
  57         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
  58         default:                return 0;
  59         }
  60 }
  61
  62 static unsigned pos(struct isl_dim *dim, enum isl_dim_type type)
  63 {
  64         switch (type) {
  65         case isl_dim_param:     return 1;
  66         case isl_dim_in:        return 1 + dim->nparam;
  67         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  68         default:                return 0;
  69         }
  70 }
  71
  72 static void isl_dim_map_dim_range(struct isl_dim_map *dim_map,
  73         struct isl_dim *dim, enum isl_dim_type type,
  74         unsigned first, unsigned n, unsigned dst_pos)
  75 {
  76         int i;
  77         unsigned src_pos;
  78
  79         if (!dim_map || !dim)
  80                 return;
  81
  82         src_pos = pos(dim, type);
  83         for (i = 0; i < n; ++i)
  84                 dim_map->pos[1 + dst_pos + i] = src_pos + first + i;
  85 }
  86
  87 static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
  88                 enum isl_dim_type type, unsigned dst_pos)
  89 {
  90         isl_dim_map_dim_range(dim_map, dim, type, 0, n(dim, type), dst_pos);
  91 }
  92
  93 static void isl_dim_map_div(struct isl_dim_map *dim_map,
  94                 struct isl_basic_map *bmap, unsigned dst_pos)
  95 {
  96         int i;
  97         unsigned src_pos;
  98
  99         if (!dim_map || !bmap)
 100                 return;
 101
 102         src_pos = 1 + isl_dim_total(bmap->dim);
 103         for (i = 0; i < bmap->n_div; ++i)
 104                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
 105 }
 106
 107 static void isl_dim_map_dump(struct isl_dim_map *dim_map)
 108 {
 109         int i;
 110
 111         for (i = 0; i < dim_map->len; ++i)
 112                 fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
 113         fprintf(stderr, "\n");
 114 }
 115
 116 unsigned isl_basic_map_dim(const struct isl_basic_map *bmap,
 117                                 enum isl_dim_type type)
 118 {
 119         switch (type) {
 120         case isl_dim_param:
 121         case isl_dim_in:
 122         case isl_dim_out:       return isl_dim_size(bmap->dim, type);
 123         case isl_dim_div:       return bmap->n_div;
 124         case isl_dim_all:       return isl_basic_map_total_dim(bmap);
 125         default:                return 0;
 126         }
 127 }
 128
 129 unsigned isl_map_dim(const struct isl_map *map, enum isl_dim_type type)
 130 {
 131         return map ? n(map->dim, type) : 0;
 132 }
 133
 134 unsigned isl_set_dim(const struct isl_set *set, enum isl_dim_type type)
 135 {
 136         return set ? n(set->dim, type) : 0;
 137 }
 138
 139 unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
 140                                         enum isl_dim_type type)
 141 {
 142         struct isl_dim *dim = bmap->dim;
 143         switch (type) {
 144         case isl_dim_param:     return 1;
 145         case isl_dim_in:        return 1 + dim->nparam;
 146         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 147         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 148         default:                return 0;
 149         }
 150 }
 151
 152 static unsigned map_offset(struct isl_map *map, enum isl_dim_type type)
 153 {
 154         return pos(map->dim, type);
 155 }
 156
 157 unsigned isl_basic_set_dim(const struct isl_basic_set *bset,
 158                                 enum isl_dim_type type)
 159 {
 160         return isl_basic_map_dim((const struct isl_basic_map*)bset, type);
 161 }
 162
 163 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
 164 {
 165         return bset->dim->n_out;
 166 }
 167
 168 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
 169 {
 170         return bset->dim->nparam;
 171 }
 172
 173 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 174 {
 175         return isl_dim_total(bset->dim) + bset->n_div;
 176 }
 177
 178 unsigned isl_set_n_dim(const struct isl_set *set)
 179 {
 180         return set->dim->n_out;
 181 }
 182
 183 unsigned isl_set_n_param(const struct isl_set *set)
 184 {
 185         return set->dim->nparam;
 186 }
 187
 188 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
 189 {
 190         return bmap->dim->n_in;
 191 }
 192
 193 unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
 194 {
 195         return bmap->dim->n_out;
 196 }
 197
 198 unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
 199 {
 200         return bmap->dim->nparam;
 201 }
 202
 203 unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
 204 {
 205         return bmap->n_div;
 206 }
 207
 208 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
 209 {
 210         return isl_dim_total(bmap->dim) + bmap->n_div;
 211 }
 212
 213 unsigned isl_map_n_in(const struct isl_map *map)
 214 {
 215         return map->dim->n_in;
 216 }
 217
 218 unsigned isl_map_n_out(const struct isl_map *map)
 219 {
 220         return map->dim->n_out;
 221 }
 222
 223 unsigned isl_map_n_param(const struct isl_map *map)
 224 {
 225         return map->dim->nparam;
 226 }
 227
 228 int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
 229 {
 230         return map->dim->n_in == set->dim->n_out &&
 231                map->dim->nparam == set->dim->nparam;
 232 }
 233
 234 int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
 235                 struct isl_basic_set *bset)
 236 {
 237         return bmap->dim->n_in == bset->dim->n_out &&
 238                bmap->dim->nparam == bset->dim->nparam;
 239 }
 240
 241 int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
 242                 struct isl_basic_set *bset)
 243 {
 244         return bmap->dim->n_out == bset->dim->n_out &&
 245                bmap->dim->nparam == bset->dim->nparam;
 246 }
 247
 248 struct isl_dim *isl_basic_map_get_dim(struct isl_basic_map *bmap)
 249 {
 250         if (!bmap)
 251                 return NULL;
 252         return isl_dim_copy(bmap->dim);
 253 }
 254
 255 struct isl_dim *isl_basic_set_get_dim(struct isl_basic_set *bset)
 256 {
 257         if (!bset)
 258                 return NULL;
 259         return isl_dim_copy(bset->dim);
 260 }
 261
 262 struct isl_dim *isl_map_get_dim(struct isl_map *map)
 263 {
 264         if (!map)
 265                 return NULL;
 266         return isl_dim_copy(map->dim);
 267 }
 268
 269 struct isl_dim *isl_set_get_dim(struct isl_set *set)
 270 {
 271         if (!set)
 272                 return NULL;
 273         return isl_dim_copy(set->dim);
 274 }
 275
 276 static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 277                 struct isl_basic_map *bmap, unsigned extra,
 278                 unsigned n_eq, unsigned n_ineq)
 279 {
 280         int i;
 281         size_t row_size = 1 + isl_dim_total(bmap->dim) + extra;
 282
 283         bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
 284         if (isl_blk_is_error(bmap->block)) {
 285                 free(bmap);
 286                 return NULL;
 287         }
 288
 289         bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
 290         if (!bmap->ineq) {
 291                 isl_blk_free(ctx, bmap->block);
 292                 free(bmap);
 293                 return NULL;
 294         }
 295
 296         if (extra == 0) {
 297                 bmap->block2 = isl_blk_empty();
 298                 bmap->div = NULL;
 299         } else {
 300                 bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
 301                 if (isl_blk_is_error(bmap->block2)) {
 302                         free(bmap->ineq);
 303                         isl_blk_free(ctx, bmap->block);
 304                         free(bmap);
 305                         return NULL;
 306                 }
 307
 308                 bmap->div = isl_alloc_array(ctx, isl_int *, extra);
 309                 if (!bmap->div) {
 310                         isl_blk_free(ctx, bmap->block2);
 311                         free(bmap->ineq);
 312                         isl_blk_free(ctx, bmap->block);
 313                         free(bmap);
 314                         return NULL;
 315                 }
 316         }
 317
 318         for (i = 0; i < n_ineq + n_eq; ++i)
 319                 bmap->ineq[i] = bmap->block.data + i * row_size;
 320
 321         for (i = 0; i < extra; ++i)
 322                 bmap->div[i] = bmap->block2.data + i * (1 + row_size);
 323
 324         bmap->ctx = ctx;
 325         isl_ctx_ref(ctx);
 326         bmap->ref = 1;
 327         bmap->flags = 0;
 328         bmap->c_size = n_eq + n_ineq;
 329         bmap->eq = bmap->ineq + n_ineq;
 330         bmap->extra = extra;
 331         bmap->n_eq = 0;
 332         bmap->n_ineq = 0;
 333         bmap->n_div = 0;
 334         bmap->sample = NULL;
 335
 336         return bmap;
 337 }
 338
 339 struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
 340                 unsigned nparam, unsigned dim, unsigned extra,
 341                 unsigned n_eq, unsigned n_ineq)
 342 {
 343         struct isl_basic_map *bmap;
 344         bmap = isl_basic_map_alloc(ctx, nparam, 0, dim, extra, n_eq, n_ineq);
 345         return (struct isl_basic_set *)bmap;
 346 }
 347
 348 struct isl_basic_set *isl_basic_set_alloc_dim(struct isl_dim *dim,
 349                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 350 {
 351         struct isl_basic_map *bmap;
 352         if (!dim)
 353                 return NULL;
 354         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
 355         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 356         return (struct isl_basic_set *)bmap;
 357 }
 358
 359 struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_dim *dim,
 360                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 361 {
 362         struct isl_basic_map *bmap;
 363
 364         if (!dim)
 365                 return NULL;
 366         bmap = isl_alloc_type(dim->ctx, struct isl_basic_map);
 367         if (!bmap)
 368                 goto error;
 369         bmap->dim = dim;
 370
 371         return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
 372 error:
 373         isl_dim_free(dim);
 374         return NULL;
 375 }
 376
 377 struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
 378                 unsigned nparam, unsigned in, unsigned out, unsigned extra,
 379                 unsigned n_eq, unsigned n_ineq)
 380 {
 381         struct isl_basic_map *bmap;
 382         struct isl_dim *dim;
 383
 384         dim = isl_dim_alloc(ctx, nparam, in, out);
 385         if (!dim)
 386                 return NULL;
 387
 388         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 389         return bmap;
 390 }
 391
 392 static void dup_constraints(
 393                 struct isl_basic_map *dst, struct isl_basic_map *src)
 394 {
 395         int i;
 396         unsigned total = isl_basic_map_total_dim(src);
 397
 398         for (i = 0; i < src->n_eq; ++i) {
 399                 int j = isl_basic_map_alloc_equality(dst);
 400                 isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
 401         }
 402
 403         for (i = 0; i < src->n_ineq; ++i) {
 404                 int j = isl_basic_map_alloc_inequality(dst);
 405                 isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
 406         }
 407
 408         for (i = 0; i < src->n_div; ++i) {
 409                 int j = isl_basic_map_alloc_div(dst);
 410                 isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
 411         }
 412         ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
 413 }
 414
 415 struct isl_basic_map *isl_basic_map_dup(struct isl_basic_map *bmap)
 416 {
 417         struct isl_basic_map *dup;
 418
 419         if (!bmap)
 420                 return NULL;
 421         dup = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
 422                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
 423         if (!dup)
 424                 return NULL;
 425         dup_constraints(dup, bmap);
 426         dup->flags = bmap->flags;
 427         dup->sample = isl_vec_copy(bmap->sample);
 428         return dup;
 429 }
 430
 431 struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
 432 {
 433         struct isl_basic_map *dup;
 434
 435         dup = isl_basic_map_dup((struct isl_basic_map *)bset);
 436         return (struct isl_basic_set *)dup;
 437 }
 438
 439 struct isl_basic_set *isl_basic_set_copy(struct isl_basic_set *bset)
 440 {
 441         if (!bset)
 442                 return NULL;
 443
 444         if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
 445                 bset->ref++;
 446                 return bset;
 447         }
 448         return isl_basic_set_dup(bset);
 449 }
 450
 451 struct isl_set *isl_set_copy(struct isl_set *set)
 452 {
 453         if (!set)
 454                 return NULL;
 455
 456         set->ref++;
 457         return set;
 458 }
 459
 460 struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
 461 {
 462         if (!bmap)
 463                 return NULL;
 464
 465         if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
 466                 bmap->ref++;
 467                 return bmap;
 468         }
 469         bmap = isl_basic_map_dup(bmap);
 470         if (bmap)
 471                 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
 472         return bmap;
 473 }
 474
 475 struct isl_map *isl_map_copy(struct isl_map *map)
 476 {
 477         if (!map)
 478                 return NULL;
 479
 480         map->ref++;
 481         return map;
 482 }
 483
 484 void isl_basic_map_free(struct isl_basic_map *bmap)
 485 {
 486         if (!bmap)
 487                 return;
 488
 489         if (--bmap->ref > 0)
 490                 return;
 491
 492         isl_ctx_deref(bmap->ctx);
 493         free(bmap->div);
 494         isl_blk_free(bmap->ctx, bmap->block2);
 495         free(bmap->ineq);
 496         isl_blk_free(bmap->ctx, bmap->block);
 497         isl_vec_free(bmap->sample);
 498         isl_dim_free(bmap->dim);
 499         free(bmap);
 500 }
 501
 502 void isl_basic_set_free(struct isl_basic_set *bset)
 503 {
 504         isl_basic_map_free((struct isl_basic_map *)bset);
 505 }
 506
 507 static int room_for_con(struct isl_basic_map *bmap, unsigned n)
 508 {
 509         return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
 510 }
 511
 512 int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
 513 {
 514         struct isl_ctx *ctx;
 515         if (!bmap)
 516                 return -1;
 517         ctx = bmap->ctx;
 518         isl_assert(ctx, room_for_con(bmap, 1), return -1);
 519         isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
 520                         return -1);
 521         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 522         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 523         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
 524         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 525         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 526         if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
 527                 isl_int *t;
 528                 int j = isl_basic_map_alloc_inequality(bmap);
 529                 if (j < 0)
 530                         return -1;
 531                 t = bmap->ineq[j];
 532                 bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
 533                 bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
 534                 bmap->eq[-1] = t;
 535                 bmap->n_eq++;
 536                 bmap->n_ineq--;
 537                 bmap->eq--;
 538                 return 0;
 539         }
 540         isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
 541                       bmap->extra - bmap->n_div);
 542         return bmap->n_eq++;
 543 }
 544
 545 int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
 546 {
 547         return isl_basic_map_alloc_equality((struct isl_basic_map *)bset);
 548 }
 549
 550 int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
 551 {
 552         if (!bmap)
 553                 return -1;
 554         isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
 555         bmap->n_eq -= n;
 556         return 0;
 557 }
 558
 559 int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
 560 {
 561         return isl_basic_map_free_equality((struct isl_basic_map *)bset, n);
 562 }
 563
 564 int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
 565 {
 566         isl_int *t;
 567         if (!bmap)
 568                 return -1;
 569         isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
 570
 571         if (pos != bmap->n_eq - 1) {
 572                 t = bmap->eq[pos];
 573                 bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
 574                 bmap->eq[bmap->n_eq - 1] = t;
 575         }
 576         bmap->n_eq--;
 577         return 0;
 578 }
 579
 580 int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos)
 581 {
 582         return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos);
 583 }
 584
 585 void isl_basic_map_inequality_to_equality(
 586                 struct isl_basic_map *bmap, unsigned pos)
 587 {
 588         isl_int *t;
 589
 590         t = bmap->ineq[pos];
 591         bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 592         bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
 593         bmap->eq[-1] = t;
 594         bmap->n_eq++;
 595         bmap->n_ineq--;
 596         bmap->eq--;
 597         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 598         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 599         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 600         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 601 }
 602
 603 static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
 604 {
 605         return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
 606 }
 607
 608 int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap)
 609 {
 610         struct isl_ctx *ctx;
 611         if (!bmap)
 612                 return -1;
 613         ctx = bmap->ctx;
 614         isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
 615         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
 616         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 617         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 618         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 619         isl_seq_clr(bmap->ineq[bmap->n_ineq] +
 620                       1 + isl_basic_map_total_dim(bmap),
 621                       bmap->extra - bmap->n_div);
 622         return bmap->n_ineq++;
 623 }
 624
 625 int isl_basic_set_alloc_inequality(struct isl_basic_set *bset)
 626 {
 627         return isl_basic_map_alloc_inequality((struct isl_basic_map *)bset);
 628 }
 629
 630 int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
 631 {
 632         if (!bmap)
 633                 return -1;
 634         isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
 635         bmap->n_ineq -= n;
 636         return 0;
 637 }
 638
 639 int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
 640 {
 641         return isl_basic_map_free_inequality((struct isl_basic_map *)bset, n);
 642 }
 643
 644 int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
 645 {
 646         isl_int *t;
 647         if (!bmap)
 648                 return -1;
 649         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
 650
 651         if (pos != bmap->n_ineq - 1) {
 652                 t = bmap->ineq[pos];
 653                 bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 654                 bmap->ineq[bmap->n_ineq - 1] = t;
 655                 ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 656         }
 657         bmap->n_ineq--;
 658         return 0;
 659 }
 660
 661 int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
 662 {
 663         return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos);
 664 }
 665
 666 __isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
 667         isl_int *eq)
 668 {
 669         int k;
 670
 671         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
 672         if (!bmap)
 673                 return NULL;
 674         k = isl_basic_map_alloc_equality(bmap);
 675         if (k < 0)
 676                 goto error;
 677         isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
 678         return bmap;
 679 error:
 680         isl_basic_map_free(bmap);
 681         return NULL;
 682 }
 683
 684 __isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
 685         isl_int *eq)
 686 {
 687         return (isl_basic_set *)
 688                 isl_basic_map_add_eq((isl_basic_map *)bset, eq);
 689 }
 690
 691 __isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
 692         isl_int *ineq)
 693 {
 694         int k;
 695
 696         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
 697         if (!bmap)
 698                 return NULL;
 699         k = isl_basic_map_alloc_inequality(bmap);
 700         if (k < 0)
 701                 goto error;
 702         isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
 703         return bmap;
 704 error:
 705         isl_basic_map_free(bmap);
 706         return NULL;
 707 }
 708
 709 __isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
 710         isl_int *ineq)
 711 {
 712         return (isl_basic_set *)
 713                 isl_basic_map_add_ineq((isl_basic_map *)bset, ineq);
 714 }
 715
 716 int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
 717 {
 718         if (!bmap)
 719                 return -1;
 720         isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
 721         isl_seq_clr(bmap->div[bmap->n_div] +
 722                       1 + 1 + isl_basic_map_total_dim(bmap),
 723                       bmap->extra - bmap->n_div);
 724         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 725         return bmap->n_div++;
 726 }
 727
 728 int isl_basic_set_alloc_div(struct isl_basic_set *bset)
 729 {
 730         return isl_basic_map_alloc_div((struct isl_basic_map *)bset);
 731 }
 732
 733 int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
 734 {
 735         if (!bmap)
 736                 return -1;
 737         isl_assert(bmap->ctx, n <= bmap->n_div, return -1);
 738         bmap->n_div -= n;
 739         return 0;
 740 }
 741
 742 int isl_basic_set_free_div(struct isl_basic_set *bset, unsigned n)
 743 {
 744         return isl_basic_map_free_div((struct isl_basic_map *)bset, n);
 745 }
 746
 747 /* Copy constraint from src to dst, putting the vars of src at offset
 748  * dim_off in dst and the divs of src at offset div_off in dst.
 749  * If both sets are actually map, then dim_off applies to the input
 750  * variables.
 751  */
 752 static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
 753                             struct isl_basic_map *src_map, isl_int *src,
 754                             unsigned in_off, unsigned out_off, unsigned div_off)
 755 {
 756         unsigned src_nparam = isl_basic_map_n_param(src_map);
 757         unsigned dst_nparam = isl_basic_map_n_param(dst_map);
 758         unsigned src_in = isl_basic_map_n_in(src_map);
 759         unsigned dst_in = isl_basic_map_n_in(dst_map);
 760         unsigned src_out = isl_basic_map_n_out(src_map);
 761         unsigned dst_out = isl_basic_map_n_out(dst_map);
 762         isl_int_set(dst[0], src[0]);
 763         isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
 764         if (dst_nparam > src_nparam)
 765                 isl_seq_clr(dst+1+src_nparam,
 766                                 dst_nparam - src_nparam);
 767         isl_seq_clr(dst+1+dst_nparam, in_off);
 768         isl_seq_cpy(dst+1+dst_nparam+in_off,
 769                     src+1+src_nparam,
 770                     isl_min(dst_in-in_off, src_in));
 771         if (dst_in-in_off > src_in)
 772                 isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
 773                                 dst_in - in_off - src_in);
 774         isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
 775         isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
 776                     src+1+src_nparam+src_in,
 777                     isl_min(dst_out-out_off, src_out));
 778         if (dst_out-out_off > src_out)
 779                 isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
 780                                 dst_out - out_off - src_out);
 781         isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
 782         isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
 783                     src+1+src_nparam+src_in+src_out,
 784                     isl_min(dst_map->extra-div_off, src_map->n_div));
 785         if (dst_map->n_div-div_off > src_map->n_div)
 786                 isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
 787                                 div_off+src_map->n_div,
 788                                 dst_map->n_div - div_off - src_map->n_div);
 789 }
 790
 791 static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
 792                      struct isl_basic_map *src_map, isl_int *src,
 793                      unsigned in_off, unsigned out_off, unsigned div_off)
 794 {
 795         isl_int_set(dst[0], src[0]);
 796         copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
 797 }
 798
 799 static struct isl_basic_map *add_constraints(struct isl_basic_map *bmap1,
 800                 struct isl_basic_map *bmap2, unsigned i_pos, unsigned o_pos)
 801 {
 802         int i;
 803         unsigned div_off;
 804
 805         if (!bmap1 || !bmap2)
 806                 goto error;
 807
 808         div_off = bmap1->n_div;
 809
 810         for (i = 0; i < bmap2->n_eq; ++i) {
 811                 int i1 = isl_basic_map_alloc_equality(bmap1);
 812                 if (i1 < 0)
 813                         goto error;
 814                 copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
 815                                 i_pos, o_pos, div_off);
 816         }
 817
 818         for (i = 0; i < bmap2->n_ineq; ++i) {
 819                 int i1 = isl_basic_map_alloc_inequality(bmap1);
 820                 if (i1 < 0)
 821                         goto error;
 822                 copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
 823                                 i_pos, o_pos, div_off);
 824         }
 825
 826         for (i = 0; i < bmap2->n_div; ++i) {
 827                 int i1 = isl_basic_map_alloc_div(bmap1);
 828                 if (i1 < 0)
 829                         goto error;
 830                 copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
 831                          i_pos, o_pos, div_off);
 832         }
 833
 834         isl_basic_map_free(bmap2);
 835
 836         return bmap1;
 837
 838 error:
 839         isl_basic_map_free(bmap1);
 840         isl_basic_map_free(bmap2);
 841         return NULL;
 842 }
 843
 844 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
 845                                         struct isl_dim_map *dim_map)
 846 {
 847         int i;
 848
 849         for (i = 0; i < dim_map->len; ++i) {
 850                 if (dim_map->pos[i] < 0)
 851                         isl_int_set_si(dst[i], 0);
 852                 else
 853                         isl_int_set(dst[i], src[dim_map->pos[i]]);
 854         }
 855 }
 856
 857 static void copy_div_dim_map(isl_int *dst, isl_int *src,
 858                                         struct isl_dim_map *dim_map)
 859 {
 860         isl_int_set(dst[0], src[0]);
 861         copy_constraint_dim_map(dst+1, src+1, dim_map);
 862 }
 863
 864 static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst,
 865                 struct isl_basic_map *src, struct isl_dim_map *dim_map)
 866 {
 867         int i;
 868
 869         if (!src || !dst || !dim_map)
 870                 goto error;
 871
 872         for (i = 0; i < src->n_eq; ++i) {
 873                 int i1 = isl_basic_map_alloc_equality(dst);
 874                 if (i1 < 0)
 875                         goto error;
 876                 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
 877         }
 878
 879         for (i = 0; i < src->n_ineq; ++i) {
 880                 int i1 = isl_basic_map_alloc_inequality(dst);
 881                 if (i1 < 0)
 882                         goto error;
 883                 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
 884         }
 885
 886         for (i = 0; i < src->n_div; ++i) {
 887                 int i1 = isl_basic_map_alloc_div(dst);
 888                 if (i1 < 0)
 889                         goto error;
 890                 copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
 891         }
 892
 893         free(dim_map);
 894         isl_basic_map_free(src);
 895
 896         return dst;
 897 error:
 898         free(dim_map);
 899         isl_basic_map_free(src);
 900         isl_basic_map_free(dst);
 901         return NULL;
 902 }
 903
 904 struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
 905                 struct isl_basic_set *bset2, unsigned pos)
 906 {
 907         return (struct isl_basic_set *)
 908                 add_constraints((struct isl_basic_map *)bset1,
 909                                 (struct isl_basic_map *)bset2, 0, pos);
 910 }
 911
 912 struct isl_basic_map *isl_basic_map_extend_dim(struct isl_basic_map *base,
 913                 struct isl_dim *dim, unsigned extra,
 914                 unsigned n_eq, unsigned n_ineq)
 915 {
 916         struct isl_basic_map *ext;
 917         unsigned flags;
 918         int dims_ok;
 919
 920         if (!dim)
 921                 goto error;
 922
 923         if (!base)
 924                 goto error;
 925
 926         dims_ok = isl_dim_equal(base->dim, dim) &&
 927                   base->extra >= base->n_div + extra;
 928
 929         if (dims_ok && room_for_con(base, n_eq + n_ineq) &&
 930                        room_for_ineq(base, n_ineq)) {
 931                 isl_dim_free(dim);
 932                 return base;
 933         }
 934
 935         isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
 936         isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
 937         isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
 938         extra += base->extra;
 939         n_eq += base->n_eq;
 940         n_ineq += base->n_ineq;
 941
 942         ext = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 943         dim = NULL;
 944         if (!ext)
 945                 goto error;
 946
 947         if (dims_ok)
 948                 ext->sample = isl_vec_copy(base->sample);
 949         flags = base->flags;
 950         ext = add_constraints(ext, base, 0, 0);
 951         if (ext) {
 952                 ext->flags = flags;
 953                 ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
 954         }
 955
 956         return ext;
 957
 958 error:
 959         isl_dim_free(dim);
 960         isl_basic_map_free(base);
 961         return NULL;
 962 }
 963
 964 struct isl_basic_set *isl_basic_set_extend_dim(struct isl_basic_set *base,
 965                 struct isl_dim *dim, unsigned extra,
 966                 unsigned n_eq, unsigned n_ineq)
 967 {
 968         return (struct isl_basic_set *)
 969                 isl_basic_map_extend_dim((struct isl_basic_map *)base, dim,
 970                                                         extra, n_eq, n_ineq);
 971 }
 972
 973 struct isl_basic_map *isl_basic_map_extend_constraints(
 974                 struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
 975 {
 976         if (!base)
 977                 return NULL;
 978         return isl_basic_map_extend_dim(base, isl_dim_copy(base->dim),
 979                                         0, n_eq, n_ineq);
 980 }
 981
 982 struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
 983                 unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
 984                 unsigned n_eq, unsigned n_ineq)
 985 {
 986         struct isl_basic_map *bmap;
 987         struct isl_dim *dim;
 988
 989         if (!base)
 990                 return NULL;
 991         dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out);
 992         if (!dim)
 993                 return NULL;
 994
 995         bmap = isl_basic_map_extend_dim(base, dim, extra, n_eq, n_ineq);
 996         return bmap;
 997 }
 998
 999 struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
1000                 unsigned nparam, unsigned dim, unsigned extra,
1001                 unsigned n_eq, unsigned n_ineq)
1002 {
1003         return (struct isl_basic_set *)
1004                 isl_basic_map_extend((struct isl_basic_map *)base,
1005                                         nparam, 0, dim, extra, n_eq, n_ineq);
1006 }
1007
1008 struct isl_basic_set *isl_basic_set_extend_constraints(
1009                 struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
1010 {
1011         return (struct isl_basic_set *)
1012                 isl_basic_map_extend_constraints((struct isl_basic_map *)base,
1013                                                     n_eq, n_ineq);
1014 }
1015
1016 struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset)
1017 {
1018         return (struct isl_basic_set *)
1019                 isl_basic_map_cow((struct isl_basic_map *)bset);
1020 }
1021
1022 struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
1023 {
1024         if (!bmap)
1025                 return NULL;
1026
1027         if (bmap->ref > 1) {
1028                 bmap->ref--;
1029                 bmap = isl_basic_map_dup(bmap);
1030         }
1031         ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
1032         return bmap;
1033 }
1034
1035 struct isl_set *isl_set_cow(struct isl_set *set)
1036 {
1037         if (!set)
1038                 return NULL;
1039
1040         if (set->ref == 1)
1041                 return set;
1042         set->ref--;
1043         return isl_set_dup(set);
1044 }
1045
1046 struct isl_map *isl_map_cow(struct isl_map *map)
1047 {
1048         if (!map)
1049                 return NULL;
1050
1051         if (map->ref == 1)
1052                 return map;
1053         map->ref--;
1054         return isl_map_dup(map);
1055 }
1056
1057 static void swap_vars(struct isl_blk blk, isl_int *a,
1058                         unsigned a_len, unsigned b_len)
1059 {
1060         isl_seq_cpy(blk.data, a+a_len, b_len);
1061         isl_seq_cpy(blk.data+b_len, a, a_len);
1062         isl_seq_cpy(a, blk.data, b_len+a_len);
1063 }
1064
1065 struct isl_basic_set *isl_basic_set_swap_vars(
1066                 struct isl_basic_set *bset, unsigned n)
1067 {
1068         int i;
1069         struct isl_blk blk;
1070         unsigned dim;
1071         unsigned nparam;
1072
1073         if (!bset)
1074                 goto error;
1075
1076         nparam = isl_basic_set_n_param(bset);
1077         dim = isl_basic_set_n_dim(bset);
1078         isl_assert(bset->ctx, n <= dim, goto error);
1079
1080         if (n == dim)
1081                 return bset;
1082
1083         bset = isl_basic_set_cow(bset);
1084         if (!bset)
1085                 return NULL;
1086
1087         blk = isl_blk_alloc(bset->ctx, dim);
1088         if (isl_blk_is_error(blk))
1089                 goto error;
1090
1091         for (i = 0; i < bset->n_eq; ++i)
1092                 swap_vars(blk,
1093                           bset->eq[i]+1+nparam, n, dim - n);
1094
1095         for (i = 0; i < bset->n_ineq; ++i)
1096                 swap_vars(blk,
1097                           bset->ineq[i]+1+nparam, n, dim - n);
1098
1099         for (i = 0; i < bset->n_div; ++i)
1100                 swap_vars(blk,
1101                           bset->div[i]+1+1+nparam, n, dim - n);
1102
1103         isl_blk_free(bset->ctx, blk);
1104
1105         ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
1106         return isl_basic_set_gauss(bset, NULL);
1107 error:
1108         isl_basic_set_free(bset);
1109         return NULL;
1110 }
1111
1112 struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n)
1113 {
1114         int i;
1115         set = isl_set_cow(set);
1116         if (!set)
1117                 return NULL;
1118
1119         for (i = 0; i < set->n; ++i) {
1120                 set->p[i] = isl_basic_set_swap_vars(set->p[i], n);
1121                 if (!set->p[i]) {
1122                         isl_set_free(set);
1123                         return NULL;
1124                 }
1125         }
1126         ISL_F_CLR(set, ISL_SET_NORMALIZED);
1127         return set;
1128 }
1129
1130 struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
1131 {
1132         int i = 0;
1133         unsigned total;
1134         if (!bmap)
1135                 goto error;
1136         total = isl_basic_map_total_dim(bmap);
1137         isl_basic_map_free_div(bmap, bmap->n_div);
1138         isl_basic_map_free_inequality(bmap, bmap->n_ineq);
1139         if (bmap->n_eq > 0)
1140                 isl_basic_map_free_equality(bmap, bmap->n_eq-1);
1141         else {
1142                 i = isl_basic_map_alloc_equality(bmap);
1143                 if (i < 0)
1144                         goto error;
1145         }
1146         isl_int_set_si(bmap->eq[i][0], 1);
1147         isl_seq_clr(bmap->eq[i]+1, total);
1148         ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
1149         isl_vec_free(bmap->sample);
1150         bmap->sample = NULL;
1151         return isl_basic_map_finalize(bmap);
1152 error:
1153         isl_basic_map_free(bmap);
1154         return NULL;
1155 }
1156
1157 struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset)
1158 {
1159         return (struct isl_basic_set *)
1160                 isl_basic_map_set_to_empty((struct isl_basic_map *)bset);
1161 }
1162
1163 void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
1164 {
1165         int i;
1166         unsigned off = isl_dim_total(bmap->dim);
1167         isl_int *t = bmap->div[a];
1168         bmap->div[a] = bmap->div[b];
1169         bmap->div[b] = t;
1170
1171         for (i = 0; i < bmap->n_eq; ++i)
1172                 isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
1173
1174         for (i = 0; i < bmap->n_ineq; ++i)
1175                 isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
1176
1177         for (i = 0; i < bmap->n_div; ++i)
1178                 isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
1179         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1180 }
1181
1182 /* Eliminate the specified n dimensions starting at first from the
1183  * constraints using Fourier-Motzkin.  The dimensions themselves
1184  * are not removed.
1185  */
1186 __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
1187         enum isl_dim_type type, unsigned first, unsigned n)
1188 {
1189         int i;
1190
1191         if (!map)
1192                 return NULL;
1193         if (n == 0)
1194                 return map;
1195
1196         map = isl_map_cow(map);
1197         if (!map)
1198                 return NULL;
1199         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
1200         first += pos(map->dim, type) - 1;
1201
1202         for (i = 0; i < map->n; ++i) {
1203                 map->p[i] = isl_basic_map_eliminate_vars(map->p[i], first, n);
1204                 if (!map->p[i])
1205                         goto error;
1206         }
1207         return map;
1208 error:
1209         isl_map_free(map);
1210         return NULL;
1211 }
1212
1213 /* Eliminate the specified n dimensions starting at first from the
1214  * constraints using Fourier-Motzkin.  The dimensions themselves
1215  * are not removed.
1216  */
1217 __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
1218         enum isl_dim_type type, unsigned first, unsigned n)
1219 {
1220         return (isl_set *)isl_map_eliminate((isl_map *)set, type, first, n);
1221 }
1222
1223 /* Eliminate the specified n dimensions starting at first from the
1224  * constraints using Fourier-Motzkin.  The dimensions themselves
1225  * are not removed.
1226  */
1227 __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
1228         unsigned first, unsigned n)
1229 {
1230         return isl_set_eliminate(set, isl_dim_set, first, n);
1231 }
1232
1233 /* Project out n dimensions starting at first using Fourier-Motzkin */
1234 struct isl_set *isl_set_remove_dims(struct isl_set *set,
1235         unsigned first, unsigned n)
1236 {
1237         set = isl_set_eliminate_dims(set, first, n);
1238         set = isl_set_drop_dims(set, first, n);
1239         return set;
1240 }
1241
1242 struct isl_basic_set *isl_basic_set_remove_divs(struct isl_basic_set *bset)
1243 {
1244         bset = isl_basic_set_eliminate_vars(bset, isl_dim_total(bset->dim),
1245                                                 bset->n_div);
1246         if (!bset)
1247                 return NULL;
1248         bset->n_div = 0;
1249         return bset;
1250 }
1251
1252 struct isl_set *isl_set_remove_divs(struct isl_set *set)
1253 {
1254         int i;
1255
1256         if (!set)
1257                 return NULL;
1258         if (set->n == 0)
1259                 return set;
1260
1261         set = isl_set_cow(set);
1262         if (!set)
1263                 return NULL;
1264
1265         for (i = 0; i < set->n; ++i) {
1266                 set->p[i] = isl_basic_set_remove_divs(set->p[i]);
1267                 if (!set->p[i])
1268                         goto error;
1269         }
1270         return set;
1271 error:
1272         isl_set_free(set);
1273         return NULL;
1274 }
1275
1276 struct isl_basic_map *isl_basic_map_remove(struct isl_basic_map *bmap,
1277         enum isl_dim_type type, unsigned first, unsigned n)
1278 {
1279         if (!bmap)
1280                 return NULL;
1281         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
1282                         goto error);
1283         if (n == 0)
1284                 return bmap;
1285         bmap = isl_basic_map_eliminate_vars(bmap,
1286                         isl_basic_map_offset(bmap, type) - 1 + first, n);
1287         if (!bmap)
1288                 return bmap;
1289         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && type == isl_dim_div)
1290                 return bmap;
1291         bmap = isl_basic_map_drop(bmap, type, first, n);
1292         return bmap;
1293 error:
1294         isl_basic_map_free(bmap);
1295         return NULL;
1296 }
1297
1298 __isl_give isl_basic_set *isl_basic_set_remove(__isl_take isl_basic_set *bset,
1299         enum isl_dim_type type, unsigned first, unsigned n)
1300 {
1301         return (isl_basic_set *)
1302                 isl_basic_map_remove((isl_basic_map *)bset, type, first, n);
1303 }
1304
1305 struct isl_map *isl_map_remove(struct isl_map *map,
1306         enum isl_dim_type type, unsigned first, unsigned n)
1307 {
1308         int i;
1309
1310         if (n == 0)
1311                 return map;
1312
1313         map = isl_map_cow(map);
1314         if (!map)
1315                 return NULL;
1316         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
1317
1318         for (i = 0; i < map->n; ++i) {
1319                 map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
1320                         isl_basic_map_offset(map->p[i], type) - 1 + first, n);
1321                 if (!map->p[i])
1322                         goto error;
1323         }
1324         map = isl_map_drop(map, type, first, n);
1325         return map;
1326 error:
1327         isl_map_free(map);
1328         return NULL;
1329 }
1330
1331 __isl_give isl_set *isl_set_remove(__isl_take isl_set *bset,
1332         enum isl_dim_type type, unsigned first, unsigned n)
1333 {
1334         return (isl_set *)isl_map_remove((isl_map *)bset, type, first, n);
1335 }
1336
1337 /* Project out n inputs starting at first using Fourier-Motzkin */
1338 struct isl_map *isl_map_remove_inputs(struct isl_map *map,
1339         unsigned first, unsigned n)
1340 {
1341         return isl_map_remove(map, isl_dim_in, first, n);
1342 }
1343
1344 /* Project out n dimensions starting at first using Fourier-Motzkin */
1345 struct isl_basic_set *isl_basic_set_remove_dims(struct isl_basic_set *bset,
1346         unsigned first, unsigned n)
1347 {
1348         unsigned nparam = isl_basic_set_n_param(bset);
1349         bset = isl_basic_set_eliminate_vars(bset, nparam + first, n);
1350         bset = isl_basic_set_drop_dims(bset, first, n);
1351         return bset;
1352 }
1353
1354 static void dump_term(struct isl_basic_map *bmap,
1355                         isl_int c, int pos, FILE *out)
1356 {
1357         const char *name;
1358         unsigned in = isl_basic_map_n_in(bmap);
1359         unsigned dim = in + isl_basic_map_n_out(bmap);
1360         unsigned nparam = isl_basic_map_n_param(bmap);
1361         if (!pos)
1362                 isl_int_print(out, c, 0);
1363         else {
1364                 if (!isl_int_is_one(c))
1365                         isl_int_print(out, c, 0);
1366                 if (pos < 1 + nparam) {
1367                         name = isl_dim_get_name(bmap->dim,
1368                                                 isl_dim_param, pos - 1);
1369                         if (name)
1370                                 fprintf(out, "%s", name);
1371                         else
1372                                 fprintf(out, "p%d", pos - 1);
1373                 } else if (pos < 1 + nparam + in)
1374                         fprintf(out, "i%d", pos - 1 - nparam);
1375                 else if (pos < 1 + nparam + dim)
1376                         fprintf(out, "o%d", pos - 1 - nparam - in);
1377                 else
1378                         fprintf(out, "e%d", pos - 1 - nparam - dim);
1379         }
1380 }
1381
1382 static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
1383                                 int sign, FILE *out)
1384 {
1385         int i;
1386         int first;
1387         unsigned len = 1 + isl_basic_map_total_dim(bmap);
1388         isl_int v;
1389
1390         isl_int_init(v);
1391         for (i = 0, first = 1; i < len; ++i) {
1392                 if (isl_int_sgn(c[i]) * sign <= 0)
1393                         continue;
1394                 if (!first)
1395                         fprintf(out, " + ");
1396                 first = 0;
1397                 isl_int_abs(v, c[i]);
1398                 dump_term(bmap, v, i, out);
1399         }
1400         isl_int_clear(v);
1401         if (first)
1402                 fprintf(out, "0");
1403 }
1404
1405 static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
1406                                 const char *op, FILE *out, int indent)
1407 {
1408         int i;
1409
1410         fprintf(out, "%*s", indent, "");
1411
1412         dump_constraint_sign(bmap, c, 1, out);
1413         fprintf(out, " %s ", op);
1414         dump_constraint_sign(bmap, c, -1, out);
1415
1416         fprintf(out, "\n");
1417
1418         for (i = bmap->n_div; i < bmap->extra; ++i) {
1419                 if (isl_int_is_zero(c[1+isl_dim_total(bmap->dim)+i]))
1420                         continue;
1421                 fprintf(out, "%*s", indent, "");
1422                 fprintf(out, "ERROR: unused div coefficient not zero\n");
1423                 abort();
1424         }
1425 }
1426
1427 static void dump_constraints(struct isl_basic_map *bmap,
1428                                 isl_int **c, unsigned n,
1429                                 const char *op, FILE *out, int indent)
1430 {
1431         int i;
1432
1433         for (i = 0; i < n; ++i)
1434                 dump_constraint(bmap, c[i], op, out, indent);
1435 }
1436
1437 static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
1438 {
1439         int j;
1440         int first = 1;
1441         unsigned total = isl_basic_map_total_dim(bmap);
1442
1443         for (j = 0; j < 1 + total; ++j) {
1444                 if (isl_int_is_zero(exp[j]))
1445                         continue;
1446                 if (!first && isl_int_is_pos(exp[j]))
1447                         fprintf(out, "+");
1448                 dump_term(bmap, exp[j], j, out);
1449                 first = 0;
1450         }
1451 }
1452
1453 static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
1454 {
1455         int i;
1456
1457         dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
1458         dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
1459
1460         for (i = 0; i < bmap->n_div; ++i) {
1461                 fprintf(out, "%*s", indent, "");
1462                 fprintf(out, "e%d = [(", i);
1463                 dump_affine(bmap, bmap->div[i]+1, out);
1464                 fprintf(out, ")/");
1465                 isl_int_print(out, bmap->div[i][0], 0);
1466                 fprintf(out, "]\n");
1467         }
1468 }
1469
1470 void isl_basic_set_dump(struct isl_basic_set *bset, FILE *out, int indent)
1471 {
1472         if (!bset) {
1473                 fprintf(out, "null basic set\n");
1474                 return;
1475         }
1476
1477         fprintf(out, "%*s", indent, "");
1478         fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
1479                         bset->ref, bset->dim->nparam, bset->dim->n_out,
1480                         bset->extra, bset->flags);
1481         dump((struct isl_basic_map *)bset, out, indent);
1482 }
1483
1484 void isl_basic_map_dump(struct isl_basic_map *bmap, FILE *out, int indent)
1485 {
1486         if (!bmap) {
1487                 fprintf(out, "null basic map\n");
1488                 return;
1489         }
1490
1491         fprintf(out, "%*s", indent, "");
1492         fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
1493                         "flags: %x, n_name: %d\n",
1494                 bmap->ref,
1495                 bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
1496                 bmap->extra, bmap->flags, bmap->dim->n_name);
1497         dump(bmap, out, indent);
1498 }
1499
1500 int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
1501 {
1502         unsigned total;
1503         if (!bmap)
1504                 return -1;
1505         total = isl_basic_map_total_dim(bmap);
1506         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
1507         isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
1508         isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
1509         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1510         return 0;
1511 }
1512
1513 struct isl_set *isl_set_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
1514 {
1515         struct isl_set *set;
1516
1517         if (!dim)
1518                 return NULL;
1519         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
1520         isl_assert(dim->ctx, n >= 0, return NULL);
1521         set = isl_alloc(dim->ctx, struct isl_set,
1522                         sizeof(struct isl_set) +
1523                         (n - 1) * sizeof(struct isl_basic_set *));
1524         if (!set)
1525                 goto error;
1526
1527         set->ctx = dim->ctx;
1528         isl_ctx_ref(set->ctx);
1529         set->ref = 1;
1530         set->size = n;
1531         set->n = 0;
1532         set->dim = dim;
1533         set->flags = flags;
1534         return set;
1535 error:
1536         isl_dim_free(dim);
1537         return NULL;
1538 }
1539
1540 struct isl_set *isl_set_alloc(struct isl_ctx *ctx,
1541                 unsigned nparam, unsigned dim, int n, unsigned flags)
1542 {
1543         struct isl_set *set;
1544         struct isl_dim *dims;
1545
1546         dims = isl_dim_alloc(ctx, nparam, 0, dim);
1547         if (!dims)
1548                 return NULL;
1549
1550         set = isl_set_alloc_dim(dims, n, flags);
1551         return set;
1552 }
1553
1554 /* Make sure "map" has room for at least "n" more basic maps.
1555  */
1556 struct isl_map *isl_map_grow(struct isl_map *map, int n)
1557 {
1558         int i;
1559         struct isl_map *grown = NULL;
1560
1561         if (!map)
1562                 return NULL;
1563         isl_assert(map->ctx, n >= 0, goto error);
1564         if (map->n + n <= map->size)
1565                 return map;
1566         grown = isl_map_alloc_dim(isl_map_get_dim(map), map->n + n, map->flags);
1567         if (!grown)
1568                 goto error;
1569         for (i = 0; i < map->n; ++i) {
1570                 grown->p[i] = isl_basic_map_copy(map->p[i]);
1571                 if (!grown->p[i])
1572                         goto error;
1573                 grown->n++;
1574         }
1575         isl_map_free(map);
1576         return grown;
1577 error:
1578         isl_map_free(grown);
1579         isl_map_free(map);
1580         return NULL;
1581 }
1582
1583 /* Make sure "set" has room for at least "n" more basic sets.
1584  */
1585 struct isl_set *isl_set_grow(struct isl_set *set, int n)
1586 {
1587         return (struct isl_set *)isl_map_grow((struct isl_map *)set, n);
1588 }
1589
1590 struct isl_set *isl_set_dup(struct isl_set *set)
1591 {
1592         int i;
1593         struct isl_set *dup;
1594
1595         if (!set)
1596                 return NULL;
1597
1598         dup = isl_set_alloc_dim(isl_dim_copy(set->dim), set->n, set->flags);
1599         if (!dup)
1600                 return NULL;
1601         for (i = 0; i < set->n; ++i)
1602                 dup = isl_set_add_basic_set(dup, isl_basic_set_copy(set->p[i]));
1603         return dup;
1604 }
1605
1606 struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset)
1607 {
1608         struct isl_set *set;
1609
1610         if (!bset)
1611                 return NULL;
1612
1613         set = isl_set_alloc_dim(isl_dim_copy(bset->dim), 1, ISL_MAP_DISJOINT);
1614         if (!set) {
1615                 isl_basic_set_free(bset);
1616                 return NULL;
1617         }
1618         return isl_set_add_basic_set(set, bset);
1619 }
1620
1621 struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap)
1622 {
1623         struct isl_map *map;
1624
1625         if (!bmap)
1626                 return NULL;
1627
1628         map = isl_map_alloc_dim(isl_dim_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
1629         if (!map) {
1630                 isl_basic_map_free(bmap);
1631                 return NULL;
1632         }
1633         return isl_map_add_basic_map(map, bmap);
1634 }
1635
1636 __isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
1637                                                 __isl_take isl_basic_set *bset)
1638 {
1639         return (struct isl_set *)isl_map_add_basic_map((struct isl_map *)set,
1640                                                 (struct isl_basic_map *)bset);
1641 }
1642
1643 void isl_set_free(struct isl_set *set)
1644 {
1645         int i;
1646
1647         if (!set)
1648                 return;
1649
1650         if (--set->ref > 0)
1651                 return;
1652
1653         isl_ctx_deref(set->ctx);
1654         for (i = 0; i < set->n; ++i)
1655                 isl_basic_set_free(set->p[i]);
1656         isl_dim_free(set->dim);
1657         free(set);
1658 }
1659
1660 void isl_set_dump(struct isl_set *set, FILE *out, int indent)
1661 {
1662         int i;
1663
1664         if (!set) {
1665                 fprintf(out, "null set\n");
1666                 return;
1667         }
1668
1669         fprintf(out, "%*s", indent, "");
1670         fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
1671                         set->ref, set->n, set->dim->nparam, set->dim->n_out,
1672                         set->flags);
1673         for (i = 0; i < set->n; ++i) {
1674                 fprintf(out, "%*s", indent, "");
1675                 fprintf(out, "basic set %d:\n", i);
1676                 isl_basic_set_dump(set->p[i], out, indent+4);
1677         }
1678 }
1679
1680 void isl_map_dump(struct isl_map *map, FILE *out, int indent)
1681 {
1682         int i;
1683
1684         if (!map) {
1685                 fprintf(out, "null map\n");
1686                 return;
1687         }
1688
1689         fprintf(out, "%*s", indent, "");
1690         fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
1691                      "flags: %x, n_name: %d\n",
1692                         map->ref, map->n, map->dim->nparam, map->dim->n_in,
1693                         map->dim->n_out, map->flags, map->dim->n_name);
1694         for (i = 0; i < map->n; ++i) {
1695                 fprintf(out, "%*s", indent, "");
1696                 fprintf(out, "basic map %d:\n", i);
1697                 isl_basic_map_dump(map->p[i], out, indent+4);
1698         }
1699 }
1700
1701 struct isl_basic_map *isl_basic_map_intersect_domain(
1702                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1703 {
1704         struct isl_basic_map *bmap_domain;
1705         struct isl_dim *dim;
1706
1707         if (!bmap || !bset)
1708                 goto error;
1709
1710         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1711                                         bset->dim, isl_dim_param), goto error);
1712
1713         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1714                 isl_assert(bset->ctx,
1715                     isl_basic_map_compatible_domain(bmap, bset), goto error);
1716
1717         bmap = isl_basic_map_cow(bmap);
1718         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1719                         bset->n_div, bset->n_eq, bset->n_ineq);
1720         if (!bmap)
1721                 goto error;
1722         dim = isl_dim_reverse(isl_dim_copy(bset->dim));
1723         bmap_domain = isl_basic_map_from_basic_set(bset, dim);
1724         bmap = add_constraints(bmap, bmap_domain, 0, 0);
1725
1726         bmap = isl_basic_map_simplify(bmap);
1727         return isl_basic_map_finalize(bmap);
1728 error:
1729         isl_basic_map_free(bmap);
1730         isl_basic_set_free(bset);
1731         return NULL;
1732 }
1733
1734 struct isl_basic_map *isl_basic_map_intersect_range(
1735                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1736 {
1737         struct isl_basic_map *bmap_range;
1738
1739         if (!bmap || !bset)
1740                 goto error;
1741
1742         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1743                                         bset->dim, isl_dim_param), goto error);
1744
1745         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1746                 isl_assert(bset->ctx,
1747                     isl_basic_map_compatible_range(bmap, bset), goto error);
1748
1749         bmap = isl_basic_map_cow(bmap);
1750         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1751                         bset->n_div, bset->n_eq, bset->n_ineq);
1752         if (!bmap)
1753                 goto error;
1754         bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
1755         bmap = add_constraints(bmap, bmap_range, 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 int isl_basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
1766 {
1767         int i;
1768         unsigned total;
1769         isl_int s;
1770
1771         total = 1 + isl_basic_map_total_dim(bmap);
1772         if (total != vec->size)
1773                 return -1;
1774
1775         isl_int_init(s);
1776
1777         for (i = 0; i < bmap->n_eq; ++i) {
1778                 isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
1779                 if (!isl_int_is_zero(s)) {
1780                         isl_int_clear(s);
1781                         return 0;
1782                 }
1783         }
1784
1785         for (i = 0; i < bmap->n_ineq; ++i) {
1786                 isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
1787                 if (isl_int_is_neg(s)) {
1788                         isl_int_clear(s);
1789                         return 0;
1790                 }
1791         }
1792
1793         isl_int_clear(s);
1794
1795         return 1;
1796 }
1797
1798 int isl_basic_set_contains(struct isl_basic_set *bset, struct isl_vec *vec)
1799 {
1800         return isl_basic_map_contains((struct isl_basic_map *)bset, vec);
1801 }
1802
1803 struct isl_basic_map *isl_basic_map_intersect(
1804                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1805 {
1806         struct isl_vec *sample = NULL;
1807
1808         if (!bmap1 || !bmap2)
1809                 goto error;
1810
1811         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
1812                                      bmap2->dim, isl_dim_param), goto error);
1813         if (isl_dim_total(bmap1->dim) ==
1814                                 isl_dim_size(bmap1->dim, isl_dim_param) &&
1815             isl_dim_total(bmap2->dim) !=
1816                                 isl_dim_size(bmap2->dim, isl_dim_param))
1817                 return isl_basic_map_intersect(bmap2, bmap1);
1818
1819         if (isl_dim_total(bmap2->dim) !=
1820                                         isl_dim_size(bmap2->dim, isl_dim_param))
1821                 isl_assert(bmap1->ctx,
1822                             isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
1823
1824         if (bmap1->sample &&
1825             isl_basic_map_contains(bmap1, bmap1->sample) > 0 &&
1826             isl_basic_map_contains(bmap2, bmap1->sample) > 0)
1827                 sample = isl_vec_copy(bmap1->sample);
1828         else if (bmap2->sample &&
1829             isl_basic_map_contains(bmap1, bmap2->sample) > 0 &&
1830             isl_basic_map_contains(bmap2, bmap2->sample) > 0)
1831                 sample = isl_vec_copy(bmap2->sample);
1832
1833         bmap1 = isl_basic_map_cow(bmap1);
1834         bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
1835                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
1836         if (!bmap1)
1837                 goto error;
1838         bmap1 = add_constraints(bmap1, bmap2, 0, 0);
1839
1840         if (sample) {
1841                 isl_vec_free(bmap1->sample);
1842                 bmap1->sample = sample;
1843         }
1844
1845         bmap1 = isl_basic_map_simplify(bmap1);
1846         return isl_basic_map_finalize(bmap1);
1847 error:
1848         if (sample)
1849                 isl_vec_free(sample);
1850         isl_basic_map_free(bmap1);
1851         isl_basic_map_free(bmap2);
1852         return NULL;
1853 }
1854
1855 struct isl_basic_set *isl_basic_set_intersect(
1856                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
1857 {
1858         return (struct isl_basic_set *)
1859                 isl_basic_map_intersect(
1860                         (struct isl_basic_map *)bset1,
1861                         (struct isl_basic_map *)bset2);
1862 }
1863
1864 /* Special case of isl_map_intersect, where both map1 and map2
1865  * are convex, without any divs and such that either map1 or map2
1866  * contains a single constraint.  This constraint is then simply
1867  * added to the other map.
1868  */
1869 static __isl_give isl_map *map_intersect_add_constraint(
1870         __isl_take isl_map *map1, __isl_take isl_map *map2)
1871 {
1872         struct isl_basic_map *bmap1;
1873         struct isl_basic_map *bmap2;
1874
1875         isl_assert(map1->ctx, map1->n == 1, goto error);
1876         isl_assert(map2->ctx, map1->n == 1, goto error);
1877         isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
1878         isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);
1879
1880         if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
1881                 return isl_map_intersect(map2, map1);
1882
1883         isl_assert(map2->ctx,
1884                     map2->p[0]->n_eq + map2->p[0]->n_ineq == 1, goto error);
1885
1886         map1 = isl_map_cow(map1);
1887         if (!map1)
1888                 goto error;
1889         if (isl_map_fast_is_empty(map1)) {
1890                 isl_map_free(map2);
1891                 return map1;
1892         }
1893         map1->p[0] = isl_basic_map_cow(map1->p[0]);
1894         if (map2->p[0]->n_eq == 1)
1895                 map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
1896         else
1897                 map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
1898                                                         map2->p[0]->ineq[0]);
1899
1900         map1->p[0] = isl_basic_map_simplify(map1->p[0]);
1901         map1->p[0] = isl_basic_map_finalize(map1->p[0]);
1902         if (!map1->p[0])
1903                 goto error;
1904
1905         if (isl_basic_map_fast_is_empty(map1->p[0])) {
1906                 isl_basic_map_free(map1->p[0]);
1907                 map1->n = 0;
1908         }
1909
1910         isl_map_free(map2);
1911
1912         return map1;
1913 error:
1914         isl_map_free(map1);
1915         isl_map_free(map2);
1916         return NULL;
1917 }
1918
1919 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
1920 {
1921         unsigned flags = 0;
1922         struct isl_map *result;
1923         int i, j;
1924
1925         if (!map1 || !map2)
1926                 goto error;
1927
1928         if (isl_map_fast_is_empty(map1)) {
1929                 isl_map_free(map2);
1930                 return map1;
1931         }
1932         if (isl_map_fast_is_empty(map2)) {
1933                 isl_map_free(map1);
1934                 return map2;
1935         }
1936
1937         if (map1->n == 1 && map2->n == 1 &&
1938             map1->p[0]->n_div == 0 && map2->p[0]->n_div == 0 &&
1939             isl_dim_equal(map1->dim, map2->dim) &&
1940             (map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 ||
1941              map2->p[0]->n_eq + map2->p[0]->n_ineq == 1))
1942                 return map_intersect_add_constraint(map1, map2);
1943         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
1944                                          map2->dim, isl_dim_param), goto error);
1945         if (isl_dim_total(map1->dim) ==
1946                                 isl_dim_size(map1->dim, isl_dim_param) &&
1947             isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1948                 return isl_map_intersect(map2, map1);
1949
1950         if (isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1951                 isl_assert(map1->ctx,
1952                             isl_dim_equal(map1->dim, map2->dim), goto error);
1953
1954         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
1955             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
1956                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
1957
1958         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
1959                                 map1->n * map2->n, flags);
1960         if (!result)
1961                 goto error;
1962         for (i = 0; i < map1->n; ++i)
1963                 for (j = 0; j < map2->n; ++j) {
1964                         struct isl_basic_map *part;
1965                         part = isl_basic_map_intersect(
1966                                     isl_basic_map_copy(map1->p[i]),
1967                                     isl_basic_map_copy(map2->p[j]));
1968                         if (isl_basic_map_is_empty(part))
1969                                 isl_basic_map_free(part);
1970                         else
1971                                 result = isl_map_add_basic_map(result, part);
1972                         if (!result)
1973                                 goto error;
1974                 }
1975         isl_map_free(map1);
1976         isl_map_free(map2);
1977         return result;
1978 error:
1979         isl_map_free(map1);
1980         isl_map_free(map2);
1981         return NULL;
1982 }
1983
1984 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
1985 {
1986         return (struct isl_set *)
1987                 isl_map_intersect((struct isl_map *)set1,
1988                                   (struct isl_map *)set2);
1989 }
1990
1991 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
1992 {
1993         struct isl_dim *dim;
1994         struct isl_basic_set *bset;
1995         unsigned in;
1996
1997         if (!bmap)
1998                 return NULL;
1999         bmap = isl_basic_map_cow(bmap);
2000         if (!bmap)
2001                 return NULL;
2002         dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
2003         in = isl_basic_map_n_in(bmap);
2004         bset = isl_basic_set_from_basic_map(bmap);
2005         bset = isl_basic_set_swap_vars(bset, in);
2006         return isl_basic_map_from_basic_set(bset, dim);
2007 }
2008
2009 __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap,
2010                 enum isl_dim_type type, unsigned pos, unsigned n)
2011 {
2012         struct isl_dim *res_dim;
2013         struct isl_basic_map *res;
2014         struct isl_dim_map *dim_map;
2015         unsigned total, off;
2016         enum isl_dim_type t;
2017
2018         if (n == 0)
2019                 return bmap;
2020
2021         if (!bmap)
2022                 return NULL;
2023
2024         res_dim = isl_dim_insert(isl_basic_map_get_dim(bmap), type, pos, n);
2025
2026         total = isl_basic_map_total_dim(bmap) + n;
2027         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2028         off = 0;
2029         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2030                 if (t != type) {
2031                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2032                 } else {
2033                         unsigned size = isl_basic_map_dim(bmap, t);
2034                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2035                                                 0, pos, off);
2036                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2037                                                 pos, size - pos, off + pos + n);
2038                 }
2039                 off += isl_dim_size(res_dim, t);
2040         }
2041         isl_dim_map_div(dim_map, bmap, off);
2042
2043         res = isl_basic_map_alloc_dim(res_dim,
2044                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2045         res = add_constraints_dim_map(res, bmap, dim_map);
2046         res = isl_basic_map_simplify(res);
2047         return isl_basic_map_finalize(res);
2048 }
2049
2050 __isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
2051                 enum isl_dim_type type, unsigned n)
2052 {
2053         if (!bmap)
2054                 return NULL;
2055         return isl_basic_map_insert(bmap, type,
2056                                         isl_basic_map_dim(bmap, type), n);
2057 }
2058
2059 __isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset,
2060                 enum isl_dim_type type, unsigned n)
2061 {
2062         if (!bset)
2063                 return NULL;
2064         isl_assert(bset->ctx, type != isl_dim_in, goto error);
2065         return (isl_basic_set *)isl_basic_map_add((isl_basic_map *)bset, type, n);
2066 error:
2067         isl_basic_set_free(bset);
2068         return NULL;
2069 }
2070
2071 __isl_give isl_map *isl_map_insert(__isl_take isl_map *map,
2072                 enum isl_dim_type type, unsigned pos, unsigned n)
2073 {
2074         int i;
2075
2076         if (n == 0)
2077                 return map;
2078
2079         map = isl_map_cow(map);
2080         if (!map)
2081                 return NULL;
2082
2083         map->dim = isl_dim_insert(map->dim, type, pos, n);
2084         if (!map->dim)
2085                 goto error;
2086
2087         for (i = 0; i < map->n; ++i) {
2088                 map->p[i] = isl_basic_map_insert(map->p[i], type, pos, n);
2089                 if (!map->p[i])
2090                         goto error;
2091         }
2092
2093         return map;
2094 error:
2095         isl_map_free(map);
2096         return NULL;
2097 }
2098
2099 __isl_give isl_map *isl_map_add(__isl_take isl_map *map,
2100                 enum isl_dim_type type, unsigned n)
2101 {
2102         if (!map)
2103                 return NULL;
2104         return isl_map_insert(map, type, isl_map_dim(map, type), n);
2105 }
2106
2107 __isl_give isl_set *isl_set_add(__isl_take isl_set *set,
2108                 enum isl_dim_type type, unsigned n)
2109 {
2110         if (!set)
2111                 return NULL;
2112         isl_assert(set->ctx, type != isl_dim_in, goto error);
2113         return (isl_set *)isl_map_add((isl_map *)set, type, n);
2114 error:
2115         isl_set_free(set);
2116         return NULL;
2117 }
2118
2119 __isl_give isl_basic_map *isl_basic_map_move_dims(
2120         __isl_take isl_basic_map *bmap,
2121         enum isl_dim_type dst_type, unsigned dst_pos,
2122         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2123 {
2124         int i;
2125         struct isl_dim_map *dim_map;
2126         struct isl_basic_map *res;
2127         enum isl_dim_type t;
2128         unsigned total, off;
2129
2130         if (!bmap)
2131                 return NULL;
2132         if (n == 0)
2133                 return bmap;
2134
2135         isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type),
2136                 goto error);
2137
2138         if (dst_type == src_type && dst_pos == src_pos)
2139                 return bmap;
2140
2141         isl_assert(bmap->ctx, dst_type != src_type, goto error);
2142
2143         if (pos(bmap->dim, dst_type) + dst_pos ==
2144             pos(bmap->dim, src_type) + src_pos +
2145                                             ((src_type < dst_type) ? n : 0)) {
2146                 bmap = isl_basic_map_cow(bmap);
2147                 if (!bmap)
2148                         return NULL;
2149
2150                 bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
2151                                                 src_type, src_pos, n);
2152                 if (!bmap->dim)
2153                         goto error;
2154
2155                 bmap = isl_basic_map_finalize(bmap);
2156
2157                 return bmap;
2158         }
2159
2160         total = isl_basic_map_total_dim(bmap);
2161         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2162
2163         off = 0;
2164         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2165                 unsigned size = isl_dim_size(bmap->dim, t);
2166                 if (t == dst_type) {
2167                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2168                                             0, dst_pos, off);
2169                         off += dst_pos;
2170                         isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
2171                                             src_pos, n, off);
2172                         off += n;
2173                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2174                                             dst_pos, size - dst_pos, off);
2175                         off += size - dst_pos;
2176                 } else if (t == src_type) {
2177                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2178                                             0, src_pos, off);
2179                         off += src_pos;
2180                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2181                                         src_pos + n, size - src_pos - n, off);
2182                         off += size - src_pos - n;
2183                 } else {
2184                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2185                         off += size;
2186                 }
2187         }
2188         isl_dim_map_div(dim_map, bmap, off + n);
2189
2190         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2191                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2192         bmap = add_constraints_dim_map(res, bmap, dim_map);
2193
2194         bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
2195                                         src_type, src_pos, n);
2196         if (!bmap->dim)
2197                 goto error;
2198
2199         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2200         bmap = isl_basic_map_gauss(bmap, NULL);
2201         bmap = isl_basic_map_finalize(bmap);
2202
2203         return bmap;
2204 error:
2205         isl_basic_map_free(bmap);
2206         return NULL;
2207 }
2208
2209 __isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
2210         enum isl_dim_type dst_type, unsigned dst_pos,
2211         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2212 {
2213         return (isl_basic_set *)isl_basic_map_move_dims(
2214                 (isl_basic_map *)bset, dst_type, dst_pos, src_type, src_pos, n);
2215 }
2216
2217 __isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
2218         enum isl_dim_type dst_type, unsigned dst_pos,
2219         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2220 {
2221         if (!set)
2222                 return NULL;
2223         isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
2224         return (isl_set *)isl_map_move_dims((isl_map *)set, dst_type, dst_pos,
2225                                         src_type, src_pos, n);
2226 error:
2227         isl_set_free(set);
2228         return NULL;
2229 }
2230
2231 __isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
2232         enum isl_dim_type dst_type, unsigned dst_pos,
2233         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2234 {
2235         int i;
2236
2237         if (!map)
2238                 return NULL;
2239         if (n == 0)
2240                 return map;
2241
2242         isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type),
2243                 goto error);
2244
2245         if (dst_type == src_type && dst_pos == src_pos)
2246                 return map;
2247
2248         isl_assert(map->ctx, dst_type != src_type, goto error);
2249
2250         map = isl_map_cow(map);
2251         if (!map)
2252                 return NULL;
2253
2254         map->dim = isl_dim_move(map->dim, dst_type, dst_pos, src_type, src_pos, n);
2255         if (!map->dim)
2256                 goto error;
2257
2258         for (i = 0; i < map->n; ++i) {
2259                 map->p[i] = isl_basic_map_move_dims(map->p[i],
2260                                                 dst_type, dst_pos,
2261                                                 src_type, src_pos, n);
2262                 if (!map->p[i])
2263                         goto error;
2264         }
2265
2266         return map;
2267 error:
2268         isl_map_free(map);
2269         return NULL;
2270 }
2271
2272 /* Move the specified dimensions to the last columns right before
2273  * the divs.  Don't change the dimension specification of bmap.
2274  * That's the responsibility of the caller.
2275  */
2276 static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
2277         enum isl_dim_type type, unsigned first, unsigned n)
2278 {
2279         struct isl_dim_map *dim_map;
2280         struct isl_basic_map *res;
2281         enum isl_dim_type t;
2282         unsigned total, off;
2283
2284         if (!bmap)
2285                 return NULL;
2286         if (pos(bmap->dim, type) + first + n == 1 + isl_dim_total(bmap->dim))
2287                 return bmap;
2288
2289         total = isl_basic_map_total_dim(bmap);
2290         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2291
2292         off = 0;
2293         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2294                 unsigned size = isl_dim_size(bmap->dim, t);
2295                 if (t == type) {
2296                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2297                                             0, first, off);
2298                         off += first;
2299                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2300                                             first, n, total - bmap->n_div - n);
2301                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2302                                             first + n, size - (first + n), off);
2303                         off += size - (first + n);
2304                 } else {
2305                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2306                         off += size;
2307                 }
2308         }
2309         isl_dim_map_div(dim_map, bmap, off + n);
2310
2311         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2312                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2313         res = add_constraints_dim_map(res, bmap, dim_map);
2314         return res;
2315 }
2316
2317 /* Turn the n dimensions of type type, starting at first
2318  * into existentially quantified variables.
2319  */
2320 __isl_give isl_basic_map *isl_basic_map_project_out(
2321                 __isl_take isl_basic_map *bmap,
2322                 enum isl_dim_type type, unsigned first, unsigned n)
2323 {
2324         int i;
2325         size_t row_size;
2326         isl_int **new_div;
2327         isl_int *old;
2328
2329         if (n == 0)
2330                 return bmap;
2331
2332         if (!bmap)
2333                 return NULL;
2334
2335         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
2336                 return isl_basic_map_remove(bmap, type, first, n);
2337
2338         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
2339                         goto error);
2340
2341         bmap = move_last(bmap, type, first, n);
2342         bmap = isl_basic_map_cow(bmap);
2343
2344         row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra;
2345         old = bmap->block2.data;
2346         bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
2347                                         (bmap->extra + n) * (1 + row_size));
2348         if (!bmap->block2.data)
2349                 goto error;
2350         new_div = isl_alloc_array(ctx, isl_int *, bmap->extra + n);
2351         if (!new_div)
2352                 goto error;
2353         for (i = 0; i < n; ++i) {
2354                 new_div[i] = bmap->block2.data +
2355                                 (bmap->extra + i) * (1 + row_size);
2356                 isl_seq_clr(new_div[i], 1 + row_size);
2357         }
2358         for (i = 0; i < bmap->extra; ++i)
2359                 new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
2360         free(bmap->div);
2361         bmap->div = new_div;
2362         bmap->n_div += n;
2363         bmap->extra += n;
2364
2365         bmap->dim = isl_dim_drop(bmap->dim, type, first, n);
2366         if (!bmap->dim)
2367                 goto error;
2368         bmap = isl_basic_map_simplify(bmap);
2369         bmap = isl_basic_map_drop_redundant_divs(bmap);
2370         return isl_basic_map_finalize(bmap);
2371 error:
2372         isl_basic_map_free(bmap);
2373         return NULL;
2374 }
2375
2376 /* Turn the n dimensions of type type, starting at first
2377  * into existentially quantified variables.
2378  */
2379 struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
2380                 enum isl_dim_type type, unsigned first, unsigned n)
2381 {
2382         return (isl_basic_set *)isl_basic_map_project_out(
2383                         (isl_basic_map *)bset, type, first, n);
2384 }
2385
2386 /* Turn the n dimensions of type type, starting at first
2387  * into existentially quantified variables.
2388  */
2389 __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
2390                 enum isl_dim_type type, unsigned first, unsigned n)
2391 {
2392         int i;
2393
2394         if (!map)
2395                 return NULL;
2396
2397         if (n == 0)
2398                 return map;
2399
2400         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
2401
2402         map = isl_map_cow(map);
2403         if (!map)
2404                 return NULL;
2405
2406         map->dim = isl_dim_drop(map->dim, type, first, n);
2407         if (!map->dim)
2408                 goto error;
2409
2410         for (i = 0; i < map->n; ++i) {
2411                 map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
2412                 if (!map->p[i])
2413                         goto error;
2414         }
2415
2416         return map;
2417 error:
2418         isl_map_free(map);
2419         return map;
2420 }
2421
2422 /* Turn the n dimensions of type type, starting at first
2423  * into existentially quantified variables.
2424  */
2425 __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
2426                 enum isl_dim_type type, unsigned first, unsigned n)
2427 {
2428         return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n);
2429 }
2430
2431 static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2432 {
2433         int i, j;
2434
2435         for (i = 0; i < n; ++i) {
2436                 j = isl_basic_map_alloc_div(bmap);
2437                 if (j < 0)
2438                         goto error;
2439                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2440         }
2441         return bmap;
2442 error:
2443         isl_basic_map_free(bmap);
2444         return NULL;
2445 }
2446
2447 struct isl_basic_map *isl_basic_map_apply_range(
2448                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2449 {
2450         struct isl_dim *dim_result = NULL;
2451         struct isl_basic_map *bmap;
2452         unsigned n_in, n_out, n, nparam, total, pos;
2453         struct isl_dim_map *dim_map1, *dim_map2;
2454
2455         if (!bmap1 || !bmap2)
2456                 goto error;
2457
2458         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2459                                   isl_dim_copy(bmap2->dim));
2460
2461         n_in = isl_basic_map_n_in(bmap1);
2462         n_out = isl_basic_map_n_out(bmap2);
2463         n = isl_basic_map_n_out(bmap1);
2464         nparam = isl_basic_map_n_param(bmap1);
2465
2466         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2467         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2468         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2469         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2470         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2471         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2472         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2473         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2474         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2475         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2476         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2477
2478         bmap = isl_basic_map_alloc_dim(dim_result,
2479                         bmap1->n_div + bmap2->n_div + n,
2480                         bmap1->n_eq + bmap2->n_eq,
2481                         bmap1->n_ineq + bmap2->n_ineq);
2482         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2483         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2484         bmap = add_divs(bmap, n);
2485         bmap = isl_basic_map_simplify(bmap);
2486         bmap = isl_basic_map_drop_redundant_divs(bmap);
2487         return isl_basic_map_finalize(bmap);
2488 error:
2489         isl_basic_map_free(bmap1);
2490         isl_basic_map_free(bmap2);
2491         return NULL;
2492 }
2493
2494 struct isl_basic_set *isl_basic_set_apply(
2495                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2496 {
2497         if (!bset || !bmap)
2498                 goto error;
2499
2500         isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
2501                     goto error);
2502
2503         return (struct isl_basic_set *)
2504                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2505 error:
2506         isl_basic_set_free(bset);
2507         isl_basic_map_free(bmap);
2508         return NULL;
2509 }
2510
2511 struct isl_basic_map *isl_basic_map_apply_domain(
2512                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2513 {
2514         if (!bmap1 || !bmap2)
2515                 goto error;
2516
2517         isl_assert(bmap1->ctx,
2518             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2519         isl_assert(bmap1->ctx,
2520             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2521             goto error);
2522
2523         bmap1 = isl_basic_map_reverse(bmap1);
2524         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2525         return isl_basic_map_reverse(bmap1);
2526 error:
2527         isl_basic_map_free(bmap1);
2528         isl_basic_map_free(bmap2);
2529         return NULL;
2530 }
2531
2532 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
2533  * A \cap B -> f(A) + f(B)
2534  */
2535 struct isl_basic_map *isl_basic_map_sum(
2536                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2537 {
2538         unsigned n_in, n_out, nparam, total, pos;
2539         struct isl_basic_map *bmap = NULL;
2540         struct isl_dim_map *dim_map1, *dim_map2;
2541         int i;
2542
2543         if (!bmap1 || !bmap2)
2544                 goto error;
2545
2546         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
2547                 goto error);
2548
2549         nparam = isl_basic_map_n_param(bmap1);
2550         n_in = isl_basic_map_n_in(bmap1);
2551         n_out = isl_basic_map_n_out(bmap1);
2552
2553         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
2554         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2555         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
2556         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2557         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
2558         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2559         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2560         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
2561         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2562         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2563         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
2564
2565         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
2566                         bmap1->n_div + bmap2->n_div + 2 * n_out,
2567                         bmap1->n_eq + bmap2->n_eq + n_out,
2568                         bmap1->n_ineq + bmap2->n_ineq);
2569         for (i = 0; i < n_out; ++i) {
2570                 int j = isl_basic_map_alloc_equality(bmap);
2571                 if (j < 0)
2572                         goto error;
2573                 isl_seq_clr(bmap->eq[j], 1+total);
2574                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
2575                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
2576                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
2577         }
2578         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2579         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2580         bmap = add_divs(bmap, 2 * n_out);
2581
2582         bmap = isl_basic_map_simplify(bmap);
2583         return isl_basic_map_finalize(bmap);
2584 error:
2585         isl_basic_map_free(bmap);
2586         isl_basic_map_free(bmap1);
2587         isl_basic_map_free(bmap2);
2588         return NULL;
2589 }
2590
2591 /* Given two maps A -> f(A) and B -> g(B), construct a map
2592  * A \cap B -> f(A) + f(B)
2593  */
2594 struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2)
2595 {
2596         struct isl_map *result;
2597         int i, j;
2598
2599         if (!map1 || !map2)
2600                 goto error;
2601
2602         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2603
2604         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2605                                 map1->n * map2->n, 0);
2606         if (!result)
2607                 goto error;
2608         for (i = 0; i < map1->n; ++i)
2609                 for (j = 0; j < map2->n; ++j) {
2610                         struct isl_basic_map *part;
2611                         part = isl_basic_map_sum(
2612                                     isl_basic_map_copy(map1->p[i]),
2613                                     isl_basic_map_copy(map2->p[j]));
2614                         if (isl_basic_map_is_empty(part))
2615                                 isl_basic_map_free(part);
2616                         else
2617                                 result = isl_map_add_basic_map(result, part);
2618                         if (!result)
2619                                 goto error;
2620                 }
2621         isl_map_free(map1);
2622         isl_map_free(map2);
2623         return result;
2624 error:
2625         isl_map_free(map1);
2626         isl_map_free(map2);
2627         return NULL;
2628 }
2629
2630 __isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
2631         __isl_take isl_set *set2)
2632 {
2633         return (isl_set *)isl_map_sum((isl_map *)set1, (isl_map *)set2);
2634 }
2635
2636 /* Given a basic map A -> f(A), construct A -> -f(A).
2637  */
2638 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
2639 {
2640         int i, j;
2641         unsigned off, n;
2642
2643         bmap = isl_basic_map_cow(bmap);
2644         if (!bmap)
2645                 return NULL;
2646
2647         n = isl_basic_map_dim(bmap, isl_dim_out);
2648         off = isl_basic_map_offset(bmap, isl_dim_out);
2649         for (i = 0; i < bmap->n_eq; ++i)
2650                 for (j = 0; j < n; ++j)
2651                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
2652         for (i = 0; i < bmap->n_ineq; ++i)
2653                 for (j = 0; j < n; ++j)
2654                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
2655         for (i = 0; i < bmap->n_div; ++i)
2656                 for (j = 0; j < n; ++j)
2657                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
2658         return isl_basic_map_finalize(bmap);
2659 }
2660
2661 /* Given a map A -> f(A), construct A -> -f(A).
2662  */
2663 struct isl_map *isl_map_neg(struct isl_map *map)
2664 {
2665         int i;
2666
2667         map = isl_map_cow(map);
2668         if (!map)
2669                 return NULL;
2670
2671         for (i = 0; i < map->n; ++i) {
2672                 map->p[i] = isl_basic_map_neg(map->p[i]);
2673                 if (!map->p[i])
2674                         goto error;
2675         }
2676
2677         return map;
2678 error:
2679         isl_map_free(map);
2680         return NULL;
2681 }
2682
2683 __isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
2684 {
2685         return (isl_set *)isl_map_neg((isl_map *)set);
2686 }
2687
2688 /* Given a basic map A -> f(A) and an integer d, construct a basic map
2689  * A -> floor(f(A)/d).
2690  */
2691 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
2692                 isl_int d)
2693 {
2694         unsigned n_in, n_out, nparam, total, pos;
2695         struct isl_basic_map *result = NULL;
2696         struct isl_dim_map *dim_map;
2697         int i;
2698
2699         if (!bmap)
2700                 return NULL;
2701
2702         nparam = isl_basic_map_n_param(bmap);
2703         n_in = isl_basic_map_n_in(bmap);
2704         n_out = isl_basic_map_n_out(bmap);
2705
2706         total = nparam + n_in + n_out + bmap->n_div + n_out;
2707         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2708         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
2709         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
2710         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
2711         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
2712
2713         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
2714                         bmap->n_div + n_out,
2715                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
2716         result = add_constraints_dim_map(result, bmap, dim_map);
2717         result = add_divs(result, n_out);
2718         for (i = 0; i < n_out; ++i) {
2719                 int j;
2720                 j = isl_basic_map_alloc_inequality(result);
2721                 if (j < 0)
2722                         goto error;
2723                 isl_seq_clr(result->ineq[j], 1+total);
2724                 isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
2725                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
2726                 j = isl_basic_map_alloc_inequality(result);
2727                 if (j < 0)
2728                         goto error;
2729                 isl_seq_clr(result->ineq[j], 1+total);
2730                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
2731                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
2732                 isl_int_sub_ui(result->ineq[j][0], d, 1);
2733         }
2734
2735         result = isl_basic_map_simplify(result);
2736         return isl_basic_map_finalize(result);
2737 error:
2738         isl_basic_map_free(result);
2739         return NULL;
2740 }
2741
2742 /* Given a map A -> f(A) and an integer d, construct a map
2743  * A -> floor(f(A)/d).
2744  */
2745 struct isl_map *isl_map_floordiv(struct isl_map *map, isl_int d)
2746 {
2747         int i;
2748
2749         map = isl_map_cow(map);
2750         if (!map)
2751                 return NULL;
2752
2753         ISL_F_CLR(map, ISL_MAP_DISJOINT);
2754         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2755         for (i = 0; i < map->n; ++i) {
2756                 map->p[i] = isl_basic_map_floordiv(map->p[i], d);
2757                 if (!map->p[i])
2758                         goto error;
2759         }
2760
2761         return map;
2762 error:
2763         isl_map_free(map);
2764         return NULL;
2765 }
2766
2767 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
2768 {
2769         int i;
2770         unsigned nparam;
2771         unsigned n_in;
2772
2773         i = isl_basic_map_alloc_equality(bmap);
2774         if (i < 0)
2775                 goto error;
2776         nparam = isl_basic_map_n_param(bmap);
2777         n_in = isl_basic_map_n_in(bmap);
2778         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2779         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2780         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2781         return isl_basic_map_finalize(bmap);
2782 error:
2783         isl_basic_map_free(bmap);
2784         return NULL;
2785 }
2786
2787 /* Add a constraints to "bmap" expressing i_pos < o_pos
2788  */
2789 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2790 {
2791         int i;
2792         unsigned nparam;
2793         unsigned n_in;
2794
2795         i = isl_basic_map_alloc_inequality(bmap);
2796         if (i < 0)
2797                 goto error;
2798         nparam = isl_basic_map_n_param(bmap);
2799         n_in = isl_basic_map_n_in(bmap);
2800         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2801         isl_int_set_si(bmap->ineq[i][0], -1);
2802         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2803         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2804         return isl_basic_map_finalize(bmap);
2805 error:
2806         isl_basic_map_free(bmap);
2807         return NULL;
2808 }
2809
2810 /* Add a constraint to "bmap" expressing i_pos <= o_pos
2811  */
2812 static __isl_give isl_basic_map *var_less_or_equal(
2813         __isl_take isl_basic_map *bmap, unsigned pos)
2814 {
2815         int i;
2816         unsigned nparam;
2817         unsigned n_in;
2818
2819         i = isl_basic_map_alloc_inequality(bmap);
2820         if (i < 0)
2821                 goto error;
2822         nparam = isl_basic_map_n_param(bmap);
2823         n_in = isl_basic_map_n_in(bmap);
2824         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2825         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2826         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2827         return isl_basic_map_finalize(bmap);
2828 error:
2829         isl_basic_map_free(bmap);
2830         return NULL;
2831 }
2832
2833 /* Add a constraints to "bmap" expressing i_pos > o_pos
2834  */
2835 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
2836 {
2837         int i;
2838         unsigned nparam;
2839         unsigned n_in;
2840
2841         i = isl_basic_map_alloc_inequality(bmap);
2842         if (i < 0)
2843                 goto error;
2844         nparam = isl_basic_map_n_param(bmap);
2845         n_in = isl_basic_map_n_in(bmap);
2846         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2847         isl_int_set_si(bmap->ineq[i][0], -1);
2848         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2849         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2850         return isl_basic_map_finalize(bmap);
2851 error:
2852         isl_basic_map_free(bmap);
2853         return NULL;
2854 }
2855
2856 /* Add a constraint to "bmap" expressing i_pos >= o_pos
2857  */
2858 static __isl_give isl_basic_map *var_more_or_equal(
2859         __isl_take isl_basic_map *bmap, unsigned pos)
2860 {
2861         int i;
2862         unsigned nparam;
2863         unsigned n_in;
2864
2865         i = isl_basic_map_alloc_inequality(bmap);
2866         if (i < 0)
2867                 goto error;
2868         nparam = isl_basic_map_n_param(bmap);
2869         n_in = isl_basic_map_n_in(bmap);
2870         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2871         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2872         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2873         return isl_basic_map_finalize(bmap);
2874 error:
2875         isl_basic_map_free(bmap);
2876         return NULL;
2877 }
2878
2879 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
2880 {
2881         int i;
2882         struct isl_basic_map *bmap;
2883         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
2884         if (!bmap)
2885                 return NULL;
2886         for (i = 0; i < n_equal && bmap; ++i)
2887                 bmap = var_equal(bmap, i);
2888         return isl_basic_map_finalize(bmap);
2889 }
2890
2891 /* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
2892  */
2893 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
2894 {
2895         int i;
2896         struct isl_basic_map *bmap;
2897         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2898         if (!bmap)
2899                 return NULL;
2900         for (i = 0; i < pos && bmap; ++i)
2901                 bmap = var_equal(bmap, i);
2902         if (bmap)
2903                 bmap = var_less(bmap, pos);
2904         return isl_basic_map_finalize(bmap);
2905 }
2906
2907 /* Return a relation on of dimension "dim" expressing i_[0..pos] <<= o_[0..pos]
2908  */
2909 __isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
2910         __isl_take isl_dim *dim, unsigned pos)
2911 {
2912         int i;
2913         isl_basic_map *bmap;
2914
2915         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2916         for (i = 0; i < pos; ++i)
2917                 bmap = var_equal(bmap, i);
2918         bmap = var_less_or_equal(bmap, pos);
2919         return isl_basic_map_finalize(bmap);
2920 }
2921
2922 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
2923  */
2924 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
2925 {
2926         int i;
2927         struct isl_basic_map *bmap;
2928         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2929         if (!bmap)
2930                 return NULL;
2931         for (i = 0; i < pos && bmap; ++i)
2932                 bmap = var_equal(bmap, i);
2933         if (bmap)
2934                 bmap = var_more(bmap, pos);
2935         return isl_basic_map_finalize(bmap);
2936 }
2937
2938 /* Return a relation on of dimension "dim" expressing i_[0..pos] >>= o_[0..pos]
2939  */
2940 __isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
2941         __isl_take isl_dim *dim, unsigned pos)
2942 {
2943         int i;
2944         isl_basic_map *bmap;
2945
2946         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2947         for (i = 0; i < pos; ++i)
2948                 bmap = var_equal(bmap, i);
2949         bmap = var_more_or_equal(bmap, pos);
2950         return isl_basic_map_finalize(bmap);
2951 }
2952
2953 static __isl_give isl_map *map_lex_lte_first(__isl_take isl_dim *dims,
2954         unsigned n, int equal)
2955 {
2956         struct isl_map *map;
2957         int i;
2958
2959         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
2960
2961         for (i = 0; i + 1 < n; ++i)
2962                 map = isl_map_add_basic_map(map,
2963                                   isl_basic_map_less_at(isl_dim_copy(dims), i));
2964         if (n > 0) {
2965                 if (equal)
2966                         map = isl_map_add_basic_map(map,
2967                               isl_basic_map_less_or_equal_at(dims, n - 1));
2968                 else
2969                         map = isl_map_add_basic_map(map,
2970                               isl_basic_map_less_at(dims, n - 1));
2971         } else
2972                 isl_dim_free(dims);
2973
2974         return map;
2975 }
2976
2977 static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
2978 {
2979         if (!dims)
2980                 return NULL;
2981         return map_lex_lte_first(dims, dims->n_out, equal);
2982 }
2983
2984 __isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_dim *dim, unsigned n)
2985 {
2986         return map_lex_lte_first(dim, n, 0);
2987 }
2988
2989 __isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n)
2990 {
2991         return map_lex_lte_first(dim, n, 1);
2992 }
2993
2994 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
2995 {
2996         return map_lex_lte(isl_dim_map(set_dim), 0);
2997 }
2998
2999 __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
3000 {
3001         return map_lex_lte(isl_dim_map(set_dim), 1);
3002 }
3003
3004 static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims,
3005         unsigned n, int equal)
3006 {
3007         struct isl_map *map;
3008         int i;
3009
3010         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3011
3012         for (i = 0; i + 1 < n; ++i)
3013                 map = isl_map_add_basic_map(map,
3014                                   isl_basic_map_more_at(isl_dim_copy(dims), i));
3015         if (n > 0) {
3016                 if (equal)
3017                         map = isl_map_add_basic_map(map,
3018                               isl_basic_map_more_or_equal_at(dims, n - 1));
3019                 else
3020                         map = isl_map_add_basic_map(map,
3021                               isl_basic_map_more_at(dims, n - 1));
3022         } else
3023                 isl_dim_free(dims);
3024
3025         return map;
3026 }
3027
3028 static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
3029 {
3030         if (!dims)
3031                 return NULL;
3032         return map_lex_gte_first(dims, dims->n_out, equal);
3033 }
3034
3035 __isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_dim *dim, unsigned n)
3036 {
3037         return map_lex_gte_first(dim, n, 0);
3038 }
3039
3040 __isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n)
3041 {
3042         return map_lex_gte_first(dim, n, 1);
3043 }
3044
3045 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
3046 {
3047         return map_lex_gte(isl_dim_map(set_dim), 0);
3048 }
3049
3050 __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim)
3051 {
3052         return map_lex_gte(isl_dim_map(set_dim), 1);
3053 }
3054
3055 struct isl_basic_map *isl_basic_map_from_basic_set(
3056                 struct isl_basic_set *bset, struct isl_dim *dim)
3057 {
3058         struct isl_basic_map *bmap;
3059
3060         bset = isl_basic_set_cow(bset);
3061         if (!bset || !dim)
3062                 goto error;
3063
3064         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
3065         isl_dim_free(bset->dim);
3066         bmap = (struct isl_basic_map *) bset;
3067         bmap->dim = dim;
3068         return isl_basic_map_finalize(bmap);
3069 error:
3070         isl_basic_set_free(bset);
3071         isl_dim_free(dim);
3072         return NULL;
3073 }
3074
3075 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
3076 {
3077         if (!bmap)
3078                 goto error;
3079         if (bmap->dim->n_in == 0)
3080                 return (struct isl_basic_set *)bmap;
3081         bmap = isl_basic_map_cow(bmap);
3082         if (!bmap)
3083                 goto error;
3084         bmap->dim = isl_dim_cow(bmap->dim);
3085         if (!bmap->dim)
3086                 goto error;
3087         bmap->dim->n_out += bmap->dim->n_in;
3088         bmap->dim->n_in = 0;
3089         bmap = isl_basic_map_finalize(bmap);
3090         return (struct isl_basic_set *)bmap;
3091 error:
3092         isl_basic_map_free(bmap);
3093         return NULL;
3094 }
3095
3096 /* For a div d = floor(f/m), add the constraints
3097  *
3098  *              f - m d >= 0
3099  *              -(f-(n-1)) + m d >= 0
3100  *
3101  * Note that the second constraint is the negation of
3102  *
3103  *              f - m d >= n
3104  */
3105 int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
3106         unsigned pos, isl_int *div)
3107 {
3108         int i, j;
3109         unsigned total = isl_basic_map_total_dim(bmap);
3110
3111         i = isl_basic_map_alloc_inequality(bmap);
3112         if (i < 0)
3113                 return -1;
3114         isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
3115         isl_int_neg(bmap->ineq[i][1 + pos], div[0]);
3116
3117         j = isl_basic_map_alloc_inequality(bmap);
3118         if (j < 0)
3119                 return -1;
3120         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
3121         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][1 + pos]);
3122         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
3123         return j;
3124 }
3125
3126 int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
3127         unsigned pos, isl_int *div)
3128 {
3129         return isl_basic_map_add_div_constraints_var((isl_basic_map *)bset,
3130                                                         pos, div);
3131 }
3132
3133 int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
3134 {
3135         unsigned total = isl_basic_map_total_dim(bmap);
3136         unsigned div_pos = total - bmap->n_div + div;
3137
3138         return isl_basic_map_add_div_constraints_var(bmap, div_pos,
3139                                                         bmap->div[div]);
3140 }
3141
3142 struct isl_basic_set *isl_basic_map_underlying_set(
3143                 struct isl_basic_map *bmap)
3144 {
3145         if (!bmap)
3146                 goto error;
3147         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
3148                 return (struct isl_basic_set *)bmap;
3149         bmap = isl_basic_map_cow(bmap);
3150         if (!bmap)
3151                 goto error;
3152         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
3153         if (!bmap->dim)
3154                 goto error;
3155         bmap->extra -= bmap->n_div;
3156         bmap->n_div = 0;
3157         bmap = isl_basic_map_finalize(bmap);
3158         return (struct isl_basic_set *)bmap;
3159 error:
3160         return NULL;
3161 }
3162
3163 __isl_give isl_basic_set *isl_basic_set_underlying_set(
3164                 __isl_take isl_basic_set *bset)
3165 {
3166         return isl_basic_map_underlying_set((isl_basic_map *)bset);
3167 }
3168
3169 struct isl_basic_map *isl_basic_map_overlying_set(
3170         struct isl_basic_set *bset, struct isl_basic_map *like)
3171 {
3172         struct isl_basic_map *bmap;
3173         struct isl_ctx *ctx;
3174         unsigned total;
3175         int i;
3176
3177         if (!bset || !like)
3178                 goto error;
3179         ctx = bset->ctx;
3180         isl_assert(ctx, bset->n_div == 0, goto error);
3181         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
3182         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
3183                         goto error);
3184         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
3185                 isl_basic_map_free(like);
3186                 return (struct isl_basic_map *)bset;
3187         }
3188         bset = isl_basic_set_cow(bset);
3189         if (!bset)
3190                 goto error;
3191         total = bset->dim->n_out + bset->extra;
3192         bmap = (struct isl_basic_map *)bset;
3193         isl_dim_free(bmap->dim);
3194         bmap->dim = isl_dim_copy(like->dim);
3195         if (!bmap->dim)
3196                 goto error;
3197         bmap->n_div = like->n_div;
3198         bmap->extra += like->n_div;
3199         if (bmap->extra) {
3200                 unsigned ltotal;
3201                 ltotal = total - bmap->extra + like->extra;
3202                 if (ltotal > total)
3203                         ltotal = total;
3204                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
3205                                         bmap->extra * (1 + 1 + total));
3206                 if (isl_blk_is_error(bmap->block2))
3207                         goto error;
3208                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
3209                                                 bmap->extra);
3210                 if (!bmap->div)
3211                         goto error;
3212                 for (i = 0; i < bmap->extra; ++i)
3213                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
3214                 for (i = 0; i < like->n_div; ++i) {
3215                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
3216                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
3217                 }
3218                 bmap = isl_basic_map_extend_constraints(bmap,
3219                                                         0, 2 * like->n_div);
3220                 for (i = 0; i < like->n_div; ++i) {
3221                         if (isl_int_is_zero(bmap->div[i][0]))
3222                                 continue;
3223                         if (isl_basic_map_add_div_constraints(bmap, i) < 0)
3224                                 goto error;
3225                 }
3226         }
3227         isl_basic_map_free(like);
3228         bmap = isl_basic_map_simplify(bmap);
3229         bmap = isl_basic_map_finalize(bmap);
3230         return bmap;
3231 error:
3232         isl_basic_map_free(like);
3233         isl_basic_set_free(bset);
3234         return NULL;
3235 }
3236
3237 struct isl_basic_set *isl_basic_set_from_underlying_set(
3238         struct isl_basic_set *bset, struct isl_basic_set *like)
3239 {
3240         return (struct isl_basic_set *)
3241                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
3242 }
3243
3244 struct isl_set *isl_set_from_underlying_set(
3245         struct isl_set *set, struct isl_basic_set *like)
3246 {
3247         int i;
3248
3249         if (!set || !like)
3250                 goto error;
3251         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
3252                     goto error);
3253         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
3254                 isl_basic_set_free(like);
3255                 return set;
3256         }
3257         set = isl_set_cow(set);
3258         if (!set)
3259                 goto error;
3260         for (i = 0; i < set->n; ++i) {
3261                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
3262                                                       isl_basic_set_copy(like));
3263                 if (!set->p[i])
3264                         goto error;
3265         }
3266         isl_dim_free(set->dim);
3267         set->dim = isl_dim_copy(like->dim);
3268         if (!set->dim)
3269                 goto error;
3270         isl_basic_set_free(like);
3271         return set;
3272 error:
3273         isl_basic_set_free(like);
3274         isl_set_free(set);
3275         return NULL;
3276 }
3277
3278 struct isl_set *isl_map_underlying_set(struct isl_map *map)
3279 {
3280         int i;
3281
3282         map = isl_map_cow(map);
3283         if (!map)
3284                 return NULL;
3285         map->dim = isl_dim_cow(map->dim);
3286         if (!map->dim)
3287                 goto error;
3288
3289         for (i = 1; i < map->n; ++i)
3290                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
3291                                 goto error);
3292         for (i = 0; i < map->n; ++i) {
3293                 map->p[i] = (struct isl_basic_map *)
3294                                 isl_basic_map_underlying_set(map->p[i]);
3295                 if (!map->p[i])
3296                         goto error;
3297         }
3298         if (map->n == 0)
3299                 map->dim = isl_dim_underlying(map->dim, 0);
3300         else {
3301                 isl_dim_free(map->dim);
3302                 map->dim = isl_dim_copy(map->p[0]->dim);
3303         }
3304         if (!map->dim)
3305                 goto error;
3306         return (struct isl_set *)map;
3307 error:
3308         isl_map_free(map);
3309         return NULL;
3310 }
3311
3312 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
3313 {
3314         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
3315 }
3316
3317 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
3318 {
3319         struct isl_basic_set *domain;
3320         unsigned n_in;
3321         unsigned n_out;
3322         if (!bmap)
3323                 return NULL;
3324         n_in = isl_basic_map_n_in(bmap);
3325         n_out = isl_basic_map_n_out(bmap);
3326         domain = isl_basic_set_from_basic_map(bmap);
3327         return isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
3328 }
3329
3330 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
3331 {
3332         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
3333 }
3334
3335 struct isl_set *isl_map_range(struct isl_map *map)
3336 {
3337         int i;
3338         struct isl_set *set;
3339
3340         if (!map)
3341                 goto error;
3342         if (isl_map_dim(map, isl_dim_in) == 0)
3343                 return (isl_set *)map;
3344
3345         map = isl_map_cow(map);
3346         if (!map)
3347                 goto error;
3348
3349         set = (struct isl_set *) map;
3350         set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
3351         if (!set->dim)
3352                 goto error;
3353         for (i = 0; i < map->n; ++i) {
3354                 set->p[i] = isl_basic_map_range(map->p[i]);
3355                 if (!set->p[i])
3356                         goto error;
3357         }
3358         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3359         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3360         return set;
3361 error:
3362         isl_map_free(map);
3363         return NULL;
3364 }
3365
3366 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3367 {
3368         int i;
3369         struct isl_map *map = NULL;
3370
3371         set = isl_set_cow(set);
3372         if (!set || !dim)
3373                 goto error;
3374         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3375         map = (struct isl_map *)set;
3376         for (i = 0; i < set->n; ++i) {
3377                 map->p[i] = isl_basic_map_from_basic_set(
3378                                 set->p[i], isl_dim_copy(dim));
3379                 if (!map->p[i])
3380                         goto error;
3381         }
3382         isl_dim_free(map->dim);
3383         map->dim = dim;
3384         return map;
3385 error:
3386         isl_dim_free(dim);
3387         isl_set_free(set);
3388         return NULL;
3389 }
3390
3391 struct isl_map *isl_map_from_range(struct isl_set *set)
3392 {
3393         return (struct isl_map *)set;
3394 }
3395
3396 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
3397 {
3398         return isl_map_reverse(isl_map_from_range(set));;
3399 }
3400
3401 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
3402         __isl_take isl_set *range)
3403 {
3404         return isl_map_product(isl_map_from_domain(domain),
3405                                isl_map_from_range(range));
3406 }
3407
3408 struct isl_set *isl_set_from_map(struct isl_map *map)
3409 {
3410         int i;
3411         struct isl_set *set = NULL;
3412
3413         if (!map)
3414                 return NULL;
3415         map = isl_map_cow(map);
3416         if (!map)
3417                 return NULL;
3418         map->dim = isl_dim_cow(map->dim);
3419         if (!map->dim)
3420                 goto error;
3421         map->dim->n_out += map->dim->n_in;
3422         map->dim->n_in = 0;
3423         set = (struct isl_set *)map;
3424         for (i = 0; i < map->n; ++i) {
3425                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3426                 if (!set->p[i])
3427                         goto error;
3428         }
3429         return set;
3430 error:
3431         isl_map_free(map);
3432         return NULL;
3433 }
3434
3435 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3436 {
3437         struct isl_map *map;
3438
3439         if (!dim)
3440                 return NULL;
3441         isl_assert(dim->ctx, n >= 0, return NULL);
3442         map = isl_alloc(dim->ctx, struct isl_map,
3443                         sizeof(struct isl_map) +
3444                         (n - 1) * sizeof(struct isl_basic_map *));
3445         if (!map)
3446                 goto error;
3447
3448         map->ctx = dim->ctx;
3449         isl_ctx_ref(map->ctx);
3450         map->ref = 1;
3451         map->size = n;
3452         map->n = 0;
3453         map->dim = dim;
3454         map->flags = flags;
3455         return map;
3456 error:
3457         isl_dim_free(dim);
3458         return NULL;
3459 }
3460
3461 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3462                 unsigned nparam, unsigned in, unsigned out, int n,
3463                 unsigned flags)
3464 {
3465         struct isl_map *map;
3466         struct isl_dim *dims;
3467
3468         dims = isl_dim_alloc(ctx, nparam, in, out);
3469         if (!dims)
3470                 return NULL;
3471
3472         map = isl_map_alloc_dim(dims, n, flags);
3473         return map;
3474 }
3475
3476 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
3477 {
3478         struct isl_basic_map *bmap;
3479         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
3480         bmap = isl_basic_map_set_to_empty(bmap);
3481         return bmap;
3482 }
3483
3484 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3485 {
3486         struct isl_basic_set *bset;
3487         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3488         bset = isl_basic_set_set_to_empty(bset);
3489         return bset;
3490 }
3491
3492 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3493 {
3494         struct isl_basic_map *bmap;
3495         if (!model)
3496                 return NULL;
3497         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3498         bmap = isl_basic_map_set_to_empty(bmap);
3499         return bmap;
3500 }
3501
3502 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3503 {
3504         struct isl_basic_map *bmap;
3505         if (!model)
3506                 return NULL;
3507         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3508         bmap = isl_basic_map_set_to_empty(bmap);
3509         return bmap;
3510 }
3511
3512 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3513 {
3514         struct isl_basic_set *bset;
3515         if (!model)
3516                 return NULL;
3517         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3518         bset = isl_basic_set_set_to_empty(bset);
3519         return bset;
3520 }
3521
3522 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3523 {
3524         struct isl_basic_map *bmap;
3525         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3526         return bmap;
3527 }
3528
3529 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3530 {
3531         struct isl_basic_set *bset;
3532         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3533         return bset;
3534 }
3535
3536 __isl_give isl_basic_map *isl_basic_map_universe_like(
3537                 __isl_keep isl_basic_map *model)
3538 {
3539         if (!model)
3540                 return NULL;
3541         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3542 }
3543
3544 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3545 {
3546         if (!model)
3547                 return NULL;
3548         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3549 }
3550
3551 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3552         __isl_keep isl_set *model)
3553 {
3554         if (!model)
3555                 return NULL;
3556         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3557 }
3558
3559 struct isl_map *isl_map_empty(struct isl_dim *dim)
3560 {
3561         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3562 }
3563
3564 struct isl_map *isl_map_empty_like(struct isl_map *model)
3565 {
3566         if (!model)
3567                 return NULL;
3568         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3569 }
3570
3571 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3572 {
3573         if (!model)
3574                 return NULL;
3575         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3576 }
3577
3578 struct isl_set *isl_set_empty(struct isl_dim *dim)
3579 {
3580         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3581 }
3582
3583 struct isl_set *isl_set_empty_like(struct isl_set *model)
3584 {
3585         if (!model)
3586                 return NULL;
3587         return isl_set_empty(isl_dim_copy(model->dim));
3588 }
3589
3590 struct isl_map *isl_map_universe(struct isl_dim *dim)
3591 {
3592         struct isl_map *map;
3593         if (!dim)
3594                 return NULL;
3595         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3596         map = isl_map_add_basic_map(map, isl_basic_map_universe(dim));
3597         return map;
3598 }
3599
3600 struct isl_set *isl_set_universe(struct isl_dim *dim)
3601 {
3602         struct isl_set *set;
3603         if (!dim)
3604                 return NULL;
3605         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3606         set = isl_set_add_basic_set(set, isl_basic_set_universe(dim));
3607         return set;
3608 }
3609
3610 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3611 {
3612         if (!model)
3613                 return NULL;
3614         return isl_set_universe(isl_dim_copy(model->dim));
3615 }
3616
3617 struct isl_map *isl_map_dup(struct isl_map *map)
3618 {
3619         int i;
3620         struct isl_map *dup;
3621
3622         if (!map)
3623                 return NULL;
3624         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3625         for (i = 0; i < map->n; ++i)
3626                 dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i]));
3627         return dup;
3628 }
3629
3630 __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
3631                                                 __isl_take isl_basic_map *bmap)
3632 {
3633         if (!bmap || !map)
3634                 goto error;
3635         if (isl_basic_map_fast_is_empty(bmap)) {
3636                 isl_basic_map_free(bmap);
3637                 return map;
3638         }
3639         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3640         isl_assert(map->ctx, map->n < map->size, goto error);
3641         map->p[map->n] = bmap;
3642         map->n++;
3643         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3644         return map;
3645 error:
3646         if (map)
3647                 isl_map_free(map);
3648         if (bmap)
3649                 isl_basic_map_free(bmap);
3650         return NULL;
3651 }
3652
3653 void isl_map_free(struct isl_map *map)
3654 {
3655         int i;
3656
3657         if (!map)
3658                 return;
3659
3660         if (--map->ref > 0)
3661                 return;
3662
3663         isl_ctx_deref(map->ctx);
3664         for (i = 0; i < map->n; ++i)
3665                 isl_basic_map_free(map->p[i]);
3666         isl_dim_free(map->dim);
3667         free(map);
3668 }
3669
3670 struct isl_map *isl_map_extend(struct isl_map *base,
3671                 unsigned nparam, unsigned n_in, unsigned n_out)
3672 {
3673         int i;
3674
3675         base = isl_map_cow(base);
3676         if (!base)
3677                 return NULL;
3678
3679         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3680         if (!base->dim)
3681                 goto error;
3682         for (i = 0; i < base->n; ++i) {
3683                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3684                                 isl_dim_copy(base->dim), 0, 0, 0);
3685                 if (!base->p[i])
3686                         goto error;
3687         }
3688         return base;
3689 error:
3690         isl_map_free(base);
3691         return NULL;
3692 }
3693
3694 struct isl_set *isl_set_extend(struct isl_set *base,
3695                 unsigned nparam, unsigned dim)
3696 {
3697         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3698                                                         nparam, 0, dim);
3699 }
3700
3701 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3702         struct isl_basic_map *bmap, unsigned pos, int value)
3703 {
3704         int j;
3705
3706         bmap = isl_basic_map_cow(bmap);
3707         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3708         j = isl_basic_map_alloc_equality(bmap);
3709         if (j < 0)
3710                 goto error;
3711         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3712         isl_int_set_si(bmap->eq[j][pos], -1);
3713         isl_int_set_si(bmap->eq[j][0], value);
3714         bmap = isl_basic_map_simplify(bmap);
3715         return isl_basic_map_finalize(bmap);
3716 error:
3717         isl_basic_map_free(bmap);
3718         return NULL;
3719 }
3720
3721 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3722         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3723 {
3724         int j;
3725
3726         bmap = isl_basic_map_cow(bmap);
3727         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3728         j = isl_basic_map_alloc_equality(bmap);
3729         if (j < 0)
3730                 goto error;
3731         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3732         isl_int_set_si(bmap->eq[j][pos], -1);
3733         isl_int_set(bmap->eq[j][0], value);
3734         bmap = isl_basic_map_simplify(bmap);
3735         return isl_basic_map_finalize(bmap);
3736 error:
3737         isl_basic_map_free(bmap);
3738         return NULL;
3739 }
3740
3741 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3742                 enum isl_dim_type type, unsigned pos, int value)
3743 {
3744         if (!bmap)
3745                 return NULL;
3746         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3747         return isl_basic_map_fix_pos_si(bmap,
3748                 isl_basic_map_offset(bmap, type) + pos, value);
3749 error:
3750         isl_basic_map_free(bmap);
3751         return NULL;
3752 }
3753
3754 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3755                 enum isl_dim_type type, unsigned pos, isl_int value)
3756 {
3757         if (!bmap)
3758                 return NULL;
3759         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3760         return isl_basic_map_fix_pos(bmap,
3761                 isl_basic_map_offset(bmap, type) + pos, value);
3762 error:
3763         isl_basic_map_free(bmap);
3764         return NULL;
3765 }
3766
3767 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3768                 enum isl_dim_type type, unsigned pos, int value)
3769 {
3770         return (struct isl_basic_set *)
3771                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3772                                         type, pos, value);
3773 }
3774
3775 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3776                 enum isl_dim_type type, unsigned pos, isl_int value)
3777 {
3778         return (struct isl_basic_set *)
3779                 isl_basic_map_fix((struct isl_basic_map *)bset,
3780                                         type, pos, value);
3781 }
3782
3783 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3784                 unsigned input, int value)
3785 {
3786         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3787 }
3788
3789 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3790                 unsigned dim, int value)
3791 {
3792         return (struct isl_basic_set *)
3793                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3794                                         isl_dim_set, dim, value);
3795 }
3796
3797 struct isl_map *isl_map_fix_si(struct isl_map *map,
3798                 enum isl_dim_type type, unsigned pos, int value)
3799 {
3800         int i;
3801
3802         map = isl_map_cow(map);
3803         if (!map)
3804                 return NULL;
3805
3806         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3807         for (i = 0; i < map->n; ++i) {
3808                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
3809                 if (!map->p[i])
3810                         goto error;
3811         }
3812         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3813         return map;
3814 error:
3815         isl_map_free(map);
3816         return NULL;
3817 }
3818
3819 __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
3820                 enum isl_dim_type type, unsigned pos, int value)
3821 {
3822         return (struct isl_set *)
3823                 isl_map_fix_si((struct isl_map *)set, type, pos, value);
3824 }
3825
3826 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
3827                 enum isl_dim_type type, unsigned pos, isl_int value)
3828 {
3829         int i;
3830
3831         map = isl_map_cow(map);
3832         if (!map)
3833                 return NULL;
3834
3835         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3836         for (i = 0; i < map->n; ++i) {
3837                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
3838                 if (!map->p[i])
3839                         goto error;
3840         }
3841         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3842         return map;
3843 error:
3844         isl_map_free(map);
3845         return NULL;
3846 }
3847
3848 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
3849                 enum isl_dim_type type, unsigned pos, isl_int value)
3850 {
3851         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
3852 }
3853
3854 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3855                 unsigned input, int value)
3856 {
3857         return isl_map_fix_si(map, isl_dim_in, input, value);
3858 }
3859
3860 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3861 {
3862         return (struct isl_set *)
3863                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
3864 }
3865
3866 __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
3867                 __isl_take isl_basic_map *bmap,
3868                 enum isl_dim_type type, unsigned pos, int value)
3869 {
3870         int j;
3871
3872         if (!bmap)
3873                 return NULL;
3874         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3875         pos += isl_basic_map_offset(bmap, type);
3876         bmap = isl_basic_map_cow(bmap);
3877         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
3878         j = isl_basic_map_alloc_inequality(bmap);
3879         if (j < 0)
3880                 goto error;
3881         isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
3882         isl_int_set_si(bmap->ineq[j][pos], 1);
3883         isl_int_set_si(bmap->ineq[j][0], -value);
3884         bmap = isl_basic_map_simplify(bmap);
3885         return isl_basic_map_finalize(bmap);
3886 error:
3887         isl_basic_map_free(bmap);
3888         return NULL;
3889 }
3890
3891 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3892         unsigned dim, isl_int value)
3893 {
3894         int j;
3895
3896         bset = isl_basic_set_cow(bset);
3897         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3898         j = isl_basic_set_alloc_inequality(bset);
3899         if (j < 0)
3900                 goto error;
3901         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3902         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3903         isl_int_neg(bset->ineq[j][0], value);
3904         bset = isl_basic_set_simplify(bset);
3905         return isl_basic_set_finalize(bset);
3906 error:
3907         isl_basic_set_free(bset);
3908         return NULL;
3909 }
3910
3911 __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
3912                 enum isl_dim_type type, unsigned pos, int value)
3913 {
3914         int i;
3915
3916         map = isl_map_cow(map);
3917         if (!map)
3918                 return NULL;
3919
3920         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3921         for (i = 0; i < map->n; ++i) {
3922                 map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
3923                                                          type, pos, value);
3924                 if (!map->p[i])
3925                         goto error;
3926         }
3927         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3928         return map;
3929 error:
3930         isl_map_free(map);
3931         return NULL;
3932 }
3933
3934 __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
3935                 enum isl_dim_type type, unsigned pos, int value)
3936 {
3937         return (struct isl_set *)
3938                 isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
3939 }
3940
3941 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3942                                         isl_int value)
3943 {
3944         int i;
3945
3946         set = isl_set_cow(set);
3947         if (!set)
3948                 return NULL;
3949
3950         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3951         for (i = 0; i < set->n; ++i) {
3952                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3953                 if (!set->p[i])
3954                         goto error;
3955         }
3956         return set;
3957 error:
3958         isl_set_free(set);
3959         return NULL;
3960 }
3961
3962 struct isl_map *isl_map_reverse(struct isl_map *map)
3963 {
3964         int i;
3965
3966         map = isl_map_cow(map);
3967         if (!map)
3968                 return NULL;
3969
3970         map->dim = isl_dim_reverse(map->dim);
3971         if (!map->dim)
3972                 goto error;
3973         for (i = 0; i < map->n; ++i) {
3974                 map->p[i] = isl_basic_map_reverse(map->p[i]);
3975                 if (!map->p[i])
3976                         goto error;
3977         }
3978         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3979         return map;
3980 error:
3981         isl_map_free(map);
3982         return NULL;
3983 }
3984
3985 static struct isl_map *isl_basic_map_partial_lexopt(
3986                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3987                 struct isl_set **empty, int max)
3988 {
3989         if (!bmap)
3990                 goto error;
3991         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
3992                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
3993         else
3994                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
3995 error:
3996         isl_basic_map_free(bmap);
3997         isl_basic_set_free(dom);
3998         if (empty)
3999                 *empty = NULL;
4000         return NULL;
4001 }
4002
4003 struct isl_map *isl_basic_map_partial_lexmax(
4004                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4005                 struct isl_set **empty)
4006 {
4007         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
4008 }
4009
4010 struct isl_map *isl_basic_map_partial_lexmin(
4011                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4012                 struct isl_set **empty)
4013 {
4014         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
4015 }
4016
4017 struct isl_set *isl_basic_set_partial_lexmin(
4018                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4019                 struct isl_set **empty)
4020 {
4021         return (struct isl_set *)
4022                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
4023                         dom, empty);
4024 }
4025
4026 struct isl_set *isl_basic_set_partial_lexmax(
4027                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4028                 struct isl_set **empty)
4029 {
4030         return (struct isl_set *)
4031                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
4032                         dom, empty);
4033 }
4034
4035 /* Given a basic map "bmap", compute the lexicograhically minimal
4036  * (or maximal) image element for each domain element in dom.
4037  * Set *empty to those elements in dom that do not have an image element.
4038  *
4039  * We first make sure the basic sets in dom are disjoint and then
4040  * simply collect the results over each of the basic sets separately.
4041  * We could probably improve the efficiency a bit by moving the union
4042  * domain down into the parametric integer programming.
4043  */
4044 static __isl_give isl_map *basic_map_partial_lexopt(
4045                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
4046                 __isl_give isl_set **empty, int max)
4047 {
4048         int i;
4049         struct isl_map *res;
4050
4051         dom = isl_set_make_disjoint(dom);
4052         if (!dom)
4053                 goto error;
4054
4055         if (isl_set_fast_is_empty(dom)) {
4056                 res = isl_map_empty_like_basic_map(bmap);
4057                 *empty = isl_set_empty_like(dom);
4058                 isl_set_free(dom);
4059                 isl_basic_map_free(bmap);
4060                 return res;
4061         }
4062
4063         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4064                         isl_basic_set_copy(dom->p[0]), empty, max);
4065
4066         for (i = 1; i < dom->n; ++i) {
4067                 struct isl_map *res_i;
4068                 struct isl_set *empty_i;
4069
4070                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4071                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
4072
4073                 res = isl_map_union_disjoint(res, res_i);
4074                 *empty = isl_set_union_disjoint(*empty, empty_i);
4075         }
4076
4077         isl_set_free(dom);
4078         isl_basic_map_free(bmap);
4079         return res;
4080 error:
4081         *empty = NULL;
4082         isl_set_free(dom);
4083         isl_basic_map_free(bmap);
4084         return NULL;
4085 }
4086
4087 /* Given a map "map", compute the lexicograhically minimal
4088  * (or maximal) image element for each domain element in dom.
4089  * Set *empty to those elements in dom that do not have an image element.
4090  *
4091  * We first compute the lexicographically minimal or maximal element
4092  * in the first basic map.  This results in a partial solution "res"
4093  * and a subset "todo" of dom that still need to be handled.
4094  * We then consider each of the remaining maps in "map" and successively
4095  * improve both "res" and "todo".
4096  *
4097  * Let res^k and todo^k be the results after k steps and let i = k + 1.
4098  * Assume we are computing the lexicographical maximum.
4099  * We first intersect basic map i with a relation that maps elements
4100  * to elements that are lexicographically larger than the image elements
4101  * in res^k and the compute the maximum image element of this intersection.
4102  * The result ("better") corresponds to those image elements in basic map i
4103  * that are better than what we had before.  The remainder ("keep") are the
4104  * domain elements for which the image element in res_k was better.
4105  * We also compute the lexicographical maximum of basic map i in todo^k.
4106  * res^i is the result of the operation + better + those elements in
4107  *              res^k that we should keep
4108  * todo^i is the remainder of the maximum operation on todo^k.
4109  */
4110 static __isl_give isl_map *isl_map_partial_lexopt(
4111                 __isl_take isl_map *map, __isl_take isl_set *dom,
4112                 __isl_give isl_set **empty, int max)
4113 {
4114         int i;
4115         struct isl_map *res;
4116         struct isl_set *todo;
4117
4118         if (!map || !dom)
4119                 goto error;
4120
4121         if (isl_map_fast_is_empty(map)) {
4122                 if (empty)
4123                         *empty = dom;
4124                 else
4125                         isl_set_free(dom);
4126                 return map;
4127         }
4128
4129         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
4130                                         isl_set_copy(dom), &todo, max);
4131
4132         for (i = 1; i < map->n; ++i) {
4133                 struct isl_map *lt;
4134                 struct isl_map *better;
4135                 struct isl_set *keep;
4136                 struct isl_map *res_i;
4137                 struct isl_set *todo_i;
4138                 struct isl_dim *dim = isl_map_get_dim(res);
4139
4140                 dim = isl_dim_range(dim);
4141                 if (max)
4142                         lt = isl_map_lex_lt(dim);
4143                 else
4144                         lt = isl_map_lex_gt(dim);
4145                 lt = isl_map_apply_range(isl_map_copy(res), lt);
4146                 lt = isl_map_intersect(lt,
4147                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
4148                 better = isl_map_partial_lexopt(lt,
4149                         isl_map_domain(isl_map_copy(res)),
4150                         &keep, max);
4151
4152                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
4153                                                 todo, &todo_i, max);
4154
4155                 res = isl_map_intersect_domain(res, keep);
4156                 res = isl_map_union_disjoint(res, res_i);
4157                 res = isl_map_union_disjoint(res, better);
4158                 todo = todo_i;
4159         }
4160
4161         isl_set_free(dom);
4162         isl_map_free(map);
4163
4164         if (empty)
4165                 *empty = todo;
4166         else
4167                 isl_set_free(todo);
4168
4169         return res;
4170 error:
4171         if (empty)
4172                 *empty = NULL;
4173         isl_set_free(dom);
4174         isl_map_free(map);
4175         return NULL;
4176 }
4177
4178 __isl_give isl_map *isl_map_partial_lexmax(
4179                 __isl_take isl_map *map, __isl_take isl_set *dom,
4180                 __isl_give isl_set **empty)
4181 {
4182         return isl_map_partial_lexopt(map, dom, empty, 1);
4183 }
4184
4185 __isl_give isl_map *isl_map_partial_lexmin(
4186                 __isl_take isl_map *map, __isl_take isl_set *dom,
4187                 __isl_give isl_set **empty)
4188 {
4189         return isl_map_partial_lexopt(map, dom, empty, 0);
4190 }
4191
4192 __isl_give isl_set *isl_set_partial_lexmin(
4193                 __isl_take isl_set *set, __isl_take isl_set *dom,
4194                 __isl_give isl_set **empty)
4195 {
4196         return (struct isl_set *)
4197                 isl_map_partial_lexmin((struct isl_map *)set,
4198                         dom, empty);
4199 }
4200
4201 __isl_give isl_set *isl_set_partial_lexmax(
4202                 __isl_take isl_set *set, __isl_take isl_set *dom,
4203                 __isl_give isl_set **empty)
4204 {
4205         return (struct isl_set *)
4206                 isl_map_partial_lexmax((struct isl_map *)set,
4207                         dom, empty);
4208 }
4209
4210 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
4211 {
4212         struct isl_basic_set *dom = NULL;
4213         struct isl_dim *dom_dim;
4214
4215         if (!bmap)
4216                 goto error;
4217         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
4218         dom = isl_basic_set_universe(dom_dim);
4219         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
4220 error:
4221         isl_basic_map_free(bmap);
4222         return NULL;
4223 }
4224
4225 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
4226 {
4227         return isl_basic_map_lexopt(bmap, 0);
4228 }
4229
4230 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
4231 {
4232         return isl_basic_map_lexopt(bmap, 1);
4233 }
4234
4235 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
4236 {
4237         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
4238 }
4239
4240 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
4241 {
4242         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
4243 }
4244
4245 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
4246 {
4247         struct isl_set *dom = NULL;
4248         struct isl_dim *dom_dim;
4249
4250         if (!map)
4251                 goto error;
4252         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
4253         dom = isl_set_universe(dom_dim);
4254         return isl_map_partial_lexopt(map, dom, NULL, max);
4255 error:
4256         isl_map_free(map);
4257         return NULL;
4258 }
4259
4260 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
4261 {
4262         return isl_map_lexopt(map, 0);
4263 }
4264
4265 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
4266 {
4267         return isl_map_lexopt(map, 1);
4268 }
4269
4270 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
4271 {
4272         return (isl_set *)isl_map_lexmin((isl_map *)set);
4273 }
4274
4275 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
4276 {
4277         return (isl_set *)isl_map_lexmax((isl_map *)set);
4278 }
4279
4280 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
4281         struct isl_dim *dim)
4282 {
4283         int i;
4284
4285         if (!map || !dim)
4286                 goto error;
4287
4288         for (i = 0; i < map->n; ++i) {
4289                 isl_dim_free(map->p[i]->dim);
4290                 map->p[i]->dim = isl_dim_copy(dim);
4291         }
4292         isl_dim_free(map->dim);
4293         map->dim = dim;
4294
4295         return map;
4296 error:
4297         isl_map_free(map);
4298         isl_dim_free(dim);
4299         return NULL;
4300 }
4301
4302 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
4303         struct isl_dim *dim)
4304 {
4305         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
4306 }
4307
4308 /* Apply a preimage specified by "mat" on the parameters of "bset".
4309  * bset is assumed to have only parameters and divs.
4310  */
4311 static struct isl_basic_set *basic_set_parameter_preimage(
4312         struct isl_basic_set *bset, struct isl_mat *mat)
4313 {
4314         unsigned nparam;
4315
4316         if (!bset || !mat)
4317                 goto error;
4318
4319         bset->dim = isl_dim_cow(bset->dim);
4320         if (!bset->dim)
4321                 goto error;
4322
4323         nparam = isl_basic_set_dim(bset, isl_dim_param);
4324
4325         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
4326
4327         bset->dim->nparam = 0;
4328         bset->dim->n_out = nparam;
4329         bset = isl_basic_set_preimage(bset, mat);
4330         if (bset) {
4331                 bset->dim->nparam = bset->dim->n_out;
4332                 bset->dim->n_out = 0;
4333         }
4334         return bset;
4335 error:
4336         isl_mat_free(mat);
4337         isl_basic_set_free(bset);
4338         return NULL;
4339 }
4340
4341 /* Apply a preimage specified by "mat" on the parameters of "set".
4342  * set is assumed to have only parameters and divs.
4343  */
4344 static struct isl_set *set_parameter_preimage(
4345         struct isl_set *set, struct isl_mat *mat)
4346 {
4347         struct isl_dim *dim = NULL;
4348         unsigned nparam;
4349
4350         if (!set || !mat)
4351                 goto error;
4352
4353         dim = isl_dim_copy(set->dim);
4354         dim = isl_dim_cow(dim);
4355         if (!dim)
4356                 goto error;
4357
4358         nparam = isl_set_dim(set, isl_dim_param);
4359
4360         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
4361
4362         dim->nparam = 0;
4363         dim->n_out = nparam;
4364         isl_set_reset_dim(set, dim);
4365         set = isl_set_preimage(set, mat);
4366         if (!set)
4367                 goto error2;
4368         dim = isl_dim_copy(set->dim);
4369         dim = isl_dim_cow(dim);
4370         if (!dim)
4371                 goto error2;
4372         dim->nparam = dim->n_out;
4373         dim->n_out = 0;
4374         isl_set_reset_dim(set, dim);
4375         return set;
4376 error:
4377         isl_dim_free(dim);
4378         isl_mat_free(mat);
4379 error2:
4380         isl_set_free(set);
4381         return NULL;
4382 }
4383
4384 /* Intersect the basic set "bset" with the affine space specified by the
4385  * equalities in "eq".
4386  */
4387 static struct isl_basic_set *basic_set_append_equalities(
4388         struct isl_basic_set *bset, struct isl_mat *eq)
4389 {
4390         int i, k;
4391         unsigned len;
4392
4393         if (!bset || !eq)
4394                 goto error;
4395
4396         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
4397                                         eq->n_row, 0);
4398         if (!bset)
4399                 goto error;
4400
4401         len = 1 + isl_dim_total(bset->dim) + bset->extra;
4402         for (i = 0; i < eq->n_row; ++i) {
4403                 k = isl_basic_set_alloc_equality(bset);
4404                 if (k < 0)
4405                         goto error;
4406                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
4407                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
4408         }
4409         isl_mat_free(eq);
4410
4411         bset = isl_basic_set_gauss(bset, NULL);
4412         bset = isl_basic_set_finalize(bset);
4413
4414         return bset;
4415 error:
4416         isl_mat_free(eq);
4417         isl_basic_set_free(bset);
4418         return NULL;
4419 }
4420
4421 /* Intersect the set "set" with the affine space specified by the
4422  * equalities in "eq".
4423  */
4424 static struct isl_set *set_append_equalities(struct isl_set *set,
4425         struct isl_mat *eq)
4426 {
4427         int i;
4428
4429         if (!set || !eq)
4430                 goto error;
4431
4432         for (i = 0; i < set->n; ++i) {
4433                 set->p[i] = basic_set_append_equalities(set->p[i],
4434                                         isl_mat_copy(eq));
4435                 if (!set->p[i])
4436                         goto error;
4437         }
4438         isl_mat_free(eq);
4439         return set;
4440 error:
4441         isl_mat_free(eq);
4442         isl_set_free(set);
4443         return NULL;
4444 }
4445
4446 /* Project the given basic set onto its parameter domain, possibly introducing
4447  * new, explicit, existential variables in the constraints.
4448  * The input has parameters and (possibly implicit) existential variables.
4449  * The output has the same parameters, but only
4450  * explicit existentially quantified variables.
4451  *
4452  * The actual projection is performed by pip, but pip doesn't seem
4453  * to like equalities very much, so we first remove the equalities
4454  * among the parameters by performing a variable compression on
4455  * the parameters.  Afterward, an inverse transformation is performed
4456  * and the equalities among the parameters are inserted back in.
4457  */
4458 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
4459 {
4460         int i, j;
4461         struct isl_mat *eq;
4462         struct isl_mat *T, *T2;
4463         struct isl_set *set;
4464         unsigned nparam, n_div;
4465
4466         bset = isl_basic_set_cow(bset);
4467         if (!bset)
4468                 return NULL;
4469
4470         if (bset->n_eq == 0)
4471                 return isl_basic_set_lexmin(bset);
4472
4473         isl_basic_set_gauss(bset, NULL);
4474
4475         nparam = isl_basic_set_dim(bset, isl_dim_param);
4476         n_div = isl_basic_set_dim(bset, isl_dim_div);
4477
4478         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
4479                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
4480                         ++i;
4481         }
4482         if (i == bset->n_eq)
4483                 return isl_basic_set_lexmin(bset);
4484
4485         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
4486                 0, 1 + nparam);
4487         eq = isl_mat_cow(eq);
4488         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
4489         if (T && T->n_col == 0) {
4490                 isl_mat_free(T);
4491                 isl_mat_free(T2);
4492                 isl_mat_free(eq);
4493                 bset = isl_basic_set_set_to_empty(bset);
4494                 return isl_set_from_basic_set(bset);
4495         }
4496         bset = basic_set_parameter_preimage(bset, T);
4497
4498         set = isl_basic_set_lexmin(bset);
4499         set = set_parameter_preimage(set, T2);
4500         set = set_append_equalities(set, eq);
4501         return set;
4502 }
4503
4504 /* Compute an explicit representation for all the existentially
4505  * quantified variables.
4506  * The input and output dimensions are first turned into parameters.
4507  * compute_divs then returns a map with the same parameters and
4508  * no input or output dimensions and the dimension specification
4509  * is reset to that of the input.
4510  */
4511 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
4512 {
4513         struct isl_basic_set *bset;
4514         struct isl_set *set;
4515         struct isl_map *map;
4516         struct isl_dim *dim, *orig_dim = NULL;
4517         unsigned         nparam;
4518         unsigned         n_in;
4519         unsigned         n_out;
4520
4521         bmap = isl_basic_map_cow(bmap);
4522         if (!bmap)
4523                 return NULL;
4524
4525         nparam = isl_basic_map_dim(bmap, isl_dim_param);
4526         n_in = isl_basic_map_dim(bmap, isl_dim_in);
4527         n_out = isl_basic_map_dim(bmap, isl_dim_out);
4528         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
4529         if (!dim)
4530                 goto error;
4531
4532         orig_dim = bmap->dim;
4533         bmap->dim = dim;
4534         bset = (struct isl_basic_set *)bmap;
4535
4536         set = parameter_compute_divs(bset);
4537         map = (struct isl_map *)set;
4538         map = isl_map_reset_dim(map, orig_dim);
4539
4540         return map;
4541 error:
4542         isl_basic_map_free(bmap);
4543         return NULL;
4544 }
4545
4546 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
4547 {
4548         int i;
4549         unsigned off;
4550
4551         if (!bmap)
4552                 return -1;
4553
4554         off = isl_dim_total(bmap->dim);
4555         for (i = 0; i < bmap->n_div; ++i) {
4556                 if (isl_int_is_zero(bmap->div[i][0]))
4557                         return 0;
4558                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
4559                                 return -1);
4560         }
4561         return 1;
4562 }
4563
4564 static int map_divs_known(__isl_keep isl_map *map)
4565 {
4566         int i;
4567
4568         if (!map)
4569                 return -1;
4570
4571         for (i = 0; i < map->n; ++i) {
4572                 int known = basic_map_divs_known(map->p[i]);
4573                 if (known <= 0)
4574                         return known;
4575         }
4576
4577         return 1;
4578 }
4579
4580 /* If bmap contains any unknown divs, then compute explicit
4581  * expressions for them.  However, this computation may be
4582  * quite expensive, so first try to remove divs that aren't
4583  * strictly needed.
4584  */
4585 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
4586 {
4587         int i;
4588         int known;
4589         struct isl_map *map;
4590
4591         known = basic_map_divs_known(bmap);
4592         if (known < 0)
4593                 goto error;
4594         if (known)
4595                 return isl_map_from_basic_map(bmap);
4596
4597         bmap = isl_basic_map_drop_redundant_divs(bmap);
4598
4599         known = basic_map_divs_known(bmap);
4600         if (known < 0)
4601                 goto error;
4602         if (known)
4603                 return isl_map_from_basic_map(bmap);
4604
4605         map = compute_divs(bmap);
4606         return map;
4607 error:
4608         isl_basic_map_free(bmap);
4609         return NULL;
4610 }
4611
4612 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4613 {
4614         int i;
4615         int known;
4616         struct isl_map *res;
4617
4618         if (!map)
4619                 return NULL;
4620         if (map->n == 0)
4621                 return map;
4622
4623         known = map_divs_known(map);
4624         if (known < 0) {
4625                 isl_map_free(map);
4626                 return NULL;
4627         }
4628         if (known)
4629                 return map;
4630
4631         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4632         for (i = 1 ; i < map->n; ++i) {
4633                 struct isl_map *r2;
4634                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4635                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4636                         res = isl_map_union_disjoint(res, r2);
4637                 else
4638                         res = isl_map_union(res, r2);
4639         }
4640         isl_map_free(map);
4641
4642         return res;
4643 }
4644
4645 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4646 {
4647         return (struct isl_set *)
4648                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4649 }
4650
4651 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4652 {
4653         return (struct isl_set *)
4654                 isl_map_compute_divs((struct isl_map *)set);
4655 }
4656
4657 struct isl_set *isl_map_domain(struct isl_map *map)
4658 {
4659         int i;
4660         struct isl_set *set;
4661
4662         if (!map)
4663                 goto error;
4664
4665         map = isl_map_cow(map);
4666         if (!map)
4667                 return NULL;
4668
4669         set = (struct isl_set *)map;
4670         set->dim = isl_dim_domain(set->dim);
4671         if (!set->dim)
4672                 goto error;
4673         for (i = 0; i < map->n; ++i) {
4674                 set->p[i] = isl_basic_map_domain(map->p[i]);
4675                 if (!set->p[i])
4676                         goto error;
4677         }
4678         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4679         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4680         return set;
4681 error:
4682         isl_map_free(map);
4683         return NULL;
4684 }
4685
4686 struct isl_map *isl_map_union_disjoint(
4687                         struct isl_map *map1, struct isl_map *map2)
4688 {
4689         int i;
4690         unsigned flags = 0;
4691         struct isl_map *map = NULL;
4692
4693         if (!map1 || !map2)
4694                 goto error;
4695
4696         if (map1->n == 0) {
4697                 isl_map_free(map1);
4698                 return map2;
4699         }
4700         if (map2->n == 0) {
4701                 isl_map_free(map2);
4702                 return map1;
4703         }
4704
4705         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4706
4707         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4708             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4709                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4710
4711         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4712                                 map1->n + map2->n, flags);
4713         if (!map)
4714                 goto error;
4715         for (i = 0; i < map1->n; ++i) {
4716                 map = isl_map_add_basic_map(map,
4717                                   isl_basic_map_copy(map1->p[i]));
4718                 if (!map)
4719                         goto error;
4720         }
4721         for (i = 0; i < map2->n; ++i) {
4722                 map = isl_map_add_basic_map(map,
4723                                   isl_basic_map_copy(map2->p[i]));
4724                 if (!map)
4725                         goto error;
4726         }
4727         isl_map_free(map1);
4728         isl_map_free(map2);
4729         return map;
4730 error:
4731         isl_map_free(map);
4732         isl_map_free(map1);
4733         isl_map_free(map2);
4734         return NULL;
4735 }
4736
4737 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4738 {
4739         map1 = isl_map_union_disjoint(map1, map2);
4740         if (!map1)
4741                 return NULL;
4742         if (map1->n > 1)
4743                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4744         return map1;
4745 }
4746
4747 struct isl_set *isl_set_union_disjoint(
4748                         struct isl_set *set1, struct isl_set *set2)
4749 {
4750         return (struct isl_set *)
4751                 isl_map_union_disjoint(
4752                         (struct isl_map *)set1, (struct isl_map *)set2);
4753 }
4754
4755 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4756 {
4757         return (struct isl_set *)
4758                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4759 }
4760
4761 struct isl_map *isl_map_intersect_range(
4762                 struct isl_map *map, struct isl_set *set)
4763 {
4764         unsigned flags = 0;
4765         struct isl_map *result;
4766         int i, j;
4767
4768         if (!map || !set)
4769                 goto error;
4770
4771         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4772             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4773                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4774
4775         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4776                                         map->n * set->n, flags);
4777         if (!result)
4778                 goto error;
4779         for (i = 0; i < map->n; ++i)
4780                 for (j = 0; j < set->n; ++j) {
4781                         result = isl_map_add_basic_map(result,
4782                             isl_basic_map_intersect_range(
4783                                 isl_basic_map_copy(map->p[i]),
4784                                 isl_basic_set_copy(set->p[j])));
4785                         if (!result)
4786                                 goto error;
4787                 }
4788         isl_map_free(map);
4789         isl_set_free(set);
4790         return result;
4791 error:
4792         isl_map_free(map);
4793         isl_set_free(set);
4794         return NULL;
4795 }
4796
4797 struct isl_map *isl_map_intersect_domain(
4798                 struct isl_map *map, struct isl_set *set)
4799 {
4800         return isl_map_reverse(
4801                 isl_map_intersect_range(isl_map_reverse(map), set));
4802 }
4803
4804 struct isl_map *isl_map_apply_domain(
4805                 struct isl_map *map1, struct isl_map *map2)
4806 {
4807         if (!map1 || !map2)
4808                 goto error;
4809         map1 = isl_map_reverse(map1);
4810         map1 = isl_map_apply_range(map1, map2);
4811         return isl_map_reverse(map1);
4812 error:
4813         isl_map_free(map1);
4814         isl_map_free(map2);
4815         return NULL;
4816 }
4817
4818 struct isl_map *isl_map_apply_range(
4819                 struct isl_map *map1, struct isl_map *map2)
4820 {
4821         struct isl_dim *dim_result;
4822         struct isl_map *result;
4823         int i, j;
4824
4825         if (!map1 || !map2)
4826                 goto error;
4827
4828         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4829                                   isl_dim_copy(map2->dim));
4830
4831         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4832         if (!result)
4833                 goto error;
4834         for (i = 0; i < map1->n; ++i)
4835                 for (j = 0; j < map2->n; ++j) {
4836                         result = isl_map_add_basic_map(result,
4837                             isl_basic_map_apply_range(
4838                                 isl_basic_map_copy(map1->p[i]),
4839                                 isl_basic_map_copy(map2->p[j])));
4840                         if (!result)
4841                                 goto error;
4842                 }
4843         isl_map_free(map1);
4844         isl_map_free(map2);
4845         if (result && result->n <= 1)
4846                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4847         return result;
4848 error:
4849         isl_map_free(map1);
4850         isl_map_free(map2);
4851         return NULL;
4852 }
4853
4854 /*
4855  * returns range - domain
4856  */
4857 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4858 {
4859         isl_dim *dims;
4860         struct isl_basic_set *bset;
4861         unsigned dim;
4862         unsigned nparam;
4863         int i;
4864
4865         if (!bmap)
4866                 goto error;
4867         dim = isl_basic_map_n_in(bmap);
4868         nparam = isl_basic_map_n_param(bmap);
4869         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4870         bset = isl_basic_set_from_basic_map(bmap);
4871         bset = isl_basic_set_cow(bset);
4872         dims = isl_basic_set_get_dim(bset);
4873         dims = isl_dim_add(dims, isl_dim_set, dim);
4874         bset = isl_basic_set_extend_dim(bset, dims, 0, dim, 0);
4875         bset = isl_basic_set_swap_vars(bset, 2*dim);
4876         for (i = 0; i < dim; ++i) {
4877                 int j = isl_basic_map_alloc_equality(
4878                                             (struct isl_basic_map *)bset);
4879                 if (j < 0)
4880                         goto error;
4881                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4882                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4883                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4884                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4885         }
4886         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4887 error:
4888         isl_basic_map_free(bmap);
4889         return NULL;
4890 }
4891
4892 /*
4893  * returns range - domain
4894  */
4895 struct isl_set *isl_map_deltas(struct isl_map *map)
4896 {
4897         int i;
4898         isl_dim *dim;
4899         struct isl_set *result;
4900
4901         if (!map)
4902                 return NULL;
4903
4904         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4905         dim = isl_map_get_dim(map);
4906         dim = isl_dim_domain(dim);
4907         result = isl_set_alloc_dim(dim, map->n, map->flags);
4908         if (!result)
4909                 goto error;
4910         for (i = 0; i < map->n; ++i)
4911                 result = isl_set_add_basic_set(result,
4912                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4913         isl_map_free(map);
4914         return result;
4915 error:
4916         isl_map_free(map);
4917         return NULL;
4918 }
4919
4920 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4921 {
4922         struct isl_basic_map *bmap;
4923         unsigned nparam;
4924         unsigned dim;
4925         int i;
4926
4927         if (!dims)
4928                 return NULL;
4929
4930         nparam = dims->nparam;
4931         dim = dims->n_out;
4932         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4933         if (!bmap)
4934                 goto error;
4935
4936         for (i = 0; i < dim; ++i) {
4937                 int j = isl_basic_map_alloc_equality(bmap);
4938                 if (j < 0)
4939                         goto error;
4940                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4941                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
4942                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
4943         }
4944         return isl_basic_map_finalize(bmap);
4945 error:
4946         isl_basic_map_free(bmap);
4947         return NULL;
4948 }
4949
4950 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
4951 {
4952         struct isl_dim *dim = isl_dim_map(set_dim);
4953         if (!dim)
4954                 return NULL;
4955         return basic_map_identity(dim);
4956 }
4957
4958 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
4959 {
4960         if (!model || !model->dim)
4961                 return NULL;
4962         isl_assert(model->ctx,
4963                         model->dim->n_in == model->dim->n_out, return NULL);
4964         return basic_map_identity(isl_dim_copy(model->dim));
4965 }
4966
4967 static struct isl_map *map_identity(struct isl_dim *dim)
4968 {
4969         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
4970         return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim)));
4971 }
4972
4973 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
4974 {
4975         struct isl_dim *dim = isl_dim_map(set_dim);
4976         if (!dim)
4977                 return NULL;
4978         return map_identity(dim);
4979 }
4980
4981 struct isl_map *isl_map_identity_like(struct isl_map *model)
4982 {
4983         if (!model || !model->dim)
4984                 return NULL;
4985         isl_assert(model->ctx,
4986                         model->dim->n_in == model->dim->n_out, return NULL);
4987         return map_identity(isl_dim_copy(model->dim));
4988 }
4989
4990 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
4991 {
4992         if (!model || !model->dim)
4993                 return NULL;
4994         isl_assert(model->ctx,
4995                         model->dim->n_in == model->dim->n_out, return NULL);
4996         return map_identity(isl_dim_copy(model->dim));
4997 }
4998
4999 /* Construct a basic set with all set dimensions having only non-negative
5000  * values.
5001  */
5002 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
5003 {
5004         int i;
5005         unsigned nparam;
5006         unsigned dim;
5007         struct isl_basic_set *bset;
5008
5009         if (!dims)
5010                 return NULL;
5011         nparam = dims->nparam;
5012         dim = dims->n_out;
5013         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
5014         if (!bset)
5015                 return NULL;
5016         for (i = 0; i < dim; ++i) {
5017                 int k = isl_basic_set_alloc_inequality(bset);
5018                 if (k < 0)
5019                         goto error;
5020                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
5021                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
5022         }
5023         return bset;
5024 error:
5025         isl_basic_set_free(bset);
5026         return NULL;
5027 }
5028
5029 __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set,
5030         enum isl_dim_type type, unsigned first, unsigned n)
5031 {
5032         int i;
5033         isl_basic_set *nonneg = NULL;
5034         isl_basic_set *neg = NULL;
5035
5036         if (!set)
5037                 return NULL;
5038         if (n == 0)
5039                 return set;
5040
5041         isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error);
5042
5043         for (i = 0; i < n; ++i) {
5044                 int k;
5045
5046                 neg = NULL;
5047                 nonneg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5048                 k = isl_basic_set_alloc_inequality(nonneg);
5049                 if (k < 0)
5050                         goto error;
5051                 isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg));
5052                 isl_int_set_si(nonneg->ineq[k][pos(set->dim, type) + first + i], 1);
5053
5054                 neg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5055                 k = isl_basic_set_alloc_inequality(neg);
5056                 if (k < 0)
5057                         goto error;
5058                 isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg));
5059                 isl_int_set_si(neg->ineq[k][0], -1);
5060                 isl_int_set_si(neg->ineq[k][pos(set->dim, type) + first + i], -1);
5061
5062                 set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg));
5063         }
5064
5065         return set;
5066 error:
5067         isl_basic_set_free(nonneg);
5068         isl_basic_set_free(neg);
5069         isl_set_free(set);
5070         return NULL;
5071 }
5072
5073 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
5074 {
5075         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
5076 }
5077
5078 int isl_basic_map_is_subset(
5079                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5080 {
5081         int is_subset;
5082         struct isl_map *map1;
5083         struct isl_map *map2;
5084
5085         if (!bmap1 || !bmap2)
5086                 return -1;
5087
5088         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
5089         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
5090
5091         is_subset = isl_map_is_subset(map1, map2);
5092
5093         isl_map_free(map1);
5094         isl_map_free(map2);
5095
5096         return is_subset;
5097 }
5098
5099 int isl_basic_map_is_equal(
5100                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5101 {
5102         int is_subset;
5103
5104         if (!bmap1 || !bmap2)
5105                 return -1;
5106         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5107         if (is_subset != 1)
5108                 return is_subset;
5109         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5110         return is_subset;
5111 }
5112
5113 int isl_basic_set_is_equal(
5114                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5115 {
5116         return isl_basic_map_is_equal(
5117                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
5118 }
5119
5120 int isl_map_is_empty(struct isl_map *map)
5121 {
5122         int i;
5123         int is_empty;
5124
5125         if (!map)
5126                 return -1;
5127         for (i = 0; i < map->n; ++i) {
5128                 is_empty = isl_basic_map_is_empty(map->p[i]);
5129                 if (is_empty < 0)
5130                         return -1;
5131                 if (!is_empty)
5132                         return 0;
5133         }
5134         return 1;
5135 }
5136
5137 int isl_map_fast_is_empty(struct isl_map *map)
5138 {
5139         return map->n == 0;
5140 }
5141
5142 int isl_set_fast_is_empty(struct isl_set *set)
5143 {
5144         return set->n == 0;
5145 }
5146
5147 int isl_set_is_empty(struct isl_set *set)
5148 {
5149         return isl_map_is_empty((struct isl_map *)set);
5150 }
5151
5152 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
5153 {
5154         int is_subset;
5155
5156         if (!map1 || !map2)
5157                 return -1;
5158         is_subset = isl_map_is_subset(map1, map2);
5159         if (is_subset != 1)
5160                 return is_subset;
5161         is_subset = isl_map_is_subset(map2, map1);
5162         return is_subset;
5163 }
5164
5165 int isl_basic_map_is_strict_subset(
5166                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5167 {
5168         int is_subset;
5169
5170         if (!bmap1 || !bmap2)
5171                 return -1;
5172         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5173         if (is_subset != 1)
5174                 return is_subset;
5175         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5176         if (is_subset == -1)
5177                 return is_subset;
5178         return !is_subset;
5179 }
5180
5181 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
5182 {
5183         int is_subset;
5184
5185         if (!map1 || !map2)
5186                 return -1;
5187         is_subset = isl_map_is_subset(map1, map2);
5188         if (is_subset != 1)
5189                 return is_subset;
5190         is_subset = isl_map_is_subset(map2, map1);
5191         if (is_subset == -1)
5192                 return is_subset;
5193         return !is_subset;
5194 }
5195
5196 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
5197 {
5198         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
5199 }
5200
5201 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
5202 {
5203         if (!bmap)
5204                 return -1;
5205         return bmap->n_eq == 0 && bmap->n_ineq == 0;
5206 }
5207
5208 int isl_basic_set_is_universe(struct isl_basic_set *bset)
5209 {
5210         if (!bset)
5211                 return -1;
5212         return bset->n_eq == 0 && bset->n_ineq == 0;
5213 }
5214
5215 int isl_map_fast_is_universe(__isl_keep isl_map *map)
5216 {
5217         if (!map)
5218                 return -1;
5219
5220         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
5221 }
5222
5223 int isl_set_fast_is_universe(__isl_keep isl_set *set)
5224 {
5225         return isl_map_fast_is_universe((isl_map *) set);
5226 }
5227
5228 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
5229 {
5230         struct isl_basic_set *bset = NULL;
5231         struct isl_vec *sample = NULL;
5232         int empty;
5233         unsigned total;
5234
5235         if (!bmap)
5236                 return -1;
5237
5238         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
5239                 return 1;
5240
5241         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
5242                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
5243                 copy = isl_basic_map_convex_hull(copy);
5244                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
5245                 isl_basic_map_free(copy);
5246                 return empty;
5247         }
5248
5249         total = 1 + isl_basic_map_total_dim(bmap);
5250         if (bmap->sample && bmap->sample->size == total) {
5251                 int contains = isl_basic_map_contains(bmap, bmap->sample);
5252                 if (contains < 0)
5253                         return -1;
5254                 if (contains)
5255                         return 0;
5256         }
5257         isl_vec_free(bmap->sample);
5258         bmap->sample = NULL;
5259         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
5260         if (!bset)
5261                 return -1;
5262         sample = isl_basic_set_sample_vec(bset);
5263         if (!sample)
5264                 return -1;
5265         empty = sample->size == 0;
5266         isl_vec_free(bmap->sample);
5267         bmap->sample = sample;
5268         if (empty)
5269                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
5270
5271         return empty;
5272 }
5273
5274 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
5275 {
5276         if (!bmap)
5277                 return -1;
5278         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
5279 }
5280
5281 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
5282 {
5283         if (!bset)
5284                 return -1;
5285         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
5286 }
5287
5288 int isl_basic_set_is_empty(struct isl_basic_set *bset)
5289 {
5290         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
5291 }
5292
5293 struct isl_map *isl_basic_map_union(
5294         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5295 {
5296         struct isl_map *map;
5297         if (!bmap1 || !bmap2)
5298                 return NULL;
5299
5300         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
5301
5302         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
5303         if (!map)
5304                 goto error;
5305         map = isl_map_add_basic_map(map, bmap1);
5306         map = isl_map_add_basic_map(map, bmap2);
5307         return map;
5308 error:
5309         isl_basic_map_free(bmap1);
5310         isl_basic_map_free(bmap2);
5311         return NULL;
5312 }
5313
5314 struct isl_set *isl_basic_set_union(
5315                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5316 {
5317         return (struct isl_set *)isl_basic_map_union(
5318                                             (struct isl_basic_map *)bset1,
5319                                             (struct isl_basic_map *)bset2);
5320 }
5321
5322 /* Order divs such that any div only depends on previous divs */
5323 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
5324 {
5325         int i;
5326         unsigned off = isl_dim_total(bmap->dim);
5327
5328         for (i = 0; i < bmap->n_div; ++i) {
5329                 int pos;
5330                 if (isl_int_is_zero(bmap->div[i][0]))
5331                         continue;
5332                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
5333                                                             bmap->n_div-i);
5334                 if (pos == -1)
5335                         continue;
5336                 isl_basic_map_swap_div(bmap, i, i + pos);
5337                 --i;
5338         }
5339         return bmap;
5340 }
5341
5342 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
5343 {
5344         return (struct isl_basic_set *)
5345                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
5346 }
5347
5348 __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
5349 {
5350         int i;
5351
5352         if (!map)
5353                 return 0;
5354
5355         for (i = 0; i < map->n; ++i) {
5356                 map->p[i] = isl_basic_map_order_divs(map->p[i]);
5357                 if (!map->p[i])
5358                         goto error;
5359         }
5360
5361         return map;
5362 error:
5363         isl_map_free(map);
5364         return NULL;
5365 }
5366
5367 /* Look for a div in dst that corresponds to the div "div" in src.
5368  * The divs before "div" in src and dst are assumed to be the same.
5369  *
5370  * Returns -1 if no corresponding div was found and the position
5371  * of the corresponding div in dst otherwise.
5372  */
5373 static int find_div(struct isl_basic_map *dst,
5374                         struct isl_basic_map *src, unsigned div)
5375 {
5376         int i;
5377
5378         unsigned total = isl_dim_total(src->dim);
5379
5380         isl_assert(dst->ctx, div <= dst->n_div, return -1);
5381         for (i = div; i < dst->n_div; ++i)
5382                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
5383                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
5384                                                 dst->n_div - div) == -1)
5385                         return i;
5386         return -1;
5387 }
5388
5389 struct isl_basic_map *isl_basic_map_align_divs(
5390                 struct isl_basic_map *dst, struct isl_basic_map *src)
5391 {
5392         int i;
5393         unsigned total = isl_dim_total(src->dim);
5394
5395         if (!dst || !src)
5396                 goto error;
5397
5398         if (src->n_div == 0)
5399                 return dst;
5400
5401         for (i = 0; i < src->n_div; ++i)
5402                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
5403
5404         src = isl_basic_map_order_divs(src);
5405         dst = isl_basic_map_cow(dst);
5406         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
5407                         src->n_div, 0, 2 * src->n_div);
5408         if (!dst)
5409                 return NULL;
5410         for (i = 0; i < src->n_div; ++i) {
5411                 int j = find_div(dst, src, i);
5412                 if (j < 0) {
5413                         j = isl_basic_map_alloc_div(dst);
5414                         if (j < 0)
5415                                 goto error;
5416                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
5417                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
5418                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
5419                                 goto error;
5420                 }
5421                 if (j != i)
5422                         isl_basic_map_swap_div(dst, i, j);
5423         }
5424         return dst;
5425 error:
5426         isl_basic_map_free(dst);
5427         return NULL;
5428 }
5429
5430 struct isl_basic_set *isl_basic_set_align_divs(
5431                 struct isl_basic_set *dst, struct isl_basic_set *src)
5432 {
5433         return (struct isl_basic_set *)isl_basic_map_align_divs(
5434                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
5435 }
5436
5437 struct isl_map *isl_map_align_divs(struct isl_map *map)
5438 {
5439         int i;
5440
5441         if (!map)
5442                 return NULL;
5443         if (map->n == 0)
5444                 return map;
5445         map = isl_map_compute_divs(map);
5446         map = isl_map_cow(map);
5447         if (!map)
5448                 return NULL;
5449
5450         for (i = 1; i < map->n; ++i)
5451                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
5452         for (i = 1; i < map->n; ++i)
5453                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
5454
5455         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5456         return map;
5457 }
5458
5459 struct isl_set *isl_set_align_divs(struct isl_set *set)
5460 {
5461         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
5462 }
5463
5464 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
5465 {
5466         if (!set || !map)
5467                 goto error;
5468         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
5469         map = isl_map_intersect_domain(map, set);
5470         set = isl_map_range(map);
5471         return set;
5472 error:
5473         isl_set_free(set);
5474         isl_map_free(map);
5475         return NULL;
5476 }
5477
5478 /* There is no need to cow as removing empty parts doesn't change
5479  * the meaning of the set.
5480  */
5481 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
5482 {
5483         int i;
5484
5485         if (!map)
5486                 return NULL;
5487
5488         for (i = map->n-1; i >= 0; --i) {
5489                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
5490                         continue;
5491                 isl_basic_map_free(map->p[i]);
5492                 if (i != map->n-1) {
5493                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5494                         map->p[i] = map->p[map->n-1];
5495                 }
5496                 map->n--;
5497         }
5498
5499         return map;
5500 }
5501
5502 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
5503 {
5504         return (struct isl_set *)
5505                 isl_map_remove_empty_parts((struct isl_map *)set);
5506 }
5507
5508 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
5509 {
5510         struct isl_basic_map *bmap;
5511         if (!map || map->n == 0)
5512                 return NULL;
5513         bmap = map->p[map->n-1];
5514         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
5515         return isl_basic_map_copy(bmap);
5516 }
5517
5518 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
5519 {
5520         return (struct isl_basic_set *)
5521                 isl_map_copy_basic_map((struct isl_map *)set);
5522 }
5523
5524 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
5525                                                 __isl_keep isl_basic_map *bmap)
5526 {
5527         int i;
5528
5529         if (!map || !bmap)
5530                 goto error;
5531         for (i = map->n-1; i >= 0; --i) {
5532                 if (map->p[i] != bmap)
5533                         continue;
5534                 map = isl_map_cow(map);
5535                 if (!map)
5536                         goto error;
5537                 isl_basic_map_free(map->p[i]);
5538                 if (i != map->n-1) {
5539                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
5540                         map->p[i] = map->p[map->n-1];
5541                 }
5542                 map->n--;
5543                 return map;
5544         }
5545         return map;
5546 error:
5547         isl_map_free(map);
5548         return NULL;
5549 }
5550
5551 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
5552                                                 struct isl_basic_set *bset)
5553 {
5554         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
5555                                                 (struct isl_basic_map *)bset);
5556 }
5557
5558 /* Given two basic sets bset1 and bset2, compute the maximal difference
5559  * between the values of dimension pos in bset1 and those in bset2
5560  * for any common value of the parameters and dimensions preceding pos.
5561  */
5562 static enum isl_lp_result basic_set_maximal_difference_at(
5563         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
5564         int pos, isl_int *opt)
5565 {
5566         struct isl_dim *dims;
5567         struct isl_basic_map *bmap1 = NULL;
5568         struct isl_basic_map *bmap2 = NULL;
5569         struct isl_ctx *ctx;
5570         struct isl_vec *obj;
5571         unsigned total;
5572         unsigned nparam;
5573         unsigned dim1, dim2;
5574         enum isl_lp_result res;
5575
5576         if (!bset1 || !bset2)
5577                 return isl_lp_error;
5578
5579         nparam = isl_basic_set_n_param(bset1);
5580         dim1 = isl_basic_set_n_dim(bset1);
5581         dim2 = isl_basic_set_n_dim(bset2);
5582         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
5583         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
5584         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
5585         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
5586         if (!bmap1 || !bmap2)
5587                 goto error;
5588         bmap1 = isl_basic_map_cow(bmap1);
5589         bmap1 = isl_basic_map_extend(bmap1, nparam,
5590                         pos, (dim1 - pos) + (dim2 - pos),
5591                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
5592         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
5593         if (!bmap1)
5594                 goto error;
5595         total = isl_basic_map_total_dim(bmap1);
5596         ctx = bmap1->ctx;
5597         obj = isl_vec_alloc(ctx, 1 + total);
5598         isl_seq_clr(obj->block.data, 1 + total);
5599         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
5600         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
5601         if (!obj)
5602                 goto error;
5603         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
5604                                         opt, NULL, NULL);
5605         isl_basic_map_free(bmap1);
5606         isl_vec_free(obj);
5607         return res;
5608 error:
5609         isl_basic_map_free(bmap1);
5610         isl_basic_map_free(bmap2);
5611         return isl_lp_error;
5612 }
5613
5614 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
5615  * for any common value of the parameters and dimensions preceding pos
5616  * in both basic sets, the values of dimension pos in bset1 are
5617  * smaller or larger than those in bset2.
5618  *
5619  * Returns
5620  *       1 if bset1 follows bset2
5621  *      -1 if bset1 precedes bset2
5622  *       0 if bset1 and bset2 are incomparable
5623  *      -2 if some error occurred.
5624  */
5625 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
5626         struct isl_basic_set *bset2, int pos)
5627 {
5628         isl_int opt;
5629         enum isl_lp_result res;
5630         int cmp;
5631
5632         isl_int_init(opt);
5633
5634         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5635
5636         if (res == isl_lp_empty)
5637                 cmp = 0;
5638         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5639                   res == isl_lp_unbounded)
5640                 cmp = 1;
5641         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5642                 cmp = -1;
5643         else
5644                 cmp = -2;
5645
5646         isl_int_clear(opt);
5647         return cmp;
5648 }
5649
5650 /* Given two basic sets bset1 and bset2, check whether
5651  * for any common value of the parameters and dimensions preceding pos
5652  * there is a value of dimension pos in bset1 that is larger
5653  * than a value of the same dimension in bset2.
5654  *
5655  * Return
5656  *       1 if there exists such a pair
5657  *       0 if there is no such pair, but there is a pair of equal values
5658  *      -1 otherwise
5659  *      -2 if some error occurred.
5660  */
5661 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
5662         __isl_keep isl_basic_set *bset2, int pos)
5663 {
5664         isl_int opt;
5665         enum isl_lp_result res;
5666         int cmp;
5667
5668         isl_int_init(opt);
5669
5670         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5671
5672         if (res == isl_lp_empty)
5673                 cmp = -1;
5674         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5675                   res == isl_lp_unbounded)
5676                 cmp = 1;
5677         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5678                 cmp = -1;
5679         else if (res == isl_lp_ok)
5680                 cmp = 0;
5681         else
5682                 cmp = -2;
5683
5684         isl_int_clear(opt);
5685         return cmp;
5686 }
5687
5688 /* Given two sets set1 and set2, check whether
5689  * for any common value of the parameters and dimensions preceding pos
5690  * there is a value of dimension pos in set1 that is larger
5691  * than a value of the same dimension in set2.
5692  *
5693  * Return
5694  *       1 if there exists such a pair
5695  *       0 if there is no such pair, but there is a pair of equal values
5696  *      -1 otherwise
5697  *      -2 if some error occurred.
5698  */
5699 int isl_set_follows_at(__isl_keep isl_set *set1,
5700         __isl_keep isl_set *set2, int pos)
5701 {
5702         int i, j;
5703         int follows = -1;
5704
5705         if (!set1 || !set2)
5706                 return -2;
5707
5708         for (i = 0; i < set1->n; ++i)
5709                 for (j = 0; j < set2->n; ++j) {
5710                         int f;
5711                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5712                         if (f == 1 || f == -2)
5713                                 return f;
5714                         if (f > follows)
5715                                 follows = f;
5716                 }
5717
5718         return follows;
5719 }
5720
5721 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5722         unsigned pos, isl_int *val)
5723 {
5724         int i;
5725         int d;
5726         unsigned total;
5727
5728         if (!bmap)
5729                 return -1;
5730         total = isl_basic_map_total_dim(bmap);
5731         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5732                 for (; d+1 > pos; --d)
5733                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5734                                 break;
5735                 if (d != pos)
5736                         continue;
5737                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5738                         return 0;
5739                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5740                         return 0;
5741                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5742                         return 0;
5743                 if (val)
5744                         isl_int_neg(*val, bmap->eq[i][0]);
5745                 return 1;
5746         }
5747         return 0;
5748 }
5749
5750 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5751         unsigned pos, isl_int *val)
5752 {
5753         int i;
5754         isl_int v;
5755         isl_int tmp;
5756         int fixed;
5757
5758         if (!map)
5759                 return -1;
5760         if (map->n == 0)
5761                 return 0;
5762         if (map->n == 1)
5763                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5764         isl_int_init(v);
5765         isl_int_init(tmp);
5766         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5767         for (i = 1; fixed == 1 && i < map->n; ++i) {
5768                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5769                 if (fixed == 1 && isl_int_ne(tmp, v))
5770                         fixed = 0;
5771         }
5772         if (val)
5773                 isl_int_set(*val, v);
5774         isl_int_clear(tmp);
5775         isl_int_clear(v);
5776         return fixed;
5777 }
5778
5779 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5780         unsigned pos, isl_int *val)
5781 {
5782         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5783                                                 pos, val);
5784 }
5785
5786 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5787         isl_int *val)
5788 {
5789         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5790 }
5791
5792 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5793         enum isl_dim_type type, unsigned pos, isl_int *val)
5794 {
5795         if (pos >= isl_basic_map_dim(bmap, type))
5796                 return -1;
5797         return isl_basic_map_fast_has_fixed_var(bmap,
5798                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
5799 }
5800
5801 int isl_map_fast_is_fixed(struct isl_map *map,
5802         enum isl_dim_type type, unsigned pos, isl_int *val)
5803 {
5804         if (pos >= isl_map_dim(map, type))
5805                 return -1;
5806         return isl_map_fast_has_fixed_var(map,
5807                 map_offset(map, type) - 1 + pos, val);
5808 }
5809
5810 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5811  * then return this fixed value in *val.
5812  */
5813 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
5814         isl_int *val)
5815 {
5816         return isl_basic_set_fast_has_fixed_var(bset,
5817                                         isl_basic_set_n_param(bset) + dim, val);
5818 }
5819
5820 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5821  * then return this fixed value in *val.
5822  */
5823 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
5824 {
5825         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
5826 }
5827
5828 /* Check if input variable in has fixed value and if so and if val is not NULL,
5829  * then return this fixed value in *val.
5830  */
5831 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
5832 {
5833         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
5834 }
5835
5836 /* Check if dimension dim has an (obvious) fixed lower bound and if so
5837  * and if val is not NULL, then return this lower bound in *val.
5838  */
5839 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
5840         unsigned dim, isl_int *val)
5841 {
5842         int i, i_eq = -1, i_ineq = -1;
5843         isl_int *c;
5844         unsigned total;
5845         unsigned nparam;
5846
5847         if (!bset)
5848                 return -1;
5849         total = isl_basic_set_total_dim(bset);
5850         nparam = isl_basic_set_n_param(bset);
5851         for (i = 0; i < bset->n_eq; ++i) {
5852                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
5853                         continue;
5854                 if (i_eq != -1)
5855                         return 0;
5856                 i_eq = i;
5857         }
5858         for (i = 0; i < bset->n_ineq; ++i) {
5859                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
5860                         continue;
5861                 if (i_eq != -1 || i_ineq != -1)
5862                         return 0;
5863                 i_ineq = i;
5864         }
5865         if (i_eq == -1 && i_ineq == -1)
5866                 return 0;
5867         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
5868         /* The coefficient should always be one due to normalization. */
5869         if (!isl_int_is_one(c[1+nparam+dim]))
5870                 return 0;
5871         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
5872                 return 0;
5873         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
5874                                         total - nparam - dim - 1) != -1)
5875                 return 0;
5876         if (val)
5877                 isl_int_neg(*val, c[0]);
5878         return 1;
5879 }
5880
5881 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
5882         unsigned dim, isl_int *val)
5883 {
5884         int i;
5885         isl_int v;
5886         isl_int tmp;
5887         int fixed;
5888
5889         if (!set)
5890                 return -1;
5891         if (set->n == 0)
5892                 return 0;
5893         if (set->n == 1)
5894                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5895                                                                 dim, val);
5896         isl_int_init(v);
5897         isl_int_init(tmp);
5898         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5899                                                                 dim, &v);
5900         for (i = 1; fixed == 1 && i < set->n; ++i) {
5901                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5902                                                                 dim, &tmp);
5903                 if (fixed == 1 && isl_int_ne(tmp, v))
5904                         fixed = 0;
5905         }
5906         if (val)
5907                 isl_int_set(*val, v);
5908         isl_int_clear(tmp);
5909         isl_int_clear(v);
5910         return fixed;
5911 }
5912
5913 struct constraint {
5914         unsigned        size;
5915         isl_int         *c;
5916 };
5917
5918 static int qsort_constraint_cmp(const void *p1, const void *p2)
5919 {
5920         const struct constraint *c1 = (const struct constraint *)p1;
5921         const struct constraint *c2 = (const struct constraint *)p2;
5922         unsigned size = isl_min(c1->size, c2->size);
5923         return isl_seq_cmp(c1->c, c2->c, size);
5924 }
5925
5926 static struct isl_basic_map *isl_basic_map_sort_constraints(
5927         struct isl_basic_map *bmap)
5928 {
5929         int i;
5930         struct constraint *c;
5931         unsigned total;
5932
5933         if (!bmap)
5934                 return NULL;
5935         total = isl_basic_map_total_dim(bmap);
5936         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5937         if (!c)
5938                 goto error;
5939         for (i = 0; i < bmap->n_ineq; ++i) {
5940                 c[i].size = total;
5941                 c[i].c = bmap->ineq[i];
5942         }
5943         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5944         for (i = 0; i < bmap->n_ineq; ++i)
5945                 bmap->ineq[i] = c[i].c;
5946         free(c);
5947         return bmap;
5948 error:
5949         isl_basic_map_free(bmap);
5950         return NULL;
5951 }
5952
5953 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5954 {
5955         if (!bmap)
5956                 return NULL;
5957         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5958                 return bmap;
5959         bmap = isl_basic_map_convex_hull(bmap);
5960         bmap = isl_basic_map_sort_constraints(bmap);
5961         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5962         return bmap;
5963 }
5964
5965 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5966 {
5967         return (struct isl_basic_set *)isl_basic_map_normalize(
5968                                                 (struct isl_basic_map *)bset);
5969 }
5970
5971 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5972         const struct isl_basic_map *bmap2)
5973 {
5974         int i, cmp;
5975         unsigned total;
5976
5977         if (bmap1 == bmap2)
5978                 return 0;
5979         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5980                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5981         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5982                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5983         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5984                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5985         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5986             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5987                 return 0;
5988         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5989                 return 1;
5990         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5991                 return -1;
5992         if (bmap1->n_eq != bmap2->n_eq)
5993                 return bmap1->n_eq - bmap2->n_eq;
5994         if (bmap1->n_ineq != bmap2->n_ineq)
5995                 return bmap1->n_ineq - bmap2->n_ineq;
5996         if (bmap1->n_div != bmap2->n_div)
5997                 return bmap1->n_div - bmap2->n_div;
5998         total = isl_basic_map_total_dim(bmap1);
5999         for (i = 0; i < bmap1->n_eq; ++i) {
6000                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
6001                 if (cmp)
6002                         return cmp;
6003         }
6004         for (i = 0; i < bmap1->n_ineq; ++i) {
6005                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
6006                 if (cmp)
6007                         return cmp;
6008         }
6009         for (i = 0; i < bmap1->n_div; ++i) {
6010                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
6011                 if (cmp)
6012                         return cmp;
6013         }
6014         return 0;
6015 }
6016
6017 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
6018         struct isl_basic_map *bmap2)
6019 {
6020         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
6021 }
6022
6023 static int qsort_bmap_cmp(const void *p1, const void *p2)
6024 {
6025         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
6026         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
6027
6028         return isl_basic_map_fast_cmp(bmap1, bmap2);
6029 }
6030
6031 /* We normalize in place, but if anything goes wrong we need
6032  * to return NULL, so we need to make sure we don't change the
6033  * meaning of any possible other copies of map.
6034  */
6035 struct isl_map *isl_map_normalize(struct isl_map *map)
6036 {
6037         int i, j;
6038         struct isl_basic_map *bmap;
6039
6040         if (!map)
6041                 return NULL;
6042         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
6043                 return map;
6044         for (i = 0; i < map->n; ++i) {
6045                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
6046                 if (!bmap)
6047                         goto error;
6048                 isl_basic_map_free(map->p[i]);
6049                 map->p[i] = bmap;
6050         }
6051         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
6052         ISL_F_SET(map, ISL_MAP_NORMALIZED);
6053         map = isl_map_remove_empty_parts(map);
6054         if (!map)
6055                 return NULL;
6056         for (i = map->n - 1; i >= 1; --i) {
6057                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
6058                         continue;
6059                 isl_basic_map_free(map->p[i-1]);
6060                 for (j = i; j < map->n; ++j)
6061                         map->p[j-1] = map->p[j];
6062                 map->n--;
6063         }
6064         return map;
6065 error:
6066         isl_map_free(map);
6067         return NULL;
6068
6069 }
6070
6071 struct isl_set *isl_set_normalize(struct isl_set *set)
6072 {
6073         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
6074 }
6075
6076 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
6077 {
6078         int i;
6079         int equal;
6080
6081         if (!map1 || !map2)
6082                 return -1;
6083
6084         if (map1 == map2)
6085                 return 1;
6086         if (!isl_dim_equal(map1->dim, map2->dim))
6087                 return 0;
6088
6089         map1 = isl_map_copy(map1);
6090         map2 = isl_map_copy(map2);
6091         map1 = isl_map_normalize(map1);
6092         map2 = isl_map_normalize(map2);
6093         if (!map1 || !map2)
6094                 goto error;
6095         equal = map1->n == map2->n;
6096         for (i = 0; equal && i < map1->n; ++i) {
6097                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
6098                 if (equal < 0)
6099                         goto error;
6100         }
6101         isl_map_free(map1);
6102         isl_map_free(map2);
6103         return equal;
6104 error:
6105         isl_map_free(map1);
6106         isl_map_free(map2);
6107         return -1;
6108 }
6109
6110 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
6111 {
6112         return isl_map_fast_is_equal((struct isl_map *)set1,
6113                                                 (struct isl_map *)set2);
6114 }
6115
6116 /* Return an interval that ranges from min to max (inclusive)
6117  */
6118 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
6119         isl_int min, isl_int max)
6120 {
6121         int k;
6122         struct isl_basic_set *bset = NULL;
6123
6124         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
6125         if (!bset)
6126                 goto error;
6127
6128         k = isl_basic_set_alloc_inequality(bset);
6129         if (k < 0)
6130                 goto error;
6131         isl_int_set_si(bset->ineq[k][1], 1);
6132         isl_int_neg(bset->ineq[k][0], min);
6133
6134         k = isl_basic_set_alloc_inequality(bset);
6135         if (k < 0)
6136                 goto error;
6137         isl_int_set_si(bset->ineq[k][1], -1);
6138         isl_int_set(bset->ineq[k][0], max);
6139
6140         return bset;
6141 error:
6142         isl_basic_set_free(bset);
6143         return NULL;
6144 }
6145
6146 /* Return the Cartesian product of the basic sets in list (in the given order).
6147  */
6148 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
6149 {
6150         int i;
6151         unsigned dim;
6152         unsigned nparam;
6153         unsigned extra;
6154         unsigned n_eq;
6155         unsigned n_ineq;
6156         struct isl_basic_set *product = NULL;
6157
6158         if (!list)
6159                 goto error;
6160         isl_assert(list->ctx, list->n > 0, goto error);
6161         isl_assert(list->ctx, list->p[0], goto error);
6162         nparam = isl_basic_set_n_param(list->p[0]);
6163         dim = isl_basic_set_n_dim(list->p[0]);
6164         extra = list->p[0]->n_div;
6165         n_eq = list->p[0]->n_eq;
6166         n_ineq = list->p[0]->n_ineq;
6167         for (i = 1; i < list->n; ++i) {
6168                 isl_assert(list->ctx, list->p[i], goto error);
6169                 isl_assert(list->ctx,
6170                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
6171                 dim += isl_basic_set_n_dim(list->p[i]);
6172                 extra += list->p[i]->n_div;
6173                 n_eq += list->p[i]->n_eq;
6174                 n_ineq += list->p[i]->n_ineq;
6175         }
6176         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
6177                                         n_eq, n_ineq);
6178         if (!product)
6179                 goto error;
6180         dim = 0;
6181         for (i = 0; i < list->n; ++i) {
6182                 isl_basic_set_add_constraints(product,
6183                                         isl_basic_set_copy(list->p[i]), dim);
6184                 dim += isl_basic_set_n_dim(list->p[i]);
6185         }
6186         isl_basic_set_list_free(list);
6187         return product;
6188 error:
6189         isl_basic_set_free(product);
6190         isl_basic_set_list_free(list);
6191         return NULL;
6192 }
6193
6194 struct isl_basic_map *isl_basic_map_product(
6195                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
6196 {
6197         struct isl_dim *dim_result = NULL;
6198         struct isl_basic_map *bmap;
6199         unsigned in1, in2, out1, out2, nparam, total, pos;
6200         struct isl_dim_map *dim_map1, *dim_map2;
6201
6202         if (!bmap1 || !bmap2)
6203                 goto error;
6204
6205         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
6206                                      bmap2->dim, isl_dim_param), goto error);
6207         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
6208                                                    isl_dim_copy(bmap2->dim));
6209
6210         in1 = isl_basic_map_n_in(bmap1);
6211         in2 = isl_basic_map_n_in(bmap2);
6212         out1 = isl_basic_map_n_out(bmap1);
6213         out2 = isl_basic_map_n_out(bmap2);
6214         nparam = isl_basic_map_n_param(bmap1);
6215
6216         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
6217         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
6218         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
6219         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
6220         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
6221         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
6222         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
6223         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
6224         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
6225         isl_dim_map_div(dim_map1, bmap1, pos += out2);
6226         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
6227
6228         bmap = isl_basic_map_alloc_dim(dim_result,
6229                         bmap1->n_div + bmap2->n_div,
6230                         bmap1->n_eq + bmap2->n_eq,
6231                         bmap1->n_ineq + bmap2->n_ineq);
6232         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
6233         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
6234         bmap = isl_basic_map_simplify(bmap);
6235         return isl_basic_map_finalize(bmap);
6236 error:
6237         isl_basic_map_free(bmap1);
6238         isl_basic_map_free(bmap2);
6239         return NULL;
6240 }
6241
6242 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
6243  */
6244 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
6245 {
6246         unsigned flags = 0;
6247         struct isl_map *result;
6248         int i, j;
6249
6250         if (!map1 || !map2)
6251                 goto error;
6252
6253         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
6254                                          map2->dim, isl_dim_param), goto error);
6255
6256         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
6257             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
6258                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
6259
6260         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
6261                                                    isl_dim_copy(map2->dim)),
6262                                 map1->n * map2->n, flags);
6263         if (!result)
6264                 goto error;
6265         for (i = 0; i < map1->n; ++i)
6266                 for (j = 0; j < map2->n; ++j) {
6267                         struct isl_basic_map *part;
6268                         part = isl_basic_map_product(
6269                                     isl_basic_map_copy(map1->p[i]),
6270                                     isl_basic_map_copy(map2->p[j]));
6271                         if (isl_basic_map_is_empty(part))
6272                                 isl_basic_map_free(part);
6273                         else
6274                                 result = isl_map_add_basic_map(result, part);
6275                         if (!result)
6276                                 goto error;
6277                 }
6278         isl_map_free(map1);
6279         isl_map_free(map2);
6280         return result;
6281 error:
6282         isl_map_free(map1);
6283         isl_map_free(map2);
6284         return NULL;
6285 }
6286
6287 /* Given two set A and B, construct its Cartesian product A x B.
6288  */
6289 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
6290 {
6291         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
6292                                                  (struct isl_map *)set2);
6293 }
6294
6295 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
6296 {
6297         int i;
6298         uint32_t hash = isl_hash_init();
6299         unsigned total;
6300
6301         if (!bset)
6302                 return 0;
6303         bset = isl_basic_set_copy(bset);
6304         bset = isl_basic_set_normalize(bset);
6305         if (!bset)
6306                 return 0;
6307         total = isl_basic_set_total_dim(bset);
6308         isl_hash_byte(hash, bset->n_eq & 0xFF);
6309         for (i = 0; i < bset->n_eq; ++i) {
6310                 uint32_t c_hash;
6311                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
6312                 isl_hash_hash(hash, c_hash);
6313         }
6314         isl_hash_byte(hash, bset->n_ineq & 0xFF);
6315         for (i = 0; i < bset->n_ineq; ++i) {
6316                 uint32_t c_hash;
6317                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
6318                 isl_hash_hash(hash, c_hash);
6319         }
6320         isl_hash_byte(hash, bset->n_div & 0xFF);
6321         for (i = 0; i < bset->n_div; ++i) {
6322                 uint32_t c_hash;
6323                 if (isl_int_is_zero(bset->div[i][0]))
6324                         continue;
6325                 isl_hash_byte(hash, i & 0xFF);
6326                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
6327                 isl_hash_hash(hash, c_hash);
6328         }
6329         isl_basic_set_free(bset);
6330         return hash;
6331 }
6332
6333 uint32_t isl_set_get_hash(struct isl_set *set)
6334 {
6335         int i;
6336         uint32_t hash;
6337
6338         if (!set)
6339                 return 0;
6340         set = isl_set_copy(set);
6341         set = isl_set_normalize(set);
6342         if (!set)
6343                 return 0;
6344
6345         hash = isl_hash_init();
6346         for (i = 0; i < set->n; ++i) {
6347                 uint32_t bset_hash;
6348                 bset_hash = isl_basic_set_get_hash(set->p[i]);
6349                 isl_hash_hash(hash, bset_hash);
6350         }
6351
6352         isl_set_free(set);
6353
6354         return hash;
6355 }
6356
6357 /* Check if the value for dimension dim is completely determined
6358  * by the values of the other parameters and variables.
6359  * That is, check if dimension dim is involved in an equality.
6360  */
6361 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
6362 {
6363         int i;
6364         unsigned nparam;
6365
6366         if (!bset)
6367                 return -1;
6368         nparam = isl_basic_set_n_param(bset);
6369         for (i = 0; i < bset->n_eq; ++i)
6370                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
6371                         return 1;
6372         return 0;
6373 }
6374
6375 /* Check if the value for dimension dim is completely determined
6376  * by the values of the other parameters and variables.
6377  * That is, check if dimension dim is involved in an equality
6378  * for each of the subsets.
6379  */
6380 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
6381 {
6382         int i;
6383
6384         if (!set)
6385                 return -1;
6386         for (i = 0; i < set->n; ++i) {
6387                 int unique;
6388                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
6389                 if (unique != 1)
6390                         return unique;
6391         }
6392         return 1;
6393 }
6394
6395 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
6396         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
6397 {
6398         int i;
6399
6400         if (!map)
6401                 return -1;
6402
6403         for (i = 0; i < map->n; ++i)
6404                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
6405                         return -1;
6406
6407         return 0;
6408 }
6409
6410 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
6411         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
6412 {
6413         int i;
6414
6415         if (!set)
6416                 return -1;
6417
6418         for (i = 0; i < set->n; ++i)
6419                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
6420                         return -1;
6421
6422         return 0;
6423 }
6424
6425 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
6426 {
6427         struct isl_dim *dim;
6428
6429         if (!bset)
6430                 return NULL;
6431
6432         if (bset->n_div == 0)
6433                 return bset;
6434
6435         bset = isl_basic_set_cow(bset);
6436         if (!bset)
6437                 return NULL;
6438
6439         dim = isl_basic_set_get_dim(bset);
6440         dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
6441         if (!dim)
6442                 goto error;
6443         isl_dim_free(bset->dim);
6444         bset->dim = dim;
6445         bset->n_div = 0;
6446
6447         bset = isl_basic_set_finalize(bset);
6448
6449         return bset;
6450 error:
6451         isl_basic_set_free(bset);
6452         return NULL;
6453 }
6454
6455 __isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
6456 {
6457         int i;
6458         struct isl_dim *dim;
6459         unsigned n_div;
6460
6461         set = isl_set_align_divs(set);
6462
6463         if (!set)
6464                 return NULL;
6465         if (set->n == 0 || set->p[0]->n_div == 0)
6466                 return set;
6467
6468         set = isl_set_cow(set);
6469         if (!set)
6470                 return NULL;
6471
6472         n_div = set->p[0]->n_div;
6473         dim = isl_set_get_dim(set);
6474         dim = isl_dim_add(dim, isl_dim_set, n_div);
6475         if (!dim)
6476                 goto error;
6477         isl_dim_free(set->dim);
6478         set->dim = dim;
6479
6480         for (i = 0; i < set->n; ++i) {
6481                 set->p[i] = isl_basic_set_lift(set->p[i]);
6482                 if (!set->p[i])
6483                         goto error;
6484         }
6485
6486         return set;
6487 error:
6488         isl_set_free(set);
6489         return NULL;
6490 }
6491
6492 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
6493 {
6494         struct isl_dim *dim;
6495         struct isl_basic_map *bmap;
6496         unsigned n_set;
6497         unsigned n_div;
6498         unsigned n_param;
6499         unsigned total;
6500         int i, k, l;
6501
6502         set = isl_set_align_divs(set);
6503
6504         if (!set)
6505                 return NULL;
6506
6507         dim = isl_set_get_dim(set);
6508         if (set->n == 0 || set->p[0]->n_div == 0) {
6509                 isl_set_free(set);
6510                 return isl_map_identity(dim);
6511         }
6512
6513         n_div = set->p[0]->n_div;
6514         dim = isl_dim_map(dim);
6515         n_param = isl_dim_size(dim, isl_dim_param);
6516         n_set = isl_dim_size(dim, isl_dim_in);
6517         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
6518         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
6519         for (i = 0; i < n_set; ++i)
6520                 bmap = var_equal(bmap, i);
6521
6522         total = n_param + n_set + n_set + n_div;
6523         for (i = 0; i < n_div; ++i) {
6524                 k = isl_basic_map_alloc_inequality(bmap);
6525                 if (k < 0)
6526                         goto error;
6527                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
6528                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
6529                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
6530                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
6531                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
6532                             set->p[0]->div[i][0]);
6533
6534                 l = isl_basic_map_alloc_inequality(bmap);
6535                 if (l < 0)
6536                         goto error;
6537                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
6538                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
6539                             set->p[0]->div[i][0]);
6540                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
6541         }
6542
6543         isl_set_free(set);
6544         return isl_map_from_basic_map(bmap);
6545 error:
6546         isl_set_free(set);
6547         isl_basic_map_free(bmap);
6548         return NULL;
6549 }
6550
6551 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
6552 {
6553         unsigned dim;
6554         int size = 0;
6555
6556         if (!bset)
6557                 return -1;
6558
6559         dim = isl_basic_set_total_dim(bset);
6560         size += bset->n_eq * (1 + dim);
6561         size += bset->n_ineq * (1 + dim);
6562         size += bset->n_div * (2 + dim);
6563
6564         return size;
6565 }
6566
6567 int isl_set_size(__isl_keep isl_set *set)
6568 {
6569         int i;
6570         int size = 0;
6571
6572         if (!set)
6573                 return -1;
6574
6575         for (i = 0; i < set->n; ++i)
6576                 size += isl_basic_set_size(set->p[i]);
6577
6578         return size;
6579 }
6580
6581 int isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
6582         enum isl_dim_type type, unsigned pos)
6583 {
6584         int i;
6585         int lower, upper;
6586
6587         if (!bmap)
6588                 return -1;
6589
6590         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
6591
6592         pos += isl_basic_map_offset(bmap, type);
6593
6594         for (i = 0; i < bmap->n_eq; ++i)
6595                 if (!isl_int_is_zero(bmap->eq[i][pos]))
6596                         return 1;
6597
6598         lower = upper = 0;
6599         for (i = 0; i < bmap->n_ineq; ++i) {
6600                 int sgn = isl_int_sgn(bmap->ineq[i][pos]);
6601                 if (sgn > 0)
6602                         lower = 1;
6603                 if (sgn < 0)
6604                         upper = 1;
6605         }
6606
6607         return lower && upper;
6608 }
6609
6610 int isl_map_dim_is_bounded(__isl_keep isl_map *map,
6611         enum isl_dim_type type, unsigned pos)
6612 {
6613         int i;
6614
6615         if (!map)
6616                 return -1;
6617
6618         for (i = 0; i < map->n; ++i) {
6619                 int bounded;
6620                 bounded = isl_basic_map_dim_is_bounded(map->p[i], type, pos);
6621                 if (bounded < 0 || !bounded)
6622                         return bounded;
6623         }
6624
6625         return 1;
6626 }
6627
6628 /* Return 1 if the specified dim is involved in both an upper bound
6629  * and a lower bound.
6630  */
6631 int isl_set_dim_is_bounded(__isl_keep isl_set *set,
6632         enum isl_dim_type type, unsigned pos)
6633 {
6634         return isl_map_dim_is_bounded((isl_map *)set, type, pos);
6635 }
6636
6637 /* For each of the "n" variables starting at "first", determine
6638  * the sign of the variable and put the results in the first "n"
6639  * elements of the array "signs".
6640  * Sign
6641  *      1 means that the variable is non-negative
6642  *      -1 means that the variable is non-positive
6643  *      0 means the variable attains both positive and negative values.
6644  */
6645 int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
6646         unsigned first, unsigned n, int *signs)
6647 {
6648         isl_vec *bound = NULL;
6649         struct isl_tab *tab = NULL;
6650         struct isl_tab_undo *snap;
6651         int i;
6652
6653         if (!bset || !signs)
6654                 return -1;
6655
6656         bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset));
6657         tab = isl_tab_from_basic_set(bset);
6658         if (!bound || !tab)
6659                 goto error;
6660
6661         isl_seq_clr(bound->el, bound->size);
6662         isl_int_set_si(bound->el[0], -1);
6663
6664         snap = isl_tab_snap(tab);
6665         for (i = 0; i < n; ++i) {
6666                 int empty;
6667
6668                 isl_int_set_si(bound->el[1 + first + i], -1);
6669                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6670                         goto error;
6671                 empty = tab->empty;
6672                 isl_int_set_si(bound->el[1 + first + i], 0);
6673                 if (isl_tab_rollback(tab, snap) < 0)
6674                         goto error;
6675
6676                 if (empty) {
6677                         signs[i] = 1;
6678                         continue;
6679                 }
6680
6681                 isl_int_set_si(bound->el[1 + first + i], 1);
6682                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6683                         goto error;
6684                 empty = tab->empty;
6685                 isl_int_set_si(bound->el[1 + first + i], 0);
6686                 if (isl_tab_rollback(tab, snap) < 0)
6687                         goto error;
6688
6689                 signs[i] = empty ? -1 : 0;
6690         }
6691
6692         isl_tab_free(tab);
6693         isl_vec_free(bound);
6694         return 0;
6695 error:
6696         isl_tab_free(tab);
6697         isl_vec_free(bound);
6698         return -1;
6699 }
6700
6701 int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
6702         enum isl_dim_type type, unsigned first, unsigned n, int *signs)
6703 {
6704         if (!bset || !signs)
6705                 return -1;
6706         isl_assert(bset->ctx, first + n <= isl_basic_set_dim(bset, type),
6707                 return -1);
6708
6709         first += pos(bset->dim, type) - 1;
6710         return isl_basic_set_vars_get_sign(bset, first, n, signs);
6711 }
6712
6713 /* Check if the given map is single-valued.
6714  * We simply compute
6715  *
6716  *      M \circ M^-1
6717  *
6718  * and check if the result is a subset of the identity mapping.
6719  */
6720 int isl_map_is_single_valued(__isl_keep isl_map *map)
6721 {
6722         isl_map *test;
6723         isl_map *id;
6724         int sv;
6725
6726         test = isl_map_reverse(isl_map_copy(map));
6727         test = isl_map_apply_range(test, isl_map_copy(map));
6728
6729         id = isl_map_identity(isl_dim_range(isl_map_get_dim(map)));
6730
6731         sv = isl_map_is_subset(test, id);
6732
6733         isl_map_free(test);
6734         isl_map_free(id);
6735
6736         return sv;
6737 }