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