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