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 static int 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 (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 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
3435 {
3436         struct isl_basic_set *dom = NULL;
3437         struct isl_dim *dom_dim;
3438
3439         if (!bmap)
3440                 goto error;
3441         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
3442         dom = isl_basic_set_universe(dom_dim);
3443         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
3444 error:
3445         isl_basic_map_free(bmap);
3446         return NULL;
3447 }
3448
3449 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
3450 {
3451         return isl_basic_map_lexopt(bmap, 0);
3452 }
3453
3454 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
3455 {
3456         return isl_basic_map_lexopt(bmap, 1);
3457 }
3458
3459 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
3460 {
3461         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
3462 }
3463
3464 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
3465 {
3466         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
3467 }
3468
3469 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
3470         struct isl_dim *dim)
3471 {
3472         int i;
3473
3474         if (!map || !dim)
3475                 goto error;
3476
3477         for (i = 0; i < map->n; ++i) {
3478                 isl_dim_free(map->p[i]->dim);
3479                 map->p[i]->dim = isl_dim_copy(dim);
3480         }
3481         isl_dim_free(map->dim);
3482         map->dim = dim;
3483
3484         return map;
3485 error:
3486         isl_map_free(map);
3487         isl_dim_free(dim);
3488         return NULL;
3489 }
3490
3491 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
3492         struct isl_dim *dim)
3493 {
3494         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
3495 }
3496
3497 /* Apply a preimage specified by "mat" on the parameters of "bset".
3498  * bset is assumed to have only parameters and divs.
3499  */
3500 static struct isl_basic_set *basic_set_parameter_preimage(
3501         struct isl_basic_set *bset, struct isl_mat *mat)
3502 {
3503         unsigned nparam;
3504
3505         if (!bset || !mat)
3506                 goto error;
3507
3508         bset->dim = isl_dim_cow(bset->dim);
3509         if (!bset->dim)
3510                 goto error;
3511
3512         nparam = isl_basic_set_dim(bset, isl_dim_param);
3513
3514         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
3515
3516         bset->dim->nparam = 0;
3517         bset->dim->n_out = nparam;
3518         bset = isl_basic_set_preimage(bset, mat);
3519         if (bset) {
3520                 bset->dim->nparam = bset->dim->n_out;
3521                 bset->dim->n_out = 0;
3522         }
3523         return bset;
3524 error:
3525         isl_mat_free(mat);
3526         isl_basic_set_free(bset);
3527         return NULL;
3528 }
3529
3530 /* Apply a preimage specified by "mat" on the parameters of "set".
3531  * set is assumed to have only parameters and divs.
3532  */
3533 static struct isl_set *set_parameter_preimage(
3534         struct isl_set *set, struct isl_mat *mat)
3535 {
3536         struct isl_dim *dim = NULL;
3537         unsigned nparam;
3538
3539         if (!set || !mat)
3540                 goto error;
3541
3542         dim = isl_dim_copy(set->dim);
3543         dim = isl_dim_cow(dim);
3544         if (!dim)
3545                 goto error;
3546
3547         nparam = isl_set_dim(set, isl_dim_param);
3548
3549         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
3550
3551         dim->nparam = 0;
3552         dim->n_out = nparam;
3553         isl_set_reset_dim(set, dim);
3554         set = isl_set_preimage(set, mat);
3555         if (!set)
3556                 goto error2;
3557         dim = isl_dim_copy(set->dim);
3558         dim = isl_dim_cow(dim);
3559         if (!dim)
3560                 goto error2;
3561         dim->nparam = dim->n_out;
3562         dim->n_out = 0;
3563         isl_set_reset_dim(set, dim);
3564         return set;
3565 error:
3566         isl_dim_free(dim);
3567         isl_mat_free(mat);
3568 error2:
3569         isl_set_free(set);
3570         return NULL;
3571 }
3572
3573 /* Intersect the basic set "bset" with the affine space specified by the
3574  * equalities in "eq".
3575  */
3576 static struct isl_basic_set *basic_set_append_equalities(
3577         struct isl_basic_set *bset, struct isl_mat *eq)
3578 {
3579         int i, k;
3580         unsigned len;
3581
3582         if (!bset || !eq)
3583                 goto error;
3584
3585         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
3586                                         eq->n_row, 0);
3587         if (!bset)
3588                 goto error;
3589
3590         len = 1 + isl_dim_total(bset->dim) + bset->extra;
3591         for (i = 0; i < eq->n_row; ++i) {
3592                 k = isl_basic_set_alloc_equality(bset);
3593                 if (k < 0)
3594                         goto error;
3595                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
3596                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
3597         }
3598         isl_mat_free(eq);
3599
3600         return bset;
3601 error:
3602         isl_mat_free(eq);
3603         isl_basic_set_free(bset);
3604         return NULL;
3605 }
3606
3607 /* Intersect the set "set" with the affine space specified by the
3608  * equalities in "eq".
3609  */
3610 static struct isl_set *set_append_equalities(struct isl_set *set,
3611         struct isl_mat *eq)
3612 {
3613         int i;
3614
3615         if (!set || !eq)
3616                 goto error;
3617
3618         for (i = 0; i < set->n; ++i) {
3619                 set->p[i] = basic_set_append_equalities(set->p[i],
3620                                         isl_mat_copy(eq));
3621                 if (!set->p[i])
3622                         goto error;
3623         }
3624         isl_mat_free(eq);
3625         return set;
3626 error:
3627         isl_mat_free(eq);
3628         isl_set_free(set);
3629         return NULL;
3630 }
3631
3632 /* Project the given basic set onto its parameter domain, possibly introducing
3633  * new, explicit, existential variables in the constraints.
3634  * The input has parameters and (possibly implicit) existential variables.
3635  * The output has the same parameters, but only
3636  * explicit existentially quantified variables.
3637  *
3638  * The actual projection is performed by pip, but pip doesn't seem
3639  * to like equalities very much, so we first remove the equalities
3640  * among the parameters by performing a variable compression on
3641  * the parameters.  Afterward, an inverse transformation is performed
3642  * and the equalities among the parameters are inserted back in.
3643  */
3644 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
3645 {
3646         int i, j;
3647         struct isl_mat *eq;
3648         struct isl_mat *T, *T2;
3649         struct isl_set *set;
3650         unsigned nparam, n_div;
3651
3652         bset = isl_basic_set_cow(bset);
3653         if (!bset)
3654                 return NULL;
3655
3656         if (bset->n_eq == 0)
3657                 return isl_basic_set_lexmin(bset);
3658
3659         isl_basic_set_gauss(bset, NULL);
3660
3661         nparam = isl_basic_set_dim(bset, isl_dim_param);
3662         n_div = isl_basic_set_dim(bset, isl_dim_div);
3663
3664         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
3665                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
3666                         ++i;
3667         }
3668         if (i == bset->n_eq)
3669                 return isl_basic_set_lexmin(bset);
3670
3671         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
3672                 0, 1 + nparam);
3673         eq = isl_mat_cow(eq);
3674         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
3675         bset = basic_set_parameter_preimage(bset, T);
3676
3677         set = isl_basic_set_lexmin(bset);
3678         set = set_parameter_preimage(set, T2);
3679         set = set_append_equalities(set, eq);
3680         return set;
3681 }
3682
3683 /* Compute an explicit representation for all the existentially
3684  * quantified variables.
3685  * The input and output dimensions are first turned into parameters.
3686  * compute_divs then returns a map with the same parameters and
3687  * no input or output dimensions and the dimension specification
3688  * is reset to that of the input.
3689  */
3690 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
3691 {
3692         struct isl_basic_set *bset;
3693         struct isl_set *set;
3694         struct isl_map *map;
3695         struct isl_dim *dim, *orig_dim = NULL;
3696         unsigned         nparam;
3697         unsigned         n_in;
3698         unsigned         n_out;
3699
3700         bmap = isl_basic_map_cow(bmap);
3701         if (!bmap)
3702                 return NULL;
3703
3704         nparam = isl_basic_map_dim(bmap, isl_dim_param);
3705         n_in = isl_basic_map_dim(bmap, isl_dim_in);
3706         n_out = isl_basic_map_dim(bmap, isl_dim_out);
3707         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
3708         if (!dim)
3709                 goto error;
3710
3711         orig_dim = bmap->dim;
3712         bmap->dim = dim;
3713         bset = (struct isl_basic_set *)bmap;
3714
3715         set = parameter_compute_divs(bset);
3716         map = (struct isl_map *)set;
3717         map = isl_map_reset_dim(map, orig_dim);
3718
3719         return map;
3720 error:
3721         isl_basic_map_free(bmap);
3722         return NULL;
3723 }
3724
3725 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
3726 {
3727         int i;
3728         unsigned off;
3729
3730         if (!bmap)
3731                 return -1;
3732
3733         off = isl_dim_total(bmap->dim);
3734         for (i = 0; i < bmap->n_div; ++i) {
3735                 if (isl_int_is_zero(bmap->div[i][0]))
3736                         return 0;
3737                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
3738                                 return -1);
3739         }
3740         return 1;
3741 }
3742
3743 static int map_divs_known(__isl_keep isl_map *map)
3744 {
3745         int i;
3746
3747         if (!map)
3748                 return -1;
3749
3750         for (i = 0; i < map->n; ++i) {
3751                 int known = basic_map_divs_known(map->p[i]);
3752                 if (known <= 0)
3753                         return known;
3754         }
3755
3756         return 1;
3757 }
3758
3759 /* If bmap contains any unknown divs, then compute explicit
3760  * expressions for them.  However, this computation may be
3761  * quite expensive, so first try to remove divs that aren't
3762  * strictly needed.
3763  */
3764 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
3765 {
3766         int i;
3767         int known;
3768         struct isl_map *map;
3769
3770         known = basic_map_divs_known(bmap);
3771         if (known < 0)
3772                 goto error;
3773         if (known)
3774                 return isl_map_from_basic_map(bmap);
3775
3776         bmap = isl_basic_map_drop_redundant_divs(bmap);
3777
3778         known = basic_map_divs_known(bmap);
3779         if (known < 0)
3780                 goto error;
3781         if (known)
3782                 return isl_map_from_basic_map(bmap);
3783
3784         map = compute_divs(bmap);
3785         return map;
3786 error:
3787         isl_basic_map_free(bmap);
3788         return NULL;
3789 }
3790
3791 struct isl_map *isl_map_compute_divs(struct isl_map *map)
3792 {
3793         int i;
3794         int known;
3795         struct isl_map *res;
3796
3797         if (!map)
3798                 return NULL;
3799         if (map->n == 0)
3800                 return map;
3801
3802         known = map_divs_known(map);
3803         if (known < 0) {
3804                 isl_map_free(map);
3805                 return NULL;
3806         }
3807         if (known)
3808                 return map;
3809
3810         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
3811         for (i = 1 ; i < map->n; ++i) {
3812                 struct isl_map *r2;
3813                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
3814                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
3815                         res = isl_map_union_disjoint(res, r2);
3816                 else
3817                         res = isl_map_union(res, r2);
3818         }
3819         isl_map_free(map);
3820
3821         return res;
3822 }
3823
3824 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
3825 {
3826         return (struct isl_set *)
3827                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
3828 }
3829
3830 struct isl_set *isl_set_compute_divs(struct isl_set *set)
3831 {
3832         return (struct isl_set *)
3833                 isl_map_compute_divs((struct isl_map *)set);
3834 }
3835
3836 struct isl_set *isl_map_domain(struct isl_map *map)
3837 {
3838         int i;
3839         struct isl_set *set;
3840
3841         if (!map)
3842                 goto error;
3843
3844         map = isl_map_cow(map);
3845         if (!map)
3846                 return NULL;
3847
3848         set = (struct isl_set *)map;
3849         set->dim = isl_dim_domain(set->dim);
3850         if (!set->dim)
3851                 goto error;
3852         for (i = 0; i < map->n; ++i) {
3853                 set->p[i] = isl_basic_map_domain(map->p[i]);
3854                 if (!set->p[i])
3855                         goto error;
3856         }
3857         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3858         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3859         return set;
3860 error:
3861         isl_map_free(map);
3862         return NULL;
3863 }
3864
3865 struct isl_map *isl_map_union_disjoint(
3866                         struct isl_map *map1, struct isl_map *map2)
3867 {
3868         int i;
3869         unsigned flags = 0;
3870         struct isl_map *map = NULL;
3871
3872         if (!map1 || !map2)
3873                 goto error;
3874
3875         if (map1->n == 0) {
3876                 isl_map_free(map1);
3877                 return map2;
3878         }
3879         if (map2->n == 0) {
3880                 isl_map_free(map2);
3881                 return map1;
3882         }
3883
3884         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
3885
3886         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
3887             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
3888                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
3889
3890         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
3891                                 map1->n + map2->n, flags);
3892         if (!map)
3893                 goto error;
3894         for (i = 0; i < map1->n; ++i) {
3895                 map = isl_map_add(map,
3896                                   isl_basic_map_copy(map1->p[i]));
3897                 if (!map)
3898                         goto error;
3899         }
3900         for (i = 0; i < map2->n; ++i) {
3901                 map = isl_map_add(map,
3902                                   isl_basic_map_copy(map2->p[i]));
3903                 if (!map)
3904                         goto error;
3905         }
3906         isl_map_free(map1);
3907         isl_map_free(map2);
3908         return map;
3909 error:
3910         isl_map_free(map);
3911         isl_map_free(map1);
3912         isl_map_free(map2);
3913         return NULL;
3914 }
3915
3916 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
3917 {
3918         map1 = isl_map_union_disjoint(map1, map2);
3919         if (!map1)
3920                 return NULL;
3921         if (map1->n > 1)
3922                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
3923         return map1;
3924 }
3925
3926 struct isl_set *isl_set_union_disjoint(
3927                         struct isl_set *set1, struct isl_set *set2)
3928 {
3929         return (struct isl_set *)
3930                 isl_map_union_disjoint(
3931                         (struct isl_map *)set1, (struct isl_map *)set2);
3932 }
3933
3934 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
3935 {
3936         return (struct isl_set *)
3937                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
3938 }
3939
3940 struct isl_map *isl_map_intersect_range(
3941                 struct isl_map *map, struct isl_set *set)
3942 {
3943         unsigned flags = 0;
3944         struct isl_map *result;
3945         int i, j;
3946
3947         if (!map || !set)
3948                 goto error;
3949
3950         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
3951             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
3952                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
3953
3954         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
3955                                         map->n * set->n, flags);
3956         if (!result)
3957                 goto error;
3958         for (i = 0; i < map->n; ++i)
3959                 for (j = 0; j < set->n; ++j) {
3960                         result = isl_map_add(result,
3961                             isl_basic_map_intersect_range(
3962                                 isl_basic_map_copy(map->p[i]),
3963                                 isl_basic_set_copy(set->p[j])));
3964                         if (!result)
3965                                 goto error;
3966                 }
3967         isl_map_free(map);
3968         isl_set_free(set);
3969         return result;
3970 error:
3971         isl_map_free(map);
3972         isl_set_free(set);
3973         return NULL;
3974 }
3975
3976 struct isl_map *isl_map_intersect_domain(
3977                 struct isl_map *map, struct isl_set *set)
3978 {
3979         return isl_map_reverse(
3980                 isl_map_intersect_range(isl_map_reverse(map), set));
3981 }
3982
3983 struct isl_map *isl_map_apply_domain(
3984                 struct isl_map *map1, struct isl_map *map2)
3985 {
3986         if (!map1 || !map2)
3987                 goto error;
3988         map1 = isl_map_reverse(map1);
3989         map1 = isl_map_apply_range(map1, map2);
3990         return isl_map_reverse(map1);
3991 error:
3992         isl_map_free(map1);
3993         isl_map_free(map2);
3994         return NULL;
3995 }
3996
3997 struct isl_map *isl_map_apply_range(
3998                 struct isl_map *map1, struct isl_map *map2)
3999 {
4000         struct isl_dim *dim_result;
4001         struct isl_map *result;
4002         int i, j;
4003
4004         if (!map1 || !map2)
4005                 goto error;
4006
4007         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4008                                   isl_dim_copy(map2->dim));
4009
4010         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4011         if (!result)
4012                 goto error;
4013         for (i = 0; i < map1->n; ++i)
4014                 for (j = 0; j < map2->n; ++j) {
4015                         result = isl_map_add(result,
4016                             isl_basic_map_apply_range(
4017                                 isl_basic_map_copy(map1->p[i]),
4018                                 isl_basic_map_copy(map2->p[j])));
4019                         if (!result)
4020                                 goto error;
4021                 }
4022         isl_map_free(map1);
4023         isl_map_free(map2);
4024         if (result && result->n <= 1)
4025                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4026         return result;
4027 error:
4028         isl_map_free(map1);
4029         isl_map_free(map2);
4030         return NULL;
4031 }
4032
4033 /*
4034  * returns range - domain
4035  */
4036 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4037 {
4038         struct isl_basic_set *bset;
4039         unsigned dim;
4040         unsigned nparam;
4041         int i;
4042
4043         if (!bmap)
4044                 goto error;
4045         dim = isl_basic_map_n_in(bmap);
4046         nparam = isl_basic_map_n_param(bmap);
4047         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4048         bset = isl_basic_set_from_basic_map(bmap);
4049         bset = isl_basic_set_cow(bset);
4050         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
4051         bset = isl_basic_set_swap_vars(bset, 2*dim);
4052         for (i = 0; i < dim; ++i) {
4053                 int j = isl_basic_map_alloc_equality(
4054                                             (struct isl_basic_map *)bset);
4055                 if (j < 0)
4056                         goto error;
4057                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4058                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4059                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4060                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4061         }
4062         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4063 error:
4064         isl_basic_map_free(bmap);
4065         return NULL;
4066 }
4067
4068 /*
4069  * returns range - domain
4070  */
4071 struct isl_set *isl_map_deltas(struct isl_map *map)
4072 {
4073         int i;
4074         struct isl_set *result;
4075
4076         if (!map)
4077                 return NULL;
4078
4079         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4080         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
4081                                         isl_map_n_in(map), map->n, map->flags);
4082         if (!result)
4083                 goto error;
4084         for (i = 0; i < map->n; ++i)
4085                 result = isl_set_add(result,
4086                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4087         isl_map_free(map);
4088         return result;
4089 error:
4090         isl_map_free(map);
4091         return NULL;
4092 }
4093
4094 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4095 {
4096         struct isl_basic_map *bmap;
4097         unsigned nparam;
4098         unsigned dim;
4099         int i;
4100
4101         if (!dims)
4102                 return NULL;
4103
4104         nparam = dims->nparam;
4105         dim = dims->n_out;
4106         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4107         if (!bmap)
4108                 goto error;
4109
4110         for (i = 0; i < dim; ++i) {
4111                 int j = isl_basic_map_alloc_equality(bmap);
4112                 if (j < 0)
4113                         goto error;
4114                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4115                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
4116                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
4117         }
4118         return isl_basic_map_finalize(bmap);
4119 error:
4120         isl_basic_map_free(bmap);
4121         return NULL;
4122 }
4123
4124 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
4125 {
4126         struct isl_dim *dim = isl_dim_map(set_dim);
4127         if (!dim)
4128                 return NULL;
4129         return basic_map_identity(dim);
4130 }
4131
4132 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
4133 {
4134         if (!model || !model->dim)
4135                 return NULL;
4136         isl_assert(model->ctx,
4137                         model->dim->n_in == model->dim->n_out, return NULL);
4138         return basic_map_identity(isl_dim_copy(model->dim));
4139 }
4140
4141 static struct isl_map *map_identity(struct isl_dim *dim)
4142 {
4143         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
4144         return isl_map_add(map, basic_map_identity(isl_dim_copy(dim)));
4145 }
4146
4147 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
4148 {
4149         struct isl_dim *dim = isl_dim_map(set_dim);
4150         if (!dim)
4151                 return NULL;
4152         return map_identity(dim);
4153 }
4154
4155 struct isl_map *isl_map_identity_like(struct isl_map *model)
4156 {
4157         if (!model || !model->dim)
4158                 return NULL;
4159         isl_assert(model->ctx,
4160                         model->dim->n_in == model->dim->n_out, return NULL);
4161         return map_identity(isl_dim_copy(model->dim));
4162 }
4163
4164 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
4165 {
4166         if (!model || !model->dim)
4167                 return NULL;
4168         isl_assert(model->ctx,
4169                         model->dim->n_in == model->dim->n_out, return NULL);
4170         return map_identity(isl_dim_copy(model->dim));
4171 }
4172
4173 /* Construct a basic set with all set dimensions having only non-negative
4174  * values.
4175  */
4176 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
4177 {
4178         int i;
4179         unsigned nparam;
4180         unsigned dim;
4181         struct isl_basic_set *bset;
4182
4183         if (!dims)
4184                 return NULL;
4185         nparam = dims->nparam;
4186         dim = dims->n_out;
4187         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
4188         if (!bset)
4189                 return NULL;
4190         for (i = 0; i < dim; ++i) {
4191                 int k = isl_basic_set_alloc_inequality(bset);
4192                 if (k < 0)
4193                         goto error;
4194                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
4195                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
4196         }
4197         return bset;
4198 error:
4199         isl_basic_set_free(bset);
4200         return NULL;
4201 }
4202
4203 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
4204 {
4205         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
4206 }
4207
4208 int isl_basic_map_is_subset(
4209                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4210 {
4211         int is_subset;
4212         struct isl_map *map1;
4213         struct isl_map *map2;
4214
4215         if (!bmap1 || !bmap2)
4216                 return -1;
4217
4218         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
4219         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
4220
4221         is_subset = isl_map_is_subset(map1, map2);
4222
4223         isl_map_free(map1);
4224         isl_map_free(map2);
4225
4226         return is_subset;
4227 }
4228
4229 int isl_basic_map_is_equal(
4230                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4231 {
4232         int is_subset;
4233
4234         if (!bmap1 || !bmap2)
4235                 return -1;
4236         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4237         if (is_subset != 1)
4238                 return is_subset;
4239         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4240         return is_subset;
4241 }
4242
4243 int isl_basic_set_is_equal(
4244                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4245 {
4246         return isl_basic_map_is_equal(
4247                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4248 }
4249
4250 int isl_map_is_empty(struct isl_map *map)
4251 {
4252         int i;
4253         int is_empty;
4254
4255         if (!map)
4256                 return -1;
4257         for (i = 0; i < map->n; ++i) {
4258                 is_empty = isl_basic_map_is_empty(map->p[i]);
4259                 if (is_empty < 0)
4260                         return -1;
4261                 if (!is_empty)
4262                         return 0;
4263         }
4264         return 1;
4265 }
4266
4267 int isl_map_fast_is_empty(struct isl_map *map)
4268 {
4269         return map->n == 0;
4270 }
4271
4272 int isl_set_fast_is_empty(struct isl_set *set)
4273 {
4274         return set->n == 0;
4275 }
4276
4277 int isl_set_is_empty(struct isl_set *set)
4278 {
4279         return isl_map_is_empty((struct isl_map *)set);
4280 }
4281
4282 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4283 {
4284         int is_subset;
4285
4286         if (!map1 || !map2)
4287                 return -1;
4288         is_subset = isl_map_is_subset(map1, map2);
4289         if (is_subset != 1)
4290                 return is_subset;
4291         is_subset = isl_map_is_subset(map2, map1);
4292         return is_subset;
4293 }
4294
4295 int isl_basic_map_is_strict_subset(
4296                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4297 {
4298         int is_subset;
4299
4300         if (!bmap1 || !bmap2)
4301                 return -1;
4302         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4303         if (is_subset != 1)
4304                 return is_subset;
4305         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4306         if (is_subset == -1)
4307                 return is_subset;
4308         return !is_subset;
4309 }
4310
4311 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
4312 {
4313         int is_subset;
4314
4315         if (!map1 || !map2)
4316                 return -1;
4317         is_subset = isl_map_is_subset(map1, map2);
4318         if (is_subset != 1)
4319                 return is_subset;
4320         is_subset = isl_map_is_subset(map2, map1);
4321         if (is_subset == -1)
4322                 return is_subset;
4323         return !is_subset;
4324 }
4325
4326 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
4327 {
4328         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
4329 }
4330
4331 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4332 {
4333         if (!bmap)
4334                 return -1;
4335         return bmap->n_eq == 0 && bmap->n_ineq == 0;
4336 }
4337
4338 int isl_basic_set_is_universe(struct isl_basic_set *bset)
4339 {
4340         if (!bset)
4341                 return -1;
4342         return bset->n_eq == 0 && bset->n_ineq == 0;
4343 }
4344
4345 int isl_map_fast_is_universe(__isl_keep isl_map *map)
4346 {
4347         if (!map)
4348                 return -1;
4349
4350         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
4351 }
4352
4353 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4354 {
4355         struct isl_basic_set *bset = NULL;
4356         struct isl_vec *sample = NULL;
4357         int empty;
4358         unsigned total;
4359
4360         if (!bmap)
4361                 return -1;
4362
4363         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4364                 return 1;
4365
4366         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4367                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4368                 copy = isl_basic_map_convex_hull(copy);
4369                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4370                 isl_basic_map_free(copy);
4371                 return empty;
4372         }
4373
4374         total = 1 + isl_basic_map_total_dim(bmap);
4375         if (bmap->sample && bmap->sample->size == total) {
4376                 int contains = isl_basic_map_contains(bmap, bmap->sample);
4377                 if (contains < 0)
4378                         return -1;
4379                 if (contains)
4380                         return 0;
4381         }
4382         isl_vec_free(bmap->sample);
4383         bmap->sample = NULL;
4384         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4385         if (!bset)
4386                 return -1;
4387         sample = isl_basic_set_sample_vec(bset);
4388         if (!sample)
4389                 return -1;
4390         empty = sample->size == 0;
4391         isl_vec_free(bmap->sample);
4392         bmap->sample = sample;
4393         if (empty)
4394                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
4395
4396         return empty;
4397 }
4398
4399 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
4400 {
4401         if (!bmap)
4402                 return -1;
4403         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
4404 }
4405
4406 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
4407 {
4408         if (!bset)
4409                 return -1;
4410         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
4411 }
4412
4413 int isl_basic_set_is_empty(struct isl_basic_set *bset)
4414 {
4415         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
4416 }
4417
4418 struct isl_map *isl_basic_map_union(
4419         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4420 {
4421         struct isl_map *map;
4422         if (!bmap1 || !bmap2)
4423                 return NULL;
4424
4425         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
4426
4427         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
4428         if (!map)
4429                 goto error;
4430         map = isl_map_add(map, bmap1);
4431         map = isl_map_add(map, bmap2);
4432         return map;
4433 error:
4434         isl_basic_map_free(bmap1);
4435         isl_basic_map_free(bmap2);
4436         return NULL;
4437 }
4438
4439 struct isl_set *isl_basic_set_union(
4440                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4441 {
4442         return (struct isl_set *)isl_basic_map_union(
4443                                             (struct isl_basic_map *)bset1,
4444                                             (struct isl_basic_map *)bset2);
4445 }
4446
4447 /* Order divs such that any div only depends on previous divs */
4448 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
4449 {
4450         int i;
4451         unsigned off = isl_dim_total(bmap->dim);
4452
4453         for (i = 0; i < bmap->n_div; ++i) {
4454                 int pos;
4455                 if (isl_int_is_zero(bmap->div[i][0]))
4456                         continue;
4457                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
4458                                                             bmap->n_div-i);
4459                 if (pos == -1)
4460                         continue;
4461                 isl_basic_map_swap_div(bmap, i, i + pos);
4462                 --i;
4463         }
4464         return bmap;
4465 }
4466
4467 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
4468 {
4469         return (struct isl_basic_set *)
4470                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
4471 }
4472
4473 /* Look for a div in dst that corresponds to the div "div" in src.
4474  * The divs before "div" in src and dst are assumed to be the same.
4475  *
4476  * Returns -1 if no corresponding div was found and the position
4477  * of the corresponding div in dst otherwise.
4478  */
4479 static int find_div(struct isl_basic_map *dst,
4480                         struct isl_basic_map *src, unsigned div)
4481 {
4482         int i;
4483
4484         unsigned total = isl_dim_total(src->dim);
4485
4486         isl_assert(dst->ctx, div <= dst->n_div, return -1);
4487         for (i = div; i < dst->n_div; ++i)
4488                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
4489                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
4490                                                 dst->n_div - div) == -1)
4491                         return i;
4492         return -1;
4493 }
4494
4495 struct isl_basic_map *isl_basic_map_align_divs(
4496                 struct isl_basic_map *dst, struct isl_basic_map *src)
4497 {
4498         int i;
4499         unsigned total = isl_dim_total(src->dim);
4500
4501         if (!dst || !src)
4502                 goto error;
4503
4504         if (src->n_div == 0)
4505                 return dst;
4506
4507         for (i = 0; i < src->n_div; ++i)
4508                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
4509
4510         src = isl_basic_map_order_divs(src);
4511         dst = isl_basic_map_cow(dst);
4512         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
4513                         src->n_div, 0, 2 * src->n_div);
4514         if (!dst)
4515                 return NULL;
4516         for (i = 0; i < src->n_div; ++i) {
4517                 int j = find_div(dst, src, i);
4518                 if (j < 0) {
4519                         j = isl_basic_map_alloc_div(dst);
4520                         if (j < 0)
4521                                 goto error;
4522                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
4523                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
4524                         if (add_div_constraints(dst, j) < 0)
4525                                 goto error;
4526                 }
4527                 if (j != i)
4528                         isl_basic_map_swap_div(dst, i, j);
4529         }
4530         return dst;
4531 error:
4532         isl_basic_map_free(dst);
4533         return NULL;
4534 }
4535
4536 struct isl_basic_set *isl_basic_set_align_divs(
4537                 struct isl_basic_set *dst, struct isl_basic_set *src)
4538 {
4539         return (struct isl_basic_set *)isl_basic_map_align_divs(
4540                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
4541 }
4542
4543 struct isl_map *isl_map_align_divs(struct isl_map *map)
4544 {
4545         int i;
4546
4547         if (!map)
4548                 return NULL;
4549         if (map->n == 0)
4550                 return map;
4551         map = isl_map_compute_divs(map);
4552         map = isl_map_cow(map);
4553         if (!map)
4554                 return NULL;
4555
4556         for (i = 1; i < map->n; ++i)
4557                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
4558         for (i = 1; i < map->n; ++i)
4559                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
4560
4561         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4562         return map;
4563 }
4564
4565 struct isl_set *isl_set_align_divs(struct isl_set *set)
4566 {
4567         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
4568 }
4569
4570 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
4571 {
4572         if (!set || !map)
4573                 goto error;
4574         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
4575         map = isl_map_intersect_domain(map, set);
4576         set = isl_map_range(map);
4577         return set;
4578 error:
4579         isl_set_free(set);
4580         isl_map_free(map);
4581         return NULL;
4582 }
4583
4584 /* There is no need to cow as removing empty parts doesn't change
4585  * the meaning of the set.
4586  */
4587 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
4588 {
4589         int i;
4590
4591         if (!map)
4592                 return NULL;
4593
4594         for (i = map->n-1; i >= 0; --i) {
4595                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
4596                         continue;
4597                 isl_basic_map_free(map->p[i]);
4598                 if (i != map->n-1) {
4599                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4600                         map->p[i] = map->p[map->n-1];
4601                 }
4602                 map->n--;
4603         }
4604
4605         return map;
4606 }
4607
4608 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
4609 {
4610         return (struct isl_set *)
4611                 isl_map_remove_empty_parts((struct isl_map *)set);
4612 }
4613
4614 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
4615 {
4616         struct isl_basic_map *bmap;
4617         if (!map || map->n == 0)
4618                 return NULL;
4619         bmap = map->p[map->n-1];
4620         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
4621         return isl_basic_map_copy(bmap);
4622 }
4623
4624 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
4625 {
4626         return (struct isl_basic_set *)
4627                 isl_map_copy_basic_map((struct isl_map *)set);
4628 }
4629
4630 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
4631                                                 __isl_keep isl_basic_map *bmap)
4632 {
4633         int i;
4634
4635         if (!map || !bmap)
4636                 goto error;
4637         for (i = map->n-1; i >= 0; --i) {
4638                 if (map->p[i] != bmap)
4639                         continue;
4640                 map = isl_map_cow(map);
4641                 if (!map)
4642                         goto error;
4643                 isl_basic_map_free(map->p[i]);
4644                 if (i != map->n-1) {
4645                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
4646                         map->p[i] = map->p[map->n-1];
4647                 }
4648                 map->n--;
4649                 return map;
4650         }
4651         return map;
4652 error:
4653         isl_map_free(map);
4654         return NULL;
4655 }
4656
4657 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
4658                                                 struct isl_basic_set *bset)
4659 {
4660         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
4661                                                 (struct isl_basic_map *)bset);
4662 }
4663
4664 /* Given two basic sets bset1 and bset2, compute the maximal difference
4665  * between the values of dimension pos in bset1 and those in bset2
4666  * for any common value of the parameters and dimensions preceding pos.
4667  */
4668 static enum isl_lp_result basic_set_maximal_difference_at(
4669         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
4670         int pos, isl_int *opt)
4671 {
4672         struct isl_dim *dims;
4673         struct isl_basic_map *bmap1 = NULL;
4674         struct isl_basic_map *bmap2 = NULL;
4675         struct isl_ctx *ctx;
4676         struct isl_vec *obj;
4677         unsigned total;
4678         unsigned nparam;
4679         unsigned dim1, dim2;
4680         enum isl_lp_result res;
4681
4682         if (!bset1 || !bset2)
4683                 return isl_lp_error;
4684
4685         nparam = isl_basic_set_n_param(bset1);
4686         dim1 = isl_basic_set_n_dim(bset1);
4687         dim2 = isl_basic_set_n_dim(bset2);
4688         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
4689         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
4690         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
4691         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
4692         if (!bmap1 || !bmap2)
4693                 goto error;
4694         bmap1 = isl_basic_map_cow(bmap1);
4695         bmap1 = isl_basic_map_extend(bmap1, nparam,
4696                         pos, (dim1 - pos) + (dim2 - pos),
4697                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
4698         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
4699         if (!bmap1)
4700                 goto error;
4701         total = isl_basic_map_total_dim(bmap1);
4702         ctx = bmap1->ctx;
4703         obj = isl_vec_alloc(ctx, 1 + total);
4704         isl_seq_clr(obj->block.data, 1 + total);
4705         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
4706         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
4707         if (!obj)
4708                 goto error;
4709         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
4710                                         opt, NULL, NULL);
4711         isl_basic_map_free(bmap1);
4712         isl_vec_free(obj);
4713         return res;
4714 error:
4715         isl_basic_map_free(bmap1);
4716         isl_basic_map_free(bmap2);
4717         return isl_lp_error;
4718 }
4719
4720 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
4721  * for any common value of the parameters and dimensions preceding pos
4722  * in both basic sets, the values of dimension pos in bset1 are
4723  * smaller or larger than those in bset2.
4724  *
4725  * Returns
4726  *       1 if bset1 follows bset2
4727  *      -1 if bset1 precedes bset2
4728  *       0 if bset1 and bset2 are incomparable
4729  *      -2 if some error occurred.
4730  */
4731 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
4732         struct isl_basic_set *bset2, int pos)
4733 {
4734         isl_int opt;
4735         enum isl_lp_result res;
4736         int cmp;
4737
4738         isl_int_init(opt);
4739
4740         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
4741
4742         if (res == isl_lp_empty)
4743                 cmp = 0;
4744         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
4745                   res == isl_lp_unbounded)
4746                 cmp = 1;
4747         else if (res == isl_lp_ok && isl_int_is_neg(opt))
4748                 cmp = -1;
4749         else
4750                 cmp = -2;
4751
4752         isl_int_clear(opt);
4753         return cmp;
4754 }
4755
4756 /* Given two basic sets bset1 and bset2, check whether
4757  * for any common value of the parameters and dimensions preceding pos
4758  * there is a value of dimension pos in bset1 that is larger
4759  * than a value of the same dimension in bset2.
4760  *
4761  * Return
4762  *       1 if there exists such a pair
4763  *       0 if there is no such pair, but there is a pair of equal values
4764  *      -1 otherwise
4765  *      -2 if some error occurred.
4766  */
4767 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
4768         __isl_keep isl_basic_set *bset2, int pos)
4769 {
4770         isl_int opt;
4771         enum isl_lp_result res;
4772         int cmp;
4773
4774         isl_int_init(opt);
4775
4776         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
4777
4778         if (res == isl_lp_empty)
4779                 cmp = -1;
4780         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
4781                   res == isl_lp_unbounded)
4782                 cmp = 1;
4783         else if (res == isl_lp_ok && isl_int_is_neg(opt))
4784                 cmp = -1;
4785         else if (res == isl_lp_ok)
4786                 cmp = 0;
4787         else
4788                 cmp = -2;
4789
4790         isl_int_clear(opt);
4791         return cmp;
4792 }
4793
4794 /* Given two sets set1 and set2, check whether
4795  * for any common value of the parameters and dimensions preceding pos
4796  * there is a value of dimension pos in set1 that is larger
4797  * than a value of the same dimension in set2.
4798  *
4799  * Return
4800  *       1 if there exists such a pair
4801  *       0 if there is no such pair, but there is a pair of equal values
4802  *      -1 otherwise
4803  *      -2 if some error occurred.
4804  */
4805 int isl_set_follows_at(__isl_keep isl_set *set1,
4806         __isl_keep isl_set *set2, int pos)
4807 {
4808         int i, j;
4809         int follows = -1;
4810
4811         if (!set1 || !set2)
4812                 return -2;
4813
4814         for (i = 0; i < set1->n; ++i)
4815                 for (j = 0; j < set2->n; ++j) {
4816                         int f;
4817                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
4818                         if (f == 1 || f == -2)
4819                                 return f;
4820                         if (f > follows)
4821                                 follows = f;
4822                 }
4823
4824         return follows;
4825 }
4826
4827 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
4828         unsigned pos, isl_int *val)
4829 {
4830         int i;
4831         int d;
4832         unsigned total;
4833
4834         if (!bmap)
4835                 return -1;
4836         total = isl_basic_map_total_dim(bmap);
4837         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
4838                 for (; d+1 > pos; --d)
4839                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
4840                                 break;
4841                 if (d != pos)
4842                         continue;
4843                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
4844                         return 0;
4845                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
4846                         return 0;
4847                 if (!isl_int_is_one(bmap->eq[i][1+d]))
4848                         return 0;
4849                 if (val)
4850                         isl_int_neg(*val, bmap->eq[i][0]);
4851                 return 1;
4852         }
4853         return 0;
4854 }
4855
4856 static int isl_map_fast_has_fixed_var(struct isl_map *map,
4857         unsigned pos, isl_int *val)
4858 {
4859         int i;
4860         isl_int v;
4861         isl_int tmp;
4862         int fixed;
4863
4864         if (!map)
4865                 return -1;
4866         if (map->n == 0)
4867                 return 0;
4868         if (map->n == 1)
4869                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
4870         isl_int_init(v);
4871         isl_int_init(tmp);
4872         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
4873         for (i = 1; fixed == 1 && i < map->n; ++i) {
4874                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
4875                 if (fixed == 1 && isl_int_ne(tmp, v))
4876                         fixed = 0;
4877         }
4878         if (val)
4879                 isl_int_set(*val, v);
4880         isl_int_clear(tmp);
4881         isl_int_clear(v);
4882         return fixed;
4883 }
4884
4885 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
4886         unsigned pos, isl_int *val)
4887 {
4888         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
4889                                                 pos, val);
4890 }
4891
4892 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
4893         isl_int *val)
4894 {
4895         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
4896 }
4897
4898 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
4899         enum isl_dim_type type, unsigned pos, isl_int *val)
4900 {
4901         if (pos >= isl_basic_map_dim(bmap, type))
4902                 return -1;
4903         return isl_basic_map_fast_has_fixed_var(bmap,
4904                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
4905 }
4906
4907 int isl_map_fast_is_fixed(struct isl_map *map,
4908         enum isl_dim_type type, unsigned pos, isl_int *val)
4909 {
4910         if (pos >= isl_map_dim(map, type))
4911                 return -1;
4912         return isl_map_fast_has_fixed_var(map,
4913                 map_offset(map, type) - 1 + pos, val);
4914 }
4915
4916 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4917  * then return this fixed value in *val.
4918  */
4919 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
4920         isl_int *val)
4921 {
4922         return isl_basic_set_fast_has_fixed_var(bset,
4923                                         isl_basic_set_n_param(bset) + dim, val);
4924 }
4925
4926 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4927  * then return this fixed value in *val.
4928  */
4929 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
4930 {
4931         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
4932 }
4933
4934 /* Check if input variable in has fixed value and if so and if val is not NULL,
4935  * then return this fixed value in *val.
4936  */
4937 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
4938 {
4939         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
4940 }
4941
4942 /* Check if dimension dim has an (obvious) fixed lower bound and if so
4943  * and if val is not NULL, then return this lower bound in *val.
4944  */
4945 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
4946         unsigned dim, isl_int *val)
4947 {
4948         int i, i_eq = -1, i_ineq = -1;
4949         isl_int *c;
4950         unsigned total;
4951         unsigned nparam;
4952
4953         if (!bset)
4954                 return -1;
4955         total = isl_basic_set_total_dim(bset);
4956         nparam = isl_basic_set_n_param(bset);
4957         for (i = 0; i < bset->n_eq; ++i) {
4958                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
4959                         continue;
4960                 if (i_eq != -1)
4961                         return 0;
4962                 i_eq = i;
4963         }
4964         for (i = 0; i < bset->n_ineq; ++i) {
4965                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
4966                         continue;
4967                 if (i_eq != -1 || i_ineq != -1)
4968                         return 0;
4969                 i_ineq = i;
4970         }
4971         if (i_eq == -1 && i_ineq == -1)
4972                 return 0;
4973         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
4974         /* The coefficient should always be one due to normalization. */
4975         if (!isl_int_is_one(c[1+nparam+dim]))
4976                 return 0;
4977         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
4978                 return 0;
4979         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
4980                                         total - nparam - dim - 1) != -1)
4981                 return 0;
4982         if (val)
4983                 isl_int_neg(*val, c[0]);
4984         return 1;
4985 }
4986
4987 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
4988         unsigned dim, isl_int *val)
4989 {
4990         int i;
4991         isl_int v;
4992         isl_int tmp;
4993         int fixed;
4994
4995         if (!set)
4996                 return -1;
4997         if (set->n == 0)
4998                 return 0;
4999         if (set->n == 1)
5000                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5001                                                                 dim, val);
5002         isl_int_init(v);
5003         isl_int_init(tmp);
5004         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5005                                                                 dim, &v);
5006         for (i = 1; fixed == 1 && i < set->n; ++i) {
5007                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5008                                                                 dim, &tmp);
5009                 if (fixed == 1 && isl_int_ne(tmp, v))
5010                         fixed = 0;
5011         }
5012         if (val)
5013                 isl_int_set(*val, v);
5014         isl_int_clear(tmp);
5015         isl_int_clear(v);
5016         return fixed;
5017 }
5018
5019 struct constraint {
5020         unsigned        size;
5021         isl_int         *c;
5022 };
5023
5024 static int qsort_constraint_cmp(const void *p1, const void *p2)
5025 {
5026         const struct constraint *c1 = (const struct constraint *)p1;
5027         const struct constraint *c2 = (const struct constraint *)p2;
5028         unsigned size = isl_min(c1->size, c2->size);
5029         return isl_seq_cmp(c1->c, c2->c, size);
5030 }
5031
5032 static struct isl_basic_map *isl_basic_map_sort_constraints(
5033         struct isl_basic_map *bmap)
5034 {
5035         int i;
5036         struct constraint *c;
5037         unsigned total;
5038
5039         if (!bmap)
5040                 return NULL;
5041         total = isl_basic_map_total_dim(bmap);
5042         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5043         if (!c)
5044                 goto error;
5045         for (i = 0; i < bmap->n_ineq; ++i) {
5046                 c[i].size = total;
5047                 c[i].c = bmap->ineq[i];
5048         }
5049         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5050         for (i = 0; i < bmap->n_ineq; ++i)
5051                 bmap->ineq[i] = c[i].c;
5052         free(c);
5053         return bmap;
5054 error:
5055         isl_basic_map_free(bmap);
5056         return NULL;
5057 }
5058
5059 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5060 {
5061         if (!bmap)
5062                 return NULL;
5063         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5064                 return bmap;
5065         bmap = isl_basic_map_convex_hull(bmap);
5066         bmap = isl_basic_map_sort_constraints(bmap);
5067         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5068         return bmap;
5069 }
5070
5071 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5072 {
5073         return (struct isl_basic_set *)isl_basic_map_normalize(
5074                                                 (struct isl_basic_map *)bset);
5075 }
5076
5077 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5078         const struct isl_basic_map *bmap2)
5079 {
5080         int i, cmp;
5081         unsigned total;
5082
5083         if (bmap1 == bmap2)
5084                 return 0;
5085         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5086                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5087         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5088                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5089         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5090                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5091         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5092             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5093                 return 0;
5094         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5095                 return 1;
5096         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5097                 return -1;
5098         if (bmap1->n_eq != bmap2->n_eq)
5099                 return bmap1->n_eq - bmap2->n_eq;
5100         if (bmap1->n_ineq != bmap2->n_ineq)
5101                 return bmap1->n_ineq - bmap2->n_ineq;
5102         if (bmap1->n_div != bmap2->n_div)
5103                 return bmap1->n_div - bmap2->n_div;
5104         total = isl_basic_map_total_dim(bmap1);
5105         for (i = 0; i < bmap1->n_eq; ++i) {
5106                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5107                 if (cmp)
5108                         return cmp;
5109         }
5110         for (i = 0; i < bmap1->n_ineq; ++i) {
5111                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5112                 if (cmp)
5113                         return cmp;
5114         }
5115         for (i = 0; i < bmap1->n_div; ++i) {
5116                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5117                 if (cmp)
5118                         return cmp;
5119         }
5120         return 0;
5121 }
5122
5123 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5124         struct isl_basic_map *bmap2)
5125 {
5126         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5127 }
5128
5129 static int qsort_bmap_cmp(const void *p1, const void *p2)
5130 {
5131         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5132         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5133
5134         return isl_basic_map_fast_cmp(bmap1, bmap2);
5135 }
5136
5137 /* We normalize in place, but if anything goes wrong we need
5138  * to return NULL, so we need to make sure we don't change the
5139  * meaning of any possible other copies of map.
5140  */
5141 struct isl_map *isl_map_normalize(struct isl_map *map)
5142 {
5143         int i, j;
5144         struct isl_basic_map *bmap;
5145
5146         if (!map)
5147                 return NULL;
5148         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
5149                 return map;
5150         for (i = 0; i < map->n; ++i) {
5151                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5152                 if (!bmap)
5153                         goto error;
5154                 isl_basic_map_free(map->p[i]);
5155                 map->p[i] = bmap;
5156         }
5157         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5158         ISL_F_SET(map, ISL_MAP_NORMALIZED);
5159         map = isl_map_remove_empty_parts(map);
5160         if (!map)
5161                 return NULL;
5162         for (i = map->n - 1; i >= 1; --i) {
5163                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5164                         continue;
5165                 isl_basic_map_free(map->p[i-1]);
5166                 for (j = i; j < map->n; ++j)
5167                         map->p[j-1] = map->p[j];
5168                 map->n--;
5169         }
5170         return map;
5171 error:
5172         isl_map_free(map);
5173         return NULL;
5174
5175 }
5176
5177 struct isl_set *isl_set_normalize(struct isl_set *set)
5178 {
5179         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5180 }
5181
5182 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5183 {
5184         int i;
5185         int equal;
5186
5187         if (!map1 || !map2)
5188                 return -1;
5189
5190         if (map1 == map2)
5191                 return 1;
5192         if (!isl_dim_equal(map1->dim, map2->dim))
5193                 return 0;
5194
5195         map1 = isl_map_copy(map1);
5196         map2 = isl_map_copy(map2);
5197         map1 = isl_map_normalize(map1);
5198         map2 = isl_map_normalize(map2);
5199         if (!map1 || !map2)
5200                 goto error;
5201         equal = map1->n == map2->n;
5202         for (i = 0; equal && i < map1->n; ++i) {
5203                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5204                 if (equal < 0)
5205                         goto error;
5206         }
5207         isl_map_free(map1);
5208         isl_map_free(map2);
5209         return equal;
5210 error:
5211         isl_map_free(map1);
5212         isl_map_free(map2);
5213         return -1;
5214 }
5215
5216 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5217 {
5218         return isl_map_fast_is_equal((struct isl_map *)set1,
5219                                                 (struct isl_map *)set2);
5220 }
5221
5222 /* Return an interval that ranges from min to max (inclusive)
5223  */
5224 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5225         isl_int min, isl_int max)
5226 {
5227         int k;
5228         struct isl_basic_set *bset = NULL;
5229
5230         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5231         if (!bset)
5232                 goto error;
5233
5234         k = isl_basic_set_alloc_inequality(bset);
5235         if (k < 0)
5236                 goto error;
5237         isl_int_set_si(bset->ineq[k][1], 1);
5238         isl_int_neg(bset->ineq[k][0], min);
5239
5240         k = isl_basic_set_alloc_inequality(bset);
5241         if (k < 0)
5242                 goto error;
5243         isl_int_set_si(bset->ineq[k][1], -1);
5244         isl_int_set(bset->ineq[k][0], max);
5245
5246         return bset;
5247 error:
5248         isl_basic_set_free(bset);
5249         return NULL;
5250 }
5251
5252 /* Return the Cartesian product of the basic sets in list (in the given order).
5253  */
5254 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5255 {
5256         int i;
5257         unsigned dim;
5258         unsigned nparam;
5259         unsigned extra;
5260         unsigned n_eq;
5261         unsigned n_ineq;
5262         struct isl_basic_set *product = NULL;
5263
5264         if (!list)
5265                 goto error;
5266         isl_assert(list->ctx, list->n > 0, goto error);
5267         isl_assert(list->ctx, list->p[0], goto error);
5268         nparam = isl_basic_set_n_param(list->p[0]);
5269         dim = isl_basic_set_n_dim(list->p[0]);
5270         extra = list->p[0]->n_div;
5271         n_eq = list->p[0]->n_eq;
5272         n_ineq = list->p[0]->n_ineq;
5273         for (i = 1; i < list->n; ++i) {
5274                 isl_assert(list->ctx, list->p[i], goto error);
5275                 isl_assert(list->ctx,
5276                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5277                 dim += isl_basic_set_n_dim(list->p[i]);
5278                 extra += list->p[i]->n_div;
5279                 n_eq += list->p[i]->n_eq;
5280                 n_ineq += list->p[i]->n_ineq;
5281         }
5282         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5283                                         n_eq, n_ineq);
5284         if (!product)
5285                 goto error;
5286         dim = 0;
5287         for (i = 0; i < list->n; ++i) {
5288                 isl_basic_set_add_constraints(product,
5289                                         isl_basic_set_copy(list->p[i]), dim);
5290                 dim += isl_basic_set_n_dim(list->p[i]);
5291         }
5292         isl_basic_set_list_free(list);
5293         return product;
5294 error:
5295         isl_basic_set_free(product);
5296         isl_basic_set_list_free(list);
5297         return NULL;
5298 }
5299
5300 struct isl_basic_map *isl_basic_map_product(
5301                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5302 {
5303         struct isl_dim *dim_result = NULL;
5304         struct isl_basic_map *bmap;
5305         unsigned in1, in2, out1, out2, nparam, total, pos;
5306         struct isl_dim_map *dim_map1, *dim_map2;
5307
5308         if (!bmap1 || !bmap2)
5309                 goto error;
5310
5311         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
5312                                      bmap2->dim, isl_dim_param), goto error);
5313         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
5314                                                    isl_dim_copy(bmap2->dim));
5315
5316         in1 = isl_basic_map_n_in(bmap1);
5317         in2 = isl_basic_map_n_in(bmap2);
5318         out1 = isl_basic_map_n_out(bmap1);
5319         out2 = isl_basic_map_n_out(bmap2);
5320         nparam = isl_basic_map_n_param(bmap1);
5321
5322         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
5323         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
5324         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
5325         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
5326         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
5327         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
5328         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
5329         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
5330         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
5331         isl_dim_map_div(dim_map1, bmap1, pos += out2);
5332         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
5333
5334         bmap = isl_basic_map_alloc_dim(dim_result,
5335                         bmap1->n_div + bmap2->n_div,
5336                         bmap1->n_eq + bmap2->n_eq,
5337                         bmap1->n_ineq + bmap2->n_ineq);
5338         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
5339         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
5340         bmap = isl_basic_map_simplify(bmap);
5341         return isl_basic_map_finalize(bmap);
5342 error:
5343         isl_basic_map_free(bmap1);
5344         isl_basic_map_free(bmap2);
5345         return NULL;
5346 }
5347
5348 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
5349  */
5350 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
5351 {
5352         unsigned flags = 0;
5353         struct isl_map *result;
5354         int i, j;
5355
5356         if (!map1 || !map2)
5357                 goto error;
5358
5359         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
5360                                          map2->dim, isl_dim_param), goto error);
5361
5362         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
5363             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
5364                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
5365
5366         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
5367                                                    isl_dim_copy(map2->dim)),
5368                                 map1->n * map2->n, flags);
5369         if (!result)
5370                 goto error;
5371         for (i = 0; i < map1->n; ++i)
5372                 for (j = 0; j < map2->n; ++j) {
5373                         struct isl_basic_map *part;
5374                         part = isl_basic_map_product(
5375                                     isl_basic_map_copy(map1->p[i]),
5376                                     isl_basic_map_copy(map2->p[j]));
5377                         if (isl_basic_map_is_empty(part))
5378                                 isl_basic_map_free(part);
5379                         else
5380                                 result = isl_map_add(result, part);
5381                         if (!result)
5382                                 goto error;
5383                 }
5384         isl_map_free(map1);
5385         isl_map_free(map2);
5386         return result;
5387 error:
5388         isl_map_free(map1);
5389         isl_map_free(map2);
5390         return NULL;
5391 }
5392
5393 /* Given two set A and B, construct its Cartesian product A x B.
5394  */
5395 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
5396 {
5397         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
5398                                                  (struct isl_map *)set2);
5399 }
5400
5401 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5402 {
5403         int i;
5404         uint32_t hash = isl_hash_init();
5405         unsigned total;
5406
5407         if (!bset)
5408                 return 0;
5409         bset = isl_basic_set_copy(bset);
5410         bset = isl_basic_set_normalize(bset);
5411         if (!bset)
5412                 return 0;
5413         total = isl_basic_set_total_dim(bset);
5414         isl_hash_byte(hash, bset->n_eq & 0xFF);
5415         for (i = 0; i < bset->n_eq; ++i) {
5416                 uint32_t c_hash;
5417                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5418                 isl_hash_hash(hash, c_hash);
5419         }
5420         isl_hash_byte(hash, bset->n_ineq & 0xFF);
5421         for (i = 0; i < bset->n_ineq; ++i) {
5422                 uint32_t c_hash;
5423                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
5424                 isl_hash_hash(hash, c_hash);
5425         }
5426         isl_hash_byte(hash, bset->n_div & 0xFF);
5427         for (i = 0; i < bset->n_div; ++i) {
5428                 uint32_t c_hash;
5429                 if (isl_int_is_zero(bset->div[i][0]))
5430                         continue;
5431                 isl_hash_byte(hash, i & 0xFF);
5432                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
5433                 isl_hash_hash(hash, c_hash);
5434         }
5435         isl_basic_set_free(bset);
5436         return hash;
5437 }
5438
5439 uint32_t isl_set_get_hash(struct isl_set *set)
5440 {
5441         int i;
5442         uint32_t hash;
5443
5444         if (!set)
5445                 return 0;
5446         set = isl_set_copy(set);
5447         set = isl_set_normalize(set);
5448         if (!set)
5449                 return 0;
5450
5451         hash = isl_hash_init();
5452         for (i = 0; i < set->n; ++i) {
5453                 uint32_t bset_hash;
5454                 bset_hash = isl_basic_set_get_hash(set->p[i]);
5455                 isl_hash_hash(hash, bset_hash);
5456         }
5457
5458         isl_set_free(set);
5459
5460         return hash;
5461 }
5462
5463 /* Check if the value for dimension dim is completely determined
5464  * by the values of the other parameters and variables.
5465  * That is, check if dimension dim is involved in an equality.
5466  */
5467 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
5468 {
5469         int i;
5470         unsigned nparam;
5471
5472         if (!bset)
5473                 return -1;
5474         nparam = isl_basic_set_n_param(bset);
5475         for (i = 0; i < bset->n_eq; ++i)
5476                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
5477                         return 1;
5478         return 0;
5479 }
5480
5481 /* Check if the value for dimension dim is completely determined
5482  * by the values of the other parameters and variables.
5483  * That is, check if dimension dim is involved in an equality
5484  * for each of the subsets.
5485  */
5486 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
5487 {
5488         int i;
5489
5490         if (!set)
5491                 return -1;
5492         for (i = 0; i < set->n; ++i) {
5493                 int unique;
5494                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
5495                 if (unique != 1)
5496                         return unique;
5497         }
5498         return 1;
5499 }
5500
5501 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
5502         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
5503 {
5504         int i;
5505
5506         if (!map)
5507                 return -1;
5508
5509         for (i = 0; i < map->n; ++i)
5510                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
5511                         return -1;
5512
5513         return 0;
5514 }
5515
5516 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
5517         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
5518 {
5519         int i;
5520
5521         if (!set)
5522                 return -1;
5523
5524         for (i = 0; i < set->n; ++i)
5525                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
5526                         return -1;
5527
5528         return 0;
5529 }
5530
5531 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
5532 {
5533         struct isl_dim *dim;
5534         struct isl_basic_map *bmap;
5535         unsigned n_set;
5536         unsigned n_div;
5537         unsigned n_param;
5538         unsigned total;
5539         int i, k, l;
5540
5541         set = isl_set_align_divs(set);
5542
5543         if (!set)
5544                 return NULL;
5545
5546         dim = isl_set_get_dim(set);
5547         if (set->n == 0 || set->p[0]->n_div == 0) {
5548                 isl_set_free(set);
5549                 return isl_map_identity(dim);
5550         }
5551
5552         n_div = set->p[0]->n_div;
5553         dim = isl_dim_map(dim);
5554         n_param = isl_dim_size(dim, isl_dim_param);
5555         n_set = isl_dim_size(dim, isl_dim_in);
5556         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
5557         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
5558         for (i = 0; i < n_set; ++i)
5559                 bmap = var_equal(bmap, i);
5560
5561         total = n_param + n_set + n_set + n_div;
5562         for (i = 0; i < n_div; ++i) {
5563                 k = isl_basic_map_alloc_inequality(bmap);
5564                 if (k < 0)
5565                         goto error;
5566                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
5567                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
5568                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
5569                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
5570                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
5571                             set->p[0]->div[i][0]);
5572
5573                 l = isl_basic_map_alloc_inequality(bmap);
5574                 if (l < 0)
5575                         goto error;
5576                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
5577                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
5578                             set->p[0]->div[i][0]);
5579                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
5580         }
5581
5582         isl_set_free(set);
5583         return isl_map_from_basic_map(bmap);
5584 error:
5585         isl_set_free(set);
5586         isl_basic_map_free(bmap);
5587         return NULL;
5588 }
5589
5590 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
5591 {
5592         unsigned dim;
5593         int size = 0;
5594
5595         if (!bset)
5596                 return -1;
5597
5598         dim = isl_basic_set_total_dim(bset);
5599         size += bset->n_eq * (1 + dim);
5600         size += bset->n_ineq * (1 + dim);
5601         size += bset->n_div * (2 + dim);
5602
5603         return size;
5604 }
5605
5606 int isl_set_size(__isl_keep isl_set *set)
5607 {
5608         int i;
5609         int size = 0;
5610
5611         if (!set)
5612                 return -1;
5613
5614         for (i = 0; i < set->n; ++i)
5615                 size += isl_basic_set_size(set->p[i]);
5616
5617         return size;
5618 }