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