isl_map.c

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