isl_map.c

   1 #include <string.h>
   2 #include <strings.h>
   3 #include "isl_ctx.h"
   4 #include "isl_blk.h"
   5 #include "isl_dim.h"
   6 #include "isl_list.h"
   7 #include "isl_lp.h"
   8 #include "isl_seq.h"
   9 #include "isl_set.h"
  10 #include "isl_map.h"
  11 #include "isl_map_private.h"
  12 #include "isl_map_piplib.h"
  13 #include "isl_sample.h"
  14 #include "isl_vec.h"
  15
  16 /* Maps dst positions to src positions */
  17 struct isl_dim_map {
  18         unsigned len;
  19         int pos[1];
  20 };
  21
  22 static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
  23 {
  24         int i;
  25         struct isl_dim_map *dim_map;
  26         dim_map = isl_alloc(ctx, struct isl_dim_map,
  27                                 sizeof(struct isl_dim_map) + len * sizeof(int));
  28         if (!dim_map)
  29                 return NULL;
  30         dim_map->len = 1 + len;
  31         dim_map->pos[0] = 0;
  32         for (i = 0; i < len; ++i)
  33                 dim_map->pos[1 + i] = -1;
  34         return dim_map;
  35 }
  36
  37 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
  38 {
  39         switch (type) {
  40         case isl_dim_param:     return dim->nparam;
  41         case isl_dim_in:        return dim->n_in;
  42         case isl_dim_out:       return dim->n_out;
  43         }
  44 }
  45
  46 static unsigned pos(struct isl_dim *dim, enum isl_dim_type type)
  47 {
  48         switch (type) {
  49         case isl_dim_param:     return 1;
  50         case isl_dim_in:        return 1 + dim->nparam;
  51         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  52         }
  53 }
  54
  55 static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
  56                 enum isl_dim_type type, unsigned dst_pos)
  57 {
  58         int i;
  59         unsigned src_pos;
  60
  61         if (!dim_map || !dim)
  62                 return;
  63
  64         src_pos = pos(dim, type);
  65         for (i = 0; i < n(dim, type); ++i)
  66                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
  67 }
  68
  69 static void isl_dim_map_div(struct isl_dim_map *dim_map,
  70                 struct isl_basic_map *bmap, unsigned dst_pos)
  71 {
  72         int i;
  73         unsigned src_pos;
  74
  75         if (!dim_map || !bmap)
  76                 return;
  77
  78         src_pos = 1 + isl_dim_total(bmap->dim);
  79         for (i = 0; i < bmap->n_div; ++i)
  80                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
  81 }
  82
  83 static void isl_dim_map_dump(struct isl_dim_map *dim_map)
  84 {
  85         int i;
  86
  87         for (i = 0; i < dim_map->len; ++i)
  88                 fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
  89         fprintf(stderr, "\n");
  90 }
  91
  92 unsigned isl_basic_map_dim(const struct isl_basic_map *bmap,
  93                                 enum isl_dim_type type)
  94 {
  95         struct isl_dim *dim = bmap->dim;
  96         switch (type) {
  97         case isl_dim_param:
  98         case isl_dim_in:
  99         case isl_dim_out:       return isl_dim_size(bmap->dim, type);
 100         case isl_dim_div:       return bmap->n_div;
 101         case isl_dim_all:       return isl_basic_map_total_dim(bmap);
 102         }
 103 }
 104
 105 unsigned isl_map_dim(const struct isl_map *map, enum isl_dim_type type)
 106 {
 107         return n(map->dim, type);
 108 }
 109
 110 unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
 111                                         enum isl_dim_type type)
 112 {
 113         struct isl_dim *dim = bmap->dim;
 114         switch (type) {
 115         case isl_dim_param:     return 1;
 116         case isl_dim_in:        return 1 + dim->nparam;
 117         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 118         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 119         }
 120 }
 121
 122 static unsigned map_offset(struct isl_map *map, enum isl_dim_type type)
 123 {
 124         return pos(map->dim, type);
 125 }
 126
 127 unsigned isl_basic_set_dim(const struct isl_basic_set *bset,
 128                                 enum isl_dim_type type)
 129 {
 130         return isl_basic_map_dim((const struct isl_basic_map*)bset, type);
 131 }
 132
 133 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
 134 {
 135         return bset->dim->n_out;
 136 }
 137
 138 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
 139 {
 140         return bset->dim->nparam;
 141 }
 142
 143 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 144 {
 145         return isl_dim_total(bset->dim) + bset->n_div;
 146 }
 147
 148 unsigned isl_set_n_dim(const struct isl_set *set)
 149 {
 150         return set->dim->n_out;
 151 }
 152
 153 unsigned isl_set_n_param(const struct isl_set *set)
 154 {
 155         return set->dim->nparam;
 156 }
 157
 158 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
 159 {
 160         return bmap->dim->n_in;
 161 }
 162
 163 unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
 164 {
 165         return bmap->dim->n_out;
 166 }
 167
 168 unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
 169 {
 170         return bmap->dim->nparam;
 171 }
 172
 173 unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
 174 {
 175         return bmap->n_div;
 176 }
 177
 178 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
 179 {
 180         return isl_dim_total(bmap->dim) + bmap->n_div;
 181 }
 182
 183 unsigned isl_map_n_in(const struct isl_map *map)
 184 {
 185         return map->dim->n_in;
 186 }
 187
 188 unsigned isl_map_n_out(const struct isl_map *map)
 189 {
 190         return map->dim->n_out;
 191 }
 192
 193 unsigned isl_map_n_param(const struct isl_map *map)
 194 {
 195         return map->dim->nparam;
 196 }
 197
 198 int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
 199 {
 200         return map->dim->n_in == set->dim->n_out &&
 201                map->dim->nparam == set->dim->nparam;
 202 }
 203
 204 int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
 205                 struct isl_basic_set *bset)
 206 {
 207         return bmap->dim->n_in == bset->dim->n_out &&
 208                bmap->dim->nparam == bset->dim->nparam;
 209 }
 210
 211 int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
 212                 struct isl_basic_set *bset)
 213 {
 214         return bmap->dim->n_out == bset->dim->n_out &&
 215                bmap->dim->nparam == bset->dim->nparam;
 216 }
 217
 218 static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 219                 struct isl_basic_map *bmap, unsigned extra,
 220                 unsigned n_eq, unsigned n_ineq)
 221 {
 222         int i;
 223         size_t row_size = 1 + isl_dim_total(bmap->dim) + extra;
 224
 225         bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
 226         if (isl_blk_is_error(bmap->block)) {
 227                 free(bmap);
 228                 return NULL;
 229         }
 230
 231         bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
 232         if (!bmap->ineq) {
 233                 isl_blk_free(ctx, bmap->block);
 234                 free(bmap);
 235                 return NULL;
 236         }
 237
 238         if (extra == 0) {
 239                 bmap->block2 = isl_blk_empty();
 240                 bmap->div = NULL;
 241         } else {
 242                 bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
 243                 if (isl_blk_is_error(bmap->block2)) {
 244                         free(bmap->ineq);
 245                         isl_blk_free(ctx, bmap->block);
 246                         free(bmap);
 247                         return NULL;
 248                 }
 249
 250                 bmap->div = isl_alloc_array(ctx, isl_int *, extra);
 251                 if (!bmap->div) {
 252                         isl_blk_free(ctx, bmap->block2);
 253                         free(bmap->ineq);
 254                         isl_blk_free(ctx, bmap->block);
 255                         free(bmap);
 256                         return NULL;
 257                 }
 258         }
 259
 260         for (i = 0; i < n_ineq + n_eq; ++i)
 261                 bmap->ineq[i] = bmap->block.data + i * row_size;
 262
 263         for (i = 0; i < extra; ++i)
 264                 bmap->div[i] = bmap->block2.data + i * (1 + row_size);
 265
 266         bmap->ctx = ctx;
 267         isl_ctx_ref(ctx);
 268         bmap->ref = 1;
 269         bmap->flags = 0;
 270         bmap->c_size = n_eq + n_ineq;
 271         bmap->eq = bmap->ineq + n_ineq;
 272         bmap->extra = extra;
 273         bmap->n_eq = 0;
 274         bmap->n_ineq = 0;
 275         bmap->n_div = 0;
 276         bmap->sample = NULL;
 277
 278         return bmap;
 279 error:
 280         isl_basic_map_free(bmap);
 281         return NULL;
 282 }
 283
 284 struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
 285                 unsigned nparam, unsigned dim, unsigned extra,
 286                 unsigned n_eq, unsigned n_ineq)
 287 {
 288         struct isl_basic_map *bmap;
 289         bmap = isl_basic_map_alloc(ctx, nparam, 0, dim, extra, n_eq, n_ineq);
 290         return (struct isl_basic_set *)bmap;
 291 }
 292
 293 struct isl_basic_set *isl_basic_set_alloc_dim(struct isl_dim *dim,
 294                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 295 {
 296         struct isl_basic_map *bmap;
 297         if (!dim)
 298                 return NULL;
 299         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
 300         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 301         return (struct isl_basic_set *)bmap;
 302 }
 303
 304 struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_dim *dim,
 305                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 306 {
 307         struct isl_basic_map *bmap;
 308
 309         if (!dim)
 310                 return NULL;
 311         bmap = isl_alloc_type(dim->ctx, struct isl_basic_map);
 312         if (!bmap)
 313                 goto error;
 314         bmap->dim = dim;
 315
 316         return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
 317 error:
 318         isl_dim_free(dim);
 319         return NULL;
 320 }
 321
 322 struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
 323                 unsigned nparam, unsigned in, unsigned out, unsigned extra,
 324                 unsigned n_eq, unsigned n_ineq)
 325 {
 326         struct isl_basic_map *bmap;
 327         struct isl_dim *dim;
 328
 329         dim = isl_dim_alloc(ctx, nparam, in, out);
 330         if (!dim)
 331                 return NULL;
 332
 333         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 334         return bmap;
 335 }
 336
 337 static void dup_constraints(
 338                 struct isl_basic_map *dst, struct isl_basic_map *src)
 339 {
 340         int i;
 341         unsigned total = isl_basic_map_total_dim(src);
 342
 343         for (i = 0; i < src->n_eq; ++i) {
 344                 int j = isl_basic_map_alloc_equality(dst);
 345                 isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
 346         }
 347
 348         for (i = 0; i < src->n_ineq; ++i) {
 349                 int j = isl_basic_map_alloc_inequality(dst);
 350                 isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
 351         }
 352
 353         for (i = 0; i < src->n_div; ++i) {
 354                 int j = isl_basic_map_alloc_div(dst);
 355                 isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
 356         }
 357         ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
 358 }
 359
 360 struct isl_basic_map *isl_basic_map_dup(struct isl_basic_map *bmap)
 361 {
 362         struct isl_basic_map *dup;
 363
 364         if (!bmap)
 365                 return NULL;
 366         dup = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
 367                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
 368         if (!dup)
 369                 return NULL;
 370         dup->flags = bmap->flags;
 371         dup_constraints(dup, bmap);
 372         dup->sample = isl_vec_copy(bmap->ctx, bmap->sample);
 373         return dup;
 374 }
 375
 376 struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
 377 {
 378         struct isl_basic_map *dup;
 379
 380         dup = isl_basic_map_dup((struct isl_basic_map *)bset);
 381         return (struct isl_basic_set *)dup;
 382 }
 383
 384 struct isl_basic_set *isl_basic_set_copy(struct isl_basic_set *bset)
 385 {
 386         if (!bset)
 387                 return NULL;
 388
 389         if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
 390                 bset->ref++;
 391                 return bset;
 392         }
 393         return isl_basic_set_dup(bset);
 394 }
 395
 396 struct isl_set *isl_set_copy(struct isl_set *set)
 397 {
 398         if (!set)
 399                 return NULL;
 400
 401         set->ref++;
 402         return set;
 403 }
 404
 405 struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
 406 {
 407         if (!bmap)
 408                 return NULL;
 409
 410         if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
 411                 bmap->ref++;
 412                 return bmap;
 413         }
 414         return isl_basic_map_dup(bmap);
 415 }
 416
 417 struct isl_map *isl_map_copy(struct isl_map *map)
 418 {
 419         if (!map)
 420                 return NULL;
 421
 422         map->ref++;
 423         return map;
 424 }
 425
 426 void isl_basic_map_free(struct isl_basic_map *bmap)
 427 {
 428         if (!bmap)
 429                 return;
 430
 431         if (--bmap->ref > 0)
 432                 return;
 433
 434         isl_ctx_deref(bmap->ctx);
 435         free(bmap->div);
 436         isl_blk_free(bmap->ctx, bmap->block2);
 437         free(bmap->ineq);
 438         isl_blk_free(bmap->ctx, bmap->block);
 439         isl_vec_free(bmap->ctx, bmap->sample);
 440         isl_dim_free(bmap->dim);
 441         free(bmap);
 442 }
 443
 444 void isl_basic_set_free(struct isl_basic_set *bset)
 445 {
 446         isl_basic_map_free((struct isl_basic_map *)bset);
 447 }
 448
 449 int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
 450 {
 451         struct isl_ctx *ctx;
 452         if (!bmap)
 453                 return -1;
 454         ctx = bmap->ctx;
 455         isl_assert(ctx, bmap->n_eq + bmap->n_ineq < bmap->c_size, return -1);
 456         isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
 457                         return -1);
 458         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 459         if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
 460                 isl_int *t;
 461                 int j = isl_basic_map_alloc_inequality(bmap);
 462                 if (j < 0)
 463                         return -1;
 464                 t = bmap->ineq[j];
 465                 bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
 466                 bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
 467                 bmap->eq[-1] = t;
 468                 bmap->n_eq++;
 469                 bmap->n_ineq--;
 470                 bmap->eq--;
 471                 return 0;
 472         }
 473         isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
 474                       bmap->extra - bmap->n_div);
 475         return bmap->n_eq++;
 476 }
 477
 478 int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
 479 {
 480         return isl_basic_map_alloc_equality((struct isl_basic_map *)bset);
 481 }
 482
 483 int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
 484 {
 485         if (!bmap)
 486                 return -1;
 487         isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
 488         bmap->n_eq -= n;
 489         return 0;
 490 }
 491
 492 int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
 493 {
 494         isl_int *t;
 495         if (!bmap)
 496                 return -1;
 497         isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
 498
 499         if (pos != bmap->n_eq - 1) {
 500                 t = bmap->eq[pos];
 501                 bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
 502                 bmap->eq[bmap->n_eq - 1] = t;
 503         }
 504         bmap->n_eq--;
 505         return 0;
 506 }
 507
 508 int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos)
 509 {
 510         return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos);
 511 }
 512
 513 void isl_basic_map_inequality_to_equality(
 514                 struct isl_basic_map *bmap, unsigned pos)
 515 {
 516         isl_int *t;
 517
 518         t = bmap->ineq[pos];
 519         bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 520         bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
 521         bmap->eq[-1] = t;
 522         bmap->n_eq++;
 523         bmap->n_ineq--;
 524         bmap->eq--;
 525         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 526         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 527         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 528 }
 529
 530 int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap)
 531 {
 532         struct isl_ctx *ctx;
 533         if (!bmap)
 534                 return -1;
 535         ctx = bmap->ctx;
 536         isl_assert(ctx, bmap->n_ineq < bmap->eq - bmap->ineq, return -1);
 537         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
 538         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 539         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 540         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 541         isl_seq_clr(bmap->ineq[bmap->n_ineq] +
 542                       1 + isl_basic_map_total_dim(bmap),
 543                       bmap->extra - bmap->n_div);
 544         return bmap->n_ineq++;
 545 }
 546
 547 int isl_basic_set_alloc_inequality(struct isl_basic_set *bset)
 548 {
 549         return isl_basic_map_alloc_inequality((struct isl_basic_map *)bset);
 550 }
 551
 552 int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
 553 {
 554         if (!bmap)
 555                 return -1;
 556         isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
 557         bmap->n_ineq -= n;
 558         return 0;
 559 }
 560
 561 int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
 562 {
 563         return isl_basic_map_free_inequality((struct isl_basic_map *)bset, n);
 564 }
 565
 566 int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
 567 {
 568         isl_int *t;
 569         if (!bmap)
 570                 return -1;
 571         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
 572
 573         if (pos != bmap->n_ineq - 1) {
 574                 t = bmap->ineq[pos];
 575                 bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 576                 bmap->ineq[bmap->n_ineq - 1] = t;
 577                 ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 578         }
 579         bmap->n_ineq--;
 580         return 0;
 581 }
 582
 583 int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
 584 {
 585         return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos);
 586 }
 587
 588 int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
 589 {
 590         if (!bmap)
 591                 return -1;
 592         isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
 593         isl_seq_clr(bmap->div[bmap->n_div] +
 594                       1 + 1 + isl_basic_map_total_dim(bmap),
 595                       bmap->extra - bmap->n_div);
 596         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 597         return bmap->n_div++;
 598 }
 599
 600 int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
 601 {
 602         if (!bmap)
 603                 return -1;
 604         isl_assert(bmap->ctx, n <= bmap->n_div, return -1);
 605         bmap->n_div -= n;
 606         return 0;
 607 }
 608
 609 /* Copy constraint from src to dst, putting the vars of src at offset
 610  * dim_off in dst and the divs of src at offset div_off in dst.
 611  * If both sets are actually map, then dim_off applies to the input
 612  * variables.
 613  */
 614 static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
 615                             struct isl_basic_map *src_map, isl_int *src,
 616                             unsigned in_off, unsigned out_off, unsigned div_off)
 617 {
 618         unsigned src_nparam = isl_basic_map_n_param(src_map);
 619         unsigned dst_nparam = isl_basic_map_n_param(dst_map);
 620         unsigned src_in = isl_basic_map_n_in(src_map);
 621         unsigned dst_in = isl_basic_map_n_in(dst_map);
 622         unsigned src_out = isl_basic_map_n_out(src_map);
 623         unsigned dst_out = isl_basic_map_n_out(dst_map);
 624         isl_int_set(dst[0], src[0]);
 625         isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
 626         if (dst_nparam > src_nparam)
 627                 isl_seq_clr(dst+1+src_nparam,
 628                                 dst_nparam - src_nparam);
 629         isl_seq_clr(dst+1+dst_nparam, in_off);
 630         isl_seq_cpy(dst+1+dst_nparam+in_off,
 631                     src+1+src_nparam,
 632                     isl_min(dst_in-in_off, src_in));
 633         if (dst_in-in_off > src_in)
 634                 isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
 635                                 dst_in - in_off - src_in);
 636         isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
 637         isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
 638                     src+1+src_nparam+src_in,
 639                     isl_min(dst_out-out_off, src_out));
 640         if (dst_out-out_off > src_out)
 641                 isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
 642                                 dst_out - out_off - src_out);
 643         isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
 644         isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
 645                     src+1+src_nparam+src_in+src_out,
 646                     isl_min(dst_map->extra-div_off, src_map->n_div));
 647         if (dst_map->n_div-div_off > src_map->n_div)
 648                 isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
 649                                 div_off+src_map->n_div,
 650                                 dst_map->n_div - div_off - src_map->n_div);
 651 }
 652
 653 static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
 654                      struct isl_basic_map *src_map, isl_int *src,
 655                      unsigned in_off, unsigned out_off, unsigned div_off)
 656 {
 657         isl_int_set(dst[0], src[0]);
 658         copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
 659 }
 660
 661 static struct isl_basic_map *add_constraints(struct isl_basic_map *bmap1,
 662                 struct isl_basic_map *bmap2, unsigned i_pos, unsigned o_pos)
 663 {
 664         int i;
 665         unsigned div_off;
 666
 667         if (!bmap1 || !bmap2)
 668                 goto error;
 669
 670         div_off = bmap1->n_div;
 671
 672         for (i = 0; i < bmap2->n_eq; ++i) {
 673                 int i1 = isl_basic_map_alloc_equality(bmap1);
 674                 if (i1 < 0)
 675                         goto error;
 676                 copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
 677                                 i_pos, o_pos, div_off);
 678         }
 679
 680         for (i = 0; i < bmap2->n_ineq; ++i) {
 681                 int i1 = isl_basic_map_alloc_inequality(bmap1);
 682                 if (i1 < 0)
 683                         goto error;
 684                 copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
 685                                 i_pos, o_pos, div_off);
 686         }
 687
 688         for (i = 0; i < bmap2->n_div; ++i) {
 689                 int i1 = isl_basic_map_alloc_div(bmap1);
 690                 if (i1 < 0)
 691                         goto error;
 692                 copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
 693                          i_pos, o_pos, div_off);
 694         }
 695
 696         isl_basic_map_free(bmap2);
 697
 698         return bmap1;
 699
 700 error:
 701         isl_basic_map_free(bmap1);
 702         isl_basic_map_free(bmap2);
 703         return NULL;
 704 }
 705
 706 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
 707                                         struct isl_dim_map *dim_map)
 708 {
 709         int i;
 710
 711         for (i = 0; i < dim_map->len; ++i) {
 712                 if (dim_map->pos[i] < 0)
 713                         isl_int_set_si(dst[i], 0);
 714                 else
 715                         isl_int_set(dst[i], src[dim_map->pos[i]]);
 716         }
 717 }
 718
 719 static void copy_div_dim_map(isl_int *dst, isl_int *src,
 720                                         struct isl_dim_map *dim_map)
 721 {
 722         isl_int_set(dst[0], src[0]);
 723         copy_constraint_dim_map(dst+1, src+1, dim_map);
 724 }
 725
 726 static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst,
 727                 struct isl_basic_map *src, struct isl_dim_map *dim_map)
 728 {
 729         int i;
 730
 731         if (!src || !dst || !dim_map)
 732                 goto error;
 733
 734         for (i = 0; i < src->n_eq; ++i) {
 735                 int i1 = isl_basic_map_alloc_equality(dst);
 736                 if (i1 < 0)
 737                         goto error;
 738                 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
 739         }
 740
 741         for (i = 0; i < src->n_ineq; ++i) {
 742                 int i1 = isl_basic_map_alloc_inequality(dst);
 743                 if (i1 < 0)
 744                         goto error;
 745                 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
 746         }
 747
 748         for (i = 0; i < src->n_div; ++i) {
 749                 int i1 = isl_basic_map_alloc_div(dst);
 750                 if (i1 < 0)
 751                         goto error;
 752                 copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
 753         }
 754
 755         free(dim_map);
 756         isl_basic_map_free(src);
 757
 758         return dst;
 759 error:
 760         free(dim_map);
 761         isl_basic_map_free(src);
 762         isl_basic_map_free(dst);
 763         return NULL;
 764 }
 765
 766 struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
 767                 struct isl_basic_set *bset2, unsigned pos)
 768 {
 769         return (struct isl_basic_set *)
 770                 add_constraints((struct isl_basic_map *)bset1,
 771                                 (struct isl_basic_map *)bset2, 0, pos);
 772 }
 773
 774 struct isl_basic_map *isl_basic_map_extend_dim(struct isl_basic_map *base,
 775                 struct isl_dim *dim, unsigned extra,
 776                 unsigned n_eq, unsigned n_ineq)
 777 {
 778         struct isl_basic_map *ext;
 779         unsigned flags;
 780         int dims_ok;
 781
 782         if (!dim)
 783                 goto error;
 784
 785         base = isl_basic_map_cow(base);
 786         if (!base)
 787                 goto error;
 788
 789         dims_ok = isl_dim_equal(base->dim, dim) &&
 790                   base->extra >= base->n_div + extra;
 791
 792         if (dims_ok && n_eq == 0 && n_ineq == 0) {
 793                 isl_dim_free(dim);
 794                 return base;
 795         }
 796
 797         isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
 798         isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
 799         isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
 800         extra += base->extra;
 801         n_eq += base->n_eq;
 802         n_ineq += base->n_ineq;
 803
 804         ext = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 805         dim = NULL;
 806         if (!ext)
 807                 goto error;
 808
 809         flags = base->flags;
 810         ext = add_constraints(ext, base, 0, 0);
 811         if (ext) {
 812                 ext->flags = flags;
 813                 ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
 814         }
 815
 816         return ext;
 817
 818 error:
 819         isl_dim_free(dim);
 820         isl_basic_map_free(base);
 821         return NULL;
 822 }
 823
 824 struct isl_basic_map *isl_basic_map_extend_constraints(
 825                 struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
 826 {
 827         if (!base)
 828                 return NULL;
 829         return isl_basic_map_extend_dim(base, isl_dim_copy(base->dim),
 830                                         0, n_eq, n_ineq);
 831 }
 832
 833 struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
 834                 unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
 835                 unsigned n_eq, unsigned n_ineq)
 836 {
 837         struct isl_basic_map *bmap;
 838         struct isl_dim *dim;
 839
 840         if (!base)
 841                 return NULL;
 842         dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out);
 843         if (!dim)
 844                 return NULL;
 845
 846         bmap = isl_basic_map_extend_dim(base, dim, extra, n_eq, n_ineq);
 847         return bmap;
 848 }
 849
 850 struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
 851                 unsigned nparam, unsigned dim, unsigned extra,
 852                 unsigned n_eq, unsigned n_ineq)
 853 {
 854         return (struct isl_basic_set *)
 855                 isl_basic_map_extend((struct isl_basic_map *)base,
 856                                         nparam, 0, dim, extra, n_eq, n_ineq);
 857 }
 858
 859 struct isl_basic_set *isl_basic_set_extend_constraints(
 860                 struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
 861 {
 862         return (struct isl_basic_set *)
 863                 isl_basic_map_extend_constraints((struct isl_basic_map *)base,
 864                                                     n_eq, n_ineq);
 865 }
 866
 867 struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset)
 868 {
 869         return (struct isl_basic_set *)
 870                 isl_basic_map_cow((struct isl_basic_map *)bset);
 871 }
 872
 873 struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
 874 {
 875         if (!bmap)
 876                 return NULL;
 877
 878         if (bmap->ref > 1) {
 879                 bmap->ref--;
 880                 bmap = isl_basic_map_dup(bmap);
 881         }
 882         ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
 883         return bmap;
 884 }
 885
 886 struct isl_set *isl_set_cow(struct isl_set *set)
 887 {
 888         if (!set)
 889                 return NULL;
 890
 891         if (set->ref == 1)
 892                 return set;
 893         set->ref--;
 894         return isl_set_dup(set);
 895 }
 896
 897 struct isl_map *isl_map_cow(struct isl_map *map)
 898 {
 899         if (!map)
 900                 return NULL;
 901
 902         if (map->ref == 1)
 903                 return map;
 904         map->ref--;
 905         return isl_map_dup(map);
 906 }
 907
 908 static void swap_vars(struct isl_blk blk, isl_int *a,
 909                         unsigned a_len, unsigned b_len)
 910 {
 911         isl_seq_cpy(blk.data, a+a_len, b_len);
 912         isl_seq_cpy(blk.data+b_len, a, a_len);
 913         isl_seq_cpy(a, blk.data, b_len+a_len);
 914 }
 915
 916 struct isl_basic_set *isl_basic_set_swap_vars(
 917                 struct isl_basic_set *bset, unsigned n)
 918 {
 919         int i;
 920         struct isl_blk blk;
 921         unsigned dim;
 922         unsigned nparam;
 923
 924         if (!bset)
 925                 goto error;
 926
 927         nparam = isl_basic_set_n_param(bset);
 928         dim = isl_basic_set_n_dim(bset);
 929         isl_assert(bset->ctx, n <= dim, goto error);
 930
 931         if (n == dim)
 932                 return bset;
 933
 934         bset = isl_basic_set_cow(bset);
 935         if (!bset)
 936                 return NULL;
 937
 938         blk = isl_blk_alloc(bset->ctx, dim);
 939         if (isl_blk_is_error(blk))
 940                 goto error;
 941
 942         for (i = 0; i < bset->n_eq; ++i)
 943                 swap_vars(blk,
 944                           bset->eq[i]+1+nparam, n, dim - n);
 945
 946         for (i = 0; i < bset->n_ineq; ++i)
 947                 swap_vars(blk,
 948                           bset->ineq[i]+1+nparam, n, dim - n);
 949
 950         for (i = 0; i < bset->n_div; ++i)
 951                 swap_vars(blk,
 952                           bset->div[i]+1+1+nparam, n, dim - n);
 953
 954         isl_blk_free(bset->ctx, blk);
 955
 956         ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
 957         return bset;
 958
 959 error:
 960         isl_basic_set_free(bset);
 961         return NULL;
 962 }
 963
 964 struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n)
 965 {
 966         int i;
 967         set = isl_set_cow(set);
 968         if (!set)
 969                 return NULL;
 970
 971         for (i = 0; i < set->n; ++i) {
 972                 set->p[i] = isl_basic_set_swap_vars(set->p[i], n);
 973                 if (!set->p[i]) {
 974                         isl_set_free(set);
 975                         return NULL;
 976                 }
 977         }
 978         ISL_F_CLR(set, ISL_SET_NORMALIZED);
 979         return set;
 980 }
 981
 982 struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
 983 {
 984         int i = 0;
 985         unsigned total;
 986         if (!bmap)
 987                 goto error;
 988         total = isl_basic_map_total_dim(bmap);
 989         isl_basic_map_free_div(bmap, bmap->n_div);
 990         isl_basic_map_free_inequality(bmap, bmap->n_ineq);
 991         if (bmap->n_eq > 0)
 992                 isl_basic_map_free_equality(bmap, bmap->n_eq-1);
 993         else {
 994                 isl_basic_map_alloc_equality(bmap);
 995                 if (i < 0)
 996                         goto error;
 997         }
 998         isl_int_set_si(bmap->eq[i][0], 1);
 999         isl_seq_clr(bmap->eq[i]+1, total);
1000         ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
1001         return isl_basic_map_finalize(bmap);
1002 error:
1003         isl_basic_map_free(bmap);
1004         return NULL;
1005 }
1006
1007 struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset)
1008 {
1009         return (struct isl_basic_set *)
1010                 isl_basic_map_set_to_empty((struct isl_basic_map *)bset);
1011 }
1012
1013 static void swap_div(struct isl_basic_map *bmap, int a, int b)
1014 {
1015         int i;
1016         unsigned off = isl_dim_total(bmap->dim);
1017         isl_int *t = bmap->div[a];
1018         bmap->div[a] = bmap->div[b];
1019         bmap->div[b] = t;
1020
1021         for (i = 0; i < bmap->n_eq; ++i)
1022                 isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
1023
1024         for (i = 0; i < bmap->n_ineq; ++i)
1025                 isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
1026
1027         for (i = 0; i < bmap->n_div; ++i)
1028                 isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
1029         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1030 }
1031
1032 /* Eliminate the specified n dimensions starting at first from the
1033  * constraints using Fourier-Motzkin, The dimensions themselves
1034  * are not removed.
1035  */
1036 struct isl_set *isl_set_eliminate_dims(struct isl_set *set,
1037         unsigned first, unsigned n)
1038 {
1039         int i;
1040         unsigned nparam;
1041
1042         if (!set)
1043                 return NULL;
1044         if (n == 0)
1045                 return set;
1046
1047         set = isl_set_cow(set);
1048         if (!set)
1049                 return NULL;
1050         isl_assert(set->ctx, first+n <= isl_set_n_dim(set), goto error);
1051         nparam = isl_set_n_param(set);
1052
1053         for (i = 0; i < set->n; ++i) {
1054                 set->p[i] = isl_basic_set_eliminate_vars(set->p[i],
1055                                                             nparam + first, n);
1056                 if (!set->p[i])
1057                         goto error;
1058         }
1059         return set;
1060 error:
1061         isl_set_free(set);
1062         return NULL;
1063 }
1064
1065 /* Project out n dimensions starting at first using Fourier-Motzkin */
1066 struct isl_set *isl_set_remove_dims(struct isl_set *set,
1067         unsigned first, unsigned n)
1068 {
1069         set = isl_set_eliminate_dims(set, first, n);
1070         set = isl_set_drop_dims(set, first, n);
1071         return set;
1072 }
1073
1074 struct isl_basic_set *isl_basic_set_remove_divs(struct isl_basic_set *bset)
1075 {
1076         bset = isl_basic_set_eliminate_vars(bset, isl_dim_total(bset->dim),
1077                                                 bset->n_div);
1078         if (!bset)
1079                 return NULL;
1080         bset->n_div = 0;
1081         return bset;
1082 }
1083
1084 struct isl_set *isl_set_remove_divs(struct isl_set *set)
1085 {
1086         int i;
1087
1088         if (!set)
1089                 return NULL;
1090         if (set->n == 0)
1091                 return set;
1092
1093         set = isl_set_cow(set);
1094         if (!set)
1095                 return NULL;
1096
1097         for (i = 0; i < set->n; ++i) {
1098                 set->p[i] = isl_basic_set_remove_divs(set->p[i]);
1099                 if (!set->p[i])
1100                         goto error;
1101         }
1102         return set;
1103 error:
1104         isl_set_free(set);
1105         return NULL;
1106 }
1107
1108 struct isl_basic_map *isl_basic_map_remove(struct isl_basic_map *bmap,
1109         enum isl_dim_type type, unsigned first, unsigned n)
1110 {
1111         if (!bmap)
1112                 return NULL;
1113         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
1114                         goto error);
1115         if (n == 0)
1116                 return bmap;
1117         bmap = isl_basic_map_eliminate_vars(bmap,
1118                         isl_basic_map_offset(bmap, type) - 1 + first, n);
1119         bmap = isl_basic_map_drop(bmap, type, first, n);
1120         return bmap;
1121 error:
1122         isl_basic_map_free(bmap);
1123         return NULL;
1124 }
1125
1126 struct isl_map *isl_map_remove(struct isl_map *map,
1127         enum isl_dim_type type, unsigned first, unsigned n)
1128 {
1129         int i;
1130         unsigned nparam;
1131
1132         if (n == 0)
1133                 return map;
1134
1135         map = isl_map_cow(map);
1136         if (!map)
1137                 return NULL;
1138         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
1139
1140         for (i = 0; i < map->n; ++i) {
1141                 map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
1142                         isl_basic_map_offset(map->p[i], type) - 1 + first, n);
1143                 if (!map->p[i])
1144                         goto error;
1145         }
1146         map = isl_map_drop(map, type, first, n);
1147         return map;
1148 error:
1149         isl_map_free(map);
1150         return NULL;
1151 }
1152
1153 /* Project out n inputs starting at first using Fourier-Motzkin */
1154 struct isl_map *isl_map_remove_inputs(struct isl_map *map,
1155         unsigned first, unsigned n)
1156 {
1157         return isl_map_remove(map, isl_dim_in, first, n);
1158 }
1159
1160 /* Project out n dimensions starting at first using Fourier-Motzkin */
1161 struct isl_basic_set *isl_basic_set_remove_dims(struct isl_basic_set *bset,
1162         unsigned first, unsigned n)
1163 {
1164         unsigned nparam = isl_basic_set_n_param(bset);
1165         bset = isl_basic_set_eliminate_vars(bset, nparam + first, n);
1166         bset = isl_basic_set_drop_dims(bset, first, n);
1167         return bset;
1168 }
1169
1170 static void dump_term(struct isl_basic_map *bmap,
1171                         isl_int c, int pos, FILE *out)
1172 {
1173         const char *name;
1174         unsigned in = isl_basic_map_n_in(bmap);
1175         unsigned dim = in + isl_basic_map_n_out(bmap);
1176         unsigned nparam = isl_basic_map_n_param(bmap);
1177         if (!pos)
1178                 isl_int_print(out, c, 0);
1179         else {
1180                 if (!isl_int_is_one(c))
1181                         isl_int_print(out, c, 0);
1182                 if (pos < 1 + nparam) {
1183                         name = isl_dim_get_name(bmap->dim,
1184                                                 isl_dim_param, pos - 1);
1185                         if (name)
1186                                 fprintf(out, "%s", name);
1187                         else
1188                                 fprintf(out, "p%d", pos - 1);
1189                 } else if (pos < 1 + nparam + in)
1190                         fprintf(out, "i%d", pos - 1 - nparam);
1191                 else if (pos < 1 + nparam + dim)
1192                         fprintf(out, "o%d", pos - 1 - nparam - in);
1193                 else
1194                         fprintf(out, "e%d", pos - 1 - nparam - dim);
1195         }
1196 }
1197
1198 static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
1199                                 int sign, FILE *out)
1200 {
1201         int i;
1202         int first;
1203         unsigned len = 1 + isl_basic_map_total_dim(bmap);
1204         isl_int v;
1205
1206         isl_int_init(v);
1207         for (i = 0, first = 1; i < len; ++i) {
1208                 if (isl_int_sgn(c[i]) * sign <= 0)
1209                         continue;
1210                 if (!first)
1211                         fprintf(out, " + ");
1212                 first = 0;
1213                 isl_int_abs(v, c[i]);
1214                 dump_term(bmap, v, i, out);
1215         }
1216         isl_int_clear(v);
1217         if (first)
1218                 fprintf(out, "0");
1219 }
1220
1221 static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
1222                                 const char *op, FILE *out, int indent)
1223 {
1224         int i;
1225
1226         fprintf(out, "%*s", indent, "");
1227
1228         dump_constraint_sign(bmap, c, 1, out);
1229         fprintf(out, " %s ", op);
1230         dump_constraint_sign(bmap, c, -1, out);
1231
1232         fprintf(out, "\n");
1233
1234         for (i = bmap->n_div; i < bmap->extra; ++i) {
1235                 if (isl_int_is_zero(c[1+isl_dim_total(bmap->dim)+i]))
1236                         continue;
1237                 fprintf(out, "%*s", indent, "");
1238                 fprintf(out, "ERROR: unused div coefficient not zero\n");
1239                 abort();
1240         }
1241 }
1242
1243 static void dump_constraints(struct isl_basic_map *bmap,
1244                                 isl_int **c, unsigned n,
1245                                 const char *op, FILE *out, int indent)
1246 {
1247         int i;
1248
1249         for (i = 0; i < n; ++i)
1250                 dump_constraint(bmap, c[i], op, out, indent);
1251 }
1252
1253 static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
1254 {
1255         int j;
1256         int first = 1;
1257         unsigned total = isl_basic_map_total_dim(bmap);
1258
1259         for (j = 0; j < 1 + total; ++j) {
1260                 if (isl_int_is_zero(exp[j]))
1261                         continue;
1262                 if (!first && isl_int_is_pos(exp[j]))
1263                         fprintf(out, "+");
1264                 dump_term(bmap, exp[j], j, out);
1265                 first = 0;
1266         }
1267 }
1268
1269 static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
1270 {
1271         int i;
1272
1273         dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
1274         dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
1275
1276         for (i = 0; i < bmap->n_div; ++i) {
1277                 fprintf(out, "%*s", indent, "");
1278                 fprintf(out, "e%d = [(", i);
1279                 dump_affine(bmap, bmap->div[i]+1, out);
1280                 fprintf(out, ")/");
1281                 isl_int_print(out, bmap->div[i][0], 0);
1282                 fprintf(out, "]\n");
1283         }
1284 }
1285
1286 void isl_basic_set_dump(struct isl_basic_set *bset, FILE *out, int indent)
1287 {
1288         if (!bset) {
1289                 fprintf(out, "null basic set\n");
1290                 return;
1291         }
1292
1293         fprintf(out, "%*s", indent, "");
1294         fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
1295                         bset->ref, bset->dim->nparam, bset->dim->n_out,
1296                         bset->extra, bset->flags);
1297         dump((struct isl_basic_map *)bset, out, indent);
1298 }
1299
1300 void isl_basic_map_dump(struct isl_basic_map *bmap, FILE *out, int indent)
1301 {
1302         if (!bmap) {
1303                 fprintf(out, "null basic map\n");
1304                 return;
1305         }
1306
1307         fprintf(out, "%*s", indent, "");
1308         fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
1309                         "flags: %x, n_name: %d\n",
1310                 bmap->ref,
1311                 bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
1312                 bmap->extra, bmap->flags, bmap->dim->n_name);
1313         dump(bmap, out, indent);
1314 }
1315
1316 int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
1317 {
1318         unsigned total;
1319         if (!bmap)
1320                 return -1;
1321         total = isl_basic_map_total_dim(bmap);
1322         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
1323         isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
1324         isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
1325         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1326         return 0;
1327 }
1328
1329 struct isl_set *isl_set_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
1330 {
1331         struct isl_set *set;
1332
1333         if (!dim)
1334                 return NULL;
1335         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
1336         isl_assert(dim->ctx, n >= 0, return NULL);
1337         set = isl_alloc(dim->ctx, struct isl_set,
1338                         sizeof(struct isl_set) +
1339                         n * sizeof(struct isl_basic_set *));
1340         if (!set)
1341                 goto error;
1342
1343         set->ctx = dim->ctx;
1344         isl_ctx_ref(set->ctx);
1345         set->ref = 1;
1346         set->size = n;
1347         set->n = 0;
1348         set->dim = dim;
1349         set->flags = flags;
1350         return set;
1351 error:
1352         isl_dim_free(dim);
1353         return NULL;
1354 }
1355
1356 struct isl_set *isl_set_alloc(struct isl_ctx *ctx,
1357                 unsigned nparam, unsigned dim, int n, unsigned flags)
1358 {
1359         struct isl_set *set;
1360         struct isl_dim *dims;
1361
1362         dims = isl_dim_alloc(ctx, nparam, 0, dim);
1363         if (!dims)
1364                 return NULL;
1365
1366         set = isl_set_alloc_dim(dims, n, flags);
1367         return set;
1368 }
1369
1370 struct isl_set *isl_set_dup(struct isl_set *set)
1371 {
1372         int i;
1373         struct isl_set *dup;
1374
1375         if (!set)
1376                 return NULL;
1377
1378         dup = isl_set_alloc_dim(isl_dim_copy(set->dim), set->n, set->flags);
1379         if (!dup)
1380                 return NULL;
1381         for (i = 0; i < set->n; ++i)
1382                 dup = isl_set_add(dup, isl_basic_set_copy(set->p[i]));
1383         return dup;
1384 }
1385
1386 struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset)
1387 {
1388         struct isl_set *set;
1389
1390         if (!bset)
1391                 return NULL;
1392
1393         set = isl_set_alloc_dim(isl_dim_copy(bset->dim), 1, ISL_MAP_DISJOINT);
1394         if (!set) {
1395                 isl_basic_set_free(bset);
1396                 return NULL;
1397         }
1398         return isl_set_add(set, bset);
1399 }
1400
1401 struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap)
1402 {
1403         struct isl_map *map;
1404
1405         if (!bmap)
1406                 return NULL;
1407
1408         map = isl_map_alloc_dim(isl_dim_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
1409         if (!map) {
1410                 isl_basic_map_free(bmap);
1411                 return NULL;
1412         }
1413         return isl_map_add(map, bmap);
1414 }
1415
1416 struct isl_set *isl_set_add(struct isl_set *set, struct isl_basic_set *bset)
1417 {
1418         if (!bset || !set)
1419                 goto error;
1420         isl_assert(set->ctx, isl_dim_equal(set->dim, bset->dim), goto error);
1421         isl_assert(set->ctx, set->n < set->size, goto error);
1422         set->p[set->n] = bset;
1423         set->n++;
1424         return set;
1425 error:
1426         if (set)
1427                 isl_set_free(set);
1428         if (bset)
1429                 isl_basic_set_free(bset);
1430         return NULL;
1431 }
1432
1433 void isl_set_free(struct isl_set *set)
1434 {
1435         int i;
1436
1437         if (!set)
1438                 return;
1439
1440         if (--set->ref > 0)
1441                 return;
1442
1443         isl_ctx_deref(set->ctx);
1444         for (i = 0; i < set->n; ++i)
1445                 isl_basic_set_free(set->p[i]);
1446         isl_dim_free(set->dim);
1447         free(set);
1448 }
1449
1450 void isl_set_dump(struct isl_set *set, FILE *out, int indent)
1451 {
1452         int i;
1453
1454         if (!set) {
1455                 fprintf(out, "null set\n");
1456                 return;
1457         }
1458
1459         fprintf(out, "%*s", indent, "");
1460         fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
1461                         set->ref, set->n, set->dim->nparam, set->dim->n_out,
1462                         set->flags);
1463         for (i = 0; i < set->n; ++i) {
1464                 fprintf(out, "%*s", indent, "");
1465                 fprintf(out, "basic set %d:\n", i);
1466                 isl_basic_set_dump(set->p[i], out, indent+4);
1467         }
1468 }
1469
1470 void isl_map_dump(struct isl_map *map, FILE *out, int indent)
1471 {
1472         int i;
1473
1474         if (!map) {
1475                 fprintf(out, "null map\n");
1476                 return;
1477         }
1478
1479         fprintf(out, "%*s", indent, "");
1480         fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
1481                      "flags: %x, n_name: %d\n",
1482                         map->ref, map->n, map->dim->nparam, map->dim->n_in,
1483                         map->dim->n_out, map->flags, map->dim->n_name);
1484         for (i = 0; i < map->n; ++i) {
1485                 fprintf(out, "%*s", indent, "");
1486                 fprintf(out, "basic map %d:\n", i);
1487                 isl_basic_map_dump(map->p[i], out, indent+4);
1488         }
1489 }
1490
1491 struct isl_basic_map *isl_basic_map_intersect_domain(
1492                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1493 {
1494         struct isl_basic_map *bmap_domain;
1495         struct isl_dim *dim;
1496
1497         if (!bmap || !bset)
1498                 goto error;
1499
1500         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1501                                         bset->dim, isl_dim_param), goto error);
1502
1503         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1504                 isl_assert(bset->ctx,
1505                     isl_basic_map_compatible_domain(bmap, bset), goto error);
1506
1507         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1508                         bset->n_div, bset->n_eq, bset->n_ineq);
1509         if (!bmap)
1510                 goto error;
1511         dim = isl_dim_reverse(isl_dim_copy(bset->dim));
1512         bmap_domain = isl_basic_map_from_basic_set(bset, dim);
1513         bmap = add_constraints(bmap, bmap_domain, 0, 0);
1514
1515         bmap = isl_basic_map_simplify(bmap);
1516         return isl_basic_map_finalize(bmap);
1517 error:
1518         isl_basic_map_free(bmap);
1519         isl_basic_set_free(bset);
1520         return NULL;
1521 }
1522
1523 struct isl_basic_map *isl_basic_map_intersect_range(
1524                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1525 {
1526         struct isl_basic_map *bmap_range;
1527
1528         if (!bmap || !bset)
1529                 goto error;
1530
1531         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1532                                         bset->dim, isl_dim_param), goto error);
1533
1534         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1535                 isl_assert(bset->ctx,
1536                     isl_basic_map_compatible_range(bmap, bset), goto error);
1537
1538         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1539                         bset->n_div, bset->n_eq, bset->n_ineq);
1540         if (!bmap)
1541                 goto error;
1542         bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
1543         bmap = add_constraints(bmap, bmap_range, 0, 0);
1544
1545         bmap = isl_basic_map_simplify(bmap);
1546         return isl_basic_map_finalize(bmap);
1547 error:
1548         isl_basic_map_free(bmap);
1549         isl_basic_set_free(bset);
1550         return NULL;
1551 }
1552
1553 struct isl_basic_map *isl_basic_map_intersect(
1554                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1555 {
1556         if (!bmap1 || !bmap2)
1557                 goto error;
1558
1559         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
1560                                      bmap2->dim, isl_dim_param), goto error);
1561         if (isl_dim_total(bmap1->dim) ==
1562                                 isl_dim_size(bmap1->dim, isl_dim_param) &&
1563             isl_dim_total(bmap2->dim) !=
1564                                 isl_dim_size(bmap2->dim, isl_dim_param))
1565                 return isl_basic_map_intersect(bmap2, bmap1);
1566
1567         if (isl_dim_total(bmap2->dim) !=
1568                                         isl_dim_size(bmap2->dim, isl_dim_param))
1569                 isl_assert(bmap1->ctx,
1570                             isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
1571
1572         bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
1573                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
1574         if (!bmap1)
1575                 goto error;
1576         bmap1 = add_constraints(bmap1, bmap2, 0, 0);
1577
1578         bmap1 = isl_basic_map_simplify(bmap1);
1579         return isl_basic_map_finalize(bmap1);
1580 error:
1581         isl_basic_map_free(bmap1);
1582         isl_basic_map_free(bmap2);
1583         return NULL;
1584 }
1585
1586 struct isl_basic_set *isl_basic_set_intersect(
1587                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
1588 {
1589         return (struct isl_basic_set *)
1590                 isl_basic_map_intersect(
1591                         (struct isl_basic_map *)bset1,
1592                         (struct isl_basic_map *)bset2);
1593 }
1594
1595 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
1596 {
1597         unsigned flags = 0;
1598         struct isl_map *result;
1599         int i, j;
1600
1601         if (!map1 || !map2)
1602                 goto error;
1603
1604         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
1605                                          map2->dim, isl_dim_param), goto error);
1606         if (isl_dim_total(map1->dim) ==
1607                                 isl_dim_size(map1->dim, isl_dim_param) &&
1608             isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1609                 return isl_map_intersect(map2, map1);
1610
1611         if (isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
1612                 isl_assert(map1->ctx,
1613                             isl_dim_equal(map1->dim, map2->dim), goto error);
1614
1615         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
1616             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
1617                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
1618
1619         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
1620                                 map1->n * map2->n, flags);
1621         if (!result)
1622                 goto error;
1623         for (i = 0; i < map1->n; ++i)
1624                 for (j = 0; j < map2->n; ++j) {
1625                         struct isl_basic_map *part;
1626                         part = isl_basic_map_intersect(
1627                                     isl_basic_map_copy(map1->p[i]),
1628                                     isl_basic_map_copy(map2->p[j]));
1629                         if (isl_basic_map_is_empty(part))
1630                                 isl_basic_map_free(part);
1631                         else
1632                                 result = isl_map_add(result, part);
1633                         if (!result)
1634                                 goto error;
1635                 }
1636         isl_map_free(map1);
1637         isl_map_free(map2);
1638         return result;
1639 error:
1640         isl_map_free(map1);
1641         isl_map_free(map2);
1642         return NULL;
1643 }
1644
1645 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
1646 {
1647         return (struct isl_set *)
1648                 isl_map_intersect((struct isl_map *)set1,
1649                                   (struct isl_map *)set2);
1650 }
1651
1652 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
1653 {
1654         struct isl_dim *dim;
1655         struct isl_basic_set *bset;
1656         unsigned in;
1657
1658         if (!bmap)
1659                 return NULL;
1660         bmap = isl_basic_map_cow(bmap);
1661         if (!bmap)
1662                 return NULL;
1663         dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
1664         in = isl_basic_map_n_in(bmap);
1665         bset = isl_basic_set_from_basic_map(bmap);
1666         bset = isl_basic_set_swap_vars(bset, in);
1667         return isl_basic_map_from_basic_set(bset, dim);
1668 }
1669
1670 /* Turn final n dimensions into existentially quantified variables.
1671  */
1672 struct isl_basic_set *isl_basic_set_project_out(
1673                 struct isl_basic_set *bset, unsigned n, unsigned flags)
1674 {
1675         int i;
1676         size_t row_size;
1677         isl_int **new_div;
1678         isl_int *old;
1679
1680         if (!bset)
1681                 return NULL;
1682
1683         isl_assert(bset->ctx, n <= isl_basic_set_n_dim(bset), goto error);
1684
1685         if (n == 0)
1686                 return bset;
1687
1688         bset = isl_basic_set_cow(bset);
1689
1690         row_size = 1 + isl_dim_total(bset->dim) + bset->extra;
1691         old = bset->block2.data;
1692         bset->block2 = isl_blk_extend(bset->ctx, bset->block2,
1693                                         (bset->extra + n) * (1 + row_size));
1694         if (!bset->block2.data)
1695                 goto error;
1696         new_div = isl_alloc_array(ctx, isl_int *, bset->extra + n);
1697         if (!new_div)
1698                 goto error;
1699         for (i = 0; i < n; ++i) {
1700                 new_div[i] = bset->block2.data +
1701                                 (bset->extra + i) * (1 + row_size);
1702                 isl_seq_clr(new_div[i], 1 + row_size);
1703         }
1704         for (i = 0; i < bset->extra; ++i)
1705                 new_div[n + i] = bset->block2.data + (bset->div[i] - old);
1706         free(bset->div);
1707         bset->div = new_div;
1708         bset->n_div += n;
1709         bset->extra += n;
1710         bset->dim = isl_dim_drop_outputs(bset->dim,
1711                                             isl_basic_set_n_dim(bset) - n, n);
1712         if (!bset->dim)
1713                 goto error;
1714         bset = isl_basic_set_simplify(bset);
1715         return isl_basic_set_finalize(bset);
1716 error:
1717         isl_basic_set_free(bset);
1718         return NULL;
1719 }
1720
1721 struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
1722 {
1723         int i, j;
1724
1725         for (i = 0; i < n; ++i) {
1726                 j = isl_basic_map_alloc_div(bmap);
1727                 if (j < 0)
1728                         goto error;
1729                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
1730         }
1731         return bmap;
1732 error:
1733         isl_basic_map_free(bmap);
1734         return NULL;
1735 }
1736
1737 struct isl_basic_map *isl_basic_map_apply_range(
1738                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1739 {
1740         struct isl_dim *dim_result = NULL;
1741         struct isl_basic_map *bmap;
1742         unsigned n_in, n_out, n, nparam, total, pos;
1743         struct isl_dim_map *dim_map1, *dim_map2;
1744
1745         if (!bmap1 || !bmap2)
1746                 goto error;
1747
1748         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
1749                                   isl_dim_copy(bmap2->dim));
1750
1751         n_in = isl_basic_map_n_in(bmap1);
1752         n_out = isl_basic_map_n_out(bmap2);
1753         n = isl_basic_map_n_out(bmap1);
1754         nparam = isl_basic_map_n_param(bmap1);
1755
1756         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
1757         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
1758         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
1759         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
1760         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
1761         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
1762         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
1763         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
1764         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
1765         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
1766         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
1767
1768         bmap = isl_basic_map_alloc_dim(dim_result,
1769                         bmap1->n_div + bmap2->n_div + n,
1770                         bmap1->n_eq + bmap2->n_eq,
1771                         bmap1->n_ineq + bmap2->n_ineq);
1772         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
1773         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
1774         bmap = add_divs(bmap, n);
1775         bmap = isl_basic_map_simplify(bmap);
1776         return isl_basic_map_finalize(bmap);
1777 error:
1778         isl_basic_map_free(bmap1);
1779         isl_basic_map_free(bmap2);
1780         return NULL;
1781 }
1782
1783 struct isl_basic_set *isl_basic_set_apply(
1784                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
1785 {
1786         if (!bset || !bmap)
1787                 goto error;
1788
1789         isl_assert(set->ctx, isl_basic_map_compatible_domain(bmap, bset),
1790                     goto error);
1791
1792         return (struct isl_basic_set *)
1793                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
1794 error:
1795         isl_basic_set_free(bset);
1796         isl_basic_map_free(bmap);
1797         return NULL;
1798 }
1799
1800 struct isl_basic_map *isl_basic_map_apply_domain(
1801                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1802 {
1803         if (!bmap1 || !bmap2)
1804                 goto error;
1805
1806         isl_assert(ctx,
1807             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
1808         isl_assert(ctx,
1809             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
1810             goto error);
1811
1812         bmap1 = isl_basic_map_reverse(bmap1);
1813         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
1814         return isl_basic_map_reverse(bmap1);
1815 error:
1816         isl_basic_map_free(bmap1);
1817         isl_basic_map_free(bmap2);
1818         return NULL;
1819 }
1820
1821 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
1822  * A \cap B -> f(A) + f(B)
1823  */
1824 struct isl_basic_map *isl_basic_map_sum(
1825                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1826 {
1827         unsigned n_in, n_out, nparam, total, pos;
1828         struct isl_basic_map *bmap = NULL;
1829         struct isl_dim_map *dim_map1, *dim_map2;
1830         int i;
1831
1832         if (!bmap1 || !bmap2)
1833                 goto error;
1834
1835         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
1836                 goto error);
1837
1838         nparam = isl_basic_map_n_param(bmap1);
1839         n_in = isl_basic_map_n_in(bmap1);
1840         n_out = isl_basic_map_n_out(bmap1);
1841
1842         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
1843         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
1844         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
1845         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
1846         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
1847         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
1848         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
1849         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
1850         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
1851         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
1852         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
1853
1854         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
1855                         bmap1->n_div + bmap2->n_div + 2 * n_out,
1856                         bmap1->n_eq + bmap2->n_eq + n_out,
1857                         bmap1->n_ineq + bmap2->n_ineq);
1858         for (i = 0; i < n_out; ++i) {
1859                 int j = isl_basic_map_alloc_equality(bmap);
1860                 if (j < 0)
1861                         goto error;
1862                 isl_seq_clr(bmap->eq[j], 1+total);
1863                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
1864                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
1865                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
1866         }
1867         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
1868         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
1869         bmap = add_divs(bmap, 2 * n_out);
1870
1871         bmap = isl_basic_map_simplify(bmap);
1872         return isl_basic_map_finalize(bmap);
1873 error:
1874         isl_basic_map_free(bmap);
1875         isl_basic_map_free(bmap1);
1876         isl_basic_map_free(bmap2);
1877         return NULL;
1878 }
1879
1880 /* Given a basic map A -> f(A), construct A -> -f(A).
1881  */
1882 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
1883 {
1884         int i, j;
1885         unsigned off, n;
1886
1887         bmap = isl_basic_map_cow(bmap);
1888         if (!bmap)
1889                 return NULL;
1890
1891         n = isl_basic_map_dim(bmap, isl_dim_out);
1892         off = isl_basic_map_offset(bmap, isl_dim_out);
1893         for (i = 0; i < bmap->n_eq; ++i)
1894                 for (j = 0; j < n; ++j)
1895                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
1896         for (i = 0; i < bmap->n_ineq; ++i)
1897                 for (j = 0; j < n; ++j)
1898                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
1899         for (i = 0; i < bmap->n_div; ++i)
1900                 for (j = 0; j < n; ++j)
1901                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
1902         return isl_basic_map_finalize(bmap);
1903 }
1904
1905 /* Given a basic map A -> f(A) and an integer d, construct a basic map
1906  * A -> floor(f(A)/d).
1907  */
1908 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
1909                 isl_int d)
1910 {
1911         unsigned n_in, n_out, nparam, total, pos;
1912         struct isl_basic_map *result = NULL;
1913         struct isl_dim_map *dim_map;
1914         int i;
1915
1916         if (!bmap)
1917                 return NULL;
1918
1919         nparam = isl_basic_map_n_param(bmap);
1920         n_in = isl_basic_map_n_in(bmap);
1921         n_out = isl_basic_map_n_out(bmap);
1922
1923         total = nparam + n_in + n_out + bmap->n_div + n_out;
1924         dim_map = isl_dim_map_alloc(bmap->ctx, total);
1925         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
1926         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
1927         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
1928         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
1929
1930         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
1931                         bmap->n_div + n_out,
1932                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
1933         result = add_constraints_dim_map(result, bmap, dim_map);
1934         result = add_divs(result, n_out);
1935         for (i = 0; i < n_out; ++i) {
1936                 int j;
1937                 j = isl_basic_map_alloc_inequality(result);
1938                 if (j < 0)
1939                         goto error;
1940                 isl_seq_clr(result->ineq[j], 1+total);
1941                 isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
1942                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
1943                 j = isl_basic_map_alloc_inequality(result);
1944                 if (j < 0)
1945                         goto error;
1946                 isl_seq_clr(result->ineq[j], 1+total);
1947                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
1948                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
1949                 isl_int_sub_ui(result->ineq[j][0], d, 1);
1950         }
1951
1952         result = isl_basic_map_simplify(result);
1953         return isl_basic_map_finalize(result);
1954 error:
1955         isl_basic_map_free(result);
1956         return NULL;
1957 }
1958
1959 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
1960 {
1961         int i;
1962         unsigned nparam;
1963         unsigned n_in;
1964
1965         i = isl_basic_map_alloc_equality(bmap);
1966         if (i < 0)
1967                 goto error;
1968         nparam = isl_basic_map_n_param(bmap);
1969         n_in = isl_basic_map_n_in(bmap);
1970         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
1971         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
1972         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
1973         return isl_basic_map_finalize(bmap);
1974 error:
1975         isl_basic_map_free(bmap);
1976         return NULL;
1977 }
1978
1979 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
1980 {
1981         int i;
1982         unsigned nparam;
1983         unsigned n_in;
1984
1985         i = isl_basic_map_alloc_inequality(bmap);
1986         if (i < 0)
1987                 goto error;
1988         nparam = isl_basic_map_n_param(bmap);
1989         n_in = isl_basic_map_n_in(bmap);
1990         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
1991         isl_int_set_si(bmap->ineq[i][0], -1);
1992         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
1993         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
1994         return isl_basic_map_finalize(bmap);
1995 error:
1996         isl_basic_map_free(bmap);
1997         return NULL;
1998 }
1999
2000 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2001 {
2002         int i;
2003         unsigned nparam;
2004         unsigned n_in;
2005
2006         i = isl_basic_map_alloc_inequality(bmap);
2007         if (i < 0)
2008                 goto error;
2009         nparam = isl_basic_map_n_param(bmap);
2010         n_in = isl_basic_map_n_in(bmap);
2011         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2012         isl_int_set_si(bmap->ineq[i][0], -1);
2013         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2014         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2015         return isl_basic_map_finalize(bmap);
2016 error:
2017         isl_basic_map_free(bmap);
2018         return NULL;
2019 }
2020
2021 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
2022 {
2023         int i;
2024         struct isl_basic_map *bmap;
2025         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
2026         if (!bmap)
2027                 return NULL;
2028         for (i = 0; i < n_equal && bmap; ++i)
2029                 bmap = var_equal(bmap, i);
2030         return isl_basic_map_finalize(bmap);
2031 }
2032
2033 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
2034 {
2035         int i;
2036         struct isl_basic_map *bmap;
2037         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2038         if (!bmap)
2039                 return NULL;
2040         for (i = 0; i < pos && bmap; ++i)
2041                 bmap = var_equal(bmap, i);
2042         if (bmap)
2043                 bmap = var_less(bmap, pos);
2044         return isl_basic_map_finalize(bmap);
2045 }
2046
2047 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
2048 {
2049         int i;
2050         struct isl_basic_map *bmap;
2051         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2052         if (!bmap)
2053                 return NULL;
2054         for (i = 0; i < pos && bmap; ++i)
2055                 bmap = var_equal(bmap, i);
2056         if (bmap)
2057                 bmap = var_more(bmap, pos);
2058         return isl_basic_map_finalize(bmap);
2059 }
2060
2061 struct isl_basic_map *isl_basic_map_from_basic_set(
2062                 struct isl_basic_set *bset, struct isl_dim *dim)
2063 {
2064         struct isl_basic_map *bmap;
2065
2066         bset = isl_basic_set_cow(bset);
2067         if (!bset || !dim)
2068                 goto error;
2069
2070         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
2071         isl_dim_free(bset->dim);
2072         bmap = (struct isl_basic_map *) bset;
2073         bmap->dim = dim;
2074         return isl_basic_map_finalize(bmap);
2075 error:
2076         isl_basic_set_free(bset);
2077         isl_dim_free(dim);
2078         return NULL;
2079 }
2080
2081 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
2082 {
2083         if (!bmap)
2084                 goto error;
2085         if (bmap->dim->n_in == 0)
2086                 return (struct isl_basic_set *)bmap;
2087         bmap = isl_basic_map_cow(bmap);
2088         if (!bmap)
2089                 goto error;
2090         bmap->dim = isl_dim_cow(bmap->dim);
2091         if (!bmap->dim)
2092                 goto error;
2093         bmap->dim->n_out += bmap->dim->n_in;
2094         bmap->dim->n_in = 0;
2095         bmap = isl_basic_map_finalize(bmap);
2096         return (struct isl_basic_set *)bmap;
2097 error:
2098         isl_basic_map_free(bmap);
2099         return NULL;
2100 }
2101
2102 /* For a div d = floor(f/m), add the constraints
2103  *
2104  *              f - m d >= 0
2105  *              -(f-(n-1)) + m d >= 0
2106  *
2107  * Note that the second constraint is the negation of
2108  *
2109  *              f - m d >= n
2110  */
2111 static int add_div_constraints(struct isl_basic_map *bmap, unsigned div)
2112 {
2113         int i, j;
2114         unsigned total = isl_basic_map_total_dim(bmap);
2115         unsigned div_pos = 1 + total - bmap->n_div + div;
2116
2117         i = isl_basic_map_alloc_inequality(bmap);
2118         if (i < 0)
2119                 return -1;
2120         isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total);
2121         isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]);
2122
2123         j = isl_basic_map_alloc_inequality(bmap);
2124         if (j < 0)
2125                 return -1;
2126         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
2127         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]);
2128         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
2129         return j;
2130 }
2131
2132 struct isl_basic_set *isl_basic_map_underlying_set(
2133                 struct isl_basic_map *bmap)
2134 {
2135         if (!bmap)
2136                 goto error;
2137         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
2138                 return (struct isl_basic_set *)bmap;
2139         bmap = isl_basic_map_cow(bmap);
2140         if (!bmap)
2141                 goto error;
2142         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
2143         if (!bmap->dim)
2144                 goto error;
2145         bmap->extra -= bmap->n_div;
2146         bmap->n_div = 0;
2147         bmap = isl_basic_map_finalize(bmap);
2148         return (struct isl_basic_set *)bmap;
2149 error:
2150         return NULL;
2151 }
2152
2153 struct isl_basic_map *isl_basic_map_overlying_set(
2154         struct isl_basic_set *bset, struct isl_basic_map *like)
2155 {
2156         struct isl_basic_map *bmap;
2157         struct isl_ctx *ctx;
2158         unsigned total;
2159         int i;
2160
2161         if (!bset || !like)
2162                 goto error;
2163         ctx = bset->ctx;
2164         isl_assert(ctx, bset->n_div == 0, goto error);
2165         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
2166         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
2167                         goto error);
2168         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
2169                 isl_basic_map_free(like);
2170                 return (struct isl_basic_map *)bset;
2171         }
2172         bset = isl_basic_set_cow(bset);
2173         if (!bset)
2174                 goto error;
2175         total = bset->dim->n_out + bset->extra;
2176         bmap = (struct isl_basic_map *)bset;
2177         isl_dim_free(bmap->dim);
2178         bmap->dim = isl_dim_copy(like->dim);
2179         if (!bmap->dim)
2180                 goto error;
2181         bmap->n_div = like->n_div;
2182         bmap->extra += like->n_div;
2183         if (bmap->extra) {
2184                 unsigned ltotal;
2185                 ltotal = total - bmap->extra + like->extra;
2186                 if (ltotal > total)
2187                         ltotal = total;
2188                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
2189                                         bmap->extra * (1 + 1 + total));
2190                 if (isl_blk_is_error(bmap->block2))
2191                         goto error;
2192                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
2193                                                 bmap->extra);
2194                 if (!bmap->div)
2195                         goto error;
2196                 for (i = 0; i < bmap->extra; ++i)
2197                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
2198                 for (i = 0; i < like->n_div; ++i) {
2199                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
2200                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
2201                 }
2202                 bmap = isl_basic_map_extend_constraints(bmap,
2203                                                         0, 2 * like->n_div);
2204                 for (i = 0; i < like->n_div; ++i) {
2205                         if (isl_int_is_zero(bmap->div[i][0]))
2206                                 continue;
2207                         if (add_div_constraints(bmap, i) < 0)
2208                                 goto error;
2209                 }
2210         }
2211         isl_basic_map_free(like);
2212         bmap = isl_basic_map_simplify(bmap);
2213         bmap = isl_basic_map_finalize(bmap);
2214         return bmap;
2215 error:
2216         isl_basic_map_free(like);
2217         isl_basic_set_free(bset);
2218         return NULL;
2219 }
2220
2221 struct isl_basic_set *isl_basic_set_from_underlying_set(
2222         struct isl_basic_set *bset, struct isl_basic_set *like)
2223 {
2224         return (struct isl_basic_set *)
2225                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
2226 }
2227
2228 struct isl_set *isl_set_from_underlying_set(
2229         struct isl_set *set, struct isl_basic_set *like)
2230 {
2231         int i;
2232
2233         if (!set || !like)
2234                 goto error;
2235         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
2236                     goto error);
2237         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
2238                 isl_basic_set_free(like);
2239                 return set;
2240         }
2241         set = isl_set_cow(set);
2242         if (!set)
2243                 goto error;
2244         for (i = 0; i < set->n; ++i) {
2245                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
2246                                                       isl_basic_set_copy(like));
2247                 if (!set->p[i])
2248                         goto error;
2249         }
2250         isl_dim_free(set->dim);
2251         set->dim = isl_dim_copy(like->dim);
2252         if (!set->dim)
2253                 goto error;
2254         isl_basic_set_free(like);
2255         return set;
2256 error:
2257         isl_basic_set_free(like);
2258         isl_set_free(set);
2259         return NULL;
2260 }
2261
2262 struct isl_set *isl_map_underlying_set(struct isl_map *map)
2263 {
2264         int i;
2265
2266         map = isl_map_cow(map);
2267         if (!map)
2268                 return NULL;
2269         map->dim = isl_dim_cow(map->dim);
2270         if (!map->dim)
2271                 goto error;
2272
2273         for (i = 1; i < map->n; ++i)
2274                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
2275                                 goto error);
2276         for (i = 0; i < map->n; ++i) {
2277                 map->p[i] = (struct isl_basic_map *)
2278                                 isl_basic_map_underlying_set(map->p[i]);
2279                 if (!map->p[i])
2280                         goto error;
2281         }
2282         if (map->n == 0)
2283                 map->dim = isl_dim_underlying(map->dim, 0);
2284         else {
2285                 isl_dim_free(map->dim);
2286                 map->dim = isl_dim_copy(map->p[0]->dim);
2287         }
2288         if (!map->dim)
2289                 goto error;
2290         return (struct isl_set *)map;
2291 error:
2292         isl_map_free(map);
2293         return NULL;
2294 }
2295
2296 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
2297 {
2298         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
2299 }
2300
2301 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
2302 {
2303         struct isl_basic_set *domain;
2304         unsigned n_out;
2305         if (!bmap)
2306                 return NULL;
2307         n_out = isl_basic_map_n_out(bmap);
2308         domain = isl_basic_set_from_basic_map(bmap);
2309         return isl_basic_set_project_out(domain, n_out, 0);
2310 }
2311
2312 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
2313 {
2314         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
2315 }
2316
2317 struct isl_set *isl_map_range(struct isl_map *map)
2318 {
2319         int i;
2320         struct isl_set *set;
2321
2322         if (!map)
2323                 goto error;
2324         map = isl_map_cow(map);
2325         if (!map)
2326                 goto error;
2327
2328         set = (struct isl_set *) map;
2329         if (set->dim->n_in != 0) {
2330                 set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
2331                 if (!set->dim)
2332                         goto error;
2333         }
2334         for (i = 0; i < map->n; ++i) {
2335                 set->p[i] = isl_basic_map_range(map->p[i]);
2336                 if (!set->p[i])
2337                         goto error;
2338         }
2339         ISL_F_CLR(set, ISL_MAP_DISJOINT);
2340         ISL_F_CLR(set, ISL_SET_NORMALIZED);
2341         return set;
2342 error:
2343         isl_map_free(map);
2344         return NULL;
2345 }
2346
2347 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
2348 {
2349         int i;
2350         struct isl_map *map = NULL;
2351
2352         set = isl_set_cow(set);
2353         if (!set || !dim)
2354                 goto error;
2355         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
2356         map = (struct isl_map *)set;
2357         for (i = 0; i < set->n; ++i) {
2358                 map->p[i] = isl_basic_map_from_basic_set(
2359                                 set->p[i], isl_dim_copy(dim));
2360                 if (!map->p[i])
2361                         goto error;
2362         }
2363         isl_dim_free(map->dim);
2364         map->dim = dim;
2365         return map;
2366 error:
2367         isl_dim_free(dim);
2368         isl_set_free(set);
2369         return NULL;
2370 }
2371
2372 struct isl_map *isl_map_from_range(struct isl_set *set)
2373 {
2374         return (struct isl_map *)set;
2375 }
2376
2377 struct isl_set *isl_set_from_map(struct isl_map *map)
2378 {
2379         int i;
2380         struct isl_set *set = NULL;
2381
2382         if (!map)
2383                 return NULL;
2384         map = isl_map_cow(map);
2385         if (!map)
2386                 return NULL;
2387         map->dim = isl_dim_cow(map->dim);
2388         if (!map->dim)
2389                 goto error;
2390         map->dim->n_out += map->dim->n_in;
2391         map->dim->n_in = 0;
2392         set = (struct isl_set *)map;
2393         for (i = 0; i < map->n; ++i) {
2394                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
2395                 if (!set->p[i])
2396                         goto error;
2397         }
2398         return set;
2399 error:
2400         isl_map_free(map);
2401         return NULL;
2402 }
2403
2404 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
2405 {
2406         struct isl_map *map;
2407
2408         if (!dim)
2409                 return NULL;
2410         isl_assert(dim->ctx, n >= 0, return NULL);
2411         map = isl_alloc(dim->ctx, struct isl_map,
2412                         sizeof(struct isl_map) +
2413                         n * sizeof(struct isl_basic_map *));
2414         if (!map)
2415                 goto error;
2416
2417         map->ctx = dim->ctx;
2418         isl_ctx_ref(map->ctx);
2419         map->ref = 1;
2420         map->size = n;
2421         map->n = 0;
2422         map->dim = dim;
2423         map->flags = flags;
2424         return map;
2425 error:
2426         isl_dim_free(dim);
2427         return NULL;
2428 }
2429
2430 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
2431                 unsigned nparam, unsigned in, unsigned out, int n,
2432                 unsigned flags)
2433 {
2434         struct isl_map *map;
2435         struct isl_dim *dims;
2436
2437         dims = isl_dim_alloc(ctx, nparam, in, out);
2438         if (!dims)
2439                 return NULL;
2440
2441         map = isl_map_alloc_dim(dims, n, flags);
2442         return map;
2443 }
2444
2445 struct isl_basic_map *isl_basic_map_empty(struct isl_ctx *ctx,
2446                 unsigned nparam, unsigned in, unsigned out)
2447 {
2448         struct isl_basic_map *bmap;
2449         bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, 1, 0);
2450         bmap = isl_basic_map_set_to_empty(bmap);
2451         return bmap;
2452 }
2453
2454 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
2455 {
2456         struct isl_basic_set *bset;
2457         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
2458         bset = isl_basic_set_set_to_empty(bset);
2459         return bset;
2460 }
2461
2462 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
2463 {
2464         struct isl_basic_map *bmap;
2465         if (!model)
2466                 return NULL;
2467         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
2468         bmap = isl_basic_map_set_to_empty(bmap);
2469         return bmap;
2470 }
2471
2472 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
2473 {
2474         struct isl_basic_map *bmap;
2475         if (!model)
2476                 return NULL;
2477         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
2478         bmap = isl_basic_map_set_to_empty(bmap);
2479         return bmap;
2480 }
2481
2482 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
2483 {
2484         struct isl_basic_set *bset;
2485         if (!model)
2486                 return NULL;
2487         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
2488         bset = isl_basic_set_set_to_empty(bset);
2489         return bset;
2490 }
2491
2492 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
2493 {
2494         struct isl_basic_map *bmap;
2495         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
2496         return bmap;
2497 }
2498
2499 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
2500 {
2501         struct isl_basic_set *bset;
2502         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
2503         return bset;
2504 }
2505
2506 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
2507 {
2508         if (!model)
2509                 return NULL;
2510         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
2511 }
2512
2513 struct isl_map *isl_map_empty(struct isl_dim *dim)
2514 {
2515         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
2516 }
2517
2518 struct isl_map *isl_map_empty_like(struct isl_map *model)
2519 {
2520         if (!model)
2521                 return NULL;
2522         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
2523 }
2524
2525 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
2526 {
2527         if (!model)
2528                 return NULL;
2529         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
2530 }
2531
2532 struct isl_set *isl_set_empty(struct isl_dim *dim)
2533 {
2534         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
2535 }
2536
2537 struct isl_set *isl_set_empty_like(struct isl_set *model)
2538 {
2539         if (!model)
2540                 return NULL;
2541         return isl_set_empty(isl_dim_copy(model->dim));
2542 }
2543
2544 struct isl_set *isl_set_universe(struct isl_dim *dim)
2545 {
2546         struct isl_set *set;
2547         if (!dim)
2548                 return NULL;
2549         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
2550         set = isl_set_add(set, isl_basic_set_universe(dim));
2551         return set;
2552 }
2553
2554 struct isl_map *isl_map_dup(struct isl_map *map)
2555 {
2556         int i;
2557         struct isl_map *dup;
2558
2559         if (!map)
2560                 return NULL;
2561         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
2562         for (i = 0; i < map->n; ++i)
2563                 dup = isl_map_add(dup, isl_basic_map_copy(map->p[i]));
2564         return dup;
2565 }
2566
2567 struct isl_map *isl_map_add(struct isl_map *map, struct isl_basic_map *bmap)
2568 {
2569         if (!bmap || !map)
2570                 goto error;
2571         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
2572         isl_assert(map->ctx, map->n < map->size, goto error);
2573         map->p[map->n] = bmap;
2574         map->n++;
2575         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2576         return map;
2577 error:
2578         if (map)
2579                 isl_map_free(map);
2580         if (bmap)
2581                 isl_basic_map_free(bmap);
2582         return NULL;
2583 }
2584
2585 void isl_map_free(struct isl_map *map)
2586 {
2587         int i;
2588
2589         if (!map)
2590                 return;
2591
2592         if (--map->ref > 0)
2593                 return;
2594
2595         isl_ctx_deref(map->ctx);
2596         for (i = 0; i < map->n; ++i)
2597                 isl_basic_map_free(map->p[i]);
2598         isl_dim_free(map->dim);
2599         free(map);
2600 }
2601
2602 struct isl_map *isl_map_extend(struct isl_map *base,
2603                 unsigned nparam, unsigned n_in, unsigned n_out)
2604 {
2605         int i;
2606
2607         base = isl_map_cow(base);
2608         if (!base)
2609                 return NULL;
2610
2611         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
2612         if (!base->dim)
2613                 goto error;
2614         for (i = 0; i < base->n; ++i) {
2615                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
2616                                 isl_dim_copy(base->dim), 0, 0, 0);
2617                 if (!base->p[i])
2618                         goto error;
2619         }
2620         return base;
2621 error:
2622         isl_map_free(base);
2623         return NULL;
2624 }
2625
2626 struct isl_set *isl_set_extend(struct isl_set *base,
2627                 unsigned nparam, unsigned dim)
2628 {
2629         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
2630                                                         nparam, 0, dim);
2631 }
2632
2633 static struct isl_basic_map *isl_basic_map_fix_pos(struct isl_basic_map *bmap,
2634                 unsigned pos, int value)
2635 {
2636         int j;
2637
2638         bmap = isl_basic_map_cow(bmap);
2639         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
2640         j = isl_basic_map_alloc_equality(bmap);
2641         if (j < 0)
2642                 goto error;
2643         isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
2644         isl_int_set_si(bmap->eq[j][pos], -1);
2645         isl_int_set_si(bmap->eq[j][0], value);
2646         bmap = isl_basic_map_simplify(bmap);
2647         return isl_basic_map_finalize(bmap);
2648 error:
2649         isl_basic_map_free(bmap);
2650         return NULL;
2651 }
2652
2653 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
2654                 enum isl_dim_type type, unsigned pos, int value)
2655 {
2656         if (!bmap)
2657                 return NULL;
2658         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
2659         return isl_basic_map_fix_pos(bmap, isl_basic_map_offset(bmap, type) + pos,
2660                                         value);
2661 error:
2662         isl_basic_map_free(bmap);
2663         return NULL;
2664 }
2665
2666 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
2667                 enum isl_dim_type type, unsigned pos, int value)
2668 {
2669         return (struct isl_basic_set *)
2670                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
2671                                         type, pos, value);
2672 }
2673
2674 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
2675                 unsigned input, int value)
2676 {
2677         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
2678 }
2679
2680 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
2681                 unsigned dim, int value)
2682 {
2683         return (struct isl_basic_set *)
2684                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
2685                                         isl_dim_set, dim, value);
2686 }
2687
2688 struct isl_map *isl_map_fix_si(struct isl_map *map,
2689                 enum isl_dim_type type, unsigned pos, int value)
2690 {
2691         int i;
2692
2693         map = isl_map_cow(map);
2694         if (!map)
2695                 return NULL;
2696
2697         isl_assert(ctx, pos < isl_map_dim(map, type), goto error);
2698         for (i = 0; i < map->n; ++i) {
2699                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
2700                 if (!map->p[i])
2701                         goto error;
2702         }
2703         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2704         return map;
2705 error:
2706         isl_map_free(map);
2707         return NULL;
2708 }
2709
2710 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
2711                 unsigned input, int value)
2712 {
2713         return isl_map_fix_si(map, isl_dim_in, input, value);
2714 }
2715
2716 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
2717 {
2718         return (struct isl_set *)
2719                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
2720 }
2721
2722 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
2723         unsigned dim, isl_int value)
2724 {
2725         int j;
2726         unsigned nparam;
2727
2728         bset = isl_basic_set_cow(bset);
2729         bset = isl_basic_set_extend_constraints(bset, 0, 1);
2730         j = isl_basic_set_alloc_inequality(bset);
2731         if (j < 0)
2732                 goto error;
2733         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
2734         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
2735         isl_int_neg(bset->ineq[j][0], value);
2736         bset = isl_basic_set_simplify(bset);
2737         return isl_basic_set_finalize(bset);
2738 error:
2739         isl_basic_set_free(bset);
2740         return NULL;
2741 }
2742
2743 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
2744                                         isl_int value)
2745 {
2746         int i;
2747
2748         set = isl_set_cow(set);
2749         if (!set)
2750                 return NULL;
2751
2752         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
2753         for (i = 0; i < set->n; ++i) {
2754                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
2755                 if (!set->p[i])
2756                         goto error;
2757         }
2758         return set;
2759 error:
2760         isl_set_free(set);
2761         return NULL;
2762 }
2763
2764 struct isl_map *isl_map_reverse(struct isl_map *map)
2765 {
2766         int i;
2767         unsigned t;
2768
2769         map = isl_map_cow(map);
2770         if (!map)
2771                 return NULL;
2772
2773         map->dim = isl_dim_reverse(map->dim);
2774         if (!map->dim)
2775                 goto error;
2776         for (i = 0; i < map->n; ++i) {
2777                 map->p[i] = isl_basic_map_reverse(map->p[i]);
2778                 if (!map->p[i])
2779                         goto error;
2780         }
2781         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2782         return map;
2783 error:
2784         isl_map_free(map);
2785         return NULL;
2786 }
2787
2788 struct isl_map *isl_basic_map_lexmax(
2789                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
2790                 struct isl_set **empty)
2791 {
2792         return isl_pip_basic_map_lexmax(bmap, dom, empty);
2793 }
2794
2795 struct isl_map *isl_basic_map_lexmin(
2796                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
2797                 struct isl_set **empty)
2798 {
2799         return isl_pip_basic_map_lexmin(bmap, dom, empty);
2800 }
2801
2802 struct isl_set *isl_basic_set_lexmin(struct isl_basic_set *bset)
2803 {
2804         struct isl_basic_map *bmap = NULL;
2805         struct isl_basic_set *dom = NULL;
2806         struct isl_map *min;
2807         struct isl_dim *param_dim;
2808
2809         if (!bset)
2810                 goto error;
2811         bmap = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
2812         if (!bmap)
2813                 goto error;
2814         param_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
2815         dom = isl_basic_set_universe(param_dim);
2816         if (!dom)
2817                 goto error;
2818         min = isl_basic_map_lexmin(bmap, dom, NULL);
2819         return isl_map_range(min);
2820 error:
2821         isl_basic_map_free(bmap);
2822         return NULL;
2823 }
2824
2825 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
2826 {
2827         int i;
2828         unsigned off;
2829
2830         if (!bmap)
2831                 return NULL;
2832         off = isl_dim_total(bmap->dim);
2833         for (i = 0; i < bmap->n_div; ++i) {
2834                 if (isl_int_is_zero(bmap->div[i][0]))
2835                         return isl_pip_basic_map_compute_divs(bmap);
2836                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
2837                                 goto error);
2838         }
2839         return isl_map_from_basic_map(bmap);
2840 error:
2841         isl_basic_map_free(bmap);
2842         return NULL;
2843 }
2844
2845 struct isl_map *isl_map_compute_divs(struct isl_map *map)
2846 {
2847         int i;
2848         struct isl_map *res;
2849
2850         if (!map)
2851                 return NULL;
2852         if (map->n == 0)
2853                 return map;
2854         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
2855         for (i = 1 ; i < map->n; ++i) {
2856                 struct isl_map *r2;
2857                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
2858                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
2859                         res = isl_map_union_disjoint(res, r2);
2860                 else
2861                         res = isl_map_union(res, r2);
2862         }
2863         isl_map_free(map);
2864
2865         return res;
2866 }
2867
2868 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
2869 {
2870         return (struct isl_set *)
2871                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
2872 }
2873
2874 struct isl_set *isl_set_compute_divs(struct isl_set *set)
2875 {
2876         return (struct isl_set *)
2877                 isl_map_compute_divs((struct isl_map *)set);
2878 }
2879
2880 struct isl_set *isl_map_domain(struct isl_map *map)
2881 {
2882         int i;
2883         struct isl_set *set;
2884
2885         if (!map)
2886                 goto error;
2887
2888         map = isl_map_cow(map);
2889         if (!map)
2890                 return NULL;
2891
2892         set = (struct isl_set *)map;
2893         set->dim = isl_dim_domain(set->dim);
2894         if (!set->dim)
2895                 goto error;
2896         for (i = 0; i < map->n; ++i) {
2897                 set->p[i] = isl_basic_map_domain(map->p[i]);
2898                 if (!set->p[i])
2899                         goto error;
2900         }
2901         ISL_F_CLR(set, ISL_MAP_DISJOINT);
2902         ISL_F_CLR(set, ISL_SET_NORMALIZED);
2903         return set;
2904 error:
2905         isl_map_free(map);
2906         return NULL;
2907 }
2908
2909 struct isl_map *isl_map_union_disjoint(
2910                         struct isl_map *map1, struct isl_map *map2)
2911 {
2912         int i;
2913         unsigned flags = 0;
2914         struct isl_map *map = NULL;
2915
2916         if (!map1 || !map2)
2917                 goto error;
2918
2919         if (map1->n == 0) {
2920                 isl_map_free(map1);
2921                 return map2;
2922         }
2923         if (map2->n == 0) {
2924                 isl_map_free(map2);
2925                 return map1;
2926         }
2927
2928         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2929
2930         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
2931             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
2932                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
2933
2934         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2935                                 map1->n + map2->n, flags);
2936         if (!map)
2937                 goto error;
2938         for (i = 0; i < map1->n; ++i) {
2939                 map = isl_map_add(map,
2940                                   isl_basic_map_copy(map1->p[i]));
2941                 if (!map)
2942                         goto error;
2943         }
2944         for (i = 0; i < map2->n; ++i) {
2945                 map = isl_map_add(map,
2946                                   isl_basic_map_copy(map2->p[i]));
2947                 if (!map)
2948                         goto error;
2949         }
2950         isl_map_free(map1);
2951         isl_map_free(map2);
2952         return map;
2953 error:
2954         isl_map_free(map);
2955         isl_map_free(map1);
2956         isl_map_free(map2);
2957         return NULL;
2958 }
2959
2960 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
2961 {
2962         map1 = isl_map_union_disjoint(map1, map2);
2963         if (!map1)
2964                 return NULL;
2965         if (map1->n > 1)
2966                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
2967         return map1;
2968 }
2969
2970 struct isl_set *isl_set_union_disjoint(
2971                         struct isl_set *set1, struct isl_set *set2)
2972 {
2973         return (struct isl_set *)
2974                 isl_map_union_disjoint(
2975                         (struct isl_map *)set1, (struct isl_map *)set2);
2976 }
2977
2978 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
2979 {
2980         return (struct isl_set *)
2981                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
2982 }
2983
2984 struct isl_map *isl_map_intersect_range(
2985                 struct isl_map *map, struct isl_set *set)
2986 {
2987         unsigned flags = 0;
2988         struct isl_map *result;
2989         int i, j;
2990
2991         if (!map || !set)
2992                 goto error;
2993
2994         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
2995             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
2996                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
2997
2998         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
2999                                         map->n * set->n, flags);
3000         if (!result)
3001                 goto error;
3002         for (i = 0; i < map->n; ++i)
3003                 for (j = 0; j < set->n; ++j) {
3004                         result = isl_map_add(result,
3005                             isl_basic_map_intersect_range(
3006                                 isl_basic_map_copy(map->p[i]),
3007                                 isl_basic_set_copy(set->p[j])));
3008                         if (!result)
3009                                 goto error;
3010                 }
3011         isl_map_free(map);
3012         isl_set_free(set);
3013         return result;
3014 error:
3015         isl_map_free(map);
3016         isl_set_free(set);
3017         return NULL;
3018 }
3019
3020 struct isl_map *isl_map_intersect_domain(
3021                 struct isl_map *map, struct isl_set *set)
3022 {
3023         return isl_map_reverse(
3024                 isl_map_intersect_range(isl_map_reverse(map), set));
3025 }
3026
3027 struct isl_map *isl_map_apply_domain(
3028                 struct isl_map *map1, struct isl_map *map2)
3029 {
3030         if (!map1 || !map2)
3031                 goto error;
3032         map1 = isl_map_reverse(map1);
3033         map1 = isl_map_apply_range(map1, map2);
3034         return isl_map_reverse(map1);
3035 error:
3036         isl_map_free(map1);
3037         isl_map_free(map2);
3038         return NULL;
3039 }
3040
3041 struct isl_map *isl_map_apply_range(
3042                 struct isl_map *map1, struct isl_map *map2)
3043 {
3044         struct isl_dim *dim_result;
3045         struct isl_map *result;
3046         int i, j;
3047         unsigned nparam;
3048         unsigned n_in;
3049         unsigned n_out;
3050
3051         if (!map1 || !map2)
3052                 goto error;
3053
3054         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
3055                                   isl_dim_copy(map2->dim));
3056
3057         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
3058         if (!result)
3059                 goto error;
3060         for (i = 0; i < map1->n; ++i)
3061                 for (j = 0; j < map2->n; ++j) {
3062                         result = isl_map_add(result,
3063                             isl_basic_map_apply_range(
3064                                 isl_basic_map_copy(map1->p[i]),
3065                                 isl_basic_map_copy(map2->p[j])));
3066                         if (!result)
3067                                 goto error;
3068                 }
3069         isl_map_free(map1);
3070         isl_map_free(map2);
3071         if (result && result->n <= 1)
3072                 ISL_F_SET(result, ISL_MAP_DISJOINT);
3073         return result;
3074 error:
3075         isl_map_free(map1);
3076         isl_map_free(map2);
3077         return NULL;
3078 }
3079
3080 /*
3081  * returns range - domain
3082  */
3083 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
3084 {
3085         struct isl_basic_set *bset;
3086         unsigned dim;
3087         unsigned nparam;
3088         int i;
3089
3090         if (!bmap)
3091                 goto error;
3092         dim = isl_basic_map_n_in(bmap);
3093         nparam = isl_basic_map_n_param(bmap);
3094         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
3095         bset = isl_basic_set_from_basic_map(bmap);
3096         bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
3097         bset = isl_basic_set_swap_vars(bset, 2*dim);
3098         for (i = 0; i < dim; ++i) {
3099                 int j = isl_basic_map_alloc_equality(
3100                                             (struct isl_basic_map *)bset);
3101                 if (j < 0)
3102                         goto error;
3103                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
3104                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
3105                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
3106                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
3107         }
3108         return isl_basic_set_project_out(bset, 2*dim, 0);
3109 error:
3110         isl_basic_map_free(bmap);
3111         return NULL;
3112 }
3113
3114 /*
3115  * returns range - domain
3116  */
3117 struct isl_set *isl_map_deltas(struct isl_map *map)
3118 {
3119         int i;
3120         struct isl_set *result;
3121
3122         if (!map)
3123                 return NULL;
3124
3125         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
3126         result = isl_set_alloc(map->ctx, isl_map_n_param(map),
3127                                         isl_map_n_in(map), map->n, map->flags);
3128         if (!result)
3129                 goto error;
3130         for (i = 0; i < map->n; ++i)
3131                 result = isl_set_add(result,
3132                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
3133         isl_map_free(map);
3134         return result;
3135 error:
3136         isl_map_free(map);
3137         return NULL;
3138 }
3139
3140 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
3141 {
3142         struct isl_basic_map *bmap;
3143         unsigned nparam;
3144         unsigned dim;
3145         int i;
3146
3147         if (!dims)
3148                 return NULL;
3149
3150         nparam = dims->nparam;
3151         dim = dims->n_out;
3152         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
3153         if (!bmap)
3154                 goto error;
3155
3156         for (i = 0; i < dim; ++i) {
3157                 int j = isl_basic_map_alloc_equality(bmap);
3158                 if (j < 0)
3159                         goto error;
3160                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3161                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
3162                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
3163         }
3164         return isl_basic_map_finalize(bmap);
3165 error:
3166         isl_basic_map_free(bmap);
3167         return NULL;
3168 }
3169
3170 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
3171 {
3172         struct isl_dim *dim = isl_dim_map(set_dim);
3173         if (!dim)
3174                 return NULL;
3175         return basic_map_identity(dim);
3176 }
3177
3178 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
3179 {
3180         if (!model || !model->dim)
3181                 return NULL;
3182         isl_assert(model->ctx,
3183                         model->dim->n_in == model->dim->n_out, return NULL);
3184         return basic_map_identity(isl_dim_copy(model->dim));
3185 }
3186
3187 static struct isl_map *map_identity(struct isl_dim *dim)
3188 {
3189         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
3190         return isl_map_add(map, basic_map_identity(isl_dim_copy(dim)));
3191 }
3192
3193 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
3194 {
3195         struct isl_dim *dim = isl_dim_map(set_dim);
3196         if (!dim)
3197                 return NULL;
3198         return map_identity(dim);
3199 }
3200
3201 struct isl_map *isl_map_identity_like(struct isl_basic_map *model)
3202 {
3203         if (!model || !model->dim)
3204                 return NULL;
3205         isl_assert(model->ctx,
3206                         model->dim->n_in == model->dim->n_out, return NULL);
3207         return map_identity(isl_dim_copy(model->dim));
3208 }
3209
3210 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
3211 {
3212         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
3213 }
3214
3215 int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
3216 {
3217         return isl_map_is_subset(
3218                         (struct isl_map *)set1, (struct isl_map *)set2);
3219 }
3220
3221 int isl_basic_map_is_subset(
3222                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3223 {
3224         int is_subset;
3225         struct isl_map *map1;
3226         struct isl_map *map2;
3227
3228         if (!bmap1 || !bmap2)
3229                 return -1;
3230
3231         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
3232         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
3233
3234         is_subset = isl_map_is_subset(map1, map2);
3235
3236         isl_map_free(map1);
3237         isl_map_free(map2);
3238
3239         return is_subset;
3240 }
3241
3242 int isl_basic_map_is_equal(
3243                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3244 {
3245         int is_subset;
3246
3247         if (!bmap1 || !bmap2)
3248                 return -1;
3249         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
3250         if (is_subset != 1)
3251                 return is_subset;
3252         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
3253         return is_subset;
3254 }
3255
3256 int isl_basic_set_is_equal(
3257                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
3258 {
3259         return isl_basic_map_is_equal(
3260                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
3261 }
3262
3263 int isl_map_is_empty(struct isl_map *map)
3264 {
3265         int i;
3266         int is_empty;
3267
3268         if (!map)
3269                 return -1;
3270         for (i = 0; i < map->n; ++i) {
3271                 is_empty = isl_basic_map_is_empty(map->p[i]);
3272                 if (is_empty < 0)
3273                         return -1;
3274                 if (!is_empty)
3275                         return 0;
3276         }
3277         return 1;
3278 }
3279
3280 int isl_map_fast_is_empty(struct isl_map *map)
3281 {
3282         return map->n == 0;
3283 }
3284
3285 int isl_set_is_empty(struct isl_set *set)
3286 {
3287         return isl_map_is_empty((struct isl_map *)set);
3288 }
3289
3290 int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2)
3291 {
3292         int i;
3293         int is_subset = 0;
3294         struct isl_map *diff;
3295
3296         if (!map1 || !map2)
3297                 return -1;
3298
3299         if (isl_map_is_empty(map1))
3300                 return 1;
3301
3302         if (isl_map_is_empty(map2))
3303                 return 0;
3304
3305         diff = isl_map_subtract(isl_map_copy(map1), isl_map_copy(map2));
3306         if (!diff)
3307                 return -1;
3308
3309         is_subset = isl_map_is_empty(diff);
3310         isl_map_free(diff);
3311
3312         return is_subset;
3313 }
3314
3315 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
3316 {
3317         int is_subset;
3318
3319         if (!map1 || !map2)
3320                 return -1;
3321         is_subset = isl_map_is_subset(map1, map2);
3322         if (is_subset != 1)
3323                 return is_subset;
3324         is_subset = isl_map_is_subset(map2, map1);
3325         return is_subset;
3326 }
3327
3328 int isl_basic_map_is_strict_subset(
3329                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3330 {
3331         int is_subset;
3332
3333         if (!bmap1 || !bmap2)
3334                 return -1;
3335         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
3336         if (is_subset != 1)
3337                 return is_subset;
3338         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
3339         if (is_subset == -1)
3340                 return is_subset;
3341         return !is_subset;
3342 }
3343
3344 static int basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
3345 {
3346         int i;
3347         unsigned total;
3348         isl_int s;
3349
3350         total = 1 + isl_basic_map_total_dim(bmap);
3351         if (total != vec->size)
3352                 return -1;
3353
3354         isl_int_init(s);
3355
3356         for (i = 0; i < bmap->n_eq; ++i) {
3357                 isl_seq_inner_product(vec->block.data, bmap->eq[i], total, &s);
3358                 if (!isl_int_is_zero(s)) {
3359                         isl_int_clear(s);
3360                         return 0;
3361                 }
3362         }
3363
3364         for (i = 0; i < bmap->n_ineq; ++i) {
3365                 isl_seq_inner_product(vec->block.data, bmap->ineq[i], total, &s);
3366                 if (isl_int_is_neg(s)) {
3367                         isl_int_clear(s);
3368                         return 0;
3369                 }
3370         }
3371
3372         isl_int_clear(s);
3373
3374         return 1;
3375 }
3376
3377 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
3378 {
3379         if (!bmap)
3380                 return -1;
3381         return bmap->n_eq == 0 && bmap->n_ineq == 0;
3382 }
3383
3384 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
3385 {
3386         struct isl_basic_set *bset = NULL;
3387         struct isl_vec *sample = NULL;
3388         int empty;
3389         unsigned total;
3390
3391         if (!bmap)
3392                 return -1;
3393
3394         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
3395                 return 1;
3396
3397         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
3398                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
3399                 copy = isl_basic_map_convex_hull(copy);
3400                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
3401                 isl_basic_map_free(copy);
3402                 return empty;
3403         }
3404
3405         total = 1 + isl_basic_map_total_dim(bmap);
3406         if (bmap->sample && bmap->sample->size == total) {
3407                 int contains = basic_map_contains(bmap, bmap->sample);
3408                 if (contains < 0)
3409                         return -1;
3410                 if (contains)
3411                         return 0;
3412         }
3413         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
3414         if (!bset)
3415                 return -1;
3416         sample = isl_basic_set_sample(bset);
3417         if (!sample)
3418                 return -1;
3419         empty = sample->size == 0;
3420         if (bmap->sample)
3421                 isl_vec_free(bmap->ctx, bmap->sample);
3422         bmap->sample = sample;
3423
3424         return empty;
3425 }
3426
3427 int isl_basic_set_is_empty(struct isl_basic_set *bset)
3428 {
3429         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
3430 }
3431
3432 struct isl_map *isl_basic_map_union(
3433         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3434 {
3435         struct isl_map *map;
3436         if (!bmap1 || !bmap2)
3437                 return NULL;
3438
3439         isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
3440
3441         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
3442         if (!map)
3443                 goto error;
3444         map = isl_map_add(map, bmap1);
3445         map = isl_map_add(map, bmap2);
3446         return map;
3447 error:
3448         isl_basic_map_free(bmap1);
3449         isl_basic_map_free(bmap2);
3450         return NULL;
3451 }
3452
3453 struct isl_set *isl_basic_set_union(
3454                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
3455 {
3456         return (struct isl_set *)isl_basic_map_union(
3457                                             (struct isl_basic_map *)bset1,
3458                                             (struct isl_basic_map *)bset2);
3459 }
3460
3461 /* Order divs such that any div only depends on previous divs */
3462 static struct isl_basic_map *order_divs(struct isl_basic_map *bmap)
3463 {
3464         int i;
3465         unsigned off = isl_dim_total(bmap->dim);
3466
3467         for (i = 0; i < bmap->n_div; ++i) {
3468                 int pos;
3469                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
3470                                                             bmap->n_div-i);
3471                 if (pos == -1)
3472                         continue;
3473                 swap_div(bmap, i, pos);
3474                 --i;
3475         }
3476         return bmap;
3477 }
3478
3479 /* Look for a div in dst that corresponds to the div "div" in src.
3480  * The divs before "div" in src and dst are assumed to be the same.
3481  *
3482  * Returns -1 if no corresponding div was found and the position
3483  * of the corresponding div in dst otherwise.
3484  */
3485 static int find_div(struct isl_basic_map *dst,
3486                         struct isl_basic_map *src, unsigned div)
3487 {
3488         int i;
3489
3490         unsigned total = isl_dim_total(src->dim);
3491
3492         isl_assert(dst->ctx, div <= dst->n_div, return -1);
3493         for (i = div; i < dst->n_div; ++i)
3494                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
3495                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
3496                                                 dst->n_div - div) == -1)
3497                         return i;
3498         return -1;
3499 }
3500
3501 struct isl_basic_map *isl_basic_map_align_divs(
3502                 struct isl_basic_map *dst, struct isl_basic_map *src)
3503 {
3504         int i;
3505         unsigned total = isl_dim_total(src->dim);
3506
3507         if (!dst || !src)
3508                 goto error;
3509
3510         if (src->n_div == 0)
3511                 return dst;
3512
3513         for (i = 0; i < src->n_div; ++i)
3514                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
3515
3516         src = order_divs(src);
3517         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
3518                         src->n_div, 0, 2 * src->n_div);
3519         if (!dst)
3520                 return NULL;
3521         for (i = 0; i < src->n_div; ++i) {
3522                 int j = find_div(dst, src, i);
3523                 if (j < 0) {
3524                         j = isl_basic_map_alloc_div(dst);
3525                         if (j < 0)
3526                                 goto error;
3527                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
3528                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
3529                         if (add_div_constraints(dst, j) < 0)
3530                                 goto error;
3531                 }
3532                 if (j != i)
3533                         swap_div(dst, i, j);
3534         }
3535         return dst;
3536 error:
3537         isl_basic_map_free(dst);
3538         return NULL;
3539 }
3540
3541 struct isl_basic_set *isl_basic_set_align_divs(
3542                 struct isl_basic_set *dst, struct isl_basic_set *src)
3543 {
3544         return (struct isl_basic_set *)isl_basic_map_align_divs(
3545                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
3546 }
3547
3548 struct isl_map *isl_map_align_divs(struct isl_map *map)
3549 {
3550         int i;
3551
3552         map = isl_map_compute_divs(map);
3553         map = isl_map_cow(map);
3554         if (!map)
3555                 return NULL;
3556
3557         for (i = 1; i < map->n; ++i)
3558                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
3559         for (i = 1; i < map->n; ++i)
3560                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
3561
3562         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3563         return map;
3564 }
3565
3566 static struct isl_map *add_cut_constraint(struct isl_map *dst,
3567                 struct isl_basic_map *src, isl_int *c,
3568                 unsigned len, int oppose)
3569 {
3570         struct isl_basic_map *copy = NULL;
3571         int is_empty;
3572         int k;
3573         unsigned total;
3574
3575         copy = isl_basic_map_copy(src);
3576         copy = isl_basic_map_cow(copy);
3577         if (!copy)
3578                 goto error;
3579         copy = isl_basic_map_extend_constraints(copy, 0, 1);
3580         k = isl_basic_map_alloc_inequality(copy);
3581         if (k < 0)
3582                 goto error;
3583         if (oppose)
3584                 isl_seq_neg(copy->ineq[k], c, len);
3585         else
3586                 isl_seq_cpy(copy->ineq[k], c, len);
3587         total = 1 + isl_basic_map_total_dim(copy);
3588         isl_seq_clr(copy->ineq[k]+len, total - len);
3589         isl_inequality_negate(copy, k);
3590         copy = isl_basic_map_simplify(copy);
3591         copy = isl_basic_map_finalize(copy);
3592         is_empty = isl_basic_map_is_empty(copy);
3593         if (is_empty < 0)
3594                 goto error;
3595         if (!is_empty)
3596                 dst = isl_map_add(dst, copy);
3597         else
3598                 isl_basic_map_free(copy);
3599         return dst;
3600 error:
3601         isl_basic_map_free(copy);
3602         isl_map_free(dst);
3603         return NULL;
3604 }
3605
3606 static struct isl_map *subtract(struct isl_map *map, struct isl_basic_map *bmap)
3607 {
3608         int i, j, k;
3609         unsigned flags = 0;
3610         struct isl_map *rest = NULL;
3611         unsigned max;
3612         unsigned total = isl_basic_map_total_dim(bmap);
3613
3614         assert(bmap);
3615
3616         if (!map)
3617                 goto error;
3618
3619         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
3620                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
3621
3622         max = map->n * (2 * bmap->n_eq + bmap->n_ineq);
3623         rest = isl_map_alloc_dim(isl_dim_copy(map->dim), max, flags);
3624         if (!rest)
3625                 goto error;
3626
3627         for (i = 0; i < map->n; ++i) {
3628                 map->p[i] = isl_basic_map_align_divs(map->p[i], bmap);
3629                 if (!map->p[i])
3630                         goto error;
3631         }
3632
3633         for (j = 0; j < map->n; ++j)
3634                 map->p[j] = isl_basic_map_cow(map->p[j]);
3635
3636         for (i = 0; i < bmap->n_eq; ++i) {
3637                 for (j = 0; j < map->n; ++j) {
3638                         rest = add_cut_constraint(rest,
3639                                 map->p[j], bmap->eq[i], 1+total, 0);
3640                         if (!rest)
3641                                 goto error;
3642
3643                         rest = add_cut_constraint(rest,
3644                                 map->p[j], bmap->eq[i], 1+total, 1);
3645                         if (!rest)
3646                                 goto error;
3647
3648                         map->p[j] = isl_basic_map_extend_constraints(map->p[j],
3649                                 1, 0);
3650                         if (!map->p[j])
3651                                 goto error;
3652                         k = isl_basic_map_alloc_equality(map->p[j]);
3653                         if (k < 0)
3654                                 goto error;
3655                         isl_seq_cpy(map->p[j]->eq[k], bmap->eq[i], 1+total);
3656                         isl_seq_clr(map->p[j]->eq[k]+1+total,
3657                                         map->p[j]->n_div - bmap->n_div);
3658                 }
3659         }
3660
3661         for (i = 0; i < bmap->n_ineq; ++i) {
3662                 for (j = 0; j < map->n; ++j) {
3663                         rest = add_cut_constraint(rest,
3664                                 map->p[j], bmap->ineq[i], 1+total, 0);
3665                         if (!rest)
3666                                 goto error;
3667
3668                         map->p[j] = isl_basic_map_extend_constraints(map->p[j],
3669                                 0, 1);
3670                         if (!map->p[j])
3671                                 goto error;
3672                         k = isl_basic_map_alloc_inequality(map->p[j]);
3673                         if (k < 0)
3674                                 goto error;
3675                         isl_seq_cpy(map->p[j]->ineq[k], bmap->ineq[i], 1+total);
3676                         isl_seq_clr(map->p[j]->ineq[k]+1+total,
3677                                         map->p[j]->n_div - bmap->n_div);
3678                 }
3679         }
3680
3681         isl_map_free(map);
3682         return rest;
3683 error:
3684         isl_map_free(map);
3685         isl_map_free(rest);
3686         return NULL;
3687 }
3688
3689 struct isl_map *isl_map_subtract(struct isl_map *map1, struct isl_map *map2)
3690 {
3691         int i;
3692         if (!map1 || !map2)
3693                 goto error;
3694
3695         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
3696
3697         if (isl_map_is_empty(map2)) {
3698                 isl_map_free(map2);
3699                 return map1;
3700         }
3701
3702         map1 = isl_map_compute_divs(map1);
3703         map2 = isl_map_compute_divs(map2);
3704         if (!map1 || !map2)
3705                 goto error;
3706
3707         for (i = 0; map1 && i < map2->n; ++i)
3708                 map1 = subtract(map1, map2->p[i]);
3709
3710         isl_map_free(map2);
3711         return map1;
3712 error:
3713         isl_map_free(map1);
3714         isl_map_free(map2);
3715         return NULL;
3716 }
3717
3718 struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2)
3719 {
3720         return (struct isl_set *)
3721                 isl_map_subtract(
3722                         (struct isl_map *)set1, (struct isl_map *)set2);
3723 }
3724
3725 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
3726 {
3727         if (!set || !map)
3728                 goto error;
3729         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
3730         map = isl_map_intersect_domain(map, set);
3731         set = isl_map_range(map);
3732         return set;
3733 error:
3734         isl_set_free(set);
3735         isl_map_free(map);
3736         return NULL;
3737 }
3738
3739 /* There is no need to cow as removing empty parts doesn't change
3740  * the meaning of the set.
3741  */
3742 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
3743 {
3744         int i;
3745
3746         if (!map)
3747                 return NULL;
3748
3749         for (i = map->n-1; i >= 0; --i) {
3750                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
3751                         continue;
3752                 isl_basic_map_free(map->p[i]);
3753                 if (i != map->n-1) {
3754                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3755                         map->p[i] = map->p[map->n-1];
3756                 }
3757                 map->n--;
3758         }
3759
3760         return map;
3761 }
3762
3763 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
3764 {
3765         return (struct isl_set *)
3766                 isl_map_remove_empty_parts((struct isl_map *)set);
3767 }
3768
3769 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
3770 {
3771         struct isl_basic_map *bmap;
3772         if (!map || map->n == 0)
3773                 return NULL;
3774         bmap = map->p[map->n-1];
3775         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
3776         return isl_basic_map_copy(bmap);
3777 }
3778
3779 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
3780 {
3781         (struct isl_basic_set *)isl_map_copy_basic_map((struct isl_map *)set);
3782 }
3783
3784 struct isl_map *isl_map_drop_basic_map(struct isl_map *map,
3785                                                 struct isl_basic_map *bmap)
3786 {
3787         int i;
3788
3789         if (!map || !bmap)
3790                 goto error;
3791         for (i = map->n-1; i >= 0; --i) {
3792                 if (map->p[i] != bmap)
3793                         continue;
3794                 map = isl_map_cow(map);
3795                 if (!map)
3796                         goto error;
3797                 isl_basic_map_free(map->p[i]);
3798                 if (i != map->n-1) {
3799                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
3800                         map->p[i] = map->p[map->n-1];
3801                 }
3802                 map->n--;
3803                 return map;
3804         }
3805         isl_basic_map_free(bmap);
3806         return map;
3807 error:
3808         isl_map_free(map);
3809         isl_basic_map_free(bmap);
3810         return NULL;
3811 }
3812
3813 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
3814                                                 struct isl_basic_set *bset)
3815 {
3816         (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
3817                                                 (struct isl_basic_map *)bset);
3818 }
3819
3820 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
3821  * for any common value of the parameters and dimensions preceding dim
3822  * in both basic sets, the values of dimension pos in bset1 are
3823  * smaller or larger than those in bset2.
3824  *
3825  * Returns
3826  *       1 if bset1 follows bset2
3827  *      -1 if bset1 precedes bset2
3828  *       0 if bset1 and bset2 are incomparable
3829  *      -2 if some error occurred.
3830  */
3831 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
3832         struct isl_basic_set *bset2, int pos)
3833 {
3834         struct isl_dim *dims;
3835         struct isl_basic_map *bmap1 = NULL;
3836         struct isl_basic_map *bmap2 = NULL;
3837         struct isl_ctx *ctx;
3838         struct isl_vec *obj;
3839         unsigned total;
3840         unsigned nparam;
3841         unsigned dim1, dim2;
3842         isl_int num, den;
3843         enum isl_lp_result res;
3844         int cmp;
3845
3846         if (!bset1 || !bset2)
3847                 return -2;
3848
3849         nparam = isl_basic_set_n_param(bset1);
3850         dim1 = isl_basic_set_n_dim(bset1);
3851         dim2 = isl_basic_set_n_dim(bset2);
3852         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
3853         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
3854         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
3855         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
3856         if (!bmap1 || !bmap2)
3857                 goto error;
3858         bmap1 = isl_basic_map_extend(bmap1, nparam,
3859                         pos, (dim1 - pos) + (dim2 - pos),
3860                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
3861         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
3862         if (!bmap1)
3863                 goto error;
3864         total = isl_basic_map_total_dim(bmap1);
3865         ctx = bmap1->ctx;
3866         obj = isl_vec_alloc(ctx, total);
3867         isl_seq_clr(obj->block.data, total);
3868         isl_int_set_si(obj->block.data[nparam+pos], 1);
3869         isl_int_set_si(obj->block.data[nparam+pos+(dim1-pos)], -1);
3870         if (!obj)
3871                 goto error;
3872         isl_int_init(num);
3873         isl_int_init(den);
3874         res = isl_solve_lp(bmap1, 0, obj->block.data, ctx->one, &num, &den);
3875         if (res == isl_lp_empty)
3876                 cmp = 0;
3877         else if (res == isl_lp_ok && isl_int_is_pos(num))
3878                 cmp = 1;
3879         else if ((res == isl_lp_ok && isl_int_is_neg(num)) ||
3880                   res == isl_lp_unbounded)
3881                 cmp = -1;
3882         else
3883                 cmp = -2;
3884         isl_int_clear(num);
3885         isl_int_clear(den);
3886         isl_basic_map_free(bmap1);
3887         isl_vec_free(ctx, obj);
3888         return cmp;
3889 error:
3890         isl_basic_map_free(bmap1);
3891         isl_basic_map_free(bmap2);
3892         return -2;
3893 }
3894
3895 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
3896         unsigned pos, isl_int *val)
3897 {
3898         int i;
3899         int d;
3900         unsigned total;
3901
3902         if (!bmap)
3903                 return -1;
3904         total = isl_basic_map_total_dim(bmap);
3905         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
3906                 for (; d+1 > pos; --d)
3907                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
3908                                 break;
3909                 if (d != pos)
3910                         continue;
3911                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
3912                         return 0;
3913                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
3914                         return 0;
3915                 if (!isl_int_is_one(bmap->eq[i][1+d]))
3916                         return 0;
3917                 if (val)
3918                         isl_int_neg(*val, bmap->eq[i][0]);
3919                 return 1;
3920         }
3921         return 0;
3922 }
3923
3924 static int isl_map_fast_has_fixed_var(struct isl_map *map,
3925         unsigned pos, isl_int *val)
3926 {
3927         int i;
3928         isl_int v;
3929         isl_int tmp;
3930         int fixed;
3931
3932         if (!map)
3933                 return -1;
3934         if (map->n == 0)
3935                 return 0;
3936         if (map->n == 1)
3937                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
3938         isl_int_init(v);
3939         isl_int_init(tmp);
3940         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
3941         for (i = 1; fixed == 1 && i < map->n; ++i) {
3942                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
3943                 if (fixed == 1 && isl_int_ne(tmp, v))
3944                         fixed = 0;
3945         }
3946         if (val)
3947                 isl_int_set(*val, v);
3948         isl_int_clear(tmp);
3949         isl_int_clear(v);
3950         return fixed;
3951 }
3952
3953 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
3954         isl_int *val)
3955 {
3956         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
3957 }
3958
3959 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
3960         enum isl_dim_type type, unsigned pos, isl_int *val)
3961 {
3962         if (pos >= isl_basic_map_dim(bmap, type))
3963                 return -1;
3964         return isl_basic_map_fast_has_fixed_var(bmap,
3965                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
3966 }
3967
3968 /* Check if dimension dim has fixed value and if so and if val is not NULL,
3969  * then return this fixed value in *val.
3970  */
3971 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
3972 {
3973         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
3974 }
3975
3976 /* Check if input variable in has fixed value and if so and if val is not NULL,
3977  * then return this fixed value in *val.
3978  */
3979 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
3980 {
3981         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
3982 }
3983
3984 /* Check if dimension dim has an (obvious) fixed lower bound and if so
3985  * and if val is not NULL, then return this lower bound in *val.
3986  */
3987 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
3988         unsigned dim, isl_int *val)
3989 {
3990         int i, i_eq = -1, i_ineq = -1;
3991         isl_int *c;
3992         unsigned total;
3993         unsigned nparam;
3994
3995         if (!bset)
3996                 return -1;
3997         total = isl_basic_set_total_dim(bset);
3998         nparam = isl_basic_set_n_param(bset);
3999         for (i = 0; i < bset->n_eq; ++i) {
4000                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
4001                         continue;
4002                 if (i_eq != -1)
4003                         return 0;
4004                 i_eq = i;
4005         }
4006         for (i = 0; i < bset->n_ineq; ++i) {
4007                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
4008                         continue;
4009                 if (i_eq != -1 || i_ineq != -1)
4010                         return 0;
4011                 i_ineq = i;
4012         }
4013         if (i_eq == -1 && i_ineq == -1)
4014                 return 0;
4015         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
4016         /* The coefficient should always be one due to normalization. */
4017         if (!isl_int_is_one(c[1+nparam+dim]))
4018                 return 0;
4019         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
4020                 return 0;
4021         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
4022                                         total - nparam - dim - 1) != -1)
4023                 return 0;
4024         if (val)
4025                 isl_int_neg(*val, c[0]);
4026         return 1;
4027 }
4028
4029 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
4030         unsigned dim, isl_int *val)
4031 {
4032         int i;
4033         isl_int v;
4034         isl_int tmp;
4035         int fixed;
4036
4037         if (!set)
4038                 return -1;
4039         if (set->n == 0)
4040                 return 0;
4041         if (set->n == 1)
4042                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4043                                                                 dim, val);
4044         isl_int_init(v);
4045         isl_int_init(tmp);
4046         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4047                                                                 dim, &v);
4048         for (i = 1; fixed == 1 && i < set->n; ++i) {
4049                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
4050                                                                 dim, &tmp);
4051                 if (fixed == 1 && isl_int_ne(tmp, v))
4052                         fixed = 0;
4053         }
4054         if (val)
4055                 isl_int_set(*val, v);
4056         isl_int_clear(tmp);
4057         isl_int_clear(v);
4058         return fixed;
4059 }
4060
4061 struct constraint {
4062         unsigned        size;
4063         isl_int         *c;
4064 };
4065
4066 static int qsort_constraint_cmp(const void *p1, const void *p2)
4067 {
4068         const struct constraint *c1 = (const struct constraint *)p1;
4069         const struct constraint *c2 = (const struct constraint *)p2;
4070         unsigned size = isl_min(c1->size, c2->size);
4071         return isl_seq_cmp(c1->c, c2->c, size);
4072 }
4073
4074 static struct isl_basic_map *isl_basic_map_sort_constraints(
4075         struct isl_basic_map *bmap)
4076 {
4077         int i;
4078         struct constraint *c;
4079         unsigned total;
4080
4081         if (!bmap)
4082                 return NULL;
4083         total = isl_basic_map_total_dim(bmap);
4084         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
4085         if (!c)
4086                 goto error;
4087         for (i = 0; i < bmap->n_ineq; ++i) {
4088                 c[i].size = total;
4089                 c[i].c = bmap->ineq[i];
4090         }
4091         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
4092         for (i = 0; i < bmap->n_ineq; ++i)
4093                 bmap->ineq[i] = c[i].c;
4094         free(c);
4095         return bmap;
4096 error:
4097         isl_basic_map_free(bmap);
4098         return NULL;
4099 }
4100
4101 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
4102 {
4103         if (!bmap)
4104                 return NULL;
4105         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
4106                 return bmap;
4107         bmap = isl_basic_map_convex_hull(bmap);
4108         bmap = isl_basic_map_sort_constraints(bmap);
4109         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
4110         return bmap;
4111 }
4112
4113 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
4114 {
4115         return (struct isl_basic_set *)isl_basic_map_normalize(
4116                                                 (struct isl_basic_map *)bset);
4117 }
4118
4119 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
4120         const struct isl_basic_map *bmap2)
4121 {
4122         int i, cmp;
4123         unsigned total;
4124
4125         if (bmap1 == bmap2)
4126                 return 0;
4127         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
4128                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
4129         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
4130                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
4131         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
4132                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
4133         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
4134             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
4135                 return 0;
4136         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
4137                 return 1;
4138         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
4139                 return -1;
4140         if (bmap1->n_eq != bmap2->n_eq)
4141                 return bmap1->n_eq - bmap2->n_eq;
4142         if (bmap1->n_ineq != bmap2->n_ineq)
4143                 return bmap1->n_ineq - bmap2->n_ineq;
4144         if (bmap1->n_div != bmap2->n_div)
4145                 return bmap1->n_div - bmap2->n_div;
4146         total = isl_basic_map_total_dim(bmap1);
4147         for (i = 0; i < bmap1->n_eq; ++i) {
4148                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
4149                 if (cmp)
4150                         return cmp;
4151         }
4152         for (i = 0; i < bmap1->n_ineq; ++i) {
4153                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
4154                 if (cmp)
4155                         return cmp;
4156         }
4157         for (i = 0; i < bmap1->n_div; ++i) {
4158                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
4159                 if (cmp)
4160                         return cmp;
4161         }
4162         return 0;
4163 }
4164
4165 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
4166         struct isl_basic_map *bmap2)
4167 {
4168         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
4169 }
4170
4171 static int qsort_bmap_cmp(const void *p1, const void *p2)
4172 {
4173         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
4174         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
4175
4176         return isl_basic_map_fast_cmp(bmap1, bmap2);
4177 }
4178
4179 /* We normalize in place, but if anything goes wrong we need
4180  * to return NULL, so we need to make sure we don't change the
4181  * meaning of any possible other copies of map.
4182  */
4183 struct isl_map *isl_map_normalize(struct isl_map *map)
4184 {
4185         int i, j;
4186         struct isl_basic_map *bmap;
4187
4188         if (!map)
4189                 return NULL;
4190         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
4191                 return map;
4192         for (i = 0; i < map->n; ++i) {
4193                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
4194                 if (!bmap)
4195                         goto error;
4196                 isl_basic_map_free(map->p[i]);
4197                 map->p[i] = bmap;
4198         }
4199         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
4200         ISL_F_SET(map, ISL_MAP_NORMALIZED);
4201         map = isl_map_remove_empty_parts(map);
4202         if (!map)
4203                 return NULL;
4204         for (i = map->n - 1; i >= 1; --i) {
4205                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
4206                         continue;
4207                 isl_basic_map_free(map->p[i-1]);
4208                 for (j = i; j < map->n; ++j)
4209                         map->p[j-1] = map->p[j];
4210                 map->n--;
4211         }
4212         return map;
4213 error:
4214         isl_map_free(map);
4215         return NULL;
4216
4217 }
4218
4219 struct isl_set *isl_set_normalize(struct isl_set *set)
4220 {
4221         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
4222 }
4223
4224 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
4225 {
4226         int i;
4227         int equal;
4228
4229         if (!map1 || !map2)
4230                 return -1;
4231
4232         if (map1 == map2)
4233                 return 1;
4234         if (!isl_dim_equal(map1->dim, map2->dim))
4235                 return 0;
4236
4237         map1 = isl_map_copy(map1);
4238         map2 = isl_map_copy(map2);
4239         map1 = isl_map_normalize(map1);
4240         map2 = isl_map_normalize(map2);
4241         if (!map1 || !map2)
4242                 goto error;
4243         equal = map1->n == map2->n;
4244         for (i = 0; equal && i < map1->n; ++i) {
4245                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
4246                 if (equal < 0)
4247                         goto error;
4248         }
4249         isl_map_free(map1);
4250         isl_map_free(map2);
4251         return equal;
4252 error:
4253         isl_map_free(map1);
4254         isl_map_free(map2);
4255         return -1;
4256 }
4257
4258 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
4259 {
4260         return isl_map_fast_is_equal((struct isl_map *)set1,
4261                                                 (struct isl_map *)set2);
4262 }
4263
4264 /* Return an interval that ranges from min to max (inclusive)
4265  */
4266 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
4267         isl_int min, isl_int max)
4268 {
4269         int k;
4270         struct isl_basic_set *bset = NULL;
4271
4272         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
4273         if (!bset)
4274                 goto error;
4275
4276         k = isl_basic_set_alloc_inequality(bset);
4277         if (k < 0)
4278                 goto error;
4279         isl_int_set_si(bset->ineq[k][1], 1);
4280         isl_int_neg(bset->ineq[k][0], min);
4281
4282         k = isl_basic_set_alloc_inequality(bset);
4283         if (k < 0)
4284                 goto error;
4285         isl_int_set_si(bset->ineq[k][1], -1);
4286         isl_int_set(bset->ineq[k][0], max);
4287
4288         return bset;
4289 error:
4290         isl_basic_set_free(bset);
4291         return NULL;
4292 }
4293
4294 /* Return the Cartesian product of the basic sets in list (in the given order).
4295  */
4296 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
4297 {
4298         int i;
4299         unsigned dim;
4300         unsigned nparam;
4301         unsigned extra;
4302         unsigned n_eq;
4303         unsigned n_ineq;
4304         struct isl_basic_set *product = NULL;
4305
4306         if (!list)
4307                 goto error;
4308         isl_assert(list->ctx, list->n > 0, goto error);
4309         isl_assert(list->ctx, list->p[0], goto error);
4310         nparam = isl_basic_set_n_param(list->p[0]);
4311         dim = isl_basic_set_n_dim(list->p[0]);
4312         extra = list->p[0]->n_div;
4313         n_eq = list->p[0]->n_eq;
4314         n_ineq = list->p[0]->n_ineq;
4315         for (i = 1; i < list->n; ++i) {
4316                 isl_assert(list->ctx, list->p[i], goto error);
4317                 isl_assert(list->ctx,
4318                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
4319                 dim += isl_basic_set_n_dim(list->p[i]);
4320                 extra += list->p[i]->n_div;
4321                 n_eq += list->p[i]->n_eq;
4322                 n_ineq += list->p[i]->n_ineq;
4323         }
4324         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
4325                                         n_eq, n_ineq);
4326         if (!product)
4327                 goto error;
4328         dim = 0;
4329         for (i = 0; i < list->n; ++i) {
4330                 isl_basic_set_add_constraints(product,
4331                                         isl_basic_set_copy(list->p[i]), dim);
4332                 dim += isl_basic_set_n_dim(list->p[i]);
4333         }
4334         isl_basic_set_list_free(list);
4335         return product;
4336 error:
4337         isl_basic_set_free(product);
4338         isl_basic_set_list_free(list);
4339         return NULL;
4340 }
4341
4342 struct isl_basic_map *isl_basic_map_product(
4343                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4344 {
4345         struct isl_dim *dim_result = NULL;
4346         struct isl_basic_map *bmap;
4347         unsigned in1, in2, out1, out2, nparam, total, pos;
4348         struct isl_dim_map *dim_map1, *dim_map2;
4349
4350         if (!bmap1 || !bmap2)
4351                 goto error;
4352
4353         isl_assert(map1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
4354                                      bmap2->dim, isl_dim_param), goto error);
4355         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
4356                                                    isl_dim_copy(bmap2->dim));
4357
4358         in1 = isl_basic_map_n_in(bmap1);
4359         in2 = isl_basic_map_n_in(bmap2);
4360         out1 = isl_basic_map_n_out(bmap1);
4361         out2 = isl_basic_map_n_out(bmap2);
4362         nparam = isl_basic_map_n_param(bmap1);
4363
4364         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
4365         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4366         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
4367         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4368         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
4369         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4370         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
4371         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
4372         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
4373         isl_dim_map_div(dim_map1, bmap1, pos += out2);
4374         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4375
4376         bmap = isl_basic_map_alloc_dim(dim_result,
4377                         bmap1->n_div + bmap2->n_div,
4378                         bmap1->n_eq + bmap2->n_eq,
4379                         bmap1->n_ineq + bmap2->n_ineq);
4380         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
4381         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
4382         bmap = isl_basic_map_simplify(bmap);
4383         return isl_basic_map_finalize(bmap);
4384 error:
4385         isl_basic_map_free(bmap1);
4386         isl_basic_map_free(bmap2);
4387         return NULL;
4388 }
4389
4390 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
4391  */
4392 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
4393 {
4394         unsigned flags = 0;
4395         struct isl_map *result;
4396         int i, j;
4397
4398         if (!map1 || !map2)
4399                 goto error;
4400
4401         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
4402                                          map2->dim, isl_dim_param), goto error);
4403
4404         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4405             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4406                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4407
4408         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
4409                                                    isl_dim_copy(map2->dim)),
4410                                 map1->n * map2->n, flags);
4411         if (!result)
4412                 goto error;
4413         for (i = 0; i < map1->n; ++i)
4414                 for (j = 0; j < map2->n; ++j) {
4415                         struct isl_basic_map *part;
4416                         part = isl_basic_map_product(
4417                                     isl_basic_map_copy(map1->p[i]),
4418                                     isl_basic_map_copy(map2->p[j]));
4419                         if (isl_basic_map_is_empty(part))
4420                                 isl_basic_map_free(part);
4421                         else
4422                                 result = isl_map_add(result, part);
4423                         if (!result)
4424                                 goto error;
4425                 }
4426         isl_map_free(map1);
4427         isl_map_free(map2);
4428         return result;
4429 error:
4430         isl_map_free(map1);
4431         isl_map_free(map2);
4432         return NULL;
4433 }
4434
4435 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
4436 {
4437         int i;
4438         uint32_t hash;
4439         unsigned total;
4440
4441         if (!bset)
4442                 return 0;
4443         bset = isl_basic_set_copy(bset);
4444         bset = isl_basic_set_normalize(bset);
4445         if (!bset)
4446                 return 0;
4447         total = isl_basic_set_total_dim(bset);
4448         isl_hash_byte(hash, bset->n_eq & 0xFF);
4449         for (i = 0; i < bset->n_eq; ++i) {
4450                 uint32_t c_hash;
4451                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
4452                 isl_hash_hash(hash, c_hash);
4453         }
4454         isl_hash_byte(hash, bset->n_ineq & 0xFF);
4455         for (i = 0; i < bset->n_ineq; ++i) {
4456                 uint32_t c_hash;
4457                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
4458                 isl_hash_hash(hash, c_hash);
4459         }
4460         isl_hash_byte(hash, bset->n_div & 0xFF);
4461         for (i = 0; i < bset->n_div; ++i) {
4462                 uint32_t c_hash;
4463                 if (isl_int_is_zero(bset->div[i][0]))
4464                         continue;
4465                 isl_hash_byte(hash, i & 0xFF);
4466                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
4467                 isl_hash_hash(hash, c_hash);
4468         }
4469         isl_basic_set_free(bset);
4470         return hash;
4471 }
4472
4473 uint32_t isl_set_get_hash(struct isl_set *set)
4474 {
4475         int i;
4476         uint32_t hash;
4477
4478         if (!set)
4479                 return 0;
4480         set = isl_set_copy(set);
4481         set = isl_set_normalize(set);
4482         if (!set)
4483                 return 0;
4484
4485         hash = isl_hash_init();
4486         for (i = 0; i < set->n; ++i) {
4487                 uint32_t bset_hash;
4488                 bset_hash = isl_basic_set_get_hash(set->p[i]);
4489                 isl_hash_hash(hash, bset_hash);
4490         }
4491
4492         isl_set_free(set);
4493
4494         return hash;
4495 }
4496
4497 /* Check if the value for dimension dim is completely determined
4498  * by the values of the other parameters and variables.
4499  * That is, check if dimension dim is involved in an equality.
4500  */
4501 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
4502 {
4503         int i;
4504         unsigned nparam;
4505
4506         if (!bset)
4507                 return -1;
4508         nparam = isl_basic_set_n_param(bset);
4509         for (i = 0; i < bset->n_eq; ++i)
4510                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
4511                         return 1;
4512         return 0;
4513 }
4514
4515 /* Check if the value for dimension dim is completely determined
4516  * by the values of the other parameters and variables.
4517  * That is, check if dimension dim is involved in an equality
4518  * for each of the subsets.
4519  */
4520 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
4521 {
4522         int i;
4523
4524         if (!set)
4525                 return -1;
4526         for (i = 0; i < set->n; ++i) {
4527                 int unique;
4528                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
4529                 if (unique != 1)
4530                         return unique;
4531         }
4532         return 1;
4533 }