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