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