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