isl_space.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  *
   5  * Use of this software is governed by the MIT 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 <stdlib.h>
  14 #include <isl_space_private.h>
  15 #include <isl_id_private.h>
  16 #include <isl_reordering.h>
  17
  18 isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim)
  19 {
  20         return dim ? dim->ctx : NULL;
  21 }
  22
  23 __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
  24                         unsigned nparam, unsigned n_in, unsigned n_out)
  25 {
  26         isl_space *dim;
  27
  28         dim = isl_alloc_type(ctx, struct isl_space);
  29         if (!dim)
  30                 return NULL;
  31
  32         dim->ctx = ctx;
  33         isl_ctx_ref(ctx);
  34         dim->ref = 1;
  35         dim->nparam = nparam;
  36         dim->n_in = n_in;
  37         dim->n_out = n_out;
  38
  39         dim->tuple_id[0] = NULL;
  40         dim->tuple_id[1] = NULL;
  41
  42         dim->nested[0] = NULL;
  43         dim->nested[1] = NULL;
  44
  45         dim->n_id = 0;
  46         dim->ids = NULL;
  47
  48         return dim;
  49 }
  50
  51 /* Mark the space as being that of a set, by setting the domain tuple
  52  * to isl_id_none.
  53  */
  54 static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
  55 {
  56         space = isl_space_cow(space);
  57         if (!space)
  58                 return NULL;
  59         space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
  60         return space;
  61 }
  62
  63 /* Is the space that of a set?
  64  */
  65 int isl_space_is_set(__isl_keep isl_space *space)
  66 {
  67         if (!space)
  68                 return -1;
  69         if (space->n_in != 0 || space->nested[0])
  70                 return 0;
  71         if (space->tuple_id[0] != &isl_id_none)
  72                 return 0;
  73         return 1;
  74 }
  75
  76 /* Is the given space that of a map?
  77  */
  78 int isl_space_is_map(__isl_keep isl_space *space)
  79 {
  80         if (!space)
  81                 return -1;
  82         return space->tuple_id[0] != &isl_id_none &&
  83                 space->tuple_id[1] != &isl_id_none;
  84 }
  85
  86 __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
  87                         unsigned nparam, unsigned dim)
  88 {
  89         isl_space *space;
  90         space = isl_space_alloc(ctx, nparam, 0, dim);
  91         space = mark_as_set(space);
  92         return space;
  93 }
  94
  95 /* Mark the space as being that of a parameter domain, by setting
  96  * both tuples to isl_id_none.
  97  */
  98 static __isl_give isl_space *mark_as_params(isl_space *space)
  99 {
 100         if (!space)
 101                 return NULL;
 102         space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
 103         space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
 104         return space;
 105 }
 106
 107 /* Is the space that of a parameter domain?
 108  */
 109 int isl_space_is_params(__isl_keep isl_space *space)
 110 {
 111         if (!space)
 112                 return -1;
 113         if (space->n_in != 0 || space->nested[0] ||
 114             space->n_out != 0 || space->nested[1])
 115                 return 0;
 116         if (space->tuple_id[0] != &isl_id_none)
 117                 return 0;
 118         if (space->tuple_id[1] != &isl_id_none)
 119                 return 0;
 120         return 1;
 121 }
 122
 123 /* Create a space for a parameter domain.
 124  */
 125 __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
 126 {
 127         isl_space *space;
 128         space = isl_space_alloc(ctx, nparam, 0, 0);
 129         space = mark_as_params(space);
 130         return space;
 131 }
 132
 133 static unsigned global_pos(__isl_keep isl_space *dim,
 134                                  enum isl_dim_type type, unsigned pos)
 135 {
 136         struct isl_ctx *ctx = dim->ctx;
 137
 138         switch (type) {
 139         case isl_dim_param:
 140                 isl_assert(ctx, pos < dim->nparam,
 141                             return isl_space_dim(dim, isl_dim_all));
 142                 return pos;
 143         case isl_dim_in:
 144                 isl_assert(ctx, pos < dim->n_in,
 145                             return isl_space_dim(dim, isl_dim_all));
 146                 return pos + dim->nparam;
 147         case isl_dim_out:
 148                 isl_assert(ctx, pos < dim->n_out,
 149                             return isl_space_dim(dim, isl_dim_all));
 150                 return pos + dim->nparam + dim->n_in;
 151         default:
 152                 isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));
 153         }
 154         return isl_space_dim(dim, isl_dim_all);
 155 }
 156
 157 /* Extend length of ids array to the total number of dimensions.
 158  */
 159 static __isl_give isl_space *extend_ids(__isl_take isl_space *dim)
 160 {
 161         isl_id **ids;
 162         int i;
 163
 164         if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)
 165                 return dim;
 166
 167         if (!dim->ids) {
 168                 dim->ids = isl_calloc_array(dim->ctx,
 169                                 isl_id *, isl_space_dim(dim, isl_dim_all));
 170                 if (!dim->ids)
 171                         goto error;
 172         } else {
 173                 ids = isl_realloc_array(dim->ctx, dim->ids,
 174                                 isl_id *, isl_space_dim(dim, isl_dim_all));
 175                 if (!ids)
 176                         goto error;
 177                 dim->ids = ids;
 178                 for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); ++i)
 179                         dim->ids[i] = NULL;
 180         }
 181
 182         dim->n_id = isl_space_dim(dim, isl_dim_all);
 183
 184         return dim;
 185 error:
 186         isl_space_free(dim);
 187         return NULL;
 188 }
 189
 190 static __isl_give isl_space *set_id(__isl_take isl_space *dim,
 191         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 192 {
 193         dim = isl_space_cow(dim);
 194
 195         if (!dim)
 196                 goto error;
 197
 198         pos = global_pos(dim, type, pos);
 199         if (pos == isl_space_dim(dim, isl_dim_all))
 200                 goto error;
 201
 202         if (pos >= dim->n_id) {
 203                 if (!id)
 204                         return dim;
 205                 dim = extend_ids(dim);
 206                 if (!dim)
 207                         goto error;
 208         }
 209
 210         dim->ids[pos] = id;
 211
 212         return dim;
 213 error:
 214         isl_id_free(id);
 215         isl_space_free(dim);
 216         return NULL;
 217 }
 218
 219 static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,
 220                                  enum isl_dim_type type, unsigned pos)
 221 {
 222         if (!dim)
 223                 return NULL;
 224
 225         pos = global_pos(dim, type, pos);
 226         if (pos == isl_space_dim(dim, isl_dim_all))
 227                 return NULL;
 228         if (pos >= dim->n_id)
 229                 return NULL;
 230         return dim->ids[pos];
 231 }
 232
 233 static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)
 234 {
 235         switch (type) {
 236         case isl_dim_param:     return 0;
 237         case isl_dim_in:        return dim->nparam;
 238         case isl_dim_out:       return dim->nparam + dim->n_in;
 239         default:                return 0;
 240         }
 241 }
 242
 243 static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
 244 {
 245         switch (type) {
 246         case isl_dim_param:     return dim->nparam;
 247         case isl_dim_in:        return dim->n_in;
 248         case isl_dim_out:       return dim->n_out;
 249         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
 250         default:                return 0;
 251         }
 252 }
 253
 254 unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)
 255 {
 256         if (!dim)
 257                 return 0;
 258         return n(dim, type);
 259 }
 260
 261 unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
 262 {
 263         if (!dim)
 264                 return 0;
 265         return offset(dim, type);
 266 }
 267
 268 static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
 269         enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
 270         enum isl_dim_type src_type)
 271 {
 272         int i;
 273         isl_id *id;
 274
 275         if (!dst)
 276                 return NULL;
 277
 278         for (i = 0; i < n(src, src_type); ++i) {
 279                 id = get_id(src, src_type, i);
 280                 if (!id)
 281                         continue;
 282                 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
 283                 if (!dst)
 284                         return NULL;
 285         }
 286         return dst;
 287 }
 288
 289 __isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)
 290 {
 291         isl_space *dup;
 292         if (!dim)
 293                 return NULL;
 294         dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
 295         if (!dup)
 296                 return NULL;
 297         if (dim->tuple_id[0] &&
 298             !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0])))
 299                 goto error;
 300         if (dim->tuple_id[1] &&
 301             !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1])))
 302                 goto error;
 303         if (dim->nested[0] && !(dup->nested[0] = isl_space_copy(dim->nested[0])))
 304                 goto error;
 305         if (dim->nested[1] && !(dup->nested[1] = isl_space_copy(dim->nested[1])))
 306                 goto error;
 307         if (!dim->ids)
 308                 return dup;
 309         dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);
 310         dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);
 311         dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);
 312         return dup;
 313 error:
 314         isl_space_free(dup);
 315         return NULL;
 316 }
 317
 318 __isl_give isl_space *isl_space_cow(__isl_take isl_space *dim)
 319 {
 320         if (!dim)
 321                 return NULL;
 322
 323         if (dim->ref == 1)
 324                 return dim;
 325         dim->ref--;
 326         return isl_space_dup(dim);
 327 }
 328
 329 __isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
 330 {
 331         if (!dim)
 332                 return NULL;
 333
 334         dim->ref++;
 335         return dim;
 336 }
 337
 338 void *isl_space_free(__isl_take isl_space *dim)
 339 {
 340         int i;
 341
 342         if (!dim)
 343                 return NULL;
 344
 345         if (--dim->ref > 0)
 346                 return NULL;
 347
 348         isl_id_free(dim->tuple_id[0]);
 349         isl_id_free(dim->tuple_id[1]);
 350
 351         isl_space_free(dim->nested[0]);
 352         isl_space_free(dim->nested[1]);
 353
 354         for (i = 0; i < dim->n_id; ++i)
 355                 isl_id_free(dim->ids[i]);
 356         free(dim->ids);
 357         isl_ctx_deref(dim->ctx);
 358
 359         free(dim);
 360
 361         return NULL;
 362 }
 363
 364 /* Check if "s" is a valid dimension or tuple name.
 365  * We currently only forbid names that look like a number.
 366  *
 367  * s is assumed to be non-NULL.
 368  */
 369 static int name_ok(isl_ctx *ctx, const char *s)
 370 {
 371         char *p;
 372         long dummy;
 373
 374         dummy = strtol(s, &p, 0);
 375         if (p != s)
 376                 isl_die(ctx, isl_error_invalid, "name looks like a number",
 377                         return 0);
 378
 379         return 1;
 380 }
 381
 382 /* Is it possible for the given dimension type to have a tuple id?
 383  */
 384 static int space_can_have_id(__isl_keep isl_space *space,
 385         enum isl_dim_type type)
 386 {
 387         if (!space)
 388                 return 0;
 389         if (isl_space_is_params(space))
 390                 isl_die(space->ctx, isl_error_invalid,
 391                         "parameter spaces don't have tuple ids", return 0);
 392         if (isl_space_is_set(space) && type != isl_dim_set)
 393                 isl_die(space->ctx, isl_error_invalid,
 394                         "set spaces can only have a set id", return 0);
 395         if (type != isl_dim_in && type != isl_dim_out)
 396                 isl_die(space->ctx, isl_error_invalid,
 397                         "only input, output and set tuples can have ids",
 398                         return 0);
 399
 400         return 1;
 401 }
 402
 403 /* Does the tuple have an id?
 404  */
 405 int isl_space_has_tuple_id(__isl_keep isl_space *dim, enum isl_dim_type type)
 406 {
 407         if (!space_can_have_id(dim, type))
 408                 return -1;
 409         return dim->tuple_id[type - isl_dim_in] != NULL;
 410 }
 411
 412 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim,
 413         enum isl_dim_type type)
 414 {
 415         int has_id;
 416
 417         if (!dim)
 418                 return NULL;
 419         has_id = isl_space_has_tuple_id(dim, type);
 420         if (has_id < 0)
 421                 return NULL;
 422         if (!has_id)
 423                 isl_die(dim->ctx, isl_error_invalid,
 424                         "tuple has no id", return NULL);
 425         return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
 426 }
 427
 428 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim,
 429         enum isl_dim_type type, __isl_take isl_id *id)
 430 {
 431         dim = isl_space_cow(dim);
 432         if (!dim || !id)
 433                 goto error;
 434         if (type != isl_dim_in && type != isl_dim_out)
 435                 isl_die(dim->ctx, isl_error_invalid,
 436                         "only input, output and set tuples can have names",
 437                         goto error);
 438
 439         isl_id_free(dim->tuple_id[type - isl_dim_in]);
 440         dim->tuple_id[type - isl_dim_in] = id;
 441
 442         return dim;
 443 error:
 444         isl_id_free(id);
 445         isl_space_free(dim);
 446         return NULL;
 447 }
 448
 449 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,
 450         enum isl_dim_type type)
 451 {
 452         dim = isl_space_cow(dim);
 453         if (!dim)
 454                 return NULL;
 455         if (type != isl_dim_in && type != isl_dim_out)
 456                 isl_die(dim->ctx, isl_error_invalid,
 457                         "only input, output and set tuples can have names",
 458                         goto error);
 459
 460         isl_id_free(dim->tuple_id[type - isl_dim_in]);
 461         dim->tuple_id[type - isl_dim_in] = NULL;
 462
 463         return dim;
 464 error:
 465         isl_space_free(dim);
 466         return NULL;
 467 }
 468
 469 /* Set the id of the given dimension of "space" to "id".
 470  * If the dimension already has an id, then it is replaced.
 471  * If the dimension is a parameter, then we need to change it
 472  * in the nested spaces (if any) as well.
 473  */
 474 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
 475         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 476 {
 477         space = isl_space_cow(space);
 478         if (!space || !id)
 479                 goto error;
 480
 481         if (type == isl_dim_param) {
 482                 int i;
 483
 484                 for (i = 0; i < 2; ++i) {
 485                         if (!space->nested[i])
 486                                 continue;
 487                         space->nested[i] =
 488                                 isl_space_set_dim_id(space->nested[i],
 489                                                 type, pos, isl_id_copy(id));
 490                         if (!space->nested[i])
 491                                 goto error;
 492                 }
 493         }
 494
 495         isl_id_free(get_id(space, type, pos));
 496         return set_id(space, type, pos, id);
 497 error:
 498         isl_id_free(id);
 499         isl_space_free(space);
 500         return NULL;
 501 }
 502
 503 /* Reset the id of the given dimension of "space".
 504  * If the dimension already has an id, then it is removed.
 505  * If the dimension is a parameter, then we need to reset it
 506  * in the nested spaces (if any) as well.
 507  */
 508 __isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
 509         enum isl_dim_type type, unsigned pos)
 510 {
 511         space = isl_space_cow(space);
 512         if (!space)
 513                 goto error;
 514
 515         if (type == isl_dim_param) {
 516                 int i;
 517
 518                 for (i = 0; i < 2; ++i) {
 519                         if (!space->nested[i])
 520                                 continue;
 521                         space->nested[i] =
 522                                 isl_space_reset_dim_id(space->nested[i],
 523                                                         type, pos);
 524                         if (!space->nested[i])
 525                                 goto error;
 526                 }
 527         }
 528
 529         isl_id_free(get_id(space, type, pos));
 530         return set_id(space, type, pos, NULL);
 531 error:
 532         isl_space_free(space);
 533         return NULL;
 534 }
 535
 536 int isl_space_has_dim_id(__isl_keep isl_space *dim,
 537         enum isl_dim_type type, unsigned pos)
 538 {
 539         if (!dim)
 540                 return -1;
 541         return get_id(dim, type, pos) != NULL;
 542 }
 543
 544 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim,
 545         enum isl_dim_type type, unsigned pos)
 546 {
 547         if (!dim)
 548                 return NULL;
 549         if (!get_id(dim, type, pos))
 550                 isl_die(dim->ctx, isl_error_invalid,
 551                         "dim has no id", return NULL);
 552         return isl_id_copy(get_id(dim, type, pos));
 553 }
 554
 555 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim,
 556         enum isl_dim_type type, const char *s)
 557 {
 558         isl_id *id;
 559
 560         if (!dim)
 561                 return NULL;
 562
 563         if (!s)
 564                 return isl_space_reset_tuple_id(dim, type);
 565
 566         if (!name_ok(dim->ctx, s))
 567                 goto error;
 568
 569         id = isl_id_alloc(dim->ctx, s, NULL);
 570         return isl_space_set_tuple_id(dim, type, id);
 571 error:
 572         isl_space_free(dim);
 573         return NULL;
 574 }
 575
 576 /* Does the tuple have a name?
 577  */
 578 int isl_space_has_tuple_name(__isl_keep isl_space *space,
 579         enum isl_dim_type type)
 580 {
 581         isl_id *id;
 582
 583         if (!space_can_have_id(space, type))
 584                 return -1;
 585         id = space->tuple_id[type - isl_dim_in];
 586         return id && id->name;
 587 }
 588
 589 const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,
 590          enum isl_dim_type type)
 591 {
 592         isl_id *id;
 593         if (!dim)
 594                 return NULL;
 595         if (type != isl_dim_in && type != isl_dim_out)
 596                 return NULL;
 597         id = dim->tuple_id[type - isl_dim_in];
 598         return id ? id->name : NULL;
 599 }
 600
 601 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim,
 602                                  enum isl_dim_type type, unsigned pos,
 603                                  const char *s)
 604 {
 605         isl_id *id;
 606
 607         if (!dim)
 608                 return NULL;
 609         if (!s)
 610                 return isl_space_reset_dim_id(dim, type, pos);
 611         if (!name_ok(dim->ctx, s))
 612                 goto error;
 613         id = isl_id_alloc(dim->ctx, s, NULL);
 614         return isl_space_set_dim_id(dim, type, pos, id);
 615 error:
 616         isl_space_free(dim);
 617         return NULL;
 618 }
 619
 620 /* Does the given dimension have a name?
 621  */
 622 int isl_space_has_dim_name(__isl_keep isl_space *space,
 623         enum isl_dim_type type, unsigned pos)
 624 {
 625         isl_id *id;
 626
 627         if (!space)
 628                 return -1;
 629         id = get_id(space, type, pos);
 630         return id && id->name;
 631 }
 632
 633 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim,
 634                                  enum isl_dim_type type, unsigned pos)
 635 {
 636         isl_id *id = get_id(dim, type, pos);
 637         return id ? id->name : NULL;
 638 }
 639
 640 int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type,
 641         __isl_keep isl_id *id)
 642 {
 643         int i;
 644         int offset;
 645         int n;
 646
 647         if (!dim || !id)
 648                 return -1;
 649
 650         offset = isl_space_offset(dim, type);
 651         n = isl_space_dim(dim, type);
 652         for (i = 0; i < n && offset + i < dim->n_id; ++i)
 653                 if (dim->ids[offset + i] == id)
 654                         return i;
 655
 656         return -1;
 657 }
 658
 659 int isl_space_find_dim_by_name(__isl_keep isl_space *space,
 660         enum isl_dim_type type, const char *name)
 661 {
 662         int i;
 663         int offset;
 664         int n;
 665
 666         if (!space || !name)
 667                 return -1;
 668
 669         offset = isl_space_offset(space, type);
 670         n = isl_space_dim(space, type);
 671         for (i = 0; i < n && offset + i < space->n_id; ++i)
 672                 if (space->ids[offset + i]->name &&
 673                     !strcmp(space->ids[offset + i]->name, name))
 674                         return i;
 675
 676         return -1;
 677 }
 678
 679 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,
 680         enum isl_dim_type type)
 681 {
 682         if (!dim)
 683                 return NULL;
 684         if (type == isl_dim_in)
 685                 return dim->tuple_id[0];
 686         if (type == isl_dim_out)
 687                 return dim->tuple_id[1];
 688         return NULL;
 689 }
 690
 691 static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
 692         enum isl_dim_type type)
 693 {
 694         if (!dim)
 695                 return NULL;
 696         if (type == isl_dim_in)
 697                 return dim->nested[0];
 698         if (type == isl_dim_out)
 699                 return dim->nested[1];
 700         return NULL;
 701 }
 702
 703 int isl_space_tuple_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
 704                         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
 705 {
 706         isl_id *id1, *id2;
 707         isl_space *nested1, *nested2;
 708
 709         if (!dim1 || !dim2)
 710                 return -1;
 711
 712         if (dim1 == dim2 && dim1_type == dim2_type)
 713                 return 1;
 714
 715         if (n(dim1, dim1_type) != n(dim2, dim2_type))
 716                 return 0;
 717         id1 = tuple_id(dim1, dim1_type);
 718         id2 = tuple_id(dim2, dim2_type);
 719         if (!id1 ^ !id2)
 720                 return 0;
 721         if (id1 && id1 != id2)
 722                 return 0;
 723         nested1 = nested(dim1, dim1_type);
 724         nested2 = nested(dim2, dim2_type);
 725         if (!nested1 ^ !nested2)
 726                 return 0;
 727         if (nested1 && !isl_space_is_equal(nested1, nested2))
 728                 return 0;
 729         return 1;
 730 }
 731
 732 static int match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
 733         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
 734 {
 735         int i;
 736
 737         if (dim1 == dim2 && dim1_type == dim2_type)
 738                 return 1;
 739
 740         if (!isl_space_tuple_match(dim1, dim1_type, dim2, dim2_type))
 741                 return 0;
 742
 743         if (!dim1->ids && !dim2->ids)
 744                 return 1;
 745
 746         for (i = 0; i < n(dim1, dim1_type); ++i) {
 747                 if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i))
 748                         return 0;
 749         }
 750         return 1;
 751 }
 752
 753 int isl_space_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
 754         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
 755 {
 756         if (!dim1 || !dim2)
 757                 return -1;
 758
 759         return match(dim1, dim1_type, dim2, dim2_type);
 760 }
 761
 762 static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
 763         unsigned first, unsigned n, __isl_keep isl_id **ids)
 764 {
 765         int i;
 766
 767         for (i = 0; i < n ; ++i)
 768                 ids[i] = get_id(dim, type, first + i);
 769 }
 770
 771 __isl_give isl_space *isl_space_extend(__isl_take isl_space *dim,
 772                         unsigned nparam, unsigned n_in, unsigned n_out)
 773 {
 774         isl_id **ids = NULL;
 775
 776         if (!dim)
 777                 return NULL;
 778         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 779                 return dim;
 780
 781         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 782         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 783         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 784
 785         dim = isl_space_cow(dim);
 786         if (!dim)
 787                 goto error;
 788
 789         if (dim->ids) {
 790                 ids = isl_calloc_array(dim->ctx, isl_id *,
 791                                          nparam + n_in + n_out);
 792                 if (!ids)
 793                         goto error;
 794                 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
 795                 get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam);
 796                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in);
 797                 free(dim->ids);
 798                 dim->ids = ids;
 799                 dim->n_id = nparam + n_in + n_out;
 800         }
 801         dim->nparam = nparam;
 802         dim->n_in = n_in;
 803         dim->n_out = n_out;
 804
 805         return dim;
 806 error:
 807         free(ids);
 808         isl_space_free(dim);
 809         return NULL;
 810 }
 811
 812 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *dim,
 813         enum isl_dim_type type, unsigned n)
 814 {
 815         if (!dim)
 816                 return NULL;
 817         dim = isl_space_reset(dim, type);
 818         switch (type) {
 819         case isl_dim_param:
 820                 dim = isl_space_extend(dim,
 821                                         dim->nparam + n, dim->n_in, dim->n_out);
 822                 if (dim && dim->nested[0] &&
 823                     !(dim->nested[0] = isl_space_add_dims(dim->nested[0],
 824                                                     isl_dim_param, n)))
 825                         goto error;
 826                 if (dim && dim->nested[1] &&
 827                     !(dim->nested[1] = isl_space_add_dims(dim->nested[1],
 828                                                     isl_dim_param, n)))
 829                         goto error;
 830                 return dim;
 831         case isl_dim_in:
 832                 return isl_space_extend(dim,
 833                                         dim->nparam, dim->n_in + n, dim->n_out);
 834         case isl_dim_out:
 835                 return isl_space_extend(dim,
 836                                         dim->nparam, dim->n_in, dim->n_out + n);
 837         default:
 838                 isl_die(dim->ctx, isl_error_invalid,
 839                         "cannot add dimensions of specified type", goto error);
 840         }
 841 error:
 842         isl_space_free(dim);
 843         return NULL;
 844 }
 845
 846 static int valid_dim_type(enum isl_dim_type type)
 847 {
 848         switch (type) {
 849         case isl_dim_param:
 850         case isl_dim_in:
 851         case isl_dim_out:
 852                 return 1;
 853         default:
 854                 return 0;
 855         }
 856 }
 857
 858 /* Insert "n" dimensions of type "type" at position "pos".
 859  * If we are inserting parameters, then they are also inserted in
 860  * any nested spaces.
 861  */
 862 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *dim,
 863         enum isl_dim_type type, unsigned pos, unsigned n)
 864 {
 865         isl_id **ids = NULL;
 866
 867         if (!dim)
 868                 return NULL;
 869         if (n == 0)
 870                 return isl_space_reset(dim, type);
 871
 872         if (!valid_dim_type(type))
 873                 isl_die(dim->ctx, isl_error_invalid,
 874                         "cannot insert dimensions of specified type",
 875                         goto error);
 876
 877         isl_assert(dim->ctx, pos <= isl_space_dim(dim, type), goto error);
 878
 879         dim = isl_space_cow(dim);
 880         if (!dim)
 881                 return NULL;
 882
 883         if (dim->ids) {
 884                 enum isl_dim_type t, o = isl_dim_param;
 885                 int off;
 886                 int s[3];
 887                 ids = isl_calloc_array(dim->ctx, isl_id *,
 888                                      dim->nparam + dim->n_in + dim->n_out + n);
 889                 if (!ids)
 890                         goto error;
 891                 off = 0;
 892                 s[isl_dim_param - o] = dim->nparam;
 893                 s[isl_dim_in - o] = dim->n_in;
 894                 s[isl_dim_out - o] = dim->n_out;
 895                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 896                         if (t != type) {
 897                                 get_ids(dim, t, 0, s[t - o], ids + off);
 898                                 off += s[t - o];
 899                         } else {
 900                                 get_ids(dim, t, 0, pos, ids + off);
 901                                 off += pos + n;
 902                                 get_ids(dim, t, pos, s[t - o] - pos, ids + off);
 903                                 off += s[t - o] - pos;
 904                         }
 905                 }
 906                 free(dim->ids);
 907                 dim->ids = ids;
 908                 dim->n_id = dim->nparam + dim->n_in + dim->n_out + n;
 909         }
 910         switch (type) {
 911         case isl_dim_param:     dim->nparam += n; break;
 912         case isl_dim_in:        dim->n_in += n; break;
 913         case isl_dim_out:       dim->n_out += n; break;
 914         default:                ;
 915         }
 916         dim = isl_space_reset(dim, type);
 917
 918         if (type == isl_dim_param) {
 919                 if (dim && dim->nested[0] &&
 920                     !(dim->nested[0] = isl_space_insert_dims(dim->nested[0],
 921                                                     isl_dim_param, pos, n)))
 922                         goto error;
 923                 if (dim && dim->nested[1] &&
 924                     !(dim->nested[1] = isl_space_insert_dims(dim->nested[1],
 925                                                     isl_dim_param, pos, n)))
 926                         goto error;
 927         }
 928
 929         return dim;
 930 error:
 931         isl_space_free(dim);
 932         return NULL;
 933 }
 934
 935 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *dim,
 936         enum isl_dim_type dst_type, unsigned dst_pos,
 937         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 938 {
 939         int i;
 940
 941         if (!dim)
 942                 return NULL;
 943         if (n == 0)
 944                 return dim;
 945
 946         isl_assert(dim->ctx, src_pos + n <= isl_space_dim(dim, src_type),
 947                 goto error);
 948
 949         if (dst_type == src_type && dst_pos == src_pos)
 950                 return dim;
 951
 952         isl_assert(dim->ctx, dst_type != src_type, goto error);
 953
 954         dim = isl_space_reset(dim, src_type);
 955         dim = isl_space_reset(dim, dst_type);
 956
 957         dim = isl_space_cow(dim);
 958         if (!dim)
 959                 return NULL;
 960
 961         if (dim->ids) {
 962                 isl_id **ids;
 963                 enum isl_dim_type t, o = isl_dim_param;
 964                 int off;
 965                 int s[3];
 966                 ids = isl_calloc_array(dim->ctx, isl_id *,
 967                                          dim->nparam + dim->n_in + dim->n_out);
 968                 if (!ids)
 969                         goto error;
 970                 off = 0;
 971                 s[isl_dim_param - o] = dim->nparam;
 972                 s[isl_dim_in - o] = dim->n_in;
 973                 s[isl_dim_out - o] = dim->n_out;
 974                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 975                         if (t == dst_type) {
 976                                 get_ids(dim, t, 0, dst_pos, ids + off);
 977                                 off += dst_pos;
 978                                 get_ids(dim, src_type, src_pos, n, ids + off);
 979                                 off += n;
 980                                 get_ids(dim, t, dst_pos, s[t - o] - dst_pos,
 981                                                 ids + off);
 982                                 off += s[t - o] - dst_pos;
 983                         } else if (t == src_type) {
 984                                 get_ids(dim, t, 0, src_pos, ids + off);
 985                                 off += src_pos;
 986                                 get_ids(dim, t, src_pos + n,
 987                                             s[t - o] - src_pos - n, ids + off);
 988                                 off += s[t - o] - src_pos - n;
 989                         } else {
 990                                 get_ids(dim, t, 0, s[t - o], ids + off);
 991                                 off += s[t - o];
 992                         }
 993                 }
 994                 free(dim->ids);
 995                 dim->ids = ids;
 996                 dim->n_id = dim->nparam + dim->n_in + dim->n_out;
 997         }
 998
 999         switch (dst_type) {
1000         case isl_dim_param:     dim->nparam += n; break;
1001         case isl_dim_in:        dim->n_in += n; break;
1002         case isl_dim_out:       dim->n_out += n; break;
1003         default:                ;
1004         }
1005
1006         switch (src_type) {
1007         case isl_dim_param:     dim->nparam -= n; break;
1008         case isl_dim_in:        dim->n_in -= n; break;
1009         case isl_dim_out:       dim->n_out -= n; break;
1010         default:                ;
1011         }
1012
1013         if (dst_type != isl_dim_param && src_type != isl_dim_param)
1014                 return dim;
1015
1016         for (i = 0; i < 2; ++i) {
1017                 if (!dim->nested[i])
1018                         continue;
1019                 dim->nested[i] = isl_space_replace(dim->nested[i],
1020                                                  isl_dim_param, dim);
1021                 if (!dim->nested[i])
1022                         goto error;
1023         }
1024
1025         return dim;
1026 error:
1027         isl_space_free(dim);
1028         return NULL;
1029 }
1030
1031 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1032         __isl_take isl_space *right)
1033 {
1034         isl_space *dim;
1035
1036         if (!left || !right)
1037                 goto error;
1038
1039         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1040                         goto error);
1041         isl_assert(left->ctx,
1042                 isl_space_tuple_match(left, isl_dim_out, right, isl_dim_in),
1043                 goto error);
1044
1045         dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
1046         if (!dim)
1047                 goto error;
1048
1049         dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
1050         dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
1051         dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
1052
1053         if (dim && left->tuple_id[0] &&
1054             !(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
1055                 goto error;
1056         if (dim && right->tuple_id[1] &&
1057             !(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
1058                 goto error;
1059         if (dim && left->nested[0] &&
1060             !(dim->nested[0] = isl_space_copy(left->nested[0])))
1061                 goto error;
1062         if (dim && right->nested[1] &&
1063             !(dim->nested[1] = isl_space_copy(right->nested[1])))
1064                 goto error;
1065
1066         isl_space_free(left);
1067         isl_space_free(right);
1068
1069         return dim;
1070 error:
1071         isl_space_free(left);
1072         isl_space_free(right);
1073         return NULL;
1074 }
1075
1076 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1077         __isl_take isl_space *right)
1078 {
1079         isl_space *dom1, *dom2, *nest1, *nest2;
1080
1081         if (!left || !right)
1082                 goto error;
1083
1084         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1085                         goto error);
1086
1087         dom1 = isl_space_domain(isl_space_copy(left));
1088         dom2 = isl_space_domain(isl_space_copy(right));
1089         nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1090
1091         dom1 = isl_space_range(left);
1092         dom2 = isl_space_range(right);
1093         nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1094
1095         return isl_space_join(isl_space_reverse(nest1), nest2);
1096 error:
1097         isl_space_free(left);
1098         isl_space_free(right);
1099         return NULL;
1100 }
1101
1102 /* Given two spaces { A -> C } and { B -> C }, construct the space
1103  * { [A -> B] -> C }
1104  */
1105 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1106         __isl_take isl_space *right)
1107 {
1108         isl_space *ran, *dom1, *dom2, *nest;
1109
1110         if (!left || !right)
1111                 goto error;
1112
1113         if (!match(left, isl_dim_param, right, isl_dim_param))
1114                 isl_die(left->ctx, isl_error_invalid,
1115                         "parameters need to match", goto error);
1116         if (!isl_space_tuple_match(left, isl_dim_out, right, isl_dim_out))
1117                 isl_die(left->ctx, isl_error_invalid,
1118                         "ranges need to match", goto error);
1119
1120         ran = isl_space_range(isl_space_copy(left));
1121
1122         dom1 = isl_space_domain(left);
1123         dom2 = isl_space_domain(right);
1124         nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1125
1126         return isl_space_join(isl_space_reverse(nest), ran);
1127 error:
1128         isl_space_free(left);
1129         isl_space_free(right);
1130         return NULL;
1131 }
1132
1133 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1134         __isl_take isl_space *right)
1135 {
1136         isl_space *dom, *ran1, *ran2, *nest;
1137
1138         if (!left || !right)
1139                 goto error;
1140
1141         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1142                         goto error);
1143         if (!isl_space_tuple_match(left, isl_dim_in, right, isl_dim_in))
1144                 isl_die(left->ctx, isl_error_invalid,
1145                         "domains need to match", goto error);
1146
1147         dom = isl_space_domain(isl_space_copy(left));
1148
1149         ran1 = isl_space_range(left);
1150         ran2 = isl_space_range(right);
1151         nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1152
1153         return isl_space_join(isl_space_reverse(dom), nest);
1154 error:
1155         isl_space_free(left);
1156         isl_space_free(right);
1157         return NULL;
1158 }
1159
1160 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *dim)
1161 {
1162         isl_ctx *ctx;
1163         isl_id **ids = NULL;
1164
1165         if (!dim)
1166                 return NULL;
1167         ctx = isl_space_get_ctx(dim);
1168         if (!isl_space_is_set(dim))
1169                 isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1170         dim = isl_space_cow(dim);
1171         if (!dim)
1172                 return NULL;
1173         if (dim->ids) {
1174                 ids = isl_calloc_array(dim->ctx, isl_id *,
1175                                         dim->nparam + dim->n_out + dim->n_out);
1176                 if (!ids)
1177                         goto error;
1178                 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
1179                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->nparam);
1180         }
1181         dim->n_in = dim->n_out;
1182         if (ids) {
1183                 free(dim->ids);
1184                 dim->ids = ids;
1185                 dim->n_id = dim->nparam + dim->n_out + dim->n_out;
1186                 dim = copy_ids(dim, isl_dim_out, 0, dim, isl_dim_in);
1187         }
1188         isl_id_free(dim->tuple_id[0]);
1189         dim->tuple_id[0] = isl_id_copy(dim->tuple_id[1]);
1190         isl_space_free(dim->nested[0]);
1191         dim->nested[0] = isl_space_copy(dim->nested[1]);
1192         return dim;
1193 error:
1194         isl_space_free(dim);
1195         return NULL;
1196 }
1197
1198 __isl_give isl_space *isl_space_map_from_domain_and_range(
1199         __isl_take isl_space *domain, __isl_take isl_space *range)
1200 {
1201         if (!domain || !range)
1202                 goto error;
1203         if (!isl_space_is_set(domain))
1204                 isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1205                         "domain is not a set space", goto error);
1206         if (!isl_space_is_set(range))
1207                 isl_die(isl_space_get_ctx(range), isl_error_invalid,
1208                         "range is not a set space", goto error);
1209         return isl_space_join(isl_space_reverse(domain), range);
1210 error:
1211         isl_space_free(domain);
1212         isl_space_free(range);
1213         return NULL;
1214 }
1215
1216 static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
1217         enum isl_dim_type type,
1218         unsigned first, unsigned n, __isl_take isl_id **ids)
1219 {
1220         int i;
1221
1222         for (i = 0; i < n ; ++i)
1223                 dim = set_id(dim, type, first + i, ids[i]);
1224
1225         return dim;
1226 }
1227
1228 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim)
1229 {
1230         unsigned t;
1231         isl_space *nested;
1232         isl_id **ids = NULL;
1233         isl_id *id;
1234
1235         if (!dim)
1236                 return NULL;
1237         if (match(dim, isl_dim_in, dim, isl_dim_out))
1238                 return dim;
1239
1240         dim = isl_space_cow(dim);
1241         if (!dim)
1242                 return NULL;
1243
1244         id = dim->tuple_id[0];
1245         dim->tuple_id[0] = dim->tuple_id[1];
1246         dim->tuple_id[1] = id;
1247
1248         nested = dim->nested[0];
1249         dim->nested[0] = dim->nested[1];
1250         dim->nested[1] = nested;
1251
1252         if (dim->ids) {
1253                 ids = isl_alloc_array(dim->ctx, isl_id *,
1254                                         dim->n_in + dim->n_out);
1255                 if (!ids)
1256                         goto error;
1257                 get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
1258                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
1259         }
1260
1261         t = dim->n_in;
1262         dim->n_in = dim->n_out;
1263         dim->n_out = t;
1264
1265         if (dim->ids) {
1266                 dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
1267                 dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
1268                 free(ids);
1269         }
1270
1271         return dim;
1272 error:
1273         free(ids);
1274         isl_space_free(dim);
1275         return NULL;
1276 }
1277
1278 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim,
1279         enum isl_dim_type type, unsigned first, unsigned num)
1280 {
1281         int i;
1282
1283         if (!dim)
1284                 return NULL;
1285
1286         if (num == 0)
1287                 return isl_space_reset(dim, type);
1288
1289         if (!valid_dim_type(type))
1290                 isl_die(dim->ctx, isl_error_invalid,
1291                         "cannot drop dimensions of specified type", goto error);
1292
1293         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
1294         dim = isl_space_cow(dim);
1295         if (!dim)
1296                 goto error;
1297         if (dim->ids) {
1298                 dim = extend_ids(dim);
1299                 if (!dim)
1300                         goto error;
1301                 for (i = 0; i < num; ++i)
1302                         isl_id_free(get_id(dim, type, first + i));
1303                 for (i = first+num; i < n(dim, type); ++i)
1304                         set_id(dim, type, i - num, get_id(dim, type, i));
1305                 switch (type) {
1306                 case isl_dim_param:
1307                         get_ids(dim, isl_dim_in, 0, dim->n_in,
1308                                 dim->ids + offset(dim, isl_dim_in) - num);
1309                 case isl_dim_in:
1310                         get_ids(dim, isl_dim_out, 0, dim->n_out,
1311                                 dim->ids + offset(dim, isl_dim_out) - num);
1312                 default:
1313                         ;
1314                 }
1315                 dim->n_id -= num;
1316         }
1317         switch (type) {
1318         case isl_dim_param:     dim->nparam -= num; break;
1319         case isl_dim_in:        dim->n_in -= num; break;
1320         case isl_dim_out:       dim->n_out -= num; break;
1321         default:                ;
1322         }
1323         dim = isl_space_reset(dim, type);
1324         if (type == isl_dim_param) {
1325                 if (dim && dim->nested[0] &&
1326                     !(dim->nested[0] = isl_space_drop_dims(dim->nested[0],
1327                                                     isl_dim_param, first, num)))
1328                         goto error;
1329                 if (dim && dim->nested[1] &&
1330                     !(dim->nested[1] = isl_space_drop_dims(dim->nested[1],
1331                                                     isl_dim_param, first, num)))
1332                         goto error;
1333         }
1334         return dim;
1335 error:
1336         isl_space_free(dim);
1337         return NULL;
1338 }
1339
1340 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1341                 unsigned first, unsigned n)
1342 {
1343         if (!dim)
1344                 return NULL;
1345         return isl_space_drop_dims(dim, isl_dim_in, first, n);
1346 }
1347
1348 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1349                 unsigned first, unsigned n)
1350 {
1351         if (!dim)
1352                 return NULL;
1353         return isl_space_drop_dims(dim, isl_dim_out, first, n);
1354 }
1355
1356 __isl_give isl_space *isl_space_domain(__isl_take isl_space *dim)
1357 {
1358         if (!dim)
1359                 return NULL;
1360         dim = isl_space_drop_outputs(dim, 0, dim->n_out);
1361         dim = isl_space_reverse(dim);
1362         dim = mark_as_set(dim);
1363         return dim;
1364 }
1365
1366 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim)
1367 {
1368         if (!dim)
1369                 return NULL;
1370         if (!isl_space_is_set(dim))
1371                 isl_die(isl_space_get_ctx(dim), isl_error_invalid,
1372                         "not a set space", goto error);
1373         dim = isl_space_reverse(dim);
1374         dim = isl_space_reset(dim, isl_dim_out);
1375         return dim;
1376 error:
1377         isl_space_free(dim);
1378         return NULL;
1379 }
1380
1381 __isl_give isl_space *isl_space_range(__isl_take isl_space *dim)
1382 {
1383         if (!dim)
1384                 return NULL;
1385         dim = isl_space_drop_inputs(dim, 0, dim->n_in);
1386         dim = mark_as_set(dim);
1387         return dim;
1388 }
1389
1390 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim)
1391 {
1392         if (!dim)
1393                 return NULL;
1394         if (!isl_space_is_set(dim))
1395                 isl_die(isl_space_get_ctx(dim), isl_error_invalid,
1396                         "not a set space", goto error);
1397         return isl_space_reset(dim, isl_dim_in);
1398 error:
1399         isl_space_free(dim);
1400         return NULL;
1401 }
1402
1403 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1404 {
1405         if (isl_space_is_params(space))
1406                 return space;
1407         space = isl_space_drop_dims(space,
1408                             isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1409         space = isl_space_drop_dims(space,
1410                             isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1411         space = mark_as_params(space);
1412         return space;
1413 }
1414
1415 __isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
1416 {
1417         if (!space)
1418                 return NULL;
1419         if (!isl_space_is_params(space))
1420                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1421                         "not a parameter space", goto error);
1422         return isl_space_reset(space, isl_dim_set);
1423 error:
1424         isl_space_free(space);
1425         return NULL;
1426 }
1427
1428 __isl_give isl_space *isl_space_as_set_space(__isl_take isl_space *dim)
1429 {
1430         dim = isl_space_cow(dim);
1431         if (!dim)
1432                 return NULL;
1433
1434         dim->n_out += dim->n_in;
1435         dim->n_in = 0;
1436         dim = isl_space_reset(dim, isl_dim_in);
1437         dim = isl_space_reset(dim, isl_dim_out);
1438
1439         return dim;
1440 }
1441
1442 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim,
1443         unsigned n_div)
1444 {
1445         int i;
1446
1447         if (!dim)
1448                 return NULL;
1449         if (n_div == 0 &&
1450             dim->nparam == 0 && dim->n_in == 0 && dim->n_id == 0)
1451                 return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out);
1452         dim = isl_space_cow(dim);
1453         if (!dim)
1454                 return NULL;
1455         dim->n_out += dim->nparam + dim->n_in + n_div;
1456         dim->nparam = 0;
1457         dim->n_in = 0;
1458
1459         for (i = 0; i < dim->n_id; ++i)
1460                 isl_id_free(get_id(dim, isl_dim_out, i));
1461         dim->n_id = 0;
1462         dim = isl_space_reset(dim, isl_dim_in);
1463         dim = isl_space_reset(dim, isl_dim_out);
1464
1465         return dim;
1466 }
1467
1468 /* Are the two spaces the same, including positions and names of parameters?
1469  */
1470 int isl_space_is_equal(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2)
1471 {
1472         if (!dim1 || !dim2)
1473                 return -1;
1474         if (dim1 == dim2)
1475                 return 1;
1476         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1477                isl_space_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1478                isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1479 }
1480
1481 /* Is space1 equal to the domain of space2?
1482  *
1483  * In the internal version we also allow space2 to be the space of a set,
1484  * provided space1 is a parameter space.
1485  */
1486 int isl_space_is_domain_internal(__isl_keep isl_space *space1,
1487         __isl_keep isl_space *space2)
1488 {
1489         if (!space1 || !space2)
1490                 return -1;
1491         if (!isl_space_is_set(space1))
1492                 return 0;
1493         return match(space1, isl_dim_param, space2, isl_dim_param) &&
1494                isl_space_tuple_match(space1, isl_dim_set, space2, isl_dim_in);
1495 }
1496
1497 /* Is space1 equal to the domain of space2?
1498  */
1499 int isl_space_is_domain(__isl_keep isl_space *space1,
1500         __isl_keep isl_space *space2)
1501 {
1502         if (!space2)
1503                 return -1;
1504         if (!isl_space_is_map(space2))
1505                 return 0;
1506         return isl_space_is_domain_internal(space1, space2);
1507 }
1508
1509 /* Is space1 equal to the range of space2?
1510  *
1511  * In the internal version, space2 is allowed to be the space of a set,
1512  * in which case it should be equal to space1.
1513  */
1514 int isl_space_is_range_internal(__isl_keep isl_space *space1,
1515         __isl_keep isl_space *space2)
1516 {
1517         if (!space1 || !space2)
1518                 return -1;
1519         if (!isl_space_is_set(space1))
1520                 return 0;
1521         return match(space1, isl_dim_param, space2, isl_dim_param) &&
1522                isl_space_tuple_match(space1, isl_dim_set, space2, isl_dim_out);
1523 }
1524
1525 /* Is space1 equal to the range of space2?
1526  */
1527 int isl_space_is_range(__isl_keep isl_space *space1,
1528         __isl_keep isl_space *space2)
1529 {
1530         if (!space2)
1531                 return -1;
1532         if (!isl_space_is_map(space2))
1533                 return 0;
1534         return isl_space_is_range_internal(space1, space2);
1535 }
1536
1537 int isl_space_compatible(__isl_keep isl_space *dim1,
1538         __isl_keep isl_space *dim2)
1539 {
1540         return dim1->nparam == dim2->nparam &&
1541                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1542 }
1543
1544 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_space *dim)
1545 {
1546         int i;
1547         isl_id *id;
1548
1549         if (!dim)
1550                 return hash;
1551
1552         isl_hash_byte(hash, dim->nparam % 256);
1553         isl_hash_byte(hash, dim->n_in % 256);
1554         isl_hash_byte(hash, dim->n_out % 256);
1555
1556         for (i = 0; i < dim->nparam; ++i) {
1557                 id = get_id(dim, isl_dim_param, i);
1558                 hash = isl_hash_id(hash, id);
1559         }
1560
1561         id = tuple_id(dim, isl_dim_in);
1562         hash = isl_hash_id(hash, id);
1563         id = tuple_id(dim, isl_dim_out);
1564         hash = isl_hash_id(hash, id);
1565
1566         hash = isl_hash_dim(hash, dim->nested[0]);
1567         hash = isl_hash_dim(hash, dim->nested[1]);
1568
1569         return hash;
1570 }
1571
1572 uint32_t isl_space_get_hash(__isl_keep isl_space *dim)
1573 {
1574         uint32_t hash;
1575
1576         if (!dim)
1577                 return 0;
1578
1579         hash = isl_hash_init();
1580         hash = isl_hash_dim(hash, dim);
1581
1582         return hash;
1583 }
1584
1585 int isl_space_is_wrapping(__isl_keep isl_space *dim)
1586 {
1587         if (!dim)
1588                 return -1;
1589
1590         if (!isl_space_is_set(dim))
1591                 return 0;
1592
1593         return dim->nested[1] != NULL;
1594 }
1595
1596 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim)
1597 {
1598         isl_space *wrap;
1599
1600         if (!dim)
1601                 return NULL;
1602
1603         wrap = isl_space_set_alloc(dim->ctx,
1604                                     dim->nparam, dim->n_in + dim->n_out);
1605
1606         wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
1607         wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
1608         wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1609
1610         if (!wrap)
1611                 goto error;
1612
1613         wrap->nested[1] = dim;
1614
1615         return wrap;
1616 error:
1617         isl_space_free(dim);
1618         return NULL;
1619 }
1620
1621 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim)
1622 {
1623         isl_space *unwrap;
1624
1625         if (!dim)
1626                 return NULL;
1627
1628         if (!isl_space_is_wrapping(dim))
1629                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping space",
1630                         goto error);
1631
1632         unwrap = isl_space_copy(dim->nested[1]);
1633         isl_space_free(dim);
1634
1635         return unwrap;
1636 error:
1637         isl_space_free(dim);
1638         return NULL;
1639 }
1640
1641 int isl_space_is_named_or_nested(__isl_keep isl_space *dim, enum isl_dim_type type)
1642 {
1643         if (type != isl_dim_in && type != isl_dim_out)
1644                 return 0;
1645         if (!dim)
1646                 return -1;
1647         if (dim->tuple_id[type - isl_dim_in])
1648                 return 1;
1649         if (dim->nested[type - isl_dim_in])
1650                 return 1;
1651         return 0;
1652 }
1653
1654 int isl_space_may_be_set(__isl_keep isl_space *dim)
1655 {
1656         if (!dim)
1657                 return -1;
1658         if (isl_space_is_set(dim))
1659                 return 1;
1660         if (isl_space_dim(dim, isl_dim_in) != 0)
1661                 return 0;
1662         if (isl_space_is_named_or_nested(dim, isl_dim_in))
1663                 return 0;
1664         return 1;
1665 }
1666
1667 __isl_give isl_space *isl_space_reset(__isl_take isl_space *dim,
1668         enum isl_dim_type type)
1669 {
1670         if (!isl_space_is_named_or_nested(dim, type))
1671                 return dim;
1672
1673         dim = isl_space_cow(dim);
1674         if (!dim)
1675                 return NULL;
1676
1677         isl_id_free(dim->tuple_id[type - isl_dim_in]);
1678         dim->tuple_id[type - isl_dim_in] = NULL;
1679         isl_space_free(dim->nested[type - isl_dim_in]);
1680         dim->nested[type - isl_dim_in] = NULL;
1681
1682         return dim;
1683 }
1684
1685 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim)
1686 {
1687         if (!dim)
1688                 return NULL;
1689         if (!dim->nested[0] && !dim->nested[1])
1690                 return dim;
1691
1692         if (dim->nested[0])
1693                 dim = isl_space_reset(dim, isl_dim_in);
1694         if (dim && dim->nested[1])
1695                 dim = isl_space_reset(dim, isl_dim_out);
1696
1697         return dim;
1698 }
1699
1700 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *dim)
1701 {
1702         if (!dim)
1703                 return NULL;
1704         if (!dim->nested[0])
1705                 return dim;
1706
1707         return isl_space_reset(dim, isl_dim_in);
1708 }
1709
1710 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *dim)
1711 {
1712         if (!dim)
1713                 return NULL;
1714         if (!dim->nested[1])
1715                 return dim;
1716
1717         return isl_space_reset(dim, isl_dim_out);
1718 }
1719
1720 /* Replace the dimensions of the given type of dst by those of src.
1721  */
1722 __isl_give isl_space *isl_space_replace(__isl_take isl_space *dst,
1723         enum isl_dim_type type, __isl_keep isl_space *src)
1724 {
1725         dst = isl_space_cow(dst);
1726
1727         if (!dst || !src)
1728                 goto error;
1729
1730         dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
1731         dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
1732         dst = copy_ids(dst, type, 0, src, type);
1733
1734         if (dst && type == isl_dim_param) {
1735                 int i;
1736                 for (i = 0; i <= 1; ++i) {
1737                         if (!dst->nested[i])
1738                                 continue;
1739                         dst->nested[i] = isl_space_replace(dst->nested[i],
1740                                                          type, src);
1741                         if (!dst->nested[i])
1742                                 goto error;
1743                 }
1744         }
1745
1746         return dst;
1747 error:
1748         isl_space_free(dst);
1749         return NULL;
1750 }
1751
1752 /* Given a dimension specification "dim" of a set, create a dimension
1753  * specification for the lift of the set.  In particular, the result
1754  * is of the form [dim -> local[..]], with n_local variables in the
1755  * range of the wrapped map.
1756  */
1757 __isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local)
1758 {
1759         isl_space *local_dim;
1760
1761         if (!dim)
1762                 return NULL;
1763
1764         local_dim = isl_space_dup(dim);
1765         local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out);
1766         local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local);
1767         local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local");
1768         dim = isl_space_join(isl_space_from_domain(dim),
1769                             isl_space_from_range(local_dim));
1770         dim = isl_space_wrap(dim);
1771         dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted");
1772
1773         return dim;
1774 }
1775
1776 int isl_space_can_zip(__isl_keep isl_space *dim)
1777 {
1778         if (!dim)
1779                 return -1;
1780
1781         return dim->nested[0] && dim->nested[1];
1782 }
1783
1784 __isl_give isl_space *isl_space_zip(__isl_take isl_space *dim)
1785 {
1786         isl_space *dom, *ran;
1787         isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1788
1789         if (!isl_space_can_zip(dim))
1790                 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1791                         goto error);
1792
1793         if (!dim)
1794                 return NULL;
1795         dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim)));
1796         ran = isl_space_unwrap(isl_space_range(dim));
1797         dom_dom = isl_space_domain(isl_space_copy(dom));
1798         dom_ran = isl_space_range(dom);
1799         ran_dom = isl_space_domain(isl_space_copy(ran));
1800         ran_ran = isl_space_range(ran);
1801         dom = isl_space_join(isl_space_from_domain(dom_dom),
1802                            isl_space_from_range(ran_dom));
1803         ran = isl_space_join(isl_space_from_domain(dom_ran),
1804                            isl_space_from_range(ran_ran));
1805         return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1806                             isl_space_from_range(isl_space_wrap(ran)));
1807 error:
1808         isl_space_free(dim);
1809         return NULL;
1810 }
1811
1812 /* Can we apply isl_space_curry to "space"?
1813  * That is, does it have a nested relation in its domain?
1814  */
1815 int isl_space_can_curry(__isl_keep isl_space *space)
1816 {
1817         if (!space)
1818                 return -1;
1819
1820         return !!space->nested[0];
1821 }
1822
1823 /* Given a space (A -> B) -> C, return the corresponding space
1824  * A -> (B -> C).
1825  */
1826 __isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
1827 {
1828         isl_space *dom, *ran;
1829         isl_space *dom_dom, *dom_ran;
1830
1831         if (!space)
1832                 return NULL;
1833
1834         if (!isl_space_can_curry(space))
1835                 isl_die(space->ctx, isl_error_invalid,
1836                         "space cannot be curried", goto error);
1837
1838         dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
1839         ran = isl_space_range(space);
1840         dom_dom = isl_space_domain(isl_space_copy(dom));
1841         dom_ran = isl_space_range(dom);
1842         ran = isl_space_join(isl_space_from_domain(dom_ran),
1843                            isl_space_from_range(ran));
1844         return isl_space_join(isl_space_from_domain(dom_dom),
1845                             isl_space_from_range(isl_space_wrap(ran)));
1846 error:
1847         isl_space_free(space);
1848         return NULL;
1849 }
1850
1851 /* Can we apply isl_space_uncurry to "space"?
1852  * That is, does it have a nested relation in its range?
1853  */
1854 int isl_space_can_uncurry(__isl_keep isl_space *space)
1855 {
1856         if (!space)
1857                 return -1;
1858
1859         return !!space->nested[1];
1860 }
1861
1862 /* Given a space A -> (B -> C), return the corresponding space
1863  * (A -> B) -> C.
1864  */
1865 __isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
1866 {
1867         isl_space *dom, *ran;
1868         isl_space *ran_dom, *ran_ran;
1869
1870         if (!space)
1871                 return NULL;
1872
1873         if (!isl_space_can_uncurry(space))
1874                 isl_die(space->ctx, isl_error_invalid,
1875                         "space cannot be uncurried",
1876                         return isl_space_free(space));
1877
1878         dom = isl_space_domain(isl_space_copy(space));
1879         ran = isl_space_unwrap(isl_space_range(space));
1880         ran_dom = isl_space_domain(isl_space_copy(ran));
1881         ran_ran = isl_space_range(ran);
1882         dom = isl_space_join(isl_space_from_domain(dom),
1883                            isl_space_from_range(ran_dom));
1884         return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1885                             isl_space_from_range(ran_ran));
1886 }
1887
1888 int isl_space_has_named_params(__isl_keep isl_space *dim)
1889 {
1890         int i;
1891         unsigned off;
1892
1893         if (!dim)
1894                 return -1;
1895         if (dim->nparam == 0)
1896                 return 1;
1897         off = isl_space_offset(dim, isl_dim_param);
1898         if (off + dim->nparam > dim->n_id)
1899                 return 0;
1900         for (i = 0; i < dim->nparam; ++i)
1901                 if (!dim->ids[off + i])
1902                         return 0;
1903         return 1;
1904 }
1905
1906 /* Align the initial parameters of dim1 to match the order in dim2.
1907  */
1908 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1,
1909         __isl_take isl_space *dim2)
1910 {
1911         isl_reordering *exp;
1912
1913         if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2))
1914                 isl_die(isl_space_get_ctx(dim1), isl_error_invalid,
1915                         "parameter alignment requires named parameters",
1916                         goto error);
1917
1918         dim2 = isl_space_params(dim2);
1919         exp = isl_parameter_alignment_reordering(dim1, dim2);
1920         exp = isl_reordering_extend_space(exp, dim1);
1921         isl_space_free(dim2);
1922         if (!exp)
1923                 return NULL;
1924         dim1 = isl_space_copy(exp->dim);
1925         isl_reordering_free(exp);
1926         return dim1;
1927 error:
1928         isl_space_free(dim1);
1929         isl_space_free(dim2);
1930         return NULL;
1931 }
1932
1933 /* Given the space of set (domain), construct a space for a map
1934  * with as domain the given space and as range the range of "model".
1935  */
1936 __isl_give isl_space *isl_space_extend_domain_with_range(
1937         __isl_take isl_space *space, __isl_take isl_space *model)
1938 {
1939         if (!model)
1940                 goto error;
1941
1942         space = isl_space_from_domain(space);
1943         space = isl_space_add_dims(space, isl_dim_out,
1944                                     isl_space_dim(model, isl_dim_out));
1945         if (isl_space_has_tuple_id(model, isl_dim_out))
1946                 space = isl_space_set_tuple_id(space, isl_dim_out,
1947                                 isl_space_get_tuple_id(model, isl_dim_out));
1948         if (!space)
1949                 goto error;
1950         if (model->nested[1]) {
1951                 isl_space *nested = isl_space_copy(model->nested[1]);
1952                 int n_nested, n_space;
1953                 nested = isl_space_align_params(nested, isl_space_copy(space));
1954                 n_nested = isl_space_dim(nested, isl_dim_param);
1955                 n_space = isl_space_dim(space, isl_dim_param);
1956                 if (n_nested > n_space)
1957                         nested = isl_space_drop_dims(nested, isl_dim_param,
1958                                                 n_space, n_nested - n_space);
1959                 if (!nested)
1960                         goto error;
1961                 space->nested[1] = nested;
1962         }
1963         isl_space_free(model);
1964         return space;
1965 error:
1966         isl_space_free(model);
1967         isl_space_free(space);
1968         return NULL;
1969 }