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