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