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_set *isl_set_insert(__isl_take isl_set *set,
2218                 enum isl_dim_type type, unsigned pos, unsigned n)
2219 {
2220         return (isl_set *)isl_map_insert((isl_map *)set, type, pos, n);
2221 }
2222
2223 __isl_give isl_map *isl_map_add(__isl_take isl_map *map,
2224                 enum isl_dim_type type, unsigned n)
2225 {
2226         if (!map)
2227                 return NULL;
2228         return isl_map_insert(map, type, isl_map_dim(map, type), n);
2229 }
2230
2231 __isl_give isl_set *isl_set_add(__isl_take isl_set *set,
2232                 enum isl_dim_type type, unsigned n)
2233 {
2234         if (!set)
2235                 return NULL;
2236         isl_assert(set->ctx, type != isl_dim_in, goto error);
2237         return (isl_set *)isl_map_add((isl_map *)set, type, n);
2238 error:
2239         isl_set_free(set);
2240         return NULL;
2241 }
2242
2243 __isl_give isl_basic_map *isl_basic_map_move_dims(
2244         __isl_take isl_basic_map *bmap,
2245         enum isl_dim_type dst_type, unsigned dst_pos,
2246         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2247 {
2248         int i;
2249         struct isl_dim_map *dim_map;
2250         struct isl_basic_map *res;
2251         enum isl_dim_type t;
2252         unsigned total, off;
2253
2254         if (!bmap)
2255                 return NULL;
2256         if (n == 0)
2257                 return bmap;
2258
2259         isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type),
2260                 goto error);
2261
2262         if (dst_type == src_type && dst_pos == src_pos)
2263                 return bmap;
2264
2265         isl_assert(bmap->ctx, dst_type != src_type, goto error);
2266
2267         if (pos(bmap->dim, dst_type) + dst_pos ==
2268             pos(bmap->dim, src_type) + src_pos +
2269                                             ((src_type < dst_type) ? n : 0)) {
2270                 bmap = isl_basic_map_cow(bmap);
2271                 if (!bmap)
2272                         return NULL;
2273
2274                 bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
2275                                                 src_type, src_pos, n);
2276                 if (!bmap->dim)
2277                         goto error;
2278
2279                 bmap = isl_basic_map_finalize(bmap);
2280
2281                 return bmap;
2282         }
2283
2284         total = isl_basic_map_total_dim(bmap);
2285         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2286
2287         off = 0;
2288         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2289                 unsigned size = isl_dim_size(bmap->dim, t);
2290                 if (t == dst_type) {
2291                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2292                                             0, dst_pos, off);
2293                         off += dst_pos;
2294                         isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
2295                                             src_pos, n, off);
2296                         off += n;
2297                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2298                                             dst_pos, size - dst_pos, off);
2299                         off += size - dst_pos;
2300                 } else if (t == src_type) {
2301                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2302                                             0, src_pos, off);
2303                         off += src_pos;
2304                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2305                                         src_pos + n, size - src_pos - n, off);
2306                         off += size - src_pos - n;
2307                 } else {
2308                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2309                         off += size;
2310                 }
2311         }
2312         isl_dim_map_div(dim_map, bmap, off);
2313
2314         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2315                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2316         bmap = add_constraints_dim_map(res, bmap, dim_map);
2317
2318         bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
2319                                         src_type, src_pos, n);
2320         if (!bmap->dim)
2321                 goto error;
2322
2323         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2324         bmap = isl_basic_map_gauss(bmap, NULL);
2325         bmap = isl_basic_map_finalize(bmap);
2326
2327         return bmap;
2328 error:
2329         isl_basic_map_free(bmap);
2330         return NULL;
2331 }
2332
2333 __isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
2334         enum isl_dim_type dst_type, unsigned dst_pos,
2335         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2336 {
2337         return (isl_basic_set *)isl_basic_map_move_dims(
2338                 (isl_basic_map *)bset, dst_type, dst_pos, src_type, src_pos, n);
2339 }
2340
2341 __isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
2342         enum isl_dim_type dst_type, unsigned dst_pos,
2343         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2344 {
2345         if (!set)
2346                 return NULL;
2347         isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
2348         return (isl_set *)isl_map_move_dims((isl_map *)set, dst_type, dst_pos,
2349                                         src_type, src_pos, n);
2350 error:
2351         isl_set_free(set);
2352         return NULL;
2353 }
2354
2355 __isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
2356         enum isl_dim_type dst_type, unsigned dst_pos,
2357         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2358 {
2359         int i;
2360
2361         if (!map)
2362                 return NULL;
2363         if (n == 0)
2364                 return map;
2365
2366         isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type),
2367                 goto error);
2368
2369         if (dst_type == src_type && dst_pos == src_pos)
2370                 return map;
2371
2372         isl_assert(map->ctx, dst_type != src_type, goto error);
2373
2374         map = isl_map_cow(map);
2375         if (!map)
2376                 return NULL;
2377
2378         map->dim = isl_dim_move(map->dim, dst_type, dst_pos, src_type, src_pos, n);
2379         if (!map->dim)
2380                 goto error;
2381
2382         for (i = 0; i < map->n; ++i) {
2383                 map->p[i] = isl_basic_map_move_dims(map->p[i],
2384                                                 dst_type, dst_pos,
2385                                                 src_type, src_pos, n);
2386                 if (!map->p[i])
2387                         goto error;
2388         }
2389
2390         return map;
2391 error:
2392         isl_map_free(map);
2393         return NULL;
2394 }
2395
2396 /* Move the specified dimensions to the last columns right before
2397  * the divs.  Don't change the dimension specification of bmap.
2398  * That's the responsibility of the caller.
2399  */
2400 static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
2401         enum isl_dim_type type, unsigned first, unsigned n)
2402 {
2403         struct isl_dim_map *dim_map;
2404         struct isl_basic_map *res;
2405         enum isl_dim_type t;
2406         unsigned total, off;
2407
2408         if (!bmap)
2409                 return NULL;
2410         if (pos(bmap->dim, type) + first + n == 1 + isl_dim_total(bmap->dim))
2411                 return bmap;
2412
2413         total = isl_basic_map_total_dim(bmap);
2414         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2415
2416         off = 0;
2417         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2418                 unsigned size = isl_dim_size(bmap->dim, t);
2419                 if (t == type) {
2420                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2421                                             0, first, off);
2422                         off += first;
2423                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2424                                             first, n, total - bmap->n_div - n);
2425                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2426                                             first + n, size - (first + n), off);
2427                         off += size - (first + n);
2428                 } else {
2429                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2430                         off += size;
2431                 }
2432         }
2433         isl_dim_map_div(dim_map, bmap, off + n);
2434
2435         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2436                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2437         res = add_constraints_dim_map(res, bmap, dim_map);
2438         return res;
2439 }
2440
2441 /* Turn the n dimensions of type type, starting at first
2442  * into existentially quantified variables.
2443  */
2444 __isl_give isl_basic_map *isl_basic_map_project_out(
2445                 __isl_take isl_basic_map *bmap,
2446                 enum isl_dim_type type, unsigned first, unsigned n)
2447 {
2448         int i;
2449         size_t row_size;
2450         isl_int **new_div;
2451         isl_int *old;
2452
2453         if (n == 0)
2454                 return bmap;
2455
2456         if (!bmap)
2457                 return NULL;
2458
2459         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
2460                 return isl_basic_map_remove(bmap, type, first, n);
2461
2462         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
2463                         goto error);
2464
2465         bmap = move_last(bmap, type, first, n);
2466         bmap = isl_basic_map_cow(bmap);
2467         if (!bmap)
2468                 return NULL;
2469
2470         row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra;
2471         old = bmap->block2.data;
2472         bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
2473                                         (bmap->extra + n) * (1 + row_size));
2474         if (!bmap->block2.data)
2475                 goto error;
2476         new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
2477         if (!new_div)
2478                 goto error;
2479         for (i = 0; i < n; ++i) {
2480                 new_div[i] = bmap->block2.data +
2481                                 (bmap->extra + i) * (1 + row_size);
2482                 isl_seq_clr(new_div[i], 1 + row_size);
2483         }
2484         for (i = 0; i < bmap->extra; ++i)
2485                 new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
2486         free(bmap->div);
2487         bmap->div = new_div;
2488         bmap->n_div += n;
2489         bmap->extra += n;
2490
2491         bmap->dim = isl_dim_drop(bmap->dim, type, first, n);
2492         if (!bmap->dim)
2493                 goto error;
2494         bmap = isl_basic_map_simplify(bmap);
2495         bmap = isl_basic_map_drop_redundant_divs(bmap);
2496         return isl_basic_map_finalize(bmap);
2497 error:
2498         isl_basic_map_free(bmap);
2499         return NULL;
2500 }
2501
2502 /* Turn the n dimensions of type type, starting at first
2503  * into existentially quantified variables.
2504  */
2505 struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
2506                 enum isl_dim_type type, unsigned first, unsigned n)
2507 {
2508         return (isl_basic_set *)isl_basic_map_project_out(
2509                         (isl_basic_map *)bset, type, first, n);
2510 }
2511
2512 /* Turn the n dimensions of type type, starting at first
2513  * into existentially quantified variables.
2514  */
2515 __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
2516                 enum isl_dim_type type, unsigned first, unsigned n)
2517 {
2518         int i;
2519
2520         if (!map)
2521                 return NULL;
2522
2523         if (n == 0)
2524                 return map;
2525
2526         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
2527
2528         map = isl_map_cow(map);
2529         if (!map)
2530                 return NULL;
2531
2532         map->dim = isl_dim_drop(map->dim, type, first, n);
2533         if (!map->dim)
2534                 goto error;
2535
2536         for (i = 0; i < map->n; ++i) {
2537                 map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
2538                 if (!map->p[i])
2539                         goto error;
2540         }
2541
2542         return map;
2543 error:
2544         isl_map_free(map);
2545         return NULL;
2546 }
2547
2548 /* Turn the n dimensions of type type, starting at first
2549  * into existentially quantified variables.
2550  */
2551 __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
2552                 enum isl_dim_type type, unsigned first, unsigned n)
2553 {
2554         return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n);
2555 }
2556
2557 static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2558 {
2559         int i, j;
2560
2561         for (i = 0; i < n; ++i) {
2562                 j = isl_basic_map_alloc_div(bmap);
2563                 if (j < 0)
2564                         goto error;
2565                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2566         }
2567         return bmap;
2568 error:
2569         isl_basic_map_free(bmap);
2570         return NULL;
2571 }
2572
2573 struct isl_basic_map *isl_basic_map_apply_range(
2574                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2575 {
2576         struct isl_dim *dim_result = NULL;
2577         struct isl_basic_map *bmap;
2578         unsigned n_in, n_out, n, nparam, total, pos;
2579         struct isl_dim_map *dim_map1, *dim_map2;
2580
2581         if (!bmap1 || !bmap2)
2582                 goto error;
2583
2584         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2585                                   isl_dim_copy(bmap2->dim));
2586
2587         n_in = isl_basic_map_n_in(bmap1);
2588         n_out = isl_basic_map_n_out(bmap2);
2589         n = isl_basic_map_n_out(bmap1);
2590         nparam = isl_basic_map_n_param(bmap1);
2591
2592         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2593         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2594         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2595         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2596         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2597         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2598         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2599         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2600         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2601         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2602         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2603
2604         bmap = isl_basic_map_alloc_dim(dim_result,
2605                         bmap1->n_div + bmap2->n_div + n,
2606                         bmap1->n_eq + bmap2->n_eq,
2607                         bmap1->n_ineq + bmap2->n_ineq);
2608         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2609         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2610         bmap = add_divs(bmap, n);
2611         bmap = isl_basic_map_simplify(bmap);
2612         bmap = isl_basic_map_drop_redundant_divs(bmap);
2613         return isl_basic_map_finalize(bmap);
2614 error:
2615         isl_basic_map_free(bmap1);
2616         isl_basic_map_free(bmap2);
2617         return NULL;
2618 }
2619
2620 struct isl_basic_set *isl_basic_set_apply(
2621                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2622 {
2623         if (!bset || !bmap)
2624                 goto error;
2625
2626         isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
2627                     goto error);
2628
2629         return (struct isl_basic_set *)
2630                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2631 error:
2632         isl_basic_set_free(bset);
2633         isl_basic_map_free(bmap);
2634         return NULL;
2635 }
2636
2637 struct isl_basic_map *isl_basic_map_apply_domain(
2638                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2639 {
2640         if (!bmap1 || !bmap2)
2641                 goto error;
2642
2643         isl_assert(bmap1->ctx,
2644             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2645         isl_assert(bmap1->ctx,
2646             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2647             goto error);
2648
2649         bmap1 = isl_basic_map_reverse(bmap1);
2650         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2651         return isl_basic_map_reverse(bmap1);
2652 error:
2653         isl_basic_map_free(bmap1);
2654         isl_basic_map_free(bmap2);
2655         return NULL;
2656 }
2657
2658 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
2659  * A \cap B -> f(A) + f(B)
2660  */
2661 struct isl_basic_map *isl_basic_map_sum(
2662                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2663 {
2664         unsigned n_in, n_out, nparam, total, pos;
2665         struct isl_basic_map *bmap = NULL;
2666         struct isl_dim_map *dim_map1, *dim_map2;
2667         int i;
2668
2669         if (!bmap1 || !bmap2)
2670                 goto error;
2671
2672         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
2673                 goto error);
2674
2675         nparam = isl_basic_map_n_param(bmap1);
2676         n_in = isl_basic_map_n_in(bmap1);
2677         n_out = isl_basic_map_n_out(bmap1);
2678
2679         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
2680         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2681         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
2682         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2683         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
2684         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2685         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2686         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
2687         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2688         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2689         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
2690
2691         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
2692                         bmap1->n_div + bmap2->n_div + 2 * n_out,
2693                         bmap1->n_eq + bmap2->n_eq + n_out,
2694                         bmap1->n_ineq + bmap2->n_ineq);
2695         for (i = 0; i < n_out; ++i) {
2696                 int j = isl_basic_map_alloc_equality(bmap);
2697                 if (j < 0)
2698                         goto error;
2699                 isl_seq_clr(bmap->eq[j], 1+total);
2700                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
2701                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
2702                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
2703         }
2704         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2705         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2706         bmap = add_divs(bmap, 2 * n_out);
2707
2708         bmap = isl_basic_map_simplify(bmap);
2709         return isl_basic_map_finalize(bmap);
2710 error:
2711         isl_basic_map_free(bmap);
2712         isl_basic_map_free(bmap1);
2713         isl_basic_map_free(bmap2);
2714         return NULL;
2715 }
2716
2717 /* Given two maps A -> f(A) and B -> g(B), construct a map
2718  * A \cap B -> f(A) + f(B)
2719  */
2720 struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2)
2721 {
2722         struct isl_map *result;
2723         int i, j;
2724
2725         if (!map1 || !map2)
2726                 goto error;
2727
2728         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2729
2730         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2731                                 map1->n * map2->n, 0);
2732         if (!result)
2733                 goto error;
2734         for (i = 0; i < map1->n; ++i)
2735                 for (j = 0; j < map2->n; ++j) {
2736                         struct isl_basic_map *part;
2737                         part = isl_basic_map_sum(
2738                                     isl_basic_map_copy(map1->p[i]),
2739                                     isl_basic_map_copy(map2->p[j]));
2740                         if (isl_basic_map_is_empty(part))
2741                                 isl_basic_map_free(part);
2742                         else
2743                                 result = isl_map_add_basic_map(result, part);
2744                         if (!result)
2745                                 goto error;
2746                 }
2747         isl_map_free(map1);
2748         isl_map_free(map2);
2749         return result;
2750 error:
2751         isl_map_free(map1);
2752         isl_map_free(map2);
2753         return NULL;
2754 }
2755
2756 __isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
2757         __isl_take isl_set *set2)
2758 {
2759         return (isl_set *)isl_map_sum((isl_map *)set1, (isl_map *)set2);
2760 }
2761
2762 /* Given a basic map A -> f(A), construct A -> -f(A).
2763  */
2764 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
2765 {
2766         int i, j;
2767         unsigned off, n;
2768
2769         bmap = isl_basic_map_cow(bmap);
2770         if (!bmap)
2771                 return NULL;
2772
2773         n = isl_basic_map_dim(bmap, isl_dim_out);
2774         off = isl_basic_map_offset(bmap, isl_dim_out);
2775         for (i = 0; i < bmap->n_eq; ++i)
2776                 for (j = 0; j < n; ++j)
2777                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
2778         for (i = 0; i < bmap->n_ineq; ++i)
2779                 for (j = 0; j < n; ++j)
2780                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
2781         for (i = 0; i < bmap->n_div; ++i)
2782                 for (j = 0; j < n; ++j)
2783                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
2784         return isl_basic_map_finalize(bmap);
2785 }
2786
2787 /* Given a map A -> f(A), construct A -> -f(A).
2788  */
2789 struct isl_map *isl_map_neg(struct isl_map *map)
2790 {
2791         int i;
2792
2793         map = isl_map_cow(map);
2794         if (!map)
2795                 return NULL;
2796
2797         for (i = 0; i < map->n; ++i) {
2798                 map->p[i] = isl_basic_map_neg(map->p[i]);
2799                 if (!map->p[i])
2800                         goto error;
2801         }
2802
2803         return map;
2804 error:
2805         isl_map_free(map);
2806         return NULL;
2807 }
2808
2809 __isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
2810 {
2811         return (isl_set *)isl_map_neg((isl_map *)set);
2812 }
2813
2814 /* Given a basic map A -> f(A) and an integer d, construct a basic map
2815  * A -> floor(f(A)/d).
2816  */
2817 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
2818                 isl_int d)
2819 {
2820         unsigned n_in, n_out, nparam, total, pos;
2821         struct isl_basic_map *result = NULL;
2822         struct isl_dim_map *dim_map;
2823         int i;
2824
2825         if (!bmap)
2826                 return NULL;
2827
2828         nparam = isl_basic_map_n_param(bmap);
2829         n_in = isl_basic_map_n_in(bmap);
2830         n_out = isl_basic_map_n_out(bmap);
2831
2832         total = nparam + n_in + n_out + bmap->n_div + n_out;
2833         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2834         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
2835         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
2836         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
2837         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
2838
2839         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
2840                         bmap->n_div + n_out,
2841                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
2842         result = add_constraints_dim_map(result, bmap, dim_map);
2843         result = add_divs(result, n_out);
2844         for (i = 0; i < n_out; ++i) {
2845                 int j;
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_neg(result->ineq[j][1+nparam+n_in+i], d);
2851                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
2852                 j = isl_basic_map_alloc_inequality(result);
2853                 if (j < 0)
2854                         goto error;
2855                 isl_seq_clr(result->ineq[j], 1+total);
2856                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
2857                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
2858                 isl_int_sub_ui(result->ineq[j][0], d, 1);
2859         }
2860
2861         result = isl_basic_map_simplify(result);
2862         return isl_basic_map_finalize(result);
2863 error:
2864         isl_basic_map_free(result);
2865         return NULL;
2866 }
2867
2868 /* Given a map A -> f(A) and an integer d, construct a map
2869  * A -> floor(f(A)/d).
2870  */
2871 struct isl_map *isl_map_floordiv(struct isl_map *map, isl_int d)
2872 {
2873         int i;
2874
2875         map = isl_map_cow(map);
2876         if (!map)
2877                 return NULL;
2878
2879         ISL_F_CLR(map, ISL_MAP_DISJOINT);
2880         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2881         for (i = 0; i < map->n; ++i) {
2882                 map->p[i] = isl_basic_map_floordiv(map->p[i], d);
2883                 if (!map->p[i])
2884                         goto error;
2885         }
2886
2887         return map;
2888 error:
2889         isl_map_free(map);
2890         return NULL;
2891 }
2892
2893 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
2894 {
2895         int i;
2896         unsigned nparam;
2897         unsigned n_in;
2898
2899         i = isl_basic_map_alloc_equality(bmap);
2900         if (i < 0)
2901                 goto error;
2902         nparam = isl_basic_map_n_param(bmap);
2903         n_in = isl_basic_map_n_in(bmap);
2904         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2905         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2906         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2907         return isl_basic_map_finalize(bmap);
2908 error:
2909         isl_basic_map_free(bmap);
2910         return NULL;
2911 }
2912
2913 /* Add a constraints to "bmap" expressing i_pos < o_pos
2914  */
2915 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2916 {
2917         int i;
2918         unsigned nparam;
2919         unsigned n_in;
2920
2921         i = isl_basic_map_alloc_inequality(bmap);
2922         if (i < 0)
2923                 goto error;
2924         nparam = isl_basic_map_n_param(bmap);
2925         n_in = isl_basic_map_n_in(bmap);
2926         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2927         isl_int_set_si(bmap->ineq[i][0], -1);
2928         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2929         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2930         return isl_basic_map_finalize(bmap);
2931 error:
2932         isl_basic_map_free(bmap);
2933         return NULL;
2934 }
2935
2936 /* Add a constraint to "bmap" expressing i_pos <= o_pos
2937  */
2938 static __isl_give isl_basic_map *var_less_or_equal(
2939         __isl_take isl_basic_map *bmap, unsigned pos)
2940 {
2941         int i;
2942         unsigned nparam;
2943         unsigned n_in;
2944
2945         i = isl_basic_map_alloc_inequality(bmap);
2946         if (i < 0)
2947                 goto error;
2948         nparam = isl_basic_map_n_param(bmap);
2949         n_in = isl_basic_map_n_in(bmap);
2950         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2951         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2952         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2953         return isl_basic_map_finalize(bmap);
2954 error:
2955         isl_basic_map_free(bmap);
2956         return NULL;
2957 }
2958
2959 /* Add a constraints to "bmap" expressing i_pos > o_pos
2960  */
2961 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
2962 {
2963         int i;
2964         unsigned nparam;
2965         unsigned n_in;
2966
2967         i = isl_basic_map_alloc_inequality(bmap);
2968         if (i < 0)
2969                 goto error;
2970         nparam = isl_basic_map_n_param(bmap);
2971         n_in = isl_basic_map_n_in(bmap);
2972         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2973         isl_int_set_si(bmap->ineq[i][0], -1);
2974         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2975         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2976         return isl_basic_map_finalize(bmap);
2977 error:
2978         isl_basic_map_free(bmap);
2979         return NULL;
2980 }
2981
2982 /* Add a constraint to "bmap" expressing i_pos >= o_pos
2983  */
2984 static __isl_give isl_basic_map *var_more_or_equal(
2985         __isl_take isl_basic_map *bmap, unsigned pos)
2986 {
2987         int i;
2988         unsigned nparam;
2989         unsigned n_in;
2990
2991         i = isl_basic_map_alloc_inequality(bmap);
2992         if (i < 0)
2993                 goto error;
2994         nparam = isl_basic_map_n_param(bmap);
2995         n_in = isl_basic_map_n_in(bmap);
2996         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2997         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2998         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2999         return isl_basic_map_finalize(bmap);
3000 error:
3001         isl_basic_map_free(bmap);
3002         return NULL;
3003 }
3004
3005 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
3006 {
3007         int i;
3008         struct isl_basic_map *bmap;
3009         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
3010         if (!bmap)
3011                 return NULL;
3012         for (i = 0; i < n_equal && bmap; ++i)
3013                 bmap = var_equal(bmap, i);
3014         return isl_basic_map_finalize(bmap);
3015 }
3016
3017 /* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
3018  */
3019 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
3020 {
3021         int i;
3022         struct isl_basic_map *bmap;
3023         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
3024         if (!bmap)
3025                 return NULL;
3026         for (i = 0; i < pos && bmap; ++i)
3027                 bmap = var_equal(bmap, i);
3028         if (bmap)
3029                 bmap = var_less(bmap, pos);
3030         return isl_basic_map_finalize(bmap);
3031 }
3032
3033 /* Return a relation on of dimension "dim" expressing i_[0..pos] <<= o_[0..pos]
3034  */
3035 __isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
3036         __isl_take isl_dim *dim, unsigned pos)
3037 {
3038         int i;
3039         isl_basic_map *bmap;
3040
3041         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
3042         for (i = 0; i < pos; ++i)
3043                 bmap = var_equal(bmap, i);
3044         bmap = var_less_or_equal(bmap, pos);
3045         return isl_basic_map_finalize(bmap);
3046 }
3047
3048 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
3049  */
3050 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
3051 {
3052         int i;
3053         struct isl_basic_map *bmap;
3054         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
3055         if (!bmap)
3056                 return NULL;
3057         for (i = 0; i < pos && bmap; ++i)
3058                 bmap = var_equal(bmap, i);
3059         if (bmap)
3060                 bmap = var_more(bmap, pos);
3061         return isl_basic_map_finalize(bmap);
3062 }
3063
3064 /* Return a relation on of dimension "dim" expressing i_[0..pos] >>= o_[0..pos]
3065  */
3066 __isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
3067         __isl_take isl_dim *dim, unsigned pos)
3068 {
3069         int i;
3070         isl_basic_map *bmap;
3071
3072         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
3073         for (i = 0; i < pos; ++i)
3074                 bmap = var_equal(bmap, i);
3075         bmap = var_more_or_equal(bmap, pos);
3076         return isl_basic_map_finalize(bmap);
3077 }
3078
3079 static __isl_give isl_map *map_lex_lte_first(__isl_take isl_dim *dims,
3080         unsigned n, int equal)
3081 {
3082         struct isl_map *map;
3083         int i;
3084
3085         if (n == 0 && equal)
3086                 return isl_map_universe(dims);
3087
3088         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3089
3090         for (i = 0; i + 1 < n; ++i)
3091                 map = isl_map_add_basic_map(map,
3092                                   isl_basic_map_less_at(isl_dim_copy(dims), i));
3093         if (n > 0) {
3094                 if (equal)
3095                         map = isl_map_add_basic_map(map,
3096                               isl_basic_map_less_or_equal_at(dims, n - 1));
3097                 else
3098                         map = isl_map_add_basic_map(map,
3099                               isl_basic_map_less_at(dims, n - 1));
3100         } else
3101                 isl_dim_free(dims);
3102
3103         return map;
3104 }
3105
3106 static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
3107 {
3108         if (!dims)
3109                 return NULL;
3110         return map_lex_lte_first(dims, dims->n_out, equal);
3111 }
3112
3113 __isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_dim *dim, unsigned n)
3114 {
3115         return map_lex_lte_first(dim, n, 0);
3116 }
3117
3118 __isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n)
3119 {
3120         return map_lex_lte_first(dim, n, 1);
3121 }
3122
3123 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
3124 {
3125         return map_lex_lte(isl_dim_map(set_dim), 0);
3126 }
3127
3128 __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
3129 {
3130         return map_lex_lte(isl_dim_map(set_dim), 1);
3131 }
3132
3133 static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims,
3134         unsigned n, int equal)
3135 {
3136         struct isl_map *map;
3137         int i;
3138
3139         if (n == 0 && equal)
3140                 return isl_map_universe(dims);
3141
3142         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3143
3144         for (i = 0; i + 1 < n; ++i)
3145                 map = isl_map_add_basic_map(map,
3146                                   isl_basic_map_more_at(isl_dim_copy(dims), i));
3147         if (n > 0) {
3148                 if (equal)
3149                         map = isl_map_add_basic_map(map,
3150                               isl_basic_map_more_or_equal_at(dims, n - 1));
3151                 else
3152                         map = isl_map_add_basic_map(map,
3153                               isl_basic_map_more_at(dims, n - 1));
3154         } else
3155                 isl_dim_free(dims);
3156
3157         return map;
3158 }
3159
3160 static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
3161 {
3162         if (!dims)
3163                 return NULL;
3164         return map_lex_gte_first(dims, dims->n_out, equal);
3165 }
3166
3167 __isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_dim *dim, unsigned n)
3168 {
3169         return map_lex_gte_first(dim, n, 0);
3170 }
3171
3172 __isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n)
3173 {
3174         return map_lex_gte_first(dim, n, 1);
3175 }
3176
3177 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
3178 {
3179         return map_lex_gte(isl_dim_map(set_dim), 0);
3180 }
3181
3182 __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim)
3183 {
3184         return map_lex_gte(isl_dim_map(set_dim), 1);
3185 }
3186
3187 struct isl_basic_map *isl_basic_map_from_basic_set(
3188                 struct isl_basic_set *bset, struct isl_dim *dim)
3189 {
3190         struct isl_basic_map *bmap;
3191
3192         bset = isl_basic_set_cow(bset);
3193         if (!bset || !dim)
3194                 goto error;
3195
3196         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
3197         isl_dim_free(bset->dim);
3198         bmap = (struct isl_basic_map *) bset;
3199         bmap->dim = dim;
3200         return isl_basic_map_finalize(bmap);
3201 error:
3202         isl_basic_set_free(bset);
3203         isl_dim_free(dim);
3204         return NULL;
3205 }
3206
3207 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
3208 {
3209         if (!bmap)
3210                 goto error;
3211         if (bmap->dim->n_in == 0)
3212                 return (struct isl_basic_set *)bmap;
3213         bmap = isl_basic_map_cow(bmap);
3214         if (!bmap)
3215                 goto error;
3216         bmap->dim = isl_dim_as_set_dim(bmap->dim);
3217         if (!bmap->dim)
3218                 goto error;
3219         bmap = isl_basic_map_finalize(bmap);
3220         return (struct isl_basic_set *)bmap;
3221 error:
3222         isl_basic_map_free(bmap);
3223         return NULL;
3224 }
3225
3226 /* For a div d = floor(f/m), add the constraints
3227  *
3228  *              f - m d >= 0
3229  *              -(f-(n-1)) + m d >= 0
3230  *
3231  * Note that the second constraint is the negation of
3232  *
3233  *              f - m d >= n
3234  */
3235 int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
3236         unsigned pos, isl_int *div)
3237 {
3238         int i, j;
3239         unsigned total = isl_basic_map_total_dim(bmap);
3240
3241         i = isl_basic_map_alloc_inequality(bmap);
3242         if (i < 0)
3243                 return -1;
3244         isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
3245         isl_int_neg(bmap->ineq[i][1 + pos], div[0]);
3246
3247         j = isl_basic_map_alloc_inequality(bmap);
3248         if (j < 0)
3249                 return -1;
3250         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
3251         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][1 + pos]);
3252         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
3253         return j;
3254 }
3255
3256 int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
3257         unsigned pos, isl_int *div)
3258 {
3259         return isl_basic_map_add_div_constraints_var((isl_basic_map *)bset,
3260                                                         pos, div);
3261 }
3262
3263 int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
3264 {
3265         unsigned total = isl_basic_map_total_dim(bmap);
3266         unsigned div_pos = total - bmap->n_div + div;
3267
3268         return isl_basic_map_add_div_constraints_var(bmap, div_pos,
3269                                                         bmap->div[div]);
3270 }
3271
3272 struct isl_basic_set *isl_basic_map_underlying_set(
3273                 struct isl_basic_map *bmap)
3274 {
3275         if (!bmap)
3276                 goto error;
3277         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 &&
3278             bmap->n_div == 0 && !isl_dim_get_tuple_name(bmap->dim, isl_dim_out))
3279                 return (struct isl_basic_set *)bmap;
3280         bmap = isl_basic_map_cow(bmap);
3281         if (!bmap)
3282                 goto error;
3283         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
3284         if (!bmap->dim)
3285                 goto error;
3286         bmap->extra -= bmap->n_div;
3287         bmap->n_div = 0;
3288         bmap = isl_basic_map_finalize(bmap);
3289         return (struct isl_basic_set *)bmap;
3290 error:
3291         return NULL;
3292 }
3293
3294 __isl_give isl_basic_set *isl_basic_set_underlying_set(
3295                 __isl_take isl_basic_set *bset)
3296 {
3297         return isl_basic_map_underlying_set((isl_basic_map *)bset);
3298 }
3299
3300 struct isl_basic_map *isl_basic_map_overlying_set(
3301         struct isl_basic_set *bset, struct isl_basic_map *like)
3302 {
3303         struct isl_basic_map *bmap;
3304         struct isl_ctx *ctx;
3305         unsigned total;
3306         int i;
3307
3308         if (!bset || !like)
3309                 goto error;
3310         ctx = bset->ctx;
3311         isl_assert(ctx, bset->n_div == 0, goto error);
3312         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
3313         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
3314                         goto error);
3315         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
3316                 isl_basic_map_free(like);
3317                 return (struct isl_basic_map *)bset;
3318         }
3319         bset = isl_basic_set_cow(bset);
3320         if (!bset)
3321                 goto error;
3322         total = bset->dim->n_out + bset->extra;
3323         bmap = (struct isl_basic_map *)bset;
3324         isl_dim_free(bmap->dim);
3325         bmap->dim = isl_dim_copy(like->dim);
3326         if (!bmap->dim)
3327                 goto error;
3328         bmap->n_div = like->n_div;
3329         bmap->extra += like->n_div;
3330         if (bmap->extra) {
3331                 unsigned ltotal;
3332                 ltotal = total - bmap->extra + like->extra;
3333                 if (ltotal > total)
3334                         ltotal = total;
3335                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
3336                                         bmap->extra * (1 + 1 + total));
3337                 if (isl_blk_is_error(bmap->block2))
3338                         goto error;
3339                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
3340                                                 bmap->extra);
3341                 if (!bmap->div)
3342                         goto error;
3343                 for (i = 0; i < bmap->extra; ++i)
3344                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
3345                 for (i = 0; i < like->n_div; ++i) {
3346                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
3347                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
3348                 }
3349                 bmap = isl_basic_map_extend_constraints(bmap,
3350                                                         0, 2 * like->n_div);
3351                 for (i = 0; i < like->n_div; ++i) {
3352                         if (isl_int_is_zero(bmap->div[i][0]))
3353                                 continue;
3354                         if (isl_basic_map_add_div_constraints(bmap, i) < 0)
3355                                 goto error;
3356                 }
3357         }
3358         isl_basic_map_free(like);
3359         bmap = isl_basic_map_simplify(bmap);
3360         bmap = isl_basic_map_finalize(bmap);
3361         return bmap;
3362 error:
3363         isl_basic_map_free(like);
3364         isl_basic_set_free(bset);
3365         return NULL;
3366 }
3367
3368 struct isl_basic_set *isl_basic_set_from_underlying_set(
3369         struct isl_basic_set *bset, struct isl_basic_set *like)
3370 {
3371         return (struct isl_basic_set *)
3372                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
3373 }
3374
3375 struct isl_set *isl_set_from_underlying_set(
3376         struct isl_set *set, struct isl_basic_set *like)
3377 {
3378         int i;
3379
3380         if (!set || !like)
3381                 goto error;
3382         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
3383                     goto error);
3384         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
3385                 isl_basic_set_free(like);
3386                 return set;
3387         }
3388         set = isl_set_cow(set);
3389         if (!set)
3390                 goto error;
3391         for (i = 0; i < set->n; ++i) {
3392                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
3393                                                       isl_basic_set_copy(like));
3394                 if (!set->p[i])
3395                         goto error;
3396         }
3397         isl_dim_free(set->dim);
3398         set->dim = isl_dim_copy(like->dim);
3399         if (!set->dim)
3400                 goto error;
3401         isl_basic_set_free(like);
3402         return set;
3403 error:
3404         isl_basic_set_free(like);
3405         isl_set_free(set);
3406         return NULL;
3407 }
3408
3409 struct isl_set *isl_map_underlying_set(struct isl_map *map)
3410 {
3411         int i;
3412
3413         map = isl_map_cow(map);
3414         if (!map)
3415                 return NULL;
3416         map->dim = isl_dim_cow(map->dim);
3417         if (!map->dim)
3418                 goto error;
3419
3420         for (i = 1; i < map->n; ++i)
3421                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
3422                                 goto error);
3423         for (i = 0; i < map->n; ++i) {
3424                 map->p[i] = (struct isl_basic_map *)
3425                                 isl_basic_map_underlying_set(map->p[i]);
3426                 if (!map->p[i])
3427                         goto error;
3428         }
3429         if (map->n == 0)
3430                 map->dim = isl_dim_underlying(map->dim, 0);
3431         else {
3432                 isl_dim_free(map->dim);
3433                 map->dim = isl_dim_copy(map->p[0]->dim);
3434         }
3435         if (!map->dim)
3436                 goto error;
3437         return (struct isl_set *)map;
3438 error:
3439         isl_map_free(map);
3440         return NULL;
3441 }
3442
3443 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
3444 {
3445         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
3446 }
3447
3448 static __isl_give isl_basic_map *isl_basic_map_reset_dim(
3449         __isl_take isl_basic_map *bmap, __isl_take isl_dim *dim)
3450 {
3451         bmap = isl_basic_map_cow(bmap);
3452         if (!bmap || !dim)
3453                 goto error;
3454
3455         isl_dim_free(bmap->dim);
3456         bmap->dim = dim;
3457
3458         bmap = isl_basic_map_finalize(bmap);
3459
3460         return bmap;
3461 error:
3462         isl_basic_map_free(bmap);
3463         isl_dim_free(dim);
3464         return NULL;
3465 }
3466
3467 static __isl_give isl_basic_set *isl_basic_set_reset_dim(
3468         __isl_take isl_basic_set *bset, __isl_take isl_dim *dim)
3469 {
3470         return (isl_basic_set *)isl_basic_map_reset_dim((isl_basic_map *)bset,
3471                                                         dim);
3472 }
3473
3474 __isl_give isl_map *isl_map_reset_dim(__isl_take isl_map *map,
3475         __isl_take isl_dim *dim)
3476 {
3477         int i;
3478
3479         map = isl_map_cow(map);
3480         if (!map || !dim)
3481                 goto error;
3482
3483         for (i = 0; i < map->n; ++i) {
3484                 map->p[i] = isl_basic_map_reset_dim(map->p[i],
3485                                                     isl_dim_copy(dim));
3486                 if (!map->p[i])
3487                         goto error;
3488         }
3489         isl_dim_free(map->dim);
3490         map->dim = dim;
3491
3492         return map;
3493 error:
3494         isl_map_free(map);
3495         isl_dim_free(dim);
3496         return NULL;
3497 }
3498
3499 __isl_give isl_set *isl_set_reset_dim(__isl_take isl_set *set,
3500         __isl_take isl_dim *dim)
3501 {
3502         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
3503 }
3504
3505 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
3506 {
3507         isl_dim *dim;
3508         struct isl_basic_set *domain;
3509         unsigned n_in;
3510         unsigned n_out;
3511
3512         if (!bmap)
3513                 return NULL;
3514         dim = isl_dim_domain(isl_basic_map_get_dim(bmap));
3515
3516         n_in = isl_basic_map_n_in(bmap);
3517         n_out = isl_basic_map_n_out(bmap);
3518         domain = isl_basic_set_from_basic_map(bmap);
3519         domain = isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
3520
3521         domain = isl_basic_set_reset_dim(domain, dim);
3522
3523         return domain;
3524 }
3525
3526 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
3527 {
3528         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
3529 }
3530
3531 struct isl_set *isl_map_range(struct isl_map *map)
3532 {
3533         int i;
3534         struct isl_set *set;
3535
3536         if (!map)
3537                 goto error;
3538         if (isl_map_dim(map, isl_dim_in) == 0)
3539                 return (isl_set *)map;
3540
3541         map = isl_map_cow(map);
3542         if (!map)
3543                 goto error;
3544
3545         set = (struct isl_set *) map;
3546         set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
3547         if (!set->dim)
3548                 goto error;
3549         for (i = 0; i < map->n; ++i) {
3550                 set->p[i] = isl_basic_map_range(map->p[i]);
3551                 if (!set->p[i])
3552                         goto error;
3553         }
3554         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3555         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3556         return set;
3557 error:
3558         isl_map_free(map);
3559         return NULL;
3560 }
3561
3562 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3563 {
3564         int i;
3565         struct isl_map *map = NULL;
3566
3567         set = isl_set_cow(set);
3568         if (!set || !dim)
3569                 goto error;
3570         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3571         map = (struct isl_map *)set;
3572         for (i = 0; i < set->n; ++i) {
3573                 map->p[i] = isl_basic_map_from_basic_set(
3574                                 set->p[i], isl_dim_copy(dim));
3575                 if (!map->p[i])
3576                         goto error;
3577         }
3578         isl_dim_free(map->dim);
3579         map->dim = dim;
3580         return map;
3581 error:
3582         isl_dim_free(dim);
3583         isl_set_free(set);
3584         return NULL;
3585 }
3586
3587 struct isl_map *isl_map_from_range(struct isl_set *set)
3588 {
3589         return (struct isl_map *)set;
3590 }
3591
3592 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
3593 {
3594         return isl_map_reverse(isl_map_from_range(set));
3595 }
3596
3597 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
3598         __isl_take isl_set *range)
3599 {
3600         return isl_map_apply_range(isl_map_from_domain(domain),
3601                                    isl_map_from_range(range));
3602 }
3603
3604 struct isl_set *isl_set_from_map(struct isl_map *map)
3605 {
3606         int i;
3607         struct isl_set *set = NULL;
3608
3609         if (!map)
3610                 return NULL;
3611         map = isl_map_cow(map);
3612         if (!map)
3613                 return NULL;
3614         map->dim = isl_dim_as_set_dim(map->dim);
3615         if (!map->dim)
3616                 goto error;
3617         set = (struct isl_set *)map;
3618         for (i = 0; i < map->n; ++i) {
3619                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3620                 if (!set->p[i])
3621                         goto error;
3622         }
3623         return set;
3624 error:
3625         isl_map_free(map);
3626         return NULL;
3627 }
3628
3629 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3630 {
3631         struct isl_map *map;
3632
3633         if (!dim)
3634                 return NULL;
3635         isl_assert(dim->ctx, n >= 0, return NULL);
3636         map = isl_alloc(dim->ctx, struct isl_map,
3637                         sizeof(struct isl_map) +
3638                         (n - 1) * sizeof(struct isl_basic_map *));
3639         if (!map)
3640                 goto error;
3641
3642         map->ctx = dim->ctx;
3643         isl_ctx_ref(map->ctx);
3644         map->ref = 1;
3645         map->size = n;
3646         map->n = 0;
3647         map->dim = dim;
3648         map->flags = flags;
3649         return map;
3650 error:
3651         isl_dim_free(dim);
3652         return NULL;
3653 }
3654
3655 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3656                 unsigned nparam, unsigned in, unsigned out, int n,
3657                 unsigned flags)
3658 {
3659         struct isl_map *map;
3660         struct isl_dim *dims;
3661
3662         dims = isl_dim_alloc(ctx, nparam, in, out);
3663         if (!dims)
3664                 return NULL;
3665
3666         map = isl_map_alloc_dim(dims, n, flags);
3667         return map;
3668 }
3669
3670 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
3671 {
3672         struct isl_basic_map *bmap;
3673         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
3674         bmap = isl_basic_map_set_to_empty(bmap);
3675         return bmap;
3676 }
3677
3678 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3679 {
3680         struct isl_basic_set *bset;
3681         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3682         bset = isl_basic_set_set_to_empty(bset);
3683         return bset;
3684 }
3685
3686 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3687 {
3688         struct isl_basic_map *bmap;
3689         if (!model)
3690                 return NULL;
3691         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3692         bmap = isl_basic_map_set_to_empty(bmap);
3693         return bmap;
3694 }
3695
3696 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3697 {
3698         struct isl_basic_map *bmap;
3699         if (!model)
3700                 return NULL;
3701         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3702         bmap = isl_basic_map_set_to_empty(bmap);
3703         return bmap;
3704 }
3705
3706 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3707 {
3708         struct isl_basic_set *bset;
3709         if (!model)
3710                 return NULL;
3711         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3712         bset = isl_basic_set_set_to_empty(bset);
3713         return bset;
3714 }
3715
3716 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3717 {
3718         struct isl_basic_map *bmap;
3719         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3720         return bmap;
3721 }
3722
3723 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3724 {
3725         struct isl_basic_set *bset;
3726         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3727         return bset;
3728 }
3729
3730 __isl_give isl_basic_map *isl_basic_map_universe_like(
3731                 __isl_keep isl_basic_map *model)
3732 {
3733         if (!model)
3734                 return NULL;
3735         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3736 }
3737
3738 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3739 {
3740         if (!model)
3741                 return NULL;
3742         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3743 }
3744
3745 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3746         __isl_keep isl_set *model)
3747 {
3748         if (!model)
3749                 return NULL;
3750         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3751 }
3752
3753 struct isl_map *isl_map_empty(struct isl_dim *dim)
3754 {
3755         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3756 }
3757
3758 struct isl_map *isl_map_empty_like(struct isl_map *model)
3759 {
3760         if (!model)
3761                 return NULL;
3762         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3763 }
3764
3765 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3766 {
3767         if (!model)
3768                 return NULL;
3769         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3770 }
3771
3772 struct isl_set *isl_set_empty(struct isl_dim *dim)
3773 {
3774         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3775 }
3776
3777 struct isl_set *isl_set_empty_like(struct isl_set *model)
3778 {
3779         if (!model)
3780                 return NULL;
3781         return isl_set_empty(isl_dim_copy(model->dim));
3782 }
3783
3784 struct isl_map *isl_map_universe(struct isl_dim *dim)
3785 {
3786         struct isl_map *map;
3787         if (!dim)
3788                 return NULL;
3789         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3790         map = isl_map_add_basic_map(map, isl_basic_map_universe(dim));
3791         return map;
3792 }
3793
3794 struct isl_set *isl_set_universe(struct isl_dim *dim)
3795 {
3796         struct isl_set *set;
3797         if (!dim)
3798                 return NULL;
3799         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3800         set = isl_set_add_basic_set(set, isl_basic_set_universe(dim));
3801         return set;
3802 }
3803
3804 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3805 {
3806         if (!model)
3807                 return NULL;
3808         return isl_set_universe(isl_dim_copy(model->dim));
3809 }
3810
3811 struct isl_map *isl_map_dup(struct isl_map *map)
3812 {
3813         int i;
3814         struct isl_map *dup;
3815
3816         if (!map)
3817                 return NULL;
3818         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3819         for (i = 0; i < map->n; ++i)
3820                 dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i]));
3821         return dup;
3822 }
3823
3824 __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
3825                                                 __isl_take isl_basic_map *bmap)
3826 {
3827         if (!bmap || !map)
3828                 goto error;
3829         if (isl_basic_map_fast_is_empty(bmap)) {
3830                 isl_basic_map_free(bmap);
3831                 return map;
3832         }
3833         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3834         isl_assert(map->ctx, map->n < map->size, goto error);
3835         map->p[map->n] = bmap;
3836         map->n++;
3837         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3838         return map;
3839 error:
3840         if (map)
3841                 isl_map_free(map);
3842         if (bmap)
3843                 isl_basic_map_free(bmap);
3844         return NULL;
3845 }
3846
3847 void isl_map_free(struct isl_map *map)
3848 {
3849         int i;
3850
3851         if (!map)
3852                 return;
3853
3854         if (--map->ref > 0)
3855                 return;
3856
3857         isl_ctx_deref(map->ctx);
3858         for (i = 0; i < map->n; ++i)
3859                 isl_basic_map_free(map->p[i]);
3860         isl_dim_free(map->dim);
3861         free(map);
3862 }
3863
3864 struct isl_map *isl_map_extend(struct isl_map *base,
3865                 unsigned nparam, unsigned n_in, unsigned n_out)
3866 {
3867         int i;
3868
3869         base = isl_map_cow(base);
3870         if (!base)
3871                 return NULL;
3872
3873         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3874         if (!base->dim)
3875                 goto error;
3876         for (i = 0; i < base->n; ++i) {
3877                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3878                                 isl_dim_copy(base->dim), 0, 0, 0);
3879                 if (!base->p[i])
3880                         goto error;
3881         }
3882         return base;
3883 error:
3884         isl_map_free(base);
3885         return NULL;
3886 }
3887
3888 struct isl_set *isl_set_extend(struct isl_set *base,
3889                 unsigned nparam, unsigned dim)
3890 {
3891         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3892                                                         nparam, 0, dim);
3893 }
3894
3895 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3896         struct isl_basic_map *bmap, unsigned pos, int value)
3897 {
3898         int j;
3899
3900         bmap = isl_basic_map_cow(bmap);
3901         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3902         j = isl_basic_map_alloc_equality(bmap);
3903         if (j < 0)
3904                 goto error;
3905         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3906         isl_int_set_si(bmap->eq[j][pos], -1);
3907         isl_int_set_si(bmap->eq[j][0], value);
3908         bmap = isl_basic_map_simplify(bmap);
3909         return isl_basic_map_finalize(bmap);
3910 error:
3911         isl_basic_map_free(bmap);
3912         return NULL;
3913 }
3914
3915 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3916         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3917 {
3918         int j;
3919
3920         bmap = isl_basic_map_cow(bmap);
3921         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3922         j = isl_basic_map_alloc_equality(bmap);
3923         if (j < 0)
3924                 goto error;
3925         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3926         isl_int_set_si(bmap->eq[j][pos], -1);
3927         isl_int_set(bmap->eq[j][0], value);
3928         bmap = isl_basic_map_simplify(bmap);
3929         return isl_basic_map_finalize(bmap);
3930 error:
3931         isl_basic_map_free(bmap);
3932         return NULL;
3933 }
3934
3935 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3936                 enum isl_dim_type type, unsigned pos, int value)
3937 {
3938         if (!bmap)
3939                 return NULL;
3940         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3941         return isl_basic_map_fix_pos_si(bmap,
3942                 isl_basic_map_offset(bmap, type) + pos, value);
3943 error:
3944         isl_basic_map_free(bmap);
3945         return NULL;
3946 }
3947
3948 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3949                 enum isl_dim_type type, unsigned pos, isl_int value)
3950 {
3951         if (!bmap)
3952                 return NULL;
3953         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3954         return isl_basic_map_fix_pos(bmap,
3955                 isl_basic_map_offset(bmap, type) + pos, value);
3956 error:
3957         isl_basic_map_free(bmap);
3958         return NULL;
3959 }
3960
3961 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3962                 enum isl_dim_type type, unsigned pos, int value)
3963 {
3964         return (struct isl_basic_set *)
3965                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3966                                         type, pos, value);
3967 }
3968
3969 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3970                 enum isl_dim_type type, unsigned pos, isl_int value)
3971 {
3972         return (struct isl_basic_set *)
3973                 isl_basic_map_fix((struct isl_basic_map *)bset,
3974                                         type, pos, value);
3975 }
3976
3977 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3978                 unsigned input, int value)
3979 {
3980         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3981 }
3982
3983 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3984                 unsigned dim, int value)
3985 {
3986         return (struct isl_basic_set *)
3987                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3988                                         isl_dim_set, dim, value);
3989 }
3990
3991 struct isl_map *isl_map_fix_si(struct isl_map *map,
3992                 enum isl_dim_type type, unsigned pos, int value)
3993 {
3994         int i;
3995
3996         map = isl_map_cow(map);
3997         if (!map)
3998                 return NULL;
3999
4000         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
4001         for (i = 0; i < map->n; ++i) {
4002                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
4003                 if (!map->p[i])
4004                         goto error;
4005         }
4006         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4007         return map;
4008 error:
4009         isl_map_free(map);
4010         return NULL;
4011 }
4012
4013 __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
4014                 enum isl_dim_type type, unsigned pos, int value)
4015 {
4016         return (struct isl_set *)
4017                 isl_map_fix_si((struct isl_map *)set, type, pos, value);
4018 }
4019
4020 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
4021                 enum isl_dim_type type, unsigned pos, isl_int value)
4022 {
4023         int i;
4024
4025         map = isl_map_cow(map);
4026         if (!map)
4027                 return NULL;
4028
4029         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
4030         for (i = 0; i < map->n; ++i) {
4031                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
4032                 if (!map->p[i])
4033                         goto error;
4034         }
4035         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4036         return map;
4037 error:
4038         isl_map_free(map);
4039         return NULL;
4040 }
4041
4042 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
4043                 enum isl_dim_type type, unsigned pos, isl_int value)
4044 {
4045         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
4046 }
4047
4048 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
4049                 unsigned input, int value)
4050 {
4051         return isl_map_fix_si(map, isl_dim_in, input, value);
4052 }
4053
4054 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
4055 {
4056         return (struct isl_set *)
4057                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
4058 }
4059
4060 __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
4061                 __isl_take isl_basic_map *bmap,
4062                 enum isl_dim_type type, unsigned pos, int value)
4063 {
4064         int j;
4065
4066         if (!bmap)
4067                 return NULL;
4068         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
4069         pos += isl_basic_map_offset(bmap, type);
4070         bmap = isl_basic_map_cow(bmap);
4071         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
4072         j = isl_basic_map_alloc_inequality(bmap);
4073         if (j < 0)
4074                 goto error;
4075         isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
4076         isl_int_set_si(bmap->ineq[j][pos], 1);
4077         isl_int_set_si(bmap->ineq[j][0], -value);
4078         bmap = isl_basic_map_simplify(bmap);
4079         return isl_basic_map_finalize(bmap);
4080 error:
4081         isl_basic_map_free(bmap);
4082         return NULL;
4083 }
4084
4085 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
4086         unsigned dim, isl_int value)
4087 {
4088         int j;
4089
4090         bset = isl_basic_set_cow(bset);
4091         bset = isl_basic_set_extend_constraints(bset, 0, 1);
4092         j = isl_basic_set_alloc_inequality(bset);
4093         if (j < 0)
4094                 goto error;
4095         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
4096         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
4097         isl_int_neg(bset->ineq[j][0], value);
4098         bset = isl_basic_set_simplify(bset);
4099         return isl_basic_set_finalize(bset);
4100 error:
4101         isl_basic_set_free(bset);
4102         return NULL;
4103 }
4104
4105 __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
4106                 enum isl_dim_type type, unsigned pos, int value)
4107 {
4108         int i;
4109
4110         map = isl_map_cow(map);
4111         if (!map)
4112                 return NULL;
4113
4114         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
4115         for (i = 0; i < map->n; ++i) {
4116                 map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
4117                                                          type, pos, value);
4118                 if (!map->p[i])
4119                         goto error;
4120         }
4121         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4122         return map;
4123 error:
4124         isl_map_free(map);
4125         return NULL;
4126 }
4127
4128 __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
4129                 enum isl_dim_type type, unsigned pos, int value)
4130 {
4131         return (struct isl_set *)
4132                 isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
4133 }
4134
4135 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
4136                                         isl_int value)
4137 {
4138         int i;
4139
4140         set = isl_set_cow(set);
4141         if (!set)
4142                 return NULL;
4143
4144         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
4145         for (i = 0; i < set->n; ++i) {
4146                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
4147                 if (!set->p[i])
4148                         goto error;
4149         }
4150         return set;
4151 error:
4152         isl_set_free(set);
4153         return NULL;
4154 }
4155
4156 struct isl_map *isl_map_reverse(struct isl_map *map)
4157 {
4158         int i;
4159
4160         map = isl_map_cow(map);
4161         if (!map)
4162                 return NULL;
4163
4164         map->dim = isl_dim_reverse(map->dim);
4165         if (!map->dim)
4166                 goto error;
4167         for (i = 0; i < map->n; ++i) {
4168                 map->p[i] = isl_basic_map_reverse(map->p[i]);
4169                 if (!map->p[i])
4170                         goto error;
4171         }
4172         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4173         return map;
4174 error:
4175         isl_map_free(map);
4176         return NULL;
4177 }
4178
4179 static struct isl_map *isl_basic_map_partial_lexopt(
4180                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4181                 struct isl_set **empty, int max)
4182 {
4183         if (!bmap)
4184                 goto error;
4185         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
4186                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
4187         else
4188                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
4189 error:
4190         isl_basic_map_free(bmap);
4191         isl_basic_set_free(dom);
4192         if (empty)
4193                 *empty = NULL;
4194         return NULL;
4195 }
4196
4197 struct isl_map *isl_basic_map_partial_lexmax(
4198                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4199                 struct isl_set **empty)
4200 {
4201         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
4202 }
4203
4204 struct isl_map *isl_basic_map_partial_lexmin(
4205                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4206                 struct isl_set **empty)
4207 {
4208         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
4209 }
4210
4211 struct isl_set *isl_basic_set_partial_lexmin(
4212                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4213                 struct isl_set **empty)
4214 {
4215         return (struct isl_set *)
4216                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
4217                         dom, empty);
4218 }
4219
4220 struct isl_set *isl_basic_set_partial_lexmax(
4221                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4222                 struct isl_set **empty)
4223 {
4224         return (struct isl_set *)
4225                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
4226                         dom, empty);
4227 }
4228
4229 /* Given a basic map "bmap", compute the lexicograhically minimal
4230  * (or maximal) image element for each domain element in dom.
4231  * Set *empty to those elements in dom that do not have an image element.
4232  *
4233  * We first make sure the basic sets in dom are disjoint and then
4234  * simply collect the results over each of the basic sets separately.
4235  * We could probably improve the efficiency a bit by moving the union
4236  * domain down into the parametric integer programming.
4237  */
4238 static __isl_give isl_map *basic_map_partial_lexopt(
4239                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
4240                 __isl_give isl_set **empty, int max)
4241 {
4242         int i;
4243         struct isl_map *res;
4244
4245         dom = isl_set_make_disjoint(dom);
4246         if (!dom)
4247                 goto error;
4248
4249         if (isl_set_fast_is_empty(dom)) {
4250                 res = isl_map_empty_like_basic_map(bmap);
4251                 *empty = isl_set_empty_like(dom);
4252                 isl_set_free(dom);
4253                 isl_basic_map_free(bmap);
4254                 return res;
4255         }
4256
4257         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4258                         isl_basic_set_copy(dom->p[0]), empty, max);
4259
4260         for (i = 1; i < dom->n; ++i) {
4261                 struct isl_map *res_i;
4262                 struct isl_set *empty_i;
4263
4264                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4265                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
4266
4267                 res = isl_map_union_disjoint(res, res_i);
4268                 *empty = isl_set_union_disjoint(*empty, empty_i);
4269         }
4270
4271         isl_set_free(dom);
4272         isl_basic_map_free(bmap);
4273         return res;
4274 error:
4275         *empty = NULL;
4276         isl_set_free(dom);
4277         isl_basic_map_free(bmap);
4278         return NULL;
4279 }
4280
4281 /* Given a map "map", compute the lexicograhically minimal
4282  * (or maximal) image element for each domain element in dom.
4283  * Set *empty to those elements in dom that do not have an image element.
4284  *
4285  * We first compute the lexicographically minimal or maximal element
4286  * in the first basic map.  This results in a partial solution "res"
4287  * and a subset "todo" of dom that still need to be handled.
4288  * We then consider each of the remaining maps in "map" and successively
4289  * improve both "res" and "todo".
4290  *
4291  * Let res^k and todo^k be the results after k steps and let i = k + 1.
4292  * Assume we are computing the lexicographical maximum.
4293  * We first intersect basic map i with a relation that maps elements
4294  * to elements that are lexicographically larger than the image elements
4295  * in res^k and the compute the maximum image element of this intersection.
4296  * The result ("better") corresponds to those image elements in basic map i
4297  * that are better than what we had before.  The remainder ("keep") are the
4298  * domain elements for which the image element in res_k was better.
4299  * We also compute the lexicographical maximum of basic map i in todo^k.
4300  * res^i is the result of the operation + better + those elements in
4301  *              res^k that we should keep
4302  * todo^i is the remainder of the maximum operation on todo^k.
4303  */
4304 static __isl_give isl_map *isl_map_partial_lexopt(
4305                 __isl_take isl_map *map, __isl_take isl_set *dom,
4306                 __isl_give isl_set **empty, int max)
4307 {
4308         int i;
4309         struct isl_map *res;
4310         struct isl_set *todo;
4311
4312         if (!map || !dom)
4313                 goto error;
4314
4315         if (isl_map_fast_is_empty(map)) {
4316                 if (empty)
4317                         *empty = dom;
4318                 else
4319                         isl_set_free(dom);
4320                 return map;
4321         }
4322
4323         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
4324                                         isl_set_copy(dom), &todo, max);
4325
4326         for (i = 1; i < map->n; ++i) {
4327                 struct isl_map *lt;
4328                 struct isl_map *better;
4329                 struct isl_set *keep;
4330                 struct isl_map *res_i;
4331                 struct isl_set *todo_i;
4332                 struct isl_dim *dim = isl_map_get_dim(res);
4333
4334                 dim = isl_dim_range(dim);
4335                 if (max)
4336                         lt = isl_map_lex_lt(dim);
4337                 else
4338                         lt = isl_map_lex_gt(dim);
4339                 lt = isl_map_apply_range(isl_map_copy(res), lt);
4340                 lt = isl_map_intersect(lt,
4341                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
4342                 better = isl_map_partial_lexopt(lt,
4343                         isl_map_domain(isl_map_copy(res)),
4344                         &keep, max);
4345
4346                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
4347                                                 todo, &todo_i, max);
4348
4349                 res = isl_map_intersect_domain(res, keep);
4350                 res = isl_map_union_disjoint(res, res_i);
4351                 res = isl_map_union_disjoint(res, better);
4352                 todo = todo_i;
4353         }
4354
4355         isl_set_free(dom);
4356         isl_map_free(map);
4357
4358         if (empty)
4359                 *empty = todo;
4360         else
4361                 isl_set_free(todo);
4362
4363         return res;
4364 error:
4365         if (empty)
4366                 *empty = NULL;
4367         isl_set_free(dom);
4368         isl_map_free(map);
4369         return NULL;
4370 }
4371
4372 __isl_give isl_map *isl_map_partial_lexmax(
4373                 __isl_take isl_map *map, __isl_take isl_set *dom,
4374                 __isl_give isl_set **empty)
4375 {
4376         return isl_map_partial_lexopt(map, dom, empty, 1);
4377 }
4378
4379 __isl_give isl_map *isl_map_partial_lexmin(
4380                 __isl_take isl_map *map, __isl_take isl_set *dom,
4381                 __isl_give isl_set **empty)
4382 {
4383         return isl_map_partial_lexopt(map, dom, empty, 0);
4384 }
4385
4386 __isl_give isl_set *isl_set_partial_lexmin(
4387                 __isl_take isl_set *set, __isl_take isl_set *dom,
4388                 __isl_give isl_set **empty)
4389 {
4390         return (struct isl_set *)
4391                 isl_map_partial_lexmin((struct isl_map *)set,
4392                         dom, empty);
4393 }
4394
4395 __isl_give isl_set *isl_set_partial_lexmax(
4396                 __isl_take isl_set *set, __isl_take isl_set *dom,
4397                 __isl_give isl_set **empty)
4398 {
4399         return (struct isl_set *)
4400                 isl_map_partial_lexmax((struct isl_map *)set,
4401                         dom, empty);
4402 }
4403
4404 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
4405 {
4406         struct isl_basic_set *dom = NULL;
4407         struct isl_dim *dom_dim;
4408
4409         if (!bmap)
4410                 goto error;
4411         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
4412         dom = isl_basic_set_universe(dom_dim);
4413         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
4414 error:
4415         isl_basic_map_free(bmap);
4416         return NULL;
4417 }
4418
4419 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
4420 {
4421         return isl_basic_map_lexopt(bmap, 0);
4422 }
4423
4424 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
4425 {
4426         return isl_basic_map_lexopt(bmap, 1);
4427 }
4428
4429 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
4430 {
4431         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
4432 }
4433
4434 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
4435 {
4436         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
4437 }
4438
4439 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
4440 {
4441         struct isl_set *dom = NULL;
4442         struct isl_dim *dom_dim;
4443
4444         if (!map)
4445                 goto error;
4446         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
4447         dom = isl_set_universe(dom_dim);
4448         return isl_map_partial_lexopt(map, dom, NULL, max);
4449 error:
4450         isl_map_free(map);
4451         return NULL;
4452 }
4453
4454 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
4455 {
4456         return isl_map_lexopt(map, 0);
4457 }
4458
4459 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
4460 {
4461         return isl_map_lexopt(map, 1);
4462 }
4463
4464 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
4465 {
4466         return (isl_set *)isl_map_lexmin((isl_map *)set);
4467 }
4468
4469 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
4470 {
4471         return (isl_set *)isl_map_lexmax((isl_map *)set);
4472 }
4473
4474 /* Apply a preimage specified by "mat" on the parameters of "bset".
4475  * bset is assumed to have only parameters and divs.
4476  */
4477 static struct isl_basic_set *basic_set_parameter_preimage(
4478         struct isl_basic_set *bset, struct isl_mat *mat)
4479 {
4480         unsigned nparam;
4481
4482         if (!bset || !mat)
4483                 goto error;
4484
4485         bset->dim = isl_dim_cow(bset->dim);
4486         if (!bset->dim)
4487                 goto error;
4488
4489         nparam = isl_basic_set_dim(bset, isl_dim_param);
4490
4491         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
4492
4493         bset->dim->nparam = 0;
4494         bset->dim->n_out = nparam;
4495         bset = isl_basic_set_preimage(bset, mat);
4496         if (bset) {
4497                 bset->dim->nparam = bset->dim->n_out;
4498                 bset->dim->n_out = 0;
4499         }
4500         return bset;
4501 error:
4502         isl_mat_free(mat);
4503         isl_basic_set_free(bset);
4504         return NULL;
4505 }
4506
4507 /* Apply a preimage specified by "mat" on the parameters of "set".
4508  * set is assumed to have only parameters and divs.
4509  */
4510 static struct isl_set *set_parameter_preimage(
4511         struct isl_set *set, struct isl_mat *mat)
4512 {
4513         struct isl_dim *dim = NULL;
4514         unsigned nparam;
4515
4516         if (!set || !mat)
4517                 goto error;
4518
4519         dim = isl_dim_copy(set->dim);
4520         dim = isl_dim_cow(dim);
4521         if (!dim)
4522                 goto error;
4523
4524         nparam = isl_set_dim(set, isl_dim_param);
4525
4526         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
4527
4528         dim->nparam = 0;
4529         dim->n_out = nparam;
4530         isl_set_reset_dim(set, dim);
4531         set = isl_set_preimage(set, mat);
4532         if (!set)
4533                 goto error2;
4534         dim = isl_dim_copy(set->dim);
4535         dim = isl_dim_cow(dim);
4536         if (!dim)
4537                 goto error2;
4538         dim->nparam = dim->n_out;
4539         dim->n_out = 0;
4540         isl_set_reset_dim(set, dim);
4541         return set;
4542 error:
4543         isl_dim_free(dim);
4544         isl_mat_free(mat);
4545 error2:
4546         isl_set_free(set);
4547         return NULL;
4548 }
4549
4550 /* Intersect the basic set "bset" with the affine space specified by the
4551  * equalities in "eq".
4552  */
4553 static struct isl_basic_set *basic_set_append_equalities(
4554         struct isl_basic_set *bset, struct isl_mat *eq)
4555 {
4556         int i, k;
4557         unsigned len;
4558
4559         if (!bset || !eq)
4560                 goto error;
4561
4562         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
4563                                         eq->n_row, 0);
4564         if (!bset)
4565                 goto error;
4566
4567         len = 1 + isl_dim_total(bset->dim) + bset->extra;
4568         for (i = 0; i < eq->n_row; ++i) {
4569                 k = isl_basic_set_alloc_equality(bset);
4570                 if (k < 0)
4571                         goto error;
4572                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
4573                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
4574         }
4575         isl_mat_free(eq);
4576
4577         bset = isl_basic_set_gauss(bset, NULL);
4578         bset = isl_basic_set_finalize(bset);
4579
4580         return bset;
4581 error:
4582         isl_mat_free(eq);
4583         isl_basic_set_free(bset);
4584         return NULL;
4585 }
4586
4587 /* Intersect the set "set" with the affine space specified by the
4588  * equalities in "eq".
4589  */
4590 static struct isl_set *set_append_equalities(struct isl_set *set,
4591         struct isl_mat *eq)
4592 {
4593         int i;
4594
4595         if (!set || !eq)
4596                 goto error;
4597
4598         for (i = 0; i < set->n; ++i) {
4599                 set->p[i] = basic_set_append_equalities(set->p[i],
4600                                         isl_mat_copy(eq));
4601                 if (!set->p[i])
4602                         goto error;
4603         }
4604         isl_mat_free(eq);
4605         return set;
4606 error:
4607         isl_mat_free(eq);
4608         isl_set_free(set);
4609         return NULL;
4610 }
4611
4612 /* Project the given basic set onto its parameter domain, possibly introducing
4613  * new, explicit, existential variables in the constraints.
4614  * The input has parameters and (possibly implicit) existential variables.
4615  * The output has the same parameters, but only
4616  * explicit existentially quantified variables.
4617  *
4618  * The actual projection is performed by pip, but pip doesn't seem
4619  * to like equalities very much, so we first remove the equalities
4620  * among the parameters by performing a variable compression on
4621  * the parameters.  Afterward, an inverse transformation is performed
4622  * and the equalities among the parameters are inserted back in.
4623  */
4624 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
4625 {
4626         int i, j;
4627         struct isl_mat *eq;
4628         struct isl_mat *T, *T2;
4629         struct isl_set *set;
4630         unsigned nparam, n_div;
4631
4632         bset = isl_basic_set_cow(bset);
4633         if (!bset)
4634                 return NULL;
4635
4636         if (bset->n_eq == 0)
4637                 return isl_basic_set_lexmin(bset);
4638
4639         isl_basic_set_gauss(bset, NULL);
4640
4641         nparam = isl_basic_set_dim(bset, isl_dim_param);
4642         n_div = isl_basic_set_dim(bset, isl_dim_div);
4643
4644         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
4645                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
4646                         ++i;
4647         }
4648         if (i == bset->n_eq)
4649                 return isl_basic_set_lexmin(bset);
4650
4651         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
4652                 0, 1 + nparam);
4653         eq = isl_mat_cow(eq);
4654         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
4655         if (T && T->n_col == 0) {
4656                 isl_mat_free(T);
4657                 isl_mat_free(T2);
4658                 isl_mat_free(eq);
4659                 bset = isl_basic_set_set_to_empty(bset);
4660                 return isl_set_from_basic_set(bset);
4661         }
4662         bset = basic_set_parameter_preimage(bset, T);
4663
4664         set = isl_basic_set_lexmin(bset);
4665         set = set_parameter_preimage(set, T2);
4666         set = set_append_equalities(set, eq);
4667         return set;
4668 }
4669
4670 /* Compute an explicit representation for all the existentially
4671  * quantified variables.
4672  * The input and output dimensions are first turned into parameters.
4673  * compute_divs then returns a map with the same parameters and
4674  * no input or output dimensions and the dimension specification
4675  * is reset to that of the input.
4676  */
4677 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
4678 {
4679         struct isl_basic_set *bset;
4680         struct isl_set *set;
4681         struct isl_map *map;
4682         struct isl_dim *dim, *orig_dim = NULL;
4683         unsigned         nparam;
4684         unsigned         n_in;
4685         unsigned         n_out;
4686
4687         bmap = isl_basic_map_cow(bmap);
4688         if (!bmap)
4689                 return NULL;
4690
4691         nparam = isl_basic_map_dim(bmap, isl_dim_param);
4692         n_in = isl_basic_map_dim(bmap, isl_dim_in);
4693         n_out = isl_basic_map_dim(bmap, isl_dim_out);
4694         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
4695         if (!dim)
4696                 goto error;
4697
4698         orig_dim = bmap->dim;
4699         bmap->dim = dim;
4700         bset = (struct isl_basic_set *)bmap;
4701
4702         set = parameter_compute_divs(bset);
4703         map = (struct isl_map *)set;
4704         map = isl_map_reset_dim(map, orig_dim);
4705
4706         return map;
4707 error:
4708         isl_basic_map_free(bmap);
4709         return NULL;
4710 }
4711
4712 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
4713 {
4714         int i;
4715         unsigned off;
4716
4717         if (!bmap)
4718                 return -1;
4719
4720         off = isl_dim_total(bmap->dim);
4721         for (i = 0; i < bmap->n_div; ++i) {
4722                 if (isl_int_is_zero(bmap->div[i][0]))
4723                         return 0;
4724                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
4725                                 return -1);
4726         }
4727         return 1;
4728 }
4729
4730 static int map_divs_known(__isl_keep isl_map *map)
4731 {
4732         int i;
4733
4734         if (!map)
4735                 return -1;
4736
4737         for (i = 0; i < map->n; ++i) {
4738                 int known = basic_map_divs_known(map->p[i]);
4739                 if (known <= 0)
4740                         return known;
4741         }
4742
4743         return 1;
4744 }
4745
4746 /* If bmap contains any unknown divs, then compute explicit
4747  * expressions for them.  However, this computation may be
4748  * quite expensive, so first try to remove divs that aren't
4749  * strictly needed.
4750  */
4751 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
4752 {
4753         int i;
4754         int known;
4755         struct isl_map *map;
4756
4757         known = basic_map_divs_known(bmap);
4758         if (known < 0)
4759                 goto error;
4760         if (known)
4761                 return isl_map_from_basic_map(bmap);
4762
4763         bmap = isl_basic_map_drop_redundant_divs(bmap);
4764
4765         known = basic_map_divs_known(bmap);
4766         if (known < 0)
4767                 goto error;
4768         if (known)
4769                 return isl_map_from_basic_map(bmap);
4770
4771         map = compute_divs(bmap);
4772         return map;
4773 error:
4774         isl_basic_map_free(bmap);
4775         return NULL;
4776 }
4777
4778 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4779 {
4780         int i;
4781         int known;
4782         struct isl_map *res;
4783
4784         if (!map)
4785                 return NULL;
4786         if (map->n == 0)
4787                 return map;
4788
4789         known = map_divs_known(map);
4790         if (known < 0) {
4791                 isl_map_free(map);
4792                 return NULL;
4793         }
4794         if (known)
4795                 return map;
4796
4797         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4798         for (i = 1 ; i < map->n; ++i) {
4799                 struct isl_map *r2;
4800                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4801                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4802                         res = isl_map_union_disjoint(res, r2);
4803                 else
4804                         res = isl_map_union(res, r2);
4805         }
4806         isl_map_free(map);
4807
4808         return res;
4809 }
4810
4811 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4812 {
4813         return (struct isl_set *)
4814                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4815 }
4816
4817 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4818 {
4819         return (struct isl_set *)
4820                 isl_map_compute_divs((struct isl_map *)set);
4821 }
4822
4823 struct isl_set *isl_map_domain(struct isl_map *map)
4824 {
4825         int i;
4826         struct isl_set *set;
4827
4828         if (!map)
4829                 goto error;
4830
4831         map = isl_map_cow(map);
4832         if (!map)
4833                 return NULL;
4834
4835         set = (struct isl_set *)map;
4836         set->dim = isl_dim_domain(set->dim);
4837         if (!set->dim)
4838                 goto error;
4839         for (i = 0; i < map->n; ++i) {
4840                 set->p[i] = isl_basic_map_domain(map->p[i]);
4841                 if (!set->p[i])
4842                         goto error;
4843         }
4844         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4845         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4846         return set;
4847 error:
4848         isl_map_free(map);
4849         return NULL;
4850 }
4851
4852 struct isl_map *isl_map_union_disjoint(
4853                         struct isl_map *map1, struct isl_map *map2)
4854 {
4855         int i;
4856         unsigned flags = 0;
4857         struct isl_map *map = NULL;
4858
4859         if (!map1 || !map2)
4860                 goto error;
4861
4862         if (map1->n == 0) {
4863                 isl_map_free(map1);
4864                 return map2;
4865         }
4866         if (map2->n == 0) {
4867                 isl_map_free(map2);
4868                 return map1;
4869         }
4870
4871         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4872
4873         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4874             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4875                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4876
4877         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4878                                 map1->n + map2->n, flags);
4879         if (!map)
4880                 goto error;
4881         for (i = 0; i < map1->n; ++i) {
4882                 map = isl_map_add_basic_map(map,
4883                                   isl_basic_map_copy(map1->p[i]));
4884                 if (!map)
4885                         goto error;
4886         }
4887         for (i = 0; i < map2->n; ++i) {
4888                 map = isl_map_add_basic_map(map,
4889                                   isl_basic_map_copy(map2->p[i]));
4890                 if (!map)
4891                         goto error;
4892         }
4893         isl_map_free(map1);
4894         isl_map_free(map2);
4895         return map;
4896 error:
4897         isl_map_free(map);
4898         isl_map_free(map1);
4899         isl_map_free(map2);
4900         return NULL;
4901 }
4902
4903 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4904 {
4905         map1 = isl_map_union_disjoint(map1, map2);
4906         if (!map1)
4907                 return NULL;
4908         if (map1->n > 1)
4909                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4910         return map1;
4911 }
4912
4913 struct isl_set *isl_set_union_disjoint(
4914                         struct isl_set *set1, struct isl_set *set2)
4915 {
4916         return (struct isl_set *)
4917                 isl_map_union_disjoint(
4918                         (struct isl_map *)set1, (struct isl_map *)set2);
4919 }
4920
4921 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4922 {
4923         return (struct isl_set *)
4924                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4925 }
4926
4927 struct isl_map *isl_map_intersect_range(
4928                 struct isl_map *map, struct isl_set *set)
4929 {
4930         unsigned flags = 0;
4931         struct isl_map *result;
4932         int i, j;
4933
4934         if (!map || !set)
4935                 goto error;
4936
4937         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4938             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4939                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4940
4941         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4942                                         map->n * set->n, flags);
4943         if (!result)
4944                 goto error;
4945         for (i = 0; i < map->n; ++i)
4946                 for (j = 0; j < set->n; ++j) {
4947                         result = isl_map_add_basic_map(result,
4948                             isl_basic_map_intersect_range(
4949                                 isl_basic_map_copy(map->p[i]),
4950                                 isl_basic_set_copy(set->p[j])));
4951                         if (!result)
4952                                 goto error;
4953                 }
4954         isl_map_free(map);
4955         isl_set_free(set);
4956         return result;
4957 error:
4958         isl_map_free(map);
4959         isl_set_free(set);
4960         return NULL;
4961 }
4962
4963 struct isl_map *isl_map_intersect_domain(
4964                 struct isl_map *map, struct isl_set *set)
4965 {
4966         return isl_map_reverse(
4967                 isl_map_intersect_range(isl_map_reverse(map), set));
4968 }
4969
4970 struct isl_map *isl_map_apply_domain(
4971                 struct isl_map *map1, struct isl_map *map2)
4972 {
4973         if (!map1 || !map2)
4974                 goto error;
4975         map1 = isl_map_reverse(map1);
4976         map1 = isl_map_apply_range(map1, map2);
4977         return isl_map_reverse(map1);
4978 error:
4979         isl_map_free(map1);
4980         isl_map_free(map2);
4981         return NULL;
4982 }
4983
4984 struct isl_map *isl_map_apply_range(
4985                 struct isl_map *map1, struct isl_map *map2)
4986 {
4987         struct isl_dim *dim_result;
4988         struct isl_map *result;
4989         int i, j;
4990
4991         if (!map1 || !map2)
4992                 goto error;
4993
4994         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4995                                   isl_dim_copy(map2->dim));
4996
4997         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4998         if (!result)
4999                 goto error;
5000         for (i = 0; i < map1->n; ++i)
5001                 for (j = 0; j < map2->n; ++j) {
5002                         result = isl_map_add_basic_map(result,
5003                             isl_basic_map_apply_range(
5004                                 isl_basic_map_copy(map1->p[i]),
5005                                 isl_basic_map_copy(map2->p[j])));
5006                         if (!result)
5007                                 goto error;
5008                 }
5009         isl_map_free(map1);
5010         isl_map_free(map2);
5011         if (result && result->n <= 1)
5012                 ISL_F_SET(result, ISL_MAP_DISJOINT);
5013         return result;
5014 error:
5015         isl_map_free(map1);
5016         isl_map_free(map2);
5017         return NULL;
5018 }
5019
5020 /*
5021  * returns range - domain
5022  */
5023 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
5024 {
5025         isl_dim *dims, *target_dim;
5026         struct isl_basic_set *bset;
5027         unsigned dim;
5028         unsigned nparam;
5029         int i;
5030
5031         if (!bmap)
5032                 goto error;
5033         isl_assert(bmap->ctx, isl_dim_tuple_match(bmap->dim, isl_dim_in,
5034                                                   bmap->dim, isl_dim_out),
5035                    goto error);
5036         target_dim = isl_dim_domain(isl_basic_map_get_dim(bmap));
5037         dim = isl_basic_map_n_in(bmap);
5038         nparam = isl_basic_map_n_param(bmap);
5039         bset = isl_basic_set_from_basic_map(bmap);
5040         bset = isl_basic_set_cow(bset);
5041         dims = isl_basic_set_get_dim(bset);
5042         dims = isl_dim_add(dims, isl_dim_set, dim);
5043         bset = isl_basic_set_extend_dim(bset, dims, 0, dim, 0);
5044         bset = isl_basic_set_swap_vars(bset, 2*dim);
5045         for (i = 0; i < dim; ++i) {
5046                 int j = isl_basic_map_alloc_equality(
5047                                             (struct isl_basic_map *)bset);
5048                 if (j < 0)
5049                         goto error;
5050                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
5051                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
5052                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
5053                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
5054         }
5055         bset = isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
5056         bset = isl_basic_set_reset_dim(bset, target_dim);
5057         return bset;
5058 error:
5059         isl_basic_map_free(bmap);
5060         return NULL;
5061 }
5062
5063 /*
5064  * returns range - domain
5065  */
5066 struct isl_set *isl_map_deltas(struct isl_map *map)
5067 {
5068         int i;
5069         isl_dim *dim;
5070         struct isl_set *result;
5071
5072         if (!map)
5073                 return NULL;
5074
5075         isl_assert(map->ctx, isl_dim_tuple_match(map->dim, isl_dim_in,
5076                                                  map->dim, isl_dim_out),
5077                    goto error);
5078         dim = isl_map_get_dim(map);
5079         dim = isl_dim_domain(dim);
5080         result = isl_set_alloc_dim(dim, map->n, map->flags);
5081         if (!result)
5082                 goto error;
5083         for (i = 0; i < map->n; ++i)
5084                 result = isl_set_add_basic_set(result,
5085                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
5086         isl_map_free(map);
5087         return result;
5088 error:
5089         isl_map_free(map);
5090         return NULL;
5091 }
5092
5093 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
5094 {
5095         struct isl_basic_map *bmap;
5096         unsigned nparam;
5097         unsigned dim;
5098         int i;
5099
5100         if (!dims)
5101                 return NULL;
5102
5103         nparam = dims->nparam;
5104         dim = dims->n_out;
5105         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
5106         if (!bmap)
5107                 goto error;
5108
5109         for (i = 0; i < dim; ++i) {
5110                 int j = isl_basic_map_alloc_equality(bmap);
5111                 if (j < 0)
5112                         goto error;
5113                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
5114                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
5115                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
5116         }
5117         return isl_basic_map_finalize(bmap);
5118 error:
5119         isl_basic_map_free(bmap);
5120         return NULL;
5121 }
5122
5123 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
5124 {
5125         struct isl_dim *dim = isl_dim_map(set_dim);
5126         if (!dim)
5127                 return NULL;
5128         return basic_map_identity(dim);
5129 }
5130
5131 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
5132 {
5133         if (!model || !model->dim)
5134                 return NULL;
5135         isl_assert(model->ctx,
5136                         model->dim->n_in == model->dim->n_out, return NULL);
5137         return basic_map_identity(isl_dim_copy(model->dim));
5138 }
5139
5140 static struct isl_map *map_identity(struct isl_dim *dim)
5141 {
5142         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
5143         return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim)));
5144 }
5145
5146 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
5147 {
5148         struct isl_dim *dim = isl_dim_map(set_dim);
5149         if (!dim)
5150                 return NULL;
5151         return map_identity(dim);
5152 }
5153
5154 struct isl_map *isl_map_identity_like(struct isl_map *model)
5155 {
5156         if (!model || !model->dim)
5157                 return NULL;
5158         isl_assert(model->ctx,
5159                         model->dim->n_in == model->dim->n_out, return NULL);
5160         return map_identity(isl_dim_copy(model->dim));
5161 }
5162
5163 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
5164 {
5165         if (!model || !model->dim)
5166                 return NULL;
5167         isl_assert(model->ctx,
5168                         model->dim->n_in == model->dim->n_out, return NULL);
5169         return map_identity(isl_dim_copy(model->dim));
5170 }
5171
5172 /* Construct a basic set with all set dimensions having only non-negative
5173  * values.
5174  */
5175 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
5176 {
5177         int i;
5178         unsigned nparam;
5179         unsigned dim;
5180         struct isl_basic_set *bset;
5181
5182         if (!dims)
5183                 return NULL;
5184         nparam = dims->nparam;
5185         dim = dims->n_out;
5186         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
5187         if (!bset)
5188                 return NULL;
5189         for (i = 0; i < dim; ++i) {
5190                 int k = isl_basic_set_alloc_inequality(bset);
5191                 if (k < 0)
5192                         goto error;
5193                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
5194                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
5195         }
5196         return bset;
5197 error:
5198         isl_basic_set_free(bset);
5199         return NULL;
5200 }
5201
5202 __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set,
5203         enum isl_dim_type type, unsigned first, unsigned n)
5204 {
5205         int i;
5206         isl_basic_set *nonneg = NULL;
5207         isl_basic_set *neg = NULL;
5208
5209         if (!set)
5210                 return NULL;
5211         if (n == 0)
5212                 return set;
5213
5214         isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error);
5215
5216         for (i = 0; i < n; ++i) {
5217                 int k;
5218
5219                 neg = NULL;
5220                 nonneg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5221                 k = isl_basic_set_alloc_inequality(nonneg);
5222                 if (k < 0)
5223                         goto error;
5224                 isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg));
5225                 isl_int_set_si(nonneg->ineq[k][pos(set->dim, type) + first + i], 1);
5226
5227                 neg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5228                 k = isl_basic_set_alloc_inequality(neg);
5229                 if (k < 0)
5230                         goto error;
5231                 isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg));
5232                 isl_int_set_si(neg->ineq[k][0], -1);
5233                 isl_int_set_si(neg->ineq[k][pos(set->dim, type) + first + i], -1);
5234
5235                 set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg));
5236         }
5237
5238         return set;
5239 error:
5240         isl_basic_set_free(nonneg);
5241         isl_basic_set_free(neg);
5242         isl_set_free(set);
5243         return NULL;
5244 }
5245
5246 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
5247 {
5248         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
5249 }
5250
5251 int isl_basic_map_is_subset(
5252                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5253 {
5254         int is_subset;
5255         struct isl_map *map1;
5256         struct isl_map *map2;
5257
5258         if (!bmap1 || !bmap2)
5259                 return -1;
5260
5261         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
5262         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
5263
5264         is_subset = isl_map_is_subset(map1, map2);
5265
5266         isl_map_free(map1);
5267         isl_map_free(map2);
5268
5269         return is_subset;
5270 }
5271
5272 int isl_basic_map_is_equal(
5273                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5274 {
5275         int is_subset;
5276
5277         if (!bmap1 || !bmap2)
5278                 return -1;
5279         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5280         if (is_subset != 1)
5281                 return is_subset;
5282         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5283         return is_subset;
5284 }
5285
5286 int isl_basic_set_is_equal(
5287                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5288 {
5289         return isl_basic_map_is_equal(
5290                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
5291 }
5292
5293 int isl_map_is_empty(struct isl_map *map)
5294 {
5295         int i;
5296         int is_empty;
5297
5298         if (!map)
5299                 return -1;
5300         for (i = 0; i < map->n; ++i) {
5301                 is_empty = isl_basic_map_is_empty(map->p[i]);
5302                 if (is_empty < 0)
5303                         return -1;
5304                 if (!is_empty)
5305                         return 0;
5306         }
5307         return 1;
5308 }
5309
5310 int isl_map_fast_is_empty(struct isl_map *map)
5311 {
5312         return map ? map->n == 0 : -1;
5313 }
5314
5315 int isl_set_fast_is_empty(struct isl_set *set)
5316 {
5317         return set ? set->n == 0 : -1;
5318 }
5319
5320 int isl_set_is_empty(struct isl_set *set)
5321 {
5322         return isl_map_is_empty((struct isl_map *)set);
5323 }
5324
5325 int isl_map_has_equal_dim(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
5326 {
5327         if (!map1 || !map2)
5328                 return -1;
5329
5330         return isl_dim_equal(map1->dim, map2->dim);
5331 }
5332
5333 int isl_set_has_equal_dim(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
5334 {
5335         if (!set1 || !set2)
5336                 return -1;
5337
5338         return isl_dim_equal(set1->dim, set2->dim);
5339 }
5340
5341 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
5342 {
5343         int is_subset;
5344
5345         if (!map1 || !map2)
5346                 return -1;
5347         is_subset = isl_map_is_subset(map1, map2);
5348         if (is_subset != 1)
5349                 return is_subset;
5350         is_subset = isl_map_is_subset(map2, map1);
5351         return is_subset;
5352 }
5353
5354 int isl_basic_map_is_strict_subset(
5355                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5356 {
5357         int is_subset;
5358
5359         if (!bmap1 || !bmap2)
5360                 return -1;
5361         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5362         if (is_subset != 1)
5363                 return is_subset;
5364         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5365         if (is_subset == -1)
5366                 return is_subset;
5367         return !is_subset;
5368 }
5369
5370 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
5371 {
5372         int is_subset;
5373
5374         if (!map1 || !map2)
5375                 return -1;
5376         is_subset = isl_map_is_subset(map1, map2);
5377         if (is_subset != 1)
5378                 return is_subset;
5379         is_subset = isl_map_is_subset(map2, map1);
5380         if (is_subset == -1)
5381                 return is_subset;
5382         return !is_subset;
5383 }
5384
5385 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
5386 {
5387         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
5388 }
5389
5390 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
5391 {
5392         if (!bmap)
5393                 return -1;
5394         return bmap->n_eq == 0 && bmap->n_ineq == 0;
5395 }
5396
5397 int isl_basic_set_is_universe(struct isl_basic_set *bset)
5398 {
5399         if (!bset)
5400                 return -1;
5401         return bset->n_eq == 0 && bset->n_ineq == 0;
5402 }
5403
5404 int isl_map_fast_is_universe(__isl_keep isl_map *map)
5405 {
5406         int i;
5407
5408         if (!map)
5409                 return -1;
5410
5411         for (i = 0; i < map->n; ++i) {
5412                 int r = isl_basic_map_is_universe(map->p[i]);
5413                 if (r < 0 || r)
5414                         return r;
5415         }
5416
5417         return 0;
5418 }
5419
5420 int isl_set_fast_is_universe(__isl_keep isl_set *set)
5421 {
5422         return isl_map_fast_is_universe((isl_map *) set);
5423 }
5424
5425 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
5426 {
5427         struct isl_basic_set *bset = NULL;
5428         struct isl_vec *sample = NULL;
5429         int empty;
5430         unsigned total;
5431
5432         if (!bmap)
5433                 return -1;
5434
5435         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
5436                 return 1;
5437
5438         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
5439                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
5440                 copy = isl_basic_map_remove_redundancies(copy);
5441                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
5442                 isl_basic_map_free(copy);
5443                 return empty;
5444         }
5445
5446         total = 1 + isl_basic_map_total_dim(bmap);
5447         if (bmap->sample && bmap->sample->size == total) {
5448                 int contains = isl_basic_map_contains(bmap, bmap->sample);
5449                 if (contains < 0)
5450                         return -1;
5451                 if (contains)
5452                         return 0;
5453         }
5454         isl_vec_free(bmap->sample);
5455         bmap->sample = NULL;
5456         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
5457         if (!bset)
5458                 return -1;
5459         sample = isl_basic_set_sample_vec(bset);
5460         if (!sample)
5461                 return -1;
5462         empty = sample->size == 0;
5463         isl_vec_free(bmap->sample);
5464         bmap->sample = sample;
5465         if (empty)
5466                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
5467
5468         return empty;
5469 }
5470
5471 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
5472 {
5473         if (!bmap)
5474                 return -1;
5475         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
5476 }
5477
5478 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
5479 {
5480         if (!bset)
5481                 return -1;
5482         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
5483 }
5484
5485 int isl_basic_set_is_empty(struct isl_basic_set *bset)
5486 {
5487         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
5488 }
5489
5490 struct isl_map *isl_basic_map_union(
5491         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5492 {
5493         struct isl_map *map;
5494         if (!bmap1 || !bmap2)
5495                 return NULL;
5496
5497         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
5498
5499         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
5500         if (!map)
5501                 goto error;
5502         map = isl_map_add_basic_map(map, bmap1);
5503         map = isl_map_add_basic_map(map, bmap2);
5504         return map;
5505 error:
5506         isl_basic_map_free(bmap1);
5507         isl_basic_map_free(bmap2);
5508         return NULL;
5509 }
5510
5511 struct isl_set *isl_basic_set_union(
5512                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5513 {
5514         return (struct isl_set *)isl_basic_map_union(
5515                                             (struct isl_basic_map *)bset1,
5516                                             (struct isl_basic_map *)bset2);
5517 }
5518
5519 /* Order divs such that any div only depends on previous divs */
5520 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
5521 {
5522         int i;
5523         unsigned off;
5524
5525         if (!bmap)
5526                 return NULL;
5527
5528         off = isl_dim_total(bmap->dim);
5529
5530         for (i = 0; i < bmap->n_div; ++i) {
5531                 int pos;
5532                 if (isl_int_is_zero(bmap->div[i][0]))
5533                         continue;
5534                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
5535                                                             bmap->n_div-i);
5536                 if (pos == -1)
5537                         continue;
5538                 isl_basic_map_swap_div(bmap, i, i + pos);
5539                 --i;
5540         }
5541         return bmap;
5542 }
5543
5544 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
5545 {
5546         return (struct isl_basic_set *)
5547                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
5548 }
5549
5550 __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
5551 {
5552         int i;
5553
5554         if (!map)
5555                 return 0;
5556
5557         for (i = 0; i < map->n; ++i) {
5558                 map->p[i] = isl_basic_map_order_divs(map->p[i]);
5559                 if (!map->p[i])
5560                         goto error;
5561         }
5562
5563         return map;
5564 error:
5565         isl_map_free(map);
5566         return NULL;
5567 }
5568
5569 /* Look for a div in dst that corresponds to the div "div" in src.
5570  * The divs before "div" in src and dst are assumed to be the same.
5571  *
5572  * Returns -1 if no corresponding div was found and the position
5573  * of the corresponding div in dst otherwise.
5574  */
5575 static int find_div(struct isl_basic_map *dst,
5576                         struct isl_basic_map *src, unsigned div)
5577 {
5578         int i;
5579
5580         unsigned total = isl_dim_total(src->dim);
5581
5582         isl_assert(dst->ctx, div <= dst->n_div, return -1);
5583         for (i = div; i < dst->n_div; ++i)
5584                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
5585                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
5586                                                 dst->n_div - div) == -1)
5587                         return i;
5588         return -1;
5589 }
5590
5591 struct isl_basic_map *isl_basic_map_align_divs(
5592                 struct isl_basic_map *dst, struct isl_basic_map *src)
5593 {
5594         int i;
5595         unsigned total = isl_dim_total(src->dim);
5596
5597         if (!dst || !src)
5598                 goto error;
5599
5600         if (src->n_div == 0)
5601                 return dst;
5602
5603         for (i = 0; i < src->n_div; ++i)
5604                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
5605
5606         src = isl_basic_map_order_divs(src);
5607         dst = isl_basic_map_cow(dst);
5608         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
5609                         src->n_div, 0, 2 * src->n_div);
5610         if (!dst)
5611                 return NULL;
5612         for (i = 0; i < src->n_div; ++i) {
5613                 int j = find_div(dst, src, i);
5614                 if (j < 0) {
5615                         j = isl_basic_map_alloc_div(dst);
5616                         if (j < 0)
5617                                 goto error;
5618                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
5619                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
5620                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
5621                                 goto error;
5622                 }
5623                 if (j != i)
5624                         isl_basic_map_swap_div(dst, i, j);
5625         }
5626         return dst;
5627 error:
5628         isl_basic_map_free(dst);
5629         return NULL;
5630 }
5631
5632 struct isl_basic_set *isl_basic_set_align_divs(
5633                 struct isl_basic_set *dst, struct isl_basic_set *src)
5634 {
5635         return (struct isl_basic_set *)isl_basic_map_align_divs(
5636                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
5637 }
5638
5639 struct isl_map *isl_map_align_divs(struct isl_map *map)
5640 {
5641         int i;
5642
5643         if (!map)
5644                 return NULL;
5645         if (map->n == 0)
5646                 return map;
5647         map = isl_map_compute_divs(map);
5648         map = isl_map_cow(map);
5649         if (!map)
5650                 return NULL;
5651
5652         for (i = 1; i < map->n; ++i)
5653                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
5654         for (i = 1; i < map->n; ++i)
5655                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
5656
5657         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5658         return map;
5659 }
5660
5661 struct isl_set *isl_set_align_divs(struct isl_set *set)
5662 {
5663         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
5664 }
5665
5666 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
5667 {
5668         if (!set || !map)
5669                 goto error;
5670         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
5671         map = isl_map_intersect_domain(map, set);
5672         set = isl_map_range(map);
5673         return set;
5674 error:
5675         isl_set_free(set);
5676         isl_map_free(map);
5677         return NULL;
5678 }
5679
5680 /* There is no need to cow as removing empty parts doesn't change
5681  * the meaning of the set.
5682  */
5683 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
5684 {
5685         int i;
5686
5687         if (!map)
5688                 return NULL;
5689
5690         for (i = map->n-1; i >= 0; --i) {
5691                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
5692                         continue;
5693                 isl_basic_map_free(map->p[i]);
5694                 if (i != map->n-1) {
5695                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5696                         map->p[i] = map->p[map->n-1];
5697                 }
5698                 map->n--;
5699         }
5700
5701         return map;
5702 }
5703
5704 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
5705 {
5706         return (struct isl_set *)
5707                 isl_map_remove_empty_parts((struct isl_map *)set);
5708 }
5709
5710 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
5711 {
5712         struct isl_basic_map *bmap;
5713         if (!map || map->n == 0)
5714                 return NULL;
5715         bmap = map->p[map->n-1];
5716         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
5717         return isl_basic_map_copy(bmap);
5718 }
5719
5720 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
5721 {
5722         return (struct isl_basic_set *)
5723                 isl_map_copy_basic_map((struct isl_map *)set);
5724 }
5725
5726 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
5727                                                 __isl_keep isl_basic_map *bmap)
5728 {
5729         int i;
5730
5731         if (!map || !bmap)
5732                 goto error;
5733         for (i = map->n-1; i >= 0; --i) {
5734                 if (map->p[i] != bmap)
5735                         continue;
5736                 map = isl_map_cow(map);
5737                 if (!map)
5738                         goto error;
5739                 isl_basic_map_free(map->p[i]);
5740                 if (i != map->n-1) {
5741                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
5742                         map->p[i] = map->p[map->n-1];
5743                 }
5744                 map->n--;
5745                 return map;
5746         }
5747         return map;
5748 error:
5749         isl_map_free(map);
5750         return NULL;
5751 }
5752
5753 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
5754                                                 struct isl_basic_set *bset)
5755 {
5756         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
5757                                                 (struct isl_basic_map *)bset);
5758 }
5759
5760 /* Given two basic sets bset1 and bset2, compute the maximal difference
5761  * between the values of dimension pos in bset1 and those in bset2
5762  * for any common value of the parameters and dimensions preceding pos.
5763  */
5764 static enum isl_lp_result basic_set_maximal_difference_at(
5765         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
5766         int pos, isl_int *opt)
5767 {
5768         struct isl_dim *dims;
5769         struct isl_basic_map *bmap1 = NULL;
5770         struct isl_basic_map *bmap2 = NULL;
5771         struct isl_ctx *ctx;
5772         struct isl_vec *obj;
5773         unsigned total;
5774         unsigned nparam;
5775         unsigned dim1, dim2;
5776         enum isl_lp_result res;
5777
5778         if (!bset1 || !bset2)
5779                 return isl_lp_error;
5780
5781         nparam = isl_basic_set_n_param(bset1);
5782         dim1 = isl_basic_set_n_dim(bset1);
5783         dim2 = isl_basic_set_n_dim(bset2);
5784         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
5785         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
5786         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
5787         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
5788         if (!bmap1 || !bmap2)
5789                 goto error;
5790         bmap1 = isl_basic_map_cow(bmap1);
5791         bmap1 = isl_basic_map_extend(bmap1, nparam,
5792                         pos, (dim1 - pos) + (dim2 - pos),
5793                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
5794         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
5795         if (!bmap1)
5796                 goto error;
5797         total = isl_basic_map_total_dim(bmap1);
5798         ctx = bmap1->ctx;
5799         obj = isl_vec_alloc(ctx, 1 + total);
5800         isl_seq_clr(obj->block.data, 1 + total);
5801         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
5802         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
5803         if (!obj)
5804                 goto error;
5805         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
5806                                         opt, NULL, NULL);
5807         isl_basic_map_free(bmap1);
5808         isl_vec_free(obj);
5809         return res;
5810 error:
5811         isl_basic_map_free(bmap1);
5812         isl_basic_map_free(bmap2);
5813         return isl_lp_error;
5814 }
5815
5816 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
5817  * for any common value of the parameters and dimensions preceding pos
5818  * in both basic sets, the values of dimension pos in bset1 are
5819  * smaller or larger than those in bset2.
5820  *
5821  * Returns
5822  *       1 if bset1 follows bset2
5823  *      -1 if bset1 precedes bset2
5824  *       0 if bset1 and bset2 are incomparable
5825  *      -2 if some error occurred.
5826  */
5827 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
5828         struct isl_basic_set *bset2, int pos)
5829 {
5830         isl_int opt;
5831         enum isl_lp_result res;
5832         int cmp;
5833
5834         isl_int_init(opt);
5835
5836         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5837
5838         if (res == isl_lp_empty)
5839                 cmp = 0;
5840         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5841                   res == isl_lp_unbounded)
5842                 cmp = 1;
5843         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5844                 cmp = -1;
5845         else
5846                 cmp = -2;
5847
5848         isl_int_clear(opt);
5849         return cmp;
5850 }
5851
5852 /* Given two basic sets bset1 and bset2, check whether
5853  * for any common value of the parameters and dimensions preceding pos
5854  * there is a value of dimension pos in bset1 that is larger
5855  * than a value of the same dimension in bset2.
5856  *
5857  * Return
5858  *       1 if there exists such a pair
5859  *       0 if there is no such pair, but there is a pair of equal values
5860  *      -1 otherwise
5861  *      -2 if some error occurred.
5862  */
5863 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
5864         __isl_keep isl_basic_set *bset2, int pos)
5865 {
5866         isl_int opt;
5867         enum isl_lp_result res;
5868         int cmp;
5869
5870         isl_int_init(opt);
5871
5872         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5873
5874         if (res == isl_lp_empty)
5875                 cmp = -1;
5876         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5877                   res == isl_lp_unbounded)
5878                 cmp = 1;
5879         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5880                 cmp = -1;
5881         else if (res == isl_lp_ok)
5882                 cmp = 0;
5883         else
5884                 cmp = -2;
5885
5886         isl_int_clear(opt);
5887         return cmp;
5888 }
5889
5890 /* Given two sets set1 and set2, check whether
5891  * for any common value of the parameters and dimensions preceding pos
5892  * there is a value of dimension pos in set1 that is larger
5893  * than a value of the same dimension in set2.
5894  *
5895  * Return
5896  *       1 if there exists such a pair
5897  *       0 if there is no such pair, but there is a pair of equal values
5898  *      -1 otherwise
5899  *      -2 if some error occurred.
5900  */
5901 int isl_set_follows_at(__isl_keep isl_set *set1,
5902         __isl_keep isl_set *set2, int pos)
5903 {
5904         int i, j;
5905         int follows = -1;
5906
5907         if (!set1 || !set2)
5908                 return -2;
5909
5910         for (i = 0; i < set1->n; ++i)
5911                 for (j = 0; j < set2->n; ++j) {
5912                         int f;
5913                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5914                         if (f == 1 || f == -2)
5915                                 return f;
5916                         if (f > follows)
5917                                 follows = f;
5918                 }
5919
5920         return follows;
5921 }
5922
5923 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5924         unsigned pos, isl_int *val)
5925 {
5926         int i;
5927         int d;
5928         unsigned total;
5929
5930         if (!bmap)
5931                 return -1;
5932         total = isl_basic_map_total_dim(bmap);
5933         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5934                 for (; d+1 > pos; --d)
5935                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5936                                 break;
5937                 if (d != pos)
5938                         continue;
5939                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5940                         return 0;
5941                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5942                         return 0;
5943                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5944                         return 0;
5945                 if (val)
5946                         isl_int_neg(*val, bmap->eq[i][0]);
5947                 return 1;
5948         }
5949         return 0;
5950 }
5951
5952 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5953         unsigned pos, isl_int *val)
5954 {
5955         int i;
5956         isl_int v;
5957         isl_int tmp;
5958         int fixed;
5959
5960         if (!map)
5961                 return -1;
5962         if (map->n == 0)
5963                 return 0;
5964         if (map->n == 1)
5965                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5966         isl_int_init(v);
5967         isl_int_init(tmp);
5968         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5969         for (i = 1; fixed == 1 && i < map->n; ++i) {
5970                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5971                 if (fixed == 1 && isl_int_ne(tmp, v))
5972                         fixed = 0;
5973         }
5974         if (val)
5975                 isl_int_set(*val, v);
5976         isl_int_clear(tmp);
5977         isl_int_clear(v);
5978         return fixed;
5979 }
5980
5981 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5982         unsigned pos, isl_int *val)
5983 {
5984         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5985                                                 pos, val);
5986 }
5987
5988 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5989         isl_int *val)
5990 {
5991         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5992 }
5993
5994 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5995         enum isl_dim_type type, unsigned pos, isl_int *val)
5996 {
5997         if (pos >= isl_basic_map_dim(bmap, type))
5998                 return -1;
5999         return isl_basic_map_fast_has_fixed_var(bmap,
6000                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
6001 }
6002
6003 int isl_map_fast_is_fixed(struct isl_map *map,
6004         enum isl_dim_type type, unsigned pos, isl_int *val)
6005 {
6006         if (pos >= isl_map_dim(map, type))
6007                 return -1;
6008         return isl_map_fast_has_fixed_var(map,
6009                 map_offset(map, type) - 1 + pos, val);
6010 }
6011
6012 /* Check if dimension dim has fixed value and if so and if val is not NULL,
6013  * then return this fixed value in *val.
6014  */
6015 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
6016         isl_int *val)
6017 {
6018         return isl_basic_set_fast_has_fixed_var(bset,
6019                                         isl_basic_set_n_param(bset) + dim, val);
6020 }
6021
6022 /* Check if dimension dim has fixed value and if so and if val is not NULL,
6023  * then return this fixed value in *val.
6024  */
6025 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
6026 {
6027         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
6028 }
6029
6030 /* Check if input variable in has fixed value and if so and if val is not NULL,
6031  * then return this fixed value in *val.
6032  */
6033 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
6034 {
6035         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
6036 }
6037
6038 /* Check if dimension dim has an (obvious) fixed lower bound and if so
6039  * and if val is not NULL, then return this lower bound in *val.
6040  */
6041 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
6042         unsigned dim, isl_int *val)
6043 {
6044         int i, i_eq = -1, i_ineq = -1;
6045         isl_int *c;
6046         unsigned total;
6047         unsigned nparam;
6048
6049         if (!bset)
6050                 return -1;
6051         total = isl_basic_set_total_dim(bset);
6052         nparam = isl_basic_set_n_param(bset);
6053         for (i = 0; i < bset->n_eq; ++i) {
6054                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
6055                         continue;
6056                 if (i_eq != -1)
6057                         return 0;
6058                 i_eq = i;
6059         }
6060         for (i = 0; i < bset->n_ineq; ++i) {
6061                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
6062                         continue;
6063                 if (i_eq != -1 || i_ineq != -1)
6064                         return 0;
6065                 i_ineq = i;
6066         }
6067         if (i_eq == -1 && i_ineq == -1)
6068                 return 0;
6069         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
6070         /* The coefficient should always be one due to normalization. */
6071         if (!isl_int_is_one(c[1+nparam+dim]))
6072                 return 0;
6073         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
6074                 return 0;
6075         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
6076                                         total - nparam - dim - 1) != -1)
6077                 return 0;
6078         if (val)
6079                 isl_int_neg(*val, c[0]);
6080         return 1;
6081 }
6082
6083 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
6084         unsigned dim, isl_int *val)
6085 {
6086         int i;
6087         isl_int v;
6088         isl_int tmp;
6089         int fixed;
6090
6091         if (!set)
6092                 return -1;
6093         if (set->n == 0)
6094                 return 0;
6095         if (set->n == 1)
6096                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
6097                                                                 dim, val);
6098         isl_int_init(v);
6099         isl_int_init(tmp);
6100         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
6101                                                                 dim, &v);
6102         for (i = 1; fixed == 1 && i < set->n; ++i) {
6103                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
6104                                                                 dim, &tmp);
6105                 if (fixed == 1 && isl_int_ne(tmp, v))
6106                         fixed = 0;
6107         }
6108         if (val)
6109                 isl_int_set(*val, v);
6110         isl_int_clear(tmp);
6111         isl_int_clear(v);
6112         return fixed;
6113 }
6114
6115 struct constraint {
6116         unsigned        size;
6117         isl_int         *c;
6118 };
6119
6120 static int qsort_constraint_cmp(const void *p1, const void *p2)
6121 {
6122         const struct constraint *c1 = (const struct constraint *)p1;
6123         const struct constraint *c2 = (const struct constraint *)p2;
6124         unsigned size = isl_min(c1->size, c2->size);
6125         return isl_seq_cmp(c1->c, c2->c, size);
6126 }
6127
6128 static struct isl_basic_map *isl_basic_map_sort_constraints(
6129         struct isl_basic_map *bmap)
6130 {
6131         int i;
6132         struct constraint *c;
6133         unsigned total;
6134
6135         if (!bmap)
6136                 return NULL;
6137         total = isl_basic_map_total_dim(bmap);
6138         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
6139         if (!c)
6140                 goto error;
6141         for (i = 0; i < bmap->n_ineq; ++i) {
6142                 c[i].size = total;
6143                 c[i].c = bmap->ineq[i];
6144         }
6145         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
6146         for (i = 0; i < bmap->n_ineq; ++i)
6147                 bmap->ineq[i] = c[i].c;
6148         free(c);
6149         return bmap;
6150 error:
6151         isl_basic_map_free(bmap);
6152         return NULL;
6153 }
6154
6155 __isl_give isl_basic_set *isl_basic_set_sort_constraints(
6156         __isl_take isl_basic_set *bset)
6157 {
6158         return (struct isl_basic_set *)isl_basic_map_sort_constraints(
6159                                                 (struct isl_basic_map *)bset);
6160 }
6161
6162 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
6163 {
6164         if (!bmap)
6165                 return NULL;
6166         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
6167                 return bmap;
6168         bmap = isl_basic_map_remove_redundancies(bmap);
6169         bmap = isl_basic_map_sort_constraints(bmap);
6170         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
6171         return bmap;
6172 }
6173
6174 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
6175 {
6176         return (struct isl_basic_set *)isl_basic_map_normalize(
6177                                                 (struct isl_basic_map *)bset);
6178 }
6179
6180 int isl_basic_map_fast_cmp(const __isl_keep isl_basic_map *bmap1,
6181         const __isl_keep isl_basic_map *bmap2)
6182 {
6183         int i, cmp;
6184         unsigned total;
6185
6186         if (bmap1 == bmap2)
6187                 return 0;
6188         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
6189                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
6190         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
6191                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
6192         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
6193                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
6194         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
6195             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
6196                 return 0;
6197         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
6198                 return 1;
6199         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
6200                 return -1;
6201         if (bmap1->n_eq != bmap2->n_eq)
6202                 return bmap1->n_eq - bmap2->n_eq;
6203         if (bmap1->n_ineq != bmap2->n_ineq)
6204                 return bmap1->n_ineq - bmap2->n_ineq;
6205         if (bmap1->n_div != bmap2->n_div)
6206                 return bmap1->n_div - bmap2->n_div;
6207         total = isl_basic_map_total_dim(bmap1);
6208         for (i = 0; i < bmap1->n_eq; ++i) {
6209                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
6210                 if (cmp)
6211                         return cmp;
6212         }
6213         for (i = 0; i < bmap1->n_ineq; ++i) {
6214                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
6215                 if (cmp)
6216                         return cmp;
6217         }
6218         for (i = 0; i < bmap1->n_div; ++i) {
6219                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
6220                 if (cmp)
6221                         return cmp;
6222         }
6223         return 0;
6224 }
6225
6226 int isl_basic_map_fast_is_equal(__isl_keep isl_basic_map *bmap1,
6227         __isl_keep isl_basic_map *bmap2)
6228 {
6229         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
6230 }
6231
6232 int isl_basic_set_fast_is_equal(__isl_keep isl_basic_set *bset1,
6233         __isl_keep isl_basic_set *bset2)
6234 {
6235         return isl_basic_map_fast_is_equal((isl_basic_map *)bset1,
6236                                             (isl_basic_map *)bset2);
6237 }
6238
6239 static int qsort_bmap_cmp(const void *p1, const void *p2)
6240 {
6241         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
6242         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
6243
6244         return isl_basic_map_fast_cmp(bmap1, bmap2);
6245 }
6246
6247 /* We normalize in place, but if anything goes wrong we need
6248  * to return NULL, so we need to make sure we don't change the
6249  * meaning of any possible other copies of map.
6250  */
6251 struct isl_map *isl_map_normalize(struct isl_map *map)
6252 {
6253         int i, j;
6254         struct isl_basic_map *bmap;
6255
6256         if (!map)
6257                 return NULL;
6258         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
6259                 return map;
6260         for (i = 0; i < map->n; ++i) {
6261                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
6262                 if (!bmap)
6263                         goto error;
6264                 isl_basic_map_free(map->p[i]);
6265                 map->p[i] = bmap;
6266         }
6267         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
6268         ISL_F_SET(map, ISL_MAP_NORMALIZED);
6269         map = isl_map_remove_empty_parts(map);
6270         if (!map)
6271                 return NULL;
6272         for (i = map->n - 1; i >= 1; --i) {
6273                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
6274                         continue;
6275                 isl_basic_map_free(map->p[i-1]);
6276                 for (j = i; j < map->n; ++j)
6277                         map->p[j-1] = map->p[j];
6278                 map->n--;
6279         }
6280         return map;
6281 error:
6282         isl_map_free(map);
6283         return NULL;
6284
6285 }
6286
6287 struct isl_set *isl_set_normalize(struct isl_set *set)
6288 {
6289         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
6290 }
6291
6292 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
6293 {
6294         int i;
6295         int equal;
6296
6297         if (!map1 || !map2)
6298                 return -1;
6299
6300         if (map1 == map2)
6301                 return 1;
6302         if (!isl_dim_equal(map1->dim, map2->dim))
6303                 return 0;
6304
6305         map1 = isl_map_copy(map1);
6306         map2 = isl_map_copy(map2);
6307         map1 = isl_map_normalize(map1);
6308         map2 = isl_map_normalize(map2);
6309         if (!map1 || !map2)
6310                 goto error;
6311         equal = map1->n == map2->n;
6312         for (i = 0; equal && i < map1->n; ++i) {
6313                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
6314                 if (equal < 0)
6315                         goto error;
6316         }
6317         isl_map_free(map1);
6318         isl_map_free(map2);
6319         return equal;
6320 error:
6321         isl_map_free(map1);
6322         isl_map_free(map2);
6323         return -1;
6324 }
6325
6326 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
6327 {
6328         return isl_map_fast_is_equal((struct isl_map *)set1,
6329                                                 (struct isl_map *)set2);
6330 }
6331
6332 /* Return an interval that ranges from min to max (inclusive)
6333  */
6334 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
6335         isl_int min, isl_int max)
6336 {
6337         int k;
6338         struct isl_basic_set *bset = NULL;
6339
6340         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
6341         if (!bset)
6342                 goto error;
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_neg(bset->ineq[k][0], min);
6349
6350         k = isl_basic_set_alloc_inequality(bset);
6351         if (k < 0)
6352                 goto error;
6353         isl_int_set_si(bset->ineq[k][1], -1);
6354         isl_int_set(bset->ineq[k][0], max);
6355
6356         return bset;
6357 error:
6358         isl_basic_set_free(bset);
6359         return NULL;
6360 }
6361
6362 /* Return the Cartesian product of the basic sets in list (in the given order).
6363  */
6364 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
6365 {
6366         int i;
6367         unsigned dim;
6368         unsigned nparam;
6369         unsigned extra;
6370         unsigned n_eq;
6371         unsigned n_ineq;
6372         struct isl_basic_set *product = NULL;
6373
6374         if (!list)
6375                 goto error;
6376         isl_assert(list->ctx, list->n > 0, goto error);
6377         isl_assert(list->ctx, list->p[0], goto error);
6378         nparam = isl_basic_set_n_param(list->p[0]);
6379         dim = isl_basic_set_n_dim(list->p[0]);
6380         extra = list->p[0]->n_div;
6381         n_eq = list->p[0]->n_eq;
6382         n_ineq = list->p[0]->n_ineq;
6383         for (i = 1; i < list->n; ++i) {
6384                 isl_assert(list->ctx, list->p[i], goto error);
6385                 isl_assert(list->ctx,
6386                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
6387                 dim += isl_basic_set_n_dim(list->p[i]);
6388                 extra += list->p[i]->n_div;
6389                 n_eq += list->p[i]->n_eq;
6390                 n_ineq += list->p[i]->n_ineq;
6391         }
6392         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
6393                                         n_eq, n_ineq);
6394         if (!product)
6395                 goto error;
6396         dim = 0;
6397         for (i = 0; i < list->n; ++i) {
6398                 isl_basic_set_add_constraints(product,
6399                                         isl_basic_set_copy(list->p[i]), dim);
6400                 dim += isl_basic_set_n_dim(list->p[i]);
6401         }
6402         isl_basic_set_list_free(list);
6403         return product;
6404 error:
6405         isl_basic_set_free(product);
6406         isl_basic_set_list_free(list);
6407         return NULL;
6408 }
6409
6410 struct isl_basic_map *isl_basic_map_product(
6411                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
6412 {
6413         struct isl_dim *dim_result = NULL;
6414         struct isl_basic_map *bmap;
6415         unsigned in1, in2, out1, out2, nparam, total, pos;
6416         struct isl_dim_map *dim_map1, *dim_map2;
6417
6418         if (!bmap1 || !bmap2)
6419                 goto error;
6420
6421         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
6422                                      bmap2->dim, isl_dim_param), goto error);
6423         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
6424                                                    isl_dim_copy(bmap2->dim));
6425
6426         in1 = isl_basic_map_n_in(bmap1);
6427         in2 = isl_basic_map_n_in(bmap2);
6428         out1 = isl_basic_map_n_out(bmap1);
6429         out2 = isl_basic_map_n_out(bmap2);
6430         nparam = isl_basic_map_n_param(bmap1);
6431
6432         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
6433         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
6434         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
6435         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
6436         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
6437         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
6438         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
6439         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
6440         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
6441         isl_dim_map_div(dim_map1, bmap1, pos += out2);
6442         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
6443
6444         bmap = isl_basic_map_alloc_dim(dim_result,
6445                         bmap1->n_div + bmap2->n_div,
6446                         bmap1->n_eq + bmap2->n_eq,
6447                         bmap1->n_ineq + bmap2->n_ineq);
6448         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
6449         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
6450         bmap = isl_basic_map_simplify(bmap);
6451         return isl_basic_map_finalize(bmap);
6452 error:
6453         isl_basic_map_free(bmap1);
6454         isl_basic_map_free(bmap2);
6455         return NULL;
6456 }
6457
6458 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> [B -> D]
6459  */
6460 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
6461 {
6462         unsigned flags = 0;
6463         struct isl_map *result;
6464         int i, j;
6465
6466         if (!map1 || !map2)
6467                 goto error;
6468
6469         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
6470                                          map2->dim, isl_dim_param), goto error);
6471
6472         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
6473             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
6474                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
6475
6476         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
6477                                                    isl_dim_copy(map2->dim)),
6478                                 map1->n * map2->n, flags);
6479         if (!result)
6480                 goto error;
6481         for (i = 0; i < map1->n; ++i)
6482                 for (j = 0; j < map2->n; ++j) {
6483                         struct isl_basic_map *part;
6484                         part = isl_basic_map_product(
6485                                     isl_basic_map_copy(map1->p[i]),
6486                                     isl_basic_map_copy(map2->p[j]));
6487                         if (isl_basic_map_is_empty(part))
6488                                 isl_basic_map_free(part);
6489                         else
6490                                 result = isl_map_add_basic_map(result, part);
6491                         if (!result)
6492                                 goto error;
6493                 }
6494         isl_map_free(map1);
6495         isl_map_free(map2);
6496         return result;
6497 error:
6498         isl_map_free(map1);
6499         isl_map_free(map2);
6500         return NULL;
6501 }
6502
6503 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
6504  */
6505 __isl_give isl_map *isl_map_flat_product(__isl_take isl_map *map1,
6506         __isl_take isl_map *map2)
6507 {
6508         isl_map *prod;
6509
6510         prod = isl_map_product(map1, map2);
6511         prod = isl_map_flatten(prod);
6512         return prod;
6513 }
6514
6515 /* Given two set A and B, construct its Cartesian product A x B.
6516  */
6517 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
6518 {
6519         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
6520                                                  (struct isl_map *)set2);
6521 }
6522
6523 __isl_give isl_set *isl_set_flat_product(__isl_take isl_set *set1,
6524         __isl_take isl_set *set2)
6525 {
6526         return (isl_set *)isl_map_flat_product((isl_map *)set1, (isl_map *)set2);
6527 }
6528
6529 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
6530 {
6531         int i;
6532         uint32_t hash = isl_hash_init();
6533         unsigned total;
6534
6535         if (!bset)
6536                 return 0;
6537         bset = isl_basic_set_copy(bset);
6538         bset = isl_basic_set_normalize(bset);
6539         if (!bset)
6540                 return 0;
6541         total = isl_basic_set_total_dim(bset);
6542         isl_hash_byte(hash, bset->n_eq & 0xFF);
6543         for (i = 0; i < bset->n_eq; ++i) {
6544                 uint32_t c_hash;
6545                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
6546                 isl_hash_hash(hash, c_hash);
6547         }
6548         isl_hash_byte(hash, bset->n_ineq & 0xFF);
6549         for (i = 0; i < bset->n_ineq; ++i) {
6550                 uint32_t c_hash;
6551                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
6552                 isl_hash_hash(hash, c_hash);
6553         }
6554         isl_hash_byte(hash, bset->n_div & 0xFF);
6555         for (i = 0; i < bset->n_div; ++i) {
6556                 uint32_t c_hash;
6557                 if (isl_int_is_zero(bset->div[i][0]))
6558                         continue;
6559                 isl_hash_byte(hash, i & 0xFF);
6560                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
6561                 isl_hash_hash(hash, c_hash);
6562         }
6563         isl_basic_set_free(bset);
6564         return hash;
6565 }
6566
6567 uint32_t isl_set_get_hash(struct isl_set *set)
6568 {
6569         int i;
6570         uint32_t hash;
6571
6572         if (!set)
6573                 return 0;
6574         set = isl_set_copy(set);
6575         set = isl_set_normalize(set);
6576         if (!set)
6577                 return 0;
6578
6579         hash = isl_hash_init();
6580         for (i = 0; i < set->n; ++i) {
6581                 uint32_t bset_hash;
6582                 bset_hash = isl_basic_set_get_hash(set->p[i]);
6583                 isl_hash_hash(hash, bset_hash);
6584         }
6585
6586         isl_set_free(set);
6587
6588         return hash;
6589 }
6590
6591 /* Check if the value for dimension dim is completely determined
6592  * by the values of the other parameters and variables.
6593  * That is, check if dimension dim is involved in an equality.
6594  */
6595 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
6596 {
6597         int i;
6598         unsigned nparam;
6599
6600         if (!bset)
6601                 return -1;
6602         nparam = isl_basic_set_n_param(bset);
6603         for (i = 0; i < bset->n_eq; ++i)
6604                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
6605                         return 1;
6606         return 0;
6607 }
6608
6609 /* Check if the value for dimension dim is completely determined
6610  * by the values of the other parameters and variables.
6611  * That is, check if dimension dim is involved in an equality
6612  * for each of the subsets.
6613  */
6614 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
6615 {
6616         int i;
6617
6618         if (!set)
6619                 return -1;
6620         for (i = 0; i < set->n; ++i) {
6621                 int unique;
6622                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
6623                 if (unique != 1)
6624                         return unique;
6625         }
6626         return 1;
6627 }
6628
6629 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
6630         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
6631 {
6632         int i;
6633
6634         if (!map)
6635                 return -1;
6636
6637         for (i = 0; i < map->n; ++i)
6638                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
6639                         return -1;
6640
6641         return 0;
6642 }
6643
6644 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
6645         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
6646 {
6647         int i;
6648
6649         if (!set)
6650                 return -1;
6651
6652         for (i = 0; i < set->n; ++i)
6653                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
6654                         return -1;
6655
6656         return 0;
6657 }
6658
6659 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
6660 {
6661         struct isl_dim *dim;
6662
6663         if (!bset)
6664                 return NULL;
6665
6666         if (bset->n_div == 0)
6667                 return bset;
6668
6669         bset = isl_basic_set_cow(bset);
6670         if (!bset)
6671                 return NULL;
6672
6673         dim = isl_basic_set_get_dim(bset);
6674         dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
6675         if (!dim)
6676                 goto error;
6677         isl_dim_free(bset->dim);
6678         bset->dim = dim;
6679         bset->n_div = 0;
6680
6681         bset = isl_basic_set_finalize(bset);
6682
6683         return bset;
6684 error:
6685         isl_basic_set_free(bset);
6686         return NULL;
6687 }
6688
6689 __isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
6690 {
6691         int i;
6692         struct isl_dim *dim;
6693         unsigned n_div;
6694
6695         set = isl_set_align_divs(set);
6696
6697         if (!set)
6698                 return NULL;
6699         if (set->n == 0 || set->p[0]->n_div == 0)
6700                 return set;
6701
6702         set = isl_set_cow(set);
6703         if (!set)
6704                 return NULL;
6705
6706         n_div = set->p[0]->n_div;
6707         dim = isl_set_get_dim(set);
6708         dim = isl_dim_add(dim, isl_dim_set, n_div);
6709         if (!dim)
6710                 goto error;
6711         isl_dim_free(set->dim);
6712         set->dim = dim;
6713
6714         for (i = 0; i < set->n; ++i) {
6715                 set->p[i] = isl_basic_set_lift(set->p[i]);
6716                 if (!set->p[i])
6717                         goto error;
6718         }
6719
6720         return set;
6721 error:
6722         isl_set_free(set);
6723         return NULL;
6724 }
6725
6726 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
6727 {
6728         struct isl_dim *dim;
6729         struct isl_basic_map *bmap;
6730         unsigned n_set;
6731         unsigned n_div;
6732         unsigned n_param;
6733         unsigned total;
6734         int i, k, l;
6735
6736         set = isl_set_align_divs(set);
6737
6738         if (!set)
6739                 return NULL;
6740
6741         dim = isl_set_get_dim(set);
6742         if (set->n == 0 || set->p[0]->n_div == 0) {
6743                 isl_set_free(set);
6744                 return isl_map_identity(dim);
6745         }
6746
6747         n_div = set->p[0]->n_div;
6748         dim = isl_dim_map(dim);
6749         n_param = isl_dim_size(dim, isl_dim_param);
6750         n_set = isl_dim_size(dim, isl_dim_in);
6751         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
6752         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
6753         for (i = 0; i < n_set; ++i)
6754                 bmap = var_equal(bmap, i);
6755
6756         total = n_param + n_set + n_set + n_div;
6757         for (i = 0; i < n_div; ++i) {
6758                 k = isl_basic_map_alloc_inequality(bmap);
6759                 if (k < 0)
6760                         goto error;
6761                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
6762                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
6763                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
6764                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
6765                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
6766                             set->p[0]->div[i][0]);
6767
6768                 l = isl_basic_map_alloc_inequality(bmap);
6769                 if (l < 0)
6770                         goto error;
6771                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
6772                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
6773                             set->p[0]->div[i][0]);
6774                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
6775         }
6776
6777         isl_set_free(set);
6778         return isl_map_from_basic_map(bmap);
6779 error:
6780         isl_set_free(set);
6781         isl_basic_map_free(bmap);
6782         return NULL;
6783 }
6784
6785 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
6786 {
6787         unsigned dim;
6788         int size = 0;
6789
6790         if (!bset)
6791                 return -1;
6792
6793         dim = isl_basic_set_total_dim(bset);
6794         size += bset->n_eq * (1 + dim);
6795         size += bset->n_ineq * (1 + dim);
6796         size += bset->n_div * (2 + dim);
6797
6798         return size;
6799 }
6800
6801 int isl_set_size(__isl_keep isl_set *set)
6802 {
6803         int i;
6804         int size = 0;
6805
6806         if (!set)
6807                 return -1;
6808
6809         for (i = 0; i < set->n; ++i)
6810                 size += isl_basic_set_size(set->p[i]);
6811
6812         return size;
6813 }
6814
6815 int isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
6816         enum isl_dim_type type, unsigned pos)
6817 {
6818         int i;
6819         int lower, upper;
6820
6821         if (!bmap)
6822                 return -1;
6823
6824         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
6825
6826         pos += isl_basic_map_offset(bmap, type);
6827
6828         for (i = 0; i < bmap->n_eq; ++i)
6829                 if (!isl_int_is_zero(bmap->eq[i][pos]))
6830                         return 1;
6831
6832         lower = upper = 0;
6833         for (i = 0; i < bmap->n_ineq; ++i) {
6834                 int sgn = isl_int_sgn(bmap->ineq[i][pos]);
6835                 if (sgn > 0)
6836                         lower = 1;
6837                 if (sgn < 0)
6838                         upper = 1;
6839         }
6840
6841         return lower && upper;
6842 }
6843
6844 int isl_map_dim_is_bounded(__isl_keep isl_map *map,
6845         enum isl_dim_type type, unsigned pos)
6846 {
6847         int i;
6848
6849         if (!map)
6850                 return -1;
6851
6852         for (i = 0; i < map->n; ++i) {
6853                 int bounded;
6854                 bounded = isl_basic_map_dim_is_bounded(map->p[i], type, pos);
6855                 if (bounded < 0 || !bounded)
6856                         return bounded;
6857         }
6858
6859         return 1;
6860 }
6861
6862 /* Return 1 if the specified dim is involved in both an upper bound
6863  * and a lower bound.
6864  */
6865 int isl_set_dim_is_bounded(__isl_keep isl_set *set,
6866         enum isl_dim_type type, unsigned pos)
6867 {
6868         return isl_map_dim_is_bounded((isl_map *)set, type, pos);
6869 }
6870
6871 /* For each of the "n" variables starting at "first", determine
6872  * the sign of the variable and put the results in the first "n"
6873  * elements of the array "signs".
6874  * Sign
6875  *      1 means that the variable is non-negative
6876  *      -1 means that the variable is non-positive
6877  *      0 means the variable attains both positive and negative values.
6878  */
6879 int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
6880         unsigned first, unsigned n, int *signs)
6881 {
6882         isl_vec *bound = NULL;
6883         struct isl_tab *tab = NULL;
6884         struct isl_tab_undo *snap;
6885         int i;
6886
6887         if (!bset || !signs)
6888                 return -1;
6889
6890         bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset));
6891         tab = isl_tab_from_basic_set(bset);
6892         if (!bound || !tab)
6893                 goto error;
6894
6895         isl_seq_clr(bound->el, bound->size);
6896         isl_int_set_si(bound->el[0], -1);
6897
6898         snap = isl_tab_snap(tab);
6899         for (i = 0; i < n; ++i) {
6900                 int empty;
6901
6902                 isl_int_set_si(bound->el[1 + first + i], -1);
6903                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6904                         goto error;
6905                 empty = tab->empty;
6906                 isl_int_set_si(bound->el[1 + first + i], 0);
6907                 if (isl_tab_rollback(tab, snap) < 0)
6908                         goto error;
6909
6910                 if (empty) {
6911                         signs[i] = 1;
6912                         continue;
6913                 }
6914
6915                 isl_int_set_si(bound->el[1 + first + i], 1);
6916                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6917                         goto error;
6918                 empty = tab->empty;
6919                 isl_int_set_si(bound->el[1 + first + i], 0);
6920                 if (isl_tab_rollback(tab, snap) < 0)
6921                         goto error;
6922
6923                 signs[i] = empty ? -1 : 0;
6924         }
6925
6926         isl_tab_free(tab);
6927         isl_vec_free(bound);
6928         return 0;
6929 error:
6930         isl_tab_free(tab);
6931         isl_vec_free(bound);
6932         return -1;
6933 }
6934
6935 int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
6936         enum isl_dim_type type, unsigned first, unsigned n, int *signs)
6937 {
6938         if (!bset || !signs)
6939                 return -1;
6940         isl_assert(bset->ctx, first + n <= isl_basic_set_dim(bset, type),
6941                 return -1);
6942
6943         first += pos(bset->dim, type) - 1;
6944         return isl_basic_set_vars_get_sign(bset, first, n, signs);
6945 }
6946
6947 /* Check if the given map is single-valued.
6948  * We simply compute
6949  *
6950  *      M \circ M^-1
6951  *
6952  * and check if the result is a subset of the identity mapping.
6953  */
6954 int isl_map_is_single_valued(__isl_keep isl_map *map)
6955 {
6956         isl_map *test;
6957         isl_map *id;
6958         int sv;
6959
6960         test = isl_map_reverse(isl_map_copy(map));
6961         test = isl_map_apply_range(test, isl_map_copy(map));
6962
6963         id = isl_map_identity(isl_dim_range(isl_map_get_dim(map)));
6964
6965         sv = isl_map_is_subset(test, id);
6966
6967         isl_map_free(test);
6968         isl_map_free(id);
6969
6970         return sv;
6971 }
6972
6973 int isl_map_is_bijective(__isl_keep isl_map *map)
6974 {
6975         int sv;
6976
6977         sv = isl_map_is_single_valued(map);
6978         if (sv < 0 || !sv)
6979                 return sv;
6980
6981         map = isl_map_copy(map);
6982         map = isl_map_reverse(map);
6983         sv = isl_map_is_single_valued(map);
6984         isl_map_free(map);
6985
6986         return sv;
6987 }
6988
6989 int isl_set_is_singleton(__isl_keep isl_set *set)
6990 {
6991         return isl_map_is_single_valued((isl_map *)set);
6992 }
6993
6994 int isl_map_is_translation(__isl_keep isl_map *map)
6995 {
6996         int ok;
6997         isl_set *delta;
6998
6999         delta = isl_map_deltas(isl_map_copy(map));
7000         ok = isl_set_is_singleton(delta);
7001         isl_set_free(delta);
7002
7003         return ok;
7004 }
7005
7006 static int unique(isl_int *p, unsigned pos, unsigned len)
7007 {
7008         if (isl_seq_first_non_zero(p, pos) != -1)
7009                 return 0;
7010         if (isl_seq_first_non_zero(p + pos + 1, len - pos - 1) != -1)
7011                 return 0;
7012         return 1;
7013 }
7014
7015 int isl_basic_set_is_box(__isl_keep isl_basic_set *bset)
7016 {
7017         int i, j;
7018         unsigned nvar;
7019         unsigned ovar;
7020
7021         if (!bset)
7022                 return -1;
7023
7024         if (isl_basic_set_dim(bset, isl_dim_div) != 0)
7025                 return 0;
7026
7027         nvar = isl_basic_set_dim(bset, isl_dim_set);
7028         ovar = isl_dim_offset(bset->dim, isl_dim_set);
7029         for (j = 0; j < nvar; ++j) {
7030                 int lower = 0, upper = 0;
7031                 for (i = 0; i < bset->n_eq; ++i) {
7032                         if (isl_int_is_zero(bset->eq[i][1 + ovar + j]))
7033                                 continue;
7034                         if (!unique(bset->eq[i] + 1 + ovar, j, nvar))
7035                                 return 0;
7036                         break;
7037                 }
7038                 if (i < bset->n_eq)
7039                         continue;
7040                 for (i = 0; i < bset->n_ineq; ++i) {
7041                         if (isl_int_is_zero(bset->ineq[i][1 + ovar + j]))
7042                                 continue;
7043                         if (!unique(bset->ineq[i] + 1 + ovar, j, nvar))
7044                                 return 0;
7045                         if (isl_int_is_pos(bset->ineq[i][1 + ovar + j]))
7046                                 lower = 1;
7047                         else
7048                                 upper = 1;
7049                 }
7050                 if (!lower || !upper)
7051                         return 0;
7052         }
7053
7054         return 1;
7055 }
7056
7057 int isl_set_is_box(__isl_keep isl_set *set)
7058 {
7059         if (!set)
7060                 return -1;
7061         if (set->n != 1)
7062                 return 0;
7063
7064         return isl_basic_set_is_box(set->p[0]);
7065 }
7066
7067 int isl_basic_set_is_wrapping(__isl_keep isl_basic_set *bset)
7068 {
7069         if (!bset)
7070                 return -1;
7071
7072         return isl_dim_is_wrapping(bset->dim);
7073 }
7074
7075 int isl_set_is_wrapping(__isl_keep isl_set *set)
7076 {
7077         if (!set)
7078                 return -1;
7079
7080         return isl_dim_is_wrapping(set->dim);
7081 }
7082
7083 __isl_give isl_basic_set *isl_basic_map_wrap(__isl_take isl_basic_map *bmap)
7084 {
7085         bmap = isl_basic_map_cow(bmap);
7086         if (!bmap)
7087                 return NULL;
7088
7089         bmap->dim = isl_dim_wrap(bmap->dim);
7090         if (!bmap->dim)
7091                 goto error;
7092
7093         bmap = isl_basic_map_finalize(bmap);
7094
7095         return (isl_basic_set *)bmap;
7096 error:
7097         isl_basic_map_free(bmap);
7098         return NULL;
7099 }
7100
7101 __isl_give isl_set *isl_map_wrap(__isl_take isl_map *map)
7102 {
7103         int i;
7104
7105         map = isl_map_cow(map);
7106         if (!map)
7107                 return NULL;
7108
7109         for (i = 0; i < map->n; ++i) {
7110                 map->p[i] = (isl_basic_map *)isl_basic_map_wrap(map->p[i]);
7111                 if (!map->p[i])
7112                         goto error;
7113         }
7114         map->dim = isl_dim_wrap(map->dim);
7115         if (!map->dim)
7116                 goto error;
7117
7118         return (isl_set *)map;
7119 error:
7120         isl_map_free(map);
7121         return NULL;
7122 }
7123
7124 __isl_give isl_basic_map *isl_basic_set_unwrap(__isl_take isl_basic_set *bset)
7125 {
7126         bset = isl_basic_set_cow(bset);
7127         if (!bset)
7128                 return NULL;
7129
7130         bset->dim = isl_dim_unwrap(bset->dim);
7131         if (!bset->dim)
7132                 goto error;
7133
7134         bset = isl_basic_set_finalize(bset);
7135
7136         return (isl_basic_map *)bset;
7137 error:
7138         isl_basic_set_free(bset);
7139         return NULL;
7140 }
7141
7142 __isl_give isl_map *isl_set_unwrap(__isl_take isl_set *set)
7143 {
7144         int i;
7145
7146         if (!set)
7147                 return NULL;
7148
7149         if (!isl_set_is_wrapping(set))
7150                 isl_die(set->ctx, isl_error_invalid, "not a wrapping set",
7151                         goto error);
7152
7153         set = isl_set_cow(set);
7154         if (!set)
7155                 return NULL;
7156
7157         for (i = 0; i < set->n; ++i) {
7158                 set->p[i] = (isl_basic_set *)isl_basic_set_unwrap(set->p[i]);
7159                 if (!set->p[i])
7160                         goto error;
7161         }
7162
7163         set->dim = isl_dim_unwrap(set->dim);
7164         if (!set->dim)
7165                 goto error;
7166
7167         return (isl_map *)set;
7168 error:
7169         isl_set_free(set);
7170         return NULL;
7171 }
7172
7173 __isl_give isl_basic_map *isl_basic_map_reset(__isl_take isl_basic_map *bmap,
7174         enum isl_dim_type type)
7175 {
7176         if (!bmap)
7177                 return NULL;
7178
7179         if (!isl_dim_is_named_or_nested(bmap->dim, type))
7180                 return bmap;
7181
7182         bmap = isl_basic_map_cow(bmap);
7183         if (!bmap)
7184                 return NULL;
7185
7186         bmap->dim = isl_dim_reset(bmap->dim, type);
7187         if (!bmap->dim)
7188                 goto error;
7189
7190         bmap = isl_basic_map_finalize(bmap);
7191
7192         return bmap;
7193 error:
7194         isl_basic_map_free(bmap);
7195         return NULL;
7196 }
7197
7198 __isl_give isl_map *isl_map_reset(__isl_take isl_map *map,
7199         enum isl_dim_type type)
7200 {
7201         int i;
7202
7203         if (!map)
7204                 return NULL;
7205
7206         if (!isl_dim_is_named_or_nested(map->dim, type))
7207                 return map;
7208
7209         map = isl_map_cow(map);
7210         if (!map)
7211                 return NULL;
7212
7213         for (i = 0; i < map->n; ++i) {
7214                 map->p[i] = isl_basic_map_reset(map->p[i], type);
7215                 if (!map->p[i])
7216                         goto error;
7217         }
7218         map->dim = isl_dim_reset(map->dim, type);
7219         if (!map->dim)
7220                 goto error;
7221
7222         return map;
7223 error:
7224         isl_map_free(map);
7225         return NULL;
7226 }
7227
7228 __isl_give isl_basic_map *isl_basic_map_flatten(__isl_take isl_basic_map *bmap)
7229 {
7230         if (!bmap)
7231                 return NULL;
7232
7233         if (!bmap->dim->nested[0] && !bmap->dim->nested[1])
7234                 return bmap;
7235
7236         bmap = isl_basic_map_cow(bmap);
7237         if (!bmap)
7238                 return NULL;
7239
7240         bmap->dim = isl_dim_flatten(bmap->dim);
7241         if (!bmap->dim)
7242                 goto error;
7243
7244         bmap = isl_basic_map_finalize(bmap);
7245
7246         return bmap;
7247 error:
7248         isl_basic_map_free(bmap);
7249         return NULL;
7250 }
7251
7252 __isl_give isl_map *isl_map_flatten(__isl_take isl_map *map)
7253 {
7254         int i;
7255
7256         if (!map)
7257                 return NULL;
7258
7259         if (!map->dim->nested[0] && !map->dim->nested[1])
7260                 return map;
7261
7262         map = isl_map_cow(map);
7263         if (!map)
7264                 return NULL;
7265
7266         for (i = 0; i < map->n; ++i) {
7267                 map->p[i] = isl_basic_map_flatten(map->p[i]);
7268                 if (!map->p[i])
7269                         goto error;
7270         }
7271         map->dim = isl_dim_flatten(map->dim);
7272         if (!map->dim)
7273                 goto error;
7274
7275         return map;
7276 error:
7277         isl_map_free(map);
7278         return NULL;
7279 }