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