isl_map.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  11  */
  12
  13 #include <string.h>
  14 #include <strings.h>
  15 #include "isl_ctx.h"
  16 #include "isl_blk.h"
  17 #include "isl_dim_private.h"
  18 #include "isl_equalities.h"
  19 #include "isl_list.h"
  20 #include "isl_lp.h"
  21 #include "isl_seq.h"
  22 #include "isl_set.h"
  23 #include "isl_map.h"
  24 #include "isl_map_private.h"
  25 #include "isl_map_piplib.h"
  26 #include "isl_sample.h"
  27 #include "isl_tab.h"
  28 #include "isl_vec.h"
  29
  30 /* Maps dst positions to src positions */
  31 struct isl_dim_map {
  32         unsigned len;
  33         int pos[1];
  34 };
  35
  36 static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
  37 {
  38         int i;
  39         struct isl_dim_map *dim_map;
  40         dim_map = isl_alloc(ctx, struct isl_dim_map,
  41                                 sizeof(struct isl_dim_map) + len * sizeof(int));
  42         if (!dim_map)
  43                 return NULL;
  44         dim_map->len = 1 + len;
  45         dim_map->pos[0] = 0;
  46         for (i = 0; i < len; ++i)
  47                 dim_map->pos[1 + i] = -1;
  48         return dim_map;
  49 }
  50
  51 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
  52 {
  53         switch (type) {
  54         case isl_dim_param:     return dim->nparam;
  55         case isl_dim_in:        return dim->n_in;
  56         case isl_dim_out:       return dim->n_out;
  57         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
  58         default:                return 0;
  59         }
  60 }
  61
  62 static unsigned pos(struct isl_dim *dim, enum isl_dim_type type)
  63 {
  64         switch (type) {
  65         case isl_dim_param:     return 1;
  66         case isl_dim_in:        return 1 + dim->nparam;
  67         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  68         default:                return 0;
  69         }
  70 }
  71
  72 static void isl_dim_map_dim_range(struct isl_dim_map *dim_map,
  73         struct isl_dim *dim, enum isl_dim_type type,
  74         unsigned first, unsigned n, unsigned dst_pos)
  75 {
  76         int i;
  77         unsigned src_pos;
  78
  79         if (!dim_map || !dim)
  80                 return;
  81
  82         src_pos = pos(dim, type);
  83         for (i = 0; i < n; ++i)
  84                 dim_map->pos[1 + dst_pos + i] = src_pos + first + i;
  85 }
  86
  87 static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
  88                 enum isl_dim_type type, unsigned dst_pos)
  89 {
  90         isl_dim_map_dim_range(dim_map, dim, type, 0, n(dim, type), dst_pos);
  91 }
  92
  93 static void isl_dim_map_div(struct isl_dim_map *dim_map,
  94                 struct isl_basic_map *bmap, unsigned dst_pos)
  95 {
  96         int i;
  97         unsigned src_pos;
  98
  99         if (!dim_map || !bmap)
 100                 return;
 101
 102         src_pos = 1 + isl_dim_total(bmap->dim);
 103         for (i = 0; i < bmap->n_div; ++i)
 104                 dim_map->pos[1 + dst_pos + i] = src_pos + i;
 105 }
 106
 107 static void isl_dim_map_dump(struct isl_dim_map *dim_map)
 108 {
 109         int i;
 110
 111         for (i = 0; i < dim_map->len; ++i)
 112                 fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
 113         fprintf(stderr, "\n");
 114 }
 115
 116 unsigned isl_basic_map_dim(const struct isl_basic_map *bmap,
 117                                 enum isl_dim_type type)
 118 {
 119         switch (type) {
 120         case isl_dim_param:
 121         case isl_dim_in:
 122         case isl_dim_out:       return isl_dim_size(bmap->dim, type);
 123         case isl_dim_div:       return bmap->n_div;
 124         case isl_dim_all:       return isl_basic_map_total_dim(bmap);
 125         default:                return 0;
 126         }
 127 }
 128
 129 unsigned isl_map_dim(const struct isl_map *map, enum isl_dim_type type)
 130 {
 131         return map ? n(map->dim, type) : 0;
 132 }
 133
 134 unsigned isl_set_dim(const struct isl_set *set, enum isl_dim_type type)
 135 {
 136         return set ? n(set->dim, type) : 0;
 137 }
 138
 139 unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
 140                                         enum isl_dim_type type)
 141 {
 142         struct isl_dim *dim = bmap->dim;
 143         switch (type) {
 144         case isl_dim_param:     return 1;
 145         case isl_dim_in:        return 1 + dim->nparam;
 146         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 147         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 148         default:                return 0;
 149         }
 150 }
 151
 152 static unsigned map_offset(struct isl_map *map, enum isl_dim_type type)
 153 {
 154         return pos(map->dim, type);
 155 }
 156
 157 unsigned isl_basic_set_dim(const struct isl_basic_set *bset,
 158                                 enum isl_dim_type type)
 159 {
 160         return isl_basic_map_dim((const struct isl_basic_map*)bset, type);
 161 }
 162
 163 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
 164 {
 165         return bset->dim->n_out;
 166 }
 167
 168 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
 169 {
 170         return bset->dim->nparam;
 171 }
 172
 173 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 174 {
 175         return isl_dim_total(bset->dim) + bset->n_div;
 176 }
 177
 178 unsigned isl_set_n_dim(const struct isl_set *set)
 179 {
 180         return isl_set_dim(set, isl_dim_set);
 181 }
 182
 183 unsigned isl_set_n_param(const struct isl_set *set)
 184 {
 185         return isl_set_dim(set, isl_dim_param);
 186 }
 187
 188 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
 189 {
 190         return bmap->dim->n_in;
 191 }
 192
 193 unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
 194 {
 195         return bmap->dim->n_out;
 196 }
 197
 198 unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
 199 {
 200         return bmap->dim->nparam;
 201 }
 202
 203 unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
 204 {
 205         return bmap->n_div;
 206 }
 207
 208 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
 209 {
 210         return bmap ? isl_dim_total(bmap->dim) + bmap->n_div : 0;
 211 }
 212
 213 unsigned isl_map_n_in(const struct isl_map *map)
 214 {
 215         return map->dim->n_in;
 216 }
 217
 218 unsigned isl_map_n_out(const struct isl_map *map)
 219 {
 220         return map->dim->n_out;
 221 }
 222
 223 unsigned isl_map_n_param(const struct isl_map *map)
 224 {
 225         return map->dim->nparam;
 226 }
 227
 228 int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
 229 {
 230         return map->dim->n_in == set->dim->n_out &&
 231                map->dim->nparam == set->dim->nparam;
 232 }
 233
 234 int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
 235                 struct isl_basic_set *bset)
 236 {
 237         return bmap->dim->n_in == bset->dim->n_out &&
 238                bmap->dim->nparam == bset->dim->nparam;
 239 }
 240
 241 int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
 242                 struct isl_basic_set *bset)
 243 {
 244         return bmap->dim->n_out == bset->dim->n_out &&
 245                bmap->dim->nparam == bset->dim->nparam;
 246 }
 247
 248 struct isl_dim *isl_basic_map_get_dim(struct isl_basic_map *bmap)
 249 {
 250         if (!bmap)
 251                 return NULL;
 252         return isl_dim_copy(bmap->dim);
 253 }
 254
 255 struct isl_dim *isl_basic_set_get_dim(struct isl_basic_set *bset)
 256 {
 257         if (!bset)
 258                 return NULL;
 259         return isl_dim_copy(bset->dim);
 260 }
 261
 262 struct isl_dim *isl_map_get_dim(struct isl_map *map)
 263 {
 264         if (!map)
 265                 return NULL;
 266         return isl_dim_copy(map->dim);
 267 }
 268
 269 struct isl_dim *isl_set_get_dim(struct isl_set *set)
 270 {
 271         if (!set)
 272                 return NULL;
 273         return isl_dim_copy(set->dim);
 274 }
 275
 276 __isl_give isl_basic_map *isl_basic_map_set_dim_name(
 277         __isl_take isl_basic_map *bmap,
 278         enum isl_dim_type type, unsigned pos, const char *s)
 279 {
 280         if (!bmap)
 281                 return NULL;
 282         bmap->dim = isl_dim_set_name(bmap->dim, type, pos, s);
 283         if (!bmap->dim)
 284                 goto error;
 285         return bmap;
 286 error:
 287         isl_basic_map_free(bmap);
 288         return NULL;
 289 }
 290
 291 __isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map,
 292         enum isl_dim_type type, unsigned pos, const char *s)
 293 {
 294         int i;
 295
 296         if (!map)
 297                 return NULL;
 298
 299         map->dim = isl_dim_set_name(map->dim, type, pos, s);
 300         if (!map->dim)
 301                 goto error;
 302
 303         for (i = 0; i < map->n; ++i) {
 304                 map->p[i] = isl_basic_map_set_dim_name(map->p[i], type, pos, s);
 305                 if (!map->p[i])
 306                         goto error;
 307         }
 308
 309         return map;
 310 error:
 311         isl_map_free(map);
 312         return NULL;
 313 }
 314
 315 __isl_give isl_basic_set *isl_basic_set_set_dim_name(
 316         __isl_take isl_basic_set *bset,
 317         enum isl_dim_type type, unsigned pos, const char *s)
 318 {
 319         return (isl_basic_set *)isl_basic_map_set_dim_name(
 320                 (isl_basic_map *)bset, type, pos, s);
 321 }
 322
 323 __isl_give isl_set *isl_set_set_dim_name(__isl_take isl_set *set,
 324         enum isl_dim_type type, unsigned pos, const char *s)
 325 {
 326         return (isl_set *)isl_map_set_dim_name((isl_map *)set, type, pos, s);
 327 }
 328
 329 int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
 330 {
 331         if (!bmap)
 332                 return -1;
 333         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
 334 }
 335
 336 static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 337                 struct isl_basic_map *bmap, unsigned extra,
 338                 unsigned n_eq, unsigned n_ineq)
 339 {
 340         int i;
 341         size_t row_size = 1 + isl_dim_total(bmap->dim) + extra;
 342
 343         bmap->ctx = ctx;
 344         isl_ctx_ref(ctx);
 345
 346         bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
 347         if (isl_blk_is_error(bmap->block))
 348                 goto error;
 349
 350         bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
 351         if (!bmap->ineq)
 352                 goto error;
 353
 354         if (extra == 0) {
 355                 bmap->block2 = isl_blk_empty();
 356                 bmap->div = NULL;
 357         } else {
 358                 bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
 359                 if (isl_blk_is_error(bmap->block2))
 360                         goto error;
 361
 362                 bmap->div = isl_alloc_array(ctx, isl_int *, extra);
 363                 if (!bmap->div)
 364                         goto error;
 365         }
 366
 367         for (i = 0; i < n_ineq + n_eq; ++i)
 368                 bmap->ineq[i] = bmap->block.data + i * row_size;
 369
 370         for (i = 0; i < extra; ++i)
 371                 bmap->div[i] = bmap->block2.data + i * (1 + row_size);
 372
 373         bmap->ref = 1;
 374         bmap->flags = 0;
 375         bmap->c_size = n_eq + n_ineq;
 376         bmap->eq = bmap->ineq + n_ineq;
 377         bmap->extra = extra;
 378         bmap->n_eq = 0;
 379         bmap->n_ineq = 0;
 380         bmap->n_div = 0;
 381         bmap->sample = NULL;
 382
 383         return bmap;
 384 error:
 385         isl_basic_map_free(bmap);
 386         return NULL;
 387 }
 388
 389 struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
 390                 unsigned nparam, unsigned dim, unsigned extra,
 391                 unsigned n_eq, unsigned n_ineq)
 392 {
 393         struct isl_basic_map *bmap;
 394         bmap = isl_basic_map_alloc(ctx, nparam, 0, dim, extra, n_eq, n_ineq);
 395         return (struct isl_basic_set *)bmap;
 396 }
 397
 398 struct isl_basic_set *isl_basic_set_alloc_dim(struct isl_dim *dim,
 399                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 400 {
 401         struct isl_basic_map *bmap;
 402         if (!dim)
 403                 return NULL;
 404         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
 405         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 406         return (struct isl_basic_set *)bmap;
 407 }
 408
 409 struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_dim *dim,
 410                 unsigned extra, unsigned n_eq, unsigned n_ineq)
 411 {
 412         struct isl_basic_map *bmap;
 413
 414         if (!dim)
 415                 return NULL;
 416         bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
 417         if (!bmap)
 418                 goto error;
 419         bmap->dim = dim;
 420
 421         return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
 422 error:
 423         isl_dim_free(dim);
 424         return NULL;
 425 }
 426
 427 struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
 428                 unsigned nparam, unsigned in, unsigned out, unsigned extra,
 429                 unsigned n_eq, unsigned n_ineq)
 430 {
 431         struct isl_basic_map *bmap;
 432         struct isl_dim *dim;
 433
 434         dim = isl_dim_alloc(ctx, nparam, in, out);
 435         if (!dim)
 436                 return NULL;
 437
 438         bmap = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 439         return bmap;
 440 }
 441
 442 static void dup_constraints(
 443                 struct isl_basic_map *dst, struct isl_basic_map *src)
 444 {
 445         int i;
 446         unsigned total = isl_basic_map_total_dim(src);
 447
 448         for (i = 0; i < src->n_eq; ++i) {
 449                 int j = isl_basic_map_alloc_equality(dst);
 450                 isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
 451         }
 452
 453         for (i = 0; i < src->n_ineq; ++i) {
 454                 int j = isl_basic_map_alloc_inequality(dst);
 455                 isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
 456         }
 457
 458         for (i = 0; i < src->n_div; ++i) {
 459                 int j = isl_basic_map_alloc_div(dst);
 460                 isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
 461         }
 462         ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
 463 }
 464
 465 struct isl_basic_map *isl_basic_map_dup(struct isl_basic_map *bmap)
 466 {
 467         struct isl_basic_map *dup;
 468
 469         if (!bmap)
 470                 return NULL;
 471         dup = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
 472                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
 473         if (!dup)
 474                 return NULL;
 475         dup_constraints(dup, bmap);
 476         dup->flags = bmap->flags;
 477         dup->sample = isl_vec_copy(bmap->sample);
 478         return dup;
 479 }
 480
 481 struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
 482 {
 483         struct isl_basic_map *dup;
 484
 485         dup = isl_basic_map_dup((struct isl_basic_map *)bset);
 486         return (struct isl_basic_set *)dup;
 487 }
 488
 489 struct isl_basic_set *isl_basic_set_copy(struct isl_basic_set *bset)
 490 {
 491         if (!bset)
 492                 return NULL;
 493
 494         if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
 495                 bset->ref++;
 496                 return bset;
 497         }
 498         return isl_basic_set_dup(bset);
 499 }
 500
 501 struct isl_set *isl_set_copy(struct isl_set *set)
 502 {
 503         if (!set)
 504                 return NULL;
 505
 506         set->ref++;
 507         return set;
 508 }
 509
 510 struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
 511 {
 512         if (!bmap)
 513                 return NULL;
 514
 515         if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
 516                 bmap->ref++;
 517                 return bmap;
 518         }
 519         bmap = isl_basic_map_dup(bmap);
 520         if (bmap)
 521                 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
 522         return bmap;
 523 }
 524
 525 struct isl_map *isl_map_copy(struct isl_map *map)
 526 {
 527         if (!map)
 528                 return NULL;
 529
 530         map->ref++;
 531         return map;
 532 }
 533
 534 void isl_basic_map_free(struct isl_basic_map *bmap)
 535 {
 536         if (!bmap)
 537                 return;
 538
 539         if (--bmap->ref > 0)
 540                 return;
 541
 542         isl_ctx_deref(bmap->ctx);
 543         free(bmap->div);
 544         isl_blk_free(bmap->ctx, bmap->block2);
 545         free(bmap->ineq);
 546         isl_blk_free(bmap->ctx, bmap->block);
 547         isl_vec_free(bmap->sample);
 548         isl_dim_free(bmap->dim);
 549         free(bmap);
 550 }
 551
 552 void isl_basic_set_free(struct isl_basic_set *bset)
 553 {
 554         isl_basic_map_free((struct isl_basic_map *)bset);
 555 }
 556
 557 static int room_for_con(struct isl_basic_map *bmap, unsigned n)
 558 {
 559         return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
 560 }
 561
 562 int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
 563 {
 564         struct isl_ctx *ctx;
 565         if (!bmap)
 566                 return -1;
 567         ctx = bmap->ctx;
 568         isl_assert(ctx, room_for_con(bmap, 1), return -1);
 569         isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
 570                         return -1);
 571         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 572         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 573         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
 574         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 575         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 576         if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
 577                 isl_int *t;
 578                 int j = isl_basic_map_alloc_inequality(bmap);
 579                 if (j < 0)
 580                         return -1;
 581                 t = bmap->ineq[j];
 582                 bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
 583                 bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
 584                 bmap->eq[-1] = t;
 585                 bmap->n_eq++;
 586                 bmap->n_ineq--;
 587                 bmap->eq--;
 588                 return 0;
 589         }
 590         isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
 591                       bmap->extra - bmap->n_div);
 592         return bmap->n_eq++;
 593 }
 594
 595 int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
 596 {
 597         return isl_basic_map_alloc_equality((struct isl_basic_map *)bset);
 598 }
 599
 600 int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
 601 {
 602         if (!bmap)
 603                 return -1;
 604         isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
 605         bmap->n_eq -= n;
 606         return 0;
 607 }
 608
 609 int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
 610 {
 611         return isl_basic_map_free_equality((struct isl_basic_map *)bset, n);
 612 }
 613
 614 int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
 615 {
 616         isl_int *t;
 617         if (!bmap)
 618                 return -1;
 619         isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
 620
 621         if (pos != bmap->n_eq - 1) {
 622                 t = bmap->eq[pos];
 623                 bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
 624                 bmap->eq[bmap->n_eq - 1] = t;
 625         }
 626         bmap->n_eq--;
 627         return 0;
 628 }
 629
 630 int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos)
 631 {
 632         return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos);
 633 }
 634
 635 void isl_basic_map_inequality_to_equality(
 636                 struct isl_basic_map *bmap, unsigned pos)
 637 {
 638         isl_int *t;
 639
 640         t = bmap->ineq[pos];
 641         bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 642         bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
 643         bmap->eq[-1] = t;
 644         bmap->n_eq++;
 645         bmap->n_ineq--;
 646         bmap->eq--;
 647         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 648         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 649         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 650         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 651 }
 652
 653 static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
 654 {
 655         return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
 656 }
 657
 658 int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap)
 659 {
 660         struct isl_ctx *ctx;
 661         if (!bmap)
 662                 return -1;
 663         ctx = bmap->ctx;
 664         isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
 665         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
 666         ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
 667         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 668         ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
 669         isl_seq_clr(bmap->ineq[bmap->n_ineq] +
 670                       1 + isl_basic_map_total_dim(bmap),
 671                       bmap->extra - bmap->n_div);
 672         return bmap->n_ineq++;
 673 }
 674
 675 int isl_basic_set_alloc_inequality(struct isl_basic_set *bset)
 676 {
 677         return isl_basic_map_alloc_inequality((struct isl_basic_map *)bset);
 678 }
 679
 680 int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
 681 {
 682         if (!bmap)
 683                 return -1;
 684         isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
 685         bmap->n_ineq -= n;
 686         return 0;
 687 }
 688
 689 int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
 690 {
 691         return isl_basic_map_free_inequality((struct isl_basic_map *)bset, n);
 692 }
 693
 694 int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
 695 {
 696         isl_int *t;
 697         if (!bmap)
 698                 return -1;
 699         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
 700
 701         if (pos != bmap->n_ineq - 1) {
 702                 t = bmap->ineq[pos];
 703                 bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
 704                 bmap->ineq[bmap->n_ineq - 1] = t;
 705                 ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
 706         }
 707         bmap->n_ineq--;
 708         return 0;
 709 }
 710
 711 int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
 712 {
 713         return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos);
 714 }
 715
 716 __isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
 717         isl_int *eq)
 718 {
 719         int k;
 720
 721         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
 722         if (!bmap)
 723                 return NULL;
 724         k = isl_basic_map_alloc_equality(bmap);
 725         if (k < 0)
 726                 goto error;
 727         isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
 728         return bmap;
 729 error:
 730         isl_basic_map_free(bmap);
 731         return NULL;
 732 }
 733
 734 __isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
 735         isl_int *eq)
 736 {
 737         return (isl_basic_set *)
 738                 isl_basic_map_add_eq((isl_basic_map *)bset, eq);
 739 }
 740
 741 __isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
 742         isl_int *ineq)
 743 {
 744         int k;
 745
 746         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
 747         if (!bmap)
 748                 return NULL;
 749         k = isl_basic_map_alloc_inequality(bmap);
 750         if (k < 0)
 751                 goto error;
 752         isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
 753         return bmap;
 754 error:
 755         isl_basic_map_free(bmap);
 756         return NULL;
 757 }
 758
 759 __isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
 760         isl_int *ineq)
 761 {
 762         return (isl_basic_set *)
 763                 isl_basic_map_add_ineq((isl_basic_map *)bset, ineq);
 764 }
 765
 766 int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
 767 {
 768         if (!bmap)
 769                 return -1;
 770         isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
 771         isl_seq_clr(bmap->div[bmap->n_div] +
 772                       1 + 1 + isl_basic_map_total_dim(bmap),
 773                       bmap->extra - bmap->n_div);
 774         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
 775         return bmap->n_div++;
 776 }
 777
 778 int isl_basic_set_alloc_div(struct isl_basic_set *bset)
 779 {
 780         return isl_basic_map_alloc_div((struct isl_basic_map *)bset);
 781 }
 782
 783 int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
 784 {
 785         if (!bmap)
 786                 return -1;
 787         isl_assert(bmap->ctx, n <= bmap->n_div, return -1);
 788         bmap->n_div -= n;
 789         return 0;
 790 }
 791
 792 int isl_basic_set_free_div(struct isl_basic_set *bset, unsigned n)
 793 {
 794         return isl_basic_map_free_div((struct isl_basic_map *)bset, n);
 795 }
 796
 797 /* Copy constraint from src to dst, putting the vars of src at offset
 798  * dim_off in dst and the divs of src at offset div_off in dst.
 799  * If both sets are actually map, then dim_off applies to the input
 800  * variables.
 801  */
 802 static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
 803                             struct isl_basic_map *src_map, isl_int *src,
 804                             unsigned in_off, unsigned out_off, unsigned div_off)
 805 {
 806         unsigned src_nparam = isl_basic_map_n_param(src_map);
 807         unsigned dst_nparam = isl_basic_map_n_param(dst_map);
 808         unsigned src_in = isl_basic_map_n_in(src_map);
 809         unsigned dst_in = isl_basic_map_n_in(dst_map);
 810         unsigned src_out = isl_basic_map_n_out(src_map);
 811         unsigned dst_out = isl_basic_map_n_out(dst_map);
 812         isl_int_set(dst[0], src[0]);
 813         isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
 814         if (dst_nparam > src_nparam)
 815                 isl_seq_clr(dst+1+src_nparam,
 816                                 dst_nparam - src_nparam);
 817         isl_seq_clr(dst+1+dst_nparam, in_off);
 818         isl_seq_cpy(dst+1+dst_nparam+in_off,
 819                     src+1+src_nparam,
 820                     isl_min(dst_in-in_off, src_in));
 821         if (dst_in-in_off > src_in)
 822                 isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
 823                                 dst_in - in_off - src_in);
 824         isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
 825         isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
 826                     src+1+src_nparam+src_in,
 827                     isl_min(dst_out-out_off, src_out));
 828         if (dst_out-out_off > src_out)
 829                 isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
 830                                 dst_out - out_off - src_out);
 831         isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
 832         isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
 833                     src+1+src_nparam+src_in+src_out,
 834                     isl_min(dst_map->extra-div_off, src_map->n_div));
 835         if (dst_map->n_div-div_off > src_map->n_div)
 836                 isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
 837                                 div_off+src_map->n_div,
 838                                 dst_map->n_div - div_off - src_map->n_div);
 839 }
 840
 841 static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
 842                      struct isl_basic_map *src_map, isl_int *src,
 843                      unsigned in_off, unsigned out_off, unsigned div_off)
 844 {
 845         isl_int_set(dst[0], src[0]);
 846         copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
 847 }
 848
 849 static struct isl_basic_map *add_constraints(struct isl_basic_map *bmap1,
 850                 struct isl_basic_map *bmap2, unsigned i_pos, unsigned o_pos)
 851 {
 852         int i;
 853         unsigned div_off;
 854
 855         if (!bmap1 || !bmap2)
 856                 goto error;
 857
 858         div_off = bmap1->n_div;
 859
 860         for (i = 0; i < bmap2->n_eq; ++i) {
 861                 int i1 = isl_basic_map_alloc_equality(bmap1);
 862                 if (i1 < 0)
 863                         goto error;
 864                 copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
 865                                 i_pos, o_pos, div_off);
 866         }
 867
 868         for (i = 0; i < bmap2->n_ineq; ++i) {
 869                 int i1 = isl_basic_map_alloc_inequality(bmap1);
 870                 if (i1 < 0)
 871                         goto error;
 872                 copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
 873                                 i_pos, o_pos, div_off);
 874         }
 875
 876         for (i = 0; i < bmap2->n_div; ++i) {
 877                 int i1 = isl_basic_map_alloc_div(bmap1);
 878                 if (i1 < 0)
 879                         goto error;
 880                 copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
 881                          i_pos, o_pos, div_off);
 882         }
 883
 884         isl_basic_map_free(bmap2);
 885
 886         return bmap1;
 887
 888 error:
 889         isl_basic_map_free(bmap1);
 890         isl_basic_map_free(bmap2);
 891         return NULL;
 892 }
 893
 894 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
 895                                         struct isl_dim_map *dim_map)
 896 {
 897         int i;
 898
 899         for (i = 0; i < dim_map->len; ++i) {
 900                 if (dim_map->pos[i] < 0)
 901                         isl_int_set_si(dst[i], 0);
 902                 else
 903                         isl_int_set(dst[i], src[dim_map->pos[i]]);
 904         }
 905 }
 906
 907 static void copy_div_dim_map(isl_int *dst, isl_int *src,
 908                                         struct isl_dim_map *dim_map)
 909 {
 910         isl_int_set(dst[0], src[0]);
 911         copy_constraint_dim_map(dst+1, src+1, dim_map);
 912 }
 913
 914 static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst,
 915                 struct isl_basic_map *src, struct isl_dim_map *dim_map)
 916 {
 917         int i;
 918
 919         if (!src || !dst || !dim_map)
 920                 goto error;
 921
 922         for (i = 0; i < src->n_eq; ++i) {
 923                 int i1 = isl_basic_map_alloc_equality(dst);
 924                 if (i1 < 0)
 925                         goto error;
 926                 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
 927         }
 928
 929         for (i = 0; i < src->n_ineq; ++i) {
 930                 int i1 = isl_basic_map_alloc_inequality(dst);
 931                 if (i1 < 0)
 932                         goto error;
 933                 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
 934         }
 935
 936         for (i = 0; i < src->n_div; ++i) {
 937                 int i1 = isl_basic_map_alloc_div(dst);
 938                 if (i1 < 0)
 939                         goto error;
 940                 copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
 941         }
 942
 943         free(dim_map);
 944         isl_basic_map_free(src);
 945
 946         return dst;
 947 error:
 948         free(dim_map);
 949         isl_basic_map_free(src);
 950         isl_basic_map_free(dst);
 951         return NULL;
 952 }
 953
 954 struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
 955                 struct isl_basic_set *bset2, unsigned pos)
 956 {
 957         return (struct isl_basic_set *)
 958                 add_constraints((struct isl_basic_map *)bset1,
 959                                 (struct isl_basic_map *)bset2, 0, pos);
 960 }
 961
 962 struct isl_basic_map *isl_basic_map_extend_dim(struct isl_basic_map *base,
 963                 struct isl_dim *dim, unsigned extra,
 964                 unsigned n_eq, unsigned n_ineq)
 965 {
 966         struct isl_basic_map *ext;
 967         unsigned flags;
 968         int dims_ok;
 969
 970         if (!dim)
 971                 goto error;
 972
 973         if (!base)
 974                 goto error;
 975
 976         dims_ok = isl_dim_equal(base->dim, dim) &&
 977                   base->extra >= base->n_div + extra;
 978
 979         if (dims_ok && room_for_con(base, n_eq + n_ineq) &&
 980                        room_for_ineq(base, n_ineq)) {
 981                 isl_dim_free(dim);
 982                 return base;
 983         }
 984
 985         isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
 986         isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
 987         isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
 988         extra += base->extra;
 989         n_eq += base->n_eq;
 990         n_ineq += base->n_ineq;
 991
 992         ext = isl_basic_map_alloc_dim(dim, extra, n_eq, n_ineq);
 993         dim = NULL;
 994         if (!ext)
 995                 goto error;
 996
 997         if (dims_ok)
 998                 ext->sample = isl_vec_copy(base->sample);
 999         flags = base->flags;
1000         ext = add_constraints(ext, base, 0, 0);
1001         if (ext) {
1002                 ext->flags = flags;
1003                 ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
1004         }
1005
1006         return ext;
1007
1008 error:
1009         isl_dim_free(dim);
1010         isl_basic_map_free(base);
1011         return NULL;
1012 }
1013
1014 struct isl_basic_set *isl_basic_set_extend_dim(struct isl_basic_set *base,
1015                 struct isl_dim *dim, unsigned extra,
1016                 unsigned n_eq, unsigned n_ineq)
1017 {
1018         return (struct isl_basic_set *)
1019                 isl_basic_map_extend_dim((struct isl_basic_map *)base, dim,
1020                                                         extra, n_eq, n_ineq);
1021 }
1022
1023 struct isl_basic_map *isl_basic_map_extend_constraints(
1024                 struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
1025 {
1026         if (!base)
1027                 return NULL;
1028         return isl_basic_map_extend_dim(base, isl_dim_copy(base->dim),
1029                                         0, n_eq, n_ineq);
1030 }
1031
1032 struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
1033                 unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
1034                 unsigned n_eq, unsigned n_ineq)
1035 {
1036         struct isl_basic_map *bmap;
1037         struct isl_dim *dim;
1038
1039         if (!base)
1040                 return NULL;
1041         dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out);
1042         if (!dim)
1043                 goto error;
1044
1045         bmap = isl_basic_map_extend_dim(base, dim, extra, n_eq, n_ineq);
1046         return bmap;
1047 error:
1048         isl_basic_map_free(base);
1049         return NULL;
1050 }
1051
1052 struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
1053                 unsigned nparam, unsigned dim, unsigned extra,
1054                 unsigned n_eq, unsigned n_ineq)
1055 {
1056         return (struct isl_basic_set *)
1057                 isl_basic_map_extend((struct isl_basic_map *)base,
1058                                         nparam, 0, dim, extra, n_eq, n_ineq);
1059 }
1060
1061 struct isl_basic_set *isl_basic_set_extend_constraints(
1062                 struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
1063 {
1064         return (struct isl_basic_set *)
1065                 isl_basic_map_extend_constraints((struct isl_basic_map *)base,
1066                                                     n_eq, n_ineq);
1067 }
1068
1069 struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset)
1070 {
1071         return (struct isl_basic_set *)
1072                 isl_basic_map_cow((struct isl_basic_map *)bset);
1073 }
1074
1075 struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
1076 {
1077         if (!bmap)
1078                 return NULL;
1079
1080         if (bmap->ref > 1) {
1081                 bmap->ref--;
1082                 bmap = isl_basic_map_dup(bmap);
1083         }
1084         if (bmap)
1085                 ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
1086         return bmap;
1087 }
1088
1089 struct isl_set *isl_set_cow(struct isl_set *set)
1090 {
1091         if (!set)
1092                 return NULL;
1093
1094         if (set->ref == 1)
1095                 return set;
1096         set->ref--;
1097         return isl_set_dup(set);
1098 }
1099
1100 struct isl_map *isl_map_cow(struct isl_map *map)
1101 {
1102         if (!map)
1103                 return NULL;
1104
1105         if (map->ref == 1)
1106                 return map;
1107         map->ref--;
1108         return isl_map_dup(map);
1109 }
1110
1111 static void swap_vars(struct isl_blk blk, isl_int *a,
1112                         unsigned a_len, unsigned b_len)
1113 {
1114         isl_seq_cpy(blk.data, a+a_len, b_len);
1115         isl_seq_cpy(blk.data+b_len, a, a_len);
1116         isl_seq_cpy(a, blk.data, b_len+a_len);
1117 }
1118
1119 struct isl_basic_set *isl_basic_set_swap_vars(
1120                 struct isl_basic_set *bset, unsigned n)
1121 {
1122         int i;
1123         struct isl_blk blk;
1124         unsigned dim;
1125         unsigned nparam;
1126
1127         if (!bset)
1128                 goto error;
1129
1130         nparam = isl_basic_set_n_param(bset);
1131         dim = isl_basic_set_n_dim(bset);
1132         isl_assert(bset->ctx, n <= dim, goto error);
1133
1134         if (n == dim)
1135                 return bset;
1136
1137         bset = isl_basic_set_cow(bset);
1138         if (!bset)
1139                 return NULL;
1140
1141         blk = isl_blk_alloc(bset->ctx, dim);
1142         if (isl_blk_is_error(blk))
1143                 goto error;
1144
1145         for (i = 0; i < bset->n_eq; ++i)
1146                 swap_vars(blk,
1147                           bset->eq[i]+1+nparam, n, dim - n);
1148
1149         for (i = 0; i < bset->n_ineq; ++i)
1150                 swap_vars(blk,
1151                           bset->ineq[i]+1+nparam, n, dim - n);
1152
1153         for (i = 0; i < bset->n_div; ++i)
1154                 swap_vars(blk,
1155                           bset->div[i]+1+1+nparam, n, dim - n);
1156
1157         isl_blk_free(bset->ctx, blk);
1158
1159         ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
1160         return isl_basic_set_gauss(bset, NULL);
1161 error:
1162         isl_basic_set_free(bset);
1163         return NULL;
1164 }
1165
1166 struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n)
1167 {
1168         int i;
1169         set = isl_set_cow(set);
1170         if (!set)
1171                 return NULL;
1172
1173         for (i = 0; i < set->n; ++i) {
1174                 set->p[i] = isl_basic_set_swap_vars(set->p[i], n);
1175                 if (!set->p[i]) {
1176                         isl_set_free(set);
1177                         return NULL;
1178                 }
1179         }
1180         ISL_F_CLR(set, ISL_SET_NORMALIZED);
1181         return set;
1182 }
1183
1184 struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
1185 {
1186         int i = 0;
1187         unsigned total;
1188         if (!bmap)
1189                 goto error;
1190         total = isl_basic_map_total_dim(bmap);
1191         isl_basic_map_free_div(bmap, bmap->n_div);
1192         isl_basic_map_free_inequality(bmap, bmap->n_ineq);
1193         if (bmap->n_eq > 0)
1194                 isl_basic_map_free_equality(bmap, bmap->n_eq-1);
1195         else {
1196                 i = isl_basic_map_alloc_equality(bmap);
1197                 if (i < 0)
1198                         goto error;
1199         }
1200         isl_int_set_si(bmap->eq[i][0], 1);
1201         isl_seq_clr(bmap->eq[i]+1, total);
1202         ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
1203         isl_vec_free(bmap->sample);
1204         bmap->sample = NULL;
1205         return isl_basic_map_finalize(bmap);
1206 error:
1207         isl_basic_map_free(bmap);
1208         return NULL;
1209 }
1210
1211 struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset)
1212 {
1213         return (struct isl_basic_set *)
1214                 isl_basic_map_set_to_empty((struct isl_basic_map *)bset);
1215 }
1216
1217 void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
1218 {
1219         int i;
1220         unsigned off = isl_dim_total(bmap->dim);
1221         isl_int *t = bmap->div[a];
1222         bmap->div[a] = bmap->div[b];
1223         bmap->div[b] = t;
1224
1225         for (i = 0; i < bmap->n_eq; ++i)
1226                 isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
1227
1228         for (i = 0; i < bmap->n_ineq; ++i)
1229                 isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
1230
1231         for (i = 0; i < bmap->n_div; ++i)
1232                 isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
1233         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1234 }
1235
1236 /* Eliminate the specified n dimensions starting at first from the
1237  * constraints using Fourier-Motzkin.  The dimensions themselves
1238  * are not removed.
1239  */
1240 __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
1241         enum isl_dim_type type, unsigned first, unsigned n)
1242 {
1243         int i;
1244
1245         if (!map)
1246                 return NULL;
1247         if (n == 0)
1248                 return map;
1249
1250         map = isl_map_cow(map);
1251         if (!map)
1252                 return NULL;
1253         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
1254         first += pos(map->dim, type) - 1;
1255
1256         for (i = 0; i < map->n; ++i) {
1257                 map->p[i] = isl_basic_map_eliminate_vars(map->p[i], first, n);
1258                 if (!map->p[i])
1259                         goto error;
1260         }
1261         return map;
1262 error:
1263         isl_map_free(map);
1264         return NULL;
1265 }
1266
1267 /* Eliminate the specified n dimensions starting at first from the
1268  * constraints using Fourier-Motzkin.  The dimensions themselves
1269  * are not removed.
1270  */
1271 __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
1272         enum isl_dim_type type, unsigned first, unsigned n)
1273 {
1274         return (isl_set *)isl_map_eliminate((isl_map *)set, type, first, n);
1275 }
1276
1277 /* Eliminate the specified n dimensions starting at first from the
1278  * constraints using Fourier-Motzkin.  The dimensions themselves
1279  * are not removed.
1280  */
1281 __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
1282         unsigned first, unsigned n)
1283 {
1284         return isl_set_eliminate(set, isl_dim_set, first, n);
1285 }
1286
1287 /* Project out n dimensions starting at first using Fourier-Motzkin */
1288 struct isl_set *isl_set_remove_dims(struct isl_set *set,
1289         unsigned first, unsigned n)
1290 {
1291         set = isl_set_eliminate_dims(set, first, n);
1292         set = isl_set_drop_dims(set, first, n);
1293         return set;
1294 }
1295
1296 struct isl_basic_set *isl_basic_set_remove_divs(struct isl_basic_set *bset)
1297 {
1298         bset = isl_basic_set_eliminate_vars(bset, isl_dim_total(bset->dim),
1299                                                 bset->n_div);
1300         if (!bset)
1301                 return NULL;
1302         bset->n_div = 0;
1303         return bset;
1304 }
1305
1306 struct isl_set *isl_set_remove_divs(struct isl_set *set)
1307 {
1308         int i;
1309
1310         if (!set)
1311                 return NULL;
1312         if (set->n == 0)
1313                 return set;
1314
1315         set = isl_set_cow(set);
1316         if (!set)
1317                 return NULL;
1318
1319         for (i = 0; i < set->n; ++i) {
1320                 set->p[i] = isl_basic_set_remove_divs(set->p[i]);
1321                 if (!set->p[i])
1322                         goto error;
1323         }
1324         return set;
1325 error:
1326         isl_set_free(set);
1327         return NULL;
1328 }
1329
1330 struct isl_basic_map *isl_basic_map_remove(struct isl_basic_map *bmap,
1331         enum isl_dim_type type, unsigned first, unsigned n)
1332 {
1333         if (!bmap)
1334                 return NULL;
1335         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
1336                         goto error);
1337         if (n == 0)
1338                 return bmap;
1339         bmap = isl_basic_map_eliminate_vars(bmap,
1340                         isl_basic_map_offset(bmap, type) - 1 + first, n);
1341         if (!bmap)
1342                 return bmap;
1343         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && type == isl_dim_div)
1344                 return bmap;
1345         bmap = isl_basic_map_drop(bmap, type, first, n);
1346         return bmap;
1347 error:
1348         isl_basic_map_free(bmap);
1349         return NULL;
1350 }
1351
1352 __isl_give isl_basic_set *isl_basic_set_remove(__isl_take isl_basic_set *bset,
1353         enum isl_dim_type type, unsigned first, unsigned n)
1354 {
1355         return (isl_basic_set *)
1356                 isl_basic_map_remove((isl_basic_map *)bset, type, first, n);
1357 }
1358
1359 struct isl_map *isl_map_remove(struct isl_map *map,
1360         enum isl_dim_type type, unsigned first, unsigned n)
1361 {
1362         int i;
1363
1364         if (n == 0)
1365                 return map;
1366
1367         map = isl_map_cow(map);
1368         if (!map)
1369                 return NULL;
1370         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
1371
1372         for (i = 0; i < map->n; ++i) {
1373                 map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
1374                         isl_basic_map_offset(map->p[i], type) - 1 + first, n);
1375                 if (!map->p[i])
1376                         goto error;
1377         }
1378         map = isl_map_drop(map, type, first, n);
1379         return map;
1380 error:
1381         isl_map_free(map);
1382         return NULL;
1383 }
1384
1385 __isl_give isl_set *isl_set_remove(__isl_take isl_set *bset,
1386         enum isl_dim_type type, unsigned first, unsigned n)
1387 {
1388         return (isl_set *)isl_map_remove((isl_map *)bset, type, first, n);
1389 }
1390
1391 /* Project out n inputs starting at first using Fourier-Motzkin */
1392 struct isl_map *isl_map_remove_inputs(struct isl_map *map,
1393         unsigned first, unsigned n)
1394 {
1395         return isl_map_remove(map, isl_dim_in, first, n);
1396 }
1397
1398 /* Project out n dimensions starting at first using Fourier-Motzkin */
1399 struct isl_basic_set *isl_basic_set_remove_dims(struct isl_basic_set *bset,
1400         unsigned first, unsigned n)
1401 {
1402         unsigned nparam = isl_basic_set_n_param(bset);
1403         bset = isl_basic_set_eliminate_vars(bset, nparam + first, n);
1404         bset = isl_basic_set_drop_dims(bset, first, n);
1405         return bset;
1406 }
1407
1408 static void dump_term(struct isl_basic_map *bmap,
1409                         isl_int c, int pos, FILE *out)
1410 {
1411         const char *name;
1412         unsigned in = isl_basic_map_n_in(bmap);
1413         unsigned dim = in + isl_basic_map_n_out(bmap);
1414         unsigned nparam = isl_basic_map_n_param(bmap);
1415         if (!pos)
1416                 isl_int_print(out, c, 0);
1417         else {
1418                 if (!isl_int_is_one(c))
1419                         isl_int_print(out, c, 0);
1420                 if (pos < 1 + nparam) {
1421                         name = isl_dim_get_name(bmap->dim,
1422                                                 isl_dim_param, pos - 1);
1423                         if (name)
1424                                 fprintf(out, "%s", name);
1425                         else
1426                                 fprintf(out, "p%d", pos - 1);
1427                 } else if (pos < 1 + nparam + in)
1428                         fprintf(out, "i%d", pos - 1 - nparam);
1429                 else if (pos < 1 + nparam + dim)
1430                         fprintf(out, "o%d", pos - 1 - nparam - in);
1431                 else
1432                         fprintf(out, "e%d", pos - 1 - nparam - dim);
1433         }
1434 }
1435
1436 static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
1437                                 int sign, FILE *out)
1438 {
1439         int i;
1440         int first;
1441         unsigned len = 1 + isl_basic_map_total_dim(bmap);
1442         isl_int v;
1443
1444         isl_int_init(v);
1445         for (i = 0, first = 1; i < len; ++i) {
1446                 if (isl_int_sgn(c[i]) * sign <= 0)
1447                         continue;
1448                 if (!first)
1449                         fprintf(out, " + ");
1450                 first = 0;
1451                 isl_int_abs(v, c[i]);
1452                 dump_term(bmap, v, i, out);
1453         }
1454         isl_int_clear(v);
1455         if (first)
1456                 fprintf(out, "0");
1457 }
1458
1459 static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
1460                                 const char *op, FILE *out, int indent)
1461 {
1462         int i;
1463
1464         fprintf(out, "%*s", indent, "");
1465
1466         dump_constraint_sign(bmap, c, 1, out);
1467         fprintf(out, " %s ", op);
1468         dump_constraint_sign(bmap, c, -1, out);
1469
1470         fprintf(out, "\n");
1471
1472         for (i = bmap->n_div; i < bmap->extra; ++i) {
1473                 if (isl_int_is_zero(c[1+isl_dim_total(bmap->dim)+i]))
1474                         continue;
1475                 fprintf(out, "%*s", indent, "");
1476                 fprintf(out, "ERROR: unused div coefficient not zero\n");
1477                 abort();
1478         }
1479 }
1480
1481 static void dump_constraints(struct isl_basic_map *bmap,
1482                                 isl_int **c, unsigned n,
1483                                 const char *op, FILE *out, int indent)
1484 {
1485         int i;
1486
1487         for (i = 0; i < n; ++i)
1488                 dump_constraint(bmap, c[i], op, out, indent);
1489 }
1490
1491 static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
1492 {
1493         int j;
1494         int first = 1;
1495         unsigned total = isl_basic_map_total_dim(bmap);
1496
1497         for (j = 0; j < 1 + total; ++j) {
1498                 if (isl_int_is_zero(exp[j]))
1499                         continue;
1500                 if (!first && isl_int_is_pos(exp[j]))
1501                         fprintf(out, "+");
1502                 dump_term(bmap, exp[j], j, out);
1503                 first = 0;
1504         }
1505 }
1506
1507 static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
1508 {
1509         int i;
1510
1511         dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
1512         dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
1513
1514         for (i = 0; i < bmap->n_div; ++i) {
1515                 fprintf(out, "%*s", indent, "");
1516                 fprintf(out, "e%d = [(", i);
1517                 dump_affine(bmap, bmap->div[i]+1, out);
1518                 fprintf(out, ")/");
1519                 isl_int_print(out, bmap->div[i][0], 0);
1520                 fprintf(out, "]\n");
1521         }
1522 }
1523
1524 void isl_basic_set_dump(struct isl_basic_set *bset, FILE *out, int indent)
1525 {
1526         if (!bset) {
1527                 fprintf(out, "null basic set\n");
1528                 return;
1529         }
1530
1531         fprintf(out, "%*s", indent, "");
1532         fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
1533                         bset->ref, bset->dim->nparam, bset->dim->n_out,
1534                         bset->extra, bset->flags);
1535         dump((struct isl_basic_map *)bset, out, indent);
1536 }
1537
1538 void isl_basic_map_dump(struct isl_basic_map *bmap, FILE *out, int indent)
1539 {
1540         if (!bmap) {
1541                 fprintf(out, "null basic map\n");
1542                 return;
1543         }
1544
1545         fprintf(out, "%*s", indent, "");
1546         fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
1547                         "flags: %x, n_name: %d\n",
1548                 bmap->ref,
1549                 bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
1550                 bmap->extra, bmap->flags, bmap->dim->n_name);
1551         dump(bmap, out, indent);
1552 }
1553
1554 int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
1555 {
1556         unsigned total;
1557         if (!bmap)
1558                 return -1;
1559         total = isl_basic_map_total_dim(bmap);
1560         isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
1561         isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
1562         isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
1563         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1564         return 0;
1565 }
1566
1567 struct isl_set *isl_set_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
1568 {
1569         struct isl_set *set;
1570
1571         if (!dim)
1572                 return NULL;
1573         isl_assert(dim->ctx, dim->n_in == 0, return NULL);
1574         isl_assert(dim->ctx, n >= 0, return NULL);
1575         set = isl_alloc(dim->ctx, struct isl_set,
1576                         sizeof(struct isl_set) +
1577                         (n - 1) * sizeof(struct isl_basic_set *));
1578         if (!set)
1579                 goto error;
1580
1581         set->ctx = dim->ctx;
1582         isl_ctx_ref(set->ctx);
1583         set->ref = 1;
1584         set->size = n;
1585         set->n = 0;
1586         set->dim = dim;
1587         set->flags = flags;
1588         return set;
1589 error:
1590         isl_dim_free(dim);
1591         return NULL;
1592 }
1593
1594 struct isl_set *isl_set_alloc(struct isl_ctx *ctx,
1595                 unsigned nparam, unsigned dim, int n, unsigned flags)
1596 {
1597         struct isl_set *set;
1598         struct isl_dim *dims;
1599
1600         dims = isl_dim_alloc(ctx, nparam, 0, dim);
1601         if (!dims)
1602                 return NULL;
1603
1604         set = isl_set_alloc_dim(dims, n, flags);
1605         return set;
1606 }
1607
1608 /* Make sure "map" has room for at least "n" more basic maps.
1609  */
1610 struct isl_map *isl_map_grow(struct isl_map *map, int n)
1611 {
1612         int i;
1613         struct isl_map *grown = NULL;
1614
1615         if (!map)
1616                 return NULL;
1617         isl_assert(map->ctx, n >= 0, goto error);
1618         if (map->n + n <= map->size)
1619                 return map;
1620         grown = isl_map_alloc_dim(isl_map_get_dim(map), map->n + n, map->flags);
1621         if (!grown)
1622                 goto error;
1623         for (i = 0; i < map->n; ++i) {
1624                 grown->p[i] = isl_basic_map_copy(map->p[i]);
1625                 if (!grown->p[i])
1626                         goto error;
1627                 grown->n++;
1628         }
1629         isl_map_free(map);
1630         return grown;
1631 error:
1632         isl_map_free(grown);
1633         isl_map_free(map);
1634         return NULL;
1635 }
1636
1637 /* Make sure "set" has room for at least "n" more basic sets.
1638  */
1639 struct isl_set *isl_set_grow(struct isl_set *set, int n)
1640 {
1641         return (struct isl_set *)isl_map_grow((struct isl_map *)set, n);
1642 }
1643
1644 struct isl_set *isl_set_dup(struct isl_set *set)
1645 {
1646         int i;
1647         struct isl_set *dup;
1648
1649         if (!set)
1650                 return NULL;
1651
1652         dup = isl_set_alloc_dim(isl_dim_copy(set->dim), set->n, set->flags);
1653         if (!dup)
1654                 return NULL;
1655         for (i = 0; i < set->n; ++i)
1656                 dup = isl_set_add_basic_set(dup, isl_basic_set_copy(set->p[i]));
1657         return dup;
1658 }
1659
1660 struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset)
1661 {
1662         struct isl_set *set;
1663
1664         if (!bset)
1665                 return NULL;
1666
1667         set = isl_set_alloc_dim(isl_dim_copy(bset->dim), 1, ISL_MAP_DISJOINT);
1668         if (!set) {
1669                 isl_basic_set_free(bset);
1670                 return NULL;
1671         }
1672         return isl_set_add_basic_set(set, bset);
1673 }
1674
1675 struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap)
1676 {
1677         struct isl_map *map;
1678
1679         if (!bmap)
1680                 return NULL;
1681
1682         map = isl_map_alloc_dim(isl_dim_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
1683         if (!map) {
1684                 isl_basic_map_free(bmap);
1685                 return NULL;
1686         }
1687         return isl_map_add_basic_map(map, bmap);
1688 }
1689
1690 __isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
1691                                                 __isl_take isl_basic_set *bset)
1692 {
1693         return (struct isl_set *)isl_map_add_basic_map((struct isl_map *)set,
1694                                                 (struct isl_basic_map *)bset);
1695 }
1696
1697 void isl_set_free(struct isl_set *set)
1698 {
1699         int i;
1700
1701         if (!set)
1702                 return;
1703
1704         if (--set->ref > 0)
1705                 return;
1706
1707         isl_ctx_deref(set->ctx);
1708         for (i = 0; i < set->n; ++i)
1709                 isl_basic_set_free(set->p[i]);
1710         isl_dim_free(set->dim);
1711         free(set);
1712 }
1713
1714 void isl_set_dump(struct isl_set *set, FILE *out, int indent)
1715 {
1716         int i;
1717
1718         if (!set) {
1719                 fprintf(out, "null set\n");
1720                 return;
1721         }
1722
1723         fprintf(out, "%*s", indent, "");
1724         fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
1725                         set->ref, set->n, set->dim->nparam, set->dim->n_out,
1726                         set->flags);
1727         for (i = 0; i < set->n; ++i) {
1728                 fprintf(out, "%*s", indent, "");
1729                 fprintf(out, "basic set %d:\n", i);
1730                 isl_basic_set_dump(set->p[i], out, indent+4);
1731         }
1732 }
1733
1734 void isl_map_dump(struct isl_map *map, FILE *out, int indent)
1735 {
1736         int i;
1737
1738         if (!map) {
1739                 fprintf(out, "null map\n");
1740                 return;
1741         }
1742
1743         fprintf(out, "%*s", indent, "");
1744         fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
1745                      "flags: %x, n_name: %d\n",
1746                         map->ref, map->n, map->dim->nparam, map->dim->n_in,
1747                         map->dim->n_out, map->flags, map->dim->n_name);
1748         for (i = 0; i < map->n; ++i) {
1749                 fprintf(out, "%*s", indent, "");
1750                 fprintf(out, "basic map %d:\n", i);
1751                 isl_basic_map_dump(map->p[i], out, indent+4);
1752         }
1753 }
1754
1755 struct isl_basic_map *isl_basic_map_intersect_domain(
1756                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1757 {
1758         struct isl_basic_map *bmap_domain;
1759         struct isl_dim *dim;
1760
1761         if (!bmap || !bset)
1762                 goto error;
1763
1764         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1765                                         bset->dim, isl_dim_param), goto error);
1766
1767         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1768                 isl_assert(bset->ctx,
1769                     isl_basic_map_compatible_domain(bmap, bset), goto error);
1770
1771         bmap = isl_basic_map_cow(bmap);
1772         if (!bmap)
1773                 goto error;
1774         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1775                         bset->n_div, bset->n_eq, bset->n_ineq);
1776         dim = isl_dim_reverse(isl_dim_copy(bset->dim));
1777         bmap_domain = isl_basic_map_from_basic_set(bset, dim);
1778         bmap = add_constraints(bmap, bmap_domain, 0, 0);
1779
1780         bmap = isl_basic_map_simplify(bmap);
1781         return isl_basic_map_finalize(bmap);
1782 error:
1783         isl_basic_map_free(bmap);
1784         isl_basic_set_free(bset);
1785         return NULL;
1786 }
1787
1788 struct isl_basic_map *isl_basic_map_intersect_range(
1789                 struct isl_basic_map *bmap, struct isl_basic_set *bset)
1790 {
1791         struct isl_basic_map *bmap_range;
1792
1793         if (!bmap || !bset)
1794                 goto error;
1795
1796         isl_assert(bset->ctx, isl_dim_match(bmap->dim, isl_dim_param,
1797                                         bset->dim, isl_dim_param), goto error);
1798
1799         if (isl_dim_size(bset->dim, isl_dim_set) != 0)
1800                 isl_assert(bset->ctx,
1801                     isl_basic_map_compatible_range(bmap, bset), goto error);
1802
1803         bmap = isl_basic_map_cow(bmap);
1804         if (!bmap)
1805                 goto error;
1806         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1807                         bset->n_div, bset->n_eq, bset->n_ineq);
1808         bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
1809         bmap = add_constraints(bmap, bmap_range, 0, 0);
1810
1811         bmap = isl_basic_map_simplify(bmap);
1812         return isl_basic_map_finalize(bmap);
1813 error:
1814         isl_basic_map_free(bmap);
1815         isl_basic_set_free(bset);
1816         return NULL;
1817 }
1818
1819 int isl_basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
1820 {
1821         int i;
1822         unsigned total;
1823         isl_int s;
1824
1825         total = 1 + isl_basic_map_total_dim(bmap);
1826         if (total != vec->size)
1827                 return -1;
1828
1829         isl_int_init(s);
1830
1831         for (i = 0; i < bmap->n_eq; ++i) {
1832                 isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
1833                 if (!isl_int_is_zero(s)) {
1834                         isl_int_clear(s);
1835                         return 0;
1836                 }
1837         }
1838
1839         for (i = 0; i < bmap->n_ineq; ++i) {
1840                 isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
1841                 if (isl_int_is_neg(s)) {
1842                         isl_int_clear(s);
1843                         return 0;
1844                 }
1845         }
1846
1847         isl_int_clear(s);
1848
1849         return 1;
1850 }
1851
1852 int isl_basic_set_contains(struct isl_basic_set *bset, struct isl_vec *vec)
1853 {
1854         return isl_basic_map_contains((struct isl_basic_map *)bset, vec);
1855 }
1856
1857 struct isl_basic_map *isl_basic_map_intersect(
1858                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
1859 {
1860         struct isl_vec *sample = NULL;
1861
1862         if (!bmap1 || !bmap2)
1863                 goto error;
1864
1865         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
1866                                      bmap2->dim, isl_dim_param), goto error);
1867         if (isl_dim_total(bmap1->dim) ==
1868                                 isl_dim_size(bmap1->dim, isl_dim_param) &&
1869             isl_dim_total(bmap2->dim) !=
1870                                 isl_dim_size(bmap2->dim, isl_dim_param))
1871                 return isl_basic_map_intersect(bmap2, bmap1);
1872
1873         if (isl_dim_total(bmap2->dim) !=
1874                                         isl_dim_size(bmap2->dim, isl_dim_param))
1875                 isl_assert(bmap1->ctx,
1876                             isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
1877
1878         if (bmap1->sample &&
1879             isl_basic_map_contains(bmap1, bmap1->sample) > 0 &&
1880             isl_basic_map_contains(bmap2, bmap1->sample) > 0)
1881                 sample = isl_vec_copy(bmap1->sample);
1882         else if (bmap2->sample &&
1883             isl_basic_map_contains(bmap1, bmap2->sample) > 0 &&
1884             isl_basic_map_contains(bmap2, bmap2->sample) > 0)
1885                 sample = isl_vec_copy(bmap2->sample);
1886
1887         bmap1 = isl_basic_map_cow(bmap1);
1888         if (!bmap1)
1889                 goto error;
1890         bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
1891                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
1892         bmap1 = add_constraints(bmap1, bmap2, 0, 0);
1893
1894         if (!bmap1)
1895                 isl_vec_free(sample);
1896         else if (sample) {
1897                 isl_vec_free(bmap1->sample);
1898                 bmap1->sample = sample;
1899         }
1900
1901         bmap1 = isl_basic_map_simplify(bmap1);
1902         return isl_basic_map_finalize(bmap1);
1903 error:
1904         if (sample)
1905                 isl_vec_free(sample);
1906         isl_basic_map_free(bmap1);
1907         isl_basic_map_free(bmap2);
1908         return NULL;
1909 }
1910
1911 struct isl_basic_set *isl_basic_set_intersect(
1912                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
1913 {
1914         return (struct isl_basic_set *)
1915                 isl_basic_map_intersect(
1916                         (struct isl_basic_map *)bset1,
1917                         (struct isl_basic_map *)bset2);
1918 }
1919
1920 /* Special case of isl_map_intersect, where both map1 and map2
1921  * are convex, without any divs and such that either map1 or map2
1922  * contains a single constraint.  This constraint is then simply
1923  * added to the other map.
1924  */
1925 static __isl_give isl_map *map_intersect_add_constraint(
1926         __isl_take isl_map *map1, __isl_take isl_map *map2)
1927 {
1928         struct isl_basic_map *bmap1;
1929         struct isl_basic_map *bmap2;
1930
1931         isl_assert(map1->ctx, map1->n == 1, goto error);
1932         isl_assert(map2->ctx, map1->n == 1, goto error);
1933         isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
1934         isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);
1935
1936         if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
1937                 return isl_map_intersect(map2, map1);
1938
1939         isl_assert(map2->ctx,
1940                     map2->p[0]->n_eq + map2->p[0]->n_ineq == 1, goto error);
1941
1942         map1 = isl_map_cow(map1);
1943         if (!map1)
1944                 goto error;
1945         if (isl_map_fast_is_empty(map1)) {
1946                 isl_map_free(map2);
1947                 return map1;
1948         }
1949         map1->p[0] = isl_basic_map_cow(map1->p[0]);
1950         if (map2->p[0]->n_eq == 1)
1951                 map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
1952         else
1953                 map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
1954                                                         map2->p[0]->ineq[0]);
1955
1956         map1->p[0] = isl_basic_map_simplify(map1->p[0]);
1957         map1->p[0] = isl_basic_map_finalize(map1->p[0]);
1958         if (!map1->p[0])
1959                 goto error;
1960
1961         if (isl_basic_map_fast_is_empty(map1->p[0])) {
1962                 isl_basic_map_free(map1->p[0]);
1963                 map1->n = 0;
1964         }
1965
1966         isl_map_free(map2);
1967
1968         return map1;
1969 error:
1970         isl_map_free(map1);
1971         isl_map_free(map2);
1972         return NULL;
1973 }
1974
1975 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
1976 {
1977         unsigned flags = 0;
1978         struct isl_map *result;
1979         int i, j;
1980
1981         if (!map1 || !map2)
1982                 goto error;
1983
1984         if (isl_map_fast_is_empty(map1)) {
1985                 isl_map_free(map2);
1986                 return map1;
1987         }
1988         if (isl_map_fast_is_empty(map2)) {
1989                 isl_map_free(map1);
1990                 return map2;
1991         }
1992
1993         if (map1->n == 1 && map2->n == 1 &&
1994             map1->p[0]->n_div == 0 && map2->p[0]->n_div == 0 &&
1995             isl_dim_equal(map1->dim, map2->dim) &&
1996             (map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 ||
1997              map2->p[0]->n_eq + map2->p[0]->n_ineq == 1))
1998                 return map_intersect_add_constraint(map1, map2);
1999         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
2000                                          map2->dim, isl_dim_param), goto error);
2001         if (isl_dim_total(map1->dim) ==
2002                                 isl_dim_size(map1->dim, isl_dim_param) &&
2003             isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
2004                 return isl_map_intersect(map2, map1);
2005
2006         if (isl_dim_total(map2->dim) != isl_dim_size(map2->dim, isl_dim_param))
2007                 isl_assert(map1->ctx,
2008                             isl_dim_equal(map1->dim, map2->dim), goto error);
2009
2010         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
2011             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
2012                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
2013
2014         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2015                                 map1->n * map2->n, flags);
2016         if (!result)
2017                 goto error;
2018         for (i = 0; i < map1->n; ++i)
2019                 for (j = 0; j < map2->n; ++j) {
2020                         struct isl_basic_map *part;
2021                         part = isl_basic_map_intersect(
2022                                     isl_basic_map_copy(map1->p[i]),
2023                                     isl_basic_map_copy(map2->p[j]));
2024                         if (isl_basic_map_is_empty(part))
2025                                 isl_basic_map_free(part);
2026                         else
2027                                 result = isl_map_add_basic_map(result, part);
2028                         if (!result)
2029                                 goto error;
2030                 }
2031         isl_map_free(map1);
2032         isl_map_free(map2);
2033         return result;
2034 error:
2035         isl_map_free(map1);
2036         isl_map_free(map2);
2037         return NULL;
2038 }
2039
2040 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
2041 {
2042         return (struct isl_set *)
2043                 isl_map_intersect((struct isl_map *)set1,
2044                                   (struct isl_map *)set2);
2045 }
2046
2047 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
2048 {
2049         struct isl_dim *dim;
2050         struct isl_basic_set *bset;
2051         unsigned in;
2052
2053         if (!bmap)
2054                 return NULL;
2055         bmap = isl_basic_map_cow(bmap);
2056         if (!bmap)
2057                 return NULL;
2058         dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
2059         in = isl_basic_map_n_in(bmap);
2060         bset = isl_basic_set_from_basic_map(bmap);
2061         bset = isl_basic_set_swap_vars(bset, in);
2062         return isl_basic_map_from_basic_set(bset, dim);
2063 }
2064
2065 __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap,
2066                 enum isl_dim_type type, unsigned pos, unsigned n)
2067 {
2068         struct isl_dim *res_dim;
2069         struct isl_basic_map *res;
2070         struct isl_dim_map *dim_map;
2071         unsigned total, off;
2072         enum isl_dim_type t;
2073
2074         if (n == 0)
2075                 return bmap;
2076
2077         if (!bmap)
2078                 return NULL;
2079
2080         res_dim = isl_dim_insert(isl_basic_map_get_dim(bmap), type, pos, n);
2081
2082         total = isl_basic_map_total_dim(bmap) + n;
2083         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2084         off = 0;
2085         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2086                 if (t != type) {
2087                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2088                 } else {
2089                         unsigned size = isl_basic_map_dim(bmap, t);
2090                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2091                                                 0, pos, off);
2092                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2093                                                 pos, size - pos, off + pos + n);
2094                 }
2095                 off += isl_dim_size(res_dim, t);
2096         }
2097         isl_dim_map_div(dim_map, bmap, off);
2098
2099         res = isl_basic_map_alloc_dim(res_dim,
2100                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2101         res = add_constraints_dim_map(res, bmap, dim_map);
2102         res = isl_basic_map_simplify(res);
2103         return isl_basic_map_finalize(res);
2104 }
2105
2106 __isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
2107                 enum isl_dim_type type, unsigned n)
2108 {
2109         if (!bmap)
2110                 return NULL;
2111         return isl_basic_map_insert(bmap, type,
2112                                         isl_basic_map_dim(bmap, type), n);
2113 }
2114
2115 __isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset,
2116                 enum isl_dim_type type, unsigned n)
2117 {
2118         if (!bset)
2119                 return NULL;
2120         isl_assert(bset->ctx, type != isl_dim_in, goto error);
2121         return (isl_basic_set *)isl_basic_map_add((isl_basic_map *)bset, type, n);
2122 error:
2123         isl_basic_set_free(bset);
2124         return NULL;
2125 }
2126
2127 __isl_give isl_map *isl_map_insert(__isl_take isl_map *map,
2128                 enum isl_dim_type type, unsigned pos, unsigned n)
2129 {
2130         int i;
2131
2132         if (n == 0)
2133                 return map;
2134
2135         map = isl_map_cow(map);
2136         if (!map)
2137                 return NULL;
2138
2139         map->dim = isl_dim_insert(map->dim, type, pos, n);
2140         if (!map->dim)
2141                 goto error;
2142
2143         for (i = 0; i < map->n; ++i) {
2144                 map->p[i] = isl_basic_map_insert(map->p[i], type, pos, n);
2145                 if (!map->p[i])
2146                         goto error;
2147         }
2148
2149         return map;
2150 error:
2151         isl_map_free(map);
2152         return NULL;
2153 }
2154
2155 __isl_give isl_map *isl_map_add(__isl_take isl_map *map,
2156                 enum isl_dim_type type, unsigned n)
2157 {
2158         if (!map)
2159                 return NULL;
2160         return isl_map_insert(map, type, isl_map_dim(map, type), n);
2161 }
2162
2163 __isl_give isl_set *isl_set_add(__isl_take isl_set *set,
2164                 enum isl_dim_type type, unsigned n)
2165 {
2166         if (!set)
2167                 return NULL;
2168         isl_assert(set->ctx, type != isl_dim_in, goto error);
2169         return (isl_set *)isl_map_add((isl_map *)set, type, n);
2170 error:
2171         isl_set_free(set);
2172         return NULL;
2173 }
2174
2175 __isl_give isl_basic_map *isl_basic_map_move_dims(
2176         __isl_take isl_basic_map *bmap,
2177         enum isl_dim_type dst_type, unsigned dst_pos,
2178         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2179 {
2180         int i;
2181         struct isl_dim_map *dim_map;
2182         struct isl_basic_map *res;
2183         enum isl_dim_type t;
2184         unsigned total, off;
2185
2186         if (!bmap)
2187                 return NULL;
2188         if (n == 0)
2189                 return bmap;
2190
2191         isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type),
2192                 goto error);
2193
2194         if (dst_type == src_type && dst_pos == src_pos)
2195                 return bmap;
2196
2197         isl_assert(bmap->ctx, dst_type != src_type, goto error);
2198
2199         if (pos(bmap->dim, dst_type) + dst_pos ==
2200             pos(bmap->dim, src_type) + src_pos +
2201                                             ((src_type < dst_type) ? n : 0)) {
2202                 bmap = isl_basic_map_cow(bmap);
2203                 if (!bmap)
2204                         return NULL;
2205
2206                 bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
2207                                                 src_type, src_pos, n);
2208                 if (!bmap->dim)
2209                         goto error;
2210
2211                 bmap = isl_basic_map_finalize(bmap);
2212
2213                 return bmap;
2214         }
2215
2216         total = isl_basic_map_total_dim(bmap);
2217         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2218
2219         off = 0;
2220         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2221                 unsigned size = isl_dim_size(bmap->dim, t);
2222                 if (t == dst_type) {
2223                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2224                                             0, dst_pos, off);
2225                         off += dst_pos;
2226                         isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
2227                                             src_pos, n, off);
2228                         off += n;
2229                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2230                                             dst_pos, size - dst_pos, off);
2231                         off += size - dst_pos;
2232                 } else if (t == src_type) {
2233                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2234                                             0, src_pos, off);
2235                         off += src_pos;
2236                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2237                                         src_pos + n, size - src_pos - n, off);
2238                         off += size - src_pos - n;
2239                 } else {
2240                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2241                         off += size;
2242                 }
2243         }
2244         isl_dim_map_div(dim_map, bmap, off + n);
2245
2246         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2247                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2248         bmap = add_constraints_dim_map(res, bmap, dim_map);
2249
2250         bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
2251                                         src_type, src_pos, n);
2252         if (!bmap->dim)
2253                 goto error;
2254
2255         ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2256         bmap = isl_basic_map_gauss(bmap, NULL);
2257         bmap = isl_basic_map_finalize(bmap);
2258
2259         return bmap;
2260 error:
2261         isl_basic_map_free(bmap);
2262         return NULL;
2263 }
2264
2265 __isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
2266         enum isl_dim_type dst_type, unsigned dst_pos,
2267         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2268 {
2269         return (isl_basic_set *)isl_basic_map_move_dims(
2270                 (isl_basic_map *)bset, dst_type, dst_pos, src_type, src_pos, n);
2271 }
2272
2273 __isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
2274         enum isl_dim_type dst_type, unsigned dst_pos,
2275         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2276 {
2277         if (!set)
2278                 return NULL;
2279         isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
2280         return (isl_set *)isl_map_move_dims((isl_map *)set, dst_type, dst_pos,
2281                                         src_type, src_pos, n);
2282 error:
2283         isl_set_free(set);
2284         return NULL;
2285 }
2286
2287 __isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
2288         enum isl_dim_type dst_type, unsigned dst_pos,
2289         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2290 {
2291         int i;
2292
2293         if (!map)
2294                 return NULL;
2295         if (n == 0)
2296                 return map;
2297
2298         isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type),
2299                 goto error);
2300
2301         if (dst_type == src_type && dst_pos == src_pos)
2302                 return map;
2303
2304         isl_assert(map->ctx, dst_type != src_type, goto error);
2305
2306         map = isl_map_cow(map);
2307         if (!map)
2308                 return NULL;
2309
2310         map->dim = isl_dim_move(map->dim, dst_type, dst_pos, src_type, src_pos, n);
2311         if (!map->dim)
2312                 goto error;
2313
2314         for (i = 0; i < map->n; ++i) {
2315                 map->p[i] = isl_basic_map_move_dims(map->p[i],
2316                                                 dst_type, dst_pos,
2317                                                 src_type, src_pos, n);
2318                 if (!map->p[i])
2319                         goto error;
2320         }
2321
2322         return map;
2323 error:
2324         isl_map_free(map);
2325         return NULL;
2326 }
2327
2328 /* Move the specified dimensions to the last columns right before
2329  * the divs.  Don't change the dimension specification of bmap.
2330  * That's the responsibility of the caller.
2331  */
2332 static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
2333         enum isl_dim_type type, unsigned first, unsigned n)
2334 {
2335         struct isl_dim_map *dim_map;
2336         struct isl_basic_map *res;
2337         enum isl_dim_type t;
2338         unsigned total, off;
2339
2340         if (!bmap)
2341                 return NULL;
2342         if (pos(bmap->dim, type) + first + n == 1 + isl_dim_total(bmap->dim))
2343                 return bmap;
2344
2345         total = isl_basic_map_total_dim(bmap);
2346         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2347
2348         off = 0;
2349         for (t = isl_dim_param; t <= isl_dim_out; ++t) {
2350                 unsigned size = isl_dim_size(bmap->dim, t);
2351                 if (t == type) {
2352                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2353                                             0, first, off);
2354                         off += first;
2355                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2356                                             first, n, total - bmap->n_div - n);
2357                         isl_dim_map_dim_range(dim_map, bmap->dim, t,
2358                                             first + n, size - (first + n), off);
2359                         off += size - (first + n);
2360                 } else {
2361                         isl_dim_map_dim(dim_map, bmap->dim, t, off);
2362                         off += size;
2363                 }
2364         }
2365         isl_dim_map_div(dim_map, bmap, off + n);
2366
2367         res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
2368                         bmap->n_div, bmap->n_eq, bmap->n_ineq);
2369         res = add_constraints_dim_map(res, bmap, dim_map);
2370         return res;
2371 }
2372
2373 /* Turn the n dimensions of type type, starting at first
2374  * into existentially quantified variables.
2375  */
2376 __isl_give isl_basic_map *isl_basic_map_project_out(
2377                 __isl_take isl_basic_map *bmap,
2378                 enum isl_dim_type type, unsigned first, unsigned n)
2379 {
2380         int i;
2381         size_t row_size;
2382         isl_int **new_div;
2383         isl_int *old;
2384
2385         if (n == 0)
2386                 return bmap;
2387
2388         if (!bmap)
2389                 return NULL;
2390
2391         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
2392                 return isl_basic_map_remove(bmap, type, first, n);
2393
2394         isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
2395                         goto error);
2396
2397         bmap = move_last(bmap, type, first, n);
2398         bmap = isl_basic_map_cow(bmap);
2399         if (!bmap)
2400                 return NULL;
2401
2402         row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra;
2403         old = bmap->block2.data;
2404         bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
2405                                         (bmap->extra + n) * (1 + row_size));
2406         if (!bmap->block2.data)
2407                 goto error;
2408         new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
2409         if (!new_div)
2410                 goto error;
2411         for (i = 0; i < n; ++i) {
2412                 new_div[i] = bmap->block2.data +
2413                                 (bmap->extra + i) * (1 + row_size);
2414                 isl_seq_clr(new_div[i], 1 + row_size);
2415         }
2416         for (i = 0; i < bmap->extra; ++i)
2417                 new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
2418         free(bmap->div);
2419         bmap->div = new_div;
2420         bmap->n_div += n;
2421         bmap->extra += n;
2422
2423         bmap->dim = isl_dim_drop(bmap->dim, type, first, n);
2424         if (!bmap->dim)
2425                 goto error;
2426         bmap = isl_basic_map_simplify(bmap);
2427         bmap = isl_basic_map_drop_redundant_divs(bmap);
2428         return isl_basic_map_finalize(bmap);
2429 error:
2430         isl_basic_map_free(bmap);
2431         return NULL;
2432 }
2433
2434 /* Turn the n dimensions of type type, starting at first
2435  * into existentially quantified variables.
2436  */
2437 struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
2438                 enum isl_dim_type type, unsigned first, unsigned n)
2439 {
2440         return (isl_basic_set *)isl_basic_map_project_out(
2441                         (isl_basic_map *)bset, type, first, n);
2442 }
2443
2444 /* Turn the n dimensions of type type, starting at first
2445  * into existentially quantified variables.
2446  */
2447 __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
2448                 enum isl_dim_type type, unsigned first, unsigned n)
2449 {
2450         int i;
2451
2452         if (!map)
2453                 return NULL;
2454
2455         if (n == 0)
2456                 return map;
2457
2458         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
2459
2460         map = isl_map_cow(map);
2461         if (!map)
2462                 return NULL;
2463
2464         map->dim = isl_dim_drop(map->dim, type, first, n);
2465         if (!map->dim)
2466                 goto error;
2467
2468         for (i = 0; i < map->n; ++i) {
2469                 map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
2470                 if (!map->p[i])
2471                         goto error;
2472         }
2473
2474         return map;
2475 error:
2476         isl_map_free(map);
2477         return NULL;
2478 }
2479
2480 /* Turn the n dimensions of type type, starting at first
2481  * into existentially quantified variables.
2482  */
2483 __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
2484                 enum isl_dim_type type, unsigned first, unsigned n)
2485 {
2486         return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n);
2487 }
2488
2489 static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2490 {
2491         int i, j;
2492
2493         for (i = 0; i < n; ++i) {
2494                 j = isl_basic_map_alloc_div(bmap);
2495                 if (j < 0)
2496                         goto error;
2497                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2498         }
2499         return bmap;
2500 error:
2501         isl_basic_map_free(bmap);
2502         return NULL;
2503 }
2504
2505 struct isl_basic_map *isl_basic_map_apply_range(
2506                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2507 {
2508         struct isl_dim *dim_result = NULL;
2509         struct isl_basic_map *bmap;
2510         unsigned n_in, n_out, n, nparam, total, pos;
2511         struct isl_dim_map *dim_map1, *dim_map2;
2512
2513         if (!bmap1 || !bmap2)
2514                 goto error;
2515
2516         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2517                                   isl_dim_copy(bmap2->dim));
2518
2519         n_in = isl_basic_map_n_in(bmap1);
2520         n_out = isl_basic_map_n_out(bmap2);
2521         n = isl_basic_map_n_out(bmap1);
2522         nparam = isl_basic_map_n_param(bmap1);
2523
2524         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2525         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2526         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2527         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2528         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2529         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2530         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2531         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2532         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2533         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2534         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2535
2536         bmap = isl_basic_map_alloc_dim(dim_result,
2537                         bmap1->n_div + bmap2->n_div + n,
2538                         bmap1->n_eq + bmap2->n_eq,
2539                         bmap1->n_ineq + bmap2->n_ineq);
2540         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2541         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2542         bmap = add_divs(bmap, n);
2543         bmap = isl_basic_map_simplify(bmap);
2544         bmap = isl_basic_map_drop_redundant_divs(bmap);
2545         return isl_basic_map_finalize(bmap);
2546 error:
2547         isl_basic_map_free(bmap1);
2548         isl_basic_map_free(bmap2);
2549         return NULL;
2550 }
2551
2552 struct isl_basic_set *isl_basic_set_apply(
2553                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2554 {
2555         if (!bset || !bmap)
2556                 goto error;
2557
2558         isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
2559                     goto error);
2560
2561         return (struct isl_basic_set *)
2562                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2563 error:
2564         isl_basic_set_free(bset);
2565         isl_basic_map_free(bmap);
2566         return NULL;
2567 }
2568
2569 struct isl_basic_map *isl_basic_map_apply_domain(
2570                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2571 {
2572         if (!bmap1 || !bmap2)
2573                 goto error;
2574
2575         isl_assert(bmap1->ctx,
2576             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2577         isl_assert(bmap1->ctx,
2578             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2579             goto error);
2580
2581         bmap1 = isl_basic_map_reverse(bmap1);
2582         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2583         return isl_basic_map_reverse(bmap1);
2584 error:
2585         isl_basic_map_free(bmap1);
2586         isl_basic_map_free(bmap2);
2587         return NULL;
2588 }
2589
2590 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
2591  * A \cap B -> f(A) + f(B)
2592  */
2593 struct isl_basic_map *isl_basic_map_sum(
2594                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2595 {
2596         unsigned n_in, n_out, nparam, total, pos;
2597         struct isl_basic_map *bmap = NULL;
2598         struct isl_dim_map *dim_map1, *dim_map2;
2599         int i;
2600
2601         if (!bmap1 || !bmap2)
2602                 goto error;
2603
2604         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
2605                 goto error);
2606
2607         nparam = isl_basic_map_n_param(bmap1);
2608         n_in = isl_basic_map_n_in(bmap1);
2609         n_out = isl_basic_map_n_out(bmap1);
2610
2611         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
2612         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2613         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
2614         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2615         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
2616         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2617         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2618         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
2619         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2620         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2621         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
2622
2623         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
2624                         bmap1->n_div + bmap2->n_div + 2 * n_out,
2625                         bmap1->n_eq + bmap2->n_eq + n_out,
2626                         bmap1->n_ineq + bmap2->n_ineq);
2627         for (i = 0; i < n_out; ++i) {
2628                 int j = isl_basic_map_alloc_equality(bmap);
2629                 if (j < 0)
2630                         goto error;
2631                 isl_seq_clr(bmap->eq[j], 1+total);
2632                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
2633                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
2634                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
2635         }
2636         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2637         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2638         bmap = add_divs(bmap, 2 * n_out);
2639
2640         bmap = isl_basic_map_simplify(bmap);
2641         return isl_basic_map_finalize(bmap);
2642 error:
2643         isl_basic_map_free(bmap);
2644         isl_basic_map_free(bmap1);
2645         isl_basic_map_free(bmap2);
2646         return NULL;
2647 }
2648
2649 /* Given two maps A -> f(A) and B -> g(B), construct a map
2650  * A \cap B -> f(A) + f(B)
2651  */
2652 struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2)
2653 {
2654         struct isl_map *result;
2655         int i, j;
2656
2657         if (!map1 || !map2)
2658                 goto error;
2659
2660         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2661
2662         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2663                                 map1->n * map2->n, 0);
2664         if (!result)
2665                 goto error;
2666         for (i = 0; i < map1->n; ++i)
2667                 for (j = 0; j < map2->n; ++j) {
2668                         struct isl_basic_map *part;
2669                         part = isl_basic_map_sum(
2670                                     isl_basic_map_copy(map1->p[i]),
2671                                     isl_basic_map_copy(map2->p[j]));
2672                         if (isl_basic_map_is_empty(part))
2673                                 isl_basic_map_free(part);
2674                         else
2675                                 result = isl_map_add_basic_map(result, part);
2676                         if (!result)
2677                                 goto error;
2678                 }
2679         isl_map_free(map1);
2680         isl_map_free(map2);
2681         return result;
2682 error:
2683         isl_map_free(map1);
2684         isl_map_free(map2);
2685         return NULL;
2686 }
2687
2688 __isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
2689         __isl_take isl_set *set2)
2690 {
2691         return (isl_set *)isl_map_sum((isl_map *)set1, (isl_map *)set2);
2692 }
2693
2694 /* Given a basic map A -> f(A), construct A -> -f(A).
2695  */
2696 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
2697 {
2698         int i, j;
2699         unsigned off, n;
2700
2701         bmap = isl_basic_map_cow(bmap);
2702         if (!bmap)
2703                 return NULL;
2704
2705         n = isl_basic_map_dim(bmap, isl_dim_out);
2706         off = isl_basic_map_offset(bmap, isl_dim_out);
2707         for (i = 0; i < bmap->n_eq; ++i)
2708                 for (j = 0; j < n; ++j)
2709                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
2710         for (i = 0; i < bmap->n_ineq; ++i)
2711                 for (j = 0; j < n; ++j)
2712                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
2713         for (i = 0; i < bmap->n_div; ++i)
2714                 for (j = 0; j < n; ++j)
2715                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
2716         return isl_basic_map_finalize(bmap);
2717 }
2718
2719 /* Given a map A -> f(A), construct A -> -f(A).
2720  */
2721 struct isl_map *isl_map_neg(struct isl_map *map)
2722 {
2723         int i;
2724
2725         map = isl_map_cow(map);
2726         if (!map)
2727                 return NULL;
2728
2729         for (i = 0; i < map->n; ++i) {
2730                 map->p[i] = isl_basic_map_neg(map->p[i]);
2731                 if (!map->p[i])
2732                         goto error;
2733         }
2734
2735         return map;
2736 error:
2737         isl_map_free(map);
2738         return NULL;
2739 }
2740
2741 __isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
2742 {
2743         return (isl_set *)isl_map_neg((isl_map *)set);
2744 }
2745
2746 /* Given a basic map A -> f(A) and an integer d, construct a basic map
2747  * A -> floor(f(A)/d).
2748  */
2749 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
2750                 isl_int d)
2751 {
2752         unsigned n_in, n_out, nparam, total, pos;
2753         struct isl_basic_map *result = NULL;
2754         struct isl_dim_map *dim_map;
2755         int i;
2756
2757         if (!bmap)
2758                 return NULL;
2759
2760         nparam = isl_basic_map_n_param(bmap);
2761         n_in = isl_basic_map_n_in(bmap);
2762         n_out = isl_basic_map_n_out(bmap);
2763
2764         total = nparam + n_in + n_out + bmap->n_div + n_out;
2765         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2766         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
2767         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
2768         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
2769         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
2770
2771         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
2772                         bmap->n_div + n_out,
2773                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
2774         result = add_constraints_dim_map(result, bmap, dim_map);
2775         result = add_divs(result, n_out);
2776         for (i = 0; i < n_out; ++i) {
2777                 int j;
2778                 j = isl_basic_map_alloc_inequality(result);
2779                 if (j < 0)
2780                         goto error;
2781                 isl_seq_clr(result->ineq[j], 1+total);
2782                 isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
2783                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
2784                 j = isl_basic_map_alloc_inequality(result);
2785                 if (j < 0)
2786                         goto error;
2787                 isl_seq_clr(result->ineq[j], 1+total);
2788                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
2789                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
2790                 isl_int_sub_ui(result->ineq[j][0], d, 1);
2791         }
2792
2793         result = isl_basic_map_simplify(result);
2794         return isl_basic_map_finalize(result);
2795 error:
2796         isl_basic_map_free(result);
2797         return NULL;
2798 }
2799
2800 /* Given a map A -> f(A) and an integer d, construct a map
2801  * A -> floor(f(A)/d).
2802  */
2803 struct isl_map *isl_map_floordiv(struct isl_map *map, isl_int d)
2804 {
2805         int i;
2806
2807         map = isl_map_cow(map);
2808         if (!map)
2809                 return NULL;
2810
2811         ISL_F_CLR(map, ISL_MAP_DISJOINT);
2812         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2813         for (i = 0; i < map->n; ++i) {
2814                 map->p[i] = isl_basic_map_floordiv(map->p[i], d);
2815                 if (!map->p[i])
2816                         goto error;
2817         }
2818
2819         return map;
2820 error:
2821         isl_map_free(map);
2822         return NULL;
2823 }
2824
2825 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
2826 {
2827         int i;
2828         unsigned nparam;
2829         unsigned n_in;
2830
2831         i = isl_basic_map_alloc_equality(bmap);
2832         if (i < 0)
2833                 goto error;
2834         nparam = isl_basic_map_n_param(bmap);
2835         n_in = isl_basic_map_n_in(bmap);
2836         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2837         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2838         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2839         return isl_basic_map_finalize(bmap);
2840 error:
2841         isl_basic_map_free(bmap);
2842         return NULL;
2843 }
2844
2845 /* Add a constraints to "bmap" expressing i_pos < o_pos
2846  */
2847 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2848 {
2849         int i;
2850         unsigned nparam;
2851         unsigned n_in;
2852
2853         i = isl_basic_map_alloc_inequality(bmap);
2854         if (i < 0)
2855                 goto error;
2856         nparam = isl_basic_map_n_param(bmap);
2857         n_in = isl_basic_map_n_in(bmap);
2858         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2859         isl_int_set_si(bmap->ineq[i][0], -1);
2860         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2861         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2862         return isl_basic_map_finalize(bmap);
2863 error:
2864         isl_basic_map_free(bmap);
2865         return NULL;
2866 }
2867
2868 /* Add a constraint to "bmap" expressing i_pos <= o_pos
2869  */
2870 static __isl_give isl_basic_map *var_less_or_equal(
2871         __isl_take isl_basic_map *bmap, unsigned pos)
2872 {
2873         int i;
2874         unsigned nparam;
2875         unsigned n_in;
2876
2877         i = isl_basic_map_alloc_inequality(bmap);
2878         if (i < 0)
2879                 goto error;
2880         nparam = isl_basic_map_n_param(bmap);
2881         n_in = isl_basic_map_n_in(bmap);
2882         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2883         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2884         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2885         return isl_basic_map_finalize(bmap);
2886 error:
2887         isl_basic_map_free(bmap);
2888         return NULL;
2889 }
2890
2891 /* Add a constraints to "bmap" expressing i_pos > o_pos
2892  */
2893 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
2894 {
2895         int i;
2896         unsigned nparam;
2897         unsigned n_in;
2898
2899         i = isl_basic_map_alloc_inequality(bmap);
2900         if (i < 0)
2901                 goto error;
2902         nparam = isl_basic_map_n_param(bmap);
2903         n_in = isl_basic_map_n_in(bmap);
2904         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2905         isl_int_set_si(bmap->ineq[i][0], -1);
2906         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2907         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2908         return isl_basic_map_finalize(bmap);
2909 error:
2910         isl_basic_map_free(bmap);
2911         return NULL;
2912 }
2913
2914 /* Add a constraint to "bmap" expressing i_pos >= o_pos
2915  */
2916 static __isl_give isl_basic_map *var_more_or_equal(
2917         __isl_take isl_basic_map *bmap, unsigned pos)
2918 {
2919         int i;
2920         unsigned nparam;
2921         unsigned n_in;
2922
2923         i = isl_basic_map_alloc_inequality(bmap);
2924         if (i < 0)
2925                 goto error;
2926         nparam = isl_basic_map_n_param(bmap);
2927         n_in = isl_basic_map_n_in(bmap);
2928         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2929         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2930         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2931         return isl_basic_map_finalize(bmap);
2932 error:
2933         isl_basic_map_free(bmap);
2934         return NULL;
2935 }
2936
2937 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
2938 {
2939         int i;
2940         struct isl_basic_map *bmap;
2941         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
2942         if (!bmap)
2943                 return NULL;
2944         for (i = 0; i < n_equal && bmap; ++i)
2945                 bmap = var_equal(bmap, i);
2946         return isl_basic_map_finalize(bmap);
2947 }
2948
2949 /* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
2950  */
2951 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
2952 {
2953         int i;
2954         struct isl_basic_map *bmap;
2955         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2956         if (!bmap)
2957                 return NULL;
2958         for (i = 0; i < pos && bmap; ++i)
2959                 bmap = var_equal(bmap, i);
2960         if (bmap)
2961                 bmap = var_less(bmap, pos);
2962         return isl_basic_map_finalize(bmap);
2963 }
2964
2965 /* Return a relation on of dimension "dim" expressing i_[0..pos] <<= o_[0..pos]
2966  */
2967 __isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
2968         __isl_take isl_dim *dim, unsigned pos)
2969 {
2970         int i;
2971         isl_basic_map *bmap;
2972
2973         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2974         for (i = 0; i < pos; ++i)
2975                 bmap = var_equal(bmap, i);
2976         bmap = var_less_or_equal(bmap, pos);
2977         return isl_basic_map_finalize(bmap);
2978 }
2979
2980 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
2981  */
2982 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
2983 {
2984         int i;
2985         struct isl_basic_map *bmap;
2986         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2987         if (!bmap)
2988                 return NULL;
2989         for (i = 0; i < pos && bmap; ++i)
2990                 bmap = var_equal(bmap, i);
2991         if (bmap)
2992                 bmap = var_more(bmap, pos);
2993         return isl_basic_map_finalize(bmap);
2994 }
2995
2996 /* Return a relation on of dimension "dim" expressing i_[0..pos] >>= o_[0..pos]
2997  */
2998 __isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
2999         __isl_take isl_dim *dim, unsigned pos)
3000 {
3001         int i;
3002         isl_basic_map *bmap;
3003
3004         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
3005         for (i = 0; i < pos; ++i)
3006                 bmap = var_equal(bmap, i);
3007         bmap = var_more_or_equal(bmap, pos);
3008         return isl_basic_map_finalize(bmap);
3009 }
3010
3011 static __isl_give isl_map *map_lex_lte_first(__isl_take isl_dim *dims,
3012         unsigned n, int equal)
3013 {
3014         struct isl_map *map;
3015         int i;
3016
3017         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3018
3019         for (i = 0; i + 1 < n; ++i)
3020                 map = isl_map_add_basic_map(map,
3021                                   isl_basic_map_less_at(isl_dim_copy(dims), i));
3022         if (n > 0) {
3023                 if (equal)
3024                         map = isl_map_add_basic_map(map,
3025                               isl_basic_map_less_or_equal_at(dims, n - 1));
3026                 else
3027                         map = isl_map_add_basic_map(map,
3028                               isl_basic_map_less_at(dims, n - 1));
3029         } else
3030                 isl_dim_free(dims);
3031
3032         return map;
3033 }
3034
3035 static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
3036 {
3037         if (!dims)
3038                 return NULL;
3039         return map_lex_lte_first(dims, dims->n_out, equal);
3040 }
3041
3042 __isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_dim *dim, unsigned n)
3043 {
3044         return map_lex_lte_first(dim, n, 0);
3045 }
3046
3047 __isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n)
3048 {
3049         return map_lex_lte_first(dim, n, 1);
3050 }
3051
3052 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
3053 {
3054         return map_lex_lte(isl_dim_map(set_dim), 0);
3055 }
3056
3057 __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
3058 {
3059         return map_lex_lte(isl_dim_map(set_dim), 1);
3060 }
3061
3062 static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims,
3063         unsigned n, int equal)
3064 {
3065         struct isl_map *map;
3066         int i;
3067
3068         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3069
3070         for (i = 0; i + 1 < n; ++i)
3071                 map = isl_map_add_basic_map(map,
3072                                   isl_basic_map_more_at(isl_dim_copy(dims), i));
3073         if (n > 0) {
3074                 if (equal)
3075                         map = isl_map_add_basic_map(map,
3076                               isl_basic_map_more_or_equal_at(dims, n - 1));
3077                 else
3078                         map = isl_map_add_basic_map(map,
3079                               isl_basic_map_more_at(dims, n - 1));
3080         } else
3081                 isl_dim_free(dims);
3082
3083         return map;
3084 }
3085
3086 static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
3087 {
3088         if (!dims)
3089                 return NULL;
3090         return map_lex_gte_first(dims, dims->n_out, equal);
3091 }
3092
3093 __isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_dim *dim, unsigned n)
3094 {
3095         return map_lex_gte_first(dim, n, 0);
3096 }
3097
3098 __isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n)
3099 {
3100         return map_lex_gte_first(dim, n, 1);
3101 }
3102
3103 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
3104 {
3105         return map_lex_gte(isl_dim_map(set_dim), 0);
3106 }
3107
3108 __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim)
3109 {
3110         return map_lex_gte(isl_dim_map(set_dim), 1);
3111 }
3112
3113 struct isl_basic_map *isl_basic_map_from_basic_set(
3114                 struct isl_basic_set *bset, struct isl_dim *dim)
3115 {
3116         struct isl_basic_map *bmap;
3117
3118         bset = isl_basic_set_cow(bset);
3119         if (!bset || !dim)
3120                 goto error;
3121
3122         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
3123         isl_dim_free(bset->dim);
3124         bmap = (struct isl_basic_map *) bset;
3125         bmap->dim = dim;
3126         return isl_basic_map_finalize(bmap);
3127 error:
3128         isl_basic_set_free(bset);
3129         isl_dim_free(dim);
3130         return NULL;
3131 }
3132
3133 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
3134 {
3135         if (!bmap)
3136                 goto error;
3137         if (bmap->dim->n_in == 0)
3138                 return (struct isl_basic_set *)bmap;
3139         bmap = isl_basic_map_cow(bmap);
3140         if (!bmap)
3141                 goto error;
3142         bmap->dim = isl_dim_cow(bmap->dim);
3143         if (!bmap->dim)
3144                 goto error;
3145         bmap->dim->n_out += bmap->dim->n_in;
3146         bmap->dim->n_in = 0;
3147         bmap = isl_basic_map_finalize(bmap);
3148         return (struct isl_basic_set *)bmap;
3149 error:
3150         isl_basic_map_free(bmap);
3151         return NULL;
3152 }
3153
3154 /* For a div d = floor(f/m), add the constraints
3155  *
3156  *              f - m d >= 0
3157  *              -(f-(n-1)) + m d >= 0
3158  *
3159  * Note that the second constraint is the negation of
3160  *
3161  *              f - m d >= n
3162  */
3163 int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
3164         unsigned pos, isl_int *div)
3165 {
3166         int i, j;
3167         unsigned total = isl_basic_map_total_dim(bmap);
3168
3169         i = isl_basic_map_alloc_inequality(bmap);
3170         if (i < 0)
3171                 return -1;
3172         isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
3173         isl_int_neg(bmap->ineq[i][1 + pos], div[0]);
3174
3175         j = isl_basic_map_alloc_inequality(bmap);
3176         if (j < 0)
3177                 return -1;
3178         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
3179         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][1 + pos]);
3180         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
3181         return j;
3182 }
3183
3184 int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
3185         unsigned pos, isl_int *div)
3186 {
3187         return isl_basic_map_add_div_constraints_var((isl_basic_map *)bset,
3188                                                         pos, div);
3189 }
3190
3191 int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
3192 {
3193         unsigned total = isl_basic_map_total_dim(bmap);
3194         unsigned div_pos = total - bmap->n_div + div;
3195
3196         return isl_basic_map_add_div_constraints_var(bmap, div_pos,
3197                                                         bmap->div[div]);
3198 }
3199
3200 struct isl_basic_set *isl_basic_map_underlying_set(
3201                 struct isl_basic_map *bmap)
3202 {
3203         if (!bmap)
3204                 goto error;
3205         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
3206                 return (struct isl_basic_set *)bmap;
3207         bmap = isl_basic_map_cow(bmap);
3208         if (!bmap)
3209                 goto error;
3210         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
3211         if (!bmap->dim)
3212                 goto error;
3213         bmap->extra -= bmap->n_div;
3214         bmap->n_div = 0;
3215         bmap = isl_basic_map_finalize(bmap);
3216         return (struct isl_basic_set *)bmap;
3217 error:
3218         return NULL;
3219 }
3220
3221 __isl_give isl_basic_set *isl_basic_set_underlying_set(
3222                 __isl_take isl_basic_set *bset)
3223 {
3224         return isl_basic_map_underlying_set((isl_basic_map *)bset);
3225 }
3226
3227 struct isl_basic_map *isl_basic_map_overlying_set(
3228         struct isl_basic_set *bset, struct isl_basic_map *like)
3229 {
3230         struct isl_basic_map *bmap;
3231         struct isl_ctx *ctx;
3232         unsigned total;
3233         int i;
3234
3235         if (!bset || !like)
3236                 goto error;
3237         ctx = bset->ctx;
3238         isl_assert(ctx, bset->n_div == 0, goto error);
3239         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
3240         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
3241                         goto error);
3242         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
3243                 isl_basic_map_free(like);
3244                 return (struct isl_basic_map *)bset;
3245         }
3246         bset = isl_basic_set_cow(bset);
3247         if (!bset)
3248                 goto error;
3249         total = bset->dim->n_out + bset->extra;
3250         bmap = (struct isl_basic_map *)bset;
3251         isl_dim_free(bmap->dim);
3252         bmap->dim = isl_dim_copy(like->dim);
3253         if (!bmap->dim)
3254                 goto error;
3255         bmap->n_div = like->n_div;
3256         bmap->extra += like->n_div;
3257         if (bmap->extra) {
3258                 unsigned ltotal;
3259                 ltotal = total - bmap->extra + like->extra;
3260                 if (ltotal > total)
3261                         ltotal = total;
3262                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
3263                                         bmap->extra * (1 + 1 + total));
3264                 if (isl_blk_is_error(bmap->block2))
3265                         goto error;
3266                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
3267                                                 bmap->extra);
3268                 if (!bmap->div)
3269                         goto error;
3270                 for (i = 0; i < bmap->extra; ++i)
3271                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
3272                 for (i = 0; i < like->n_div; ++i) {
3273                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
3274                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
3275                 }
3276                 bmap = isl_basic_map_extend_constraints(bmap,
3277                                                         0, 2 * like->n_div);
3278                 for (i = 0; i < like->n_div; ++i) {
3279                         if (isl_int_is_zero(bmap->div[i][0]))
3280                                 continue;
3281                         if (isl_basic_map_add_div_constraints(bmap, i) < 0)
3282                                 goto error;
3283                 }
3284         }
3285         isl_basic_map_free(like);
3286         bmap = isl_basic_map_simplify(bmap);
3287         bmap = isl_basic_map_finalize(bmap);
3288         return bmap;
3289 error:
3290         isl_basic_map_free(like);
3291         isl_basic_set_free(bset);
3292         return NULL;
3293 }
3294
3295 struct isl_basic_set *isl_basic_set_from_underlying_set(
3296         struct isl_basic_set *bset, struct isl_basic_set *like)
3297 {
3298         return (struct isl_basic_set *)
3299                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
3300 }
3301
3302 struct isl_set *isl_set_from_underlying_set(
3303         struct isl_set *set, struct isl_basic_set *like)
3304 {
3305         int i;
3306
3307         if (!set || !like)
3308                 goto error;
3309         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
3310                     goto error);
3311         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
3312                 isl_basic_set_free(like);
3313                 return set;
3314         }
3315         set = isl_set_cow(set);
3316         if (!set)
3317                 goto error;
3318         for (i = 0; i < set->n; ++i) {
3319                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
3320                                                       isl_basic_set_copy(like));
3321                 if (!set->p[i])
3322                         goto error;
3323         }
3324         isl_dim_free(set->dim);
3325         set->dim = isl_dim_copy(like->dim);
3326         if (!set->dim)
3327                 goto error;
3328         isl_basic_set_free(like);
3329         return set;
3330 error:
3331         isl_basic_set_free(like);
3332         isl_set_free(set);
3333         return NULL;
3334 }
3335
3336 struct isl_set *isl_map_underlying_set(struct isl_map *map)
3337 {
3338         int i;
3339
3340         map = isl_map_cow(map);
3341         if (!map)
3342                 return NULL;
3343         map->dim = isl_dim_cow(map->dim);
3344         if (!map->dim)
3345                 goto error;
3346
3347         for (i = 1; i < map->n; ++i)
3348                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
3349                                 goto error);
3350         for (i = 0; i < map->n; ++i) {
3351                 map->p[i] = (struct isl_basic_map *)
3352                                 isl_basic_map_underlying_set(map->p[i]);
3353                 if (!map->p[i])
3354                         goto error;
3355         }
3356         if (map->n == 0)
3357                 map->dim = isl_dim_underlying(map->dim, 0);
3358         else {
3359                 isl_dim_free(map->dim);
3360                 map->dim = isl_dim_copy(map->p[0]->dim);
3361         }
3362         if (!map->dim)
3363                 goto error;
3364         return (struct isl_set *)map;
3365 error:
3366         isl_map_free(map);
3367         return NULL;
3368 }
3369
3370 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
3371 {
3372         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
3373 }
3374
3375 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
3376 {
3377         struct isl_basic_set *domain;
3378         unsigned n_in;
3379         unsigned n_out;
3380         if (!bmap)
3381                 return NULL;
3382         n_in = isl_basic_map_n_in(bmap);
3383         n_out = isl_basic_map_n_out(bmap);
3384         domain = isl_basic_set_from_basic_map(bmap);
3385         return isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
3386 }
3387
3388 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
3389 {
3390         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
3391 }
3392
3393 struct isl_set *isl_map_range(struct isl_map *map)
3394 {
3395         int i;
3396         struct isl_set *set;
3397
3398         if (!map)
3399                 goto error;
3400         if (isl_map_dim(map, isl_dim_in) == 0)
3401                 return (isl_set *)map;
3402
3403         map = isl_map_cow(map);
3404         if (!map)
3405                 goto error;
3406
3407         set = (struct isl_set *) map;
3408         set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
3409         if (!set->dim)
3410                 goto error;
3411         for (i = 0; i < map->n; ++i) {
3412                 set->p[i] = isl_basic_map_range(map->p[i]);
3413                 if (!set->p[i])
3414                         goto error;
3415         }
3416         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3417         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3418         return set;
3419 error:
3420         isl_map_free(map);
3421         return NULL;
3422 }
3423
3424 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3425 {
3426         int i;
3427         struct isl_map *map = NULL;
3428
3429         set = isl_set_cow(set);
3430         if (!set || !dim)
3431                 goto error;
3432         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3433         map = (struct isl_map *)set;
3434         for (i = 0; i < set->n; ++i) {
3435                 map->p[i] = isl_basic_map_from_basic_set(
3436                                 set->p[i], isl_dim_copy(dim));
3437                 if (!map->p[i])
3438                         goto error;
3439         }
3440         isl_dim_free(map->dim);
3441         map->dim = dim;
3442         return map;
3443 error:
3444         isl_dim_free(dim);
3445         isl_set_free(set);
3446         return NULL;
3447 }
3448
3449 struct isl_map *isl_map_from_range(struct isl_set *set)
3450 {
3451         return (struct isl_map *)set;
3452 }
3453
3454 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
3455 {
3456         return isl_map_reverse(isl_map_from_range(set));;
3457 }
3458
3459 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
3460         __isl_take isl_set *range)
3461 {
3462         return isl_map_product(isl_map_from_domain(domain),
3463                                isl_map_from_range(range));
3464 }
3465
3466 struct isl_set *isl_set_from_map(struct isl_map *map)
3467 {
3468         int i;
3469         struct isl_set *set = NULL;
3470
3471         if (!map)
3472                 return NULL;
3473         map = isl_map_cow(map);
3474         if (!map)
3475                 return NULL;
3476         map->dim = isl_dim_cow(map->dim);
3477         if (!map->dim)
3478                 goto error;
3479         map->dim->n_out += map->dim->n_in;
3480         map->dim->n_in = 0;
3481         set = (struct isl_set *)map;
3482         for (i = 0; i < map->n; ++i) {
3483                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3484                 if (!set->p[i])
3485                         goto error;
3486         }
3487         return set;
3488 error:
3489         isl_map_free(map);
3490         return NULL;
3491 }
3492
3493 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3494 {
3495         struct isl_map *map;
3496
3497         if (!dim)
3498                 return NULL;
3499         isl_assert(dim->ctx, n >= 0, return NULL);
3500         map = isl_alloc(dim->ctx, struct isl_map,
3501                         sizeof(struct isl_map) +
3502                         (n - 1) * sizeof(struct isl_basic_map *));
3503         if (!map)
3504                 goto error;
3505
3506         map->ctx = dim->ctx;
3507         isl_ctx_ref(map->ctx);
3508         map->ref = 1;
3509         map->size = n;
3510         map->n = 0;
3511         map->dim = dim;
3512         map->flags = flags;
3513         return map;
3514 error:
3515         isl_dim_free(dim);
3516         return NULL;
3517 }
3518
3519 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3520                 unsigned nparam, unsigned in, unsigned out, int n,
3521                 unsigned flags)
3522 {
3523         struct isl_map *map;
3524         struct isl_dim *dims;
3525
3526         dims = isl_dim_alloc(ctx, nparam, in, out);
3527         if (!dims)
3528                 return NULL;
3529
3530         map = isl_map_alloc_dim(dims, n, flags);
3531         return map;
3532 }
3533
3534 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
3535 {
3536         struct isl_basic_map *bmap;
3537         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
3538         bmap = isl_basic_map_set_to_empty(bmap);
3539         return bmap;
3540 }
3541
3542 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3543 {
3544         struct isl_basic_set *bset;
3545         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3546         bset = isl_basic_set_set_to_empty(bset);
3547         return bset;
3548 }
3549
3550 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3551 {
3552         struct isl_basic_map *bmap;
3553         if (!model)
3554                 return NULL;
3555         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3556         bmap = isl_basic_map_set_to_empty(bmap);
3557         return bmap;
3558 }
3559
3560 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3561 {
3562         struct isl_basic_map *bmap;
3563         if (!model)
3564                 return NULL;
3565         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3566         bmap = isl_basic_map_set_to_empty(bmap);
3567         return bmap;
3568 }
3569
3570 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3571 {
3572         struct isl_basic_set *bset;
3573         if (!model)
3574                 return NULL;
3575         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3576         bset = isl_basic_set_set_to_empty(bset);
3577         return bset;
3578 }
3579
3580 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3581 {
3582         struct isl_basic_map *bmap;
3583         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3584         return bmap;
3585 }
3586
3587 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3588 {
3589         struct isl_basic_set *bset;
3590         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3591         return bset;
3592 }
3593
3594 __isl_give isl_basic_map *isl_basic_map_universe_like(
3595                 __isl_keep isl_basic_map *model)
3596 {
3597         if (!model)
3598                 return NULL;
3599         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3600 }
3601
3602 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3603 {
3604         if (!model)
3605                 return NULL;
3606         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3607 }
3608
3609 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3610         __isl_keep isl_set *model)
3611 {
3612         if (!model)
3613                 return NULL;
3614         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3615 }
3616
3617 struct isl_map *isl_map_empty(struct isl_dim *dim)
3618 {
3619         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3620 }
3621
3622 struct isl_map *isl_map_empty_like(struct isl_map *model)
3623 {
3624         if (!model)
3625                 return NULL;
3626         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3627 }
3628
3629 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3630 {
3631         if (!model)
3632                 return NULL;
3633         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3634 }
3635
3636 struct isl_set *isl_set_empty(struct isl_dim *dim)
3637 {
3638         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3639 }
3640
3641 struct isl_set *isl_set_empty_like(struct isl_set *model)
3642 {
3643         if (!model)
3644                 return NULL;
3645         return isl_set_empty(isl_dim_copy(model->dim));
3646 }
3647
3648 struct isl_map *isl_map_universe(struct isl_dim *dim)
3649 {
3650         struct isl_map *map;
3651         if (!dim)
3652                 return NULL;
3653         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3654         map = isl_map_add_basic_map(map, isl_basic_map_universe(dim));
3655         return map;
3656 }
3657
3658 struct isl_set *isl_set_universe(struct isl_dim *dim)
3659 {
3660         struct isl_set *set;
3661         if (!dim)
3662                 return NULL;
3663         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3664         set = isl_set_add_basic_set(set, isl_basic_set_universe(dim));
3665         return set;
3666 }
3667
3668 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3669 {
3670         if (!model)
3671                 return NULL;
3672         return isl_set_universe(isl_dim_copy(model->dim));
3673 }
3674
3675 struct isl_map *isl_map_dup(struct isl_map *map)
3676 {
3677         int i;
3678         struct isl_map *dup;
3679
3680         if (!map)
3681                 return NULL;
3682         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3683         for (i = 0; i < map->n; ++i)
3684                 dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i]));
3685         return dup;
3686 }
3687
3688 __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
3689                                                 __isl_take isl_basic_map *bmap)
3690 {
3691         if (!bmap || !map)
3692                 goto error;
3693         if (isl_basic_map_fast_is_empty(bmap)) {
3694                 isl_basic_map_free(bmap);
3695                 return map;
3696         }
3697         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3698         isl_assert(map->ctx, map->n < map->size, goto error);
3699         map->p[map->n] = bmap;
3700         map->n++;
3701         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3702         return map;
3703 error:
3704         if (map)
3705                 isl_map_free(map);
3706         if (bmap)
3707                 isl_basic_map_free(bmap);
3708         return NULL;
3709 }
3710
3711 void isl_map_free(struct isl_map *map)
3712 {
3713         int i;
3714
3715         if (!map)
3716                 return;
3717
3718         if (--map->ref > 0)
3719                 return;
3720
3721         isl_ctx_deref(map->ctx);
3722         for (i = 0; i < map->n; ++i)
3723                 isl_basic_map_free(map->p[i]);
3724         isl_dim_free(map->dim);
3725         free(map);
3726 }
3727
3728 struct isl_map *isl_map_extend(struct isl_map *base,
3729                 unsigned nparam, unsigned n_in, unsigned n_out)
3730 {
3731         int i;
3732
3733         base = isl_map_cow(base);
3734         if (!base)
3735                 return NULL;
3736
3737         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3738         if (!base->dim)
3739                 goto error;
3740         for (i = 0; i < base->n; ++i) {
3741                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3742                                 isl_dim_copy(base->dim), 0, 0, 0);
3743                 if (!base->p[i])
3744                         goto error;
3745         }
3746         return base;
3747 error:
3748         isl_map_free(base);
3749         return NULL;
3750 }
3751
3752 struct isl_set *isl_set_extend(struct isl_set *base,
3753                 unsigned nparam, unsigned dim)
3754 {
3755         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3756                                                         nparam, 0, dim);
3757 }
3758
3759 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3760         struct isl_basic_map *bmap, unsigned pos, int value)
3761 {
3762         int j;
3763
3764         bmap = isl_basic_map_cow(bmap);
3765         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3766         j = isl_basic_map_alloc_equality(bmap);
3767         if (j < 0)
3768                 goto error;
3769         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3770         isl_int_set_si(bmap->eq[j][pos], -1);
3771         isl_int_set_si(bmap->eq[j][0], value);
3772         bmap = isl_basic_map_simplify(bmap);
3773         return isl_basic_map_finalize(bmap);
3774 error:
3775         isl_basic_map_free(bmap);
3776         return NULL;
3777 }
3778
3779 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3780         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3781 {
3782         int j;
3783
3784         bmap = isl_basic_map_cow(bmap);
3785         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3786         j = isl_basic_map_alloc_equality(bmap);
3787         if (j < 0)
3788                 goto error;
3789         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3790         isl_int_set_si(bmap->eq[j][pos], -1);
3791         isl_int_set(bmap->eq[j][0], value);
3792         bmap = isl_basic_map_simplify(bmap);
3793         return isl_basic_map_finalize(bmap);
3794 error:
3795         isl_basic_map_free(bmap);
3796         return NULL;
3797 }
3798
3799 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3800                 enum isl_dim_type type, unsigned pos, int value)
3801 {
3802         if (!bmap)
3803                 return NULL;
3804         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3805         return isl_basic_map_fix_pos_si(bmap,
3806                 isl_basic_map_offset(bmap, type) + pos, value);
3807 error:
3808         isl_basic_map_free(bmap);
3809         return NULL;
3810 }
3811
3812 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3813                 enum isl_dim_type type, unsigned pos, isl_int value)
3814 {
3815         if (!bmap)
3816                 return NULL;
3817         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3818         return isl_basic_map_fix_pos(bmap,
3819                 isl_basic_map_offset(bmap, type) + pos, value);
3820 error:
3821         isl_basic_map_free(bmap);
3822         return NULL;
3823 }
3824
3825 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3826                 enum isl_dim_type type, unsigned pos, int value)
3827 {
3828         return (struct isl_basic_set *)
3829                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3830                                         type, pos, value);
3831 }
3832
3833 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3834                 enum isl_dim_type type, unsigned pos, isl_int value)
3835 {
3836         return (struct isl_basic_set *)
3837                 isl_basic_map_fix((struct isl_basic_map *)bset,
3838                                         type, pos, value);
3839 }
3840
3841 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3842                 unsigned input, int value)
3843 {
3844         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3845 }
3846
3847 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3848                 unsigned dim, int value)
3849 {
3850         return (struct isl_basic_set *)
3851                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3852                                         isl_dim_set, dim, value);
3853 }
3854
3855 struct isl_map *isl_map_fix_si(struct isl_map *map,
3856                 enum isl_dim_type type, unsigned pos, int value)
3857 {
3858         int i;
3859
3860         map = isl_map_cow(map);
3861         if (!map)
3862                 return NULL;
3863
3864         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3865         for (i = 0; i < map->n; ++i) {
3866                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
3867                 if (!map->p[i])
3868                         goto error;
3869         }
3870         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3871         return map;
3872 error:
3873         isl_map_free(map);
3874         return NULL;
3875 }
3876
3877 __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
3878                 enum isl_dim_type type, unsigned pos, int value)
3879 {
3880         return (struct isl_set *)
3881                 isl_map_fix_si((struct isl_map *)set, type, pos, value);
3882 }
3883
3884 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
3885                 enum isl_dim_type type, unsigned pos, isl_int value)
3886 {
3887         int i;
3888
3889         map = isl_map_cow(map);
3890         if (!map)
3891                 return NULL;
3892
3893         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3894         for (i = 0; i < map->n; ++i) {
3895                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
3896                 if (!map->p[i])
3897                         goto error;
3898         }
3899         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3900         return map;
3901 error:
3902         isl_map_free(map);
3903         return NULL;
3904 }
3905
3906 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
3907                 enum isl_dim_type type, unsigned pos, isl_int value)
3908 {
3909         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
3910 }
3911
3912 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3913                 unsigned input, int value)
3914 {
3915         return isl_map_fix_si(map, isl_dim_in, input, value);
3916 }
3917
3918 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3919 {
3920         return (struct isl_set *)
3921                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
3922 }
3923
3924 __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
3925                 __isl_take isl_basic_map *bmap,
3926                 enum isl_dim_type type, unsigned pos, int value)
3927 {
3928         int j;
3929
3930         if (!bmap)
3931                 return NULL;
3932         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3933         pos += isl_basic_map_offset(bmap, type);
3934         bmap = isl_basic_map_cow(bmap);
3935         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
3936         j = isl_basic_map_alloc_inequality(bmap);
3937         if (j < 0)
3938                 goto error;
3939         isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
3940         isl_int_set_si(bmap->ineq[j][pos], 1);
3941         isl_int_set_si(bmap->ineq[j][0], -value);
3942         bmap = isl_basic_map_simplify(bmap);
3943         return isl_basic_map_finalize(bmap);
3944 error:
3945         isl_basic_map_free(bmap);
3946         return NULL;
3947 }
3948
3949 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3950         unsigned dim, isl_int value)
3951 {
3952         int j;
3953
3954         bset = isl_basic_set_cow(bset);
3955         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3956         j = isl_basic_set_alloc_inequality(bset);
3957         if (j < 0)
3958                 goto error;
3959         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3960         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3961         isl_int_neg(bset->ineq[j][0], value);
3962         bset = isl_basic_set_simplify(bset);
3963         return isl_basic_set_finalize(bset);
3964 error:
3965         isl_basic_set_free(bset);
3966         return NULL;
3967 }
3968
3969 __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
3970                 enum isl_dim_type type, unsigned pos, int value)
3971 {
3972         int i;
3973
3974         map = isl_map_cow(map);
3975         if (!map)
3976                 return NULL;
3977
3978         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3979         for (i = 0; i < map->n; ++i) {
3980                 map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
3981                                                          type, pos, value);
3982                 if (!map->p[i])
3983                         goto error;
3984         }
3985         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3986         return map;
3987 error:
3988         isl_map_free(map);
3989         return NULL;
3990 }
3991
3992 __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
3993                 enum isl_dim_type type, unsigned pos, int value)
3994 {
3995         return (struct isl_set *)
3996                 isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
3997 }
3998
3999 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
4000                                         isl_int value)
4001 {
4002         int i;
4003
4004         set = isl_set_cow(set);
4005         if (!set)
4006                 return NULL;
4007
4008         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
4009         for (i = 0; i < set->n; ++i) {
4010                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
4011                 if (!set->p[i])
4012                         goto error;
4013         }
4014         return set;
4015 error:
4016         isl_set_free(set);
4017         return NULL;
4018 }
4019
4020 struct isl_map *isl_map_reverse(struct isl_map *map)
4021 {
4022         int i;
4023
4024         map = isl_map_cow(map);
4025         if (!map)
4026                 return NULL;
4027
4028         map->dim = isl_dim_reverse(map->dim);
4029         if (!map->dim)
4030                 goto error;
4031         for (i = 0; i < map->n; ++i) {
4032                 map->p[i] = isl_basic_map_reverse(map->p[i]);
4033                 if (!map->p[i])
4034                         goto error;
4035         }
4036         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4037         return map;
4038 error:
4039         isl_map_free(map);
4040         return NULL;
4041 }
4042
4043 static struct isl_map *isl_basic_map_partial_lexopt(
4044                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4045                 struct isl_set **empty, int max)
4046 {
4047         if (!bmap)
4048                 goto error;
4049         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
4050                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
4051         else
4052                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
4053 error:
4054         isl_basic_map_free(bmap);
4055         isl_basic_set_free(dom);
4056         if (empty)
4057                 *empty = NULL;
4058         return NULL;
4059 }
4060
4061 struct isl_map *isl_basic_map_partial_lexmax(
4062                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4063                 struct isl_set **empty)
4064 {
4065         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
4066 }
4067
4068 struct isl_map *isl_basic_map_partial_lexmin(
4069                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4070                 struct isl_set **empty)
4071 {
4072         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
4073 }
4074
4075 struct isl_set *isl_basic_set_partial_lexmin(
4076                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4077                 struct isl_set **empty)
4078 {
4079         return (struct isl_set *)
4080                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
4081                         dom, empty);
4082 }
4083
4084 struct isl_set *isl_basic_set_partial_lexmax(
4085                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4086                 struct isl_set **empty)
4087 {
4088         return (struct isl_set *)
4089                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
4090                         dom, empty);
4091 }
4092
4093 /* Given a basic map "bmap", compute the lexicograhically minimal
4094  * (or maximal) image element for each domain element in dom.
4095  * Set *empty to those elements in dom that do not have an image element.
4096  *
4097  * We first make sure the basic sets in dom are disjoint and then
4098  * simply collect the results over each of the basic sets separately.
4099  * We could probably improve the efficiency a bit by moving the union
4100  * domain down into the parametric integer programming.
4101  */
4102 static __isl_give isl_map *basic_map_partial_lexopt(
4103                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
4104                 __isl_give isl_set **empty, int max)
4105 {
4106         int i;
4107         struct isl_map *res;
4108
4109         dom = isl_set_make_disjoint(dom);
4110         if (!dom)
4111                 goto error;
4112
4113         if (isl_set_fast_is_empty(dom)) {
4114                 res = isl_map_empty_like_basic_map(bmap);
4115                 *empty = isl_set_empty_like(dom);
4116                 isl_set_free(dom);
4117                 isl_basic_map_free(bmap);
4118                 return res;
4119         }
4120
4121         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4122                         isl_basic_set_copy(dom->p[0]), empty, max);
4123
4124         for (i = 1; i < dom->n; ++i) {
4125                 struct isl_map *res_i;
4126                 struct isl_set *empty_i;
4127
4128                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4129                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
4130
4131                 res = isl_map_union_disjoint(res, res_i);
4132                 *empty = isl_set_union_disjoint(*empty, empty_i);
4133         }
4134
4135         isl_set_free(dom);
4136         isl_basic_map_free(bmap);
4137         return res;
4138 error:
4139         *empty = NULL;
4140         isl_set_free(dom);
4141         isl_basic_map_free(bmap);
4142         return NULL;
4143 }
4144
4145 /* Given a map "map", compute the lexicograhically minimal
4146  * (or maximal) image element for each domain element in dom.
4147  * Set *empty to those elements in dom that do not have an image element.
4148  *
4149  * We first compute the lexicographically minimal or maximal element
4150  * in the first basic map.  This results in a partial solution "res"
4151  * and a subset "todo" of dom that still need to be handled.
4152  * We then consider each of the remaining maps in "map" and successively
4153  * improve both "res" and "todo".
4154  *
4155  * Let res^k and todo^k be the results after k steps and let i = k + 1.
4156  * Assume we are computing the lexicographical maximum.
4157  * We first intersect basic map i with a relation that maps elements
4158  * to elements that are lexicographically larger than the image elements
4159  * in res^k and the compute the maximum image element of this intersection.
4160  * The result ("better") corresponds to those image elements in basic map i
4161  * that are better than what we had before.  The remainder ("keep") are the
4162  * domain elements for which the image element in res_k was better.
4163  * We also compute the lexicographical maximum of basic map i in todo^k.
4164  * res^i is the result of the operation + better + those elements in
4165  *              res^k that we should keep
4166  * todo^i is the remainder of the maximum operation on todo^k.
4167  */
4168 static __isl_give isl_map *isl_map_partial_lexopt(
4169                 __isl_take isl_map *map, __isl_take isl_set *dom,
4170                 __isl_give isl_set **empty, int max)
4171 {
4172         int i;
4173         struct isl_map *res;
4174         struct isl_set *todo;
4175
4176         if (!map || !dom)
4177                 goto error;
4178
4179         if (isl_map_fast_is_empty(map)) {
4180                 if (empty)
4181                         *empty = dom;
4182                 else
4183                         isl_set_free(dom);
4184                 return map;
4185         }
4186
4187         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
4188                                         isl_set_copy(dom), &todo, max);
4189
4190         for (i = 1; i < map->n; ++i) {
4191                 struct isl_map *lt;
4192                 struct isl_map *better;
4193                 struct isl_set *keep;
4194                 struct isl_map *res_i;
4195                 struct isl_set *todo_i;
4196                 struct isl_dim *dim = isl_map_get_dim(res);
4197
4198                 dim = isl_dim_range(dim);
4199                 if (max)
4200                         lt = isl_map_lex_lt(dim);
4201                 else
4202                         lt = isl_map_lex_gt(dim);
4203                 lt = isl_map_apply_range(isl_map_copy(res), lt);
4204                 lt = isl_map_intersect(lt,
4205                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
4206                 better = isl_map_partial_lexopt(lt,
4207                         isl_map_domain(isl_map_copy(res)),
4208                         &keep, max);
4209
4210                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
4211                                                 todo, &todo_i, max);
4212
4213                 res = isl_map_intersect_domain(res, keep);
4214                 res = isl_map_union_disjoint(res, res_i);
4215                 res = isl_map_union_disjoint(res, better);
4216                 todo = todo_i;
4217         }
4218
4219         isl_set_free(dom);
4220         isl_map_free(map);
4221
4222         if (empty)
4223                 *empty = todo;
4224         else
4225                 isl_set_free(todo);
4226
4227         return res;
4228 error:
4229         if (empty)
4230                 *empty = NULL;
4231         isl_set_free(dom);
4232         isl_map_free(map);
4233         return NULL;
4234 }
4235
4236 __isl_give isl_map *isl_map_partial_lexmax(
4237                 __isl_take isl_map *map, __isl_take isl_set *dom,
4238                 __isl_give isl_set **empty)
4239 {
4240         return isl_map_partial_lexopt(map, dom, empty, 1);
4241 }
4242
4243 __isl_give isl_map *isl_map_partial_lexmin(
4244                 __isl_take isl_map *map, __isl_take isl_set *dom,
4245                 __isl_give isl_set **empty)
4246 {
4247         return isl_map_partial_lexopt(map, dom, empty, 0);
4248 }
4249
4250 __isl_give isl_set *isl_set_partial_lexmin(
4251                 __isl_take isl_set *set, __isl_take isl_set *dom,
4252                 __isl_give isl_set **empty)
4253 {
4254         return (struct isl_set *)
4255                 isl_map_partial_lexmin((struct isl_map *)set,
4256                         dom, empty);
4257 }
4258
4259 __isl_give isl_set *isl_set_partial_lexmax(
4260                 __isl_take isl_set *set, __isl_take isl_set *dom,
4261                 __isl_give isl_set **empty)
4262 {
4263         return (struct isl_set *)
4264                 isl_map_partial_lexmax((struct isl_map *)set,
4265                         dom, empty);
4266 }
4267
4268 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
4269 {
4270         struct isl_basic_set *dom = NULL;
4271         struct isl_dim *dom_dim;
4272
4273         if (!bmap)
4274                 goto error;
4275         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
4276         dom = isl_basic_set_universe(dom_dim);
4277         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
4278 error:
4279         isl_basic_map_free(bmap);
4280         return NULL;
4281 }
4282
4283 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
4284 {
4285         return isl_basic_map_lexopt(bmap, 0);
4286 }
4287
4288 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
4289 {
4290         return isl_basic_map_lexopt(bmap, 1);
4291 }
4292
4293 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
4294 {
4295         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
4296 }
4297
4298 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
4299 {
4300         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
4301 }
4302
4303 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
4304 {
4305         struct isl_set *dom = NULL;
4306         struct isl_dim *dom_dim;
4307
4308         if (!map)
4309                 goto error;
4310         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
4311         dom = isl_set_universe(dom_dim);
4312         return isl_map_partial_lexopt(map, dom, NULL, max);
4313 error:
4314         isl_map_free(map);
4315         return NULL;
4316 }
4317
4318 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
4319 {
4320         return isl_map_lexopt(map, 0);
4321 }
4322
4323 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
4324 {
4325         return isl_map_lexopt(map, 1);
4326 }
4327
4328 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
4329 {
4330         return (isl_set *)isl_map_lexmin((isl_map *)set);
4331 }
4332
4333 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
4334 {
4335         return (isl_set *)isl_map_lexmax((isl_map *)set);
4336 }
4337
4338 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
4339         struct isl_dim *dim)
4340 {
4341         int i;
4342
4343         if (!map || !dim)
4344                 goto error;
4345
4346         for (i = 0; i < map->n; ++i) {
4347                 isl_dim_free(map->p[i]->dim);
4348                 map->p[i]->dim = isl_dim_copy(dim);
4349         }
4350         isl_dim_free(map->dim);
4351         map->dim = dim;
4352
4353         return map;
4354 error:
4355         isl_map_free(map);
4356         isl_dim_free(dim);
4357         return NULL;
4358 }
4359
4360 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
4361         struct isl_dim *dim)
4362 {
4363         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
4364 }
4365
4366 /* Apply a preimage specified by "mat" on the parameters of "bset".
4367  * bset is assumed to have only parameters and divs.
4368  */
4369 static struct isl_basic_set *basic_set_parameter_preimage(
4370         struct isl_basic_set *bset, struct isl_mat *mat)
4371 {
4372         unsigned nparam;
4373
4374         if (!bset || !mat)
4375                 goto error;
4376
4377         bset->dim = isl_dim_cow(bset->dim);
4378         if (!bset->dim)
4379                 goto error;
4380
4381         nparam = isl_basic_set_dim(bset, isl_dim_param);
4382
4383         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
4384
4385         bset->dim->nparam = 0;
4386         bset->dim->n_out = nparam;
4387         bset = isl_basic_set_preimage(bset, mat);
4388         if (bset) {
4389                 bset->dim->nparam = bset->dim->n_out;
4390                 bset->dim->n_out = 0;
4391         }
4392         return bset;
4393 error:
4394         isl_mat_free(mat);
4395         isl_basic_set_free(bset);
4396         return NULL;
4397 }
4398
4399 /* Apply a preimage specified by "mat" on the parameters of "set".
4400  * set is assumed to have only parameters and divs.
4401  */
4402 static struct isl_set *set_parameter_preimage(
4403         struct isl_set *set, struct isl_mat *mat)
4404 {
4405         struct isl_dim *dim = NULL;
4406         unsigned nparam;
4407
4408         if (!set || !mat)
4409                 goto error;
4410
4411         dim = isl_dim_copy(set->dim);
4412         dim = isl_dim_cow(dim);
4413         if (!dim)
4414                 goto error;
4415
4416         nparam = isl_set_dim(set, isl_dim_param);
4417
4418         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
4419
4420         dim->nparam = 0;
4421         dim->n_out = nparam;
4422         isl_set_reset_dim(set, dim);
4423         set = isl_set_preimage(set, mat);
4424         if (!set)
4425                 goto error2;
4426         dim = isl_dim_copy(set->dim);
4427         dim = isl_dim_cow(dim);
4428         if (!dim)
4429                 goto error2;
4430         dim->nparam = dim->n_out;
4431         dim->n_out = 0;
4432         isl_set_reset_dim(set, dim);
4433         return set;
4434 error:
4435         isl_dim_free(dim);
4436         isl_mat_free(mat);
4437 error2:
4438         isl_set_free(set);
4439         return NULL;
4440 }
4441
4442 /* Intersect the basic set "bset" with the affine space specified by the
4443  * equalities in "eq".
4444  */
4445 static struct isl_basic_set *basic_set_append_equalities(
4446         struct isl_basic_set *bset, struct isl_mat *eq)
4447 {
4448         int i, k;
4449         unsigned len;
4450
4451         if (!bset || !eq)
4452                 goto error;
4453
4454         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
4455                                         eq->n_row, 0);
4456         if (!bset)
4457                 goto error;
4458
4459         len = 1 + isl_dim_total(bset->dim) + bset->extra;
4460         for (i = 0; i < eq->n_row; ++i) {
4461                 k = isl_basic_set_alloc_equality(bset);
4462                 if (k < 0)
4463                         goto error;
4464                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
4465                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
4466         }
4467         isl_mat_free(eq);
4468
4469         bset = isl_basic_set_gauss(bset, NULL);
4470         bset = isl_basic_set_finalize(bset);
4471
4472         return bset;
4473 error:
4474         isl_mat_free(eq);
4475         isl_basic_set_free(bset);
4476         return NULL;
4477 }
4478
4479 /* Intersect the set "set" with the affine space specified by the
4480  * equalities in "eq".
4481  */
4482 static struct isl_set *set_append_equalities(struct isl_set *set,
4483         struct isl_mat *eq)
4484 {
4485         int i;
4486
4487         if (!set || !eq)
4488                 goto error;
4489
4490         for (i = 0; i < set->n; ++i) {
4491                 set->p[i] = basic_set_append_equalities(set->p[i],
4492                                         isl_mat_copy(eq));
4493                 if (!set->p[i])
4494                         goto error;
4495         }
4496         isl_mat_free(eq);
4497         return set;
4498 error:
4499         isl_mat_free(eq);
4500         isl_set_free(set);
4501         return NULL;
4502 }
4503
4504 /* Project the given basic set onto its parameter domain, possibly introducing
4505  * new, explicit, existential variables in the constraints.
4506  * The input has parameters and (possibly implicit) existential variables.
4507  * The output has the same parameters, but only
4508  * explicit existentially quantified variables.
4509  *
4510  * The actual projection is performed by pip, but pip doesn't seem
4511  * to like equalities very much, so we first remove the equalities
4512  * among the parameters by performing a variable compression on
4513  * the parameters.  Afterward, an inverse transformation is performed
4514  * and the equalities among the parameters are inserted back in.
4515  */
4516 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
4517 {
4518         int i, j;
4519         struct isl_mat *eq;
4520         struct isl_mat *T, *T2;
4521         struct isl_set *set;
4522         unsigned nparam, n_div;
4523
4524         bset = isl_basic_set_cow(bset);
4525         if (!bset)
4526                 return NULL;
4527
4528         if (bset->n_eq == 0)
4529                 return isl_basic_set_lexmin(bset);
4530
4531         isl_basic_set_gauss(bset, NULL);
4532
4533         nparam = isl_basic_set_dim(bset, isl_dim_param);
4534         n_div = isl_basic_set_dim(bset, isl_dim_div);
4535
4536         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
4537                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
4538                         ++i;
4539         }
4540         if (i == bset->n_eq)
4541                 return isl_basic_set_lexmin(bset);
4542
4543         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
4544                 0, 1 + nparam);
4545         eq = isl_mat_cow(eq);
4546         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
4547         if (T && T->n_col == 0) {
4548                 isl_mat_free(T);
4549                 isl_mat_free(T2);
4550                 isl_mat_free(eq);
4551                 bset = isl_basic_set_set_to_empty(bset);
4552                 return isl_set_from_basic_set(bset);
4553         }
4554         bset = basic_set_parameter_preimage(bset, T);
4555
4556         set = isl_basic_set_lexmin(bset);
4557         set = set_parameter_preimage(set, T2);
4558         set = set_append_equalities(set, eq);
4559         return set;
4560 }
4561
4562 /* Compute an explicit representation for all the existentially
4563  * quantified variables.
4564  * The input and output dimensions are first turned into parameters.
4565  * compute_divs then returns a map with the same parameters and
4566  * no input or output dimensions and the dimension specification
4567  * is reset to that of the input.
4568  */
4569 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
4570 {
4571         struct isl_basic_set *bset;
4572         struct isl_set *set;
4573         struct isl_map *map;
4574         struct isl_dim *dim, *orig_dim = NULL;
4575         unsigned         nparam;
4576         unsigned         n_in;
4577         unsigned         n_out;
4578
4579         bmap = isl_basic_map_cow(bmap);
4580         if (!bmap)
4581                 return NULL;
4582
4583         nparam = isl_basic_map_dim(bmap, isl_dim_param);
4584         n_in = isl_basic_map_dim(bmap, isl_dim_in);
4585         n_out = isl_basic_map_dim(bmap, isl_dim_out);
4586         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
4587         if (!dim)
4588                 goto error;
4589
4590         orig_dim = bmap->dim;
4591         bmap->dim = dim;
4592         bset = (struct isl_basic_set *)bmap;
4593
4594         set = parameter_compute_divs(bset);
4595         map = (struct isl_map *)set;
4596         map = isl_map_reset_dim(map, orig_dim);
4597
4598         return map;
4599 error:
4600         isl_basic_map_free(bmap);
4601         return NULL;
4602 }
4603
4604 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
4605 {
4606         int i;
4607         unsigned off;
4608
4609         if (!bmap)
4610                 return -1;
4611
4612         off = isl_dim_total(bmap->dim);
4613         for (i = 0; i < bmap->n_div; ++i) {
4614                 if (isl_int_is_zero(bmap->div[i][0]))
4615                         return 0;
4616                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
4617                                 return -1);
4618         }
4619         return 1;
4620 }
4621
4622 static int map_divs_known(__isl_keep isl_map *map)
4623 {
4624         int i;
4625
4626         if (!map)
4627                 return -1;
4628
4629         for (i = 0; i < map->n; ++i) {
4630                 int known = basic_map_divs_known(map->p[i]);
4631                 if (known <= 0)
4632                         return known;
4633         }
4634
4635         return 1;
4636 }
4637
4638 /* If bmap contains any unknown divs, then compute explicit
4639  * expressions for them.  However, this computation may be
4640  * quite expensive, so first try to remove divs that aren't
4641  * strictly needed.
4642  */
4643 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
4644 {
4645         int i;
4646         int known;
4647         struct isl_map *map;
4648
4649         known = basic_map_divs_known(bmap);
4650         if (known < 0)
4651                 goto error;
4652         if (known)
4653                 return isl_map_from_basic_map(bmap);
4654
4655         bmap = isl_basic_map_drop_redundant_divs(bmap);
4656
4657         known = basic_map_divs_known(bmap);
4658         if (known < 0)
4659                 goto error;
4660         if (known)
4661                 return isl_map_from_basic_map(bmap);
4662
4663         map = compute_divs(bmap);
4664         return map;
4665 error:
4666         isl_basic_map_free(bmap);
4667         return NULL;
4668 }
4669
4670 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4671 {
4672         int i;
4673         int known;
4674         struct isl_map *res;
4675
4676         if (!map)
4677                 return NULL;
4678         if (map->n == 0)
4679                 return map;
4680
4681         known = map_divs_known(map);
4682         if (known < 0) {
4683                 isl_map_free(map);
4684                 return NULL;
4685         }
4686         if (known)
4687                 return map;
4688
4689         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4690         for (i = 1 ; i < map->n; ++i) {
4691                 struct isl_map *r2;
4692                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4693                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4694                         res = isl_map_union_disjoint(res, r2);
4695                 else
4696                         res = isl_map_union(res, r2);
4697         }
4698         isl_map_free(map);
4699
4700         return res;
4701 }
4702
4703 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4704 {
4705         return (struct isl_set *)
4706                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4707 }
4708
4709 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4710 {
4711         return (struct isl_set *)
4712                 isl_map_compute_divs((struct isl_map *)set);
4713 }
4714
4715 struct isl_set *isl_map_domain(struct isl_map *map)
4716 {
4717         int i;
4718         struct isl_set *set;
4719
4720         if (!map)
4721                 goto error;
4722
4723         map = isl_map_cow(map);
4724         if (!map)
4725                 return NULL;
4726
4727         set = (struct isl_set *)map;
4728         set->dim = isl_dim_domain(set->dim);
4729         if (!set->dim)
4730                 goto error;
4731         for (i = 0; i < map->n; ++i) {
4732                 set->p[i] = isl_basic_map_domain(map->p[i]);
4733                 if (!set->p[i])
4734                         goto error;
4735         }
4736         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4737         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4738         return set;
4739 error:
4740         isl_map_free(map);
4741         return NULL;
4742 }
4743
4744 struct isl_map *isl_map_union_disjoint(
4745                         struct isl_map *map1, struct isl_map *map2)
4746 {
4747         int i;
4748         unsigned flags = 0;
4749         struct isl_map *map = NULL;
4750
4751         if (!map1 || !map2)
4752                 goto error;
4753
4754         if (map1->n == 0) {
4755                 isl_map_free(map1);
4756                 return map2;
4757         }
4758         if (map2->n == 0) {
4759                 isl_map_free(map2);
4760                 return map1;
4761         }
4762
4763         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4764
4765         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4766             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4767                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4768
4769         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4770                                 map1->n + map2->n, flags);
4771         if (!map)
4772                 goto error;
4773         for (i = 0; i < map1->n; ++i) {
4774                 map = isl_map_add_basic_map(map,
4775                                   isl_basic_map_copy(map1->p[i]));
4776                 if (!map)
4777                         goto error;
4778         }
4779         for (i = 0; i < map2->n; ++i) {
4780                 map = isl_map_add_basic_map(map,
4781                                   isl_basic_map_copy(map2->p[i]));
4782                 if (!map)
4783                         goto error;
4784         }
4785         isl_map_free(map1);
4786         isl_map_free(map2);
4787         return map;
4788 error:
4789         isl_map_free(map);
4790         isl_map_free(map1);
4791         isl_map_free(map2);
4792         return NULL;
4793 }
4794
4795 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4796 {
4797         map1 = isl_map_union_disjoint(map1, map2);
4798         if (!map1)
4799                 return NULL;
4800         if (map1->n > 1)
4801                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4802         return map1;
4803 }
4804
4805 struct isl_set *isl_set_union_disjoint(
4806                         struct isl_set *set1, struct isl_set *set2)
4807 {
4808         return (struct isl_set *)
4809                 isl_map_union_disjoint(
4810                         (struct isl_map *)set1, (struct isl_map *)set2);
4811 }
4812
4813 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4814 {
4815         return (struct isl_set *)
4816                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4817 }
4818
4819 struct isl_map *isl_map_intersect_range(
4820                 struct isl_map *map, struct isl_set *set)
4821 {
4822         unsigned flags = 0;
4823         struct isl_map *result;
4824         int i, j;
4825
4826         if (!map || !set)
4827                 goto error;
4828
4829         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4830             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4831                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4832
4833         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4834                                         map->n * set->n, flags);
4835         if (!result)
4836                 goto error;
4837         for (i = 0; i < map->n; ++i)
4838                 for (j = 0; j < set->n; ++j) {
4839                         result = isl_map_add_basic_map(result,
4840                             isl_basic_map_intersect_range(
4841                                 isl_basic_map_copy(map->p[i]),
4842                                 isl_basic_set_copy(set->p[j])));
4843                         if (!result)
4844                                 goto error;
4845                 }
4846         isl_map_free(map);
4847         isl_set_free(set);
4848         return result;
4849 error:
4850         isl_map_free(map);
4851         isl_set_free(set);
4852         return NULL;
4853 }
4854
4855 struct isl_map *isl_map_intersect_domain(
4856                 struct isl_map *map, struct isl_set *set)
4857 {
4858         return isl_map_reverse(
4859                 isl_map_intersect_range(isl_map_reverse(map), set));
4860 }
4861
4862 struct isl_map *isl_map_apply_domain(
4863                 struct isl_map *map1, struct isl_map *map2)
4864 {
4865         if (!map1 || !map2)
4866                 goto error;
4867         map1 = isl_map_reverse(map1);
4868         map1 = isl_map_apply_range(map1, map2);
4869         return isl_map_reverse(map1);
4870 error:
4871         isl_map_free(map1);
4872         isl_map_free(map2);
4873         return NULL;
4874 }
4875
4876 struct isl_map *isl_map_apply_range(
4877                 struct isl_map *map1, struct isl_map *map2)
4878 {
4879         struct isl_dim *dim_result;
4880         struct isl_map *result;
4881         int i, j;
4882
4883         if (!map1 || !map2)
4884                 goto error;
4885
4886         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4887                                   isl_dim_copy(map2->dim));
4888
4889         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4890         if (!result)
4891                 goto error;
4892         for (i = 0; i < map1->n; ++i)
4893                 for (j = 0; j < map2->n; ++j) {
4894                         result = isl_map_add_basic_map(result,
4895                             isl_basic_map_apply_range(
4896                                 isl_basic_map_copy(map1->p[i]),
4897                                 isl_basic_map_copy(map2->p[j])));
4898                         if (!result)
4899                                 goto error;
4900                 }
4901         isl_map_free(map1);
4902         isl_map_free(map2);
4903         if (result && result->n <= 1)
4904                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4905         return result;
4906 error:
4907         isl_map_free(map1);
4908         isl_map_free(map2);
4909         return NULL;
4910 }
4911
4912 /*
4913  * returns range - domain
4914  */
4915 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4916 {
4917         isl_dim *dims;
4918         struct isl_basic_set *bset;
4919         unsigned dim;
4920         unsigned nparam;
4921         int i;
4922
4923         if (!bmap)
4924                 goto error;
4925         dim = isl_basic_map_n_in(bmap);
4926         nparam = isl_basic_map_n_param(bmap);
4927         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4928         bset = isl_basic_set_from_basic_map(bmap);
4929         bset = isl_basic_set_cow(bset);
4930         dims = isl_basic_set_get_dim(bset);
4931         dims = isl_dim_add(dims, isl_dim_set, dim);
4932         bset = isl_basic_set_extend_dim(bset, dims, 0, dim, 0);
4933         bset = isl_basic_set_swap_vars(bset, 2*dim);
4934         for (i = 0; i < dim; ++i) {
4935                 int j = isl_basic_map_alloc_equality(
4936                                             (struct isl_basic_map *)bset);
4937                 if (j < 0)
4938                         goto error;
4939                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4940                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4941                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4942                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4943         }
4944         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4945 error:
4946         isl_basic_map_free(bmap);
4947         return NULL;
4948 }
4949
4950 /*
4951  * returns range - domain
4952  */
4953 struct isl_set *isl_map_deltas(struct isl_map *map)
4954 {
4955         int i;
4956         isl_dim *dim;
4957         struct isl_set *result;
4958
4959         if (!map)
4960                 return NULL;
4961
4962         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4963         dim = isl_map_get_dim(map);
4964         dim = isl_dim_domain(dim);
4965         result = isl_set_alloc_dim(dim, map->n, map->flags);
4966         if (!result)
4967                 goto error;
4968         for (i = 0; i < map->n; ++i)
4969                 result = isl_set_add_basic_set(result,
4970                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4971         isl_map_free(map);
4972         return result;
4973 error:
4974         isl_map_free(map);
4975         return NULL;
4976 }
4977
4978 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4979 {
4980         struct isl_basic_map *bmap;
4981         unsigned nparam;
4982         unsigned dim;
4983         int i;
4984
4985         if (!dims)
4986                 return NULL;
4987
4988         nparam = dims->nparam;
4989         dim = dims->n_out;
4990         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4991         if (!bmap)
4992                 goto error;
4993
4994         for (i = 0; i < dim; ++i) {
4995                 int j = isl_basic_map_alloc_equality(bmap);
4996                 if (j < 0)
4997                         goto error;
4998                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4999                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
5000                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
5001         }
5002         return isl_basic_map_finalize(bmap);
5003 error:
5004         isl_basic_map_free(bmap);
5005         return NULL;
5006 }
5007
5008 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
5009 {
5010         struct isl_dim *dim = isl_dim_map(set_dim);
5011         if (!dim)
5012                 return NULL;
5013         return basic_map_identity(dim);
5014 }
5015
5016 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
5017 {
5018         if (!model || !model->dim)
5019                 return NULL;
5020         isl_assert(model->ctx,
5021                         model->dim->n_in == model->dim->n_out, return NULL);
5022         return basic_map_identity(isl_dim_copy(model->dim));
5023 }
5024
5025 static struct isl_map *map_identity(struct isl_dim *dim)
5026 {
5027         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
5028         return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim)));
5029 }
5030
5031 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
5032 {
5033         struct isl_dim *dim = isl_dim_map(set_dim);
5034         if (!dim)
5035                 return NULL;
5036         return map_identity(dim);
5037 }
5038
5039 struct isl_map *isl_map_identity_like(struct isl_map *model)
5040 {
5041         if (!model || !model->dim)
5042                 return NULL;
5043         isl_assert(model->ctx,
5044                         model->dim->n_in == model->dim->n_out, return NULL);
5045         return map_identity(isl_dim_copy(model->dim));
5046 }
5047
5048 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
5049 {
5050         if (!model || !model->dim)
5051                 return NULL;
5052         isl_assert(model->ctx,
5053                         model->dim->n_in == model->dim->n_out, return NULL);
5054         return map_identity(isl_dim_copy(model->dim));
5055 }
5056
5057 /* Construct a basic set with all set dimensions having only non-negative
5058  * values.
5059  */
5060 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
5061 {
5062         int i;
5063         unsigned nparam;
5064         unsigned dim;
5065         struct isl_basic_set *bset;
5066
5067         if (!dims)
5068                 return NULL;
5069         nparam = dims->nparam;
5070         dim = dims->n_out;
5071         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
5072         if (!bset)
5073                 return NULL;
5074         for (i = 0; i < dim; ++i) {
5075                 int k = isl_basic_set_alloc_inequality(bset);
5076                 if (k < 0)
5077                         goto error;
5078                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
5079                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
5080         }
5081         return bset;
5082 error:
5083         isl_basic_set_free(bset);
5084         return NULL;
5085 }
5086
5087 __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set,
5088         enum isl_dim_type type, unsigned first, unsigned n)
5089 {
5090         int i;
5091         isl_basic_set *nonneg = NULL;
5092         isl_basic_set *neg = NULL;
5093
5094         if (!set)
5095                 return NULL;
5096         if (n == 0)
5097                 return set;
5098
5099         isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error);
5100
5101         for (i = 0; i < n; ++i) {
5102                 int k;
5103
5104                 neg = NULL;
5105                 nonneg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5106                 k = isl_basic_set_alloc_inequality(nonneg);
5107                 if (k < 0)
5108                         goto error;
5109                 isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg));
5110                 isl_int_set_si(nonneg->ineq[k][pos(set->dim, type) + first + i], 1);
5111
5112                 neg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5113                 k = isl_basic_set_alloc_inequality(neg);
5114                 if (k < 0)
5115                         goto error;
5116                 isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg));
5117                 isl_int_set_si(neg->ineq[k][0], -1);
5118                 isl_int_set_si(neg->ineq[k][pos(set->dim, type) + first + i], -1);
5119
5120                 set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg));
5121         }
5122
5123         return set;
5124 error:
5125         isl_basic_set_free(nonneg);
5126         isl_basic_set_free(neg);
5127         isl_set_free(set);
5128         return NULL;
5129 }
5130
5131 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
5132 {
5133         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
5134 }
5135
5136 int isl_basic_map_is_subset(
5137                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5138 {
5139         int is_subset;
5140         struct isl_map *map1;
5141         struct isl_map *map2;
5142
5143         if (!bmap1 || !bmap2)
5144                 return -1;
5145
5146         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
5147         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
5148
5149         is_subset = isl_map_is_subset(map1, map2);
5150
5151         isl_map_free(map1);
5152         isl_map_free(map2);
5153
5154         return is_subset;
5155 }
5156
5157 int isl_basic_map_is_equal(
5158                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5159 {
5160         int is_subset;
5161
5162         if (!bmap1 || !bmap2)
5163                 return -1;
5164         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5165         if (is_subset != 1)
5166                 return is_subset;
5167         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5168         return is_subset;
5169 }
5170
5171 int isl_basic_set_is_equal(
5172                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5173 {
5174         return isl_basic_map_is_equal(
5175                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
5176 }
5177
5178 int isl_map_is_empty(struct isl_map *map)
5179 {
5180         int i;
5181         int is_empty;
5182
5183         if (!map)
5184                 return -1;
5185         for (i = 0; i < map->n; ++i) {
5186                 is_empty = isl_basic_map_is_empty(map->p[i]);
5187                 if (is_empty < 0)
5188                         return -1;
5189                 if (!is_empty)
5190                         return 0;
5191         }
5192         return 1;
5193 }
5194
5195 int isl_map_fast_is_empty(struct isl_map *map)
5196 {
5197         return map ? map->n == 0 : -1;
5198 }
5199
5200 int isl_set_fast_is_empty(struct isl_set *set)
5201 {
5202         return set ? set->n == 0 : -1;
5203 }
5204
5205 int isl_set_is_empty(struct isl_set *set)
5206 {
5207         return isl_map_is_empty((struct isl_map *)set);
5208 }
5209
5210 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
5211 {
5212         int is_subset;
5213
5214         if (!map1 || !map2)
5215                 return -1;
5216         is_subset = isl_map_is_subset(map1, map2);
5217         if (is_subset != 1)
5218                 return is_subset;
5219         is_subset = isl_map_is_subset(map2, map1);
5220         return is_subset;
5221 }
5222
5223 int isl_basic_map_is_strict_subset(
5224                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5225 {
5226         int is_subset;
5227
5228         if (!bmap1 || !bmap2)
5229                 return -1;
5230         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5231         if (is_subset != 1)
5232                 return is_subset;
5233         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5234         if (is_subset == -1)
5235                 return is_subset;
5236         return !is_subset;
5237 }
5238
5239 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
5240 {
5241         int is_subset;
5242
5243         if (!map1 || !map2)
5244                 return -1;
5245         is_subset = isl_map_is_subset(map1, map2);
5246         if (is_subset != 1)
5247                 return is_subset;
5248         is_subset = isl_map_is_subset(map2, map1);
5249         if (is_subset == -1)
5250                 return is_subset;
5251         return !is_subset;
5252 }
5253
5254 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
5255 {
5256         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
5257 }
5258
5259 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
5260 {
5261         if (!bmap)
5262                 return -1;
5263         return bmap->n_eq == 0 && bmap->n_ineq == 0;
5264 }
5265
5266 int isl_basic_set_is_universe(struct isl_basic_set *bset)
5267 {
5268         if (!bset)
5269                 return -1;
5270         return bset->n_eq == 0 && bset->n_ineq == 0;
5271 }
5272
5273 int isl_map_fast_is_universe(__isl_keep isl_map *map)
5274 {
5275         if (!map)
5276                 return -1;
5277
5278         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
5279 }
5280
5281 int isl_set_fast_is_universe(__isl_keep isl_set *set)
5282 {
5283         return isl_map_fast_is_universe((isl_map *) set);
5284 }
5285
5286 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
5287 {
5288         struct isl_basic_set *bset = NULL;
5289         struct isl_vec *sample = NULL;
5290         int empty;
5291         unsigned total;
5292
5293         if (!bmap)
5294                 return -1;
5295
5296         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
5297                 return 1;
5298
5299         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
5300                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
5301                 copy = isl_basic_map_convex_hull(copy);
5302                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
5303                 isl_basic_map_free(copy);
5304                 return empty;
5305         }
5306
5307         total = 1 + isl_basic_map_total_dim(bmap);
5308         if (bmap->sample && bmap->sample->size == total) {
5309                 int contains = isl_basic_map_contains(bmap, bmap->sample);
5310                 if (contains < 0)
5311                         return -1;
5312                 if (contains)
5313                         return 0;
5314         }
5315         isl_vec_free(bmap->sample);
5316         bmap->sample = NULL;
5317         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
5318         if (!bset)
5319                 return -1;
5320         sample = isl_basic_set_sample_vec(bset);
5321         if (!sample)
5322                 return -1;
5323         empty = sample->size == 0;
5324         isl_vec_free(bmap->sample);
5325         bmap->sample = sample;
5326         if (empty)
5327                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
5328
5329         return empty;
5330 }
5331
5332 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
5333 {
5334         if (!bmap)
5335                 return -1;
5336         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
5337 }
5338
5339 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
5340 {
5341         if (!bset)
5342                 return -1;
5343         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
5344 }
5345
5346 int isl_basic_set_is_empty(struct isl_basic_set *bset)
5347 {
5348         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
5349 }
5350
5351 struct isl_map *isl_basic_map_union(
5352         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5353 {
5354         struct isl_map *map;
5355         if (!bmap1 || !bmap2)
5356                 return NULL;
5357
5358         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
5359
5360         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
5361         if (!map)
5362                 goto error;
5363         map = isl_map_add_basic_map(map, bmap1);
5364         map = isl_map_add_basic_map(map, bmap2);
5365         return map;
5366 error:
5367         isl_basic_map_free(bmap1);
5368         isl_basic_map_free(bmap2);
5369         return NULL;
5370 }
5371
5372 struct isl_set *isl_basic_set_union(
5373                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5374 {
5375         return (struct isl_set *)isl_basic_map_union(
5376                                             (struct isl_basic_map *)bset1,
5377                                             (struct isl_basic_map *)bset2);
5378 }
5379
5380 /* Order divs such that any div only depends on previous divs */
5381 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
5382 {
5383         int i;
5384         unsigned off;
5385
5386         if (!bmap)
5387                 return NULL;
5388
5389         off = isl_dim_total(bmap->dim);
5390
5391         for (i = 0; i < bmap->n_div; ++i) {
5392                 int pos;
5393                 if (isl_int_is_zero(bmap->div[i][0]))
5394                         continue;
5395                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
5396                                                             bmap->n_div-i);
5397                 if (pos == -1)
5398                         continue;
5399                 isl_basic_map_swap_div(bmap, i, i + pos);
5400                 --i;
5401         }
5402         return bmap;
5403 }
5404
5405 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
5406 {
5407         return (struct isl_basic_set *)
5408                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
5409 }
5410
5411 __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
5412 {
5413         int i;
5414
5415         if (!map)
5416                 return 0;
5417
5418         for (i = 0; i < map->n; ++i) {
5419                 map->p[i] = isl_basic_map_order_divs(map->p[i]);
5420                 if (!map->p[i])
5421                         goto error;
5422         }
5423
5424         return map;
5425 error:
5426         isl_map_free(map);
5427         return NULL;
5428 }
5429
5430 /* Look for a div in dst that corresponds to the div "div" in src.
5431  * The divs before "div" in src and dst are assumed to be the same.
5432  *
5433  * Returns -1 if no corresponding div was found and the position
5434  * of the corresponding div in dst otherwise.
5435  */
5436 static int find_div(struct isl_basic_map *dst,
5437                         struct isl_basic_map *src, unsigned div)
5438 {
5439         int i;
5440
5441         unsigned total = isl_dim_total(src->dim);
5442
5443         isl_assert(dst->ctx, div <= dst->n_div, return -1);
5444         for (i = div; i < dst->n_div; ++i)
5445                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
5446                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
5447                                                 dst->n_div - div) == -1)
5448                         return i;
5449         return -1;
5450 }
5451
5452 struct isl_basic_map *isl_basic_map_align_divs(
5453                 struct isl_basic_map *dst, struct isl_basic_map *src)
5454 {
5455         int i;
5456         unsigned total = isl_dim_total(src->dim);
5457
5458         if (!dst || !src)
5459                 goto error;
5460
5461         if (src->n_div == 0)
5462                 return dst;
5463
5464         for (i = 0; i < src->n_div; ++i)
5465                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
5466
5467         src = isl_basic_map_order_divs(src);
5468         dst = isl_basic_map_cow(dst);
5469         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
5470                         src->n_div, 0, 2 * src->n_div);
5471         if (!dst)
5472                 return NULL;
5473         for (i = 0; i < src->n_div; ++i) {
5474                 int j = find_div(dst, src, i);
5475                 if (j < 0) {
5476                         j = isl_basic_map_alloc_div(dst);
5477                         if (j < 0)
5478                                 goto error;
5479                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
5480                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
5481                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
5482                                 goto error;
5483                 }
5484                 if (j != i)
5485                         isl_basic_map_swap_div(dst, i, j);
5486         }
5487         return dst;
5488 error:
5489         isl_basic_map_free(dst);
5490         return NULL;
5491 }
5492
5493 struct isl_basic_set *isl_basic_set_align_divs(
5494                 struct isl_basic_set *dst, struct isl_basic_set *src)
5495 {
5496         return (struct isl_basic_set *)isl_basic_map_align_divs(
5497                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
5498 }
5499
5500 struct isl_map *isl_map_align_divs(struct isl_map *map)
5501 {
5502         int i;
5503
5504         if (!map)
5505                 return NULL;
5506         if (map->n == 0)
5507                 return map;
5508         map = isl_map_compute_divs(map);
5509         map = isl_map_cow(map);
5510         if (!map)
5511                 return NULL;
5512
5513         for (i = 1; i < map->n; ++i)
5514                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
5515         for (i = 1; i < map->n; ++i)
5516                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
5517
5518         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5519         return map;
5520 }
5521
5522 struct isl_set *isl_set_align_divs(struct isl_set *set)
5523 {
5524         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
5525 }
5526
5527 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
5528 {
5529         if (!set || !map)
5530                 goto error;
5531         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
5532         map = isl_map_intersect_domain(map, set);
5533         set = isl_map_range(map);
5534         return set;
5535 error:
5536         isl_set_free(set);
5537         isl_map_free(map);
5538         return NULL;
5539 }
5540
5541 /* There is no need to cow as removing empty parts doesn't change
5542  * the meaning of the set.
5543  */
5544 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
5545 {
5546         int i;
5547
5548         if (!map)
5549                 return NULL;
5550
5551         for (i = map->n-1; i >= 0; --i) {
5552                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
5553                         continue;
5554                 isl_basic_map_free(map->p[i]);
5555                 if (i != map->n-1) {
5556                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5557                         map->p[i] = map->p[map->n-1];
5558                 }
5559                 map->n--;
5560         }
5561
5562         return map;
5563 }
5564
5565 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
5566 {
5567         return (struct isl_set *)
5568                 isl_map_remove_empty_parts((struct isl_map *)set);
5569 }
5570
5571 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
5572 {
5573         struct isl_basic_map *bmap;
5574         if (!map || map->n == 0)
5575                 return NULL;
5576         bmap = map->p[map->n-1];
5577         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
5578         return isl_basic_map_copy(bmap);
5579 }
5580
5581 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
5582 {
5583         return (struct isl_basic_set *)
5584                 isl_map_copy_basic_map((struct isl_map *)set);
5585 }
5586
5587 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
5588                                                 __isl_keep isl_basic_map *bmap)
5589 {
5590         int i;
5591
5592         if (!map || !bmap)
5593                 goto error;
5594         for (i = map->n-1; i >= 0; --i) {
5595                 if (map->p[i] != bmap)
5596                         continue;
5597                 map = isl_map_cow(map);
5598                 if (!map)
5599                         goto error;
5600                 isl_basic_map_free(map->p[i]);
5601                 if (i != map->n-1) {
5602                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
5603                         map->p[i] = map->p[map->n-1];
5604                 }
5605                 map->n--;
5606                 return map;
5607         }
5608         return map;
5609 error:
5610         isl_map_free(map);
5611         return NULL;
5612 }
5613
5614 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
5615                                                 struct isl_basic_set *bset)
5616 {
5617         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
5618                                                 (struct isl_basic_map *)bset);
5619 }
5620
5621 /* Given two basic sets bset1 and bset2, compute the maximal difference
5622  * between the values of dimension pos in bset1 and those in bset2
5623  * for any common value of the parameters and dimensions preceding pos.
5624  */
5625 static enum isl_lp_result basic_set_maximal_difference_at(
5626         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
5627         int pos, isl_int *opt)
5628 {
5629         struct isl_dim *dims;
5630         struct isl_basic_map *bmap1 = NULL;
5631         struct isl_basic_map *bmap2 = NULL;
5632         struct isl_ctx *ctx;
5633         struct isl_vec *obj;
5634         unsigned total;
5635         unsigned nparam;
5636         unsigned dim1, dim2;
5637         enum isl_lp_result res;
5638
5639         if (!bset1 || !bset2)
5640                 return isl_lp_error;
5641
5642         nparam = isl_basic_set_n_param(bset1);
5643         dim1 = isl_basic_set_n_dim(bset1);
5644         dim2 = isl_basic_set_n_dim(bset2);
5645         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
5646         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
5647         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
5648         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
5649         if (!bmap1 || !bmap2)
5650                 goto error;
5651         bmap1 = isl_basic_map_cow(bmap1);
5652         bmap1 = isl_basic_map_extend(bmap1, nparam,
5653                         pos, (dim1 - pos) + (dim2 - pos),
5654                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
5655         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
5656         if (!bmap1)
5657                 goto error;
5658         total = isl_basic_map_total_dim(bmap1);
5659         ctx = bmap1->ctx;
5660         obj = isl_vec_alloc(ctx, 1 + total);
5661         isl_seq_clr(obj->block.data, 1 + total);
5662         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
5663         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
5664         if (!obj)
5665                 goto error;
5666         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
5667                                         opt, NULL, NULL);
5668         isl_basic_map_free(bmap1);
5669         isl_vec_free(obj);
5670         return res;
5671 error:
5672         isl_basic_map_free(bmap1);
5673         isl_basic_map_free(bmap2);
5674         return isl_lp_error;
5675 }
5676
5677 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
5678  * for any common value of the parameters and dimensions preceding pos
5679  * in both basic sets, the values of dimension pos in bset1 are
5680  * smaller or larger than those in bset2.
5681  *
5682  * Returns
5683  *       1 if bset1 follows bset2
5684  *      -1 if bset1 precedes bset2
5685  *       0 if bset1 and bset2 are incomparable
5686  *      -2 if some error occurred.
5687  */
5688 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
5689         struct isl_basic_set *bset2, int pos)
5690 {
5691         isl_int opt;
5692         enum isl_lp_result res;
5693         int cmp;
5694
5695         isl_int_init(opt);
5696
5697         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5698
5699         if (res == isl_lp_empty)
5700                 cmp = 0;
5701         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5702                   res == isl_lp_unbounded)
5703                 cmp = 1;
5704         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5705                 cmp = -1;
5706         else
5707                 cmp = -2;
5708
5709         isl_int_clear(opt);
5710         return cmp;
5711 }
5712
5713 /* Given two basic sets bset1 and bset2, check whether
5714  * for any common value of the parameters and dimensions preceding pos
5715  * there is a value of dimension pos in bset1 that is larger
5716  * than a value of the same dimension in bset2.
5717  *
5718  * Return
5719  *       1 if there exists such a pair
5720  *       0 if there is no such pair, but there is a pair of equal values
5721  *      -1 otherwise
5722  *      -2 if some error occurred.
5723  */
5724 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
5725         __isl_keep isl_basic_set *bset2, int pos)
5726 {
5727         isl_int opt;
5728         enum isl_lp_result res;
5729         int cmp;
5730
5731         isl_int_init(opt);
5732
5733         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5734
5735         if (res == isl_lp_empty)
5736                 cmp = -1;
5737         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5738                   res == isl_lp_unbounded)
5739                 cmp = 1;
5740         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5741                 cmp = -1;
5742         else if (res == isl_lp_ok)
5743                 cmp = 0;
5744         else
5745                 cmp = -2;
5746
5747         isl_int_clear(opt);
5748         return cmp;
5749 }
5750
5751 /* Given two sets set1 and set2, check whether
5752  * for any common value of the parameters and dimensions preceding pos
5753  * there is a value of dimension pos in set1 that is larger
5754  * than a value of the same dimension in set2.
5755  *
5756  * Return
5757  *       1 if there exists such a pair
5758  *       0 if there is no such pair, but there is a pair of equal values
5759  *      -1 otherwise
5760  *      -2 if some error occurred.
5761  */
5762 int isl_set_follows_at(__isl_keep isl_set *set1,
5763         __isl_keep isl_set *set2, int pos)
5764 {
5765         int i, j;
5766         int follows = -1;
5767
5768         if (!set1 || !set2)
5769                 return -2;
5770
5771         for (i = 0; i < set1->n; ++i)
5772                 for (j = 0; j < set2->n; ++j) {
5773                         int f;
5774                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5775                         if (f == 1 || f == -2)
5776                                 return f;
5777                         if (f > follows)
5778                                 follows = f;
5779                 }
5780
5781         return follows;
5782 }
5783
5784 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5785         unsigned pos, isl_int *val)
5786 {
5787         int i;
5788         int d;
5789         unsigned total;
5790
5791         if (!bmap)
5792                 return -1;
5793         total = isl_basic_map_total_dim(bmap);
5794         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5795                 for (; d+1 > pos; --d)
5796                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5797                                 break;
5798                 if (d != pos)
5799                         continue;
5800                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5801                         return 0;
5802                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5803                         return 0;
5804                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5805                         return 0;
5806                 if (val)
5807                         isl_int_neg(*val, bmap->eq[i][0]);
5808                 return 1;
5809         }
5810         return 0;
5811 }
5812
5813 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5814         unsigned pos, isl_int *val)
5815 {
5816         int i;
5817         isl_int v;
5818         isl_int tmp;
5819         int fixed;
5820
5821         if (!map)
5822                 return -1;
5823         if (map->n == 0)
5824                 return 0;
5825         if (map->n == 1)
5826                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5827         isl_int_init(v);
5828         isl_int_init(tmp);
5829         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5830         for (i = 1; fixed == 1 && i < map->n; ++i) {
5831                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5832                 if (fixed == 1 && isl_int_ne(tmp, v))
5833                         fixed = 0;
5834         }
5835         if (val)
5836                 isl_int_set(*val, v);
5837         isl_int_clear(tmp);
5838         isl_int_clear(v);
5839         return fixed;
5840 }
5841
5842 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5843         unsigned pos, isl_int *val)
5844 {
5845         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5846                                                 pos, val);
5847 }
5848
5849 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5850         isl_int *val)
5851 {
5852         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5853 }
5854
5855 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5856         enum isl_dim_type type, unsigned pos, isl_int *val)
5857 {
5858         if (pos >= isl_basic_map_dim(bmap, type))
5859                 return -1;
5860         return isl_basic_map_fast_has_fixed_var(bmap,
5861                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
5862 }
5863
5864 int isl_map_fast_is_fixed(struct isl_map *map,
5865         enum isl_dim_type type, unsigned pos, isl_int *val)
5866 {
5867         if (pos >= isl_map_dim(map, type))
5868                 return -1;
5869         return isl_map_fast_has_fixed_var(map,
5870                 map_offset(map, type) - 1 + pos, val);
5871 }
5872
5873 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5874  * then return this fixed value in *val.
5875  */
5876 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
5877         isl_int *val)
5878 {
5879         return isl_basic_set_fast_has_fixed_var(bset,
5880                                         isl_basic_set_n_param(bset) + dim, val);
5881 }
5882
5883 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5884  * then return this fixed value in *val.
5885  */
5886 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
5887 {
5888         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
5889 }
5890
5891 /* Check if input variable in has fixed value and if so and if val is not NULL,
5892  * then return this fixed value in *val.
5893  */
5894 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
5895 {
5896         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
5897 }
5898
5899 /* Check if dimension dim has an (obvious) fixed lower bound and if so
5900  * and if val is not NULL, then return this lower bound in *val.
5901  */
5902 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
5903         unsigned dim, isl_int *val)
5904 {
5905         int i, i_eq = -1, i_ineq = -1;
5906         isl_int *c;
5907         unsigned total;
5908         unsigned nparam;
5909
5910         if (!bset)
5911                 return -1;
5912         total = isl_basic_set_total_dim(bset);
5913         nparam = isl_basic_set_n_param(bset);
5914         for (i = 0; i < bset->n_eq; ++i) {
5915                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
5916                         continue;
5917                 if (i_eq != -1)
5918                         return 0;
5919                 i_eq = i;
5920         }
5921         for (i = 0; i < bset->n_ineq; ++i) {
5922                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
5923                         continue;
5924                 if (i_eq != -1 || i_ineq != -1)
5925                         return 0;
5926                 i_ineq = i;
5927         }
5928         if (i_eq == -1 && i_ineq == -1)
5929                 return 0;
5930         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
5931         /* The coefficient should always be one due to normalization. */
5932         if (!isl_int_is_one(c[1+nparam+dim]))
5933                 return 0;
5934         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
5935                 return 0;
5936         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
5937                                         total - nparam - dim - 1) != -1)
5938                 return 0;
5939         if (val)
5940                 isl_int_neg(*val, c[0]);
5941         return 1;
5942 }
5943
5944 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
5945         unsigned dim, isl_int *val)
5946 {
5947         int i;
5948         isl_int v;
5949         isl_int tmp;
5950         int fixed;
5951
5952         if (!set)
5953                 return -1;
5954         if (set->n == 0)
5955                 return 0;
5956         if (set->n == 1)
5957                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5958                                                                 dim, val);
5959         isl_int_init(v);
5960         isl_int_init(tmp);
5961         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5962                                                                 dim, &v);
5963         for (i = 1; fixed == 1 && i < set->n; ++i) {
5964                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5965                                                                 dim, &tmp);
5966                 if (fixed == 1 && isl_int_ne(tmp, v))
5967                         fixed = 0;
5968         }
5969         if (val)
5970                 isl_int_set(*val, v);
5971         isl_int_clear(tmp);
5972         isl_int_clear(v);
5973         return fixed;
5974 }
5975
5976 struct constraint {
5977         unsigned        size;
5978         isl_int         *c;
5979 };
5980
5981 static int qsort_constraint_cmp(const void *p1, const void *p2)
5982 {
5983         const struct constraint *c1 = (const struct constraint *)p1;
5984         const struct constraint *c2 = (const struct constraint *)p2;
5985         unsigned size = isl_min(c1->size, c2->size);
5986         return isl_seq_cmp(c1->c, c2->c, size);
5987 }
5988
5989 static struct isl_basic_map *isl_basic_map_sort_constraints(
5990         struct isl_basic_map *bmap)
5991 {
5992         int i;
5993         struct constraint *c;
5994         unsigned total;
5995
5996         if (!bmap)
5997                 return NULL;
5998         total = isl_basic_map_total_dim(bmap);
5999         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
6000         if (!c)
6001                 goto error;
6002         for (i = 0; i < bmap->n_ineq; ++i) {
6003                 c[i].size = total;
6004                 c[i].c = bmap->ineq[i];
6005         }
6006         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
6007         for (i = 0; i < bmap->n_ineq; ++i)
6008                 bmap->ineq[i] = c[i].c;
6009         free(c);
6010         return bmap;
6011 error:
6012         isl_basic_map_free(bmap);
6013         return NULL;
6014 }
6015
6016 __isl_give isl_basic_set *isl_basic_set_sort_constraints(
6017         __isl_take isl_basic_set *bset)
6018 {
6019         return (struct isl_basic_set *)isl_basic_map_sort_constraints(
6020                                                 (struct isl_basic_map *)bset);
6021 }
6022
6023 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
6024 {
6025         if (!bmap)
6026                 return NULL;
6027         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
6028                 return bmap;
6029         bmap = isl_basic_map_convex_hull(bmap);
6030         bmap = isl_basic_map_sort_constraints(bmap);
6031         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
6032         return bmap;
6033 }
6034
6035 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
6036 {
6037         return (struct isl_basic_set *)isl_basic_map_normalize(
6038                                                 (struct isl_basic_map *)bset);
6039 }
6040
6041 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
6042         const struct isl_basic_map *bmap2)
6043 {
6044         int i, cmp;
6045         unsigned total;
6046
6047         if (bmap1 == bmap2)
6048                 return 0;
6049         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
6050                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
6051         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
6052                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
6053         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
6054                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
6055         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
6056             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
6057                 return 0;
6058         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
6059                 return 1;
6060         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
6061                 return -1;
6062         if (bmap1->n_eq != bmap2->n_eq)
6063                 return bmap1->n_eq - bmap2->n_eq;
6064         if (bmap1->n_ineq != bmap2->n_ineq)
6065                 return bmap1->n_ineq - bmap2->n_ineq;
6066         if (bmap1->n_div != bmap2->n_div)
6067                 return bmap1->n_div - bmap2->n_div;
6068         total = isl_basic_map_total_dim(bmap1);
6069         for (i = 0; i < bmap1->n_eq; ++i) {
6070                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
6071                 if (cmp)
6072                         return cmp;
6073         }
6074         for (i = 0; i < bmap1->n_ineq; ++i) {
6075                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
6076                 if (cmp)
6077                         return cmp;
6078         }
6079         for (i = 0; i < bmap1->n_div; ++i) {
6080                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
6081                 if (cmp)
6082                         return cmp;
6083         }
6084         return 0;
6085 }
6086
6087 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
6088         struct isl_basic_map *bmap2)
6089 {
6090         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
6091 }
6092
6093 int isl_basic_set_fast_is_equal(__isl_keep isl_basic_set *bset1,
6094         __isl_keep isl_basic_set *bset2)
6095 {
6096         return isl_basic_map_fast_is_equal((isl_basic_map *)bset1,
6097                                             (isl_basic_map *)bset2);
6098 }
6099
6100 static int qsort_bmap_cmp(const void *p1, const void *p2)
6101 {
6102         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
6103         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
6104
6105         return isl_basic_map_fast_cmp(bmap1, bmap2);
6106 }
6107
6108 /* We normalize in place, but if anything goes wrong we need
6109  * to return NULL, so we need to make sure we don't change the
6110  * meaning of any possible other copies of map.
6111  */
6112 struct isl_map *isl_map_normalize(struct isl_map *map)
6113 {
6114         int i, j;
6115         struct isl_basic_map *bmap;
6116
6117         if (!map)
6118                 return NULL;
6119         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
6120                 return map;
6121         for (i = 0; i < map->n; ++i) {
6122                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
6123                 if (!bmap)
6124                         goto error;
6125                 isl_basic_map_free(map->p[i]);
6126                 map->p[i] = bmap;
6127         }
6128         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
6129         ISL_F_SET(map, ISL_MAP_NORMALIZED);
6130         map = isl_map_remove_empty_parts(map);
6131         if (!map)
6132                 return NULL;
6133         for (i = map->n - 1; i >= 1; --i) {
6134                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
6135                         continue;
6136                 isl_basic_map_free(map->p[i-1]);
6137                 for (j = i; j < map->n; ++j)
6138                         map->p[j-1] = map->p[j];
6139                 map->n--;
6140         }
6141         return map;
6142 error:
6143         isl_map_free(map);
6144         return NULL;
6145
6146 }
6147
6148 struct isl_set *isl_set_normalize(struct isl_set *set)
6149 {
6150         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
6151 }
6152
6153 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
6154 {
6155         int i;
6156         int equal;
6157
6158         if (!map1 || !map2)
6159                 return -1;
6160
6161         if (map1 == map2)
6162                 return 1;
6163         if (!isl_dim_equal(map1->dim, map2->dim))
6164                 return 0;
6165
6166         map1 = isl_map_copy(map1);
6167         map2 = isl_map_copy(map2);
6168         map1 = isl_map_normalize(map1);
6169         map2 = isl_map_normalize(map2);
6170         if (!map1 || !map2)
6171                 goto error;
6172         equal = map1->n == map2->n;
6173         for (i = 0; equal && i < map1->n; ++i) {
6174                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
6175                 if (equal < 0)
6176                         goto error;
6177         }
6178         isl_map_free(map1);
6179         isl_map_free(map2);
6180         return equal;
6181 error:
6182         isl_map_free(map1);
6183         isl_map_free(map2);
6184         return -1;
6185 }
6186
6187 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
6188 {
6189         return isl_map_fast_is_equal((struct isl_map *)set1,
6190                                                 (struct isl_map *)set2);
6191 }
6192
6193 /* Return an interval that ranges from min to max (inclusive)
6194  */
6195 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
6196         isl_int min, isl_int max)
6197 {
6198         int k;
6199         struct isl_basic_set *bset = NULL;
6200
6201         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
6202         if (!bset)
6203                 goto error;
6204
6205         k = isl_basic_set_alloc_inequality(bset);
6206         if (k < 0)
6207                 goto error;
6208         isl_int_set_si(bset->ineq[k][1], 1);
6209         isl_int_neg(bset->ineq[k][0], min);
6210
6211         k = isl_basic_set_alloc_inequality(bset);
6212         if (k < 0)
6213                 goto error;
6214         isl_int_set_si(bset->ineq[k][1], -1);
6215         isl_int_set(bset->ineq[k][0], max);
6216
6217         return bset;
6218 error:
6219         isl_basic_set_free(bset);
6220         return NULL;
6221 }
6222
6223 /* Return the Cartesian product of the basic sets in list (in the given order).
6224  */
6225 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
6226 {
6227         int i;
6228         unsigned dim;
6229         unsigned nparam;
6230         unsigned extra;
6231         unsigned n_eq;
6232         unsigned n_ineq;
6233         struct isl_basic_set *product = NULL;
6234
6235         if (!list)
6236                 goto error;
6237         isl_assert(list->ctx, list->n > 0, goto error);
6238         isl_assert(list->ctx, list->p[0], goto error);
6239         nparam = isl_basic_set_n_param(list->p[0]);
6240         dim = isl_basic_set_n_dim(list->p[0]);
6241         extra = list->p[0]->n_div;
6242         n_eq = list->p[0]->n_eq;
6243         n_ineq = list->p[0]->n_ineq;
6244         for (i = 1; i < list->n; ++i) {
6245                 isl_assert(list->ctx, list->p[i], goto error);
6246                 isl_assert(list->ctx,
6247                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
6248                 dim += isl_basic_set_n_dim(list->p[i]);
6249                 extra += list->p[i]->n_div;
6250                 n_eq += list->p[i]->n_eq;
6251                 n_ineq += list->p[i]->n_ineq;
6252         }
6253         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
6254                                         n_eq, n_ineq);
6255         if (!product)
6256                 goto error;
6257         dim = 0;
6258         for (i = 0; i < list->n; ++i) {
6259                 isl_basic_set_add_constraints(product,
6260                                         isl_basic_set_copy(list->p[i]), dim);
6261                 dim += isl_basic_set_n_dim(list->p[i]);
6262         }
6263         isl_basic_set_list_free(list);
6264         return product;
6265 error:
6266         isl_basic_set_free(product);
6267         isl_basic_set_list_free(list);
6268         return NULL;
6269 }
6270
6271 struct isl_basic_map *isl_basic_map_product(
6272                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
6273 {
6274         struct isl_dim *dim_result = NULL;
6275         struct isl_basic_map *bmap;
6276         unsigned in1, in2, out1, out2, nparam, total, pos;
6277         struct isl_dim_map *dim_map1, *dim_map2;
6278
6279         if (!bmap1 || !bmap2)
6280                 goto error;
6281
6282         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
6283                                      bmap2->dim, isl_dim_param), goto error);
6284         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
6285                                                    isl_dim_copy(bmap2->dim));
6286
6287         in1 = isl_basic_map_n_in(bmap1);
6288         in2 = isl_basic_map_n_in(bmap2);
6289         out1 = isl_basic_map_n_out(bmap1);
6290         out2 = isl_basic_map_n_out(bmap2);
6291         nparam = isl_basic_map_n_param(bmap1);
6292
6293         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
6294         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
6295         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
6296         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
6297         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
6298         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
6299         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
6300         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
6301         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
6302         isl_dim_map_div(dim_map1, bmap1, pos += out2);
6303         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
6304
6305         bmap = isl_basic_map_alloc_dim(dim_result,
6306                         bmap1->n_div + bmap2->n_div,
6307                         bmap1->n_eq + bmap2->n_eq,
6308                         bmap1->n_ineq + bmap2->n_ineq);
6309         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
6310         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
6311         bmap = isl_basic_map_simplify(bmap);
6312         return isl_basic_map_finalize(bmap);
6313 error:
6314         isl_basic_map_free(bmap1);
6315         isl_basic_map_free(bmap2);
6316         return NULL;
6317 }
6318
6319 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
6320  */
6321 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
6322 {
6323         unsigned flags = 0;
6324         struct isl_map *result;
6325         int i, j;
6326
6327         if (!map1 || !map2)
6328                 goto error;
6329
6330         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
6331                                          map2->dim, isl_dim_param), goto error);
6332
6333         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
6334             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
6335                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
6336
6337         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
6338                                                    isl_dim_copy(map2->dim)),
6339                                 map1->n * map2->n, flags);
6340         if (!result)
6341                 goto error;
6342         for (i = 0; i < map1->n; ++i)
6343                 for (j = 0; j < map2->n; ++j) {
6344                         struct isl_basic_map *part;
6345                         part = isl_basic_map_product(
6346                                     isl_basic_map_copy(map1->p[i]),
6347                                     isl_basic_map_copy(map2->p[j]));
6348                         if (isl_basic_map_is_empty(part))
6349                                 isl_basic_map_free(part);
6350                         else
6351                                 result = isl_map_add_basic_map(result, part);
6352                         if (!result)
6353                                 goto error;
6354                 }
6355         isl_map_free(map1);
6356         isl_map_free(map2);
6357         return result;
6358 error:
6359         isl_map_free(map1);
6360         isl_map_free(map2);
6361         return NULL;
6362 }
6363
6364 /* Given two set A and B, construct its Cartesian product A x B.
6365  */
6366 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
6367 {
6368         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
6369                                                  (struct isl_map *)set2);
6370 }
6371
6372 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
6373 {
6374         int i;
6375         uint32_t hash = isl_hash_init();
6376         unsigned total;
6377
6378         if (!bset)
6379                 return 0;
6380         bset = isl_basic_set_copy(bset);
6381         bset = isl_basic_set_normalize(bset);
6382         if (!bset)
6383                 return 0;
6384         total = isl_basic_set_total_dim(bset);
6385         isl_hash_byte(hash, bset->n_eq & 0xFF);
6386         for (i = 0; i < bset->n_eq; ++i) {
6387                 uint32_t c_hash;
6388                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
6389                 isl_hash_hash(hash, c_hash);
6390         }
6391         isl_hash_byte(hash, bset->n_ineq & 0xFF);
6392         for (i = 0; i < bset->n_ineq; ++i) {
6393                 uint32_t c_hash;
6394                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
6395                 isl_hash_hash(hash, c_hash);
6396         }
6397         isl_hash_byte(hash, bset->n_div & 0xFF);
6398         for (i = 0; i < bset->n_div; ++i) {
6399                 uint32_t c_hash;
6400                 if (isl_int_is_zero(bset->div[i][0]))
6401                         continue;
6402                 isl_hash_byte(hash, i & 0xFF);
6403                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
6404                 isl_hash_hash(hash, c_hash);
6405         }
6406         isl_basic_set_free(bset);
6407         return hash;
6408 }
6409
6410 uint32_t isl_set_get_hash(struct isl_set *set)
6411 {
6412         int i;
6413         uint32_t hash;
6414
6415         if (!set)
6416                 return 0;
6417         set = isl_set_copy(set);
6418         set = isl_set_normalize(set);
6419         if (!set)
6420                 return 0;
6421
6422         hash = isl_hash_init();
6423         for (i = 0; i < set->n; ++i) {
6424                 uint32_t bset_hash;
6425                 bset_hash = isl_basic_set_get_hash(set->p[i]);
6426                 isl_hash_hash(hash, bset_hash);
6427         }
6428
6429         isl_set_free(set);
6430
6431         return hash;
6432 }
6433
6434 /* Check if the value for dimension dim is completely determined
6435  * by the values of the other parameters and variables.
6436  * That is, check if dimension dim is involved in an equality.
6437  */
6438 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
6439 {
6440         int i;
6441         unsigned nparam;
6442
6443         if (!bset)
6444                 return -1;
6445         nparam = isl_basic_set_n_param(bset);
6446         for (i = 0; i < bset->n_eq; ++i)
6447                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
6448                         return 1;
6449         return 0;
6450 }
6451
6452 /* Check if the value for dimension dim is completely determined
6453  * by the values of the other parameters and variables.
6454  * That is, check if dimension dim is involved in an equality
6455  * for each of the subsets.
6456  */
6457 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
6458 {
6459         int i;
6460
6461         if (!set)
6462                 return -1;
6463         for (i = 0; i < set->n; ++i) {
6464                 int unique;
6465                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
6466                 if (unique != 1)
6467                         return unique;
6468         }
6469         return 1;
6470 }
6471
6472 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
6473         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
6474 {
6475         int i;
6476
6477         if (!map)
6478                 return -1;
6479
6480         for (i = 0; i < map->n; ++i)
6481                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
6482                         return -1;
6483
6484         return 0;
6485 }
6486
6487 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
6488         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
6489 {
6490         int i;
6491
6492         if (!set)
6493                 return -1;
6494
6495         for (i = 0; i < set->n; ++i)
6496                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
6497                         return -1;
6498
6499         return 0;
6500 }
6501
6502 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
6503 {
6504         struct isl_dim *dim;
6505
6506         if (!bset)
6507                 return NULL;
6508
6509         if (bset->n_div == 0)
6510                 return bset;
6511
6512         bset = isl_basic_set_cow(bset);
6513         if (!bset)
6514                 return NULL;
6515
6516         dim = isl_basic_set_get_dim(bset);
6517         dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
6518         if (!dim)
6519                 goto error;
6520         isl_dim_free(bset->dim);
6521         bset->dim = dim;
6522         bset->n_div = 0;
6523
6524         bset = isl_basic_set_finalize(bset);
6525
6526         return bset;
6527 error:
6528         isl_basic_set_free(bset);
6529         return NULL;
6530 }
6531
6532 __isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
6533 {
6534         int i;
6535         struct isl_dim *dim;
6536         unsigned n_div;
6537
6538         set = isl_set_align_divs(set);
6539
6540         if (!set)
6541                 return NULL;
6542         if (set->n == 0 || set->p[0]->n_div == 0)
6543                 return set;
6544
6545         set = isl_set_cow(set);
6546         if (!set)
6547                 return NULL;
6548
6549         n_div = set->p[0]->n_div;
6550         dim = isl_set_get_dim(set);
6551         dim = isl_dim_add(dim, isl_dim_set, n_div);
6552         if (!dim)
6553                 goto error;
6554         isl_dim_free(set->dim);
6555         set->dim = dim;
6556
6557         for (i = 0; i < set->n; ++i) {
6558                 set->p[i] = isl_basic_set_lift(set->p[i]);
6559                 if (!set->p[i])
6560                         goto error;
6561         }
6562
6563         return set;
6564 error:
6565         isl_set_free(set);
6566         return NULL;
6567 }
6568
6569 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
6570 {
6571         struct isl_dim *dim;
6572         struct isl_basic_map *bmap;
6573         unsigned n_set;
6574         unsigned n_div;
6575         unsigned n_param;
6576         unsigned total;
6577         int i, k, l;
6578
6579         set = isl_set_align_divs(set);
6580
6581         if (!set)
6582                 return NULL;
6583
6584         dim = isl_set_get_dim(set);
6585         if (set->n == 0 || set->p[0]->n_div == 0) {
6586                 isl_set_free(set);
6587                 return isl_map_identity(dim);
6588         }
6589
6590         n_div = set->p[0]->n_div;
6591         dim = isl_dim_map(dim);
6592         n_param = isl_dim_size(dim, isl_dim_param);
6593         n_set = isl_dim_size(dim, isl_dim_in);
6594         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
6595         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
6596         for (i = 0; i < n_set; ++i)
6597                 bmap = var_equal(bmap, i);
6598
6599         total = n_param + n_set + n_set + n_div;
6600         for (i = 0; i < n_div; ++i) {
6601                 k = isl_basic_map_alloc_inequality(bmap);
6602                 if (k < 0)
6603                         goto error;
6604                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
6605                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
6606                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
6607                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
6608                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
6609                             set->p[0]->div[i][0]);
6610
6611                 l = isl_basic_map_alloc_inequality(bmap);
6612                 if (l < 0)
6613                         goto error;
6614                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
6615                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
6616                             set->p[0]->div[i][0]);
6617                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
6618         }
6619
6620         isl_set_free(set);
6621         return isl_map_from_basic_map(bmap);
6622 error:
6623         isl_set_free(set);
6624         isl_basic_map_free(bmap);
6625         return NULL;
6626 }
6627
6628 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
6629 {
6630         unsigned dim;
6631         int size = 0;
6632
6633         if (!bset)
6634                 return -1;
6635
6636         dim = isl_basic_set_total_dim(bset);
6637         size += bset->n_eq * (1 + dim);
6638         size += bset->n_ineq * (1 + dim);
6639         size += bset->n_div * (2 + dim);
6640
6641         return size;
6642 }
6643
6644 int isl_set_size(__isl_keep isl_set *set)
6645 {
6646         int i;
6647         int size = 0;
6648
6649         if (!set)
6650                 return -1;
6651
6652         for (i = 0; i < set->n; ++i)
6653                 size += isl_basic_set_size(set->p[i]);
6654
6655         return size;
6656 }
6657
6658 int isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
6659         enum isl_dim_type type, unsigned pos)
6660 {
6661         int i;
6662         int lower, upper;
6663
6664         if (!bmap)
6665                 return -1;
6666
6667         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
6668
6669         pos += isl_basic_map_offset(bmap, type);
6670
6671         for (i = 0; i < bmap->n_eq; ++i)
6672                 if (!isl_int_is_zero(bmap->eq[i][pos]))
6673                         return 1;
6674
6675         lower = upper = 0;
6676         for (i = 0; i < bmap->n_ineq; ++i) {
6677                 int sgn = isl_int_sgn(bmap->ineq[i][pos]);
6678                 if (sgn > 0)
6679                         lower = 1;
6680                 if (sgn < 0)
6681                         upper = 1;
6682         }
6683
6684         return lower && upper;
6685 }
6686
6687 int isl_map_dim_is_bounded(__isl_keep isl_map *map,
6688         enum isl_dim_type type, unsigned pos)
6689 {
6690         int i;
6691
6692         if (!map)
6693                 return -1;
6694
6695         for (i = 0; i < map->n; ++i) {
6696                 int bounded;
6697                 bounded = isl_basic_map_dim_is_bounded(map->p[i], type, pos);
6698                 if (bounded < 0 || !bounded)
6699                         return bounded;
6700         }
6701
6702         return 1;
6703 }
6704
6705 /* Return 1 if the specified dim is involved in both an upper bound
6706  * and a lower bound.
6707  */
6708 int isl_set_dim_is_bounded(__isl_keep isl_set *set,
6709         enum isl_dim_type type, unsigned pos)
6710 {
6711         return isl_map_dim_is_bounded((isl_map *)set, type, pos);
6712 }
6713
6714 /* For each of the "n" variables starting at "first", determine
6715  * the sign of the variable and put the results in the first "n"
6716  * elements of the array "signs".
6717  * Sign
6718  *      1 means that the variable is non-negative
6719  *      -1 means that the variable is non-positive
6720  *      0 means the variable attains both positive and negative values.
6721  */
6722 int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
6723         unsigned first, unsigned n, int *signs)
6724 {
6725         isl_vec *bound = NULL;
6726         struct isl_tab *tab = NULL;
6727         struct isl_tab_undo *snap;
6728         int i;
6729
6730         if (!bset || !signs)
6731                 return -1;
6732
6733         bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset));
6734         tab = isl_tab_from_basic_set(bset);
6735         if (!bound || !tab)
6736                 goto error;
6737
6738         isl_seq_clr(bound->el, bound->size);
6739         isl_int_set_si(bound->el[0], -1);
6740
6741         snap = isl_tab_snap(tab);
6742         for (i = 0; i < n; ++i) {
6743                 int empty;
6744
6745                 isl_int_set_si(bound->el[1 + first + i], -1);
6746                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6747                         goto error;
6748                 empty = tab->empty;
6749                 isl_int_set_si(bound->el[1 + first + i], 0);
6750                 if (isl_tab_rollback(tab, snap) < 0)
6751                         goto error;
6752
6753                 if (empty) {
6754                         signs[i] = 1;
6755                         continue;
6756                 }
6757
6758                 isl_int_set_si(bound->el[1 + first + i], 1);
6759                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6760                         goto error;
6761                 empty = tab->empty;
6762                 isl_int_set_si(bound->el[1 + first + i], 0);
6763                 if (isl_tab_rollback(tab, snap) < 0)
6764                         goto error;
6765
6766                 signs[i] = empty ? -1 : 0;
6767         }
6768
6769         isl_tab_free(tab);
6770         isl_vec_free(bound);
6771         return 0;
6772 error:
6773         isl_tab_free(tab);
6774         isl_vec_free(bound);
6775         return -1;
6776 }
6777
6778 int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
6779         enum isl_dim_type type, unsigned first, unsigned n, int *signs)
6780 {
6781         if (!bset || !signs)
6782                 return -1;
6783         isl_assert(bset->ctx, first + n <= isl_basic_set_dim(bset, type),
6784                 return -1);
6785
6786         first += pos(bset->dim, type) - 1;
6787         return isl_basic_set_vars_get_sign(bset, first, n, signs);
6788 }
6789
6790 /* Check if the given map is single-valued.
6791  * We simply compute
6792  *
6793  *      M \circ M^-1
6794  *
6795  * and check if the result is a subset of the identity mapping.
6796  */
6797 int isl_map_is_single_valued(__isl_keep isl_map *map)
6798 {
6799         isl_map *test;
6800         isl_map *id;
6801         int sv;
6802
6803         test = isl_map_reverse(isl_map_copy(map));
6804         test = isl_map_apply_range(test, isl_map_copy(map));
6805
6806         id = isl_map_identity(isl_dim_range(isl_map_get_dim(map)));
6807
6808         sv = isl_map_is_subset(test, id);
6809
6810         isl_map_free(test);
6811         isl_map_free(id);
6812
6813         return sv;
6814 }
6815
6816 int isl_set_is_singleton(__isl_keep isl_set *set)
6817 {
6818         return isl_map_is_single_valued((isl_map *)set);
6819 }
6820
6821 int isl_map_is_translation(__isl_keep isl_map *map)
6822 {
6823         int ok;
6824         isl_set *delta;
6825
6826         delta = isl_map_deltas(isl_map_copy(map));
6827         ok = isl_set_is_singleton(delta);
6828         isl_set_free(delta);
6829
6830         return ok;
6831 }
6832
6833 static int unique(isl_int *p, unsigned pos, unsigned len)
6834 {
6835         if (isl_seq_first_non_zero(p, pos) != -1)
6836                 return 0;
6837         if (isl_seq_first_non_zero(p + pos + 1, len - pos - 1) != -1)
6838                 return 0;
6839         return 1;
6840 }
6841
6842 int isl_basic_set_is_box(__isl_keep isl_basic_set *bset)
6843 {
6844         int i, j;
6845         unsigned nvar;
6846         unsigned ovar;
6847
6848         if (!bset)
6849                 return -1;
6850
6851         if (isl_basic_set_dim(bset, isl_dim_div) != 0)
6852                 return 0;
6853
6854         nvar = isl_basic_set_dim(bset, isl_dim_set);
6855         ovar = isl_dim_offset(bset->dim, isl_dim_set);
6856         for (j = 0; j < nvar; ++j) {
6857                 int lower = 0, upper = 0;
6858                 for (i = 0; i < bset->n_eq; ++i) {
6859                         if (isl_int_is_zero(bset->eq[i][1 + ovar + j]))
6860                                 continue;
6861                         if (!unique(bset->eq[i] + 1 + ovar, j, nvar))
6862                                 return 0;
6863                         break;
6864                 }
6865                 if (i < bset->n_eq)
6866                         continue;
6867                 for (i = 0; i < bset->n_ineq; ++i) {
6868                         if (isl_int_is_zero(bset->ineq[i][1 + ovar + j]))
6869                                 continue;
6870                         if (!unique(bset->ineq[i] + 1 + ovar, j, nvar))
6871                                 return 0;
6872                         if (isl_int_is_pos(bset->ineq[i][1 + ovar + j]))
6873                                 lower = 1;
6874                         else
6875                                 upper = 1;
6876                 }
6877                 if (!lower || !upper)
6878                         return 0;
6879         }
6880
6881         return 1;
6882 }
6883
6884 int isl_set_is_box(__isl_keep isl_set *set)
6885 {
6886         if (!set)
6887                 return -1;
6888         if (set->n != 1)
6889                 return 0;
6890
6891         return isl_basic_set_is_box(set->p[0]);
6892 }