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