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 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 <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 __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
  52                         unsigned nparam, unsigned dim)
  53 {
  54         return isl_space_alloc(ctx, nparam, 0, dim);
  55 }
  56
  57 /* Create a space for a parameter domain.
  58  */
  59 __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
  60 {
  61         isl_space *space;
  62         space = isl_space_alloc(ctx, nparam, 0, 0);
  63         return space;
  64 }
  65
  66 static unsigned global_pos(__isl_keep isl_space *dim,
  67                                  enum isl_dim_type type, unsigned pos)
  68 {
  69         struct isl_ctx *ctx = dim->ctx;
  70
  71         switch (type) {
  72         case isl_dim_param:
  73                 isl_assert(ctx, pos < dim->nparam,
  74                             return isl_space_dim(dim, isl_dim_all));
  75                 return pos;
  76         case isl_dim_in:
  77                 isl_assert(ctx, pos < dim->n_in,
  78                             return isl_space_dim(dim, isl_dim_all));
  79                 return pos + dim->nparam;
  80         case isl_dim_out:
  81                 isl_assert(ctx, pos < dim->n_out,
  82                             return isl_space_dim(dim, isl_dim_all));
  83                 return pos + dim->nparam + dim->n_in;
  84         default:
  85                 isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));
  86         }
  87         return isl_space_dim(dim, isl_dim_all);
  88 }
  89
  90 /* Extend length of ids array to the total number of dimensions.
  91  */
  92 static __isl_give isl_space *extend_ids(__isl_take isl_space *dim)
  93 {
  94         isl_id **ids;
  95         int i;
  96
  97         if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)
  98                 return dim;
  99
 100         if (!dim->ids) {
 101                 dim->ids = isl_calloc_array(dim->ctx,
 102                                 isl_id *, isl_space_dim(dim, isl_dim_all));
 103                 if (!dim->ids)
 104                         goto error;
 105         } else {
 106                 ids = isl_realloc_array(dim->ctx, dim->ids,
 107                                 isl_id *, isl_space_dim(dim, isl_dim_all));
 108                 if (!ids)
 109                         goto error;
 110                 dim->ids = ids;
 111                 for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); ++i)
 112                         dim->ids[i] = NULL;
 113         }
 114
 115         dim->n_id = isl_space_dim(dim, isl_dim_all);
 116
 117         return dim;
 118 error:
 119         isl_space_free(dim);
 120         return NULL;
 121 }
 122
 123 static __isl_give isl_space *set_id(__isl_take isl_space *dim,
 124         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 125 {
 126         dim = isl_space_cow(dim);
 127
 128         if (!dim)
 129                 goto error;
 130
 131         pos = global_pos(dim, type, pos);
 132         if (pos == isl_space_dim(dim, isl_dim_all))
 133                 goto error;
 134
 135         if (pos >= dim->n_id) {
 136                 if (!id)
 137                         return dim;
 138                 dim = extend_ids(dim);
 139                 if (!dim)
 140                         goto error;
 141         }
 142
 143         dim->ids[pos] = id;
 144
 145         return dim;
 146 error:
 147         isl_id_free(id);
 148         isl_space_free(dim);
 149         return NULL;
 150 }
 151
 152 static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,
 153                                  enum isl_dim_type type, unsigned pos)
 154 {
 155         if (!dim)
 156                 return NULL;
 157
 158         pos = global_pos(dim, type, pos);
 159         if (pos == isl_space_dim(dim, isl_dim_all))
 160                 return NULL;
 161         if (pos >= dim->n_id)
 162                 return NULL;
 163         return dim->ids[pos];
 164 }
 165
 166 static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)
 167 {
 168         switch (type) {
 169         case isl_dim_param:     return 0;
 170         case isl_dim_in:        return dim->nparam;
 171         case isl_dim_out:       return dim->nparam + dim->n_in;
 172         default:                return 0;
 173         }
 174 }
 175
 176 static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
 177 {
 178         switch (type) {
 179         case isl_dim_param:     return dim->nparam;
 180         case isl_dim_in:        return dim->n_in;
 181         case isl_dim_out:       return dim->n_out;
 182         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
 183         default:                return 0;
 184         }
 185 }
 186
 187 unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)
 188 {
 189         if (!dim)
 190                 return 0;
 191         return n(dim, type);
 192 }
 193
 194 unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
 195 {
 196         if (!dim)
 197                 return 0;
 198         return offset(dim, type);
 199 }
 200
 201 static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
 202         enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
 203         enum isl_dim_type src_type)
 204 {
 205         int i;
 206         isl_id *id;
 207
 208         if (!dst)
 209                 return NULL;
 210
 211         for (i = 0; i < n(src, src_type); ++i) {
 212                 id = get_id(src, src_type, i);
 213                 if (!id)
 214                         continue;
 215                 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
 216                 if (!dst)
 217                         return NULL;
 218         }
 219         return dst;
 220 }
 221
 222 __isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)
 223 {
 224         isl_space *dup;
 225         if (!dim)
 226                 return NULL;
 227         dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
 228         if (dim->tuple_id[0] &&
 229             !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0])))
 230                 goto error;
 231         if (dim->tuple_id[1] &&
 232             !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1])))
 233                 goto error;
 234         if (dim->nested[0] && !(dup->nested[0] = isl_space_copy(dim->nested[0])))
 235                 goto error;
 236         if (dim->nested[1] && !(dup->nested[1] = isl_space_copy(dim->nested[1])))
 237                 goto error;
 238         if (!dim->ids)
 239                 return dup;
 240         dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);
 241         dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);
 242         dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);
 243         return dup;
 244 error:
 245         isl_space_free(dup);
 246         return NULL;
 247 }
 248
 249 __isl_give isl_space *isl_space_cow(__isl_take isl_space *dim)
 250 {
 251         if (!dim)
 252                 return NULL;
 253
 254         if (dim->ref == 1)
 255                 return dim;
 256         dim->ref--;
 257         return isl_space_dup(dim);
 258 }
 259
 260 __isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
 261 {
 262         if (!dim)
 263                 return NULL;
 264
 265         dim->ref++;
 266         return dim;
 267 }
 268
 269 void isl_space_free(__isl_take isl_space *dim)
 270 {
 271         int i;
 272
 273         if (!dim)
 274                 return;
 275
 276         if (--dim->ref > 0)
 277                 return;
 278
 279         isl_id_free(dim->tuple_id[0]);
 280         isl_id_free(dim->tuple_id[1]);
 281
 282         isl_space_free(dim->nested[0]);
 283         isl_space_free(dim->nested[1]);
 284
 285         for (i = 0; i < dim->n_id; ++i)
 286                 isl_id_free(dim->ids[i]);
 287         free(dim->ids);
 288         isl_ctx_deref(dim->ctx);
 289
 290         free(dim);
 291 }
 292
 293 static int name_ok(isl_ctx *ctx, const char *s)
 294 {
 295         char *p;
 296         long dummy;
 297
 298         dummy = strtol(s, &p, 0);
 299         if (p != s)
 300                 isl_die(ctx, isl_error_invalid, "name looks like a number",
 301                         return 0);
 302
 303         return 1;
 304 }
 305
 306 int isl_space_has_tuple_id(__isl_keep isl_space *dim, enum isl_dim_type type)
 307 {
 308         if (!dim)
 309                 return -1;
 310         if (type != isl_dim_in && type != isl_dim_out)
 311                 isl_die(dim->ctx, isl_error_invalid,
 312                         "only input, output and set tuples can have ids",
 313                         return -1);
 314         return dim->tuple_id[type - isl_dim_in] != NULL;
 315 }
 316
 317 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim,
 318         enum isl_dim_type type)
 319 {
 320         if (!dim)
 321                 return NULL;
 322         if (type != isl_dim_in && type != isl_dim_out)
 323                 isl_die(dim->ctx, isl_error_invalid,
 324                         "only input, output and set tuples can have ids",
 325                         return NULL);
 326         if (!dim->tuple_id[type - isl_dim_in])
 327                 isl_die(dim->ctx, isl_error_invalid,
 328                         "tuple has no id", return NULL);
 329         return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
 330 }
 331
 332 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim,
 333         enum isl_dim_type type, __isl_take isl_id *id)
 334 {
 335         dim = isl_space_cow(dim);
 336         if (!dim || !id)
 337                 goto error;
 338         if (type != isl_dim_in && type != isl_dim_out)
 339                 isl_die(dim->ctx, isl_error_invalid,
 340                         "only input, output and set tuples can have names",
 341                         goto error);
 342
 343         isl_id_free(dim->tuple_id[type - isl_dim_in]);
 344         dim->tuple_id[type - isl_dim_in] = id;
 345
 346         return dim;
 347 error:
 348         isl_id_free(id);
 349         isl_space_free(dim);
 350         return NULL;
 351 }
 352
 353 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,
 354         enum isl_dim_type type)
 355 {
 356         dim = isl_space_cow(dim);
 357         if (!dim)
 358                 return NULL;
 359         if (type != isl_dim_in && type != isl_dim_out)
 360                 isl_die(dim->ctx, isl_error_invalid,
 361                         "only input, output and set tuples can have names",
 362                         goto error);
 363
 364         isl_id_free(dim->tuple_id[type - isl_dim_in]);
 365         dim->tuple_id[type - isl_dim_in] = NULL;
 366
 367         return dim;
 368 error:
 369         isl_space_free(dim);
 370         return NULL;
 371 }
 372
 373 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *dim,
 374         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 375 {
 376         dim = isl_space_cow(dim);
 377         if (!dim || !id)
 378                 goto error;
 379         isl_id_free(get_id(dim, type, pos));
 380         return set_id(dim, type, pos, id);
 381 error:
 382         isl_id_free(id);
 383         isl_space_free(dim);
 384         return NULL;
 385 }
 386
 387 int isl_space_has_dim_id(__isl_keep isl_space *dim,
 388         enum isl_dim_type type, unsigned pos)
 389 {
 390         if (!dim)
 391                 return -1;
 392         return get_id(dim, type, pos) != NULL;
 393 }
 394
 395 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim,
 396         enum isl_dim_type type, unsigned pos)
 397 {
 398         if (!dim)
 399                 return NULL;
 400         if (!get_id(dim, type, pos))
 401                 isl_die(dim->ctx, isl_error_invalid,
 402                         "dim has no id", return NULL);
 403         return isl_id_copy(get_id(dim, type, pos));
 404 }
 405
 406 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim,
 407         enum isl_dim_type type, const char *s)
 408 {
 409         isl_id *id;
 410
 411         if (!dim)
 412                 return NULL;
 413
 414         if (!s)
 415                 return isl_space_reset_tuple_id(dim, type);
 416
 417         if (!name_ok(dim->ctx, s))
 418                 goto error;
 419
 420         id = isl_id_alloc(dim->ctx, s, NULL);
 421         return isl_space_set_tuple_id(dim, type, id);
 422 error:
 423         isl_space_free(dim);
 424         return NULL;
 425 }
 426
 427 const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,
 428          enum isl_dim_type type)
 429 {
 430         isl_id *id;
 431         if (!dim)
 432                 return NULL;
 433         if (type != isl_dim_in && type != isl_dim_out)
 434                 return NULL;
 435         id = dim->tuple_id[type - isl_dim_in];
 436         return id ? id->name : NULL;
 437 }
 438
 439 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim,
 440                                  enum isl_dim_type type, unsigned pos,
 441                                  const char *s)
 442 {
 443         isl_id *id;
 444
 445         if (!dim)
 446                 return NULL;
 447         if (!name_ok(dim->ctx, s))
 448                 goto error;
 449         id = isl_id_alloc(dim->ctx, s, NULL);
 450         return isl_space_set_dim_id(dim, type, pos, id);
 451 error:
 452         isl_space_free(dim);
 453         return NULL;
 454 }
 455
 456 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim,
 457                                  enum isl_dim_type type, unsigned pos)
 458 {
 459         isl_id *id = get_id(dim, type, pos);
 460         return id ? id->name : NULL;
 461 }
 462
 463 int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type,
 464         __isl_keep isl_id *id)
 465 {
 466         int i;
 467         int offset;
 468         int n;
 469
 470         if (!dim || !id)
 471                 return -1;
 472
 473         offset = isl_space_offset(dim, type);
 474         n = isl_space_dim(dim, type);
 475         for (i = 0; i < n && offset + i < dim->n_id; ++i)
 476                 if (dim->ids[offset + i] == id)
 477                         return i;
 478
 479         return -1;
 480 }
 481
 482 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,
 483         enum isl_dim_type type)
 484 {
 485         if (!dim)
 486                 return NULL;
 487         if (type == isl_dim_in)
 488                 return dim->tuple_id[0];
 489         if (type == isl_dim_out)
 490                 return dim->tuple_id[1];
 491         return NULL;
 492 }
 493
 494 static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
 495         enum isl_dim_type type)
 496 {
 497         if (!dim)
 498                 return NULL;
 499         if (type == isl_dim_in)
 500                 return dim->nested[0];
 501         if (type == isl_dim_out)
 502                 return dim->nested[1];
 503         return NULL;
 504 }
 505
 506 int isl_space_tuple_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
 507                         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
 508 {
 509         isl_id *id1, *id2;
 510         isl_space *nested1, *nested2;
 511
 512         if (!dim1 || !dim2)
 513                 return -1;
 514
 515         if (dim1 == dim2 && dim1_type == dim2_type)
 516                 return 1;
 517
 518         if (n(dim1, dim1_type) != n(dim2, dim2_type))
 519                 return 0;
 520         id1 = tuple_id(dim1, dim1_type);
 521         id2 = tuple_id(dim2, dim2_type);
 522         if (!id1 ^ !id2)
 523                 return 0;
 524         if (id1 && id1 != id2)
 525                 return 0;
 526         nested1 = nested(dim1, dim1_type);
 527         nested2 = nested(dim2, dim2_type);
 528         if (!nested1 ^ !nested2)
 529                 return 0;
 530         if (nested1 && !isl_space_is_equal(nested1, nested2))
 531                 return 0;
 532         return 1;
 533 }
 534
 535 static int match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
 536         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
 537 {
 538         int i;
 539
 540         if (dim1 == dim2 && dim1_type == dim2_type)
 541                 return 1;
 542
 543         if (!isl_space_tuple_match(dim1, dim1_type, dim2, dim2_type))
 544                 return 0;
 545
 546         if (!dim1->ids && !dim2->ids)
 547                 return 1;
 548
 549         for (i = 0; i < n(dim1, dim1_type); ++i) {
 550                 if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i))
 551                         return 0;
 552         }
 553         return 1;
 554 }
 555
 556 int isl_space_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
 557         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
 558 {
 559         if (!dim1 || !dim2)
 560                 return -1;
 561
 562         return match(dim1, dim1_type, dim2, dim2_type);
 563 }
 564
 565 static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
 566         unsigned first, unsigned n, __isl_keep isl_id **ids)
 567 {
 568         int i;
 569
 570         for (i = 0; i < n ; ++i)
 571                 ids[i] = get_id(dim, type, first + i);
 572 }
 573
 574 __isl_give isl_space *isl_space_extend(__isl_take isl_space *dim,
 575                         unsigned nparam, unsigned n_in, unsigned n_out)
 576 {
 577         isl_id **ids = NULL;
 578
 579         if (!dim)
 580                 return NULL;
 581         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
 582                 return dim;
 583
 584         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
 585         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
 586         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
 587
 588         dim = isl_space_cow(dim);
 589
 590         if (dim->ids) {
 591                 ids = isl_calloc_array(dim->ctx, isl_id *,
 592                                          nparam + n_in + n_out);
 593                 if (!ids)
 594                         goto error;
 595                 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
 596                 get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam);
 597                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in);
 598                 free(dim->ids);
 599                 dim->ids = ids;
 600                 dim->n_id = nparam + n_in + n_out;
 601         }
 602         dim->nparam = nparam;
 603         dim->n_in = n_in;
 604         dim->n_out = n_out;
 605
 606         return dim;
 607 error:
 608         free(ids);
 609         isl_space_free(dim);
 610         return NULL;
 611 }
 612
 613 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *dim,
 614         enum isl_dim_type type, unsigned n)
 615 {
 616         if (!dim)
 617                 return NULL;
 618         dim = isl_space_reset(dim, type);
 619         switch (type) {
 620         case isl_dim_param:
 621                 dim = isl_space_extend(dim,
 622                                         dim->nparam + n, dim->n_in, dim->n_out);
 623                 if (dim && dim->nested[0] &&
 624                     !(dim->nested[0] = isl_space_add_dims(dim->nested[0],
 625                                                     isl_dim_param, n)))
 626                         goto error;
 627                 if (dim && dim->nested[1] &&
 628                     !(dim->nested[1] = isl_space_add_dims(dim->nested[1],
 629                                                     isl_dim_param, n)))
 630                         goto error;
 631                 return dim;
 632         case isl_dim_in:
 633                 return isl_space_extend(dim,
 634                                         dim->nparam, dim->n_in + n, dim->n_out);
 635         case isl_dim_out:
 636                 return isl_space_extend(dim,
 637                                         dim->nparam, dim->n_in, dim->n_out + n);
 638         default:
 639                 isl_die(dim->ctx, isl_error_invalid,
 640                         "cannot add dimensions of specified type", goto error);
 641         }
 642 error:
 643         isl_space_free(dim);
 644         return NULL;
 645 }
 646
 647 static int valid_dim_type(enum isl_dim_type type)
 648 {
 649         switch (type) {
 650         case isl_dim_param:
 651         case isl_dim_in:
 652         case isl_dim_out:
 653                 return 1;
 654         default:
 655                 return 0;
 656         }
 657 }
 658
 659 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *dim,
 660         enum isl_dim_type type, unsigned pos, unsigned n)
 661 {
 662         isl_id **ids = NULL;
 663
 664         if (!dim)
 665                 return NULL;
 666         if (n == 0)
 667                 return isl_space_reset(dim, type);
 668
 669         if (!valid_dim_type(type))
 670                 isl_die(dim->ctx, isl_error_invalid,
 671                         "cannot insert dimensions of specified type",
 672                         goto error);
 673
 674         isl_assert(dim->ctx, pos <= isl_space_dim(dim, type), goto error);
 675
 676         dim = isl_space_cow(dim);
 677         if (!dim)
 678                 return NULL;
 679
 680         if (dim->ids) {
 681                 enum isl_dim_type t;
 682                 int off;
 683                 int s[3];
 684                 int *size = s - isl_dim_param;
 685                 ids = isl_calloc_array(dim->ctx, isl_id *,
 686                                      dim->nparam + dim->n_in + dim->n_out + n);
 687                 if (!ids)
 688                         goto error;
 689                 off = 0;
 690                 size[isl_dim_param] = dim->nparam;
 691                 size[isl_dim_in] = dim->n_in;
 692                 size[isl_dim_out] = dim->n_out;
 693                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 694                         if (t != type) {
 695                                 get_ids(dim, t, 0, size[t], ids + off);
 696                                 off += size[t];
 697                         } else {
 698                                 get_ids(dim, t, 0, pos, ids + off);
 699                                 off += pos + n;
 700                                 get_ids(dim, t, pos, size[t] - pos, ids + off);
 701                                 off += size[t] - pos;
 702                         }
 703                 }
 704                 free(dim->ids);
 705                 dim->ids = ids;
 706                 dim->n_id = dim->nparam + dim->n_in + dim->n_out + n;
 707         }
 708         switch (type) {
 709         case isl_dim_param:     dim->nparam += n; break;
 710         case isl_dim_in:        dim->n_in += n; break;
 711         case isl_dim_out:       dim->n_out += n; break;
 712         default:                ;
 713         }
 714         dim = isl_space_reset(dim, type);
 715
 716         return dim;
 717 error:
 718         isl_space_free(dim);
 719         return NULL;
 720 }
 721
 722 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *dim,
 723         enum isl_dim_type dst_type, unsigned dst_pos,
 724         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 725 {
 726         int i;
 727
 728         if (!dim)
 729                 return NULL;
 730         if (n == 0)
 731                 return dim;
 732
 733         isl_assert(dim->ctx, src_pos + n <= isl_space_dim(dim, src_type),
 734                 goto error);
 735
 736         if (dst_type == src_type && dst_pos == src_pos)
 737                 return dim;
 738
 739         isl_assert(dim->ctx, dst_type != src_type, goto error);
 740
 741         dim = isl_space_reset(dim, src_type);
 742         dim = isl_space_reset(dim, dst_type);
 743
 744         dim = isl_space_cow(dim);
 745         if (!dim)
 746                 return NULL;
 747
 748         if (dim->ids) {
 749                 isl_id **ids;
 750                 enum isl_dim_type t;
 751                 int off;
 752                 int s[3];
 753                 int *size = s - isl_dim_param;
 754                 ids = isl_calloc_array(dim->ctx, isl_id *,
 755                                          dim->nparam + dim->n_in + dim->n_out);
 756                 if (!ids)
 757                         goto error;
 758                 off = 0;
 759                 size[isl_dim_param] = dim->nparam;
 760                 size[isl_dim_in] = dim->n_in;
 761                 size[isl_dim_out] = dim->n_out;
 762                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
 763                         if (t == dst_type) {
 764                                 get_ids(dim, t, 0, dst_pos, ids + off);
 765                                 off += dst_pos;
 766                                 get_ids(dim, src_type, src_pos, n, ids + off);
 767                                 off += n;
 768                                 get_ids(dim, t, dst_pos, size[t] - dst_pos,
 769                                                 ids + off);
 770                                 off += size[t] - dst_pos;
 771                         } else if (t == src_type) {
 772                                 get_ids(dim, t, 0, src_pos, ids + off);
 773                                 off += src_pos;
 774                                 get_ids(dim, t, src_pos + n,
 775                                             size[t] - src_pos - n, ids + off);
 776                                 off += size[t] - src_pos - n;
 777                         } else {
 778                                 get_ids(dim, t, 0, size[t], ids + off);
 779                                 off += size[t];
 780                         }
 781                 }
 782                 free(dim->ids);
 783                 dim->ids = ids;
 784                 dim->n_id = dim->nparam + dim->n_in + dim->n_out;
 785         }
 786
 787         switch (dst_type) {
 788         case isl_dim_param:     dim->nparam += n; break;
 789         case isl_dim_in:        dim->n_in += n; break;
 790         case isl_dim_out:       dim->n_out += n; break;
 791         default:                ;
 792         }
 793
 794         switch (src_type) {
 795         case isl_dim_param:     dim->nparam -= n; break;
 796         case isl_dim_in:        dim->n_in -= n; break;
 797         case isl_dim_out:       dim->n_out -= n; break;
 798         default:                ;
 799         }
 800
 801         if (dst_type != isl_dim_param && src_type != isl_dim_param)
 802                 return dim;
 803
 804         for (i = 0; i < 2; ++i) {
 805                 if (!dim->nested[i])
 806                         continue;
 807                 dim->nested[i] = isl_space_replace(dim->nested[i],
 808                                                  isl_dim_param, dim);
 809                 if (!dim->nested[i])
 810                         goto error;
 811         }
 812
 813         return dim;
 814 error:
 815         isl_space_free(dim);
 816         return NULL;
 817 }
 818
 819 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
 820         __isl_take isl_space *right)
 821 {
 822         isl_space *dim;
 823
 824         if (!left || !right)
 825                 goto error;
 826
 827         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 828                         goto error);
 829         isl_assert(left->ctx,
 830                 isl_space_tuple_match(left, isl_dim_out, right, isl_dim_in),
 831                 goto error);
 832
 833         dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
 834         if (!dim)
 835                 goto error;
 836
 837         dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
 838         dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
 839         dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
 840
 841         if (dim && left->tuple_id[0] &&
 842             !(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
 843                 goto error;
 844         if (dim && right->tuple_id[1] &&
 845             !(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
 846                 goto error;
 847         if (dim && left->nested[0] &&
 848             !(dim->nested[0] = isl_space_copy(left->nested[0])))
 849                 goto error;
 850         if (dim && right->nested[1] &&
 851             !(dim->nested[1] = isl_space_copy(right->nested[1])))
 852                 goto error;
 853
 854         isl_space_free(left);
 855         isl_space_free(right);
 856
 857         return dim;
 858 error:
 859         isl_space_free(left);
 860         isl_space_free(right);
 861         return NULL;
 862 }
 863
 864 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
 865         __isl_take isl_space *right)
 866 {
 867         isl_space *dom1, *dom2, *nest1, *nest2;
 868
 869         if (!left || !right)
 870                 goto error;
 871
 872         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 873                         goto error);
 874
 875         dom1 = isl_space_domain(isl_space_copy(left));
 876         dom2 = isl_space_domain(isl_space_copy(right));
 877         nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
 878
 879         dom1 = isl_space_range(left);
 880         dom2 = isl_space_range(right);
 881         nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
 882
 883         return isl_space_join(isl_space_reverse(nest1), nest2);
 884 error:
 885         isl_space_free(left);
 886         isl_space_free(right);
 887         return NULL;
 888 }
 889
 890 /* Given two spaces { A -> C } and { B -> C }, construct the space
 891  * { [A -> B] -> C }
 892  */
 893 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
 894         __isl_take isl_space *right)
 895 {
 896         isl_space *ran, *dom1, *dom2, *nest;
 897
 898         if (!left || !right)
 899                 goto error;
 900
 901         if (!match(left, isl_dim_param, right, isl_dim_param))
 902                 isl_die(left->ctx, isl_error_invalid,
 903                         "parameters need to match", goto error);
 904         if (!isl_space_tuple_match(left, isl_dim_out, right, isl_dim_out))
 905                 isl_die(left->ctx, isl_error_invalid,
 906                         "ranges need to match", goto error);
 907
 908         ran = isl_space_range(isl_space_copy(left));
 909
 910         dom1 = isl_space_domain(left);
 911         dom2 = isl_space_domain(right);
 912         nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
 913
 914         return isl_space_join(isl_space_reverse(nest), ran);
 915 error:
 916         isl_space_free(left);
 917         isl_space_free(right);
 918         return NULL;
 919 }
 920
 921 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
 922         __isl_take isl_space *right)
 923 {
 924         isl_space *dom, *ran1, *ran2, *nest;
 925
 926         if (!left || !right)
 927                 goto error;
 928
 929         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
 930                         goto error);
 931         if (!isl_space_tuple_match(left, isl_dim_in, right, isl_dim_in))
 932                 isl_die(left->ctx, isl_error_invalid,
 933                         "domains need to match", goto error);
 934
 935         dom = isl_space_domain(isl_space_copy(left));
 936
 937         ran1 = isl_space_range(left);
 938         ran2 = isl_space_range(right);
 939         nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
 940
 941         return isl_space_join(isl_space_reverse(dom), nest);
 942 error:
 943         isl_space_free(left);
 944         isl_space_free(right);
 945         return NULL;
 946 }
 947
 948 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *dim)
 949 {
 950         isl_id **ids = NULL;
 951
 952         if (!dim)
 953                 return NULL;
 954         isl_assert(dim->ctx, dim->n_in == 0, goto error);
 955         if (dim->n_out == 0 && !isl_space_is_named_or_nested(dim, isl_dim_out))
 956                 return dim;
 957         dim = isl_space_cow(dim);
 958         if (!dim)
 959                 return NULL;
 960         if (dim->ids) {
 961                 ids = isl_calloc_array(dim->ctx, isl_id *,
 962                                         dim->nparam + dim->n_out + dim->n_out);
 963                 if (!ids)
 964                         goto error;
 965                 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
 966                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->nparam);
 967         }
 968         dim->n_in = dim->n_out;
 969         if (ids) {
 970                 free(dim->ids);
 971                 dim->ids = ids;
 972                 dim->n_id = dim->nparam + dim->n_out + dim->n_out;
 973                 dim = copy_ids(dim, isl_dim_out, 0, dim, isl_dim_in);
 974         }
 975         isl_id_free(dim->tuple_id[0]);
 976         dim->tuple_id[0] = isl_id_copy(dim->tuple_id[1]);
 977         isl_space_free(dim->nested[0]);
 978         dim->nested[0] = isl_space_copy(dim->nested[1]);
 979         return dim;
 980 error:
 981         isl_space_free(dim);
 982         return NULL;
 983 }
 984
 985 static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
 986         enum isl_dim_type type,
 987         unsigned first, unsigned n, __isl_take isl_id **ids)
 988 {
 989         int i;
 990
 991         for (i = 0; i < n ; ++i)
 992                 dim = set_id(dim, type, first + i, ids[i]);
 993
 994         return dim;
 995 }
 996
 997 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim)
 998 {
 999         unsigned t;
1000         isl_space *nested;
1001         isl_id **ids = NULL;
1002         isl_id *id;
1003
1004         if (!dim)
1005                 return NULL;
1006         if (match(dim, isl_dim_in, dim, isl_dim_out))
1007                 return dim;
1008
1009         dim = isl_space_cow(dim);
1010         if (!dim)
1011                 return NULL;
1012
1013         id = dim->tuple_id[0];
1014         dim->tuple_id[0] = dim->tuple_id[1];
1015         dim->tuple_id[1] = id;
1016
1017         nested = dim->nested[0];
1018         dim->nested[0] = dim->nested[1];
1019         dim->nested[1] = nested;
1020
1021         if (dim->ids) {
1022                 ids = isl_alloc_array(dim->ctx, isl_id *,
1023                                         dim->n_in + dim->n_out);
1024                 if (!ids)
1025                         goto error;
1026                 get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
1027                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
1028         }
1029
1030         t = dim->n_in;
1031         dim->n_in = dim->n_out;
1032         dim->n_out = t;
1033
1034         if (dim->ids) {
1035                 dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
1036                 dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
1037                 free(ids);
1038         }
1039
1040         return dim;
1041 error:
1042         free(ids);
1043         isl_space_free(dim);
1044         return NULL;
1045 }
1046
1047 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim,
1048         enum isl_dim_type type, unsigned first, unsigned num)
1049 {
1050         int i;
1051
1052         if (!dim)
1053                 return NULL;
1054
1055         if (num == 0)
1056                 return isl_space_reset(dim, type);
1057
1058         if (!valid_dim_type(type))
1059                 isl_die(dim->ctx, isl_error_invalid,
1060                         "cannot drop dimensions of specified type", goto error);
1061
1062         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
1063         dim = isl_space_cow(dim);
1064         if (!dim)
1065                 goto error;
1066         if (dim->ids) {
1067                 dim = extend_ids(dim);
1068                 if (!dim)
1069                         goto error;
1070                 for (i = 0; i < num; ++i)
1071                         isl_id_free(get_id(dim, type, first + i));
1072                 for (i = first+num; i < n(dim, type); ++i)
1073                         set_id(dim, type, i - num, get_id(dim, type, i));
1074                 switch (type) {
1075                 case isl_dim_param:
1076                         get_ids(dim, isl_dim_in, 0, dim->n_in,
1077                                 dim->ids + offset(dim, isl_dim_in) - num);
1078                 case isl_dim_in:
1079                         get_ids(dim, isl_dim_out, 0, dim->n_out,
1080                                 dim->ids + offset(dim, isl_dim_out) - num);
1081                 default:
1082                         ;
1083                 }
1084                 dim->n_id -= num;
1085         }
1086         switch (type) {
1087         case isl_dim_param:     dim->nparam -= num; break;
1088         case isl_dim_in:        dim->n_in -= num; break;
1089         case isl_dim_out:       dim->n_out -= num; break;
1090         default:                ;
1091         }
1092         dim = isl_space_reset(dim, type);
1093         if (type == isl_dim_param) {
1094                 if (dim && dim->nested[0] &&
1095                     !(dim->nested[0] = isl_space_drop_dims(dim->nested[0],
1096                                                     isl_dim_param, first, num)))
1097                         goto error;
1098                 if (dim && dim->nested[1] &&
1099                     !(dim->nested[1] = isl_space_drop_dims(dim->nested[1],
1100                                                     isl_dim_param, first, num)))
1101                         goto error;
1102         }
1103         return dim;
1104 error:
1105         isl_space_free(dim);
1106         return NULL;
1107 }
1108
1109 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1110                 unsigned first, unsigned n)
1111 {
1112         if (!dim)
1113                 return NULL;
1114         return isl_space_drop_dims(dim, isl_dim_in, first, n);
1115 }
1116
1117 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1118                 unsigned first, unsigned n)
1119 {
1120         if (!dim)
1121                 return NULL;
1122         return isl_space_drop_dims(dim, isl_dim_out, first, n);
1123 }
1124
1125 __isl_give isl_space *isl_space_domain(__isl_take isl_space *dim)
1126 {
1127         if (!dim)
1128                 return NULL;
1129         dim = isl_space_drop_outputs(dim, 0, dim->n_out);
1130         return isl_space_reverse(dim);
1131 }
1132
1133 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim)
1134 {
1135         return isl_space_reverse(dim);
1136 }
1137
1138 __isl_give isl_space *isl_space_range(__isl_take isl_space *dim)
1139 {
1140         if (!dim)
1141                 return NULL;
1142         return isl_space_drop_inputs(dim, 0, dim->n_in);
1143 }
1144
1145 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim)
1146 {
1147         return dim;
1148 }
1149
1150 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1151 {
1152         space = isl_space_drop_dims(space,
1153                             isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1154         space = isl_space_drop_dims(space,
1155                             isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1156         return space;
1157 }
1158
1159 __isl_give isl_space *isl_space_as_set_space(__isl_take isl_space *dim)
1160 {
1161         dim = isl_space_cow(dim);
1162         if (!dim)
1163                 return NULL;
1164
1165         dim->n_out += dim->n_in;
1166         dim->n_in = 0;
1167         dim = isl_space_reset(dim, isl_dim_in);
1168         dim = isl_space_reset(dim, isl_dim_out);
1169
1170         return dim;
1171 }
1172
1173 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim,
1174         unsigned n_div)
1175 {
1176         int i;
1177
1178         if (!dim)
1179                 return NULL;
1180         if (n_div == 0 &&
1181             dim->nparam == 0 && dim->n_in == 0 && dim->n_id == 0)
1182                 return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out);
1183         dim = isl_space_cow(dim);
1184         if (!dim)
1185                 return NULL;
1186         dim->n_out += dim->nparam + dim->n_in + n_div;
1187         dim->nparam = 0;
1188         dim->n_in = 0;
1189
1190         for (i = 0; i < dim->n_id; ++i)
1191                 isl_id_free(get_id(dim, isl_dim_out, i));
1192         dim->n_id = 0;
1193         dim = isl_space_reset(dim, isl_dim_in);
1194         dim = isl_space_reset(dim, isl_dim_out);
1195
1196         return dim;
1197 }
1198
1199 int isl_space_is_equal(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2)
1200 {
1201         if (!dim1 || !dim2)
1202                 return -1;
1203         if (dim1 == dim2)
1204                 return 1;
1205         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1206                isl_space_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1207                isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1208 }
1209
1210 int isl_space_compatible(__isl_keep isl_space *dim1,
1211         __isl_keep isl_space *dim2)
1212 {
1213         return dim1->nparam == dim2->nparam &&
1214                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1215 }
1216
1217 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_space *dim)
1218 {
1219         int i;
1220         isl_id *id;
1221
1222         if (!dim)
1223                 return hash;
1224
1225         hash = isl_hash_builtin(hash, dim->nparam);
1226         hash = isl_hash_builtin(hash, dim->n_in);
1227         hash = isl_hash_builtin(hash, dim->n_out);
1228
1229         for (i = 0; i < dim->nparam; ++i) {
1230                 id = get_id(dim, isl_dim_param, i);
1231                 hash = isl_hash_id(hash, id);
1232         }
1233
1234         id = tuple_id(dim, isl_dim_in);
1235         hash = isl_hash_id(hash, id);
1236         id = tuple_id(dim, isl_dim_out);
1237         hash = isl_hash_id(hash, id);
1238
1239         hash = isl_hash_dim(hash, dim->nested[0]);
1240         hash = isl_hash_dim(hash, dim->nested[1]);
1241
1242         return hash;
1243 }
1244
1245 uint32_t isl_space_get_hash(__isl_keep isl_space *dim)
1246 {
1247         uint32_t hash;
1248
1249         if (!dim)
1250                 return 0;
1251
1252         hash = isl_hash_init();
1253         hash = isl_hash_dim(hash, dim);
1254
1255         return hash;
1256 }
1257
1258 int isl_space_is_wrapping(__isl_keep isl_space *dim)
1259 {
1260         if (!dim)
1261                 return -1;
1262
1263         if (dim->n_in != 0 || dim->tuple_id[0] || dim->nested[0])
1264                 return 0;
1265
1266         return dim->nested[1] != NULL;
1267 }
1268
1269 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim)
1270 {
1271         isl_space *wrap;
1272
1273         if (!dim)
1274                 return NULL;
1275
1276         wrap = isl_space_set_alloc(dim->ctx,
1277                                     dim->nparam, dim->n_in + dim->n_out);
1278
1279         wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
1280         wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
1281         wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1282
1283         if (!wrap)
1284                 goto error;
1285
1286         wrap->nested[1] = dim;
1287
1288         return wrap;
1289 error:
1290         isl_space_free(dim);
1291         return NULL;
1292 }
1293
1294 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim)
1295 {
1296         isl_space *unwrap;
1297
1298         if (!dim)
1299                 return NULL;
1300
1301         if (!isl_space_is_wrapping(dim))
1302                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1303                         goto error);
1304
1305         unwrap = isl_space_copy(dim->nested[1]);
1306         isl_space_free(dim);
1307
1308         return unwrap;
1309 error:
1310         isl_space_free(dim);
1311         return NULL;
1312 }
1313
1314 int isl_space_is_named_or_nested(__isl_keep isl_space *dim, enum isl_dim_type type)
1315 {
1316         if (type != isl_dim_in && type != isl_dim_out)
1317                 return 0;
1318         if (!dim)
1319                 return -1;
1320         if (dim->tuple_id[type - isl_dim_in])
1321                 return 1;
1322         if (dim->nested[type - isl_dim_in])
1323                 return 1;
1324         return 0;
1325 }
1326
1327 int isl_space_may_be_set(__isl_keep isl_space *dim)
1328 {
1329         if (!dim)
1330                 return -1;
1331         if (isl_space_dim(dim, isl_dim_in) != 0)
1332                 return 0;
1333         if (isl_space_is_named_or_nested(dim, isl_dim_in))
1334                 return 0;
1335         return 1;
1336 }
1337
1338 __isl_give isl_space *isl_space_reset(__isl_take isl_space *dim,
1339         enum isl_dim_type type)
1340 {
1341         if (!isl_space_is_named_or_nested(dim, type))
1342                 return dim;
1343
1344         dim = isl_space_cow(dim);
1345         if (!dim)
1346                 return NULL;
1347
1348         isl_id_free(dim->tuple_id[type - isl_dim_in]);
1349         dim->tuple_id[type - isl_dim_in] = NULL;
1350         isl_space_free(dim->nested[type - isl_dim_in]);
1351         dim->nested[type - isl_dim_in] = NULL;
1352
1353         return dim;
1354 }
1355
1356 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim)
1357 {
1358         if (!dim)
1359                 return NULL;
1360         if (!dim->nested[0] && !dim->nested[1])
1361                 return dim;
1362
1363         if (dim->nested[0])
1364                 dim = isl_space_reset(dim, isl_dim_in);
1365         if (dim && dim->nested[1])
1366                 dim = isl_space_reset(dim, isl_dim_out);
1367
1368         return dim;
1369 }
1370
1371 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *dim)
1372 {
1373         if (!dim)
1374                 return NULL;
1375         if (!dim->nested[0])
1376                 return dim;
1377
1378         return isl_space_reset(dim, isl_dim_in);
1379 }
1380
1381 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *dim)
1382 {
1383         if (!dim)
1384                 return NULL;
1385         if (!dim->nested[1])
1386                 return dim;
1387
1388         return isl_space_reset(dim, isl_dim_out);
1389 }
1390
1391 /* Replace the dimensions of the given type of dst by those of src.
1392  */
1393 __isl_give isl_space *isl_space_replace(__isl_take isl_space *dst,
1394         enum isl_dim_type type, __isl_keep isl_space *src)
1395 {
1396         dst = isl_space_cow(dst);
1397
1398         if (!dst || !src)
1399                 goto error;
1400
1401         dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
1402         dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
1403         dst = copy_ids(dst, type, 0, src, type);
1404
1405         if (dst && type == isl_dim_param) {
1406                 int i;
1407                 for (i = 0; i <= 1; ++i) {
1408                         if (!dst->nested[i])
1409                                 continue;
1410                         dst->nested[i] = isl_space_replace(dst->nested[i],
1411                                                          type, src);
1412                         if (!dst->nested[i])
1413                                 goto error;
1414                 }
1415         }
1416
1417         return dst;
1418 error:
1419         isl_space_free(dst);
1420         return NULL;
1421 }
1422
1423 /* Given a dimension specification "dim" of a set, create a dimension
1424  * specification for the lift of the set.  In particular, the result
1425  * is of the form [dim -> local[..]], with n_local variables in the
1426  * range of the wrapped map.
1427  */
1428 __isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local)
1429 {
1430         isl_space *local_dim;
1431
1432         if (!dim)
1433                 return NULL;
1434
1435         local_dim = isl_space_dup(dim);
1436         local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out);
1437         local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local);
1438         local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local");
1439         dim = isl_space_join(isl_space_from_domain(dim),
1440                             isl_space_from_range(local_dim));
1441         dim = isl_space_wrap(dim);
1442         dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted");
1443
1444         return dim;
1445 }
1446
1447 int isl_space_can_zip(__isl_keep isl_space *dim)
1448 {
1449         if (!dim)
1450                 return -1;
1451
1452         return dim->nested[0] && dim->nested[1];
1453 }
1454
1455 __isl_give isl_space *isl_space_zip(__isl_take isl_space *dim)
1456 {
1457         isl_space *dom, *ran;
1458         isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1459
1460         if (!isl_space_can_zip(dim))
1461                 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1462                         goto error);
1463
1464         if (!dim)
1465                 return 0;
1466         dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim)));
1467         ran = isl_space_unwrap(isl_space_range(dim));
1468         dom_dom = isl_space_domain(isl_space_copy(dom));
1469         dom_ran = isl_space_range(dom);
1470         ran_dom = isl_space_domain(isl_space_copy(ran));
1471         ran_ran = isl_space_range(ran);
1472         dom = isl_space_join(isl_space_from_domain(dom_dom),
1473                            isl_space_from_range(ran_dom));
1474         ran = isl_space_join(isl_space_from_domain(dom_ran),
1475                            isl_space_from_range(ran_ran));
1476         return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1477                             isl_space_from_range(isl_space_wrap(ran)));
1478 error:
1479         isl_space_free(dim);
1480         return NULL;
1481 }
1482
1483 int isl_space_has_named_params(__isl_keep isl_space *dim)
1484 {
1485         int i;
1486         unsigned off;
1487
1488         if (!dim)
1489                 return -1;
1490         if (dim->nparam == 0)
1491                 return 1;
1492         off = isl_space_offset(dim, isl_dim_param);
1493         if (off + dim->nparam > dim->n_id)
1494                 return 0;
1495         for (i = 0; i < dim->nparam; ++i)
1496                 if (!dim->ids[off + i])
1497                         return 0;
1498         return 1;
1499 }
1500
1501 /* Align the initial parameters of dim1 to match the order in dim2.
1502  */
1503 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1,
1504         __isl_take isl_space *dim2)
1505 {
1506         isl_reordering *exp;
1507
1508         if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2))
1509                 isl_die(isl_space_get_ctx(dim1), isl_error_invalid,
1510                         "parameter alignment requires named parameters",
1511                         goto error);
1512
1513         dim2 = isl_space_params(dim2);
1514         exp = isl_parameter_alignment_reordering(dim1, dim2);
1515         exp = isl_reordering_extend_space(exp, dim1);
1516         isl_space_free(dim2);
1517         if (!exp)
1518                 return NULL;
1519         dim1 = isl_space_copy(exp->dim);
1520         isl_reordering_free(exp);
1521         return dim1;
1522 error:
1523         isl_space_free(dim1);
1524         isl_space_free(dim2);
1525         return NULL;
1526 }