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 _disjoint_ basic sets bset1 and bset2, check whether
4658  * for any common value of the parameters and dimensions preceding dim
4659  * in both basic sets, the values of dimension pos in bset1 are
4660  * smaller or larger than those in bset2.
4661  *
4662  * Returns
4663  *       1 if bset1 follows bset2
4664  *      -1 if bset1 precedes bset2
4665  *       0 if bset1 and bset2 are incomparable
4666  *      -2 if some error occurred.
4667  */
4668 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
4669         struct isl_basic_set *bset2, int pos)
4670 {
4671         struct isl_dim *dims;
4672         struct isl_basic_map *bmap1 = NULL;
4673         struct isl_basic_map *bmap2 = NULL;
4674         struct isl_ctx *ctx;
4675         struct isl_vec *obj;
4676         unsigned total;
4677         unsigned nparam;
4678         unsigned dim1, dim2;
4679         isl_int num, den;
4680         enum isl_lp_result res;
4681         int cmp;
4682
4683         if (!bset1 || !bset2)
4684                 return -2;
4685
4686         nparam = isl_basic_set_n_param(bset1);
4687         dim1 = isl_basic_set_n_dim(bset1);
4688         dim2 = isl_basic_set_n_dim(bset2);
4689         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
4690         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
4691         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
4692         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
4693         if (!bmap1 || !bmap2)
4694                 goto error;
4695         bmap1 = isl_basic_map_cow(bmap1);
4696         bmap1 = isl_basic_map_extend(bmap1, nparam,
4697                         pos, (dim1 - pos) + (dim2 - pos),
4698                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
4699         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
4700         if (!bmap1)
4701                 goto error;
4702         total = isl_basic_map_total_dim(bmap1);
4703         ctx = bmap1->ctx;
4704         obj = isl_vec_alloc(ctx, 1 + total);
4705         isl_seq_clr(obj->block.data, 1 + total);
4706         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
4707         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
4708         if (!obj)
4709                 goto error;
4710         isl_int_init(num);
4711         isl_int_init(den);
4712         res = isl_basic_map_solve_lp(bmap1, 0, obj->block.data, ctx->one,
4713                                         &num, &den, NULL);
4714         if (res == isl_lp_empty)
4715                 cmp = 0;
4716         else if (res == isl_lp_ok && isl_int_is_pos(num))
4717                 cmp = 1;
4718         else if ((res == isl_lp_ok && isl_int_is_neg(num)) ||
4719                   res == isl_lp_unbounded)
4720                 cmp = -1;
4721         else
4722                 cmp = -2;
4723         isl_int_clear(num);
4724         isl_int_clear(den);
4725         isl_basic_map_free(bmap1);
4726         isl_vec_free(obj);
4727         return cmp;
4728 error:
4729         isl_basic_map_free(bmap1);
4730         isl_basic_map_free(bmap2);
4731         return -2;
4732 }
4733
4734 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
4735         unsigned pos, isl_int *val)
4736 {
4737         int i;
4738         int d;
4739         unsigned total;
4740
4741         if (!bmap)
4742                 return -1;
4743         total = isl_basic_map_total_dim(bmap);
4744         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
4745                 for (; d+1 > pos; --d)
4746                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
4747                                 break;
4748                 if (d != pos)
4749                         continue;
4750                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
4751                         return 0;
4752                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
4753                         return 0;
4754                 if (!isl_int_is_one(bmap->eq[i][1+d]))
4755                         return 0;
4756                 if (val)
4757                         isl_int_neg(*val, bmap->eq[i][0]);
4758                 return 1;
4759         }
4760         return 0;
4761 }
4762
4763 static int isl_map_fast_has_fixed_var(struct isl_map *map,
4764         unsigned pos, isl_int *val)
4765 {
4766         int i;
4767         isl_int v;
4768         isl_int tmp;
4769         int fixed;
4770
4771         if (!map)
4772                 return -1;
4773         if (map->n == 0)
4774                 return 0;
4775         if (map->n == 1)
4776                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
4777         isl_int_init(v);
4778         isl_int_init(tmp);
4779         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
4780         for (i = 1; fixed == 1 && i < map->n; ++i) {
4781                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
4782                 if (fixed == 1 && isl_int_ne(tmp, v))
4783                         fixed = 0;
4784         }
4785         if (val)
4786                 isl_int_set(*val, v);
4787         isl_int_clear(tmp);
4788         isl_int_clear(v);
4789         return fixed;
4790 }
4791
4792 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
4793         unsigned pos, isl_int *val)
4794 {
4795         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
4796                                                 pos, val);
4797 }
4798
4799 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
4800         isl_int *val)
4801 {
4802         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
4803 }
4804
4805 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
4806         enum isl_dim_type type, unsigned pos, isl_int *val)
4807 {
4808         if (pos >= isl_basic_map_dim(bmap, type))
4809                 return -1;
4810         return isl_basic_map_fast_has_fixed_var(bmap,
4811                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
4812 }
4813
4814 int isl_map_fast_is_fixed(struct isl_map *map,
4815         enum isl_dim_type type, unsigned pos, isl_int *val)
4816 {
4817         if (pos >= isl_map_dim(map, type))
4818                 return -1;
4819         return isl_map_fast_has_fixed_var(map,
4820                 map_offset(map, type) - 1 + pos, val);
4821 }
4822
4823 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4824  * then return this fixed value in *val.
4825  */
4826 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
4827         isl_int *val)
4828 {
4829         return isl_basic_set_fast_has_fixed_var(bset,
4830                                         isl_basic_set_n_param(bset) + dim, val);
4831 }
4832
4833 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4834  * then return this fixed value in *val.
4835  */
4836 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
4837 {
4838         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
4839 }
4840
4841 /* Check if input variable in has fixed value and if so and if val is not NULL,
4842  * then return this fixed value in *val.
4843  */
4844 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
4845 {
4846         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
4847 }
4848
4849 /* Check if dimension dim has an (obvious) fixed lower bound and if so
4850  * and if val is not NULL, then return this lower bound in *val.
4851  */
4852 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
4853         unsigned dim, isl_int *val)
4854 {
4855         int i, i_eq = -1, i_ineq = -1;
4856         isl_int *c;
4857         unsigned total;
4858         unsigned nparam;
4859
4860         if (!bset)
4861                 return -1;
4862         total = isl_basic_set_total_dim(bset);
4863         nparam = isl_basic_set_n_param(bset);
4864         for (i = 0; i < bset->n_eq; ++i) {
4865                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
4866                         continue;
4867                 if (i_eq != -1)
4868                         return 0;
4869                 i_eq = i;
4870         }
4871         for (i = 0; i < bset->n_ineq; ++i) {
4872                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
4873                         continue;
4874                 if (i_eq != -1 || i_ineq != -1)
4875                         return 0;
4876                 i_ineq = i;
4877         }
4878         if (i_eq == -1 && i_ineq == -1)
4879                 return 0;
4880         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
4881         /* The coefficient should always be one due to normalization. */
4882         if (!isl_int_is_one(c[1+nparam+dim]))
4883                 return 0;
4884         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
4885                 return 0;
4886         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
4887                                         total - nparam - dim - 1) != -1)
4888                 return 0;
4889         if (val)
4890                 isl_int_neg(*val, c[0]);
4891         return 1;
4892 }
4893
4894 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
4895         unsigned dim, isl_int *val)
4896 {
4897         int i;
4898         isl_int v;
4899         isl_int tmp;
4900         int fixed;
4901
4902         if (!set)
4903                 return -1;
4904         if (set->n == 0)
4905                 return 0;
4906         if (set->n == 1)
4907                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4908                                                                 dim, val);
4909         isl_int_init(v);
4910         isl_int_init(tmp);
4911         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4912                                                                 dim, &v);
4913         for (i = 1; fixed == 1 && i < set->n; ++i) {
4914                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
4915                                                                 dim, &tmp);
4916                 if (fixed == 1 && isl_int_ne(tmp, v))
4917                         fixed = 0;
4918         }
4919         if (val)
4920                 isl_int_set(*val, v);
4921         isl_int_clear(tmp);
4922         isl_int_clear(v);
4923         return fixed;
4924 }
4925
4926 struct constraint {
4927         unsigned        size;
4928         isl_int         *c;
4929 };
4930
4931 static int qsort_constraint_cmp(const void *p1, const void *p2)
4932 {
4933         const struct constraint *c1 = (const struct constraint *)p1;
4934         const struct constraint *c2 = (const struct constraint *)p2;
4935         unsigned size = isl_min(c1->size, c2->size);
4936         return isl_seq_cmp(c1->c, c2->c, size);
4937 }
4938
4939 static struct isl_basic_map *isl_basic_map_sort_constraints(
4940         struct isl_basic_map *bmap)
4941 {
4942         int i;
4943         struct constraint *c;
4944         unsigned total;
4945
4946         if (!bmap)
4947                 return NULL;
4948         total = isl_basic_map_total_dim(bmap);
4949         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
4950         if (!c)
4951                 goto error;
4952         for (i = 0; i < bmap->n_ineq; ++i) {
4953                 c[i].size = total;
4954                 c[i].c = bmap->ineq[i];
4955         }
4956         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
4957         for (i = 0; i < bmap->n_ineq; ++i)
4958                 bmap->ineq[i] = c[i].c;
4959         free(c);
4960         return bmap;
4961 error:
4962         isl_basic_map_free(bmap);
4963         return NULL;
4964 }
4965
4966 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
4967 {
4968         if (!bmap)
4969                 return NULL;
4970         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
4971                 return bmap;
4972         bmap = isl_basic_map_convex_hull(bmap);
4973         bmap = isl_basic_map_sort_constraints(bmap);
4974         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
4975         return bmap;
4976 }
4977
4978 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
4979 {
4980         return (struct isl_basic_set *)isl_basic_map_normalize(
4981                                                 (struct isl_basic_map *)bset);
4982 }
4983
4984 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
4985         const struct isl_basic_map *bmap2)
4986 {
4987         int i, cmp;
4988         unsigned total;
4989
4990         if (bmap1 == bmap2)
4991                 return 0;
4992         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
4993                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
4994         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
4995                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
4996         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
4997                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
4998         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
4999             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5000                 return 0;
5001         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5002                 return 1;
5003         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5004                 return -1;
5005         if (bmap1->n_eq != bmap2->n_eq)
5006                 return bmap1->n_eq - bmap2->n_eq;
5007         if (bmap1->n_ineq != bmap2->n_ineq)
5008                 return bmap1->n_ineq - bmap2->n_ineq;
5009         if (bmap1->n_div != bmap2->n_div)
5010                 return bmap1->n_div - bmap2->n_div;
5011         total = isl_basic_map_total_dim(bmap1);
5012         for (i = 0; i < bmap1->n_eq; ++i) {
5013                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5014                 if (cmp)
5015                         return cmp;
5016         }
5017         for (i = 0; i < bmap1->n_ineq; ++i) {
5018                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5019                 if (cmp)
5020                         return cmp;
5021         }
5022         for (i = 0; i < bmap1->n_div; ++i) {
5023                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5024                 if (cmp)
5025                         return cmp;
5026         }
5027         return 0;
5028 }
5029
5030 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5031         struct isl_basic_map *bmap2)
5032 {
5033         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5034 }
5035
5036 static int qsort_bmap_cmp(const void *p1, const void *p2)
5037 {
5038         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5039         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5040
5041         return isl_basic_map_fast_cmp(bmap1, bmap2);
5042 }
5043
5044 /* We normalize in place, but if anything goes wrong we need
5045  * to return NULL, so we need to make sure we don't change the
5046  * meaning of any possible other copies of map.
5047  */
5048 struct isl_map *isl_map_normalize(struct isl_map *map)
5049 {
5050         int i, j;
5051         struct isl_basic_map *bmap;
5052
5053         if (!map)
5054                 return NULL;
5055         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
5056                 return map;
5057         for (i = 0; i < map->n; ++i) {
5058                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5059                 if (!bmap)
5060                         goto error;
5061                 isl_basic_map_free(map->p[i]);
5062                 map->p[i] = bmap;
5063         }
5064         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5065         ISL_F_SET(map, ISL_MAP_NORMALIZED);
5066         map = isl_map_remove_empty_parts(map);
5067         if (!map)
5068                 return NULL;
5069         for (i = map->n - 1; i >= 1; --i) {
5070                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5071                         continue;
5072                 isl_basic_map_free(map->p[i-1]);
5073                 for (j = i; j < map->n; ++j)
5074                         map->p[j-1] = map->p[j];
5075                 map->n--;
5076         }
5077         return map;
5078 error:
5079         isl_map_free(map);
5080         return NULL;
5081
5082 }
5083
5084 struct isl_set *isl_set_normalize(struct isl_set *set)
5085 {
5086         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5087 }
5088
5089 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5090 {
5091         int i;
5092         int equal;
5093
5094         if (!map1 || !map2)
5095                 return -1;
5096
5097         if (map1 == map2)
5098                 return 1;
5099         if (!isl_dim_equal(map1->dim, map2->dim))
5100                 return 0;
5101
5102         map1 = isl_map_copy(map1);
5103         map2 = isl_map_copy(map2);
5104         map1 = isl_map_normalize(map1);
5105         map2 = isl_map_normalize(map2);
5106         if (!map1 || !map2)
5107                 goto error;
5108         equal = map1->n == map2->n;
5109         for (i = 0; equal && i < map1->n; ++i) {
5110                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5111                 if (equal < 0)
5112                         goto error;
5113         }
5114         isl_map_free(map1);
5115         isl_map_free(map2);
5116         return equal;
5117 error:
5118         isl_map_free(map1);
5119         isl_map_free(map2);
5120         return -1;
5121 }
5122
5123 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5124 {
5125         return isl_map_fast_is_equal((struct isl_map *)set1,
5126                                                 (struct isl_map *)set2);
5127 }
5128
5129 /* Return an interval that ranges from min to max (inclusive)
5130  */
5131 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5132         isl_int min, isl_int max)
5133 {
5134         int k;
5135         struct isl_basic_set *bset = NULL;
5136
5137         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5138         if (!bset)
5139                 goto error;
5140
5141         k = isl_basic_set_alloc_inequality(bset);
5142         if (k < 0)
5143                 goto error;
5144         isl_int_set_si(bset->ineq[k][1], 1);
5145         isl_int_neg(bset->ineq[k][0], min);
5146
5147         k = isl_basic_set_alloc_inequality(bset);
5148         if (k < 0)
5149                 goto error;
5150         isl_int_set_si(bset->ineq[k][1], -1);
5151         isl_int_set(bset->ineq[k][0], max);
5152
5153         return bset;
5154 error:
5155         isl_basic_set_free(bset);
5156         return NULL;
5157 }
5158
5159 /* Return the Cartesian product of the basic sets in list (in the given order).
5160  */
5161 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5162 {
5163         int i;
5164         unsigned dim;
5165         unsigned nparam;
5166         unsigned extra;
5167         unsigned n_eq;
5168         unsigned n_ineq;
5169         struct isl_basic_set *product = NULL;
5170
5171         if (!list)
5172                 goto error;
5173         isl_assert(list->ctx, list->n > 0, goto error);
5174         isl_assert(list->ctx, list->p[0], goto error);
5175         nparam = isl_basic_set_n_param(list->p[0]);
5176         dim = isl_basic_set_n_dim(list->p[0]);
5177         extra = list->p[0]->n_div;
5178         n_eq = list->p[0]->n_eq;
5179         n_ineq = list->p[0]->n_ineq;
5180         for (i = 1; i < list->n; ++i) {
5181                 isl_assert(list->ctx, list->p[i], goto error);
5182                 isl_assert(list->ctx,
5183                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
5184                 dim += isl_basic_set_n_dim(list->p[i]);
5185                 extra += list->p[i]->n_div;
5186                 n_eq += list->p[i]->n_eq;
5187                 n_ineq += list->p[i]->n_ineq;
5188         }
5189         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5190                                         n_eq, n_ineq);
5191         if (!product)
5192                 goto error;
5193         dim = 0;
5194         for (i = 0; i < list->n; ++i) {
5195                 isl_basic_set_add_constraints(product,
5196                                         isl_basic_set_copy(list->p[i]), dim);
5197                 dim += isl_basic_set_n_dim(list->p[i]);
5198         }
5199         isl_basic_set_list_free(list);
5200         return product;
5201 error:
5202         isl_basic_set_free(product);
5203         isl_basic_set_list_free(list);
5204         return NULL;
5205 }
5206
5207 struct isl_basic_map *isl_basic_map_product(
5208                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5209 {
5210         struct isl_dim *dim_result = NULL;
5211         struct isl_basic_map *bmap;
5212         unsigned in1, in2, out1, out2, nparam, total, pos;
5213         struct isl_dim_map *dim_map1, *dim_map2;
5214
5215         if (!bmap1 || !bmap2)
5216                 goto error;
5217
5218         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
5219                                      bmap2->dim, isl_dim_param), goto error);
5220         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
5221                                                    isl_dim_copy(bmap2->dim));
5222
5223         in1 = isl_basic_map_n_in(bmap1);
5224         in2 = isl_basic_map_n_in(bmap2);
5225         out1 = isl_basic_map_n_out(bmap1);
5226         out2 = isl_basic_map_n_out(bmap2);
5227         nparam = isl_basic_map_n_param(bmap1);
5228
5229         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
5230         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
5231         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
5232         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
5233         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
5234         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
5235         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
5236         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
5237         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
5238         isl_dim_map_div(dim_map1, bmap1, pos += out2);
5239         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
5240
5241         bmap = isl_basic_map_alloc_dim(dim_result,
5242                         bmap1->n_div + bmap2->n_div,
5243                         bmap1->n_eq + bmap2->n_eq,
5244                         bmap1->n_ineq + bmap2->n_ineq);
5245         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
5246         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
5247         bmap = isl_basic_map_simplify(bmap);
5248         return isl_basic_map_finalize(bmap);
5249 error:
5250         isl_basic_map_free(bmap1);
5251         isl_basic_map_free(bmap2);
5252         return NULL;
5253 }
5254
5255 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
5256  */
5257 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
5258 {
5259         unsigned flags = 0;
5260         struct isl_map *result;
5261         int i, j;
5262
5263         if (!map1 || !map2)
5264                 goto error;
5265
5266         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
5267                                          map2->dim, isl_dim_param), goto error);
5268
5269         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
5270             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
5271                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
5272
5273         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
5274                                                    isl_dim_copy(map2->dim)),
5275                                 map1->n * map2->n, flags);
5276         if (!result)
5277                 goto error;
5278         for (i = 0; i < map1->n; ++i)
5279                 for (j = 0; j < map2->n; ++j) {
5280                         struct isl_basic_map *part;
5281                         part = isl_basic_map_product(
5282                                     isl_basic_map_copy(map1->p[i]),
5283                                     isl_basic_map_copy(map2->p[j]));
5284                         if (isl_basic_map_is_empty(part))
5285                                 isl_basic_map_free(part);
5286                         else
5287                                 result = isl_map_add(result, part);
5288                         if (!result)
5289                                 goto error;
5290                 }
5291         isl_map_free(map1);
5292         isl_map_free(map2);
5293         return result;
5294 error:
5295         isl_map_free(map1);
5296         isl_map_free(map2);
5297         return NULL;
5298 }
5299
5300 /* Given two set A and B, construct its Cartesian product A x B.
5301  */
5302 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
5303 {
5304         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
5305                                                  (struct isl_map *)set2);
5306 }
5307
5308 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5309 {
5310         int i;
5311         uint32_t hash = isl_hash_init();
5312         unsigned total;
5313
5314         if (!bset)
5315                 return 0;
5316         bset = isl_basic_set_copy(bset);
5317         bset = isl_basic_set_normalize(bset);
5318         if (!bset)
5319                 return 0;
5320         total = isl_basic_set_total_dim(bset);
5321         isl_hash_byte(hash, bset->n_eq & 0xFF);
5322         for (i = 0; i < bset->n_eq; ++i) {
5323                 uint32_t c_hash;
5324                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5325                 isl_hash_hash(hash, c_hash);
5326         }
5327         isl_hash_byte(hash, bset->n_ineq & 0xFF);
5328         for (i = 0; i < bset->n_ineq; ++i) {
5329                 uint32_t c_hash;
5330                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
5331                 isl_hash_hash(hash, c_hash);
5332         }
5333         isl_hash_byte(hash, bset->n_div & 0xFF);
5334         for (i = 0; i < bset->n_div; ++i) {
5335                 uint32_t c_hash;
5336                 if (isl_int_is_zero(bset->div[i][0]))
5337                         continue;
5338                 isl_hash_byte(hash, i & 0xFF);
5339                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
5340                 isl_hash_hash(hash, c_hash);
5341         }
5342         isl_basic_set_free(bset);
5343         return hash;
5344 }
5345
5346 uint32_t isl_set_get_hash(struct isl_set *set)
5347 {
5348         int i;
5349         uint32_t hash;
5350
5351         if (!set)
5352                 return 0;
5353         set = isl_set_copy(set);
5354         set = isl_set_normalize(set);
5355         if (!set)
5356                 return 0;
5357
5358         hash = isl_hash_init();
5359         for (i = 0; i < set->n; ++i) {
5360                 uint32_t bset_hash;
5361                 bset_hash = isl_basic_set_get_hash(set->p[i]);
5362                 isl_hash_hash(hash, bset_hash);
5363         }
5364
5365         isl_set_free(set);
5366
5367         return hash;
5368 }
5369
5370 /* Check if the value for dimension dim is completely determined
5371  * by the values of the other parameters and variables.
5372  * That is, check if dimension dim is involved in an equality.
5373  */
5374 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
5375 {
5376         int i;
5377         unsigned nparam;
5378
5379         if (!bset)
5380                 return -1;
5381         nparam = isl_basic_set_n_param(bset);
5382         for (i = 0; i < bset->n_eq; ++i)
5383                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
5384                         return 1;
5385         return 0;
5386 }
5387
5388 /* Check if the value for dimension dim is completely determined
5389  * by the values of the other parameters and variables.
5390  * That is, check if dimension dim is involved in an equality
5391  * for each of the subsets.
5392  */
5393 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
5394 {
5395         int i;
5396
5397         if (!set)
5398                 return -1;
5399         for (i = 0; i < set->n; ++i) {
5400                 int unique;
5401                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
5402                 if (unique != 1)
5403                         return unique;
5404         }
5405         return 1;
5406 }
5407
5408 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
5409         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
5410 {
5411         int i;
5412
5413         if (!map)
5414                 return -1;
5415
5416         for (i = 0; i < map->n; ++i)
5417                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
5418                         return -1;
5419
5420         return 0;
5421 }
5422
5423 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
5424         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
5425 {
5426         int i;
5427
5428         if (!set)
5429                 return -1;
5430
5431         for (i = 0; i < set->n; ++i)
5432                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
5433                         return -1;
5434
5435         return 0;
5436 }
5437
5438 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
5439 {
5440         struct isl_dim *dim;
5441         struct isl_basic_map *bmap;
5442         unsigned n_set;
5443         unsigned n_div;
5444         unsigned n_param;
5445         unsigned total;
5446         int i, k, l;
5447
5448         set = isl_set_align_divs(set);
5449
5450         if (!set)
5451                 return NULL;
5452
5453         dim = isl_set_get_dim(set);
5454         if (set->n == 0 || set->p[0]->n_div == 0) {
5455                 isl_set_free(set);
5456                 return isl_map_identity(dim);
5457         }
5458
5459         n_div = set->p[0]->n_div;
5460         dim = isl_dim_map(dim);
5461         n_param = isl_dim_size(dim, isl_dim_param);
5462         n_set = isl_dim_size(dim, isl_dim_in);
5463         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
5464         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
5465         for (i = 0; i < n_set; ++i)
5466                 bmap = var_equal(bmap, i);
5467
5468         total = n_param + n_set + n_set + n_div;
5469         for (i = 0; i < n_div; ++i) {
5470                 k = isl_basic_map_alloc_inequality(bmap);
5471                 if (k < 0)
5472                         goto error;
5473                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
5474                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
5475                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
5476                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
5477                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
5478                             set->p[0]->div[i][0]);
5479
5480                 l = isl_basic_map_alloc_inequality(bmap);
5481                 if (l < 0)
5482                         goto error;
5483                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
5484                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
5485                             set->p[0]->div[i][0]);
5486                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
5487         }
5488
5489         isl_set_free(set);
5490         return isl_map_from_basic_map(bmap);
5491 error:
5492         isl_set_free(set);
5493         isl_basic_map_free(bmap);
5494         return NULL;
5495 }
5496
5497 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
5498 {
5499         unsigned dim;
5500         int size = 0;
5501
5502         if (!bset)
5503                 return -1;
5504
5505         dim = isl_basic_set_total_dim(bset);
5506         size += bset->n_eq * (1 + dim);
5507         size += bset->n_ineq * (1 + dim);
5508         size += bset->n_div * (2 + dim);
5509
5510         return size;
5511 }
5512
5513 int isl_set_size(__isl_keep isl_set *set)
5514 {
5515         int i;
5516         int size = 0;
5517
5518         if (!set)
5519                 return -1;
5520
5521         for (i = 0; i < set->n; ++i)
5522                 size += isl_basic_set_size(set->p[i]);
5523
5524         return size;
5525 }