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