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 #include <isl_dim_private.h>
  30
  31 /* Maps dst positions to src positions */
  32 struct isl_dim_map {
  33         unsigned len;
  34         int pos[1];
  35 };
  36
  37 static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
  38 {
  39         int i;
  40         struct isl_dim_map *dim_map;
  41         dim_map = isl_alloc(ctx, struct isl_dim_map,
  42                                 sizeof(struct isl_dim_map) + len * sizeof(int));
  43         if (!dim_map)
  44                 return NULL;
  45         dim_map->len = 1 + len;
  46         dim_map->pos[0] = 0;
  47         for (i = 0; i < len; ++i)
  48                 dim_map->pos[1 + i] = -1;
  49         return dim_map;
  50 }
  51
  52 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
  53 {
  54         switch (type) {
  55         case isl_dim_param:     return dim->nparam;
  56         case isl_dim_in:        return dim->n_in;
  57         case isl_dim_out:       return dim->n_out;
  58         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
  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         }
  69 }
  70
  71 static void isl_dim_map_dim_range(struct isl_dim_map *dim_map,
  72         struct isl_dim *dim, enum isl_dim_type type,
  73         unsigned first, unsigned n, unsigned dst_pos)
  74 {
  75         int i;
  76         unsigned src_pos;
  77
  78         if (!dim_map || !dim)
  79                 return;
  80
  81         src_pos = pos(dim, type);
  82         for (i = 0; i < n; ++i)
  83                 dim_map->pos[1 + dst_pos + i] = src_pos + first + i;
  84 }
  85
  86 static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
  87                 enum isl_dim_type type, unsigned dst_pos)
  88 {
  89         isl_dim_map_dim_range(dim_map, dim, type, 0, n(dim, type), dst_pos);
  90 }
  91
  92 static void isl_dim_map_div(struct isl_dim_map *dim_map,
  93                 struct isl_basic_map *bmap, unsigned dst_pos)
  94 {
  95         int i;
  96         unsigned src_pos;
  97
  98         if (!dim_map || !bmap)
  99                 return;
 100
 101         src_pos = 1 + isl_dim_total(bmap->dim);
 102         for (i = 0; i < bmap->n_div; ++i)
 103                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
 104 }
 105
 106 static void isl_dim_map_dump(struct isl_dim_map *dim_map)
 107 {
 108         int i;
 109
 110         for (i = 0; i < dim_map->len; ++i)
 111                 fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
 112         fprintf(stderr, "\n");
 113 }
 114
 115 unsigned isl_basic_map_dim(const struct isl_basic_map *bmap,
 116                                 enum isl_dim_type type)
 117 {
 118         switch (type) {
 119         case isl_dim_param:
 120         case isl_dim_in:
 121         case isl_dim_out:       return isl_dim_size(bmap->dim, type);
 122         case isl_dim_div:       return bmap->n_div;
 123         case isl_dim_all:       return isl_basic_map_total_dim(bmap);
 124         }
 125 }
 126
 127 unsigned isl_map_dim(const struct isl_map *map, enum isl_dim_type type)
 128 {
 129         return map ? n(map->dim, type) : 0;
 130 }
 131
 132 unsigned isl_set_dim(const struct isl_set *set, enum isl_dim_type type)
 133 {
 134         return set ? n(set->dim, type) : 0;
 135 }
 136
 137 unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
 138                                         enum isl_dim_type type)
 139 {
 140         struct isl_dim *dim = bmap->dim;
 141         switch (type) {
 142         case isl_dim_param:     return 1;
 143         case isl_dim_in:        return 1 + dim->nparam;
 144         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 145         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 146         }
 147 }
 148
 149 static unsigned map_offset(struct isl_map *map, enum isl_dim_type type)
 150 {
 151         return pos(map->dim, type);
 152 }
 153
 154 unsigned isl_basic_set_dim(const struct isl_basic_set *bset,
 155                                 enum isl_dim_type type)
 156 {
 157         return isl_basic_map_dim((const struct isl_basic_map*)bset, type);
 158 }
 159
 160 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
 161 {
 162         return bset->dim->n_out;
 163 }
 164
 165 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
 166 {
 167         return bset->dim->nparam;
 168 }
 169
 170 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 171 {
 172         return isl_dim_total(bset->dim) + bset->n_div;
 173 }
 174
 175 unsigned isl_set_n_dim(const struct isl_set *set)
 176 {
 177         return set->dim->n_out;
 178 }
 179
 180 unsigned isl_set_n_param(const struct isl_set *set)
 181 {
 182         return set->dim->nparam;
 183 }
 184
 185 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
 186 {
 187         return bmap->dim->n_in;
 188 }
 189
 190 unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
 191 {
 192         return bmap->dim->n_out;
 193 }
 194
 195 unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
 196 {
 197         return bmap->dim->nparam;
 198 }
 199
 200 unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
 201 {
 202         return bmap->n_div;
 203 }
 204
 205 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
 206 {
 207         return isl_dim_total(bmap->dim) + bmap->n_div;
 208 }
 209
 210 unsigned isl_map_n_in(const struct isl_map *map)
 211 {
 212         return map->dim->n_in;
 213 }
 214
 215 unsigned isl_map_n_out(const struct isl_map *map)
 216 {
 217         return map->dim->n_out;
 218 }
 219
 220 unsigned isl_map_n_param(const struct isl_map *map)
 221 {
 222         return map->dim->nparam;
 223 }
 224
 225 int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
 226 {
 227         return map->dim->n_in == set->dim->n_out &&
 228                map->dim->nparam == set->dim->nparam;
 229 }
 230
 231 int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
 232                 struct isl_basic_set *bset)
 233 {
 234         return bmap->dim->n_in == bset->dim->n_out &&
 235                bmap->dim->nparam == bset->dim->nparam;
 236 }
 237
 238 int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
 239                 struct isl_basic_set *bset)
 240 {
 241         return bmap->dim->n_out == bset->dim->n_out &&
 242                bmap->dim->nparam == bset->dim->nparam;
 243 }
 244
 245 struct isl_dim *isl_basic_map_get_dim(struct isl_basic_map *bmap)
 246 {
 247         if (!bmap)
 248                 return NULL;
 249         return isl_dim_copy(bmap->dim);
 250 }
 251
 252 struct isl_dim *isl_basic_set_get_dim(struct isl_basic_set *bset)
 253 {
 254         if (!bset)
 255                 return NULL;
 256         return isl_dim_copy(bset->dim);
 257 }
 258
 259 struct isl_dim *isl_map_get_dim(struct isl_map *map)
 260 {
 261         if (!map)
 262                 return NULL;
 263         return isl_dim_copy(map->dim);
 264 }
 265
 266 struct isl_dim *isl_set_get_dim(struct isl_set *set)
 267 {
 268         if (!set)
 269                 return NULL;
 270         return isl_dim_copy(set->dim);
 271 }
 272
 273 static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 274                 struct isl_basic_map *bmap, unsigned extra,
 275                 unsigned n_eq, unsigned n_ineq)
 276 {
 277         int i;
 278         size_t row_size = 1 + isl_dim_total(bmap->dim) + extra;
 279
 280         bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
 281         if (isl_blk_is_error(bmap->block)) {
 282                 free(bmap);
 283                 return NULL;
 284         }
 285
 286         bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
 287         if (!bmap->ineq) {
 288                 isl_blk_free(ctx, bmap->block);
 289                 free(bmap);
 290                 return NULL;
 291         }
 292
 293         if (extra == 0) {
 294                 bmap->block2 = isl_blk_empty();
 295                 bmap->div = NULL;
 296         } else {
 297                 bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
 298                 if (isl_blk_is_error(bmap->block2)) {
 299                         free(bmap->ineq);
 300                         isl_blk_free(ctx, bmap->block);
 301                         free(bmap);
 302                         return NULL;
 303                 }
 304
 305                 bmap->div = isl_alloc_array(ctx, isl_int *, extra);
 306                 if (!bmap->div) {
 307                         isl_blk_free(ctx, bmap->block2);
 308                         free(bmap->ineq);
 309                         isl_blk_free(ctx, bmap->block);
 310                         free(bmap);
 311                         return NULL;
 312                 }
 313         }
 314
 315         for (i = 0; i < n_ineq + n_eq; ++i)
 316                 bmap->ineq[i] = bmap->block.data + i * row_size;
 317
 318         for (i = 0; i < extra; ++i)
 319                 bmap->div[i] = bmap->block2.data + i * (1 + row_size);
 320
 321         bmap->ctx = ctx;
 322         isl_ctx_ref(ctx);
 323         bmap->ref = 1;
 324         bmap->flags = 0;
 325         bmap->c_size = n_eq + n_ineq;
 326         bmap->eq = bmap->ineq + n_ineq;
 327         bmap->extra = extra;
 328         bmap->n_eq = 0;
 329         bmap->n_ineq = 0;
 330         bmap->n_div = 0;
 331         bmap->sample = NULL;
 332
 333         return bmap;
 334 error:
 335         isl_basic_map_free(bmap);
 336         return NULL;
 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                 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         map1->p[0] = isl_basic_map_cow(map1->p[0]);
1887         if (map2->p[0]->n_eq == 1)
1888                 map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
1889         else
1890                 map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
1891                                                         map2->p[0]->ineq[0]);
1892
1893         map1->p[0] = isl_basic_map_simplify(map1->p[0]);
1894         map1->p[0] = isl_basic_map_finalize(map1->p[0]);
1895         if (!map1->p[0])
1896                 goto error;
1897
1898         if (isl_basic_map_fast_is_empty(map1->p[0])) {
1899                 isl_basic_map_free(map1->p[0]);
1900                 map1->n = 0;
1901         }
1902
1903         isl_map_free(map2);
1904
1905         return map1;
1906 error:
1907         isl_map_free(map1);
1908         isl_map_free(map2);
1909         return NULL;
1910 }
1911
1912 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
1913 {
1914         unsigned flags = 0;
1915         struct isl_map *result;
1916         int i, j;
1917
1918         if (!map1 || !map2)
1919                 goto error;
1920
1921         if (map1->n == 1 && map2->n == 1 &&
1922             map1->p[0]->n_div == 0 && map2->p[0]->n_div == 0 &&
1923             isl_dim_equal(map1->dim, map2->dim) &&
1924             (map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 ||
1925              map2->p[0]->n_eq + map2->p[0]->n_ineq == 1))
1926                 return map_intersect_add_constraint(map1, map2);
1927         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
1928                                          map2->dim, isl_dim_param), goto error);
1929         if (isl_dim_total(map1->dim) ==
1930                                 isl_dim_size(map1->dim, isl_dim_param) &&
1931             isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1932                 return isl_map_intersect(map2, map1);
1933
1934         if (isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1935                 isl_assert(map1->ctx,
1936                             isl_dim_equal(map1->dim, map2->dim), goto error);
1937
1938         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
1939             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
1940                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
1941
1942         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
1943                                 map1->n * map2->n, flags);
1944         if (!result)
1945                 goto error;
1946         for (i = 0; i < map1->n; ++i)
1947                 for (j = 0; j < map2->n; ++j) {
1948                         struct isl_basic_map *part;
1949                         part = isl_basic_map_intersect(
1950                                     isl_basic_map_copy(map1->p[i]),
1951                                     isl_basic_map_copy(map2->p[j]));
1952                         if (isl_basic_map_is_empty(part))
1953                                 isl_basic_map_free(part);
1954                         else
1955                                 result = isl_map_add_basic_map(result, part);
1956                         if (!result)
1957                                 goto error;
1958                 }
1959         isl_map_free(map1);
1960         isl_map_free(map2);
1961         return result;
1962 error:
1963         isl_map_free(map1);
1964         isl_map_free(map2);
1965         return NULL;
1966 }
1967
1968 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
1969 {
1970         return (struct isl_set *)
1971                 isl_map_intersect((struct isl_map *)set1,
1972                                   (struct isl_map *)set2);
1973 }
1974
1975 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
1976 {
1977         struct isl_dim *dim;
1978         struct isl_basic_set *bset;
1979         unsigned in;
1980
1981         if (!bmap)
1982                 return NULL;
1983         bmap = isl_basic_map_cow(bmap);
1984         if (!bmap)
1985                 return NULL;
1986         dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
1987         in = isl_basic_map_n_in(bmap);
1988         bset = isl_basic_set_from_basic_map(bmap);
1989         bset = isl_basic_set_swap_vars(bset, in);
1990         return isl_basic_map_from_basic_set(bset, dim);
1991 }
1992
1993 __isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
1994                 enum isl_dim_type type, unsigned n)
1995 {
1996         struct isl_dim *res_dim;
1997         struct isl_basic_map *res;
1998         struct isl_dim_map *dim_map;
1999         unsigned total, pos;
2000
2001         if (n == 0)
2002                 return bmap;
2003
2004         if (!bmap)
2005                 return NULL;
2006
2007         res_dim = isl_dim_add(isl_basic_map_get_dim(bmap), type, n);
2008
2009         total = isl_basic_map_total_dim(bmap) + n;
2010         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2011         pos = 0;
2012         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos);
2013         pos += isl_dim_size(res_dim, isl_dim_param);
2014         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos);
2015         pos += isl_dim_size(res_dim, isl_dim_in);
2016         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos);
2017         pos += isl_dim_size(res_dim, isl_dim_out);
2018         isl_dim_map_div(dim_map, bmap, pos);
2019
2020         res = isl_basic_map_alloc_dim(res_dim,
2021                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2022         res = add_constraints_dim_map(res, bmap, dim_map);
2023         res = isl_basic_map_simplify(res);
2024         return isl_basic_map_finalize(res);
2025 }
2026
2027 __isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset,
2028                 enum isl_dim_type type, unsigned n)
2029 {
2030         if (!bset)
2031                 return NULL;
2032         isl_assert(bset->ctx, type != isl_dim_in, goto error);
2033         return (isl_basic_set *)isl_basic_map_add((isl_basic_map *)bset, type, n);
2034 error:
2035         isl_basic_set_free(bset);
2036         return NULL;
2037 }
2038
2039 __isl_give isl_map *isl_map_add(__isl_take isl_map *map,
2040                 enum isl_dim_type type, unsigned n)
2041 {
2042         int i;
2043
2044         if (n == 0)
2045                 return map;
2046
2047         map = isl_map_cow(map);
2048         if (!map)
2049                 return NULL;
2050
2051         map->dim = isl_dim_add(map->dim, type, n);
2052         if (!map->dim)
2053                 goto error;
2054
2055         for (i = 0; i < map->n; ++i) {
2056                 map->p[i] = isl_basic_map_add(map->p[i], type, n);
2057                 if (!map->p[i])
2058                         goto error;
2059         }
2060
2061         return map;
2062 error:
2063         isl_map_free(map);
2064         return NULL;
2065 }
2066
2067 __isl_give isl_set *isl_set_add(__isl_take isl_set *set,
2068                 enum isl_dim_type type, unsigned n)
2069 {
2070         if (!set)
2071                 return NULL;
2072         isl_assert(set->ctx, type != isl_dim_in, goto error);
2073         return (isl_set *)isl_map_add((isl_map *)set, type, n);
2074 error:
2075         isl_set_free(set);
2076         return NULL;
2077 }
2078
2079 __isl_give isl_basic_map *isl_basic_map_move(__isl_take isl_basic_map *bmap,
2080         enum isl_dim_type dst_type, unsigned dst_pos,
2081         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2082 {
2083         int i;
2084
2085         if (!bmap)
2086                 return NULL;
2087         if (n == 0)
2088                 return bmap;
2089
2090         isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type),
2091                 goto error);
2092
2093         /* just the simple case for now */
2094         isl_assert(bmap->ctx,
2095             pos(bmap->dim, dst_type) + dst_pos ==
2096             pos(bmap->dim, src_type) + src_pos + ((src_type < dst_type) ? n : 0),
2097             goto error);
2098
2099         if (dst_type == src_type)
2100                 return bmap;
2101
2102         bmap = isl_basic_map_cow(bmap);
2103         if (!bmap)
2104                 return NULL;
2105
2106         bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos, src_type, src_pos, n);
2107         if (!bmap->dim)
2108                 goto error;
2109
2110         return bmap;
2111 error:
2112         isl_basic_map_free(bmap);
2113         return NULL;
2114 }
2115
2116 __isl_give isl_set *isl_set_move(__isl_take isl_set *set,
2117         enum isl_dim_type dst_type, unsigned dst_pos,
2118         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2119 {
2120         if (!set)
2121                 return NULL;
2122         isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
2123         return (isl_set *)isl_map_move((isl_map *)set, dst_type, dst_pos,
2124                                         src_type, src_pos, n);
2125 error:
2126         isl_set_free(set);
2127         return NULL;
2128 }
2129
2130 __isl_give isl_map *isl_map_move(__isl_take isl_map *map,
2131         enum isl_dim_type dst_type, unsigned dst_pos,
2132         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2133 {
2134         int i;
2135
2136         if (!map)
2137                 return NULL;
2138         if (n == 0)
2139                 return map;
2140
2141         isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type),
2142                 goto error);
2143
2144         /* just the simple case for now */
2145         isl_assert(map->ctx,
2146             map_offset(map, dst_type) + dst_pos ==
2147             map_offset(map, src_type) + src_pos + ((src_type < dst_type) ? n : 0),
2148             goto error);
2149
2150         if (dst_type == src_type)
2151                 return map;
2152
2153         map = isl_map_cow(map);
2154         if (!map)
2155                 return NULL;
2156
2157         map->dim = isl_dim_move(map->dim, dst_type, dst_pos, src_type, src_pos, n);
2158         if (!map->dim)
2159                 goto error;
2160
2161         for (i = 0; i < map->n; ++i) {
2162                 map->p[i] = isl_basic_map_move(map->p[i], dst_type, dst_pos,
2163                                                 src_type, src_pos, n);
2164                 if (!map->p[i])
2165                         goto error;
2166         }
2167
2168         return map;
2169 error:
2170         isl_map_free(map);
2171         return NULL;
2172 }
2173
2174 /* Move the specified dimensions to the last columns right before
2175  * the divs.  Don't change the dimension specification of bmap.
2176  * That's the responsibility of the caller.
2177  */
2178 static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
2179         enum isl_dim_type type, unsigned first, unsigned n)
2180 {
2181         struct isl_dim_map *dim_map;
2182         struct isl_basic_map *res;
2183         enum isl_dim_type t;
2184         unsigned total, off;
2185
2186         if (!bmap)
2187                 return NULL;
2188         if (pos(bmap->dim, type) + first + n == 1 + isl_dim_total(bmap->dim))
2189                 return bmap;
2190
2191         total = isl_basic_map_total_dim(bmap);
2192         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2193
2194         off = 0;
2195         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2196                 unsigned size = isl_dim_size(bmap->dim, t);
2197                 if (t == type) {
2198                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2199                                             0, first, off);
2200                         off += first;
2201                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2202                                             first, n, total - bmap->n_div - n);
2203                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2204                                             first + n, size - (first + n), off);
2205                         off += size - (first + n);
2206                 } else {
2207                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2208                         off += size;
2209                 }
2210         }
2211         isl_dim_map_div(dim_map, bmap, off + n);
2212
2213         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2214                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2215         res = add_constraints_dim_map(res, bmap, dim_map);
2216         return res;
2217 }
2218
2219 /* Turn the n dimensions of type type, starting at first
2220  * into existentially quantified variables.
2221  */
2222 __isl_give isl_basic_map *isl_basic_map_project_out(
2223                 __isl_take isl_basic_map *bmap,
2224                 enum isl_dim_type type, unsigned first, unsigned n)
2225 {
2226         int i;
2227         size_t row_size;
2228         isl_int **new_div;
2229         isl_int *old;
2230
2231         if (n == 0)
2232                 return bmap;
2233
2234         if (!bmap)
2235                 return NULL;
2236
2237         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
2238                 return isl_basic_map_remove(bmap, type, first, n);
2239
2240         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
2241                         goto error);
2242
2243         bmap = move_last(bmap, type, first, n);
2244         bmap = isl_basic_map_cow(bmap);
2245
2246         row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra;
2247         old = bmap->block2.data;
2248         bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
2249                                         (bmap->extra + n) * (1 + row_size));
2250         if (!bmap->block2.data)
2251                 goto error;
2252         new_div = isl_alloc_array(ctx, isl_int *, bmap->extra + n);
2253         if (!new_div)
2254                 goto error;
2255         for (i = 0; i < n; ++i) {
2256                 new_div[i] = bmap->block2.data +
2257                                 (bmap->extra + i) * (1 + row_size);
2258                 isl_seq_clr(new_div[i], 1 + row_size);
2259         }
2260         for (i = 0; i < bmap->extra; ++i)
2261                 new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
2262         free(bmap->div);
2263         bmap->div = new_div;
2264         bmap->n_div += n;
2265         bmap->extra += n;
2266
2267         bmap->dim = isl_dim_drop(bmap->dim, type, first, n);
2268         if (!bmap->dim)
2269                 goto error;
2270         bmap = isl_basic_map_simplify(bmap);
2271         bmap = isl_basic_map_drop_redundant_divs(bmap);
2272         return isl_basic_map_finalize(bmap);
2273 error:
2274         isl_basic_map_free(bmap);
2275         return NULL;
2276 }
2277
2278 /* Turn the n dimensions of type type, starting at first
2279  * into existentially quantified variables.
2280  */
2281 struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
2282                 enum isl_dim_type type, unsigned first, unsigned n)
2283 {
2284         return (isl_basic_set *)isl_basic_map_project_out(
2285                         (isl_basic_map *)bset, type, first, n);
2286 }
2287
2288 /* Turn the n dimensions of type type, starting at first
2289  * into existentially quantified variables.
2290  */
2291 __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
2292                 enum isl_dim_type type, unsigned first, unsigned n)
2293 {
2294         int i;
2295
2296         if (!map)
2297                 return NULL;
2298
2299         if (n == 0)
2300                 return map;
2301
2302         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
2303
2304         map = isl_map_cow(map);
2305         if (!map)
2306                 return NULL;
2307
2308         map->dim = isl_dim_drop(map->dim, type, first, n);
2309         if (!map->dim)
2310                 goto error;
2311
2312         for (i = 0; i < map->n; ++i) {
2313                 map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
2314                 if (!map->p[i])
2315                         goto error;
2316         }
2317
2318         return map;
2319 error:
2320         isl_map_free(map);
2321         return map;
2322 }
2323
2324 /* Turn the n dimensions of type type, starting at first
2325  * into existentially quantified variables.
2326  */
2327 __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
2328                 enum isl_dim_type type, unsigned first, unsigned n)
2329 {
2330         return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n);
2331 }
2332
2333 static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2334 {
2335         int i, j;
2336
2337         for (i = 0; i < n; ++i) {
2338                 j = isl_basic_map_alloc_div(bmap);
2339                 if (j < 0)
2340                         goto error;
2341                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2342         }
2343         return bmap;
2344 error:
2345         isl_basic_map_free(bmap);
2346         return NULL;
2347 }
2348
2349 struct isl_basic_map *isl_basic_map_apply_range(
2350                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2351 {
2352         struct isl_dim *dim_result = NULL;
2353         struct isl_basic_map *bmap;
2354         unsigned n_in, n_out, n, nparam, total, pos;
2355         struct isl_dim_map *dim_map1, *dim_map2;
2356
2357         if (!bmap1 || !bmap2)
2358                 goto error;
2359
2360         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2361                                   isl_dim_copy(bmap2->dim));
2362
2363         n_in = isl_basic_map_n_in(bmap1);
2364         n_out = isl_basic_map_n_out(bmap2);
2365         n = isl_basic_map_n_out(bmap1);
2366         nparam = isl_basic_map_n_param(bmap1);
2367
2368         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2369         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2370         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2371         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2372         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2373         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2374         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2375         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2376         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2377         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2378         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2379
2380         bmap = isl_basic_map_alloc_dim(dim_result,
2381                         bmap1->n_div + bmap2->n_div + n,
2382                         bmap1->n_eq + bmap2->n_eq,
2383                         bmap1->n_ineq + bmap2->n_ineq);
2384         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2385         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2386         bmap = add_divs(bmap, n);
2387         bmap = isl_basic_map_simplify(bmap);
2388         bmap = isl_basic_map_drop_redundant_divs(bmap);
2389         return isl_basic_map_finalize(bmap);
2390 error:
2391         isl_basic_map_free(bmap1);
2392         isl_basic_map_free(bmap2);
2393         return NULL;
2394 }
2395
2396 struct isl_basic_set *isl_basic_set_apply(
2397                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2398 {
2399         if (!bset || !bmap)
2400                 goto error;
2401
2402         isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
2403                     goto error);
2404
2405         return (struct isl_basic_set *)
2406                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2407 error:
2408         isl_basic_set_free(bset);
2409         isl_basic_map_free(bmap);
2410         return NULL;
2411 }
2412
2413 struct isl_basic_map *isl_basic_map_apply_domain(
2414                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2415 {
2416         if (!bmap1 || !bmap2)
2417                 goto error;
2418
2419         isl_assert(bmap1->ctx,
2420             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2421         isl_assert(bmap1->ctx,
2422             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2423             goto error);
2424
2425         bmap1 = isl_basic_map_reverse(bmap1);
2426         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2427         return isl_basic_map_reverse(bmap1);
2428 error:
2429         isl_basic_map_free(bmap1);
2430         isl_basic_map_free(bmap2);
2431         return NULL;
2432 }
2433
2434 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
2435  * A \cap B -> f(A) + f(B)
2436  */
2437 struct isl_basic_map *isl_basic_map_sum(
2438                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2439 {
2440         unsigned n_in, n_out, nparam, total, pos;
2441         struct isl_basic_map *bmap = NULL;
2442         struct isl_dim_map *dim_map1, *dim_map2;
2443         int i;
2444
2445         if (!bmap1 || !bmap2)
2446                 goto error;
2447
2448         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
2449                 goto error);
2450
2451         nparam = isl_basic_map_n_param(bmap1);
2452         n_in = isl_basic_map_n_in(bmap1);
2453         n_out = isl_basic_map_n_out(bmap1);
2454
2455         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
2456         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2457         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
2458         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2459         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
2460         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2461         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2462         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
2463         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2464         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2465         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
2466
2467         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
2468                         bmap1->n_div + bmap2->n_div + 2 * n_out,
2469                         bmap1->n_eq + bmap2->n_eq + n_out,
2470                         bmap1->n_ineq + bmap2->n_ineq);
2471         for (i = 0; i < n_out; ++i) {
2472                 int j = isl_basic_map_alloc_equality(bmap);
2473                 if (j < 0)
2474                         goto error;
2475                 isl_seq_clr(bmap->eq[j], 1+total);
2476                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
2477                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
2478                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
2479         }
2480         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2481         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2482         bmap = add_divs(bmap, 2 * n_out);
2483
2484         bmap = isl_basic_map_simplify(bmap);
2485         return isl_basic_map_finalize(bmap);
2486 error:
2487         isl_basic_map_free(bmap);
2488         isl_basic_map_free(bmap1);
2489         isl_basic_map_free(bmap2);
2490         return NULL;
2491 }
2492
2493 /* Given two maps A -> f(A) and B -> g(B), construct a map
2494  * A \cap B -> f(A) + f(B)
2495  */
2496 struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2)
2497 {
2498         struct isl_map *result;
2499         int i, j;
2500
2501         if (!map1 || !map2)
2502                 goto error;
2503
2504         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2505
2506         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2507                                 map1->n * map2->n, 0);
2508         if (!result)
2509                 goto error;
2510         for (i = 0; i < map1->n; ++i)
2511                 for (j = 0; j < map2->n; ++j) {
2512                         struct isl_basic_map *part;
2513                         part = isl_basic_map_sum(
2514                                     isl_basic_map_copy(map1->p[i]),
2515                                     isl_basic_map_copy(map2->p[j]));
2516                         if (isl_basic_map_is_empty(part))
2517                                 isl_basic_map_free(part);
2518                         else
2519                                 result = isl_map_add_basic_map(result, part);
2520                         if (!result)
2521                                 goto error;
2522                 }
2523         isl_map_free(map1);
2524         isl_map_free(map2);
2525         return result;
2526 error:
2527         isl_map_free(map1);
2528         isl_map_free(map2);
2529         return NULL;
2530 }
2531
2532 /* Given a basic map A -> f(A), construct A -> -f(A).
2533  */
2534 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
2535 {
2536         int i, j;
2537         unsigned off, n;
2538
2539         bmap = isl_basic_map_cow(bmap);
2540         if (!bmap)
2541                 return NULL;
2542
2543         n = isl_basic_map_dim(bmap, isl_dim_out);
2544         off = isl_basic_map_offset(bmap, isl_dim_out);
2545         for (i = 0; i < bmap->n_eq; ++i)
2546                 for (j = 0; j < n; ++j)
2547                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
2548         for (i = 0; i < bmap->n_ineq; ++i)
2549                 for (j = 0; j < n; ++j)
2550                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
2551         for (i = 0; i < bmap->n_div; ++i)
2552                 for (j = 0; j < n; ++j)
2553                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
2554         return isl_basic_map_finalize(bmap);
2555 }
2556
2557 /* Given a map A -> f(A), construct A -> -f(A).
2558  */
2559 struct isl_map *isl_map_neg(struct isl_map *map)
2560 {
2561         int i;
2562
2563         map = isl_map_cow(map);
2564         if (!map)
2565                 return NULL;
2566
2567         for (i = 0; i < map->n; ++i) {
2568                 map->p[i] = isl_basic_map_neg(map->p[i]);
2569                 if (!map->p[i])
2570                         goto error;
2571         }
2572
2573         return map;
2574 error:
2575         isl_map_free(map);
2576         return NULL;
2577 }
2578
2579 /* Given a basic map A -> f(A) and an integer d, construct a basic map
2580  * A -> floor(f(A)/d).
2581  */
2582 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
2583                 isl_int d)
2584 {
2585         unsigned n_in, n_out, nparam, total, pos;
2586         struct isl_basic_map *result = NULL;
2587         struct isl_dim_map *dim_map;
2588         int i;
2589
2590         if (!bmap)
2591                 return NULL;
2592
2593         nparam = isl_basic_map_n_param(bmap);
2594         n_in = isl_basic_map_n_in(bmap);
2595         n_out = isl_basic_map_n_out(bmap);
2596
2597         total = nparam + n_in + n_out + bmap->n_div + n_out;
2598         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2599         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
2600         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
2601         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
2602         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
2603
2604         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
2605                         bmap->n_div + n_out,
2606                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
2607         result = add_constraints_dim_map(result, bmap, dim_map);
2608         result = add_divs(result, n_out);
2609         for (i = 0; i < n_out; ++i) {
2610                 int j;
2611                 j = isl_basic_map_alloc_inequality(result);
2612                 if (j < 0)
2613                         goto error;
2614                 isl_seq_clr(result->ineq[j], 1+total);
2615                 isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
2616                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
2617                 j = isl_basic_map_alloc_inequality(result);
2618                 if (j < 0)
2619                         goto error;
2620                 isl_seq_clr(result->ineq[j], 1+total);
2621                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
2622                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
2623                 isl_int_sub_ui(result->ineq[j][0], d, 1);
2624         }
2625
2626         result = isl_basic_map_simplify(result);
2627         return isl_basic_map_finalize(result);
2628 error:
2629         isl_basic_map_free(result);
2630         return NULL;
2631 }
2632
2633 /* Given a map A -> f(A) and an integer d, construct a map
2634  * A -> floor(f(A)/d).
2635  */
2636 struct isl_map *isl_map_floordiv(struct isl_map *map, isl_int d)
2637 {
2638         int i;
2639
2640         map = isl_map_cow(map);
2641         if (!map)
2642                 return NULL;
2643
2644         ISL_F_CLR(map, ISL_MAP_DISJOINT);
2645         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2646         for (i = 0; i < map->n; ++i) {
2647                 map->p[i] = isl_basic_map_floordiv(map->p[i], d);
2648                 if (!map->p[i])
2649                         goto error;
2650         }
2651
2652         return map;
2653 error:
2654         isl_map_free(map);
2655         return NULL;
2656 }
2657
2658 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
2659 {
2660         int i;
2661         unsigned nparam;
2662         unsigned n_in;
2663
2664         i = isl_basic_map_alloc_equality(bmap);
2665         if (i < 0)
2666                 goto error;
2667         nparam = isl_basic_map_n_param(bmap);
2668         n_in = isl_basic_map_n_in(bmap);
2669         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2670         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2671         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2672         return isl_basic_map_finalize(bmap);
2673 error:
2674         isl_basic_map_free(bmap);
2675         return NULL;
2676 }
2677
2678 /* Add a constraints to "bmap" expressing i_pos < o_pos
2679  */
2680 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2681 {
2682         int i;
2683         unsigned nparam;
2684         unsigned n_in;
2685
2686         i = isl_basic_map_alloc_inequality(bmap);
2687         if (i < 0)
2688                 goto error;
2689         nparam = isl_basic_map_n_param(bmap);
2690         n_in = isl_basic_map_n_in(bmap);
2691         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2692         isl_int_set_si(bmap->ineq[i][0], -1);
2693         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2694         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2695         return isl_basic_map_finalize(bmap);
2696 error:
2697         isl_basic_map_free(bmap);
2698         return NULL;
2699 }
2700
2701 /* Add a constraints to "bmap" expressing i_pos > o_pos
2702  */
2703 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
2704 {
2705         int i;
2706         unsigned nparam;
2707         unsigned n_in;
2708
2709         i = isl_basic_map_alloc_inequality(bmap);
2710         if (i < 0)
2711                 goto error;
2712         nparam = isl_basic_map_n_param(bmap);
2713         n_in = isl_basic_map_n_in(bmap);
2714         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2715         isl_int_set_si(bmap->ineq[i][0], -1);
2716         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2717         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2718         return isl_basic_map_finalize(bmap);
2719 error:
2720         isl_basic_map_free(bmap);
2721         return NULL;
2722 }
2723
2724 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
2725 {
2726         int i;
2727         struct isl_basic_map *bmap;
2728         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
2729         if (!bmap)
2730                 return NULL;
2731         for (i = 0; i < n_equal && bmap; ++i)
2732                 bmap = var_equal(bmap, i);
2733         return isl_basic_map_finalize(bmap);
2734 }
2735
2736 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos < o_pos
2737  */
2738 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
2739 {
2740         int i;
2741         struct isl_basic_map *bmap;
2742         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2743         if (!bmap)
2744                 return NULL;
2745         for (i = 0; i < pos && bmap; ++i)
2746                 bmap = var_equal(bmap, i);
2747         if (bmap)
2748                 bmap = var_less(bmap, pos);
2749         return isl_basic_map_finalize(bmap);
2750 }
2751
2752 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
2753  */
2754 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
2755 {
2756         int i;
2757         struct isl_basic_map *bmap;
2758         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2759         if (!bmap)
2760                 return NULL;
2761         for (i = 0; i < pos && bmap; ++i)
2762                 bmap = var_equal(bmap, i);
2763         if (bmap)
2764                 bmap = var_more(bmap, pos);
2765         return isl_basic_map_finalize(bmap);
2766 }
2767
2768 static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
2769 {
2770         struct isl_map *map;
2771         unsigned dim;
2772         int i;
2773
2774         if (!dims)
2775                 return NULL;
2776         dim = dims->n_out;
2777         map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT);
2778
2779         for (i = 0; i < dim; ++i)
2780                 map = isl_map_add_basic_map(map,
2781                                   isl_basic_map_less_at(isl_dim_copy(dims), i));
2782         if (equal)
2783                 map = isl_map_add_basic_map(map,
2784                                   isl_basic_map_equal(isl_dim_copy(dims), dim));
2785
2786         isl_dim_free(dims);
2787         return map;
2788 }
2789
2790 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
2791 {
2792         return map_lex_lte(isl_dim_map(set_dim), 0);
2793 }
2794
2795 __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
2796 {
2797         return map_lex_lte(isl_dim_map(set_dim), 1);
2798 }
2799
2800 static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
2801 {
2802         struct isl_map *map;
2803         unsigned dim;
2804         int i;
2805
2806         if (!dims)
2807                 return NULL;
2808         dim = dims->n_out;
2809         map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT);
2810
2811         for (i = 0; i < dim; ++i)
2812                 map = isl_map_add_basic_map(map,
2813                                   isl_basic_map_more_at(isl_dim_copy(dims), i));
2814         if (equal)
2815                 map = isl_map_add_basic_map(map,
2816                                   isl_basic_map_equal(isl_dim_copy(dims), dim));
2817
2818         isl_dim_free(dims);
2819         return map;
2820 }
2821
2822 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
2823 {
2824         return map_lex_gte(isl_dim_map(set_dim), 0);
2825 }
2826
2827 __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim)
2828 {
2829         return map_lex_gte(isl_dim_map(set_dim), 1);
2830 }
2831
2832 struct isl_basic_map *isl_basic_map_from_basic_set(
2833                 struct isl_basic_set *bset, struct isl_dim *dim)
2834 {
2835         struct isl_basic_map *bmap;
2836
2837         bset = isl_basic_set_cow(bset);
2838         if (!bset || !dim)
2839                 goto error;
2840
2841         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
2842         isl_dim_free(bset->dim);
2843         bmap = (struct isl_basic_map *) bset;
2844         bmap->dim = dim;
2845         return isl_basic_map_finalize(bmap);
2846 error:
2847         isl_basic_set_free(bset);
2848         isl_dim_free(dim);
2849         return NULL;
2850 }
2851
2852 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
2853 {
2854         if (!bmap)
2855                 goto error;
2856         if (bmap->dim->n_in == 0)
2857                 return (struct isl_basic_set *)bmap;
2858         bmap = isl_basic_map_cow(bmap);
2859         if (!bmap)
2860                 goto error;
2861         bmap->dim = isl_dim_cow(bmap->dim);
2862         if (!bmap->dim)
2863                 goto error;
2864         bmap->dim->n_out += bmap->dim->n_in;
2865         bmap->dim->n_in = 0;
2866         bmap = isl_basic_map_finalize(bmap);
2867         return (struct isl_basic_set *)bmap;
2868 error:
2869         isl_basic_map_free(bmap);
2870         return NULL;
2871 }
2872
2873 /* For a div d = floor(f/m), add the constraints
2874  *
2875  *              f - m d >= 0
2876  *              -(f-(n-1)) + m d >= 0
2877  *
2878  * Note that the second constraint is the negation of
2879  *
2880  *              f - m d >= n
2881  */
2882 int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
2883 {
2884         int i, j;
2885         unsigned total = isl_basic_map_total_dim(bmap);
2886         unsigned div_pos = 1 + total - bmap->n_div + div;
2887
2888         i = isl_basic_map_alloc_inequality(bmap);
2889         if (i < 0)
2890                 return -1;
2891         isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total);
2892         isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]);
2893
2894         j = isl_basic_map_alloc_inequality(bmap);
2895         if (j < 0)
2896                 return -1;
2897         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
2898         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]);
2899         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
2900         return j;
2901 }
2902
2903 struct isl_basic_set *isl_basic_map_underlying_set(
2904                 struct isl_basic_map *bmap)
2905 {
2906         if (!bmap)
2907                 goto error;
2908         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
2909                 return (struct isl_basic_set *)bmap;
2910         bmap = isl_basic_map_cow(bmap);
2911         if (!bmap)
2912                 goto error;
2913         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
2914         if (!bmap->dim)
2915                 goto error;
2916         bmap->extra -= bmap->n_div;
2917         bmap->n_div = 0;
2918         bmap = isl_basic_map_finalize(bmap);
2919         return (struct isl_basic_set *)bmap;
2920 error:
2921         return NULL;
2922 }
2923
2924 __isl_give isl_basic_set *isl_basic_set_underlying_set(
2925                 __isl_take isl_basic_set *bset)
2926 {
2927         return isl_basic_map_underlying_set((isl_basic_map *)bset);
2928 }
2929
2930 struct isl_basic_map *isl_basic_map_overlying_set(
2931         struct isl_basic_set *bset, struct isl_basic_map *like)
2932 {
2933         struct isl_basic_map *bmap;
2934         struct isl_ctx *ctx;
2935         unsigned total;
2936         int i;
2937
2938         if (!bset || !like)
2939                 goto error;
2940         ctx = bset->ctx;
2941         isl_assert(ctx, bset->n_div == 0, goto error);
2942         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
2943         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
2944                         goto error);
2945         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
2946                 isl_basic_map_free(like);
2947                 return (struct isl_basic_map *)bset;
2948         }
2949         bset = isl_basic_set_cow(bset);
2950         if (!bset)
2951                 goto error;
2952         total = bset->dim->n_out + bset->extra;
2953         bmap = (struct isl_basic_map *)bset;
2954         isl_dim_free(bmap->dim);
2955         bmap->dim = isl_dim_copy(like->dim);
2956         if (!bmap->dim)
2957                 goto error;
2958         bmap->n_div = like->n_div;
2959         bmap->extra += like->n_div;
2960         if (bmap->extra) {
2961                 unsigned ltotal;
2962                 ltotal = total - bmap->extra + like->extra;
2963                 if (ltotal > total)
2964                         ltotal = total;
2965                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
2966                                         bmap->extra * (1 + 1 + total));
2967                 if (isl_blk_is_error(bmap->block2))
2968                         goto error;
2969                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
2970                                                 bmap->extra);
2971                 if (!bmap->div)
2972                         goto error;
2973                 for (i = 0; i < bmap->extra; ++i)
2974                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
2975                 for (i = 0; i < like->n_div; ++i) {
2976                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
2977                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
2978                 }
2979                 bmap = isl_basic_map_extend_constraints(bmap,
2980                                                         0, 2 * like->n_div);
2981                 for (i = 0; i < like->n_div; ++i) {
2982                         if (isl_int_is_zero(bmap->div[i][0]))
2983                                 continue;
2984                         if (isl_basic_map_add_div_constraints(bmap, i) < 0)
2985                                 goto error;
2986                 }
2987         }
2988         isl_basic_map_free(like);
2989         bmap = isl_basic_map_simplify(bmap);
2990         bmap = isl_basic_map_finalize(bmap);
2991         return bmap;
2992 error:
2993         isl_basic_map_free(like);
2994         isl_basic_set_free(bset);
2995         return NULL;
2996 }
2997
2998 struct isl_basic_set *isl_basic_set_from_underlying_set(
2999         struct isl_basic_set *bset, struct isl_basic_set *like)
3000 {
3001         return (struct isl_basic_set *)
3002                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
3003 }
3004
3005 struct isl_set *isl_set_from_underlying_set(
3006         struct isl_set *set, struct isl_basic_set *like)
3007 {
3008         int i;
3009
3010         if (!set || !like)
3011                 goto error;
3012         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
3013                     goto error);
3014         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
3015                 isl_basic_set_free(like);
3016                 return set;
3017         }
3018         set = isl_set_cow(set);
3019         if (!set)
3020                 goto error;
3021         for (i = 0; i < set->n; ++i) {
3022                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
3023                                                       isl_basic_set_copy(like));
3024                 if (!set->p[i])
3025                         goto error;
3026         }
3027         isl_dim_free(set->dim);
3028         set->dim = isl_dim_copy(like->dim);
3029         if (!set->dim)
3030                 goto error;
3031         isl_basic_set_free(like);
3032         return set;
3033 error:
3034         isl_basic_set_free(like);
3035         isl_set_free(set);
3036         return NULL;
3037 }
3038
3039 struct isl_set *isl_map_underlying_set(struct isl_map *map)
3040 {
3041         int i;
3042
3043         map = isl_map_cow(map);
3044         if (!map)
3045                 return NULL;
3046         map->dim = isl_dim_cow(map->dim);
3047         if (!map->dim)
3048                 goto error;
3049
3050         for (i = 1; i < map->n; ++i)
3051                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
3052                                 goto error);
3053         for (i = 0; i < map->n; ++i) {
3054                 map->p[i] = (struct isl_basic_map *)
3055                                 isl_basic_map_underlying_set(map->p[i]);
3056                 if (!map->p[i])
3057                         goto error;
3058         }
3059         if (map->n == 0)
3060                 map->dim = isl_dim_underlying(map->dim, 0);
3061         else {
3062                 isl_dim_free(map->dim);
3063                 map->dim = isl_dim_copy(map->p[0]->dim);
3064         }
3065         if (!map->dim)
3066                 goto error;
3067         return (struct isl_set *)map;
3068 error:
3069         isl_map_free(map);
3070         return NULL;
3071 }
3072
3073 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
3074 {
3075         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
3076 }
3077
3078 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
3079 {
3080         struct isl_basic_set *domain;
3081         unsigned n_in;
3082         unsigned n_out;
3083         if (!bmap)
3084                 return NULL;
3085         n_in = isl_basic_map_n_in(bmap);
3086         n_out = isl_basic_map_n_out(bmap);
3087         domain = isl_basic_set_from_basic_map(bmap);
3088         return isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
3089 }
3090
3091 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
3092 {
3093         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
3094 }
3095
3096 struct isl_set *isl_map_range(struct isl_map *map)
3097 {
3098         int i;
3099         struct isl_set *set;
3100
3101         if (!map)
3102                 goto error;
3103         if (isl_map_dim(map, isl_dim_in) == 0)
3104                 return (isl_set *)map;
3105
3106         map = isl_map_cow(map);
3107         if (!map)
3108                 goto error;
3109
3110         set = (struct isl_set *) map;
3111         set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
3112         if (!set->dim)
3113                 goto error;
3114         for (i = 0; i < map->n; ++i) {
3115                 set->p[i] = isl_basic_map_range(map->p[i]);
3116                 if (!set->p[i])
3117                         goto error;
3118         }
3119         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3120         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3121         return set;
3122 error:
3123         isl_map_free(map);
3124         return NULL;
3125 }
3126
3127 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3128 {
3129         int i;
3130         struct isl_map *map = NULL;
3131
3132         set = isl_set_cow(set);
3133         if (!set || !dim)
3134                 goto error;
3135         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3136         map = (struct isl_map *)set;
3137         for (i = 0; i < set->n; ++i) {
3138                 map->p[i] = isl_basic_map_from_basic_set(
3139                                 set->p[i], isl_dim_copy(dim));
3140                 if (!map->p[i])
3141                         goto error;
3142         }
3143         isl_dim_free(map->dim);
3144         map->dim = dim;
3145         return map;
3146 error:
3147         isl_dim_free(dim);
3148         isl_set_free(set);
3149         return NULL;
3150 }
3151
3152 struct isl_map *isl_map_from_range(struct isl_set *set)
3153 {
3154         return (struct isl_map *)set;
3155 }
3156
3157 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
3158 {
3159         return isl_map_reverse(isl_map_from_range(set));;
3160 }
3161
3162 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
3163         __isl_take isl_set *range)
3164 {
3165         return isl_map_product(isl_map_from_domain(domain),
3166                                isl_map_from_range(range));
3167 }
3168
3169 struct isl_set *isl_set_from_map(struct isl_map *map)
3170 {
3171         int i;
3172         struct isl_set *set = NULL;
3173
3174         if (!map)
3175                 return NULL;
3176         map = isl_map_cow(map);
3177         if (!map)
3178                 return NULL;
3179         map->dim = isl_dim_cow(map->dim);
3180         if (!map->dim)
3181                 goto error;
3182         map->dim->n_out += map->dim->n_in;
3183         map->dim->n_in = 0;
3184         set = (struct isl_set *)map;
3185         for (i = 0; i < map->n; ++i) {
3186                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3187                 if (!set->p[i])
3188                         goto error;
3189         }
3190         return set;
3191 error:
3192         isl_map_free(map);
3193         return NULL;
3194 }
3195
3196 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3197 {
3198         struct isl_map *map;
3199
3200         if (!dim)
3201                 return NULL;
3202         isl_assert(dim->ctx, n >= 0, return NULL);
3203         map = isl_alloc(dim->ctx, struct isl_map,
3204                         sizeof(struct isl_map) +
3205                         (n - 1) * sizeof(struct isl_basic_map *));
3206         if (!map)
3207                 goto error;
3208
3209         map->ctx = dim->ctx;
3210         isl_ctx_ref(map->ctx);
3211         map->ref = 1;
3212         map->size = n;
3213         map->n = 0;
3214         map->dim = dim;
3215         map->flags = flags;
3216         return map;
3217 error:
3218         isl_dim_free(dim);
3219         return NULL;
3220 }
3221
3222 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3223                 unsigned nparam, unsigned in, unsigned out, int n,
3224                 unsigned flags)
3225 {
3226         struct isl_map *map;
3227         struct isl_dim *dims;
3228
3229         dims = isl_dim_alloc(ctx, nparam, in, out);
3230         if (!dims)
3231                 return NULL;
3232
3233         map = isl_map_alloc_dim(dims, n, flags);
3234         return map;
3235 }
3236
3237 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
3238 {
3239         struct isl_basic_map *bmap;
3240         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
3241         bmap = isl_basic_map_set_to_empty(bmap);
3242         return bmap;
3243 }
3244
3245 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3246 {
3247         struct isl_basic_set *bset;
3248         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3249         bset = isl_basic_set_set_to_empty(bset);
3250         return bset;
3251 }
3252
3253 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3254 {
3255         struct isl_basic_map *bmap;
3256         if (!model)
3257                 return NULL;
3258         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3259         bmap = isl_basic_map_set_to_empty(bmap);
3260         return bmap;
3261 }
3262
3263 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3264 {
3265         struct isl_basic_map *bmap;
3266         if (!model)
3267                 return NULL;
3268         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3269         bmap = isl_basic_map_set_to_empty(bmap);
3270         return bmap;
3271 }
3272
3273 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3274 {
3275         struct isl_basic_set *bset;
3276         if (!model)
3277                 return NULL;
3278         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3279         bset = isl_basic_set_set_to_empty(bset);
3280         return bset;
3281 }
3282
3283 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3284 {
3285         struct isl_basic_map *bmap;
3286         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3287         return bmap;
3288 }
3289
3290 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3291 {
3292         struct isl_basic_set *bset;
3293         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3294         return bset;
3295 }
3296
3297 __isl_give isl_basic_map *isl_basic_map_universe_like(
3298                 __isl_keep isl_basic_map *model)
3299 {
3300         if (!model)
3301                 return NULL;
3302         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3303 }
3304
3305 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3306 {
3307         if (!model)
3308                 return NULL;
3309         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3310 }
3311
3312 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3313         __isl_keep isl_set *model)
3314 {
3315         if (!model)
3316                 return NULL;
3317         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3318 }
3319
3320 struct isl_map *isl_map_empty(struct isl_dim *dim)
3321 {
3322         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3323 }
3324
3325 struct isl_map *isl_map_empty_like(struct isl_map *model)
3326 {
3327         if (!model)
3328                 return NULL;
3329         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3330 }
3331
3332 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3333 {
3334         if (!model)
3335                 return NULL;
3336         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3337 }
3338
3339 struct isl_set *isl_set_empty(struct isl_dim *dim)
3340 {
3341         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3342 }
3343
3344 struct isl_set *isl_set_empty_like(struct isl_set *model)
3345 {
3346         if (!model)
3347                 return NULL;
3348         return isl_set_empty(isl_dim_copy(model->dim));
3349 }
3350
3351 struct isl_map *isl_map_universe(struct isl_dim *dim)
3352 {
3353         struct isl_map *map;
3354         if (!dim)
3355                 return NULL;
3356         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3357         map = isl_map_add_basic_map(map, isl_basic_map_universe(dim));
3358         return map;
3359 }
3360
3361 struct isl_set *isl_set_universe(struct isl_dim *dim)
3362 {
3363         struct isl_set *set;
3364         if (!dim)
3365                 return NULL;
3366         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3367         set = isl_set_add_basic_set(set, isl_basic_set_universe(dim));
3368         return set;
3369 }
3370
3371 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3372 {
3373         if (!model)
3374                 return NULL;
3375         return isl_set_universe(isl_dim_copy(model->dim));
3376 }
3377
3378 struct isl_map *isl_map_dup(struct isl_map *map)
3379 {
3380         int i;
3381         struct isl_map *dup;
3382
3383         if (!map)
3384                 return NULL;
3385         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3386         for (i = 0; i < map->n; ++i)
3387                 dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i]));
3388         return dup;
3389 }
3390
3391 __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
3392                                                 __isl_take isl_basic_map *bmap)
3393 {
3394         if (!bmap || !map)
3395                 goto error;
3396         if (isl_basic_map_fast_is_empty(bmap)) {
3397                 isl_basic_map_free(bmap);
3398                 return map;
3399         }
3400         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3401         isl_assert(map->ctx, map->n < map->size, goto error);
3402         map->p[map->n] = bmap;
3403         map->n++;
3404         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3405         return map;
3406 error:
3407         if (map)
3408                 isl_map_free(map);
3409         if (bmap)
3410                 isl_basic_map_free(bmap);
3411         return NULL;
3412 }
3413
3414 void isl_map_free(struct isl_map *map)
3415 {
3416         int i;
3417
3418         if (!map)
3419                 return;
3420
3421         if (--map->ref > 0)
3422                 return;
3423
3424         isl_ctx_deref(map->ctx);
3425         for (i = 0; i < map->n; ++i)
3426                 isl_basic_map_free(map->p[i]);
3427         isl_dim_free(map->dim);
3428         free(map);
3429 }
3430
3431 struct isl_map *isl_map_extend(struct isl_map *base,
3432                 unsigned nparam, unsigned n_in, unsigned n_out)
3433 {
3434         int i;
3435
3436         base = isl_map_cow(base);
3437         if (!base)
3438                 return NULL;
3439
3440         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3441         if (!base->dim)
3442                 goto error;
3443         for (i = 0; i < base->n; ++i) {
3444                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3445                                 isl_dim_copy(base->dim), 0, 0, 0);
3446                 if (!base->p[i])
3447                         goto error;
3448         }
3449         return base;
3450 error:
3451         isl_map_free(base);
3452         return NULL;
3453 }
3454
3455 struct isl_set *isl_set_extend(struct isl_set *base,
3456                 unsigned nparam, unsigned dim)
3457 {
3458         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3459                                                         nparam, 0, dim);
3460 }
3461
3462 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3463         struct isl_basic_map *bmap, unsigned pos, int value)
3464 {
3465         int j;
3466
3467         bmap = isl_basic_map_cow(bmap);
3468         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3469         j = isl_basic_map_alloc_equality(bmap);
3470         if (j < 0)
3471                 goto error;
3472         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3473         isl_int_set_si(bmap->eq[j][pos], -1);
3474         isl_int_set_si(bmap->eq[j][0], value);
3475         bmap = isl_basic_map_simplify(bmap);
3476         return isl_basic_map_finalize(bmap);
3477 error:
3478         isl_basic_map_free(bmap);
3479         return NULL;
3480 }
3481
3482 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3483         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3484 {
3485         int j;
3486
3487         bmap = isl_basic_map_cow(bmap);
3488         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3489         j = isl_basic_map_alloc_equality(bmap);
3490         if (j < 0)
3491                 goto error;
3492         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3493         isl_int_set_si(bmap->eq[j][pos], -1);
3494         isl_int_set(bmap->eq[j][0], value);
3495         bmap = isl_basic_map_simplify(bmap);
3496         return isl_basic_map_finalize(bmap);
3497 error:
3498         isl_basic_map_free(bmap);
3499         return NULL;
3500 }
3501
3502 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3503                 enum isl_dim_type type, unsigned pos, int value)
3504 {
3505         if (!bmap)
3506                 return NULL;
3507         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3508         return isl_basic_map_fix_pos_si(bmap,
3509                 isl_basic_map_offset(bmap, type) + pos, value);
3510 error:
3511         isl_basic_map_free(bmap);
3512         return NULL;
3513 }
3514
3515 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3516                 enum isl_dim_type type, unsigned pos, isl_int value)
3517 {
3518         if (!bmap)
3519                 return NULL;
3520         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3521         return isl_basic_map_fix_pos(bmap,
3522                 isl_basic_map_offset(bmap, type) + pos, value);
3523 error:
3524         isl_basic_map_free(bmap);
3525         return NULL;
3526 }
3527
3528 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3529                 enum isl_dim_type type, unsigned pos, int value)
3530 {
3531         return (struct isl_basic_set *)
3532                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3533                                         type, pos, value);
3534 }
3535
3536 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3537                 enum isl_dim_type type, unsigned pos, isl_int value)
3538 {
3539         return (struct isl_basic_set *)
3540                 isl_basic_map_fix((struct isl_basic_map *)bset,
3541                                         type, pos, value);
3542 }
3543
3544 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3545                 unsigned input, int value)
3546 {
3547         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3548 }
3549
3550 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3551                 unsigned dim, int value)
3552 {
3553         return (struct isl_basic_set *)
3554                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3555                                         isl_dim_set, dim, value);
3556 }
3557
3558 struct isl_map *isl_map_fix_si(struct isl_map *map,
3559                 enum isl_dim_type type, unsigned pos, int value)
3560 {
3561         int i;
3562
3563         map = isl_map_cow(map);
3564         if (!map)
3565                 return NULL;
3566
3567         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3568         for (i = 0; i < map->n; ++i) {
3569                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
3570                 if (!map->p[i])
3571                         goto error;
3572         }
3573         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3574         return map;
3575 error:
3576         isl_map_free(map);
3577         return NULL;
3578 }
3579
3580 __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
3581                 enum isl_dim_type type, unsigned pos, int value)
3582 {
3583         return (struct isl_set *)
3584                 isl_map_fix_si((struct isl_map *)set, type, pos, value);
3585 }
3586
3587 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
3588                 enum isl_dim_type type, unsigned pos, isl_int value)
3589 {
3590         int i;
3591
3592         map = isl_map_cow(map);
3593         if (!map)
3594                 return NULL;
3595
3596         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3597         for (i = 0; i < map->n; ++i) {
3598                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
3599                 if (!map->p[i])
3600                         goto error;
3601         }
3602         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3603         return map;
3604 error:
3605         isl_map_free(map);
3606         return NULL;
3607 }
3608
3609 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
3610                 enum isl_dim_type type, unsigned pos, isl_int value)
3611 {
3612         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
3613 }
3614
3615 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3616                 unsigned input, int value)
3617 {
3618         return isl_map_fix_si(map, isl_dim_in, input, value);
3619 }
3620
3621 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3622 {
3623         return (struct isl_set *)
3624                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
3625 }
3626
3627 __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
3628                 __isl_take isl_basic_map *bmap,
3629                 enum isl_dim_type type, unsigned pos, int value)
3630 {
3631         int j;
3632
3633         if (!bmap)
3634                 return NULL;
3635         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3636         pos += isl_basic_map_offset(bmap, type);
3637         bmap = isl_basic_map_cow(bmap);
3638         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
3639         j = isl_basic_map_alloc_inequality(bmap);
3640         if (j < 0)
3641                 goto error;
3642         isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
3643         isl_int_set_si(bmap->ineq[j][pos], 1);
3644         isl_int_set_si(bmap->ineq[j][0], -value);
3645         bmap = isl_basic_map_simplify(bmap);
3646         return isl_basic_map_finalize(bmap);
3647 error:
3648         isl_basic_map_free(bmap);
3649         return NULL;
3650 }
3651
3652 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3653         unsigned dim, isl_int value)
3654 {
3655         int j;
3656
3657         bset = isl_basic_set_cow(bset);
3658         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3659         j = isl_basic_set_alloc_inequality(bset);
3660         if (j < 0)
3661                 goto error;
3662         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3663         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3664         isl_int_neg(bset->ineq[j][0], value);
3665         bset = isl_basic_set_simplify(bset);
3666         return isl_basic_set_finalize(bset);
3667 error:
3668         isl_basic_set_free(bset);
3669         return NULL;
3670 }
3671
3672 __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
3673                 enum isl_dim_type type, unsigned pos, int value)
3674 {
3675         int i;
3676
3677         map = isl_map_cow(map);
3678         if (!map)
3679                 return NULL;
3680
3681         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3682         for (i = 0; i < map->n; ++i) {
3683                 map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
3684                                                          type, pos, value);
3685                 if (!map->p[i])
3686                         goto error;
3687         }
3688         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3689         return map;
3690 error:
3691         isl_map_free(map);
3692         return NULL;
3693 }
3694
3695 __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
3696                 enum isl_dim_type type, unsigned pos, int value)
3697 {
3698         return (struct isl_set *)
3699                 isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
3700 }
3701
3702 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3703                                         isl_int value)
3704 {
3705         int i;
3706
3707         set = isl_set_cow(set);
3708         if (!set)
3709                 return NULL;
3710
3711         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3712         for (i = 0; i < set->n; ++i) {
3713                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3714                 if (!set->p[i])
3715                         goto error;
3716         }
3717         return set;
3718 error:
3719         isl_set_free(set);
3720         return NULL;
3721 }
3722
3723 struct isl_map *isl_map_reverse(struct isl_map *map)
3724 {
3725         int i;
3726
3727         map = isl_map_cow(map);
3728         if (!map)
3729                 return NULL;
3730
3731         map->dim = isl_dim_reverse(map->dim);
3732         if (!map->dim)
3733                 goto error;
3734         for (i = 0; i < map->n; ++i) {
3735                 map->p[i] = isl_basic_map_reverse(map->p[i]);
3736                 if (!map->p[i])
3737                         goto error;
3738         }
3739         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3740         return map;
3741 error:
3742         isl_map_free(map);
3743         return NULL;
3744 }
3745
3746 static struct isl_map *isl_basic_map_partial_lexopt(
3747                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3748                 struct isl_set **empty, int max)
3749 {
3750         if (!bmap)
3751                 goto error;
3752         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
3753                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
3754         else
3755                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
3756 error:
3757         isl_basic_map_free(bmap);
3758         isl_basic_set_free(dom);
3759         if (empty)
3760                 *empty = NULL;
3761         return NULL;
3762 }
3763
3764 struct isl_map *isl_basic_map_partial_lexmax(
3765                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3766                 struct isl_set **empty)
3767 {
3768         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
3769 }
3770
3771 struct isl_map *isl_basic_map_partial_lexmin(
3772                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3773                 struct isl_set **empty)
3774 {
3775         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
3776 }
3777
3778 struct isl_set *isl_basic_set_partial_lexmin(
3779                 struct isl_basic_set *bset, struct isl_basic_set *dom,
3780                 struct isl_set **empty)
3781 {
3782         return (struct isl_set *)
3783                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
3784                         dom, empty);
3785 }
3786
3787 struct isl_set *isl_basic_set_partial_lexmax(
3788                 struct isl_basic_set *bset, struct isl_basic_set *dom,
3789                 struct isl_set **empty)
3790 {
3791         return (struct isl_set *)
3792                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
3793                         dom, empty);
3794 }
3795
3796 /* Given a basic map "bmap", compute the lexicograhically minimal
3797  * (or maximal) image element for each domain element in dom.
3798  * Set *empty to those elements in dom that do not have an image element.
3799  *
3800  * We first make sure the basic sets in dom are disjoint and then
3801  * simply collect the results over each of the basic sets separately.
3802  * We could probably improve the efficiency a bit by moving the union
3803  * domain down into the parametric integer programming.
3804  */
3805 static __isl_give isl_map *basic_map_partial_lexopt(
3806                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
3807                 __isl_give isl_set **empty, int max)
3808 {
3809         int i;
3810         struct isl_map *res;
3811
3812         dom = isl_set_make_disjoint(dom);
3813         if (!dom)
3814                 goto error;
3815
3816         if (isl_set_fast_is_empty(dom)) {
3817                 res = isl_map_empty_like_basic_map(bmap);
3818                 *empty = isl_set_empty_like(dom);
3819                 isl_set_free(dom);
3820                 isl_basic_map_free(bmap);
3821                 return res;
3822         }
3823
3824         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
3825                         isl_basic_set_copy(dom->p[0]), empty, max);
3826
3827         for (i = 1; i < dom->n; ++i) {
3828                 struct isl_map *res_i;
3829                 struct isl_set *empty_i;
3830
3831                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
3832                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
3833
3834                 res = isl_map_union_disjoint(res, res_i);
3835                 *empty = isl_set_union_disjoint(*empty, empty_i);
3836         }
3837
3838         isl_set_free(dom);
3839         isl_basic_map_free(bmap);
3840         return res;
3841 error:
3842         *empty = NULL;
3843         isl_set_free(dom);
3844         isl_basic_map_free(bmap);
3845         return NULL;
3846 }
3847
3848 /* Given a map "map", compute the lexicograhically minimal
3849  * (or maximal) image element for each domain element in dom.
3850  * Set *empty to those elements in dom that do not have an image element.
3851  *
3852  * We first compute the lexicographically minimal or maximal element
3853  * in the first basic map.  This results in a partial solution "res"
3854  * and a subset "todo" of dom that still need to be handled.
3855  * We then consider each of the remaining maps in "map" and successively
3856  * improve both "res" and "todo".
3857  *
3858  * Let res^k and todo^k be the results after k steps and let i = k + 1.
3859  * Assume we are computing the lexicographical maximum.
3860  * We first intersect basic map i with a relation that maps elements
3861  * to elements that are lexicographically larger than the image elements
3862  * in res^k and the compute the maximum image element of this intersection.
3863  * The result ("better") corresponds to those image elements in basic map i
3864  * that are better than what we had before.  The remainder ("keep") are the
3865  * domain elements for which the image element in res_k was better.
3866  * We also compute the lexicographical maximum of basic map i in todo^k.
3867  * res^i is the result of the operation + better + those elements in
3868  *              res^k that we should keep
3869  * todo^i is the remainder of the maximum operation on todo^k.
3870  */
3871 static __isl_give isl_map *isl_map_partial_lexopt(
3872                 __isl_take isl_map *map, __isl_take isl_set *dom,
3873                 __isl_give isl_set **empty, int max)
3874 {
3875         int i;
3876         struct isl_map *res;
3877         struct isl_set *todo;
3878
3879         if (!map || !dom)
3880                 goto error;
3881
3882         if (isl_map_fast_is_empty(map)) {
3883                 if (empty)
3884                         *empty = dom;
3885                 else
3886                         isl_set_free(dom);
3887                 return map;
3888         }
3889
3890         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
3891                                         isl_set_copy(dom), &todo, max);
3892
3893         for (i = 1; i < map->n; ++i) {
3894                 struct isl_map *lt;
3895                 struct isl_map *better;
3896                 struct isl_set *keep;
3897                 struct isl_map *res_i;
3898                 struct isl_set *todo_i;
3899                 struct isl_dim *dim = isl_map_get_dim(res);
3900
3901                 dim = isl_dim_range(dim);
3902                 if (max)
3903                         lt = isl_map_lex_lt(dim);
3904                 else
3905                         lt = isl_map_lex_gt(dim);
3906                 lt = isl_map_apply_range(isl_map_copy(res), lt);
3907                 lt = isl_map_intersect(lt,
3908                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
3909                 better = isl_map_partial_lexopt(lt,
3910                         isl_map_domain(isl_map_copy(res)),
3911                         &keep, max);
3912
3913                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
3914                                                 todo, &todo_i, max);
3915
3916                 res = isl_map_intersect_domain(res, keep);
3917                 res = isl_map_union_disjoint(res, res_i);
3918                 res = isl_map_union_disjoint(res, better);
3919                 todo = todo_i;
3920         }
3921
3922         isl_set_free(dom);
3923         isl_map_free(map);
3924
3925         if (empty)
3926                 *empty = todo;
3927         else
3928                 isl_set_free(todo);
3929
3930         return res;
3931 error:
3932         if (empty)
3933                 *empty = NULL;
3934         isl_set_free(dom);
3935         isl_map_free(map);
3936         return NULL;
3937 }
3938
3939 __isl_give isl_map *isl_map_partial_lexmax(
3940                 __isl_take isl_map *map, __isl_take isl_set *dom,
3941                 __isl_give isl_set **empty)
3942 {
3943         return isl_map_partial_lexopt(map, dom, empty, 1);
3944 }
3945
3946 __isl_give isl_map *isl_map_partial_lexmin(
3947                 __isl_take isl_map *map, __isl_take isl_set *dom,
3948                 __isl_give isl_set **empty)
3949 {
3950         return isl_map_partial_lexopt(map, dom, empty, 0);
3951 }
3952
3953 __isl_give isl_set *isl_set_partial_lexmin(
3954                 __isl_take isl_set *set, __isl_take isl_set *dom,
3955                 __isl_give isl_set **empty)
3956 {
3957         return (struct isl_set *)
3958                 isl_map_partial_lexmin((struct isl_map *)set,
3959                         dom, empty);
3960 }
3961
3962 __isl_give isl_set *isl_set_partial_lexmax(
3963                 __isl_take isl_set *set, __isl_take isl_set *dom,
3964                 __isl_give isl_set **empty)
3965 {
3966         return (struct isl_set *)
3967                 isl_map_partial_lexmax((struct isl_map *)set,
3968                         dom, empty);
3969 }
3970
3971 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
3972 {
3973         struct isl_basic_set *dom = NULL;
3974         struct isl_dim *dom_dim;
3975
3976         if (!bmap)
3977                 goto error;
3978         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
3979         dom = isl_basic_set_universe(dom_dim);
3980         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
3981 error:
3982         isl_basic_map_free(bmap);
3983         return NULL;
3984 }
3985
3986 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
3987 {
3988         return isl_basic_map_lexopt(bmap, 0);
3989 }
3990
3991 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
3992 {
3993         return isl_basic_map_lexopt(bmap, 1);
3994 }
3995
3996 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
3997 {
3998         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
3999 }
4000
4001 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
4002 {
4003         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
4004 }
4005
4006 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
4007 {
4008         struct isl_set *dom = NULL;
4009         struct isl_dim *dom_dim;
4010
4011         if (!map)
4012                 goto error;
4013         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
4014         dom = isl_set_universe(dom_dim);
4015         return isl_map_partial_lexopt(map, dom, NULL, max);
4016 error:
4017         isl_map_free(map);
4018         return NULL;
4019 }
4020
4021 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
4022 {
4023         return isl_map_lexopt(map, 0);
4024 }
4025
4026 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
4027 {
4028         return isl_map_lexopt(map, 1);
4029 }
4030
4031 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
4032 {
4033         return (isl_set *)isl_map_lexmin((isl_map *)set);
4034 }
4035
4036 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
4037 {
4038         return (isl_set *)isl_map_lexmax((isl_map *)set);
4039 }
4040
4041 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
4042         struct isl_dim *dim)
4043 {
4044         int i;
4045
4046         if (!map || !dim)
4047                 goto error;
4048
4049         for (i = 0; i < map->n; ++i) {
4050                 isl_dim_free(map->p[i]->dim);
4051                 map->p[i]->dim = isl_dim_copy(dim);
4052         }
4053         isl_dim_free(map->dim);
4054         map->dim = dim;
4055
4056         return map;
4057 error:
4058         isl_map_free(map);
4059         isl_dim_free(dim);
4060         return NULL;
4061 }
4062
4063 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
4064         struct isl_dim *dim)
4065 {
4066         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
4067 }
4068
4069 /* Apply a preimage specified by "mat" on the parameters of "bset".
4070  * bset is assumed to have only parameters and divs.
4071  */
4072 static struct isl_basic_set *basic_set_parameter_preimage(
4073         struct isl_basic_set *bset, struct isl_mat *mat)
4074 {
4075         unsigned nparam;
4076
4077         if (!bset || !mat)
4078                 goto error;
4079
4080         bset->dim = isl_dim_cow(bset->dim);
4081         if (!bset->dim)
4082                 goto error;
4083
4084         nparam = isl_basic_set_dim(bset, isl_dim_param);
4085
4086         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
4087
4088         bset->dim->nparam = 0;
4089         bset->dim->n_out = nparam;
4090         bset = isl_basic_set_preimage(bset, mat);
4091         if (bset) {
4092                 bset->dim->nparam = bset->dim->n_out;
4093                 bset->dim->n_out = 0;
4094         }
4095         return bset;
4096 error:
4097         isl_mat_free(mat);
4098         isl_basic_set_free(bset);
4099         return NULL;
4100 }
4101
4102 /* Apply a preimage specified by "mat" on the parameters of "set".
4103  * set is assumed to have only parameters and divs.
4104  */
4105 static struct isl_set *set_parameter_preimage(
4106         struct isl_set *set, struct isl_mat *mat)
4107 {
4108         struct isl_dim *dim = NULL;
4109         unsigned nparam;
4110
4111         if (!set || !mat)
4112                 goto error;
4113
4114         dim = isl_dim_copy(set->dim);
4115         dim = isl_dim_cow(dim);
4116         if (!dim)
4117                 goto error;
4118
4119         nparam = isl_set_dim(set, isl_dim_param);
4120
4121         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
4122
4123         dim->nparam = 0;
4124         dim->n_out = nparam;
4125         isl_set_reset_dim(set, dim);
4126         set = isl_set_preimage(set, mat);
4127         if (!set)
4128                 goto error2;
4129         dim = isl_dim_copy(set->dim);
4130         dim = isl_dim_cow(dim);
4131         if (!dim)
4132                 goto error2;
4133         dim->nparam = dim->n_out;
4134         dim->n_out = 0;
4135         isl_set_reset_dim(set, dim);
4136         return set;
4137 error:
4138         isl_dim_free(dim);
4139         isl_mat_free(mat);
4140 error2:
4141         isl_set_free(set);
4142         return NULL;
4143 }
4144
4145 /* Intersect the basic set "bset" with the affine space specified by the
4146  * equalities in "eq".
4147  */
4148 static struct isl_basic_set *basic_set_append_equalities(
4149         struct isl_basic_set *bset, struct isl_mat *eq)
4150 {
4151         int i, k;
4152         unsigned len;
4153
4154         if (!bset || !eq)
4155                 goto error;
4156
4157         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
4158                                         eq->n_row, 0);
4159         if (!bset)
4160                 goto error;
4161
4162         len = 1 + isl_dim_total(bset->dim) + bset->extra;
4163         for (i = 0; i < eq->n_row; ++i) {
4164                 k = isl_basic_set_alloc_equality(bset);
4165                 if (k < 0)
4166                         goto error;
4167                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
4168                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
4169         }
4170         isl_mat_free(eq);
4171
4172         return bset;
4173 error:
4174         isl_mat_free(eq);
4175         isl_basic_set_free(bset);
4176         return NULL;
4177 }
4178
4179 /* Intersect the set "set" with the affine space specified by the
4180  * equalities in "eq".
4181  */
4182 static struct isl_set *set_append_equalities(struct isl_set *set,
4183         struct isl_mat *eq)
4184 {
4185         int i;
4186
4187         if (!set || !eq)
4188                 goto error;
4189
4190         for (i = 0; i < set->n; ++i) {
4191                 set->p[i] = basic_set_append_equalities(set->p[i],
4192                                         isl_mat_copy(eq));
4193                 if (!set->p[i])
4194                         goto error;
4195         }
4196         isl_mat_free(eq);
4197         return set;
4198 error:
4199         isl_mat_free(eq);
4200         isl_set_free(set);
4201         return NULL;
4202 }
4203
4204 /* Project the given basic set onto its parameter domain, possibly introducing
4205  * new, explicit, existential variables in the constraints.
4206  * The input has parameters and (possibly implicit) existential variables.
4207  * The output has the same parameters, but only
4208  * explicit existentially quantified variables.
4209  *
4210  * The actual projection is performed by pip, but pip doesn't seem
4211  * to like equalities very much, so we first remove the equalities
4212  * among the parameters by performing a variable compression on
4213  * the parameters.  Afterward, an inverse transformation is performed
4214  * and the equalities among the parameters are inserted back in.
4215  */
4216 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
4217 {
4218         int i, j;
4219         struct isl_mat *eq;
4220         struct isl_mat *T, *T2;
4221         struct isl_set *set;
4222         unsigned nparam, n_div;
4223
4224         bset = isl_basic_set_cow(bset);
4225         if (!bset)
4226                 return NULL;
4227
4228         if (bset->n_eq == 0)
4229                 return isl_basic_set_lexmin(bset);
4230
4231         isl_basic_set_gauss(bset, NULL);
4232
4233         nparam = isl_basic_set_dim(bset, isl_dim_param);
4234         n_div = isl_basic_set_dim(bset, isl_dim_div);
4235
4236         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
4237                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
4238                         ++i;
4239         }
4240         if (i == bset->n_eq)
4241                 return isl_basic_set_lexmin(bset);
4242
4243         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
4244                 0, 1 + nparam);
4245         eq = isl_mat_cow(eq);
4246         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
4247         bset = basic_set_parameter_preimage(bset, T);
4248
4249         set = isl_basic_set_lexmin(bset);
4250         set = set_parameter_preimage(set, T2);
4251         set = set_append_equalities(set, eq);
4252         return set;
4253 }
4254
4255 /* Compute an explicit representation for all the existentially
4256  * quantified variables.
4257  * The input and output dimensions are first turned into parameters.
4258  * compute_divs then returns a map with the same parameters and
4259  * no input or output dimensions and the dimension specification
4260  * is reset to that of the input.
4261  */
4262 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
4263 {
4264         struct isl_basic_set *bset;
4265         struct isl_set *set;
4266         struct isl_map *map;
4267         struct isl_dim *dim, *orig_dim = NULL;
4268         unsigned         nparam;
4269         unsigned         n_in;
4270         unsigned         n_out;
4271
4272         bmap = isl_basic_map_cow(bmap);
4273         if (!bmap)
4274                 return NULL;
4275
4276         nparam = isl_basic_map_dim(bmap, isl_dim_param);
4277         n_in = isl_basic_map_dim(bmap, isl_dim_in);
4278         n_out = isl_basic_map_dim(bmap, isl_dim_out);
4279         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
4280         if (!dim)
4281                 goto error;
4282
4283         orig_dim = bmap->dim;
4284         bmap->dim = dim;
4285         bset = (struct isl_basic_set *)bmap;
4286
4287         set = parameter_compute_divs(bset);
4288         map = (struct isl_map *)set;
4289         map = isl_map_reset_dim(map, orig_dim);
4290
4291         return map;
4292 error:
4293         isl_basic_map_free(bmap);
4294         return NULL;
4295 }
4296
4297 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
4298 {
4299         int i;
4300         unsigned off;
4301
4302         if (!bmap)
4303                 return -1;
4304
4305         off = isl_dim_total(bmap->dim);
4306         for (i = 0; i < bmap->n_div; ++i) {
4307                 if (isl_int_is_zero(bmap->div[i][0]))
4308                         return 0;
4309                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
4310                                 return -1);
4311         }
4312         return 1;
4313 }
4314
4315 static int map_divs_known(__isl_keep isl_map *map)
4316 {
4317         int i;
4318
4319         if (!map)
4320                 return -1;
4321
4322         for (i = 0; i < map->n; ++i) {
4323                 int known = basic_map_divs_known(map->p[i]);
4324                 if (known <= 0)
4325                         return known;
4326         }
4327
4328         return 1;
4329 }
4330
4331 /* If bmap contains any unknown divs, then compute explicit
4332  * expressions for them.  However, this computation may be
4333  * quite expensive, so first try to remove divs that aren't
4334  * strictly needed.
4335  */
4336 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
4337 {
4338         int i;
4339         int known;
4340         struct isl_map *map;
4341
4342         known = basic_map_divs_known(bmap);
4343         if (known < 0)
4344                 goto error;
4345         if (known)
4346                 return isl_map_from_basic_map(bmap);
4347
4348         bmap = isl_basic_map_drop_redundant_divs(bmap);
4349
4350         known = basic_map_divs_known(bmap);
4351         if (known < 0)
4352                 goto error;
4353         if (known)
4354                 return isl_map_from_basic_map(bmap);
4355
4356         map = compute_divs(bmap);
4357         return map;
4358 error:
4359         isl_basic_map_free(bmap);
4360         return NULL;
4361 }
4362
4363 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4364 {
4365         int i;
4366         int known;
4367         struct isl_map *res;
4368
4369         if (!map)
4370                 return NULL;
4371         if (map->n == 0)
4372                 return map;
4373
4374         known = map_divs_known(map);
4375         if (known < 0) {
4376                 isl_map_free(map);
4377                 return NULL;
4378         }
4379         if (known)
4380                 return map;
4381
4382         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4383         for (i = 1 ; i < map->n; ++i) {
4384                 struct isl_map *r2;
4385                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4386                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4387                         res = isl_map_union_disjoint(res, r2);
4388                 else
4389                         res = isl_map_union(res, r2);
4390         }
4391         isl_map_free(map);
4392
4393         return res;
4394 }
4395
4396 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4397 {
4398         return (struct isl_set *)
4399                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4400 }
4401
4402 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4403 {
4404         return (struct isl_set *)
4405                 isl_map_compute_divs((struct isl_map *)set);
4406 }
4407
4408 struct isl_set *isl_map_domain(struct isl_map *map)
4409 {
4410         int i;
4411         struct isl_set *set;
4412
4413         if (!map)
4414                 goto error;
4415
4416         map = isl_map_cow(map);
4417         if (!map)
4418                 return NULL;
4419
4420         set = (struct isl_set *)map;
4421         set->dim = isl_dim_domain(set->dim);
4422         if (!set->dim)
4423                 goto error;
4424         for (i = 0; i < map->n; ++i) {
4425                 set->p[i] = isl_basic_map_domain(map->p[i]);
4426                 if (!set->p[i])
4427                         goto error;
4428         }
4429         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4430         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4431         return set;
4432 error:
4433         isl_map_free(map);
4434         return NULL;
4435 }
4436
4437 struct isl_map *isl_map_union_disjoint(
4438                         struct isl_map *map1, struct isl_map *map2)
4439 {
4440         int i;
4441         unsigned flags = 0;
4442         struct isl_map *map = NULL;
4443
4444         if (!map1 || !map2)
4445                 goto error;
4446
4447         if (map1->n == 0) {
4448                 isl_map_free(map1);
4449                 return map2;
4450         }
4451         if (map2->n == 0) {
4452                 isl_map_free(map2);
4453                 return map1;
4454         }
4455
4456         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4457
4458         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4459             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4460                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4461
4462         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4463                                 map1->n + map2->n, flags);
4464         if (!map)
4465                 goto error;
4466         for (i = 0; i < map1->n; ++i) {
4467                 map = isl_map_add_basic_map(map,
4468                                   isl_basic_map_copy(map1->p[i]));
4469                 if (!map)
4470                         goto error;
4471         }
4472         for (i = 0; i < map2->n; ++i) {
4473                 map = isl_map_add_basic_map(map,
4474                                   isl_basic_map_copy(map2->p[i]));
4475                 if (!map)
4476                         goto error;
4477         }
4478         isl_map_free(map1);
4479         isl_map_free(map2);
4480         return map;
4481 error:
4482         isl_map_free(map);
4483         isl_map_free(map1);
4484         isl_map_free(map2);
4485         return NULL;
4486 }
4487
4488 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4489 {
4490         map1 = isl_map_union_disjoint(map1, map2);
4491         if (!map1)
4492                 return NULL;
4493         if (map1->n > 1)
4494                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4495         return map1;
4496 }
4497
4498 struct isl_set *isl_set_union_disjoint(
4499                         struct isl_set *set1, struct isl_set *set2)
4500 {
4501         return (struct isl_set *)
4502                 isl_map_union_disjoint(
4503                         (struct isl_map *)set1, (struct isl_map *)set2);
4504 }
4505
4506 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4507 {
4508         return (struct isl_set *)
4509                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4510 }
4511
4512 struct isl_map *isl_map_intersect_range(
4513                 struct isl_map *map, struct isl_set *set)
4514 {
4515         unsigned flags = 0;
4516         struct isl_map *result;
4517         int i, j;
4518
4519         if (!map || !set)
4520                 goto error;
4521
4522         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4523             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4524                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4525
4526         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4527                                         map->n * set->n, flags);
4528         if (!result)
4529                 goto error;
4530         for (i = 0; i < map->n; ++i)
4531                 for (j = 0; j < set->n; ++j) {
4532                         result = isl_map_add_basic_map(result,
4533                             isl_basic_map_intersect_range(
4534                                 isl_basic_map_copy(map->p[i]),
4535                                 isl_basic_set_copy(set->p[j])));
4536                         if (!result)
4537                                 goto error;
4538                 }
4539         isl_map_free(map);
4540         isl_set_free(set);
4541         return result;
4542 error:
4543         isl_map_free(map);
4544         isl_set_free(set);
4545         return NULL;
4546 }
4547
4548 struct isl_map *isl_map_intersect_domain(
4549                 struct isl_map *map, struct isl_set *set)
4550 {
4551         return isl_map_reverse(
4552                 isl_map_intersect_range(isl_map_reverse(map), set));
4553 }
4554
4555 struct isl_map *isl_map_apply_domain(
4556                 struct isl_map *map1, struct isl_map *map2)
4557 {
4558         if (!map1 || !map2)
4559                 goto error;
4560         map1 = isl_map_reverse(map1);
4561         map1 = isl_map_apply_range(map1, map2);
4562         return isl_map_reverse(map1);
4563 error:
4564         isl_map_free(map1);
4565         isl_map_free(map2);
4566         return NULL;
4567 }
4568
4569 struct isl_map *isl_map_apply_range(
4570                 struct isl_map *map1, struct isl_map *map2)
4571 {
4572         struct isl_dim *dim_result;
4573         struct isl_map *result;
4574         int i, j;
4575
4576         if (!map1 || !map2)
4577                 goto error;
4578
4579         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4580                                   isl_dim_copy(map2->dim));
4581
4582         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4583         if (!result)
4584                 goto error;
4585         for (i = 0; i < map1->n; ++i)
4586                 for (j = 0; j < map2->n; ++j) {
4587                         result = isl_map_add_basic_map(result,
4588                             isl_basic_map_apply_range(
4589                                 isl_basic_map_copy(map1->p[i]),
4590                                 isl_basic_map_copy(map2->p[j])));
4591                         if (!result)
4592                                 goto error;
4593                 }
4594         isl_map_free(map1);
4595         isl_map_free(map2);
4596         if (result && result->n <= 1)
4597                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4598         return result;
4599 error:
4600         isl_map_free(map1);
4601         isl_map_free(map2);
4602         return NULL;
4603 }
4604
4605 /*
4606  * returns range - domain
4607  */
4608 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4609 {
4610         struct isl_basic_set *bset;
4611         unsigned dim;
4612         unsigned nparam;
4613         int i;
4614
4615         if (!bmap)
4616                 goto error;
4617         dim = isl_basic_map_n_in(bmap);
4618         nparam = isl_basic_map_n_param(bmap);
4619         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4620         bset = isl_basic_set_from_basic_map(bmap);
4621         bset = isl_basic_set_cow(bset);
4622         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
4623         bset = isl_basic_set_swap_vars(bset, 2*dim);
4624         for (i = 0; i < dim; ++i) {
4625                 int j = isl_basic_map_alloc_equality(
4626                                             (struct isl_basic_map *)bset);
4627                 if (j < 0)
4628                         goto error;
4629                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4630                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4631                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4632                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4633         }
4634         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4635 error:
4636         isl_basic_map_free(bmap);
4637         return NULL;
4638 }
4639
4640 /*
4641  * returns range - domain
4642  */
4643 struct isl_set *isl_map_deltas(struct isl_map *map)
4644 {
4645         int i;
4646         struct isl_set *result;
4647
4648         if (!map)
4649                 return NULL;
4650
4651         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4652         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
4653                                         isl_map_n_in(map), map->n, map->flags);
4654         if (!result)
4655                 goto error;
4656         for (i = 0; i < map->n; ++i)
4657                 result = isl_set_add_basic_set(result,
4658                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4659         isl_map_free(map);
4660         return result;
4661 error:
4662         isl_map_free(map);
4663         return NULL;
4664 }
4665
4666 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4667 {
4668         struct isl_basic_map *bmap;
4669         unsigned nparam;
4670         unsigned dim;
4671         int i;
4672
4673         if (!dims)
4674                 return NULL;
4675
4676         nparam = dims->nparam;
4677         dim = dims->n_out;
4678         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4679         if (!bmap)
4680                 goto error;
4681
4682         for (i = 0; i < dim; ++i) {
4683                 int j = isl_basic_map_alloc_equality(bmap);
4684                 if (j < 0)
4685                         goto error;
4686                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4687                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
4688                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
4689         }
4690         return isl_basic_map_finalize(bmap);
4691 error:
4692         isl_basic_map_free(bmap);
4693         return NULL;
4694 }
4695
4696 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
4697 {
4698         struct isl_dim *dim = isl_dim_map(set_dim);
4699         if (!dim)
4700                 return NULL;
4701         return basic_map_identity(dim);
4702 }
4703
4704 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
4705 {
4706         if (!model || !model->dim)
4707                 return NULL;
4708         isl_assert(model->ctx,
4709                         model->dim->n_in == model->dim->n_out, return NULL);
4710         return basic_map_identity(isl_dim_copy(model->dim));
4711 }
4712
4713 static struct isl_map *map_identity(struct isl_dim *dim)
4714 {
4715         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
4716         return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim)));
4717 }
4718
4719 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
4720 {
4721         struct isl_dim *dim = isl_dim_map(set_dim);
4722         if (!dim)
4723                 return NULL;
4724         return map_identity(dim);
4725 }
4726
4727 struct isl_map *isl_map_identity_like(struct isl_map *model)
4728 {
4729         if (!model || !model->dim)
4730                 return NULL;
4731         isl_assert(model->ctx,
4732                         model->dim->n_in == model->dim->n_out, return NULL);
4733         return map_identity(isl_dim_copy(model->dim));
4734 }
4735
4736 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
4737 {
4738         if (!model || !model->dim)
4739                 return NULL;
4740         isl_assert(model->ctx,
4741                         model->dim->n_in == model->dim->n_out, return NULL);
4742         return map_identity(isl_dim_copy(model->dim));
4743 }
4744
4745 /* Construct a basic set with all set dimensions having only non-negative
4746  * values.
4747  */
4748 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
4749 {
4750         int i;
4751         unsigned nparam;
4752         unsigned dim;
4753         struct isl_basic_set *bset;
4754
4755         if (!dims)
4756                 return NULL;
4757         nparam = dims->nparam;
4758         dim = dims->n_out;
4759         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
4760         if (!bset)
4761                 return NULL;
4762         for (i = 0; i < dim; ++i) {
4763                 int k = isl_basic_set_alloc_inequality(bset);
4764                 if (k < 0)
4765                         goto error;
4766                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
4767                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
4768         }
4769         return bset;
4770 error:
4771         isl_basic_set_free(bset);
4772         return NULL;
4773 }
4774
4775 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
4776 {
4777         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
4778 }
4779
4780 int isl_basic_map_is_subset(
4781                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4782 {
4783         int is_subset;
4784         struct isl_map *map1;
4785         struct isl_map *map2;
4786
4787         if (!bmap1 || !bmap2)
4788                 return -1;
4789
4790         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
4791         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
4792
4793         is_subset = isl_map_is_subset(map1, map2);
4794
4795         isl_map_free(map1);
4796         isl_map_free(map2);
4797
4798         return is_subset;
4799 }
4800
4801 int isl_basic_map_is_equal(
4802                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4803 {
4804         int is_subset;
4805
4806         if (!bmap1 || !bmap2)
4807                 return -1;
4808         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4809         if (is_subset != 1)
4810                 return is_subset;
4811         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4812         return is_subset;
4813 }
4814
4815 int isl_basic_set_is_equal(
4816                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4817 {
4818         return isl_basic_map_is_equal(
4819                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4820 }
4821
4822 int isl_map_is_empty(struct isl_map *map)
4823 {
4824         int i;
4825         int is_empty;
4826
4827         if (!map)
4828                 return -1;
4829         for (i = 0; i < map->n; ++i) {
4830                 is_empty = isl_basic_map_is_empty(map->p[i]);
4831                 if (is_empty < 0)
4832                         return -1;
4833                 if (!is_empty)
4834                         return 0;
4835         }
4836         return 1;
4837 }
4838
4839 int isl_map_fast_is_empty(struct isl_map *map)
4840 {
4841         return map->n == 0;
4842 }
4843
4844 int isl_set_fast_is_empty(struct isl_set *set)
4845 {
4846         return set->n == 0;
4847 }
4848
4849 int isl_set_is_empty(struct isl_set *set)
4850 {
4851         return isl_map_is_empty((struct isl_map *)set);
4852 }
4853
4854 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4855 {
4856         int is_subset;
4857
4858         if (!map1 || !map2)
4859                 return -1;
4860         is_subset = isl_map_is_subset(map1, map2);
4861         if (is_subset != 1)
4862                 return is_subset;
4863         is_subset = isl_map_is_subset(map2, map1);
4864         return is_subset;
4865 }
4866
4867 int isl_basic_map_is_strict_subset(
4868                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4869 {
4870         int is_subset;
4871
4872         if (!bmap1 || !bmap2)
4873                 return -1;
4874         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4875         if (is_subset != 1)
4876                 return is_subset;
4877         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4878         if (is_subset == -1)
4879                 return is_subset;
4880         return !is_subset;
4881 }
4882
4883 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
4884 {
4885         int is_subset;
4886
4887         if (!map1 || !map2)
4888                 return -1;
4889         is_subset = isl_map_is_subset(map1, map2);
4890         if (is_subset != 1)
4891                 return is_subset;
4892         is_subset = isl_map_is_subset(map2, map1);
4893         if (is_subset == -1)
4894                 return is_subset;
4895         return !is_subset;
4896 }
4897
4898 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
4899 {
4900         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
4901 }
4902
4903 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4904 {
4905         if (!bmap)
4906                 return -1;
4907         return bmap->n_eq == 0 && bmap->n_ineq == 0;
4908 }
4909
4910 int isl_basic_set_is_universe(struct isl_basic_set *bset)
4911 {
4912         if (!bset)
4913                 return -1;
4914         return bset->n_eq == 0 && bset->n_ineq == 0;
4915 }
4916
4917 int isl_map_fast_is_universe(__isl_keep isl_map *map)
4918 {
4919         if (!map)
4920                 return -1;
4921
4922         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
4923 }
4924
4925 int isl_set_fast_is_universe(__isl_keep isl_set *set)
4926 {
4927         return isl_map_fast_is_universe((isl_map *) set);
4928 }
4929
4930 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4931 {
4932         struct isl_basic_set *bset = NULL;
4933         struct isl_vec *sample = NULL;
4934         int empty;
4935         unsigned total;
4936
4937         if (!bmap)
4938                 return -1;
4939
4940         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4941                 return 1;
4942
4943         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4944                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4945                 copy = isl_basic_map_convex_hull(copy);
4946                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4947                 isl_basic_map_free(copy);
4948                 return empty;
4949         }
4950
4951         total = 1 + isl_basic_map_total_dim(bmap);
4952         if (bmap->sample && bmap->sample->size == total) {
4953                 int contains = isl_basic_map_contains(bmap, bmap->sample);
4954                 if (contains < 0)
4955                         return -1;
4956                 if (contains)
4957                         return 0;
4958         }
4959         isl_vec_free(bmap->sample);
4960         bmap->sample = NULL;
4961         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4962         if (!bset)
4963                 return -1;
4964         sample = isl_basic_set_sample_vec(bset);
4965         if (!sample)
4966                 return -1;
4967         empty = sample->size == 0;
4968         isl_vec_free(bmap->sample);
4969         bmap->sample = sample;
4970         if (empty)
4971                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
4972
4973         return empty;
4974 }
4975
4976 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
4977 {
4978         if (!bmap)
4979                 return -1;
4980         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
4981 }
4982
4983 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
4984 {
4985         if (!bset)
4986                 return -1;
4987         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
4988 }
4989
4990 int isl_basic_set_is_empty(struct isl_basic_set *bset)
4991 {
4992         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
4993 }
4994
4995 struct isl_map *isl_basic_map_union(
4996         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4997 {
4998         struct isl_map *map;
4999         if (!bmap1 || !bmap2)
5000                 return NULL;
5001
5002         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
5003
5004         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
5005         if (!map)
5006                 goto error;
5007         map = isl_map_add_basic_map(map, bmap1);
5008         map = isl_map_add_basic_map(map, bmap2);
5009         return map;
5010 error:
5011         isl_basic_map_free(bmap1);
5012         isl_basic_map_free(bmap2);
5013         return NULL;
5014 }
5015
5016 struct isl_set *isl_basic_set_union(
5017                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5018 {
5019         return (struct isl_set *)isl_basic_map_union(
5020                                             (struct isl_basic_map *)bset1,
5021                                             (struct isl_basic_map *)bset2);
5022 }
5023
5024 /* Order divs such that any div only depends on previous divs */
5025 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
5026 {
5027         int i;
5028         unsigned off = isl_dim_total(bmap->dim);
5029
5030         for (i = 0; i < bmap->n_div; ++i) {
5031                 int pos;
5032                 if (isl_int_is_zero(bmap->div[i][0]))
5033                         continue;
5034                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
5035                                                             bmap->n_div-i);
5036                 if (pos == -1)
5037                         continue;
5038                 isl_basic_map_swap_div(bmap, i, i + pos);
5039                 --i;
5040         }
5041         return bmap;
5042 }
5043
5044 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
5045 {
5046         return (struct isl_basic_set *)
5047                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
5048 }
5049
5050 __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
5051 {
5052         int i;
5053
5054         if (!map)
5055                 return 0;
5056
5057         for (i = 0; i < map->n; ++i) {
5058                 map->p[i] = isl_basic_map_order_divs(map->p[i]);
5059                 if (!map->p[i])
5060                         goto error;
5061         }
5062
5063         return map;
5064 error:
5065         isl_map_free(map);
5066         return NULL;
5067 }
5068
5069 /* Look for a div in dst that corresponds to the div "div" in src.
5070  * The divs before "div" in src and dst are assumed to be the same.
5071  *
5072  * Returns -1 if no corresponding div was found and the position
5073  * of the corresponding div in dst otherwise.
5074  */
5075 static int find_div(struct isl_basic_map *dst,
5076                         struct isl_basic_map *src, unsigned div)
5077 {
5078         int i;
5079
5080         unsigned total = isl_dim_total(src->dim);
5081
5082         isl_assert(dst->ctx, div <= dst->n_div, return -1);
5083         for (i = div; i < dst->n_div; ++i)
5084                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
5085                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
5086                                                 dst->n_div - div) == -1)
5087                         return i;
5088         return -1;
5089 }
5090
5091 struct isl_basic_map *isl_basic_map_align_divs(
5092                 struct isl_basic_map *dst, struct isl_basic_map *src)
5093 {
5094         int i;
5095         unsigned total = isl_dim_total(src->dim);
5096
5097         if (!dst || !src)
5098                 goto error;
5099
5100         if (src->n_div == 0)
5101                 return dst;
5102
5103         for (i = 0; i < src->n_div; ++i)
5104                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
5105
5106         src = isl_basic_map_order_divs(src);
5107         dst = isl_basic_map_cow(dst);
5108         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
5109                         src->n_div, 0, 2 * src->n_div);
5110         if (!dst)
5111                 return NULL;
5112         for (i = 0; i < src->n_div; ++i) {
5113                 int j = find_div(dst, src, i);
5114                 if (j < 0) {
5115                         j = isl_basic_map_alloc_div(dst);
5116                         if (j < 0)
5117                                 goto error;
5118                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
5119                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
5120                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
5121                                 goto error;
5122                 }
5123                 if (j != i)
5124                         isl_basic_map_swap_div(dst, i, j);
5125         }
5126         return dst;
5127 error:
5128         isl_basic_map_free(dst);
5129         return NULL;
5130 }
5131
5132 struct isl_basic_set *isl_basic_set_align_divs(
5133                 struct isl_basic_set *dst, struct isl_basic_set *src)
5134 {
5135         return (struct isl_basic_set *)isl_basic_map_align_divs(
5136                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
5137 }
5138
5139 struct isl_map *isl_map_align_divs(struct isl_map *map)
5140 {
5141         int i;
5142
5143         if (!map)
5144                 return NULL;
5145         if (map->n == 0)
5146                 return map;
5147         map = isl_map_compute_divs(map);
5148         map = isl_map_cow(map);
5149         if (!map)
5150                 return NULL;
5151
5152         for (i = 1; i < map->n; ++i)
5153                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
5154         for (i = 1; i < map->n; ++i)
5155                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
5156
5157         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5158         return map;
5159 }
5160
5161 struct isl_set *isl_set_align_divs(struct isl_set *set)
5162 {
5163         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
5164 }
5165
5166 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
5167 {
5168         if (!set || !map)
5169                 goto error;
5170         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
5171         map = isl_map_intersect_domain(map, set);
5172         set = isl_map_range(map);
5173         return set;
5174 error:
5175         isl_set_free(set);
5176         isl_map_free(map);
5177         return NULL;
5178 }
5179
5180 /* There is no need to cow as removing empty parts doesn't change
5181  * the meaning of the set.
5182  */
5183 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
5184 {
5185         int i;
5186
5187         if (!map)
5188                 return NULL;
5189
5190         for (i = map->n-1; i >= 0; --i) {
5191                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
5192                         continue;
5193                 isl_basic_map_free(map->p[i]);
5194                 if (i != map->n-1) {
5195                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5196                         map->p[i] = map->p[map->n-1];
5197                 }
5198                 map->n--;
5199         }
5200
5201         return map;
5202 }
5203
5204 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
5205 {
5206         return (struct isl_set *)
5207                 isl_map_remove_empty_parts((struct isl_map *)set);
5208 }
5209
5210 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
5211 {
5212         struct isl_basic_map *bmap;
5213         if (!map || map->n == 0)
5214                 return NULL;
5215         bmap = map->p[map->n-1];
5216         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
5217         return isl_basic_map_copy(bmap);
5218 }
5219
5220 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
5221 {
5222         return (struct isl_basic_set *)
5223                 isl_map_copy_basic_map((struct isl_map *)set);
5224 }
5225
5226 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
5227                                                 __isl_keep isl_basic_map *bmap)
5228 {
5229         int i;
5230
5231         if (!map || !bmap)
5232                 goto error;
5233         for (i = map->n-1; i >= 0; --i) {
5234                 if (map->p[i] != bmap)
5235                         continue;
5236                 map = isl_map_cow(map);
5237                 if (!map)
5238                         goto error;
5239                 isl_basic_map_free(map->p[i]);
5240                 if (i != map->n-1) {
5241                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
5242                         map->p[i] = map->p[map->n-1];
5243                 }
5244                 map->n--;
5245                 return map;
5246         }
5247         return map;
5248 error:
5249         isl_map_free(map);
5250         return NULL;
5251 }
5252
5253 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
5254                                                 struct isl_basic_set *bset)
5255 {
5256         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
5257                                                 (struct isl_basic_map *)bset);
5258 }
5259
5260 /* Given two basic sets bset1 and bset2, compute the maximal difference
5261  * between the values of dimension pos in bset1 and those in bset2
5262  * for any common value of the parameters and dimensions preceding pos.
5263  */
5264 static enum isl_lp_result basic_set_maximal_difference_at(
5265         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
5266         int pos, isl_int *opt)
5267 {
5268         struct isl_dim *dims;
5269         struct isl_basic_map *bmap1 = NULL;
5270         struct isl_basic_map *bmap2 = NULL;
5271         struct isl_ctx *ctx;
5272         struct isl_vec *obj;
5273         unsigned total;
5274         unsigned nparam;
5275         unsigned dim1, dim2;
5276         enum isl_lp_result res;
5277
5278         if (!bset1 || !bset2)
5279                 return isl_lp_error;
5280
5281         nparam = isl_basic_set_n_param(bset1);
5282         dim1 = isl_basic_set_n_dim(bset1);
5283         dim2 = isl_basic_set_n_dim(bset2);
5284         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
5285         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
5286         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
5287         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
5288         if (!bmap1 || !bmap2)
5289                 goto error;
5290         bmap1 = isl_basic_map_cow(bmap1);
5291         bmap1 = isl_basic_map_extend(bmap1, nparam,
5292                         pos, (dim1 - pos) + (dim2 - pos),
5293                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
5294         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
5295         if (!bmap1)
5296                 goto error;
5297         total = isl_basic_map_total_dim(bmap1);
5298         ctx = bmap1->ctx;
5299         obj = isl_vec_alloc(ctx, 1 + total);
5300         isl_seq_clr(obj->block.data, 1 + total);
5301         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
5302         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
5303         if (!obj)
5304                 goto error;
5305         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
5306                                         opt, NULL, NULL);
5307         isl_basic_map_free(bmap1);
5308         isl_vec_free(obj);
5309         return res;
5310 error:
5311         isl_basic_map_free(bmap1);
5312         isl_basic_map_free(bmap2);
5313         return isl_lp_error;
5314 }
5315
5316 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
5317  * for any common value of the parameters and dimensions preceding pos
5318  * in both basic sets, the values of dimension pos in bset1 are
5319  * smaller or larger than those in bset2.
5320  *
5321  * Returns
5322  *       1 if bset1 follows bset2
5323  *      -1 if bset1 precedes bset2
5324  *       0 if bset1 and bset2 are incomparable
5325  *      -2 if some error occurred.
5326  */
5327 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
5328         struct isl_basic_set *bset2, int pos)
5329 {
5330         isl_int opt;
5331         enum isl_lp_result res;
5332         int cmp;
5333
5334         isl_int_init(opt);
5335
5336         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5337
5338         if (res == isl_lp_empty)
5339                 cmp = 0;
5340         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5341                   res == isl_lp_unbounded)
5342                 cmp = 1;
5343         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5344                 cmp = -1;
5345         else
5346                 cmp = -2;
5347
5348         isl_int_clear(opt);
5349         return cmp;
5350 }
5351
5352 /* Given two basic sets bset1 and bset2, check whether
5353  * for any common value of the parameters and dimensions preceding pos
5354  * there is a value of dimension pos in bset1 that is larger
5355  * than a value of the same dimension in bset2.
5356  *
5357  * Return
5358  *       1 if there exists such a pair
5359  *       0 if there is no such pair, but there is a pair of equal values
5360  *      -1 otherwise
5361  *      -2 if some error occurred.
5362  */
5363 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
5364         __isl_keep isl_basic_set *bset2, int pos)
5365 {
5366         isl_int opt;
5367         enum isl_lp_result res;
5368         int cmp;
5369
5370         isl_int_init(opt);
5371
5372         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5373
5374         if (res == isl_lp_empty)
5375                 cmp = -1;
5376         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5377                   res == isl_lp_unbounded)
5378                 cmp = 1;
5379         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5380                 cmp = -1;
5381         else if (res == isl_lp_ok)
5382                 cmp = 0;
5383         else
5384                 cmp = -2;
5385
5386         isl_int_clear(opt);
5387         return cmp;
5388 }
5389
5390 /* Given two sets set1 and set2, check whether
5391  * for any common value of the parameters and dimensions preceding pos
5392  * there is a value of dimension pos in set1 that is larger
5393  * than a value of the same dimension in set2.
5394  *
5395  * Return
5396  *       1 if there exists such a pair
5397  *       0 if there is no such pair, but there is a pair of equal values
5398  *      -1 otherwise
5399  *      -2 if some error occurred.
5400  */
5401 int isl_set_follows_at(__isl_keep isl_set *set1,
5402         __isl_keep isl_set *set2, int pos)
5403 {
5404         int i, j;
5405         int follows = -1;
5406
5407         if (!set1 || !set2)
5408                 return -2;
5409
5410         for (i = 0; i < set1->n; ++i)
5411                 for (j = 0; j < set2->n; ++j) {
5412                         int f;
5413                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5414                         if (f == 1 || f == -2)
5415                                 return f;
5416                         if (f > follows)
5417                                 follows = f;
5418                 }
5419
5420         return follows;
5421 }
5422
5423 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5424         unsigned pos, isl_int *val)
5425 {
5426         int i;
5427         int d;
5428         unsigned total;
5429
5430         if (!bmap)
5431                 return -1;
5432         total = isl_basic_map_total_dim(bmap);
5433         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5434                 for (; d+1 > pos; --d)
5435                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5436                                 break;
5437                 if (d != pos)
5438                         continue;
5439                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5440                         return 0;
5441                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5442                         return 0;
5443                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5444                         return 0;
5445                 if (val)
5446                         isl_int_neg(*val, bmap->eq[i][0]);
5447                 return 1;
5448         }
5449         return 0;
5450 }
5451
5452 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5453         unsigned pos, isl_int *val)
5454 {
5455         int i;
5456         isl_int v;
5457         isl_int tmp;
5458         int fixed;
5459
5460         if (!map)
5461                 return -1;
5462         if (map->n == 0)
5463                 return 0;
5464         if (map->n == 1)
5465                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5466         isl_int_init(v);
5467         isl_int_init(tmp);
5468         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5469         for (i = 1; fixed == 1 && i < map->n; ++i) {
5470                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5471                 if (fixed == 1 && isl_int_ne(tmp, v))
5472                         fixed = 0;
5473         }
5474         if (val)
5475                 isl_int_set(*val, v);
5476         isl_int_clear(tmp);
5477         isl_int_clear(v);
5478         return fixed;
5479 }
5480
5481 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5482         unsigned pos, isl_int *val)
5483 {
5484         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5485                                                 pos, val);
5486 }
5487
5488 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5489         isl_int *val)
5490 {
5491         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5492 }
5493
5494 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5495         enum isl_dim_type type, unsigned pos, isl_int *val)
5496 {
5497         if (pos >= isl_basic_map_dim(bmap, type))
5498                 return -1;
5499         return isl_basic_map_fast_has_fixed_var(bmap,
5500                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
5501 }
5502
5503 int isl_map_fast_is_fixed(struct isl_map *map,
5504         enum isl_dim_type type, unsigned pos, isl_int *val)
5505 {
5506         if (pos >= isl_map_dim(map, type))
5507                 return -1;
5508         return isl_map_fast_has_fixed_var(map,
5509                 map_offset(map, type) - 1 + pos, val);
5510 }
5511
5512 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5513  * then return this fixed value in *val.
5514  */
5515 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
5516         isl_int *val)
5517 {
5518         return isl_basic_set_fast_has_fixed_var(bset,
5519                                         isl_basic_set_n_param(bset) + dim, val);
5520 }
5521
5522 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5523  * then return this fixed value in *val.
5524  */
5525 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
5526 {
5527         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
5528 }
5529
5530 /* Check if input variable in has fixed value and if so and if val is not NULL,
5531  * then return this fixed value in *val.
5532  */
5533 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
5534 {
5535         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
5536 }
5537
5538 /* Check if dimension dim has an (obvious) fixed lower bound and if so
5539  * and if val is not NULL, then return this lower bound in *val.
5540  */
5541 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
5542         unsigned dim, isl_int *val)
5543 {
5544         int i, i_eq = -1, i_ineq = -1;
5545         isl_int *c;
5546         unsigned total;
5547         unsigned nparam;
5548
5549         if (!bset)
5550                 return -1;
5551         total = isl_basic_set_total_dim(bset);
5552         nparam = isl_basic_set_n_param(bset);
5553         for (i = 0; i < bset->n_eq; ++i) {
5554                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
5555                         continue;
5556                 if (i_eq != -1)
5557                         return 0;
5558                 i_eq = i;
5559         }
5560         for (i = 0; i < bset->n_ineq; ++i) {
5561                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
5562                         continue;
5563                 if (i_eq != -1 || i_ineq != -1)
5564                         return 0;
5565                 i_ineq = i;
5566         }
5567         if (i_eq == -1 && i_ineq == -1)
5568                 return 0;
5569         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
5570         /* The coefficient should always be one due to normalization. */
5571         if (!isl_int_is_one(c[1+nparam+dim]))
5572                 return 0;
5573         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
5574                 return 0;
5575         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
5576                                         total - nparam - dim - 1) != -1)
5577                 return 0;
5578         if (val)
5579                 isl_int_neg(*val, c[0]);
5580         return 1;
5581 }
5582
5583 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
5584         unsigned dim, isl_int *val)
5585 {
5586         int i;
5587         isl_int v;
5588         isl_int tmp;
5589         int fixed;
5590
5591         if (!set)
5592                 return -1;
5593         if (set->n == 0)
5594                 return 0;
5595         if (set->n == 1)
5596                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5597                                                                 dim, val);
5598         isl_int_init(v);
5599         isl_int_init(tmp);
5600         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5601                                                                 dim, &v);
5602         for (i = 1; fixed == 1 && i < set->n; ++i) {
5603                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5604                                                                 dim, &tmp);
5605                 if (fixed == 1 && isl_int_ne(tmp, v))
5606                         fixed = 0;
5607         }
5608         if (val)
5609                 isl_int_set(*val, v);
5610         isl_int_clear(tmp);
5611         isl_int_clear(v);
5612         return fixed;
5613 }
5614
5615 struct constraint {
5616         unsigned        size;
5617         isl_int         *c;
5618 };
5619
5620 static int qsort_constraint_cmp(const void *p1, const void *p2)
5621 {
5622         const struct constraint *c1 = (const struct constraint *)p1;
5623         const struct constraint *c2 = (const struct constraint *)p2;
5624         unsigned size = isl_min(c1->size, c2->size);
5625         return isl_seq_cmp(c1->c, c2->c, size);
5626 }
5627
5628 static struct isl_basic_map *isl_basic_map_sort_constraints(
5629         struct isl_basic_map *bmap)
5630 {
5631         int i;
5632         struct constraint *c;
5633         unsigned total;
5634
5635         if (!bmap)
5636                 return NULL;
5637         total = isl_basic_map_total_dim(bmap);
5638         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5639         if (!c)
5640                 goto error;
5641         for (i = 0; i < bmap->n_ineq; ++i) {
5642                 c[i].size = total;
5643                 c[i].c = bmap->ineq[i];
5644         }
5645         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5646         for (i = 0; i < bmap->n_ineq; ++i)
5647                 bmap->ineq[i] = c[i].c;
5648         free(c);
5649         return bmap;
5650 error:
5651         isl_basic_map_free(bmap);
5652         return NULL;
5653 }
5654
5655 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5656 {
5657         if (!bmap)
5658                 return NULL;
5659         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5660                 return bmap;
5661         bmap = isl_basic_map_convex_hull(bmap);
5662         bmap = isl_basic_map_sort_constraints(bmap);
5663         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5664         return bmap;
5665 }
5666
5667 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5668 {
5669         return (struct isl_basic_set *)isl_basic_map_normalize(
5670                                                 (struct isl_basic_map *)bset);
5671 }
5672
5673 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5674         const struct isl_basic_map *bmap2)
5675 {
5676         int i, cmp;
5677         unsigned total;
5678
5679         if (bmap1 == bmap2)
5680                 return 0;
5681         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5682                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5683         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5684                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5685         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5686                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5687         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5688             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5689                 return 0;
5690         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5691                 return 1;
5692         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5693                 return -1;
5694         if (bmap1->n_eq != bmap2->n_eq)
5695                 return bmap1->n_eq - bmap2->n_eq;
5696         if (bmap1->n_ineq != bmap2->n_ineq)
5697                 return bmap1->n_ineq - bmap2->n_ineq;
5698         if (bmap1->n_div != bmap2->n_div)
5699                 return bmap1->n_div - bmap2->n_div;
5700         total = isl_basic_map_total_dim(bmap1);
5701         for (i = 0; i < bmap1->n_eq; ++i) {
5702                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5703                 if (cmp)
5704                         return cmp;
5705         }
5706         for (i = 0; i < bmap1->n_ineq; ++i) {
5707                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5708                 if (cmp)
5709                         return cmp;
5710         }
5711         for (i = 0; i < bmap1->n_div; ++i) {
5712                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5713                 if (cmp)
5714                         return cmp;
5715         }
5716         return 0;
5717 }
5718
5719 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5720         struct isl_basic_map *bmap2)
5721 {
5722         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5723 }
5724
5725 static int qsort_bmap_cmp(const void *p1, const void *p2)
5726 {
5727         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5728         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5729
5730         return isl_basic_map_fast_cmp(bmap1, bmap2);
5731 }
5732
5733 /* We normalize in place, but if anything goes wrong we need
5734  * to return NULL, so we need to make sure we don't change the
5735  * meaning of any possible other copies of map.
5736  */
5737 struct isl_map *isl_map_normalize(struct isl_map *map)
5738 {
5739         int i, j;
5740         struct isl_basic_map *bmap;
5741
5742         if (!map)
5743                 return NULL;
5744         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
5745                 return map;
5746         for (i = 0; i < map->n; ++i) {
5747                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5748                 if (!bmap)
5749                         goto error;
5750                 isl_basic_map_free(map->p[i]);
5751                 map->p[i] = bmap;
5752         }
5753         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5754         ISL_F_SET(map, ISL_MAP_NORMALIZED);
5755         map = isl_map_remove_empty_parts(map);
5756         if (!map)
5757                 return NULL;
5758         for (i = map->n - 1; i >= 1; --i) {
5759                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5760                         continue;
5761                 isl_basic_map_free(map->p[i-1]);
5762                 for (j = i; j < map->n; ++j)
5763                         map->p[j-1] = map->p[j];
5764                 map->n--;
5765         }
5766         return map;
5767 error:
5768         isl_map_free(map);
5769         return NULL;
5770
5771 }
5772
5773 struct isl_set *isl_set_normalize(struct isl_set *set)
5774 {
5775         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5776 }
5777
5778 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5779 {
5780         int i;
5781         int equal;
5782
5783         if (!map1 || !map2)
5784                 return -1;
5785
5786         if (map1 == map2)
5787                 return 1;
5788         if (!isl_dim_equal(map1->dim, map2->dim))
5789                 return 0;
5790
5791         map1 = isl_map_copy(map1);
5792         map2 = isl_map_copy(map2);
5793         map1 = isl_map_normalize(map1);
5794         map2 = isl_map_normalize(map2);
5795         if (!map1 || !map2)
5796                 goto error;
5797         equal = map1->n == map2->n;
5798         for (i = 0; equal && i < map1->n; ++i) {
5799                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5800                 if (equal < 0)
5801                         goto error;
5802         }
5803         isl_map_free(map1);
5804         isl_map_free(map2);
5805         return equal;
5806 error:
5807         isl_map_free(map1);
5808         isl_map_free(map2);
5809         return -1;
5810 }
5811
5812 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5813 {
5814         return isl_map_fast_is_equal((struct isl_map *)set1,
5815                                                 (struct isl_map *)set2);
5816 }
5817
5818 /* Return an interval that ranges from min to max (inclusive)
5819  */
5820 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5821         isl_int min, isl_int max)
5822 {
5823         int k;
5824         struct isl_basic_set *bset = NULL;
5825
5826         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5827         if (!bset)
5828                 goto error;
5829
5830         k = isl_basic_set_alloc_inequality(bset);
5831         if (k < 0)
5832                 goto error;
5833         isl_int_set_si(bset->ineq[k][1], 1);
5834         isl_int_neg(bset->ineq[k][0], min);
5835
5836         k = isl_basic_set_alloc_inequality(bset);
5837         if (k < 0)
5838                 goto error;
5839         isl_int_set_si(bset->ineq[k][1], -1);
5840         isl_int_set(bset->ineq[k][0], max);
5841
5842         return bset;
5843 error:
5844         isl_basic_set_free(bset);
5845         return NULL;
5846 }
5847
5848 /* Return the Cartesian product of the basic sets in list (in the given order).
5849  */
5850 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5851 {
5852         int i;
5853         unsigned dim;
5854         unsigned nparam;
5855         unsigned extra;
5856         unsigned n_eq;
5857         unsigned n_ineq;
5858         struct isl_basic_set *product = NULL;
5859
5860         if (!list)
5861                 goto error;
5862         isl_assert(list->ctx, list->n > 0, goto error);
5863         isl_assert(list->ctx, list->p[0], goto error);
5864         nparam = isl_basic_set_n_param(list->p[0]);
5865         dim = isl_basic_set_n_dim(list->p[0]);
5866         extra = list->p[0]->n_div;
5867         n_eq = list->p[0]->n_eq;
5868         n_ineq = list->p[0]->n_ineq;
5869         for (i = 1; i < list->n; ++i) {
5870                 isl_assert(list->ctx, list->p[i], goto error);
5871                 isl_assert(list->ctx,
5872                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5873                 dim += isl_basic_set_n_dim(list->p[i]);
5874                 extra += list->p[i]->n_div;
5875                 n_eq += list->p[i]->n_eq;
5876                 n_ineq += list->p[i]->n_ineq;
5877         }
5878         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5879                                         n_eq, n_ineq);
5880         if (!product)
5881                 goto error;
5882         dim = 0;
5883         for (i = 0; i < list->n; ++i) {
5884                 isl_basic_set_add_constraints(product,
5885                                         isl_basic_set_copy(list->p[i]), dim);
5886                 dim += isl_basic_set_n_dim(list->p[i]);
5887         }
5888         isl_basic_set_list_free(list);
5889         return product;
5890 error:
5891         isl_basic_set_free(product);
5892         isl_basic_set_list_free(list);
5893         return NULL;
5894 }
5895
5896 struct isl_basic_map *isl_basic_map_product(
5897                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5898 {
5899         struct isl_dim *dim_result = NULL;
5900         struct isl_basic_map *bmap;
5901         unsigned in1, in2, out1, out2, nparam, total, pos;
5902         struct isl_dim_map *dim_map1, *dim_map2;
5903
5904         if (!bmap1 || !bmap2)
5905                 goto error;
5906
5907         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
5908                                      bmap2->dim, isl_dim_param), goto error);
5909         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
5910                                                    isl_dim_copy(bmap2->dim));
5911
5912         in1 = isl_basic_map_n_in(bmap1);
5913         in2 = isl_basic_map_n_in(bmap2);
5914         out1 = isl_basic_map_n_out(bmap1);
5915         out2 = isl_basic_map_n_out(bmap2);
5916         nparam = isl_basic_map_n_param(bmap1);
5917
5918         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
5919         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
5920         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
5921         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
5922         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
5923         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
5924         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
5925         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
5926         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
5927         isl_dim_map_div(dim_map1, bmap1, pos += out2);
5928         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
5929
5930         bmap = isl_basic_map_alloc_dim(dim_result,
5931                         bmap1->n_div + bmap2->n_div,
5932                         bmap1->n_eq + bmap2->n_eq,
5933                         bmap1->n_ineq + bmap2->n_ineq);
5934         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
5935         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
5936         bmap = isl_basic_map_simplify(bmap);
5937         return isl_basic_map_finalize(bmap);
5938 error:
5939         isl_basic_map_free(bmap1);
5940         isl_basic_map_free(bmap2);
5941         return NULL;
5942 }
5943
5944 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
5945  */
5946 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
5947 {
5948         unsigned flags = 0;
5949         struct isl_map *result;
5950         int i, j;
5951
5952         if (!map1 || !map2)
5953                 goto error;
5954
5955         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
5956                                          map2->dim, isl_dim_param), goto error);
5957
5958         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
5959             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
5960                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
5961
5962         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
5963                                                    isl_dim_copy(map2->dim)),
5964                                 map1->n * map2->n, flags);
5965         if (!result)
5966                 goto error;
5967         for (i = 0; i < map1->n; ++i)
5968                 for (j = 0; j < map2->n; ++j) {
5969                         struct isl_basic_map *part;
5970                         part = isl_basic_map_product(
5971                                     isl_basic_map_copy(map1->p[i]),
5972                                     isl_basic_map_copy(map2->p[j]));
5973                         if (isl_basic_map_is_empty(part))
5974                                 isl_basic_map_free(part);
5975                         else
5976                                 result = isl_map_add_basic_map(result, part);
5977                         if (!result)
5978                                 goto error;
5979                 }
5980         isl_map_free(map1);
5981         isl_map_free(map2);
5982         return result;
5983 error:
5984         isl_map_free(map1);
5985         isl_map_free(map2);
5986         return NULL;
5987 }
5988
5989 /* Given two set A and B, construct its Cartesian product A x B.
5990  */
5991 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
5992 {
5993         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
5994                                                  (struct isl_map *)set2);
5995 }
5996
5997 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5998 {
5999         int i;
6000         uint32_t hash = isl_hash_init();
6001         unsigned total;
6002
6003         if (!bset)
6004                 return 0;
6005         bset = isl_basic_set_copy(bset);
6006         bset = isl_basic_set_normalize(bset);
6007         if (!bset)
6008                 return 0;
6009         total = isl_basic_set_total_dim(bset);
6010         isl_hash_byte(hash, bset->n_eq & 0xFF);
6011         for (i = 0; i < bset->n_eq; ++i) {
6012                 uint32_t c_hash;
6013                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
6014                 isl_hash_hash(hash, c_hash);
6015         }
6016         isl_hash_byte(hash, bset->n_ineq & 0xFF);
6017         for (i = 0; i < bset->n_ineq; ++i) {
6018                 uint32_t c_hash;
6019                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
6020                 isl_hash_hash(hash, c_hash);
6021         }
6022         isl_hash_byte(hash, bset->n_div & 0xFF);
6023         for (i = 0; i < bset->n_div; ++i) {
6024                 uint32_t c_hash;
6025                 if (isl_int_is_zero(bset->div[i][0]))
6026                         continue;
6027                 isl_hash_byte(hash, i & 0xFF);
6028                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
6029                 isl_hash_hash(hash, c_hash);
6030         }
6031         isl_basic_set_free(bset);
6032         return hash;
6033 }
6034
6035 uint32_t isl_set_get_hash(struct isl_set *set)
6036 {
6037         int i;
6038         uint32_t hash;
6039
6040         if (!set)
6041                 return 0;
6042         set = isl_set_copy(set);
6043         set = isl_set_normalize(set);
6044         if (!set)
6045                 return 0;
6046
6047         hash = isl_hash_init();
6048         for (i = 0; i < set->n; ++i) {
6049                 uint32_t bset_hash;
6050                 bset_hash = isl_basic_set_get_hash(set->p[i]);
6051                 isl_hash_hash(hash, bset_hash);
6052         }
6053
6054         isl_set_free(set);
6055
6056         return hash;
6057 }
6058
6059 /* Check if the value for dimension dim is completely determined
6060  * by the values of the other parameters and variables.
6061  * That is, check if dimension dim is involved in an equality.
6062  */
6063 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
6064 {
6065         int i;
6066         unsigned nparam;
6067
6068         if (!bset)
6069                 return -1;
6070         nparam = isl_basic_set_n_param(bset);
6071         for (i = 0; i < bset->n_eq; ++i)
6072                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
6073                         return 1;
6074         return 0;
6075 }
6076
6077 /* Check if the value for dimension dim is completely determined
6078  * by the values of the other parameters and variables.
6079  * That is, check if dimension dim is involved in an equality
6080  * for each of the subsets.
6081  */
6082 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
6083 {
6084         int i;
6085
6086         if (!set)
6087                 return -1;
6088         for (i = 0; i < set->n; ++i) {
6089                 int unique;
6090                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
6091                 if (unique != 1)
6092                         return unique;
6093         }
6094         return 1;
6095 }
6096
6097 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
6098         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
6099 {
6100         int i;
6101
6102         if (!map)
6103                 return -1;
6104
6105         for (i = 0; i < map->n; ++i)
6106                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
6107                         return -1;
6108
6109         return 0;
6110 }
6111
6112 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
6113         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
6114 {
6115         int i;
6116
6117         if (!set)
6118                 return -1;
6119
6120         for (i = 0; i < set->n; ++i)
6121                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
6122                         return -1;
6123
6124         return 0;
6125 }
6126
6127 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
6128 {
6129         struct isl_dim *dim;
6130
6131         if (!bset)
6132                 return NULL;
6133
6134         if (bset->n_div == 0)
6135                 return bset;
6136
6137         bset = isl_basic_set_cow(bset);
6138         if (!bset)
6139                 return NULL;
6140
6141         dim = isl_basic_set_get_dim(bset);
6142         dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
6143         if (!dim)
6144                 goto error;
6145         isl_dim_free(bset->dim);
6146         bset->dim = dim;
6147         bset->n_div = 0;
6148
6149         return bset;
6150 error:
6151         isl_basic_set_free(bset);
6152         return NULL;
6153 }
6154
6155 __isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
6156 {
6157         int i;
6158         struct isl_dim *dim;
6159         unsigned n_div;
6160
6161         set = isl_set_align_divs(set);
6162
6163         if (!set)
6164                 return NULL;
6165         if (set->n == 0 || set->p[0]->n_div == 0)
6166                 return set;
6167
6168         set = isl_set_cow(set);
6169         if (!set)
6170                 return NULL;
6171
6172         n_div = set->p[0]->n_div;
6173         dim = isl_set_get_dim(set);
6174         dim = isl_dim_add(dim, isl_dim_set, n_div);
6175         if (!dim)
6176                 goto error;
6177         isl_dim_free(set->dim);
6178         set->dim = dim;
6179
6180         for (i = 0; i < set->n; ++i) {
6181                 set->p[i] = isl_basic_set_lift(set->p[i]);
6182                 if (!set->p[i])
6183                         goto error;
6184         }
6185
6186         return set;
6187 error:
6188         isl_set_free(set);
6189         return NULL;
6190 }
6191
6192 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
6193 {
6194         struct isl_dim *dim;
6195         struct isl_basic_map *bmap;
6196         unsigned n_set;
6197         unsigned n_div;
6198         unsigned n_param;
6199         unsigned total;
6200         int i, k, l;
6201
6202         set = isl_set_align_divs(set);
6203
6204         if (!set)
6205                 return NULL;
6206
6207         dim = isl_set_get_dim(set);
6208         if (set->n == 0 || set->p[0]->n_div == 0) {
6209                 isl_set_free(set);
6210                 return isl_map_identity(dim);
6211         }
6212
6213         n_div = set->p[0]->n_div;
6214         dim = isl_dim_map(dim);
6215         n_param = isl_dim_size(dim, isl_dim_param);
6216         n_set = isl_dim_size(dim, isl_dim_in);
6217         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
6218         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
6219         for (i = 0; i < n_set; ++i)
6220                 bmap = var_equal(bmap, i);
6221
6222         total = n_param + n_set + n_set + n_div;
6223         for (i = 0; i < n_div; ++i) {
6224                 k = isl_basic_map_alloc_inequality(bmap);
6225                 if (k < 0)
6226                         goto error;
6227                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
6228                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
6229                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
6230                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
6231                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
6232                             set->p[0]->div[i][0]);
6233
6234                 l = isl_basic_map_alloc_inequality(bmap);
6235                 if (l < 0)
6236                         goto error;
6237                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
6238                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
6239                             set->p[0]->div[i][0]);
6240                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
6241         }
6242
6243         isl_set_free(set);
6244         return isl_map_from_basic_map(bmap);
6245 error:
6246         isl_set_free(set);
6247         isl_basic_map_free(bmap);
6248         return NULL;
6249 }
6250
6251 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
6252 {
6253         unsigned dim;
6254         int size = 0;
6255
6256         if (!bset)
6257                 return -1;
6258
6259         dim = isl_basic_set_total_dim(bset);
6260         size += bset->n_eq * (1 + dim);
6261         size += bset->n_ineq * (1 + dim);
6262         size += bset->n_div * (2 + dim);
6263
6264         return size;
6265 }
6266
6267 int isl_set_size(__isl_keep isl_set *set)
6268 {
6269         int i;
6270         int size = 0;
6271
6272         if (!set)
6273                 return -1;
6274
6275         for (i = 0; i < set->n; ++i)
6276                 size += isl_basic_set_size(set->p[i]);
6277
6278         return size;
6279 }