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