isl_map.c

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