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