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