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