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