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
2400         row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra;
2401         old = bmap->block2.data;
2402         bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
2403                                         (bmap->extra + n) * (1 + row_size));
2404         if (!bmap->block2.data)
2405                 goto error;
2406         new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
2407         if (!new_div)
2408                 goto error;
2409         for (i = 0; i < n; ++i) {
2410                 new_div[i] = bmap->block2.data +
2411                                 (bmap->extra + i) * (1 + row_size);
2412                 isl_seq_clr(new_div[i], 1 + row_size);
2413         }
2414         for (i = 0; i < bmap->extra; ++i)
2415                 new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
2416         free(bmap->div);
2417         bmap->div = new_div;
2418         bmap->n_div += n;
2419         bmap->extra += n;
2420
2421         bmap->dim = isl_dim_drop(bmap->dim, type, first, n);
2422         if (!bmap->dim)
2423                 goto error;
2424         bmap = isl_basic_map_simplify(bmap);
2425         bmap = isl_basic_map_drop_redundant_divs(bmap);
2426         return isl_basic_map_finalize(bmap);
2427 error:
2428         isl_basic_map_free(bmap);
2429         return NULL;
2430 }
2431
2432 /* Turn the n dimensions of type type, starting at first
2433  * into existentially quantified variables.
2434  */
2435 struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
2436                 enum isl_dim_type type, unsigned first, unsigned n)
2437 {
2438         return (isl_basic_set *)isl_basic_map_project_out(
2439                         (isl_basic_map *)bset, type, first, n);
2440 }
2441
2442 /* Turn the n dimensions of type type, starting at first
2443  * into existentially quantified variables.
2444  */
2445 __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
2446                 enum isl_dim_type type, unsigned first, unsigned n)
2447 {
2448         int i;
2449
2450         if (!map)
2451                 return NULL;
2452
2453         if (n == 0)
2454                 return map;
2455
2456         isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
2457
2458         map = isl_map_cow(map);
2459         if (!map)
2460                 return NULL;
2461
2462         map->dim = isl_dim_drop(map->dim, type, first, n);
2463         if (!map->dim)
2464                 goto error;
2465
2466         for (i = 0; i < map->n; ++i) {
2467                 map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
2468                 if (!map->p[i])
2469                         goto error;
2470         }
2471
2472         return map;
2473 error:
2474         isl_map_free(map);
2475         return NULL;
2476 }
2477
2478 /* Turn the n dimensions of type type, starting at first
2479  * into existentially quantified variables.
2480  */
2481 __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
2482                 enum isl_dim_type type, unsigned first, unsigned n)
2483 {
2484         return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n);
2485 }
2486
2487 static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2488 {
2489         int i, j;
2490
2491         for (i = 0; i < n; ++i) {
2492                 j = isl_basic_map_alloc_div(bmap);
2493                 if (j < 0)
2494                         goto error;
2495                 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2496         }
2497         return bmap;
2498 error:
2499         isl_basic_map_free(bmap);
2500         return NULL;
2501 }
2502
2503 struct isl_basic_map *isl_basic_map_apply_range(
2504                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2505 {
2506         struct isl_dim *dim_result = NULL;
2507         struct isl_basic_map *bmap;
2508         unsigned n_in, n_out, n, nparam, total, pos;
2509         struct isl_dim_map *dim_map1, *dim_map2;
2510
2511         if (!bmap1 || !bmap2)
2512                 goto error;
2513
2514         dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2515                                   isl_dim_copy(bmap2->dim));
2516
2517         n_in = isl_basic_map_n_in(bmap1);
2518         n_out = isl_basic_map_n_out(bmap2);
2519         n = isl_basic_map_n_out(bmap1);
2520         nparam = isl_basic_map_n_param(bmap1);
2521
2522         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2523         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2524         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2525         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2526         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2527         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2528         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2529         isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2530         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2531         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2532         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2533
2534         bmap = isl_basic_map_alloc_dim(dim_result,
2535                         bmap1->n_div + bmap2->n_div + n,
2536                         bmap1->n_eq + bmap2->n_eq,
2537                         bmap1->n_ineq + bmap2->n_ineq);
2538         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2539         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2540         bmap = add_divs(bmap, n);
2541         bmap = isl_basic_map_simplify(bmap);
2542         bmap = isl_basic_map_drop_redundant_divs(bmap);
2543         return isl_basic_map_finalize(bmap);
2544 error:
2545         isl_basic_map_free(bmap1);
2546         isl_basic_map_free(bmap2);
2547         return NULL;
2548 }
2549
2550 struct isl_basic_set *isl_basic_set_apply(
2551                 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2552 {
2553         if (!bset || !bmap)
2554                 goto error;
2555
2556         isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
2557                     goto error);
2558
2559         return (struct isl_basic_set *)
2560                 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2561 error:
2562         isl_basic_set_free(bset);
2563         isl_basic_map_free(bmap);
2564         return NULL;
2565 }
2566
2567 struct isl_basic_map *isl_basic_map_apply_domain(
2568                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2569 {
2570         if (!bmap1 || !bmap2)
2571                 goto error;
2572
2573         isl_assert(bmap1->ctx,
2574             isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2575         isl_assert(bmap1->ctx,
2576             isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2577             goto error);
2578
2579         bmap1 = isl_basic_map_reverse(bmap1);
2580         bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2581         return isl_basic_map_reverse(bmap1);
2582 error:
2583         isl_basic_map_free(bmap1);
2584         isl_basic_map_free(bmap2);
2585         return NULL;
2586 }
2587
2588 /* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
2589  * A \cap B -> f(A) + f(B)
2590  */
2591 struct isl_basic_map *isl_basic_map_sum(
2592                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2593 {
2594         unsigned n_in, n_out, nparam, total, pos;
2595         struct isl_basic_map *bmap = NULL;
2596         struct isl_dim_map *dim_map1, *dim_map2;
2597         int i;
2598
2599         if (!bmap1 || !bmap2)
2600                 goto error;
2601
2602         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
2603                 goto error);
2604
2605         nparam = isl_basic_map_n_param(bmap1);
2606         n_in = isl_basic_map_n_in(bmap1);
2607         n_out = isl_basic_map_n_out(bmap1);
2608
2609         total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
2610         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2611         dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
2612         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2613         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
2614         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2615         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2616         isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
2617         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2618         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2619         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
2620
2621         bmap = isl_basic_map_alloc_dim(isl_dim_copy(bmap1->dim),
2622                         bmap1->n_div + bmap2->n_div + 2 * n_out,
2623                         bmap1->n_eq + bmap2->n_eq + n_out,
2624                         bmap1->n_ineq + bmap2->n_ineq);
2625         for (i = 0; i < n_out; ++i) {
2626                 int j = isl_basic_map_alloc_equality(bmap);
2627                 if (j < 0)
2628                         goto error;
2629                 isl_seq_clr(bmap->eq[j], 1+total);
2630                 isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
2631                 isl_int_set_si(bmap->eq[j][1+pos+i], 1);
2632                 isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
2633         }
2634         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2635         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2636         bmap = add_divs(bmap, 2 * n_out);
2637
2638         bmap = isl_basic_map_simplify(bmap);
2639         return isl_basic_map_finalize(bmap);
2640 error:
2641         isl_basic_map_free(bmap);
2642         isl_basic_map_free(bmap1);
2643         isl_basic_map_free(bmap2);
2644         return NULL;
2645 }
2646
2647 /* Given two maps A -> f(A) and B -> g(B), construct a map
2648  * A \cap B -> f(A) + f(B)
2649  */
2650 struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2)
2651 {
2652         struct isl_map *result;
2653         int i, j;
2654
2655         if (!map1 || !map2)
2656                 goto error;
2657
2658         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
2659
2660         result = isl_map_alloc_dim(isl_dim_copy(map1->dim),
2661                                 map1->n * map2->n, 0);
2662         if (!result)
2663                 goto error;
2664         for (i = 0; i < map1->n; ++i)
2665                 for (j = 0; j < map2->n; ++j) {
2666                         struct isl_basic_map *part;
2667                         part = isl_basic_map_sum(
2668                                     isl_basic_map_copy(map1->p[i]),
2669                                     isl_basic_map_copy(map2->p[j]));
2670                         if (isl_basic_map_is_empty(part))
2671                                 isl_basic_map_free(part);
2672                         else
2673                                 result = isl_map_add_basic_map(result, part);
2674                         if (!result)
2675                                 goto error;
2676                 }
2677         isl_map_free(map1);
2678         isl_map_free(map2);
2679         return result;
2680 error:
2681         isl_map_free(map1);
2682         isl_map_free(map2);
2683         return NULL;
2684 }
2685
2686 __isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
2687         __isl_take isl_set *set2)
2688 {
2689         return (isl_set *)isl_map_sum((isl_map *)set1, (isl_map *)set2);
2690 }
2691
2692 /* Given a basic map A -> f(A), construct A -> -f(A).
2693  */
2694 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
2695 {
2696         int i, j;
2697         unsigned off, n;
2698
2699         bmap = isl_basic_map_cow(bmap);
2700         if (!bmap)
2701                 return NULL;
2702
2703         n = isl_basic_map_dim(bmap, isl_dim_out);
2704         off = isl_basic_map_offset(bmap, isl_dim_out);
2705         for (i = 0; i < bmap->n_eq; ++i)
2706                 for (j = 0; j < n; ++j)
2707                         isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
2708         for (i = 0; i < bmap->n_ineq; ++i)
2709                 for (j = 0; j < n; ++j)
2710                         isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
2711         for (i = 0; i < bmap->n_div; ++i)
2712                 for (j = 0; j < n; ++j)
2713                         isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
2714         return isl_basic_map_finalize(bmap);
2715 }
2716
2717 /* Given a map A -> f(A), construct A -> -f(A).
2718  */
2719 struct isl_map *isl_map_neg(struct isl_map *map)
2720 {
2721         int i;
2722
2723         map = isl_map_cow(map);
2724         if (!map)
2725                 return NULL;
2726
2727         for (i = 0; i < map->n; ++i) {
2728                 map->p[i] = isl_basic_map_neg(map->p[i]);
2729                 if (!map->p[i])
2730                         goto error;
2731         }
2732
2733         return map;
2734 error:
2735         isl_map_free(map);
2736         return NULL;
2737 }
2738
2739 __isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
2740 {
2741         return (isl_set *)isl_map_neg((isl_map *)set);
2742 }
2743
2744 /* Given a basic map A -> f(A) and an integer d, construct a basic map
2745  * A -> floor(f(A)/d).
2746  */
2747 struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap,
2748                 isl_int d)
2749 {
2750         unsigned n_in, n_out, nparam, total, pos;
2751         struct isl_basic_map *result = NULL;
2752         struct isl_dim_map *dim_map;
2753         int i;
2754
2755         if (!bmap)
2756                 return NULL;
2757
2758         nparam = isl_basic_map_n_param(bmap);
2759         n_in = isl_basic_map_n_in(bmap);
2760         n_out = isl_basic_map_n_out(bmap);
2761
2762         total = nparam + n_in + n_out + bmap->n_div + n_out;
2763         dim_map = isl_dim_map_alloc(bmap->ctx, total);
2764         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
2765         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
2766         isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
2767         isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
2768
2769         result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
2770                         bmap->n_div + n_out,
2771                         bmap->n_eq, bmap->n_ineq + 2 * n_out);
2772         result = add_constraints_dim_map(result, bmap, dim_map);
2773         result = add_divs(result, n_out);
2774         for (i = 0; i < n_out; ++i) {
2775                 int j;
2776                 j = isl_basic_map_alloc_inequality(result);
2777                 if (j < 0)
2778                         goto error;
2779                 isl_seq_clr(result->ineq[j], 1+total);
2780                 isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
2781                 isl_int_set_si(result->ineq[j][1+pos+i], 1);
2782                 j = isl_basic_map_alloc_inequality(result);
2783                 if (j < 0)
2784                         goto error;
2785                 isl_seq_clr(result->ineq[j], 1+total);
2786                 isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
2787                 isl_int_set_si(result->ineq[j][1+pos+i], -1);
2788                 isl_int_sub_ui(result->ineq[j][0], d, 1);
2789         }
2790
2791         result = isl_basic_map_simplify(result);
2792         return isl_basic_map_finalize(result);
2793 error:
2794         isl_basic_map_free(result);
2795         return NULL;
2796 }
2797
2798 /* Given a map A -> f(A) and an integer d, construct a map
2799  * A -> floor(f(A)/d).
2800  */
2801 struct isl_map *isl_map_floordiv(struct isl_map *map, isl_int d)
2802 {
2803         int i;
2804
2805         map = isl_map_cow(map);
2806         if (!map)
2807                 return NULL;
2808
2809         ISL_F_CLR(map, ISL_MAP_DISJOINT);
2810         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2811         for (i = 0; i < map->n; ++i) {
2812                 map->p[i] = isl_basic_map_floordiv(map->p[i], d);
2813                 if (!map->p[i])
2814                         goto error;
2815         }
2816
2817         return map;
2818 error:
2819         isl_map_free(map);
2820         return NULL;
2821 }
2822
2823 static struct isl_basic_map *var_equal(struct isl_basic_map *bmap, unsigned pos)
2824 {
2825         int i;
2826         unsigned nparam;
2827         unsigned n_in;
2828
2829         i = isl_basic_map_alloc_equality(bmap);
2830         if (i < 0)
2831                 goto error;
2832         nparam = isl_basic_map_n_param(bmap);
2833         n_in = isl_basic_map_n_in(bmap);
2834         isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2835         isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2836         isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2837         return isl_basic_map_finalize(bmap);
2838 error:
2839         isl_basic_map_free(bmap);
2840         return NULL;
2841 }
2842
2843 /* Add a constraints to "bmap" expressing i_pos < o_pos
2844  */
2845 static struct isl_basic_map *var_less(struct isl_basic_map *bmap, unsigned pos)
2846 {
2847         int i;
2848         unsigned nparam;
2849         unsigned n_in;
2850
2851         i = isl_basic_map_alloc_inequality(bmap);
2852         if (i < 0)
2853                 goto error;
2854         nparam = isl_basic_map_n_param(bmap);
2855         n_in = isl_basic_map_n_in(bmap);
2856         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2857         isl_int_set_si(bmap->ineq[i][0], -1);
2858         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2859         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2860         return isl_basic_map_finalize(bmap);
2861 error:
2862         isl_basic_map_free(bmap);
2863         return NULL;
2864 }
2865
2866 /* Add a constraint to "bmap" expressing i_pos <= o_pos
2867  */
2868 static __isl_give isl_basic_map *var_less_or_equal(
2869         __isl_take isl_basic_map *bmap, unsigned pos)
2870 {
2871         int i;
2872         unsigned nparam;
2873         unsigned n_in;
2874
2875         i = isl_basic_map_alloc_inequality(bmap);
2876         if (i < 0)
2877                 goto error;
2878         nparam = isl_basic_map_n_param(bmap);
2879         n_in = isl_basic_map_n_in(bmap);
2880         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2881         isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2882         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2883         return isl_basic_map_finalize(bmap);
2884 error:
2885         isl_basic_map_free(bmap);
2886         return NULL;
2887 }
2888
2889 /* Add a constraints to "bmap" expressing i_pos > o_pos
2890  */
2891 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
2892 {
2893         int i;
2894         unsigned nparam;
2895         unsigned n_in;
2896
2897         i = isl_basic_map_alloc_inequality(bmap);
2898         if (i < 0)
2899                 goto error;
2900         nparam = isl_basic_map_n_param(bmap);
2901         n_in = isl_basic_map_n_in(bmap);
2902         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2903         isl_int_set_si(bmap->ineq[i][0], -1);
2904         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2905         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2906         return isl_basic_map_finalize(bmap);
2907 error:
2908         isl_basic_map_free(bmap);
2909         return NULL;
2910 }
2911
2912 /* Add a constraint to "bmap" expressing i_pos >= o_pos
2913  */
2914 static __isl_give isl_basic_map *var_more_or_equal(
2915         __isl_take isl_basic_map *bmap, unsigned pos)
2916 {
2917         int i;
2918         unsigned nparam;
2919         unsigned n_in;
2920
2921         i = isl_basic_map_alloc_inequality(bmap);
2922         if (i < 0)
2923                 goto error;
2924         nparam = isl_basic_map_n_param(bmap);
2925         n_in = isl_basic_map_n_in(bmap);
2926         isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2927         isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2928         isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2929         return isl_basic_map_finalize(bmap);
2930 error:
2931         isl_basic_map_free(bmap);
2932         return NULL;
2933 }
2934
2935 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
2936 {
2937         int i;
2938         struct isl_basic_map *bmap;
2939         bmap = isl_basic_map_alloc_dim(dim, 0, n_equal, 0);
2940         if (!bmap)
2941                 return NULL;
2942         for (i = 0; i < n_equal && bmap; ++i)
2943                 bmap = var_equal(bmap, i);
2944         return isl_basic_map_finalize(bmap);
2945 }
2946
2947 /* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
2948  */
2949 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
2950 {
2951         int i;
2952         struct isl_basic_map *bmap;
2953         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2954         if (!bmap)
2955                 return NULL;
2956         for (i = 0; i < pos && bmap; ++i)
2957                 bmap = var_equal(bmap, i);
2958         if (bmap)
2959                 bmap = var_less(bmap, pos);
2960         return isl_basic_map_finalize(bmap);
2961 }
2962
2963 /* Return a relation on of dimension "dim" expressing i_[0..pos] <<= o_[0..pos]
2964  */
2965 __isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
2966         __isl_take isl_dim *dim, unsigned pos)
2967 {
2968         int i;
2969         isl_basic_map *bmap;
2970
2971         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2972         for (i = 0; i < pos; ++i)
2973                 bmap = var_equal(bmap, i);
2974         bmap = var_less_or_equal(bmap, pos);
2975         return isl_basic_map_finalize(bmap);
2976 }
2977
2978 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
2979  */
2980 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
2981 {
2982         int i;
2983         struct isl_basic_map *bmap;
2984         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
2985         if (!bmap)
2986                 return NULL;
2987         for (i = 0; i < pos && bmap; ++i)
2988                 bmap = var_equal(bmap, i);
2989         if (bmap)
2990                 bmap = var_more(bmap, pos);
2991         return isl_basic_map_finalize(bmap);
2992 }
2993
2994 /* Return a relation on of dimension "dim" expressing i_[0..pos] >>= o_[0..pos]
2995  */
2996 __isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
2997         __isl_take isl_dim *dim, unsigned pos)
2998 {
2999         int i;
3000         isl_basic_map *bmap;
3001
3002         bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
3003         for (i = 0; i < pos; ++i)
3004                 bmap = var_equal(bmap, i);
3005         bmap = var_more_or_equal(bmap, pos);
3006         return isl_basic_map_finalize(bmap);
3007 }
3008
3009 static __isl_give isl_map *map_lex_lte_first(__isl_take isl_dim *dims,
3010         unsigned n, int equal)
3011 {
3012         struct isl_map *map;
3013         int i;
3014
3015         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3016
3017         for (i = 0; i + 1 < n; ++i)
3018                 map = isl_map_add_basic_map(map,
3019                                   isl_basic_map_less_at(isl_dim_copy(dims), i));
3020         if (n > 0) {
3021                 if (equal)
3022                         map = isl_map_add_basic_map(map,
3023                               isl_basic_map_less_or_equal_at(dims, n - 1));
3024                 else
3025                         map = isl_map_add_basic_map(map,
3026                               isl_basic_map_less_at(dims, n - 1));
3027         } else
3028                 isl_dim_free(dims);
3029
3030         return map;
3031 }
3032
3033 static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
3034 {
3035         if (!dims)
3036                 return NULL;
3037         return map_lex_lte_first(dims, dims->n_out, equal);
3038 }
3039
3040 __isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_dim *dim, unsigned n)
3041 {
3042         return map_lex_lte_first(dim, n, 0);
3043 }
3044
3045 __isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n)
3046 {
3047         return map_lex_lte_first(dim, n, 1);
3048 }
3049
3050 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
3051 {
3052         return map_lex_lte(isl_dim_map(set_dim), 0);
3053 }
3054
3055 __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
3056 {
3057         return map_lex_lte(isl_dim_map(set_dim), 1);
3058 }
3059
3060 static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims,
3061         unsigned n, int equal)
3062 {
3063         struct isl_map *map;
3064         int i;
3065
3066         map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
3067
3068         for (i = 0; i + 1 < n; ++i)
3069                 map = isl_map_add_basic_map(map,
3070                                   isl_basic_map_more_at(isl_dim_copy(dims), i));
3071         if (n > 0) {
3072                 if (equal)
3073                         map = isl_map_add_basic_map(map,
3074                               isl_basic_map_more_or_equal_at(dims, n - 1));
3075                 else
3076                         map = isl_map_add_basic_map(map,
3077                               isl_basic_map_more_at(dims, n - 1));
3078         } else
3079                 isl_dim_free(dims);
3080
3081         return map;
3082 }
3083
3084 static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
3085 {
3086         if (!dims)
3087                 return NULL;
3088         return map_lex_gte_first(dims, dims->n_out, equal);
3089 }
3090
3091 __isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_dim *dim, unsigned n)
3092 {
3093         return map_lex_gte_first(dim, n, 0);
3094 }
3095
3096 __isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n)
3097 {
3098         return map_lex_gte_first(dim, n, 1);
3099 }
3100
3101 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
3102 {
3103         return map_lex_gte(isl_dim_map(set_dim), 0);
3104 }
3105
3106 __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim)
3107 {
3108         return map_lex_gte(isl_dim_map(set_dim), 1);
3109 }
3110
3111 struct isl_basic_map *isl_basic_map_from_basic_set(
3112                 struct isl_basic_set *bset, struct isl_dim *dim)
3113 {
3114         struct isl_basic_map *bmap;
3115
3116         bset = isl_basic_set_cow(bset);
3117         if (!bset || !dim)
3118                 goto error;
3119
3120         isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
3121         isl_dim_free(bset->dim);
3122         bmap = (struct isl_basic_map *) bset;
3123         bmap->dim = dim;
3124         return isl_basic_map_finalize(bmap);
3125 error:
3126         isl_basic_set_free(bset);
3127         isl_dim_free(dim);
3128         return NULL;
3129 }
3130
3131 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
3132 {
3133         if (!bmap)
3134                 goto error;
3135         if (bmap->dim->n_in == 0)
3136                 return (struct isl_basic_set *)bmap;
3137         bmap = isl_basic_map_cow(bmap);
3138         if (!bmap)
3139                 goto error;
3140         bmap->dim = isl_dim_cow(bmap->dim);
3141         if (!bmap->dim)
3142                 goto error;
3143         bmap->dim->n_out += bmap->dim->n_in;
3144         bmap->dim->n_in = 0;
3145         bmap = isl_basic_map_finalize(bmap);
3146         return (struct isl_basic_set *)bmap;
3147 error:
3148         isl_basic_map_free(bmap);
3149         return NULL;
3150 }
3151
3152 /* For a div d = floor(f/m), add the constraints
3153  *
3154  *              f - m d >= 0
3155  *              -(f-(n-1)) + m d >= 0
3156  *
3157  * Note that the second constraint is the negation of
3158  *
3159  *              f - m d >= n
3160  */
3161 int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
3162         unsigned pos, isl_int *div)
3163 {
3164         int i, j;
3165         unsigned total = isl_basic_map_total_dim(bmap);
3166
3167         i = isl_basic_map_alloc_inequality(bmap);
3168         if (i < 0)
3169                 return -1;
3170         isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
3171         isl_int_neg(bmap->ineq[i][1 + pos], div[0]);
3172
3173         j = isl_basic_map_alloc_inequality(bmap);
3174         if (j < 0)
3175                 return -1;
3176         isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
3177         isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][1 + pos]);
3178         isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
3179         return j;
3180 }
3181
3182 int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
3183         unsigned pos, isl_int *div)
3184 {
3185         return isl_basic_map_add_div_constraints_var((isl_basic_map *)bset,
3186                                                         pos, div);
3187 }
3188
3189 int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
3190 {
3191         unsigned total = isl_basic_map_total_dim(bmap);
3192         unsigned div_pos = total - bmap->n_div + div;
3193
3194         return isl_basic_map_add_div_constraints_var(bmap, div_pos,
3195                                                         bmap->div[div]);
3196 }
3197
3198 struct isl_basic_set *isl_basic_map_underlying_set(
3199                 struct isl_basic_map *bmap)
3200 {
3201         if (!bmap)
3202                 goto error;
3203         if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
3204                 return (struct isl_basic_set *)bmap;
3205         bmap = isl_basic_map_cow(bmap);
3206         if (!bmap)
3207                 goto error;
3208         bmap->dim = isl_dim_underlying(bmap->dim, bmap->n_div);
3209         if (!bmap->dim)
3210                 goto error;
3211         bmap->extra -= bmap->n_div;
3212         bmap->n_div = 0;
3213         bmap = isl_basic_map_finalize(bmap);
3214         return (struct isl_basic_set *)bmap;
3215 error:
3216         return NULL;
3217 }
3218
3219 __isl_give isl_basic_set *isl_basic_set_underlying_set(
3220                 __isl_take isl_basic_set *bset)
3221 {
3222         return isl_basic_map_underlying_set((isl_basic_map *)bset);
3223 }
3224
3225 struct isl_basic_map *isl_basic_map_overlying_set(
3226         struct isl_basic_set *bset, struct isl_basic_map *like)
3227 {
3228         struct isl_basic_map *bmap;
3229         struct isl_ctx *ctx;
3230         unsigned total;
3231         int i;
3232
3233         if (!bset || !like)
3234                 goto error;
3235         ctx = bset->ctx;
3236         isl_assert(ctx, bset->n_div == 0, goto error);
3237         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
3238         isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
3239                         goto error);
3240         if (isl_dim_equal(bset->dim, like->dim) && like->n_div == 0) {
3241                 isl_basic_map_free(like);
3242                 return (struct isl_basic_map *)bset;
3243         }
3244         bset = isl_basic_set_cow(bset);
3245         if (!bset)
3246                 goto error;
3247         total = bset->dim->n_out + bset->extra;
3248         bmap = (struct isl_basic_map *)bset;
3249         isl_dim_free(bmap->dim);
3250         bmap->dim = isl_dim_copy(like->dim);
3251         if (!bmap->dim)
3252                 goto error;
3253         bmap->n_div = like->n_div;
3254         bmap->extra += like->n_div;
3255         if (bmap->extra) {
3256                 unsigned ltotal;
3257                 ltotal = total - bmap->extra + like->extra;
3258                 if (ltotal > total)
3259                         ltotal = total;
3260                 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
3261                                         bmap->extra * (1 + 1 + total));
3262                 if (isl_blk_is_error(bmap->block2))
3263                         goto error;
3264                 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
3265                                                 bmap->extra);
3266                 if (!bmap->div)
3267                         goto error;
3268                 for (i = 0; i < bmap->extra; ++i)
3269                         bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
3270                 for (i = 0; i < like->n_div; ++i) {
3271                         isl_seq_cpy(bmap->div[i], like->div[i], 1 + 1 + ltotal);
3272                         isl_seq_clr(bmap->div[i]+1+1+ltotal, total - ltotal);
3273                 }
3274                 bmap = isl_basic_map_extend_constraints(bmap,
3275                                                         0, 2 * like->n_div);
3276                 for (i = 0; i < like->n_div; ++i) {
3277                         if (isl_int_is_zero(bmap->div[i][0]))
3278                                 continue;
3279                         if (isl_basic_map_add_div_constraints(bmap, i) < 0)
3280                                 goto error;
3281                 }
3282         }
3283         isl_basic_map_free(like);
3284         bmap = isl_basic_map_simplify(bmap);
3285         bmap = isl_basic_map_finalize(bmap);
3286         return bmap;
3287 error:
3288         isl_basic_map_free(like);
3289         isl_basic_set_free(bset);
3290         return NULL;
3291 }
3292
3293 struct isl_basic_set *isl_basic_set_from_underlying_set(
3294         struct isl_basic_set *bset, struct isl_basic_set *like)
3295 {
3296         return (struct isl_basic_set *)
3297                 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
3298 }
3299
3300 struct isl_set *isl_set_from_underlying_set(
3301         struct isl_set *set, struct isl_basic_set *like)
3302 {
3303         int i;
3304
3305         if (!set || !like)
3306                 goto error;
3307         isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
3308                     goto error);
3309         if (isl_dim_equal(set->dim, like->dim) && like->n_div == 0) {
3310                 isl_basic_set_free(like);
3311                 return set;
3312         }
3313         set = isl_set_cow(set);
3314         if (!set)
3315                 goto error;
3316         for (i = 0; i < set->n; ++i) {
3317                 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
3318                                                       isl_basic_set_copy(like));
3319                 if (!set->p[i])
3320                         goto error;
3321         }
3322         isl_dim_free(set->dim);
3323         set->dim = isl_dim_copy(like->dim);
3324         if (!set->dim)
3325                 goto error;
3326         isl_basic_set_free(like);
3327         return set;
3328 error:
3329         isl_basic_set_free(like);
3330         isl_set_free(set);
3331         return NULL;
3332 }
3333
3334 struct isl_set *isl_map_underlying_set(struct isl_map *map)
3335 {
3336         int i;
3337
3338         map = isl_map_cow(map);
3339         if (!map)
3340                 return NULL;
3341         map->dim = isl_dim_cow(map->dim);
3342         if (!map->dim)
3343                 goto error;
3344
3345         for (i = 1; i < map->n; ++i)
3346                 isl_assert(map->ctx, map->p[0]->n_div == map->p[i]->n_div,
3347                                 goto error);
3348         for (i = 0; i < map->n; ++i) {
3349                 map->p[i] = (struct isl_basic_map *)
3350                                 isl_basic_map_underlying_set(map->p[i]);
3351                 if (!map->p[i])
3352                         goto error;
3353         }
3354         if (map->n == 0)
3355                 map->dim = isl_dim_underlying(map->dim, 0);
3356         else {
3357                 isl_dim_free(map->dim);
3358                 map->dim = isl_dim_copy(map->p[0]->dim);
3359         }
3360         if (!map->dim)
3361                 goto error;
3362         return (struct isl_set *)map;
3363 error:
3364         isl_map_free(map);
3365         return NULL;
3366 }
3367
3368 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
3369 {
3370         return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
3371 }
3372
3373 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
3374 {
3375         struct isl_basic_set *domain;
3376         unsigned n_in;
3377         unsigned n_out;
3378         if (!bmap)
3379                 return NULL;
3380         n_in = isl_basic_map_n_in(bmap);
3381         n_out = isl_basic_map_n_out(bmap);
3382         domain = isl_basic_set_from_basic_map(bmap);
3383         return isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
3384 }
3385
3386 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
3387 {
3388         return isl_basic_map_domain(isl_basic_map_reverse(bmap));
3389 }
3390
3391 struct isl_set *isl_map_range(struct isl_map *map)
3392 {
3393         int i;
3394         struct isl_set *set;
3395
3396         if (!map)
3397                 goto error;
3398         if (isl_map_dim(map, isl_dim_in) == 0)
3399                 return (isl_set *)map;
3400
3401         map = isl_map_cow(map);
3402         if (!map)
3403                 goto error;
3404
3405         set = (struct isl_set *) map;
3406         set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
3407         if (!set->dim)
3408                 goto error;
3409         for (i = 0; i < map->n; ++i) {
3410                 set->p[i] = isl_basic_map_range(map->p[i]);
3411                 if (!set->p[i])
3412                         goto error;
3413         }
3414         ISL_F_CLR(set, ISL_MAP_DISJOINT);
3415         ISL_F_CLR(set, ISL_SET_NORMALIZED);
3416         return set;
3417 error:
3418         isl_map_free(map);
3419         return NULL;
3420 }
3421
3422 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3423 {
3424         int i;
3425         struct isl_map *map = NULL;
3426
3427         set = isl_set_cow(set);
3428         if (!set || !dim)
3429                 goto error;
3430         isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3431         map = (struct isl_map *)set;
3432         for (i = 0; i < set->n; ++i) {
3433                 map->p[i] = isl_basic_map_from_basic_set(
3434                                 set->p[i], isl_dim_copy(dim));
3435                 if (!map->p[i])
3436                         goto error;
3437         }
3438         isl_dim_free(map->dim);
3439         map->dim = dim;
3440         return map;
3441 error:
3442         isl_dim_free(dim);
3443         isl_set_free(set);
3444         return NULL;
3445 }
3446
3447 struct isl_map *isl_map_from_range(struct isl_set *set)
3448 {
3449         return (struct isl_map *)set;
3450 }
3451
3452 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
3453 {
3454         return isl_map_reverse(isl_map_from_range(set));;
3455 }
3456
3457 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
3458         __isl_take isl_set *range)
3459 {
3460         return isl_map_product(isl_map_from_domain(domain),
3461                                isl_map_from_range(range));
3462 }
3463
3464 struct isl_set *isl_set_from_map(struct isl_map *map)
3465 {
3466         int i;
3467         struct isl_set *set = NULL;
3468
3469         if (!map)
3470                 return NULL;
3471         map = isl_map_cow(map);
3472         if (!map)
3473                 return NULL;
3474         map->dim = isl_dim_cow(map->dim);
3475         if (!map->dim)
3476                 goto error;
3477         map->dim->n_out += map->dim->n_in;
3478         map->dim->n_in = 0;
3479         set = (struct isl_set *)map;
3480         for (i = 0; i < map->n; ++i) {
3481                 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3482                 if (!set->p[i])
3483                         goto error;
3484         }
3485         return set;
3486 error:
3487         isl_map_free(map);
3488         return NULL;
3489 }
3490
3491 struct isl_map *isl_map_alloc_dim(struct isl_dim *dim, int n, unsigned flags)
3492 {
3493         struct isl_map *map;
3494
3495         if (!dim)
3496                 return NULL;
3497         isl_assert(dim->ctx, n >= 0, return NULL);
3498         map = isl_alloc(dim->ctx, struct isl_map,
3499                         sizeof(struct isl_map) +
3500                         (n - 1) * sizeof(struct isl_basic_map *));
3501         if (!map)
3502                 goto error;
3503
3504         map->ctx = dim->ctx;
3505         isl_ctx_ref(map->ctx);
3506         map->ref = 1;
3507         map->size = n;
3508         map->n = 0;
3509         map->dim = dim;
3510         map->flags = flags;
3511         return map;
3512 error:
3513         isl_dim_free(dim);
3514         return NULL;
3515 }
3516
3517 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3518                 unsigned nparam, unsigned in, unsigned out, int n,
3519                 unsigned flags)
3520 {
3521         struct isl_map *map;
3522         struct isl_dim *dims;
3523
3524         dims = isl_dim_alloc(ctx, nparam, in, out);
3525         if (!dims)
3526                 return NULL;
3527
3528         map = isl_map_alloc_dim(dims, n, flags);
3529         return map;
3530 }
3531
3532 struct isl_basic_map *isl_basic_map_empty(struct isl_dim *dim)
3533 {
3534         struct isl_basic_map *bmap;
3535         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
3536         bmap = isl_basic_map_set_to_empty(bmap);
3537         return bmap;
3538 }
3539
3540 struct isl_basic_set *isl_basic_set_empty(struct isl_dim *dim)
3541 {
3542         struct isl_basic_set *bset;
3543         bset = isl_basic_set_alloc_dim(dim, 0, 1, 0);
3544         bset = isl_basic_set_set_to_empty(bset);
3545         return bset;
3546 }
3547
3548 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3549 {
3550         struct isl_basic_map *bmap;
3551         if (!model)
3552                 return NULL;
3553         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3554         bmap = isl_basic_map_set_to_empty(bmap);
3555         return bmap;
3556 }
3557
3558 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3559 {
3560         struct isl_basic_map *bmap;
3561         if (!model)
3562                 return NULL;
3563         bmap = isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3564         bmap = isl_basic_map_set_to_empty(bmap);
3565         return bmap;
3566 }
3567
3568 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3569 {
3570         struct isl_basic_set *bset;
3571         if (!model)
3572                 return NULL;
3573         bset = isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 1, 0);
3574         bset = isl_basic_set_set_to_empty(bset);
3575         return bset;
3576 }
3577
3578 struct isl_basic_map *isl_basic_map_universe(struct isl_dim *dim)
3579 {
3580         struct isl_basic_map *bmap;
3581         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
3582         return bmap;
3583 }
3584
3585 struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim)
3586 {
3587         struct isl_basic_set *bset;
3588         bset = isl_basic_set_alloc_dim(dim, 0, 0, 0);
3589         return bset;
3590 }
3591
3592 __isl_give isl_basic_map *isl_basic_map_universe_like(
3593                 __isl_keep isl_basic_map *model)
3594 {
3595         if (!model)
3596                 return NULL;
3597         return isl_basic_map_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3598 }
3599
3600 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3601 {
3602         if (!model)
3603                 return NULL;
3604         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3605 }
3606
3607 __isl_give isl_basic_set *isl_basic_set_universe_like_set(
3608         __isl_keep isl_set *model)
3609 {
3610         if (!model)
3611                 return NULL;
3612         return isl_basic_set_alloc_dim(isl_dim_copy(model->dim), 0, 0, 0);
3613 }
3614
3615 struct isl_map *isl_map_empty(struct isl_dim *dim)
3616 {
3617         return isl_map_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3618 }
3619
3620 struct isl_map *isl_map_empty_like(struct isl_map *model)
3621 {
3622         if (!model)
3623                 return NULL;
3624         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3625 }
3626
3627 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3628 {
3629         if (!model)
3630                 return NULL;
3631         return isl_map_alloc_dim(isl_dim_copy(model->dim), 0, ISL_MAP_DISJOINT);
3632 }
3633
3634 struct isl_set *isl_set_empty(struct isl_dim *dim)
3635 {
3636         return isl_set_alloc_dim(dim, 0, ISL_MAP_DISJOINT);
3637 }
3638
3639 struct isl_set *isl_set_empty_like(struct isl_set *model)
3640 {
3641         if (!model)
3642                 return NULL;
3643         return isl_set_empty(isl_dim_copy(model->dim));
3644 }
3645
3646 struct isl_map *isl_map_universe(struct isl_dim *dim)
3647 {
3648         struct isl_map *map;
3649         if (!dim)
3650                 return NULL;
3651         map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3652         map = isl_map_add_basic_map(map, isl_basic_map_universe(dim));
3653         return map;
3654 }
3655
3656 struct isl_set *isl_set_universe(struct isl_dim *dim)
3657 {
3658         struct isl_set *set;
3659         if (!dim)
3660                 return NULL;
3661         set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT);
3662         set = isl_set_add_basic_set(set, isl_basic_set_universe(dim));
3663         return set;
3664 }
3665
3666 __isl_give isl_set *isl_set_universe_like(__isl_keep isl_set *model)
3667 {
3668         if (!model)
3669                 return NULL;
3670         return isl_set_universe(isl_dim_copy(model->dim));
3671 }
3672
3673 struct isl_map *isl_map_dup(struct isl_map *map)
3674 {
3675         int i;
3676         struct isl_map *dup;
3677
3678         if (!map)
3679                 return NULL;
3680         dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags);
3681         for (i = 0; i < map->n; ++i)
3682                 dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i]));
3683         return dup;
3684 }
3685
3686 __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
3687                                                 __isl_take isl_basic_map *bmap)
3688 {
3689         if (!bmap || !map)
3690                 goto error;
3691         if (isl_basic_map_fast_is_empty(bmap)) {
3692                 isl_basic_map_free(bmap);
3693                 return map;
3694         }
3695         isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3696         isl_assert(map->ctx, map->n < map->size, goto error);
3697         map->p[map->n] = bmap;
3698         map->n++;
3699         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3700         return map;
3701 error:
3702         if (map)
3703                 isl_map_free(map);
3704         if (bmap)
3705                 isl_basic_map_free(bmap);
3706         return NULL;
3707 }
3708
3709 void isl_map_free(struct isl_map *map)
3710 {
3711         int i;
3712
3713         if (!map)
3714                 return;
3715
3716         if (--map->ref > 0)
3717                 return;
3718
3719         isl_ctx_deref(map->ctx);
3720         for (i = 0; i < map->n; ++i)
3721                 isl_basic_map_free(map->p[i]);
3722         isl_dim_free(map->dim);
3723         free(map);
3724 }
3725
3726 struct isl_map *isl_map_extend(struct isl_map *base,
3727                 unsigned nparam, unsigned n_in, unsigned n_out)
3728 {
3729         int i;
3730
3731         base = isl_map_cow(base);
3732         if (!base)
3733                 return NULL;
3734
3735         base->dim = isl_dim_extend(base->dim, nparam, n_in, n_out);
3736         if (!base->dim)
3737                 goto error;
3738         for (i = 0; i < base->n; ++i) {
3739                 base->p[i] = isl_basic_map_extend_dim(base->p[i],
3740                                 isl_dim_copy(base->dim), 0, 0, 0);
3741                 if (!base->p[i])
3742                         goto error;
3743         }
3744         return base;
3745 error:
3746         isl_map_free(base);
3747         return NULL;
3748 }
3749
3750 struct isl_set *isl_set_extend(struct isl_set *base,
3751                 unsigned nparam, unsigned dim)
3752 {
3753         return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3754                                                         nparam, 0, dim);
3755 }
3756
3757 static struct isl_basic_map *isl_basic_map_fix_pos_si(
3758         struct isl_basic_map *bmap, unsigned pos, int value)
3759 {
3760         int j;
3761
3762         bmap = isl_basic_map_cow(bmap);
3763         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3764         j = isl_basic_map_alloc_equality(bmap);
3765         if (j < 0)
3766                 goto error;
3767         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3768         isl_int_set_si(bmap->eq[j][pos], -1);
3769         isl_int_set_si(bmap->eq[j][0], value);
3770         bmap = isl_basic_map_simplify(bmap);
3771         return isl_basic_map_finalize(bmap);
3772 error:
3773         isl_basic_map_free(bmap);
3774         return NULL;
3775 }
3776
3777 static __isl_give isl_basic_map *isl_basic_map_fix_pos(
3778         __isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
3779 {
3780         int j;
3781
3782         bmap = isl_basic_map_cow(bmap);
3783         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3784         j = isl_basic_map_alloc_equality(bmap);
3785         if (j < 0)
3786                 goto error;
3787         isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap));
3788         isl_int_set_si(bmap->eq[j][pos], -1);
3789         isl_int_set(bmap->eq[j][0], value);
3790         bmap = isl_basic_map_simplify(bmap);
3791         return isl_basic_map_finalize(bmap);
3792 error:
3793         isl_basic_map_free(bmap);
3794         return NULL;
3795 }
3796
3797 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
3798                 enum isl_dim_type type, unsigned pos, int value)
3799 {
3800         if (!bmap)
3801                 return NULL;
3802         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3803         return isl_basic_map_fix_pos_si(bmap,
3804                 isl_basic_map_offset(bmap, type) + pos, value);
3805 error:
3806         isl_basic_map_free(bmap);
3807         return NULL;
3808 }
3809
3810 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
3811                 enum isl_dim_type type, unsigned pos, isl_int value)
3812 {
3813         if (!bmap)
3814                 return NULL;
3815         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3816         return isl_basic_map_fix_pos(bmap,
3817                 isl_basic_map_offset(bmap, type) + pos, value);
3818 error:
3819         isl_basic_map_free(bmap);
3820         return NULL;
3821 }
3822
3823 struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset,
3824                 enum isl_dim_type type, unsigned pos, int value)
3825 {
3826         return (struct isl_basic_set *)
3827                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3828                                         type, pos, value);
3829 }
3830
3831 __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
3832                 enum isl_dim_type type, unsigned pos, isl_int value)
3833 {
3834         return (struct isl_basic_set *)
3835                 isl_basic_map_fix((struct isl_basic_map *)bset,
3836                                         type, pos, value);
3837 }
3838
3839 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3840                 unsigned input, int value)
3841 {
3842         return isl_basic_map_fix_si(bmap, isl_dim_in, input, value);
3843 }
3844
3845 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3846                 unsigned dim, int value)
3847 {
3848         return (struct isl_basic_set *)
3849                 isl_basic_map_fix_si((struct isl_basic_map *)bset,
3850                                         isl_dim_set, dim, value);
3851 }
3852
3853 struct isl_map *isl_map_fix_si(struct isl_map *map,
3854                 enum isl_dim_type type, unsigned pos, int value)
3855 {
3856         int i;
3857
3858         map = isl_map_cow(map);
3859         if (!map)
3860                 return NULL;
3861
3862         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3863         for (i = 0; i < map->n; ++i) {
3864                 map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
3865                 if (!map->p[i])
3866                         goto error;
3867         }
3868         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3869         return map;
3870 error:
3871         isl_map_free(map);
3872         return NULL;
3873 }
3874
3875 __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
3876                 enum isl_dim_type type, unsigned pos, int value)
3877 {
3878         return (struct isl_set *)
3879                 isl_map_fix_si((struct isl_map *)set, type, pos, value);
3880 }
3881
3882 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
3883                 enum isl_dim_type type, unsigned pos, isl_int value)
3884 {
3885         int i;
3886
3887         map = isl_map_cow(map);
3888         if (!map)
3889                 return NULL;
3890
3891         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3892         for (i = 0; i < map->n; ++i) {
3893                 map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value);
3894                 if (!map->p[i])
3895                         goto error;
3896         }
3897         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3898         return map;
3899 error:
3900         isl_map_free(map);
3901         return NULL;
3902 }
3903
3904 __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
3905                 enum isl_dim_type type, unsigned pos, isl_int value)
3906 {
3907         return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value);
3908 }
3909
3910 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3911                 unsigned input, int value)
3912 {
3913         return isl_map_fix_si(map, isl_dim_in, input, value);
3914 }
3915
3916 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3917 {
3918         return (struct isl_set *)
3919                 isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
3920 }
3921
3922 __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
3923                 __isl_take isl_basic_map *bmap,
3924                 enum isl_dim_type type, unsigned pos, int value)
3925 {
3926         int j;
3927
3928         if (!bmap)
3929                 return NULL;
3930         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
3931         pos += isl_basic_map_offset(bmap, type);
3932         bmap = isl_basic_map_cow(bmap);
3933         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
3934         j = isl_basic_map_alloc_inequality(bmap);
3935         if (j < 0)
3936                 goto error;
3937         isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
3938         isl_int_set_si(bmap->ineq[j][pos], 1);
3939         isl_int_set_si(bmap->ineq[j][0], -value);
3940         bmap = isl_basic_map_simplify(bmap);
3941         return isl_basic_map_finalize(bmap);
3942 error:
3943         isl_basic_map_free(bmap);
3944         return NULL;
3945 }
3946
3947 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3948         unsigned dim, isl_int value)
3949 {
3950         int j;
3951
3952         bset = isl_basic_set_cow(bset);
3953         bset = isl_basic_set_extend_constraints(bset, 0, 1);
3954         j = isl_basic_set_alloc_inequality(bset);
3955         if (j < 0)
3956                 goto error;
3957         isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3958         isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3959         isl_int_neg(bset->ineq[j][0], value);
3960         bset = isl_basic_set_simplify(bset);
3961         return isl_basic_set_finalize(bset);
3962 error:
3963         isl_basic_set_free(bset);
3964         return NULL;
3965 }
3966
3967 __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
3968                 enum isl_dim_type type, unsigned pos, int value)
3969 {
3970         int i;
3971
3972         map = isl_map_cow(map);
3973         if (!map)
3974                 return NULL;
3975
3976         isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
3977         for (i = 0; i < map->n; ++i) {
3978                 map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
3979                                                          type, pos, value);
3980                 if (!map->p[i])
3981                         goto error;
3982         }
3983         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
3984         return map;
3985 error:
3986         isl_map_free(map);
3987         return NULL;
3988 }
3989
3990 __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
3991                 enum isl_dim_type type, unsigned pos, int value)
3992 {
3993         return (struct isl_set *)
3994                 isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
3995 }
3996
3997 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3998                                         isl_int value)
3999 {
4000         int i;
4001
4002         set = isl_set_cow(set);
4003         if (!set)
4004                 return NULL;
4005
4006         isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
4007         for (i = 0; i < set->n; ++i) {
4008                 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
4009                 if (!set->p[i])
4010                         goto error;
4011         }
4012         return set;
4013 error:
4014         isl_set_free(set);
4015         return NULL;
4016 }
4017
4018 struct isl_map *isl_map_reverse(struct isl_map *map)
4019 {
4020         int i;
4021
4022         map = isl_map_cow(map);
4023         if (!map)
4024                 return NULL;
4025
4026         map->dim = isl_dim_reverse(map->dim);
4027         if (!map->dim)
4028                 goto error;
4029         for (i = 0; i < map->n; ++i) {
4030                 map->p[i] = isl_basic_map_reverse(map->p[i]);
4031                 if (!map->p[i])
4032                         goto error;
4033         }
4034         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4035         return map;
4036 error:
4037         isl_map_free(map);
4038         return NULL;
4039 }
4040
4041 static struct isl_map *isl_basic_map_partial_lexopt(
4042                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4043                 struct isl_set **empty, int max)
4044 {
4045         if (!bmap)
4046                 goto error;
4047         if (bmap->ctx->opt->pip == ISL_PIP_PIP)
4048                 return isl_pip_basic_map_lexopt(bmap, dom, empty, max);
4049         else
4050                 return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max);
4051 error:
4052         isl_basic_map_free(bmap);
4053         isl_basic_set_free(dom);
4054         if (empty)
4055                 *empty = NULL;
4056         return NULL;
4057 }
4058
4059 struct isl_map *isl_basic_map_partial_lexmax(
4060                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4061                 struct isl_set **empty)
4062 {
4063         return isl_basic_map_partial_lexopt(bmap, dom, empty, 1);
4064 }
4065
4066 struct isl_map *isl_basic_map_partial_lexmin(
4067                 struct isl_basic_map *bmap, struct isl_basic_set *dom,
4068                 struct isl_set **empty)
4069 {
4070         return isl_basic_map_partial_lexopt(bmap, dom, empty, 0);
4071 }
4072
4073 struct isl_set *isl_basic_set_partial_lexmin(
4074                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4075                 struct isl_set **empty)
4076 {
4077         return (struct isl_set *)
4078                 isl_basic_map_partial_lexmin((struct isl_basic_map *)bset,
4079                         dom, empty);
4080 }
4081
4082 struct isl_set *isl_basic_set_partial_lexmax(
4083                 struct isl_basic_set *bset, struct isl_basic_set *dom,
4084                 struct isl_set **empty)
4085 {
4086         return (struct isl_set *)
4087                 isl_basic_map_partial_lexmax((struct isl_basic_map *)bset,
4088                         dom, empty);
4089 }
4090
4091 /* Given a basic map "bmap", compute the lexicograhically minimal
4092  * (or maximal) image element for each domain element in dom.
4093  * Set *empty to those elements in dom that do not have an image element.
4094  *
4095  * We first make sure the basic sets in dom are disjoint and then
4096  * simply collect the results over each of the basic sets separately.
4097  * We could probably improve the efficiency a bit by moving the union
4098  * domain down into the parametric integer programming.
4099  */
4100 static __isl_give isl_map *basic_map_partial_lexopt(
4101                 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
4102                 __isl_give isl_set **empty, int max)
4103 {
4104         int i;
4105         struct isl_map *res;
4106
4107         dom = isl_set_make_disjoint(dom);
4108         if (!dom)
4109                 goto error;
4110
4111         if (isl_set_fast_is_empty(dom)) {
4112                 res = isl_map_empty_like_basic_map(bmap);
4113                 *empty = isl_set_empty_like(dom);
4114                 isl_set_free(dom);
4115                 isl_basic_map_free(bmap);
4116                 return res;
4117         }
4118
4119         res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4120                         isl_basic_set_copy(dom->p[0]), empty, max);
4121
4122         for (i = 1; i < dom->n; ++i) {
4123                 struct isl_map *res_i;
4124                 struct isl_set *empty_i;
4125
4126                 res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap),
4127                                 isl_basic_set_copy(dom->p[i]), &empty_i, max);
4128
4129                 res = isl_map_union_disjoint(res, res_i);
4130                 *empty = isl_set_union_disjoint(*empty, empty_i);
4131         }
4132
4133         isl_set_free(dom);
4134         isl_basic_map_free(bmap);
4135         return res;
4136 error:
4137         *empty = NULL;
4138         isl_set_free(dom);
4139         isl_basic_map_free(bmap);
4140         return NULL;
4141 }
4142
4143 /* Given a map "map", compute the lexicograhically minimal
4144  * (or maximal) image element for each domain element in dom.
4145  * Set *empty to those elements in dom that do not have an image element.
4146  *
4147  * We first compute the lexicographically minimal or maximal element
4148  * in the first basic map.  This results in a partial solution "res"
4149  * and a subset "todo" of dom that still need to be handled.
4150  * We then consider each of the remaining maps in "map" and successively
4151  * improve both "res" and "todo".
4152  *
4153  * Let res^k and todo^k be the results after k steps and let i = k + 1.
4154  * Assume we are computing the lexicographical maximum.
4155  * We first intersect basic map i with a relation that maps elements
4156  * to elements that are lexicographically larger than the image elements
4157  * in res^k and the compute the maximum image element of this intersection.
4158  * The result ("better") corresponds to those image elements in basic map i
4159  * that are better than what we had before.  The remainder ("keep") are the
4160  * domain elements for which the image element in res_k was better.
4161  * We also compute the lexicographical maximum of basic map i in todo^k.
4162  * res^i is the result of the operation + better + those elements in
4163  *              res^k that we should keep
4164  * todo^i is the remainder of the maximum operation on todo^k.
4165  */
4166 static __isl_give isl_map *isl_map_partial_lexopt(
4167                 __isl_take isl_map *map, __isl_take isl_set *dom,
4168                 __isl_give isl_set **empty, int max)
4169 {
4170         int i;
4171         struct isl_map *res;
4172         struct isl_set *todo;
4173
4174         if (!map || !dom)
4175                 goto error;
4176
4177         if (isl_map_fast_is_empty(map)) {
4178                 if (empty)
4179                         *empty = dom;
4180                 else
4181                         isl_set_free(dom);
4182                 return map;
4183         }
4184
4185         res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]),
4186                                         isl_set_copy(dom), &todo, max);
4187
4188         for (i = 1; i < map->n; ++i) {
4189                 struct isl_map *lt;
4190                 struct isl_map *better;
4191                 struct isl_set *keep;
4192                 struct isl_map *res_i;
4193                 struct isl_set *todo_i;
4194                 struct isl_dim *dim = isl_map_get_dim(res);
4195
4196                 dim = isl_dim_range(dim);
4197                 if (max)
4198                         lt = isl_map_lex_lt(dim);
4199                 else
4200                         lt = isl_map_lex_gt(dim);
4201                 lt = isl_map_apply_range(isl_map_copy(res), lt);
4202                 lt = isl_map_intersect(lt,
4203                         isl_map_from_basic_map(isl_basic_map_copy(map->p[i])));
4204                 better = isl_map_partial_lexopt(lt,
4205                         isl_map_domain(isl_map_copy(res)),
4206                         &keep, max);
4207
4208                 res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]),
4209                                                 todo, &todo_i, max);
4210
4211                 res = isl_map_intersect_domain(res, keep);
4212                 res = isl_map_union_disjoint(res, res_i);
4213                 res = isl_map_union_disjoint(res, better);
4214                 todo = todo_i;
4215         }
4216
4217         isl_set_free(dom);
4218         isl_map_free(map);
4219
4220         if (empty)
4221                 *empty = todo;
4222         else
4223                 isl_set_free(todo);
4224
4225         return res;
4226 error:
4227         if (empty)
4228                 *empty = NULL;
4229         isl_set_free(dom);
4230         isl_map_free(map);
4231         return NULL;
4232 }
4233
4234 __isl_give isl_map *isl_map_partial_lexmax(
4235                 __isl_take isl_map *map, __isl_take isl_set *dom,
4236                 __isl_give isl_set **empty)
4237 {
4238         return isl_map_partial_lexopt(map, dom, empty, 1);
4239 }
4240
4241 __isl_give isl_map *isl_map_partial_lexmin(
4242                 __isl_take isl_map *map, __isl_take isl_set *dom,
4243                 __isl_give isl_set **empty)
4244 {
4245         return isl_map_partial_lexopt(map, dom, empty, 0);
4246 }
4247
4248 __isl_give isl_set *isl_set_partial_lexmin(
4249                 __isl_take isl_set *set, __isl_take isl_set *dom,
4250                 __isl_give isl_set **empty)
4251 {
4252         return (struct isl_set *)
4253                 isl_map_partial_lexmin((struct isl_map *)set,
4254                         dom, empty);
4255 }
4256
4257 __isl_give isl_set *isl_set_partial_lexmax(
4258                 __isl_take isl_set *set, __isl_take isl_set *dom,
4259                 __isl_give isl_set **empty)
4260 {
4261         return (struct isl_set *)
4262                 isl_map_partial_lexmax((struct isl_map *)set,
4263                         dom, empty);
4264 }
4265
4266 __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max)
4267 {
4268         struct isl_basic_set *dom = NULL;
4269         struct isl_dim *dom_dim;
4270
4271         if (!bmap)
4272                 goto error;
4273         dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim));
4274         dom = isl_basic_set_universe(dom_dim);
4275         return isl_basic_map_partial_lexopt(bmap, dom, NULL, max);
4276 error:
4277         isl_basic_map_free(bmap);
4278         return NULL;
4279 }
4280
4281 __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap)
4282 {
4283         return isl_basic_map_lexopt(bmap, 0);
4284 }
4285
4286 __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
4287 {
4288         return isl_basic_map_lexopt(bmap, 1);
4289 }
4290
4291 __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
4292 {
4293         return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset);
4294 }
4295
4296 __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
4297 {
4298         return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset);
4299 }
4300
4301 __isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max)
4302 {
4303         struct isl_set *dom = NULL;
4304         struct isl_dim *dom_dim;
4305
4306         if (!map)
4307                 goto error;
4308         dom_dim = isl_dim_domain(isl_dim_copy(map->dim));
4309         dom = isl_set_universe(dom_dim);
4310         return isl_map_partial_lexopt(map, dom, NULL, max);
4311 error:
4312         isl_map_free(map);
4313         return NULL;
4314 }
4315
4316 __isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map)
4317 {
4318         return isl_map_lexopt(map, 0);
4319 }
4320
4321 __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
4322 {
4323         return isl_map_lexopt(map, 1);
4324 }
4325
4326 __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
4327 {
4328         return (isl_set *)isl_map_lexmin((isl_map *)set);
4329 }
4330
4331 __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
4332 {
4333         return (isl_set *)isl_map_lexmax((isl_map *)set);
4334 }
4335
4336 static struct isl_map *isl_map_reset_dim(struct isl_map *map,
4337         struct isl_dim *dim)
4338 {
4339         int i;
4340
4341         if (!map || !dim)
4342                 goto error;
4343
4344         for (i = 0; i < map->n; ++i) {
4345                 isl_dim_free(map->p[i]->dim);
4346                 map->p[i]->dim = isl_dim_copy(dim);
4347         }
4348         isl_dim_free(map->dim);
4349         map->dim = dim;
4350
4351         return map;
4352 error:
4353         isl_map_free(map);
4354         isl_dim_free(dim);
4355         return NULL;
4356 }
4357
4358 static struct isl_set *isl_set_reset_dim(struct isl_set *set,
4359         struct isl_dim *dim)
4360 {
4361         return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
4362 }
4363
4364 /* Apply a preimage specified by "mat" on the parameters of "bset".
4365  * bset is assumed to have only parameters and divs.
4366  */
4367 static struct isl_basic_set *basic_set_parameter_preimage(
4368         struct isl_basic_set *bset, struct isl_mat *mat)
4369 {
4370         unsigned nparam;
4371
4372         if (!bset || !mat)
4373                 goto error;
4374
4375         bset->dim = isl_dim_cow(bset->dim);
4376         if (!bset->dim)
4377                 goto error;
4378
4379         nparam = isl_basic_set_dim(bset, isl_dim_param);
4380
4381         isl_assert(bset->ctx, mat->n_row == 1 + nparam, goto error);
4382
4383         bset->dim->nparam = 0;
4384         bset->dim->n_out = nparam;
4385         bset = isl_basic_set_preimage(bset, mat);
4386         if (bset) {
4387                 bset->dim->nparam = bset->dim->n_out;
4388                 bset->dim->n_out = 0;
4389         }
4390         return bset;
4391 error:
4392         isl_mat_free(mat);
4393         isl_basic_set_free(bset);
4394         return NULL;
4395 }
4396
4397 /* Apply a preimage specified by "mat" on the parameters of "set".
4398  * set is assumed to have only parameters and divs.
4399  */
4400 static struct isl_set *set_parameter_preimage(
4401         struct isl_set *set, struct isl_mat *mat)
4402 {
4403         struct isl_dim *dim = NULL;
4404         unsigned nparam;
4405
4406         if (!set || !mat)
4407                 goto error;
4408
4409         dim = isl_dim_copy(set->dim);
4410         dim = isl_dim_cow(dim);
4411         if (!dim)
4412                 goto error;
4413
4414         nparam = isl_set_dim(set, isl_dim_param);
4415
4416         isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error);
4417
4418         dim->nparam = 0;
4419         dim->n_out = nparam;
4420         isl_set_reset_dim(set, dim);
4421         set = isl_set_preimage(set, mat);
4422         if (!set)
4423                 goto error2;
4424         dim = isl_dim_copy(set->dim);
4425         dim = isl_dim_cow(dim);
4426         if (!dim)
4427                 goto error2;
4428         dim->nparam = dim->n_out;
4429         dim->n_out = 0;
4430         isl_set_reset_dim(set, dim);
4431         return set;
4432 error:
4433         isl_dim_free(dim);
4434         isl_mat_free(mat);
4435 error2:
4436         isl_set_free(set);
4437         return NULL;
4438 }
4439
4440 /* Intersect the basic set "bset" with the affine space specified by the
4441  * equalities in "eq".
4442  */
4443 static struct isl_basic_set *basic_set_append_equalities(
4444         struct isl_basic_set *bset, struct isl_mat *eq)
4445 {
4446         int i, k;
4447         unsigned len;
4448
4449         if (!bset || !eq)
4450                 goto error;
4451
4452         bset = isl_basic_set_extend_dim(bset, isl_dim_copy(bset->dim), 0,
4453                                         eq->n_row, 0);
4454         if (!bset)
4455                 goto error;
4456
4457         len = 1 + isl_dim_total(bset->dim) + bset->extra;
4458         for (i = 0; i < eq->n_row; ++i) {
4459                 k = isl_basic_set_alloc_equality(bset);
4460                 if (k < 0)
4461                         goto error;
4462                 isl_seq_cpy(bset->eq[k], eq->row[i], eq->n_col);
4463                 isl_seq_clr(bset->eq[k] + eq->n_col, len - eq->n_col);
4464         }
4465         isl_mat_free(eq);
4466
4467         bset = isl_basic_set_gauss(bset, NULL);
4468         bset = isl_basic_set_finalize(bset);
4469
4470         return bset;
4471 error:
4472         isl_mat_free(eq);
4473         isl_basic_set_free(bset);
4474         return NULL;
4475 }
4476
4477 /* Intersect the set "set" with the affine space specified by the
4478  * equalities in "eq".
4479  */
4480 static struct isl_set *set_append_equalities(struct isl_set *set,
4481         struct isl_mat *eq)
4482 {
4483         int i;
4484
4485         if (!set || !eq)
4486                 goto error;
4487
4488         for (i = 0; i < set->n; ++i) {
4489                 set->p[i] = basic_set_append_equalities(set->p[i],
4490                                         isl_mat_copy(eq));
4491                 if (!set->p[i])
4492                         goto error;
4493         }
4494         isl_mat_free(eq);
4495         return set;
4496 error:
4497         isl_mat_free(eq);
4498         isl_set_free(set);
4499         return NULL;
4500 }
4501
4502 /* Project the given basic set onto its parameter domain, possibly introducing
4503  * new, explicit, existential variables in the constraints.
4504  * The input has parameters and (possibly implicit) existential variables.
4505  * The output has the same parameters, but only
4506  * explicit existentially quantified variables.
4507  *
4508  * The actual projection is performed by pip, but pip doesn't seem
4509  * to like equalities very much, so we first remove the equalities
4510  * among the parameters by performing a variable compression on
4511  * the parameters.  Afterward, an inverse transformation is performed
4512  * and the equalities among the parameters are inserted back in.
4513  */
4514 static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
4515 {
4516         int i, j;
4517         struct isl_mat *eq;
4518         struct isl_mat *T, *T2;
4519         struct isl_set *set;
4520         unsigned nparam, n_div;
4521
4522         bset = isl_basic_set_cow(bset);
4523         if (!bset)
4524                 return NULL;
4525
4526         if (bset->n_eq == 0)
4527                 return isl_basic_set_lexmin(bset);
4528
4529         isl_basic_set_gauss(bset, NULL);
4530
4531         nparam = isl_basic_set_dim(bset, isl_dim_param);
4532         n_div = isl_basic_set_dim(bset, isl_dim_div);
4533
4534         for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) {
4535                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + j]))
4536                         ++i;
4537         }
4538         if (i == bset->n_eq)
4539                 return isl_basic_set_lexmin(bset);
4540
4541         eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
4542                 0, 1 + nparam);
4543         eq = isl_mat_cow(eq);
4544         T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
4545         if (T && T->n_col == 0) {
4546                 isl_mat_free(T);
4547                 isl_mat_free(T2);
4548                 isl_mat_free(eq);
4549                 bset = isl_basic_set_set_to_empty(bset);
4550                 return isl_set_from_basic_set(bset);
4551         }
4552         bset = basic_set_parameter_preimage(bset, T);
4553
4554         set = isl_basic_set_lexmin(bset);
4555         set = set_parameter_preimage(set, T2);
4556         set = set_append_equalities(set, eq);
4557         return set;
4558 }
4559
4560 /* Compute an explicit representation for all the existentially
4561  * quantified variables.
4562  * The input and output dimensions are first turned into parameters.
4563  * compute_divs then returns a map with the same parameters and
4564  * no input or output dimensions and the dimension specification
4565  * is reset to that of the input.
4566  */
4567 static struct isl_map *compute_divs(struct isl_basic_map *bmap)
4568 {
4569         struct isl_basic_set *bset;
4570         struct isl_set *set;
4571         struct isl_map *map;
4572         struct isl_dim *dim, *orig_dim = NULL;
4573         unsigned         nparam;
4574         unsigned         n_in;
4575         unsigned         n_out;
4576
4577         bmap = isl_basic_map_cow(bmap);
4578         if (!bmap)
4579                 return NULL;
4580
4581         nparam = isl_basic_map_dim(bmap, isl_dim_param);
4582         n_in = isl_basic_map_dim(bmap, isl_dim_in);
4583         n_out = isl_basic_map_dim(bmap, isl_dim_out);
4584         dim = isl_dim_set_alloc(bmap->ctx, nparam + n_in + n_out, 0);
4585         if (!dim)
4586                 goto error;
4587
4588         orig_dim = bmap->dim;
4589         bmap->dim = dim;
4590         bset = (struct isl_basic_set *)bmap;
4591
4592         set = parameter_compute_divs(bset);
4593         map = (struct isl_map *)set;
4594         map = isl_map_reset_dim(map, orig_dim);
4595
4596         return map;
4597 error:
4598         isl_basic_map_free(bmap);
4599         return NULL;
4600 }
4601
4602 static int basic_map_divs_known(__isl_keep isl_basic_map *bmap)
4603 {
4604         int i;
4605         unsigned off;
4606
4607         if (!bmap)
4608                 return -1;
4609
4610         off = isl_dim_total(bmap->dim);
4611         for (i = 0; i < bmap->n_div; ++i) {
4612                 if (isl_int_is_zero(bmap->div[i][0]))
4613                         return 0;
4614                 isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]),
4615                                 return -1);
4616         }
4617         return 1;
4618 }
4619
4620 static int map_divs_known(__isl_keep isl_map *map)
4621 {
4622         int i;
4623
4624         if (!map)
4625                 return -1;
4626
4627         for (i = 0; i < map->n; ++i) {
4628                 int known = basic_map_divs_known(map->p[i]);
4629                 if (known <= 0)
4630                         return known;
4631         }
4632
4633         return 1;
4634 }
4635
4636 /* If bmap contains any unknown divs, then compute explicit
4637  * expressions for them.  However, this computation may be
4638  * quite expensive, so first try to remove divs that aren't
4639  * strictly needed.
4640  */
4641 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
4642 {
4643         int i;
4644         int known;
4645         struct isl_map *map;
4646
4647         known = basic_map_divs_known(bmap);
4648         if (known < 0)
4649                 goto error;
4650         if (known)
4651                 return isl_map_from_basic_map(bmap);
4652
4653         bmap = isl_basic_map_drop_redundant_divs(bmap);
4654
4655         known = basic_map_divs_known(bmap);
4656         if (known < 0)
4657                 goto error;
4658         if (known)
4659                 return isl_map_from_basic_map(bmap);
4660
4661         map = compute_divs(bmap);
4662         return map;
4663 error:
4664         isl_basic_map_free(bmap);
4665         return NULL;
4666 }
4667
4668 struct isl_map *isl_map_compute_divs(struct isl_map *map)
4669 {
4670         int i;
4671         int known;
4672         struct isl_map *res;
4673
4674         if (!map)
4675                 return NULL;
4676         if (map->n == 0)
4677                 return map;
4678
4679         known = map_divs_known(map);
4680         if (known < 0) {
4681                 isl_map_free(map);
4682                 return NULL;
4683         }
4684         if (known)
4685                 return map;
4686
4687         res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
4688         for (i = 1 ; i < map->n; ++i) {
4689                 struct isl_map *r2;
4690                 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
4691                 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
4692                         res = isl_map_union_disjoint(res, r2);
4693                 else
4694                         res = isl_map_union(res, r2);
4695         }
4696         isl_map_free(map);
4697
4698         return res;
4699 }
4700
4701 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
4702 {
4703         return (struct isl_set *)
4704                 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
4705 }
4706
4707 struct isl_set *isl_set_compute_divs(struct isl_set *set)
4708 {
4709         return (struct isl_set *)
4710                 isl_map_compute_divs((struct isl_map *)set);
4711 }
4712
4713 struct isl_set *isl_map_domain(struct isl_map *map)
4714 {
4715         int i;
4716         struct isl_set *set;
4717
4718         if (!map)
4719                 goto error;
4720
4721         map = isl_map_cow(map);
4722         if (!map)
4723                 return NULL;
4724
4725         set = (struct isl_set *)map;
4726         set->dim = isl_dim_domain(set->dim);
4727         if (!set->dim)
4728                 goto error;
4729         for (i = 0; i < map->n; ++i) {
4730                 set->p[i] = isl_basic_map_domain(map->p[i]);
4731                 if (!set->p[i])
4732                         goto error;
4733         }
4734         ISL_F_CLR(set, ISL_MAP_DISJOINT);
4735         ISL_F_CLR(set, ISL_SET_NORMALIZED);
4736         return set;
4737 error:
4738         isl_map_free(map);
4739         return NULL;
4740 }
4741
4742 struct isl_map *isl_map_union_disjoint(
4743                         struct isl_map *map1, struct isl_map *map2)
4744 {
4745         int i;
4746         unsigned flags = 0;
4747         struct isl_map *map = NULL;
4748
4749         if (!map1 || !map2)
4750                 goto error;
4751
4752         if (map1->n == 0) {
4753                 isl_map_free(map1);
4754                 return map2;
4755         }
4756         if (map2->n == 0) {
4757                 isl_map_free(map2);
4758                 return map1;
4759         }
4760
4761         isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4762
4763         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
4764             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
4765                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4766
4767         map = isl_map_alloc_dim(isl_dim_copy(map1->dim),
4768                                 map1->n + map2->n, flags);
4769         if (!map)
4770                 goto error;
4771         for (i = 0; i < map1->n; ++i) {
4772                 map = isl_map_add_basic_map(map,
4773                                   isl_basic_map_copy(map1->p[i]));
4774                 if (!map)
4775                         goto error;
4776         }
4777         for (i = 0; i < map2->n; ++i) {
4778                 map = isl_map_add_basic_map(map,
4779                                   isl_basic_map_copy(map2->p[i]));
4780                 if (!map)
4781                         goto error;
4782         }
4783         isl_map_free(map1);
4784         isl_map_free(map2);
4785         return map;
4786 error:
4787         isl_map_free(map);
4788         isl_map_free(map1);
4789         isl_map_free(map2);
4790         return NULL;
4791 }
4792
4793 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
4794 {
4795         map1 = isl_map_union_disjoint(map1, map2);
4796         if (!map1)
4797                 return NULL;
4798         if (map1->n > 1)
4799                 ISL_F_CLR(map1, ISL_MAP_DISJOINT);
4800         return map1;
4801 }
4802
4803 struct isl_set *isl_set_union_disjoint(
4804                         struct isl_set *set1, struct isl_set *set2)
4805 {
4806         return (struct isl_set *)
4807                 isl_map_union_disjoint(
4808                         (struct isl_map *)set1, (struct isl_map *)set2);
4809 }
4810
4811 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
4812 {
4813         return (struct isl_set *)
4814                 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
4815 }
4816
4817 struct isl_map *isl_map_intersect_range(
4818                 struct isl_map *map, struct isl_set *set)
4819 {
4820         unsigned flags = 0;
4821         struct isl_map *result;
4822         int i, j;
4823
4824         if (!map || !set)
4825                 goto error;
4826
4827         if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
4828             ISL_F_ISSET(set, ISL_MAP_DISJOINT))
4829                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
4830
4831         result = isl_map_alloc_dim(isl_dim_copy(map->dim),
4832                                         map->n * set->n, flags);
4833         if (!result)
4834                 goto error;
4835         for (i = 0; i < map->n; ++i)
4836                 for (j = 0; j < set->n; ++j) {
4837                         result = isl_map_add_basic_map(result,
4838                             isl_basic_map_intersect_range(
4839                                 isl_basic_map_copy(map->p[i]),
4840                                 isl_basic_set_copy(set->p[j])));
4841                         if (!result)
4842                                 goto error;
4843                 }
4844         isl_map_free(map);
4845         isl_set_free(set);
4846         return result;
4847 error:
4848         isl_map_free(map);
4849         isl_set_free(set);
4850         return NULL;
4851 }
4852
4853 struct isl_map *isl_map_intersect_domain(
4854                 struct isl_map *map, struct isl_set *set)
4855 {
4856         return isl_map_reverse(
4857                 isl_map_intersect_range(isl_map_reverse(map), set));
4858 }
4859
4860 struct isl_map *isl_map_apply_domain(
4861                 struct isl_map *map1, struct isl_map *map2)
4862 {
4863         if (!map1 || !map2)
4864                 goto error;
4865         map1 = isl_map_reverse(map1);
4866         map1 = isl_map_apply_range(map1, map2);
4867         return isl_map_reverse(map1);
4868 error:
4869         isl_map_free(map1);
4870         isl_map_free(map2);
4871         return NULL;
4872 }
4873
4874 struct isl_map *isl_map_apply_range(
4875                 struct isl_map *map1, struct isl_map *map2)
4876 {
4877         struct isl_dim *dim_result;
4878         struct isl_map *result;
4879         int i, j;
4880
4881         if (!map1 || !map2)
4882                 goto error;
4883
4884         dim_result = isl_dim_join(isl_dim_copy(map1->dim),
4885                                   isl_dim_copy(map2->dim));
4886
4887         result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
4888         if (!result)
4889                 goto error;
4890         for (i = 0; i < map1->n; ++i)
4891                 for (j = 0; j < map2->n; ++j) {
4892                         result = isl_map_add_basic_map(result,
4893                             isl_basic_map_apply_range(
4894                                 isl_basic_map_copy(map1->p[i]),
4895                                 isl_basic_map_copy(map2->p[j])));
4896                         if (!result)
4897                                 goto error;
4898                 }
4899         isl_map_free(map1);
4900         isl_map_free(map2);
4901         if (result && result->n <= 1)
4902                 ISL_F_SET(result, ISL_MAP_DISJOINT);
4903         return result;
4904 error:
4905         isl_map_free(map1);
4906         isl_map_free(map2);
4907         return NULL;
4908 }
4909
4910 /*
4911  * returns range - domain
4912  */
4913 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
4914 {
4915         isl_dim *dims;
4916         struct isl_basic_set *bset;
4917         unsigned dim;
4918         unsigned nparam;
4919         int i;
4920
4921         if (!bmap)
4922                 goto error;
4923         dim = isl_basic_map_n_in(bmap);
4924         nparam = isl_basic_map_n_param(bmap);
4925         isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
4926         bset = isl_basic_set_from_basic_map(bmap);
4927         bset = isl_basic_set_cow(bset);
4928         dims = isl_basic_set_get_dim(bset);
4929         dims = isl_dim_add(dims, isl_dim_set, dim);
4930         bset = isl_basic_set_extend_dim(bset, dims, 0, dim, 0);
4931         bset = isl_basic_set_swap_vars(bset, 2*dim);
4932         for (i = 0; i < dim; ++i) {
4933                 int j = isl_basic_map_alloc_equality(
4934                                             (struct isl_basic_map *)bset);
4935                 if (j < 0)
4936                         goto error;
4937                 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
4938                 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
4939                 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
4940                 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
4941         }
4942         return isl_basic_set_project_out(bset, isl_dim_set, dim, 2*dim);
4943 error:
4944         isl_basic_map_free(bmap);
4945         return NULL;
4946 }
4947
4948 /*
4949  * returns range - domain
4950  */
4951 struct isl_set *isl_map_deltas(struct isl_map *map)
4952 {
4953         int i;
4954         isl_dim *dim;
4955         struct isl_set *result;
4956
4957         if (!map)
4958                 return NULL;
4959
4960         isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
4961         dim = isl_map_get_dim(map);
4962         dim = isl_dim_domain(dim);
4963         result = isl_set_alloc_dim(dim, map->n, map->flags);
4964         if (!result)
4965                 goto error;
4966         for (i = 0; i < map->n; ++i)
4967                 result = isl_set_add_basic_set(result,
4968                           isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
4969         isl_map_free(map);
4970         return result;
4971 error:
4972         isl_map_free(map);
4973         return NULL;
4974 }
4975
4976 static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
4977 {
4978         struct isl_basic_map *bmap;
4979         unsigned nparam;
4980         unsigned dim;
4981         int i;
4982
4983         if (!dims)
4984                 return NULL;
4985
4986         nparam = dims->nparam;
4987         dim = dims->n_out;
4988         bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
4989         if (!bmap)
4990                 goto error;
4991
4992         for (i = 0; i < dim; ++i) {
4993                 int j = isl_basic_map_alloc_equality(bmap);
4994                 if (j < 0)
4995                         goto error;
4996                 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
4997                 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
4998                 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
4999         }
5000         return isl_basic_map_finalize(bmap);
5001 error:
5002         isl_basic_map_free(bmap);
5003         return NULL;
5004 }
5005
5006 struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
5007 {
5008         struct isl_dim *dim = isl_dim_map(set_dim);
5009         if (!dim)
5010                 return NULL;
5011         return basic_map_identity(dim);
5012 }
5013
5014 struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
5015 {
5016         if (!model || !model->dim)
5017                 return NULL;
5018         isl_assert(model->ctx,
5019                         model->dim->n_in == model->dim->n_out, return NULL);
5020         return basic_map_identity(isl_dim_copy(model->dim));
5021 }
5022
5023 static struct isl_map *map_identity(struct isl_dim *dim)
5024 {
5025         struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT);
5026         return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim)));
5027 }
5028
5029 struct isl_map *isl_map_identity(struct isl_dim *set_dim)
5030 {
5031         struct isl_dim *dim = isl_dim_map(set_dim);
5032         if (!dim)
5033                 return NULL;
5034         return map_identity(dim);
5035 }
5036
5037 struct isl_map *isl_map_identity_like(struct isl_map *model)
5038 {
5039         if (!model || !model->dim)
5040                 return NULL;
5041         isl_assert(model->ctx,
5042                         model->dim->n_in == model->dim->n_out, return NULL);
5043         return map_identity(isl_dim_copy(model->dim));
5044 }
5045
5046 struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model)
5047 {
5048         if (!model || !model->dim)
5049                 return NULL;
5050         isl_assert(model->ctx,
5051                         model->dim->n_in == model->dim->n_out, return NULL);
5052         return map_identity(isl_dim_copy(model->dim));
5053 }
5054
5055 /* Construct a basic set with all set dimensions having only non-negative
5056  * values.
5057  */
5058 struct isl_basic_set *isl_basic_set_positive_orthant(struct isl_dim *dims)
5059 {
5060         int i;
5061         unsigned nparam;
5062         unsigned dim;
5063         struct isl_basic_set *bset;
5064
5065         if (!dims)
5066                 return NULL;
5067         nparam = dims->nparam;
5068         dim = dims->n_out;
5069         bset = isl_basic_set_alloc_dim(dims, 0, 0, dim);
5070         if (!bset)
5071                 return NULL;
5072         for (i = 0; i < dim; ++i) {
5073                 int k = isl_basic_set_alloc_inequality(bset);
5074                 if (k < 0)
5075                         goto error;
5076                 isl_seq_clr(bset->ineq[k], 1 + isl_basic_set_total_dim(bset));
5077                 isl_int_set_si(bset->ineq[k][1 + nparam + i], 1);
5078         }
5079         return bset;
5080 error:
5081         isl_basic_set_free(bset);
5082         return NULL;
5083 }
5084
5085 __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set,
5086         enum isl_dim_type type, unsigned first, unsigned n)
5087 {
5088         int i;
5089         isl_basic_set *nonneg = NULL;
5090         isl_basic_set *neg = NULL;
5091
5092         if (!set)
5093                 return NULL;
5094         if (n == 0)
5095                 return set;
5096
5097         isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error);
5098
5099         for (i = 0; i < n; ++i) {
5100                 int k;
5101
5102                 neg = NULL;
5103                 nonneg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5104                 k = isl_basic_set_alloc_inequality(nonneg);
5105                 if (k < 0)
5106                         goto error;
5107                 isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg));
5108                 isl_int_set_si(nonneg->ineq[k][pos(set->dim, type) + first + i], 1);
5109
5110                 neg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
5111                 k = isl_basic_set_alloc_inequality(neg);
5112                 if (k < 0)
5113                         goto error;
5114                 isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg));
5115                 isl_int_set_si(neg->ineq[k][0], -1);
5116                 isl_int_set_si(neg->ineq[k][pos(set->dim, type) + first + i], -1);
5117
5118                 set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg));
5119         }
5120
5121         return set;
5122 error:
5123         isl_basic_set_free(nonneg);
5124         isl_basic_set_free(neg);
5125         isl_set_free(set);
5126         return NULL;
5127 }
5128
5129 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
5130 {
5131         return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
5132 }
5133
5134 int isl_basic_map_is_subset(
5135                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5136 {
5137         int is_subset;
5138         struct isl_map *map1;
5139         struct isl_map *map2;
5140
5141         if (!bmap1 || !bmap2)
5142                 return -1;
5143
5144         map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
5145         map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
5146
5147         is_subset = isl_map_is_subset(map1, map2);
5148
5149         isl_map_free(map1);
5150         isl_map_free(map2);
5151
5152         return is_subset;
5153 }
5154
5155 int isl_basic_map_is_equal(
5156                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5157 {
5158         int is_subset;
5159
5160         if (!bmap1 || !bmap2)
5161                 return -1;
5162         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5163         if (is_subset != 1)
5164                 return is_subset;
5165         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5166         return is_subset;
5167 }
5168
5169 int isl_basic_set_is_equal(
5170                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5171 {
5172         return isl_basic_map_is_equal(
5173                 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
5174 }
5175
5176 int isl_map_is_empty(struct isl_map *map)
5177 {
5178         int i;
5179         int is_empty;
5180
5181         if (!map)
5182                 return -1;
5183         for (i = 0; i < map->n; ++i) {
5184                 is_empty = isl_basic_map_is_empty(map->p[i]);
5185                 if (is_empty < 0)
5186                         return -1;
5187                 if (!is_empty)
5188                         return 0;
5189         }
5190         return 1;
5191 }
5192
5193 int isl_map_fast_is_empty(struct isl_map *map)
5194 {
5195         return map ? map->n == 0 : -1;
5196 }
5197
5198 int isl_set_fast_is_empty(struct isl_set *set)
5199 {
5200         return set ? set->n == 0 : -1;
5201 }
5202
5203 int isl_set_is_empty(struct isl_set *set)
5204 {
5205         return isl_map_is_empty((struct isl_map *)set);
5206 }
5207
5208 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
5209 {
5210         int is_subset;
5211
5212         if (!map1 || !map2)
5213                 return -1;
5214         is_subset = isl_map_is_subset(map1, map2);
5215         if (is_subset != 1)
5216                 return is_subset;
5217         is_subset = isl_map_is_subset(map2, map1);
5218         return is_subset;
5219 }
5220
5221 int isl_basic_map_is_strict_subset(
5222                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5223 {
5224         int is_subset;
5225
5226         if (!bmap1 || !bmap2)
5227                 return -1;
5228         is_subset = isl_basic_map_is_subset(bmap1, bmap2);
5229         if (is_subset != 1)
5230                 return is_subset;
5231         is_subset = isl_basic_map_is_subset(bmap2, bmap1);
5232         if (is_subset == -1)
5233                 return is_subset;
5234         return !is_subset;
5235 }
5236
5237 int isl_map_is_strict_subset(struct isl_map *map1, struct isl_map *map2)
5238 {
5239         int is_subset;
5240
5241         if (!map1 || !map2)
5242                 return -1;
5243         is_subset = isl_map_is_subset(map1, map2);
5244         if (is_subset != 1)
5245                 return is_subset;
5246         is_subset = isl_map_is_subset(map2, map1);
5247         if (is_subset == -1)
5248                 return is_subset;
5249         return !is_subset;
5250 }
5251
5252 int isl_set_is_strict_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
5253 {
5254         return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
5255 }
5256
5257 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
5258 {
5259         if (!bmap)
5260                 return -1;
5261         return bmap->n_eq == 0 && bmap->n_ineq == 0;
5262 }
5263
5264 int isl_basic_set_is_universe(struct isl_basic_set *bset)
5265 {
5266         if (!bset)
5267                 return -1;
5268         return bset->n_eq == 0 && bset->n_ineq == 0;
5269 }
5270
5271 int isl_map_fast_is_universe(__isl_keep isl_map *map)
5272 {
5273         if (!map)
5274                 return -1;
5275
5276         return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
5277 }
5278
5279 int isl_set_fast_is_universe(__isl_keep isl_set *set)
5280 {
5281         return isl_map_fast_is_universe((isl_map *) set);
5282 }
5283
5284 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
5285 {
5286         struct isl_basic_set *bset = NULL;
5287         struct isl_vec *sample = NULL;
5288         int empty;
5289         unsigned total;
5290
5291         if (!bmap)
5292                 return -1;
5293
5294         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
5295                 return 1;
5296
5297         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
5298                 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
5299                 copy = isl_basic_map_convex_hull(copy);
5300                 empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
5301                 isl_basic_map_free(copy);
5302                 return empty;
5303         }
5304
5305         total = 1 + isl_basic_map_total_dim(bmap);
5306         if (bmap->sample && bmap->sample->size == total) {
5307                 int contains = isl_basic_map_contains(bmap, bmap->sample);
5308                 if (contains < 0)
5309                         return -1;
5310                 if (contains)
5311                         return 0;
5312         }
5313         isl_vec_free(bmap->sample);
5314         bmap->sample = NULL;
5315         bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
5316         if (!bset)
5317                 return -1;
5318         sample = isl_basic_set_sample_vec(bset);
5319         if (!sample)
5320                 return -1;
5321         empty = sample->size == 0;
5322         isl_vec_free(bmap->sample);
5323         bmap->sample = sample;
5324         if (empty)
5325                 ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
5326
5327         return empty;
5328 }
5329
5330 int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
5331 {
5332         if (!bmap)
5333                 return -1;
5334         return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
5335 }
5336
5337 int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
5338 {
5339         if (!bset)
5340                 return -1;
5341         return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
5342 }
5343
5344 int isl_basic_set_is_empty(struct isl_basic_set *bset)
5345 {
5346         return isl_basic_map_is_empty((struct isl_basic_map *)bset);
5347 }
5348
5349 struct isl_map *isl_basic_map_union(
5350         struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
5351 {
5352         struct isl_map *map;
5353         if (!bmap1 || !bmap2)
5354                 return NULL;
5355
5356         isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
5357
5358         map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0);
5359         if (!map)
5360                 goto error;
5361         map = isl_map_add_basic_map(map, bmap1);
5362         map = isl_map_add_basic_map(map, bmap2);
5363         return map;
5364 error:
5365         isl_basic_map_free(bmap1);
5366         isl_basic_map_free(bmap2);
5367         return NULL;
5368 }
5369
5370 struct isl_set *isl_basic_set_union(
5371                 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
5372 {
5373         return (struct isl_set *)isl_basic_map_union(
5374                                             (struct isl_basic_map *)bset1,
5375                                             (struct isl_basic_map *)bset2);
5376 }
5377
5378 /* Order divs such that any div only depends on previous divs */
5379 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
5380 {
5381         int i;
5382         unsigned off;
5383
5384         if (!bmap)
5385                 return NULL;
5386
5387         off = isl_dim_total(bmap->dim);
5388
5389         for (i = 0; i < bmap->n_div; ++i) {
5390                 int pos;
5391                 if (isl_int_is_zero(bmap->div[i][0]))
5392                         continue;
5393                 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
5394                                                             bmap->n_div-i);
5395                 if (pos == -1)
5396                         continue;
5397                 isl_basic_map_swap_div(bmap, i, i + pos);
5398                 --i;
5399         }
5400         return bmap;
5401 }
5402
5403 struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
5404 {
5405         return (struct isl_basic_set *)
5406                 isl_basic_map_order_divs((struct isl_basic_map *)bset);
5407 }
5408
5409 __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
5410 {
5411         int i;
5412
5413         if (!map)
5414                 return 0;
5415
5416         for (i = 0; i < map->n; ++i) {
5417                 map->p[i] = isl_basic_map_order_divs(map->p[i]);
5418                 if (!map->p[i])
5419                         goto error;
5420         }
5421
5422         return map;
5423 error:
5424         isl_map_free(map);
5425         return NULL;
5426 }
5427
5428 /* Look for a div in dst that corresponds to the div "div" in src.
5429  * The divs before "div" in src and dst are assumed to be the same.
5430  *
5431  * Returns -1 if no corresponding div was found and the position
5432  * of the corresponding div in dst otherwise.
5433  */
5434 static int find_div(struct isl_basic_map *dst,
5435                         struct isl_basic_map *src, unsigned div)
5436 {
5437         int i;
5438
5439         unsigned total = isl_dim_total(src->dim);
5440
5441         isl_assert(dst->ctx, div <= dst->n_div, return -1);
5442         for (i = div; i < dst->n_div; ++i)
5443                 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
5444                     isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
5445                                                 dst->n_div - div) == -1)
5446                         return i;
5447         return -1;
5448 }
5449
5450 struct isl_basic_map *isl_basic_map_align_divs(
5451                 struct isl_basic_map *dst, struct isl_basic_map *src)
5452 {
5453         int i;
5454         unsigned total = isl_dim_total(src->dim);
5455
5456         if (!dst || !src)
5457                 goto error;
5458
5459         if (src->n_div == 0)
5460                 return dst;
5461
5462         for (i = 0; i < src->n_div; ++i)
5463                 isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
5464
5465         src = isl_basic_map_order_divs(src);
5466         dst = isl_basic_map_cow(dst);
5467         dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
5468                         src->n_div, 0, 2 * src->n_div);
5469         if (!dst)
5470                 return NULL;
5471         for (i = 0; i < src->n_div; ++i) {
5472                 int j = find_div(dst, src, i);
5473                 if (j < 0) {
5474                         j = isl_basic_map_alloc_div(dst);
5475                         if (j < 0)
5476                                 goto error;
5477                         isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i);
5478                         isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i);
5479                         if (isl_basic_map_add_div_constraints(dst, j) < 0)
5480                                 goto error;
5481                 }
5482                 if (j != i)
5483                         isl_basic_map_swap_div(dst, i, j);
5484         }
5485         return dst;
5486 error:
5487         isl_basic_map_free(dst);
5488         return NULL;
5489 }
5490
5491 struct isl_basic_set *isl_basic_set_align_divs(
5492                 struct isl_basic_set *dst, struct isl_basic_set *src)
5493 {
5494         return (struct isl_basic_set *)isl_basic_map_align_divs(
5495                 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
5496 }
5497
5498 struct isl_map *isl_map_align_divs(struct isl_map *map)
5499 {
5500         int i;
5501
5502         if (!map)
5503                 return NULL;
5504         if (map->n == 0)
5505                 return map;
5506         map = isl_map_compute_divs(map);
5507         map = isl_map_cow(map);
5508         if (!map)
5509                 return NULL;
5510
5511         for (i = 1; i < map->n; ++i)
5512                 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
5513         for (i = 1; i < map->n; ++i)
5514                 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
5515
5516         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5517         return map;
5518 }
5519
5520 struct isl_set *isl_set_align_divs(struct isl_set *set)
5521 {
5522         return (struct isl_set *)isl_map_align_divs((struct isl_map *)set);
5523 }
5524
5525 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
5526 {
5527         if (!set || !map)
5528                 goto error;
5529         isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
5530         map = isl_map_intersect_domain(map, set);
5531         set = isl_map_range(map);
5532         return set;
5533 error:
5534         isl_set_free(set);
5535         isl_map_free(map);
5536         return NULL;
5537 }
5538
5539 /* There is no need to cow as removing empty parts doesn't change
5540  * the meaning of the set.
5541  */
5542 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
5543 {
5544         int i;
5545
5546         if (!map)
5547                 return NULL;
5548
5549         for (i = map->n-1; i >= 0; --i) {
5550                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
5551                         continue;
5552                 isl_basic_map_free(map->p[i]);
5553                 if (i != map->n-1) {
5554                         ISL_F_CLR(map, ISL_MAP_NORMALIZED);
5555                         map->p[i] = map->p[map->n-1];
5556                 }
5557                 map->n--;
5558         }
5559
5560         return map;
5561 }
5562
5563 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
5564 {
5565         return (struct isl_set *)
5566                 isl_map_remove_empty_parts((struct isl_map *)set);
5567 }
5568
5569 struct isl_basic_map *isl_map_copy_basic_map(struct isl_map *map)
5570 {
5571         struct isl_basic_map *bmap;
5572         if (!map || map->n == 0)
5573                 return NULL;
5574         bmap = map->p[map->n-1];
5575         isl_assert(map->ctx, ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL), return NULL);
5576         return isl_basic_map_copy(bmap);
5577 }
5578
5579 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
5580 {
5581         return (struct isl_basic_set *)
5582                 isl_map_copy_basic_map((struct isl_map *)set);
5583 }
5584
5585 __isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map,
5586                                                 __isl_keep isl_basic_map *bmap)
5587 {
5588         int i;
5589
5590         if (!map || !bmap)
5591                 goto error;
5592         for (i = map->n-1; i >= 0; --i) {
5593                 if (map->p[i] != bmap)
5594                         continue;
5595                 map = isl_map_cow(map);
5596                 if (!map)
5597                         goto error;
5598                 isl_basic_map_free(map->p[i]);
5599                 if (i != map->n-1) {
5600                         ISL_F_CLR(map, ISL_SET_NORMALIZED);
5601                         map->p[i] = map->p[map->n-1];
5602                 }
5603                 map->n--;
5604                 return map;
5605         }
5606         return map;
5607 error:
5608         isl_map_free(map);
5609         return NULL;
5610 }
5611
5612 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
5613                                                 struct isl_basic_set *bset)
5614 {
5615         return (struct isl_set *)isl_map_drop_basic_map((struct isl_map *)set,
5616                                                 (struct isl_basic_map *)bset);
5617 }
5618
5619 /* Given two basic sets bset1 and bset2, compute the maximal difference
5620  * between the values of dimension pos in bset1 and those in bset2
5621  * for any common value of the parameters and dimensions preceding pos.
5622  */
5623 static enum isl_lp_result basic_set_maximal_difference_at(
5624         __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
5625         int pos, isl_int *opt)
5626 {
5627         struct isl_dim *dims;
5628         struct isl_basic_map *bmap1 = NULL;
5629         struct isl_basic_map *bmap2 = NULL;
5630         struct isl_ctx *ctx;
5631         struct isl_vec *obj;
5632         unsigned total;
5633         unsigned nparam;
5634         unsigned dim1, dim2;
5635         enum isl_lp_result res;
5636
5637         if (!bset1 || !bset2)
5638                 return isl_lp_error;
5639
5640         nparam = isl_basic_set_n_param(bset1);
5641         dim1 = isl_basic_set_n_dim(bset1);
5642         dim2 = isl_basic_set_n_dim(bset2);
5643         dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
5644         bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
5645         dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
5646         bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
5647         if (!bmap1 || !bmap2)
5648                 goto error;
5649         bmap1 = isl_basic_map_cow(bmap1);
5650         bmap1 = isl_basic_map_extend(bmap1, nparam,
5651                         pos, (dim1 - pos) + (dim2 - pos),
5652                         bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
5653         bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
5654         if (!bmap1)
5655                 goto error;
5656         total = isl_basic_map_total_dim(bmap1);
5657         ctx = bmap1->ctx;
5658         obj = isl_vec_alloc(ctx, 1 + total);
5659         isl_seq_clr(obj->block.data, 1 + total);
5660         isl_int_set_si(obj->block.data[1+nparam+pos], 1);
5661         isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1);
5662         if (!obj)
5663                 goto error;
5664         res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one,
5665                                         opt, NULL, NULL);
5666         isl_basic_map_free(bmap1);
5667         isl_vec_free(obj);
5668         return res;
5669 error:
5670         isl_basic_map_free(bmap1);
5671         isl_basic_map_free(bmap2);
5672         return isl_lp_error;
5673 }
5674
5675 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
5676  * for any common value of the parameters and dimensions preceding pos
5677  * in both basic sets, the values of dimension pos in bset1 are
5678  * smaller or larger than those in bset2.
5679  *
5680  * Returns
5681  *       1 if bset1 follows bset2
5682  *      -1 if bset1 precedes bset2
5683  *       0 if bset1 and bset2 are incomparable
5684  *      -2 if some error occurred.
5685  */
5686 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
5687         struct isl_basic_set *bset2, int pos)
5688 {
5689         isl_int opt;
5690         enum isl_lp_result res;
5691         int cmp;
5692
5693         isl_int_init(opt);
5694
5695         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5696
5697         if (res == isl_lp_empty)
5698                 cmp = 0;
5699         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5700                   res == isl_lp_unbounded)
5701                 cmp = 1;
5702         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5703                 cmp = -1;
5704         else
5705                 cmp = -2;
5706
5707         isl_int_clear(opt);
5708         return cmp;
5709 }
5710
5711 /* Given two basic sets bset1 and bset2, check whether
5712  * for any common value of the parameters and dimensions preceding pos
5713  * there is a value of dimension pos in bset1 that is larger
5714  * than a value of the same dimension in bset2.
5715  *
5716  * Return
5717  *       1 if there exists such a pair
5718  *       0 if there is no such pair, but there is a pair of equal values
5719  *      -1 otherwise
5720  *      -2 if some error occurred.
5721  */
5722 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
5723         __isl_keep isl_basic_set *bset2, int pos)
5724 {
5725         isl_int opt;
5726         enum isl_lp_result res;
5727         int cmp;
5728
5729         isl_int_init(opt);
5730
5731         res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
5732
5733         if (res == isl_lp_empty)
5734                 cmp = -1;
5735         else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
5736                   res == isl_lp_unbounded)
5737                 cmp = 1;
5738         else if (res == isl_lp_ok && isl_int_is_neg(opt))
5739                 cmp = -1;
5740         else if (res == isl_lp_ok)
5741                 cmp = 0;
5742         else
5743                 cmp = -2;
5744
5745         isl_int_clear(opt);
5746         return cmp;
5747 }
5748
5749 /* Given two sets set1 and set2, check whether
5750  * for any common value of the parameters and dimensions preceding pos
5751  * there is a value of dimension pos in set1 that is larger
5752  * than a value of the same dimension in set2.
5753  *
5754  * Return
5755  *       1 if there exists such a pair
5756  *       0 if there is no such pair, but there is a pair of equal values
5757  *      -1 otherwise
5758  *      -2 if some error occurred.
5759  */
5760 int isl_set_follows_at(__isl_keep isl_set *set1,
5761         __isl_keep isl_set *set2, int pos)
5762 {
5763         int i, j;
5764         int follows = -1;
5765
5766         if (!set1 || !set2)
5767                 return -2;
5768
5769         for (i = 0; i < set1->n; ++i)
5770                 for (j = 0; j < set2->n; ++j) {
5771                         int f;
5772                         f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos);
5773                         if (f == 1 || f == -2)
5774                                 return f;
5775                         if (f > follows)
5776                                 follows = f;
5777                 }
5778
5779         return follows;
5780 }
5781
5782 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
5783         unsigned pos, isl_int *val)
5784 {
5785         int i;
5786         int d;
5787         unsigned total;
5788
5789         if (!bmap)
5790                 return -1;
5791         total = isl_basic_map_total_dim(bmap);
5792         for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
5793                 for (; d+1 > pos; --d)
5794                         if (!isl_int_is_zero(bmap->eq[i][1+d]))
5795                                 break;
5796                 if (d != pos)
5797                         continue;
5798                 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
5799                         return 0;
5800                 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
5801                         return 0;
5802                 if (!isl_int_is_one(bmap->eq[i][1+d]))
5803                         return 0;
5804                 if (val)
5805                         isl_int_neg(*val, bmap->eq[i][0]);
5806                 return 1;
5807         }
5808         return 0;
5809 }
5810
5811 static int isl_map_fast_has_fixed_var(struct isl_map *map,
5812         unsigned pos, isl_int *val)
5813 {
5814         int i;
5815         isl_int v;
5816         isl_int tmp;
5817         int fixed;
5818
5819         if (!map)
5820                 return -1;
5821         if (map->n == 0)
5822                 return 0;
5823         if (map->n == 1)
5824                 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
5825         isl_int_init(v);
5826         isl_int_init(tmp);
5827         fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
5828         for (i = 1; fixed == 1 && i < map->n; ++i) {
5829                 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
5830                 if (fixed == 1 && isl_int_ne(tmp, v))
5831                         fixed = 0;
5832         }
5833         if (val)
5834                 isl_int_set(*val, v);
5835         isl_int_clear(tmp);
5836         isl_int_clear(v);
5837         return fixed;
5838 }
5839
5840 static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset,
5841         unsigned pos, isl_int *val)
5842 {
5843         return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset,
5844                                                 pos, val);
5845 }
5846
5847 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
5848         isl_int *val)
5849 {
5850         return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
5851 }
5852
5853 int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap,
5854         enum isl_dim_type type, unsigned pos, isl_int *val)
5855 {
5856         if (pos >= isl_basic_map_dim(bmap, type))
5857                 return -1;
5858         return isl_basic_map_fast_has_fixed_var(bmap,
5859                 isl_basic_map_offset(bmap, type) - 1 + pos, val);
5860 }
5861
5862 int isl_map_fast_is_fixed(struct isl_map *map,
5863         enum isl_dim_type type, unsigned pos, isl_int *val)
5864 {
5865         if (pos >= isl_map_dim(map, type))
5866                 return -1;
5867         return isl_map_fast_has_fixed_var(map,
5868                 map_offset(map, type) - 1 + pos, val);
5869 }
5870
5871 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5872  * then return this fixed value in *val.
5873  */
5874 int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim,
5875         isl_int *val)
5876 {
5877         return isl_basic_set_fast_has_fixed_var(bset,
5878                                         isl_basic_set_n_param(bset) + dim, val);
5879 }
5880
5881 /* Check if dimension dim has fixed value and if so and if val is not NULL,
5882  * then return this fixed value in *val.
5883  */
5884 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
5885 {
5886         return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
5887 }
5888
5889 /* Check if input variable in has fixed value and if so and if val is not NULL,
5890  * then return this fixed value in *val.
5891  */
5892 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
5893 {
5894         return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
5895 }
5896
5897 /* Check if dimension dim has an (obvious) fixed lower bound and if so
5898  * and if val is not NULL, then return this lower bound in *val.
5899  */
5900 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
5901         unsigned dim, isl_int *val)
5902 {
5903         int i, i_eq = -1, i_ineq = -1;
5904         isl_int *c;
5905         unsigned total;
5906         unsigned nparam;
5907
5908         if (!bset)
5909                 return -1;
5910         total = isl_basic_set_total_dim(bset);
5911         nparam = isl_basic_set_n_param(bset);
5912         for (i = 0; i < bset->n_eq; ++i) {
5913                 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
5914                         continue;
5915                 if (i_eq != -1)
5916                         return 0;
5917                 i_eq = i;
5918         }
5919         for (i = 0; i < bset->n_ineq; ++i) {
5920                 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
5921                         continue;
5922                 if (i_eq != -1 || i_ineq != -1)
5923                         return 0;
5924                 i_ineq = i;
5925         }
5926         if (i_eq == -1 && i_ineq == -1)
5927                 return 0;
5928         c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
5929         /* The coefficient should always be one due to normalization. */
5930         if (!isl_int_is_one(c[1+nparam+dim]))
5931                 return 0;
5932         if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
5933                 return 0;
5934         if (isl_seq_first_non_zero(c+1+nparam+dim+1,
5935                                         total - nparam - dim - 1) != -1)
5936                 return 0;
5937         if (val)
5938                 isl_int_neg(*val, c[0]);
5939         return 1;
5940 }
5941
5942 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
5943         unsigned dim, isl_int *val)
5944 {
5945         int i;
5946         isl_int v;
5947         isl_int tmp;
5948         int fixed;
5949
5950         if (!set)
5951                 return -1;
5952         if (set->n == 0)
5953                 return 0;
5954         if (set->n == 1)
5955                 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5956                                                                 dim, val);
5957         isl_int_init(v);
5958         isl_int_init(tmp);
5959         fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
5960                                                                 dim, &v);
5961         for (i = 1; fixed == 1 && i < set->n; ++i) {
5962                 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
5963                                                                 dim, &tmp);
5964                 if (fixed == 1 && isl_int_ne(tmp, v))
5965                         fixed = 0;
5966         }
5967         if (val)
5968                 isl_int_set(*val, v);
5969         isl_int_clear(tmp);
5970         isl_int_clear(v);
5971         return fixed;
5972 }
5973
5974 struct constraint {
5975         unsigned        size;
5976         isl_int         *c;
5977 };
5978
5979 static int qsort_constraint_cmp(const void *p1, const void *p2)
5980 {
5981         const struct constraint *c1 = (const struct constraint *)p1;
5982         const struct constraint *c2 = (const struct constraint *)p2;
5983         unsigned size = isl_min(c1->size, c2->size);
5984         return isl_seq_cmp(c1->c, c2->c, size);
5985 }
5986
5987 static struct isl_basic_map *isl_basic_map_sort_constraints(
5988         struct isl_basic_map *bmap)
5989 {
5990         int i;
5991         struct constraint *c;
5992         unsigned total;
5993
5994         if (!bmap)
5995                 return NULL;
5996         total = isl_basic_map_total_dim(bmap);
5997         c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
5998         if (!c)
5999                 goto error;
6000         for (i = 0; i < bmap->n_ineq; ++i) {
6001                 c[i].size = total;
6002                 c[i].c = bmap->ineq[i];
6003         }
6004         qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
6005         for (i = 0; i < bmap->n_ineq; ++i)
6006                 bmap->ineq[i] = c[i].c;
6007         free(c);
6008         return bmap;
6009 error:
6010         isl_basic_map_free(bmap);
6011         return NULL;
6012 }
6013
6014 __isl_give isl_basic_set *isl_basic_set_sort_constraints(
6015         __isl_take isl_basic_set *bset)
6016 {
6017         return (struct isl_basic_set *)isl_basic_map_sort_constraints(
6018                                                 (struct isl_basic_map *)bset);
6019 }
6020
6021 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
6022 {
6023         if (!bmap)
6024                 return NULL;
6025         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
6026                 return bmap;
6027         bmap = isl_basic_map_convex_hull(bmap);
6028         bmap = isl_basic_map_sort_constraints(bmap);
6029         ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
6030         return bmap;
6031 }
6032
6033 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
6034 {
6035         return (struct isl_basic_set *)isl_basic_map_normalize(
6036                                                 (struct isl_basic_map *)bset);
6037 }
6038
6039 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
6040         const struct isl_basic_map *bmap2)
6041 {
6042         int i, cmp;
6043         unsigned total;
6044
6045         if (bmap1 == bmap2)
6046                 return 0;
6047         if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
6048                 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
6049         if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
6050                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
6051         if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
6052                 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
6053         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
6054             ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
6055                 return 0;
6056         if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
6057                 return 1;
6058         if (ISL_F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
6059                 return -1;
6060         if (bmap1->n_eq != bmap2->n_eq)
6061                 return bmap1->n_eq - bmap2->n_eq;
6062         if (bmap1->n_ineq != bmap2->n_ineq)
6063                 return bmap1->n_ineq - bmap2->n_ineq;
6064         if (bmap1->n_div != bmap2->n_div)
6065                 return bmap1->n_div - bmap2->n_div;
6066         total = isl_basic_map_total_dim(bmap1);
6067         for (i = 0; i < bmap1->n_eq; ++i) {
6068                 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
6069                 if (cmp)
6070                         return cmp;
6071         }
6072         for (i = 0; i < bmap1->n_ineq; ++i) {
6073                 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
6074                 if (cmp)
6075                         return cmp;
6076         }
6077         for (i = 0; i < bmap1->n_div; ++i) {
6078                 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
6079                 if (cmp)
6080                         return cmp;
6081         }
6082         return 0;
6083 }
6084
6085 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
6086         struct isl_basic_map *bmap2)
6087 {
6088         return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
6089 }
6090
6091 int isl_basic_set_fast_is_equal(__isl_keep isl_basic_set *bset1,
6092         __isl_keep isl_basic_set *bset2)
6093 {
6094         return isl_basic_map_fast_is_equal((isl_basic_map *)bset1,
6095                                             (isl_basic_map *)bset2);
6096 }
6097
6098 static int qsort_bmap_cmp(const void *p1, const void *p2)
6099 {
6100         const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
6101         const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
6102
6103         return isl_basic_map_fast_cmp(bmap1, bmap2);
6104 }
6105
6106 /* We normalize in place, but if anything goes wrong we need
6107  * to return NULL, so we need to make sure we don't change the
6108  * meaning of any possible other copies of map.
6109  */
6110 struct isl_map *isl_map_normalize(struct isl_map *map)
6111 {
6112         int i, j;
6113         struct isl_basic_map *bmap;
6114
6115         if (!map)
6116                 return NULL;
6117         if (ISL_F_ISSET(map, ISL_MAP_NORMALIZED))
6118                 return map;
6119         for (i = 0; i < map->n; ++i) {
6120                 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
6121                 if (!bmap)
6122                         goto error;
6123                 isl_basic_map_free(map->p[i]);
6124                 map->p[i] = bmap;
6125         }
6126         qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
6127         ISL_F_SET(map, ISL_MAP_NORMALIZED);
6128         map = isl_map_remove_empty_parts(map);
6129         if (!map)
6130                 return NULL;
6131         for (i = map->n - 1; i >= 1; --i) {
6132                 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
6133                         continue;
6134                 isl_basic_map_free(map->p[i-1]);
6135                 for (j = i; j < map->n; ++j)
6136                         map->p[j-1] = map->p[j];
6137                 map->n--;
6138         }
6139         return map;
6140 error:
6141         isl_map_free(map);
6142         return NULL;
6143
6144 }
6145
6146 struct isl_set *isl_set_normalize(struct isl_set *set)
6147 {
6148         return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
6149 }
6150
6151 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
6152 {
6153         int i;
6154         int equal;
6155
6156         if (!map1 || !map2)
6157                 return -1;
6158
6159         if (map1 == map2)
6160                 return 1;
6161         if (!isl_dim_equal(map1->dim, map2->dim))
6162                 return 0;
6163
6164         map1 = isl_map_copy(map1);
6165         map2 = isl_map_copy(map2);
6166         map1 = isl_map_normalize(map1);
6167         map2 = isl_map_normalize(map2);
6168         if (!map1 || !map2)
6169                 goto error;
6170         equal = map1->n == map2->n;
6171         for (i = 0; equal && i < map1->n; ++i) {
6172                 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
6173                 if (equal < 0)
6174                         goto error;
6175         }
6176         isl_map_free(map1);
6177         isl_map_free(map2);
6178         return equal;
6179 error:
6180         isl_map_free(map1);
6181         isl_map_free(map2);
6182         return -1;
6183 }
6184
6185 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
6186 {
6187         return isl_map_fast_is_equal((struct isl_map *)set1,
6188                                                 (struct isl_map *)set2);
6189 }
6190
6191 /* Return an interval that ranges from min to max (inclusive)
6192  */
6193 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
6194         isl_int min, isl_int max)
6195 {
6196         int k;
6197         struct isl_basic_set *bset = NULL;
6198
6199         bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
6200         if (!bset)
6201                 goto error;
6202
6203         k = isl_basic_set_alloc_inequality(bset);
6204         if (k < 0)
6205                 goto error;
6206         isl_int_set_si(bset->ineq[k][1], 1);
6207         isl_int_neg(bset->ineq[k][0], min);
6208
6209         k = isl_basic_set_alloc_inequality(bset);
6210         if (k < 0)
6211                 goto error;
6212         isl_int_set_si(bset->ineq[k][1], -1);
6213         isl_int_set(bset->ineq[k][0], max);
6214
6215         return bset;
6216 error:
6217         isl_basic_set_free(bset);
6218         return NULL;
6219 }
6220
6221 /* Return the Cartesian product of the basic sets in list (in the given order).
6222  */
6223 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
6224 {
6225         int i;
6226         unsigned dim;
6227         unsigned nparam;
6228         unsigned extra;
6229         unsigned n_eq;
6230         unsigned n_ineq;
6231         struct isl_basic_set *product = NULL;
6232
6233         if (!list)
6234                 goto error;
6235         isl_assert(list->ctx, list->n > 0, goto error);
6236         isl_assert(list->ctx, list->p[0], goto error);
6237         nparam = isl_basic_set_n_param(list->p[0]);
6238         dim = isl_basic_set_n_dim(list->p[0]);
6239         extra = list->p[0]->n_div;
6240         n_eq = list->p[0]->n_eq;
6241         n_ineq = list->p[0]->n_ineq;
6242         for (i = 1; i < list->n; ++i) {
6243                 isl_assert(list->ctx, list->p[i], goto error);
6244                 isl_assert(list->ctx,
6245                     nparam == isl_basic_set_n_param(list->p[i]), goto error);
6246                 dim += isl_basic_set_n_dim(list->p[i]);
6247                 extra += list->p[i]->n_div;
6248                 n_eq += list->p[i]->n_eq;
6249                 n_ineq += list->p[i]->n_ineq;
6250         }
6251         product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
6252                                         n_eq, n_ineq);
6253         if (!product)
6254                 goto error;
6255         dim = 0;
6256         for (i = 0; i < list->n; ++i) {
6257                 isl_basic_set_add_constraints(product,
6258                                         isl_basic_set_copy(list->p[i]), dim);
6259                 dim += isl_basic_set_n_dim(list->p[i]);
6260         }
6261         isl_basic_set_list_free(list);
6262         return product;
6263 error:
6264         isl_basic_set_free(product);
6265         isl_basic_set_list_free(list);
6266         return NULL;
6267 }
6268
6269 struct isl_basic_map *isl_basic_map_product(
6270                 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
6271 {
6272         struct isl_dim *dim_result = NULL;
6273         struct isl_basic_map *bmap;
6274         unsigned in1, in2, out1, out2, nparam, total, pos;
6275         struct isl_dim_map *dim_map1, *dim_map2;
6276
6277         if (!bmap1 || !bmap2)
6278                 goto error;
6279
6280         isl_assert(bmap1->ctx, isl_dim_match(bmap1->dim, isl_dim_param,
6281                                      bmap2->dim, isl_dim_param), goto error);
6282         dim_result = isl_dim_product(isl_dim_copy(bmap1->dim),
6283                                                    isl_dim_copy(bmap2->dim));
6284
6285         in1 = isl_basic_map_n_in(bmap1);
6286         in2 = isl_basic_map_n_in(bmap2);
6287         out1 = isl_basic_map_n_out(bmap1);
6288         out2 = isl_basic_map_n_out(bmap2);
6289         nparam = isl_basic_map_n_param(bmap1);
6290
6291         total = nparam + in1 + in2 + out1 + out2 + bmap1->n_div + bmap2->n_div;
6292         dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
6293         dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
6294         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
6295         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
6296         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
6297         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos += in1);
6298         isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += in2);
6299         isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += out1);
6300         isl_dim_map_div(dim_map1, bmap1, pos += out2);
6301         isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
6302
6303         bmap = isl_basic_map_alloc_dim(dim_result,
6304                         bmap1->n_div + bmap2->n_div,
6305                         bmap1->n_eq + bmap2->n_eq,
6306                         bmap1->n_ineq + bmap2->n_ineq);
6307         bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
6308         bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
6309         bmap = isl_basic_map_simplify(bmap);
6310         return isl_basic_map_finalize(bmap);
6311 error:
6312         isl_basic_map_free(bmap1);
6313         isl_basic_map_free(bmap2);
6314         return NULL;
6315 }
6316
6317 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
6318  */
6319 struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2)
6320 {
6321         unsigned flags = 0;
6322         struct isl_map *result;
6323         int i, j;
6324
6325         if (!map1 || !map2)
6326                 goto error;
6327
6328         isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param,
6329                                          map2->dim, isl_dim_param), goto error);
6330
6331         if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
6332             ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
6333                 ISL_FL_SET(flags, ISL_MAP_DISJOINT);
6334
6335         result = isl_map_alloc_dim(isl_dim_product(isl_dim_copy(map1->dim),
6336                                                    isl_dim_copy(map2->dim)),
6337                                 map1->n * map2->n, flags);
6338         if (!result)
6339                 goto error;
6340         for (i = 0; i < map1->n; ++i)
6341                 for (j = 0; j < map2->n; ++j) {
6342                         struct isl_basic_map *part;
6343                         part = isl_basic_map_product(
6344                                     isl_basic_map_copy(map1->p[i]),
6345                                     isl_basic_map_copy(map2->p[j]));
6346                         if (isl_basic_map_is_empty(part))
6347                                 isl_basic_map_free(part);
6348                         else
6349                                 result = isl_map_add_basic_map(result, part);
6350                         if (!result)
6351                                 goto error;
6352                 }
6353         isl_map_free(map1);
6354         isl_map_free(map2);
6355         return result;
6356 error:
6357         isl_map_free(map1);
6358         isl_map_free(map2);
6359         return NULL;
6360 }
6361
6362 /* Given two set A and B, construct its Cartesian product A x B.
6363  */
6364 struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2)
6365 {
6366         return (struct isl_set *)isl_map_product((struct isl_map *)set1,
6367                                                  (struct isl_map *)set2);
6368 }
6369
6370 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
6371 {
6372         int i;
6373         uint32_t hash = isl_hash_init();
6374         unsigned total;
6375
6376         if (!bset)
6377                 return 0;
6378         bset = isl_basic_set_copy(bset);
6379         bset = isl_basic_set_normalize(bset);
6380         if (!bset)
6381                 return 0;
6382         total = isl_basic_set_total_dim(bset);
6383         isl_hash_byte(hash, bset->n_eq & 0xFF);
6384         for (i = 0; i < bset->n_eq; ++i) {
6385                 uint32_t c_hash;
6386                 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
6387                 isl_hash_hash(hash, c_hash);
6388         }
6389         isl_hash_byte(hash, bset->n_ineq & 0xFF);
6390         for (i = 0; i < bset->n_ineq; ++i) {
6391                 uint32_t c_hash;
6392                 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
6393                 isl_hash_hash(hash, c_hash);
6394         }
6395         isl_hash_byte(hash, bset->n_div & 0xFF);
6396         for (i = 0; i < bset->n_div; ++i) {
6397                 uint32_t c_hash;
6398                 if (isl_int_is_zero(bset->div[i][0]))
6399                         continue;
6400                 isl_hash_byte(hash, i & 0xFF);
6401                 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
6402                 isl_hash_hash(hash, c_hash);
6403         }
6404         isl_basic_set_free(bset);
6405         return hash;
6406 }
6407
6408 uint32_t isl_set_get_hash(struct isl_set *set)
6409 {
6410         int i;
6411         uint32_t hash;
6412
6413         if (!set)
6414                 return 0;
6415         set = isl_set_copy(set);
6416         set = isl_set_normalize(set);
6417         if (!set)
6418                 return 0;
6419
6420         hash = isl_hash_init();
6421         for (i = 0; i < set->n; ++i) {
6422                 uint32_t bset_hash;
6423                 bset_hash = isl_basic_set_get_hash(set->p[i]);
6424                 isl_hash_hash(hash, bset_hash);
6425         }
6426
6427         isl_set_free(set);
6428
6429         return hash;
6430 }
6431
6432 /* Check if the value for dimension dim is completely determined
6433  * by the values of the other parameters and variables.
6434  * That is, check if dimension dim is involved in an equality.
6435  */
6436 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
6437 {
6438         int i;
6439         unsigned nparam;
6440
6441         if (!bset)
6442                 return -1;
6443         nparam = isl_basic_set_n_param(bset);
6444         for (i = 0; i < bset->n_eq; ++i)
6445                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
6446                         return 1;
6447         return 0;
6448 }
6449
6450 /* Check if the value for dimension dim is completely determined
6451  * by the values of the other parameters and variables.
6452  * That is, check if dimension dim is involved in an equality
6453  * for each of the subsets.
6454  */
6455 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
6456 {
6457         int i;
6458
6459         if (!set)
6460                 return -1;
6461         for (i = 0; i < set->n; ++i) {
6462                 int unique;
6463                 unique = isl_basic_set_dim_is_unique(set->p[i], dim);
6464                 if (unique != 1)
6465                         return unique;
6466         }
6467         return 1;
6468 }
6469
6470 int isl_map_foreach_basic_map(__isl_keep isl_map *map,
6471         int (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
6472 {
6473         int i;
6474
6475         if (!map)
6476                 return -1;
6477
6478         for (i = 0; i < map->n; ++i)
6479                 if (fn(isl_basic_map_copy(map->p[i]), user) < 0)
6480                         return -1;
6481
6482         return 0;
6483 }
6484
6485 int isl_set_foreach_basic_set(__isl_keep isl_set *set,
6486         int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
6487 {
6488         int i;
6489
6490         if (!set)
6491                 return -1;
6492
6493         for (i = 0; i < set->n; ++i)
6494                 if (fn(isl_basic_set_copy(set->p[i]), user) < 0)
6495                         return -1;
6496
6497         return 0;
6498 }
6499
6500 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
6501 {
6502         struct isl_dim *dim;
6503
6504         if (!bset)
6505                 return NULL;
6506
6507         if (bset->n_div == 0)
6508                 return bset;
6509
6510         bset = isl_basic_set_cow(bset);
6511         if (!bset)
6512                 return NULL;
6513
6514         dim = isl_basic_set_get_dim(bset);
6515         dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
6516         if (!dim)
6517                 goto error;
6518         isl_dim_free(bset->dim);
6519         bset->dim = dim;
6520         bset->n_div = 0;
6521
6522         bset = isl_basic_set_finalize(bset);
6523
6524         return bset;
6525 error:
6526         isl_basic_set_free(bset);
6527         return NULL;
6528 }
6529
6530 __isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
6531 {
6532         int i;
6533         struct isl_dim *dim;
6534         unsigned n_div;
6535
6536         set = isl_set_align_divs(set);
6537
6538         if (!set)
6539                 return NULL;
6540         if (set->n == 0 || set->p[0]->n_div == 0)
6541                 return set;
6542
6543         set = isl_set_cow(set);
6544         if (!set)
6545                 return NULL;
6546
6547         n_div = set->p[0]->n_div;
6548         dim = isl_set_get_dim(set);
6549         dim = isl_dim_add(dim, isl_dim_set, n_div);
6550         if (!dim)
6551                 goto error;
6552         isl_dim_free(set->dim);
6553         set->dim = dim;
6554
6555         for (i = 0; i < set->n; ++i) {
6556                 set->p[i] = isl_basic_set_lift(set->p[i]);
6557                 if (!set->p[i])
6558                         goto error;
6559         }
6560
6561         return set;
6562 error:
6563         isl_set_free(set);
6564         return NULL;
6565 }
6566
6567 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
6568 {
6569         struct isl_dim *dim;
6570         struct isl_basic_map *bmap;
6571         unsigned n_set;
6572         unsigned n_div;
6573         unsigned n_param;
6574         unsigned total;
6575         int i, k, l;
6576
6577         set = isl_set_align_divs(set);
6578
6579         if (!set)
6580                 return NULL;
6581
6582         dim = isl_set_get_dim(set);
6583         if (set->n == 0 || set->p[0]->n_div == 0) {
6584                 isl_set_free(set);
6585                 return isl_map_identity(dim);
6586         }
6587
6588         n_div = set->p[0]->n_div;
6589         dim = isl_dim_map(dim);
6590         n_param = isl_dim_size(dim, isl_dim_param);
6591         n_set = isl_dim_size(dim, isl_dim_in);
6592         dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div);
6593         bmap = isl_basic_map_alloc_dim(dim, 0, n_set, 2 * n_div);
6594         for (i = 0; i < n_set; ++i)
6595                 bmap = var_equal(bmap, i);
6596
6597         total = n_param + n_set + n_set + n_div;
6598         for (i = 0; i < n_div; ++i) {
6599                 k = isl_basic_map_alloc_inequality(bmap);
6600                 if (k < 0)
6601                         goto error;
6602                 isl_seq_cpy(bmap->ineq[k], set->p[0]->div[i]+1, 1+n_param);
6603                 isl_seq_clr(bmap->ineq[k]+1+n_param, n_set);
6604                 isl_seq_cpy(bmap->ineq[k]+1+n_param+n_set,
6605                             set->p[0]->div[i]+1+1+n_param, n_set + n_div);
6606                 isl_int_neg(bmap->ineq[k][1+n_param+n_set+n_set+i],
6607                             set->p[0]->div[i][0]);
6608
6609                 l = isl_basic_map_alloc_inequality(bmap);
6610                 if (l < 0)
6611                         goto error;
6612                 isl_seq_neg(bmap->ineq[l], bmap->ineq[k], 1 + total);
6613                 isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0],
6614                             set->p[0]->div[i][0]);
6615                 isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);
6616         }
6617
6618         isl_set_free(set);
6619         return isl_map_from_basic_map(bmap);
6620 error:
6621         isl_set_free(set);
6622         isl_basic_map_free(bmap);
6623         return NULL;
6624 }
6625
6626 int isl_basic_set_size(__isl_keep isl_basic_set *bset)
6627 {
6628         unsigned dim;
6629         int size = 0;
6630
6631         if (!bset)
6632                 return -1;
6633
6634         dim = isl_basic_set_total_dim(bset);
6635         size += bset->n_eq * (1 + dim);
6636         size += bset->n_ineq * (1 + dim);
6637         size += bset->n_div * (2 + dim);
6638
6639         return size;
6640 }
6641
6642 int isl_set_size(__isl_keep isl_set *set)
6643 {
6644         int i;
6645         int size = 0;
6646
6647         if (!set)
6648                 return -1;
6649
6650         for (i = 0; i < set->n; ++i)
6651                 size += isl_basic_set_size(set->p[i]);
6652
6653         return size;
6654 }
6655
6656 int isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
6657         enum isl_dim_type type, unsigned pos)
6658 {
6659         int i;
6660         int lower, upper;
6661
6662         if (!bmap)
6663                 return -1;
6664
6665         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
6666
6667         pos += isl_basic_map_offset(bmap, type);
6668
6669         for (i = 0; i < bmap->n_eq; ++i)
6670                 if (!isl_int_is_zero(bmap->eq[i][pos]))
6671                         return 1;
6672
6673         lower = upper = 0;
6674         for (i = 0; i < bmap->n_ineq; ++i) {
6675                 int sgn = isl_int_sgn(bmap->ineq[i][pos]);
6676                 if (sgn > 0)
6677                         lower = 1;
6678                 if (sgn < 0)
6679                         upper = 1;
6680         }
6681
6682         return lower && upper;
6683 }
6684
6685 int isl_map_dim_is_bounded(__isl_keep isl_map *map,
6686         enum isl_dim_type type, unsigned pos)
6687 {
6688         int i;
6689
6690         if (!map)
6691                 return -1;
6692
6693         for (i = 0; i < map->n; ++i) {
6694                 int bounded;
6695                 bounded = isl_basic_map_dim_is_bounded(map->p[i], type, pos);
6696                 if (bounded < 0 || !bounded)
6697                         return bounded;
6698         }
6699
6700         return 1;
6701 }
6702
6703 /* Return 1 if the specified dim is involved in both an upper bound
6704  * and a lower bound.
6705  */
6706 int isl_set_dim_is_bounded(__isl_keep isl_set *set,
6707         enum isl_dim_type type, unsigned pos)
6708 {
6709         return isl_map_dim_is_bounded((isl_map *)set, type, pos);
6710 }
6711
6712 /* For each of the "n" variables starting at "first", determine
6713  * the sign of the variable and put the results in the first "n"
6714  * elements of the array "signs".
6715  * Sign
6716  *      1 means that the variable is non-negative
6717  *      -1 means that the variable is non-positive
6718  *      0 means the variable attains both positive and negative values.
6719  */
6720 int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
6721         unsigned first, unsigned n, int *signs)
6722 {
6723         isl_vec *bound = NULL;
6724         struct isl_tab *tab = NULL;
6725         struct isl_tab_undo *snap;
6726         int i;
6727
6728         if (!bset || !signs)
6729                 return -1;
6730
6731         bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset));
6732         tab = isl_tab_from_basic_set(bset);
6733         if (!bound || !tab)
6734                 goto error;
6735
6736         isl_seq_clr(bound->el, bound->size);
6737         isl_int_set_si(bound->el[0], -1);
6738
6739         snap = isl_tab_snap(tab);
6740         for (i = 0; i < n; ++i) {
6741                 int empty;
6742
6743                 isl_int_set_si(bound->el[1 + first + i], -1);
6744                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6745                         goto error;
6746                 empty = tab->empty;
6747                 isl_int_set_si(bound->el[1 + first + i], 0);
6748                 if (isl_tab_rollback(tab, snap) < 0)
6749                         goto error;
6750
6751                 if (empty) {
6752                         signs[i] = 1;
6753                         continue;
6754                 }
6755
6756                 isl_int_set_si(bound->el[1 + first + i], 1);
6757                 if (isl_tab_add_ineq(tab, bound->el) < 0)
6758                         goto error;
6759                 empty = tab->empty;
6760                 isl_int_set_si(bound->el[1 + first + i], 0);
6761                 if (isl_tab_rollback(tab, snap) < 0)
6762                         goto error;
6763
6764                 signs[i] = empty ? -1 : 0;
6765         }
6766
6767         isl_tab_free(tab);
6768         isl_vec_free(bound);
6769         return 0;
6770 error:
6771         isl_tab_free(tab);
6772         isl_vec_free(bound);
6773         return -1;
6774 }
6775
6776 int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
6777         enum isl_dim_type type, unsigned first, unsigned n, int *signs)
6778 {
6779         if (!bset || !signs)
6780                 return -1;
6781         isl_assert(bset->ctx, first + n <= isl_basic_set_dim(bset, type),
6782                 return -1);
6783
6784         first += pos(bset->dim, type) - 1;
6785         return isl_basic_set_vars_get_sign(bset, first, n, signs);
6786 }
6787
6788 /* Check if the given map is single-valued.
6789  * We simply compute
6790  *
6791  *      M \circ M^-1
6792  *
6793  * and check if the result is a subset of the identity mapping.
6794  */
6795 int isl_map_is_single_valued(__isl_keep isl_map *map)
6796 {
6797         isl_map *test;
6798         isl_map *id;
6799         int sv;
6800
6801         test = isl_map_reverse(isl_map_copy(map));
6802         test = isl_map_apply_range(test, isl_map_copy(map));
6803
6804         id = isl_map_identity(isl_dim_range(isl_map_get_dim(map)));
6805
6806         sv = isl_map_is_subset(test, id);
6807
6808         isl_map_free(test);
6809         isl_map_free(id);
6810
6811         return sv;
6812 }
6813
6814 int isl_set_is_singleton(__isl_keep isl_set *set)
6815 {
6816         return isl_map_is_single_valued((isl_map *)set);
6817 }
6818
6819 int isl_map_is_translation(__isl_keep isl_map *map)
6820 {
6821         int ok;
6822         isl_set *delta;
6823
6824         delta = isl_map_deltas(isl_map_copy(map));
6825         ok = isl_set_is_singleton(delta);
6826         isl_set_free(delta);
6827
6828         return ok;
6829 }
6830
6831 static int unique(isl_int *p, unsigned pos, unsigned len)
6832 {
6833         if (isl_seq_first_non_zero(p, pos) != -1)
6834                 return 0;
6835         if (isl_seq_first_non_zero(p + pos + 1, len - pos - 1) != -1)
6836                 return 0;
6837         return 1;
6838 }
6839
6840 int isl_basic_set_is_box(__isl_keep isl_basic_set *bset)
6841 {
6842         int i, j;
6843         unsigned nvar;
6844         unsigned ovar;
6845
6846         if (!bset)
6847                 return -1;
6848
6849         if (isl_basic_set_dim(bset, isl_dim_div) != 0)
6850                 return 0;
6851
6852         nvar = isl_basic_set_dim(bset, isl_dim_set);
6853         ovar = isl_dim_offset(bset->dim, isl_dim_set);
6854         for (j = 0; j < nvar; ++j) {
6855                 int lower = 0, upper = 0;
6856                 for (i = 0; i < bset->n_eq; ++i) {
6857                         if (isl_int_is_zero(bset->eq[i][1 + ovar + j]))
6858                                 continue;
6859                         if (!unique(bset->eq[i] + 1 + ovar, j, nvar))
6860                                 return 0;
6861                         break;
6862                 }
6863                 if (i < bset->n_eq)
6864                         continue;
6865                 for (i = 0; i < bset->n_ineq; ++i) {
6866                         if (isl_int_is_zero(bset->ineq[i][1 + ovar + j]))
6867                                 continue;
6868                         if (!unique(bset->ineq[i] + 1 + ovar, j, nvar))
6869                                 return 0;
6870                         if (isl_int_is_pos(bset->ineq[i][1 + ovar + j]))
6871                                 lower = 1;
6872                         else
6873                                 upper = 1;
6874                 }
6875                 if (!lower || !upper)
6876                         return 0;
6877         }
6878
6879         return 1;
6880 }
6881
6882 int isl_set_is_box(__isl_keep isl_set *set)
6883 {
6884         if (!set)
6885                 return -1;
6886         if (set->n != 1)
6887                 return 0;
6888
6889         return isl_basic_set_is_box(set->p[0]);
6890 }