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         map = isl_map_cow(map);
3086         if (!map)
3087                 goto error;
3088
3089         set = (struct isl_set *) map;
3090         if (set->dim->n_in != 0) {
3091                 set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
3092                 if (!set->dim)
3093                         goto error;
3094         }
3095         for (i = 0; i < map->n; ++i) {
3096                 set->p[i] = isl_basic_map_range(map->p[i]);
3097                 if (!set->p[i])
3098                         goto error;
3099         }
3100         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3101         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3102         return set;
3103 error:
3104         isl_map_free(map);
3105         return NULL;
3106 }
3107
3108 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3109 {
3110         int i;
3111         struct isl_map *map = NULL;
3112
3113         set = isl_set_cow(set);
3114         if (!set || !dim)
3115                 goto error;
3116         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3117         map = (struct isl_map *)set;
3118         for (i = 0; i < set->n; ++i) {
3119                 map->p[i] = isl_basic_map_from_basic_set(
3120                                 set->p[i], isl_dim_copy(dim));
3121                 if (!map->p[i])
3122                         goto error;
3123         }
3124         isl_dim_free(map->dim);
3125         map->dim = dim;
3126         return map;
3127 error:
3128         isl_dim_free(dim);
3129         isl_set_free(set);
3130         return NULL;
3131 }
3132
3133 struct isl_map *isl_map_from_range(struct isl_set *set)
3134 {
3135         return (struct isl_map *)set;
3136 }
3137
3138 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
3139 {
3140         return isl_map_reverse(isl_map_from_range(set));;
3141 }
3142
3143 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
3144         __isl_take isl_set *range)
3145 {
3146         return isl_map_product(isl_map_from_domain(domain),
3147                                isl_map_from_range(range));
3148 }
3149
3150 struct isl_set *isl_set_from_map(struct isl_map *map)
3151 {
3152         int i;
3153         struct isl_set *set = NULL;
3154
3155         if (!map)
3156                 return NULL;
3157         map = isl_map_cow(map);
3158         if (!map)
3159                 return NULL;
3160         map->dim = isl_dim_cow(map->dim);
3161         if (!map->dim)
3162                 goto error;
3163         map->dim->n_out += map->dim->n_in;
3164         map->dim->n_in = 0;
3165         set = (struct isl_set *)map;
3166         for (i = 0; i < map->n; ++i) {
3167                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3168                 if (!set->p[i])
3169                         goto error;
3170         }
3171         return set;
3172 error:
3173         isl_map_free(map);
3174         return NULL;
3175 }
3176
3177 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3178 {
3179         struct isl_map *map;
3180
3181         if (!dim)
3182                 return NULL;
3183         isl_assert(dim->ctx, n >= 0, return NULL);
3184         map = isl_alloc(dim->ctx, struct isl_map,
3185                         sizeof(struct isl_map) +
3186                         (n - 1) * sizeof(struct isl_basic_map *));
3187         if (!map)
3188                 goto error;
3189
3190         map->ctx = dim->ctx;
3191         isl_ctx_ref(map->ctx);
3192         map->ref = 1;
3193         map->size = n;
3194         map->n = 0;
3195         map->dim = dim;
3196         map->flags = flags;
3197         return map;
3198 error:
3199         isl_dim_free(dim);
3200         return NULL;
3201 }
3202
3203 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3204                 unsigned nparam, unsigned in, unsigned out, int n,
3205                 unsigned flags)
3206 {
3207         struct isl_map *map;
3208         struct isl_dim *dims;
3209
3210         dims = isl_dim_alloc(ctx, nparam, in, out);
3211         if (!dims)
3212                 return NULL;
3213
3214         map = isl_map_alloc_dim(dims, n, flags);
3215         return map;
3216 }
3217
3218 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
3219 {
3220         struct isl_basic_map *bmap;
3221         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
3222         bmap = isl_basic_map_set_to_empty(bmap);
3223         return bmap;
3224 }
3225
3226 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3227 {
3228         struct isl_basic_set *bset;
3229         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3230         bset = isl_basic_set_set_to_empty(bset);
3231         return bset;
3232 }
3233
3234 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3235 {
3236         struct isl_basic_map *bmap;
3237         if (!model)
3238                 return NULL;
3239         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3240         bmap = isl_basic_map_set_to_empty(bmap);
3241         return bmap;
3242 }
3243
3244 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3245 {
3246         struct isl_basic_map *bmap;
3247         if (!model)
3248                 return NULL;
3249         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3250         bmap = isl_basic_map_set_to_empty(bmap);
3251         return bmap;
3252 }
3253
3254 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3255 {
3256         struct isl_basic_set *bset;
3257         if (!model)
3258                 return NULL;
3259         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3260         bset = isl_basic_set_set_to_empty(bset);
3261         return bset;
3262 }
3263
3264 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3265 {
3266         struct isl_basic_map *bmap;
3267         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3268         return bmap;
3269 }
3270
3271 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3272 {
3273         struct isl_basic_set *bset;
3274         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3275         return bset;
3276 }
3277
3278 __isl_give isl_basic_map *isl_basic_map_universe_like(
3279                 __isl_keep isl_basic_map *model)
3280 {
3281         if (!model)
3282                 return NULL;
3283         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3284 }
3285
3286 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3287 {
3288         if (!model)
3289                 return NULL;
3290         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3291 }
3292
3293 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3294         __isl_keep isl_set *model)
3295 {
3296         if (!model)
3297                 return NULL;
3298         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3299 }
3300
3301 struct isl_map *isl_map_empty(struct isl_dim *dim)
3302 {
3303         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3304 }
3305
3306 struct isl_map *isl_map_empty_like(struct isl_map *model)
3307 {
3308         if (!model)
3309                 return NULL;
3310         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3311 }
3312
3313 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3314 {
3315         if (!model)
3316                 return NULL;
3317         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3318 }
3319
3320 struct isl_set *isl_set_empty(struct isl_dim *dim)
3321 {
3322         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3323 }
3324
3325 struct isl_set *isl_set_empty_like(struct isl_set *model)
3326 {
3327         if (!model)
3328                 return NULL;
3329         return isl_set_empty(isl_dim_copy(model->dim));
3330 }
3331
3332 struct isl_map *isl_map_universe(struct isl_dim *dim)
3333 {
3334         struct isl_map *map;
3335         if (!dim)
3336                 return NULL;
3337         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3338         map = isl_map_add_basic_map(map, isl_basic_map_universe(dim));
3339         return map;
3340 }
3341
3342 struct isl_set *isl_set_universe(struct isl_dim *dim)
3343 {
3344         struct isl_set *set;
3345         if (!dim)
3346                 return NULL;
3347         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3348         set = isl_set_add_basic_set(set, isl_basic_set_universe(dim));
3349         return set;
3350 }
3351
3352 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3353 {
3354         if (!model)
3355                 return NULL;
3356         return isl_set_universe(isl_dim_copy(model->dim));
3357 }
3358
3359 struct isl_map *isl_map_dup(struct isl_map *map)
3360 {
3361         int i;
3362         struct isl_map *dup;
3363
3364         if (!map)
3365                 return NULL;
3366         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3367         for (i = 0; i < map->n; ++i)
3368                 dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i]));
3369         return dup;
3370 }
3371
3372 __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
3373                                                 __isl_take isl_basic_map *bmap)
3374 {
3375         if (!bmap || !map)
3376                 goto error;
3377         if (isl_basic_map_fast_is_empty(bmap)) {
3378                 isl_basic_map_free(bmap);
3379                 return map;
3380         }
3381         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3382         isl_assert(map->ctx, map->n < map->size, goto error);
3383         map->p[map->n] = bmap;
3384         map->n++;
3385         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3386         return map;
3387 error:
3388         if (map)
3389                 isl_map_free(map);
3390         if (bmap)
3391                 isl_basic_map_free(bmap);
3392         return NULL;
3393 }
3394
3395 void isl_map_free(struct isl_map *map)
3396 {
3397         int i;
3398
3399         if (!map)
3400                 return;
3401
3402         if (--map->ref > 0)
3403                 return;
3404
3405         isl_ctx_deref(map->ctx);
3406         for (i = 0; i < map->n; ++i)
3407                 isl_basic_map_free(map->p[i]);
3408         isl_dim_free(map->dim);
3409         free(map);
3410 }
3411
3412 struct isl_map *isl_map_extend(struct isl_map *base,
3413                 unsigned nparam, unsigned n_in, unsigned n_out)
3414 {
3415         int i;
3416
3417         base = isl_map_cow(base);
3418         if (!base)
3419                 return NULL;
3420
3421         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3422         if (!base->dim)
3423                 goto error;
3424         for (i = 0; i < base->n; ++i) {
3425                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3426                                 isl_dim_copy(base->dim), 0, 0, 0);
3427                 if (!base->p[i])
3428                         goto error;
3429         }
3430         return base;
3431 error:
3432         isl_map_free(base);
3433         return NULL;
3434 }
3435
3436 struct isl_set *isl_set_extend(struct isl_set *base,
3437                 unsigned nparam, unsigned dim)
3438 {
3439         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3440                                                         nparam, 0, dim);
3441 }
3442
3443 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3444         struct isl_basic_map *bmap, unsigned pos, int value)
3445 {
3446         int j;
3447
3448         bmap = isl_basic_map_cow(bmap);
3449         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3450         j = isl_basic_map_alloc_equality(bmap);
3451         if (j < 0)
3452                 goto error;
3453         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3454         isl_int_set_si(bmap->eq[j][pos], -1);
3455         isl_int_set_si(bmap->eq[j][0], value);
3456         bmap = isl_basic_map_simplify(bmap);
3457         return isl_basic_map_finalize(bmap);
3458 error:
3459         isl_basic_map_free(bmap);
3460         return NULL;
3461 }
3462
3463 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3464         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3465 {
3466         int j;
3467
3468         bmap = isl_basic_map_cow(bmap);
3469         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3470         j = isl_basic_map_alloc_equality(bmap);
3471         if (j < 0)
3472                 goto error;
3473         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3474         isl_int_set_si(bmap->eq[j][pos], -1);
3475         isl_int_set(bmap->eq[j][0], value);
3476         bmap = isl_basic_map_simplify(bmap);
3477         return isl_basic_map_finalize(bmap);
3478 error:
3479         isl_basic_map_free(bmap);
3480         return NULL;
3481 }
3482
3483 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3484                 enum isl_dim_type type, unsigned pos, int value)
3485 {
3486         if (!bmap)
3487                 return NULL;
3488         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3489         return isl_basic_map_fix_pos_si(bmap,
3490                 isl_basic_map_offset(bmap, type) + pos, value);
3491 error:
3492         isl_basic_map_free(bmap);
3493         return NULL;
3494 }
3495
3496 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3497                 enum isl_dim_type type, unsigned pos, isl_int value)
3498 {
3499         if (!bmap)
3500                 return NULL;
3501         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3502         return isl_basic_map_fix_pos(bmap,
3503                 isl_basic_map_offset(bmap, type) + pos, value);
3504 error:
3505         isl_basic_map_free(bmap);
3506         return NULL;
3507 }
3508
3509 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3510                 enum isl_dim_type type, unsigned pos, int value)
3511 {
3512         return (struct isl_basic_set *)
3513                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3514                                         type, pos, value);
3515 }
3516
3517 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3518                 enum isl_dim_type type, unsigned pos, isl_int value)
3519 {
3520         return (struct isl_basic_set *)
3521                 isl_basic_map_fix((struct isl_basic_map *)bset,
3522                                         type, pos, value);
3523 }
3524
3525 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3526                 unsigned input, int value)
3527 {
3528         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3529 }
3530
3531 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3532                 unsigned dim, int value)
3533 {
3534         return (struct isl_basic_set *)
3535                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3536                                         isl_dim_set, dim, value);
3537 }
3538
3539 struct isl_map *isl_map_fix_si(struct isl_map *map,
3540                 enum isl_dim_type type, unsigned pos, int value)
3541 {
3542         int i;
3543
3544         map = isl_map_cow(map);
3545         if (!map)
3546                 return NULL;
3547
3548         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3549         for (i = 0; i < map->n; ++i) {
3550                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
3551                 if (!map->p[i])
3552                         goto error;
3553         }
3554         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3555         return map;
3556 error:
3557         isl_map_free(map);
3558         return NULL;
3559 }
3560
3561 __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
3562                 enum isl_dim_type type, unsigned pos, int value)
3563 {
3564         return (struct isl_set *)
3565                 isl_map_fix_si((struct isl_map *)set, type, pos, value);
3566 }
3567
3568 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
3569                 enum isl_dim_type type, unsigned pos, isl_int value)
3570 {
3571         int i;
3572
3573         map = isl_map_cow(map);
3574         if (!map)
3575                 return NULL;
3576
3577         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3578         for (i = 0; i < map->n; ++i) {
3579                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
3580                 if (!map->p[i])
3581                         goto error;
3582         }
3583         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3584         return map;
3585 error:
3586         isl_map_free(map);
3587         return NULL;
3588 }
3589
3590 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
3591                 enum isl_dim_type type, unsigned pos, isl_int value)
3592 {
3593         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
3594 }
3595
3596 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3597                 unsigned input, int value)
3598 {
3599         return isl_map_fix_si(map, isl_dim_in, input, value);
3600 }
3601
3602 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3603 {
3604         return (struct isl_set *)
3605                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
3606 }
3607
3608 __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
3609                 __isl_take isl_basic_map *bmap,
3610                 enum isl_dim_type type, unsigned pos, int value)
3611 {
3612         int j;
3613
3614         if (!bmap)
3615                 return NULL;
3616         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3617         pos += isl_basic_map_offset(bmap, type);
3618         bmap = isl_basic_map_cow(bmap);
3619         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
3620         j = isl_basic_map_alloc_inequality(bmap);
3621         if (j < 0)
3622                 goto error;
3623         isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
3624         isl_int_set_si(bmap->ineq[j][pos], 1);
3625         isl_int_set_si(bmap->ineq[j][0], -value);
3626         bmap = isl_basic_map_simplify(bmap);
3627         return isl_basic_map_finalize(bmap);
3628 error:
3629         isl_basic_map_free(bmap);
3630         return NULL;
3631 }
3632
3633 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3634         unsigned dim, isl_int value)
3635 {
3636         int j;
3637
3638         bset = isl_basic_set_cow(bset);
3639         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3640         j = isl_basic_set_alloc_inequality(bset);
3641         if (j < 0)
3642                 goto error;
3643         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3644         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3645         isl_int_neg(bset->ineq[j][0], value);
3646         bset = isl_basic_set_simplify(bset);
3647         return isl_basic_set_finalize(bset);
3648 error:
3649         isl_basic_set_free(bset);
3650         return NULL;
3651 }
3652
3653 __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
3654                 enum isl_dim_type type, unsigned pos, int value)
3655 {
3656         int i;
3657
3658         map = isl_map_cow(map);
3659         if (!map)
3660                 return NULL;
3661
3662         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3663         for (i = 0; i < map->n; ++i) {
3664                 map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
3665                                                          type, pos, value);
3666                 if (!map->p[i])
3667                         goto error;
3668         }
3669         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3670         return map;
3671 error:
3672         isl_map_free(map);
3673         return NULL;
3674 }
3675
3676 __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
3677                 enum isl_dim_type type, unsigned pos, int value)
3678 {
3679         return (struct isl_set *)
3680                 isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
3681 }
3682
3683 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3684                                         isl_int value)
3685 {
3686         int i;
3687
3688         set = isl_set_cow(set);
3689         if (!set)
3690                 return NULL;
3691
3692         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3693         for (i = 0; i < set->n; ++i) {
3694                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3695                 if (!set->p[i])
3696                         goto error;
3697         }
3698         return set;
3699 error:
3700         isl_set_free(set);
3701         return NULL;
3702 }
3703
3704 struct isl_map *isl_map_reverse(struct isl_map *map)
3705 {
3706         int i;
3707
3708         map = isl_map_cow(map);
3709         if (!map)
3710                 return NULL;
3711
3712         map->dim = isl_dim_reverse(map->dim);
3713         if (!map->dim)
3714                 goto error;
3715         for (i = 0; i < map->n; ++i) {
3716                 map->p[i] = isl_basic_map_reverse(map->p[i]);
3717                 if (!map->p[i])
3718                         goto error;
3719         }
3720         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3721         return map;
3722 error:
3723         isl_map_free(map);
3724         return NULL;
3725 }
3726
3727 static struct isl_map *isl_basic_map_partial_lexopt(
3728                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3729                 struct isl_set **empty, int max)
3730 {
3731         if (!bmap)
3732                 goto error;
3733         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
3734                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
3735         else
3736                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
3737 error:
3738         isl_basic_map_free(bmap);
3739         isl_basic_set_free(dom);
3740         if (empty)
3741                 *empty = NULL;
3742         return NULL;
3743 }
3744
3745 struct isl_map *isl_basic_map_partial_lexmax(
3746                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3747                 struct isl_set **empty)
3748 {
3749         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
3750 }
3751
3752 struct isl_map *isl_basic_map_partial_lexmin(
3753                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3754                 struct isl_set **empty)
3755 {
3756         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
3757 }
3758
3759 struct isl_set *isl_basic_set_partial_lexmin(
3760                 struct isl_basic_set *bset, struct isl_basic_set *dom,
3761                 struct isl_set **empty)
3762 {
3763         return (struct isl_set *)
3764                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
3765                         dom, empty);
3766 }
3767
3768 struct isl_set *isl_basic_set_partial_lexmax(
3769                 struct isl_basic_set *bset, struct isl_basic_set *dom,
3770                 struct isl_set **empty)
3771 {
3772         return (struct isl_set *)
3773                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
3774                         dom, empty);
3775 }
3776
3777 /* Given a basic map "bmap", compute the lexicograhically minimal
3778  * (or maximal) image element for each domain element in dom.
3779  * Set *empty to those elements in dom that do not have an image element.
3780  *
3781  * We first make sure the basic sets in dom are disjoint and then
3782  * simply collect the results over each of the basic sets separately.
3783  * We could probably improve the efficiency a bit by moving the union
3784  * domain down into the parametric integer programming.
3785  */
3786 static __isl_give isl_map *basic_map_partial_lexopt(
3787                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
3788                 __isl_give isl_set **empty, int max)
3789 {
3790         int i;
3791         struct isl_map *res;
3792
3793         dom = isl_set_make_disjoint(dom);
3794         if (!dom)
3795                 goto error;
3796
3797         if (isl_set_fast_is_empty(dom)) {
3798                 res = isl_map_empty_like_basic_map(bmap);
3799                 *empty = isl_set_empty_like(dom);
3800                 isl_set_free(dom);
3801                 isl_basic_map_free(bmap);
3802                 return res;
3803         }
3804
3805         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
3806                         isl_basic_set_copy(dom->p[0]), empty, max);
3807
3808         for (i = 1; i < dom->n; ++i) {
3809                 struct isl_map *res_i;
3810                 struct isl_set *empty_i;
3811
3812                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
3813                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
3814
3815                 res = isl_map_union_disjoint(res, res_i);
3816                 *empty = isl_set_union_disjoint(*empty, empty_i);
3817         }
3818
3819         isl_set_free(dom);
3820         isl_basic_map_free(bmap);
3821         return res;
3822 error:
3823         *empty = NULL;
3824         isl_set_free(dom);
3825         isl_basic_map_free(bmap);
3826         return NULL;
3827 }
3828
3829 /* Given a map "map", compute the lexicograhically minimal
3830  * (or maximal) image element for each domain element in dom.
3831  * Set *empty to those elements in dom that do not have an image element.
3832  *
3833  * We first compute the lexicographically minimal or maximal element
3834  * in the first basic map.  This results in a partial solution "res"
3835  * and a subset "todo" of dom that still need to be handled.
3836  * We then consider each of the remaining maps in "map" and successively
3837  * improve both "res" and "todo".
3838  *
3839  * Let res^k and todo^k be the results after k steps and let i = k + 1.
3840  * Assume we are computing the lexicographical maximum.
3841  * We first intersect basic map i with a relation that maps elements
3842  * to elements that are lexicographically larger than the image elements
3843  * in res^k and the compute the maximum image element of this intersection.
3844  * The result ("better") corresponds to those image elements in basic map i
3845  * that are better than what we had before.  The remainder ("keep") are the
3846  * domain elements for which the image element in res_k was better.
3847  * We also compute the lexicographical maximum of basic map i in todo^k.
3848  * res^i is the result of the operation + better + those elements in
3849  *              res^k that we should keep
3850  * todo^i is the remainder of the maximum operation on todo^k.
3851  */
3852 static __isl_give isl_map *isl_map_partial_lexopt(
3853                 __isl_take isl_map *map, __isl_take isl_set *dom,
3854                 __isl_give isl_set **empty, int max)
3855 {
3856         int i;
3857         struct isl_map *res;
3858         struct isl_set *todo;
3859
3860         if (!map || !dom)
3861                 goto error;
3862
3863         if (isl_map_fast_is_empty(map)) {
3864                 if (empty)
3865                         *empty = dom;
3866                 else
3867                         isl_set_free(dom);
3868                 return map;
3869         }
3870
3871         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
3872                                         isl_set_copy(dom), &todo, max);
3873
3874         for (i = 1; i < map->n; ++i) {
3875                 struct isl_map *lt;
3876                 struct isl_map *better;
3877                 struct isl_set *keep;
3878                 struct isl_map *res_i;
3879                 struct isl_set *todo_i;
3880                 struct isl_dim *dim = isl_map_get_dim(res);
3881
3882                 dim = isl_dim_range(dim);
3883                 if (max)
3884                         lt = isl_map_lex_lt(dim);
3885                 else
3886                         lt = isl_map_lex_gt(dim);
3887                 lt = isl_map_apply_range(isl_map_copy(res), lt);
3888                 lt = isl_map_intersect(lt,
3889                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
3890                 better = isl_map_partial_lexopt(lt,
3891                         isl_map_domain(isl_map_copy(res)),
3892                         &keep, max);
3893
3894                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
3895                                                 todo, &todo_i, max);
3896
3897                 res = isl_map_intersect_domain(res, keep);
3898                 res = isl_map_union_disjoint(res, res_i);
3899                 res = isl_map_union_disjoint(res, better);
3900                 todo = todo_i;
3901         }
3902
3903         isl_set_free(dom);
3904         isl_map_free(map);
3905
3906         if (empty)
3907                 *empty = todo;
3908         else
3909                 isl_set_free(todo);
3910
3911         return res;
3912 error:
3913         if (empty)
3914                 *empty = NULL;
3915         isl_set_free(dom);
3916         isl_map_free(map);
3917         return NULL;
3918 }
3919
3920 __isl_give isl_map *isl_map_partial_lexmax(
3921                 __isl_take isl_map *map, __isl_take isl_set *dom,
3922                 __isl_give isl_set **empty)
3923 {
3924         return isl_map_partial_lexopt(map, dom, empty, 1);
3925 }
3926
3927 __isl_give isl_map *isl_map_partial_lexmin(
3928                 __isl_take isl_map *map, __isl_take isl_set *dom,
3929                 __isl_give isl_set **empty)
3930 {
3931         return isl_map_partial_lexopt(map, dom, empty, 0);
3932 }
3933
3934 __isl_give isl_set *isl_set_partial_lexmin(
3935                 __isl_take isl_set *set, __isl_take isl_set *dom,
3936                 __isl_give isl_set **empty)
3937 {
3938         return (struct isl_set *)
3939                 isl_map_partial_lexmin((struct isl_map *)set,
3940                         dom, empty);
3941 }
3942
3943 __isl_give isl_set *isl_set_partial_lexmax(
3944                 __isl_take isl_set *set, __isl_take isl_set *dom,
3945                 __isl_give isl_set **empty)
3946 {
3947         return (struct isl_set *)
3948                 isl_map_partial_lexmax((struct isl_map *)set,
3949                         dom, empty);
3950 }
3951
3952 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
3953 {
3954         struct isl_basic_set *dom = NULL;
3955         struct isl_dim *dom_dim;
3956
3957         if (!bmap)
3958                 goto error;
3959         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
3960         dom = isl_basic_set_universe(dom_dim);
3961         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
3962 error:
3963         isl_basic_map_free(bmap);
3964         return NULL;
3965 }
3966
3967 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
3968 {
3969         return isl_basic_map_lexopt(bmap, 0);
3970 }
3971
3972 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
3973 {
3974         return isl_basic_map_lexopt(bmap, 1);
3975 }
3976
3977 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
3978 {
3979         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
3980 }
3981
3982 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
3983 {
3984         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
3985 }
3986
3987 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
3988 {
3989         struct isl_set *dom = NULL;
3990         struct isl_dim *dom_dim;
3991
3992         if (!map)
3993                 goto error;
3994         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
3995         dom = isl_set_universe(dom_dim);
3996         return isl_map_partial_lexopt(map, dom, NULL, max);
3997 error:
3998         isl_map_free(map);
3999         return NULL;
4000 }
4001
4002 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
4003 {
4004         return isl_map_lexopt(map, 0);
4005 }
4006
4007 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
4008 {
4009         return isl_map_lexopt(map, 1);
4010 }
4011
4012 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
4013 {
4014         return (isl_set *)isl_map_lexmin((isl_map *)set);
4015 }
4016
4017 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
4018 {
4019         return (isl_set *)isl_map_lexmax((isl_map *)set);
4020 }
4021
4022 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
4023         struct isl_dim *dim)
4024 {
4025         int i;
4026
4027         if (!map || !dim)
4028                 goto error;
4029
4030         for (i = 0; i < map->n; ++i) {
4031                 isl_dim_free(map->p[i]->dim);
4032                 map->p[i]->dim = isl_dim_copy(dim);
4033         }
4034         isl_dim_free(map->dim);
4035         map->dim = dim;
4036
4037         return map;
4038 error:
4039         isl_map_free(map);
4040         isl_dim_free(dim);
4041         return NULL;
4042 }
4043
4044 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
4045         struct isl_dim *dim)
4046 {
4047         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
4048 }
4049
4050 /* Apply a preimage specified by "mat" on the parameters of "bset".
4051  * bset is assumed to have only parameters and divs.
4052  */
4053 static struct isl_basic_set *basic_set_parameter_preimage(
4054         struct isl_basic_set *bset, struct isl_mat *mat)
4055 {
4056         unsigned nparam;
4057
4058         if (!bset || !mat)
4059                 goto error;
4060
4061         bset->dim = isl_dim_cow(bset->dim);
4062         if (!bset->dim)
4063                 goto error;
4064
4065         nparam = isl_basic_set_dim(bset, isl_dim_param);
4066
4067         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
4068
4069         bset->dim->nparam = 0;
4070         bset->dim->n_out = nparam;
4071         bset = isl_basic_set_preimage(bset, mat);
4072         if (bset) {
4073                 bset->dim->nparam = bset->dim->n_out;
4074                 bset->dim->n_out = 0;
4075         }
4076         return bset;
4077 error:
4078         isl_mat_free(mat);
4079         isl_basic_set_free(bset);
4080         return NULL;
4081 }
4082
4083 /* Apply a preimage specified by "mat" on the parameters of "set".
4084  * set is assumed to have only parameters and divs.
4085  */
4086 static struct isl_set *set_parameter_preimage(
4087         struct isl_set *set, struct isl_mat *mat)
4088 {
4089         struct isl_dim *dim = NULL;
4090         unsigned nparam;
4091
4092         if (!set || !mat)
4093                 goto error;
4094
4095         dim = isl_dim_copy(set->dim);
4096         dim = isl_dim_cow(dim);
4097         if (!dim)
4098                 goto error;
4099
4100         nparam = isl_set_dim(set, isl_dim_param);
4101
4102         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
4103
4104         dim->nparam = 0;
4105         dim->n_out = nparam;
4106         isl_set_reset_dim(set, dim);
4107         set = isl_set_preimage(set, mat);
4108         if (!set)
4109                 goto error2;
4110         dim = isl_dim_copy(set->dim);
4111         dim = isl_dim_cow(dim);
4112         if (!dim)
4113                 goto error2;
4114         dim->nparam = dim->n_out;
4115         dim->n_out = 0;
4116         isl_set_reset_dim(set, dim);
4117         return set;
4118 error:
4119         isl_dim_free(dim);
4120         isl_mat_free(mat);
4121 error2:
4122         isl_set_free(set);
4123         return NULL;
4124 }
4125
4126 /* Intersect the basic set "bset" with the affine space specified by the
4127  * equalities in "eq".
4128  */
4129 static struct isl_basic_set *basic_set_append_equalities(
4130         struct isl_basic_set *bset, struct isl_mat *eq)
4131 {
4132         int i, k;
4133         unsigned len;
4134
4135         if (!bset || !eq)
4136                 goto error;
4137
4138         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
4139                                         eq->n_row, 0);
4140         if (!bset)
4141                 goto error;
4142
4143         len = 1 + isl_dim_total(bset->dim) + bset->extra;
4144         for (i = 0; i < eq->n_row; ++i) {
4145                 k = isl_basic_set_alloc_equality(bset);
4146                 if (k < 0)
4147                         goto error;
4148                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
4149                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
4150         }
4151         isl_mat_free(eq);
4152
4153         return bset;
4154 error:
4155         isl_mat_free(eq);
4156         isl_basic_set_free(bset);
4157         return NULL;
4158 }
4159
4160 /* Intersect the set "set" with the affine space specified by the
4161  * equalities in "eq".
4162  */
4163 static struct isl_set *set_append_equalities(struct isl_set *set,
4164         struct isl_mat *eq)
4165 {
4166         int i;
4167
4168         if (!set || !eq)
4169                 goto error;
4170
4171         for (i = 0; i < set->n; ++i) {
4172                 set->p[i] = basic_set_append_equalities(set->p[i],
4173                                         isl_mat_copy(eq));
4174                 if (!set->p[i])
4175                         goto error;
4176         }
4177         isl_mat_free(eq);
4178         return set;
4179 error:
4180         isl_mat_free(eq);
4181         isl_set_free(set);
4182         return NULL;
4183 }
4184
4185 /* Project the given basic set onto its parameter domain, possibly introducing
4186  * new, explicit, existential variables in the constraints.
4187  * The input has parameters and (possibly implicit) existential variables.
4188  * The output has the same parameters, but only
4189  * explicit existentially quantified variables.
4190  *
4191  * The actual projection is performed by pip, but pip doesn't seem
4192  * to like equalities very much, so we first remove the equalities
4193  * among the parameters by performing a variable compression on
4194  * the parameters.  Afterward, an inverse transformation is performed
4195  * and the equalities among the parameters are inserted back in.
4196  */
4197 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
4198 {
4199         int i, j;
4200         struct isl_mat *eq;
4201         struct isl_mat *T, *T2;
4202         struct isl_set *set;
4203         unsigned nparam, n_div;
4204
4205         bset = isl_basic_set_cow(bset);
4206         if (!bset)
4207                 return NULL;
4208
4209         if (bset->n_eq == 0)
4210                 return isl_basic_set_lexmin(bset);
4211
4212         isl_basic_set_gauss(bset, NULL);
4213
4214         nparam = isl_basic_set_dim(bset, isl_dim_param);
4215         n_div = isl_basic_set_dim(bset, isl_dim_div);
4216
4217         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
4218                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
4219                         ++i;
4220         }
4221         if (i == bset->n_eq)
4222                 return isl_basic_set_lexmin(bset);
4223
4224         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
4225                 0, 1 + nparam);
4226         eq = isl_mat_cow(eq);
4227         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
4228         bset = basic_set_parameter_preimage(bset, T);
4229
4230         set = isl_basic_set_lexmin(bset);
4231         set = set_parameter_preimage(set, T2);
4232         set = set_append_equalities(set, eq);
4233         return set;
4234 }
4235
4236 /* Compute an explicit representation for all the existentially
4237  * quantified variables.
4238  * The input and output dimensions are first turned into parameters.
4239  * compute_divs then returns a map with the same parameters and
4240  * no input or output dimensions and the dimension specification
4241  * is reset to that of the input.
4242  */
4243 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
4244 {
4245         struct isl_basic_set *bset;
4246         struct isl_set *set;
4247         struct isl_map *map;
4248         struct isl_dim *dim, *orig_dim = NULL;
4249         unsigned         nparam;
4250         unsigned         n_in;
4251         unsigned         n_out;
4252
4253         bmap = isl_basic_map_cow(bmap);
4254         if (!bmap)
4255                 return NULL;
4256
4257         nparam = isl_basic_map_dim(bmap, isl_dim_param);
4258         n_in = isl_basic_map_dim(bmap, isl_dim_in);
4259         n_out = isl_basic_map_dim(bmap, isl_dim_out);
4260         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
4261         if (!dim)
4262                 goto error;
4263
4264         orig_dim = bmap->dim;
4265         bmap->dim = dim;
4266         bset = (struct isl_basic_set *)bmap;
4267
4268         set = parameter_compute_divs(bset);
4269         map = (struct isl_map *)set;
4270         map = isl_map_reset_dim(map, orig_dim);
4271
4272         return map;
4273 error:
4274         isl_basic_map_free(bmap);
4275         return NULL;
4276 }
4277
4278 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
4279 {
4280         int i;
4281         unsigned off;
4282
4283         if (!bmap)
4284                 return -1;
4285
4286         off = isl_dim_total(bmap->dim);
4287         for (i = 0; i < bmap->n_div; ++i) {
4288                 if (isl_int_is_zero(bmap->div[i][0]))
4289                         return 0;
4290                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
4291                                 return -1);
4292         }
4293         return 1;
4294 }
4295
4296 static int map_divs_known(__isl_keep isl_map *map)
4297 {
4298         int i;
4299
4300         if (!map)
4301                 return -1;
4302
4303         for (i = 0; i < map->n; ++i) {
4304                 int known = basic_map_divs_known(map->p[i]);
4305                 if (known <= 0)
4306                         return known;
4307         }
4308
4309         return 1;
4310 }
4311
4312 /* If bmap contains any unknown divs, then compute explicit
4313  * expressions for them.  However, this computation may be
4314  * quite expensive, so first try to remove divs that aren't
4315  * strictly needed.
4316  */
4317 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
4318 {
4319         int i;
4320         int known;
4321         struct isl_map *map;
4322
4323         known = basic_map_divs_known(bmap);
4324         if (known < 0)
4325                 goto error;
4326         if (known)
4327                 return isl_map_from_basic_map(bmap);
4328
4329         bmap = isl_basic_map_drop_redundant_divs(bmap);
4330
4331         known = basic_map_divs_known(bmap);
4332         if (known < 0)
4333                 goto error;
4334         if (known)
4335                 return isl_map_from_basic_map(bmap);
4336
4337         map = compute_divs(bmap);
4338         return map;
4339 error:
4340         isl_basic_map_free(bmap);
4341         return NULL;
4342 }
4343
4344 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4345 {
4346         int i;
4347         int known;
4348         struct isl_map *res;
4349
4350         if (!map)
4351                 return NULL;
4352         if (map->n == 0)
4353                 return map;
4354
4355         known = map_divs_known(map);
4356         if (known < 0) {
4357                 isl_map_free(map);
4358                 return NULL;
4359         }
4360         if (known)
4361                 return map;
4362
4363         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4364         for (i = 1 ; i < map->n; ++i) {
4365                 struct isl_map *r2;
4366                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4367                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4368                         res = isl_map_union_disjoint(res, r2);
4369                 else
4370                         res = isl_map_union(res, r2);
4371         }
4372         isl_map_free(map);
4373
4374         return res;
4375 }
4376
4377 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4378 {
4379         return (struct isl_set *)
4380                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4381 }
4382
4383 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4384 {
4385         return (struct isl_set *)
4386                 isl_map_compute_divs((struct isl_map *)set);
4387 }
4388
4389 struct isl_set *isl_map_domain(struct isl_map *map)
4390 {
4391         int i;
4392         struct isl_set *set;
4393
4394         if (!map)
4395                 goto error;
4396
4397         map = isl_map_cow(map);
4398         if (!map)
4399                 return NULL;
4400
4401         set = (struct isl_set *)map;
4402         set->dim = isl_dim_domain(set->dim);
4403         if (!set->dim)
4404                 goto error;
4405         for (i = 0; i < map->n; ++i) {
4406                 set->p[i] = isl_basic_map_domain(map->p[i]);
4407                 if (!set->p[i])
4408                         goto error;
4409         }
4410         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4411         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4412         return set;
4413 error:
4414         isl_map_free(map);
4415         return NULL;
4416 }
4417
4418 struct isl_map *isl_map_union_disjoint(
4419                         struct isl_map *map1, struct isl_map *map2)
4420 {
4421         int i;
4422         unsigned flags = 0;
4423         struct isl_map *map = NULL;
4424
4425         if (!map1 || !map2)
4426                 goto error;
4427
4428         if (map1->n == 0) {
4429                 isl_map_free(map1);
4430                 return map2;
4431         }
4432         if (map2->n == 0) {
4433                 isl_map_free(map2);
4434                 return map1;
4435         }
4436
4437         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4438
4439         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4440             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4441                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4442
4443         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4444                                 map1->n + map2->n, flags);
4445         if (!map)
4446                 goto error;
4447         for (i = 0; i < map1->n; ++i) {
4448                 map = isl_map_add_basic_map(map,
4449                                   isl_basic_map_copy(map1->p[i]));
4450                 if (!map)
4451                         goto error;
4452         }
4453         for (i = 0; i < map2->n; ++i) {
4454                 map = isl_map_add_basic_map(map,
4455                                   isl_basic_map_copy(map2->p[i]));
4456                 if (!map)
4457                         goto error;
4458         }
4459         isl_map_free(map1);
4460         isl_map_free(map2);
4461         return map;
4462 error:
4463         isl_map_free(map);
4464         isl_map_free(map1);
4465         isl_map_free(map2);
4466         return NULL;
4467 }
4468
4469 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4470 {
4471         map1 = isl_map_union_disjoint(map1, map2);
4472         if (!map1)
4473                 return NULL;
4474         if (map1->n > 1)
4475                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4476         return map1;
4477 }
4478
4479 struct isl_set *isl_set_union_disjoint(
4480                         struct isl_set *set1, struct isl_set *set2)
4481 {
4482         return (struct isl_set *)
4483                 isl_map_union_disjoint(
4484                         (struct isl_map *)set1, (struct isl_map *)set2);
4485 }
4486
4487 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4488 {
4489         return (struct isl_set *)
4490                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4491 }
4492
4493 struct isl_map *isl_map_intersect_range(
4494                 struct isl_map *map, struct isl_set *set)
4495 {
4496         unsigned flags = 0;
4497         struct isl_map *result;
4498         int i, j;
4499
4500         if (!map || !set)
4501                 goto error;
4502
4503         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4504             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4505                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4506
4507         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4508                                         map->n * set->n, flags);
4509         if (!result)
4510                 goto error;
4511         for (i = 0; i < map->n; ++i)
4512                 for (j = 0; j < set->n; ++j) {
4513                         result = isl_map_add_basic_map(result,
4514                             isl_basic_map_intersect_range(
4515                                 isl_basic_map_copy(map->p[i]),
4516                                 isl_basic_set_copy(set->p[j])));
4517                         if (!result)
4518                                 goto error;
4519                 }
4520         isl_map_free(map);
4521         isl_set_free(set);
4522         return result;
4523 error:
4524         isl_map_free(map);
4525         isl_set_free(set);
4526         return NULL;
4527 }
4528
4529 struct isl_map *isl_map_intersect_domain(
4530                 struct isl_map *map, struct isl_set *set)
4531 {
4532         return isl_map_reverse(
4533                 isl_map_intersect_range(isl_map_reverse(map), set));
4534 }
4535
4536 struct isl_map *isl_map_apply_domain(
4537                 struct isl_map *map1, struct isl_map *map2)
4538 {
4539         if (!map1 || !map2)
4540                 goto error;
4541         map1 = isl_map_reverse(map1);
4542         map1 = isl_map_apply_range(map1, map2);
4543         return isl_map_reverse(map1);
4544 error:
4545         isl_map_free(map1);
4546         isl_map_free(map2);
4547         return NULL;
4548 }
4549
4550 struct isl_map *isl_map_apply_range(
4551                 struct isl_map *map1, struct isl_map *map2)
4552 {
4553         struct isl_dim *dim_result;
4554         struct isl_map *result;
4555         int i, j;
4556
4557         if (!map1 || !map2)
4558                 goto error;
4559
4560         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4561                                   isl_dim_copy(map2->dim));
4562
4563         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4564         if (!result)
4565                 goto error;
4566         for (i = 0; i < map1->n; ++i)
4567                 for (j = 0; j < map2->n; ++j) {
4568                         result = isl_map_add_basic_map(result,
4569                             isl_basic_map_apply_range(
4570                                 isl_basic_map_copy(map1->p[i]),
4571                                 isl_basic_map_copy(map2->p[j])));
4572                         if (!result)
4573                                 goto error;
4574                 }
4575         isl_map_free(map1);
4576         isl_map_free(map2);
4577         if (result && result->n <= 1)
4578                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4579         return result;
4580 error:
4581         isl_map_free(map1);
4582         isl_map_free(map2);
4583         return NULL;
4584 }
4585
4586 /*
4587  * returns range - domain
4588  */
4589 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4590 {
4591         struct isl_basic_set *bset;
4592         unsigned dim;
4593         unsigned nparam;
4594         int i;
4595
4596         if (!bmap)
4597                 goto error;
4598         dim = isl_basic_map_n_in(bmap);
4599         nparam = isl_basic_map_n_param(bmap);
4600         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4601         bset = isl_basic_set_from_basic_map(bmap);
4602         bset = isl_basic_set_cow(bset);
4603         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
4604         bset = isl_basic_set_swap_vars(bset, 2*dim);
4605         for (i = 0; i < dim; ++i) {
4606                 int j = isl_basic_map_alloc_equality(
4607                                             (struct isl_basic_map *)bset);
4608                 if (j < 0)
4609                         goto error;
4610                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4611                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4612                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4613                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4614         }
4615         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4616 error:
4617         isl_basic_map_free(bmap);
4618         return NULL;
4619 }
4620
4621 /*
4622  * returns range - domain
4623  */
4624 struct isl_set *isl_map_deltas(struct isl_map *map)
4625 {
4626         int i;
4627         struct isl_set *result;
4628
4629         if (!map)
4630                 return NULL;
4631
4632         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4633         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
4634                                         isl_map_n_in(map), map->n, map->flags);
4635         if (!result)
4636                 goto error;
4637         for (i = 0; i < map->n; ++i)
4638                 result = isl_set_add_basic_set(result,
4639                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4640         isl_map_free(map);
4641         return result;
4642 error:
4643         isl_map_free(map);
4644         return NULL;
4645 }
4646
4647 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4648 {
4649         struct isl_basic_map *bmap;
4650         unsigned nparam;
4651         unsigned dim;
4652         int i;
4653
4654         if (!dims)
4655                 return NULL;
4656
4657         nparam = dims->nparam;
4658         dim = dims->n_out;
4659         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4660         if (!bmap)
4661                 goto error;
4662
4663         for (i = 0; i < dim; ++i) {
4664                 int j = isl_basic_map_alloc_equality(bmap);
4665                 if (j < 0)
4666                         goto error;
4667                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4668                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
4669                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
4670         }
4671         return isl_basic_map_finalize(bmap);
4672 error:
4673         isl_basic_map_free(bmap);
4674         return NULL;
4675 }
4676
4677 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
4678 {
4679         struct isl_dim *dim = isl_dim_map(set_dim);
4680         if (!dim)
4681                 return NULL;
4682         return basic_map_identity(dim);
4683 }
4684
4685 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
4686 {
4687         if (!model || !model->dim)
4688                 return NULL;
4689         isl_assert(model->ctx,
4690                         model->dim->n_in == model->dim->n_out, return NULL);
4691         return basic_map_identity(isl_dim_copy(model->dim));
4692 }
4693
4694 static struct isl_map *map_identity(struct isl_dim *dim)
4695 {
4696         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
4697         return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim)));
4698 }
4699
4700 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
4701 {
4702         struct isl_dim *dim = isl_dim_map(set_dim);
4703         if (!dim)
4704                 return NULL;
4705         return map_identity(dim);
4706 }
4707
4708 struct isl_map *isl_map_identity_like(struct isl_map *model)
4709 {
4710         if (!model || !model->dim)
4711                 return NULL;
4712         isl_assert(model->ctx,
4713                         model->dim->n_in == model->dim->n_out, return NULL);
4714         return map_identity(isl_dim_copy(model->dim));
4715 }
4716
4717 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
4718 {
4719         if (!model || !model->dim)
4720                 return NULL;
4721         isl_assert(model->ctx,
4722                         model->dim->n_in == model->dim->n_out, return NULL);
4723         return map_identity(isl_dim_copy(model->dim));
4724 }
4725
4726 /* Construct a basic set with all set dimensions having only non-negative
4727  * values.
4728  */
4729 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
4730 {
4731         int i;
4732         unsigned nparam;
4733         unsigned dim;
4734         struct isl_basic_set *bset;
4735
4736         if (!dims)
4737                 return NULL;
4738         nparam = dims->nparam;
4739         dim = dims->n_out;
4740         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
4741         if (!bset)
4742                 return NULL;
4743         for (i = 0; i < dim; ++i) {
4744                 int k = isl_basic_set_alloc_inequality(bset);
4745                 if (k < 0)
4746                         goto error;
4747                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
4748                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
4749         }
4750         return bset;
4751 error:
4752         isl_basic_set_free(bset);
4753         return NULL;
4754 }
4755
4756 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
4757 {
4758         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
4759 }
4760
4761 int isl_basic_map_is_subset(
4762                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4763 {
4764         int is_subset;
4765         struct isl_map *map1;
4766         struct isl_map *map2;
4767
4768         if (!bmap1 || !bmap2)
4769                 return -1;
4770
4771         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
4772         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
4773
4774         is_subset = isl_map_is_subset(map1, map2);
4775
4776         isl_map_free(map1);
4777         isl_map_free(map2);
4778
4779         return is_subset;
4780 }
4781
4782 int isl_basic_map_is_equal(
4783                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4784 {
4785         int is_subset;
4786
4787         if (!bmap1 || !bmap2)
4788                 return -1;
4789         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4790         if (is_subset != 1)
4791                 return is_subset;
4792         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4793         return is_subset;
4794 }
4795
4796 int isl_basic_set_is_equal(
4797                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4798 {
4799         return isl_basic_map_is_equal(
4800                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4801 }
4802
4803 int isl_map_is_empty(struct isl_map *map)
4804 {
4805         int i;
4806         int is_empty;
4807
4808         if (!map)
4809                 return -1;
4810         for (i = 0; i < map->n; ++i) {
4811                 is_empty = isl_basic_map_is_empty(map->p[i]);
4812                 if (is_empty < 0)
4813                         return -1;
4814                 if (!is_empty)
4815                         return 0;
4816         }
4817         return 1;
4818 }
4819
4820 int isl_map_fast_is_empty(struct isl_map *map)
4821 {
4822         return map->n == 0;
4823 }
4824
4825 int isl_set_fast_is_empty(struct isl_set *set)
4826 {
4827         return set->n == 0;
4828 }
4829
4830 int isl_set_is_empty(struct isl_set *set)
4831 {
4832         return isl_map_is_empty((struct isl_map *)set);
4833 }
4834
4835 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4836 {
4837         int is_subset;
4838
4839         if (!map1 || !map2)
4840                 return -1;
4841         is_subset = isl_map_is_subset(map1, map2);
4842         if (is_subset != 1)
4843                 return is_subset;
4844         is_subset = isl_map_is_subset(map2, map1);
4845         return is_subset;
4846 }
4847
4848 int isl_basic_map_is_strict_subset(
4849                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4850 {
4851         int is_subset;
4852
4853         if (!bmap1 || !bmap2)
4854                 return -1;
4855         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4856         if (is_subset != 1)
4857                 return is_subset;
4858         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4859         if (is_subset == -1)
4860                 return is_subset;
4861         return !is_subset;
4862 }
4863
4864 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
4865 {
4866         int is_subset;
4867
4868         if (!map1 || !map2)
4869                 return -1;
4870         is_subset = isl_map_is_subset(map1, map2);
4871         if (is_subset != 1)
4872                 return is_subset;
4873         is_subset = isl_map_is_subset(map2, map1);
4874         if (is_subset == -1)
4875                 return is_subset;
4876         return !is_subset;
4877 }
4878
4879 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
4880 {
4881         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
4882 }
4883
4884 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4885 {
4886         if (!bmap)
4887                 return -1;
4888         return bmap->n_eq == 0 && bmap->n_ineq == 0;
4889 }
4890
4891 int isl_basic_set_is_universe(struct isl_basic_set *bset)
4892 {
4893         if (!bset)
4894                 return -1;
4895         return bset->n_eq == 0 && bset->n_ineq == 0;
4896 }
4897
4898 int isl_map_fast_is_universe(__isl_keep isl_map *map)
4899 {
4900         if (!map)
4901                 return -1;
4902
4903         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
4904 }
4905
4906 int isl_set_fast_is_universe(__isl_keep isl_set *set)
4907 {
4908         return isl_map_fast_is_universe((isl_map *) set);
4909 }
4910
4911 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4912 {
4913         struct isl_basic_set *bset = NULL;
4914         struct isl_vec *sample = NULL;
4915         int empty;
4916         unsigned total;
4917
4918         if (!bmap)
4919                 return -1;
4920
4921         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4922                 return 1;
4923
4924         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4925                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4926                 copy = isl_basic_map_convex_hull(copy);
4927                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4928                 isl_basic_map_free(copy);
4929                 return empty;
4930         }
4931
4932         total = 1 + isl_basic_map_total_dim(bmap);
4933         if (bmap->sample && bmap->sample->size == total) {
4934                 int contains = isl_basic_map_contains(bmap, bmap->sample);
4935                 if (contains < 0)
4936                         return -1;
4937                 if (contains)
4938                         return 0;
4939         }
4940         isl_vec_free(bmap->sample);
4941         bmap->sample = NULL;
4942         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4943         if (!bset)
4944                 return -1;
4945         sample = isl_basic_set_sample_vec(bset);
4946         if (!sample)
4947                 return -1;
4948         empty = sample->size == 0;
4949         isl_vec_free(bmap->sample);
4950         bmap->sample = sample;
4951         if (empty)
4952                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
4953
4954         return empty;
4955 }
4956
4957 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
4958 {
4959         if (!bmap)
4960                 return -1;
4961         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
4962 }
4963
4964 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
4965 {
4966         if (!bset)
4967                 return -1;
4968         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
4969 }
4970
4971 int isl_basic_set_is_empty(struct isl_basic_set *bset)
4972 {
4973         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
4974 }
4975
4976 struct isl_map *isl_basic_map_union(
4977         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4978 {
4979         struct isl_map *map;
4980         if (!bmap1 || !bmap2)
4981                 return NULL;
4982
4983         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
4984
4985         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
4986         if (!map)
4987                 goto error;
4988         map = isl_map_add_basic_map(map, bmap1);
4989         map = isl_map_add_basic_map(map, bmap2);
4990         return map;
4991 error:
4992         isl_basic_map_free(bmap1);
4993         isl_basic_map_free(bmap2);
4994         return NULL;
4995 }
4996
4997 struct isl_set *isl_basic_set_union(
4998                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4999 {
5000         return (struct isl_set *)isl_basic_map_union(
5001                                             (struct isl_basic_map *)bset1,
5002                                             (struct isl_basic_map *)bset2);
5003 }
5004
5005 /* Order divs such that any div only depends on previous divs */
5006 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
5007 {
5008         int i;
5009         unsigned off = isl_dim_total(bmap->dim);
5010
5011         for (i = 0; i < bmap->n_div; ++i) {
5012                 int pos;
5013                 if (isl_int_is_zero(bmap->div[i][0]))
5014                         continue;
5015                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
5016                                                             bmap->n_div-i);
5017                 if (pos == -1)
5018                         continue;
5019                 isl_basic_map_swap_div(bmap, i, i + pos);
5020                 --i;
5021         }
5022         return bmap;
5023 }
5024
5025 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
5026 {
5027         return (struct isl_basic_set *)
5028                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
5029 }
5030
5031 __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
5032 {
5033         int i;
5034
5035         if (!map)
5036                 return 0;
5037
5038         for (i = 0; i < map->n; ++i) {
5039                 map->p[i] = isl_basic_map_order_divs(map->p[i]);
5040                 if (!map->p[i])
5041                         goto error;
5042         }
5043
5044         return map;
5045 error:
5046         isl_map_free(map);
5047         return NULL;
5048 }
5049
5050 /* Look for a div in dst that corresponds to the div "div" in src.
5051  * The divs before "div" in src and dst are assumed to be the same.
5052  *
5053  * Returns -1 if no corresponding div was found and the position
5054  * of the corresponding div in dst otherwise.
5055  */
5056 static int find_div(struct isl_basic_map *dst,
5057                         struct isl_basic_map *src, unsigned div)
5058 {
5059         int i;
5060
5061         unsigned total = isl_dim_total(src->dim);
5062
5063         isl_assert(dst->ctx, div <= dst->n_div, return -1);
5064         for (i = div; i < dst->n_div; ++i)
5065                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
5066                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
5067                                                 dst->n_div - div) == -1)
5068                         return i;
5069         return -1;
5070 }
5071
5072 struct isl_basic_map *isl_basic_map_align_divs(
5073                 struct isl_basic_map *dst, struct isl_basic_map *src)
5074 {
5075         int i;
5076         unsigned total = isl_dim_total(src->dim);
5077
5078         if (!dst || !src)
5079                 goto error;
5080
5081         if (src->n_div == 0)
5082                 return dst;
5083
5084         for (i = 0; i < src->n_div; ++i)
5085                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
5086
5087         src = isl_basic_map_order_divs(src);
5088         dst = isl_basic_map_cow(dst);
5089         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
5090                         src->n_div, 0, 2 * src->n_div);
5091         if (!dst)
5092                 return NULL;
5093         for (i = 0; i < src->n_div; ++i) {
5094                 int j = find_div(dst, src, i);
5095                 if (j < 0) {
5096                         j = isl_basic_map_alloc_div(dst);
5097                         if (j < 0)
5098                                 goto error;
5099                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
5100                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
5101                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
5102                                 goto error;
5103                 }
5104                 if (j != i)
5105                         isl_basic_map_swap_div(dst, i, j);
5106         }
5107         return dst;
5108 error:
5109         isl_basic_map_free(dst);
5110         return NULL;
5111 }
5112
5113 struct isl_basic_set *isl_basic_set_align_divs(
5114                 struct isl_basic_set *dst, struct isl_basic_set *src)
5115 {
5116         return (struct isl_basic_set *)isl_basic_map_align_divs(
5117                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
5118 }
5119
5120 struct isl_map *isl_map_align_divs(struct isl_map *map)
5121 {
5122         int i;
5123
5124         if (!map)
5125                 return NULL;
5126         if (map->n == 0)
5127                 return map;
5128         map = isl_map_compute_divs(map);
5129         map = isl_map_cow(map);
5130         if (!map)
5131                 return NULL;
5132
5133         for (i = 1; i < map->n; ++i)
5134                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
5135         for (i = 1; i < map->n; ++i)
5136                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
5137
5138         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5139         return map;
5140 }
5141
5142 struct isl_set *isl_set_align_divs(struct isl_set *set)
5143 {
5144         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
5145 }
5146
5147 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
5148 {
5149         if (!set || !map)
5150                 goto error;
5151         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
5152         map = isl_map_intersect_domain(map, set);
5153         set = isl_map_range(map);
5154         return set;
5155 error:
5156         isl_set_free(set);
5157         isl_map_free(map);
5158         return NULL;
5159 }
5160
5161 /* There is no need to cow as removing empty parts doesn't change
5162  * the meaning of the set.
5163  */
5164 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
5165 {
5166         int i;
5167
5168         if (!map)
5169                 return NULL;
5170
5171         for (i = map->n-1; i >= 0; --i) {
5172                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
5173                         continue;
5174                 isl_basic_map_free(map->p[i]);
5175                 if (i != map->n-1) {
5176                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5177                         map->p[i] = map->p[map->n-1];
5178                 }
5179                 map->n--;
5180         }
5181
5182         return map;
5183 }
5184
5185 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
5186 {
5187         return (struct isl_set *)
5188                 isl_map_remove_empty_parts((struct isl_map *)set);
5189 }
5190
5191 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
5192 {
5193         struct isl_basic_map *bmap;
5194         if (!map || map->n == 0)
5195                 return NULL;
5196         bmap = map->p[map->n-1];
5197         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
5198         return isl_basic_map_copy(bmap);
5199 }
5200
5201 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
5202 {
5203         return (struct isl_basic_set *)
5204                 isl_map_copy_basic_map((struct isl_map *)set);
5205 }
5206
5207 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
5208                                                 __isl_keep isl_basic_map *bmap)
5209 {
5210         int i;
5211
5212         if (!map || !bmap)
5213                 goto error;
5214         for (i = map->n-1; i >= 0; --i) {
5215                 if (map->p[i] != bmap)
5216                         continue;
5217                 map = isl_map_cow(map);
5218                 if (!map)
5219                         goto error;
5220                 isl_basic_map_free(map->p[i]);
5221                 if (i != map->n-1) {
5222                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
5223                         map->p[i] = map->p[map->n-1];
5224                 }
5225                 map->n--;
5226                 return map;
5227         }
5228         return map;
5229 error:
5230         isl_map_free(map);
5231         return NULL;
5232 }
5233
5234 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
5235                                                 struct isl_basic_set *bset)
5236 {
5237         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
5238                                                 (struct isl_basic_map *)bset);
5239 }
5240
5241 /* Given two basic sets bset1 and bset2, compute the maximal difference
5242  * between the values of dimension pos in bset1 and those in bset2
5243  * for any common value of the parameters and dimensions preceding pos.
5244  */
5245 static enum isl_lp_result basic_set_maximal_difference_at(
5246         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
5247         int pos, isl_int *opt)
5248 {
5249         struct isl_dim *dims;
5250         struct isl_basic_map *bmap1 = NULL;
5251         struct isl_basic_map *bmap2 = NULL;
5252         struct isl_ctx *ctx;
5253         struct isl_vec *obj;
5254         unsigned total;
5255         unsigned nparam;
5256         unsigned dim1, dim2;
5257         enum isl_lp_result res;
5258
5259         if (!bset1 || !bset2)
5260                 return isl_lp_error;
5261
5262         nparam = isl_basic_set_n_param(bset1);
5263         dim1 = isl_basic_set_n_dim(bset1);
5264         dim2 = isl_basic_set_n_dim(bset2);
5265         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
5266         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
5267         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
5268         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
5269         if (!bmap1 || !bmap2)
5270                 goto error;
5271         bmap1 = isl_basic_map_cow(bmap1);
5272         bmap1 = isl_basic_map_extend(bmap1, nparam,
5273                         pos, (dim1 - pos) + (dim2 - pos),
5274                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
5275         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
5276         if (!bmap1)
5277                 goto error;
5278         total = isl_basic_map_total_dim(bmap1);
5279         ctx = bmap1->ctx;
5280         obj = isl_vec_alloc(ctx, 1 + total);
5281         isl_seq_clr(obj->block.data, 1 + total);
5282         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
5283         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
5284         if (!obj)
5285                 goto error;
5286         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
5287                                         opt, NULL, NULL);
5288         isl_basic_map_free(bmap1);
5289         isl_vec_free(obj);
5290         return res;
5291 error:
5292         isl_basic_map_free(bmap1);
5293         isl_basic_map_free(bmap2);
5294         return isl_lp_error;
5295 }
5296
5297 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
5298  * for any common value of the parameters and dimensions preceding pos
5299  * in both basic sets, the values of dimension pos in bset1 are
5300  * smaller or larger than those in bset2.
5301  *
5302  * Returns
5303  *       1 if bset1 follows bset2
5304  *      -1 if bset1 precedes bset2
5305  *       0 if bset1 and bset2 are incomparable
5306  *      -2 if some error occurred.
5307  */
5308 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
5309         struct isl_basic_set *bset2, int pos)
5310 {
5311         isl_int opt;
5312         enum isl_lp_result res;
5313         int cmp;
5314
5315         isl_int_init(opt);
5316
5317         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5318
5319         if (res == isl_lp_empty)
5320                 cmp = 0;
5321         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5322                   res == isl_lp_unbounded)
5323                 cmp = 1;
5324         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5325                 cmp = -1;
5326         else
5327                 cmp = -2;
5328
5329         isl_int_clear(opt);
5330         return cmp;
5331 }
5332
5333 /* Given two basic sets bset1 and bset2, check whether
5334  * for any common value of the parameters and dimensions preceding pos
5335  * there is a value of dimension pos in bset1 that is larger
5336  * than a value of the same dimension in bset2.
5337  *
5338  * Return
5339  *       1 if there exists such a pair
5340  *       0 if there is no such pair, but there is a pair of equal values
5341  *      -1 otherwise
5342  *      -2 if some error occurred.
5343  */
5344 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
5345         __isl_keep isl_basic_set *bset2, int pos)
5346 {
5347         isl_int opt;
5348         enum isl_lp_result res;
5349         int cmp;
5350
5351         isl_int_init(opt);
5352
5353         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5354
5355         if (res == isl_lp_empty)
5356                 cmp = -1;
5357         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5358                   res == isl_lp_unbounded)
5359                 cmp = 1;
5360         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5361                 cmp = -1;
5362         else if (res == isl_lp_ok)
5363                 cmp = 0;
5364         else
5365                 cmp = -2;
5366
5367         isl_int_clear(opt);
5368         return cmp;
5369 }
5370
5371 /* Given two sets set1 and set2, check whether
5372  * for any common value of the parameters and dimensions preceding pos
5373  * there is a value of dimension pos in set1 that is larger
5374  * than a value of the same dimension in set2.
5375  *
5376  * Return
5377  *       1 if there exists such a pair
5378  *       0 if there is no such pair, but there is a pair of equal values
5379  *      -1 otherwise
5380  *      -2 if some error occurred.
5381  */
5382 int isl_set_follows_at(__isl_keep isl_set *set1,
5383         __isl_keep isl_set *set2, int pos)
5384 {
5385         int i, j;
5386         int follows = -1;
5387
5388         if (!set1 || !set2)
5389                 return -2;
5390
5391         for (i = 0; i < set1->n; ++i)
5392                 for (j = 0; j < set2->n; ++j) {
5393                         int f;
5394                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5395                         if (f == 1 || f == -2)
5396                                 return f;
5397                         if (f > follows)
5398                                 follows = f;
5399                 }
5400
5401         return follows;
5402 }
5403
5404 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5405         unsigned pos, isl_int *val)
5406 {
5407         int i;
5408         int d;
5409         unsigned total;
5410
5411         if (!bmap)
5412                 return -1;
5413         total = isl_basic_map_total_dim(bmap);
5414         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5415                 for (; d+1 > pos; --d)
5416                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5417                                 break;
5418                 if (d != pos)
5419                         continue;
5420                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5421                         return 0;
5422                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5423                         return 0;
5424                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5425                         return 0;
5426                 if (val)
5427                         isl_int_neg(*val, bmap->eq[i][0]);
5428                 return 1;
5429         }
5430         return 0;
5431 }
5432
5433 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5434         unsigned pos, isl_int *val)
5435 {
5436         int i;
5437         isl_int v;
5438         isl_int tmp;
5439         int fixed;
5440
5441         if (!map)
5442                 return -1;
5443         if (map->n == 0)
5444                 return 0;
5445         if (map->n == 1)
5446                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5447         isl_int_init(v);
5448         isl_int_init(tmp);
5449         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5450         for (i = 1; fixed == 1 && i < map->n; ++i) {
5451                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5452                 if (fixed == 1 && isl_int_ne(tmp, v))
5453                         fixed = 0;
5454         }
5455         if (val)
5456                 isl_int_set(*val, v);
5457         isl_int_clear(tmp);
5458         isl_int_clear(v);
5459         return fixed;
5460 }
5461
5462 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5463         unsigned pos, isl_int *val)
5464 {
5465         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5466                                                 pos, val);
5467 }
5468
5469 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5470         isl_int *val)
5471 {
5472         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5473 }
5474
5475 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5476         enum isl_dim_type type, unsigned pos, isl_int *val)
5477 {
5478         if (pos >= isl_basic_map_dim(bmap, type))
5479                 return -1;
5480         return isl_basic_map_fast_has_fixed_var(bmap,
5481                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
5482 }
5483
5484 int isl_map_fast_is_fixed(struct isl_map *map,
5485         enum isl_dim_type type, unsigned pos, isl_int *val)
5486 {
5487         if (pos >= isl_map_dim(map, type))
5488                 return -1;
5489         return isl_map_fast_has_fixed_var(map,
5490                 map_offset(map, type) - 1 + pos, val);
5491 }
5492
5493 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5494  * then return this fixed value in *val.
5495  */
5496 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
5497         isl_int *val)
5498 {
5499         return isl_basic_set_fast_has_fixed_var(bset,
5500                                         isl_basic_set_n_param(bset) + dim, val);
5501 }
5502
5503 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5504  * then return this fixed value in *val.
5505  */
5506 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
5507 {
5508         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
5509 }
5510
5511 /* Check if input variable in has fixed value and if so and if val is not NULL,
5512  * then return this fixed value in *val.
5513  */
5514 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
5515 {
5516         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
5517 }
5518
5519 /* Check if dimension dim has an (obvious) fixed lower bound and if so
5520  * and if val is not NULL, then return this lower bound in *val.
5521  */
5522 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
5523         unsigned dim, isl_int *val)
5524 {
5525         int i, i_eq = -1, i_ineq = -1;
5526         isl_int *c;
5527         unsigned total;
5528         unsigned nparam;
5529
5530         if (!bset)
5531                 return -1;
5532         total = isl_basic_set_total_dim(bset);
5533         nparam = isl_basic_set_n_param(bset);
5534         for (i = 0; i < bset->n_eq; ++i) {
5535                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
5536                         continue;
5537                 if (i_eq != -1)
5538                         return 0;
5539                 i_eq = i;
5540         }
5541         for (i = 0; i < bset->n_ineq; ++i) {
5542                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
5543                         continue;
5544                 if (i_eq != -1 || i_ineq != -1)
5545                         return 0;
5546                 i_ineq = i;
5547         }
5548         if (i_eq == -1 && i_ineq == -1)
5549                 return 0;
5550         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
5551         /* The coefficient should always be one due to normalization. */
5552         if (!isl_int_is_one(c[1+nparam+dim]))
5553                 return 0;
5554         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
5555                 return 0;
5556         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
5557                                         total - nparam - dim - 1) != -1)
5558                 return 0;
5559         if (val)
5560                 isl_int_neg(*val, c[0]);
5561         return 1;
5562 }
5563
5564 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
5565         unsigned dim, isl_int *val)
5566 {
5567         int i;
5568         isl_int v;
5569         isl_int tmp;
5570         int fixed;
5571
5572         if (!set)
5573                 return -1;
5574         if (set->n == 0)
5575                 return 0;
5576         if (set->n == 1)
5577                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5578                                                                 dim, val);
5579         isl_int_init(v);
5580         isl_int_init(tmp);
5581         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5582                                                                 dim, &v);
5583         for (i = 1; fixed == 1 && i < set->n; ++i) {
5584                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5585                                                                 dim, &tmp);
5586                 if (fixed == 1 && isl_int_ne(tmp, v))
5587                         fixed = 0;
5588         }
5589         if (val)
5590                 isl_int_set(*val, v);
5591         isl_int_clear(tmp);
5592         isl_int_clear(v);
5593         return fixed;
5594 }
5595
5596 struct constraint {
5597         unsigned        size;
5598         isl_int         *c;
5599 };
5600
5601 static int qsort_constraint_cmp(const void *p1, const void *p2)
5602 {
5603         const struct constraint *c1 = (const struct constraint *)p1;
5604         const struct constraint *c2 = (const struct constraint *)p2;
5605         unsigned size = isl_min(c1->size, c2->size);
5606         return isl_seq_cmp(c1->c, c2->c, size);
5607 }
5608
5609 static struct isl_basic_map *isl_basic_map_sort_constraints(
5610         struct isl_basic_map *bmap)
5611 {
5612         int i;
5613         struct constraint *c;
5614         unsigned total;
5615
5616         if (!bmap)
5617                 return NULL;
5618         total = isl_basic_map_total_dim(bmap);
5619         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5620         if (!c)
5621                 goto error;
5622         for (i = 0; i < bmap->n_ineq; ++i) {
5623                 c[i].size = total;
5624                 c[i].c = bmap->ineq[i];
5625         }
5626         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5627         for (i = 0; i < bmap->n_ineq; ++i)
5628                 bmap->ineq[i] = c[i].c;
5629         free(c);
5630         return bmap;
5631 error:
5632         isl_basic_map_free(bmap);
5633         return NULL;
5634 }
5635
5636 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5637 {
5638         if (!bmap)
5639                 return NULL;
5640         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5641                 return bmap;
5642         bmap = isl_basic_map_convex_hull(bmap);
5643         bmap = isl_basic_map_sort_constraints(bmap);
5644         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5645         return bmap;
5646 }
5647
5648 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5649 {
5650         return (struct isl_basic_set *)isl_basic_map_normalize(
5651                                                 (struct isl_basic_map *)bset);
5652 }
5653
5654 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5655         const struct isl_basic_map *bmap2)
5656 {
5657         int i, cmp;
5658         unsigned total;
5659
5660         if (bmap1 == bmap2)
5661                 return 0;
5662         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5663                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5664         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5665                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5666         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5667                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5668         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5669             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5670                 return 0;
5671         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5672                 return 1;
5673         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5674                 return -1;
5675         if (bmap1->n_eq != bmap2->n_eq)
5676                 return bmap1->n_eq - bmap2->n_eq;
5677         if (bmap1->n_ineq != bmap2->n_ineq)
5678                 return bmap1->n_ineq - bmap2->n_ineq;
5679         if (bmap1->n_div != bmap2->n_div)
5680                 return bmap1->n_div - bmap2->n_div;
5681         total = isl_basic_map_total_dim(bmap1);
5682         for (i = 0; i < bmap1->n_eq; ++i) {
5683                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5684                 if (cmp)
5685                         return cmp;
5686         }
5687         for (i = 0; i < bmap1->n_ineq; ++i) {
5688                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5689                 if (cmp)
5690                         return cmp;
5691         }
5692         for (i = 0; i < bmap1->n_div; ++i) {
5693                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5694                 if (cmp)
5695                         return cmp;
5696         }
5697         return 0;
5698 }
5699
5700 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5701         struct isl_basic_map *bmap2)
5702 {
5703         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5704 }
5705
5706 static int qsort_bmap_cmp(const void *p1, const void *p2)
5707 {
5708         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5709         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5710
5711         return isl_basic_map_fast_cmp(bmap1, bmap2);
5712 }
5713
5714 /* We normalize in place, but if anything goes wrong we need
5715  * to return NULL, so we need to make sure we don't change the
5716  * meaning of any possible other copies of map.
5717  */
5718 struct isl_map *isl_map_normalize(struct isl_map *map)
5719 {
5720         int i, j;
5721         struct isl_basic_map *bmap;
5722
5723         if (!map)
5724                 return NULL;
5725         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
5726                 return map;
5727         for (i = 0; i < map->n; ++i) {
5728                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5729                 if (!bmap)
5730                         goto error;
5731                 isl_basic_map_free(map->p[i]);
5732                 map->p[i] = bmap;
5733         }
5734         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5735         ISL_F_SET(map, ISL_MAP_NORMALIZED);
5736         map = isl_map_remove_empty_parts(map);
5737         if (!map)
5738                 return NULL;
5739         for (i = map->n - 1; i >= 1; --i) {
5740                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5741                         continue;
5742                 isl_basic_map_free(map->p[i-1]);
5743                 for (j = i; j < map->n; ++j)
5744                         map->p[j-1] = map->p[j];
5745                 map->n--;
5746         }
5747         return map;
5748 error:
5749         isl_map_free(map);
5750         return NULL;
5751
5752 }
5753
5754 struct isl_set *isl_set_normalize(struct isl_set *set)
5755 {
5756         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5757 }
5758
5759 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5760 {
5761         int i;
5762         int equal;
5763
5764         if (!map1 || !map2)
5765                 return -1;
5766
5767         if (map1 == map2)
5768                 return 1;
5769         if (!isl_dim_equal(map1->dim, map2->dim))
5770                 return 0;
5771
5772         map1 = isl_map_copy(map1);
5773         map2 = isl_map_copy(map2);
5774         map1 = isl_map_normalize(map1);
5775         map2 = isl_map_normalize(map2);
5776         if (!map1 || !map2)
5777                 goto error;
5778         equal = map1->n == map2->n;
5779         for (i = 0; equal && i < map1->n; ++i) {
5780                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5781                 if (equal < 0)
5782                         goto error;
5783         }
5784         isl_map_free(map1);
5785         isl_map_free(map2);
5786         return equal;
5787 error:
5788         isl_map_free(map1);
5789         isl_map_free(map2);
5790         return -1;
5791 }
5792
5793 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5794 {
5795         return isl_map_fast_is_equal((struct isl_map *)set1,
5796                                                 (struct isl_map *)set2);
5797 }
5798
5799 /* Return an interval that ranges from min to max (inclusive)
5800  */
5801 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5802         isl_int min, isl_int max)
5803 {
5804         int k;
5805         struct isl_basic_set *bset = NULL;
5806
5807         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5808         if (!bset)
5809                 goto error;
5810
5811         k = isl_basic_set_alloc_inequality(bset);
5812         if (k < 0)
5813                 goto error;
5814         isl_int_set_si(bset->ineq[k][1], 1);
5815         isl_int_neg(bset->ineq[k][0], min);
5816
5817         k = isl_basic_set_alloc_inequality(bset);
5818         if (k < 0)
5819                 goto error;
5820         isl_int_set_si(bset->ineq[k][1], -1);
5821         isl_int_set(bset->ineq[k][0], max);
5822
5823         return bset;
5824 error:
5825         isl_basic_set_free(bset);
5826         return NULL;
5827 }
5828
5829 /* Return the Cartesian product of the basic sets in list (in the given order).
5830  */
5831 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5832 {
5833         int i;
5834         unsigned dim;
5835         unsigned nparam;
5836         unsigned extra;
5837         unsigned n_eq;
5838         unsigned n_ineq;
5839         struct isl_basic_set *product = NULL;
5840
5841         if (!list)
5842                 goto error;
5843         isl_assert(list->ctx, list->n > 0, goto error);
5844         isl_assert(list->ctx, list->p[0], goto error);
5845         nparam = isl_basic_set_n_param(list->p[0]);
5846         dim = isl_basic_set_n_dim(list->p[0]);
5847         extra = list->p[0]->n_div;
5848         n_eq = list->p[0]->n_eq;
5849         n_ineq = list->p[0]->n_ineq;
5850         for (i = 1; i < list->n; ++i) {
5851                 isl_assert(list->ctx, list->p[i], goto error);
5852                 isl_assert(list->ctx,
5853                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5854                 dim += isl_basic_set_n_dim(list->p[i]);
5855                 extra += list->p[i]->n_div;
5856                 n_eq += list->p[i]->n_eq;
5857                 n_ineq += list->p[i]->n_ineq;
5858         }
5859         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5860                                         n_eq, n_ineq);
5861         if (!product)
5862                 goto error;
5863         dim = 0;
5864         for (i = 0; i < list->n; ++i) {
5865                 isl_basic_set_add_constraints(product,
5866                                         isl_basic_set_copy(list->p[i]), dim);
5867                 dim += isl_basic_set_n_dim(list->p[i]);
5868         }
5869         isl_basic_set_list_free(list);
5870         return product;
5871 error:
5872         isl_basic_set_free(product);
5873         isl_basic_set_list_free(list);
5874         return NULL;
5875 }
5876
5877 struct isl_basic_map *isl_basic_map_product(
5878                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5879 {
5880         struct isl_dim *dim_result = NULL;
5881         struct isl_basic_map *bmap;
5882         unsigned in1, in2, out1, out2, nparam, total, pos;
5883         struct isl_dim_map *dim_map1, *dim_map2;
5884
5885         if (!bmap1 || !bmap2)
5886                 goto error;
5887
5888         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
5889                                      bmap2->dim, isl_dim_param), goto error);
5890         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
5891                                                    isl_dim_copy(bmap2->dim));
5892
5893         in1 = isl_basic_map_n_in(bmap1);
5894         in2 = isl_basic_map_n_in(bmap2);
5895         out1 = isl_basic_map_n_out(bmap1);
5896         out2 = isl_basic_map_n_out(bmap2);
5897         nparam = isl_basic_map_n_param(bmap1);
5898
5899         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
5900         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
5901         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
5902         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
5903         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
5904         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
5905         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
5906         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
5907         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
5908         isl_dim_map_div(dim_map1, bmap1, pos += out2);
5909         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
5910
5911         bmap = isl_basic_map_alloc_dim(dim_result,
5912                         bmap1->n_div + bmap2->n_div,
5913                         bmap1->n_eq + bmap2->n_eq,
5914                         bmap1->n_ineq + bmap2->n_ineq);
5915         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
5916         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
5917         bmap = isl_basic_map_simplify(bmap);
5918         return isl_basic_map_finalize(bmap);
5919 error:
5920         isl_basic_map_free(bmap1);
5921         isl_basic_map_free(bmap2);
5922         return NULL;
5923 }
5924
5925 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
5926  */
5927 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
5928 {
5929         unsigned flags = 0;
5930         struct isl_map *result;
5931         int i, j;
5932
5933         if (!map1 || !map2)
5934                 goto error;
5935
5936         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
5937                                          map2->dim, isl_dim_param), goto error);
5938
5939         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
5940             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
5941                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
5942
5943         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
5944                                                    isl_dim_copy(map2->dim)),
5945                                 map1->n * map2->n, flags);
5946         if (!result)
5947                 goto error;
5948         for (i = 0; i < map1->n; ++i)
5949                 for (j = 0; j < map2->n; ++j) {
5950                         struct isl_basic_map *part;
5951                         part = isl_basic_map_product(
5952                                     isl_basic_map_copy(map1->p[i]),
5953                                     isl_basic_map_copy(map2->p[j]));
5954                         if (isl_basic_map_is_empty(part))
5955                                 isl_basic_map_free(part);
5956                         else
5957                                 result = isl_map_add_basic_map(result, part);
5958                         if (!result)
5959                                 goto error;
5960                 }
5961         isl_map_free(map1);
5962         isl_map_free(map2);
5963         return result;
5964 error:
5965         isl_map_free(map1);
5966         isl_map_free(map2);
5967         return NULL;
5968 }
5969
5970 /* Given two set A and B, construct its Cartesian product A x B.
5971  */
5972 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
5973 {
5974         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
5975                                                  (struct isl_map *)set2);
5976 }
5977
5978 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5979 {
5980         int i;
5981         uint32_t hash = isl_hash_init();
5982         unsigned total;
5983
5984         if (!bset)
5985                 return 0;
5986         bset = isl_basic_set_copy(bset);
5987         bset = isl_basic_set_normalize(bset);
5988         if (!bset)
5989                 return 0;
5990         total = isl_basic_set_total_dim(bset);
5991         isl_hash_byte(hash, bset->n_eq & 0xFF);
5992         for (i = 0; i < bset->n_eq; ++i) {
5993                 uint32_t c_hash;
5994                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5995                 isl_hash_hash(hash, c_hash);
5996         }
5997         isl_hash_byte(hash, bset->n_ineq & 0xFF);
5998         for (i = 0; i < bset->n_ineq; ++i) {
5999                 uint32_t c_hash;
6000                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
6001                 isl_hash_hash(hash, c_hash);
6002         }
6003         isl_hash_byte(hash, bset->n_div & 0xFF);
6004         for (i = 0; i < bset->n_div; ++i) {
6005                 uint32_t c_hash;
6006                 if (isl_int_is_zero(bset->div[i][0]))
6007                         continue;
6008                 isl_hash_byte(hash, i & 0xFF);
6009                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
6010                 isl_hash_hash(hash, c_hash);
6011         }
6012         isl_basic_set_free(bset);
6013         return hash;
6014 }
6015
6016 uint32_t isl_set_get_hash(struct isl_set *set)
6017 {
6018         int i;
6019         uint32_t hash;
6020
6021         if (!set)
6022                 return 0;
6023         set = isl_set_copy(set);
6024         set = isl_set_normalize(set);
6025         if (!set)
6026                 return 0;
6027
6028         hash = isl_hash_init();
6029         for (i = 0; i < set->n; ++i) {
6030                 uint32_t bset_hash;
6031                 bset_hash = isl_basic_set_get_hash(set->p[i]);
6032                 isl_hash_hash(hash, bset_hash);
6033         }
6034
6035         isl_set_free(set);
6036
6037         return hash;
6038 }
6039
6040 /* Check if the value for dimension dim is completely determined
6041  * by the values of the other parameters and variables.
6042  * That is, check if dimension dim is involved in an equality.
6043  */
6044 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
6045 {
6046         int i;
6047         unsigned nparam;
6048
6049         if (!bset)
6050                 return -1;
6051         nparam = isl_basic_set_n_param(bset);
6052         for (i = 0; i < bset->n_eq; ++i)
6053                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
6054                         return 1;
6055         return 0;
6056 }
6057
6058 /* Check if the value for dimension dim is completely determined
6059  * by the values of the other parameters and variables.
6060  * That is, check if dimension dim is involved in an equality
6061  * for each of the subsets.
6062  */
6063 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
6064 {
6065         int i;
6066
6067         if (!set)
6068                 return -1;
6069         for (i = 0; i < set->n; ++i) {
6070                 int unique;
6071                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
6072                 if (unique != 1)
6073                         return unique;
6074         }
6075         return 1;
6076 }
6077
6078 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
6079         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
6080 {
6081         int i;
6082
6083         if (!map)
6084                 return -1;
6085
6086         for (i = 0; i < map->n; ++i)
6087                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
6088                         return -1;
6089
6090         return 0;
6091 }
6092
6093 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
6094         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
6095 {
6096         int i;
6097
6098         if (!set)
6099                 return -1;
6100
6101         for (i = 0; i < set->n; ++i)
6102                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
6103                         return -1;
6104
6105         return 0;
6106 }
6107
6108 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
6109 {
6110         struct isl_dim *dim;
6111
6112         if (!bset)
6113                 return NULL;
6114
6115         if (bset->n_div == 0)
6116                 return bset;
6117
6118         bset = isl_basic_set_cow(bset);
6119         if (!bset)
6120                 return NULL;
6121
6122         dim = isl_basic_set_get_dim(bset);
6123         dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
6124         if (!dim)
6125                 goto error;
6126         isl_dim_free(bset->dim);
6127         bset->dim = dim;
6128         bset->n_div = 0;
6129
6130         return bset;
6131 error:
6132         isl_basic_set_free(bset);
6133         return NULL;
6134 }
6135
6136 __isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
6137 {
6138         int i;
6139         struct isl_dim *dim;
6140         unsigned n_div;
6141
6142         set = isl_set_align_divs(set);
6143
6144         if (!set)
6145                 return NULL;
6146         if (set->n == 0 || set->p[0]->n_div == 0)
6147                 return set;
6148
6149         set = isl_set_cow(set);
6150         if (!set)
6151                 return NULL;
6152
6153         n_div = set->p[0]->n_div;
6154         dim = isl_set_get_dim(set);
6155         dim = isl_dim_add(dim, isl_dim_set, n_div);
6156         if (!dim)
6157                 goto error;
6158         isl_dim_free(set->dim);
6159         set->dim = dim;
6160
6161         for (i = 0; i < set->n; ++i) {
6162                 set->p[i] = isl_basic_set_lift(set->p[i]);
6163                 if (!set->p[i])
6164                         goto error;
6165         }
6166
6167         return set;
6168 error:
6169         isl_set_free(set);
6170         return NULL;
6171 }
6172
6173 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
6174 {
6175         struct isl_dim *dim;
6176         struct isl_basic_map *bmap;
6177         unsigned n_set;
6178         unsigned n_div;
6179         unsigned n_param;
6180         unsigned total;
6181         int i, k, l;
6182
6183         set = isl_set_align_divs(set);
6184
6185         if (!set)
6186                 return NULL;
6187
6188         dim = isl_set_get_dim(set);
6189         if (set->n == 0 || set->p[0]->n_div == 0) {
6190                 isl_set_free(set);
6191                 return isl_map_identity(dim);
6192         }
6193
6194         n_div = set->p[0]->n_div;
6195         dim = isl_dim_map(dim);
6196         n_param = isl_dim_size(dim, isl_dim_param);
6197         n_set = isl_dim_size(dim, isl_dim_in);
6198         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
6199         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
6200         for (i = 0; i < n_set; ++i)
6201                 bmap = var_equal(bmap, i);
6202
6203         total = n_param + n_set + n_set + n_div;
6204         for (i = 0; i < n_div; ++i) {
6205                 k = isl_basic_map_alloc_inequality(bmap);
6206                 if (k < 0)
6207                         goto error;
6208                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
6209                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
6210                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
6211                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
6212                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
6213                             set->p[0]->div[i][0]);
6214
6215                 l = isl_basic_map_alloc_inequality(bmap);
6216                 if (l < 0)
6217                         goto error;
6218                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
6219                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
6220                             set->p[0]->div[i][0]);
6221                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
6222         }
6223
6224         isl_set_free(set);
6225         return isl_map_from_basic_map(bmap);
6226 error:
6227         isl_set_free(set);
6228         isl_basic_map_free(bmap);
6229         return NULL;
6230 }
6231
6232 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
6233 {
6234         unsigned dim;
6235         int size = 0;
6236
6237         if (!bset)
6238                 return -1;
6239
6240         dim = isl_basic_set_total_dim(bset);
6241         size += bset->n_eq * (1 + dim);
6242         size += bset->n_ineq * (1 + dim);
6243         size += bset->n_div * (2 + dim);
6244
6245         return size;
6246 }
6247
6248 int isl_set_size(__isl_keep isl_set *set)
6249 {
6250         int i;
6251         int size = 0;
6252
6253         if (!set)
6254                 return -1;
6255
6256         for (i = 0; i < set->n; ++i)
6257                 size += isl_basic_set_size(set->p[i]);
6258
6259         return size;
6260 }