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(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(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(map, bmap);
1602 }
1603
1604 struct isl_set *isl_set_add(struct isl_set *set, struct isl_basic_set *bset)
1605 {
1606         return (struct isl_set *)isl_map_add((struct isl_map *)set,
1607                                                 (struct isl_basic_map *)bset);
1608 }
1609
1610 void isl_set_free(struct isl_set *set)
1611 {
1612         int i;
1613
1614         if (!set)
1615                 return;
1616
1617         if (--set->ref > 0)
1618                 return;
1619
1620         isl_ctx_deref(set->ctx);
1621         for (i = 0; i < set->n; ++i)
1622                 isl_basic_set_free(set->p[i]);
1623         isl_dim_free(set->dim);
1624         free(set);
1625 }
1626
1627 void isl_set_dump(struct isl_set *set, FILE *out, int indent)
1628 {
1629         int i;
1630
1631         if (!set) {
1632                 fprintf(out, "null set\n");
1633                 return;
1634         }
1635
1636         fprintf(out, "%*s", indent, "");
1637         fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
1638                         set->ref, set->n, set->dim->nparam, set->dim->n_out,
1639                         set->flags);
1640         for (i = 0; i < set->n; ++i) {
1641                 fprintf(out, "%*s", indent, "");
1642                 fprintf(out, "basic set %d:\n", i);
1643                 isl_basic_set_dump(set->p[i], out, indent+4);
1644         }
1645 }
1646
1647 void isl_map_dump(struct isl_map *map, FILE *out, int indent)
1648 {
1649         int i;
1650
1651         if (!map) {
1652                 fprintf(out, "null map\n");
1653                 return;
1654         }
1655
1656         fprintf(out, "%*s", indent, "");
1657         fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
1658                      "flags: %x, n_name: %d\n",
1659                         map->ref, map->n, map->dim->nparam, map->dim->n_in,
1660                         map->dim->n_out, map->flags, map->dim->n_name);
1661         for (i = 0; i < map->n; ++i) {
1662                 fprintf(out, "%*s", indent, "");
1663                 fprintf(out, "basic map %d:\n", i);
1664                 isl_basic_map_dump(map->p[i], out, indent+4);
1665         }
1666 }
1667
1668 struct isl_basic_map *isl_basic_map_intersect_domain(
1669                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1670 {
1671         struct isl_basic_map *bmap_domain;
1672         struct isl_dim *dim;
1673
1674         if (!bmap || !bset)
1675                 goto error;
1676
1677         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1678                                         bset->dim, isl_dim_param), goto error);
1679
1680         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1681                 isl_assert(bset->ctx,
1682                     isl_basic_map_compatible_domain(bmap, bset), goto error);
1683
1684         bmap = isl_basic_map_cow(bmap);
1685         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1686                         bset->n_div, bset->n_eq, bset->n_ineq);
1687         if (!bmap)
1688                 goto error;
1689         dim = isl_dim_reverse(isl_dim_copy(bset->dim));
1690         bmap_domain = isl_basic_map_from_basic_set(bset, dim);
1691         bmap = add_constraints(bmap, bmap_domain, 0, 0);
1692
1693         bmap = isl_basic_map_simplify(bmap);
1694         return isl_basic_map_finalize(bmap);
1695 error:
1696         isl_basic_map_free(bmap);
1697         isl_basic_set_free(bset);
1698         return NULL;
1699 }
1700
1701 struct isl_basic_map *isl_basic_map_intersect_range(
1702                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1703 {
1704         struct isl_basic_map *bmap_range;
1705
1706         if (!bmap || !bset)
1707                 goto error;
1708
1709         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1710                                         bset->dim, isl_dim_param), goto error);
1711
1712         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1713                 isl_assert(bset->ctx,
1714                     isl_basic_map_compatible_range(bmap, bset), goto error);
1715
1716         bmap = isl_basic_map_cow(bmap);
1717         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1718                         bset->n_div, bset->n_eq, bset->n_ineq);
1719         if (!bmap)
1720                 goto error;
1721         bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
1722         bmap = add_constraints(bmap, bmap_range, 0, 0);
1723
1724         bmap = isl_basic_map_simplify(bmap);
1725         return isl_basic_map_finalize(bmap);
1726 error:
1727         isl_basic_map_free(bmap);
1728         isl_basic_set_free(bset);
1729         return NULL;
1730 }
1731
1732 int isl_basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
1733 {
1734         int i;
1735         unsigned total;
1736         isl_int s;
1737
1738         total = 1 + isl_basic_map_total_dim(bmap);
1739         if (total != vec->size)
1740                 return -1;
1741
1742         isl_int_init(s);
1743
1744         for (i = 0; i < bmap->n_eq; ++i) {
1745                 isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
1746                 if (!isl_int_is_zero(s)) {
1747                         isl_int_clear(s);
1748                         return 0;
1749                 }
1750         }
1751
1752         for (i = 0; i < bmap->n_ineq; ++i) {
1753                 isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
1754                 if (isl_int_is_neg(s)) {
1755                         isl_int_clear(s);
1756                         return 0;
1757                 }
1758         }
1759
1760         isl_int_clear(s);
1761
1762         return 1;
1763 }
1764
1765 int isl_basic_set_contains(struct isl_basic_set *bset, struct isl_vec *vec)
1766 {
1767         return isl_basic_map_contains((struct isl_basic_map *)bset, vec);
1768 }
1769
1770 struct isl_basic_map *isl_basic_map_intersect(
1771                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1772 {
1773         struct isl_vec *sample = NULL;
1774
1775         if (!bmap1 || !bmap2)
1776                 goto error;
1777
1778         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
1779                                      bmap2->dim, isl_dim_param), goto error);
1780         if (isl_dim_total(bmap1->dim) ==
1781                                 isl_dim_size(bmap1->dim, isl_dim_param) &&
1782             isl_dim_total(bmap2->dim) !=
1783                                 isl_dim_size(bmap2->dim, isl_dim_param))
1784                 return isl_basic_map_intersect(bmap2, bmap1);
1785
1786         if (isl_dim_total(bmap2->dim) !=
1787                                         isl_dim_size(bmap2->dim, isl_dim_param))
1788                 isl_assert(bmap1->ctx,
1789                             isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
1790
1791         if (bmap1->sample &&
1792             isl_basic_map_contains(bmap1, bmap1->sample) > 0 &&
1793             isl_basic_map_contains(bmap2, bmap1->sample) > 0)
1794                 sample = isl_vec_copy(bmap1->sample);
1795         else if (bmap2->sample &&
1796             isl_basic_map_contains(bmap1, bmap2->sample) > 0 &&
1797             isl_basic_map_contains(bmap2, bmap2->sample) > 0)
1798                 sample = isl_vec_copy(bmap2->sample);
1799
1800         bmap1 = isl_basic_map_cow(bmap1);
1801         bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
1802                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
1803         if (!bmap1)
1804                 goto error;
1805         bmap1 = add_constraints(bmap1, bmap2, 0, 0);
1806
1807         if (sample) {
1808                 isl_vec_free(bmap1->sample);
1809                 bmap1->sample = sample;
1810         }
1811
1812         bmap1 = isl_basic_map_simplify(bmap1);
1813         return isl_basic_map_finalize(bmap1);
1814 error:
1815         if (sample)
1816                 isl_vec_free(sample);
1817         isl_basic_map_free(bmap1);
1818         isl_basic_map_free(bmap2);
1819         return NULL;
1820 }
1821
1822 struct isl_basic_set *isl_basic_set_intersect(
1823                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
1824 {
1825         return (struct isl_basic_set *)
1826                 isl_basic_map_intersect(
1827                         (struct isl_basic_map *)bset1,
1828                         (struct isl_basic_map *)bset2);
1829 }
1830
1831 /* Special case of isl_map_intersect, where both map1 and map2
1832  * are convex, without any divs and such that either map1 or map2
1833  * contains a single constraint.  This constraint is then simply
1834  * added to the other map.
1835  */
1836 static __isl_give isl_map *map_intersect_add_constraint(
1837         __isl_take isl_map *map1, __isl_take isl_map *map2)
1838 {
1839         struct isl_basic_map *bmap1;
1840         struct isl_basic_map *bmap2;
1841
1842         isl_assert(map1->ctx, map1->n == 1, goto error);
1843         isl_assert(map2->ctx, map1->n == 1, goto error);
1844         isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
1845         isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);
1846
1847         if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
1848                 return isl_map_intersect(map2, map1);
1849
1850         isl_assert(map2->ctx,
1851                     map2->p[0]->n_eq + map2->p[0]->n_ineq == 1, goto error);
1852
1853         map1 = isl_map_cow(map1);
1854         if (!map1)
1855                 goto error;
1856         map1->p[0] = isl_basic_map_cow(map1->p[0]);
1857         if (map2->p[0]->n_eq == 1)
1858                 map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
1859         else
1860                 map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
1861                                                         map2->p[0]->ineq[0]);
1862
1863         map1->p[0] = isl_basic_map_simplify(map1->p[0]);
1864         map1->p[0] = isl_basic_map_finalize(map1->p[0]);
1865         if (!map1->p[0])
1866                 goto error;
1867
1868         isl_map_free(map2);
1869
1870         return map1;
1871 error:
1872         isl_map_free(map1);
1873         isl_map_free(map2);
1874         return NULL;
1875 }
1876
1877 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
1878 {
1879         unsigned flags = 0;
1880         struct isl_map *result;
1881         int i, j;
1882
1883         if (!map1 || !map2)
1884                 goto error;
1885
1886         if (map1->n == 1 && map2->n == 1 &&
1887             map1->p[0]->n_div == 0 && map2->p[0]->n_div == 0 &&
1888             isl_dim_equal(map1->dim, map2->dim) &&
1889             (map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 ||
1890              map2->p[0]->n_eq + map2->p[0]->n_ineq == 1))
1891                 return map_intersect_add_constraint(map1, map2);
1892         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
1893                                          map2->dim, isl_dim_param), goto error);
1894         if (isl_dim_total(map1->dim) ==
1895                                 isl_dim_size(map1->dim, isl_dim_param) &&
1896             isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1897                 return isl_map_intersect(map2, map1);
1898
1899         if (isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1900                 isl_assert(map1->ctx,
1901                             isl_dim_equal(map1->dim, map2->dim), goto error);
1902
1903         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
1904             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
1905                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
1906
1907         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
1908                                 map1->n * map2->n, flags);
1909         if (!result)
1910                 goto error;
1911         for (i = 0; i < map1->n; ++i)
1912                 for (j = 0; j < map2->n; ++j) {
1913                         struct isl_basic_map *part;
1914                         part = isl_basic_map_intersect(
1915                                     isl_basic_map_copy(map1->p[i]),
1916                                     isl_basic_map_copy(map2->p[j]));
1917                         if (isl_basic_map_is_empty(part))
1918                                 isl_basic_map_free(part);
1919                         else
1920                                 result = isl_map_add(result, part);
1921                         if (!result)
1922                                 goto error;
1923                 }
1924         isl_map_free(map1);
1925         isl_map_free(map2);
1926         return result;
1927 error:
1928         isl_map_free(map1);
1929         isl_map_free(map2);
1930         return NULL;
1931 }
1932
1933 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
1934 {
1935         return (struct isl_set *)
1936                 isl_map_intersect((struct isl_map *)set1,
1937                                   (struct isl_map *)set2);
1938 }
1939
1940 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
1941 {
1942         struct isl_dim *dim;
1943         struct isl_basic_set *bset;
1944         unsigned in;
1945
1946         if (!bmap)
1947                 return NULL;
1948         bmap = isl_basic_map_cow(bmap);
1949         if (!bmap)
1950                 return NULL;
1951         dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
1952         in = isl_basic_map_n_in(bmap);
1953         bset = isl_basic_set_from_basic_map(bmap);
1954         bset = isl_basic_set_swap_vars(bset, in);
1955         return isl_basic_map_from_basic_set(bset, dim);
1956 }
1957
1958 /* Turn final n dimensions into existentially quantified variables.
1959  */
1960 struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
1961                 enum isl_dim_type type, unsigned first, unsigned n)
1962 {
1963         int i;
1964         size_t row_size;
1965         isl_int **new_div;
1966         isl_int *old;
1967
1968         if (!bset)
1969                 return NULL;
1970
1971         isl_assert(bset->ctx, type == isl_dim_set, goto error);
1972         isl_assert(bset->ctx, first + n == isl_basic_set_n_dim(bset), goto error);
1973
1974         if (n == 0)
1975                 return bset;
1976
1977         if (ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL))
1978                 return isl_basic_set_remove(bset, type, first, n);
1979
1980         bset = isl_basic_set_cow(bset);
1981
1982         row_size = 1 + isl_dim_total(bset->dim) + bset->extra;
1983         old = bset->block2.data;
1984         bset->block2 = isl_blk_extend(bset->ctx, bset->block2,
1985                                         (bset->extra + n) * (1 + row_size));
1986         if (!bset->block2.data)
1987                 goto error;
1988         new_div = isl_alloc_array(ctx, isl_int *, bset->extra + n);
1989         if (!new_div)
1990                 goto error;
1991         for (i = 0; i < n; ++i) {
1992                 new_div[i] = bset->block2.data +
1993                                 (bset->extra + i) * (1 + row_size);
1994                 isl_seq_clr(new_div[i], 1 + row_size);
1995         }
1996         for (i = 0; i < bset->extra; ++i)
1997                 new_div[n + i] = bset->block2.data + (bset->div[i] - old);
1998         free(bset->div);
1999         bset->div = new_div;
2000         bset->n_div += n;
2001         bset->extra += n;
2002         bset->dim = isl_dim_drop_outputs(bset->dim,
2003                                             isl_basic_set_n_dim(bset) - n, n);
2004         if (!bset->dim)
2005                 goto error;
2006         bset = isl_basic_set_simplify(bset);
2007         bset = isl_basic_set_drop_redundant_divs(bset);
2008         return isl_basic_set_finalize(bset);
2009 error:
2010         isl_basic_set_free(bset);
2011         return NULL;
2012 }
2013
2014 /* Turn final n dimensions into existentially quantified variables.
2015  */
2016 __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
2017                 enum isl_dim_type type, unsigned first, unsigned n)
2018 {
2019         int i;
2020
2021         if (!set)
2022                 return NULL;
2023
2024         isl_assert(set->ctx, type == isl_dim_set, goto error);
2025         isl_assert(set->ctx, first + n == isl_set_n_dim(set), goto error);
2026
2027         set = isl_set_cow(set);
2028         if (!set)
2029                 goto error;
2030         set->dim = isl_dim_drop_outputs(set->dim, first, n);
2031         for (i = 0; i < set->n; ++i) {
2032                 set->p[i] = isl_basic_set_project_out(set->p[i], type, first, n);
2033                 if (!set->p[i])
2034                         goto error;
2035         }
2036
2037         ISL_F_CLR(set, ISL_SET_NORMALIZED);
2038         return set;
2039 error:
2040         isl_set_free(set);
2041         return NULL;
2042 }
2043
2044 static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2045 {
2046         int i, j;
2047
2048         for (i = 0; i < n; ++i) {
2049                 j = isl_basic_map_alloc_div(bmap);
2050                 if (j < 0)
2051                         goto error;
2052                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2053         }
2054         return bmap;
2055 error:
2056         isl_basic_map_free(bmap);
2057         return NULL;
2058 }
2059
2060 struct isl_basic_map *isl_basic_map_apply_range(
2061                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2062 {
2063         struct isl_dim *dim_result = NULL;
2064         struct isl_basic_map *bmap;
2065         unsigned n_in, n_out, n, nparam, total, pos;
2066         struct isl_dim_map *dim_map1, *dim_map2;
2067
2068         if (!bmap1 || !bmap2)
2069                 goto error;
2070
2071         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2072                                   isl_dim_copy(bmap2->dim));
2073
2074         n_in = isl_basic_map_n_in(bmap1);
2075         n_out = isl_basic_map_n_out(bmap2);
2076         n = isl_basic_map_n_out(bmap1);
2077         nparam = isl_basic_map_n_param(bmap1);
2078
2079         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2080         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2081         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2082         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2083         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2084         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2085         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2086         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2087         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2088         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2089         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2090
2091         bmap = isl_basic_map_alloc_dim(dim_result,
2092                         bmap1->n_div + bmap2->n_div + n,
2093                         bmap1->n_eq + bmap2->n_eq,
2094                         bmap1->n_ineq + bmap2->n_ineq);
2095         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2096         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2097         bmap = add_divs(bmap, n);
2098         bmap = isl_basic_map_simplify(bmap);
2099         bmap = isl_basic_map_drop_redundant_divs(bmap);
2100         return isl_basic_map_finalize(bmap);
2101 error:
2102         isl_basic_map_free(bmap1);
2103         isl_basic_map_free(bmap2);
2104         return NULL;
2105 }
2106
2107 struct isl_basic_set *isl_basic_set_apply(
2108                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2109 {
2110         if (!bset || !bmap)
2111                 goto error;
2112
2113         isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
2114                     goto error);
2115
2116         return (struct isl_basic_set *)
2117                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2118 error:
2119         isl_basic_set_free(bset);
2120         isl_basic_map_free(bmap);
2121         return NULL;
2122 }
2123
2124 struct isl_basic_map *isl_basic_map_apply_domain(
2125                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2126 {
2127         if (!bmap1 || !bmap2)
2128                 goto error;
2129
2130         isl_assert(bmap1->ctx,
2131             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2132         isl_assert(bmap1->ctx,
2133             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2134             goto error);
2135
2136         bmap1 = isl_basic_map_reverse(bmap1);
2137         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2138         return isl_basic_map_reverse(bmap1);
2139 error:
2140         isl_basic_map_free(bmap1);
2141         isl_basic_map_free(bmap2);
2142         return NULL;
2143 }
2144
2145 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
2146  * A \cap B -> f(A) + f(B)
2147  */
2148 struct isl_basic_map *isl_basic_map_sum(
2149                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2150 {
2151         unsigned n_in, n_out, nparam, total, pos;
2152         struct isl_basic_map *bmap = NULL;
2153         struct isl_dim_map *dim_map1, *dim_map2;
2154         int i;
2155
2156         if (!bmap1 || !bmap2)
2157                 goto error;
2158
2159         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
2160                 goto error);
2161
2162         nparam = isl_basic_map_n_param(bmap1);
2163         n_in = isl_basic_map_n_in(bmap1);
2164         n_out = isl_basic_map_n_out(bmap1);
2165
2166         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
2167         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2168         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
2169         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2170         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
2171         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2172         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2173         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
2174         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2175         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2176         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
2177
2178         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
2179                         bmap1->n_div + bmap2->n_div + 2 * n_out,
2180                         bmap1->n_eq + bmap2->n_eq + n_out,
2181                         bmap1->n_ineq + bmap2->n_ineq);
2182         for (i = 0; i < n_out; ++i) {
2183                 int j = isl_basic_map_alloc_equality(bmap);
2184                 if (j < 0)
2185                         goto error;
2186                 isl_seq_clr(bmap->eq[j], 1+total);
2187                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
2188                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
2189                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
2190         }
2191         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2192         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2193         bmap = add_divs(bmap, 2 * n_out);
2194
2195         bmap = isl_basic_map_simplify(bmap);
2196         return isl_basic_map_finalize(bmap);
2197 error:
2198         isl_basic_map_free(bmap);
2199         isl_basic_map_free(bmap1);
2200         isl_basic_map_free(bmap2);
2201         return NULL;
2202 }
2203
2204 /* Given two maps A -> f(A) and B -> g(B), construct a map
2205  * A \cap B -> f(A) + f(B)
2206  */
2207 struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2)
2208 {
2209         struct isl_map *result;
2210         int i, j;
2211
2212         if (!map1 || !map2)
2213                 goto error;
2214
2215         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2216
2217         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2218                                 map1->n * map2->n, 0);
2219         if (!result)
2220                 goto error;
2221         for (i = 0; i < map1->n; ++i)
2222                 for (j = 0; j < map2->n; ++j) {
2223                         struct isl_basic_map *part;
2224                         part = isl_basic_map_sum(
2225                                     isl_basic_map_copy(map1->p[i]),
2226                                     isl_basic_map_copy(map2->p[j]));
2227                         if (isl_basic_map_is_empty(part))
2228                                 isl_basic_map_free(part);
2229                         else
2230                                 result = isl_map_add(result, part);
2231                         if (!result)
2232                                 goto error;
2233                 }
2234         isl_map_free(map1);
2235         isl_map_free(map2);
2236         return result;
2237 error:
2238         isl_map_free(map1);
2239         isl_map_free(map2);
2240         return NULL;
2241 }
2242
2243 /* Given a basic map A -> f(A), construct A -> -f(A).
2244  */
2245 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
2246 {
2247         int i, j;
2248         unsigned off, n;
2249
2250         bmap = isl_basic_map_cow(bmap);
2251         if (!bmap)
2252                 return NULL;
2253
2254         n = isl_basic_map_dim(bmap, isl_dim_out);
2255         off = isl_basic_map_offset(bmap, isl_dim_out);
2256         for (i = 0; i < bmap->n_eq; ++i)
2257                 for (j = 0; j < n; ++j)
2258                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
2259         for (i = 0; i < bmap->n_ineq; ++i)
2260                 for (j = 0; j < n; ++j)
2261                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
2262         for (i = 0; i < bmap->n_div; ++i)
2263                 for (j = 0; j < n; ++j)
2264                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
2265         return isl_basic_map_finalize(bmap);
2266 }
2267
2268 /* Given a map A -> f(A), construct A -> -f(A).
2269  */
2270 struct isl_map *isl_map_neg(struct isl_map *map)
2271 {
2272         int i;
2273
2274         map = isl_map_cow(map);
2275         if (!map)
2276                 return NULL;
2277
2278         for (i = 0; i < map->n; ++i) {
2279                 map->p[i] = isl_basic_map_neg(map->p[i]);
2280                 if (!map->p[i])
2281                         goto error;
2282         }
2283
2284         return map;
2285 error:
2286         isl_map_free(map);
2287         return NULL;
2288 }
2289
2290 /* Given a basic map A -> f(A) and an integer d, construct a basic map
2291  * A -> floor(f(A)/d).
2292  */
2293 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
2294                 isl_int d)
2295 {
2296         unsigned n_in, n_out, nparam, total, pos;
2297         struct isl_basic_map *result = NULL;
2298         struct isl_dim_map *dim_map;
2299         int i;
2300
2301         if (!bmap)
2302                 return NULL;
2303
2304         nparam = isl_basic_map_n_param(bmap);
2305         n_in = isl_basic_map_n_in(bmap);
2306         n_out = isl_basic_map_n_out(bmap);
2307
2308         total = nparam + n_in + n_out + bmap->n_div + n_out;
2309         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2310         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
2311         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
2312         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
2313         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
2314
2315         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
2316                         bmap->n_div + n_out,
2317                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
2318         result = add_constraints_dim_map(result, bmap, dim_map);
2319         result = add_divs(result, n_out);
2320         for (i = 0; i < n_out; ++i) {
2321                 int j;
2322                 j = isl_basic_map_alloc_inequality(result);
2323                 if (j < 0)
2324                         goto error;
2325                 isl_seq_clr(result->ineq[j], 1+total);
2326                 isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
2327                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
2328                 j = isl_basic_map_alloc_inequality(result);
2329                 if (j < 0)
2330                         goto error;
2331                 isl_seq_clr(result->ineq[j], 1+total);
2332                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
2333                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
2334                 isl_int_sub_ui(result->ineq[j][0], d, 1);
2335         }
2336
2337         result = isl_basic_map_simplify(result);
2338         return isl_basic_map_finalize(result);
2339 error:
2340         isl_basic_map_free(result);
2341         return NULL;
2342 }
2343
2344 /* Given a map A -> f(A) and an integer d, construct a map
2345  * A -> floor(f(A)/d).
2346  */
2347 struct isl_map *isl_map_floordiv(struct isl_map *map, isl_int d)
2348 {
2349         int i;
2350
2351         map = isl_map_cow(map);
2352         if (!map)
2353                 return NULL;
2354
2355         ISL_F_CLR(map, ISL_MAP_DISJOINT);
2356         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2357         for (i = 0; i < map->n; ++i) {
2358                 map->p[i] = isl_basic_map_floordiv(map->p[i], d);
2359                 if (!map->p[i])
2360                         goto error;
2361         }
2362
2363         return map;
2364 error:
2365         isl_map_free(map);
2366         return NULL;
2367 }
2368
2369 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
2370 {
2371         int i;
2372         unsigned nparam;
2373         unsigned n_in;
2374
2375         i = isl_basic_map_alloc_equality(bmap);
2376         if (i < 0)
2377                 goto error;
2378         nparam = isl_basic_map_n_param(bmap);
2379         n_in = isl_basic_map_n_in(bmap);
2380         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2381         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2382         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2383         return isl_basic_map_finalize(bmap);
2384 error:
2385         isl_basic_map_free(bmap);
2386         return NULL;
2387 }
2388
2389 /* Add a constraints to "bmap" expressing i_pos < o_pos
2390  */
2391 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2392 {
2393         int i;
2394         unsigned nparam;
2395         unsigned n_in;
2396
2397         i = isl_basic_map_alloc_inequality(bmap);
2398         if (i < 0)
2399                 goto error;
2400         nparam = isl_basic_map_n_param(bmap);
2401         n_in = isl_basic_map_n_in(bmap);
2402         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2403         isl_int_set_si(bmap->ineq[i][0], -1);
2404         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2405         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2406         return isl_basic_map_finalize(bmap);
2407 error:
2408         isl_basic_map_free(bmap);
2409         return NULL;
2410 }
2411
2412 /* Add a constraints to "bmap" expressing i_pos > o_pos
2413  */
2414 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
2415 {
2416         int i;
2417         unsigned nparam;
2418         unsigned n_in;
2419
2420         i = isl_basic_map_alloc_inequality(bmap);
2421         if (i < 0)
2422                 goto error;
2423         nparam = isl_basic_map_n_param(bmap);
2424         n_in = isl_basic_map_n_in(bmap);
2425         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2426         isl_int_set_si(bmap->ineq[i][0], -1);
2427         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2428         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2429         return isl_basic_map_finalize(bmap);
2430 error:
2431         isl_basic_map_free(bmap);
2432         return NULL;
2433 }
2434
2435 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
2436 {
2437         int i;
2438         struct isl_basic_map *bmap;
2439         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
2440         if (!bmap)
2441                 return NULL;
2442         for (i = 0; i < n_equal && bmap; ++i)
2443                 bmap = var_equal(bmap, i);
2444         return isl_basic_map_finalize(bmap);
2445 }
2446
2447 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos < o_pos
2448  */
2449 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
2450 {
2451         int i;
2452         struct isl_basic_map *bmap;
2453         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2454         if (!bmap)
2455                 return NULL;
2456         for (i = 0; i < pos && bmap; ++i)
2457                 bmap = var_equal(bmap, i);
2458         if (bmap)
2459                 bmap = var_less(bmap, pos);
2460         return isl_basic_map_finalize(bmap);
2461 }
2462
2463 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
2464  */
2465 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
2466 {
2467         int i;
2468         struct isl_basic_map *bmap;
2469         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2470         if (!bmap)
2471                 return NULL;
2472         for (i = 0; i < pos && bmap; ++i)
2473                 bmap = var_equal(bmap, i);
2474         if (bmap)
2475                 bmap = var_more(bmap, pos);
2476         return isl_basic_map_finalize(bmap);
2477 }
2478
2479 static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
2480 {
2481         struct isl_map *map;
2482         unsigned dim;
2483         int i;
2484
2485         if (!dims)
2486                 return NULL;
2487         dim = dims->n_out;
2488         map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT);
2489
2490         for (i = 0; i < dim; ++i)
2491                 map = isl_map_add(map,
2492                                   isl_basic_map_less_at(isl_dim_copy(dims), i));
2493         if (equal)
2494                 map = isl_map_add(map,
2495                                   isl_basic_map_equal(isl_dim_copy(dims), dim));
2496
2497         isl_dim_free(dims);
2498         return map;
2499 }
2500
2501 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
2502 {
2503         return map_lex_lte(isl_dim_map(set_dim), 0);
2504 }
2505
2506 __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
2507 {
2508         return map_lex_lte(isl_dim_map(set_dim), 1);
2509 }
2510
2511 static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
2512 {
2513         struct isl_map *map;
2514         unsigned dim;
2515         int i;
2516
2517         if (!dims)
2518                 return NULL;
2519         dim = dims->n_out;
2520         map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT);
2521
2522         for (i = 0; i < dim; ++i)
2523                 map = isl_map_add(map,
2524                                   isl_basic_map_more_at(isl_dim_copy(dims), i));
2525         if (equal)
2526                 map = isl_map_add(map,
2527                                   isl_basic_map_equal(isl_dim_copy(dims), dim));
2528
2529         isl_dim_free(dims);
2530         return map;
2531 }
2532
2533 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
2534 {
2535         return map_lex_gte(isl_dim_map(set_dim), 0);
2536 }
2537
2538 __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim)
2539 {
2540         return map_lex_gte(isl_dim_map(set_dim), 1);
2541 }
2542
2543 struct isl_basic_map *isl_basic_map_from_basic_set(
2544                 struct isl_basic_set *bset, struct isl_dim *dim)
2545 {
2546         struct isl_basic_map *bmap;
2547
2548         bset = isl_basic_set_cow(bset);
2549         if (!bset || !dim)
2550                 goto error;
2551
2552         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
2553         isl_dim_free(bset->dim);
2554         bmap = (struct isl_basic_map *) bset;
2555         bmap->dim = dim;
2556         return isl_basic_map_finalize(bmap);
2557 error:
2558         isl_basic_set_free(bset);
2559         isl_dim_free(dim);
2560         return NULL;
2561 }
2562
2563 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
2564 {
2565         if (!bmap)
2566                 goto error;
2567         if (bmap->dim->n_in == 0)
2568                 return (struct isl_basic_set *)bmap;
2569         bmap = isl_basic_map_cow(bmap);
2570         if (!bmap)
2571                 goto error;
2572         bmap->dim = isl_dim_cow(bmap->dim);
2573         if (!bmap->dim)
2574                 goto error;
2575         bmap->dim->n_out += bmap->dim->n_in;
2576         bmap->dim->n_in = 0;
2577         bmap = isl_basic_map_finalize(bmap);
2578         return (struct isl_basic_set *)bmap;
2579 error:
2580         isl_basic_map_free(bmap);
2581         return NULL;
2582 }
2583
2584 /* For a div d = floor(f/m), add the constraints
2585  *
2586  *              f - m d >= 0
2587  *              -(f-(n-1)) + m d >= 0
2588  *
2589  * Note that the second constraint is the negation of
2590  *
2591  *              f - m d >= n
2592  */
2593 int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
2594 {
2595         int i, j;
2596         unsigned total = isl_basic_map_total_dim(bmap);
2597         unsigned div_pos = 1 + total - bmap->n_div + div;
2598
2599         i = isl_basic_map_alloc_inequality(bmap);
2600         if (i < 0)
2601                 return -1;
2602         isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total);
2603         isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]);
2604
2605         j = isl_basic_map_alloc_inequality(bmap);
2606         if (j < 0)
2607                 return -1;
2608         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
2609         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]);
2610         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
2611         return j;
2612 }
2613
2614 struct isl_basic_set *isl_basic_map_underlying_set(
2615                 struct isl_basic_map *bmap)
2616 {
2617         if (!bmap)
2618                 goto error;
2619         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
2620                 return (struct isl_basic_set *)bmap;
2621         bmap = isl_basic_map_cow(bmap);
2622         if (!bmap)
2623                 goto error;
2624         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
2625         if (!bmap->dim)
2626                 goto error;
2627         bmap->extra -= bmap->n_div;
2628         bmap->n_div = 0;
2629         bmap = isl_basic_map_finalize(bmap);
2630         return (struct isl_basic_set *)bmap;
2631 error:
2632         return NULL;
2633 }
2634
2635 __isl_give isl_basic_set *isl_basic_set_underlying_set(
2636                 __isl_take isl_basic_set *bset)
2637 {
2638         return isl_basic_map_underlying_set((isl_basic_map *)bset);
2639 }
2640
2641 struct isl_basic_map *isl_basic_map_overlying_set(
2642         struct isl_basic_set *bset, struct isl_basic_map *like)
2643 {
2644         struct isl_basic_map *bmap;
2645         struct isl_ctx *ctx;
2646         unsigned total;
2647         int i;
2648
2649         if (!bset || !like)
2650                 goto error;
2651         ctx = bset->ctx;
2652         isl_assert(ctx, bset->n_div == 0, goto error);
2653         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
2654         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
2655                         goto error);
2656         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
2657                 isl_basic_map_free(like);
2658                 return (struct isl_basic_map *)bset;
2659         }
2660         bset = isl_basic_set_cow(bset);
2661         if (!bset)
2662                 goto error;
2663         total = bset->dim->n_out + bset->extra;
2664         bmap = (struct isl_basic_map *)bset;
2665         isl_dim_free(bmap->dim);
2666         bmap->dim = isl_dim_copy(like->dim);
2667         if (!bmap->dim)
2668                 goto error;
2669         bmap->n_div = like->n_div;
2670         bmap->extra += like->n_div;
2671         if (bmap->extra) {
2672                 unsigned ltotal;
2673                 ltotal = total - bmap->extra + like->extra;
2674                 if (ltotal > total)
2675                         ltotal = total;
2676                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
2677                                         bmap->extra * (1 + 1 + total));
2678                 if (isl_blk_is_error(bmap->block2))
2679                         goto error;
2680                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
2681                                                 bmap->extra);
2682                 if (!bmap->div)
2683                         goto error;
2684                 for (i = 0; i < bmap->extra; ++i)
2685                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
2686                 for (i = 0; i < like->n_div; ++i) {
2687                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
2688                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
2689                 }
2690                 bmap = isl_basic_map_extend_constraints(bmap,
2691                                                         0, 2 * like->n_div);
2692                 for (i = 0; i < like->n_div; ++i) {
2693                         if (isl_int_is_zero(bmap->div[i][0]))
2694                                 continue;
2695                         if (isl_basic_map_add_div_constraints(bmap, i) < 0)
2696                                 goto error;
2697                 }
2698         }
2699         isl_basic_map_free(like);
2700         bmap = isl_basic_map_simplify(bmap);
2701         bmap = isl_basic_map_finalize(bmap);
2702         return bmap;
2703 error:
2704         isl_basic_map_free(like);
2705         isl_basic_set_free(bset);
2706         return NULL;
2707 }
2708
2709 struct isl_basic_set *isl_basic_set_from_underlying_set(
2710         struct isl_basic_set *bset, struct isl_basic_set *like)
2711 {
2712         return (struct isl_basic_set *)
2713                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
2714 }
2715
2716 struct isl_set *isl_set_from_underlying_set(
2717         struct isl_set *set, struct isl_basic_set *like)
2718 {
2719         int i;
2720
2721         if (!set || !like)
2722                 goto error;
2723         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
2724                     goto error);
2725         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
2726                 isl_basic_set_free(like);
2727                 return set;
2728         }
2729         set = isl_set_cow(set);
2730         if (!set)
2731                 goto error;
2732         for (i = 0; i < set->n; ++i) {
2733                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
2734                                                       isl_basic_set_copy(like));
2735                 if (!set->p[i])
2736                         goto error;
2737         }
2738         isl_dim_free(set->dim);
2739         set->dim = isl_dim_copy(like->dim);
2740         if (!set->dim)
2741                 goto error;
2742         isl_basic_set_free(like);
2743         return set;
2744 error:
2745         isl_basic_set_free(like);
2746         isl_set_free(set);
2747         return NULL;
2748 }
2749
2750 struct isl_set *isl_map_underlying_set(struct isl_map *map)
2751 {
2752         int i;
2753
2754         map = isl_map_cow(map);
2755         if (!map)
2756                 return NULL;
2757         map->dim = isl_dim_cow(map->dim);
2758         if (!map->dim)
2759                 goto error;
2760
2761         for (i = 1; i < map->n; ++i)
2762                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
2763                                 goto error);
2764         for (i = 0; i < map->n; ++i) {
2765                 map->p[i] = (struct isl_basic_map *)
2766                                 isl_basic_map_underlying_set(map->p[i]);
2767                 if (!map->p[i])
2768                         goto error;
2769         }
2770         if (map->n == 0)
2771                 map->dim = isl_dim_underlying(map->dim, 0);
2772         else {
2773                 isl_dim_free(map->dim);
2774                 map->dim = isl_dim_copy(map->p[0]->dim);
2775         }
2776         if (!map->dim)
2777                 goto error;
2778         return (struct isl_set *)map;
2779 error:
2780         isl_map_free(map);
2781         return NULL;
2782 }
2783
2784 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
2785 {
2786         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
2787 }
2788
2789 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
2790 {
2791         struct isl_basic_set *domain;
2792         unsigned n_in;
2793         unsigned n_out;
2794         if (!bmap)
2795                 return NULL;
2796         n_in = isl_basic_map_n_in(bmap);
2797         n_out = isl_basic_map_n_out(bmap);
2798         domain = isl_basic_set_from_basic_map(bmap);
2799         return isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
2800 }
2801
2802 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
2803 {
2804         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
2805 }
2806
2807 struct isl_set *isl_map_range(struct isl_map *map)
2808 {
2809         int i;
2810         struct isl_set *set;
2811
2812         if (!map)
2813                 goto error;
2814         map = isl_map_cow(map);
2815         if (!map)
2816                 goto error;
2817
2818         set = (struct isl_set *) map;
2819         if (set->dim->n_in != 0) {
2820                 set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
2821                 if (!set->dim)
2822                         goto error;
2823         }
2824         for (i = 0; i < map->n; ++i) {
2825                 set->p[i] = isl_basic_map_range(map->p[i]);
2826                 if (!set->p[i])
2827                         goto error;
2828         }
2829         ISL_F_CLR(set, ISL_MAP_DISJOINT);
2830         ISL_F_CLR(set, ISL_SET_NORMALIZED);
2831         return set;
2832 error:
2833         isl_map_free(map);
2834         return NULL;
2835 }
2836
2837 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
2838 {
2839         int i;
2840         struct isl_map *map = NULL;
2841
2842         set = isl_set_cow(set);
2843         if (!set || !dim)
2844                 goto error;
2845         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
2846         map = (struct isl_map *)set;
2847         for (i = 0; i < set->n; ++i) {
2848                 map->p[i] = isl_basic_map_from_basic_set(
2849                                 set->p[i], isl_dim_copy(dim));
2850                 if (!map->p[i])
2851                         goto error;
2852         }
2853         isl_dim_free(map->dim);
2854         map->dim = dim;
2855         return map;
2856 error:
2857         isl_dim_free(dim);
2858         isl_set_free(set);
2859         return NULL;
2860 }
2861
2862 struct isl_map *isl_map_from_range(struct isl_set *set)
2863 {
2864         return (struct isl_map *)set;
2865 }
2866
2867 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
2868 {
2869         return isl_map_reverse(isl_map_from_range(set));;
2870 }
2871
2872 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
2873         __isl_take isl_set *range)
2874 {
2875         return isl_map_product(isl_map_from_domain(domain),
2876                                isl_map_from_range(range));
2877 }
2878
2879 struct isl_set *isl_set_from_map(struct isl_map *map)
2880 {
2881         int i;
2882         struct isl_set *set = NULL;
2883
2884         if (!map)
2885                 return NULL;
2886         map = isl_map_cow(map);
2887         if (!map)
2888                 return NULL;
2889         map->dim = isl_dim_cow(map->dim);
2890         if (!map->dim)
2891                 goto error;
2892         map->dim->n_out += map->dim->n_in;
2893         map->dim->n_in = 0;
2894         set = (struct isl_set *)map;
2895         for (i = 0; i < map->n; ++i) {
2896                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
2897                 if (!set->p[i])
2898                         goto error;
2899         }
2900         return set;
2901 error:
2902         isl_map_free(map);
2903         return NULL;
2904 }
2905
2906 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
2907 {
2908         struct isl_map *map;
2909
2910         if (!dim)
2911                 return NULL;
2912         isl_assert(dim->ctx, n >= 0, return NULL);
2913         map = isl_alloc(dim->ctx, struct isl_map,
2914                         sizeof(struct isl_map) +
2915                         (n - 1) * sizeof(struct isl_basic_map *));
2916         if (!map)
2917                 goto error;
2918
2919         map->ctx = dim->ctx;
2920         isl_ctx_ref(map->ctx);
2921         map->ref = 1;
2922         map->size = n;
2923         map->n = 0;
2924         map->dim = dim;
2925         map->flags = flags;
2926         return map;
2927 error:
2928         isl_dim_free(dim);
2929         return NULL;
2930 }
2931
2932 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
2933                 unsigned nparam, unsigned in, unsigned out, int n,
2934                 unsigned flags)
2935 {
2936         struct isl_map *map;
2937         struct isl_dim *dims;
2938
2939         dims = isl_dim_alloc(ctx, nparam, in, out);
2940         if (!dims)
2941                 return NULL;
2942
2943         map = isl_map_alloc_dim(dims, n, flags);
2944         return map;
2945 }
2946
2947 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
2948 {
2949         struct isl_basic_map *bmap;
2950         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
2951         bmap = isl_basic_map_set_to_empty(bmap);
2952         return bmap;
2953 }
2954
2955 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
2956 {
2957         struct isl_basic_set *bset;
2958         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
2959         bset = isl_basic_set_set_to_empty(bset);
2960         return bset;
2961 }
2962
2963 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
2964 {
2965         struct isl_basic_map *bmap;
2966         if (!model)
2967                 return NULL;
2968         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
2969         bmap = isl_basic_map_set_to_empty(bmap);
2970         return bmap;
2971 }
2972
2973 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
2974 {
2975         struct isl_basic_map *bmap;
2976         if (!model)
2977                 return NULL;
2978         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
2979         bmap = isl_basic_map_set_to_empty(bmap);
2980         return bmap;
2981 }
2982
2983 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
2984 {
2985         struct isl_basic_set *bset;
2986         if (!model)
2987                 return NULL;
2988         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
2989         bset = isl_basic_set_set_to_empty(bset);
2990         return bset;
2991 }
2992
2993 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
2994 {
2995         struct isl_basic_map *bmap;
2996         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
2997         return bmap;
2998 }
2999
3000 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3001 {
3002         struct isl_basic_set *bset;
3003         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3004         return bset;
3005 }
3006
3007 __isl_give isl_basic_map *isl_basic_map_universe_like(
3008                 __isl_keep isl_basic_map *model)
3009 {
3010         if (!model)
3011                 return NULL;
3012         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3013 }
3014
3015 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3016 {
3017         if (!model)
3018                 return NULL;
3019         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3020 }
3021
3022 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3023         __isl_keep isl_set *model)
3024 {
3025         if (!model)
3026                 return NULL;
3027         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3028 }
3029
3030 struct isl_map *isl_map_empty(struct isl_dim *dim)
3031 {
3032         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3033 }
3034
3035 struct isl_map *isl_map_empty_like(struct isl_map *model)
3036 {
3037         if (!model)
3038                 return NULL;
3039         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3040 }
3041
3042 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3043 {
3044         if (!model)
3045                 return NULL;
3046         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3047 }
3048
3049 struct isl_set *isl_set_empty(struct isl_dim *dim)
3050 {
3051         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3052 }
3053
3054 struct isl_set *isl_set_empty_like(struct isl_set *model)
3055 {
3056         if (!model)
3057                 return NULL;
3058         return isl_set_empty(isl_dim_copy(model->dim));
3059 }
3060
3061 struct isl_map *isl_map_universe(struct isl_dim *dim)
3062 {
3063         struct isl_map *map;
3064         if (!dim)
3065                 return NULL;
3066         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3067         map = isl_map_add(map, isl_basic_map_universe(dim));
3068         return map;
3069 }
3070
3071 struct isl_set *isl_set_universe(struct isl_dim *dim)
3072 {
3073         struct isl_set *set;
3074         if (!dim)
3075                 return NULL;
3076         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3077         set = isl_set_add(set, isl_basic_set_universe(dim));
3078         return set;
3079 }
3080
3081 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3082 {
3083         if (!model)
3084                 return NULL;
3085         return isl_set_universe(isl_dim_copy(model->dim));
3086 }
3087
3088 struct isl_map *isl_map_dup(struct isl_map *map)
3089 {
3090         int i;
3091         struct isl_map *dup;
3092
3093         if (!map)
3094                 return NULL;
3095         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3096         for (i = 0; i < map->n; ++i)
3097                 dup = isl_map_add(dup, isl_basic_map_copy(map->p[i]));
3098         return dup;
3099 }
3100
3101 struct isl_map *isl_map_add(struct isl_map *map, struct isl_basic_map *bmap)
3102 {
3103         if (!bmap || !map)
3104                 goto error;
3105         if (isl_basic_map_fast_is_empty(bmap)) {
3106                 isl_basic_map_free(bmap);
3107                 return map;
3108         }
3109         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3110         isl_assert(map->ctx, map->n < map->size, goto error);
3111         map->p[map->n] = bmap;
3112         map->n++;
3113         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3114         return map;
3115 error:
3116         if (map)
3117                 isl_map_free(map);
3118         if (bmap)
3119                 isl_basic_map_free(bmap);
3120         return NULL;
3121 }
3122
3123 void isl_map_free(struct isl_map *map)
3124 {
3125         int i;
3126
3127         if (!map)
3128                 return;
3129
3130         if (--map->ref > 0)
3131                 return;
3132
3133         isl_ctx_deref(map->ctx);
3134         for (i = 0; i < map->n; ++i)
3135                 isl_basic_map_free(map->p[i]);
3136         isl_dim_free(map->dim);
3137         free(map);
3138 }
3139
3140 struct isl_map *isl_map_extend(struct isl_map *base,
3141                 unsigned nparam, unsigned n_in, unsigned n_out)
3142 {
3143         int i;
3144
3145         base = isl_map_cow(base);
3146         if (!base)
3147                 return NULL;
3148
3149         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3150         if (!base->dim)
3151                 goto error;
3152         for (i = 0; i < base->n; ++i) {
3153                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3154                                 isl_dim_copy(base->dim), 0, 0, 0);
3155                 if (!base->p[i])
3156                         goto error;
3157         }
3158         return base;
3159 error:
3160         isl_map_free(base);
3161         return NULL;
3162 }
3163
3164 struct isl_set *isl_set_extend(struct isl_set *base,
3165                 unsigned nparam, unsigned dim)
3166 {
3167         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3168                                                         nparam, 0, dim);
3169 }
3170
3171 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3172         struct isl_basic_map *bmap, unsigned pos, int value)
3173 {
3174         int j;
3175
3176         bmap = isl_basic_map_cow(bmap);
3177         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3178         j = isl_basic_map_alloc_equality(bmap);
3179         if (j < 0)
3180                 goto error;
3181         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3182         isl_int_set_si(bmap->eq[j][pos], -1);
3183         isl_int_set_si(bmap->eq[j][0], value);
3184         bmap = isl_basic_map_simplify(bmap);
3185         return isl_basic_map_finalize(bmap);
3186 error:
3187         isl_basic_map_free(bmap);
3188         return NULL;
3189 }
3190
3191 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3192         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3193 {
3194         int j;
3195
3196         bmap = isl_basic_map_cow(bmap);
3197         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3198         j = isl_basic_map_alloc_equality(bmap);
3199         if (j < 0)
3200                 goto error;
3201         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3202         isl_int_set_si(bmap->eq[j][pos], -1);
3203         isl_int_set(bmap->eq[j][0], value);
3204         bmap = isl_basic_map_simplify(bmap);
3205         return isl_basic_map_finalize(bmap);
3206 error:
3207         isl_basic_map_free(bmap);
3208         return NULL;
3209 }
3210
3211 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3212                 enum isl_dim_type type, unsigned pos, int value)
3213 {
3214         if (!bmap)
3215                 return NULL;
3216         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3217         return isl_basic_map_fix_pos_si(bmap,
3218                 isl_basic_map_offset(bmap, type) + pos, value);
3219 error:
3220         isl_basic_map_free(bmap);
3221         return NULL;
3222 }
3223
3224 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3225                 enum isl_dim_type type, unsigned pos, isl_int value)
3226 {
3227         if (!bmap)
3228                 return NULL;
3229         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3230         return isl_basic_map_fix_pos(bmap,
3231                 isl_basic_map_offset(bmap, type) + pos, value);
3232 error:
3233         isl_basic_map_free(bmap);
3234         return NULL;
3235 }
3236
3237 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3238                 enum isl_dim_type type, unsigned pos, int value)
3239 {
3240         return (struct isl_basic_set *)
3241                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3242                                         type, pos, value);
3243 }
3244
3245 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3246                 enum isl_dim_type type, unsigned pos, isl_int value)
3247 {
3248         return (struct isl_basic_set *)
3249                 isl_basic_map_fix((struct isl_basic_map *)bset,
3250                                         type, pos, value);
3251 }
3252
3253 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3254                 unsigned input, int value)
3255 {
3256         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3257 }
3258
3259 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3260                 unsigned dim, int value)
3261 {
3262         return (struct isl_basic_set *)
3263                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3264                                         isl_dim_set, dim, value);
3265 }
3266
3267 struct isl_map *isl_map_fix_si(struct isl_map *map,
3268                 enum isl_dim_type type, unsigned pos, int value)
3269 {
3270         int i;
3271
3272         map = isl_map_cow(map);
3273         if (!map)
3274                 return NULL;
3275
3276         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3277         for (i = 0; i < map->n; ++i) {
3278                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
3279                 if (!map->p[i])
3280                         goto error;
3281         }
3282         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3283         return map;
3284 error:
3285         isl_map_free(map);
3286         return NULL;
3287 }
3288
3289 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
3290                 enum isl_dim_type type, unsigned pos, isl_int value)
3291 {
3292         int i;
3293
3294         map = isl_map_cow(map);
3295         if (!map)
3296                 return NULL;
3297
3298         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3299         for (i = 0; i < map->n; ++i) {
3300                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
3301                 if (!map->p[i])
3302                         goto error;
3303         }
3304         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3305         return map;
3306 error:
3307         isl_map_free(map);
3308         return NULL;
3309 }
3310
3311 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
3312                 enum isl_dim_type type, unsigned pos, isl_int value)
3313 {
3314         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
3315 }
3316
3317 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3318                 unsigned input, int value)
3319 {
3320         return isl_map_fix_si(map, isl_dim_in, input, value);
3321 }
3322
3323 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3324 {
3325         return (struct isl_set *)
3326                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
3327 }
3328
3329 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3330         unsigned dim, isl_int value)
3331 {
3332         int j;
3333
3334         bset = isl_basic_set_cow(bset);
3335         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3336         j = isl_basic_set_alloc_inequality(bset);
3337         if (j < 0)
3338                 goto error;
3339         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3340         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3341         isl_int_neg(bset->ineq[j][0], value);
3342         bset = isl_basic_set_simplify(bset);
3343         return isl_basic_set_finalize(bset);
3344 error:
3345         isl_basic_set_free(bset);
3346         return NULL;
3347 }
3348
3349 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3350                                         isl_int value)
3351 {
3352         int i;
3353
3354         set = isl_set_cow(set);
3355         if (!set)
3356                 return NULL;
3357
3358         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3359         for (i = 0; i < set->n; ++i) {
3360                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3361                 if (!set->p[i])
3362                         goto error;
3363         }
3364         return set;
3365 error:
3366         isl_set_free(set);
3367         return NULL;
3368 }
3369
3370 struct isl_map *isl_map_reverse(struct isl_map *map)
3371 {
3372         int i;
3373
3374         map = isl_map_cow(map);
3375         if (!map)
3376                 return NULL;
3377
3378         map->dim = isl_dim_reverse(map->dim);
3379         if (!map->dim)
3380                 goto error;
3381         for (i = 0; i < map->n; ++i) {
3382                 map->p[i] = isl_basic_map_reverse(map->p[i]);
3383                 if (!map->p[i])
3384                         goto error;
3385         }
3386         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3387         return map;
3388 error:
3389         isl_map_free(map);
3390         return NULL;
3391 }
3392
3393 static struct isl_map *isl_basic_map_partial_lexopt(
3394                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3395                 struct isl_set **empty, int max)
3396 {
3397         if (!bmap)
3398                 goto error;
3399         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
3400                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
3401         else
3402                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
3403 error:
3404         isl_basic_map_free(bmap);
3405         isl_basic_set_free(dom);
3406         if (empty)
3407                 *empty = NULL;
3408         return NULL;
3409 }
3410
3411 struct isl_map *isl_basic_map_partial_lexmax(
3412                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3413                 struct isl_set **empty)
3414 {
3415         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
3416 }
3417
3418 struct isl_map *isl_basic_map_partial_lexmin(
3419                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3420                 struct isl_set **empty)
3421 {
3422         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
3423 }
3424
3425 struct isl_set *isl_basic_set_partial_lexmin(
3426                 struct isl_basic_set *bset, struct isl_basic_set *dom,
3427                 struct isl_set **empty)
3428 {
3429         return (struct isl_set *)
3430                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
3431                         dom, empty);
3432 }
3433
3434 struct isl_set *isl_basic_set_partial_lexmax(
3435                 struct isl_basic_set *bset, struct isl_basic_set *dom,
3436                 struct isl_set **empty)
3437 {
3438         return (struct isl_set *)
3439                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
3440                         dom, empty);
3441 }
3442
3443 /* Given a basic map "bmap", compute the lexicograhically minimal
3444  * (or maximal) image element for each domain element in dom.
3445  * Set *empty to those elements in dom that do not have an image element.
3446  *
3447  * We first make sure the basic sets in dom are disjoint and then
3448  * simply collect the results over each of the basic sets separately.
3449  * We could probably improve the efficiency a bit by moving the union
3450  * domain down into the parametric integer programming.
3451  */
3452 static __isl_give isl_map *basic_map_partial_lexopt(
3453                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
3454                 __isl_give isl_set **empty, int max)
3455 {
3456         int i;
3457         struct isl_map *res;
3458
3459         dom = isl_set_make_disjoint(dom);
3460         if (!dom)
3461                 goto error;
3462
3463         if (isl_set_fast_is_empty(dom)) {
3464                 res = isl_map_empty_like_basic_map(bmap);
3465                 *empty = isl_set_empty_like(dom);
3466                 isl_set_free(dom);
3467                 isl_basic_map_free(bmap);
3468                 return res;
3469         }
3470
3471         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
3472                         isl_basic_set_copy(dom->p[0]), empty, max);
3473
3474         for (i = 1; i < dom->n; ++i) {
3475                 struct isl_map *res_i;
3476                 struct isl_set *empty_i;
3477
3478                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
3479                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
3480
3481                 res = isl_map_union_disjoint(res, res_i);
3482                 *empty = isl_set_union_disjoint(*empty, empty_i);
3483         }
3484
3485         isl_set_free(dom);
3486         isl_basic_map_free(bmap);
3487         return res;
3488 error:
3489         *empty = NULL;
3490         isl_set_free(dom);
3491         isl_basic_map_free(bmap);
3492         return NULL;
3493 }
3494
3495 /* Given a map "map", compute the lexicograhically minimal
3496  * (or maximal) image element for each domain element in dom.
3497  * Set *empty to those elements in dom that do not have an image element.
3498  *
3499  * We first compute the lexicographically minimal or maximal element
3500  * in the first basic map.  This results in a partial solution "res"
3501  * and a subset "todo" of dom that still need to be handled.
3502  * We then consider each of the remaining maps in "map" and successively
3503  * improve both "res" and "todo".
3504  *
3505  * Let res^k and todo^k be the results after k steps and let i = k + 1.
3506  * Assume we are computing the lexicographical maximum.
3507  * We first intersect basic map i with a relation that maps elements
3508  * to elements that are lexicographically larger than the image elements
3509  * in res^k and the compute the maximum image element of this intersection.
3510  * The result ("better") corresponds to those image elements in basic map i
3511  * that are better than what we had before.  The remainder ("keep") are the
3512  * domain elements for which the image element in res_k was better.
3513  * We also compute the lexicographical maximum of basic map i in todo^k.
3514  * res^i is the result of the operation + better + those elements in
3515  *              res^k that we should keep
3516  * todo^i is the remainder of the maximum operation on todo^k.
3517  */
3518 static __isl_give isl_map *isl_map_partial_lexopt(
3519                 __isl_take isl_map *map, __isl_take isl_set *dom,
3520                 __isl_give isl_set **empty, int max)
3521 {
3522         int i;
3523         struct isl_map *res;
3524         struct isl_set *todo;
3525
3526         if (!map || !dom)
3527                 goto error;
3528
3529         if (isl_map_fast_is_empty(map)) {
3530                 if (empty)
3531                         *empty = dom;
3532                 else
3533                         isl_set_free(dom);
3534                 return map;
3535         }
3536
3537         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
3538                                         isl_set_copy(dom), &todo, max);
3539
3540         for (i = 1; i < map->n; ++i) {
3541                 struct isl_map *lt;
3542                 struct isl_map *better;
3543                 struct isl_set *keep;
3544                 struct isl_map *res_i;
3545                 struct isl_set *todo_i;
3546                 struct isl_dim *dim = isl_map_get_dim(res);
3547
3548                 dim = isl_dim_range(dim);
3549                 if (max)
3550                         lt = isl_map_lex_lt(dim);
3551                 else
3552                         lt = isl_map_lex_gt(dim);
3553                 lt = isl_map_apply_range(isl_map_copy(res), lt);
3554                 lt = isl_map_intersect(lt,
3555                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
3556                 better = isl_map_partial_lexopt(lt,
3557                         isl_map_domain(isl_map_copy(res)),
3558                         &keep, max);
3559
3560                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
3561                                                 todo, &todo_i, max);
3562
3563                 res = isl_map_intersect_domain(res, keep);
3564                 res = isl_map_union_disjoint(res, res_i);
3565                 res = isl_map_union_disjoint(res, better);
3566                 todo = todo_i;
3567         }
3568
3569         isl_set_free(dom);
3570         isl_map_free(map);
3571
3572         if (empty)
3573                 *empty = todo;
3574         else
3575                 isl_set_free(todo);
3576
3577         return res;
3578 error:
3579         if (empty)
3580                 *empty = NULL;
3581         isl_set_free(dom);
3582         isl_map_free(map);
3583         return NULL;
3584 }
3585
3586 __isl_give isl_map *isl_map_partial_lexmax(
3587                 __isl_take isl_map *map, __isl_take isl_set *dom,
3588                 __isl_give isl_set **empty)
3589 {
3590         return isl_map_partial_lexopt(map, dom, empty, 1);
3591 }
3592
3593 __isl_give isl_map *isl_map_partial_lexmin(
3594                 __isl_take isl_map *map, __isl_take isl_set *dom,
3595                 __isl_give isl_set **empty)
3596 {
3597         return isl_map_partial_lexopt(map, dom, empty, 0);
3598 }
3599
3600 __isl_give isl_set *isl_set_partial_lexmin(
3601                 __isl_take isl_set *set, __isl_take isl_set *dom,
3602                 __isl_give isl_set **empty)
3603 {
3604         return (struct isl_set *)
3605                 isl_map_partial_lexmin((struct isl_map *)set,
3606                         dom, empty);
3607 }
3608
3609 __isl_give isl_set *isl_set_partial_lexmax(
3610                 __isl_take isl_set *set, __isl_take isl_set *dom,
3611                 __isl_give isl_set **empty)
3612 {
3613         return (struct isl_set *)
3614                 isl_map_partial_lexmax((struct isl_map *)set,
3615                         dom, empty);
3616 }
3617
3618 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
3619 {
3620         struct isl_basic_set *dom = NULL;
3621         struct isl_dim *dom_dim;
3622
3623         if (!bmap)
3624                 goto error;
3625         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
3626         dom = isl_basic_set_universe(dom_dim);
3627         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
3628 error:
3629         isl_basic_map_free(bmap);
3630         return NULL;
3631 }
3632
3633 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
3634 {
3635         return isl_basic_map_lexopt(bmap, 0);
3636 }
3637
3638 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
3639 {
3640         return isl_basic_map_lexopt(bmap, 1);
3641 }
3642
3643 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
3644 {
3645         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
3646 }
3647
3648 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
3649 {
3650         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
3651 }
3652
3653 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
3654 {
3655         struct isl_set *dom = NULL;
3656         struct isl_dim *dom_dim;
3657
3658         if (!map)
3659                 goto error;
3660         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
3661         dom = isl_set_universe(dom_dim);
3662         return isl_map_partial_lexopt(map, dom, NULL, max);
3663 error:
3664         isl_map_free(map);
3665         return NULL;
3666 }
3667
3668 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
3669 {
3670         return isl_map_lexopt(map, 0);
3671 }
3672
3673 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
3674 {
3675         return isl_map_lexopt(map, 1);
3676 }
3677
3678 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
3679 {
3680         return (isl_set *)isl_map_lexmin((isl_map *)set);
3681 }
3682
3683 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
3684 {
3685         return (isl_set *)isl_map_lexmax((isl_map *)set);
3686 }
3687
3688 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
3689         struct isl_dim *dim)
3690 {
3691         int i;
3692
3693         if (!map || !dim)
3694                 goto error;
3695
3696         for (i = 0; i < map->n; ++i) {
3697                 isl_dim_free(map->p[i]->dim);
3698                 map->p[i]->dim = isl_dim_copy(dim);
3699         }
3700         isl_dim_free(map->dim);
3701         map->dim = dim;
3702
3703         return map;
3704 error:
3705         isl_map_free(map);
3706         isl_dim_free(dim);
3707         return NULL;
3708 }
3709
3710 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
3711         struct isl_dim *dim)
3712 {
3713         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
3714 }
3715
3716 /* Apply a preimage specified by "mat" on the parameters of "bset".
3717  * bset is assumed to have only parameters and divs.
3718  */
3719 static struct isl_basic_set *basic_set_parameter_preimage(
3720         struct isl_basic_set *bset, struct isl_mat *mat)
3721 {
3722         unsigned nparam;
3723
3724         if (!bset || !mat)
3725                 goto error;
3726
3727         bset->dim = isl_dim_cow(bset->dim);
3728         if (!bset->dim)
3729                 goto error;
3730
3731         nparam = isl_basic_set_dim(bset, isl_dim_param);
3732
3733         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
3734
3735         bset->dim->nparam = 0;
3736         bset->dim->n_out = nparam;
3737         bset = isl_basic_set_preimage(bset, mat);
3738         if (bset) {
3739                 bset->dim->nparam = bset->dim->n_out;
3740                 bset->dim->n_out = 0;
3741         }
3742         return bset;
3743 error:
3744         isl_mat_free(mat);
3745         isl_basic_set_free(bset);
3746         return NULL;
3747 }
3748
3749 /* Apply a preimage specified by "mat" on the parameters of "set".
3750  * set is assumed to have only parameters and divs.
3751  */
3752 static struct isl_set *set_parameter_preimage(
3753         struct isl_set *set, struct isl_mat *mat)
3754 {
3755         struct isl_dim *dim = NULL;
3756         unsigned nparam;
3757
3758         if (!set || !mat)
3759                 goto error;
3760
3761         dim = isl_dim_copy(set->dim);
3762         dim = isl_dim_cow(dim);
3763         if (!dim)
3764                 goto error;
3765
3766         nparam = isl_set_dim(set, isl_dim_param);
3767
3768         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
3769
3770         dim->nparam = 0;
3771         dim->n_out = nparam;
3772         isl_set_reset_dim(set, dim);
3773         set = isl_set_preimage(set, mat);
3774         if (!set)
3775                 goto error2;
3776         dim = isl_dim_copy(set->dim);
3777         dim = isl_dim_cow(dim);
3778         if (!dim)
3779                 goto error2;
3780         dim->nparam = dim->n_out;
3781         dim->n_out = 0;
3782         isl_set_reset_dim(set, dim);
3783         return set;
3784 error:
3785         isl_dim_free(dim);
3786         isl_mat_free(mat);
3787 error2:
3788         isl_set_free(set);
3789         return NULL;
3790 }
3791
3792 /* Intersect the basic set "bset" with the affine space specified by the
3793  * equalities in "eq".
3794  */
3795 static struct isl_basic_set *basic_set_append_equalities(
3796         struct isl_basic_set *bset, struct isl_mat *eq)
3797 {
3798         int i, k;
3799         unsigned len;
3800
3801         if (!bset || !eq)
3802                 goto error;
3803
3804         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
3805                                         eq->n_row, 0);
3806         if (!bset)
3807                 goto error;
3808
3809         len = 1 + isl_dim_total(bset->dim) + bset->extra;
3810         for (i = 0; i < eq->n_row; ++i) {
3811                 k = isl_basic_set_alloc_equality(bset);
3812                 if (k < 0)
3813                         goto error;
3814                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
3815                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
3816         }
3817         isl_mat_free(eq);
3818
3819         return bset;
3820 error:
3821         isl_mat_free(eq);
3822         isl_basic_set_free(bset);
3823         return NULL;
3824 }
3825
3826 /* Intersect the set "set" with the affine space specified by the
3827  * equalities in "eq".
3828  */
3829 static struct isl_set *set_append_equalities(struct isl_set *set,
3830         struct isl_mat *eq)
3831 {
3832         int i;
3833
3834         if (!set || !eq)
3835                 goto error;
3836
3837         for (i = 0; i < set->n; ++i) {
3838                 set->p[i] = basic_set_append_equalities(set->p[i],
3839                                         isl_mat_copy(eq));
3840                 if (!set->p[i])
3841                         goto error;
3842         }
3843         isl_mat_free(eq);
3844         return set;
3845 error:
3846         isl_mat_free(eq);
3847         isl_set_free(set);
3848         return NULL;
3849 }
3850
3851 /* Project the given basic set onto its parameter domain, possibly introducing
3852  * new, explicit, existential variables in the constraints.
3853  * The input has parameters and (possibly implicit) existential variables.
3854  * The output has the same parameters, but only
3855  * explicit existentially quantified variables.
3856  *
3857  * The actual projection is performed by pip, but pip doesn't seem
3858  * to like equalities very much, so we first remove the equalities
3859  * among the parameters by performing a variable compression on
3860  * the parameters.  Afterward, an inverse transformation is performed
3861  * and the equalities among the parameters are inserted back in.
3862  */
3863 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
3864 {
3865         int i, j;
3866         struct isl_mat *eq;
3867         struct isl_mat *T, *T2;
3868         struct isl_set *set;
3869         unsigned nparam, n_div;
3870
3871         bset = isl_basic_set_cow(bset);
3872         if (!bset)
3873                 return NULL;
3874
3875         if (bset->n_eq == 0)
3876                 return isl_basic_set_lexmin(bset);
3877
3878         isl_basic_set_gauss(bset, NULL);
3879
3880         nparam = isl_basic_set_dim(bset, isl_dim_param);
3881         n_div = isl_basic_set_dim(bset, isl_dim_div);
3882
3883         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
3884                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
3885                         ++i;
3886         }
3887         if (i == bset->n_eq)
3888                 return isl_basic_set_lexmin(bset);
3889
3890         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
3891                 0, 1 + nparam);
3892         eq = isl_mat_cow(eq);
3893         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
3894         bset = basic_set_parameter_preimage(bset, T);
3895
3896         set = isl_basic_set_lexmin(bset);
3897         set = set_parameter_preimage(set, T2);
3898         set = set_append_equalities(set, eq);
3899         return set;
3900 }
3901
3902 /* Compute an explicit representation for all the existentially
3903  * quantified variables.
3904  * The input and output dimensions are first turned into parameters.
3905  * compute_divs then returns a map with the same parameters and
3906  * no input or output dimensions and the dimension specification
3907  * is reset to that of the input.
3908  */
3909 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
3910 {
3911         struct isl_basic_set *bset;
3912         struct isl_set *set;
3913         struct isl_map *map;
3914         struct isl_dim *dim, *orig_dim = NULL;
3915         unsigned         nparam;
3916         unsigned         n_in;
3917         unsigned         n_out;
3918
3919         bmap = isl_basic_map_cow(bmap);
3920         if (!bmap)
3921                 return NULL;
3922
3923         nparam = isl_basic_map_dim(bmap, isl_dim_param);
3924         n_in = isl_basic_map_dim(bmap, isl_dim_in);
3925         n_out = isl_basic_map_dim(bmap, isl_dim_out);
3926         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
3927         if (!dim)
3928                 goto error;
3929
3930         orig_dim = bmap->dim;
3931         bmap->dim = dim;
3932         bset = (struct isl_basic_set *)bmap;
3933
3934         set = parameter_compute_divs(bset);
3935         map = (struct isl_map *)set;
3936         map = isl_map_reset_dim(map, orig_dim);
3937
3938         return map;
3939 error:
3940         isl_basic_map_free(bmap);
3941         return NULL;
3942 }
3943
3944 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
3945 {
3946         int i;
3947         unsigned off;
3948
3949         if (!bmap)
3950                 return -1;
3951
3952         off = isl_dim_total(bmap->dim);
3953         for (i = 0; i < bmap->n_div; ++i) {
3954                 if (isl_int_is_zero(bmap->div[i][0]))
3955                         return 0;
3956                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
3957                                 return -1);
3958         }
3959         return 1;
3960 }
3961
3962 static int map_divs_known(__isl_keep isl_map *map)
3963 {
3964         int i;
3965
3966         if (!map)
3967                 return -1;
3968
3969         for (i = 0; i < map->n; ++i) {
3970                 int known = basic_map_divs_known(map->p[i]);
3971                 if (known <= 0)
3972                         return known;
3973         }
3974
3975         return 1;
3976 }
3977
3978 /* If bmap contains any unknown divs, then compute explicit
3979  * expressions for them.  However, this computation may be
3980  * quite expensive, so first try to remove divs that aren't
3981  * strictly needed.
3982  */
3983 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
3984 {
3985         int i;
3986         int known;
3987         struct isl_map *map;
3988
3989         known = basic_map_divs_known(bmap);
3990         if (known < 0)
3991                 goto error;
3992         if (known)
3993                 return isl_map_from_basic_map(bmap);
3994
3995         bmap = isl_basic_map_drop_redundant_divs(bmap);
3996
3997         known = basic_map_divs_known(bmap);
3998         if (known < 0)
3999                 goto error;
4000         if (known)
4001                 return isl_map_from_basic_map(bmap);
4002
4003         map = compute_divs(bmap);
4004         return map;
4005 error:
4006         isl_basic_map_free(bmap);
4007         return NULL;
4008 }
4009
4010 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4011 {
4012         int i;
4013         int known;
4014         struct isl_map *res;
4015
4016         if (!map)
4017                 return NULL;
4018         if (map->n == 0)
4019                 return map;
4020
4021         known = map_divs_known(map);
4022         if (known < 0) {
4023                 isl_map_free(map);
4024                 return NULL;
4025         }
4026         if (known)
4027                 return map;
4028
4029         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4030         for (i = 1 ; i < map->n; ++i) {
4031                 struct isl_map *r2;
4032                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4033                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4034                         res = isl_map_union_disjoint(res, r2);
4035                 else
4036                         res = isl_map_union(res, r2);
4037         }
4038         isl_map_free(map);
4039
4040         return res;
4041 }
4042
4043 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4044 {
4045         return (struct isl_set *)
4046                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4047 }
4048
4049 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4050 {
4051         return (struct isl_set *)
4052                 isl_map_compute_divs((struct isl_map *)set);
4053 }
4054
4055 struct isl_set *isl_map_domain(struct isl_map *map)
4056 {
4057         int i;
4058         struct isl_set *set;
4059
4060         if (!map)
4061                 goto error;
4062
4063         map = isl_map_cow(map);
4064         if (!map)
4065                 return NULL;
4066
4067         set = (struct isl_set *)map;
4068         set->dim = isl_dim_domain(set->dim);
4069         if (!set->dim)
4070                 goto error;
4071         for (i = 0; i < map->n; ++i) {
4072                 set->p[i] = isl_basic_map_domain(map->p[i]);
4073                 if (!set->p[i])
4074                         goto error;
4075         }
4076         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4077         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4078         return set;
4079 error:
4080         isl_map_free(map);
4081         return NULL;
4082 }
4083
4084 struct isl_map *isl_map_union_disjoint(
4085                         struct isl_map *map1, struct isl_map *map2)
4086 {
4087         int i;
4088         unsigned flags = 0;
4089         struct isl_map *map = NULL;
4090
4091         if (!map1 || !map2)
4092                 goto error;
4093
4094         if (map1->n == 0) {
4095                 isl_map_free(map1);
4096                 return map2;
4097         }
4098         if (map2->n == 0) {
4099                 isl_map_free(map2);
4100                 return map1;
4101         }
4102
4103         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4104
4105         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4106             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4107                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4108
4109         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4110                                 map1->n + map2->n, flags);
4111         if (!map)
4112                 goto error;
4113         for (i = 0; i < map1->n; ++i) {
4114                 map = isl_map_add(map,
4115                                   isl_basic_map_copy(map1->p[i]));
4116                 if (!map)
4117                         goto error;
4118         }
4119         for (i = 0; i < map2->n; ++i) {
4120                 map = isl_map_add(map,
4121                                   isl_basic_map_copy(map2->p[i]));
4122                 if (!map)
4123                         goto error;
4124         }
4125         isl_map_free(map1);
4126         isl_map_free(map2);
4127         return map;
4128 error:
4129         isl_map_free(map);
4130         isl_map_free(map1);
4131         isl_map_free(map2);
4132         return NULL;
4133 }
4134
4135 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4136 {
4137         map1 = isl_map_union_disjoint(map1, map2);
4138         if (!map1)
4139                 return NULL;
4140         if (map1->n > 1)
4141                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4142         return map1;
4143 }
4144
4145 struct isl_set *isl_set_union_disjoint(
4146                         struct isl_set *set1, struct isl_set *set2)
4147 {
4148         return (struct isl_set *)
4149                 isl_map_union_disjoint(
4150                         (struct isl_map *)set1, (struct isl_map *)set2);
4151 }
4152
4153 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4154 {
4155         return (struct isl_set *)
4156                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4157 }
4158
4159 struct isl_map *isl_map_intersect_range(
4160                 struct isl_map *map, struct isl_set *set)
4161 {
4162         unsigned flags = 0;
4163         struct isl_map *result;
4164         int i, j;
4165
4166         if (!map || !set)
4167                 goto error;
4168
4169         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4170             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4171                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4172
4173         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4174                                         map->n * set->n, flags);
4175         if (!result)
4176                 goto error;
4177         for (i = 0; i < map->n; ++i)
4178                 for (j = 0; j < set->n; ++j) {
4179                         result = isl_map_add(result,
4180                             isl_basic_map_intersect_range(
4181                                 isl_basic_map_copy(map->p[i]),
4182                                 isl_basic_set_copy(set->p[j])));
4183                         if (!result)
4184                                 goto error;
4185                 }
4186         isl_map_free(map);
4187         isl_set_free(set);
4188         return result;
4189 error:
4190         isl_map_free(map);
4191         isl_set_free(set);
4192         return NULL;
4193 }
4194
4195 struct isl_map *isl_map_intersect_domain(
4196                 struct isl_map *map, struct isl_set *set)
4197 {
4198         return isl_map_reverse(
4199                 isl_map_intersect_range(isl_map_reverse(map), set));
4200 }
4201
4202 struct isl_map *isl_map_apply_domain(
4203                 struct isl_map *map1, struct isl_map *map2)
4204 {
4205         if (!map1 || !map2)
4206                 goto error;
4207         map1 = isl_map_reverse(map1);
4208         map1 = isl_map_apply_range(map1, map2);
4209         return isl_map_reverse(map1);
4210 error:
4211         isl_map_free(map1);
4212         isl_map_free(map2);
4213         return NULL;
4214 }
4215
4216 struct isl_map *isl_map_apply_range(
4217                 struct isl_map *map1, struct isl_map *map2)
4218 {
4219         struct isl_dim *dim_result;
4220         struct isl_map *result;
4221         int i, j;
4222
4223         if (!map1 || !map2)
4224                 goto error;
4225
4226         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4227                                   isl_dim_copy(map2->dim));
4228
4229         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4230         if (!result)
4231                 goto error;
4232         for (i = 0; i < map1->n; ++i)
4233                 for (j = 0; j < map2->n; ++j) {
4234                         result = isl_map_add(result,
4235                             isl_basic_map_apply_range(
4236                                 isl_basic_map_copy(map1->p[i]),
4237                                 isl_basic_map_copy(map2->p[j])));
4238                         if (!result)
4239                                 goto error;
4240                 }
4241         isl_map_free(map1);
4242         isl_map_free(map2);
4243         if (result && result->n <= 1)
4244                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4245         return result;
4246 error:
4247         isl_map_free(map1);
4248         isl_map_free(map2);
4249         return NULL;
4250 }
4251
4252 /*
4253  * returns range - domain
4254  */
4255 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4256 {
4257         struct isl_basic_set *bset;
4258         unsigned dim;
4259         unsigned nparam;
4260         int i;
4261
4262         if (!bmap)
4263                 goto error;
4264         dim = isl_basic_map_n_in(bmap);
4265         nparam = isl_basic_map_n_param(bmap);
4266         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4267         bset = isl_basic_set_from_basic_map(bmap);
4268         bset = isl_basic_set_cow(bset);
4269         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
4270         bset = isl_basic_set_swap_vars(bset, 2*dim);
4271         for (i = 0; i < dim; ++i) {
4272                 int j = isl_basic_map_alloc_equality(
4273                                             (struct isl_basic_map *)bset);
4274                 if (j < 0)
4275                         goto error;
4276                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4277                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4278                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4279                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4280         }
4281         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4282 error:
4283         isl_basic_map_free(bmap);
4284         return NULL;
4285 }
4286
4287 /*
4288  * returns range - domain
4289  */
4290 struct isl_set *isl_map_deltas(struct isl_map *map)
4291 {
4292         int i;
4293         struct isl_set *result;
4294
4295         if (!map)
4296                 return NULL;
4297
4298         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4299         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
4300                                         isl_map_n_in(map), map->n, map->flags);
4301         if (!result)
4302                 goto error;
4303         for (i = 0; i < map->n; ++i)
4304                 result = isl_set_add(result,
4305                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4306         isl_map_free(map);
4307         return result;
4308 error:
4309         isl_map_free(map);
4310         return NULL;
4311 }
4312
4313 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4314 {
4315         struct isl_basic_map *bmap;
4316         unsigned nparam;
4317         unsigned dim;
4318         int i;
4319
4320         if (!dims)
4321                 return NULL;
4322
4323         nparam = dims->nparam;
4324         dim = dims->n_out;
4325         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4326         if (!bmap)
4327                 goto error;
4328
4329         for (i = 0; i < dim; ++i) {
4330                 int j = isl_basic_map_alloc_equality(bmap);
4331                 if (j < 0)
4332                         goto error;
4333                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4334                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
4335                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
4336         }
4337         return isl_basic_map_finalize(bmap);
4338 error:
4339         isl_basic_map_free(bmap);
4340         return NULL;
4341 }
4342
4343 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
4344 {
4345         struct isl_dim *dim = isl_dim_map(set_dim);
4346         if (!dim)
4347                 return NULL;
4348         return basic_map_identity(dim);
4349 }
4350
4351 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
4352 {
4353         if (!model || !model->dim)
4354                 return NULL;
4355         isl_assert(model->ctx,
4356                         model->dim->n_in == model->dim->n_out, return NULL);
4357         return basic_map_identity(isl_dim_copy(model->dim));
4358 }
4359
4360 static struct isl_map *map_identity(struct isl_dim *dim)
4361 {
4362         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
4363         return isl_map_add(map, basic_map_identity(isl_dim_copy(dim)));
4364 }
4365
4366 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
4367 {
4368         struct isl_dim *dim = isl_dim_map(set_dim);
4369         if (!dim)
4370                 return NULL;
4371         return map_identity(dim);
4372 }
4373
4374 struct isl_map *isl_map_identity_like(struct isl_map *model)
4375 {
4376         if (!model || !model->dim)
4377                 return NULL;
4378         isl_assert(model->ctx,
4379                         model->dim->n_in == model->dim->n_out, return NULL);
4380         return map_identity(isl_dim_copy(model->dim));
4381 }
4382
4383 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
4384 {
4385         if (!model || !model->dim)
4386                 return NULL;
4387         isl_assert(model->ctx,
4388                         model->dim->n_in == model->dim->n_out, return NULL);
4389         return map_identity(isl_dim_copy(model->dim));
4390 }
4391
4392 /* Construct a basic set with all set dimensions having only non-negative
4393  * values.
4394  */
4395 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
4396 {
4397         int i;
4398         unsigned nparam;
4399         unsigned dim;
4400         struct isl_basic_set *bset;
4401
4402         if (!dims)
4403                 return NULL;
4404         nparam = dims->nparam;
4405         dim = dims->n_out;
4406         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
4407         if (!bset)
4408                 return NULL;
4409         for (i = 0; i < dim; ++i) {
4410                 int k = isl_basic_set_alloc_inequality(bset);
4411                 if (k < 0)
4412                         goto error;
4413                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
4414                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
4415         }
4416         return bset;
4417 error:
4418         isl_basic_set_free(bset);
4419         return NULL;
4420 }
4421
4422 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
4423 {
4424         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
4425 }
4426
4427 int isl_basic_map_is_subset(
4428                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4429 {
4430         int is_subset;
4431         struct isl_map *map1;
4432         struct isl_map *map2;
4433
4434         if (!bmap1 || !bmap2)
4435                 return -1;
4436
4437         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
4438         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
4439
4440         is_subset = isl_map_is_subset(map1, map2);
4441
4442         isl_map_free(map1);
4443         isl_map_free(map2);
4444
4445         return is_subset;
4446 }
4447
4448 int isl_basic_map_is_equal(
4449                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4450 {
4451         int is_subset;
4452
4453         if (!bmap1 || !bmap2)
4454                 return -1;
4455         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4456         if (is_subset != 1)
4457                 return is_subset;
4458         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4459         return is_subset;
4460 }
4461
4462 int isl_basic_set_is_equal(
4463                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4464 {
4465         return isl_basic_map_is_equal(
4466                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4467 }
4468
4469 int isl_map_is_empty(struct isl_map *map)
4470 {
4471         int i;
4472         int is_empty;
4473
4474         if (!map)
4475                 return -1;
4476         for (i = 0; i < map->n; ++i) {
4477                 is_empty = isl_basic_map_is_empty(map->p[i]);
4478                 if (is_empty < 0)
4479                         return -1;
4480                 if (!is_empty)
4481                         return 0;
4482         }
4483         return 1;
4484 }
4485
4486 int isl_map_fast_is_empty(struct isl_map *map)
4487 {
4488         return map->n == 0;
4489 }
4490
4491 int isl_set_fast_is_empty(struct isl_set *set)
4492 {
4493         return set->n == 0;
4494 }
4495
4496 int isl_set_is_empty(struct isl_set *set)
4497 {
4498         return isl_map_is_empty((struct isl_map *)set);
4499 }
4500
4501 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4502 {
4503         int is_subset;
4504
4505         if (!map1 || !map2)
4506                 return -1;
4507         is_subset = isl_map_is_subset(map1, map2);
4508         if (is_subset != 1)
4509                 return is_subset;
4510         is_subset = isl_map_is_subset(map2, map1);
4511         return is_subset;
4512 }
4513
4514 int isl_basic_map_is_strict_subset(
4515                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4516 {
4517         int is_subset;
4518
4519         if (!bmap1 || !bmap2)
4520                 return -1;
4521         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4522         if (is_subset != 1)
4523                 return is_subset;
4524         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4525         if (is_subset == -1)
4526                 return is_subset;
4527         return !is_subset;
4528 }
4529
4530 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
4531 {
4532         int is_subset;
4533
4534         if (!map1 || !map2)
4535                 return -1;
4536         is_subset = isl_map_is_subset(map1, map2);
4537         if (is_subset != 1)
4538                 return is_subset;
4539         is_subset = isl_map_is_subset(map2, map1);
4540         if (is_subset == -1)
4541                 return is_subset;
4542         return !is_subset;
4543 }
4544
4545 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
4546 {
4547         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
4548 }
4549
4550 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4551 {
4552         if (!bmap)
4553                 return -1;
4554         return bmap->n_eq == 0 && bmap->n_ineq == 0;
4555 }
4556
4557 int isl_basic_set_is_universe(struct isl_basic_set *bset)
4558 {
4559         if (!bset)
4560                 return -1;
4561         return bset->n_eq == 0 && bset->n_ineq == 0;
4562 }
4563
4564 int isl_map_fast_is_universe(__isl_keep isl_map *map)
4565 {
4566         if (!map)
4567                 return -1;
4568
4569         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
4570 }
4571
4572 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4573 {
4574         struct isl_basic_set *bset = NULL;
4575         struct isl_vec *sample = NULL;
4576         int empty;
4577         unsigned total;
4578
4579         if (!bmap)
4580                 return -1;
4581
4582         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4583                 return 1;
4584
4585         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4586                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4587                 copy = isl_basic_map_convex_hull(copy);
4588                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4589                 isl_basic_map_free(copy);
4590                 return empty;
4591         }
4592
4593         total = 1 + isl_basic_map_total_dim(bmap);
4594         if (bmap->sample && bmap->sample->size == total) {
4595                 int contains = isl_basic_map_contains(bmap, bmap->sample);
4596                 if (contains < 0)
4597                         return -1;
4598                 if (contains)
4599                         return 0;
4600         }
4601         isl_vec_free(bmap->sample);
4602         bmap->sample = NULL;
4603         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4604         if (!bset)
4605                 return -1;
4606         sample = isl_basic_set_sample_vec(bset);
4607         if (!sample)
4608                 return -1;
4609         empty = sample->size == 0;
4610         isl_vec_free(bmap->sample);
4611         bmap->sample = sample;
4612         if (empty)
4613                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
4614
4615         return empty;
4616 }
4617
4618 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
4619 {
4620         if (!bmap)
4621                 return -1;
4622         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
4623 }
4624
4625 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
4626 {
4627         if (!bset)
4628                 return -1;
4629         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
4630 }
4631
4632 int isl_basic_set_is_empty(struct isl_basic_set *bset)
4633 {
4634         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
4635 }
4636
4637 struct isl_map *isl_basic_map_union(
4638         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4639 {
4640         struct isl_map *map;
4641         if (!bmap1 || !bmap2)
4642                 return NULL;
4643
4644         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
4645
4646         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
4647         if (!map)
4648                 goto error;
4649         map = isl_map_add(map, bmap1);
4650         map = isl_map_add(map, bmap2);
4651         return map;
4652 error:
4653         isl_basic_map_free(bmap1);
4654         isl_basic_map_free(bmap2);
4655         return NULL;
4656 }
4657
4658 struct isl_set *isl_basic_set_union(
4659                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4660 {
4661         return (struct isl_set *)isl_basic_map_union(
4662                                             (struct isl_basic_map *)bset1,
4663                                             (struct isl_basic_map *)bset2);
4664 }
4665
4666 /* Order divs such that any div only depends on previous divs */
4667 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
4668 {
4669         int i;
4670         unsigned off = isl_dim_total(bmap->dim);
4671
4672         for (i = 0; i < bmap->n_div; ++i) {
4673                 int pos;
4674                 if (isl_int_is_zero(bmap->div[i][0]))
4675                         continue;
4676                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
4677                                                             bmap->n_div-i);
4678                 if (pos == -1)
4679                         continue;
4680                 isl_basic_map_swap_div(bmap, i, i + pos);
4681                 --i;
4682         }
4683         return bmap;
4684 }
4685
4686 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
4687 {
4688         return (struct isl_basic_set *)
4689                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
4690 }
4691
4692 /* Look for a div in dst that corresponds to the div "div" in src.
4693  * The divs before "div" in src and dst are assumed to be the same.
4694  *
4695  * Returns -1 if no corresponding div was found and the position
4696  * of the corresponding div in dst otherwise.
4697  */
4698 static int find_div(struct isl_basic_map *dst,
4699                         struct isl_basic_map *src, unsigned div)
4700 {
4701         int i;
4702
4703         unsigned total = isl_dim_total(src->dim);
4704
4705         isl_assert(dst->ctx, div <= dst->n_div, return -1);
4706         for (i = div; i < dst->n_div; ++i)
4707                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
4708                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
4709                                                 dst->n_div - div) == -1)
4710                         return i;
4711         return -1;
4712 }
4713
4714 struct isl_basic_map *isl_basic_map_align_divs(
4715                 struct isl_basic_map *dst, struct isl_basic_map *src)
4716 {
4717         int i;
4718         unsigned total = isl_dim_total(src->dim);
4719
4720         if (!dst || !src)
4721                 goto error;
4722
4723         if (src->n_div == 0)
4724                 return dst;
4725
4726         for (i = 0; i < src->n_div; ++i)
4727                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
4728
4729         src = isl_basic_map_order_divs(src);
4730         dst = isl_basic_map_cow(dst);
4731         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
4732                         src->n_div, 0, 2 * src->n_div);
4733         if (!dst)
4734                 return NULL;
4735         for (i = 0; i < src->n_div; ++i) {
4736                 int j = find_div(dst, src, i);
4737                 if (j < 0) {
4738                         j = isl_basic_map_alloc_div(dst);
4739                         if (j < 0)
4740                                 goto error;
4741                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
4742                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
4743                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
4744                                 goto error;
4745                 }
4746                 if (j != i)
4747                         isl_basic_map_swap_div(dst, i, j);
4748         }
4749         return dst;
4750 error:
4751         isl_basic_map_free(dst);
4752         return NULL;
4753 }
4754
4755 struct isl_basic_set *isl_basic_set_align_divs(
4756                 struct isl_basic_set *dst, struct isl_basic_set *src)
4757 {
4758         return (struct isl_basic_set *)isl_basic_map_align_divs(
4759                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
4760 }
4761
4762 struct isl_map *isl_map_align_divs(struct isl_map *map)
4763 {
4764         int i;
4765
4766         if (!map)
4767                 return NULL;
4768         if (map->n == 0)
4769                 return map;
4770         map = isl_map_compute_divs(map);
4771         map = isl_map_cow(map);
4772         if (!map)
4773                 return NULL;
4774
4775         for (i = 1; i < map->n; ++i)
4776                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
4777         for (i = 1; i < map->n; ++i)
4778                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
4779
4780         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4781         return map;
4782 }
4783
4784 struct isl_set *isl_set_align_divs(struct isl_set *set)
4785 {
4786         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
4787 }
4788
4789 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
4790 {
4791         if (!set || !map)
4792                 goto error;
4793         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
4794         map = isl_map_intersect_domain(map, set);
4795         set = isl_map_range(map);
4796         return set;
4797 error:
4798         isl_set_free(set);
4799         isl_map_free(map);
4800         return NULL;
4801 }
4802
4803 /* There is no need to cow as removing empty parts doesn't change
4804  * the meaning of the set.
4805  */
4806 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
4807 {
4808         int i;
4809
4810         if (!map)
4811                 return NULL;
4812
4813         for (i = map->n-1; i >= 0; --i) {
4814                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
4815                         continue;
4816                 isl_basic_map_free(map->p[i]);
4817                 if (i != map->n-1) {
4818                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4819                         map->p[i] = map->p[map->n-1];
4820                 }
4821                 map->n--;
4822         }
4823
4824         return map;
4825 }
4826
4827 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
4828 {
4829         return (struct isl_set *)
4830                 isl_map_remove_empty_parts((struct isl_map *)set);
4831 }
4832
4833 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
4834 {
4835         struct isl_basic_map *bmap;
4836         if (!map || map->n == 0)
4837                 return NULL;
4838         bmap = map->p[map->n-1];
4839         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
4840         return isl_basic_map_copy(bmap);
4841 }
4842
4843 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
4844 {
4845         return (struct isl_basic_set *)
4846                 isl_map_copy_basic_map((struct isl_map *)set);
4847 }
4848
4849 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
4850                                                 __isl_keep isl_basic_map *bmap)
4851 {
4852         int i;
4853
4854         if (!map || !bmap)
4855                 goto error;
4856         for (i = map->n-1; i >= 0; --i) {
4857                 if (map->p[i] != bmap)
4858                         continue;
4859                 map = isl_map_cow(map);
4860                 if (!map)
4861                         goto error;
4862                 isl_basic_map_free(map->p[i]);
4863                 if (i != map->n-1) {
4864                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
4865                         map->p[i] = map->p[map->n-1];
4866                 }
4867                 map->n--;
4868                 return map;
4869         }
4870         return map;
4871 error:
4872         isl_map_free(map);
4873         return NULL;
4874 }
4875
4876 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
4877                                                 struct isl_basic_set *bset)
4878 {
4879         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
4880                                                 (struct isl_basic_map *)bset);
4881 }
4882
4883 /* Given two basic sets bset1 and bset2, compute the maximal difference
4884  * between the values of dimension pos in bset1 and those in bset2
4885  * for any common value of the parameters and dimensions preceding pos.
4886  */
4887 static enum isl_lp_result basic_set_maximal_difference_at(
4888         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
4889         int pos, isl_int *opt)
4890 {
4891         struct isl_dim *dims;
4892         struct isl_basic_map *bmap1 = NULL;
4893         struct isl_basic_map *bmap2 = NULL;
4894         struct isl_ctx *ctx;
4895         struct isl_vec *obj;
4896         unsigned total;
4897         unsigned nparam;
4898         unsigned dim1, dim2;
4899         enum isl_lp_result res;
4900
4901         if (!bset1 || !bset2)
4902                 return isl_lp_error;
4903
4904         nparam = isl_basic_set_n_param(bset1);
4905         dim1 = isl_basic_set_n_dim(bset1);
4906         dim2 = isl_basic_set_n_dim(bset2);
4907         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
4908         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
4909         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
4910         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
4911         if (!bmap1 || !bmap2)
4912                 goto error;
4913         bmap1 = isl_basic_map_cow(bmap1);
4914         bmap1 = isl_basic_map_extend(bmap1, nparam,
4915                         pos, (dim1 - pos) + (dim2 - pos),
4916                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
4917         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
4918         if (!bmap1)
4919                 goto error;
4920         total = isl_basic_map_total_dim(bmap1);
4921         ctx = bmap1->ctx;
4922         obj = isl_vec_alloc(ctx, 1 + total);
4923         isl_seq_clr(obj->block.data, 1 + total);
4924         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
4925         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
4926         if (!obj)
4927                 goto error;
4928         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
4929                                         opt, NULL, NULL);
4930         isl_basic_map_free(bmap1);
4931         isl_vec_free(obj);
4932         return res;
4933 error:
4934         isl_basic_map_free(bmap1);
4935         isl_basic_map_free(bmap2);
4936         return isl_lp_error;
4937 }
4938
4939 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
4940  * for any common value of the parameters and dimensions preceding pos
4941  * in both basic sets, the values of dimension pos in bset1 are
4942  * smaller or larger than those in bset2.
4943  *
4944  * Returns
4945  *       1 if bset1 follows bset2
4946  *      -1 if bset1 precedes bset2
4947  *       0 if bset1 and bset2 are incomparable
4948  *      -2 if some error occurred.
4949  */
4950 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
4951         struct isl_basic_set *bset2, int pos)
4952 {
4953         isl_int opt;
4954         enum isl_lp_result res;
4955         int cmp;
4956
4957         isl_int_init(opt);
4958
4959         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
4960
4961         if (res == isl_lp_empty)
4962                 cmp = 0;
4963         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
4964                   res == isl_lp_unbounded)
4965                 cmp = 1;
4966         else if (res == isl_lp_ok && isl_int_is_neg(opt))
4967                 cmp = -1;
4968         else
4969                 cmp = -2;
4970
4971         isl_int_clear(opt);
4972         return cmp;
4973 }
4974
4975 /* Given two basic sets bset1 and bset2, check whether
4976  * for any common value of the parameters and dimensions preceding pos
4977  * there is a value of dimension pos in bset1 that is larger
4978  * than a value of the same dimension in bset2.
4979  *
4980  * Return
4981  *       1 if there exists such a pair
4982  *       0 if there is no such pair, but there is a pair of equal values
4983  *      -1 otherwise
4984  *      -2 if some error occurred.
4985  */
4986 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
4987         __isl_keep isl_basic_set *bset2, int pos)
4988 {
4989         isl_int opt;
4990         enum isl_lp_result res;
4991         int cmp;
4992
4993         isl_int_init(opt);
4994
4995         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
4996
4997         if (res == isl_lp_empty)
4998                 cmp = -1;
4999         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5000                   res == isl_lp_unbounded)
5001                 cmp = 1;
5002         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5003                 cmp = -1;
5004         else if (res == isl_lp_ok)
5005                 cmp = 0;
5006         else
5007                 cmp = -2;
5008
5009         isl_int_clear(opt);
5010         return cmp;
5011 }
5012
5013 /* Given two sets set1 and set2, check whether
5014  * for any common value of the parameters and dimensions preceding pos
5015  * there is a value of dimension pos in set1 that is larger
5016  * than a value of the same dimension in set2.
5017  *
5018  * Return
5019  *       1 if there exists such a pair
5020  *       0 if there is no such pair, but there is a pair of equal values
5021  *      -1 otherwise
5022  *      -2 if some error occurred.
5023  */
5024 int isl_set_follows_at(__isl_keep isl_set *set1,
5025         __isl_keep isl_set *set2, int pos)
5026 {
5027         int i, j;
5028         int follows = -1;
5029
5030         if (!set1 || !set2)
5031                 return -2;
5032
5033         for (i = 0; i < set1->n; ++i)
5034                 for (j = 0; j < set2->n; ++j) {
5035                         int f;
5036                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5037                         if (f == 1 || f == -2)
5038                                 return f;
5039                         if (f > follows)
5040                                 follows = f;
5041                 }
5042
5043         return follows;
5044 }
5045
5046 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5047         unsigned pos, isl_int *val)
5048 {
5049         int i;
5050         int d;
5051         unsigned total;
5052
5053         if (!bmap)
5054                 return -1;
5055         total = isl_basic_map_total_dim(bmap);
5056         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5057                 for (; d+1 > pos; --d)
5058                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5059                                 break;
5060                 if (d != pos)
5061                         continue;
5062                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5063                         return 0;
5064                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5065                         return 0;
5066                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5067                         return 0;
5068                 if (val)
5069                         isl_int_neg(*val, bmap->eq[i][0]);
5070                 return 1;
5071         }
5072         return 0;
5073 }
5074
5075 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5076         unsigned pos, isl_int *val)
5077 {
5078         int i;
5079         isl_int v;
5080         isl_int tmp;
5081         int fixed;
5082
5083         if (!map)
5084                 return -1;
5085         if (map->n == 0)
5086                 return 0;
5087         if (map->n == 1)
5088                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5089         isl_int_init(v);
5090         isl_int_init(tmp);
5091         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5092         for (i = 1; fixed == 1 && i < map->n; ++i) {
5093                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5094                 if (fixed == 1 && isl_int_ne(tmp, v))
5095                         fixed = 0;
5096         }
5097         if (val)
5098                 isl_int_set(*val, v);
5099         isl_int_clear(tmp);
5100         isl_int_clear(v);
5101         return fixed;
5102 }
5103
5104 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5105         unsigned pos, isl_int *val)
5106 {
5107         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5108                                                 pos, val);
5109 }
5110
5111 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5112         isl_int *val)
5113 {
5114         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5115 }
5116
5117 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5118         enum isl_dim_type type, unsigned pos, isl_int *val)
5119 {
5120         if (pos >= isl_basic_map_dim(bmap, type))
5121                 return -1;
5122         return isl_basic_map_fast_has_fixed_var(bmap,
5123                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
5124 }
5125
5126 int isl_map_fast_is_fixed(struct isl_map *map,
5127         enum isl_dim_type type, unsigned pos, isl_int *val)
5128 {
5129         if (pos >= isl_map_dim(map, type))
5130                 return -1;
5131         return isl_map_fast_has_fixed_var(map,
5132                 map_offset(map, type) - 1 + pos, val);
5133 }
5134
5135 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5136  * then return this fixed value in *val.
5137  */
5138 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
5139         isl_int *val)
5140 {
5141         return isl_basic_set_fast_has_fixed_var(bset,
5142                                         isl_basic_set_n_param(bset) + dim, val);
5143 }
5144
5145 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5146  * then return this fixed value in *val.
5147  */
5148 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
5149 {
5150         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
5151 }
5152
5153 /* Check if input variable in has fixed value and if so and if val is not NULL,
5154  * then return this fixed value in *val.
5155  */
5156 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
5157 {
5158         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
5159 }
5160
5161 /* Check if dimension dim has an (obvious) fixed lower bound and if so
5162  * and if val is not NULL, then return this lower bound in *val.
5163  */
5164 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
5165         unsigned dim, isl_int *val)
5166 {
5167         int i, i_eq = -1, i_ineq = -1;
5168         isl_int *c;
5169         unsigned total;
5170         unsigned nparam;
5171
5172         if (!bset)
5173                 return -1;
5174         total = isl_basic_set_total_dim(bset);
5175         nparam = isl_basic_set_n_param(bset);
5176         for (i = 0; i < bset->n_eq; ++i) {
5177                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
5178                         continue;
5179                 if (i_eq != -1)
5180                         return 0;
5181                 i_eq = i;
5182         }
5183         for (i = 0; i < bset->n_ineq; ++i) {
5184                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
5185                         continue;
5186                 if (i_eq != -1 || i_ineq != -1)
5187                         return 0;
5188                 i_ineq = i;
5189         }
5190         if (i_eq == -1 && i_ineq == -1)
5191                 return 0;
5192         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
5193         /* The coefficient should always be one due to normalization. */
5194         if (!isl_int_is_one(c[1+nparam+dim]))
5195                 return 0;
5196         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
5197                 return 0;
5198         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
5199                                         total - nparam - dim - 1) != -1)
5200                 return 0;
5201         if (val)
5202                 isl_int_neg(*val, c[0]);
5203         return 1;
5204 }
5205
5206 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
5207         unsigned dim, isl_int *val)
5208 {
5209         int i;
5210         isl_int v;
5211         isl_int tmp;
5212         int fixed;
5213
5214         if (!set)
5215                 return -1;
5216         if (set->n == 0)
5217                 return 0;
5218         if (set->n == 1)
5219                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5220                                                                 dim, val);
5221         isl_int_init(v);
5222         isl_int_init(tmp);
5223         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5224                                                                 dim, &v);
5225         for (i = 1; fixed == 1 && i < set->n; ++i) {
5226                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5227                                                                 dim, &tmp);
5228                 if (fixed == 1 && isl_int_ne(tmp, v))
5229                         fixed = 0;
5230         }
5231         if (val)
5232                 isl_int_set(*val, v);
5233         isl_int_clear(tmp);
5234         isl_int_clear(v);
5235         return fixed;
5236 }
5237
5238 struct constraint {
5239         unsigned        size;
5240         isl_int         *c;
5241 };
5242
5243 static int qsort_constraint_cmp(const void *p1, const void *p2)
5244 {
5245         const struct constraint *c1 = (const struct constraint *)p1;
5246         const struct constraint *c2 = (const struct constraint *)p2;
5247         unsigned size = isl_min(c1->size, c2->size);
5248         return isl_seq_cmp(c1->c, c2->c, size);
5249 }
5250
5251 static struct isl_basic_map *isl_basic_map_sort_constraints(
5252         struct isl_basic_map *bmap)
5253 {
5254         int i;
5255         struct constraint *c;
5256         unsigned total;
5257
5258         if (!bmap)
5259                 return NULL;
5260         total = isl_basic_map_total_dim(bmap);
5261         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5262         if (!c)
5263                 goto error;
5264         for (i = 0; i < bmap->n_ineq; ++i) {
5265                 c[i].size = total;
5266                 c[i].c = bmap->ineq[i];
5267         }
5268         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5269         for (i = 0; i < bmap->n_ineq; ++i)
5270                 bmap->ineq[i] = c[i].c;
5271         free(c);
5272         return bmap;
5273 error:
5274         isl_basic_map_free(bmap);
5275         return NULL;
5276 }
5277
5278 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5279 {
5280         if (!bmap)
5281                 return NULL;
5282         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5283                 return bmap;
5284         bmap = isl_basic_map_convex_hull(bmap);
5285         bmap = isl_basic_map_sort_constraints(bmap);
5286         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5287         return bmap;
5288 }
5289
5290 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5291 {
5292         return (struct isl_basic_set *)isl_basic_map_normalize(
5293                                                 (struct isl_basic_map *)bset);
5294 }
5295
5296 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5297         const struct isl_basic_map *bmap2)
5298 {
5299         int i, cmp;
5300         unsigned total;
5301
5302         if (bmap1 == bmap2)
5303                 return 0;
5304         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5305                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5306         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5307                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5308         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5309                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5310         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5311             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5312                 return 0;
5313         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5314                 return 1;
5315         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5316                 return -1;
5317         if (bmap1->n_eq != bmap2->n_eq)
5318                 return bmap1->n_eq - bmap2->n_eq;
5319         if (bmap1->n_ineq != bmap2->n_ineq)
5320                 return bmap1->n_ineq - bmap2->n_ineq;
5321         if (bmap1->n_div != bmap2->n_div)
5322                 return bmap1->n_div - bmap2->n_div;
5323         total = isl_basic_map_total_dim(bmap1);
5324         for (i = 0; i < bmap1->n_eq; ++i) {
5325                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5326                 if (cmp)
5327                         return cmp;
5328         }
5329         for (i = 0; i < bmap1->n_ineq; ++i) {
5330                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5331                 if (cmp)
5332                         return cmp;
5333         }
5334         for (i = 0; i < bmap1->n_div; ++i) {
5335                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5336                 if (cmp)
5337                         return cmp;
5338         }
5339         return 0;
5340 }
5341
5342 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5343         struct isl_basic_map *bmap2)
5344 {
5345         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5346 }
5347
5348 static int qsort_bmap_cmp(const void *p1, const void *p2)
5349 {
5350         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5351         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5352
5353         return isl_basic_map_fast_cmp(bmap1, bmap2);
5354 }
5355
5356 /* We normalize in place, but if anything goes wrong we need
5357  * to return NULL, so we need to make sure we don't change the
5358  * meaning of any possible other copies of map.
5359  */
5360 struct isl_map *isl_map_normalize(struct isl_map *map)
5361 {
5362         int i, j;
5363         struct isl_basic_map *bmap;
5364
5365         if (!map)
5366                 return NULL;
5367         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
5368                 return map;
5369         for (i = 0; i < map->n; ++i) {
5370                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5371                 if (!bmap)
5372                         goto error;
5373                 isl_basic_map_free(map->p[i]);
5374                 map->p[i] = bmap;
5375         }
5376         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5377         ISL_F_SET(map, ISL_MAP_NORMALIZED);
5378         map = isl_map_remove_empty_parts(map);
5379         if (!map)
5380                 return NULL;
5381         for (i = map->n - 1; i >= 1; --i) {
5382                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5383                         continue;
5384                 isl_basic_map_free(map->p[i-1]);
5385                 for (j = i; j < map->n; ++j)
5386                         map->p[j-1] = map->p[j];
5387                 map->n--;
5388         }
5389         return map;
5390 error:
5391         isl_map_free(map);
5392         return NULL;
5393
5394 }
5395
5396 struct isl_set *isl_set_normalize(struct isl_set *set)
5397 {
5398         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5399 }
5400
5401 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5402 {
5403         int i;
5404         int equal;
5405
5406         if (!map1 || !map2)
5407                 return -1;
5408
5409         if (map1 == map2)
5410                 return 1;
5411         if (!isl_dim_equal(map1->dim, map2->dim))
5412                 return 0;
5413
5414         map1 = isl_map_copy(map1);
5415         map2 = isl_map_copy(map2);
5416         map1 = isl_map_normalize(map1);
5417         map2 = isl_map_normalize(map2);
5418         if (!map1 || !map2)
5419                 goto error;
5420         equal = map1->n == map2->n;
5421         for (i = 0; equal && i < map1->n; ++i) {
5422                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5423                 if (equal < 0)
5424                         goto error;
5425         }
5426         isl_map_free(map1);
5427         isl_map_free(map2);
5428         return equal;
5429 error:
5430         isl_map_free(map1);
5431         isl_map_free(map2);
5432         return -1;
5433 }
5434
5435 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5436 {
5437         return isl_map_fast_is_equal((struct isl_map *)set1,
5438                                                 (struct isl_map *)set2);
5439 }
5440
5441 /* Return an interval that ranges from min to max (inclusive)
5442  */
5443 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5444         isl_int min, isl_int max)
5445 {
5446         int k;
5447         struct isl_basic_set *bset = NULL;
5448
5449         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5450         if (!bset)
5451                 goto error;
5452
5453         k = isl_basic_set_alloc_inequality(bset);
5454         if (k < 0)
5455                 goto error;
5456         isl_int_set_si(bset->ineq[k][1], 1);
5457         isl_int_neg(bset->ineq[k][0], min);
5458
5459         k = isl_basic_set_alloc_inequality(bset);
5460         if (k < 0)
5461                 goto error;
5462         isl_int_set_si(bset->ineq[k][1], -1);
5463         isl_int_set(bset->ineq[k][0], max);
5464
5465         return bset;
5466 error:
5467         isl_basic_set_free(bset);
5468         return NULL;
5469 }
5470
5471 /* Return the Cartesian product of the basic sets in list (in the given order).
5472  */
5473 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5474 {
5475         int i;
5476         unsigned dim;
5477         unsigned nparam;
5478         unsigned extra;
5479         unsigned n_eq;
5480         unsigned n_ineq;
5481         struct isl_basic_set *product = NULL;
5482
5483         if (!list)
5484                 goto error;
5485         isl_assert(list->ctx, list->n > 0, goto error);
5486         isl_assert(list->ctx, list->p[0], goto error);
5487         nparam = isl_basic_set_n_param(list->p[0]);
5488         dim = isl_basic_set_n_dim(list->p[0]);
5489         extra = list->p[0]->n_div;
5490         n_eq = list->p[0]->n_eq;
5491         n_ineq = list->p[0]->n_ineq;
5492         for (i = 1; i < list->n; ++i) {
5493                 isl_assert(list->ctx, list->p[i], goto error);
5494                 isl_assert(list->ctx,
5495                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5496                 dim += isl_basic_set_n_dim(list->p[i]);
5497                 extra += list->p[i]->n_div;
5498                 n_eq += list->p[i]->n_eq;
5499                 n_ineq += list->p[i]->n_ineq;
5500         }
5501         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5502                                         n_eq, n_ineq);
5503         if (!product)
5504                 goto error;
5505         dim = 0;
5506         for (i = 0; i < list->n; ++i) {
5507                 isl_basic_set_add_constraints(product,
5508                                         isl_basic_set_copy(list->p[i]), dim);
5509                 dim += isl_basic_set_n_dim(list->p[i]);
5510         }
5511         isl_basic_set_list_free(list);
5512         return product;
5513 error:
5514         isl_basic_set_free(product);
5515         isl_basic_set_list_free(list);
5516         return NULL;
5517 }
5518
5519 struct isl_basic_map *isl_basic_map_product(
5520                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5521 {
5522         struct isl_dim *dim_result = NULL;
5523         struct isl_basic_map *bmap;
5524         unsigned in1, in2, out1, out2, nparam, total, pos;
5525         struct isl_dim_map *dim_map1, *dim_map2;
5526
5527         if (!bmap1 || !bmap2)
5528                 goto error;
5529
5530         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
5531                                      bmap2->dim, isl_dim_param), goto error);
5532         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
5533                                                    isl_dim_copy(bmap2->dim));
5534
5535         in1 = isl_basic_map_n_in(bmap1);
5536         in2 = isl_basic_map_n_in(bmap2);
5537         out1 = isl_basic_map_n_out(bmap1);
5538         out2 = isl_basic_map_n_out(bmap2);
5539         nparam = isl_basic_map_n_param(bmap1);
5540
5541         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
5542         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
5543         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
5544         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
5545         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
5546         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
5547         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
5548         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
5549         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
5550         isl_dim_map_div(dim_map1, bmap1, pos += out2);
5551         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
5552
5553         bmap = isl_basic_map_alloc_dim(dim_result,
5554                         bmap1->n_div + bmap2->n_div,
5555                         bmap1->n_eq + bmap2->n_eq,
5556                         bmap1->n_ineq + bmap2->n_ineq);
5557         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
5558         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
5559         bmap = isl_basic_map_simplify(bmap);
5560         return isl_basic_map_finalize(bmap);
5561 error:
5562         isl_basic_map_free(bmap1);
5563         isl_basic_map_free(bmap2);
5564         return NULL;
5565 }
5566
5567 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
5568  */
5569 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
5570 {
5571         unsigned flags = 0;
5572         struct isl_map *result;
5573         int i, j;
5574
5575         if (!map1 || !map2)
5576                 goto error;
5577
5578         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
5579                                          map2->dim, isl_dim_param), goto error);
5580
5581         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
5582             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
5583                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
5584
5585         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
5586                                                    isl_dim_copy(map2->dim)),
5587                                 map1->n * map2->n, flags);
5588         if (!result)
5589                 goto error;
5590         for (i = 0; i < map1->n; ++i)
5591                 for (j = 0; j < map2->n; ++j) {
5592                         struct isl_basic_map *part;
5593                         part = isl_basic_map_product(
5594                                     isl_basic_map_copy(map1->p[i]),
5595                                     isl_basic_map_copy(map2->p[j]));
5596                         if (isl_basic_map_is_empty(part))
5597                                 isl_basic_map_free(part);
5598                         else
5599                                 result = isl_map_add(result, part);
5600                         if (!result)
5601                                 goto error;
5602                 }
5603         isl_map_free(map1);
5604         isl_map_free(map2);
5605         return result;
5606 error:
5607         isl_map_free(map1);
5608         isl_map_free(map2);
5609         return NULL;
5610 }
5611
5612 /* Given two set A and B, construct its Cartesian product A x B.
5613  */
5614 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
5615 {
5616         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
5617                                                  (struct isl_map *)set2);
5618 }
5619
5620 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5621 {
5622         int i;
5623         uint32_t hash = isl_hash_init();
5624         unsigned total;
5625
5626         if (!bset)
5627                 return 0;
5628         bset = isl_basic_set_copy(bset);
5629         bset = isl_basic_set_normalize(bset);
5630         if (!bset)
5631                 return 0;
5632         total = isl_basic_set_total_dim(bset);
5633         isl_hash_byte(hash, bset->n_eq & 0xFF);
5634         for (i = 0; i < bset->n_eq; ++i) {
5635                 uint32_t c_hash;
5636                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5637                 isl_hash_hash(hash, c_hash);
5638         }
5639         isl_hash_byte(hash, bset->n_ineq & 0xFF);
5640         for (i = 0; i < bset->n_ineq; ++i) {
5641                 uint32_t c_hash;
5642                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
5643                 isl_hash_hash(hash, c_hash);
5644         }
5645         isl_hash_byte(hash, bset->n_div & 0xFF);
5646         for (i = 0; i < bset->n_div; ++i) {
5647                 uint32_t c_hash;
5648                 if (isl_int_is_zero(bset->div[i][0]))
5649                         continue;
5650                 isl_hash_byte(hash, i & 0xFF);
5651                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
5652                 isl_hash_hash(hash, c_hash);
5653         }
5654         isl_basic_set_free(bset);
5655         return hash;
5656 }
5657
5658 uint32_t isl_set_get_hash(struct isl_set *set)
5659 {
5660         int i;
5661         uint32_t hash;
5662
5663         if (!set)
5664                 return 0;
5665         set = isl_set_copy(set);
5666         set = isl_set_normalize(set);
5667         if (!set)
5668                 return 0;
5669
5670         hash = isl_hash_init();
5671         for (i = 0; i < set->n; ++i) {
5672                 uint32_t bset_hash;
5673                 bset_hash = isl_basic_set_get_hash(set->p[i]);
5674                 isl_hash_hash(hash, bset_hash);
5675         }
5676
5677         isl_set_free(set);
5678
5679         return hash;
5680 }
5681
5682 /* Check if the value for dimension dim is completely determined
5683  * by the values of the other parameters and variables.
5684  * That is, check if dimension dim is involved in an equality.
5685  */
5686 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
5687 {
5688         int i;
5689         unsigned nparam;
5690
5691         if (!bset)
5692                 return -1;
5693         nparam = isl_basic_set_n_param(bset);
5694         for (i = 0; i < bset->n_eq; ++i)
5695                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
5696                         return 1;
5697         return 0;
5698 }
5699
5700 /* Check if the value for dimension dim is completely determined
5701  * by the values of the other parameters and variables.
5702  * That is, check if dimension dim is involved in an equality
5703  * for each of the subsets.
5704  */
5705 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
5706 {
5707         int i;
5708
5709         if (!set)
5710                 return -1;
5711         for (i = 0; i < set->n; ++i) {
5712                 int unique;
5713                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
5714                 if (unique != 1)
5715                         return unique;
5716         }
5717         return 1;
5718 }
5719
5720 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
5721         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
5722 {
5723         int i;
5724
5725         if (!map)
5726                 return -1;
5727
5728         for (i = 0; i < map->n; ++i)
5729                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
5730                         return -1;
5731
5732         return 0;
5733 }
5734
5735 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
5736         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
5737 {
5738         int i;
5739
5740         if (!set)
5741                 return -1;
5742
5743         for (i = 0; i < set->n; ++i)
5744                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
5745                         return -1;
5746
5747         return 0;
5748 }
5749
5750 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
5751 {
5752         struct isl_dim *dim;
5753         struct isl_basic_map *bmap;
5754         unsigned n_set;
5755         unsigned n_div;
5756         unsigned n_param;
5757         unsigned total;
5758         int i, k, l;
5759
5760         set = isl_set_align_divs(set);
5761
5762         if (!set)
5763                 return NULL;
5764
5765         dim = isl_set_get_dim(set);
5766         if (set->n == 0 || set->p[0]->n_div == 0) {
5767                 isl_set_free(set);
5768                 return isl_map_identity(dim);
5769         }
5770
5771         n_div = set->p[0]->n_div;
5772         dim = isl_dim_map(dim);
5773         n_param = isl_dim_size(dim, isl_dim_param);
5774         n_set = isl_dim_size(dim, isl_dim_in);
5775         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
5776         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
5777         for (i = 0; i < n_set; ++i)
5778                 bmap = var_equal(bmap, i);
5779
5780         total = n_param + n_set + n_set + n_div;
5781         for (i = 0; i < n_div; ++i) {
5782                 k = isl_basic_map_alloc_inequality(bmap);
5783                 if (k < 0)
5784                         goto error;
5785                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
5786                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
5787                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
5788                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
5789                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
5790                             set->p[0]->div[i][0]);
5791
5792                 l = isl_basic_map_alloc_inequality(bmap);
5793                 if (l < 0)
5794                         goto error;
5795                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
5796                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
5797                             set->p[0]->div[i][0]);
5798                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
5799         }
5800
5801         isl_set_free(set);
5802         return isl_map_from_basic_map(bmap);
5803 error:
5804         isl_set_free(set);
5805         isl_basic_map_free(bmap);
5806         return NULL;
5807 }
5808
5809 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
5810 {
5811         unsigned dim;
5812         int size = 0;
5813
5814         if (!bset)
5815                 return -1;
5816
5817         dim = isl_basic_set_total_dim(bset);
5818         size += bset->n_eq * (1 + dim);
5819         size += bset->n_ineq * (1 + dim);
5820         size += bset->n_div * (2 + dim);
5821
5822         return size;
5823 }
5824
5825 int isl_set_size(__isl_keep isl_set *set)
5826 {
5827         int i;
5828         int size = 0;
5829
5830         if (!set)
5831                 return -1;
5832
5833         for (i = 0; i < set->n; ++i)
5834                 size += isl_basic_set_size(set->p[i]);
5835
5836         return size;
5837 }