isl_map.c

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